Математическое и загадочное

[E.K.]

А дальше подумалось, что задачку можно и иначе сформулировать. Например, с весами. Есть n тяжёлых монет и n лёгких, их поочерёдно кидают на весы. Какова вероятность того, что весы всё время будут или ровно висеть - или же свешиваться только в одну сторону?.. Нет, не так. А вот так:

 

Парусный корабль идёт из точки-а в точку-бэ строго против ветра. Само собой, идёт галсами: повернёт направо, повернёт налево. Причём в каждый помент времени он случайно поворачивает или вправо - либо же влево. С какой вероятностью он всё время будет идти только с одной стороны линии "а-бэ"?

 

Пусть он должен быть только слева от линии А-Б, для наглядности картинка - так понятнее?

 

Наверное же, в таких условиях - подсчитать вероятности попадания в "Б" гораздо проще!

[santax]

У меня была логика следующая родилась:

2000 фанклубней: 1000 с билетами и 1000 без. На каждом шаге (из 2000) число оставшихся фанклубней с билетами должно быть меньше или равно числа фанклубней без билетов. Если это условие рушится на каком-то шаге, то уже дальше комбинация не подходит.

Но вот как её просчитать для 2000 итераций, я не могу пока посчитать.

[iv65]

А дальше подумалось, что задачку можно и иначе сформулировать. Например, с весами. Есть n тяжёлых монет и n лёгких, их поочерёдно кидают на весы. Какова вероятность того, что весы всё время будут или ровно висеть - или же свешиваться только в одну сторону?..

Вероятность этого очень мала (весы приходят в равновесие) при малых значениях  n

 

Ткну пальцем в небо: при больших значениях n , при допустим, n=1000 -1,

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

Нельзя ли небольшую вводную?

При каких значениях этого параметра :

https://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%B2%D0%B5%D1%80%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%B2%D0%B0%D0%BB

Вы предполагаете решить эту нерешаемую задачу?

Заранее,

Спасибо за Ваш ответ.

@santax,

 https://forum.kasperskyclub.ru/index.php?showtopic=54210&page=80&do=findComment&comment=957911

В условиях этой задачи:

https://forum.kasperskyclub.ru/index.php?showtopic=54210&page=79&do=findComment&comment=955752

говорится о количестве фан-клубней на 20 (двадцать) единиц больше.

 

 

100%, если учесть, что они встали друг за другом. Сперва тот кто возвращает билет, а затем кто покупает билет.

ИМХО

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

Изменено 21 февраля, 2020 пользователем iv65

[E.K.]

Пусть он должен быть только слева от линии А-Б, для наглядности картинка - так понятнее?

 

Наверное же, в таких условиях - подсчитать вероятности попадания в "Б" гораздо проще!

И тут же смело я начал рисовать убедительные картинки -

 

И ещё более убедительные картинки ->

 

Как тут же понял, что у нас не бесконечная выборка. Что после первой "1/2" дальше совершенно не 50%, поскольку "кто-то уже сдал билет". То есть, например, было 5 билетов и 5 безбилетников, которые случайно попадают на кассу. В первой попытке вероятность "ура" = 1/2. Примерно 50%. Но во втором заходе случайность выборки не 50%-50%, а "4-5" - поскольку один билетик уже сдан в кассу. То есть, на каждом ходе надо учитывать историю уже прошедших историй.. Что условные соседи "q" и "r" не дают 1/2*(q+r) на следующей итерации (на картинке я выделил их коричневым).

 

Короче, как-то всё неприглядно вырисовывается...

[E.K.]

Ага, а вот так если попробовать? Самый "крайний проходной" вариант выглядит вот так:

 

101010...10    (поочерёдно "с билетом" - "без билета").

 

Если хоть одну единицу сдвинуть направо или поменять местами единицу слева с каким-то нулём правее - то всё ломается. Если переставить единицу (или несколько) влево и поменять местами с "левыми" нулями - то всё норм. То есть, нужно подсчитать количество различных перестановок единиц налево. Для всех наборов этих единиц.

 

Переставляем одну единицу влево. Первую единицу двигать некуда, вторую можно переставить только в одну позицию, для третьей уже два варианта: 10101... - поменять местами какой-то из нолей с третьей единицей можно двумя способами. Чевёртую единицу - три варианта, - и так далее. Последнюю единицу можно переставить в n-1 позицию.

 

