Page 5 of 5

Re: Combi Marathon

Posted: Fri Mar 31, 2017 10:11 pm
by rah4927
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$.

Re: Combi Marathon

Posted: Tue Apr 11, 2017 10:30 pm
by ahmedittihad
Solution? And another problem please.

Re: Combi Marathon

Posted: Sun Aug 20, 2017 10:07 pm
by Nirjhor
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.

Re: Combi Marathon

Posted: Fri Dec 01, 2017 7:30 pm
by ahmedittihad
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.

Re: Combi Marathon

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

Re: Combi Marathon

Posted: Wed Feb 14, 2018 1:06 pm
by SN.Pushpita
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. :)

Re: Combi Marathon

Posted: Wed Feb 14, 2018 1:20 pm
by SN.Pushpita
First one has holes but the second one is correct.

Re: Combi Marathon

Posted: Wed Feb 14, 2018 1:57 pm
by samiul_samin
Problem 21. Find the number of subsets of {1,2,3,4,...,2000},the sum of whose elements is divisible by 5 .

Re: Combi Marathon

Posted: Fri Feb 16, 2018 9:23 am
by samiul_samin
21. Source:
102 combinatorial problems
Hint
Use relvant polynomials
Answer
$\dfrac 15(2^{2000}+2^{402})$