Составитель Борис Демешев
 Скачать 1.58 Mb.
|
|
Верно ли, что можно так вписать куб, что все его вершины будут одноцветными? Задача 11.4. Пусть 𝐴 - произвольная матрица. Докажите, что существует вектор 𝑣 состоящий из единиц или минус единиц, такой что 𝑣𝐴𝑣 𝑡 ≥ 𝑡𝑟(𝐴) Source: Задача 𝑆 be a finite set of points in the plane such that no three of them are on a line. For each convex polygon 𝑃 whose vertices are in 𝑆, let 𝑎(𝑃 ) be the number of vertices of 𝑃 , and let 𝑏(𝑃 ) be the number of points of 𝑆 which are outside 𝑃 . Prove that for every real number 𝑥: ∑︀ 𝑃 𝑥 𝑎(𝑃 ) (1 − 𝑥) 𝑏(𝑃 ) = 1 , where the sum is taken over all convex polygons with vertices in 𝑆. Remark. A line segment, a point, and the empty set are considered as convex polygons of 2, 1, and 0 vertices Задача ТВИМС-задачник. Демешев Борис. roah@yandex.ru 57 Erdos-Ko-Rado theorem [ Alon, Spencer, Probabilistic нуждается в обработке.........] Если: Ω = {0, 1, ..., 𝑛 − 1}. И ℋ - набор пересекающихся подмножеств Ω, состоящих из 𝑘 ≤ элементов, те, если 𝐴 ∈ ℋ и 𝐵 ∈ ℋ, то 𝐴 ∩ 𝐵 ̸= То число элементов #ℋ ≤ 𝐶 𝑘−1 𝑛−1 Доказательство: а) Пусть 𝐴 𝑠 - множество из 𝑘 чисел подряд, начиная с числа 𝑠 (при необходимости, счет продолжается с нуля. Сколько множеств может входить в б) Пусть 𝜎 - случайная перестановка, и 𝑖 случайный номер. Найдите 𝑃 (𝐴 ∈ в) Завершите док-во Задача 11.7. Turan’s theorem [Grimmett, Пусть 𝐺 - конечный граф без петель и двойных ребер. Обозначим 𝑑 𝑘 - число ребер, исходящих из вершины 𝑘 (степень вершины. На графе можно отметить несколько вершин так, чтобы ни одна из них не была напрямую связана с другой. Докажите, что максимальное количество таких вершин Задача idea of Sasha В копилке 40 золотых и 60 серебряных монета) Какова вероятность того, что при выборе 20 монет ровно 𝑖 окажутся серебряными? б) Чему равна сумма этих вероятностей (𝑖 = в) Предложите вероятностное доказательство формулы ∑︀ 𝑖 𝐶 𝑖 𝑎 𝐶 𝑛−𝑖 𝑏 = 𝐶 𝑛 𝑎+𝑏 Задача 11.9. Со стола упало 10 чашек. Каждая разбивается с вероятностью а) Какова вероятность, что разобьется ровно 𝑘 чашек? б) Предложите вероятностное доказательство формулы ∑︀ 𝑖 𝐶 𝑖 𝑛 = Задача a square of side 1, you have been able to capture 51 ants, who are possibly panicking. You have a glass, whose radius is 1/7. Show that you can at any moment position the glass so as to encompass at least 4 of them. Задача 11.11. Пусть 𝑝 𝑛,𝑘 - число перестановок из 𝑛 элементов, оставляющих на месте 𝑘 элементов. Найдите Оптимизация, Теория игр Задача 12.1. Есть две пустые урны, 50 белых и 50 черных шаров. Сначала наугад выбирается одна из урн, затем из нее выбирается один шар наугад. Как следует разложить шары по урнам (в каждой урне должен лежать хотя бы один шар, чтобы вероятность вытащить белый шар была максимальной? Задача 12.2. [ Mosteller] Чтобы подбодрить сына, делающего успехи в игре в теннис, отец обещает ему приз, если он выиграет подряд по крайней мере две теннисные партии против своего отца и клубного чемпиона по одной из схем отец - чемпион - отец или чемпион - отец - чемпион по выбору сына. Чемпион играет лучше отца. Какую схему следует выбрать сыну? Задача 12.3. [ Mosteller] Выборка с возврашением или без возвращения? Две урны содержат красные и черные шары, неразличимые на ощупь. Урна А содержит 2 красных и 1 черный шар, урна В красный и 100 черных шаров. Наудачу выбирается одна из урн, ивы получаете награду, если правильно называете урну после вытаскивания двух шаров из нее. После ТВИМС-задачник. Демешев Борис. вытаскивания первого шара и определения его цвета вы решаете, вернуть ли в урну этот шар перед вторым вытаскиванием. Какой должна быть ваша стратегия? Задача 12.4. There are n different pairs of sox in a drawer. One sock is taken out at a time until a matching pair has been found. a) If n is known what is the most likely value of r, the number of sox drawn out? b) If r is known what value of n gives the greatest chance of this happening? Ugly answers? Задача 12.5. Четыре шкатулки Имеется 4 внешне одинаковых шкатулки. Внутри каждой шкатулки написан ее номер. Внутри шкатулки номер 4 также лежит 1 млн. рублей. Выиграете в следующую игру: Вы выбираете шкатулки одну за одной. После выбора шкатулки, Вы можете либо забрать ее, либо продолжить игру. Игра заканчивается в тот момент, когда Вы решаете забрать шкатулку или когда оказывается, что номер внутри выбранной только что шкатулки меньше, чем номер внутри предыдущей шкатулки. Номера внутри шкатулки определяет ведущий, Вы жене знаете содержимого шкатулок. Вашем выигрышем является содержимое последней выбранной шкатулки. Какова оптимальная стратегия? Каков ожидаемый выигрыш при оптимальной стратегии www.wilmott.com-forum-brainteasers Задача 12.6. Пусть 𝐴 - корреляционная матрица. Чему равен наибольший возможный определитель Задача hard] I am trying to find someone whom I know is in a 5-story building, say a bookstore, and based on what I know about her, the probabilities of finding her on each floor are: 5th: 15% 4th: 40% 3rd: 10% 2nd:30% 1st: 5% I start from the 1st floor, and it takes me 1 minute to take an escalator up or down to an adjacent floor, and 5 minutes to completely search a floor, after which I will either have found her and we can leave, or I will know she is not on that floor. Of course, I can stop and search the floors in any order, so the time I spend searching does not have to follow in adjacent floors, but I can only travel between adjacent floors. Assuming she stays where she is, in which order should I search the floors to minimize my expected time until finding Задача, 2.7.16. Transitive Есть три неправильные монетки (𝐴, 𝐵, 𝐶), выпадающие с вероятностью 3/5 на орла. Игроки по очереди выбирают себе монетку. Затем подкидывают. У кого больше очков, тот и выиграл. Очки считаются так: монетка 𝐴 - 10 очков за решку и 2 очка за «орла» монетка 𝐵 - 4 очка за решку и 4 очка за «орла» монетка 𝐶 - 3 очков за решку и 20 очков за «орла» У какого игрока больше шансов выиграть в этой игре, если каждый игрок максимизирует вероятность выигрыша? Задача 12.9. If X, Y, and Z are 3 random variables such that X and Y are 90% correlated, and Y and Z are 80% ТВИМС-задачник. Демешев Борис. roah@yandex.ru 59 correlated, what is the minimum correlation that X and Z can have? Задача 12.10. Имеется дерево (граф) с 2006 ребрами. Аи В - это две вершины этого дерева. Мы движемся случайным образом от А кВ не поворачивая назад. На каждой развилке мы выбираем равновероятно каждое из возможных ребер. а) При какой форме графа и при каком выборе точек Аи В вероятность попасть из А в В будет минимальной? б) Чему будет равна эта вероятность? Задача 12.11. Есть три рулетки на первой равновероятно выпадают числа 2, 4 и 9; на второй - 1, 6 и 8; на третьей- 3, 5 и 7. Сначала первый игрок выбирает рулетку себе, затем второй игрок выбирает рулетку себе. После этого рулетки запускаются, и выигрывает тот, чья рулетка покажет большее число. Каким игроком лучше быть в этой игре Почему? Задача 12.12. Вы хотите приобрести некую фирму. Стоимость фирмы для ее нынешних владельцев - случайная величина, равномерно распределенная на отрезке [0;1]. Вы предлагаете владельцам продать ее за называемую Вами сумму. Владельцы либо соглашаются, либо нет. Если владельцы согласны, то Выплатите обещанную сумму и получаете фирму. Когда фирма переходит в Ваши руки, ее стоимость сразу возрастает на а) Чему равен Ваш ожидаемый выигрыш, если Вы предлагаете цену б) Какова оптимальная предлагаемая цена? Задача 12.13. Дама пик Устав от вереницы женихов, разборчивая невеста уединилась. Передней колода из 36 карт, хорошо перемешанная. На этот раз принцесса должна предсказать появление дамы пик. То есть принцесса открывает одну за одной карты из колоды ив любой момент может остановиться и сделать заявление Следующая карта будет дама пик. Если это окажется правдой, то принцесса выиграла. Оптимальная стратегия? Задача 12.14. Пьяный водитель На шоссе подряд идут два поворота. Внешне повороты неотличимы друг от друга. Будучи слегка «навеселе» Вася возвращается домой. Васе нужен второй по счету поворотно из-за своего состояния он не может определить, какой по счету поворот он проезжает. Поэтому он поворачивает с вероятностью 𝑝, ас вероятностью 𝑞 = 1 − 𝑝 едет прямо на каждом повороте. Если Вася повернет на первом повороте, то заедет в соседнюю деревню и получит полезность 2. Если он свернет на втором повороте, то получит полезность 5. Если Вася проедет оба поворота, то получит полезность Найдите оптимальное 𝑝. Задача 12.15. Ящик сносками В ящике лежат красные и черные носки. Если из ящика наудачу вытягиваются два носка, то вероятность того, что оба они красные, равна а) Каково минимальное возможное число носков в ящике? б) Каково минимально возможное число носков в ящике, если число черных носков четно? Задача 12.16. Mechanism Поп нанял Балду, чтобы тот предсказывал ему погоду. Дождь идет с вероятностью 𝑝. Благодаря народным приметам Балда точно знает 𝑝 накануне вечером. Балда выдает Попу свою оценку вероятности дождя завтра. а) Как будет вести себя Балда, если Поп выплачивает ему награждение по принципу если дождь действительно был, то выплачивается ˆ𝑝, если дождя не было, то 1 − б) Поп решил заставить Балду выдавать точные оценки. В случае дождя Поп платит 𝑓(ˆ𝑝), и 𝑓(1− ˆ𝑝) ТВИМС-задачник. Демешев Борис. в случае сухой погоды. Какую 𝑓 следует выбрать Попу? в)??? Подсказка: при решении задачи Поп столкнется со странным дифференциальным уравнением, у которого много решений, но 9-ти классов церковно-приходской школы ему вполне должно хватить... Коммент: в условии задачи опечатка - в ЦПХ было 4 класса. Хотя кто знает, когда там проходили диф. уры? Задача 12.17. Поиск функции плотности Два спортсмена готовятся к соревнованиям. Каждый из них выбирает свой уровень усилий 𝑒 𝑖 ∈ [0; 1] . Побеждает тот, кто приложил больше усилий при подготовке. Если оба приложили одинаковое количество усилий, тоне побеждает никто. Победитель получает платеж равный 1. Издержки по приложению усилий равны 𝐶 𝑖 = для каждого игрока. а) Существует ли равновесие по Нэшу в чистых стратегиях? б) Найдите равновесие по Нэшу, в котором уровень усилий каждого игрока имеет функцию плотности, отличную от нуля на [𝑎; 𝑏]. Задача 12.18. Энтропией св. 𝑋 называется число 𝐸 (︁ log 2 1 𝑝(𝑋) )︁, где 𝑝(𝑡) = 𝑃(𝑋 = 𝑡) для дискретных свили- функция плотности для непрерывных с.в. Энтропия измеряет количество информации (в битах, получаемое при наблюдении св. 𝑋. Пусть имеется монетка, выпадающая гербом с вероятностью 𝜃. Св. 𝑋 равна единице, если монетка выпадает гербом, и нулю в противном случае. При каком 𝜃 энтропия будет максимальной? Задача 12.19. Маша и Саша играют в быстрые шахматы. У них одинаковый класс игры и оба предпочитают играть белыми, те. вероятность выигрыша того, кто играет белыми равна 𝑝 > 0, 5. Партии играются до 10 побед. Первую партию Маша играет белыми. Она считает, что в каждой последующей партии белыми должен играть тот, кто выиграл предыдущую партию. Саша считает, что ходить белыми нужно по очереди. При каком варианте правилу Маши больше шансы выиграть? Задача 12.20. О пользе гадания на кофейной гуще замолвите слово. . . Маша пишет на бумажках два любых различных натуральных числа по своему выбору. Одну бумажку она прячет в левую руку, а другую - в правую. Саша выбирает любую Машину руку. Маша показывает число, написанное на выбранной бумажке. Саша высказывает свою догадку о том, открыл ли он большее из двух чисел или меньшее. Если Саша не угадал, то Маша выиграла. Перед выбором руки и высказыванием догадки Саша может обратиться к потомственной гадалке в пятом поколении Глафире Лукитичне (500% гарантия, снятие порчи и сглаза без греха и ущерба для здоровья, исправляет некачественную работу шарлатанов. Глафира Лукитична называет наугад (ничего не зная о Маше) одно из чисел {︀1 1 2 ; 2 1 2 ; 3 1 2 ; с вероятностями соответственно равными {︀ 1 2 ; 1 4 ; 1 8 ; Другими словами, действия Саши (выбор левой или правой руки и высказываемая версия) могут зависеть от слов гадалки. Какую стратегию Саше следует выбрать, чтобы гарантировать себе (вне зависимости от действий Маши) вероятность выигрыша строго более 50%? Задача 12.21. Наш суд - самый гуманный суд в мире! Как известно, истина распределена равномерно на отрезке [0;1]. Истец называет число [0;1] - желаемую компенсацию за моральный ущерб. Одновременно с истцом ответчик называет свою оценку ущерба (на том же отрезке. Суд обязывает ответчика выплатить истцу моральный ущерб в том объеме, который оказался ближе всего к истине. а) Как следует играть истцу и ответчику? б) А если истина распределена нормально 𝑁(0; 1)? Задача 12.22. Маша и Саша came back! ТВИМС-задачник. Демешев Борис. Маша наблюдает реализацию двух независимых случайных величин 𝑋 и 𝑌 , распределенных равномерно на [0; 1]. Она выбирает, значение какой из них рассказать Саше. Саша выигрывает, если угадает, какая из величин наибольшая (та, значение которой он узнал от Маши, или другая. Маша выигрывает, если Саша ошибется. Найдите оптимальные стратегии. Задача 12.23. В мешке лежат бочонки. На каждом из них написана цифра. На одном бочонке написана цифра на двух бочонках - цифра 2,..., на девяти бочонках - цифра 9. Маша вытаскивает один бочонок наугад. Саша не знает, какой бочонок достала Маша. Саша может задавать Маше вопросы, на которые можно отвечать только да или «нет». а) Как выглядит стратегия, минимизирующая ожидаемое число вопросов, необходимых чтобы угадать цифру? б) Как выглядит стратегия, минимизирующая число вопросов, достаточных, чтобы угадать цифру в самом неблагоприятном случае? Задача 12.24. Перед Машей колода в 52 карты. Маша открывает карты одну за одной. Изначально у Маши доллар. Маша может делать любую ставку в пределах имеющейся у нее суммы на цвет следующей карты. Найдите оптимальную стратегию и ожидаемый выигрыш, который приносит эта стратегия. Предположим бесконечную делимость денег. Задача 12.25. [ Mosteller] Выигрыш в небезобидной игре Игра состоит из последовательности партий, в каждой из которых вы или ваш партнер выигрывает очко, вы - с вероятностью 𝑝 (меньшей, чем 1/2), он - с вероятностью 1 − 𝑝. Число игр должно быть четным. Для выигрыша надо набрать больше половины очков. Предположим, что вам известно, что = 0, 45 , ив случае выигрыша вы получаете приз. Если число партий в игре выбирается заранее, то каков будет ваш выбор? Задача 12.26. Разборчиая принцесса-1 К принцессе случайным образом выстроилась очередь из 𝑛 женихов. Цель принцессы - выбрать самого богатого (даже второй по богатству жених королевства не устраивает принцессу. Женихи заходят по очереди. Когда заходит очередной претендент, принцесса узнает его годовой доходи должна либо выбрать его, либо перейти к следующему. Вернуться к предыдущему нельзя. Предполагается, что все варианты расположения женихов по доходу равновероятны. а) Найдите 𝑔 𝑛 - вероятность того, что принцесса выбрала самого богатого жениха, если известно, что она остановилась на 𝑛 -ом претенденте, доход которого был больше, чему предыдущих претенден- тов. б) Обозначим ℎ 𝑛 - вероятность выигрыша принцессы в случае, если она пропускает 𝑛 первых женихова далее играет наилучшую стратегию. Докажите, что не возрастает. в) Как выглядит левее точки 𝑔 𝑛 = г) Составьте разностное уравнение на правее точки 𝑔 𝑛 = д) Найдите Тигр Причем здесь 𝑒? Причем здесь Березовский? Задача 12.27. Разборчиая принцесса-2 Имеется 100 женихов. Доход го жениха равен 𝑋 𝑖 . Величины 𝑋 𝑖 - iid, равномерны на отрезке [0; Женихи заходят по очереди. Когда заходит очередной претендент, принцесса узнает его годовой доходи должна либо выбрать его, либо перейти к следующему. Вернуться к предыдущему нельзя. Принцесса максимизирует ожидаемую полезность. Как выглядит оптимальная стратегия? Задача 12.28. Подбрасываются два различных неправильных кубика. Возможно ли, что вероятность того, что сумма равна 𝑖, 𝑝 𝑖 ∈ (2/33; Возможно ли получение всех чисел от 2 до 12 сделать равновероятным ТВИМС-задачник. Демешев Борис. roah@yandex.ru 62 Source: IMS2007 Задача 12.29. Усама бен Ладен хочет перенести 1000 тротиловых шашек из одной пещеры в другую. При транспортировке каждая шашка взрывается с вероятностью 𝑝. Если взрывается одна шашка, то взрываются и все остальные, перевозимые вместе с ней. Сам Усама при взрыве всегда чудом остается жив. Какими партиями нужно переносить шашки, чтобы минимизировать среднее число переносок? Подсказка: для простоты можно считать, что размер партии не меняется во времени. Вариация?: source: чудо-сканер у Жени Надоршина, по мотивам истории со сканированием Mikosch Задача 12.30. Известно, что случайная величина 𝑋 принимает значения из отрезка [0; а) Найдите наибольшую возможную дисперсию. б) Приведите пример случайной величины, имеющей такую дисперсию aops, 122082 Задача 12.31. Петя с Васей играют в крестики-нолики на поле 3 × 3. Вася начинает игру крестиками. Петя играет в первый рази поэтому ставит нолики случайным образом в свободные клетки, и Васе известно об этом. Какова должна быть стратегия Васи, чтобы вероятность его выигрыша была наибольшей? Чему будет равна эта вероятность? Задача 12.32. Человек хочет купить чудо-пылесос, и конечно, подешевле. Посещение каждого магазина связано с издержками, равными 𝑐 > 0. Цена чудо-пылесоса в каждом магазине имеет равномерное распределение на отрезке [0; 𝑀]. Предположим также, что если человек решит вернуться в уже посещенный магазин, то цена там уже могла измениться, и поэтому уже посещенный магазин можно рассматривать как новый. Магазинов, где продается чудо-пылесос, бесконечно много) Как выглядит оптимальная стратегия? |