E.K. Опубликовано 20 февраля, 2020 Автор Поделиться Опубликовано 20 февраля, 2020 А дальше подумалось, что задачку можно и иначе сформулировать. Например, с весами. Есть n тяжёлых монет и n лёгких, их поочерёдно кидают на весы. Какова вероятность того, что весы всё время будут или ровно висеть - или же свешиваться только в одну сторону?.. Нет, не так. А вот так: Парусный корабль идёт из точки-а в точку-бэ строго против ветра. Само собой, идёт галсами: повернёт направо, повернёт налево. Причём в каждый помент времени он случайно поворачивает или вправо - либо же влево. С какой вероятностью он всё время будет идти только с одной стороны линии "а-бэ"? Пусть он должен быть только слева от линии А-Б, для наглядности картинка - так понятнее? Наверное же, в таких условиях - подсчитать вероятности попадания в "Б" гораздо проще! 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
santax Опубликовано 21 февраля, 2020 Поделиться Опубликовано 21 февраля, 2020 У меня была логика следующая родилась: 2000 фанклубней: 1000 с билетами и 1000 без. На каждом шаге (из 2000) число оставшихся фанклубней с билетами должно быть меньше или равно числа фанклубней без билетов. Если это условие рушится на каком-то шаге, то уже дальше комбинация не подходит. Но вот как её просчитать для 2000 итераций, я не могу пока посчитать. 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
iv65 Опубликовано 21 февраля, 2020 Поделиться Опубликовано 21 февраля, 2020 (изменено) А дальше подумалось, что задачку можно и иначе сформулировать. Например, с весами. Есть 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. Опубликовано 21 февраля, 2020 Автор Поделиться Опубликовано 21 февраля, 2020 Пусть он должен быть только слева от линии А-Б, для наглядности картинка - так понятнее? Наверное же, в таких условиях - подсчитать вероятности попадания в "Б" гораздо проще! И тут же смело я начал рисовать убедительные картинки - И ещё более убедительные картинки -> Как тут же понял, что у нас не бесконечная выборка. Что после первой "1/2" дальше совершенно не 50%, поскольку "кто-то уже сдал билет". То есть, например, было 5 билетов и 5 безбилетников, которые случайно попадают на кассу. В первой попытке вероятность "ура" = 1/2. Примерно 50%. Но во втором заходе случайность выборки не 50%-50%, а "4-5" - поскольку один билетик уже сдан в кассу. То есть, на каждом ходе надо учитывать историю уже прошедших историй.. Что условные соседи "q" и "r" не дают 1/2*(q+r) на следующей итерации (на картинке я выделил их коричневым). Короче, как-то всё неприглядно вырисовывается... 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 22 февраля, 2020 Автор Поделиться Опубликовано 22 февраля, 2020 Ага, а вот так если попробовать? Самый "крайний проходной" вариант выглядит вот так: 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? .. как бы это подсчитать... вышел зайчик погулять.. 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
iv65 Опубликовано 22 февраля, 2020 Поделиться Опубликовано 22 февраля, 2020 (изменено) Короче, как-то всё неприглядно вырисовывается... Вы совершенно правы, так как в условиях этой задачи имеется это: " Есть n тяжёлых монет и n лёгких, " Глубоко личное ИМХО При одинаковых значениях данного и искомого: https://infourok.ru/urok-matematiki-vo-klasse-po-teme-dannie-i-iskomoe-415687.html Эту задачу невозможно решить в принципе. Уж очень много неизвестных величин в представленной Вами задаче. Но, "решение любой задачи имеется всегда". А именно, либо да, либо нет Изменено 22 февраля, 2020 пользователем iv65 Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 22 февраля, 2020 Автор Поделиться Опубликовано 22 февраля, 2020 Эту задачу невозможно решить в принципе. "Мы делаем невозможное. Возможное сделают и без нас" (с) ! Дальнейшие рассуждения могут содержать ошибки. Исправления (если будут таковые) - они будут вноситься в этот же текст. ! Возможные дополнения будут также добавляться в конец этого текста. => Целью является подсчитать количество "перестановок единиц влево" комбинации 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) = сколько будет? 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 22 февраля, 2020 Автор Поделиться Опубликовано 22 февраля, 2020 Ага, сумма 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 = это всё как-то очень сильно напоминает биномиальные коэффициэнты, но какие-то другие.. Горячо, ой горячо... 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 23 февраля, 2020 Автор Поделиться Опубликовано 23 февраля, 2020 Чёрт, решение оказалось с одной стороны элементарным, а с другой стороны... Математики, доказавшие подобные штуки в 18-19 веках, навсегда вошли в историю математики. Это Леонард Эйлер и Эжен Шарль Каталан. Доказательство следующее. Мы уже "ручками" получили, что количество "удачных" очередей для n=1,2,3,4 есть 1,2,5,14. А если погуглить (именно погуглить, яндекс такси-еда..) - так вот, если погуглить эту последовательность, то мы попадаем в... Числа Каталана! (помните я их использую в предновогодних разминках с номерами года 2018-2019-2020?) И там, на этой самой странице всё и расписано.. Решение я почерпнул оттуда. Сейчас я его сюда странслирую. Для начала переведём нули-единицы в скобки. Пусть клубень с билетом будет открывающей скобкой '(', а клубень без билета закрывающей ')'. В таком случае наша задача "купить все билеты" конгруэнтна количеству "правильных скобочных последовательностей" - то есть, "обеспечивающим последовательную вложенность подпоследовательностей, обрамлённых открытой и закрытой скобкой одного типа" (с) Википедия. А количество таких последовательностей и есть Числа Каталана. Рассмотрим рекурсию "правильных скобочных субпоследовательностей" (ПСС). Если w1 и w2 обе ПСС, то их объединение с дополнительными скобками (w1)w2 тоже ПСС. То есть, чтобы получить значение количества ПСС для 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 Всё. Решено. Можно выкидывать новогоднюю ёлку, пора пришла! 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
santax Опубликовано 23 февраля, 2020 Поделиться Опубликовано 23 февраля, 2020 Ужас... Эйлеру и Каталану заняться нечем было в 18-19 веках.. Но спасибо им - нам не нужно проходить их пути поиска доказательств. 1 2 Ссылка на комментарий Поделиться на другие сайты Поделиться
iv65 Опубликовано 24 февраля, 2020 Поделиться Опубликовано 24 февраля, 2020 (изменено) А если погуглить (именно погуглить, яндекс такси-еда..) Насколько я помню, гуглить на этом форуме - читерство А за решение этой задачи огромное спасибо людям, которые даже и не подозревали о существовании калькуляторов, и, тем более ПК. Да были великие люди, и недаром, о них пишут всякие Википедии. Сразу вспомнились эти слова: 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. Опубликовано 24 февраля, 2020 Автор Поделиться Опубликовано 24 февраля, 2020 Насколько я помню, гуглить на этом форуме - читерство Читерство - гуглить решения задач. А вот залезть и посмотреть на таблицу простых чисел, теоремы Эйлера, основы комбинаторики, вольфрамом проверить, последовательность поискать - ничего зазорного в этом нет. 2 Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 6 марта, 2020 Автор Поделиться Опубликовано 6 марта, 2020 Наверное, вы думаете, что я забыл про вас? И не надейтесь! Сегодня у меня для любителей судоку: Говорят, что настоящие мастера такие задачки в уме решают. Как именно - мне пока непонятно.. 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
Skarbovoy Опубликовано 6 марта, 2020 Поделиться Опубликовано 6 марта, 2020 Наверное, вы думаете, что я забыл про вас? И не надейтесь! Сегодня у меня для любителей судоку: Последнюю судоку год назад решил здесь. Пруф: Для получения ссылки нужен премиум акаунт. Ссылка на комментарий Поделиться на другие сайты Поделиться
E.K. Опубликовано 6 марта, 2020 Автор Поделиться Опубликовано 6 марта, 2020 Последнюю судоку год назад решил здесь. Пруф: Sudoku Solver.PNG Для получения ссылки нужен премиум акаунт. 1) Добро пожаловать обратно в наш уютный... серпентарий Поскольку я по гороскопу змея, а бОльшую часть работы приходится делать здесь мне.. Вот, например, вы пропустили еженовогодный забег "собери 2020 из ничего". 2) По поводу программного решения подобных задачек.. Я не против, но в данном конкретном случае эта задачка должна быть решена мозгом. Если более подходящего нет, то человеческим. Собственным. 2.1) Чуть позже накину программистких упражнений на эту тему. Не просто решить, а найти оптимальное решение в зависимости от развесовки веток и переборов.. Чуть позже попрошу поупражняться. Но задачка хорошая! Если своим умом решать, а не машинным. 1 1 Ссылка на комментарий Поделиться на другие сайты Поделиться
Рекомендуемые сообщения
Пожалуйста, войдите, чтобы комментировать
Вы сможете оставить комментарий после входа в
Войти