Image via Wikipedia

A king has 100 identical servants, each with a different rank between 1 and 100. At the end of each day, each servant comes into the king's quarters, one-by-one, in a random order, and announces his rank to let the king know that he is done working for the day.For example, servant 14 comes in and says "Servant 14, reporting in."

One day, the king's aide comes in and tells the king that one of the servants is missing, though he isn't sure which one.

Before the other servants begin reporting in for the night, the king asks for a piece of paper to write on to help him figure out which servant is missing. Unfortunately, all that's available is a very small piece that can only hold one number at a time. The king is free to erase what he writes and write something new as many times as he likes, but he can only have one number written down at a time.

The king's memory is bad and he won't be able to remember all the exact numbers as the servants report in, so he must use the paper to help him.

How can he use the paper such that once the final servant has reported in, he'll know exactly which servant is missing?

If he adds the ranks as he goes, then the missing servant's rank will be 5050-(sum).

ReplyDeleteAlternatively he could write 5050 and subtract the ranks as they come so that the paper is left with the rank of the missing servant.

ReplyDeleteYou got it. I still think the King should be able to afford a notebook, though.

ReplyDeleteHe could also tell the servants to line up by rank and figure it out that way.

ReplyDelete