По следам старых форумов

[Dendr]

Набрел на форум, который когда-то почитывал, и в частности, раздел задач. Уже 9 лет прошло, как они публиковались там, так что можно и освежить тут.
Может быть, кто-то эту задачу видел и раньше (поиск по условию, по крайней мере, дает ссылки на еще два источника, помимо моего). Но все равно многие наверняка уже забыли.
Итак, условие:

В Вашингтоне, Белом Доме произошел следующий разговор.

Джордж: У меня в Техасе в небольшом квадратном поместье, размеры которого 19х19 миль, есть ранчо. Ранчо прямоугольное, но не квадратное, длины обеих сторон выражаются целым числом миль. Стороны ранчо параллельны сторонам поместья.

Кондолиза: Подождите-ка! Так получилось, что я знаю площадь Вашего ранчо (совершенно случайно, уверяю Вас). А ну-ка, смогу ли я определить его размеры? (Смущенно фыркает). Мне все-таки нужна дополнительная информация. Правда ли, что короткая сторона строго меньше, чем половина длинной стороны? (Джордж отвечает на ее вопрос)

Кондолиза: Тогда я знаю размеры Вашего поместья!

Колин: Мне тоже известна площадь Вашего ранчо (сугубо служебная информация). Но я не слышал, что Вы ответили Кондолизе, однако, я могу тоже назвать длины сторон Вашего ранчо.

Дик: Я не знал площадь этого ранчо, но послушав Вас я знаю размеры этого ранчо.

Так каковы размеры ранчо Джорджа?

Подсказка-разъяснение: подразумевается, что Дик слышал всё, что сказали другие участники, в том числе и ответ Джорджа на вопрос Кондолизы.

[Юляша]

Пока что удалось определить, что Джордж ответил "Да".

Edit

Ответ у меня есть, но на уровне: если ответ существует, то он такой. Доказывать, что это действительно ответ, мне лениво.

[Dendr]

Ну, для решения надо:
1. Честно выписать все возможные площади, предположительно, известные Кондолизе, и попытаться построить из них стороны, исключая квадратные поля. Убедиться, что если число (площадь, выраженная в квадратных милях) - составное, то она не сможет назвать стороны. Всего S может заключаться, как несложно подсчитать, от 6 до 144.

2. Вычеркнуть варианты, которые никак не позволяют Кондолизе узнать стороны при любом ответе Джорджа (например, S=16=1х16=2х8 - Джордж в любом случае ответил бы "Да", и Кондолиза не может определить стороны)

3. Оставить те варианты S, которые на ответ "Да" Джорджа дают одну пару сторон, а на "Нет" - несколько. А также наоборот. Например, S=45 - не годится: если бы было "Да", то стороны 3х15, а если "Нет", то 5х9. Кондолиза бы ответила, но Колин, зная, что S=45 - был бы все еще в затруднении.
Куда как лучше годится S=24: если "Да", то 2х12 или 3х8, если "Нет", то 4х6. Колин не слышал ответа Джорджа, но знает, что Кондолиза поняла стороны поля. Значит, делает он вывод, тот сказал "Нет", и стороны 4х6.

4. На этом шаге остаются 8 возможностей для S. Дик мог их выписать, еще не обращая внимания на ответ, который дал Джордж. Но он знает, что Колин смог дать ответ, поэтому делит их на две группы - в одних случаях Джордж ответил "Нет", в других - "Да". В одной из групп, что немаловажно, ровно одна S.

5. А поскольку Дик понял, какие стороны у поля, то ответ Джорджа был именно тот, который приводил к малой группе. Поэтому решающий задачу может понять, что ответил Джордж, и теперь оказывается на месте Дика, и дает легко ответ:
--->72=4х18<---

[Dendr]

А вот такая задачка. Немного на физику, но математики в ней больше.

Один нумизмат имел стол с правильным круглым отверстием, предназначенного для чернильницы. У того нумизмата были две монеты из чистого золота одинаковой толщины. Большая из монет как раз заполняла все отверстие; меньшая же монета при медленном подталкивании к отверстию начинала крениться в тот самый момент, когда ее край достигал центра отверстия. Большая монета весила 6 унций. Сколько весила малая монета?

[Юляша]

Ну, для решения надо:

