The Practical Value of Proofs

 

Introduction to the problem.

----------------------------------

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.

 

Remark.Let the students find and present their solutions. Don't expect that they provide proofs. Show them the proof given below, and follow up with a discussion. 

 

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.

 

Thus, from three numbers we can build at most 3 + 6 + 3 = 12 numbers. So we cannot build all 16.

 

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.

 

When a teacher asks students to do some task, the students know that the task can be done. Therefore they think that working on doable tasks is the norm. It is not so when people are working on real problems. Here, attempts to do something that cannot be done are the norm, so failures and wasted efforts happen often, and success is an exception.
Webpage Maintained by Owen Ramsey
Lesson Index