Комментарии 88
Задача для 7 класса? Я студент-программист, и даже не понял, о чем речь в задаче идет :)
Да вроде несложно. :) Что там непонятного?
"десятичное число", с ходу непонятно - идёт ли речь о десятичной дроби или о позиционной системе счисления с основанием = 10 ;)
о десятичной системе счисления. Там только целые числа. Дробей нет
То ли я неправильно понял условие, то ли предложенное в статье решение абсолютно неверно. Если бы оно было верно, то это означало бы, что сумма любых 9 чисел от 0 до 9 кратна 10, что неверно - первый же контрпример этому это просто девять единиц.
Незнайка записывает 9 разрядов .. и пропускает один
Долго думал, почему у меня получилось 8 разрядов, а в статье - 9
Непонятно при чем тут отображение
между множествами 10^9(записанные Незнайкой разряды)*10(номер пропущенного) и 10^10 (десятизначное число, которое видит Шпунтик)
потому что нужно отображение одной десятичной цифры в десятиразрядное число!
потому что 9 заданных разрядов ни на что фактически не влияют, так как могут быть произвольными и должны однозначно отобразиться тоже в одну десятичную цифру!
На самом деле кодируется одна десятичная цифра! И кодируется она с помощью другой единственной десятичной цифры! Единственный способ кодирования одной десятичной цифры с помощью другой десятичной цифры это операция сложения по модулю
Сколько есть вариантов отобразить 10^9 в одну десятичную цифру? А бесконечное количество!
Можно сразу сложить по модулю, можно к каждому разряду прибавить 5 по модулю и после этого все сложить по модулю, можно 5 раз прибавить 7 по модулю к каждому и потом сложить по модулю...
операция сложения по модулю линейная ее бесконечно можно повторять чтобы все равно получить однозначное отображение всего входного множества на выходное множество.
9 десятичных цифр одназначно отображаются в позицию (то есть в заданную десятичную цифру номера этой позиции) единственным способом суммированием всех 9 + номер позиции по модулю! Потому что при декодировании этого номера из 10 цифр мы не знаем исходный порядок в котором эти цифры формировали код. Единственная операция (она же способ отображения) которая позволяет игнорировать этот порядок, то есть результат которой не зависит от этого порядка это операция суммирования по модулю.
Множество тут одно из 10-ти элементов только с этим множеством надо рассматривать операции-отображения.
В общем задача состоит в том чтобы найти уникальную метрику последовательности элементов десятичного (или в общем случае N-арного) множества:
а1, а2,...а9
или
A1, A2,...An
метрику которая однозначно преобразуется в метрику последовательности:
а1, а2,...а9 + х
где х - это вычисленный елемент новой последовательности позиция которого определяется исходной метрикой, то есть нужна еще одна функция параметрами которой будут метрика последовательности и позиция добавленного элемента:
F(М(а1, а2,...а9), П) => элемент десятичного множества для позиции П
должна также отображаться в элемент десятичного множества. Поэтому отображения на самом деле нужно два(!), а не одно:
отображение последовательности десятичных элементов в метрику последовательности которая тоже должна быть десятичным елементом;
и отображение двух десятичных элементов в десятичный элемент новой последовательности
В общем это обычный случай ошибки с формулировкой математической задачи! Искать надо два достаточно простых отображения, а вы пытались искать одно сложное.
Можно, кстати, легко доказать что вашего сложного отображения 10^9 в 10^10 не существует:
Если бы оно существовало, то существовало бы и отображение 10^10 в 10^11, но 10-чный элемент не может кодировать 11-ричную позицию!
Тяжело искать черную кошку в темной комнате, когда ее там нет.
я вот тоже не понял. Автор предлагает остаток от деления записывать. Но откуда Шпунтик узнает КУДА Винтик записал остаток от деления? Перебором?
но допустим, а ведь коллизии никто не отменял.
Мне стало интересно попробовать свои силы, чтобы оценить количество похожих решений (где надо складывать разряды по модулю 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 уже некуда писать. Поэтому, решил оставить все формулы плоскими, нежели часть плоскими, а часть красивыми.
Подумал ещё и понял, что предлагаемое мной решение номер 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.
Добрый день. По части "cлабого" решения - да, эти соображения корректны. Однако они дают лишь очень небольшую долю решений. У меня по некоторым прикидкам получалась оценка ((10^9))!/(((10^8)!)^10). И это только один из множителей. С "сильным" решением сейчас буду еще разбираться.
PS. Cогласен, формулы планарным текстом выглядят жутко... :)
Ну, я уже сам себя опроверг :) Позже я смутно сообразил, в какую сторону примерно следует думать, но там мои математические возможности пока заканчиваются.
Ещё момент, я заметил по комментариям, что не всем понятно условие задачи. И, если честно, я тоже не сразу въехал (т. к. не сразу ясно, что значит "договориться", и какое мы отображение ищем). Хочу предложить вам на ваше усмотрение добавить в описание такую или какую-либо похожую переформулировку:
Не уверен, насколько сам ясно написал, но надеюсь, кому-то поможет
Пусть F - функция, отображающая строку S из 10 цифр в 1 десятичную цифру:
Назовём F функцией Незнайки, если для любых 10 строк Si, любая пара которых отличается одной и только одной цифрой (все разряды одинаковые, кроме одного), верно тождество
Вопрос - сколько существует различных функций Незнайки?
Интуитивная иллюстрация - мы берём рандомную строку, в ней тыкаем рандомный разряд, "прокручиваем" его от 0 до 9, и F от этой строки обязательно пробежит все значения от 0 до 9, хоть и необязательно в таком же порядке. Тем самым, что бы ни загадал Незнайка, Винтик всегда "прокрутит" рязряд в нужный ему номер. Выбор конкретной функции Незнайки - это способ Винтика и Шпунтика "договориться". Таким образом, количество функций Незнайки = количество способов решить задачу.
P. S. Всё, разобрался с формулами - цвет фона тёмной темы совпадал с цветом шрифта формул в TeX-режиме, вот я и не мог их набрать.
Ответ на вопрос, сколько существует взаимно однозначных отображений между двумя множествами конечного размера довольно прост: N!
Это, конечно так. Если б у нас была полная доска 10^10x10^10 то небьющие друг друга ладьи можно было бы расставить (10^10)! способов. Но тут наложено ограничение. Например, если Незнайка приносит число ...777777777, то на выходе мы можем получить только 0777777777, 1777777777,...9777777777. Поэтому решений меньше.
Где N это что? Множества разного размера.
Вставляемая Винтиком цифра должна должна давать такую сумму всех цифр, последний разряд которой равен позиции вставляемой цифры. Делением на 10 только усложняется смысл.
Не понял формулировку - Незнайка называет цифру, а Винтик выбирает место? Или же Винтик выбирает и цифру и место?
"Короче, Шпунт, у Незнайки синяя авторучка, а у меня - толстый красный карандаш."
Как-то не уловил как автор собирается различать решения. Например, возьмем способ, которые приведен в статье (сумма по модулю 10). Теперь, я предложу другое решение - делаем все ровно так же, но Винтик пишет число на 1 меньше, а Шпунтик, соответственно, после своих вычислений увеличивает число на 1. Это другое решение (дает разные цифры) или то же (суть-то модулярного сложения остается)?
Ох уж эти пост-мета-версии школьных олимпиадных задачек, подержите мое пиво!
Время диалапа и бумажных автобусных билетов, на каждом билете выбит шестизначный номер. Билеты бывают счастливые: в Москве это значит, что совпадают суммы первых трех и последних трех цифр, в Питере - что совпадают суммы цифр на четных и нечетных местах. Можно придумать свой рецепт счастья и сравнивать, например, суммы цифр на первом, втором и четвертом месте с остальными. Но на самом деле интересный вопрос в другом: а сколько существует билетов, цифры в которых нельзя разбить ни на какие две группы с равной суммой?
На самом деле таких билетов довольно много, поэтому хочется ввести еще пару ограничений. Их я уже не помню, но кажется мы вводили условия на 1) четную сумму всех цифр (иначе какие вам две группы), 2) все цифры должны быть разными. И назвали такие билеты суперсчастливыми. Было очевидно, что их мало, но сколько - неясно.
Как-то раз мне стало скучно в поезде, и я нашел все такие комбинации перебором :) их оказалось то ли 7, то ли 9. Но в седьмом классе было сложно додуматься до самого интересного вопроса: а есть ли у задачи аналитическое решение?
P.S. По-моему, мы обсуждали этот вопрос с Дмитрием Юрьевичем. Но недолго: у него всегда было много гораздо более интересных задач ;)
Они ведь могли договариваться и об алгоритмах:
Если Незнайка записал все цифры одинаковые, то пиши неодинаковую.
Если все цифры Незнайки одинаковые кроме одной, то пиши 0, если эта одна 0 - то 9. Если это девятки, то 8.
И т.п.
И количество таких алгоритмов будет сопоставимо с количеством всех возможных перестановок 9 чисел с повторениями...
Незнайка записывает 9 разрядов 10-значного десятичного числа и пропускает один по своему выбору. Пропущенный разряд он предлагает записать Винтику, а затем показывает полученное 10 -значное число Шпунтику. Как могут Винтик и Шпунтик договориться, чтобы Шпунтик угадал, какой именно разряд записал Винтик?
Ну, например, Шпунтик и Винтик договариваются, что после того, как Винтик записал разряд, он звонит Шпунтику по телефону и говорит, какой разряд он записал? В условии задачи нет ничего, что запрещало бы В и Ш обмениваться инцормацией по side channel, а "всё, что явно не запрещено условием, разрешено"...
Оставим в стороне вопрос о том, насколько это остроумно, и подумаем вот над чем: что было бы, если бы формулировки задач были совершенно строгими?
В статье сначала описывается одна задача, а потом задаётся совершенно другой вопрос.
Количество алгоритмов (в широком смысле, т.е. любых функций) для ОПГ "Винтик и Шпунтик" и количество различных взаимно-однозначных отображений между множествами чисел – это две совершенно разные вещи. Первое континуально, второе конечно. Очевидно, что к одному и тому же результату можно приходить разными алгоритмами.
А если учесть, что Винтик и Шпунтик должны договориться между собой за конечное время, используя дискретный конечный алфавит, тогда получается третий результат. Тоже конечное число.
Если рассуждать только об отображениях множеств, то Винтик и Шпунтик имеют на входе таблицу из всех возможных комбинаций 10 цифр – 9 написанных Незнайкой плюс номер пропущенного разряда. Чтобы получить полный набор правил для себя, они должны к каждой строке из этой таблицы приписать свою цифру, которая однозначно кодирует номер пропущенного разряда, то есть последний столбец таблицы. Содержимое первых 9 цифр важно для коммуникации Винтика и Шпунтика об алгоритме, но не представляет никакой значимости для заданного вопроса. По сути, результаты отличаются только способом кодирования 10 позиций при помощи 10 цифр, то есть способом упорядочивания 10 элементов. Поэтому ответов, дающих численно разные результаты, существует 10!, то есть 3628800.
Винтик и Шпунтик имеют на входе таблицу из всех возможных комбинаций 10 цифр – 9 написанных Незнайкой плюс номер пропущенного разряда.
Не совсем так. Это Винтик имеет такую таблицу. А Шпунтик имеет другую таблицу: синтаксически это всё те же комбинации 10 цифр, но семантически это 9 цифр, написанных Незнайкой, плюс одна, написанная Винтиком, -- а номер пропущенного разряда как раз ему неизвестен.
Винтик отображает первую таблицу во вторую, а Шпунтик -- вторую в первую. Поэтому и требуется взаимная однозначность.
Если мы начинаем думать о коммуникации между Винтиком и Шпунтиком, это осложняет рассмотрение лишними подробностями, но ничего не даёт по существу заданного вопроса. Проще здесь их рассмотреть, как единое целое. У нас одной цифрой, которую пишет Винтик, кодируется одна цифра, которая является номером пропущенного разряда, вот что важно. А как кодируется - нас не спрашивают.
Эта задача может иметь либо 0 решений (если Шпунтик не в состоянии восстановить информацию), либо 10!. Поскольку одно решение мы нашли, то их 10!. Все их можно получить перестановками кодовой последовательности в первом решении, а других не существует в силу ограниченной ёмкости канала связи.
Другими словами, соответствий между цифрой, которую написал Винтик, и цифрой, которую произнёс Шпунтик, ровно 10! в силу природы цифр.
Позвольте, заданный вопрос существенно полагается на формат коммуникации между Винтиком и Шпунтиком -- а именно на возможность однозначно восстановить прообраз продемонстрированной Шпунтику комбинации. Не любое отображение годится, а лишь то, которое обладает таким свойством.
И разумеется, номер пропущенного разряда кодируется не просто одной цифрой, которую пишет Винтик, а этой цифрой, взятой в контексте, заданным Незнайкой.
То, что Вы пишете, верно, но несущественно для ответа на поставленный автором вопрос.
Я говорю о том, что, найдя одно отображение, удовлетворяющее условиям задачи, мы можем получить из него все остальные просто перестановками кодовой таблицы (например, договорившись, что ответ 6 обозначает 2, 2 обозначает 3, а 3 обозначает 6 и т.д.). Любое другое отображение, позволяющее восстановить прообраз, будет совпадать с одним из отображений в полученных перестановках, потому что никак по-другому, чем 10! способами, одну десятичную цифру из другой невозможно получить без потери информации. А терять информацию мы здесь не имеем права, её ровно впритык.
Контекст мы здесь выносим за скобки, хотя он, конечно, оказывает влияние на наше первое решение.
У Винтика на выходе одна цифра, и у Шпунтика на выходе одна цифра. Всё. Как они их вычисляют, неважно. Число возможных взаимно-однозначных комбинаций этих двух цифр сверху ограничено 10!, и все их мы построили путём перестановок кодовой таблицы из одного способа. При этом совершенно неважно, что Шпунтик не знает, какую именно цифру написал Винтик.
Таким образом, окончательный полный ответ такой:
Алгоритмов для В&Ш вообще континуально много.
Дискретных конечных алгоритмов для В&Ш счётно много.
Таких алгоритмов, которые В может согласовать с Ш – конечное число, определяемое временем на согласование и пропускной способностью канала переговоров.
Алгоритмов, отличающихся по своим результатам – 3628800.
Всё. Как они их вычисляют, неважно. Число возможных взаимно-однозначных комбинаций этих двух цифр сверху ограничено 10!, и все их мы построили путём перестановок кодовой таблицы из одного способа. При этом совершенно неважно, что Шпунтик не знает, какую именно цифру написал Винтик.
А для троичного случая (трехзначное число и три цифры 0,1,2) у вас по этой логике сколько решений получается?
6, конечно.
Цифра, которую написал Винтик – цифра, которую произнёс Шпунтик:
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 случаев.
6, конечно
Маловато будет :) Вы отбрасываете в рассуждениях контекст и теряете информацию, предполагая, что отображение для каждой цифры постоянно.
Ниже пример решения, где '-' означает пропущенный разряд. Перед стрелочкой стоит число, которое Незнайка передал Винтику, после нее - которое Винтик передал Шпунтику. (Прошу прощения за форматирование, новый редактор комментариев - углючище нерукотворное).
Пример
-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
-00 -> 000
-01 -> 101
-02 -> 002
Если это решение, то какой алгоритм действий Винтика и Шпунтика в этом случае?
Просто сверить по таблице?
У Винтика на выходе одна цифра, и у Шпунтика на выходе одна цифра. […] Число возможных взаимно-однозначных комбинаций этих двух цифр сверху ограничено 10!
Откуда взялось требование взаимной однозначности этих цифр? Почему Шпунтик не может для одной и той же цифры Винтика вернуть разные цифры в зависимости от контекста?
Да, всё верно, выше@Stiverпривёл пример.
Ничего не понял, но мне кажется, что Винтик посчитает сумму цифр, написанных Незнайкой, и добавит цифру от1 до 9 так, чтобы сумма цифр при делении на 9 имела остаток, равный номеру угадываемого разряда, начиная, например, слева (остаток 0 соответствует девятому разряду). Он сможет это сделать, т.к. прибавляя цифры от 1 до 9, он получит все девять различных остатков. При этом не возникает проблемы 0 в первом разряде, т.к. Винтик пишет ненулевую цифру. После этого приходит Шпунтик, считает сумму цифр, находит её остаток при делении на 9 и указывает по остатку номер нужного разряда. А все остальные решения какие-то выдуманные.
С учётом замечаний, приведённых @Stiver, правильная оценка количества различных отображений, по-видимому, следующая.
Нам надо найти, сколькими способами правую часть таблицы, предложенной Стивером, состоящую из n**n чисел от 0 до n**n-1, можно разделить на n равных групп, причём порядок групп важен, так как номер группы – это ни что иное, как ответ Шпунтика, т.е. номер искомого разряда. Каждое различное разбиение на группы будет давать новое решение, других решений нет.
Беглый гуглинг показывает, что количество способов равно
где mn – размер таблицы, т.е. m = n**(n-1). В нашем случае, n=10 и m=10**9.
При этом Винтик должен иметь возможность выбором числа в указанном ему разряде определить результирующее число в нужную группу. Это как-то учитывается?
Винтик ищет увиденное перед собой в левом столбце таблицы и подставляет то число, которое прописано в правом столбце таблицы. Это наиболее общий алгоритм.
В этой формуле m! ведь сокращается? Остается (mn)! / (n!)^m, правильно?
По логике вещей, да.
Винтик может увидеть перед собой 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. Вы хотели домножить на некую вероятность. Она должна быть совсем маленькой, с кучей нулей после запятой.
Она и есть маленькая. Чтобы два списка из 10 миллиардов 10-значных чисел попарно совпали в каждом элементе в 9 разрядах.
Для одной строки вероятность совпадения 1e-9, и это число грубо надо возвести в степень 1e10, то есть для всей таблицы 1e-9**1e10. Но на самом деле вероятность условная, числа в каждой группе сильно мешают друг другу (если мы уже использовали одно число, подходящее под маску, то найти следующее менее вероятно), поэтому результат ещё меньше.
Так что тут грандиозные числа сокращаются между собой.
Получается некая оценка, но очень "сверху". Давайте обратимся к тернарному случаю, поскольку он лучше всего изучен. В этом раскладе n = 3, m = 3^2 =9. По формуле мы получаем 27!/((3!)^9) - это больше чем 10^20. В то время как решений всего лишь 10752.
Как я уточнил выше в ответ на верное замечание @Alexandroppolus, надо ещё умножить это значение на вероятность P совпадения случайного списка чисел со случайным списком маскок. Очевидно, P = k / (n**n)! , где в числителе стоит некое число совпадающих масок, а в знаменателе – общее число списков, т.е. как раз (mn)!. Поэтому 27! тут сокращается.
По сути, мы свели задачу ВШ к более простой комбинаторной задаче поиска P, то есть вероятности того, что Винтик, заранее вытащив случайное n-значное число из списка 0..(n**n-1), сможет превратить в него случайную записанную Незнайкой маску, и успешно повторить это действие столько раз, сколько существует масок, не используя ранее вытянутые числа.
Ваш метод позволяет построить для какого либо из 10752 решения всю таблицу тернарной функции? Хотелось бы посмотреть на случаи, не связанные с вариацией решения из условия (сумма по модулю + константа).
В Вашем телеграме посты видел, но как по тем диаграммам построить функцию пока не понял.
Шаг 1: Понимание множеств
Множество A: 10-значные числа, которые Шпунтик может видеть, равно 10^10 , так как каждая цифра может быть от 0 до 9, и нет ограничений на первую цифру.
Множество B: Пары из 9 известных цифр и позиции пропущенной цифры. Есть
9 ×10^9 возможных наборов цифр (поскольку первая цифра не может быть 0), и 10 возможных позиций для пропущенной цифры.
Шаг 2: Создание однозначного отображения
Функция отображения: Определим функцию
𝑓 : 𝐵 → A, которая принимает пару из 9 цифр и позиции и отображает её в полное 10-значное число. Для этого нужно определить способ, как Шпунтик может определить пропущенную позицию и цифру, основываясь только на итоговом числе.
Шаг 3: Контрольная сумма или хеш-функция
Контрольная сумма: Договоримся, что Винтик и Шпунтик используют определенную контрольную сумму. Например, они могут использовать простую сумму всех цифр числа по модулю 10 (или другую контрольную сумму, которая учитывает позицию цифры для увеличения энтропии).
Процесс: Незнайка передает Винтику 9 цифр и контрольную сумму, включая пропущенную цифру. Винтик дописывает свою цифру, вычисляет контрольную сумму нового числа и передает число Шпунтику. Шпунтик, в свою очередь, используя контрольную сумму, может восстановить пропущенную цифру и её позицию, перебирая возможные варианты.
Шаг 4: Взаимно однозначное отображение
Анализ: Каждое 10-значное число, которое видит Шпунтик, можно однозначно преобразовать обратно в набор из 9 цифр и позицию пропущенной цифры, используя обратную контрольную сумму. Это делает отображение взаимно однозначным.
Вывод
Таким образом, количество взаимно однозначных отображений между множествами
B и A равно 10^10.
Видимо, это тоже оценка снизу. В тернарном случае по этой логике получалось бы 3^3 = 27. А там 10752 решения
Это количество вариантов, которыми можно преобразовать одно произвольное число. А нам нужно сочетание для всех возможных преобразований чисел.
В общем, так.
Имеем регулярный двудольный граф степени 10, задающий отображение двух множеств. Одно множество -- все последовательности десятичных цифр длиной 10 (далее чисел); другое множество -- все "шаблоны" (последовательности цифр, в которых ровно одна из цифр заменена на символ-джокер; далее шаблоны). Размер каждой из долей 10^10, при этом каждое число связано с 10 разными шаблонами, а каждый шаблон -- с 10 разными числами.
Незнайка выбирает шаблон, после чего Винтик выбирает одно из чисел, связанных с этим шаблоном, после чего Шпунтик должен выбрать из шаблонов, связанных с этим числом, тот же шаблон, что был выбран Незнайкой изначально.
Для того чтобы последнее было возможно, необходимо и достаточно выбрать в упомянутом графе регулярный подграф степени 1 (или, иными словами, совершенное паросочетание). Иначе говоря, из каждых 10 ребер, инцидентных одному и тому же числу, оставить ровно одно, но при этом так, чтобы и из каждых 10 ребер, инцидентных одному и тому же шаблону, осталось тоже ровно одно.
Число совершенных паросочетаний в двудольном графе равно перманенту его матрицы смежности. (Перманент -- это как детерминант, но все слагаемые со знаком "+").
В теории, этого достаточно. На практике, вычисление перманента -- вычислительно сложная задача и при n=10^10 ловить нечего.
(Для тернарного случая мои расчеты дали 10752)
Это правильный ответ. А вы именно перманент считали?
Размер множества шаблонов меньше 1e10. Так как 1 шаблон заменяет 10 чисел.
Поэтому совершенного паросочетания не существует.
Может ли Шпунтик задавать вопросы Винтику? В условиях задачи об этом нет ни слова.
Единственное что сказано, "как могут Винтик и Шпунтик договориться, чтобы Шпунтик угадал, какой именно разряд записал Винтик"? Если вопросы задавать можно, то понадобиться всего 3 или 4 вопроса.
Пусть разряды (места) пронумерованы в порядке 0123456789. Разделим их на группы 01234 и 56789. Эти группы разделим на подгруппы 012, 34 и 567, 89. Подгруппу из трёх разрядов разделим ещё на одну подгруппу 01, 2 и 56, 7. Пусть 01234 = A, 56789 = B, 012 и 567 = С, 34 и 89 = D, 01 и 56 = E.
Пусть искомый разряд 5. Тогда Шпунтик задаёт Винтику следующие вопросы. Твой разряд в группе A? Винтик отвечает, нет. Твой разряд в подгруппе C? Винтик отвечает, да. Твой разряд в подгруппе E? Винтик отвечает, да. Твой разряд 6? Винтик отвечает, нет. Следовательно, искомый разряд 5. При этом не имеет значения что мы ищем.
Правильно ли я понимаю, что задача состоит в следующем?
Пусть 
. Функцией 10-значной логики назовём произвольное отображение 
.
Сколько существует таких функций 
, что для них существует такая функция 
, что 
?
Не понял, почему формулировка задачи жирным именно такая. Моя формулировка: найти множество всех функций F(x0,...x9), таких, что меняя любой аргумент, можно получить значение функции равное номеру этого аргумента. Само собой, все аргументы это числа от 0 до 9. Так звучит как-то яснее и без всяких множеств и взаимных отображений.
Из такой постановки задачи ясно, что:
1) функция должна пробегать все значения от 0 до 9 при изменении любого из аргументов от 0 до 9, но в любом порядке.
То есть, если надо не написать в функцию в виде математического выражения, а надо в виде таблицы соответствий, то вариантов получается 10! (факториал). Но это не ответ на задачу, потому что даже одно соответствие (0 -> 0,... 9 -> 9) можно записать в виде многих математических выражений. Например, ответ из статьи: сумма всех аргументов и остаток от деления на 10. Второй вариант: сумма попарных разностей элементов и ее остаток. Третий вариант: разность сумм первой пятёрки элементов и второй пятёрки и ее остаток. И так далее, и тому подобное. То есть, любая комбинация из десяти знаков + и -. А если добавить ещё всякие промежуточные псевдовычисления, то количество вариантов математических выражений становится бесконечно. Например, выбрать любое целое число, добавить его к каждой цифре и далее все то же самое. То есть, одно и то же соответствие может вычисляться бесконечным количеством формально разных выражений/функций.
Но если все таблицы соответствий принять как изоморфные/излишние, если убрать все лишние псевдовычисления, то остаётся множество из десяти плюсов и минусов, а это 2 в десятой степени, 1024.
По принципу "трясти надо" набросал программку более или менее тупого перебора в лоб. Для n = 3 посчитало 10752 без проблем, для n = 4 получается дерево вариантов глубиной около 150 и средней ветвистости около 2. То есть количество решений можно видимо ожидать где-то в районе 2^150 -> 10^45.
Последние 30 уровней дерева
Depth 156: 2
Depth 155: 8
Depth 154: 12
Depth 153: 32
Depth 152: 42
Depth 151: 88
Depth 150: 216
Depth 149: 432
Depth 148: 864
Depth 147: 2912
Depth 146: 8288
Depth 145: 17504
Depth 144: 42144
Depth 143: 92352
Depth 142: 150400
Depth 141: 272384
Depth 140: 538112
Depth 139: 1489664
Depth 138: 1489664
Depth 137: 3049728
Depth 136: 3049728
Depth 135: 6029056
Depth 134: 9078784
Depth 133: 9078784
Depth 132: 24022528
Depth 131: 38761472
Depth 130: 77074944
Depth 129: 154149888
Depth 128: 308299776
Depth 127: 616599552
Интересно. У меня получалось побольше. Я правда, пальцем в небо тыкал. А как считали?
У меня получалось побольше.
Разница в принципе небольшая, просто 10^45 - скорее оценка снизу, а 10^67 ближе к верхней границе диапазона. Дерево ветвится от 2 до 3 (4 в первом уровне и 1 в отдельных вырожденных узлах можно пренебречь) и чем выше, тем больше троек. В целом количество решений будет где-то между 2^150 (10^45) и 3^150 (10^71).
Пример ветвлений на случайном пути
Children 0: 4
Children 1: 3
Children 2: 3
Children 3: 3
Children 4: 3
Children 5: 3
Children 6: 2
Children 7: 3
Children 8: 3
Children 9: 2
Children 10: 2
Children 11: 3
Children 12: 2
Children 13: 2
Children 14: 2
Children 15: 2
Children 16: 2
Children 17: 2
Children 18: 2
Children 19: 3
Children 20: 2
Children 21: 2
Children 22: 2
Children 23: 3
Children 24: 2
Children 25: 2
Children 26: 2
Children 27: 3
Children 28: 3
Children 29: 2
Children 30: 3
Children 31: 3
Children 32: 2
Children 33: 2
Children 34: 2
Children 35: 3
Children 36: 2
Children 37: 2
Children 38: 2
Children 39: 2
Children 40: 2
Children 41: 2
Children 42: 2
Children 43: 2
Children 44: 2
Children 45: 2
Children 46: 2
Children 47: 3
Children 48: 2
Children 49: 2
Children 50: 2
Children 51: 3
Children 52: 2
Children 53: 2
Children 54: 2
Children 55: 3
Children 56: 2
Children 57: 2
Children 58: 2
Children 59: 2
Children 60: 2
Children 61: 2
Children 62: 2
Children 63: 2
Children 64: 2
Children 65: 2
Children 66: 2
Children 67: 2
Children 68: 3
Children 69: 2
Children 70: 3
Children 71: 1
Children 72: 2
Children 73: 3
Children 74: 1
Children 75: 3
Children 76: 2
Children 77: 2
Children 78: 2
Children 79: 2
Children 80: 2
Children 81: 2
Children 82: 2
Children 83: 2
Children 84: 2
Children 85: 2
Children 86: 2
Children 87: 2
Children 88: 2
Children 89: 3
Children 90: 2
Children 91: 2
Children 92: 2
Children 93: 2
Children 94: 2
Children 95: 2
Children 96: 2
Children 97: 2
Children 98: 2
Children 99: 2
Children 100: 2
Children 101: 2
Children 102: 2
Children 103: 2
Children 104: 2
Children 105: 2
Children 106: 2
Children 107: 2
Children 108: 2
Children 109: 2
Children 110: 2
Children 111: 2
Children 112: 2
Children 113: 2
Children 114: 2
Children 115: 2
Children 116: 2
Children 117: 2
Children 118: 2
Children 119: 2
Children 120: 2
Children 121: 2
Children 122: 2
Children 123: 2
Children 124: 2
Children 125: 2
Children 126: 2
Children 127: 2
Children 128: 2
Children 129: 2
Children 130: 2
Children 131: 2
Children 132: 2
Children 133: 1
Children 134: 2
Children 135: 2
Children 136: 1
Children 137: 2
Children 138: 1
Children 139: 3
Children 140: 2
Children 141: 2
Children 142: 2
Children 143: 2
Children 144: 2
Children 145: 2
Children 146: 2
Children 147: 2
Children 148: 2
Children 149: 2
Children 150: 2
Children 151: 2
Children 152: 2
Children 153: 2
Children 154: 2
Children 155: 2
А как считали?
Просто рекурсивным перебором с выбором узла с минимальным количеством оставшихся вариантов. Хочу еще попробовать приделать оптимизацию для использования симметрии (чтобы изоморфные случаи заново не считать) - любопытно, насколько можно ускорить перебор.
Я учусь в 7 классе и тоже хочу попробовать разобраться в задаче. К сожалению, у меня пока не хватает знаний, чтобы целиком понять решение первоначальной задачи и сам вопрос.
1)
Одно решение найти несложно – оно вполне доступно и семикласснику. Шпунтик вычисляет остаток от деления на 10 суммы всех разрядов десятичного числа, которое видит. В нашем случае она равна 45. И ,значит, 5 – номер пропущенного разряда.
Я не понимаю, что имеется ввиду под суммой всех разрядов, т.к. каждая цифра совпадает с номером ее разряда. И как Шпунтик понимает, что пропущенный разряд - 5? Объясните поподробнее, пожалуйста, например, как договариваются Винтик и Шпунтик.
2) В чем заключается суть вопроса? Мне не понятен термин "взаимно- однозначные отображения". Википедия выдает это:
Но это про множества. Здесь ровно одна цифра соответствует ровно одной букве. А в данном случае что соответствует чему?
3) Что имеется ввиду под редуцированными случаями? Что число пишется в двоичной или троичной или .... системе счисления? Тогда задача и вправду упростится.
Заранее спасибо за ответ. Я не претендую на приз, судя по комментам, наполненными сложными словами, просто пост показался мне интересным.
Я не понимаю, что имеется ввиду под суммой всех разрядов, т.к. каждая цифра совпадает с номером ее разряда. И как Шпунтик понимает, что пропущенный разряд - 5? Объясните поподробнее, пожалуйста, например, как договариваются Винтик и Шпунтик.
Это в приведенном примере цифра совпадает с номером ее разряда, а в общем случае -- как получится. Имеется в виду попросту сумма цифр во всех разрядах.
Шпунтик просто вычисляет эту сумму и берет последнюю цифру (или, что то же самое, остаток от деления на 10). И эта цифра магическим образом оказывается равной номеру пропущенного Незнайкой (и заполненного Винтиком) разряда.
А вот чтобы эта магия сработала, Винтик и Шпунтик и должны договориться, что Винтик будет вписывать не какую попало цифру, а именно такую, чтобы получившийся остаток был равен этому номеру. Это сделать несложно, поскольку сумму остальных цифр (кроме своей) он знает, знает и остаток от деления этой суммы на 10, может рассчитать, насколько этот остаток отличается от нужного ему (то есть от номера пропущенного разряда), а значит, может выбрать такую цифру, чтобы эту разницу компенсировать (одной цифры всегда хватит).
Это один способ, самый очевидный. Но вообще-то, не обязательно действовать именно по такому алгоритму. В общем случае, В&Ш могут заранее подготовить специальную таблицу, в которой для каждого из возможных заданий Незнайки будет записано, какую цифру Винтик должен вписать. Задание состоит из 9 цифр и номера пропущенного разряда (например, 012346789 и 5), но можно представлять его и как результат вставки спецсимвола на место пропущенного разряда (например. 01234_6789) -- это одно и то же. Результат Винтика тоже можно представлять как одну вписываемую цифру (например, 5), а можно как готовый результат ее подстановки (например, 0123456789). Шпунтик потом получит это число (результат подстановки), найдет его в той же таблице с другой стороны и посмотрит, какое должно было быть задание Незнайки, чтобы получилось такое число.
Только вот, чтобы магия срабатывала, обязательно должно быть, чтобы не только у Винтика был единственный вариант ответа для каждого задания, но и чтобы наоборот, каждый ответ Винтика мог быть получен из только из одного задания (иначе говоря, чтобы не было такого, что разные задания дают один и тот же ответ).
Это и называется взаимно-однозначным отображением. На картинке на месте X будет задание Незнайки, а на месте Y -- результат Винтика.
Важно, что и цифр в используемой системе счисления 10, и разрядов в рассматриваемом числе столько же. Когда задача кажется слишком сложной, иногда помогает рассмотреть сначала более простую ("редуцированную", как выразился автор поста) задачу. В нашем случае, мы можем вместо 10 взять 2, 3, 4 и так далее -- главное, чтобы и система счисления (то есть, попросту размер набора используемых цифр), и количество разрядов в числе равнялись одному и тому же значению.
главное, чтобы и система счисления (то есть, попросту размер набора используемых цифр), и количество разрядов в числе равнялись одному и тому же значению.
Достаточно, чтобы количество цифр числа не превышало основание счисления. Меньше - можно. Просто делить (чтобы получить остаток) надо на количество цифр в числе.
Кстати, в случае неравенства отображение перестаёт быть взаимно-однозначным, и для некоторых исходных, написанных Незнайкой, у Винтика будет возможность выбирать из нескольких вариантов вставляемой цифры. Например, для трёхзначного числа и написанного Незнайкой 1_2 Винтик может вставить любую цифру из набора 1, 4, 7. Соответствующие суммы будут 4, 7 и 10, но все они при делении на 3 дают в остатке 1 (позиции нумеруем, само собой, с нуля).
На мой взгляд, условия задачи неполны. Сначала спрашивается как могут договориться два субъекта, потом спрашивается про количество взаимно-однозначных соответствий. Незнайка может с равной вероятностью оставить пустым любой из разрядов. Эту вероятность он передаёт Винтику, так как выбор делает именно Незнайка. Раз существует равная вероятность, то у Шпунтика нет возможности без дополнительных сведений и договорённостей определить какой разряд был выбран Незнайкой, а потом записан Винтиком. Тут у студентов вузов проблемы возникают, а вы про семиклассников...
Разряд это условное место от 1 до 10. В числе 7777777777 все десять разрядов. Один из них был пропущен Незнайкой и записан Винтиком семёркой. Без доп.сведений никак не определить какой разряд был записан Винтиком.
Также в условиях задачи говорится, что "Незнайка записывает 9 разрядов 10-значного десятичного числа и пропускает один по своему выбору". Что значит "пропускает один"? От чего? От 9 разрядов или от 10? Если пропускает один от записанных, тогда 9-1=8. В общем не задача, а сумбур.
Разряд это условное место от 1 до 10. В числе 7777777777 все десять разрядов. Один из них был пропущен Незнайкой и записан Винтиком семёркой. Без доп.сведений никак не определить какой разряд был записан Винтиком.
Договоренность ВинКтика и ШпунКтика как раз и есть дополнительные тайные сведения.
То, куда мне видится - ШпунКтик должен увидеть положение "пустой" ячейки потом зашифровать это положение и записать в пустую ячейку. ВинКтик должен опознать цифру шифра, расшифровать ее и дать правильный ответ. Отличить цифру, которую записал Шп. от соседней нельзя - нет гарантии, что не будет такая-же еще. Значит надо поиграться суммой, наверное произведений места на цифру. Надо набросать - да даже в экселе- пару формул. Думаю здесь сойдется.
По мне - смысла лезть в вероятности нет. Можно задачу надо упростить до 4-5 знаков, а потом расширить на 10.
Для решения этой задачи нам нужно найти количество взаимно-однозначных отображений между двумя множествами.
Первое множество: 10^9 * 10 = 10^10 (десятизначные числа, где последняя цифра пропущена).
Второе множество: 10^10 (десятизначные числа).
Для каждой цифры из первого множества существует ровно одно соответствующее десятизначное число из второго множества. Таким образом, количество взаимно-однозначных отображений равно количеству перестановок 10 разрядов числа 10^10, то есть 10!.
Итак, количество взаимно-однозначных отображений между данными множествами равно 3628800.
Vintik & Shpuntik Challenge