combinatorics problem

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

combinatorics problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

312 posts

#1 h Jan 23, 2016, 8:32 PM • 1 Y

Y by Adventure10

$65$ distinct natural numbers not exceeding $2016$ are given. Prove that among these numbers we can find four $a,b,c,d$ such that $a+b-c-d$ is divisible by $2016.$

Z K Y

The post below has been deleted. Click to close.

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

1099 posts

jlammy

#2 h Jan 23, 2016, 8:42 PM • 2 Y

Y by Adventure10, Mango247

There are $\tbinom{65}{2}=2080$ possible sums, so we can find two such that $a+b\equiv c+d\pmod{2016}$ .

Z K Y

The post below has been deleted. Click to close.

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

196 posts

mjuk

#3 h Jan 23, 2016, 9:48 PM • 1 Y

Y by Adventure10

henderson wrote:

$65$ distinct natural numbers not exceeding $2016$ are given. Prove that among these numbers we can find four $a,b,c,d$ such that $a+b-c-d$ is divisible by $2016.$

Do $a,b,c,d$ have to be different?

Z K Y

The post below has been deleted. Click to close.

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

312 posts

#4 h Jan 24, 2016, 9:45 AM • 2 Y

Y by Adventure10, Mango247

mjuk wrote:

henderson wrote:

$65$ distinct natural numbers not exceeding $2016$ are given. Prove that among these numbers we can find four $a,b,c,d$ such that $a+b-c-d$ is divisible by $2016.$

Do $a,b,c,d$ have to be different?

yes, they are distinct numbers.

Z K Y

The post below has been deleted. Click to close.

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

1750 posts

#5 h Oct 28, 2019, 3:46 AM • 2 Y

Y by v4913, Adventure10

henderson wrote:

$65$ distinct natural numbers not exceeding $2016$ are given. Prove that among these numbers we can find four $a,b,c,d$ such that $a+b-c-d$ is divisible by $2016.$

SOURCE:
Azerbaijan Junior Mathematical Olympiad 2016

SOLUTION
Note that we only care about the numbers' remainders when divided by $2016$ , so we can replace the $65$ natural numbers with numbers in the range $0$ to $2016$ .
We can make the condition $a+b-c-d$ being divisible by $2016$ instead that $a+b-c-d = 0 \implies a+b=c+d$ . Then, there are $2016 \cdot 2 = 4032$ possible sums (anything from $0$ to $4032$ inclusive). If two of the $65$ numbers have the same sum, then the problem is solved, so assume that no two of the $65$ numbers have the same sum. Then, there are $\binom{65}{2} = 4160$ possible sums. By the pigeonhole principle, we can find four $a,b,c,d$ such that $a+b-c-d$ is divisible by $2016$ .

This post has been edited 2 times. Last edited by AopsUser101, Oct 28, 2019, 4:00 AM

Z K Y

The post below has been deleted. Click to close.

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

168 posts

#6 h Nov 15, 2024, 2:03 PM

Y by

$\binom{65}{2} >2016$
This finishes the problem where $\binom{65}{2}$ equals to the number of all possible sums so we can always find such pairs

This post has been edited 1 time. Last edited by wizixez, Nov 15, 2024, 2:04 PM

Z K Y

The post below has been deleted. Click to close.

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

2 posts

#7 h May 31, 2025, 8:17 AM

Y by

Let the $65$ natural numbers be $a_1,a_2, \dots , a_{65}$ . For pairs $(a_i,a_j) ,i<j$ , there are $\displaystyle \binom{65}{2}=2080$ possible pairs. By the Pigeonhole Principle, there exist
$\bigg\lfloor \dfrac{2080-1}{2016}\bigg\rfloor+1=2$ pairs with the same remainder when divided by 2016. That is,
$a_i+a_j \equiv a_m +a_k \pmod{2016}$ If $\{a_i,a_j\} \ne \{a_k,a_m\}$ the proof is complete.
If $a_i=a_m$ , then $a_j \equiv a_k \pmod{2016}$ . This implies $\{ a_j,a_k\} =\{0,2016\}$ .
Among the $65$ numbers $a_1, \dots , a_{65}$ , remove $2016$ (assume $a_{65}=2016$ ).
The remaing $64$ numbers $a_1, \dots , a_{64}$ yield $\displaystyle \binom{64}{2}=2016$ pair
$\bullet$ If among these 2016 sums, two have the same remainder modulo, then:
$a_u+a_v \equiv a_r +a_t \pmod{2016}$ If $a_u=a_r$ , then $a_v \equiv a_t \pmod{2016}$ , which is impossible since $0 \le a_v, a_t <2015$ and all number are distinct.
Thus $\{a_u,a_v\} \ne \{ a_r,a_t\}$ , proving the claim.
$\bullet$ If all $2016$ sums have distinct remainders modulo $2016$ , they cover all possible residues. Hence, there exists a pair $(a_p,a_q)$ such that:
$a_p+a_q \equiv 0 \pmod{2016}$ If $a_p=0$ , then $a_q \equiv 0 \pmod{2016}$ , which contradicts $a_q \ne 0,2016$ .
Therefore, $\{a_p,a_q\} \ne 0$ . Selecting the four distinct numbers $a_p,a_q,0,2016$ gives:
$a_p +a_q \equiv 0 + 2016 \pmod{2016}$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a