В мир информатики
Задачник

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

к заданиям, опубликованным в газете “В мир информатики” № 97 (“Информатика” № 21/2007)

1. Задача “Забытый номер квартиры”

Ответ: 206.

Решение

Введем обозначения:

1) n — искомый номер квартиры;

2) n₂ — число, являющееся точным квадратом (n₂ = n – 10);

3) n₃ — число, являющееся точным кубом (n₃ = n + 10).

Определим, какой может быть последняя цифра числа n. Для этого составим такую таблицу (см. справа).

Учитывая, что разность между числами n₂ и n₃ равна 20, можно сделать вывод о том, что последняя цифра в них должна быть одна и та же. А это означает, что последней цифрой искомого числа — номера квартиры Бори — может быть одна из цифр 0, 1, 5 или 6.

Исследуем эти цифры.

1. Цифра 0

Число, являющееся точным кубом и оканчивающееся нулем, должно обязательно оканчиваться как минимум тремя нулями (убедитесь в этом!), а число, являющееся точным квадратом и оканчивающееся нулем, — как минимум двумя нулями. Это означает, что при последней цифре 0 в искомом числе разность между числами n₂ и n₃ не может быть равна 20, как это следует из условия. Значит, цифрой 0 искомый номер оканчиваться не может.

2. Цифра 1

При ней минимальное число — точный куб — равно 1331 (113), а значение, на 20 меньшее (1311), не является точным квадратом. Аналогично не подходят и следующие значения — точные кубы (9261, 29?791, …), даже если допустить, что такие номера квартиры возможны.

3. Цифра 5

Рассмотрим два минимальных числа — точных куба, оканчивающихся пятеркой:

1) 125 (5³) — в этом случае n = 115, но тогда n₂ = n – 10 = 105 не является точным квадратом;

2) 3375 (15³) — при этом n₂ = n₃ – 20 = 3355, также не являющееся точным квадратом.

Значит, последней цифрой искомого номера квартиры может быть только 6.

Минимальное число, являющееся точным кубом и оканчивающееся такой цифрой, это 216 (6³), и можно убедиться, что при этом 206 является числом, соответствующим утверждениям и Лёни, и Коли, т.е. именно такой номер имеет квартира Бори.

Правильные ответы прислали:

— Артюшенко Кристина, Спивачук Анастасия и Шайморданова Индира, Красноярский край, г. Канск, школа № 5, учитель Павлова Н.Н.;

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

— Ахтамова Рената, г. Уфа, Республика Башкортостан, гимназия № 3, учитель Болдырева С.В.;

— Баженов Василий и Баженов Михаил, средняя школа села Горелово Тамбовской обл., учитель Шитова Л.А.;

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

— Глазова Ирина, Гончаров Михаил, Шуляченко Даниил и Шурыгин Евгений, средняя школа села Шереметьево Вяземского р-на Хабаровского края, учитель Дивакова А.И.;

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

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

— Махотин Степан, г. Челябинск, школа № 124, учитель Юртаева Г.Ю.;

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

— Швайка Павел, г. Рубцовск Алтайского края, школа № 1, учитель Толмачева Н.П.;

— Хамитова Алина, г. Стерлитамак, Республика Башкортостан, школа № 12, учитель Дмитриева О.В.;

— Яценко Иван, средняя школа села Кубайка, Красноярский край, учитель Чудов Н.А.

2. Задача “Кто прекраснейшая из богинь?”

Решение

Пронумеруем утверждения богинь:

1) Афродита: “Я самая прекрасная”;

2) Афина: “Афродита не самая прекрасная”;

3) Гера: “Я самая прекрасная”;

4) Афродита: “Гера не самая прекрасная”;

5) Афина: “Я самая прекрасная”.

Парис мог рассуждать так.

1. Предположим, что Афина изрекла истину. Тогда Афина — прекраснейшая из богинь, и по предположению, что остальные богини сказали ложь, утверждение 4 ложно. Из его отрицания следует, что Гера — прекраснейшая из богинь, но тогда получается противоречие со сделанным допущением.

2. Предположим, что истину изрекла Гера. Тогда Гера — прекраснейшая из богинь и, по предположению, утверждение 2 ложно. Мы снова приходим к противоречию, так как Афродита не может быть прекраснейшей из богинь, коль скоро прекраснейшая из богинь — Гера. Следовательно, и это исходное предположение ложно.

3. Предположим, что Афродита изрекла истину. Тогда Афродита — прекраснейшая из богинь. Отрицания утверждений 2, 3 и 5 истинны и подтверждают, что Афродита прекраснейшая из богинь.

Итак, по решению, вынесенному “судом Париса”, прекраснейшая из богинь — Афродита.

Если бы Парис знал законы логики (J), то он бы смог использовать их следующим образом.

Прежде всего он бы обозначил простые высказывания:

1) “Прекраснейшей является Афродита” — А;

2) “Прекраснейшей является Афина” — В;

3) “Прекраснейшей является Гера” — С.

Затем он бы рассмотрел три варианта.

