В мир информатики # 87 (1–15 марта).
Задачник

Ответы, решения. разъяснения

№ 81 (“Информатика”№  22/2006)

Задача 1

1. Разобьем все монеты на три кучки по 33 монеты в каждой. При первом взвешивании сравним на весах веc двух любых кучек — выявим кучку из 33 монет, среди которых есть искомая.

2. Действуя аналогично, вторым взвешиванием можно выявить кучку из 11 монет, среди которых находится фальшивая.

3. Разобьем все монеты на три кучки: 4, 4 и 3 монеты. Сравним на весах первые две кучки. Если весы будут в равновесии, то фальшивая монета находится среди трех оставшихся монет, и ее можно выявить еще одним, четвертым взвешиванием.

Если же одна из чашек с четырьмя монетами перетянет, то фальшивая монета лежит в другой чашке, и еще за два взвешивания можно ее найти (общее число взвешиваний — 5).

Задача 2

Сначала положим на две чашки весов по 13 монет, затем (если весы находятся в равновесии) уберем их и положим по 11 из еще не бравшихся монет, затем по 9, 7, 5, 3 и 1 до тех пор, пока одна из чашек не перевесит. Если такого не произойдет, то после седьмого взвешивания (когда на чашках весов будет по одной монете) останется одна, 99-я по счету, монета, которая во взвешиваниях не участвовала. Она и является фальшивой.

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

Итак, при каком-то, k-м, взвешивании мы можем выявить n монет, среди которых находится искомая фальшивая. Можно записать, что n = (7 – k) * 2 + 1. Получается, что мы пришли к задаче нахождения среди (7 – k) * 2 + 1 монет фальшивой монеты за (7 – k) взвешиваний (т.к. k взвешиваний уже проведено, причем каждая монета в рассматриваемой группе взвешивалась один раз).

Введем новую величину m = 7 – k. Тогда только что сформулированная задача сводится к следующей: среди (2m + 1) монет найти фальшивую монету за m взвешиваний (среди трех монет за одно взвешивание, среди пяти монет — за два, …, среди тринадцати — за 6). При этом никакую монету нельзя взвешивать более одного раза. Ее можно решить так.

Надо все монеты, кроме одной, разбить на m пар и последовательно сравнивать веса монет каждой пары — для этого понадобится m взвешиваний. Если при каком-то взвешивании равновесие нарушится, то более легкая монета и является фальшивой.
В противном случае фальшивая монета — оставшаяся “без пары”.

Ответы прислали:

— Абдуллин Рамиль, средняя школа деревни Старый Бабич Кармаскалинского р-на Республики Башкортостан, учитель Абдуллин Р.Ф.;

— Айтыкина Лилия, г. Прокопьевск Кемеровской обл., школа № 3, учитель Шерстнева Л.М.;

— Бессараб Лариса и Тюшняков Юрий, средняя школа села Шереметьево Вяземского р-на Хабаровского края, учитель Дивакова А.И.;

— Гайсина Галия и Гайсин Рашит, г. Уфа, Республика Башкортостан, школа № 18, учитель Искандарова А.Р.;

— Глухов Валентин, Кемаев Юрий, Морозов Александр, Полушкин Геннадий и Полушкин Евгений, Кемлянская средняя школа Ичалковского р-на Республики Мордовия, учитель Силантьев О.П.;

— Глюз Юлия, средняя школа села Гилевка Алтайского края, учитель Збарах В.Ф.;

— Деминцев Борис, средняя школа села Сердар, Республика Марий Эл, учитель Чернова Л.И.;

— Ефимов Михаил, Иванова Татьяна, Ходоровская Виктория и Шеплякова Анастасия, г. Сегежа, Республика Карелия, школа № 5, учитель Меньшиков В.В.;

— Ефимова Вера, средняя школа села Качикатцы Хангалусского улуса, Республика Саха (Якутия), учитель Яковлева М.Д.;

— Иларионов Дмитрий, Спиридонов Валерий и Улыбышева Ирина, г. Струнино Владимирской обл., школа № 11, учитель Волков Ю.П.;

— Кузнецова Евгения, г. Ярославль, школа № 33, учитель Головина Л.И.;

— Лебедков Николай и Фролов Артем, средняя школа поселка Тавричанка Альшеевского р-на, Республика Башкортостан, учитель Корнеева М.В.;

— Максимов Борис, средняя школа села Качикатцы Хангалусского улуса, Республика Саха (Якутия), учитель Яковлева М.Д.;

