Combi Marathon

For discussing Olympiad Level Combinatorics problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
Re: Combi Marathon

Unread post by rah4927 » Fri Mar 31, 2017 10:11 pm

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

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

Re: Combi Marathon

Unread post by ahmedittihad » Tue Apr 11, 2017 10:30 pm

Solution? And another problem please.
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

Unread post by Nirjhor » Sun Aug 20, 2017 10:07 pm

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.

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

Re: Combi Marathon

Unread post by ahmedittihad » Fri Dec 01, 2017 7:30 pm

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

Unread post by SN.Pushpita » Fri Dec 08, 2017 10:08 am

ahmedittihad wrote: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.
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

Unread post by SN.Pushpita » Wed Feb 14, 2018 1:06 pm

SN.Pushpita wrote:
Fri Dec 08, 2017 10:08 am
ahmedittihad wrote: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.
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

Unread post by SN.Pushpita » Wed Feb 14, 2018 1:20 pm

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

Unread post by samiul_samin » Wed Feb 14, 2018 1:57 pm

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

Re: Combi Marathon

Unread post by samiul_samin » Fri Feb 16, 2018 9:23 am

21. Source:
102 combinatorial problems
Hint
Use relvant polynomials
Answer
$\dfrac 15(2^{2000}+2^{402})$

Post Reply