Итого для одной переставляемой единицы имеем 1+2+...+(n-1) = n*(n-1)/2 вариантов.

 

Теперь переставляем две единицы. Самую первую не трогаем - её некуда переставляь налево. Следующие единицы можно переставлять.. А там что-то много вариантов.. C(2,n-1) вроде как.. То есть, (n-1)!/(2*(n-3)!) = (n-1)*(n-2)/2.

 

1010101010...1010 - 1 вариант перестановок.

1010101010...1010 - 2 варианта.

1010101010...1010 - 3.

...

1010101010...1010 - n-3.

1010101010...1010 - n-2.

 

1010101010...1010 - 3.

1010101010...1010 - 5? .. как бы это подсчитать... вышел зайчик погулять..

[iv65]

Короче, как-то всё неприглядно вырисовывается...

Вы совершенно правы, так как в условиях этой задачи имеется это:

" Есть n тяжёлых монет и n лёгких, "

Глубоко личное ИМХО

При одинаковых значениях данного и искомого:

https://infourok.ru/urok-matematiki-vo-klasse-po-teme-dannie-i-iskomoe-415687.html

Эту задачу невозможно решить в принципе.

Уж очень много неизвестных величин в представленной Вами задаче.

Но, "решение любой задачи имеется всегда".

А именно, либо да, либо нет

Изменено 22 февраля, 2020 пользователем iv65

[E.K.]

Эту задачу невозможно решить в принципе.

"Мы делаем невозможное. Возможное сделают и без нас" (с)

 

! Дальнейшие рассуждения могут содержать ошибки. Исправления (если будут таковые) - они будут вноситься в этот же текст.

! Возможные дополнения будут также добавляться в конец этого текста.

 

=> Целью является подсчитать количество "перестановок единиц влево" комбинации 101010...1010, состоящей из n пар '10' - попеременно стоящих n единиц и n нулей.

 

Для начала два правила.

 

1. При перестановках порядок переставляемых единиц сохраняется. То есть, если переставляемые единицы изначально стояли слева направо как "первая-вторая-...-последняя", то в результате перестановки они тоже должны стоять в том же порядке. Иначе будут дубликаты и некоторые перестановки будут подсчитаны два и более раз.

 

10..0..0..a..b...

 

Если разрешить произвольную перестановку, то получаем два одинаковых результата:

 

10..a..b..0..0.. = 10..1..1..0..0..

10..b..a..0..0.. = 10..1..1..0..0..

 

2. Перестановка совершается одновременно для всех единиц. То есть, нельзя "более правую" единицу 'b' поставить на место, освобождающееся от перестановки единицы 'a'.

 

10..0..a..b...

 

Если разрешить последовательную перестановку с возможностью замещения "нового" нуля, то получаем результат, идентичный просто перестановке одной единицы 'b':

 

10..a..b..0.. = 10..1..1..0.. 

10..b..a..0.. = 10..1..1..0.. 

 

3. Подобными операциями мы покрываем все возможные варианты "успешной очереди". Поскольку любую такую "успешную" последовательность одним движением можно вернуть в исходный 101010..010.

 

То есть, выбираем "паровозик" из единиц и одним махом и неменяя порядок "вагончиков" переставляем его в нули.

 

Количество перестановок одной единицы мы уже подсчитали. Это 1+2+...+(n-1) = n*(n-1)/2 вариантов. Давайте подсчитаем сколько вариантов перестановки двух единиц. Вдруг это нам поможет решить всю задачку?

 

Итак, есть последовательность:

 

10...010...010..

1 -k-нулей- 1 -m-нулей - 1..

 

или так, чтобы было понятно где "единица-a" и где "единица-b" ->

 

1 -k-нулей- a -m-нулей - b..

 

Количество возможных перестановок.. Например, чтобы мозг разогреть:

 

1010101 - одна перестановка (переставляемые единицы выделены)

1010101 - два варианта.

1010101 - три..

 

Единицу-а (1a) можно поставить вместо любого из k "левых нулей". Единицу-b (1b) ставим в любой ноль, которые правее новой позиции единицы-a (кроме изначальной позиции 1a). Получается..

 

1a в первый ноль -> у 1b m+k-1 вариантов перестановок (m+k-1 доступных нулей).

1a в ноль-2 -> у 1b m+k-2 вариантов.

1a в ноль-3 -> у 1b m+k-3 вариантов.

...

1a в ноль-k -> у 1b m вариантов.

 

