Problem 59079. The Hacker Parole Problem
The hacker parole problem
100 hackers have been imprisoned, but have been given a way to get parole.
Each of the 100 prisoners has been given a number. There is also a room with 100 numbered boxes. Each box contains a number. Each prisoner goes into the room and has 50 tries to find their number in a box.
If all 100 prisoners can find their number within 50 tries, then they all get parole. But, if one prisoner cannot find their number within 50 tries all the hackers go back to prison for another year.
The hackers meet and devise an algorithm that has better than a 30 percent chance of going free that year.
The hacker's solution
It is obvious that having each prisoner randomly open boxes will fail. Each prisoner has a 0.5 chance of finding their number and so the chance that all 100 are able to do it is 0.5^100. Essentially giving a 0 probablility.
The hacker solution is to have each prisoner go into the room and use their number to find a box. They open the box, and if their number is in it they are done. If their number is not in it, then they use the number in the box to choose another box. They continue following the numbers and opening boxes until they find the box with their number on it.
This solution will free all the prisoners over 30% of the time. This is because the random numbers in boxes form loops. For example if we have five boxes and five number we might see this set of numbers stored in boxes.
The hacker holding number 3 would open box 3 and find a 4. Then the hacker would open box 4 and find a 1. Then the hacker would open box 1 and find a 3.
This solution works because numbers stored this way always form at least one loop. In this case we have the following loops:
3 -> 4 -> 1 -> 3
5 -> 2 -> 5
The hackers know that they will get their freedom if the longest loop among the 100 boxes is 50 boxes or shorter. This happens 30% of the time, thus they get their freedom 30% of the time.
Testing the solution
We want to test the hacker's algorithm by running 10,000 trials and seeing how often the hackers won their freedom. Math says that the number should be greater than or equal to 3000 times in 10,000 trials.
Your assignment is to write a function named runTrial() that takes a vector of boxes in the room and runs a trial of the hacker's algorithm. It returns whether the hackers found the number after looking at only half the boxes. The boxes are a vector that contains randomized numbers from 1:numBoxes.
The testbench will run your trial 10000 times and capture the number of times the hackers won their freedom. That number should be above 3000.
The function looks like this:
function foundAll = runTrial(numBoxes)
%% Insert your code here. I solved this problem in 11 lines inside the function
end
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers5
Suggested Problems
-
Sum all integers from 1 to 2^n
15320 Solvers
-
Create a square matrix of multiples
475 Solvers
-
Fahrenheit to Celsius converter
553 Solvers
-
792 Solvers
-
1118 Solvers
More from this Author3
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!