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

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

1. Не по правилам факториальной системы счисления записано число 8 663 320 (в седьмом разряде могут быть использованы только цифры 0, 1, 2, …, 7).

2. Десятичный эквивалент чисел, записанных

а) в факториальной системе счисления (буква f в виде индекса говорит о записи числа в этой системе):

— 502101_f = 5 · 7! + 2 · 4! + 1 · 3! + 1 · 1! = 5 · 720 + 2 · 24 + 1 · 6 + 1 = 3655₁₀;

— 4422310_f = 4 · 7! + 4 · 6! + 2 · 5! + 2 · 4! + 3 · 3! + 1 · 2! = 4 · 5040 + 4 · 720 + 2 · 120 + 2 · 24 + 3 · 6 + 1 · 2 =
= 23348₁₀;

б) в фибоначчиевой системе счисления:

— 10010101_Fib = 1 · 34 + 1 · 8 + 1 · 3 + 1 · 1 = 46₁₀;

— 101010101_Fib = 1 · 55 + 1 · 21 + 1 · 8 + 1 · 3 + 1 · 1 = 88₁₀.

Примечание. Весомость разрядов в фибоначчиевой системе счисления приведена в таблице:

3. Запись десятичных чисел 34 502 и 45 087 012 в факториальной системе счисления:

а) число 34 502:

— перевод методом деления:

Деление (с остатком) исходного числа и промежуточных частных производится на числа 2, 3 и т.д. до тех пор, пока частное не будет меньше очередного делителя. Полученное частное и остатки выписываются “справа налево”. Итак, 34502₁₀ = 6552210_f;

— перевод методом выделения наибольших факториалов:

34 502 = 5040 · 6 + 4262 = 6 · 7! + 720 · 5 + 662 = 6 · 7! + 5 · 6! + 120 · 5 + 62 = 6 · 7! + 5 · 6! + 5 · 5! + 24 · 2 + 14 =
= 6 · 7! + 5 · 6! + 5 · 5! + 2 · 4! + 6 · 2 + 2 = 6 · 7! + 5 · 6! + 5 · 5! + 2 · 4! + 2 · 3! + 2 = 6 · 7! + 5 · 6! + 5 · 5! + 2 · 4! + 2 · 3! +
+ 1 · 2! + 0 = 6 · 7! + 5 · 6! + 5 · 5! + 2 · 4! + 2 · 3! + 1 · 2! + 0 · 1! = 6552210_f ;

б) число 45 087 012:

45087012₁₀ = 11421550200_f.

4. Первые 14 натуральных чисел в фибоначчиевой системе счисления:

Правила перечисления натуральных чисел (правила получения очередного числа) в этой системе могут быть сформулированы, например, следующим образом²:

1) если последние две цифры предыдущего числа равны нулю, то записываем единицу в правый разряд; конец;

2) сдвигаем самую правую единицу в записи предыдущего числа влево, вместо нее пишем ноль. Если левее нее рядом единицы не окажется, то конец; в противном случае записываем на месте самой правой единицы ноль и снова выполняем данный пункт.

5. Запись десятичных чисел 30, 125 и 1949 в фибоначчиевой системе счисления:

30₁₀ = 21₁₀ + 8₁₀ + 1₁₀ = 1010001_Fib;

125₁₀ = 89₁₀ + 34₁₀ + 2₁₀ = 1010000010_Fib;

1949₁₀ = 1597₁₀ + 233₁₀ + 89₁₀ + 21₁₀ + 8₁₀+ 1₁₀ = 1000101001010001_Fib.

6. На рисунке ниже показаны счеты для изображения чисел в факториальной системе счисления. Если вести нумерацию проволок счетов снизу вверх, то можно увидеть, что количество косточек на каждой проволоке равно номеру проволоки, увеличенному на 1 (в факториальной системе количество цифр, используемых в том или ином разряде, равно номеру разряда, также увеличенному на 1). На каждой проволоке может быть отложено количество косточек, на 1 меньшее общего числа косточек (как на обычных, так называемых “русских”, счетах из 10 косточек могут быть отложены 9). А в факториальной системе максимально возможная цифра также равна номеру разряда. Учитывая это и вспомнив, что базис (вес разрядов) в такой системе счисления образует последовательность факториалов натуральных чисел: 1! = 1, 2! = 2, 3! = 6, …, можем сказать, что каждая косточка, расположенная на k-й проволоке, имеет вес k!. Итак, на правых счетах отложено число 22010_fib =
= 2 · 5! + 2 · 4! + 0 · 3! + 1 · 2! + 0 · 1! = 290₁₀.

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

