Даны 2012 гирек разной массы. Они разбиты на две группы (по 1006 в каждой),внутри которых упорядочены по массе. Предложите способ за 11 взвешиваний найти 1006-ую гирьку по массе среди всех.
Решение:
Пусть $\{p_1,\dots, p_{1006}\}$, $\{q_1,\dots, q_{1006}\}$ данные группы гирек, каждая из которых упорядочена по массе. Можно считать, что первая группа упорядоченна по возрастанию, а вторая -- по убыванию: $p_1<p_2\cdots<p_{1006}$ и $q_1>q_2>\cdots>q_{1006}$.
Определим $x_i=p_i-q_i$.
шаги 1-10: Найдём наибольший номер $i$ такой что $x_i< 0$. По постарению $x_1< p_2\dots < x_{1006}$ и номер $i$ можно найти методом деления пополам (двоичный поиск). Это займёт не более 10 шагов. Обозначим этот номер $i^*$
шаг 11: Искомая гирька --это $\max\{p_{i^*}, q_{i^*+1}\}$
Краткое доказательство может иметь следующий вид.
Если $x_i>0$ ($p_i>q_i$), то гирька $p_i$ может находится только на 1007-м месте и выше (то же верно для всех $p_j$, где $j>i$). С другой стороны, гирька $q_i$ может находится только на 1006-м месте и ниже.
Если $x_i<0$ ($p_i<q_i$), то гирька $p_i$ может находится только на 1006-м месте и ниже (то же верно для всех $p_j$, где $j>i$). С другой стороны, гирька $q_i$ может находится только на 1007-м месте и выше.
Нас интересует гирька с максимальной массой из тех, что находятся на 1006-м месте и ниже.
P.S. Вот и вот, что-то очень похожее.
шаг 11: Искомая гирька --это $\max\{p_{i^*}, q_{i^*+1}\}$
Краткое доказательство может иметь следующий вид.
Если $x_i>0$ ($p_i>q_i$), то гирька $p_i$ может находится только на 1007-м месте и выше (то же верно для всех $p_j$, где $j>i$). С другой стороны, гирька $q_i$ может находится только на 1006-м месте и ниже.
Если $x_i<0$ ($p_i<q_i$), то гирька $p_i$ может находится только на 1006-м месте и ниже (то же верно для всех $p_j$, где $j>i$). С другой стороны, гирька $q_i$ может находится только на 1007-м месте и выше.
Нас интересует гирька с максимальной массой из тех, что находятся на 1006-м месте и ниже.
P.S. Вот и вот, что-то очень похожее.
2 комментария:
Суть задачи вы описали правильно, но, в кратком доказательстве не понятно что имеется ввиду после слов "с другой стороны". По моему мнению, эту задачу проще решить начиная сравнивать 503-ие(p503 и q503) элементы обеих убывающих групп, исключая при дальнейшем сравнении, элементы с 1 по 503 включительно в более легкой гуппе(где легче 503-й элемент) и с 504 по 1006 в другой группе. Затем сравнивать 252-й и т.д..
Согласен, я усложнил доказательство. Но идея состояла в том, что вектор x имеет вид (- - - - - + + + + +), и найдя последний минус мы получим решение.
То, что идёт после слов "с другой стороны" означает (например при x_i>0) что гирька q_i меньше чем как минимум 1006 гирек (в общем наборе).
Я тоже сначала хотел сравнивать упорядоченные наборы, но потом мене пришла в голову эта симметричная конструкция (правда обосновывать её не удобно).
Отправить комментарий