Логика → .02 Невозможность определить гарантированно

а)

Разобьём конфеты на групп по штуки. За хода можно узнать всё про данные конфеты спросив, например, про наборы Если на первые два вопросы ответы будут разными, то мы узнаем, каковы конфеты и а из третьего вопроса поймём, какова Вернувшись к первому вопросу, узнаем и про Если же ответы на первые два вопроса совпадают, значит, и одинаковы. Если ответ на третий вопрос меньше то и невкусные, а если или более, то вкусные; вкусная ли определим по четности этого ответа. И вновь, вернувшись к первому вопросу, определим, какова

Замечание.

Подойдёт и другой набор вопросов, например,

______________________________________________________________________________________________________________________________________________________

б)

Возможны различные решения этого пункта. Приведём решение, позволяющее найти все конфеты даже за ходов. Докажем следующее утверждение: "Если для конфет задача решается за вопросов, то для конфет ее можно решить за вопроса"(Поскольку для одной конфеты достаточно одного вопроса, то для конфет хватит вопросов).

Действительно, пусть есть способ узнать про конфет за вопросов, и пусть первый из этих вопросов задаётся про некоторое множество X. Добавим три конфеты а к списку вопросов добавим три вопроса про множества , и и уберём вопрос про По ответам на эти вопросы можно узнать, каковы конфеты и сколько сладких конфет в (точно так же, как в пункте а, только заменяется на

Если то их синусы различны и положительны.

Пусть найдётся для которого эти три синуса получаются такими же, но в другом порядке. Разберём случаи возможных когда совпадает с одним из написанных на доске чисел:

1) Синусы получаются такие же, как и для в том же порядке.

2) В этом случае и получаются такие же, как и для в том же порядке, а меняет знак, т.е. получается другой набор чисел.

3) В этом случае Однако что не совпадает ни с ни с так как больше каждого из них.

4) В этом случае Однако что не совпадает ни с ни с так как отрицательно.

5) В этом случае Однако что не совпадает ни с ни с так как больше каждого из них.

6) В этом случае Однако что не совпадает ни с ни с так как отрицательно.

Таким образом, единственная возможность получить те же 3 синуса, это случай 1), в котором порядок синусов также совпадает.

Теперь приведём противоположный пример: рассмотрим Тогда С другой стороны, пусть Тогда Таким образом, Петя не сможет отличить эти две ситуации друг от друга.

Приведем два примера, которые подходят под условие, но в одном тяжелее молот, а в другом — костюм. Это будет означать, что однозначно определить, что тяжелее, нельзя, ведь возможные два варианта.

Итак, пусть в первом примере молот весит кг, щит кг, а костюм кг. Все условия соблюдаются, и при этом молот тяжелее костюма.

Во втором примере пусть молот весит кг, щит кг, а костюм кг. Опять же, все условия соблюдаются, но при этом костюм тяжелее молота.

Приведем два различных примера расстановки чисел, при которых тем не менее ответы на все вопросы будут одинаковы. Это расстановки , , , , и , , , , . И в той, и в другой расстановке ответом на любой вопрос будет “”, так как по крайней мере один из сомножителей равен . Тем не менее, расстановки различны, значит, однозначно определить все числа нельзя.

Покажем, как отвечать на вопросы Пина так, чтобы он не смог однозначно определить, находится ли точка внутри квадрата, а также объясним, почему он не сможет это определить.

Отметим произвольную точку внутри квадрата и будем отвечать за Лосяша так, будто бы загадана точка . Заметим, что точка внутри квадрата подходит под все ответы, значит, если Пин смог определить, находится ли точка внутри квадрата, то он считает, что находится.

С другой стороны, после деления плоскости двумя прямыми на части каждая часть бесконечна. Значит, в той части, в которой оказалась загаданная точка, еще точно есть область за пределами квадрата. Тогда, если бы исходно точка была отмечена в этой области, то все ответы Пина были бы такими же, но при этом точка уже не лежала бы внутри квадрата.

Таким образом, мы показали, что при данной последовательности ответов точка может как лежать внутри, так и не лежать, значит, Пин не может действовать так, чтобы после двух вопросов однозначно определить, находится ли точка внутри квадрата.

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

Сначала попробуем найти пару пробирок с ядом и противоядием, не устанавливая, где в этой паре яд, а где противоядие. Для этого огрубим результат лаборатории, убрав из него знак (то есть будем считать, что для каждой смеси лаборатория сообщает результат если в смеси есть яд без противоядия или противоядие без яда, и ноль иначе). Pacсмотрим две строки, соответствующие пробиркам с ядом и противоядием. Их покоординатная сумма, взятая по модулю совпадает со строкой результатов, присланных лабораторией. Следовательно, если все суммы пар строк таблицы, взятые по модулю будут попарно различны, то в результате тестирования мы сможем определить номера строк, соответствующих яду и противоядию.

Такую таблицу можно построить следующим образом. Первую ее строку заполним произвольно. Вторую строку заполняем так, чтобы она не совпадала с первой. Третья и все последующие строки должны удовлетворять двум условиям:

- новая строка не должна совпадать с уже заполненными;

- новая строка должна быть такой, чтобы суммы всех возможных пар построенных строк, взятые по модулю были различны.

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

Следовательно, правила построения таблицы можно переформулировать следующим образом:

- новая строка не должна совпадать с уже заполненными;

- новая строка должна быть такой, чтобы она была отлична от всех возможных сумм троек уже построенных строк.

Число строк длины составленных из нулей и единиц, равно Запретов, даже после заполнения всех строк, будет не более чем

Следовательно, такую таблицу можно построить.

Чтобы определить пару пробирок с ядом и противоядием, найдем все попарные суммы строк таблицы, взятые по модулю Найдем такие строки и что совпадает с огрубленным результатом лаборатории. Пробирки, соответствующие строкам и содержат яд и противоядие. Далее, рассматривая уже настоящий результат лаборатории, мы сможем точно сказать, в какой пробирке яд, a в какой противоядие. Действительно, обязательно найдется хотя бы одна смесь, содержащая либо только яд, либо только противоядие, иначе строки таблицы, соответствующие пробирке с ядом и пробирке с противоядием, будут одинаковыми, что запрещено построением. Тогда по знаку результата для этой смеси мы сможем определить, был в ней яд или противоядие.

Поскольку ребят всего пять, то майку какого-то из трёх цветов (красного, синего или зелёного) носит только один из них. Это не Аркадий, не Дмитрий и не Владимир, так как кроме каждого из них есть ребята и в синей, и в красной, и в зелёной майке. Поэтому майку уникального цвета носит Борис или Григорий. Значит, майки Бориса и Григория — разного цвета.