The Hardest Prisoner Problem Ever (Part 3)

Logic Level 4

Do not attempt this problem until you have solved
The Hardest Prisoner Problem Ever (Part 1) and
The Hardest Prisoner Problem Ever (Part 2) .

This problem is the same as Part 1 except:

  • you have 8 switches in the room instead of 1
  • you have on the order of 1,000,000,000,000,000,000,000,000 ( 1 0 24 10^{24} prisoners aka a yotta-prisoner) prisoners instead of 6.
  • your goal now is to find an algorithm that will win as quickly as possible.

Assuming that the prisoners use the fastest possible strategy, approximately how long will the game take as a function of the number of prisoners, n n ? (i.e. what is O(fastest strategy)?)

n n n 3 n^3 ln ( n ) \ln(n) n ln ( n ) n\ln(n) n ( ln ( n ) ) 2 n (\ln (n))^2 n 2 n^2

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

I guessed, wow i'm smart!

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...