COMBINATORICS MARATHON: SEASON 2

[sourav das]

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$.

[*Mahi*]

$\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.

example.png (4.13KiB)Viewed 6382 times

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.

[*Mahi*]

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$.

[Masum]

going on unanswered

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*]

Hmmm. I wanted the solution from the non-veterans, actually...

[mahathir]

Did he solve it by using generating functions?

[Corei13]

I just found two simple recursions. Those recursions can be solved either using generating functions or using other algebra stuffs.

[mahathir]

I just found two simple recursions. Those recursions can be solved either using generating functions or using other algebra stuffs.

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]

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$.

[*Mahi*]

You just gave the solution (my own soln. uses these recursions too)... so I think you have to post a new one!