— Малахова Татьяна и Щеголькова Елена, г. Благодарный Ставропольского края, школа № 9, учитель Стрепетова А.В.;

— Семенов Александр, средняя школа села Житное, Астраханская обл., Икрянинский р-н, учитель Семенова Е.Ю.;

— Юргин Андрей, основная школа села Кубайка Красноярского края, учитель Семеновский В.А.

Правильное решение задачи “На конгрессе” (она была опубликована в указанном номере нашей газеты) представили также:

— Абрамова Татьяна, Новобурасский р-н Саратовской обл., Ириновская средняя школа, учитель Брунов А.С.;

— Айтыкина Лилия, г. Прокопьевск Кемеровской обл., школа № 3, учитель Шерстнева Л.М.;

— Бессараб Лариса и Тюшняков Юрий, средняя школа села Шереметьево Вяземского р-на Хабаровского края, учитель Дивакова А.И.;

— Лебедков Николай, средняя школа поселка Тавричанка Альшеевского р-на, Республика Башкортостан, учитель Корнеева М.В.;

— Мотина Юлия и Потлова Татьяна, средняя школа села Речица Ливенского р-на Орловской обл., учитель Потлова О.А.;

— Полежаева Дарья, средняя школа села Подсосное Назаровского р-на Красноярского края, учитель Кривова Н.П.;

— Сергеев Максим, г. Сибай, Республика Башкортостан, лицей “ПолиТЭк”, учитель Кусябаева Г.С.;

— Ткаченко Анна, средняя школа села Подсосное Назаровского р-на Красноярского края, учитель Кривова Н.П.

Юлия Мотина и Татьяна Потлова также правильно решили новый вариант задачи “Коля, Оля и тетя Поля” (см. газету-вкладку “В мир информатики” № 81 / “Информатика” № 22/2006).

Правильный ответ на задание, предложенное в статье “Три письма” (газета “В мир информатики” № 80 / “Информатика” № 21/2006), прислали также:

— Бронетко Денис, Гудименко Инга, Исакова Олеся, Исламова Резеда, Карнач Дмитрий, Китайкин Артем, Лозовой Максим, Мегеря Марина, Миронова Ольга, Сара Диана, Сметанин Павел, Шевченко Юлия и Шолохов Илья, поселок Лимбяяха Новоуренгойского р-на Тюменской обл., школа № 1, учитель Исакова И.С.;

— Городничева Александра, г. Заозерный Красноярского края, гимназия № 2, учитель Владимирова Н.А.;

— Кузнецова Евгения, г. Ярославль, школа № 33, учитель Головина Л.И.;

— Максимов Борис, средняя школа села Качикатцы Хангалусского улуса, Республика Саха (Якутия), учитель Яковлева М.Д.;

— Филонов Евгений, средняя школа поселка Тавричанка Альшеевского р-на, Республика Башкортостан, учитель Корнеева М.В.

Правильное решение головоломки “судоку”, описанной в газете-вкладке “В мир информатики” № 78 (“Информатика” № 19/2006), представили также:

— Богомолов Алексей и Нурлыгаянов Максим, г. Заозерный Красноярского края, гимназия № 2, учитель Владимирова Н.А.;

— Гордиенко Евгений, средняя школа села Гилевка Алтайского края, учитель Збарах В.Ф.;

— Епифанова Екатерина, средняя школа села Ложниково, Омская обл., Тарский р-н, учитель Коровин Д.В.

Правильное решение буквенного ребуса, опубликованного в указанном номере нашей газеты, прислали также4:

— Александров Алексей, г. Новочеркасск, Суворовское училище МВД РФ, преподаватель Воронкова О.Б.;

— Ефимова Вера, средняя школа села Качикатцы Хангалусского улуса, Республика Саха (Якутия), учитель Яковлева М.Д.

Трусов Максим, Новобурасский р-н Саратовской обл., Ириновская средняя школа, учитель Брунов А.С., по материалам статьи “Биологические ритмы”, опубликованной в газете “В мир информатики” № 81 (“Информатика” № 22/2006), в системе программирования Delphi разработал программу, с помощью которой можно определить так называемые “суперблагоприятные” и “супернеблагоприятные” дни (см. указанную статью).

Повар и пицца

В распоряжении повара имеются перец, лук, грибы, помидоры, морковь и анчоусы, причем все это можно, по его мнению, добавлять к сыру, чтобы приготовить пиццу (а можно и ничего не добавлять!). Сколько типов пиццы может приготовить повар?

⁵ Задача предназначена для учащихся начальной школы и учеников 5–7-х классов.