В мир информатики # 94 (16–30 сентября).
Внимание! Конкурс

Итоги конкурса № 56 для учащихся

Напомним, что необходимо было объяснить, почему в электронной таблице Microsоft Excel разность значений факториала одного и того же числа (25), рассчитанных по-разному, отличалась от нуля.

Ответ. Дело в том, что 25! (факториал числа 25) — довольно большое число (оно равно 15 511 210 043 331 000 000 000 000), и в ходе вычислений имеющейся разрядной сетки компьютера для полного сохранения результатов расчетов недостаточно, и происходит округление последних разрядов. Так как расчеты проводились двумя способами, то и округление произошло по-разному, из-за чего разность стала не равной нулю.

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

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

— Ананьев Иван, Винидиктов Александр и Ильясов Михаил, Красноярский край, г. Канск, школа № 5, учитель Павлова Н.Н.;

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

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

— Бондаренко Андрей, г. Петропавловск-Камчатский, Центр образования “Эврика”, преподаватель Шмаков А.Л. (учитель информатики в школе № 33 Кравченко А.О.);

— Гумерова Наиля, Енгалычёва Анастасия, Орлов Сергей и Черепкова Анна, г. Нижний Новгород, педагогический колледж им. К.Д. Ушинского, преподаватель Занозин Д.А.;

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

— Еропкина Юлия и Чеботарева Екатерина, участники компьютерного кружка Дворца детского творчества им. В.П. Чкалова, г. Нижний Новгород, педагог Занозина Г.В.;

— Кобзарь Марина, поселок Магдагачи Амурской обл., школа № 3, учитель Лоцманова В.А.;

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

— Хасаншин Ленар, Республика Татарстан,
г. Нурлат, школа № 2, учитель Нургатина Г.И.

Победителями конкурса признаны: Абдуллин Рамиль; Ананьев Иван, Винидиктов Александр и Ильясов Михаил; Антипина Анна, Занозин Михаил, Диденко Оксана и Пахомов Сергей; Гумерова Наиля, Енгалычёва Анастасия, Орлов Сергей и Черепкова Анна; Еропкина Юлия и Чеботарева Екатерина; Кобзарь Марина. Они будут награждены дипломами. Поздравляем! Отметим также ответ Андрея Бондаренко, который провел эксперимент по вычислению факториалов больших чисел.

Итоги конкурса № 57
для учащихся

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

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

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

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

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

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

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

— Афлятунов Эраст, Игошев Станислав и Мельник Алексей, г. Лениногорск, Республика Татарстан, школа № 8, учитель Кашапова Р.Х.;

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

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

— Баженова Екатерина, Гераськин Андрей, Маковкин Владимир, Половинкин Михаил и Щуков Александр, г. Новокузнецк Кемеровской обл., гимназия № 44, учитель Павлова Т.А.;

— Баканова Светлана, Мазурова Виктория и Первушин Вячеслав, поселок Чунский Иркутской обл., школа № 90, учитель Гнидина И.А.;

— Бахорина Юлия и Красильникова Светлана, г. Вологда, школа № 30, учитель Губичева А.В;

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

— Бондарь Юлия, Сосунова Ирина и Щербаков Дмитрий, поселок Ростовка Омского р-на Омской обл., “Сибирская школа № 2”, учитель Жолудева Е.А.;

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

— Будаев Батор, средняя школа села Барагхан Курумканского р-на, Республика Бурятия, учитель Доржиева Г.Ю.;

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

— Бунина Анастасия, г. Ревда Свердловской области, школа № 28, учитель Кольцова Е.М.;

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

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

— Варламова Ольга и Огурцова Ольга, г. Новокузнецк, школа № 100, учитель Папшева В.В.;

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

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

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

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

— Галанова Алла, г. Ярославль, школа № 33, учитель Цикина Е.Н.;

— Галиуллина Софья и Татаркин Максим, г. Новокузнецк Кемеровской обл., гимназия № 44, учитель Лобко Л.Н.;

— Богданцев Андрей, Галушкова Карина, ученица 1-го (!) класса, Каминский Константин, Карпова Варвара, Кудряшов Евгений, Малявкин Георгий и Смирнов Юрий, поселок Надвоицы, Республика Карелия, школа № 1, учитель Богданова Л.М.;

— Гарифуллина Лейсан, Адельшинская средняя школа, Чистопольский р-н Республики Татарстан, учитель Фатхутдинова А.А.;

— Гергенрендер Саша, Никитенко Татьяна и Тылик Даниил, г. Яровое, Алтайский край, Центр научно-технического творчества учащихся (ЦНТТУ), педагог Качина Т.В.;

