Digit sum


Prereqs:

Show students this puzzle after they've seen the divisibility rules for \(3\) and \(9,\) as this motivates the idea of defining the digit sum of a number.


Definition:

The digit sum is obtained by adding together all the digits of a number. For example, the digit sum of \(941\) is \(9 + 4 + 1 = 15.\)


Problem:

Partition the numbers \(0,\,1,\,2,\ldots,\,123456,\) into two sets in the following way. In the first set, place all numbers whose digit sum is even, and in the second set, place all numbers whose digit sum is odd. Are there more numbers in the first set than there are in the second set?


Solution:

Every even number, from \(0\) to \(123456,\) except \(123456,\) can be paired with an odd number. Each even number differs by one in the sum of its digits from the odd number it's paired with. The sum of the digits of \(123456\) is \(21.\) so there is one more number with an odd digit sum than there are with even digit sums.


Going further:

Partition the numbers \(0,\,1,\,2,\ldots,\,n,\) instead of \(0,\,1,\,2,\ldots,\,123456.\)


Source:

The problem and solution were adapted from "The Inquisitive Problem Solver," problem 23, part b.