Задачки-2

sha · Post by **sha** » 23 Mar 2001 02:21

<BLOCKQUOTE>quote:<HR>Originally posted by DV:
[i:2234c00166]
Вероятность поломать длинный кусок спички в этом случае уже не 1/2. Новая задача, однако.[/i:2234c00166]<HR></BLOCKQUOTE>

Кстати, а чем такая постановка задачи (когда просто выбираем две точки на отрезке), отличается от первой (когда ломаем один раз, а потом произвольно ломаем второй раз)?

COPOKA · Post by **COPOKA** » 23 Mar 2001 04:11

Originally posted by sha:
А как насчет ассоциативного мышления?
Надо продолжить последовательность
24, 81, 63, 26, 41, 28,... <BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[i:65cbd597b4]25[/i:65cbd597b4]<HR></BLOCKQUOTE>
А потом - 65, да? Cute! [img:65cbd597b4]images/smiles/icon_smile.gif[/img:65cbd597b4]

А мою задачку про пиратов тоже никто дорешивать не хочет... Скучна пиратская психология [img:65cbd597b4]images/smiles/icon_sad.gif[/img:65cbd597b4]

sha · Post by **sha** » 23 Mar 2001 04:42

<BLOCKQUOTE>quote:<HR>Originally posted by tengiz:
[i:6a740c04e2]Moleg,

Sha,

Я не знал и не сейчас не знаю, судя по Вашей реакции на ответ Zaphod, без подсказки вряд ли узнаю [img:6a740c04e2]images/smiles/icon_razz.gif[/img:6a740c04e2].

Вот Вам за это такая же «глухая» задача о продолжении последовательности:

11, 21, 1211, 111221, 312211, 13112221, ...

[ 22-03-2001: Message edited by: tengiz ][/i:6a740c04e2]<HR></BLOCKQUOTE>

Ну во-первых вы пропустили первое число [img:6a740c04e2]images/smiles/icon_smile.gif[/img:6a740c04e2], т.е. последовательность вообще-то начинается с 1: 1, 11, 21, 1211,

вот [img:6a740c04e2]images/smiles/icon_smile.gif[/img:6a740c04e2], ну а следующее:

1113213211

mmg · Post by **mmg** » 23 Mar 2001 04:59

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[i:e20fe3e5a4]Что называется, "обычная задача". Изюминки что-то не видать. Или есть?[/i:e20fe3e5a4]<HR></BLOCKQUOTE>

Прошу прощения, на самом деле, это была провокация с моей стороны, поскольку я ее решить не могу. И никто не мог, по крайней мере до начала 90-х. Сейчас может уже и решили, я специально не следил. Это довольно известная математическая проблема, обычно называемая the 3x+1 problem [img:e20fe3e5a4]images/smiles/icon_smile.gif[/img:e20fe3e5a4]

saner · Post by **saner** » 23 Mar 2001 05:04

<BLOCKQUOTE>quote:<HR>Originally posted by COPOKA:
[i:94c65da502]Originally posted by sha:
А как насчет ассоциативного мышления?
Надо продолжить последовательность
24, 81, 63, 26, 41, 28,...

Originally posted by Zaphod:
25[/i:94c65da502]<HR></BLOCKQUOTE>
А потом - 65, да? Cute! [img:94c65da502]images/smiles/icon_smile.gif[/img:94c65da502]

а потом - 12 [img:94c65da502]images/smiles/icon_smile.gif[/img:94c65da502]

[i:94c65da502]
А мою задачку про пиратов тоже никто дорешивать не хочет... Скучна пиратская психология [img:94c65da502]images/smiles/icon_sad.gif[/img:94c65da502][/i:94c65da502]

при N монетках шанс выжить есть у 2*(N+1) пиратов. нет?

кста - есть еще схожая задачка на индукцию про ученых и их неверных жен [img:94c65da502]images/smiles/icon_smile.gif[/img:94c65da502]

Joker · Post by **Joker** » 23 Mar 2001 05:09

Так. Ну что, любители логарифмов? Созрели для красивого решения?

Итак. Все кусочки спички, как бы мы ее ни ломали, в сумме равны длине спички. Примем ее за единицу и обозначим длины кусочков x, y, z. Имеем ограничение x+y+z=1. Причем x, y, z >0. Это уравнение наклонной плоскости в первом октанте, которая имеет в нем вид треугольника. Нарисуйте сами.

Теперь. Условие образование треугольника — сумма двух сторон должна быть больше третьей. Имеем три условия:
x+y>z
y+z>x
z+x>y
Эти три неравенства выделяют в рассматриваемом треугольнике треугольную же серединку.

