COMBINATORICS MARATHON: SEASON 2
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
I guess it's time to restart Combinatorics Marathon.
RULES: Very simple. I'll start this Marathon with a Combinatorics problem. Next who can give the solution of the problem, will get a chance to post a new problem. Different solutions are welcome too. Who will give a different solution also can get a chance to post a new problem. To make things interesting, one have to post solution of a problem within 12 hours. After 12 hours, the problem will be a star problem and the problem will be re-posted in a new topic. But the Combinatorics Marathon will be continued by posting a new problem from the former solvers....
Hope u will enjoy the Combinatorics Marathon.
Problem 1:
A tennis tournament has at least three participants. Every participant plays exactly one
match against every other participant, and moreover every participant wins at least one
of his or her matches. (Draws do not occur in tennis.)
Show that there are three participants $A, B, C$ for which the following holds: $A$ wins
against $B$, $B$ wins against $C$, and $C$ wins against $A$.
RULES: Very simple. I'll start this Marathon with a Combinatorics problem. Next who can give the solution of the problem, will get a chance to post a new problem. Different solutions are welcome too. Who will give a different solution also can get a chance to post a new problem. To make things interesting, one have to post solution of a problem within 12 hours. After 12 hours, the problem will be a star problem and the problem will be re-posted in a new topic. But the Combinatorics Marathon will be continued by posting a new problem from the former solvers....
Hope u will enjoy the Combinatorics Marathon.
Problem 1:
A tennis tournament has at least three participants. Every participant plays exactly one
match against every other participant, and moreover every participant wins at least one
of his or her matches. (Draws do not occur in tennis.)
Show that there are three participants $A, B, C$ for which the following holds: $A$ wins
against $B$, $B$ wins against $C$, and $C$ wins against $A$.
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
Re: COMBINATORICS MARATHON: SEASON 2
$\text{Solution:}$
We denote a defeats b by $a \rightarrow b$. So the graph is a complete directed graph with directed edges from $x$ to $y$ if $x$ defeats $y$.
Now there is at least an outward edge from all the points. So If we start from the vertice where there is least edges coming in, we can always get a complete cycle. So now there is only one thing to prove, if there is a cycle of length $k$ in a set like this, then there will be also a cycle of length $3$.
Now let the cycle of length $k$ be $a_1 \rightarrow a_2 \rightarrow a_3 \rightarrow ... \rightarrow a_k $. Now if we join two points of that cycle with non-directed a line, then the cycle will be divided in two parts, with opposite direction. So whichever direction the new line be given, a new cycle is always created.So if there exists a cycle of $k$ length in a set there will always be a cycle of $m$ length with $m<k$ in that set. And agai, as the minimal length of a cycle is $3$, and $k$ is always decreasing, so the cycle having smallest length will be of length $3$ eventually.
We denote a defeats b by $a \rightarrow b$. So the graph is a complete directed graph with directed edges from $x$ to $y$ if $x$ defeats $y$.
Now there is at least an outward edge from all the points. So If we start from the vertice where there is least edges coming in, we can always get a complete cycle. So now there is only one thing to prove, if there is a cycle of length $k$ in a set like this, then there will be also a cycle of length $3$.
Now let the cycle of length $k$ be $a_1 \rightarrow a_2 \rightarrow a_3 \rightarrow ... \rightarrow a_k $. Now if we join two points of that cycle with non-directed a line, then the cycle will be divided in two parts, with opposite direction. So whichever direction the new line be given, a new cycle is always created.So if there exists a cycle of $k$ length in a set there will always be a cycle of $m$ length with $m<k$ in that set. And agai, as the minimal length of a cycle is $3$, and $k$ is always decreasing, so the cycle having smallest length will be of length $3$ eventually.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: COMBINATORICS MARATHON: SEASON 2
It was a good problem of recursion by Masum vai, going on unanswered, so I posted it here.
New problem!
There are $3$ types of tiles available $2\times1,1\times2,2\times2$. In how many ways can you tile $2\times n$ rectangle without considering reflections?
For ex. We have $3$ tiling for $n=3$, $8$ for $n=4$.
New problem!
There are $3$ types of tiles available $2\times1,1\times2,2\times2$. In how many ways can you tile $2\times n$ rectangle without considering reflections?
For ex. We have $3$ tiling for $n=3$, $8$ for $n=4$.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: COMBINATORICS MARATHON: SEASON 2
Actually it was from a programming contest and I gave this to Dj and in that night he gave me the solution through the phone*Mahi* wrote: going on unanswered
One one thing is neutral in the universe, that is $0$.
Re: COMBINATORICS MARATHON: SEASON 2
Hmmm. I wanted the solution from the non-veterans, actually...
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Re: COMBINATORICS MARATHON: SEASON 2
Did he solve it by using generating functions?
Re: COMBINATORICS MARATHON: SEASON 2
I just found two simple recursions. Those recursions can be solved either using generating functions or using other algebra stuffs.
ধনঞ্জয় বিশ্বাস
Re: COMBINATORICS MARATHON: SEASON 2
are your equations for odd $n$ and even $n$,is it a three term recurrence?could you give your recursions,i want to check with my one.Iam not so sure about my solution.I used generating functions by the way to find the answer.If my two recursions are right,then my answer is right.Corei13 wrote:I just found two simple recursions. Those recursions can be solved either using generating functions or using other algebra stuffs.
Re: COMBINATORICS MARATHON: SEASON 2
Let $a_n$ is the solution.
Let, $b_n$ is the numbers of tiling WITH considering reflections.
Then, $b_{n} = b_{n-1} +2 b_{n-2}$
Let, $c_n$ is the numbers of tiling which remains same after reflection.
Then, $c_{2n} = b_n + 2*b_{n-1}$ and $c_{2n+1} =b_n$
Now, $b_n$ = Total number of tiling = symmetric tiling + non-symmetric tiling
So, it's easy to find $b_n = c_n + 2 ( a_n - c_n ) = 2 a_n - c_n $
As, we know $b_n$ and $c_n$, we can find $a_n$.
Let, $b_n$ is the numbers of tiling WITH considering reflections.
Then, $b_{n} = b_{n-1} +2 b_{n-2}$
Let, $c_n$ is the numbers of tiling which remains same after reflection.
Then, $c_{2n} = b_n + 2*b_{n-1}$ and $c_{2n+1} =b_n$
Now, $b_n$ = Total number of tiling = symmetric tiling + non-symmetric tiling
So, it's easy to find $b_n = c_n + 2 ( a_n - c_n ) = 2 a_n - c_n $
As, we know $b_n$ and $c_n$, we can find $a_n$.
ধনঞ্জয় বিশ্বাস
Re: COMBINATORICS MARATHON: SEASON 2
You just gave the solution (my own soln. uses these recursions too)... so I think you have to post a new one!
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi