Determine all natural numbers $n$ for which there is a partition of $\{1,2,...,3n\}$ in $n$ pairwise disjoint subsets of the form $\{a,b,c\}$, such that numbers $b-a$ and $c-b$ are different numbers from the set $\{n-1, n, n+1\}$.
Problem
Source: Serbian National Olympiad 2013, Problem 4
Tags: induction, pigeonhole principle, combinatorics proposed, combinatorics
24.04.2013 19:17
Hi ; Use induction on $ n $ and I get $ n $ must be even Best Regard
24.04.2013 19:33
all natural even numbers n is answer of the problem for odd numbers first partition 1,2,3,..,3n in 3 part : A={1,2,..,n} and B={n+1,n+2,...,2n} and C={2n+1,...,3n} prove that in subset {a,b,c} such that {a-b,b-c} is subset of {n-1,n,n+1}and (a-b,b-c) different and (a-b) larger than (b-c) then {a},{b},{c} are subsets of C,B,A respectively. then by induction prove than n cannot be odd.
02.05.2013 13:06
tweener wrote: mojyla222 wrote: all natural even numbers n is answer of the problem for odd numbers first partition 1,2,3,..,3n in 3 part : A={1,2,..,n} and B={n+1,n+2,...,2n} and C={2n+1,...,3n} prove that in subset {a,b,c} such that {a-b,b-c} is subset of {n-1,n,n+1}and (a-b,b-c) different and (a-b) larger than (b-c) then {a},{b},{c} are subsets of C,B,A respectively. then by induction prove than n cannot be odd. What is a,b,c in your solution ? Anyone has alternative solutions ? a,b,c are different natural numbers between 1,3n
02.10.2014 07:42
Here's a solution that hopefully makes sense. The set containing $1$ is $\{1, n, 2n\}, \{1, n, 2n+1\}, \{1, n+1, 2n\}, \{1, n+1, 2n+2\}, \{1, n+2, 2n+1\}$ or $\{1, n+2, 2n+2\}$. In the first case, we have $n$ consecutive numbers, namely $\{2n+1, 2n+2, \cdots, 3n\}$ that must belong in the remaining $n-1$ sets; thus by the Pigeonhole Principle two of them belong to the same set. As no two numbers in a set can have an absolute difference of less than $n-1$, $2n+1$ and $3n$ must be in the same set. The third number in this set is $(2n+1)-n$ or $(2n+1)-(n+1)$ i.e. $n+1$ or $n$. $n$ has already been used, so the set must be $\{n+1, 2n+1, 3n\}$. So we are now left with the numbers $\{2, 3, \cdots, n-1, n+2, n+3, \cdots, 2n-1, 2n+2, 2n+3, \cdots, 3n-1\}$ to be split into $n-2$ sets. We can apply an argument similar to the above for each of the other 5 cases, and we find that the problem is equivalent to dividing $\{1, 2, \cdots, n-2, n+1, n+2, \cdots, 2n-2, 2n+1, 2n+2, \cdots 3n-2\}$ into $n-2$ sets (here we have shifted the terms up or down by some constant amount). Now write these numbers into a table with $3$ rows and $n-2$ columns, with $1, 2, \cdots, n-2$ in the first row in that order, $n+1, n+2, \cdots, 2n-2$ in the second row in that order, $2n+1, 2n+2, \cdots, 3n-2$ in the third row in that order. We must find $n-2$ "snakes" going from the first row to the third row that cover all squares. Each snake cannot be a straight line and if it occupies the $i$-th square in a row, it can only occupy the $i-1, i$ or $i+1$-th square in the next row. It doesn't take long to see that two snakes must occupy every square in the first two columns, hence we obtain that $n$ works if and only if $n-2$ does. This is probably the induction thing that was touched upon in the other solution in this thread.
04.10.2014 16:59
Any partition corresponds to the partition of a regular polygon $P_1P_2 \cdots P_{3n}$ into triangles $A_iB_iC_i$, each of which has angles (measured in degrees) $\frac{n-1}{3n} 180, \frac{n}{3n} 180, \frac{n+1}{3n}$. We may number the vertices in such a way so that $A_1, B_1, C_1$ corresponds to $P_n, P_{2n-1}, P_{3n}$ in some permutation. WLOG, we may assume that $A_1, B_1, C_1 = P_n, P_{2n-1}, P_{3n}$ in that order. One of the remaining $n-1$ triples must contain two numbers in the interval $[2n, 3n-1 ]$: it follows that there exists a triplet $\{ n-1, 2n, 3n-1 \}$. Every other triple contain one number from each interval $[ 1, n-2 ], [ n+1, 2n-2 ], [2n+1, 3n-2 ]$. Hence the mapping $\{a, b, c \} \to \{a, b-2, c-4 \}$ yields an appropriate partition of $\{1,2, \cdots, 3n\}$. This is clearly impossible for $n-1$, so a simple induction implies that it is impossible for all odd $n$, but if $n=2m$, then the triples $\{2i-1, 2i+n, 2i+2n-1 \}$ and $\{2i, 2i+n-1, 2i+2n \}$, for all $i=1 \cdots m$, satisfy the requirements.