- An amateur photographer is enjoying a parade when he discovers he has only one picture left on his roll of film (and of course has no more film.) He knows there are four more floats in the parade and he wants to maximize his chances of making his last picture be of the best float. What should he do?
- What if there are 5 floats remaining?
- 6 floats?
- 10 floats?
- 100 floats?
- N floats?

[After a few responses, I'd like to add: There is not meant to be a trick to the picture taking. The picture may only include one float, and after a float has passed by, its picture may not be taken.]

Source: Extended from puzzles from Michael Winckler, Brendan Voge, and rec.puzzles.

Igor Volkov sent a solution on 12/23/97. I think it aptly shows the best method is to wait for N/e floats to pass by, then take a picture of the next best float. For two pictures, wait for about .284N floats, then take pictures of the next two best floats. His solution is included here. My simulation results for small N follows that.

Hello, Ken: May I propose the solution for "The Best Picture"? We have no information about the best float a priori. The only thing we know is the number of floats N. So we can look through the first F floats (without making the picture) and find out the best among them (denote the best float as B). Then using the gathered information we make the picture of the first float that more beautiful than B. If there is no such float we do nothing. Let's find the value of F in order to maximize the probability of success. Surely we can summarize the series and get cumbersome expressions. But there is simpler way (that gives approximate result). Let's suppose that the sequence of N floats is represented by segment [0,1] (we will consider "continuous" distribution of floats on the segment and associate the floating point number of segment [0,1] and the float in the parade). Suppose that number b corresponds to float B, x corresponds to the best float X. We like to find the real number f that maximizes the probability of case "float x is in [f, 1] and there are no floats in the sequence between B and X that more beautiful than B". We can find this probability considering the following cases: probability a) The second of the most beautiful floats is in [0, f] f b) The second beautiful float is in [x, 1] and the third is in [0, f] f(1-x) c) The second and the third beautiful floats is in [x, 1] and the fourth is in [0, f] f(1-x)^2 etc. Find the probability of case "the most beautiful float is x": P=f+f(1-x)+ f(1-x)^2+...=f/x and find the probability of case "x in [f, 1]": p(f)=integral_f^1 f/x dx = f ln(1/f). We get p(f)=max=1/e if f=1/e as p'(f)=ln(1/f)-1. Suppose that photographer has 2 pictures. We can consider the following scheme: We look through the first F floats, and find B - the best of floats. Consider the "tail" of the sequence and make the picture of the first float X that more beautiful than B and then photo Y - the first float that either more beautiful than X or more beautiful than B among the rest floats. Suppose that X and Y are two the most beautiful floats in the parade. Let's find f - the number corresponds to F. We should consider the cases probability a) The third of most beautiful floats is in [0, f] f b) The third of most beautiful floats is in [y, 1] and the fourth is in [0, f] f(1-y) c) The third and the fourth of the most beautiful floats is in [y, 1] and the fifth is in [0, f] f(1-y)^2 etc. The probability of the case "x and y are the best floats" is p=f+f(1-y)+f(1-y)^2+...=f/y and so as f<=x<=y<=1 we have p(f)=integral_f^1 (integral_f^y f/y dx) dy = f(1-f)+f^2 ln(f.) p'(f)=1-f+2f ln(f) p'(f)=0 and p(f)=max <=> f=0.2846681369 approximately. Finally p(f)=0.1 approximately. Igor Volkov. PS: Sorry for my broken English.

I made a quick simulation to exhaust all options for small N and my results are below. A quick solution to N = 4 is at Michael Winckler's solution site. An answer for N, without explanation can be found in the rec.puzzles solutions. Apparently, the best choice for X is roughly N/e.

My results for small N. The numbers represent X, # times N is found, % N is found.

N | Possible Orders of Floats | X, N, % | X, N, % | X, N, % | Best X | ||||

3 | 0, 2, .33 | 1, 3, .5 | 2, 2, .33 | 1 | |||||

4 | 0, 6, .25 | 1, 11, .46 | 2, 10, .42 | 1 | |||||

5 | 1, 50, .42 | 2, 52, .43 | 3, 42, .35 | 2 | |||||

6 | 1, 274, .38 | 2, 308, .43 | 3, 282, .39 | 2 | |||||

7 | 1, 1764, .35 | 2, 2088, .414 | 3, 2052, .407 | 2 | |||||

8 | 2, 16056, .40 | 3, 16524, .41 | 4, 15312, .38 | 3 | |||||

9 | 2, 138528, .38 | 3, 147312, .406 | 4, 142656, .39 | 3 |

Mail to Ken