# I. Sharygin's Problem of Criminal Ministers

In a criminal state, the King made up his mind to fight against corruption, and in the beginning 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 seats around a big 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 Chief Court Administrator, any minister might be charged provided there were sufficient law grounds. The Chief Lawyer suggested to proclaim that minister criminal who would be the first found minister having more money in his account than each of his two neighbours (on the left and on the right). Suggest a method that would enable them to manage for sure to find a minister that matched the above conditions 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.)

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

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 *suitable* or *S-triple* if

The solution is based on two observation.

Assume for example that

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 *worst case scenario*, then the only possibility is *worst case scenario* we can't depend on luck.) And on the iteration before that? *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 |

To obtain the starting triple we need 3 lookups. Therefore, we must start with

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 *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! Something I wanted to talk about 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.

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny