Maths Olympiad Prep

Library / /215 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

Example 1 If a set does not contain three numbers x,y,zx, y, z that satisfy x+y=zx+y=z, then it is called simple. Let M={1,2,,2n+1},AM=\{1,2, \cdots, 2 n+1\}, A be a simple subset of MM, find the maximum value of A|A|. (1982

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

Solution

Let A={1,3,5,,2n+1}A=\{1,3,5, \cdots, 2 n+1\}, then AA is simple, and at this point A=n+1|A|=n+1. We will prove that for any simple subset AA, An+1|A| \leqslant n+1. We use proof by contradiction. Assume A>n+1|A|>n+1, then AA contains at least n+2n+2 elements, let them be: a1<a2<<an+2a_{1} < a_{2} < \cdots < a_{n+2}. Consider the 2n+22n+2 numbers: a1,a2,,an+2a_{1}, a_{2}, \cdots, a_{n+2} and a2a1,a3a1,,an+2a1a_{2}-a_{1}, a_{3}-a_{1}, \cdots, a_{n+2}-a_{1}. These are all positive integers not exceeding 2n+12n+1. By the pigeonhole principle, there must be two elements that are equal, and they can only be some bib_{i} and some aja1a_{j}-a_{1}, thus a1+bi=aja_{1}+b_{i}=a_{j}, so AA is not simple, a contradiction.

Method 2: Consider the 2n+22n+2 elements: a2<a3<<an+2a_{2}<a_{3}<\cdots<a_{n+2} and a2a1<a3a1<<an+2a1a_{2}-a_{1}<a_{3}-a_{1}<\cdots<a_{n+2}-a_{1}, they are all positive integers not exceeding 2n+12n+1, so there must be two elements that are equal: let them be aia1=aja_{i}-a_{1}=a_{j}. Therefore, AA is not simple, a contradiction.

Method 3: Consider the 2n+32n+3 elements: a1<a2<a3<<an+2a_{1}<a_{2}<a_{3}<\cdots<a_{n+2} and a2a1<a3a1<<an+2a1a_{2}-a_{1}<a_{3}-a_{1}<\cdots<a_{n+2}-a_{1}, they are all positive integers not exceeding 2n+12n+1. Note that 2n+3(2n+1)=22n+3-(2n+1)=2, so there must be two pairs of elements that are equal: aia1=aj,asa1=ata_{i}-a_{1}=a_{j}, a_{s}-a_{1}=a_{t}, and at least one of aj,ata_{j}, a_{t} is not a1a_{1}, thus AA is not simple, a contradiction.

In conclusion, the maximum value of A|A| is n+1n+1.

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