I Hate Pranks

Computer Science Level 1

I have always hated my classmates pulling silly pranks on me. Yet, my entire class is full of them.

One of the pranksters in my class hid my notebook under someone's desk in my classroom.

Suppose that I find out who the prankster is that hid the notebook.

Then, if I pinpoint the desk he hid it under, he would say "Yes."
If I guess a wrong desk, he would just wink, without giving any further clues.
If I approach someone other than the prankster and try guessing, they would just wink as well.

Unfortunately, in fact, neither do I know whose desk it is under nor do I know who has hidden it.

Which best describes the number of questions that I'd need to ask in the worst case?

O(n)

O(n^2)

O(\lg n)

1 solution

Elliott J
Oct 15, 2016

Suppose that there are $k$ desks, m people, and that our question is "Is my notebook under this desk?".

Recall that if we ask anyone who isn't the prankster, they will just wink. So in order to discover that a particular person isn't the prankster we have to ask them our question for every desk.

Thus in the worst case scenario: out of all the people we could ask, we would ask the prankster last; and out of all the desks, we would ask the prankster about the correct desk last.

So the number of questions in the worst case scenario would be $m\times k$ .

Now, without the loss of generality (WLOG) $m < k$ , and $m^2 < k\times m < k^2$ .
So in any case we have $O(n^2)$ .

I Hate Pranks

1 solution

0 pending reports