Получаем сумму:

 

m+k-1  +  m+k-2  +  m+k-3  +  ... + m+0  =  k*m + k*(k-1)/2  =  k*(m + (k-1)/2)

 

Теперь это надо просуммировать для всех натуральных k и m, где k+m. Т.е. все возможные выборки позиций для 1a и 1b. Номер самой первой единицы считаем нулевым, поскольку она в перестановках не участвует:

 

10a0b0..010 

10a010..0b0    k=1,m=n-2.

1010a0..0b0    k=2,m=n-3.

 

Так, получаем вот такие варианты количества доступных нулей для переставляемой пары единиц. Ещё раз, это все возможные варианты {k,m} ->

 

1,1 - 1,2 - 1,3 - 1,4 - ... - 1,n-2

2,1 - 2,2 - 2,3 - ... - 2,n-3

3,1 - 3,2 - 3,3 - ... - 3,n-4

...

n-3,1 - n-3,2

n-2,1

 

И все эти пары нужно подставить в ранее полученное k*(m + (k-1)/2). Итого, для предварительной оценки количества вариантов перестановок пары единиц получаем вот такого крокодила:

 

k=1:     S1 = 1 + 2 + 3 + 4 + ... + n-2                                    = 1/2 * (n-1)*(n-2)    // арифметическая прогрессия

k=2:     S2 = 2*(1+1/2 + 2+1/2 + 3+1/2 + ... + n-3 + 1/2)      = 2/2 * (n-1)*(n-3)    // проверяйте, вроде правильно

k=3:     S3 = 3*(1+1 + 2+1 + 3+1 + ... + n-4+1)                    = 3/2 * (n-1)*(n-4)

k=4:     S4 = 4*(1+3/2 + 2+3/2 + 3+3/2 + ... + n-5 + 3/2)      = 4/2 * (n-1)*(n-5)

...

k=n-3:  S(n-3) = (n-3)*( 1 + (n-4)/2 + 2 + (n-4)/2 )                = (n-3)*(n-1)      // что есть (n-3)/2 * (n-1)*2

k=n-2:  S(n-2) = (n-2)*( 1 + (n-3)/2 )                                     = (n-2)/2 * (n-1)*1

 

Проверяйте на ошибки..

 

Я беру паузу, потом подсчитаю... здесь же. Если никто меня не опередит. Но предупреждаю - это только для пары единиц. Вдруг посмотрим на результат и угадаем формулу количества вариантов для тройки, четвёрки и (n-1)-ки переставляемых единичек..

 

--- Продолжаю.

 

