## 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: 181
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.

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

### Re: Combi Marathon

Problem 20

A pentagon with all sides equal is given. Prove that the circles having those sides as diameters can't cover the the entire region of that pentagon.
Frankly, my dear, I don't give a damn.

SN.Pushpita
Posts: 11
Joined: Thu Aug 10, 2017 1:44 pm

### Re: Combi Marathon

A pentagon with all sides equal is given. Prove that the circles having those sides as diameters can't cover the the entire region of that pentagon.
Sketch of solution:
This claim is true for convex pentagon.For any convex pentagon,the summation of internal angles is 540 and 540-3×60=2×180. So there are at least 3 internal angles >60.From those angles take 2 whose vertices are of maximum distance among those 3 pairs.Wlog these vertices be A and C.where the convex pentagon is ABCDE.<A,<C are greater than 60 .So angleABE =angleAEB are less than 60.Same goes for angle BCD and BDC.Now
CLAIM 1 .BED is an acute angled triangle.(consider all sides =a and get BE,BD,ED in terms of a and angle ABE and BDC and the rest is easy trig)
The perpendicular bisector of BE and BD intersect at O .O is the circumcenter of BED.M be the midpoint of DE.OM _|_ DE.It is easy to see that O is not contained in any of the circles having AE,AB,BC,CD as diameters.Now if <EBD <45 we are done.This is easy trig using the above mentioned relations and are left to the reader

SN.Pushpita
Posts: 11
Joined: Thu Aug 10, 2017 1:44 pm

### Re: Combi Marathon

SN.Pushpita wrote:
Fri Dec 08, 2017 10:08 am

A pentagon with all sides equal is given. Prove that the circles having those sides as diameters can't cover the the entire region of that pentagon.
Sketch of solution:
This claim is true for convex pentagon.For any convex pentagon,the summation of internal angles is 540 and 540-3×60=2×180. So there are at least 3 internal angles >60.So among them 2 are adjacent. Let them Be A and B. Now let G,H,I,J,K,,F are the midpoints of BC,AB,AE ED DC ,EC respectively. It is easy to show that BE and AC are the largest sides of triangles ABC and ABE. Now let the length of sides of pentagon=2a.So it is easy to see that FG>a ,FI >a.Now assume that FH <a Then AFB>90.So from triangle AFB, F B,FA<2a.Take BFC and AFE triangles. Clearly <BFC >60 and <AFE>60 so AFB <60,a contradiction.
Actually the problem is almost done here.Just now we have to choose a point X on extended DF which satisfies XF <(FG-a),(FI-a) and (FH-a).it is possible to find such a point.and It is easy to prove that this point is satisfies everything. Last edited by SN.Pushpita on Thu Feb 15, 2018 1:32 pm, edited 1 time in total.

SN.Pushpita
Posts: 11
Joined: Thu Aug 10, 2017 1:44 pm

### Re: Combi Marathon

First one has holes but the second one is correct.
Last edited by SN.Pushpita on Wed Feb 14, 2018 9:30 pm, edited 1 time in total.

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

### Re: Combi Marathon

Problem 21. Find the number of subsets of {1,2,3,4,...,2000},the sum of whose elements is divisible by 5 .

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

21. Source:
Hint