Find all natural numbers $n (n \geq 2)$ such that there exists reals $a_1, a_2, \dots, a_n$ which satisfy \[ \{ |a_i - a_j| \mid 1\leq i<j \leq n\} = \left\{1,2,\dots,\frac{n(n-1)}{2}\right\}. \] Let $A=\{1,2,3,4,5,6\}, B=\{7,8,9,\dots,n\}$. $A_i(i=1,2,\dots,20)$ contains eight numbers, three of which are chosen from $A$ and the other five numbers from $B$. $|A_i \cap A_j|\leq 2, 1\leq i<j\leq 20$. Find the minimum possible value of $n$.
Problem
Source: China Team Selection Test 2002, Day 2, Problem 1
Tags: algebra unsolved, algebra
mathuz
20.10.2013 09:47
here nice proof: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=588&t=290361
MathPanda1
06.04.2016 22:31
How about for the second part? orl wrote: Let $A=\{1,2,3,4,5,6\}, B=\{7,8,9,\dots,n\}$. $A_i(i=1,2,\dots,20)$ contains eight numbers, three of which are chosen from $A$ and the other five numbers from $B$. $|A_i \cap A_j|\leq 2, 1\leq i<j\leq 20$. Find the minimum possible value of $n$.
MathPanda1
08.04.2016 21:23
Anyone have a solution?
Pathological
11.08.2019 22:42
It's strange that the two parts of the problem are completely unrelated... Anyways, here's a (hopefully correct) solution for the second part. We claim that the answer is $n = \boxed{41.}$ For the construction, consider the following $20$ sets:
$A_1 = \{1, 2, 3, 7, 8, 9, 22, 23\}$
$A_2 = \{1, 2, 4, 10, 11, 12, 24, 25\}$
$A_3 = \{1, 2, 5, 13, 14, 15, 26, 27\}$
$A_4 = \{1, 3, 4, 13, 16, 17, 28, 29\}$
$A_5 = \{1, 3, 5, 11, 18, 19, 30, 31\}$
$A_6 = \{1, 4, 5, 9, 20, 21, 32, 33\}$
$A_7 = \{2, 3, 4, 14, 18, 20, 34, 35\}$
$A_8 = \{2, 3, 5, 12, 16, 21, 36, 37\}$
$A_9 = \{2, 4, 5, 8, 17, 19, 38, 39\}$
$A_{10} = \{3, 4, 5, 7, 10, 15, 40, 41\}$
$A_{11} = \{1, 2, 6, 16, 19, 20, 40, 41\}$
$A_{12} = \{1, 3, 6, 12, 15, 21, 38, 39\}$
$A_{13} = \{1, 4, 6, 7, 14, 18, 36, 37\}$
$A_{14} = \{1, 5, 6, 8, 10, 17, 34, 35\}$
$A_{15} = \{2, 3, 6, 10, 11, 17, 32, 33\}$
$A_{16} = \{2, 4, 6, 13, 15, 21, 30, 31\}$
$A_{17} = \{2, 5, 6, 7, 9, 18, 28, 29\}$
$A_{18} = \{3, 4, 6, 8, 9, 19, 26, 27\}$
$A_{19} = \{3, 5, 6, 13, 14, 20, 24, 25\}$
$A_{20} = \{4, 5, 6, 11, 12, 16, 22, 23\}$
Now, we will show that $n = 41$ is indeed minimal. Observe that since $\binom{6}{3} = 20$, for each subset $S \subseteq \{1, 2, 3, 4, 5, 6\}$ of size $3$, there exists a unique $1 \le i \le 20$ with $A_i \cap \{1, 2, 3, 4, 5, 6\} = S.$ In view of this, consider a function $f$ which maps the size three subsets of $\{1, 2, 3, 4, 5, 6\}$ to the $A_i$'s as follows: for a subset $S \subseteq \{1, 2, 3, 4, 5, 6\}$ of size $3$, let $f(S)$ be $A_i$, where $1 \le i \le 20$ is the unique index such that $A_i \cap \{1, 2, 3, 4, 5, 6\} = S.$ Now, let $S_1, S_2, \cdots, S_{10}$ be the $\binom{5}{3} = 10$ subsets of $\{1, 2, 3, 4, 5\}$ of size $3.$ Let $T_1, T_2, \cdots, T_{10}$ denote $f(S_1) / S_1, f(S_2) / S_2, \cdots, f(S_{10}) / S_{10}$ respectively. Observe that $T_i \cap T_j \le 2 - |S_i \cap S_j|$ for every pair of integers $1 \le i < j \le 10.$ Furthermore, observe that $|T_i \cap T_j \cap T_k| = 0$, since one of $|S_i \cap S_j|, |S_j \cap S_k|, |S_k \cap S_i|$ is at least $2.$ Therefore, by PIE, we have that $$|T_1 \cup T_2 \cup \cdots \cup T_{10}| = \sum_{i = 1}^{10} |T_i| - \sum_{1 \le i < j \le 10} |T_i \cap T_j| \ge 5 \cdot 10 - 15 = 35, \qquad (1)$$where we used $|T_i \cap T_j| \le 2 - |S_i \cap S_j|$ in the last part. Therefore, since $T_1 \cup T_2 \cup \cdots \cup T_{10} \subseteq \{7, 8, 9, 10, \cdots, n\}$, $(1)$ yields that $|\{7, 8, 9, 10, \cdots, n\}| \ge 35 \Rightarrow n \ge 41,$ as desired. $\square$
sami1618
09.03.2024 17:22
We claim only $n=2,3,4$ work using $(0,1)$, $(0,1,3)$, and $(0,1,4,6)$. Now consider a $n>4$, let $\frac{n(n-1)}{2}=N$.
WLOG we have $a_1=0$ and $a_2=N$ and all $a_i$ lying in between the two.
Now we will need to produce a difference of $N-1$ so WLOG let $a_3=1$
Now we will need to produce a difference of $N-2$ we can't have $a_4=(2,N-1)$ so we have $a_4=N-2$
Again the only possible value of $a_5$ that creates a difference of $N-3$ and doesn't repeat a difference is $4$ and it also happens to create a difference of $N-4$.
Then we notice there is no possible way to place a difference of $N-5$ without repeating. So we must have $n\leq 4$ giving the above solutions.
The answer is $\fbox{41}$: Refer to the set $A_i$ by the three elements it includes from $1$ to $6$. Denote $v(k)$ to be the set of all $A_i:k\in A_i$. If $v(k)$ includes two complementary $A_i$ such as $(1,2,3)$ and $(4,5,6)$ then it can not have another element. If it does not then it can have at most four elements such as $(1,2,3)$, $(1,4,5)$, $(2,4,6)$, and $(3,5,6)$. Now if you consider the $15$ distinct $v(k):|v(k)|=4$ and two copies of the $10$ distinct $v(k):|v(k)|=2$ then the conditions are satisfied leading to the answer of $41$.
Now let the number of $v(k)$ with $|v(k)|=i$ be $a_i$. Then we get: $${{3}\choose{2}} a_3+{{4}\choose{2}}a_4\leq 90\Rightarrow a_3+2a_4\leq 30$$$$a_1+2a_2+3a_3+4a_4=100$$We want to minimize $a_1+a_2+a_3+a_4$. By subtracting the last two equations we get $a_1+2a_2+2a_3+2a_4\geq 70\Rightarrow a_1+a_2+a_3+a_4\geq 35$. So indeed the lowest $n$ is $35+6=41$.