There are $ 3n, n \in \mathbb{Z}^+$ girl students who took part in a summer camp. There were three girl students to be on duty every day. When the summer camp ended, it was found that any two of the $ 3n$ students had just one time to be on duty on the same day. (1) When $ n=3,$ is there any arrangement satisfying the requirement above. Prove yor conclusion. (2) Prove that $ n$ is an odd number.
Problem
Source: CGMO 2002, Problem 2
Tags: modular arithmetic, combinatorics unsolved, combinatorics
jgnr
28.12.2008 01:33
(1) Label the girls $ 1,2,3,4,5,6,7,8,9$.
Day 1: 1,2,3
Day 2: 1,4,5
Day 3: 1,6,7
Day 4: 1,8,9
Day 5: 2,4,8
Day 6: 2,5,6
Day 7: 2,7,9
Day 8: 3,4,7
Day 9: 3,5,9
Day 10: 3,6,8
Day 11: 4,6,9
Day 12: 5,7,8
It is clear that this arrangement satisfies the given requirements.
(2) Assume that there are an even number of girls, namely $ A_1, A_2, A_3, \ldots, A_{2n}$. In one day, $ A_1$ must be with two of them. In another day $ A_1$ must be with another two. And so on. Finally $ A_1$ is already "out of partner". So the number of girls must be odd.
Adriana N.
20.03.2011 18:58
(1)$n=3$ so there are 9 girls. we can note the girls with $1,2,3,4,...,9$.We form distinct groups of three,for example: $(1,2,3);(4,5,6);(7,8,9);(1,4,7);(1,5,8);(1,6,9);(2,4,8);(2,5,9);(3,4,9);(3,5,7);(3,6,8);(2,6,7)$ Is it a good arrangement?
mavropnevma
20.03.2011 20:37
These are Steiner triple systems, see http://mathworld.wolfram.com/SteinerTripleSystem.html. There exists one if and only if $N \equiv 1,3 \pmod{6}$, hence when $N=3n$ for $n \equiv 1 \pmod{2}$.
vsathiam
04.12.2016 04:23
jgnr wrote:
(1) Label the girls $ 1,2,3,4,5,6,7,8,9$.
Day 1: 1,2,3
Day 2: 1,4,5
Day 3: 1,6,7
Day 4: 1,8,9
Day 5: 2,4,8
Day 6: 2,5,6
Day 7: 2,7,9
Day 8: 3,4,7
Day 9: 3,5,9
Day 10: 3,6,8
Day 11: 4,6,9
Day 12: 5,7,8
It is clear that this arrangement satisfies the given requirements.
(2) Assume that there are an even number of girls, namely $ A_1, A_2, A_3, \ldots, A_{2n}$. In one day, $ A_1$ must be with two of them. In another day $ A_1$ must be with another two. And so on. Finally $ A_1$ is already "out of partner". So the number of girls must be odd.
I got the same exact triples in the order you gave
sansgankrsngupta
15.10.2024 10:28
OG! (1) You can easily give a trivial arrangement (2) $n$ is odd $\iff$ $3n-1$ is even Now we prove that $3n-1$ is even. Select one girl out of the $3n$ girls, the girl must have went with 2 other girls on a night which she went and she can't go with the same girl twice, Thus, on every night she goes out, she must chose 2 girls both different from the girls that she has already been on duty with her, since she goes with each of the $3n-1$ other girls exactly once, therefore $3n-1$ girls should be able to be divided into $k$ disjoint pairs of 2 girls, such that the union of those $k$ pairs is $3n-1$. Thus $3n-1=2k$ or it is even. Q.E.D