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.)

Solution

Fibonacci Numbers

  1. Ceva's Theorem: A Matter of Appreciation
  2. When the Counting Gets Tough, the Tough Count on Mathematics
  3. I. Sharygin's Problem of Criminal Ministers
  4. Single Pile Games
  5. Take-Away Games
  6. Number 8 Is Interesting
  7. Curry's Paradox
  8. A Problem in Checker-Jumping
  9. Fibonacci's Quickies
  10. Fibonacci Numbers in Equilateral Triangle
  11. Binet's Formula by Inducion
  12. Binet's Formula via Generating Functions
  13. Generating Functions from Recurrences
  14. Cassini's Identity
  15. Fibonacci Idendtities with Matrices
  16. GCD of Fibonacci Numbers
  17. Binet's Formula with Cosines
  18. Lame's Theorem - First Application of Fibonacci Numbers

|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 (n < m < k) triple of ministers (n, m, k) is called suitable or 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 the two. 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 case, 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

#Lookups123456789
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! 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.


Related material
Read more...

Worst-Case Scenario

  • One Dimensional Ants
  • More than half of the integers from {1, 2, ..., 2n}
  • Chvatal's Art Gallery Theorem
  • Mastermind: an interactive gizmo

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

    Copyright © 1996-2018 Alexander Bogomolny

    71546610