Problem 59079. The Hacker Parole Problem

  • Created by Ray
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
Solve

Solution Stats

71.43% Correct | 28.57% Incorrect
Last Solution submitted on Oct 15, 2023

Solution Comments

Show comments

Problem Recent Solvers5

Suggested Problems

More from this Author3

Problem Tags

matrix manipulation

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!