Итак, нужно подсчитать все возможные варианты для {k,m} = {1,k+m. Для каждого конкретного k значения m получаются {1,2,...,n-k-1}. Отлично. Подсчитаем сумму Sk для произвольного k:

 

Sk = Sum (k*(m + (k-1)/2)) для m= от 1 до n-k-1 =

k*( (1+2+...+(n-k-1)) +            // проверяйте вычисления..

1/2*(n-k-1)*(k-1) ) =

 

k/2 * ( (n-k-1)*(n-k) + (n-k-1)*(k-1) ) = k/2 * (n-1) * (n-k-1)

 

Итого, для каждого k число вариантов перестановок = k/2 * (n-1) * (n-k-1)

Вроде бы сходится со значениями S1,S2,...Sx выше.

 

Теперь надо подсчитать их сумму для всех k={1,2,...n-2} =>

 

S = Sum (k/2 * (n-1) * (n-k-1)) для всех этих k =

(n-1)/2 * ( n*k - k*(k+1) ) = 

 

Как считать Sum(n*k) = понятно, это n умноженное на арифметическую прогрессию 1,2,...,n-2 = (n-1)*(n-2)/2

 

А вот как считать сумму k*(k+1) по всем k от единицы до (n-2) я что-то залип.. Это получается сумма арифметических прогрессий.. Ой, спасите-помогите...

 

2 + 6 + 12 + 20 + 30 + 42 + ... + (n-2)*(n-1) = сколько будет?

[E.K.]

Ага, сумма k*(k+1) по всем k от единицы до (n-2) есть сумма всех квадратов до (n-2) плюс сумма всех k.

 

Сумма всех квадратов от 1 до x = x(x+1)(2x+1)/6 (можно найти здесь, доказательство методом матиндукции). Тогда сумма всех k*(k+1) =

 

(n-2)*(n-1)(2n-3)/6 + (n-1)*(n-2)/2 = (n-1)(n-2)/6 * ( 2n-3 + 3 ) = n(n-1)(n-2)/3

 

То есть, сумма всех вариантов перестановок двух единиц =

 

S = Sum (k/2 * (n-1) * (n-k-1)) для всех этих k =

(n-1)/2 * ( n*k - k*(k+1) ) = (n-1)/2 * ( n*(n-1)(n-2)/2 - n*(n-1)(n-2)/3 ) = n * (n-1)^2 * (n-2) / 12

 

Проверяем для n=3: 101010 должна получиться единица.. 3*4*1/12 = 1

Проверяем для n=4: 10101010 должно получиться.. шесть. А получается.. 4*9*2/12 = 6.

 

Верно!

 

Итого, количество уже выловленных вариантов равно:

 

1                                        - это изначальный 101010..1010, плюс

n * (n-1) / 2                       - количество перестановок одной единицы.

n * (n-1)^2 * (n-2) / 12      - количество перестановок двух единиц.

 

Проверяем для четырёх. Если посмотреть вооон туда, то для четырёх подсчитано вручную. Ответ = 14 вариантов. То есть, ещё один вариант перестановки трёх единиц (чтобы получить 11110000 - а больше перестановок трёх единиц и нет), тогда => 1 изначальный + 6 + 6 + 1 завершающий = 14.

 

Всё верно. Но что-то браться за подсчёт вариантов трёх переставляемых единиц... как-то страшно.

 

Но что видно:

n=2: количество вариантов 1+1 = 2 из всех возможных 6 вариантов, вероятность "успеха очереди" = 1/3

n=3: будет 1 + 3 + 1 = 5 из 20 вариантов, успех = 1/4.

n=4: будет 1 + 6 + 6 + 1 = 14 из С(4,8) = 8!/(4!*4!) = 5*6*7*8/24 = 70, вероятность успеха = 1/5.

 

Вот эти 1-3-1, 1-6-6-1 = это всё как-то очень сильно напоминает биномиальные коэффициэнты, но какие-то другие.. Горячо, ой горячо...

[E.K.]

Чёрт, решение оказалось с одной стороны элементарным, а с другой стороны... Математики, доказавшие подобные штуки в 18-19 веках, навсегда вошли в историю математики. Это Леонард Эйлер и Эжен Шарль Каталан.

 

Доказательство следующее. Мы уже "ручками" получили, что количество "удачных" очередей для n=1,2,3,4 есть 1,2,5,14. А если погуглить (именно погуглить, яндекс такси-еда..) - так вот, если погуглить эту последовательность, то мы попадаем в... Числа Каталана! (помните я их использую в предновогодних разминках с номерами года 2018-2019-2020?) И там, на этой самой странице всё и расписано.. Решение я почерпнул оттуда. Сейчас я его сюда странслирую.

 

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

 

Рассмотрим рекурсию "правильных скобочных субпоследовательностей" (ПСС). Если w₁ и w₂ обе ПСС, то их объединение с дополнительными скобками (w₁)w₂ тоже ПСС. То есть, чтобы получить значение количества ПСС для n+1 необходимо разбить все ПСС для n на всевозможные подпоследовательности, расставить туда скобки '()' и подсчитать полученный результат:

 

ПСС(n+1) = ()%ПСС(n)% + (%()ПСС(n) без открывающей скобки% + ... + ... ... и так далее двигаем новые скобки ( и ) дальше и дальше. То есть, сначала ставим '()' перед всеми вариантами ПСС(n), а потом оборачиваем этими скобками все возможные ПСС-подпоследовательности. И считаем их сумму. Если выражаться формально, то это будет.. Обозначим "Количество ПСС" как КПСС:

 

КПСС(n+1) = КПСС(0)*КПСС(n) + КПСС(1)*КПСС(n-1) + КПСС(2)*КПСС(n-2) + ... + КПСС(n)*КПСС(0).

 

Пусть КПСС(0) = 1 (никто не пришёл с билетом, задачку считаем решённой).

 

Тогда:

КПСС(1) = тоже 1.

КПСС(2) = КПСС(0)*КПСС(1) + КПСС(1)*КПСС(0) = 2.   

// последовательность получается: 1,1,2, ниже получаем 5, 14, 42...

КПСС(3) = 1*2 + 1*1 + 2*1 = 5.

КПСС(4) = 1*5 + 1*2 + 2*1 + 5*1 = 14.

КПСС(5) = 1*14 + 1*5 + 2*2 + 5*1 + 14*1 = 42.

КПСС(6) = 1*42 + 1*14 + 2*5 + 5*2 + 14*1 + 42*1 = 132.

 

Продолжать можно бесконечно. Но для решения нашей задачки эти знания пока недостаточно практичны. Надо бы свести в формулу покороче... и есть такая! Числа Каталана C(n) // выше они же 'КПСС' =>

 

C(n) = (2n)! / n!*(n+1)!

 

Но доказательства там.. достаточно злобные. Пока принимаем их на веру.

 

Итого имеем, что:

 

1) количество "правильных очередей" (оно же "правильные скобочные последовательности") = (2n)! / n!*(n+1)!

2) общее количество всех очередей - это обычное сочетание из n по 2n и равно это: C(n,2n) = (2n)! / n!*n!

 

