# 2021-22 MATH PRIZE PROBLEM #3

• Each month the Mathematics Department offers a math prize problem – a mathematical brain teaser – with a first prize of \$25, a second prize of \$15, and, of course, bragging rights. These problems do not require advanced knowledge of mathematics, just a curious mind and a willingness to slug it out with the problem.

## Find a set S of 6 integers with the following property: For any integer n in the range 1 ≤ n ≤ 60, there is a subset of integers in S whose sum is n.

Submit a solution to this problem to Prof. Ken Ching (kching@mmm.edu, CH 614) by March 23rd. The first correct submission will win a first prize of 25 dining dollars. All other correct submissions will receive recognition and bragging rights, and one of these submissions will be randomly selected for a second prize of 15 dining dollars. All are welcome to participate, but prizes are for MMC students only. Solution will be posted online and outside CH 603.

### Solution

The set S={1, 2, 4, 8, 16, 32} has the desired property. The set {1, 2} can generate the three numbers 1, 2, and 3 = 1 + 2. Adding 4 to the set will generate four more numbers: 4, 5 = 1 + 4, 6 = 2 + 4, and 7 = 1 + 2 + 4. Adding 8 to the set will generate eight more numbers: 8, 9,…, 15. Continuing in this manner shows S can generate all the integers from 1 to 63.