Combi Prob

For discussing Olympiad Level Combinatorics problems
Almx26
Posts:5
Joined:Fri Aug 28, 2020 11:08 am
Location:Chattogram,Bangladesh
Contact:
Combi Prob

Unread post by Almx26 » Mon Oct 26, 2020 6:42 pm

Can you show that given any 52 integers,there exists 2 of them whose sum or,otherwise difference, is divisible by 100
Is it true with 51 integers?Why?
(Copied and collected)

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Combi Prob

Unread post by Mehrab4226 » Sat Feb 06, 2021 10:07 pm

Almx26 wrote:
Mon Oct 26, 2020 6:42 pm
Can you show that given any 52 integers, there exists 2 of them whose sum or, otherwise difference, is divisible by 100
Is it true with 51 integers? Why?
(Copied and collected)
This is a PHP problem. We make 2 sets of possible values of the 52 integers in mod(100).
$S_1= \{1,2,3,4,\cdots 50\}$, $S_2= \{-1,-2,-3,\cdots -50\}$, and $S_3=\{ 0 \}$. Now let us establish one-one correspondence with $S_1$ and $S_2$

$$
\begin{matrix}
1 & 2 & 3 & \cdots &50\\
\updownarrow & \updownarrow & \updownarrow & \cdots & \updownarrow \\
-1 & -2 & -3 & \cdots & -50
\end{matrix}
$$
Clearly, there are 49 such correspondence, If 50 integers are taken from the sets then by PHP there must be one of the correspondences having 2 integers. Thus, either their sum will be 0mod(100)(If the integers are different in mod(100)) or their difference will be 0mod(100) otherwise.
If we don't take 50 integers from $S_1$ and $S_2$ then, 2 integers are from $S_3$, which, you know maintains our property. $\square$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply