нужен совет математиков

[Ignat 0]

И так, пойдем обедать. Сегодня в 13:00, встречаемся на углу улиц Sokolovska и Kollarova.

 

Ок.

[KOTRPA 0]

Ужос! Стока людей стараются программировать и никто не хочет считать! Между прочим, дискра - обязательный предмет у каждого будущего математика и программиста на первом курсе! :-)

Учить дискретку на первом курсе -- маразм!

Только после полного курса матана, аналитик, теории вероятности & etc. Иначе будет непонятно что за всем этим бередом стоит.

[Ignat 0]

А что такое "аналитик"?

[Stevendall 0]

"аналитик"

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

 

В связи с темой, пересмотрел учебник по комбинаторике... Нет там прямой формулы для расчёта топиковой задачи. Тогда не понял, кто-то тут намекая на дискриптиву хочет сказать, что задача не по комбинаторике?

[Ignat 0]

Вот обещанное точное решение

 

ШАГ 1. Рассмотрим следующую задачу:

(См. Виленкин, Комбинаторика, стр. 63, ссылка где скачать книгу в посте выше)

 

Задача о львах и тиграх

 

Укротитель хищных зверей хочет вывести на арену цирка 5 львов и 4 тигров;

при этом нельзя чтобы 2 тигра шли друг за другом.

Сколькими способами он может расположить зверей.

 

Решение смотрим в книжке (очень простое, но лень набирать)

Там же смотрим следующую общую формулу, для n львов и k тигров

(k меньше либо равно n+1).

Формула : n!(n+1)!/(n-k+1)!

 

(для тех, кто не помнит, что такое n! (n-факториал) = 1*2*3*4*....(n-2)*(n-1)*n)

 

Сформулируем это в виде теоремы

 

Теорема (о львах и тиграх)

 

Укротитель хищных зверей хочет вывести на арену цирка n львов и k тигров

(k меньше либо равно n+1); при этом нельзя чтобы 2 тигра шли друг за другом.

Тогда это можно сделать n!(n+1)!/(n-k+1)! способами.

 

ШАГ 2.

Пусть цифры 1,2,3,4 обозначают 4 короля.

Рассмотрим как эти короли могут располагаться относительно друг друга,

когда карты выложены в ряд с 1 по 36.

Может оказаться, что некоторые короли будут рядом,

например 23, или все будут рядом 3241 или никакие два не будут рядом и.т.д.

 

Пусть –(минус) обозначает какое-то количество карт (большее чем 0),

среди которых нет королей.

 

Тогда короли могут встретиться в полосе из 36 карт

Следующими способами

 

Способ 1K ( никакие два короля не будут рядом )

1-2-3-4.

 

Способ 2K (короли лягут парами,всего 12 вариантов)

12-34 13-24 14-23

21-34 13-42 14-32

12-43 31-24 41-23

21-43 31-42 41-32

 

 

Способ 3K (два короля вместе и два отдельно, всего 12 вариантов)

12-3-4 13-2-4 14-2-3

21-3-4 31-2-4 41-2-3

23-1-4 24-1-3 34-1-2

32-1-4 42-1-3 43-1-2

 

Способ 4K (три вместе и один отдельно,всего 24 варианта)

123-4 124-3 134-2 234-1

132-4 ... ... ...

213-4 ... ... ...

231-4 ... ... ...

312-4 ... ... ...

321-4 ... ... ...

 

Способ 5K (четыре вместе, всего 4!=24 варианта)

1234

....

....

 

 

ШАГ 3.

 

Те же 5 способов расположения возможны и для тузов.

По аналогии назовем их Способ 1Т,...Способ 5Т.

 

 

ШАГ 4.(Главный)

 

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

(хотя тузы могут лежать рядом с тузами, а короли рядом с королями).

 

Например, пусть короли лежат как в способе 1К (то есть никакие 2 короля не лежат рядом),

а тузы лежат как в способе 5Т(то есть 4 туза подряд),

но в фиксированном порядке (например, туз пиковый,туз трефовый, туз бубновый и

туз червовый).

 

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

применим теорему о львах и тиграх

 

В нашем случае Тигры это 4 короля + 1 блок из подряд идущих 4-х тузов,

то есть всего 5 тигров.

Львы --- это остальные карты 36-4К-4Т=28.

