Grigori Perelman’s Puzzle
Have you heard of Grigori Perelman? If you like math, you probably have. He is one of the most renowned mathematicians in the world. I recently got a book on the Leningrad Mathematical Olympiads (scheduled for publication in English in 2025) and found Grigori’s name there. He authored one of the Olympiad problems from 1984. For context, he was born in 1966. Here it is.
Puzzle. You are given ten numbers: one “1” and nine “0”s. You are allowed to replace any two numbers with their arithmetic mean. What is the smallest number that can appear in place of the “1” after a series of such operations?
Share:
Andrew:
Is it 2^-9? You can average the “1” slot with each of the zeroes once, diminishing it by 1/2 each time. After that, all of the values are greater than or equal to the “1” slot so you can’t proceed any further.
I don’t think averaging any of the other values is helpful at any time, since it either involves averaging two values that are both bigger than the “1” slot (which does nothing), or it destroys a zero (which is counterproductive).
11 September 2024, 8:52 amBen Orlin:
Ah, I originally misread this as imagining that a and b are replaced with the single number (a+b)/2, shrinking the size of the set each time you act, in which case the 2^-9 answer is even more clearly correct!
But I wonder if the intended problem involves the additional constraints that you may only average *adjacent* numbers. E.g., after one step you could have 0.5 0.5 0 0 0 0 0 0 0 0, and after two steps you could have 0.5 0.25 0.25 0 0 0 0 0 0 0.
In this case, it seems we shall approach 0.1 in the limit, but giving a closed formula for the leading value after n steps is not so obvious!
11 September 2024, 12:48 pmtanyakh:
Yes, Andrew, I believe this is the intended solution.
And Ben, your variation is interesting.
11 September 2024, 12:52 pmzielaj:
Here’s a sketch of a proof that 2^-9 is the best possible. This proof is somewhat tedious, so I hope there’s a simpler solution.
Let’s flip 0s and 1s, so that we have one 0 and n = 9 1s, and the goal is to make the 0 bucket as high as possible. It’s convenient to think of the numbers as temperatures, and the averaging operations as heat exchange.
At any point in time, let a_1 >= … >= a_n be the temperatures of the “1” buckets, and b be the temperature of the “0” bucket. Let k be such that a_k >= b >= a_{k+1}.
By mixing b with a_k, then a_{k-1}, then a_{k-2}, etc, (the strategy described in previous comments) we can raise the temperature of b to T* = b / 2^k + \Sum_{i=1}^k a_k / 2^k.
A case-by-case analysis (examples below) should show that no moves can ever increase T*, so the strategy from the previous comments is the best we can do (I haven’t really done all the cases, but I think this approach should work). For example:
– Moving epsilon heat from a_k to b keeps T* constant.
– Moving epsilon heat from a_i to a_j (i <= j <= k) reduces T*.
– Moving epsilon heat from a_i to b (i <= k) reduces T*.
– Moving epsilon heat from b to a_i (k < i) reduces T*.
– Etc.
Finally, note that a given state can have multiple values of k, but T* is still well-defined. For example, if a_j = b, both j and j – 1 are possible values for k. However, T* has the same value:
T*_{k=j} = b / 2^j + \Sum_{i=1}^j a_i / 2^i = b / 2^j + a_j / 2^j + \Sum_{i=1}^{j-1} a_i / 2^i = b / 2^{j-1} + \Sum_{i=1}^{j-1} a_i / 2^i = T*_{k=j-1}.
16 September 2024, 9:47 amzielaj:
There’s a typo in my previous comment, the definition of T* should have been: T* = b / 2^k + \Sum_{i=1}^k a_i / 2^i. (the index inside of the sum is i, not k), sorry.
16 September 2024, 9:49 am