Kate and N dwarfs are playing a dwarf guessing game. In the beginning there are five empty boxes numbered with the numbers 1, 2, 3, 4 and 5. According to the rules of the game, Kate places at least 1 and at most 9 marbles in each box such that the number of marbles in box n for each n <m is not more than the number of marbles in box m. Not knowing how many marbles are in which box, each of the N dwarfs makes a separate guess for each box with numbers 1, 2, 3, 4, and 5. Accordingly, N dwarf estimates 5N in total. No matter how Kate puts the balls, what would N be at least if N dwarves agree to ensure that at least one of these 5N guesses is correct?
I can get it down to
The strategy would be
- The first dwarf guesses 1,3,5,7,9
- The second dwarf guesses 2,4,6,8,9
This works because there are no non-decreasing sequences that do not hit one of these guesses somewhere. For example, to avoid these guesses, the first box would need to be at least 3 (1 and 2 are guessed). Then the second box would need to be at least 5 (at least 3, but 3 and 4 are guessed). Then the third would need to be at least 7, the fourth would need to be at least 9, and thus there is no possible number for the fifth box that avoids being guessed.