Банички

[MitkoS]

Баничарница. Баничките са по 1 лев.
Започва работния ден. Касата е празна е продавачката няма никакви пари за да връща ресто.
Наредила се е опашка от 20 пенсионера и всеки от тях иска да купи точно една баничка.
Знае се, че 10 от тях имат монета от 1лв, а другите 10 имат банкнота от 2лв.
Но не се знае тяхната точна подредба в опашката.

Каква е вероятността продавачката да се разплати с всички клиенти безпроблемно (да може да връща ресто когато и дадат банкнота от 2лв) ?

ПП. Леко редактирах текста с цел да е по-ясно какво се търси.

[MitkoS]

Мина доста време от публикуването на задачата, да напиша нещо като подсказка, а ?

Текста на задачата подвежда, че става въпрос за суха математика. Всъщност може и да може с някакви формули от математиката (вероятности) да има някакво решение наготово.

Обаче задачата допуска поне едно решение, при което на преден план са прости разсъждения и малко логика как точно да преброим броя на подредбите в опашката, при които продавачката може да върне ресто на всички с 2лв (когато дойде техния ред) - да ги наречем "безпроблемни нареждания".
А пък сухата част и готовите формули да ползваме единствено за общия брой възможни нареждания на опашката, който ако не бъркам нещо, е:
20!/(10!.(20-10)!) = 184756

Та така, с разсъждения и логика търсим броя на "безпроблемните нареждания", а пък после вероятността ще я изчислим така:
вероятност = (брой на "безпроблемните нареждания") / (общия брой възможни нареждания на опашката)
т.е.
вероятност = (брой на "безпроблемните нареждания") / 184756

[tonych]

22596 са добрите подреждания... според мен
може и да съм се отклонил с няколко( надявам се не с много),по късно ще проверя още веднъж

[MitkoS]

22596 са добрите подреждания... според мен
може и да съм се отклонил с няколко( надявам се не с много),по късно ще проверя още веднъж

Ами според мен си объркал сметката. Ако искаш напиши как стигаш до тази цифра да търсим грешката заедно (може пък и аз да бъркам в сметката).

Нещо не върви тая задача
Дали да не променим условието така:
- Да намалим броя на хората в опашката на 10 (5 с по 1лв и 5 с 2лв).
- Също така, да забраним операцията "умножение" и да оставим само операцията "събиране".

Подсказка:
Забраняваме умножението и при изчислението на общия брой възможни нареждания на опашката.

ПП. "Задача 79" много прилича на тая, ама не е същата

ПП2. На който му е по-добно, нека да си кара по първоначалното условие. Далеч съм от мисълта, че тая задача може да се реши само по един начин.

[tonych]

ще внеса известна корекция... този път факториелите ги смятах на калкулатора на уина не на ръка
а ето и идеята ми:
12 две възможни комбинации една добра 12 и една не 21 съотношение 50/50 или 1/1 - два пенсионера
1122 шест комбинации две от нашите 1122 ,1212 и четири от неправомерните 2211, 2121,2112,1221 съотношение 2/4 или 1/2 - 4 пенсионера
111222 тук вече не смятам да ги разписвам мисля, че е ясно получава се съотношение 5/15 или 1/3 - 6 пенсионера
11112222 14/56 1/4 - 8
1111122222 42/210 1/5 - 10
111111222222 132/792 1/6 - 12
11111112222222 429/3003 1/7 - 14
1111111122222222 1430/11440 1/8 - 16
111111111222222222 4862/43758 1/9 - 18
11111111112222222222 16796/167960 1/10 - 20 пенсионера с 20 баници

в интерес на истината разписах комбинациите само до 8 надявам се да не съм се подвел

[MitkoS]

tonych,
От три дена се опитвам да докажа твърдението ти чрез индукция и не става и не става. Даже опитах и чрез "дедукция" - приемам го за вярно и по обратен ред си търся грешката в индукцията. Намерих я, но за съжаление е непреодолима. Поне не и за мен.

