5
$\begingroup$

On the blackboard, there are nine numbers from 1 to 9. In each operation, two of the numbers are chosen, erased, and replaced with their sum and difference. If two identical numbers appear on the blackboard, one of them is erased to ensure that there are no duplicate numbers. What is the minimum number of operations required to leave only two numbers on the blackboard?

For example:

  • Initial list 1,2,3,4,5,6,7,8,9
  • Let's choose 4,5
  • List becomes 1,2,3,6,7,8,9
  • 4+5=9; 5-4=1
  • Then the list becomes 1,1,2,3,6,7,8,9,9
  • Remove duplicates, the list becomes 1,2,3,6,7,8,9
  • End of 1st operation.

Source: HopeMath World - International Regional Competition IHC6, Question 20.

I have found a way by playing around

  • Step 1, choose 1,9 We get 2,3,4,5,6,7,8,10
  • Step 2, choose 2,8 We get 3,4,5,6,7,10
  • Step 3, choose 3,7 We get 4,5,6,10
  • Step 4, choose 4,6 We get 2,5,10
  • Step 5, choose 2,5 We get 3,7,10
  • Step 6, choose 3,7 We get 4,10

Obviously, for every operation you can get rid of two numbers max, to reduce 9 numbers to 2 numbers you need min 4 operations. Now I have found a way that requires 6 operations.

Can I be sure this is the minimum number of operations required?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

I can do it in seven operations:

1,2,3,4,5,6,7,8,9 | 6-5=1, 6+5=11
1,2,3,4,7,8,9,11 | 9-2=7, 9+2=11
1,3,4,7,8,11 | 7-4=3, 7+4=11
1,3,8,11 | 8-3=5, 8+3=11
1,5,11 | 11-1=10, 11+1=12
5,10,12 | 12-5=7, 12+5=17
7,10,17 | 17-7=10, 17+7=24
10,24

Alternative path, with smaller final numbers:

1,2,3,4,5,6,7,8,9 | 3-2=1, 3+2=5
1,4,5,6,7,8,9 | 5-4=1, 5+4=9
1,6,7,8,9 | 8-1=7, 8+1=9
6,7,9 | 9-7=2, 9+7=16
2,6,16 | 6-2=4, 6+2=8
4,8,16 | 8-4=4, 8+4=12
4,12,16 | 12-4=8, 12+4=16
8,16

EDIT: A quick computer search revealed what I should have seen by hand:

1,2,3,4,5,6,7,8,9 | 6-3=3, 6+3=9
1,2,3,4,5,7,8,9 | 3-2=1, 3+2=5
1,4,5,7,8,9 | 5-4=1, 5+4=9
1,7,8,9 | 8-1=7, 8+1=9
7,9 in four operations (among several other possible solutions).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks! 4 operations do work but how did you work that out? what was the logical thinking behind it? @AxiomaticSystem $\endgroup$
    – Vincent
    Commented Apr 3 at 11:46
  • $\begingroup$ I did a brute-force search to find the fastest predecessors to two-number sets, saw the one that was closest to my second manual solution, and patched in the necessary first step. $\endgroup$
    – AxiomaticSystem
    Commented Apr 4 at 12:14
  • $\begingroup$ As for "how do I know that four is enough", I know that three are insufficient, because at most two numbers are removed each step, and this maximum is easy to attain via my second and third steps (or other variations thereof) - all that was needed were compatible first and fourth steps to finish it up. $\endgroup$
    – AxiomaticSystem
    Commented Apr 4 at 12:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.