Brain Teasers
Sum of Threes
The
number 4 can be expressed as the sum of three positive integers in only one way:
4 = 1 + 1 + 2
However,
the number 50 can be expressed as the sum of three positive integers in 200
ways.
Somewhere
in between, there is a number n that
can be expressed as the sum of three positive integers in precisely n ways. Can you find n?
This brainteaser was
written by Derrick Niederman.
Solution:
12.
A partition is a
way of writing an integer as a sum of smaller integers. For instance, 4 + 5 + 6
is a partition of 15, and 11 + 10 + 9 + 7 + 2 is a partition of 39.
This problem is concerned with partitions that contain just three addends.
There is only one partition of 3 that contains three
addends, namely, 1 + 1 + 1. The trick to this puzzle is realizing that, as the
integer increases, the number of partitions either increases or stays the same.
For example, there is only one partition of 4 with three addends, 1 + 1 +
2, so the number of partitions stayed the same as the integer increased
from 3 to 4. However, there are two partitions of 5 that contain
three addends, 1 + 2 + 2
and 1 + 3 + 1, so there are more partitions for 5 than
there are for 4.
This
is helpful, because it means we can limit the number of integers we have to
check. Knowing that 3 has only one partition and that 50 has 200, we would
suspect that the number we are looking for would be closer to 3 than
to 50. So, take an educated guess and try 15. As it turns out, there
are 19 partitions of 15 that contain three addends (you can create a
list to prove this to yourself). That’s too high, since 19 > 15. Searching
lower, we might then check 10, which we’d find has just 7 partitions.
That’s too low, since 7 < 10.
This
now significantly limits the range we have to check, and a little more fiddling
will lead to the solution. Below are the twelve partitions of 12 with
three addends:
1 + 1 + 10 1 + 2 + 9 1
+ 3 + 8 1 + 4 + 7
1 + 5 + 6 2 + 2 + 8 2 + 3 + 7 2
+ 4 + 6
2 + 5 + 5 3 + 3 + 6 3 + 4 + 5 4
+ 4 + 4
More Brain Teasers