Если считать распределение точек вдоль спички равномерным (Внимание! Про парадокс Бертрана не забыли?), то и распределение точек вдоль отрезков (= вдоль осей координат) тоже равномерное, => и распределение точек на плоскости (которая суть линейный объект) тоже равномерное. Отсюда вероятность есть площадь "благоприятного" треугольника, отнесенная к площади всего треугольника.
То есть 1/4.

Для того, чтобы решить второй вариант задачи, достаточно сообразить, что условие второго ломания бОльшей части спички есть просто одно из условий образования треугольника. То есть оно сразу выполнено, по условию. Как и в задачке про второго мальчика, который не девочка [img:f12f83fdd8]images/smiles/icon_biggrin.gif[/img:f12f83fdd8], просто выбрасываем один из малых треугольничков из "пространства событий". Получаем столь же красивый ответ - 1/3.

А теперь самое интересное. Ответ с логарифмами безусловно правилен, я сам его получал сразу же еще N лет назад, и все коллеги, которым я подсовывал эту задачу, тоже приходили к ответу с логарифмами.
Столь же несомненно красиво и правильно описанное мной выше "геометрическое" решение. Ясно, что плоскость и вобще линейные объекты никаких логарифмов дать не могут (как тут уже замечалось). Так какое же решение правильно и в чем ошибка в другом решении? Или это опять парадокс Бертрана?

Самое забавное, что ответ с логарифмами очень близок к ответу 1/4. Я пробовал промоделировать эту задачу на компьютере и так и не добился точности, позволяющей сделать однозначный выюор между ответами. Правда, это было 15 лет назад на "Электронике Д3-28" [img:f12f83fdd8]images/smiles/icon_smile.gif[/img:f12f83fdd8]

DV · Post by DV » 23 Mar 2001 06:16

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:3112864f17]Если считать распределение точек вдоль спички равномерным (Внимание! Про парадокс Бертрана не забыли?), то и распределение точек вдоль отрезков (= вдоль осей координат) тоже равномерное, => и распределение точек на плоскости (которая суть линейный объект) тоже равномерное. [/i:3112864f17]<HR></BLOCKQUOTE>

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:3112864f17]
Есть спичка. Ее произвольным образом ломают на две части, потом одну из оставшихся частей ломают еще раз. Какова вероятность, что из трех полученных обломков можно сложить треугольник?

[/i:3112864f17]<HR></BLOCKQUOTE>

Да, как всё запущено. (c) Zaphod. Извините, но это вам не физика. Здесь десяти решении не бывает. Если сопаставить ваше решение с вашим же условием задачи, я должен с прискорбием констатировать, что ваше решение неверно.

Оно становится верным только если мы добавим в условие задачи после "потом одну из частей ломают еще раз" предложение "вероятность выбора какои-либо части прямо пропорциональна длине этои части". Тогда и только тогда ваше решение "прокатит" (c) Zaphod. Это довольно сильное дополнительное условие. Если оно верно, то должно было быть включено в описание задачи. В описании задачи этого условия не было!

Без этого уточнения, большинство людей, как вы правильно заметили, предполагает, что вероятность выбора какои-либо части для второй порубки равняется 1/2. Тогда решение с логарифмами единственно правильное.

В чем же разница? Представте себе случайное число. С вероятностю 0.5 оно имеет Гауссовское распределение с мат. ожиданием 1, с вероятностю 0.5 оно имеет гауссовское распределение с мат. ожиданием 9. Мат. ожидание етого числа очевидно равно 5. Но распределение етого числа не Гауссовское.

О чем спор вообще? Неужели это приматам на физтехах в России уже не преподают?

[ 22-03-2001: Message edited by: DV ]

DV · Post by DV » 23 Mar 2001 06:26

<BLOCKQUOTE>quote:<HR>Originally posted by sha:
[i:5b59629707]Кстати, а чем такая постановка задачи (когда просто выбираем две точки на отрезке), отличается от первой (когда ломаем один раз, а потом произвольно ломаем второй раз)?[/i:5b59629707]<HR></BLOCKQUOTE>

Я уже попытался ответить на этот вопрос. Коротко, в оригинале задачи, безусловное распределение (unconditional distribution) второй точки неравномерное (not a uniform distribution, it might as well be the case that the unconditional probability distribution function is not well defined for this problem). Извините за английский, термины русские после стольких лет забываются.

Joker · Post by **Joker** » 23 Mar 2001 06:49

