The king has a large collection of ministers, all of whom he believes to be corrupt. To teach them a lesson, he decides to behead the most corrupt minister. To do this, he wants the prime minister to conduct raids on all the ministers' houses and identify the most wealthy one. The most wealthy minister will be declared the most corrupt and beheaded.
There are 1,000,000 ministers and the king want the most corrupt minister to be identified in 200 days. The prime minister cannot raid raid all the ministers' houses within this time because he has only three raiding teams at his disposal and each team takes a full day to complete a raid. Thus he can raid only three ministers' houses each day.
Instead, the prime minister decides to adopt a different strategy. When the king meets the ministers, they all sit around a big table. The prime minister decides that it is sufficient to find one minister whose wealth is larger than that of his neighbours. The king can then be convinced that this minister is the most corrupt.
Devise a strategy for the prime minister to identify a minister whose wealth is higher than that of his neighbours, raiding one minister at one time.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky