A Problem including Fibonacci numbers

I. Sharygin's problem

In a criminal state, the King made up his mind to fight against corruption. To start off, he decided to punish one of his 91 ministers as an example for others. So, he summoned the ministers to the palace, where they took places at a big round table. The first idea was to find the one who had the largest amount of money on his bank account and to proclaim him to be a criminal. The procedure of checking the amount of money in one's bank account takes 12 minutes. But the King wished to find the charged within two hours while he took medical treatment. According to the Main Court Administrator, any minister might be charged provided there were sufficient legal grounds. The Main Lawyer suggested the first minister found to have more money in his account than each of his two neighbours (on the left and on the right) should be proclaimed a criminal. Suggest a method that would enable them to be sure to find such a minister within the two allotted hours. (The allotted, time is enough to check the bank accounts of no more than 10 ministers. Assume that the amounts of money in the accounts are all distinct.)

Solution

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at alexb@cut-the-knot.com

Let's first think of the ministers as sitting on a bench, say along a wall, and identify each of them with the number of his seat. Let f(x) denote the amount of money in the x's bank account. An ordered (n < m < k) triple of ministers (n, m, k) is called suitable or an S-triple if f(n) < f(m) and f(k) < f(m). Let's finally define the size |(n, m, k)| of a triple (n, m, k) as |(n, m, k)| = k - n. The problem is equivalent to finding an S-triple of size 2.

The solution is based on two observation.

Assume for example that m - n > 1. Take any t between n and m. Then one of two things must happen. Either f(t) < f(m), or, f(t) > f(m). In the former case, (t, m, k) is suitable. In the latter case, f(t) > f(m) > f(n), hence (n, t, m) is suitable. In both cases, the size of the triple is obviously less than |(n, m, k)|. More than that, for any S-triple, there are |(n, m, k)| - 2 ways to reduce its size. Continuing in this manner we shall necessarily reach a solution.

But can we always find a suitable triple to start from? Yes, we can. Think again of the ministers as sitting by the round table. Pick any 3 - a, b, c - following a certain direction around the table. Of the three numbers f(a), f(b), f(c) one is the largest. To introduce an ordering of ministers start counting with a minister with a smaller amount and move toward the one with the largest bank account. As we'll see, this is not the best way to start the process but it does show that the problem is solvable at least in principle. There always exists an S-triple of size 2.

Now, let's relate to any S-triple (n, m, k) the set of gaps {m - n - 1, k - m - 1}. (For example, m - n - 1 is the number of ministers sitting between n and m.) The final S-triple is associated with {0, 0}. What could have been the corresponding set on the previous iteration? If we consider what's known as the worst case scenario, then the only possibility is {0, 1}. (No other combination might have assured {0, 0} on the next iteration. In the worst case scenario we can't depend on luck.) And on the iteration before that? {1, 2}. Going further backwards, we obtain the sequence {2, 4}, {4, 7}, {7, 12}, {12, 20}, {20, 33}, {33, 54}. (It's easy to see that the numbers thus obtained are 1 less than the Fibonacci numbers.) Each iteration takes looking into 1 bank account. Again counting backwards, we have

#Lookups	1	2	3	4	5	6	7	8	9
Gaps	{0, 0}	{0, 1}	{1, 2}	{2, 4}	{4, 7}	{7, 12}	{12, 20}	{20, 33}	{33, 54}

To obtain the starting triple we need 3 lookups. Therefore, we must start with {20, 33}. Let's choose ministers a, b and c such that the gap between a and b is 20 and the gap between b and c is 33. This will leave a big gap of 91 - 20 - 33 - 3 = 35 ministers between a and c. If we are lucky and f(b) is larger than either f(a) or f(c) the problem will be solved with exactly 10 lookups. What if we are not that lucky? Well, we have a problem here.

Had the gap between a and c been 33, we would have proceeded with picking up a minister d between a and c (opposite b) so as to obtain the sequence of gaps 12 · 20 · 33 · 20. One of the triples (d, a, b) or (b, c, d) would be suitable to run further iterations of which only 6 would be needed. The problem would thus have been solved, had the number of ministers by the table been 89! I wanted to talk about this with Sharygin.

I did not. On the other hand, I did have a reliable hint from the author of the problem that the Fibonacci numbers are somehow involved here. The solution seems to me too nice to be wrong. I therefore declare it correct and the problem wrong. The right problem should have started with 89 ministers instead of 91. Please correct me if I am wrong.