задачки

[avva]

Три задачки с простыми условиями. Первая совсем простая, вторая сложнее, третья ещё сложнее (так мне кажется, по крайней мере).

1. На светофоре у перекрёстка горит 30 секунд зелёный свет, потом 30 сек. красный, потом опять 30 сек. зелёный и так далее. Сколько времени в среднем теряет водитель у перекрёстка?

2. Придумать эксперимент с "честной" монеткой (т.е. вероятности выпадения орла и решки равны 1/2), такой, что вероятность успеха эксперимента равна 1/3.

3. Дана некая ограниченная в своих размерах область на плоскости (т.е. некоторая часть плоскости, полностью влезающая в квадрат какого-то, возможно очень большого, размера). Доказать, что существует точка, так что никакая прямая сквозь эту точку не отсекает ровно 1/3 данной области.

Comments

[igorlord.livejournal.com]

1. 7.5

2. Кидаешь монетки 2 раза. Если оба раза Решка -- повторяешь всё с начала. "Успех" -- Если выпал Орел и Орел.

Re:

[avva.livejournal.com]

1. Одного ответа недостаточно, нужно обоснование.
2. Неверно.

[maq.livejournal.com]

3. Как то есть, существует? Не существует такой.

Re:

[avva.livejournal.com]

Так-таки не существует? Ну вот возьмите для примера круг и проведите прямую через его центр, которая отсекает 1/3 круга :)

[ex-ilyavinar899.livejournal.com]

2. Бросить монету 2 раза. 00 - успех, 01 - неудача, 10 - неудача, 11 - повторить эксперимент.

[avva.livejournal.com]

Да, принимается.

[igorlord.livejournal.com]

3. Серидина "квадрата". Любая прямая всегда отсеекает 1/2 -- всегда "половинки" будут иметь симетрию про вращени на 180 градусов.

[avva.livejournal.com]

Нужно не пример дать, а доказать, что для любой области существует такая точка.

[tor85.livejournal.com]

1. 7,5 сеунд?
3. А точка принадлежит плоскости?

Re:

[avva.livejournal.com]

1. Да.
3. Да.

[(Anonymous)]

3. Пусть наша плоскость имеет "вес", равномерно распределённый по ней. Найдем точку "центра тяжести" области, любая прямая проходящая через эту точку делит область на 2 равных по "весу" и, следовательно, по площади части.

[avva.livejournal.com]

Найдем точку "центра тяжести" области, любая прямая проходящая через эту точку делит область на 2 равных по "весу"

Популярное заблуждение.

Возьмите для примера равносторонний треугольник ABC, у которого длина стороны равна AB=AC=BC=2. Его площадь равна sqrt(3)/4 * (AB^2)=sqrt(3).

Из соображений симметрии центром тяжести может быть только центр треугольника.

Теперь проведите сквозь него прямую, параллельную одной из сторон. Она отсечёт меньший равносторонний треугольник - какого размера? Обозначим: центр O, центр стороны AC - M, и мы проводим прямую сквозь O, параллельную AC. Тогда мы отсекаем треугольник, высота которого будет BO; найдём эту высоту и через неё сторону и площадь.

Длина высоты исходного треугольника BM равна sqrt(3)*AC/2 = sqrt(3) (ведь это высота, т.е. произведение её на сторону равно двойной площади). Треугольник AMO прямой, угол MAO - половина CAB, т.е. 30 градусов. Значит, отношение AM/AO равно cos(30 градусов) = sqrt(3)/2. AM=1, потому что M делит AC пополам. Отсюда AO=2/sqrt(3), и тому же равняется BO, которая является высотой в отсечённом меньшем треугольнике. Тогда сторона отсечённого меньшего треугольника равна AO*(2/sqrt(3)) = 4/3. Отсюда его площадь равна sqrt(3)/4 * (4/3)^2 = 4sqrt(3)/9, т.е. ровно 4/9 от площади первоначального треугольника, а вовсе не половина.

[chio.livejournal.com]

1. 15 сек...
2. бросание монетки на ограниченную площадь, поделеную в отношении 1:3 (можно бросать любой предмет, не только монетку...)
:)
3. ... ой...

[drw.livejournal.com]

бросание монетки на ограниченную площадь, поделеную в отношении 1:3

«Я отдам вам барометр, если вы скажете мне высоту этого дома», ага. :-)

[(Anonymous)]

При любом эксперименте, в котором рассматривается _только_ идеальная монета вероятность 1/pi невозможна. Действительно, как число разнообразных исходов так и число бросков - целые числа, и любая их комбинация - рационально число.

[avva.livejournal.com]

Даже в случае 1/3 невозможно обойтись конечным количеством бросков, т.к. тогда вероятность успеха обязательно будет числом вида k/2^n.
Так что можно в эксперименте использовать неограниченно длинные последовательности бросков, главное, чтобы с вероятностью 1 мы закончили за конечное кол-во бросков.

[malaya-zemlya.livejournal.com]

2. Радикальное решение: Взять квадрат , разделить его на две части размером 1/3 и 2/3 (или 1/пи и 1-1/пи). Кинуть монетку. Если центр монетки оказался в первой части, то успех.
Менее радикальное: кидать монетку и записывать результаты кидания как последовательные цифры двоичного разложения некоторого числа х. Если в результате получится число заведомо меньшее или большее 1/3 (что должно произойти за конечное число испытаний с вероятностью 1), то объявить соответственно об успехе или неудаче. Фактически получается арифметическое кодирование.