1. Пусть истинными являются высказывания Афродиты. Тогда высказывания богинь можно записать в виде:

1) высказывание Афродиты: “Я самая прекрасная” (оно истинно) — А;

2) высказывание Афины: “Афродита не самая прекрасная” (оно ложно) — ⌉⌉А;

3) высказывание Геры: “Я самая прекрасная” (оно ложно) — ⌉С;

4) высказывание Афродиты: “Гера не самая прекрасная” (оно истинно) — ⌉С;

5) высказывание Афины: “Я самая прекрасная” (оно ложно) — ⌉В.

После этого можно “соединить” все высказывания для первого варианта (используя логическую операцию конъюнкции): А & ⌉⌉ А & ⌉С & ⌉С & ⌉В.

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

1) ⌉А;

2) ⌉А;

3) ⌉С;

4) ⌉⌉С;

5) В.

“Связка” этих высказываний: ⌉А & ⌉А & ⌉С & ⌉⌉С & В.

3. Аналогично для случая, когда истинными являются высказывания Геры:

1) ⌉А;

2) ⌉⌉А;

3) С;

4) ⌉⌉С;

5) ⌉В

и ⌉А & ⌉⌉А & С & ⌉⌉С & ⌉В.

Только один из трех рассмотренных вариантов может быть истинным:

(А & ⌉⌉А & ⌉С & ⌉С & ⌉В) v (⌉А & ⌉А & ⌉С & ⌉⌉С & В) v (⌉А & ⌉⌉А & С & ⌉⌉С & ⌉В) = 1.

Упростив это логическое выражение согласно законам логики, можно получить:

А & ⌉С & ⌉В v 0 v 0 = А & ⌉С & ⌉В,

т.е. прекраснейшей из всех богинь является Афродита.

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

— Андриенко Артем, г. Рубцовск Алтайского края, школа № 1, учитель Толмачева Н.П.;

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

— Ахтамова Рената, г. Уфа, Республика Башкортостан, гимназия № 3, учитель Болдырева С.В.;

— Баженов Василий и Баженов Михаил, средняя школа села Горелово Тамбовской обл., учитель Шитова Л.А.;

— Баклаженко Алена, средняя школа поселка Дормидонтовка Вяземского р-на Хабаровского края, учитель Афиногенова Н.И.;

— Беломестных Яна, Крашенинникова Елизавета и Логинов Дмитрий, Красноярский край, г. Канск, школа № 5, учитель Павлова Н.Н.;

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

— Глазова Ирина, Гончаров Михаил и Шурыгин Евгений, средняя школа села Шереметьево Вяземского р-на Хабаровского края, учитель Дивакова А.И.;

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

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

— Кутлуев Роман и Севостьянова Анна, г. Челябинск, школа № 124, учитель Юртаева Г.Ю.;

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

Отметим ответы Анны Севостьяновой и Романа Кутлуева, приведших два варианта решения, в том числе с использованием законов логики.

3. Задача “Перестановка коней”

Эта задача придумана итальянцем Гуарини еще в XVI веке. Изящным методом ее решения является так называемый “метод пуговиц и нитей”, предложенный известным английским мастером головоломок Г.Дьюдени.

На каждое поле нашей маленькой доски, кроме центрального (на него кони не могут попасть), поместим по пуговице (на рис. 1а их заменяют кружки). Если между двумя полями возможен ход конем, то лежащие в них пуговицы свяжем нитью (на рисунке нитям соответствуют отрезки, соединяющие кружки). Полученный клубок пуговиц и нитей распутаем так, чтобы все пуговицы расположились по кругу (рис. 1б).

а)

б)

Рис. 1

Теперь решение задачи находится почти автоматически. Выбрав одно из направлений по кругу, будем переставлять по нему коней до тех пор, пока они не поменяются местами. Необходимое перемещение коней по доске получается заменой пуговиц соответствующими полями. Нетрудно убедиться, что решение состоит из 16 перемещений коней (восьми белых и восьми черных), причем кони разного цвета могут ходить по очереди.

Поставим дополнительное условие — чтобы белые и черные кони при своем движении не угрожали друг другу (очередность ходов в этом случае можно нарушать). Найдите решение для этого случая.

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

— Алексанин Никита и Белый Павел, г. Челябинск, школа № 124, учитель Юртаева Г.Ю.;

— Аникутин Даниил, Дробизов Олег и Короткевич Денис, Красноярский край, г. Канск, школа № 5, учитель Павлова Н.Н.;

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

— Баженов Василий и Баженов Михаил, средняя школа села Горелово Тамбовской обл., учитель Шитова Л.А.;

— Врублевская Ирина, Ерош Татьяна, Климентьев Владимир, Кузьмин Евгений, Кулакова Оксана и Мельник Кристина, г. Лесосибирск Красноярского края, поселок Стрелка, школа № 8 им. Константина Филиппова, учитель Лопатин М.А.;

— Глазова Ирина, Гончаров Михаил, Шуляченко Даниил и Шурыгин Евгений, средняя школа села Шереметьево Вяземского р-на Хабаровского края, учитель Дивакова А.И.;

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

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