— Глухова Ольга, Ефимов Олег, Коваль Кристина, Кошеварова Мария, Мезенцева Наталья, Пинтикова Юлия, Поспелова Мария и Смирнова Татьяна, средняя школа села Нижнеиргинское, Красноуфимский р-н Свердловской обл., учитель Ярунина А.В., а также ученица этой школы по имени Регина (фамилия в письме не была указана);

— Громов Андрей, Лягутова Мария, Норекян Лусине, Попов Андрей, Савинцев Александр, Савинцев Иван, Черных Валерия и Шабалина Александра, поселок Медведево, Республика Марий Эл, средняя школа № 3, учитель Рокина И.А.;

— Грошевой Сергей, Республика Татарстан,
г. Альметьевск, школа № 17, учитель Аристова Н.А.;

— Гумерова Наиля, Енгалычёва Анастасия, Орлов Сергей и Черепкова Анна, г. Нижний Новгород, педагогический колледж им. К.Д. Ушинского, преподаватель Занозин Д.А.;

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

— Данилов Дмитрий, Ехлаков Дмитрий и Жигалов Денис, Кезская средняя школа № 1, Удмуртская Республика, учитель Ветошкина Н.В.;

— Дудина Светлана и Идиятов Владимир, г. Ревда Свердловской области, школа № 28, учитель Кольцова Е.М.;

— Дьякова Екатерина, Зенкина Наталья, Кичигин Виктор, Титова Анна и Тынер Анна, Омская обл., поселок Марьяновский, школа № 3, учитель Кичигина М.Л.;

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

— Епифанов Илья, Зуйков Денис, Курилкин Дмитрий, Николаев Никита, Попов Сергей и Шмуляев Андрей, г. Струнино Владимирской обл., школа № 11, учителя Волкова Т.П. и Волков Ю.П.;

— Еропкина Юлия и Чеботарева Екатерина, участники компьютерного кружка Дворца детского творчества им. В.П. Чкалова, г. Нижний Новгород, педагог Занозина Г.В.;

— Ефанова Ирина, г. Курган, школа № 10, учитель Хазова Т.М.;

— Жолудева Анна, Лазюк Александра и Хамрина Марина, г. Сегежа, Республика Карелия, школа № 6, учитель Маркевич Н.В.;

— Зайнуллина Алена, Чупрунов Александр и Шмарлина Дарья, г. Ярославль, школа № 4 им. Н.А. Некрасова, учитель Макова Т.Н.;

— Зартдинов Альберт, г. Нурлат, Республика Татарстан, школа № 2, учитель Нургатина Г.И.;

— Иванищев Богдан, г. Бор Нижегородской обл., школа № 6, учитель Голодухина Е.В.;

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

— Иванов Павел, Москва, НОУ “Школа Сотрудничества”, учитель Наумкина М.В.;

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

— Канев Бронислав, Микишев Артем и Хамитова Альбина, г. Инта, Республика Коми, гимназия № 3, учитель Беспалько Н.Т.;

— Кириенко Наталья, Першина Арина, Попов Никита и Прокопьев Иван, г. Новокузнецк Кемеровской обл., гимназия № 44, учитель Дубовицкая Н.В.;

— Кожунова Надежда и Шелехова Анна, г. Челябинск, школа № 124, учитель Юртаева Г.Ю.;

— Колмыкова Мария, г. Омск, школа № 28, учитель Козлова М.Л.;

— Коптяева Екатерина, Коржова Александра и Нестерова Ольга, Тюменская обл., Ханты-Мансийский АО — Югра, Октябрьский р-н, село Шеркал, Шеркальская национальная средняя общеобразовательная школа, учитель Ефименко А.Н.;

— Коротких Мария и Яценко Яна, г. Новокузнецк Кемеровской обл., гимназия № 44, учитель Митина Н.В.;

— Костров Алексей, средняя школа села Матвеево, Парфентьевский р-н Костромской обл., учитель Кострова Г.Л.;

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

— Леонтьева Валентина и Чурбанова Мария, Республика Чувашия, г. Ядрин, Ядринская национальная гимназия-интернат, учитель Трофимова С.Н.;

— Левкина Татьяна, Пикалова Ирина и Фаткина Анна (фамилия автора еще одного ответа в письме не указана), средняя школа села Васильевка, Липецкая обл., Воловский р-н, учитель Горбовская Н.М.;

— Ляпунова Татьяна, Михеева Ирина, Сидорова Олеся и Чурсанов Алексей, средняя школа села Лешуконское, Архангельская обл., учитель Пахова Т.М.;

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

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

— Морозова Дина, Республика Татарстан, г. Казань, школа № 22, учитель Осипова А.А.;

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

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

— Мусина Ляйсан, г. Учалы, Республика Башкортостан, лицей № 12, учитель Рязапова Ч.П.;

— Нахатакян Седа, Республика Башкортостан, г. Белебей, школа № 8, учитель Яковлева А.Л.;