<BLOCKQUOTE>quote:<HR>Originally posted by DV:
[i:8949f1a238]Оно становится верным только если мы добавим в условие задачи после "потом одну из частей ломают еще раз" предложение "вероятность выбора какои-либо части прямо пропорциональна длине этои части".[/i:8949f1a238]<HR></BLOCKQUOTE> Алё, алё? Что за бред, господа? Пожалуйста, не надо домысливать условие сверх того, что было сказано. Какая еще вероятность выбора? Вам завязали глаза, вы наугад чиркнули по спичке ножом, потом - так же наугад - чиркнули ножом еще раз, тем самым дополнительно сломав одну из частей. Если Вы поняли задачу как-то по-своему, сорри, но, как мне кажется, все остальные поняли ее правильно [img:8949f1a238]images/smiles/icon_wink.gif[/img:8949f1a238]

Так что да, "вероятность выбора какои-либо части прямо пропорциональна длине этои части", и это, по-моему, следует из условия задачи. Еще раз сорри за то, что эта фраза не была озвучена в явном виде.

P.S. Кстати, аналитическое решение точно так же, как геометрическое, предполагает равномерное распределение точек вдоль спички, иначе вам пришлось бы под интеграл добавлять весовую функцию плотности распределения.

[ 22-03-2001: Message edited by: Joker ]

Joker · Post by **Joker** » 23 Mar 2001 06:59

<BLOCKQUOTE>quote:<HR>Originally posted by sha:
[i:4e339d8e26]Кстати, а чем такая постановка задачи (когда просто выбираем две точки на отрезке), отличается от первой (когда ломаем один раз, а потом произвольно ломаем второй раз)?[/i:4e339d8e26]<HR></BLOCKQUOTE>
Абсолютно ничем не отличается. DV просто понял задачу по-своему. Можете сформулировать так: "Спичку произвольно ломают в двух местах". Я сформулировал так, как сформулировал, чтобы два варианта задачи больше походили друг на друга.

Joker · Post by **Joker** » 23 Mar 2001 07:34

<BLOCKQUOTE>quote:<HR>Originally posted by mmg:
[b:a9a7a192d6]Прошу прощения, на самом деле, это была провокация с моей стороны, поскольку я ее решить не могу. И никто не мог, по крайней мере до начала 90-х. Сейчас может уже и решили, я специально не следил. Это довольно известная математическая проблема, обычно называемая the 3x+1 problem [img:a9a7a192d6]images/smiles/icon_smile.gif[/img:a9a7a192d6][/b:a9a7a192d6]<HR></BLOCKQUOTE>
А вот еще задача. Доказать, что уравнение x^n+y^n=z^n не имеет решений в целых положительных числах при любых натуральных n>2 [img:a9a7a192d6]images/smiles/icon_wink.gif[/img:a9a7a192d6]
Тоже совсем недавно эту задачку решили [img:a9a7a192d6]images/smiles/icon_biggrin.gif[/img:a9a7a192d6]

mmg · Post by **mmg** » 23 Mar 2001 08:29

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[b:94799939d6]А вот еще задача. Доказать, что уравнение x^n+y^n=z^n не имеет решений в целых положительных числах при любых натуральных n>2 [img:94799939d6]images/smiles/icon_wink.gif[/img:94799939d6]
Тоже совсем недавно эту задачку решили [img:94799939d6]images/smiles/icon_biggrin.gif[/img:94799939d6][/b:94799939d6]<HR></BLOCKQUOTE>
Ну,ну, это уж Вы хватили [img:94799939d6]images/smiles/icon_biggrin.gif[/img:94799939d6] Я все-таки надеюсь, что моя задачка попроще. К тому же люди тут умные, вдруг кто и решит. Но на самом деле, мне больше было интересно, узнает ли кто-нибудь условие. Эту задачку всегда любили подсовывать студентам, изучающим теорию алгоритмов. Уж очень она "обычно" выглядит, вот даже Zaphod изюминки не заметил [img:94799939d6]images/smiles/icon_smile.gif[/img:94799939d6] Впрочем, теорема Ферма тоже из этой серии, тут Вы правы.

[ 22-03-2001: Message edited by: mmg ]

moleg · Post by **moleg** » 23 Mar 2001 08:31

Нельзя шутить со спичками!

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

2. Спичка произвольно ломается и часть выбрасывается. Остаток опять ломается и часть выбрасывается. Обломок какой длины останется.

moleg · Post by **moleg** » 23 Mar 2001 08:47

Originally posted by Joker:
[b:5bd048b429]DV просто понял задачу по-своему. Можете сформулировать так: "Спичку произвольно ломают в двух местах". Я сформулировал так, как сформулировал, чтобы два варианта задачи больше походили друг на друга.[/b:5bd048b429]