— Ивановский Леонид, г. Ярославль, школа № 33, учитель Ярцева О.В.;

— Куркин Иван, г. Ростов-на-Дону, школа № 109, учитель Суслина Т.И.;

— Рабинович Ксения, Иркутская обл., г. Саянск, школа № 3, учитель Бочкарникова О.Н.;

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

— Шкута Руслан, г. Рубцовск Алтайского края, школа № 1, учитель Толмачева Н.П.

4. Статья “Как найти задуманное число?”

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

Ответ

Для нахождения задуманного числа надо разделить объявленный результат на 9, затем то, что получится, удвоить и, наконец, отнять 1.

Пример. Предположим, что задумано число 7; после его утроения получаем число 21, прибавляя к нему число 3, получим 24; разделив 24 на 2 и опять результат утроив, получим число 36. Если теперь это число разделить на 9, то в частном получим 4. Удвоив число 4 и отняв единицу, получим задуманное число 7.

Обоснование. Пусть кто-то задумал нечетное число, которое обозначим через 2k + 1. После утроения и прибавления числа 3 получим число 6k + 6. Разделив это число на 2, получим число 3k + 3. Далее (3k + 3) x 3 = 9k + 9.

Частное от деления числа 9k + 9 на число 9 равно k + 1; удваивая это число и отнимая 1, находим задуманное число 2k + 1.

Ответ и программы для демонстрации фокусов по двум рассмотренным в статье задачам прислали:

— Башкирова Екатерина, Курская обл., г. Железногорск, гимназия № 1, учитель Буробина Н.Д.;

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

— Кошелева Мария, средняя школа села Татарское, Дальне-Константиновский р-н Нижегородской обл., учитель Салова Т.В.;

— Кулешова Ксения, г. Орел, лицей № 4, учитель Чапкевич И.М.;

— Яценко Иван, средняя школа села Кубайка, Красноярский край, учитель Чудов Н.А.

5. Задача “Переход по пустыне”

Решение

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

Если запас пищи и еды на k дней для одного человека обозначить V_k, где k = 0, 1, 2, 3, 4, то действия участников перехода (путешественника П и носильщиков Н1 и Н2) должны быть следующими (см. табл. 1).

Поскольку, как указано в условии, маршрут замкнутый, т.е. все участники перехода до его начала и в его конце находятся в одном пункте, то возможен также “симметричный” вариант, в котором носильщики выходят навстречу путешественникам из конечного пункта. Действия всех участников в таком случае приведены в табл. 2 на с. 42.

Некоторые читатели предложили заблаговременно создать запасы пищи и еду в промежуточных пунктах (относя туда провиант и возвращаясь назад). Это можно сделать как без носильщиков, так и с одним или двумя носильщиками.

Оказывается, что если носильщик есть только один, то задачу решить тоже можно и даже более эффективно (с какой точки зрения — определите самостоятельно, сравнив решение с приведенными выше. Ответ присылайте в редакцию). Алгоритм действий путешественника (П) и носильщика (Н) приведен в табл. 3.

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

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

— Быстров Дмитрий, Аникутин Даниил, Дмитриев Евгений, Дробизов Олег, Ильясов Михаил, Короткевич Денис, Логинов Дмитрий и Шабуров Никита, Красноярский край, г. Канск, школа № 5, учитель Павлова Н.Н.;

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

— Глижинский Дмитрий, г. Бендеры, Республика Молдова, гимназия № 2, учитель Глижинская С.Л.;

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

— Дерксен Александр, средняя школа поселка Дормидонтовка Вяземского р-на Хабаровского края, учитель Афиногенова Н.И.;

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

— Ивановский Леонид, г. Ярославль, школа № 33, учитель Ярцева О.В.;

— Кулешова Ксения, г. Орел, лицей № 4, учитель Чапкевич И.М.;

— Куркин Иван, г. Ростов-на-Дону, школа № 109, учитель Суслина Т.И.;

— Нигматуллин Руслан, село Раевский Альшеевского р-на Республики Башкортостан, школа № 2, учитель Евграфова Н.Ф.;

— Севостьянова Анна, Сергеев Николай, Толмачев Даниил и Щетинина Наталья, г. Челябинск, школа № 124, учитель Юртаева Г.Ю.;

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

— Толмачев Павел, г. Рубцовск Алтайского края, школа № 1, учитель Толмачева Н.П.;

— Хотеев Сергей, Москва, гимназия № 1530, учитель Невидимый Д.Б.;

— Яценко Иван, средняя школа села Кубайка, Красноярский край, учитель Чудов Н.А.

Новые варианты задачи

Решите задачу для случая одного носильщика и при следующих вариантах маршрута:

а) маршрут шестидневный незамкнутый, носильщик находится в его конечном пункте;

б) маршрут семидневный замкнутый;

в) маршрут семидневный незамкнутый, носильщик находится в его конечном пункте.

Решения (можно не всех задач) присылайте в редакцию.

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

В мир информатики Задачник

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

В мир информатики
Задачник