— Нилова Дарья, г. Ревда Свердловской обл., гимназия № 25, учитель Смогоржевская С.Ю.;

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

— Осипенко Семен, Пуртов Герман и Шамсутдинова Татьяна, Тюменская обл., Ханты-Мансийский АО — Югра, Октябрьский р-н, поселок Заречный, МОУ “Зареченская основная общеобразовательная школа”, учитель Антонова О.В.;

— Панасенко Илья, средняя школа села Стретенка Дальнереченского р-на Приморского края, учитель Панасенко Л.В.;

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

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

— Полищук Евгения и Тищенко Владимир, г. Талнах Красноярского края, школа № 38, учитель Тищенко Ю.Н.;

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

— Русских Марина, г. Омутнинск Кировской обл., школа № 1, учитель Запольских И.А.;

— Семенова Эвелина, Республика Саха (Якутия), село Амга, школа № 2, учитель Семенов Е.Е.;

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

— Смолин Владимир, село Комсомольское, Республика Чувашия, школа № 1, учитель Родионов П.В.;

— Смольняков Вячеслав, г. Щелково, Московская обл., школа № 10, учитель Грибченко И.В.;

— Удовиченко Евгений, г. Старый Оскол Белгородской обл., школа № 15, учитель Герасимова Н.М.;

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

— Хайбулин Егор, г. Ярославль, средняя школа № 12, учитель Каменовская Е.В.;

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

— Часнык Елизавета и Щеголькова Дина, г. Смоленск, школа № 29, учитель Родикова Р.Д.;

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

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

— Шумилова Радмила, село Первореченское Динского р-на Краснодарского края, школа № 28, учитель Бауэр Н.Е.;

— Якушев Игорь, село Майма Майминского р-на, Республика Алтай, Республиканский классический лицей, учитель Гребенников С.К.,

а также ученики школы № 5 г. Стерлитамак, Республика Башкортостан, учитель Наумова О.Л.: Габитов, Дмитриева, Ефремова, Хруцкая, Иванова, Крылова, Кулаков, Кутлубаев, Михайлова, Муртазина, Николаева, Перов, Шварёва (имена учащихся, к сожалению, в письме не указаны).

Поскольку данный конкурс вызвал у читателей очень большой интерес (о чем свидетельствует приведенный список участников), разберем решение подробно.

Прежде всего заметим, что, как правильно установили большинство участников конкурса, из приведенных в условии терминов можно составить последовательность, в которой будут представлены все 64 слова. Но приводить все возможные последовательности (цепочки) мы не будем, поскольку их… триллионы (!). Не верите? Давайте разберемся.

Выпишем все заданные термины “столбиком”:

абак

абзац

…

ярлык

ячейка

Видно, что есть слова, у которых совпадают первые и последние буквы: архитектура, дисковод, модем, растр, регистр, редактор, размер, текст. Ясно, что их можно будет вставить внутри полученной цепочки в любом месте, где уже имеются слова, оканчивающиеся на буквы а, д, … . Каким числом способов это можно сделать? Этот вопрос пока оставим без ответа, а рассмотрим слова другого типа — группы слов, которые начинаются на одну и ту же букву и оканчиваются на одну и ту же букву. Такие группы следующие:

1) абонент, алфавит, аплет, атрибут;

2) команда, корзина;

3) лента, линейка, логика;

4) развертка, рамка, раскладка;

5) разъем, режим;

6) таблица, текстура;

7) таймер, триггер;

8) язык, ярлык.

Термины каждой группы будем называть взаимозаменяемыми, поскольку, где бы ни стояли они в результирующей цепочке слов, их можно переставлять (менять местами друг с другом). Когда “взаимозаменяемых” слов в группе — 2, число возможных вариантов цепочек — также 2. Если таких слов в группе — 3, то количество возможных вариантов цепочек равно шести (убедитесь в этом!), если 4 — 24. Вы, наверное, уже установили общую формулу расчета соответствующего числа вариантов — оно равно факториалу² числа слов в группе. А поскольку каждый из возможных вариантов для каждой группы можно сочетать с каждым из возможных вариантов для другой группы, то общее число вариантов размещения всех “взаимозаменяемых” слов равно 24 · 2 · 6 · 6 · 2 · 2 · 2 · 2 = 27 648.

Вернемся теперь к словам типа архитектура, дисковод, … . В каком количестве мест можно разместить слово архитектура? Ответ — в 12 (столько слов начинаются и оканчиваются на букву а, без учета самого слова архитектура). Для слова дисковод соответствующее число вариантов равно 2, для слова модем — 4, для слова текст — 7. Сложнее со словами растр, регистр, редактор, размер. Можно рассуждать так. Число оставшихся слов на букву р — 8. “Наши” четыре слова мы можем распределить по этим восьми словам количеством способов, которое равно³:

