Школа №57 из 5 в 6 класс 2020 год Вариант 2-2

ШКОЛА №57

2020 год

2 тур

1. Внутри шляпы волшебника живут 100 кроликов: белые, синие и зелёные. Известно, что если произвольно вытащить из шляпы 81 кролика, то среди них обязательно найдутся три разноцветных. Какое наименьшее количество кроликов нужно достать, чтобы среди них точно было два разноцветных?
   
   
2. Имеется 6 шаров, среди которых три радиоактивных, и три детектора, в каждый из которых можно вложить три шара, после чего детектор укажет, есть ли среди них радиоактивный. Известно, что один из детекторов всегда даёт верные показания, второй — всегда неправильные, а третий — как повезёт. Возможно ли определить, какие из шаров радиоактивные?
   
   
3. Штирлиц передавал шифровку в Штаб. Шифровка состоит из 7 цифр 0 и 1. Первые четыре цифры — это сообщение, оставшиеся три вычисляются так:
   • 5-й бит: 1, если сумма первых трёх битов нечётна; 0, если чётна.
   • 6-й бит: 1, если сумма 1-го, 3-го и 4-го битов нечётна; иначе 0.
   • 7-й бит: 1, если сумма 1-го, 2-го и 4-го битов нечётна; иначе 0.
   Например, если Штирлиц передаёт $\texttt{0110}$, то 5-й бит = 0, 6-й = 1, 7-й = 1, и шифровка: $\texttt{0110011}$.
   
   
   1. В штабе получили сообщение $\texttt{1001010}$. Докажите, что в нём есть ошибка.
   2. Восстановите сообщение, которое пытался передать Штирлиц.
   3. Докажите, что какую бы шифровку ни передавал Штирлиц, штаб всегда сможет её восстановить, если известно, что ошибок не больше одной.
   
   
   

Решения задач

1. Внутри шляпы волшебника живут 100 кроликов: белые, синие и зелёные. Известно, что если произвольно вытащить из шляпы 81 кролика, то среди них обязательно найдутся три разноцветных. Какое наименьшее количество кроликов нужно достать, чтобы среди них точно было два разноцветных?
   Решение:
   По условию, при вытаскивании 81 кролика гарантированно присутствуют все три цвета. Это означает, что максимальное количество кроликов одного цвета не превышает 80 (иначе можно было бы вытащить 81 кролика одного цвета).
   Предположим, что распределение цветов: 80, 19, 1. Тогда для гарантии наличия двух цветов нужно вытащить такое количество кроликов, чтобы захватить хотя бы одного представителя второго цвета. В худшем случае сначала вытаскиваются все 80 кроликов одного цвета. Тогда следующая группа из 1 кролика уже будет другого цвета. Однако по условию при 81 кролике уже есть три цвета, значит третий цвет присутствует даже в этом случае.
   Таким образом, минимальное количество кроликов, гарантирующее два цвета, равно 81 - (минимальное количество третьего цвета) + 1. Поскольку третий цвет не может быть менее 1, ответ:
   $\boxed{61}$
2. Имеется 6 шаров, среди которых три радиоактивных, и три детектора, в каждый из которых можно вложить три шара, после чего детектор укажет, есть ли среди них радиоактивный. Известно, что один из детекторов всегда даёт верные показания, второй — всегда неправильные, а третий — как повезёт. Возможно ли определить, какие из шаров радиоактивные?
   Решение:
   Да, возможно. Стратегия:
   1. Проверить все шары тремя детекторами, разделив их на группы по 3 шара. Например, группы ABC, DEF.
   2. Сравнить результаты детекторов. Если два детектора дают одинаковый результат, а третий противоречит, то верным считается результат двух совпадающих (один из них гарантированно честный).
   3. Повторить проверки с разными комбинациями шаров, исключая ложные показания на основе предыдущих результатов.
   Таким образом, можно однозначно определить радиоактивные шары, используя противоречия между детекторами.
   Ответ: $\boxed{Да}$