А самото твърдение (ти си го формулирал по-различно, но иначе е същото), е че при опашка от 2.n човеци, то търсената в условието вероятност е 1/(n+1). Това със сигурност е вярно за n по-малко или равно на 10, защото може да се провери на ръка (направил съм го), но за по-големи n, поне аз не мога да го докажа и твърдя.

Предлагам да я зарежем тая задача, прекалено много аритметика и математика се появиха.
Така както е зададен въпросът в условието, отговорът на задачата е 1/11.
Обещавам по някое време да напиша как става "само със събиране".

А да ! И още нещо към tonych - прието е под "вероятност" да се разбира отношението на "сполучливите изходи" спрямо общия брой изходи, а не както ти го разглеждаш "сполучливи"/"несполучливи".

[tonych]

вземам си бележка
мисля, че не оставам неразбран

[MitkoS]

Мина доста време, да кажа набързо, как става "само със събиране".
Много прилича на "Задача 79", но допълнително се вмъква и броене.

Имаме таблица 11х11
В началното положение сме в най-долния ляв ъгъл.
Като дойде купувач с 1 лев, се придвижваме една позиция нагоре, а като дойде такъв с 2 лева, се придвижваме една позиция надясно.
Независимо от реда на купувачите, винаги стигаме в горния десен ъгъл на таблицата, като според конретната наредба на купувачите нашето придвижване в таблицата описва някакъв път.
Дотук всичко е като в "Задача 79".

За да намерим търсената вероятност, трябва да успеем да преброим всичките възможни пътища в таблицата, които не "падат" под диагонала (ако падне, значи до момента са дошли повече купувачи с 2 лв, откоркото са минали с 1 лв). Тия пътища ще ги нарека "безпроблемните".

Нека за момент си представим, че във всяка клетка по диагонала и над диагонала е записан броя на безпроблемните пътища по които може да се стигне до тая клетка.

Сега трябва да съобразим следните три неща:

1. Очевидно, в най-лявата колона е записано числото 1, защото до всяка клетка в тази колона може да се стигне по един единствен път (т.е., идвали са само купувачи с 1 лев). В тая конкретна колона, всичките пътища са безпроблемни така или иначе. А какво ще запишем в най-долната клетка на тая колона е въпрос на дефиниция. На мен ми изглежда най-естествено там да запишем 0, а не 1.

2. В клетките по диагонала пише същото което пише в клетка отляво до тях (с изключение на най-долната лява където вече приех, че ще е 0). Защо ? Защото търсим само безпроблемните пътища, а те "идват" отляво. Ако дойдат отдолу, значи не са безпроблемни.

3. В клетките които са над диагонала и не са в най-лявата колона трябва да пише сумата на клетката отляво и клетката отдолу (това по принцип са всичките пътища до тая клетка - или ще се "дойде" в тая клетка отдолу, или ще е от ляво).

Тия съображения от 1 до 3, ни дават простичък алгоритъм, чрез който на ръка можем набързо да пресметнем броя на безпроблемните пътища за клетките над диагонала в таблицата. Започваме отдолу и отляво и клетка по клетка сумираме.
При таблица 11х11 и само със събиране за около 5 минути стигаме до най-горния десен ъгъл на таблицата и на практика сме изчислили общия брой безпроблемни пътища, което всъщност ни трябва.

ПП 1.
Най-важното е съображение 2. То ни гарантира че през цялото време броим само безпроблемните пътища.

ПП 2.
В Задача 79 се "движим" по решетката, а тук по клетките - все тая, реших да е по клетките, защото е по-прегледно (според мен) да пишем цифрите вътре в клетките, е не по рамката. И затова табличката е 11х11 а не 10х10.
А също така, там решетката е завъртяна на 45 градуса, но това няма никакво значение - просто на мен ми е по-лесно да описвам алгоритъма за "права" таблица, отколкото за завъртяна решетка.

ПП 3.
Хе-хе, никой не забеляза грубата грешка в Съображение 1.
Поправих я вече, не я търсете.

А също така, направих и картинка