Cylinder Lottery

A collection of cylinders are mixed in a large lottery-style mixing bowl. Each cylinder initially contains a single $100 note.

The goal of the contestant is to get all the money in all the cylinders in as few draws from the mixing bowl as possible. This would seem easy except that each time a cylinder is drawn randomly from the mixing bowl, whether or not $100 is found or removed after the cylinder top is unscrewed, the mixing bowl administrator (hereafter, the mixer) screws the cylinder together, returns it to the mixing bowl, and mixes all the cylinders together.

Warm-Up: Suppose there are two cylinders. What is the expected number of draws the contestant needs to get all the cash?

Solution to Warm-Up: The first draw gives the contestant one $100 note. In expectation, the contestant needs two more draws (1/(1/2)) to get the next note. So three draws altogether, in expectation.

Warm-Up: What is the expected number of draws if there are four cylinders?

Solution: 1 + (1/0.75) + (1/0.5) + (1/0.25), so around 8 1/3.

Now for the game. We give the contestant the ability to ask for k “cleanings.” In a cleaning, all empty cylinders are removed from the mixing bowl.

Question: Suppose there are initially four cylinders each having a $100. When should the contestant ask for a cleaning and what is the expected number of draws required?

Solution: When the contestant C draws the first cylinder, C will get $100 for sure. The contestant will get a second $100 note with an expected 1/0.75 additional draws. If the contestant asks for a cleaning after finding the second $100, then the situation is like the first Warm-Up for which the expected number of draws is 3. So, the overall expectation is 3 + 2 1/3 or approximately 5 1/3 draws.

Now, we can start to push this a bit more.

Question: Suppose there are 20 cylinders and the contestant may ask for one cleaning. When should that cleaning be and what is the expected number of draws needed? How does that compare with the case when there are no cleanings.

Solution: When there are no cleanings, the contestant would need approximately 68 1/2 draws. With a cleaning when there are five non-empty cylinders left, then the expected number of draws would be only about 37.

Question: Suppose there are 20 cylinders and the contestant may ask for two cleanings. When should those cleanings be and what is the expected number of draws needed?

Solution: The first cleaning should be when there are 10 cylinders left and the second when there are three. The expected number of draws is approximately 29.

Suppose the mixer is allowed a certain number of “refillings.” In a refilling, 1/2 of all empty cylinders that have been removed by cleaning are placed back in the mixing bowl. If there are an odd number of empty cylinders, say 2e+1, then the mixer refills with e. The mixer may do more than one refilling in a row if the refilling budget allows this. For example, if there are 21 empty cylinders that have been removed by cleaning, two refillings will place 10 + 5 cylinders back in the mixing bowl.

This gives us a game in which the contestant tries to obtain all the $100 notes in as few draws as possible and the mixer tries to make that number be as large as possible by strategically refilling.

Question: Consider again the situation in which we start with 20 cylinders each with $100. Suppose that the contestant is allowed one cleaning and the mixer one refilling. When should that cleaning be, when should the refilling be, and what is the expected number of draws needed assuming the mixer is rational?

Solution: The mixer should refill immediately after the contestant cleans. Given that, the contestant cleans later than without refilling: when there are only four non-empty cylinders left. The number of draws is much larger however. Instead of roughly 37 draws without refilling, around 52 are required.

Upstart: Given an initial number of cylinders N, if there are c cleanings and r refillings what is the strategy and what is the minimum expected number of draws the contestant can achieve regardless of when the mixer performs refillings. Hint: Dynamic programming may help.