Кроме того, в каждом из этих 70 способов можно менять порядок размещения наших четырех слов. Следовательно, общее число вариантов размещения слов растр, регистр, редактор и размер равно 70 · 4! = 70 · 24 = 1680, а вариантов размещения слов архитектура, …, размер, текст — 12 · 2 · 4 · 1680 · 7 = 1 128 960.

С учетом размещения еще и всех “взаимозаменяемых” слов число различных цепочек равно 1 128 960 · 27 648 = 31 213 486 080.

Далее, многие участники конкурса правильно определили, что полученная ими цепочка терминов имеет следующую особенность: ее последнее слово оканчивается на букву, с которой начинается первое слово (они назвали такую цепочку “кольцевой”). Это означает, что начинать цепочку можно с любого из 64 слов. А из этого, в свою очередь, следует, что каждую из 31 213 486 080 цепочек можно записать 64 различными способами, т.е. общее число вариантов последовательностей слов равно 31 213 486 080 · 64 = 1 997 663 109 120 (!). Вот вам и триллионы, о которых шла речь в начале…

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

Прежде всего можно убрать из полного перечня слова архитектура, …, размер, текст (записав их где-то отдельно). Как указывалось, эти слова потом можно будет вставить в какие-то места получившейся цепочки.

Далее можно увидеть, что среди заданных слов есть слова, “уникальные” с точки зрения первой буквы: браузер, график, журнал, набор, откат, пробел, цикл, шаблон. С каждым из этих слов можно “связать” единственно возможные другие слова, образовав “подцепочки”: масштаб — браузер, аналог — график, арбитраж — журнал, кэш — шаблон — набор, слово — откат, лэптоп — пробел, абзац — цикл.

После этого методом проб можно увеличивать перечисленные подцепочки и пробовать соединять их в еще более длинные. В результате, как указывалось, можно получить какую-то цепочку из 56 терминов. Дальнейшие действия очевидны (размещение слов архитектура, дисковод, …, размер, текст; перестановки “взаимозаменяемых” слов и др.).

Победителями конкурса признаны участники, приведшие несколько вариантов последовательностей⁴, описавшие методику их получения, представившие необходимые расчеты и т.п.:

— Афлятунов Эраст, Игошев Станислав и Мельник Алексей, г. Лениногорск, Республика Татарстан, школа № 8, учитель Кашапова Р.Х.;

— Громов Андрей, Лягутова Мария, Норекян Лусине, Попов Андрей, Савинцев Александр, Савинцев Иван, Черных Валерия и Шабалина Александра, поселок Медведево, Республика Марий Эл, средняя школа № 3, учитель Рокина И.А.;

— Грошевой Сергей, Республика Татарстан,
г. Альметьевск, школа № 17, учитель Аристова Н.А.;

— Епифанов Илья, Зуйков Денис, Курилкин Дмитрий, Николаев Никита, Попов Сергей и Шмуляев Андрей, г. Струнино Владимирской обл., школа
№ 11, учителя Волкова Т.П. и Волков Ю.П.;

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

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

— Осипенко Семен, Пуртов Герман и Шамсутдинова Татьяна, Тюменская обл., Ханты-Мансийский АО — Югра, Октябрьский р-н, поселок Заречный, МОУ “Зареченская основная общеобразовательная школа”, учитель Антонова О.В.;

— Тищенко Владимир, г. Талнах Красноярского края, школа № 38, учитель Тищенко Ю.Н.;

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

— Хайбулин Егор, г. Ярославль, средняя школа № 12, учитель Каменовская Е.В.;

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

Все они будут награждены дипломами. Поздравляем!

Чемпионат СНГ среди школьников по решению судоку :). Тур 1

Напомним (см. газету-вкладку “В мир информатики” № 78 / “Информатика” № 19/2006), что судоку — это головоломка, представляющая собой квадрат 9 х 9:

Он разбит на 9 квадратиков 3 х 3. Задача состоит в том, чтобы заполнить пустые клетки таким образом, чтобы в каждом квадратике, в каждой строке и каждом столбце “большого” квадрата был полный набор цифр от 1 до 9.

Решите, пожалуйста, приведенный судоку.

² Напомним, что факториалом натурального числа n (обозначается n!) называют произведение 1 • 2 • 3 • …• n. Заметим также, что комбинации из различных “положений” взаимозаменяемых слов в математике называют перестановками.

³ Приведенное выражение равно количеству сочетаний из 8 элементов по 4. Что такое сочетания? Если из m различных элементов составлять группы по n элементов в каждой, не обращая внимание на порядок элементов в группе, то получающиеся при этом комбинации в математике называются “сочетаниями из m элементов по n”. В общем случае число сочетаний из m элементов по n может быть определено по формуле: .

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