— Алиева Саира, Балахонова Анастасия, Митрошина Ольга, Финк Андрей, Чудиновский Евгений и Шмагун Татьяна, средняя школа села Средний Васюган, Томская обл., Каргасокский р-н, учитель Вторушина Н.А.;

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

— Валиев Наим и Кулахметов Рашид, средняя школа села Восточное Нижегородской обл., учитель Долгова Г.А.;

— Григоренко Василий, Григоренко Дмитрий, Есипова Мария, Круглякова Мария и Яснова Дарья, средняя школа поселка Осиновка, Алтайский край, учитель Евдокимова А.И.;

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

— Мнацаканян Ашот, средняя школа поселка Новопетровский Московской обл., учитель Артамоно­ва В.В.;

— Никаноров Вячеслав, Украина, г. Кременчуг Полтавской обл., школа № 19, учитель Борисенко С.А.;

— Тренина Анна, Тюменская обл., Ямало-Ненецкий автономный округ, г. Ноябрьск, школа № 2, учитель Бабаева Н.А.;

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

— Хотеев Сергей, Москва, гимназия № 1530, учитель Шамшев М.В.

Лучшими признаны ответы Анны Трениной, Антона Трусова и учащихся средней школы села Средний Васюган. Все они будут награждены дипломами. Поздравляем!

2. Задача “51 монета”

Решение

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

Ясно, что аналогично решается и задача в общем виде: “Найти фальшивую монету в группе из (2m + 1) монет за m взвешиваний, взвешивая каждую монету не более одного раза”.

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

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

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

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

— Балло Алина, Гаянова Луиза, Пилипчак Наталья и Федоренко Иван, Тюменская обл., г. Новый Уренгой, поселок Лимбяяха, школа № 9, учитель Исакова И.С.;

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

— Болдин Иван, Илюхина Елизавета, Кузнецов Дмитрий, Ланева Олеся, Ливадонова Алена, Магомедова Аминат, Макарова Ксения, Мандрыкин Александр, Прилуцкий Руслан, Рыбакова Екатерина, Сальников Егор, Сапунов Максим, Седнев Даниил, Чупрова Анастасия и Яшина Екатерина, г. Нижний Новгород, клуб “Космос”, педагог Занозин Д.А.;

— Быкова Анна, г. Борисоглебск Воронежской обл., гимназия № 1, учитель Степаненко О.В.;

— Валиев Наим и Кулахметов Рашид, средняя школа села Восточное Нижегородской обл., учитель Долгова Г.А.;

— Головченко Михаил, Демидова Марина, Катышева Елизавета, Пантюхина Анна, Синицын Никита, Тананаева Ксения, Шмуляев Андрей и Яманова Кристина, г. Струнино Владимирской обл., школа № 11, учитель Волков Ю.П.;

— Гончаренко Анастасия, Нелюбин Александр и Царева Анастасия, г. Сегежа, Республика Карелия, школа № 5, учитель Меньшиков В.В.;

— Григоренко Василий, Григоренко Дмитрий, Есипова Мария, Круглякова Мария и Яснова Дарья, средняя школа поселка Осиновка, Алтайский край, учитель Евдокимова А.И.;

— Землянская Марина, Нестругина Анастасия и Побединский Виталий, Воронежская обл., поселок Каменка, средняя школа № 1 им. Героя Советского Союза В.П. Захарченко, учитель Старикова М.Е.;

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

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

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

— Мнацаканян Ашот, средняя школа поселка Новопетровский Московской обл., учитель Артамонова В.В.;

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

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

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

— Хотеев Сергей, Москва, гимназия № 1530, учитель Шамшев М.В.