У меня ответ был неверный, так как тот факт, что поле - не квадратное, прошел мимо меня(.

Тем не менее, если начать с маленьких полей как минимум с тремя простыми делителями (были проверены значения 12 и 30), становится понятно, каким был ответ Джорджа. Далее, показалось правильным пойти с другого конца - ну и ошибка)).

Задачка про монету выглядит совсем простой. Ответ смотри выше))).

[Dendr]

Ну а тогда такое (кажется, когда-то уже приводил ее здесь, но это было очень давно):

Есть 16 одинаковых шаров. Известно, что ровно 2 из них - радиоактивны. Имеется также прибор, в который можно заложить любое количество шаров, и он показывает, есть ли среди заложенных хотя бы один радиоактивный (то есть у прибора только два показания - "да" и "нет"). За какое наименьшее число измерений можно наверняка найти оба радиоактивных шара?

Понятно, что можно решить "в лоб" - это 15 измерений, а лучше дихотомией найти сначала один шар, потом другой - это 8 измерений. А быстрее никак? Предел (теоретический) снизу доказывается легко, но вот можно ли его достигнуть? И если да, то как?

[Юляша]

Ну а тогда такое (кажется, когда-то уже приводил ее здесь, но это было очень давно):

Есть 16 одинаковых шаров. Известно, что ровно 2 из них - радиоактивны. Имеется также прибор, в который можно заложить любое количество шаров, и он показывает, есть ли среди заложенных хотя бы один радиоактивный (то есть у прибора только два показания - "да" и "нет"). За какое наименьшее число измерений можно наверняка найти оба радиоактивных шара?

Вроде бы достаточно легко доказать, что в 7 измерений (теоретический предел) уложиться не получится: если первым действием заложить 4 или менее шаров, то фэйл, если радиации нет, а если заложить 5 и более, то фэйл, если радиация есть.

[Dendr]

На самом деле можно. Главное, забыть для начала дихотомию, а исхитриться: первые N измерений делаются без оглядки на предыдущие. Честно признаюсь, что до ответа не смог догадаться, но люди находили решение, и очень наглядное, надо сказать.

Долго думал, нельзя ли показать это на примере "найти 2 шара из 6 за 4 измерения" - но вот тут действительно тупик.

[Юляша]

Тогда приведу свое доказательство невозможности полностью, потому что я не вижу в нем ошибки.

Перенумеруем шары от 1 до 16. Всего существует 16*15/2=120 равноправных вариантов выбора двух радиоактивных шаров.
Каждый тест делит множество вариантов на группу допустимых и группу недопустимых, причем при изменении результатов теста группы меняются местами.
Вот каковы размеры этих групп в зависимости от числа шаров в первом измерении:

1: 15 - 105
2: 29 - 91
3: 42 - 78
4: 54 - 66
5: 65 - 55
6: 75 - 45
7: 84 - 36
8: 92 - 28
и т.д.

Видно, что во всех случаях одна из групп содержит более 64 вариантов, что означает, что еще 6-и замеров недостаточно.

Для случая 2 из 6 за 4 измерения возникает та же самая проблема: после первого замера останется не менее 9 возможных случаев.

[Dendr]

Тьфу ты... Шариков то 15 в условии. Недоглядел.

[Шшок]

А вот такая задачка. Немного на физику, но математики в ней больше.

Один нумизмат имел стол с правильным круглым отверстием, предназначенного для чернильницы. У того нумизмата были две монеты из чистого золота одинаковой толщины. Большая из монет как раз заполняла все отверстие; меньшая же монета при медленном подталкивании к отверстию начинала крениться в тот самый момент, когда ее край достигал центра отверстия. Большая монета весила 6 унций. Сколько весила малая монета?

Единственное, что здесь есть от физики - это определение того момента, когда монета теряет устойчивость. Независимо от соотношения диаметров монеты и отверстия, монета начинает крениться тогда, когда длина общей хорды двух окружностей становится равна диаметру монеты (пока общая хорда короче диаметра монеты, монета лежит устойчиво). Если при этом край монеты совпадает с центром отверстия, то диаметр монеты в SQRT 2 раз меньше диаметра отверстия. Соответственно, малая монета весит 3 унции. Вроде, как-то так.

[Dendr]

Соответственно, малая монета весит 3 унции. Вроде, как-то так.

Точно так.