Question number 20. A box contains 900 cards numbered from 100 to 999. Any two cards have different numbers. Francois picks some of the cards and determines the sum of the digits on each of them. At least how many cards must he pick in order to be certain to have three cards with the same sum? So what Francois is doing is studying the face value and the digit sum on each card. Let us do the same by assigning SN to stand for the number of cards with digit sum equal to N. So we see that S1 is equal to 1, the card with face value 100. S2 is equal to 3. We have three cards, face values 200, 110, 101. S3 is equal to 6. The face values are 300, 120, 102, and then 210, 201, 111. We can continue this list, but at some point we will see that the highest face value card must have the highest digit sum. So that's 999. Next to that we have the digit sum 26 obtained by decreasing the digits of 999 one at a time. S25 occurs six times, and so let's list these numbers. As face values 997, 979, 799, and then 988, 898, and 889. So it appears this list is increasing and then decreasing. We will not investigate that claim, but we will claim that SN is bigger than or equal to 3 for values running from N is equal to 2 to N is equal to 26. And so this is because of the remaining 880 face values. We have not considered the digits sum to anywhere between 4 and 24. So we have 20 more integers as digit sums and 880 cards to fit in between them. We can see that by the pigeonhole principle, it seems that at least each digit sum will occur three times if 20 of them have to somehow be split between 880 cards. Now the suggested solutions have a detailed proof of this fact that I don't really have the space here to discuss. So we'll just use the claim that the digit sums from 2 to 26 each repeat at least three times, and then choose as many cards as possible so that only two digit sums repeat at most. And so we do that by choosing the card with face value 100, the card with face value 999, and from face values with digit sums running from 2 all the way up to 26, we choose two cards each. So together, all together, we have 2 plus 2 times 25, 52 cards, and these do not repeat. Not face values, but digit sums more than twice. And that's the maximum number of repetitions for digit sums we will see. If we choose any of the digit sums that remain running from 2 to 26, we will guarantee to have at least three cards with the same digit sum. And so we would suggest to Francois to pick 53 cards to guarantee that at least three will have the same digit sum.

pigeonhole principle

digit sum

card selection

numbered cards

combinatorics