Разделы 
Дополнительно
Задача по математике - 1857
2019-01-21 
В строку в неизвестном порядке записаны все целые числа от 1 до 100. За один вопрос про любые 50 чисел можно узнать, в каком порядке относительно друг друга записаны эти 50 чисел. За какое наименьшее число вопросов наверняка можно узнать, в каком порядке записаны все 100 чисел?
Решение:
Для нахождения искомого порядка $a_1, a_2, \cdots, a_{100}$ расположения чисел в строке необходимо, чтобы каждая из пар $(a_i, a_{i+1}), i = 1, 2, \cdots, 99$, встречалась хотя бы в одном из наборов, о которых задают вопросы, в противном случае для двух последовательностей $a_1, \cdots , a_i, a_{i+1}, \cdots , a_{100}$ и $a_1, \cdots, a_{i+1}, a_i, \cdots, a_{100}$ все ответы будут одинаковы. Докажем, что после любых двух заданных вопросов может возникнуть ситуация, когда для охвата всех пар соседних чисел (еще не охваченных) потребуется задать еще не менее трех вопросов. Пусть $k_1, k_2, \cdots, k_{50}$ - порядок расположения чисел, про которые задан первый вопрос, $k_1^{\prime}, k_2^{\prime}, \cdots, k_{50}^{\prime}$ - порядок расположения чисел, про которые задан второй вопрос. Построим набор $a_1, a_2,\cdots, a_{100}$, для которого мы не сможем, задав еще два вопроса, однозначно установить порядок расположения в нем чисел. Рассмотрим ситуацию, когда все числа, названные как в первом, так и во втором вопросе, оказались в ответах на одних и тех же местах.
В качестве искомого набора возьмем набор, у которого $k_i, k_i^{\prime} \in \{ a_{2i-1},a_{2i} \}, i = 1, 2, \cdots, 50$, и, кроме того, в каждой четверке $(a_{4m-3}, a_{4m-2}, a_{4m-1}, a_{4m}), m = 1, 2, \cdots, 25$, в первых двух вопросах не было сравнений соседних пар чисел из этой четверки. Покажем, что такой набор существует. Пусть $X$ - множество чисел, не встречавшихся в первых двух вопросах. Возможны случаи: 1) $k_{2m-1} = k_{2m-1}^{\prime}, k_{2m} = k_{2m}^{\prime}$, 2) $k_{2m-1} = k_{2m-1}^{\prime}, k_{2m} \neq k_{2m}^{\prime}$, 3) $k_{2m-1} \neq k_{2m-1}^{\prime}, k_{2m} \neq k_{2m}^{\prime}$, 4)$k_{2m-1} \neq k_{2m-1}^{\prime}, k_{2m} = k_{2m}^{\prime}$.
Для этих случаев построим четверки $(a_{4m-3},a_{4m-2},a_{4m-1},a_{4m})$ следующим образом: 1) $(k_{2m-1}, *, *, k_{2m})$, 2) $(k_{2m-1}, *, k_{2m}, k_{2m}^{\prime})$, 3)
$(k_{2m-1}, k_{2m-1}^{\prime}, k_{2m}, k_{2m}^{\prime})$, 4) $(k_{2m-1}, k_{2m-1}^{\prime}, *, k_{2m})$, где в качестве * можно взять любое из чисел множества $X$, не встречавшееся в вопросах и при построении предыдущих четверок.
Тем самым показано, что после двух вопросов возможна (независимо от желания спрашивающего) ситуация, когда ни одна из пар $(a_i: a_{i+1})$ при $i$, не кратном 4, не охвачена. Каждое из 100 чисел входит при этом хотя бы в одну неохваченную пару, и, следовательно, должно фигурировать по крайней мере в одном из последующих вопросов.
Допустим, что в данной ситуации за два вопроса можно охватить все неохваченные пары; тогда каждое из 100 чисел должно фигурировать ровно в одном из таких вопросов. Рассмотрев четверки вида $(a_{4i-3}, a_{4i-2}, a_{4i-1}, a_{4i}), i = 1,2,\cdots, 25$, заметим, что если одно из чисел такой четверки будет фигурировать в вопросе, то и остальные три тоже (иначе не все пары соседних чисел в этой четверке будут охвачены). Но тогда количество чисел в наборе, о котором задается вопрос, должно делиться на 4. Поскольку 50 не делится на 4, то имеем противоречие.
Итак, за 4 вопроса наверняка определить расположение чисел $1, 2, \cdots, 100$ в строке нельзя. Покажем, как сделать это за 5 вопросов.
Первый вопрос задаем про набор $M_1 = \{ 1, 2, \cdots , 50 \}$, второй - про набор $M_2 = \{51, 52, \cdots, 100 \}$. Набор $M_3$ будет состоять из 25 самых левых чисел набора $M_1$ и 25 самых левых чисел набора $M_2$, а набор $M_4$ - из 25 самых правых чисел набора $M_1$ и 25 самых правых набора $M_2$. Ответ на вопрос о наборе $M_3$ определит, очевидно, числа $a_1, a_2, \cdots, a_{25}$, а о наборе $M_4$ - числа $a_{76}, a_{77}, \cdots, a_{100}$. Пятым вопросом определяем расположение остальных 50 чисел в искомой строке.
Ответ. За пять вопросов.
В строку в неизвестном порядке записаны все целые числа от 1 до 100. За один вопрос про любые 50 чисел можно узнать, в каком порядке относительно друг друга записаны эти 50 чисел. За какое наименьшее число вопросов наверняка можно узнать, в каком порядке записаны все 100 чисел?
Решение:
Для нахождения искомого порядка $a_1, a_2, \cdots, a_{100}$ расположения чисел в строке необходимо, чтобы каждая из пар $(a_i, a_{i+1}), i = 1, 2, \cdots, 99$, встречалась хотя бы в одном из наборов, о которых задают вопросы, в противном случае для двух последовательностей $a_1, \cdots , a_i, a_{i+1}, \cdots , a_{100}$ и $a_1, \cdots, a_{i+1}, a_i, \cdots, a_{100}$ все ответы будут одинаковы. Докажем, что после любых двух заданных вопросов может возникнуть ситуация, когда для охвата всех пар соседних чисел (еще не охваченных) потребуется задать еще не менее трех вопросов. Пусть $k_1, k_2, \cdots, k_{50}$ - порядок расположения чисел, про которые задан первый вопрос, $k_1^{\prime}, k_2^{\prime}, \cdots, k_{50}^{\prime}$ - порядок расположения чисел, про которые задан второй вопрос. Построим набор $a_1, a_2,\cdots, a_{100}$, для которого мы не сможем, задав еще два вопроса, однозначно установить порядок расположения в нем чисел. Рассмотрим ситуацию, когда все числа, названные как в первом, так и во втором вопросе, оказались в ответах на одних и тех же местах.
В качестве искомого набора возьмем набор, у которого $k_i, k_i^{\prime} \in \{ a_{2i-1},a_{2i} \}, i = 1, 2, \cdots, 50$, и, кроме того, в каждой четверке $(a_{4m-3}, a_{4m-2}, a_{4m-1}, a_{4m}), m = 1, 2, \cdots, 25$, в первых двух вопросах не было сравнений соседних пар чисел из этой четверки. Покажем, что такой набор существует. Пусть $X$ - множество чисел, не встречавшихся в первых двух вопросах. Возможны случаи: 1) $k_{2m-1} = k_{2m-1}^{\prime}, k_{2m} = k_{2m}^{\prime}$, 2) $k_{2m-1} = k_{2m-1}^{\prime}, k_{2m} \neq k_{2m}^{\prime}$, 3) $k_{2m-1} \neq k_{2m-1}^{\prime}, k_{2m} \neq k_{2m}^{\prime}$, 4)$k_{2m-1} \neq k_{2m-1}^{\prime}, k_{2m} = k_{2m}^{\prime}$.
Для этих случаев построим четверки $(a_{4m-3},a_{4m-2},a_{4m-1},a_{4m})$ следующим образом: 1) $(k_{2m-1}, *, *, k_{2m})$, 2) $(k_{2m-1}, *, k_{2m}, k_{2m}^{\prime})$, 3)
$(k_{2m-1}, k_{2m-1}^{\prime}, k_{2m}, k_{2m}^{\prime})$, 4) $(k_{2m-1}, k_{2m-1}^{\prime}, *, k_{2m})$, где в качестве * можно взять любое из чисел множества $X$, не встречавшееся в вопросах и при построении предыдущих четверок.
Тем самым показано, что после двух вопросов возможна (независимо от желания спрашивающего) ситуация, когда ни одна из пар $(a_i: a_{i+1})$ при $i$, не кратном 4, не охвачена. Каждое из 100 чисел входит при этом хотя бы в одну неохваченную пару, и, следовательно, должно фигурировать по крайней мере в одном из последующих вопросов.
Допустим, что в данной ситуации за два вопроса можно охватить все неохваченные пары; тогда каждое из 100 чисел должно фигурировать ровно в одном из таких вопросов. Рассмотрев четверки вида $(a_{4i-3}, a_{4i-2}, a_{4i-1}, a_{4i}), i = 1,2,\cdots, 25$, заметим, что если одно из чисел такой четверки будет фигурировать в вопросе, то и остальные три тоже (иначе не все пары соседних чисел в этой четверке будут охвачены). Но тогда количество чисел в наборе, о котором задается вопрос, должно делиться на 4. Поскольку 50 не делится на 4, то имеем противоречие.
Итак, за 4 вопроса наверняка определить расположение чисел $1, 2, \cdots, 100$ в строке нельзя. Покажем, как сделать это за 5 вопросов.
Первый вопрос задаем про набор $M_1 = \{ 1, 2, \cdots , 50 \}$, второй - про набор $M_2 = \{51, 52, \cdots, 100 \}$. Набор $M_3$ будет состоять из 25 самых левых чисел набора $M_1$ и 25 самых левых чисел набора $M_2$, а набор $M_4$ - из 25 самых правых чисел набора $M_1$ и 25 самых правых набора $M_2$. Ответ на вопрос о наборе $M_3$ определит, очевидно, числа $a_1, a_2, \cdots, a_{25}$, а о наборе $M_4$ - числа $a_{76}, a_{77}, \cdots, a_{100}$. Пятым вопросом определяем расположение остальных 50 чисел в искомой строке.
Ответ. За пять вопросов.
