|
|
 |
Условие
В строку в неизвестном порядке записаны все целые числа от 1 до 100. За один вопрос про любые 50 чисел можно узнать, в каком порядке относительно друг друга записаны эти 50 чисел. За какое наименьшее число вопросов наверняка можно узнать, в каком порядке записаны все 100 чисел?
Решение
Для нахождения искомого порядка a1, a2, ..., a100 расположения чисел в строке
необходимо, чтобы каждая из пар (ai, ai+1), i = 1, 2, ..., 99, встречалась хотя бы в одном из наборов, о которых задают вопросы, в противном случае для двух последовательностей a1, ..., ai, ai+1, ..., a100 и a1, ..., ai+1, ai, a100 все ответы
будут одинаковы.
Докажем, что после любых двух заданных вопросов может возникнуть ситуация, когда для охвата всех пар соседних чисел (еще не охваченных) потребуется задать еще не менее трёх вопросов.
Пусть k1, k2, ..., k50 – порядок расположения чисел, про которые задан первый вопрос, l1, l2, ..., l50 – порядок расположения чисел, про которые задан второй вопрос. Построим набор a1, a2, ..., a100, для которого мы не сможем, задав еще два вопроса, однозначно установить порядок расположения в нём чисел. Рассмотрим ситуацию, когда все числа, названные как в первом, так и во втором вопросе, оказались в ответах на одних и тех же местах.
В качестве искомого набора возьмём набор, у которого ki, li ∈ {a2i–1, ai}, i = 1, 2, ..., 50, и, кроме того, в каждой четвёрке (a4m–3, a4m–2, a4m–1, a4m),
m = 1, 2, ..., 25, в первых двух вопросах не было сравнений соседних пар чисел из этой четверки. Покажем, что такой набор существует.
Пусть X – множество чисел, не встречавшихся в первых двух вопросах. Возможны случаи:
k2m–1 = l2m–1, k2m = l2m,
k2m–1 = l2m–1, k2m ≠ l2m,
k2m–1 ≠ l2m–1, k2m ≠ l2m,
k2m–1 ≠ l2m–1, k2m = l2m,
Для этих случаев построим четвёрки (a4m–3, a4m–2, a4m–1, a4m) следующим образом: (k2m–1, *, *, k2m), (k2m–1, *, k2m, l2m), (k2m–1, l2m–1, k2m, l2m),
(k2m–1, l2m–1, *, k2m), где в качестве * можно взять любое из чисел множества X, не встречавшееся в вопросах и при построении предыдущих четвёрок.
Тем самым показано, что после двух вопросов возможна (независимо от желания спрашивающего) ситуация, когда ни одна из пар (ai, ai+1) при i, не кратном 4, не охвачена. Каждое из 100 чисел входит при этом хотя бы в одну неохваченную пару, и, следовательно, должно фигурировать по крайней мере в одном из последующих вопросов.
Допустим, что в данной ситуации за два вопроса можно охватить все неохваченные пары; тогда каждое из 100 чисел должно фигурировать ровно в одном из таких вопросов. Рассмотрев четвёрки вида (a4i–3, a4i–2, a4i–1, a4i), i = 1, 2, ..., 25, заметим, что если одно из чисел такой четвёрки будет фигурировать в вопросе, то и остальные три тоже (иначе не все пары соседних чисел в этой четвёрке будут охвачены). Но тогда количество чисел в наборе, о котором задаётся вопрос, должно делиться на 4. Поскольку 50 не делится на 4, то имеем противоречие.
Итак, за четыре вопроса наверняка определить расположение чисел 1, 2, ..., 100 в строке нельзя.
Покажем, как сделать это за пять вопросов. Первый вопрос задаём про набор M1 = {1, 2, ..., 50}, второй – про набор M2 = {51, 52, ..., 100}. Набор M3 будет состоять из 25 самых левых чисел набора M1 и 25 самых левых чисел набора M2, а набор M4 – из 25 самых правых чисел набора M1 и 25 самых правых набора M2. Ответ на вопрос о наборе M3 определит, очевидно, числа a1, a2, ..., a25, а о наборе M4 – числа a76, a77, ..., a100. Пятым вопросом определяем расположение остальных 50 чисел в искомой строке.
Ответ
За пять вопросов.
