Ask The Wizard #369
Solve for x:
9x + 12x = 16x
Here is my solution (PDF).
This problem was asked and discussed in my forum at Wizard of Odds.
This problem was inspired by the video A Difficult Exponential Question.
Find a ten-digit number such that:
- The first digit of the number is the number of 0's in the entire number.
- The second digit of the number is the number of 1's in the entire number.
- The third digit of the number is the number of 2's in the entire number.
- The 4th digit of the number is the number of 3's in the entire number.
- The 5th digit of the number is the number of 4's in the entire number.
- The 6th digit of the number is the number of 5's in the entire number.
- The 7th digit of the number is the number of 6's in the entire number.
- The 8th digit of the number is the number of 7's in the entire number.
- The 9th digit of the number is the number of 8's in the entire number.
- The 10th digit of the number is the number of 9's in the entire number.
This question is asked and discussed in my forum at Wizard of Vegas.
An evil warden gets together 100 prisoners and gives each a unique number from 1 to 100.
Inside another room are 100 numbered boxes. The warden takes pieces of paper, numbered 1 to 100, and randomly places them in the boxes, one piece per box.
The next day, the prisoners will be allowed into the boxes room one at a time. Each prisoner may open 50 boxes. If a prisoner finds his own number (for example prisoner 23 finds the box containing the numbers 23) then he will be "successful" and may leave early if he finds it before the 50th opening. Exits are made through a separate door than the entrance. Prisoners who have not had their turn yet, will not know the outcome of any previous prisoners.
If all 100 prisoners are successful, they will all be set free. However, if one or more are unsuccessful, then they are all immediately put to death.
The prisoners are allowed a day together to strategize. Once the first prisoner enters the boxes room, no further communication is allowed. Examples of communication include, but are not limited to, moving the papers around and leaving the lids open. If any communication is detected, all prisoners will be put to death immediately.
What strategy will maximize their probability of being set free?
The general idea is if at least one prisoners fail, then lots of them may as well fail, as the ultimate outcome of death for everyone is still the same. So, a good strategy would maximize the probability of everybody's success at the expense of a high probability of many failures as well.
Consider a strategy where the player opens any box. He then reads the number on the paper in it and then opens that box second. He then reads the paper in that second box and opens the box with that number third. If he keeps repeating this process, he will eventually be lead back to the box he started with.
If the player follows this strategy and his own number is somewhere in that loop of numbers, then he will obviously eventually find, assuming no limit on boxes he may open.
To ensure the player always eventually finds his number, he can start with his own number. That way, he will eventually come back to it, although it could take anywhere from 1 to 100 box openings.
A set of boxes where this strategy eventually leads back to the first box is called a closed loop. The number of boxes in a closed loop is the size of the loop.
The key to this problem is every prisoner will be successful if there is no closed loop greater than size 50.
If there is a closed loop of 100, the prisoners will fail. What is that probability? There is a 99/100 probability the first box does NOT lead to itself. If it doesn't lead to itself, there is a 98/99 probability the second box does not lead to the original number. If that box doesn't lead to itself, then there is a 97/98 probability the next box does not lead to itself. Extending this logic, there is a (99/100)*(98/99)*(97/88)*...*(3/4)*(2/3)*(1/2) = 1/100 probability there is a closed loop of size 100.
What about a closed loop of 99? With a closed loop of 99, there would be another closed loop of 1. That closed loop of one could be any of the 100 boxes. For any one box, there is a 1/100 chance it leads to itself. For the other 99, there is a 1/99 chance they form a closed loop, by the logic above for a closed loop of 100. So, the probability of a closed loop of 99 is 100 × (1/100) & (1/99) = 1/99.
What about a closed loop of 98? With a closed loop of 98, there would be another two boxes that would lead to each other somehow, either two closed loops of one or one closed loop of two. That closed loop of one could be any of the 100 boxes. For any one box, there is a 1/100 chance it leads to itself. For the other 99, there is a 1/99 chance they form a closed loop, by the logic above for a closed loop of 100. So, the probability of a closed loop of 99 is 100 × (1/100) × (1/99) = 1/99.
What about a closed loop of 98? With a closed loop of 98, there would be another two boxes that would lead to each other somehow, either two closed loops of one or one closed loop of two. There are combin(100,2)=4,950 ways to choose two boxes out of 100. Once two are chosen, the probability those two boxes have the papers inside matching their box numbers, in any configuration, is (2/100)*(1/99) = 1 in 4,950. Then the probability the other 98 form a closed loop is 1/98. So, the probability of a closed loop of 98 is (4950)*(1/4950)*(1/98) = 1/98.
We can keep following this logic down to a closed loop of 51 having a probability of 1/51.
The probability of failure is pr(closed loop of 100) + pr(closed loop of 99) + pr(closed loop of 98) + ... + pr(closed loop of 51) = 1/100 + 1/99 + 1/98 + 1/97 + ... + 1/51 =~ 0.6881721793.
If the probability of failure is 0.688172179, then probability of success is 1 - 0.6881721793 =~ 0.3118278207.
This question is asked and discussed in my forum at Wizard of Vegas.
This question was inspired by this Veritasium video.
Your office of 100 workers does a Secret Santa gift exchange. This where you write down everybody's name on individual pieces of paper, put them all in a hat, and everybody draws a name at random to give a gift to.
The question is, how many closed loops will there be, on average?
Example of a closed loop of size 4: Gordon gives to Don, Don gives to Jon, Jon who gives to Nathan, and Nathan gives to Gordon.
Drawing your own name would be a closed loop of size 1.
Suppose there is just one employee who comes to the Secret Santa party. Obviously he will pick himself, so one closed loop.
Then a second employee arrives late and asks to join. They give her a list of the now two employees. There is a 1/2 chance she picks employee 1 and 1/2 herself. If she picks employee 1, then she can be squeezed into his loop, where she buys for employee 1 and he buys for her. So, now we're at 1 + 0.5*1 = 1.5
Then a third employee arrives late and asks to join. They give her a list of the now 3 employees. There is a 2/3 chance she picks employee 1 or 2 and 1/3 herself. If she picks employee 1 or 2, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 3. So, now we're at 1.5 + (1/3) = 11/6.
Then a fourth employee arrives late and asks to join. They give her a list of the now 4 employees. There is a 3/4 chance she picks employee 1 to 3 and 1/4 herself. If she picks employee 1 to 3, then she can be squeezed into their loop, where she buys for employee she picks and the one who formally was supposed to buy for that employee now buys for 4. So, now we're at 11/6 + (1/4) = 25/12.
Keep doing this and the final answer is 1/1 + 1/2 + 1/3 + ... + 1/100 =~ 5.187377518.
This question is asked and discussed in my forum at Wizard of Vegas.