Делим количество "правильных" на общее число очередей и получаем искомую вероятность того, что очередь из 2n фанклубней удачно сдаст-купит билет на ёлку:

 

( (2n)! / n!*(n+1)! )  / ( (2n)! / n!*n! ) = ( (2n)! / n!*(n+1)! )  / ( (2n)! / n!*n! ) = n! / (n+1)! = 1/(n+1)

 

Ответ для общего числа n пар:  1/(n+1)

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

 

p = 1/1011

 

Всё. Решено. Можно выкидывать новогоднюю ёлку, пора пришла!

[santax]

Ужас... Эйлеру и Каталану заняться нечем было в 18-19 веках.. Но спасибо им - нам не нужно проходить их пути поиска доказательств.

[iv65]

А если погуглить (именно погуглить, яндекс такси-еда..)

Насколько я помню, гуглить на этом форуме - читерство

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

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

Сразу вспомнились эти слова:

https://rustih.ru/mixail-lermontov-borodino/

— Да, были люди в наше время,

Не то, что нынешнее племя:

Богатыри — не вы!

Извиняюсь,

Никого не хотел обидеть.

https://ru.wikipedia.org/wiki/%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD,_%D0%AD%D0%B6%D0%B5%D0%BD_%D0%A8%D0%B0%D1%80%D0%BB%D1%8C

Был  ровесником Лермонтова

 https://ru.wikipedia.org/wiki/%D0%9B%D0%B5%D1%80%D0%BC%D0%BE%D0%BD%D1%82%D0%BE%D0%B2,_%D0%9C%D0%B8%D1%85%D0%B0%D0%B8%D0%BB_%D0%AE%D1%80%D1%8C%D0%B5%D0%B2%D0%B8%D1%87

Изменено 24 февраля, 2020 пользователем iv65

[E.K.]

Насколько я помню, гуглить на этом форуме - читерство 

Читерство - гуглить решения задач. А вот залезть и посмотреть на таблицу простых чисел, теоремы Эйлера, основы комбинаторики, вольфрамом проверить, последовательность поискать - ничего зазорного в этом нет.

[E.K.]

Наверное, вы думаете, что я забыл про вас? И не надейтесь! Сегодня у меня для любителей судоку:

 

Говорят, что настоящие мастера такие задачки в уме решают. Как именно - мне пока непонятно..

[Skarbovoy]

Наверное, вы думаете, что я забыл про вас? И не надейтесь! Сегодня у меня для любителей судоку:

Последнюю судоку год назад решил здесь.

Пруф:

Для получения ссылки нужен премиум акаунт.

 

 

[E.K.]

Последнюю судоку год назад решил здесь.

 

Пруф:

Sudoku Solver.PNG

Для получения ссылки нужен премиум акаунт.

 

 

1) Добро пожаловать обратно в наш уютный... серпентарий Поскольку я по гороскопу змея, а бОльшую часть работы приходится делать здесь мне.. Вот, например, вы пропустили еженовогодный забег "собери 2020 из ничего".

 

2) По поводу программного решения подобных задачек.. Я не против, но в данном конкретном случае эта задачка должна быть решена мозгом. Если более подходящего нет, то человеческим. Собственным.

 

2.1) Чуть позже накину программистких упражнений на эту тему. Не просто решить, а найти оптимальное решение в зависимости от развесовки веток и переборов.. Чуть позже попрошу поупражняться.

 

Но задачка хорошая! Если своим умом решать, а не машинным.