[ex-ilyavinar899.livejournal.com]

Да, у нас с igorlord такое же решение.

Re:

[avva.livejournal.com]

2. Радикальное решение: Взять квадрат , разделить его на две части размером 1/3 и 2/3 (или 1/пи и 1-1/пи). Кинуть монетку. Если центр монетки оказался в первой части, то успех.

Будем считать это неразрешённым решением (разрешается только смотреть на исход выпадения монетки, т.е. орёл или решка).

Менее радикальное: кидать монетку и записывать результаты кидания как последовательные цифры двоичного разложения некоторого числа х. Если в результате получится число заведомо меньшее или большее 1/3 (что должно произойти за конечное число испытаний с вероятностью 1), то объявить соответственно об успехе или неудаче. Фактически получается арифметическое кодирование.

Да, это работает. Только искомая вероятность - это ак раз Ваша "неудача" получается.

[v-b.livejournal.com]

а, кстати, под условие третьей задачи подпадает и пустое множество, которое как ни дели получится 0 и 0, а 0 -- это, как ни обидно, ровно 1/3 нуля :(

Re:

[avva.livejournal.com]

Ммда... хорошо, давайте постулируем ненулевую площадь исходного множества ;)

[mi-b.livejournal.com]

Задачка 3 мне напоминает такую: доказать, что у любого выпоклого многогранника ортогональная проекция произвольной внутренней точки на плоскости граней попадет на внутренность хотя бы одной грани.

С монеткой: предлагаемые решения плохи тем, что не обрываются гарантированно за конечное число испытаний. С пи можно сделать так же: ясно, как можно просто получуть любую вероятность n/2^к. Выбираем последовательность двоичных приближений к 1/пи, устраиваем серию экспериментов для каждого приближения. Тогда для любого эпсилон существует N, такое что за N бросаний мы получим вероятность не дальше эпсилон от 1/пи.

[avva.livejournal.com]

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

Хммммм. Набьём весь многогранник ватой, и только в данной внутренней точке поместим чрезвычайно массивный груз. Искомый результат следует из невозможности существования перпетуум мобиле ;) Так?

[p-k.livejournal.com]

#3:
Покажем, что существуют три прямые, пересекающиеся в одной точке, такие, что в каждом получившемся секторе лежит ровно одна шестая площади.

а) Для любого направления существует прямая, ему параллельная, делящая площадь пополам (ну, понятно...)

б) Пусть такая прямая проведена. Существует прямая, которая вместе с первой делит площадь на части 1/6, 1/3, 1/6 и 1/3 (в таком порядке, при обходе вокруг точки пересечения). Для доказательства сначала возьмем точку вне ограничивающего квадрата, и проведем через нее прямую, делящую одну половину фигуры на 1/6 и 1/3. Вторая половина при этом разделится на 1/2 и 0. Выбрав точку с другой стороны, получим разбиение второй половины на 0 и 1/2. По непрерывности, существует точка, для которой вторая половина разобьется на 1/6 и 1/3.

в) Точно так же, можно провести еще и третью прямую, разбивающую вместе с первой плоскость на части 1/3, 1/6, 1/3 и 1/6. Если бы все три прямые пересеклись в одной точке, то утверждение было бы доказано, но в общем случае прямые высекают треугольник. Давайте будем вращать первую прямую, и вместе с ней все построение. Положение прямых (в естественной топологии) непрерывно зависит от угла (доказательство прямое, но нудное). После поворота направления на 180 градусов, треугольник вывернется наизнанку. Значит, был такой момент, когда он был вырожден - утверждение доказано.

Дальше просто - любая прямая, проходящая через эту точку, оставляет по каждую сторону два целых сектора, в каждом из которых лежит 1/6 площади.

Интересен вопрос о точной верхней грани в этой задаче (очевидно, 1/3 не точно). Сдается мне, что это будет e^-1...

[p-k.livejournal.com]

Не, верхняя грань как раз 1/3 и будет. Более того, грань достигается - возьмем несвязную область, состоящую из трех одинаковых маленьких кругов с центрами в вершинах большого равностороннего треугольника.

Красивая задача.

Можно и мне задачку задать?

[(Anonymous)]

Имеется биллиардный стол прямоугольной формы и один шар. Шар выпускается по биссектрисе из одного из углов и бесконечно отражается от бортов. Угол падения равен углу отражения. Существует ли общее решение, каково должно быть соотношение длин бортов, чтобы:
1. Шар вернулся в исходную точку
2. Шар катался по замкнутому маршруту (траектория образует симметричный орнамент)
3. Шар катался по незамкнутому маршруту (то есть побывал бы в каждой точке стола)

К сожалению, я не знаю решения этой задачи. Предположительно, если соотношение бортов иррациональное число, то маршрут не замкнут. Но не уверен.

[semenych.livejournal.com]

По поводу второй задачи - есть замечательная статья Кнута и Яо (по-моему так) о моделировании одного дискретного распределения другим. Мой знакомый делал свой мастер именно по этой теме и доказал там интересный результат - количество испытаний будет ограничено отношением энтропии одного распределения к энтропии другого. Если интересно я поищу ссылки.