Question

A computer program is randomly fed three-digit numbers between 000 and 999 and executes the command immediately after it has been fed 4 three-digit numbers with same sum of digits.

Using pigeon-hole principle, find the minimum number of three-digit numbers to be fed to the computer program to guarantee that the command is executed?

Solution

==================================================================================================

There are 1000 numbers between 000 & 999 including the upper and lower boundaries.

Using these numbers, the minimum sum using a 3-digit number can be obtained using 000 (0+0+0 = 0). The maximum sum using a 3-digit number can be obtained using 999 (9+9+9 = 27). All other 3 digit strings using 0-9 digits can be obtained by toggling the digits in the different positions (001, 026, 237, etc.).

Now, let’s start counting!

• Thus, a total of 28 different sums are possible.
• In a worst-case scenario, every sum will come up one after another in the first three rounds.
• Thus, number of digits that can come up in the first three rounds in the worst-case scenario is 28 * 3 = 84.
• We can consider the 28 sums as the different boxes in the pigeonhole principle.
• At this point, each of the box has 3 numbers each.
• Any random number chosen at draw will add a fourth number to any one of the 28 boxes.
• This satisfies the criteria and the code will execute.

Thus, minimum number of 3-digit numbers required to guarantee the execution of the code is 84 + 1 = 85 numbers.