## Combi Marathon

For discussing Olympiad Level Combinatorics problems
Posts: 181
Joined: Mon Mar 28, 2016 6:21 pm

### Re: Combi Marathon

The following solution is not completely mine. I solved it partially and then saw the solu in AOPS.
Solution to problem 8

Wlog, we rearrange the piles such that the piles are nonincreasing and we place them on the coordinate system such that every pile starts from the x axis and the leftmost pile starts from the origin.
Define the value of a stone to be the sum of the coordinates. Similarly, define the sum of a collection to be the sum of the values of all squares.

Lemma: The value sum of any collection of piles does not increase (either stays the same or decreases) with each move.

Proof: Shifting the squares one unit down and one unit right keeps the sum invariant. Now, there is a row of stones below the x axis. Reflecting those squares about the line $y = x-1$ keeps the sum invariant again. Now if the first pile contains as many stones as any other pile, the piles are properly ordered, and the sum remains as it was before. Otherwise, some stones will be shifted to the left, decreasing the sum.

Let $K = (n, n-1, ..., 1)$. Suppose that there exist collections of piles with $\frac{n(n+1)}{2}$ stones that do not lead to $K$ after performing some number of moves. Pick the collection with minimal sum, call it $C$. Notice that all collections formed after some number of moves on $C$ have the same level sum as $C$ because by assumption they never lead to $K$. This is important because it means that all squares cycle with a period equivalent to their level (for example, if we label the top stone in the first pile of $K$ as $a$, we see that after successive moves, stone $a$ either moves South-East or North-East to its initial position - which preserves its value). Now the key observation is that $(1)$ there is a stone in $C$ which has value $n$, call it $x'$, that does not occur in $K$ (obviously, $K$ only contains stones of value $\le n-1$), and $(2)$ a stone in $K$, call it $y'$ with value $n-1$ that does not occur in $C$. To see $(1)$, notice that if all stones in $C$ had value $\le n-1$, than since $C$ contains $\frac{n(n+1)}{2}$ stones, $C = K$, so $C$ must contain a stone of value $\ge n$. If that stone has value $> n$, it has a square below it with level $n$. The argument for $(2)$ is identical (if all stones of value $n-1$ which occur in $K$ were also in $C$, $C = K$).

Finally, after $n+1$ moves, $x'$ stays in its initial position, while $y'$ moves $SE$. After so finite number of moves, therefore, $y'$ will be directly below $x'$, which is a contradiction, since $y'$ is a hole (it is not actually in $C$).
Frankly, my dear, I don't give a damn.

Posts: 181
Joined: Mon Mar 28, 2016 6:21 pm

### Re: Combi Marathon

Problem 9
There are $n$ people at a party. Each person holds some number of coins. Every minute, each person who has at least $(n -1)$ coins simultaneously gives one coin to every other person at the party. (So, it is possible that $A$ gives $B$ a coin and $B$ gives $A$ a coin at the same time.) Suppose that this process continues indefinitely. That is, for any positive integer $m$, there exists a person who will give away coins during the $mth$ minute. What is the smallest number of coins that could be at the party?
Frankly, my dear, I don't give a damn.

Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

### Re: Combi Marathon

$\text{Solution to problem 9:}$

The answer is $0+1+2+\ldots +(n-1)=\dfrac{n(n-1)}{2}$.

Label the $i^{th}$ person as $p_i$ and let the number of coins with him be $c_i$. If $c_i=i-1$, then after each minute, the number of coins are simply permuted and thus it can go forever.

Now, if a person can give out a coin at $k^{th}$ round for the first time, he must have had at least $n-k$ coins in the beginning. Also, if the same person keeps giving out coins until the $k^{th}$ move, he must have at least $k(n-1)$ coins in the beginning. Since the process continues indefinitely, it must continue for $n$ rounds, so there was at least $(n-1)+(n-2)+(n-3)+\ldots (n-n)=\dfrac{n(n-1)}{2}$ coins.

So, we need at least $\dfrac{n(n-1)}{2}$ coins.
Last edited by Thanic Nur Samin on Mon Feb 27, 2017 7:40 pm, edited 2 times in total.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

### Re: Combi Marathon

$\text{Problem 10:}$

Consider $2009$ cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of $50$ consecutive cards, the leftmost of which is showing gold, and turning them all over, so those with showed gold now show black and vice versa. The last player who can make a legal move wins.

(a) Does the game necessarily end?
(b) Does there exist a winning strategy for the starting player?
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

