Всем привет. Впереди длинные выходные, а погода (в средней полосе России) не шепчет. Посему хочу предложить вам развлекалочку на стыке математики и программирования, а также возможность немного улучшить свое финансовое положение 😊.
История эта началась лет 10 назад, когда моя дочь София Валерьевна принесла задачку (автор ее -Дмитрий Юрьевич Кузнецов аka ДЮК) с олимпиады для 7го класса.
"Незнайка записывает 9 разрядов 10-значного десятичного числа и пропускает один по своему выбору. Пропущенный разряд он предлагает записать Винтику, а затем показывает полученное 10 -значное число Шпунтику. Как могут Винтик и Шпунтик договориться, чтобы Шпунтик угадал, какой именно разряд записал Винтик? "
Ну, то есть Незнайка может написать что то такое – 01234...6789 (ведущие нули допускаются). Или такое 000111...223. Или вообще вот такое ...777777777. Винтик дописывает одну недостающую цифру (пусть в первом случае это будет 5). Затем Незнайка показывает полученное число 0123456789 Шпунтику. И тот должен угадать что именно пятый разряд Незнайка пропустил, а Винтик, соответственно, записал.
Одно решение найти несложно – оно вполне доступно и семикласснику. Шпунтик вычисляет остаток от деления на 10 суммы всех разрядов десятичного числа, которое видит. В нашем случае она равна 45. И ,значит, 5 – номер пропущенного разряда. Но я уже далеко не семиклассник, а потому думал над задачей ... два года, прежде чем до меня наконец дошло 😁. Правда, параллельно я сообразил, что решение отнюдь не единственно. И задался вопросом – а сколько всего их существует?
Сам того не подозревая, я открыл математический “Ящик Пандоры”. И уже два года извлекаю оттуда все новые и новые факты. Но ящик, все также кажется бездонным и общего решения до сих пор нет. Поначалу мне казалось, что я столкнулся с какой-то известной задачей теории групп, комбинаторики или кодирования. И я обращался к нескольким ведущим математикам современности в надежде, что они мне все растолкуют. Но они уходили и не возвращались... Пару недель назад в Нижнем Новгороде проходил финал Всероссийской Олимпиады Школьников по математике и я воспользовавшись (злоупотребив 😁) служебным положением прямо со сцены озадачил молодые умы. Но и они пока тоже хранят молчание... Потому мне остается последнее средство – обратиться к читателям Хабра.
Итак, вопрос на который предстоит найти ответ.
Сколько есть взаимно- однозначных отображений между множествами 109(записанные Незнайкой разряды)*10(номер пропущенного) и 1010 (десятизначное число, которое видит Шпунтик)?
Призовой фонд – 50 000 рублей.
Решения принимаются в комментах к данному посту или в личные сообщения на Хабр до 8.06.2024. Итоги будут подведены к 13-му июня (у меня как раз ДР). А после обещаю статью с детальным разбором задачи. Где поделюсь всем, что знаю сейчас и всем, что (надеюсь) узнаю за следующий месяц.
Сразу оговорюсь, что иметь дело с десятичным случаем довольно тяжело. Задача сводится к расстановке небьющих друг друга ладей на некотором подмножестве доски размером 1010x1010. Поэтому проще анализировать "редуцированные" случаи – двоичный (два разряда и бинарные значения 0,1), тернарный (три разряда со значениями 0, 1, 2), четверичный и тд.
Поэтому в качестве критериев определения победителя (или победителей) я выбрал следующие.
Предпочтение будет отдаваться чисто математическим методам решения перед компьютерным перебором. Если кто сумеет одолеть Винтика и Шпунтика исключительно с помощью “бумаги и ручки”, не включая компьютер, – тому честь, хвала и денежный приз. 😁. Только вот у меня есть некоторые сомнения, что совсем без компа получится....
«Размерность» решения. Ну то есть, если кто то осилит шестеричный случай он будет иметь преимущество перед тем, кто решил пятеричный. Для справки – пока полностью просчитан только тернарный.
Для компьютерных алгоритмов будет оцениваться производительность решения. Ибо задача огромна.
Ну и наличие точного ответа (числа решений).
Вот такой челендж. Удачи всем, кто решит попытать счастья в борьбе с Винтиком и Шпунтиком.
P.S. Если остались какие-то вопросы – задавайте в комментах.
P.P. S. Кое‑ какие сведения о задаче и методах ее решения можно найти в моем телеграм‑канале «Китайский русский». Например, здесь, здесь и здесь.