Таким образом получаем 28!*29!/(28-5+1)!=28!*29!/24! способов расположения

для фиксированной последовательности тузов в своем блоке.

Но тузы внутри своего блока мы можем переставить 4!=24 способами.

Поэтому Способ 1K and Способ 5Т нам даст 28!*29!/24!*24!=28!*29! способов.

 

Далее, каждому из 5 способов 1K,..,5K соответствует 5 способов 1T,..,5T

(то есть всего 25 способов).

 

Подсчет соответствующих вариантов удобно записать в виде таблицы

 

------------------------------------------------

1 столбец N способа

2 столбец количество вариантов внутри способа

3 столбец N способа

4 столбец количество вариантов внутри способа

5 столбец общее количество тигров

-------------------------------------------------

 

Способ 1К 1 Способ 1Т 1 4+4=8

Способ 2К 12 Способ 1Т 1 2+4=6

Способ 3К 12 Способ 1Т 1 3+4=7

Способ 4К 24 Способ 1Т 1 2+4=6

Способ 5К 24 Способ 1Т 1 1+4=5

Способ 1К 1 Способ 2Т 12 4+2=6

Способ 2К 12 Способ 2Т 12 2+2=4

Способ 3К 12 Способ 2Т 12 3+2=5

Способ 4К 24 Способ 2Т 12 2+2=4

Способ 5К 24 Способ 2Т 12 1+2=3

Способ 1К 1 Способ 3Т 12 4+3=7

Способ 2К 12 Способ 3Т 12 2+3=5

Способ 3К 12 Способ 3Т 12 3+3=6

Способ 4К 24 Способ 3Т 12 2+3=5

Способ 5К 24 Способ 3Т 12 1+3=4

Способ 1К 1 Способ 4Т 24 4+2=6

Способ 2К 12 Способ 4Т 24 2+2=4

Способ 3К 12 Способ 4Т 24 3+2=5

Способ 4К 24 Способ 4Т 24 2+2=4

Способ 5К 24 Способ 4Т 24 1+2=3

Способ 1К 1 Способ 5Т 24 4+1=5

Способ 2К 12 Способ 5Т 24 2+1=3

Способ 3К 12 Способ 5Т 24 3+1=4

Способ 4К 24 Способ 5Т 24 2+1=3

Способ 5К 24 Способ 5Т 24 1+1=2

 

------------------------------------------------

Заметим, что количество львов всегда равно 28.

 

ШАГ5.

 

Считаем по аналогии с примером Способ 1К and Способ 5Т)

Получаем(после несложных преобразований)

 

28!*29!*(1/21!+24/22!+216/23!+912/24!+1872/25!+1728/26!+576/27!)=

137147414927299238903756459184488448000000.

 

Таким образом мы нашли количество всех вариантов,

когда никакой король не лежит рядом с никаким тузом.

Количество всех раскладов карт в ряд от 1 до 36 равно 36!(очевидно).

 

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

равно

 

36!-полученное число,

 

что равно 234845911862601978564242988966346752000000.

 

Искомая вероятность, следовательно равна

 

234845911862601978564242988966346752000000/36!=

3293773/5217300~0.6313175397

 

QED.

[agata 1]

Ignat СПАСИБО!!!!!!!!!!!

[GDV 9787]

Респект, Ignat.

Эх, где мои 17 лет.

[Ignat 0]

agata

Не за что, просто самому стало интересно.

А вообще я почти уверен, что есть общая формула для такого рода задач.

 

Эх, где мои 17 лет.

 

Там же, где мои 14.

[GDV 9787]

Нет-нет, в данном случае имелось в виду то, что слова Высоцкого удачно совпали с моим возрастом, когда я учился на физико-математическом факультете.

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

Странно, что помню, что такое факториал.

[Ignat 0]

... учился на физико-математическом факультете.

 

Здорово!

[GDV 9787]

Да чего там здорового, коли большую часть времени я проводил в аудиториях с компами . Общался с железными мышами, Ямахами MSX и Искрами.

На матан, правда, ходил. Уж очень он у меня трудно шел.

[Ignat 0]

Искру я только видел ( дома по ней даже учебник остался), на ямахах в школе учились,

а еще помню были БК0010. А вот о железных мышах я даже не слышал.