Maths Olympiad Prep

Library / /18 of 97

Algebra Difficulty 7.5 National olympiad, round 2 Find the answer

Find all natural numbers n(n2)n (n \geq 2) such that there exists reals a1,a2,,ana_1, a_2, \dots, a_n which satisfy {aiaj1i<jn}={1,2,,n(n1)2}. \{ |a_i - a_j| \mid 1\leq i<j \leq n\} = \left\{1,2,\dots,\frac{n(n-1)}{2}\right\}.

Let A={1,2,3,4,5,6},B={7,8,9,,n}A=\{1,2,3,4,5,6\}, B=\{7,8,9,\dots,n\}. Ai(i=1,2,,20)A_i(i=1,2,\dots,20) contains eight numbers, three of which are chosen from AA and the other five numbers from BB. AiAj2,1i<j20|A_i \cap A_j|\leq 2, 1\leq i<j\leq 20. Find the minimum possible value of nn.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We need to find all natural numbers n n (where n2 n \geq 2 ) such that there exist real numbers a1,a2,,an a_1, a_2, \dots, a_n which satisfy the condition:
{aiaj1i<jn}={1,2,,n(n1)2}. \{ |a_i - a_j| \mid 1 \leq i < j \leq n \} = \left\{ 1, 2, \dots, \frac{n(n-1)}{2} \right\}.

We claim that only n=2,3,4 n = 2, 3, 4 work. We can construct the sets of numbers for these values of n n as follows:
- For n=2 n = 2 , we can use (0,1) (0, 1) .
- For n=3 n = 3 , we can use (0,1,3) (0, 1, 3) .
- For n=4 n = 4 , we can use (0,1,4,6) (0, 1, 4, 6) .

Now, consider n>4 n > 4 . Let n(n1)2=N \frac{n(n-1)}{2} = N . Without loss of generality, assume a1=0 a_1 = 0 and a2=N a_2 = N , with all other ai a_i lying between these two values. To produce a difference of N1 N-1 , let a3=1 a_3 = 1 . To produce a difference of N2 N-2 , we cannot have a4=2 a_4 = 2 or a4=N1 a_4 = N-1 , so let a4=N2 a_4 = N-2 . The only possible value for a5 a_5 that creates a difference of N3 N-3 and does not repeat a difference is 4, which also happens to create a difference of N4 N-4 .

However, there is no possible way to place a difference of N5 N-5 without repeating. Thus, it is impossible to satisfy the condition for n>4 n > 4 .

Therefore, the natural numbers n n that satisfy the given condition are n=2,3,4 n = 2, 3, 4 .

The answer is: 2,\boxed{2,} 3, 4}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.