### Re: Combi Marathon

Thanic Nur Samin wrote:$\text{Problem 10:}$

Consider $2009$ cards, each having one gold side and one black side, lying in parallel on a long table. Initially all cards show their gold sides. Two players, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of $50$ consecutive cards, the leftmost of which is showing gold, and turning them all over, so those with showed gold now show black and vice versa. The last player who can make a legal move wins.

(a) Does the game necessarily end?
(b) Does there exist a winning strategy for the starting player?
This is IMO 2009 C1 >,>

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

### Re: Combi Marathon

By general consensus among most participants in this marathon, we won't be posting a solution of the above well-known problem. You can check for solutions here.

$\text{Problem 11}$

Let $a_1,a_2,...,a_9$ be nine real numbers, not necessarily distinct, with average $m$. Let $A$ denote the number of triples $1 \le i < j < k \le 9$ for which $a_i + a_j + a_k \ge 3m$. What is the minimum possible value of $A$?

Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

### Re: Combi Marathon

$\text{Solution to problem 11}$

Translate the whole sequence by $-m$. That way, the nine terms sum to $0$ and the triples that sum to a non-negative number contribute to $A$.

Now, take all the $\dbinom{9}{3}=84$ triples. We can arrange them into sets of $3$ triples so that the union of the triples contain all $9$ numbers. Note that from all sets we get at least $1$ term that is non-negative.

So, we get that $A\ge \dfrac{84}{3}=28$.

Now, take the numbers $-1,-1,-1,-1,-1,-1,-1,-1,6$. So, there are exactly $\dbinom{8}{2}=28$ triples that has a non-negative sum, since we must take $6$ to make the sum non-negative.

So, the minimum possible value of $A$ is $28$.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

### Re: Combi Marathon

$\text{Problem 12}$

On a circle there are $150$ red and $150$ blue arcs given in such a way that each red arc intersects each blue one. Prove that there exists a point contained by at least $150$ of the given colored arcs.
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

nahin munkar
Posts: 81
Joined: Mon Aug 17, 2015 6:51 pm
Location: banasree,dhaka

### Re: Combi Marathon

Another solution to problem 11 :

If we divide the real numbers in $3$-triples, we get one of them is at least $3$m by PHP. And same, we get at least $\dfrac{1}{3}$ of the triples sum to at least $3$m.

As the number of triples is $^9C_3 =84$, so, $A \ge \dfrac{1}{3} \times 84 =28$. So, the minimum possible value of $A$ is $28$.

Construction :

It is trivial by @thanic nur samin 's construction. As from 8 $-1$s & 1 $6$, we have to choose 2 $-1$s with 1 $6$ ,
there are $^8C_2 = 28$ triples as desired.
# Mathematicians stand on each other's shoulders. ~ Carl Friedrich Gauss

rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

### Re: Combi Marathon

$\text{Solution } 12$

Below, we distinguish between arc and coloured arc by defining an arc to be any sector of the circumference of the circle. So all coloured arcs are arcs, but not vice versa.

Assume that there is no point that belongs to $n$ coloured arcs.

The way we progress is by noting that if there are two non-intersecting arcs of the same colour, we need a lot of arcs of the other colour to fill in the gaps between the two arcs.

Let's assume WLOG that every two red arcs intersect. Then to avoid a common intersection of all $n$ coloured arcs, we must have three red arcs P,Q,R that have no common points. Now, in order for every red arc to intersect the other, any other red arc needs to fully cover at least two of P,Q,R minus the pairwise intersections. Since there are three such arcs, some arc gets $2\cdot\dfrac{2n-3}{3}+2$ coloured arcs which is greater than $n$. We are done.

So assume that there are two red arcs that do not intersect each other. Note that the circle now has been divided into four arcs - the two red arcs and the arcs between them. Call the red arcs A and B. Call the gaps C and D. Each blue arc must either go through C or D in order to intersect both A and B. Since there are $n$ blue arcs, either C or D has at least $n/2$ arcs. So one of $C$ or $D$ has points which belong to at least $n/2$ arcs. Assume this is C.

Suppose there are blue arcs $B_1$ and $B_2$ that don't intersect. Then they must intersect $C$ and $D$, respectively. Then one of A and B must have at least $n/2$ red arcs. Let this be A. Now take the intersection of the "edges" of arcs A and C - both of which contain at least $n/2$ colours of each colour, hence at least $n$ colours.