A problem of combinatorics

For students of class 11-12 (age 16+)
MH Avishek
Posts: 1
Joined: Sat Dec 12, 2015 8:48 pm

A problem of combinatorics

Unread post by MH Avishek » Wed Dec 23, 2015 1:25 am

There are 36 participants at a BDMO event . Some of the participants shook hands with each other . But no two participants shook hands with each other more than once . Each participants recorder the number of handshakes they made . It was found that no two participants with the same number of handshakes made , had shaken hands with each other . Find the maximum number of handshakes at the party with PROOF .(when 2 participants shook hands with each other ,this will be counted as one handshake )

User avatar
seemanta001
Posts: 13
Joined: Sat Jun 06, 2015 9:31 am
Location: Chittagong

Re: A problem of combinatorics

Unread post by seemanta001 » Thu Jan 14, 2016 12:39 am

A person can shake hands with others for maximum $35$ times.
Suppose $A_1$ shook hands 35 times with $A_2$,$A_3$....$A_{36}$.
Then $A_2$ can shake hands maximum $34$ times.As he has already shaken hands with $A_1$, suppose he hasn't shaken hands with $A_3$.Similarly $A_3$ hasn't shaken hands with $A_2$ and can shake hands maximum $34$ times.
Thus the maximum number of handshakes in that party will be:
$$35+(2 \times 34)+(3 \times 33)+(4 \times 32)+.....+(8 \times 28)=1092$$. :)
"Sometimes it's the very people who no one imagines anything of who do the things no one can imagine"

Ragib Farhat Hasan
Posts: 37
Joined: Sun Mar 30, 2014 10:40 pm

Re: A problem of combinatorics

Unread post by Ragib Farhat Hasan » Thu Jan 14, 2016 7:32 pm

The actual solution to this problem is like this-
1 can shook hands with a max. of 35 people.
Then 2 can shook hands with a max. of 34 people (this is the total handshake made including the handshake with the 1st person).
Then 3 with max. 33, 4 with 32, 5 with 31, 6 with 30, 7 with 29 and 8 with 30 people.
Now, if everybody shook hands with each other, then total no. of handshake would be= 36C2= 630.
So now let us calculate how many handshake didn't occur-
2C2+3C2+4C2+5C2+6C2+7C2+8C2=84
Therefore, max. no. of handshake was= 630-84=546.(ans)

Golam Musabbir Joy
Posts: 11
Joined: Tue Jun 16, 2015 5:11 am
Location: Barisal, Bangladesh

Re: A problem of combinatorics

Unread post by Golam Musabbir Joy » Mon Aug 08, 2016 12:45 am

Ragib Farhat Hasan wrote:The actual solution to this problem is like this-
1 can shook hands with a max. of 35 people.
Then 2 can shook hands with a max. of 34 people (this is the total handshake made including the handshake with the 1st person).
Then 3 with max. 33, 4 with 32, 5 with 31, 6 with 30, 7 with 29 and 8 with 30 people.
Now, if everybody shook hands with each other, then total no. of handshake would be= 36C2= 630.
So now let us calculate how many handshake didn't occur-
2C2+3C2+4C2+5C2+6C2+7C2+8C2=84
Therefore, max. no. of handshake was= 630-84=546.(ans)
I didn't get the last line. please explain.

User avatar
samiul_samin
Posts: 1004
Joined: Sat Dec 09, 2017 1:32 pm

Re: A problem of combinatorics

Unread post by samiul_samin » Sun Feb 18, 2018 10:51 am

Hint
Use function
Answer
Correct answer $\fbox {3885}$

Mathlomaniac
Posts: 17
Joined: Wed Mar 07, 2018 11:35 pm
Contact:

Re: A problem of combinatorics

Unread post by Mathlomaniac » Fri Mar 09, 2018 5:49 pm

36×35/2 =630

Ragib Farhat Hasan
Posts: 37
Joined: Sun Mar 30, 2014 10:40 pm

Re: A problem of combinatorics

Unread post by Ragib Farhat Hasan » Mon Sep 03, 2018 1:22 am

Golam Musabbir Joy wrote:
Mon Aug 08, 2016 12:45 am
Ragib Farhat Hasan wrote:The actual solution to this problem is like this-
1 can shook hands with a max. of 35 people.
Then 2 can shook hands with a max. of 34 people (this is the total handshake made including the handshake with the 1st person).
Then 3 with max. 33, 4 with 32, 5 with 31, 6 with 30, 7 with 29 and 8 with 30 people.
Now, if everybody shook hands with each other, then total no. of handshake would be= 36C2= 630.
So now let us calculate how many handshake didn't occur-
2C2+3C2+4C2+5C2+6C2+7C2+8C2=84
Therefore, max. no. of handshake was= 630-84=546.(ans)
I didn't get the last line. please explain.
I meant to say that subtracting the "no. of handshakes that couldn't occur" (to satisfy the given condition) from the max. no. of handshakes that "could've occurred if there wasn't any condition" provides the final answer, that is 546.

Ragib Farhat Hasan
Posts: 37
Joined: Sun Mar 30, 2014 10:40 pm

Re: A problem of combinatorics

Unread post by Ragib Farhat Hasan » Mon Sep 03, 2018 1:31 am

Mathlomaniac wrote:
Fri Mar 09, 2018 5:49 pm
36×35/2 =630
Read the problem again.

Ragib Farhat Hasan
Posts: 37
Joined: Sun Mar 30, 2014 10:40 pm

Re: A problem of combinatorics

Unread post by Ragib Farhat Hasan » Mon Sep 03, 2018 1:33 am

samiul_samin wrote:
Sun Feb 18, 2018 10:51 am
Hint
Use function
Answer
Correct answer $\fbox {3885}$
The correct answer of this problem is 546, and it is an established solution. This problem actually appeared in the National Math Olympiad 2015 in secondary and higher secondary categories.

Moreover, read the question again. It says that no one shook hands with anyone more than once. In absence of any other conditions (though the problem states another condition), the max. no of handshake will be 36C2=630.

But under the given conditions, the answer is 546.

I hope you find where you made mistakes and correct them.

User avatar
samiul_samin
Posts: 1004
Joined: Sat Dec 09, 2017 1:32 pm

Re: A problem of combinatorics

Unread post by samiul_samin » Thu Feb 21, 2019 1:34 pm

This is BdMO National Secondary & Higher Secondary $2015$ problem no $4$. My solution was wrong :oops: :oops:

Post Reply