44
КВА НT 2020/№8
они в автобусе номер 12, а первому волшебнику – 48 лет. Задача решена! Визуализацию решения этой задачи можно посмотреть в [4].
Попробуйте самостоятельно разобраться со следующими вариантами диалога волшебников. 1 (упрощение задачи Конвея, автор – Т.Хованова [1]). A: У меня есть несколько детей, возраст каждого из них – целое положительное число, причем их сумма равна номеру этого автобуса. B: Как интересно! Возможно, если ты скажешь мне число твоих детей, я смогу вычислить их возраста? A: Нет, не сможешь. B: Ага! Наконец-то я узнал, сколько у тебя детей. Каков номер автобуса? 2 (широко известная версия). A: У меня трое детей, возраст каждого из них – целое положительное число, причем их сумма равна номеру этого автобуса, а произведение Но я не могу узнать, сколько им лет! A: Твоя дочь старше всех моих детей. B: Спасибо, этого хватает.
Сколько лет детям волшебника А и каков в этот раз номер автобуса? 3 (авторская версия [3]). A: У меня четверо сыновей, произведение их возрастов равно 180, а сумма их возрастов равна номеру этого автобуса. Б: Все равно информации недостаточно! А: Мой младший сын очень любит мороженое. Б: И этого еще недостаточно. А: А у старшего сегодня день рождения. Б: Спасибо, теперь я знаю, сколько им лет! 4. Волшебник поймал Алису и Боба и сказал каждому целое число от 0 до 10, причем их числа отличаются на единицу (и они об этом знают). Диалог: Алиса: Я не знаю твоего числа, а ты не знаешь моего. Боб: Я не знаю твоего числа, а ты не знаешь моего. Теперь ты знаешь мое число! Какое число было сообщено Бобу?
Литература 1. Tanya Khovanova. Conway’s Wizards. – https: arxiv.org abs 1210.5460 2. С.Артемов, Ю.Гиматов, В.Федоров. Много битов из ничего. – «Квант», К.Кноп. Задача о детях бармена. – https: А.Перепечко. Визуализация задачи Конвея. – https: kvantik.com extra conway-bus
ЛА Б ОРАТОРИ Я « КВА Н ТА »
Загадочные шары
С.НОВИКОВ
ВЖИЗНИ КАЖДОМУ ЧЕЛОВЕКУ порой приходится иметь дело с закрытым (зачастую незнакомым) объектом, о внутреннем устройстве которого можно лишь догадываться. Такие объекты становятся своеобразными «черными ящиками», когда внешнему наблюдателю доступны лишь входные и выходные сигналы (или какие-либо их величины), а что происходит внутри – неизвестно. О поведении черного ящика можно
DOI: https://doi.org/10.4213/kvant20200805
судить, лишь наблюдая реакции выходных величин на изменение входных. Это дает возможность в конечном итоге раскрыть «секрет» такого объекта. Возможно, вы уже встречались с черными ящиками – например, в задачах по электричеству. В нашем же случае в качестве черных ящиков выступают десять одинаковых с виду пластмассовых шаров диаметром 75 мм, внутреннее содержание которых неизвестно. Сначала мы опишем поведение шаров в разных опытах-ситуациях. Попробуйте высказать свои соображения, объясняющие причины того, почему шар (или шары) ведет себя определенным образом в описанной ситуации. И лишь потом читайте наши объяснения.
Эксперименты с шарами
Опыт 1. Шары под номерами 1 и 2 устанавливаются на одинаковой высоте на наклонной плоскости. Затем шарам дается
45
ЛА Б ОРАТОРИ Я
возможность одновременно начать движение вниз. При этом обнаруживается, что один из шаров достигает нижнего положения раньше другого шара. Почему? Опыт 2. Шар под номером 3 сначала удерживается в верхней части наклонной плоскости, а затем освобождается от внешнего воздействия. Шар начинает неспешно скатываться, но делает это очень (и очень) медленно. Что может быть причиной такого неспешного движения? Опыт 3. Шар под номером 4 начинает двигаться из верхнего положения на наклонной плоскости вниз скачками, имитирующими движение тела «шажками». Если шар в верхнем положении повернуть в направлении, перпендикулярном наклонной плоскости, на некоторый угол и вновь отпустить, то поведение шара при скатывании не меняется. Чем может быть вызвано такое скачкообразное движение шара? Опыт 4. В опыте участвуют шары под номерами 5 и 6. Шары помещают на горизонтальную поверхность, и каждый шар самостоятельно устанавливается на этой поверхности в состоянии покоя только в одномединственном положении. Подействовав рукой на вершину каждого шара, отклоняют его на некоторый достаточно большой угол от вертикали. После этого шар под номером 5 очень быстро (!) возвращается в первоначальное состояние. Если этот же шар отклонить от вертикали в какую-нибудь другую сторону и отпустить, то он вновь немедленно возвращается в первоначальное положение. Шар же под номером 6 после устранения внешнего воздействия совершает достаточно длительные по времени колебания и лишь затем возвращается в первоначальное состояние покоя. Кроме того, если оба шара подержать в руках, то первое ощущение говорит о том, что массы шаров достаточно значительные, а внутри шаров не чувствуется какихлибо перемещений тел. Почему же шары так по-разному ведут себя, прежде чем возвратиться в первоначальное состояние покоя? Опыт 5. На фото на рисунке 1 представлен неподвижно лежащий на горизонтальной поверхности шар под номером 7. Рядом с шаром находится отвес, направление нити которого совпадает с белой (назовем ее осевой) линией на корпусе шара. А на фото на рисунке 2 показан этот же шар, который находится в покое на наклонной плоскости,
« КВА Н ТА »
Рис. 1
Рис. 2
не проявляя никаких попыток нарушить состояние неподвижности. Теперь белая линия на корпусе шара не параллельна нити отвеса, а направлена перпендикулярно наклонной плоскости. При этом шар может находиться в неподвижности на наклонной
46
КВА НT 2020/№8
плоскости, имеющей и другие (большие) углы наклона. И снова осевая линия шара перпендикулярна наклонной плоскости. Почему возможно такое поведение шара на наклонной плоскости? Опыт 6. Шар под номером 8 размещается на наклонной плоскости, и он остается там в неподвижности в том положении, в котором его поместили на плоскость. Если шар, не отрывая от наклонной плоскости, повернуть на некоторый угол в любую сторону, то он останется неподвижным и не предпримет никаких попыток к скатыванию. Такие действия можно повторить неоднократно, однако поведение шара (его неподвижность на плоскости) останется неизменным. Почему? Опыт 7. Шар под номером 9 (фото на рисунке 3) подвешен с помощью нити к лапке штатива. К корпусу шара с помощью скотча прикреплена пальчиковая батарейка, а на корпусе шара имеются два отверстиягнезда для подключения этой батарейки к шару. Если с помощью подводящих проводов соединить шар с батарейкой, то шар начинает вращаться либо по часовой стрелке, либо против (при наблюдении сверху). Если же поменять полярность батарейки, то
шар будет вращаться в другую сторону. Что может быть причиной такого двойственного поведения шара? Опыт 8. Шар под номером 10 с помощью скотча прикреплен к небольшой щетке для чистки одежды (фото на рисунке 4). Щетка с шаром находятся на горизонтальной поверхности, а на корпусе шара опять имеются
Рис. 4
гнезда для подключения его к пальчиковой батарейке. Если такое подключение осуществить, то шар начинает вибрировать, а щетка начинает двигаться в определенном направлении. При смене полярности батарейки направление движения щетки с шаром меняется на противоположное. Почему?
Объяснения экспериментов
Рис. 3
Опыт 1. Ответ «лежит на поверхности»: масса одного шара больше массы другого. Быстрее скатится с наклонной плоскости более легкий шар, в нашем случае он пустой. У массивного шара момент инерции больше, чем у пустого, и ему для придания вращения нужна значительно большая энергия. Для демонстрации этого опыта у нас внутрь второго шара был помещен кусок поролона с большим числом вкрапленных в него массивных свинцовых шариков-дробинок. Опыт 2. Внутри шара может находиться «сыпучее» вещество. При скатывании шара вещество медленно перемещается из более верхнего положения в нижнее. Это и замедляет движение шара вниз по наклонной плоскости. В нашем варианте для этого использовались мелкие (не более 1 мм в диаметре) свинцовые дробинки.
47
ЛА Б ОРАТОРИ Я
Некогда я увидел этот опыт на внеклассном мероприятии учителей физики в гимназии п. Удельная Московской области. В их варианте внутрь шара был помещен жидкий мед. Эффект опыта был впечатляющий.
Опыт 3. Внутрь нашего шара был помещен массивный кусок свинца кубической формы. При скатывании шара с наклонной плоскости куб переворачивался. Это и придавало шару скачкообразный характер движения. Опыт 4. Оба шара демонстрируют устойчивое положение равновесия. Устойчивость тела, имеющего точку опоры, имеет место тогда, когда его центр тяжести занимает наиболее низкое положение из всех возможных. Пятый шар иллюстрирует поведение детской игрушки «неваляшки». Внутри шара к его корпусу прикреплен с помощью клея массивный свинцовый груз. В состоянии покоя (устойчивого равновесия) центр масс шара расположен очень низко, недалеко от точки опоры. Кроме того, точка центра масс и точка опоры лежат на одной вертикальной (отвесной и осевой) линии. Когда шар наклоняют, его центр тяжести поднимается и смещается в сторону по отношению к точке опоры и вертикальной линии. Момент силы тяжести относительно точки опоры стремится вернуть шар в первоначальное состояние. Внутри шестого шара чуть ниже его экваториальной плоскости размещен массивный свинцовый диск («бублик» с прямоугольным сечением), который жестко прикреплен к корпусу. Отличие от пятого шара заключается в том, что его центр масс находится высоко от точки опоры. При наклоне шара плечо силы тяжести относительно точки опоры оказывается значительно большим, чем в случае с «неваляшкой». Поэтому и момент силы тяжести относительно точки опоры будет больше, чем в предыдущем случае. В результате амплитуда колебаний шара увеличивается, а значит, увеличивается и время затухания колебаний. Опыт 5. Внимательно посмотрев на фотографию на рисунке 3, можно увидеть на поверхности наклонной плоскости материю. Оказывается, под материей спрятана пластина из железа. Шар удерживается на такой наклонной плоскости малогабаритным неодимовым (в форме таблетки) магнитом, который с помощью клея прикреплен к его внутренней поверхности. Опыт 6. Внутри шара находится неодимовый магнит в «свободном» состоянии. При
« КВА Н ТА »
повороте шара на некоторый угол магнит скользит по его внутренней поверхности, занимая новое положение, а шар продолжает оставаться неподвижным. Опыт 7. Внутри шара имеется миниатюрный электродвигатель, который жестко прикреплен к корпусу. Ось вращения (вал) электродвигателя совпадает с направлением диаметральной вертикальной линии шара. На валу двигателя укреплен небольшой массивный диск. При подключении электродвигателя к источнику тока вал и массивный диск начинают вращаться в определенную сторону. Корпус же шара при этом поворачивается в другую сторону. Все это является следствием проявления закона сохранения момента импульса. Если суммарный момент всех внешних сил, действующих на тело, равен нулю, то момент импульса этого тела остается постоянным. Если же у неподвижного тела какая-то его часть приобретает некоторый момент импульса, имеющий определенный знак (момент импульса – векторная величина), то некоторая другая его часть непременно приобретет момент импульса противоположного знака.
Закон сохранения момента импульса учитывается при конструировании вертолетов. Так, вертолеты конструкции М.Л.Миля имеют два винта. Первый винт-ротор вращается в определенном направлении в горизонтальной плоскости над кабиной вертолета. А чтобы корпус вертолета не вращался в другую сторону, позади него размещен хвостовой винт, который, работая, препятствует вращению корпуса. В вертолетах, изготовленных по разработкам Н.И.Камова, имеются два винта-ротора, размещенных на одной оси над кабиной, но вращающихся в противоположных направлениях.
Опыт 8. Внутри шара находится миниатюрный электродвигатель, который жестко прикреплен к корпусу шара. На вал электродвигателя насажен диск, причем так, что его ось смещена относительно оси вала (говорят – диск насажен с эксцентриситетом). В результате при работе электродвигателя возникают механические колебания, которые называются вибрациями. Эти вибрации и заставляют двигаться щетку вместе с шаром.
Колебательное движение эксцентриков используется в работе вибрационных конвейеров, предназначенных для транспортировки тонкодисперсных (до десятков микрон), зернистых и кусковых (до 1000 мм и более) материалов. Они часто применяются для перемещения руды в горнорудной промышленности.
51
ЭКЗАМЕ Н АЦИО НН ЫЕ
закрашено краской. Найдите минимальный размер области, которую надо очистить от краски, чтобы через нее было видно все нижнее основание. Показатель преломления стекла 1,5. (10 б.)
Информатика
Отборочный тур Избранные задачи
- Ученые-яблокоедоведы построили математическую модель численности популяции яблокоедов. Входные данные: Р – численность популяции; N – длительность периода моделирования в годах; U[i], i=1..N – булевские переменные, значение Истина означает, что i-й год был урожайным на яблоки. Алгоритм расчета:
Ввод P, N НЦ Для i От 1 До N Если U[i]=Истина То P := P * A Иначе P := P * B Всё КЦ Вывод P
Когда яблокоедоведы ввели в модель текущую численность популяции и выданные коллегами-яблоковедами прогнозы урожайности яблок на 5 ближайших лет, результатом оказалось число 4725 – столько яблокоедов будет через 5 лет по мнению математической модели. Какова текущая численность популяции яблокоедов, если известно, что А и В – натуральные числа и А! B? 2. Школьник Сидор недавно открыл для себя системы счисления. Особенно понравились ему «круглые» числа – где 1 и потом много ноликов. Сидору понравилось записывать такие числа из разных систем счисления (записывал он их, естественно, в той системе, в которой они были круглыми, причем в порядке возрастания). Числа он записывал подряд, без просветов – получалась строка из цифр. Например, в двоичной системе начало этой строки было таким: 110100100010000… Писал числа Сидор на листочках для заметок, когда листок заканчивался – Сидор дописывал остаток числа на следующем листке (листках) и далее, когда число заканчивалось, начинал следующее. Сколько единиц
МАТЕРИАЛЫ
оказалось у Сидора на 33-м листке, если числа он писал в троичной системе, а на листке помещается ровно 333333 цифры? 3. Вам предстоит пройти небольшой квест из взаимосвязанных заданий. 1. Оцените истинность приведенных ниже высказываний (1 – истина, 0 – ложь). Выпишите ответы подряд. x Наши минуты и секунды – наследие системы счисления древних шумеров. x Диапазон возможных значений у байта без знака вдвое меньше, чем у байта со знаком. x Существуют недвоичные компьютеры. x В троичной системе счисления четные числа оканчиваются нулем. x Компьютер не выполняет арифметические операции, а просто берет их результаты из таблиц. ! при любом натуральном N! 9. x Любое двоичное число, нацело разделенное на 2, равно тому же числу, побитно сдвинутому вправо. x В системе счисления с основанием 21 E + F = 19. 2. Трактуя ответ задания 1 как двоичное число, найдите максимальное число, которое можно получить из него за несколько (от 0 до 7) циклических сдвигов влево. 3. В какой системе счисления результат задания 2 записывается как А2? 4. Переведите результат задания 1 в десятичную систему счисления. Затем определите значение этого числа, если трактовать его как представленное в системе счисления с основанием, равным трети ответа задания 3. 4. Назовем палиндриндексом натурального числа количество систем счисления, в которых число многозначно и симметрично (рассматриваются системы счисления с основаниями от 2 до 36). Например, палиндриндекс числа 46 равен 3, так как . А вот у числа 47 палиндриндекс равен 0. Найдите в интервале от 600 до 666 два последовательных числа с палиндриндексом 0. В качестве ответа введите их сумму. 5. В старом замке с каждым ударом часов появляется призрак. Время жизни призрака S секунд. Бьют часы, как полагается, столько раз, сколько часов прошло с момента последней полуночи или последнего полудня. Пер-
52
КВА НT 2020/№8
вый удар следует ровно в момент наступления очередного часа, интервал между ударами 1 секунда. Требуется сосчитать максимальное возможное количество призраков в замке. …Стоп, не начинайте пока писать программу! Дело в том, что замок расположен не на Земле. Там, где он находится, в сутках по 2*H часов, а в часе M минут, в минуте М секунд. Гарантируется, что входные данные корректны, число призраков конечно. 1) Найдите максимальное число призраков при H 12, M 60, S 10808. 2) Найдите максимальное число призраков при H 29, M 99, S 29410. 6. Дан алгоритм (рис.4). Сколько существует различных пар значений А и В, при которых алгоритм зацикливается?
Рис. 4
Рис. 5
- Число N – байт без знака; AND, OR, NOT – поразрядные логические операции. Из приведенных ниже высказываний выберите те, которые, будучи истинными, несут ровно 3 бита информации о числе N. A. (NOT N)! 3 B. N OR 229 239 C. N OR 28 0 D. N AND 90 2 E. N 32 F. N AND 168 128
Заключительный тур
-
Большая закупка (8 баллов) Вы ведете закупки материалов в фирме, занимающейся ремонтом квартир. Краска у вашего поставщика продается в ведрах и в банках. Имеется электронная таблица (рис.5). Предполагается, что при внесении в столбец «Количество» количества краски, которое требуется, в столбце «Стоимость» появляется минимальная сумма, которую следует заплатить для приобретения количества литров краски не меньше требуемого. Какую формулу следует записать в ячейке G6, чтобы выполнять необходимые расчеты? Формула должна быть тиражируемой (таблица тянется вниз на много строк). Гарантируется, что объем ведра не меньше объема банки.
-
Непарное число (12 б.) Имеется функция f (рис.6), работающая с двумя байтами без знака, результат – тоже байт без знака. Студент Сидор написал программу, которая присваивает переменной S сначала значение 0, а потом в цикле 101 раз получает с клавиатуры число Х и присваивает S значение f(S, X). Когда Сидор запустил программу, он ввел 101 число, при этом
53
ЭКЗАМЕ Н АЦИО НН ЫЕ
МАТЕРИАЛЫ
Рис. 6
известно, что все числа, кроме 49-го по счету, встречались среди введенных дважды (не обязательно подряд). Каким было 49-е число, если известно, что 11-е число равнялось 200 и 77-м было число 3, а в результате программа вывела 55?
-
Линька яблокоедов (7 б.) Весной яблокоеды линяют, каждый из них старается сбросить все иголки. Но в силу особенностей организма яблокоеды сбрасывают иголки только пачками: яблокоед может при любом количестве иголок, не меньшем 3, сбросить 3 иголки, кроме того, при четном количестве иголок он может сбросить половину из них, а при нечетном не меньше 5 может сбросить 4 иголки. При этом если количество иголок у яблокоеда после его изменения делится без остатка на 3, то у него отрастают 4 новые иголки, а если оно не делится на 3, но делится на 7 – то 6 новых иголок. В вольере 4 линяющих яблокоеда. В данный момент у первого 31 иголка, у второго 73, у третьего 19, у четвертого 122. У скольких из них есть возможность сбросить все иголки (количество сбросов не ограничено)?
-
Пометка территории (15 б.) Будучи помещенным в свободную ячейку стеллажа-массива, яблокоед начинает метить территорию. Делает он это по такому рекурсивному алгоритму (описан он слегка неформально, но Яблокоеду понятно; рис.7). Выполняя его, яблокоед постепенно захватывает весь стеллаж, кроме занятых ячеек и
Рис. 7
ячеек, отгороженных занятыми от доступного яблокоеду пространства. Яблокоеда поместили в верхний левый угол – ячейку с координатами (1, 1) – стеллажа-массива размером 2n + 1 на 2n + 1, 1 < n < 1000, в котором в среднем «столбце» и в средней «строке» все ячейки, кроме центральных трех, заняты. а) В какой ячейке яблокоед закончит захват стеллажа при n = 4? б) В какой ячейке яблокоед закончит захват стеллажа при n = 789?
- Первоклашки (15 б.) Семь первоклашек стоят в одном ряду. Каждый из них может находиться в одном из двух состояний: 1 – смотрит в телефон, 2 – жует бутерброд. Известно, что крайнего правого первоклашку можно перевести из наблюдающего в жующее состояние, просто вытащив из рук телефон и подсунув бутерброд (и наоборот). Состояние других первоклашек можно изменить, только если ближайший справа первоклашка смотрит в телефон, а остальные первоклашки справа (если они есть) жуют бутерброды. За 5 секунд можно изменить состояние только одного первоклашки. Вначале все первоклашки смотрят в телефон. Так как наступил обеденный перерыв, необходимо перевести их всех в жующее состояние. За какое минимальное количество секунд преподаватель сможет это сделать?
54
КВА НT 2020/№8
- Зашифрованный пароль (8 б.) Петя зарегистрировался на сайте и, чтобы не забыть слово-пароль, решил выписать его в блокнот, перед этим зашифровав. Вот что написано в блокноте Пети:
1101111111100001110000001110
Какое слово было использовано для пароля? Условие Фано Петя, к счастью, еще не проходил.
-
Заклинания (10 б.) В Хогвартсе практическое занятие: 200 учеников идут вдоль аллеи из 200 яблонь и отрабатывают заклинания «Расцветамус» и «Опадамус». Первый ученик заставляет все яблони расцвести. Второй меняет состояние каждой второй яблони, и с четных яблонь цветы осыпаются. Третий меняет состояние каждой третьей яблони на противоположное, то же проделывает четвертый с каждой четвертой яблоней и т.д. Сколько цветущих яблонь будет на аллее после окончания занятия?
-
Блогеры (10 б.) Дуся и Буся – блогеры, записывающие аудио-подкасты. Сегодня они записывали свои подкасты про проблемы подснежников зимой без снега и начали запись одновременно. Дуся записывала свой монолог на телефон с одноканальным микрофоном, поддерживающим частоту дискретизации 24576 Гц c глубиной звука в 32 бита. Буся записывалась на студии в стереорежиме с четырьмя каналами записи, каждый из которых поддерживал частоту дискретизации 98304 Гц с глубиной звука в 64 бита. Дуся записывала сообщение 4 минуты, потом 6 минут готовила к загрузке (на информационном объеме файла это не отразилось) и начала загружать на свой канал, причем скорость ее соединения составила
1 МБит/с. Буся ничего не редактировала и сразу после завершения записи начала выкладывать свою запись со скоростью 2 Мбит/с. Сколько минут записывалась Буся, если известно, что подкасты загрузились одновременно?
- Логическое выражение (5 б.) Замените логическое выражение тождественным ему, содержащим не более одной логической операции:
.
- Поисковые запросы (10 б.) На рисунке 8 представлены результаты выполнения нескольких поисковых запро-
Рис. 8
сов в пределах домена. Сколько бит информации о значении Х несет в себе сообщение «По запросам “ананас & беспредел” и “ананас & валторна” выдается одинаковое количество результатов» при условии, что значение Y известно и лежит в пределах от 25 до 35?
Публикацию по математике подготовили И.Комарчев, А.Моисеев, С.Преображенский;
по физике – Т.Андреева, М.Крупина, В.Кузьмичёв;
по информатике – С.Костоуров, Е.Крылова, К.Плотникова