Maths Olympiad Prep

Track / Stage 8 / 171 of 180 #1871 of 1964

Problem 1871

IMO Shortlist mid-range; USAMO P2/P5
Number theory Difficulty 8.8 Find the answer imo_shortlist

Four integers are marked on a circle. On each step we simultaneously replace each number by the difference between this number and next number on the circle, moving in a clockwise direction; that is, the numbers a,b,c,d a,b,c,d are replaced by a\minusb,b\minusc,c\minusd,d\minusa. a\minus{}b,b\minus{}c,c\minus{}d,d\minus{}a. Is it possible after 1996 such to have numbers a,b,c,d a,b,c,d such the numbers bc\minusad,ac\minusbd,ab\minuscd |bc\minus{}ad|, |ac \minus{} bd|, |ab \minus{} cd| are primes?

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

Consider the process where we have four integers marked on a circle, labeled as a,b,c,d a, b, c, d . The operation performed at each step involves replacing each number by the difference between this number and the next number in a clockwise direction. Specifically, the transformation is as follows:
(a,b,c,d)(ab,bc,cd,da). (a, b, c, d) \to (a-b, b-c, c-d, d-a).

Our goal is to determine if it is possible for the numbers a,b,c,d a, b, c, d to evolve, after 1996 iterations of this process, into a state where the absolute values of certain combinations are prime numbers. The combinations of interest are:
bcad,acbd,abcd. |bc - ad|, \quad |ac - bd|, \quad |ab - cd|.

### Analysis:

1. Transformation Invariance:

The key observation is to consider the sum of the numbers a,b,c,d a, b, c, d . Initially, if S=a+b+c+d S = a + b + c + d , then after one transformation, the new sum becomes:
(ab)+(bc)+(cd)+(da)=0. (a-b) + (b-c) + (c-d) + (d-a) = 0.
Therefore, the sum of the numbers after any number of transformations is always zero.

2. Modulo Properties:

Since a+b+c+d=0 a + b + c + d = 0 , any change by the differences will only preserve this relationship. Hence, the evolution of these numbers is restricted by this condition.

3. Behavior of Transformations:

Another important aspect is to look at the transformations modulo 2. If we define each initial integer, say a=x a = x , b=y b = y , c=z c = z , d=w d = w , then after one transformation, we have:
xbxy,ycyz,zdzw,wawx(mod2). x-b \equiv x-y, \quad y-c \equiv y-z, \quad z-d \equiv z-w, \quad w-a \equiv w-x \pmod{2}.
Keeping track of these values, the numbers oscillate based on their initial parities.

4. Iterative Cycle and Constants:

It is known through modular arithmetic and properties of integer sequences derived from such transformations that the system stabilizes or enters a repeating cycle often resulting in zeros when the sum S=0 S = 0 .

5. Conclusion:

Since we begin with an invariant total sum of zero, and due to the nature of even and odd number alternations, after sufficient iterations, the numbers tend toward zero. Since all the numbers tend toward zero through iterations of such transformations, their combinations, bcad,acbd,abcd |bc - ad|, |ac - bd|, |ab - cd| , also tend toward non-prime values typically zero or near-zero which are not primes.

Thus, after 1996 steps, it is not possible for bcad,acbd,abcd |bc - ad|, |ac - bd|, |ab - cd| to all be prime numbers.

No \boxed{\text{No}}

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.