## Combi Marathon

For discussing Olympiad Level Combinatorics problems
rah4927
Posts: 108
Joined: Sat Feb 07, 2015 9:47 pm

### Re: Combi Marathon

Sketch of solution (with @ahmedittihad) :

Partition $K_n$ into $\lfloor \frac{n-1}{2} \rfloor$ hamiltonian cycles. Since each cycle has length $n$, we can divide each cycle into two paths of length $i$ and $n-i$. This achieves the desired construction.

The proof does need to be modified depending on the parity of $n$ - but it essentially stays the same.

Problem 18 :

Let $m$ be a positive integer, and let $T$ denote the set of all subsets of $\{1, 2, \dots, m\}$. Call a subset $S$ of $T$ $\delta$-good if for all $s_1, s_2\in S$, $s_1\neq s_2$, $|\Delta (s_1, s_2)|\ge \delta m$, where $\Delta$ denotes the symmetric difference (the symmetric difference of two sets is the set of elements that is in exactly one of the two sets). Find the largest possible integer $s$ such that there exists an integer $m$ and $\frac{1024}{2047}$-good set of size $s$.

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

### Re: Combi Marathon

Frankly, my dear, I don't give a damn.

Nirjhor
Posts: 136
Joined: Thu Aug 29, 2013 11:21 pm
Location: Varies.

### Re: Combi Marathon

Problem $\fbox{19}$

C plays a game with A and B. There's a room with a table. First C goes in the room and puts $64$ coins on the table in a row. Each coin is facing either heads or tails. Coins are identical to one another, but one of them is cursed. C decides to put that coin in position $c$. Then he calls in A and shows him the position of the cursed coin. Now he allows A to flip some coins if he wants (he can't move any coin to other positions). After that A and C leave the room and sends in B. If B can identify the cursed coin then C loses, otherwise C wins.

The rules of the game are explained to A and B beforehand, so they can discuss their strategy before entering the room. Find the minimum number $k$ of coin flips required by A so that no matter what configuration of $64$ coins C gives them and where he puts the cursed coin, A and B can win with A flipping at most $k$ coins.
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.

Revive the IMO marathon.