Jornal do Falcão

Не так давно встретилась задача -- скорее всего, она известная. Слишком уж естественная у неё формулировка. В таких случаях кому-то может быть известно "авторское" решение, которое мне было бы интересно узнать.

Задача относится к категории "пример+оценка". В таких случаях бывает, что один из пунктов решается легко, а другой несколько труднее. В данном случае пример достаточно очевиден, и интересует доказательство его оптимальности. Я придумал с этой целью чисто комбинаторное рассуждение достаточно общего характера, которое потом собираюсь изложить. Но интересны любые другие возможные подходы.

Вот формулировка задачи.

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

UPD (04.12.22) Помещаю своё решение. Оно во многом близко тому, которое в комментариях изложил relf.

Стратегия того, как за n(n-1)/2 вопросов можно всё узнать, достаточно очевидна, и я её описание опускаю. Нужно доказать, что меньшего числа вопросов в общем случае не хватает. Если имеется стратегия угадывания, то она должна работать и в случае, когда отвечающий на вопросы сам назначает по ходу дела, какой ключ к какому замку подходит. Пусть ответ "нет" даётся всегда кроме случая, когда такой ответ приводит к логическому противоречию. В такой ситуации не имеет смысла задавать вопросы, на которые заведомо последует ответ "да": если это логически следует из ранее сказанного, то вопрошающий сам может прийти к такому же выводу. Отказ от таких вопросов лишь уменьшает их количество.

Пусть все вопросы заданы. Предположим, что угадывание состоялось. Тогда можно занумеровать ключи и замки так, чтобы ключ под номером i открывал замок под номером i. Построим простой граф на n вершинах. Соединим точки с номерами i и j ребром, если по ходу дела был задан вопрос про i-й ключ и j-й замок, либо про j-й ключ и i-й замок. Заметим, что i не равно j в силу сказанного выше.

Если вопросов было задано меньше, чем n(n-1)/2, то какое-то ребро полного графа не было проведено. Пусть оно соединяет вершины i и j. Тогда могло быть так, что i-й ключ открывает j-й замок, а j-й ключ открывает i-й замок. Остальные ключи открывают, как и было, замки со своими номерами. Такая ситуация теперь возможна, а это значит, что угадывание не состоялось.

Вот ещё одна интересная задача, тоже вероятностная. Предлагаю всем желающим поучаствовать. Условие таково.

В коробке имеется M белых и N чёрных шаров, где M > N. Их начинают поочерёдно перекладывать во вторую коробку, выбирая шары случайным образом, пока первая коробка не опустеет. Перекладывание считается успешным, если в ходе процесса число белых шаров во второй коробке всегда (строго) больше числа чёрных. Какова вероятность успешного перекладывания?

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

Комментарии до времени скрыты, а способы решения допускаются любые.

UPD (31.12.21) Раскрываю комментарии. Ответов было немного, но один из них совершенно исчерпывающий. Сам я решал таким же точно способом.

Вот хорошая, на мой взгляд, вероятностная задача.

Проводится турнир по кубковой системе среди n участников. Ничьих нет, проигравшие выбывают. Все игроки считаются примерно равными по силе, то есть при встрече между собой каждый выигрывает с вероятностью 1/2. При чётном количестве игроков, они случайным образом разбиваются на пары, встречаются между собой, и победители проходят в следующий тур. При нечётном -- один случайно выбранный участник выходит в следующий тур без игры, остальные разбиваются на пары, как и выше, играя между собой. Так происходит, пока не останутся двое, которые встречаются между собой в финале. Какова вероятность, что два конкретных участника, Андрей и Борис, в ходе турнира сыграют между собой?

Я сначала нашёл закономерность, рассмотрев случаи небольших значений n, а потом доказал, что она имеет место для любого числа участников (в оригинале их было 20). В итоге удалось найти совсем "прозрачное" решение, фактически не основанное на вычислениях.

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

UPD (04.12.21) Раскрыл комментарии. Ответ 2/n. Его можно получить несколькими близкими способами. Сам я рассуждал так: все участники равноправны, выиграть турнир можно с вероятностью 1/n. Тот, кто не выиграл, кому-то одному проиграл, и с равной вероятностью каждому из n-1. Тогда вероятность того, что Андрей проиграет именно Борису, получается делением 1-1/n (вероятности того, что он не выиграет в турнире) на n-1. Это будет 1/n. Такая же вероятность того, что Борис проиграет Андрею. В сумме получается 2/n, а это и есть вероятность того, что данные участники играли (один проигрывает другому).

Всем спасибо за участие!

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

Есть стандартная колода из 52 карт. Мы её перетасовали и извлекли первую карту. Это оказалась пика. Какова вероятность того, что за ней также следует пика?

Это я никого не призываю решать, так как всё стандартно. Осталась 51 карта, пик среди них 12. Вероятность равна 12/51=4/17. То есть близко к 1/4, но чуть меньше, так как одна пика в начале была как бы отыграна.

А теперь -- собственно условие.

Есть стандартная колода из 52 карт. Мы её перетасовали и начали открывать карты, пока не появилась первая пика. Какова вероятность того, что за ней также следует пика?

Эта задача уже менее стандартна, и для меня показалась новой, хотя кто-то мог подобное уже встречать.

Комментарии я пока скрываю, так как здесь в принципе достаточно одной простой идеи. Через время всё будет раскрыто. Можно оставлять как ответы без обоснования, так и с решением.

