предполжим студ. группа состоит из N человек. Им необходимо посчитать средний балл группы, при этом не один человек из группы не хочет называть свой средний балл никому. Как группе посчитать свой средний балл на словах(те без использования ручек и бумажек)?
За ответ на этот вопрос давали блокнот. Я получил, но мой вариант решения не самый простой. Кто может предложить свой?
Свой я напишу чуть позже!
Был еще второй вопрос: в очереди за пачкой фломастероы стоимостью 50 руб стоит 100 человек. У 50 человек купюра в 50 руб. У 50 человек купюра в 100 руб. Всем необходимо купить фломастеры. Какова вероятность того, что продавец сможет дать сдачу всем покупателям?
Ответ 100 % не прошел — Он может отдать сдачу всем кому дожен после того как все купят фломастеры не катят, т.к. Отдавать сдачу он должен сразу после покупки.
первая задача решается элементарно :)
1. выбираем одного ведущего (не обязательно среди студентов)
2. Ведущий загадывает случайное число в уме (достаточно большое, сравнимое со обычным средним баллом * N) и говорит его первому студенту 'на ушко'
3. Каждый последующий студент прибавляет к этому числу свой балл и сообщает результат другому
…
4. по окончании последний студент так же шопотом говорит свою сумму ведущему
5. ведущий вычитает свое число из результата и делит его на N
т.е. никто не видит всей картины, а значит никаких вычислений провести не сможет (даже если кто то услышит случайно чью-то сумму, это ничего не даст).
т.е. никто не видит всей картины, а значит никаких вычислений провести не сможет (даже если кто то услышит случайно чью-то сумму, это ничего не даст).
почему же? если тот кому вы сказали своё число услышал то число которое сказали вам, то простая разница и будет вашим средним баллом.
ну а так да, я думаю верное решение именно это.
у меня еще были мысли про хеш-функцию, которая «накапливает» результат, но ничего внятного не придумалось.
Ну, по первой задаче, если понимать ее буквально, то достаточно показать столько пальцев рук, сколько у тебя баллов ))
Таким образом бал НАЗВАН не будет
А во втором случае — и если есть возможность сговора, то задача неразрешима.
Предположим такой алгоритм существовал бы. Тогда все участники группы кроме одного, после вычисления среднего балла могли бы сговориться, и вычислить по этому же алгоритму также и свой средний балл. Зная общий средний балл, и средний балл группы без одного человека — можно вычислить средний балл этого одного человека.
Это классика, фактически, нам необходимо составить правильный набор скобок (открывающих — "+50руб", и закрывающих — "-50руб").
И число вариантов будет равно числу Каталана для n = 50.
Численно это считается как 100!/(50!*51!).
Это удачные случаи, всего будет — C(100, 50) = 100! / (50!)^2.
Ответ — 1/51
Почему изначально берется значения Каталана для n=50? 50 скобок, в нашем случае полтиников?
Удачные случаи: 100! — количество всевозможных расстановок 100 чисел?
C(100, 50) = 100! / (50!)^2 — это что за формула?
В остальном вроде все ясно!
скобок 100.
Cn — для 2n скобок, значит n = 50.
> это что за формула?
Количество возможных расстановок очереди.
Есть 100 человек, нужно выбрать 50 из них, которые со 100 рублями, это число сочетаний с n = 100, k = 50.
Берется лист бумаги и все по очереди пишут свои баллы по предметам. То есть если, 5 человек и 5 предметов, то на листке в произвольном порядке будет 25 чисел. потом по ним считаем средний балл.
Правда бумагу использоавть нельзя. Но можно эти числа называть остальным участникам в разрозненном порядке.
Т.е. назвал все оценки по всем предметам разным людям из группы. Так делают и все. Можно и на ушко говорить.
Потом все числа складывают делят на K предметов и N человек
По второй — правильных вариантов очереди будет столько же, сколько правильных скобочных последовательностей, а именно fib(50) (где fib(1) = 1, fib(2) = 2, fib(i) = fib(i-1) + fib(i-2)).
Доказывается по индукции.
Всего вариантов очереди — число сочетаний, 100! / (50!)^2.
Ответ — fib(50) / 100! * (50!)^2
В числах получается что-то очень маленькое, типа 2e-19
Средний
Простой