Разночтения в двух формулировках небольшие, но существенные. В одной события [b:5bd048b429]независимые[/b:5bd048b429] ("красивое" решение), в другой уже нет. Все это зависит от того, какой именно был процесс выбора половинок, как и отмечали многие. Так что парадокса здесь нет, решались разные задачи. И я бы настаивал (кто бы мне дал точку опоры, чтобы настаивать [img:5bd048b429]images/smiles/icon_smile.gif[/img:5bd048b429]), что фраза "потом одну из оставшихся частей ломают еще раз" означает именно, что вероятности выбора одной из частей равны. Вот если бы Вы сказали, что после того, как спичку поломали, ее сложили опять и нанесли "решающий порез", тогда задача потеряла бы свою ... чего то в общем потеряла, но приобрела "красивое" решение.

[ 22-03-2001: Message edited by: moleg ]

obormot · Post by **obormot** » 23 Mar 2001 09:02

<BLOCKQUOTE>quote:<HR>Originally posted by ACL:
[i:d321086bb2]Из пункта А в пункт Б ведут две дороги, так что для два велосипедиста, выехавшие из А в Б по разным дорогам, смогут добраться до Б даже если они связаны веревкой длины 2R.
Вопрос - смогут ли разъехаться два автомобиля радиуса R [img:d321086bb2]images/smiles/icon_smile.gif[/img:d321086bb2], если они выедут навстречу друг другу ?[/i:d321086bb2]<HR></BLOCKQUOTE>

Предположим, что могут. Пусть они себе это делают тогда, но мы посадим пелосипедиста 1 в центр круглой машины радиуса R и отправим его из пункта А в пункт Б по первой дороге вместе с машиной.
Велосипедист 2, привязанный к 1, поедет по второй дороге, и как мы знаем, сможет доехать до пункта Б не отвязавшись (правда скорость 1-го велосипедиста теперь задается машиной в которой он едет, но ясно что можно соответствующим образом подстроить под это скорость 2-го, так что веревка не порвется).
В тот момент когда 2-й велосипедист "встретится" с машиной едущей по 2-й дороге из Б в А (т.е. совпадет с ее центром) мы получим противоречие.

А мои задачки значит никому не нравятся.. [img:d321086bb2]images/smiles/icon_eek.gif[/img:d321086bb2]
Надо про вероятность чего нарыть.. Вообще-то преподавая в свое время в математических кружках для школьников я замечала явную корреляцию между "любовью к програзму" (разделенной) и способностями к решению задачек по геометрии.. но материалистического объяснения сему феномену найдено не было.

ACL · Post by **ACL** » 23 Mar 2001 09:26

<BLOCKQUOTE>quote:<HR>Originally posted by obormot:
[i:e133e14b92] ... правда скорость 1-го велосипедиста теперь задается машиной в которой он едет, но ясно что можно соответствующим образом подстроить под это скорость 2-го, так что веревка не порвется.
[/i:e133e14b92]<HR></BLOCKQUOTE>
Браво!
Классическое решение - По оси X отложим расстояние от первого велосипедиста до пункта А. По оси Y - от второго до А. Тогда их путешествие будет выглядеть как кривая линия от одной вершины квадрата до другой диагонально противоположной. Машины же поедут по кривой соединяющей вторую пару вершин. Эти кривые, очевидно, пересекаются.

omnibee · Post by **omnibee** » 23 Mar 2001 14:37

<BLOCKQUOTE>quote:<HR>Originally posted by COPOKA:
[b:6f09b310ce]Это получается, что если имеется 200+К пиратов, для первых К уже нет никакой надежды выжить?

P.S. Они кровожадные.[/b:6f09b310ce]<HR></BLOCKQUOTE>

Если кровожадность означает, что смерть другого пирата рассматривается как личная выгода, то конечно, выживут только 200 пиратов. Остальные проголосуют против только для того, чтобы их погубить и потом распределить деньги. Но вот если пиратов >=400, тогда никто не умрет, т.к. даже если первые 200 проголосуют "против", остальные 200+ будут голосовать "за" только для того, чтобы выжить.

Распределение, естественно, всегда одно и то же - самым низкоприоритетным по дублону через одного. Остальным - право на жизнь, если повезет [img:6f09b310ce]images/smiles/icon_smile.gif[/img:6f09b310ce]

DV · Post by DV » 23 Mar 2001 19:26

<BLOCKQUOTE>quote:<HR>Originally posted by COPOKA:
[b:f341b425db]Five mathematically gifted pirates, named Angry, Boorish, Crummy, Dirty, and Evil...[/b:f341b425db]<HR></BLOCKQUOTE>

