Maths Olympiad Prep

Library / /133 of 133

Combinatorics Difficulty 7.8 National olympiad, round 2 Prove it Saudi Arabia

Fatima and Asma are playing the following game. First, Fatima chooses 20132013 pairwise different numbers, called a1,a2,,a2013a_{1}, a_{2}, \ldots, a_{2013}. Then, Asma tries to know the value of each number a1,a2,,a2013a_{1}, a_{2}, \ldots, a_{2013}. At each time, Asma chooses 1i<j20131 \leq i < j \leq 2013 and asks Fatima "What is the set {ai,aj}\{a_{i}, a_{j}\}?" (For example, if Asma asks what is the set {a1,a2}\{a_{1}, a_{2}\}, and a1=17a_{1} = 17 and a2=13a_{2} = 13, Fatima will answer {13,17}\{13, 17\}). Find the least number of questions Asma needs to ask, to know the value of all the numbers a1,a2,,a2013a_{1}, a_{2}, \ldots, a_{2013}.

Solution

Let nn be the number of different questions Asma asks to know the values of each number a1,a2,,a2013a_{1}, a_{2}, \ldots, a_{2013}. Let us make the following remarks:

a. Because Asma needs to know the value of each number aia_{i}, each number aia_{i} must appear at least in one of the sets that Asma chooses to ask about.

b. If Asma chooses a set {ai1,ai2}\{a_{i_{1}}, a_{i_{2}}\}, she needs to choose another set that contains only one of the numbers ai1,ai2a_{i_{1}}, a_{i_{2}}, so that she can distinguish between the values of ai1a_{i_{1}} and ai2a_{i_{2}}.

c. If Asma asks about the sets {ai1,ai2}\{a_{i_{1}}, a_{i_{2}}\} and {ai2,ai3}\{a_{i_{2}}, a_{i_{3}}\}, for different indices i1,i2,i3i_{1}, i_{2}, i_{3}, she will deduce the value of each number ai1,ai2,ai3a_{i_{1}}, a_{i_{2}}, a_{i_{3}}, by taking the intersection of the two sets and their differences.

d. If for some k3k \geq 3, Asma asks about the sets {ai1,ai2},{ai2,ai3},,{aik1,aik}\{a_{i_{1}}, a_{i_{2}}\}, \{a_{i_{2}}, a_{i_{3}}\}, \ldots, \{a_{i_{k-1}}, a_{i_{k}}\}, for different indices i1,i2,,iki_{1}, i_{2}, \ldots, i_{k}, she will deduce the value of each number ai1,ai2,,aika_{i_{1}}, a_{i_{2}}, \ldots, a_{i_{k}} and does not need to ask after this about the set {aik,ai1}\{a_{i_{k}}, a_{i_{1}}\} since she already knows the answer.

From now on, we assume, without loss of generality, that Asma never asks about a set that she already knows.

According to these remarks, we can make a partition of the set {a1,a2,,a2013}\{a_{1}, a_{2}, \ldots, a_{2013}\} into non-empty disjoint subsets A1,A2,,AmA_{1}, A_{2}, \ldots, A_{m} such that two numbers ai,aja_{i}, a_{j} are in the same subset AkA_{k} if and only if there exist sets {ai1,ai2},{ai2,ai3},,{ail1,ail}\{a_{i_{1}}, a_{i_{2}}\}, \{a_{i_{2}}, a_{i_{3}}\}, \ldots, \{a_{i_{l-1}}, a_{i_{l}}\} that Asma has asked about each one of them, and such that ai1=ai,ail=aja_{i_{1}} = a_{i}, a_{i_{l}} = a_{j}. Notice that if ai1,ai2,,aila_{i_{1}}, a_{i_{2}}, \ldots, a_{i_{l}} are different, because of remark (d) they are unique.

For each AiA_{i}, there are exactly #Ai1\#A_{i} - 1 sets in AiA_{i} that Asma has asked about. To see this, fix ai0Aia_{i_{0}} \in A_{i}, and for each ajAia_{j} \in A_{i} with ajai0a_{j} \neq a_{i_{0}}, associate the unique set {ail1,ail}\{a_{i_{l-1}}, a_{i_{l}}\} in the previous paragraph when ai1=ai0,ail=aja_{i_{1}} = a_{i_{0}}, a_{i_{l}} = a_{j} and ai1,ai2,,aila_{i_{1}}, a_{i_{2}}, \ldots, a_{i_{l}} are different. It is not hard to see from remark (d) that this map is a bijection between Ai{ai0}A_{i} \setminus \{a_{i_{0}}\} and the set of subsets of AiA_{i} in the questions of Asma.

Because each set in the questions of Asma is contained exactly in one of the subsets A1,A2,,AmA_{1}, A_{2}, \ldots, A_{m}, we have
n=i=1m(#Ai1)=2013m. n = \sum_{i=1}^{m} (\#A_{i} - 1) = 2013 - m.
Because each set AiA_{i} must contain at least 33 elements (remarks (a) and (b)),
m20133=671 m \leq \left\lfloor \frac{2013}{3} \right\rfloor = 671
This proves that n1342n \geq 1342.

Conversely, if Asma asks about the 13421342 sets
{a3i+1,a3i+2},{a3i+2,a3i+3},fori=0,1,,670 \{a_{3i+1}, a_{3i+2}\}, \{a_{3i+2}, a_{3i+3}\}, \quad \text{for} \quad i = 0, 1, \ldots, 670
she will know the values of all the numbers a1,a2,,a2013a_{1}, a_{2}, \ldots, a_{2013}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.