Всем привет. Впереди длинные выходные, а погода (в средней полосе России) не шепчет. Посему хочу предложить вам развлекалочку на стыке математики и программирования, а также возможность немного улучшить свое финансовое положение ?.
История эта началась лет 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. Кое‑ какие сведения о задаче и методах ее решения можно найти в моем телеграм‑канале «Китайский русский». Например, здесь, здесь и здесь.
Комментарии (53)
Epromee
08.05.2024 14:42+2Мне стало интересно попробовать свои силы, чтобы оценить количество похожих решений (где надо складывать разряды по модулю 10). Для всех возможных решений это, стало быть, нижняя граница.
Возможно, кому-то мои соображения будут интересны; а если кто-то опровергнет мои размышления - это будет поучительно и интересно мне самому, поэтому и пишу.
Дисклеймер 1: ради разминки для ума хотелось решить "без спойлеров", поэтому, инфо в Телеграм я не читал. Возможно, там это уже описано и я не сказал ничего нового. Так же, не исключаю, что я вообще неправильно понял постановку задачи.
Дисклеймер 2: на приз не претендую, т. к. даже если бы я прям хотел приз - я не доказываю отсутствие прочих решений, чем те, класс которых я рассматриваю, т. е. решений может быть больше моих, а если их больше нет, это надо отдельно доказывать, на что у меня не хватает математической подготовки.
Дисклеймер 3: я не математик, и даже если я полную чушь написал, прошу сильно не бить, а то и так неловко публично позориться XD, вместо этого - предлагаю указать на мои ошибки, кто-то другой их учтёт и, возможно, получит приз.
upd/edit: слишком длинно получилось, убрал в спойлер.
Hidden text
Решение 1, слабое (в его корректности я почти не сомневаюсь).
Я буду нумеровать разряды от 0 до 9, чтобы совпадать с самими цифрами.
Исхожу из того, что Шпунтик точно так же будет складывать все разряды и брать сумму по модулю 10. Но перед сложением, значение каждого разряда будет независимо "отображено" в другой набор чисел 0-9.
Можно считать, что в тривиальном решении как в оригинальном посте, для всех 10 разрядов задано identity преобразование (ничего не делать).
Итоговая сумма в двух разных способах для двух одинаковых наборов цифр может совпадать, но в общем случае найдётся набор, где итоговая сумма для двух способов будет отличаться.
Пример отображения, если я невнятно пишу:
0 -> 4, 1 -> 5, 2 -> 3, 3 -> 7, 4 -> 6, 5 -> 0, 6 -> 1, 7 -> 9, 8 -> 2, 9 -> 8Т. е. к каждому разряду будет применена некая функция перестановки, причём независимая от функций других разрядов. Существует 10! способов отобразить набор чисел от 0 до 9 в набор чисел от 0 до 9, чтобы два разных числа не отображались в одно и то же число.
Вариантов отображений для всей строки тогда будет (10!)^10, т. е. разрядов 10, и каждый разряд отображается одним из 10! способов.
Слабый ответ: у задачи как минимум (10!)^10 решений.
Решение 2, более сильное (и тут в его корректности я уже сомневаюсь).
Теперь, предположим, что разряды могут влиять друг на друга, скажем, 0-й разряд отобразится "по-старому" каким-то из 10! способов, а каким конкретно способом выберет 1-й разряд.
То есть, 1-й разряд преобразуется по старому, и в зависимости от полученного значения выбирается 1 из 10 вариантов отображения 0-го разряда, а каждый вариант отображения нулевого разряда это 10! способов.Так, мы можем назначить 10 вариантов из 10! способов 0-му разряду, но 1-й разряд ведь и сам сначала отображается одним из 10! способов.
Это можно представить, будто бы у нас не 1 нулевой разряд, а 10 нулевых разрядов, каждый со своим отображеним, и первый разряд выберет нам конкретный нулевой разряд.
Если эту идею обобщим, то получится, что n-ный разряд отображается 10! способами, и затем, полученное значение n-ного разряда выбирает одно из некоторых 10 правил отображения разрядов для всей предыдущей строки 0 до n-1. То есть, как будто у нас 10 строк от 0 до n-1, а n-ный разряд из них выбирает одну конкретную.
Тогда, если F(n) - это количество способов безусловно отобразить строку от 0 до n, то, добавляя очередной разряд, имеем уже (F(n)^10) способов условно в зависимости от (n+1)-го разряда отобразить строку от 0 до n; т. е. у нас есть 10 вариантов строки, каждый из которых отображается F(n) способами, значение (n+1)-го разряда выбирает конкретный 1 вариант из 10; всё это дело умножается на 10! способов отобразить собственно (n+1)-й разряд; так мы получаем полное количество способов отобразить строку от 0 до n+1.
F(n+1) = (F(n)^10)*(10!)
Теперь, есть 0 разряд, для которого вообще нет предыдущей строки, и он, очевидно, не влияет на предыдущую строку, а только отображается сам. Для него вводим особое условие.
F(0) = 10!
Старое рекурсивное условие перепишем:
F(n) = (F(n-1)^10)*(10!)
Мы собрали рекурсивную функцию, теперь, последний разряд в условии задачи 9, и для минимальной оценки нам осталось вычислить её для 9:
F(9)
Так мы (если я правильно рассуждаю) должны получить минимальное количество решений, но лично я боюсь запускать эти вычисления :)
К примеру, для 2 разрядов, F(1) равно (10!^10)*(10!), это будет равно 1436790214985056541243375671256147299530515278725120000000000000000000000 способов отображения всей строки из 10 разрядов.
Сильный ответ: решений у задачи как минимум F(9), где F(n) = (F(n-1)^10)*(10!), а F(0) = 10!
F выдаёт страшные числа, поэтому, для самопроверки, убедимся, что число отображений, вычисляемое функцией F, не больше всех возможных отображений (без ограничений на повторяемость цифр). Сколько вообще есть функций? Если у нас множество из n значений, существует n^n способов задать функцию. По аналогии с F, определим количество способов задать любые отображения на строках, минимальный номер разряда которых равен n:
G(n) = (10^(n+1))^(10^(n+1))
Для строк с одним разрядом (нулевым), будет:
G(0) = 10^10 (это больше, чем F(0), равное 10!, тут всё хорошо)
Если восстановить рекурсивное соотношение (и я не ошибся в преобразованиях), получится:
G(n) = (G(n-1)^10) * (10^(10^(n+1)))
Каждый "шаг" тут домножается на 10^(10^(n+1)), а в F на гораздо меньший (10!).
Таким образом, мы доказали, что "ограниченные отображения" не превышают количества всех возможных отображений.
P. S. Ещё прошу простить за формулы плоским текстом. Я сначала написал решение в текстовом файле. Перенося в Хабр, в редакторе формул, как ни бился, не смог набрать возведение в степень, при наборе "^" вся формула исчезает, пытаюсь вслепую написать "10", и после ввода единицы режим степени отключается, и 0 уже некуда писать. Поэтому, решил оставить все формулы плоскими, нежели часть плоскими, а часть красивыми.Epromee
08.05.2024 14:42+2Подумал ещё и понял, что предлагаемое мной решение номер 2 не гарантирует, что изменение преобразования левой от изменяемого разряда части строки сохранит возможность выбора любой суммы по модулю.
Контрпример - предположим, отображение работает так:Hidden text
0123456780 -> 2000000081
0123456781 -> 2000000072
0123456782 -> 2000000063
0123456783 -> 2000000054
0123456784 -> 2000000045
0123456785 -> 2000000036
0123456786 -> 2000000027
0123456787 -> 2000000018
0123456788 -> 2000000009
0123456789 -> 2000000090Тогда, если мы используем в качестве функции суммирования сумму цифр по модулю 10, какую бы цифру ни подставил Винтик в такую строку:
"012345678_"
Всегда получится, что сумма равна "1", т. е. Винтик не сможет "подогнать" ответ под 9.
vvvphoenix Автор
08.05.2024 14:42Добрый день. По части "cлабого" решения - да, эти соображения корректны. Однако они дают лишь очень небольшую долю решений. У меня по некоторым прикидкам получалась оценка ((10^9))!/(((10^8)!)^10). И это только один из множителей. С "сильным" решением сейчас буду еще разбираться.
PS. Cогласен, формулы планарным текстом выглядят жутко... :)
Epromee
08.05.2024 14:42Ну, я уже сам себя опроверг :) Позже я смутно сообразил, в какую сторону примерно следует думать, но там мои математические возможности пока заканчиваются.
Ещё момент, я заметил по комментариям, что не всем понятно условие задачи. И, если честно, я тоже не сразу въехал (т. к. не сразу ясно, что значит "договориться", и какое мы отображение ищем). Хочу предложить вам на ваше усмотрение добавить в описание такую или какую-либо похожую переформулировку:
Не уверен, насколько сам ясно написал, но надеюсь, кому-то поможет
Пусть F - функция, отображающая строку S из 10 цифр в 1 десятичную цифру:
Назовём F функцией Незнайки, если для любых 10 строк Si, любая пара которых отличается одной и только одной цифрой (все разряды одинаковые, кроме одного), верно тождество
Вопрос - сколько существует различных функций Незнайки?
Интуитивная иллюстрация - мы берём рандомную строку, в ней тыкаем рандомный разряд, "прокручиваем" его от 0 до 9, и F от этой строки обязательно пробежит все значения от 0 до 9, хоть и необязательно в таком же порядке. Тем самым, что бы ни загадал Незнайка, Винтик всегда "прокрутит" рязряд в нужный ему номер. Выбор конкретной функции Незнайки - это способ Винтика и Шпунтика "договориться". Таким образом, количество функций Незнайки = количество способов решить задачу.
P. S. Всё, разобрался с формулами - цвет фона тёмной темы совпадал с цветом шрифта формул в TeX-режиме, вот я и не мог их набрать.
leok
08.05.2024 14:42+1Ответ на вопрос, сколько существует взаимно однозначных отображений между двумя множествами конечного размера довольно прост: N!
vvvphoenix Автор
08.05.2024 14:42+1Это, конечно так. Если б у нас была полная доска 10^10x10^10 то небьющие друг друга ладьи можно было бы расставить (10^10)! способов. Но тут наложено ограничение. Например, если Незнайка приносит число ...777777777, то на выходе мы можем получить только 0777777777, 1777777777,...9777777777. Поэтому решений меньше.
datacase
08.05.2024 14:42Вставляемая Винтиком цифра должна должна давать такую сумму всех цифр, последний разряд которой равен позиции вставляемой цифры. Делением на 10 только усложняется смысл.
vvvphoenix Автор
08.05.2024 14:42Ну в сущности - это одно и тоже :). Согласен - на 10 можно и не делить :)
Arastas
08.05.2024 14:42Не понял формулировку - Незнайка называет цифру, а Винтик выбирает место? Или же Винтик выбирает и цифру и место?
vvvphoenix Автор
08.05.2024 14:42Нет. Незнайка оставляет один разряд незаполненным по своему произволу. И по своему же произволу записывает девять разрядов. Таким образом Винтик видит что то такое 01234...6789. И должен вместо троеточия записать какую то цифру
SquareRootOfZero
08.05.2024 14:42+12"Короче, Шпунт, у Незнайки синяя авторучка, а у меня - толстый красный карандаш."
Wesha
08.05.2024 14:42Это даже не нужно отдельно обговаривать. Одна цифра, записанная не тем же письменным прибором или не тем же почерком — записана Винтиком!
xi-tauw
08.05.2024 14:42+2Как-то не уловил как автор собирается различать решения. Например, возьмем способ, которые приведен в статье (сумма по модулю 10). Теперь, я предложу другое решение - делаем все ровно так же, но Винтик пишет число на 1 меньше, а Шпунтик, соответственно, после своих вычислений увеличивает число на 1. Это другое решение (дает разные цифры) или то же (суть-то модулярного сложения остается)?
qbertych
08.05.2024 14:42+2Ох уж эти пост-мета-версии школьных олимпиадных задачек, подержите мое пиво!
Время диалапа и бумажных автобусных билетов, на каждом билете выбит шестизначный номер. Билеты бывают счастливые: в Москве это значит, что совпадают суммы первых трех и последних трех цифр, в Питере - что совпадают суммы цифр на четных и нечетных местах. Можно придумать свой рецепт счастья и сравнивать, например, суммы цифр на первом, втором и четвертом месте с остальными. Но на самом деле интересный вопрос в другом: а сколько существует билетов, цифры в которых нельзя разбить ни на какие две группы с равной суммой?
На самом деле таких билетов довольно много, поэтому хочется ввести еще пару ограничений. Их я уже не помню, но кажется мы вводили условия на 1) четную сумму всех цифр (иначе какие вам две группы), 2) все цифры должны быть разными. И назвали такие билеты суперсчастливыми. Было очевидно, что их мало, но сколько - неясно.
Как-то раз мне стало скучно в поезде, и я нашел все такие комбинации перебором :) их оказалось то ли 7, то ли 9. Но в седьмом классе было сложно додуматься до самого интересного вопроса: а есть ли у задачи аналитическое решение?
P.S. По-моему, мы обсуждали этот вопрос с Дмитрием Юрьевичем. Но недолго: у него всегда было много гораздо более интересных задач ;)
avshkol
08.05.2024 14:42+2Они ведь могли договариваться и об алгоритмах:
Если Незнайка записал все цифры одинаковые, то пиши неодинаковую.
Если все цифры Незнайки одинаковые кроме одной, то пиши 0, если эта одна 0 - то 9. Если это девятки, то 8.
И т.п.
И количество таких алгоритмов будет сопоставимо с количеством всех возможных перестановок 9 чисел с повторениями...
Wesha
08.05.2024 14:42Незнайка записывает 9 разрядов 10-значного десятичного числа и пропускает один по своему выбору. Пропущенный разряд он предлагает записать Винтику, а затем показывает полученное 10 -значное число Шпунтику. Как могут Винтик и Шпунтик договориться, чтобы Шпунтик угадал, какой именно разряд записал Винтик?
Ну, например, Шпунтик и Винтик договариваются, что после того, как Винтик записал разряд, он звонит Шпунтику по телефону и говорит, какой разряд он записал? В условии задачи нет ничего, что запрещало бы В и Ш обмениваться инцормацией по side channel, а "всё, что явно не запрещено условием, разрешено"...
sophist
08.05.2024 14:42+1Оставим в стороне вопрос о том, насколько это остроумно, и подумаем вот над чем: что было бы, если бы формулировки задач были совершенно строгими?
vadimr
08.05.2024 14:42+1В статье сначала описывается одна задача, а потом задаётся совершенно другой вопрос.
Количество алгоритмов (в широком смысле, т.е. любых функций) для ОПГ "Винтик и Шпунтик" и количество различных взаимно-однозначных отображений между множествами чисел – это две совершенно разные вещи. Первое континуально, второе конечно. Очевидно, что к одному и тому же результату можно приходить разными алгоритмами.
А если учесть, что Винтик и Шпунтик должны договориться между собой за конечное время, используя дискретный конечный алфавит, тогда получается третий результат. Тоже конечное число.
vadimr
08.05.2024 14:42+1Если рассуждать только об отображениях множеств, то Винтик и Шпунтик имеют на входе таблицу из всех возможных комбинаций 10 цифр – 9 написанных Незнайкой плюс номер пропущенного разряда. Чтобы получить полный набор правил для себя, они должны к каждой строке из этой таблицы приписать свою цифру, которая однозначно кодирует номер пропущенного разряда, то есть последний столбец таблицы. Содержимое первых 9 цифр важно для коммуникации Винтика и Шпунтика об алгоритме, но не представляет никакой значимости для заданного вопроса. По сути, результаты отличаются только способом кодирования 10 позиций при помощи 10 цифр, то есть способом упорядочивания 10 элементов. Поэтому ответов, дающих численно разные результаты, существует 10!, то есть 3628800.
sophist
08.05.2024 14:42+1Винтик и Шпунтик имеют на входе таблицу из всех возможных комбинаций 10 цифр – 9 написанных Незнайкой плюс номер пропущенного разряда.
Не совсем так. Это Винтик имеет такую таблицу. А Шпунтик имеет другую таблицу: синтаксически это всё те же комбинации 10 цифр, но семантически это 9 цифр, написанных Незнайкой, плюс одна, написанная Винтиком, -- а номер пропущенного разряда как раз ему неизвестен.
Винтик отображает первую таблицу во вторую, а Шпунтик -- вторую в первую. Поэтому и требуется взаимная однозначность.
vadimr
08.05.2024 14:42+1Если мы начинаем думать о коммуникации между Винтиком и Шпунтиком, это осложняет рассмотрение лишними подробностями, но ничего не даёт по существу заданного вопроса. Проще здесь их рассмотреть, как единое целое. У нас одной цифрой, которую пишет Винтик, кодируется одна цифра, которая является номером пропущенного разряда, вот что важно. А как кодируется - нас не спрашивают.
Эта задача может иметь либо 0 решений (если Шпунтик не в состоянии восстановить информацию), либо 10!. Поскольку одно решение мы нашли, то их 10!. Все их можно получить перестановками кодовой последовательности в первом решении, а других не существует в силу ограниченной ёмкости канала связи.
Другими словами, соответствий между цифрой, которую написал Винтик, и цифрой, которую произнёс Шпунтик, ровно 10! в силу природы цифр.
sophist
08.05.2024 14:42+1Позвольте, заданный вопрос существенно полагается на формат коммуникации между Винтиком и Шпунтиком -- а именно на возможность однозначно восстановить прообраз продемонстрированной Шпунтику комбинации. Не любое отображение годится, а лишь то, которое обладает таким свойством.
И разумеется, номер пропущенного разряда кодируется не просто одной цифрой, которую пишет Винтик, а этой цифрой, взятой в контексте, заданным Незнайкой.
vadimr
08.05.2024 14:42+1То, что Вы пишете, верно, но несущественно для ответа на поставленный автором вопрос.
Я говорю о том, что, найдя одно отображение, удовлетворяющее условиям задачи, мы можем получить из него все остальные просто перестановками кодовой таблицы (например, договорившись, что ответ 6 обозначает 2, 2 обозначает 3, а 3 обозначает 6 и т.д.). Любое другое отображение, позволяющее восстановить прообраз, будет совпадать с одним из отображений в полученных перестановках, потому что никак по-другому, чем 10! способами, одну десятичную цифру из другой невозможно получить без потери информации. А терять информацию мы здесь не имеем права, её ровно впритык.
Контекст мы здесь выносим за скобки, хотя он, конечно, оказывает влияние на наше первое решение.
У Винтика на выходе одна цифра, и у Шпунтика на выходе одна цифра. Всё. Как они их вычисляют, неважно. Число возможных взаимно-однозначных комбинаций этих двух цифр сверху ограничено 10!, и все их мы построили путём перестановок кодовой таблицы из одного способа. При этом совершенно неважно, что Шпунтик не знает, какую именно цифру написал Винтик.
Таким образом, окончательный полный ответ такой:
Алгоритмов для В&Ш вообще континуально много.
Дискретных конечных алгоритмов для В&Ш счётно много.
Таких алгоритмов, которые В может согласовать с Ш – конечное число, определяемое временем на согласование и пропускной способностью канала переговоров.
Алгоритмов, отличающихся по своим результатам – 3628800.
Stiver
08.05.2024 14:42Всё. Как они их вычисляют, неважно. Число возможных взаимно-однозначных комбинаций этих двух цифр сверху ограничено 10!, и все их мы построили путём перестановок кодовой таблицы из одного способа. При этом совершенно неважно, что Шпунтик не знает, какую именно цифру написал Винтик.
А для троичного случая (трехзначное число и три цифры 0,1,2) у вас по этой логике сколько решений получается?
vadimr
08.05.2024 14:426, конечно.
Цифра, которую написал Винтик – цифра, которую произнёс Шпунтик:
0-0 1-1 2-2
0-1 1-0 2-2
0-2 1-1 2-0
0-0 1-2 2-1
0-1 1-2 2-0
0-2 2-0 2-1
Можете попробовать придумать алгоритм, который не сводится к одному из этих 6 случаев.
Stiver
08.05.2024 14:42+16, конечно
Маловато будет :) Вы отбрасываете в рассуждениях контекст и теряете информацию, предполагая, что отображение для каждой цифры постоянно.
Ниже пример решения, где '-' означает пропущенный разряд. Перед стрелочкой стоит число, которое Незнайка передал Винтику, после нее - которое Винтик передал Шпунтику. (Прошу прощения за форматирование, новый редактор комментариев - углючище нерукотворное).
Пример
-00 -> 000
-01 -> 101
-02 -> 002
-10 -> 110
-11 -> 111
-12 -> 212
-20 -> 220
-21 -> 021
-22 -> 222
0-0 -> 010
0-1 -> 011
0-2 -> 022
1-0 -> 100
1-1 -> 121
1-2 -> 122
2-0 -> 200
2-1 -> 211
2-2 -> 202
00- -> 001
01- -> 012
02- -> 020
10- -> 102
11- -> 112
12- -> 120
20- -> 201
21- -> 210
22- -> 221
vadimr
08.05.2024 14:42-00 -> 000
-01 -> 101
-02 -> 002
Если это решение, то какой алгоритм действий Винтика и Шпунтика в этом случае?
Просто сверить по таблице?
Stiver
08.05.2024 14:42Если это решение, то какой алгоритм действий Винтика и Шпунтика в этом случае?
У них обоих есть эта таблица. Винтик получает на вход левое число и передает Шпунтику правое. Шпунтик ищет правое и смотрит, какого разряда не хватает в левом.
P.S.
Просто сверить по таблице?
Именно так.
sophist
08.05.2024 14:42У Винтика на выходе одна цифра, и у Шпунтика на выходе одна цифра. […] Число возможных взаимно-однозначных комбинаций этих двух цифр сверху ограничено 10!
Откуда взялось требование взаимной однозначности этих цифр? Почему Шпунтик не может для одной и той же цифры Винтика вернуть разные цифры в зависимости от контекста?
levashovigor
08.05.2024 14:42+1Ничего не понял, но мне кажется, что Винтик посчитает сумму цифр, написанных Незнайкой, и добавит цифру от1 до 9 так, чтобы сумма цифр при делении на 9 имела остаток, равный номеру угадываемого разряда, начиная, например, слева (остаток 0 соответствует девятому разряду). Он сможет это сделать, т.к. прибавляя цифры от 1 до 9, он получит все девять различных остатков. При этом не возникает проблемы 0 в первом разряде, т.к. Винтик пишет ненулевую цифру. После этого приходит Шпунтик, считает сумму цифр, находит её остаток при делении на 9 и указывает по остатку номер нужного разряда. А все остальные решения какие-то выдуманные.
vadimr
08.05.2024 14:42С учётом замечаний, приведённых @Stiver, правильная оценка количества различных отображений, по-видимому, следующая.
Нам надо найти, сколькими способами правую часть таблицы, предложенной Стивером, состоящую из n**n чисел от 0 до n**n-1, можно разделить на n равных групп, причём порядок групп важен, так как номер группы – это ни что иное, как ответ Шпунтика, т.е. номер искомого разряда. Каждое различное разбиение на группы будет давать новое решение, других решений нет.
Беглый гуглинг показывает, что количество способов равно
где mn – размер таблицы, т.е. m = n**(n-1). В нашем случае, n=10 и m=10**9.
Arastas
08.05.2024 14:42При этом Винтик должен иметь возможность выбором числа в указанном ему разряде определить результирующее число в нужную группу. Это как-то учитывается?
vadimr
08.05.2024 14:42Винтик ищет увиденное перед собой в левом столбце таблицы и подставляет то число, которое прописано в правом столбце таблицы. Это наиболее общий алгоритм.
Arastas
08.05.2024 14:42+1Ваше деление на группы не может быть произвольным. Например, если в таблице все десять чисел вида 0?23456789, где ? это любая цифра от 0 до 9, отображаются в ту же группу, что и все десять чисел вида 01?3456789, то такая таблица не будет решением. Как мне кажется, у вас это не учтено.
vadimr
08.05.2024 14:42Да, это верно.
Тут надо умножить результат на вероятность того, что все числа совпадут с масками. А это довольно сложное выражение, так как вероятности условные, поскольку использованнные числа выходят из оборота. Но принципиально тогда всё должно сойтись.
Alexandroppolus
08.05.2024 14:42В этой формуле m! ведь сокращается? Остается (mn)! / (n!)^m, правильно?
vadimr
08.05.2024 14:42По логике вещей, да.
Alexandroppolus
08.05.2024 14:42Винтик может увидеть перед собой 10^10 различных раскладов (10 вариантов пропущенного разряда на 10^9 вариантов заполнения остальных разрядов), и должен в ответ на это придумать одно из 10 чисел (0...9). Т.е. у него в рамках решения зафиксирована функция кодирования (10^10) -> 10. Всего таких различных функций будет 10^(10^10).
И если я не ошибаюсь, то чтобы два решения были различными, в них должны быть разные функции кодирования. Соответственно, всего разных решений не более чем 10^(10^10), число длиной 10^10
(mn)! / (n!)^m - это прямо существенно больше. Я прикинул по формуле Стирлинга, тут получается число длиной 9 * 10^10. Вы хотели домножить на некую вероятность. Она должна быть совсем маленькой, с кучей нулей после запятой.
vadimr
08.05.2024 14:42Она и есть маленькая. Чтобы два списка из 10 миллиардов 10-значных чисел попарно совпали в каждом элементе в 9 разрядах.
Для одной строки вероятность совпадения 1e-9, и это число грубо надо возвести в степень 1e10, то есть для всей таблицы 1e-9**1e10. Но на самом деле вероятность условная, числа в каждой группе сильно мешают друг другу (если мы уже использовали одно число, подходящее под маску, то найти следующее менее вероятно), поэтому результат ещё меньше.
Так что тут грандиозные числа сокращаются между собой.
unreal4ever
Задача для 7 класса? Я студент-программист, и даже не понял, о чем речь в задаче идет :)
vvvphoenix Автор
Да вроде несложно. :) Что там непонятного?
Spaceoddity
"десятичное число", с ходу непонятно - идёт ли речь о десятичной дроби или о позиционной системе счисления с основанием = 10 ;)
vvvphoenix Автор
о десятичной системе счисления. Там только целые числа. Дробей нет
Deirel
Почему в десятичной системе счисления дробей нет? Википедия бы с вами не согласилась. Предоставление числа как суммы перемножений цифр и степеней десятки точно так же работает для цифр после десятичной точки.
nronnie
То ли я неправильно понял условие, то ли предложенное в статье решение абсолютно неверно. Если бы оно было верно, то это означало бы, что сумма любых 9 чисел от 0 до 9 кратна 10, что неверно - первый же контрпример этому это просто девять единиц.
nronnie
А... Понял. В & Ш еще ведь договариваются изначально. Тогда всё ОК.
amberovsky
Долго думал, почему у меня получилось 8 разрядов, а в статье - 9