Problem!!!(BOMC-2)

Discussion on Bangladesh National Math Camp
sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:
Problem!!!(BOMC-2)

Unread post by sourav das » Tue Apr 03, 2012 12:08 pm

Let $a_1, a_2,... a_{20}$ be distinct positive integers not exceeding $70$. Show that there is some $k$
so that $a_i$ $-a_j$ = $k$ for four different pairs ($i, j$).

Edited, comment:Sorry, I didn't Latex the minus sign
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Problem!!!(BOMC-2)

Unread post by *Mahi* » Tue Apr 03, 2012 12:28 pm

$(i,j)$ and $(j,i)$ are different pairs for $i \not = j$, are not they?
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:

Re: Problem!!!(BOMC-2)

Unread post by sourav das » Tue Apr 03, 2012 12:37 pm

*Mahi* wrote:$(i,j)$ and $(j,i)$ are different pairs for $i \not = j$, are not they?
The question didn't say ordered pairs...
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Problem!!!(BOMC-2)

Unread post by *Mahi* » Tue Apr 03, 2012 12:42 pm

When you use first brackets, the convention is to assume $(i,j)\neq (j,i)$. If you wanted to mean "not ordered pair" you could have used $\{i,j\}$ to remove the confusion.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:

Re: Problem!!!(BOMC-2)

Unread post by sourav das » Tue Apr 03, 2012 12:46 pm

*Mahi* wrote:When you use first brackets, the convention is to assume $(i,j)\neq (i,j)$. If you wanted to mean "not ordered pair" you could have used $\{i,j\}$ to remove the confusion.
Sorry , actually I just wrote what i saw in the question. And that's why I'm not confidently saying that the question doesn't mean ordered pairs...
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Problem!!!(BOMC-2)

Unread post by *Mahi* » Tue Apr 03, 2012 12:48 pm

Have you solved it yet? (If you have, with/without ordered pairs?)
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

sourav das
Posts:461
Joined:Wed Dec 15, 2010 10:05 am
Location:Dhaka
Contact:

Re: Problem!!!(BOMC-2)

Unread post by sourav das » Tue Apr 03, 2012 1:27 pm

*Mahi* wrote:Have you solved it yet? (If you have, with/without ordered pairs?)
I found this problem in an N.T. work sheet.I couldn't remember how far i went then and even if I've solved this problem I've completely forget about that. Besides actually i want to see a nice solution of this problem....

(and actually ordered pairs doesn't matter that much as if $a_i-a_j=k=a_j-a_i$ will imply $a_i=a_j$ and contradiction, so it's easy to guess we should work with only pairs )
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: Problem!!!(BOMC-2)

Unread post by *Mahi* » Tue Apr 03, 2012 2:27 pm

Sorry, a hour's load shedding :oops:
Yes, I figured that out then. But there must be $21$ elements in the set otherwise a contradiction can be built.
Solution:
There are total $210$ differences , $|a_i-a_j|$ of the numbers of set $\{a_k\}$, and also $1\leq |a_i-a_j|\leq 69$.
So, some $1 \leq k \leq 69$ equals to at least $\left \lceil \frac {210}{69} \right \rceil =4 $ differences.
For $20$ elements,contradiction:
We can choose $20$ elements from $1 ,2,\cdots 70$ by PHP with no four difference same, as there are $190$ differences.
I hope you will edit the question.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Problem!!!(BOMC-2)

Unread post by Phlembac Adib Hasan » Tue Apr 03, 2012 8:29 pm

Solution:
Let $P(a_i,a_j)\Rightarrow max(a_i,a_j)-min(a_i,a_j)$
Notice that we can make $20.19=380$ pairs from $20$ elements.But we have $P(a_i,a_j)=P(a_j,a_i)$.Hence the number of pairs is $\frac {380}{2}=190$.
Now notice that The maximum value of $a_i-a_j$ is $69$ and minimum is $1$.So from Pigeon Hole Principle, there is a $k$ for which we can write $a_i-a_j=k$ for at most$\left \lceil \frac{190}{69} \right \rceil=3$ different $P(a_i,a_j)$.So disproved.
Last edited by Phlembac Adib Hasan on Tue Apr 03, 2012 9:35 pm, edited 1 time in total.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: Problem!!!(BOMC-2)

Unread post by Phlembac Adib Hasan » Tue Apr 03, 2012 8:32 pm

How clumsy I am! :x A person without any patience. :x :x Always making silly mistakes. :x :x :x
Last edited by Phlembac Adib Hasan on Tue Apr 03, 2012 9:38 pm, edited 1 time in total.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply