Maths Olympiad Prep

Library / /209 of 220

Number theory Difficulty 7.5 National Olympiad, round 2 Prove it Ukraine

Given a prime number p>2p > 2. There are NN people in a circle, each one came up with a positive integer and then wrote down the remainder when divided by pp on a piece of paper. Then everyone showed their piece of paper to the neighbor on the right, computed the product of their number on a piece of paper and their neighbor's number, and wrote down the second number, which is the remainder of a product divided by pp. What is the largest value that NN could be, if it is known that everyone's first numbers are pairwise distinct, and each piece of paper has two distinct numbers written down?

Solution

Clearly, there cannot be more than pp different numbers. It follows from the condition of the problem, that 00 could not be someone's number on the first step, since then that person will have it on the second step as well. Also, no one can have 11 as a first number, since then the neighbor on the left will have two equal numbers. We will show that the conditions hold for N=p2N = p-2.

Indeed, let the following consecutive numbers be written down on the first step from left to right: 2,3,4,,p12, 3, 4, \ldots, p-1. They are all pairwise distinct. Assume that after the second step someone's two numbers are equal. If it's one of the first N1N-1 people, it means that the product k(k+1)k(k+1), where 2kp22 \le k \le p-2, has the same remainder when divided by pp, as the number kk. But then their difference is divisible by pp, that is, k(k+1)k=k2k(k+1)-k=k^2 is divisible by a prime number pp, thus, kpk \nmid p, which is not possible. If the NN-th person has two equal numbers, then the number p1p-1 will be multiplied by 22, but then two numbers will be different, since 2(p1)(p1)=p12(p-1)-(p-1)=p-1 is not divisible by pp.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.