If you don't impose subgame perfection criteria on this game, you obtain an equilibrium in which Angry gets 100% of the money. And you support this outcome by appropriate out-of-equilibrium beliefs for the other 4 pirates.

Дамы и господа, это ведь не физика. Тщательнее формулируите задачки.

Zaphod · Post by **Zaphod** » 23 Mar 2001 19:50

<BLOCKQUOTE>quote:<HR>Originally posted by mmg:
[b:223e8a96e6]Прошу прощения, на самом деле, это была провокация с моей стороны, поскольку я ее решить не могу. И никто не мог, по крайней мере до начала 90-х. Сейчас может уже и решили, я специально не следил. Это довольно известная математическая проблема, обычно называемая the 3x+1 problem [img:223e8a96e6]images/smiles/icon_smile.gif[/img:223e8a96e6][/b:223e8a96e6]<HR></BLOCKQUOTE>

Аяяй, я посмотрел еще раз на свое решение... ошибочка, ошибочка у меня.

Zaphod · Post by **Zaphod** » 23 Mar 2001 20:01

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[b:094c45033b] Можете сформулировать так: "Спичку произвольно ломают в двух местах". Я сформулировал так, как сформулировал, чтобы два варианта задачи больше походили друг на друга.[/b:094c45033b]<HR></BLOCKQUOTE>

Я соглашусь с оппонентами - большая разница, "ломают в двух местах" или "ломают, а потом еще раз ломают". Каков принцип выбора куска, который нужно ломать второй раз? [img:094c45033b]images/smiles/icon_smile.gif[/img:094c45033b]

Zaphod · Post by **Zaphod** » 23 Mar 2001 20:14

<BLOCKQUOTE>quote:<HR>Originally posted by moleg:
[b:d12d154f96]2. Спичка произвольно ломается и часть выбрасывается. Остаток опять ломается и часть выбрасывается. Обломок какой длины останется.[/b:d12d154f96]<HR></BLOCKQUOTE>

1/6 часть суши?

tengiz · Post by **tengiz** » 23 Mar 2001 20:15

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
Я соглашусь с оппонентами - большая разница, "ломают в двух местах" или "ломают, а потом еще раз ломают".<HR></BLOCKQUOTE>Присоединяюсь - это разные задачи.

moleg · Post by **moleg** » 23 Mar 2001 20:21

Originally posted by Zaphod:
[b:27926d2a61]1/6 часть суши?[/b:27926d2a61]

А я не знаю - за тем и спрашивал [img:27926d2a61]images/smiles/icon_wink.gif[/img:27926d2a61]

Кстати, Zaphod, а что это у Вас в "подписи" написано? Видеть-то вижу, а понять не могу [img:27926d2a61]images/smiles/icon_rolleyes.gif[/img:27926d2a61]

DV · Post by DV » 23 Mar 2001 21:23

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[b:a10cd52793]

Originally posted by sha:
[i:a10cd52793]Кстати, а чем такая постановка задачи (когда просто выбираем две точки на отрезке), отличается от первой (когда ломаем один раз, а потом произвольно ломаем второй раз)?[/i:a10cd52793]<HR></BLOCKQUOTE>
Абсолютно ничем не отличается. DV просто понял задачу по-своему. Можете сформулировать так: "Спичку произвольно ломают в двух местах". Я сформулировал так, как сформулировал, чтобы два варианта задачи больше походили друг на друга.[/b:a10cd52793]

Я все же соглашусь с moleg-ом. В первоначальнои формулировке неявно подразумевается 1/2. Ломать это вам не рубить ножом. [img:a10cd52793]images/smiles/icon_smile.gif[/img:a10cd52793] А задача хорошая. Я тут попытался вывести безусловное распределение второй точки в "ломательном" варианте задачи. Оно, конечно, отлично от "рубительного" равномерного распределения, но продраться сквозь формулы до конца терпения не хватило. Может, кто поможет? [img:a10cd52793]images/smiles/icon_smile.gif[/img:a10cd52793]

DV · Post by DV » 23 Mar 2001 21:30

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[b:5eeb2f377d]P.S. Кстати, аналитическое решение точно так же, как геометрическое, предполагает равномерное распределение точек вдоль спички, иначе вам пришлось бы под интеграл добавлять весовую функцию плотности распределения.

[ 22-03-2001: Message edited by: Joker ][/b:5eeb2f377d]<HR></BLOCKQUOTE>

В "ломательном" варианте условное распределение - равномерное. Безусловное распределение (unconditional distribution)- все-таки не равномерное.