[10 pts] Consider a company with n > 0 workers. A worker is a famous-solo- worker...

 

Transcribed Image Text:

[10 pts] Consider a company with n > 0 workers. A worker is a famous-solo- worker if she or he is known by every other worker, but knows none of them. You are the boss and you want to check if there is a famous-solo-worker in your company. You are only allowed to ask the following question to a worker: "Do you know worker j?" The workers will answer your questions truthfully. Show that you can find the famous-solo-worker, or declare that such a worker doesn't exist, with at most 3(n-1) questions. Note that there can be at most one famous-solo-worker. [10 pts] Consider a company with n > 0 workers. A worker is a famous-solo- worker if she or he is known by every other worker, but knows none of them. You are the boss and you want to check if there is a famous-solo-worker in your company. You are only allowed to ask the following question to a worker: "Do you know worker j?" The workers will answer your questions truthfully. Show that you can find the famous-solo-worker, or declare that such a worker doesn't exist, with at most 3(n-1) questions. Note that there can be at most one famous-solo-worker.

Answer rating: 100% (QA)

We use the following algorithm Step 1 For every worker i ask worker i if ... View the full answer