Joydip's Research


প্রায় $5$ বছর আগে, জয়দীপ $2017$ সংখ্যা নিয়ে গবেষণা করছিল। সে বুঝতে পারে যে $2017$ একটি মৌলিক সংখ্যা। তারপর সে দুটি পূর্ণসংখ্যা $a, b$ নেয় যেন $0 < a, b < 2017$ হয় এবং $a + b \neq 2017$ হয়। সে $A_1, A_2, \ldots, A_{2016}$ এবং $B_1, B_2, \ldots, B_{2016}$ অনুক্রম দুটি তৈরি করল যেখানে $A_k$ হল $ak$ কে $2017$ দিয়ে ভাগ করলে কত ভাগশেষ হয় তা এবং $B_k$ হল $bk$ কে $2017$ দিয়ে ভাগ করলে কত ভাগশেষ হয় তা। $A_1 + B_1, A_2 + B_2, \ldots, A_{2016} + B_{2016}$ এর মধ্যে $N$টি সংখ্যা $2017$ থেকে বড়। প্রমাণ কর $N = 1008$।



Proof Based Problems  


  0 Upvote                    0 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

Step 1:

Prove that $A_k \neq 0$ and $B_k \neq 0$ for all $k$

Proof: For the sake of contradiction, assume that $A_k = 0$.

But, $0 = A_k \equiv ak \pmod{2017}$.

So, $2017\mid ak$

But, 2017 is a prime. So, $2017\mid a$ or $2017\mid k$

But, $a,k<2017$. So, $2017\nmid a$ and $2017\nmid k$

Contradiction. In the same way, $B_k\neq 0$ can be proved.


Step 2: 

Prove that $A_k+B_k \neq 2017m$ for all $k$ and any integer $m$

Proof: For the sake of contradiction, assume that $A_k + B_k \equiv 0 \pmod{2017}$.

But, $0 \equiv A_k+B_k \equiv ak+bk \equiv (a+b)k \pmod{2017}$.

So, $2017\mid (a+b)k$

But, 2017 is a prime. So, $2017\mid a+b$ or $2017\mid k$

But, $a,b,k<2017$ and $a+b\neq 2017$. So, $2017\nmid a+b$ and $2017\nmid k$

Contradiction.


Step 3: 

For $x,y$ with $x+y = 2017$, prove that $A_x+A_y=B_x+B_y=2017$

$A_x+A_y\equiv ax+ay \equiv a(x+y) \equiv 0 \pmod{2017}$

But, $A_x,A_y \neq 0$ and $A_x,A_y<2017$ (remainder when divided by 2017).

So, $0< A_x+A_y < 2\cdot 2017$

So, $A_x+A_y = 2017$

In the same way, $B_x+B_y=2017$ can be proved.


Step 4: 

For $x,y$ with $x+y = 2017$, prove that,  either $A_x+B_x>2017$ and $A_y+B_y<2017$ 

or $A_y+B_y>2017$ and $A_x+B_x<2017$

Proof: From step 3, we have $A_x+A_y=B_x+B_y=2017$

So, $(A_x+B_x)+(A_y+B_y) = A_x+A_y+B_x+B_y = 2\cdot 2017$

But, $A_x+B_x \neq 2017$ from step 2.

So, either $A_x+B_x > 2017 \implies A_y+B_y < 2\cdot2017-2017 = 2017$

Or, $A_x+B_x < 2017 \implies A_y+B_y > 2\cdot2017-2017 = 2017$.


So, with $x+y=2017$, exactly one of $A_x+B_x$ and $A_y+B_y$ is greater than 2017.

There are $\frac{2016}{2} = 1008$ such pairs $(x,y)$. So, there are exactly 1008 $k$ with $A_k+B_k>2017$.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial



Need a hint? Checkout the editorial.

View Editorial