A room has $2017$ boxes in a circle. A set of boxes is friendly if there are at least two boxes in the set, and for each boxes in the set, if we go clockwise starting from the box, we would pass either $0$ or odd number of boxes before encountering a new box in the set. $30$ students enter the room and picks a set of boxes so that the set is friendly, and each students puts a letter inside all of the boxes that he/she chose. If the set of the boxes which have $30$ letters inside is not friendly, show that there exists two students $A, B$ and boxes $a, b$ satisfying the following condition. (i). $A$ chose $a$ but not $b$, and $B$ chose $b$ but not $a$. (ii). Starting from $a$ and going clockwise to $b$, the number of boxes that we pass through, not including $a$ and $b$, is not an odd number, and none of $A$ or $B$ chose such boxes that we passed.
Problem
Source: 2017 FKMO Day 2 Problem 6
Tags: combinatorics
rkm0959
26.03.2017 07:56
Sorry for my English To koreans - how should I translate 어울린다?
guangzhou-2015
27.03.2017 08:06
any solution
smk17048
28.03.2017 08:25
rkm0959 wrote: Sorry for my English To koreans - how should I translate 어울린다? I think friendly is fine.
smk17048
28.03.2017 14:01
I tried to write down all proof but b/c my poor ability, I couldn't make it. [sketch]
Let those boxes and students do not exist.
Then pick any two students and name a set of boxes that those two pick A1 and A2.
When box a and box b are in close distance in set X, this mean number of non-X boxes between a and b is zero.
Define even group as a group which is consisted of even number of boxes in close distance.
Define X1 as a set of even group of A1. Define X2 as a set of even group of A2.
When set X's element a and b is nearby, this mean there isn't any X's element either in clockwise or counter clockwise way.
Claim 1. A1 ∩ A2 is friendly set.
pf) let A1 ∩ A2 is not friendly set.
case 1) n(A1 ∩ A2)>=2
Then there exists two nearby elements of A1 ∩ A2 which has even number(not 0) of boxes between them.
Let those two J and K.
By lemma1, there are odd number of X1's element between J and K.
1
Then divide boxes between J and K into sections by A2's element. Also J and K are nearby elements of A1 ∩ A2, so there isn't any element of A1 ∩ A2 between them. By 1, there is one section where odd number of X1's element is included.
By lemma1, there exist two nearby A2's element which have even number(not 0) number of boxes between them.
Since A2 is friendly set, it's impossible.
case 2) n(A1 ∩ A2)=1
case 3) n(A1 ∩ A2) =0 By using lemma, these two cases are impossible.
When set X and Y follows Rule 1, this mean there isn't any element x,y such that X include x but not y, and Y include y but not x.
When set X and Y follows Rule 2, this mean starting from x and going clockwise to y, the number of boxes we pass through (not include x,y) is always odd number.
Claim 2. When friendly set A(i) and A(j) always follow rule 1 or 2 ( i,j<=30),
and if (A1 ∩ A2 ∩ A3 ∩ .... ∩ A(n)) is friendly set, (A1 ∩ A2 ∩ .... ∩ A(n+1)) is also friendly set.
pf)
case 1) If A(i) and A(j) follows rule 1, A(i) ∩ A(j) = A(i) or A(j) which means (A1 ∩ A2 ∩ .... ∩ A(n+1)) can be expressed by intersection of n A(x) which is friendly set.
case 2) all A(i) and A(j) follows rule 2.
Let A1 ∩ A2 = B1.
By lemma 2, B1 and all A3 to A(n+1) follows rule 2. By claim 1, B1 is friendly set.
So (A1 ∩ A2 ∩ .... ∩ A(n+1)) can be expressed in intersection of n friendly groups which follow rule 2.
claim 1 shows when n=2, A1 ∩ A2 is friendly set. So by claim 1 and 2, (A1 ∩ A2 ∩ .... ∩ A30) is friendly set. This is impossible.
lemma 1) When number of box between elements of two friendly set X and Y >=1, number of box between two nearby X elements is odd when
there's even number of Y's even group between them, and even when there's odd number of them.
lemma 2) When three friendly set X,Y,Z exists and (X,Y), (Y,Z), (Z,X) all follow rule 2, (X∩Y,Z) follows rule 2.
proof of 2 lemmas and claim 1's case 2 and 3 are easy but it's too hard to write it down in English.
I hope you understand me.
PARISsaintGERMAIN
07.04.2017 23:48
For 어울린다, people usually use "Hang out".