2

On a paper there exist three distinct natural numbers. A "step" means that we choose two of them and replace one of these with their arithmetic mean. Prove that there exists a finite sequence of "steps" after which we will have two equal numbers.

I know that I could use the Invariant principle, but I can't do this.

I tried to consider the product P=|a-b||a-c||b-c| but I can't prove that P decreases after each "step".

I don't know if it is a good idea or not.

Maybe you can help me. Sorry if my english is not good. I hope you will understand.

ruakh
  • 679
Thhh2023
  • 21
  • 2
    Surely you mean to say "there exists a set of valid moves which results in two, at least, of the numbers being the same." It won't be true for all sequences of moves. – lulu Feb 28 '23 at 21:24
  • 1
    Of the two numbers chosen, do we replace the larger? the smaller? or can we choose? – David G. Stork Feb 28 '23 at 21:24
  • Yes, @Iulu. There exists a set of valid moves... – Thhh2023 Feb 28 '23 at 21:26
  • So...then there's no need to search for a general Invariant as we are not looking at the general collection of moves. – lulu Feb 28 '23 at 21:27
  • @David We can choose. – Thhh2023 Feb 28 '23 at 21:27
  • 1
    Hint: Since there are three integers, at least two of them must have the same parity. – lulu Feb 28 '23 at 21:28
  • I tried to use this idea, but it did not help me. – Thhh2023 Feb 28 '23 at 21:33
  • Well...if the two numbers with the same parity coincide, then we are done. If they don't, then replace the larger with the mean. That reduces the sum of the three numbers, so we are done by induction (trusting you can handle the base case). – lulu Feb 28 '23 at 21:41
  • Side note: I'm sure this question is a duplicate, but I haven't been able to find the earlier version. Maybe someone else can? – lulu Feb 28 '23 at 21:42
  • I want a solution for a 12 years old student. So, not by induction. – Thhh2023 Feb 28 '23 at 21:45
  • I've posted a very elementary solution. I'll leave it for you to decide if it works for $12$ year olds. You should be able to rephrase it without using induction...just say that the process I describe either finds a winner or keeps getting smaller, and it can't get smaller forever. – lulu Feb 28 '23 at 21:46
  • Thank you very much! – Thhh2023 Feb 28 '23 at 21:58

2 Answers2

4

To summarize the discussion in the comments:

We'll proceed by induction on the sum of the three numbers. If the sum is $3$, which is minimal here, then the integers must be $(1,1,1)$ so we are done in that case.

Assume we have checked up to sum $k$. Then take three integers that sum to $k+1$. Take two with the same parity (choose randomly if all three have the same parity). If these two are the same, we are done. If they are not the same, then replace the larger one with the mean. That lowers the sum, so we are done by induction.

Note that taking the mean in this way reduces the sum of the three numbers by at least $1$. We see that, starting with $(a,b,c)$, this process must stop (i.e. find a pair of equal numbers) in at most $a+b+c-3$ turns. ($-3$ since we can't get below $(1,1,1)$).

lulu
  • 70,402
  • [+1] but the text is ambiguous. The question should have been "Show that we can choose a sequence of moves such that..." – Jean Marie Feb 28 '23 at 22:00
  • 1
    @JeanMarie Yes, that was the point of my first comment. If, say, you tried to use two numbers of different parities, nothing works. – lulu Feb 28 '23 at 22:05
3

Let the three natural numbers be $(a, b, c)$ such that $a < b < c$

By the pigeonhole principle, at least two of the three numbers must have the same parity.

If $a$ and $b$ have the same parity:

Replace $a$ with the arithmetic mean of $a$ and $b$.

Then, the three numbers in ascending order will be $(\frac{a+b}{2}, b, c)$

The gap between the smallest and largest number decreases by $\frac{b-a}{2} \ge 1$

If $a$ and $c$ have the same parity:

Replace $a$ with the arithmetic mean of $a$ and $c$.

Then, the three numbers in ascending order will be $(\frac{a+c}{2}, b, c)$ or $(b, \frac{a+c}{2}, c)$

The gap between the smallest and largest number decreases by $\frac{c-a}{2} \ge 1$ or $(b-a) \ge 1$

If $b$ and $c$ have the same parity:

Replace $c$ with the arithmetic mean of $b$ and $c$.

Then, the three numbers in ascending order will be $(a, b, \frac{b+c}{2})$

The gap between the smallest and largest number decreases by $\frac{c-b}{2} \ge 1$ $$\\$$ After every step, we rewrite the three numbers in ascending order, and define them as $(a, b, c)$ such that $a < b < c$

Since we always select two numbers with the same parity, the resulting sequence $(a, b, c)$ will still have natural numbers.

The gap between the smallest and largest number decreases by at least $1$ after every step.

Since this gap is finite, it must become less than 2 after a finite number of steps. At this point, we can guarantee that at least two of the numbers must be equal. Note that two numbers might become equal in fewer steps (even before the gap between the smallest and largest number becomes lesser than 2), but that too will occur in a finite number of steps.

Amogh
  • 1,103