Combinatorics problems

For discussing Olympiad Level Combinatorics problems
Ragib Farhat Hasan
Posts:62
Joined:Sun Mar 30, 2014 10:40 pm
Combinatorics problems

Unread post by Ragib Farhat Hasan » Wed Sep 23, 2015 12:13 pm

Q1. A plane has 15 points, 5 of them are collinear. Other than this, if no 3 points are collinear, find the total number of triangles and straight lines that can be formed.

Q2. A country has N cities and N roads. Between any two cities, there is maximum one road. Prove that there is at least one city, starting from which you can come back to it again without travelling the same road twice.

Q3. A= {1, 2, 3…….20}. How many subsets of A, containing three elements, can be formed so that the sum of the elements is divisible by 3?

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Combinatorics problems

Unread post by tanmoy » Thu Sep 24, 2015 12:09 am

Have you solved this? If not,here are some hints
Hint:
$\text {Problem 1}$:
We can take $1,2$ or $0$ points from the $5$ collinear points and the others from the rest $10$ points to make triangle and to make straight line we can take $1$ or $0$ points from the $5$ collinear points and the others from the rest $10$ points.
$\text {Problem 2}$:
Prove it:If a graph has $e$ edges and $v$ vertices and $e≥v$,then the graph must contain a $cycle$.


$\text {Problem 3}$:
Let $S={x: x=3k,x<21}$;$B={y: y=3k+1,y<21}$;$C={z: z=3k+2,z<21}$.
Now think how can we make $3$ element sets which satisfie the question.
"Questions we can't answer are far better than answers we can't question"

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

Re: Combinatorics problems

Unread post by Ragib Farhat Hasan » Mon Sep 28, 2015 9:26 pm

I have solved them but I am uncertain about the solutions. Can you post the solutions?

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Combinatorics problems

Unread post by tanmoy » Tue Sep 29, 2015 10:50 pm

Ragib Farhat Hasan wrote:I have solved them but I am uncertain about the solutions. Can you post the solutions?
Okay.
$\text {Problem 1}$:
We can take $1,2$ or $0$ points from the $5$ collinear points and the others from the rest $10$ points to make triangle.So,the number of total triangles that can be made by using the $15$ points is $\binom{5}{0}\binom{10}{3}+\binom{5}{1}\binom{10}{2}+\binom{5}{2}\binom{10}{1}=445$;Now to make straight line we can take $1$ or $0$ points from the $5$ collinear points and the others from the rest $10$ points.So,the number of total straight lines that can be made by using the $15$ points is $\binom{5}{0}\binom{10}{2}+\binom{5}{1}\binom{10}{1}=95+1=96$.
$\text {Problem 2}$:
There is a cycle.So,it is possible.

$\text {Problem 3}$:
Let $S={x: x=3k,x<21}$;$B={y: y=3k+1,y<21}$;$C={z: z=3k+2,z<21}$.Now,we can make $3$ element subsets that satisfy the condition in the following ways:
(1)We can take $3$ numbers from $S$.
(2)We can take $1$ number from $S$,$1$ number from $B$,$1$ number from $C$.
(3)We can take $3$ numbers from $B$.
(4)We can take $3$ numbers from $C$.
So,the total numbers of subsets which satisfy the condition is $\binom{6}{3}+\binom{6}{1}\binom{7}{1}\binom{7}{1}+\binom{7}{3}+\binom{7}{3}=384$.
.
[/quote]
Last edited by tanmoy on Wed Sep 30, 2015 2:34 pm, edited 1 time in total.
"Questions we can't answer are far better than answers we can't question"

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

Re: Combinatorics problems

Unread post by Ragib Farhat Hasan » Wed Sep 30, 2015 12:21 pm

Problem 3:
My answer is 6C3+(6)(7)(7)+7C3+7C3=384.

tanmoy
Posts:312
Joined:Fri Oct 18, 2013 11:56 pm
Location:Rangpur,Bangladesh

Re: Combinatorics problems

Unread post by tanmoy » Wed Sep 30, 2015 2:35 pm

Ragib Farhat Hasan wrote:Problem 3:
My answer is 6C3+(6)(7)(7)+7C3+7C3=384.
There was a typo.So,edited. :D
"Questions we can't answer are far better than answers we can't question"

maliha ferdous
Posts:2
Joined:Thu Mar 26, 2015 11:05 am

Re: Combinatorics problems

Unread post by maliha ferdous » Sat Oct 31, 2015 10:46 pm

A card is selected at random from a standard 52 card deck. The suit is recorded and the card is replaced in the deck. This is done a total of seven times. find the probability of all four suits occur among the cards selected.

viking71
Posts:1
Joined:Tue Oct 27, 2015 12:42 am

Re: Combinatorics problems

Unread post by viking71 » Thu Nov 05, 2015 1:20 am

I think the probability is 3/32.
Total number of incidents is $4^7$.
There are $4!$x$4^3$ incidents where all four suits occure.

Post Reply