Problem 4

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Problem 4

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Polish Math Olympiad 2025 Finals P4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

70 posts

blug

#1 h Apr 4, 2025, 11:59 AM

Y by

A positive integer $n\geq 2$ and a set $S$ consisting of $2n$ disting positive integers smaller or equal to $n^2$ are given. Prove that there exists a positive integer $r\in \{1, 2, ..., n\}$ that can be written in the form $r=a-b$ , for $a, b\in \mathbb{S}$ in at least $3$ different ways.

This post has been edited 1 time. Last edited by blug, Apr 6, 2025, 6:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

851 posts

#2 h Apr 4, 2025, 9:06 PM

Y by

Let's assume the contrary and let $S_k \coloneqq k+S$ (translation of $S$ by $k$ ). From our assumption we get $|S_i \cap S_j| \le 2$ for any $0 \le i < j \le n.$

Now let's evaluate the cardinal of the union $\bigcup_{i=0}^n S_i$ .

At first we have the set $S_0,$ which has $2n$ elements. When we union this with $S_1$ we obtain at least $2n-2$ new elements. Then, by taking the union with $S_2$ we obtain at least $2n-4$ new elements, and so on. In the end $|S_0 \cup S_1 \cup \ldots \cup S_{n-1}| \ge 2n+(2n-2)+(2n-4)+ \ldots + 2=n(n+1).$

On the other hand $S_0 \cup S_1 \cup \ldots \cup S_{n-1} \subsetneq \{1,2,\ldots,n^2+n\},$ so $|S_0 \cup S_1 \cup \ldots \cup S_{n-1}| <n(n+1),$ contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

179 posts

#3 h Apr 5, 2025, 8:26 AM

Y by

Let $S$ consist of $x_1<x_2<\ldots<x_{2n}$ . We only consider the differences $x_{i+1}-x_i$ . If all numbers in $\{1,\ldots,n\}$ were represented in at most two ways, the sum of $x_{i+1}-x_i$ would be at least $2(1+\ldots+n-1)+n=n^2$ , but it is equal to $x_{2n}-x_1 \leq (n^2-1)-1=n^2-2$ . Thus some difference can be represented in at least three ways, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1475 posts

math90

#4 h Apr 5, 2025, 12:15 PM • 1 Y

Y by blug

The ritle should be corrected to "less than or equal to $n^2$ ".

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

32 posts

Avron

#5 h Apr 7, 2025, 3:32 PM

Y by

Let the elements of $S$ be $a_1<a_2<...<a_{2n}$ and define $b_i=a_{i+1}-a_i$ for $i=1,2,...,2n-1$ . Notice that $b_1+b_2+...+b_{2n-1}=a_{2n}-a_1\leq n^2-1$ . On the other hand, if every number from the set $\{1,2,...,n\}$ appears at most twice in $b_i$ then $b_1+b_2+...+b_{2n-1}\geq 2(1+2+...+(n-1))+n=n^2-n+n=n^2>n^2-1$ which is a contradiction, so we're done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a