UPD (13.11.21) Раскрываю комментарии. Ответ к задаче: 1/4. Моё решение было такое: все карты после первой пики располагаем в обратном порядке. Вероятность от этого не меняется. По новой конфигурации всегда можно однозначно восстановить старую (при помощи той же операции). Получается, что вероятность интересующего нас события в точности равна вероятности того, что последней картой колоды будет пика, а это 1/4.

Из решений, представленных в комментариях, было два, которые мало отличаются от изложенного.

Всем спасибо за участие!

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

Условие такое. Рассматривается перестановка чисел от 1 до n. Требуется, чтобы для любых трёх чисел, идущих в этой перестановке друг за другом, сумма двух последних делилась на первое.

Пример для n=6: 1, 2, 3, 5, 4, 6.

Вопросы таковы: при каких n можно предъявить такие примеры? Могут ли значения n быть сколь угодно большими? Какое "рекордное" по величине значение n можно реально предъявить?

Поскольку вопрос в целом открыт, приветствуются совместные усилия, и комментарии для всех открыты, как и сам пост.

Попалась на днях одна симпатичная вероятностная задача. В исходной постановке, она достаточно несложная, но более общий вопрос на эту тему для меня пока что открыт.

Имеется стандартный игральный кубик. Мы бросаем его несколько раз, и все выпавшие очки суммируем. Цель игры -- набрать заданное число очков, равное n. Если в какой-то момент мы его набрали, это означает выигрыш. Если превысили, то проиграли.

а) При каком значении n шансы на выигрыш максимальны?

б) Какова закономерность в распределении шансов на выигрыш между разными значениями n, то есть как научиться их быстро сравнивать между собой?

Если бы на кубике выпадали всего два значения 1 и 2, то ответ на пункт б) достаточно прост. Но уже для значений 1, 2, 3 закономерность перестаёт быть понятной.

Комментарии не скрываются.

Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то давно. Открывать эту ссылку вовсе не обязательно. Я постараюсь изложить всё как бы почти "с нуля".

Что такое невычислимая функция? Это такая функция, которую нельзя вычислить при помощи алгоритма, то есть невозможно написать программу для её вычисления. Хотя достаточно легко доказать, что невычислимые функции существуют, не так просто предъявить конкретный пример, а тем более интересный пример. В посте по ссылке такой пример был приведён, но описанная там функция Busy Beaver слишком уж быстро растёт. Мы её слабо себе представляем, зная только то, что её значения -- какие-то огромные числа. Здесь я хочу привести другой пример невычислимой функции, которая растёт очень медленно, и поведение которой мы можем себе представить намного лучше. Дополнительным соображением, побудившим меня написать этот текст, является связь с известными логическими парадоксами, а этой проблематики я в прошлом частенько касался.

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

Итак, пусть нам дано число, и надо написать программу, которая его распечатывает, останавливаясь при этом. Будем считать, что для печати у нас есть команда print. Тогда, чтобы распечатать число, скажем, 2021, достаточно написать команду print(2021). Программа будет готова.

Ясно, что бывают числа, распечатывать которые таким способом нежелательно. Допустим, вместо 2021 у нас есть очень большое число типа 100...0 с миллионом нулей на конце. Мы не хотим составлять программу из миллиона символов. Тогда можно распечатать нули в цикле. Примерно так:

print(1);
for i:=1 to 1000000 do print(0)

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

Обозначим то число, которое мы хотим напечатать, через n. Самый простой способ написания программы требует порядка lg n + C символов, где C -- небольшая константа. В тех случаях, когда число является "случайным", то есть состоит из случайно выбираемых цифр, скорее всего, нет принципиально другого способа распечатать число кроме как указать его явно. Однако зачастую оказывается возможным поступить как-то более хитро. Один такой пример мы привели. Другие примеры могут возникнуть на следующей основе.
( Collapse )

Давненько уже не было постов под этим "тегом". А сейчас очень симпатичная задача попалась. В принципе, поучаствовать в её решении могут все желающие, так как условие должно быть предельно понятным.

Рассмотрим числа 1, 2, 3. Их сумма равна 6, и произведение также равно 6. Легко проверить, что никаких других целых чисел с такими свойствами больше нет. А можно ли найти три дробных (положительных рациональных) числа, у которых и сумма, и произведение равны 6?

В идеале, хотелось бы описать все решения системы a+b+c=6, abc=6 в рациональных числах.

Комменты скринятся.

UPD 01.01.21 Раскрыл основные комментарии.

Давненько уже постов не помещал! А тут интересная головоломка попалась.

Даны натуральные числа от 1 до 2018. Их нужно разбить на пары, и числа в каждой паре сложить. Требуется, чтобы произведение полученных 1009 чисел было точной четвёртой степенью.

Задача хороша тем, что её можно решать, условно говоря, "в трамвае". Если бы чисел было 2016, то решение совсем простое: разбиваем по принципу 1+2016, 2+2015, ... , и получаем 1008 одинаковых чисел. Их произведение, конечно, будет 4-й степенью натурального числа. А вот для 2018 решение далеко не очевидное. Но оно есть.

Забавно, что мой предыдущий пост из этой серии имел место два года (и один день) назад.

Комменты до времени "скринятся".

UPD (29.12.18) Верные решения (причём весьма разнообразные) предоставили relf, roman_rogalyov и fiviol.

UPD (03.01.19) Раскрываю все комментарии. Принципы решения здесь были самые разнообразные. Наиболее эффектными мне показались решения, в которых для первых нескольких чисел осуществляется какая-то нетривиальная группировка (то есть не по принципу "первый с последним"), и всё остальное под неё "подгоняется".

Всем спасибо за участие, и с наступившим Новым годом!