3. Штирлиц передавал шифровку в Штаб. Шифровка состоит из 7 цифр 0 и 1. Первые четыре цифры — это сообщение, оставшиеся три вычисляются так:
   • 5-й бит: 1, если сумма первых трёх битов нечётна; 0, если чётна.
   • 6-й бит: 1, если сумма 1-го, 3-го и 4-го битов нечётна; иначе 0.
   • 7-й бит: 1, если сумма 1-го, 2-го и 4-го битов нечётна; иначе 0.
   1. В штабе получили сообщение \texttt{1001010}. Докажите, что в нём есть ошибка.
      Решение:
      Первые четыре бита: 1, 0, 0, 1.
      Проверка контрольных битов:
      • 5-й бит: сумма первых трёх (1+0+0) = 1 (нечёт) → должен быть 1. Получено 0 → ошибка.
      • 6-й бит: сумма 1-го, 3-го, 4-го (1+0+1) = 2 (чёт) → должен быть 0. Получено 1 → ошибка.
      • 7-й бит: сумма 1-го, 2-го, 4-го (1+0+1) = 2 (чёт) → должен быть 0. Получено 0 → совпадение.
      Найдены две ошибки в контрольных битах.
      Ответ: Ошибка присутствует.
   2. Восстановите сообщение, которое пытался передать Штирлиц.
      Решение:
      Предположим, ошибка в 5-м бите. Тогда исходные контрольные биты: 1, 0, 0. Проверим:
      • Если исходное сообщение 1,0,0,1: контрольные биты 1,0,0 → шифровка 1001100. Но получено 1001010 → не совпадает.
      • Если ошибка в 1-м бите: исходное сообщение 0,0,0,1. Контрольные биты:
        • 5-й: 0+0+0 = 0 → 0
        • 6-й: 0+0+1 = 1 → 1
        • 7-й: 0+0+1 = 1 → 1
        Шифровка: 0001111 → не совпадает.
      • Если ошибка во 2-м бите: исходное сообщение 1,1,0,1. Контрольные биты:
        • 5-й: 1+1+0 = 2 → 0
        • 6-й: 1+0+1 = 2 → 0
        • 7-й: 1+1+1 = 3 → 1
        Шифровка: 1101001 → не совпадает.
      • Если ошибка в 6-м бите: исходное сообщение 1,0,0,1. Контрольные биты: 1,0,0. Шифровка: 1001100. Исправление 6-го бита с 1 на 0 даёт 1001100 → не совпадает с полученным 1001010.
      • Если ошибка в 4-м бите: исходное сообщение 1,0,0,0. Контрольные биты:
        • 5-й: 1+0+0 = 1 → 1
        • 6-й: 1+0+0 = 1 → 1
        • 7-й: 1+0+0 = 1 → 1
        Шифровка: 1000111 → не совпадает.
      • Верный вариант: исходное сообщение 1,0,1,1. Контрольные биты:
        • 5-й: 1+0+1 = 2 → 0
        • 6-й: 1+1+1 = 3 → 1
        • 7-й: 1+0+1 = 2 → 0
        Шифровка: 1011010. Исправление 3-го бита с 0 на 1 даёт совпадение с полученным сообщением (ошибка в 3-м бите).
      Ответ: $\boxed{1011}$
   3. Докажите, что какую бы шифровку ни передавал Штирлиц, штаб всегда сможет её восстановить, если известно, что ошибок не больше одной.
      Доказательство:
      Контрольные биты образуют систему проверок на чётность, позволяющую определить позицию ошибки. Каждый контрольный бит проверяет уникальную комбинацию исходных битов:
      • 5-й: биты 1,2,3
      • 6-й: биты 1,3,4
      • 7-й: биты 1,2,4
      При возникновении одной ошибки несовпадение контрольных битов укажет на конкретный бит. Например:
      • Ошибка в бите 1: влияет на все три контрольных бита.
      • Ошибка в бите 2: влияет на 5-й и 7-й.
      • Ошибка в бите 3: влияет на 5-й и 6-й.
      • Ошибка в бите 4: влияет на 6-й и 7-й.
      • Ошибка в контрольных битах: влияет только на один из них.
      Таким образом, по комбинации несовпадений можно точно определить, где произошла ошибка, и исправить её.