----------------------------------
You can build all whole numbers from 1 to 6 using single addition or subtraction from just two numbers, 2 and 3.1 = 3 - 2 | 2 = 2 (no operation is needed) |
3 = 3 (no op.) | 4 = 2 + 2 |
5 = 2 + 3 | 6 = 3 + 3 |
Task.
-----
Find the smallest number k, such that all whole numbers from 1 to 16 can be build by single addition or subtraction from them. Display one list k such numbers.Solution.
----------
(1) The following 4 numbers allow you to construct all whole numbers from 1 to 16: 3, 6, 7, 8.
1 = 7 - 6 | 2 = 8 - 6 |
3 = 3 (no op.) | 4 = 7 - 3 |
5 = 8 - 3 | 6 = 6 (no op.) |
7 = 7 (no op.) | 8 = 8 (no op.) |
9 = 3 + 6 | 10 = 3 + 7 |
11 = 3 + 8 | 12 = 6 + 6 |
13 = 6 + 7 | 14 = 7 + 7 |
15 = 7 + 8 | 16 = 8 + 8 |
Another solution is 4, 6, 7, and 9.
(2) Proof that k = 4.
We will show that no three numbers are sufficient to build all numbers from 1 to 16 by single addition or subtraction.
Consider any three numbers, A < B < C.
By subtraction we can build at most 3 different positive numbers,
C - B, C - A, and B - C.
By addition we can build at most 6 different numbers,
A + B, A + C, B + C, A + A, B + B, and C + C.
And 3 numbers require no operation,
A, B, and C.
Discussion.
-------------
We are often facing tasks where we do not know if they can be done at all. "If you don't succeed, try again and again", is a good principle. But if something cannot be done, it is a tremendous waste of time and effort. Mathematical proofs can show you that a task is not doable, and by that prevent all this waste.