Читатели из Нижнего Новгорода (педагог Занозин Д.А.) предложили также такой способ решения задачи. Все монеты делятся на 17 кучек по три монеты в каждой. Из каждой тройки на весах сравниваются две. Если при этих 17 взвешиваниях весы будут в равновесии, то фальшивая монета — в одной из оставшихся 17 монет. В этом случае эти 17 монет разбиваются на 5 кучек по три монеты и одну кучку из двух монет. После этого проводятся еще 6 взвешиваний. Если при них весы будут в равновесии, то выделяются 5 монет, среди которых находится фальшивая. Ее можно найти не более чем за два взвешивания. Если же на любом из взвешиваний равновесие нарушится, то более легкая монета и является фальшивой. Нетрудно убедиться, что этот способ аналогичен способу, описанному в начале.

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

3. Задача “Получить из «тропика» «приток»”

Прежде чем представлять итоги, приведем фотографию, которую прислал В.В. Меньшиков, учитель школы № 5 г. Сегежа, Республика Карелия. На ней изображены учащиеся 5-го “A” класса этой школы во время выполнения задания (каждому учащемуся были выданы трафарет и карточки с буквами):

Решение

Минимально необходимое количество перекладываний — 20. При этом задача имеет несколько вариантов решения, часть из которых приведена в таблице.

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

— Авдеев Александр, Борисов Артем, Гребеньков Егор, Жих Александр, Качан Марина, Кириллов Роман, Коренева Маргарита, Кузнецова Карина, Леонов Александр, Машкин Дмитрий, Нелюбин Александр, Никифоров Алексей, Праслова Анжела, Трофимова Елена, Харитончик Игорь и Чистиков Дмитрий, г. Сегежа, Респуб­лика Карелия, школа № 5, учитель Меньшиков В.В.;

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

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

— Аствацатурян Эдуард, средняя школа поселка Новопетровский Московской обл., учитель Артамонова В.В.;

— Асфандияров Ильнур и Саттаров Алмаз, Республика Татарстан, г. Бавлы, гимназия № 4, учитель Шафиков Н.Р.;

— Балло Алина, Володин Дмитрий, Логвиненко Александра и Пилипчак Наталья, Тюменская обл., г. Новый Уренгой, поселок Лимбяяха, школа № 9, учитель Исакова И.С.;

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

— Быкова Анна, Гавриленко Николай, Ессе Артур и Зульфикаров Алексей, г. Борисоглебск Воронежской обл., гимназия № 1, учитель Степаненко О.В.;

— Васьков Владимир, средняя школа села Кипцы, Саратовская обл., Екатериновский р-н, учитель Омельченко С.Ю.;

— Верхов Дмитрий, Вострикова Нина, Генык Елизавета, Кузовенкова Светлана, Милов Александр, Морозова Валерия, Ремизова Олеся, Федорова Екатерина и Цаплина Ольга, г. Астрахань, школа № 33, учитель Лепехина С.М.;

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

— Говорушко Иван, Дементьев Виктор, Ильенко Юлия, Ненартович Ксения, Ромушкин Александр и Рукавишникова Ирина, г. Тайшет Иркутской обл., школа-интернат № 24 ОАО “РЖД”, учитель Авхадеева Р.И.;

— Головченко Михаил, Демидова Марина, Дияну Мария, Катышева Елизавета, Пантюхина Анна, Синицын Никита, Тананаева Ксения, Чердакова Дарья и Шмуляев Андрей, г. Струнино Владимирской обл., школа № 11, учитель Волков Ю.П.;

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

— Динмухаметова Ляйсан, гимназия г. Азнакаево, Республика Татарстан, учитель Губайдуллина А.Р.;

— Елизаров Кирилл, Киселева Анастасия и Смирнов Дмитрий, г. Ярославль, школа № 33, учитель Цикина Е.Н.;

— Жерякова Ольга, Молева Ольга, Поздеева Анна, Сапронов Никита и Строганов Дмитрий, г. Челябинск, школа № 124, учитель Юртаева Г.Ю.;

— Землянская Марина, Нестругина Анастасия и Побединский Виталий, Воронежская обл., поселок Каменка, средняя школа № 1 им. Героя Советского Союза В.П. Захарченко, учитель Старикова М.Е.;

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

— Киселев Юрий, средняя школа села Дуван, Республика Башкортостан, Дуванский р-н, учитель Муратшина Ж.В.;

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

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

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

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

— Новикова Наталья, г. Заозерный Красноярского края, гимназия № 2, учитель Владимирова Н.А. (Наталья привела 32 различных способа решения задачи!);

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

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

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

а также Динисламов Руслан и Щелчков Дмитрий из гимназии № 3 (другие сведения не сообщены).