Задачки-2

sha · Post by **sha** » 21 Mar 2001 22:30

<BLOCKQUOTE>quote:<HR>Originally posted by tengiz:
[i:4bdadb5fc2]Спички:

ln(2)/4 и ln(2)/2

[ 21-03-2001: Message edited by: tengiz ][/i:4bdadb5fc2]<HR></BLOCKQUOTE>

Вот блин... а у меня после длиных математических выкладок получилось 0.25 и 0.5 соответственно [img:4bdadb5fc2]images/smiles/icon_smile.gif[/img:4bdadb5fc2]

tengiz · Post by **tengiz** » 21 Mar 2001 22:58

<BLOCKQUOTE>quote:<HR>Originally posted by sha:
[i:020f4b2894]Вот блин... а у меня после длиных математических выкладок получилось 0.25 и 0.5 соответственно [img:020f4b2894]images/smiles/icon_smile.gif[/img:020f4b2894][/i:020f4b2894]<HR></BLOCKQUOTE>Ну, у меня тоже были другие варианты, скажем такие: 3/8 и 3/4 [img:020f4b2894]images/smiles/icon_razz.gif[/img:020f4b2894]. Однако после некоторого размышления и аккуратных вычислений (не очень длинных) получилось то, что я и выдал: ln(2)/4 и ln(2)/2. Разумеется, я не уверен, что это правильно.

Конечно, можно посмотреть в каком-нибудь учебнике по теории вероятностей, как на самом деле нужно считать вероятность в нашей задаче, но суть-то темы про задачи совсем не в этом, IMHO.

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

<BLOCKQUOTE>quote:<HR>Originally posted by tengiz:
[i:94d6287bfb]

Originally posted by sha:
Вот блин... а у меня после длиных математических выкладок получилось 0.25 и 0.5 соответственно [img:94d6287bfb]images/smiles/icon_smile.gif[/img:94d6287bfb][/i:94d6287bfb]<HR></BLOCKQUOTE>Ну, у меня тоже были другие варианты, скажем такие: 3/8 и 3/4 [img:94d6287bfb]images/smiles/icon_razz.gif[/img:94d6287bfb]. Однако после некоторого размышления и аккуратных вычислений (не очень длинных) получилось то, что я и выдал: ln(2)/4 и ln(2)/2. Разумеется, я не уверен, что это правильно.

Конечно, можно посмотреть в каком-нибудь учебнике по теории вероятностей, как на самом деле нужно считать вероятность в нашей задаче, но суть-то темы про задачи совсем не в этом, IMHO.

Похоже на правду... [img:94d6287bfb]images/smiles/icon_sad.gif[/img:94d6287bfb](( У меня тоже сошлось все именно к этим логарифмам, а не к красивым дробям... А жаль.

ACL · Post by **ACL** » 21 Mar 2001 23:11

Из пункта А в пункт Б ведут две дороги, так что для два велосипедиста, выехавшие из А в Б по разным дорогам, смогут добраться до Б даже если они связаны веревкой длины 2R.
Вопрос - смогут ли разъехаться два автомобиля радиуса R [img:1160ba941d]images/smiles/icon_smile.gif[/img:1160ba941d], если они выедут навстречу друг другу ?

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

А как насчет ассоциативного мышления? [img:5a42d46660]images/smiles/icon_smile.gif[/img:5a42d46660]

Надо продолжить последовательность
24, 81, 63, 26, 41, 28,...

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

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

Нет. [img:daa2afb0a8]images/smiles/icon_smile.gif[/img:daa2afb0a8] Они уткнутся в велосипедистов [img:daa2afb0a8]images/smiles/icon_smile.gif[/img:daa2afb0a8]

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

Еще одна версия ответа про спички:

ln(2)/4 - 1/8, ln(2)/4 - 1/4.

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

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

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

P.S. Вариант. Второй раз ломают не любую, а бОльшую часть спички. Вопрос тот же.[/b:f8ed7e7f7a]

Я получил ответы 2*ln(2)-1 и ln(2)-1/2.

Решение:
<BLOCKQUOTE>code:<HR><pre>
1 0.5
int int (1/a) db da = ln(2)-1/2
0.5 a-0.5
</pre><HR></BLOCKQUOTE>
где a - первая точка и b - точка от 0 до a.
Длины отрезков b; a-b; 1-a откуда
a>0.5; a-b<0.5; b<0.5 - из неравенств.

Аналогично, если b между a и 1.

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

PALbTO · Post by **PALbTO** » 22 Mar 2001 00:43

А кто хочет сыграть со мной в наперстки? Не вздрагивайте, у меня все по-честному… [img:fb390dbe8c]images/smiles/icon_cool.gif[/img:fb390dbe8c]

Итак, есть три наперстка. Под одним горошина, а под другими двумя, как и водится – ничего. [img:fb390dbe8c]images/smiles/icon_wink.gif[/img:fb390dbe8c]
Я естественно знаю, где горошина и предлагаю играющему указать (но не поднимать) на любой наперсток. После этого, я поднимаю тот из оставшихся двух наперстков, под которым, разумеется, нет горошины и предлагаю играющему либо остаться при своем первоначальном выборе, либо выбрать другой наперсток. Какова вероятность выигрыша если играющий решит не менять свой выбор? Какова вероятность выигрыша, если играющий воспользуется моим предложением?

sha · Post by **sha** » 22 Mar 2001 00:53

<BLOCKQUOTE>quote:<HR>Originally posted by PALbTO:
[i:56c914bf9e]А кто хочет сыграть со мной в наперстки? Не вздрагивайте, у меня все по-честному… [img:56c914bf9e]images/smiles/icon_cool.gif[/img:56c914bf9e]

Итак, есть три наперстка. Под одним горошина, а под другими двумя, как и водится – ничего. [img:56c914bf9e]images/smiles/icon_wink.gif[/img:56c914bf9e]
Я естественно знаю, где горошина и предлагаю играющему указать (но не поднимать) на любой наперсток. После этого, я поднимаю тот из оставшихся двух наперстков, под которым, разумеется, нет горошины и предлагаю играющему либо остаться при своем первоначальном выборе, либо выбрать другой наперсток. Какова вероятность выигрыша если играющий решит не менять свой выбор? Какова вероятность выигрыша, если играющий воспользуется моим предложением?[/i:56c914bf9e]<HR></BLOCKQUOTE>

Вот что бывает, когде нет сил прочитать весь тред [img:56c914bf9e]images/smiles/icon_smile.gif[/img:56c914bf9e]. Эта тема уже подымалась, и даже давалась куча ссылок. [img:56c914bf9e]images/smiles/icon_smile.gif[/img:56c914bf9e]

sha · Post by **sha** » 22 Mar 2001 09:52

<BLOCKQUOTE>quote:<HR>Originally posted by PavelM:
[i:8d8f4e6180]Oboznachim levuyu chact' spichki A a pavuyu B. Veroyatnost' P(A>B) = P(A<B)= 0,5.
Dalee lomaem eche raz proizvol'no A ili B . Treugolnik slojitsa tol'ko esli slomana bol'shay chast'. takim obrazom imeem:
P(A>B)xP(lomaem A)=,25
P(A>B)xP(lomaem B)=,25
P(B>A)xP(lomaem A)=,25
P(B>A)xP(lomaem B)=,25

P(treugol'nika)=0,5

A dlya vtorogo sluchaya P=1[/i:8d8f4e6180]<HR></BLOCKQUOTE>

[img:8d8f4e6180]images/smiles/icon_smile.gif[/img:8d8f4e6180]))) Ага.... если бы все было так просто. Т.е. если ломаем большую -- то все тип-топ. Контр-пример:
А=0.8 B=0.2

Ломаем А на 0.1 и 0.7 ... и составляем треугольник со сторонами 7 2 1 [img:8d8f4e6180]images/smiles/icon_smile.gif[/img:8d8f4e6180]))))

PALbTO · Post by **PALbTO** » 22 Mar 2001 16:01

Sha, Вы совершенно правы, я действительно поленился прочесть весь топик. Monty Hall Problem здесь уже упоминали. Never mind [img:e16eae97cb]images/smiles/icon_smile.gif[/img:e16eae97cb]

DV · Post by DV » 22 Mar 2001 18:47

<BLOCKQUOTE>quote:<HR>Originally posted by DV:
[i:b6b613f59a]Еще одна версия ответа про спички:

ln(2)/4 - 1/8, ln(2)/4 - 1/4.

[ 21-03-2001: Message edited by: DV ][/i:b6b613f59a]<HR></BLOCKQUOTE>

A typo: the second answer is ln(2)/2-1/4.

Zaphod · Post by **Zaphod** » 22 Mar 2001 22:27

<BLOCKQUOTE>quote:<HR>Originally posted by mmg:
[i:efecbb91d6]Originally posted by PavelM:
Специально для Zaphod-a - задача Кантора связанная с данным парадоксом.

Пусть имеется квадратная таблица размера NxN, каждая строка и каждый столбец которой занумерованы числами от 1 до N. Известно, что в каждой строке таблицы нарисован один из двух символов — 1 или 0, причем расстановка 1 и 0 в таблице совершенно произвольна. Написать оптимальный алгоритм нахождения бинарной строки длиной N такой, чтобы она не совпадала целиком ни с одной строкой нашей таблицы, не прибегая к полному перебору.[/i:efecbb91d6]
Достаточно просмотреть таблицу по диагонали, вставляя в текущую позицию i искомой строки инверсию табличного элемента T(i,i).[/I]<HR></BLOCKQUOTE>

Предполагалось видимо, что читатель не слыхивал о Гёделе.

COPOKA · Post by **COPOKA** » 22 Mar 2001 22:38

<BLOCKQUOTE>quote:<HR>Originally posted by omnibee:
[i:8f45a85f65] Тогда старшие, как самые мудрые, откажутся от своих долей. Жизнь, она дороже [img:8f45a85f65]http://www.privet.com/ubb/smile.gif[/img:8f45a85f65]
А первым 200 - по 1 дублону через одного...

Конечно, будем считать пиратов некровожадными, хотя это и неправдоподобно.
[/i:8f45a85f65]<HR></BLOCKQUOTE>

Это получается, что если имеется 200+К пиратов, для первых К уже нет никакой надежды выжить?

P.S. Они кровожадные.

Zaphod · Post by **Zaphod** » 22 Mar 2001 22:41

<BLOCKQUOTE>quote:<HR>Originally posted by mmg:
[i:052100997d]А вот такая "простая" задачка.
Доказать, что следующий алгоритм завершается (он действительно завершается [img:052100997d]images/smiles/icon_smile.gif[/img:052100997d] для любого положительного числа X:

пока X не равен 1 повторять:
если X четное, то X = X/2,
иначе (X - нечетное) X=3*X+1[/i:052100997d]<HR></BLOCKQUOTE>

Что называется, "обычная задача". Изюминки что-то не видать. Или есть?

Zaphod · Post by **Zaphod** » 22 Mar 2001 22:52

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:2005e087e1]
Вот красивая задачка, которая мне очень нравится.

[b:2005e087e1]Есть спичка. Ее произвольным образом ломают на две части, потом одну из оставшихся частей ломают еще раз. Какова вероятность, что из трех полученных обломков можно сложить треугольник?

P.S. Вариант. Второй раз ломают не любую, а бОльшую часть спички. Вопрос тот же.[/b:2005e087e1][/i:2005e087e1]<HR></BLOCKQUOTE>

Не слишком ли стандартна сия задачка?

Жаль, не предложил ты и второй вариант - "ломают мЕньшую часть спички. То-то мы бы попризадумались, в какую же псевдометрику поместить сию спичку.

Zaphod · Post by **Zaphod** » 22 Mar 2001 22:59

<BLOCKQUOTE>quote:<HR>Originally posted by tengiz:
[i:fc7465c077]Спички:

ln(2)/4 и ln(2)/2

[ 21-03-2001: Message edited by: tengiz ][/i:fc7465c077]<HR></BLOCKQUOTE>

Ну откуда логарифмы-то?! Ограничения все линейные, распределение, надеюсь, равномерное...

Zaphod · Post by **Zaphod** » 22 Mar 2001 23:03

<BLOCKQUOTE>quote:<HR>Originally posted by obormot:
[i:e413c7b198]А мои задачки значит никому не нравятся..
[/i:e413c7b198]<HR></BLOCKQUOTE>

Так сложные слишком! Не решаются!

Zaphod · Post by **Zaphod** » 22 Mar 2001 23:30

<BLOCKQUOTE>quote:<HR>Originally posted by sha:
[i:46f382cbb0]А как насчет ассоциативного мышления? [img:46f382cbb0]images/smiles/icon_smile.gif[/img:46f382cbb0]

Надо продолжить последовательность
24, 81, 63, 26, 41, 28,...[/i:46f382cbb0]<HR></BLOCKQUOTE>

25

sha · Post by **sha** » 23 Mar 2001 01:07

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[i:13d3b0fb62]25[/i:13d3b0fb62]<HR></BLOCKQUOTE>

Ты знал, ты знал [img:13d3b0fb62]images/smiles/icon_smile.gif[/img:13d3b0fb62]

tengiz · Post by **tengiz** » 23 Mar 2001 01:56

Moleg,

Как часто бывает, я слегка маханулся в расчётах, так что Ваши ответы ближе к истине, но тоже отличается от совсем правильных в 2 раза, imho.

Zaphod,

Решение для случая, когда второй раз ломается длинная часть спички:

Берем отрезок длины 1 и случайно выбираем точку [b:7f22a701fc]a[/b:7f22a701fc] на интервале (0, 1/2), распределение равномерное. После этого генерим ещё одно равномерно распределённое значение [b:7f22a701fc]b[/b:7f22a701fc] на интервале ([b:7f22a701fc]a[/b:7f22a701fc], 1). Для того, чтобы три полученных отрезка (0, [b:7f22a701fc]a[/b:7f22a701fc]), ([b:7f22a701fc]a[/b:7f22a701fc], [b:7f22a701fc]b[/b:7f22a701fc]) и ([b:7f22a701fc]b[/b:7f22a701fc], 1) сложились в треугольник, необходимо, чтобы точка [b:7f22a701fc]b[/b:7f22a701fc] оказалась в интервале (1/2, 1/2 + [b:7f22a701fc]a[/b:7f22a701fc]). Вероятность такого события при заданном [b:7f22a701fc]a[/b:7f22a701fc]: [b:7f22a701fc]a[/b:7f22a701fc] / (1 - [b:7f22a701fc]a[/b:7f22a701fc]). Для того, чтобы посчитать итоговую вероятность, нам необходимо проинтегрировать это выражение по [b:7f22a701fc]a[/b:7f22a701fc] на интервале [0, 1/2], что и даёт: ln(2) - 1/2.

Решение для первого случая, очевидно, практически такое же, с точностью до коэффициента порядка 2 [img:7f22a701fc]images/smiles/icon_razz.gif[/img:7f22a701fc] : ln(2)/2 – 1/4.

Sha,

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

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

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

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

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

<BLOCKQUOTE>quote:<HR>Originally posted by sha:
[i:e72d0d3ab6]Ты знал, ты знал [img:e72d0d3ab6]images/smiles/icon_smile.gif[/img:e72d0d3ab6][/i:e72d0d3ab6]<HR></BLOCKQUOTE>

Да нет, не знал, просто с детства цифры люблю. Мой идеал - Рамануджан.

Zaphod · Post by **Zaphod** » 23 Mar 2001 02:04

<BLOCKQUOTE>quote:<HR>Originally posted by tengiz:
[i:acaea16e39]Zaphod,

Решение для случая, когда второй раз ломается длинная часть спички:

Берем отрезок длины 1 и случайно выбираем точку [b:acaea16e39]a[/b:acaea16e39] на интервале (0, 1/2), распределение равномерное. После этого генерим ещё одно равномерно распределённое значение [b:acaea16e39]b[/b:acaea16e39] на интервале ([b:acaea16e39]a[/b:acaea16e39], 1). Для того, чтобы три полученных отрезка (0, [b:acaea16e39]a[/b:acaea16e39]), ([b:acaea16e39]a[/b:acaea16e39], [b:acaea16e39]b[/b:acaea16e39]) и ([b:acaea16e39]b[/b:acaea16e39], 1) сложились в треугольник, необходимо, чтобы точка [b:acaea16e39]b[/b:acaea16e39] оказалась в интервале (1/2, 1/2 + [b:acaea16e39]a[/b:acaea16e39]). Вероятность такого события при заданном [b:acaea16e39]a[/b:acaea16e39]: [b:acaea16e39]a[/b:acaea16e39] / (1 - [b:acaea16e39]a[/b:acaea16e39]). Для того, чтобы посчитать итоговую вероятность, нам необходимо проинтегрировать это выражение по [b:acaea16e39]a[/b:acaea16e39] на интервале [0, 1/2], что и даёт: ln(2) - 1/2.

Решение для первого случая, очевидно, практически такое же, с точностью до коэффициента порядка 2 [img:acaea16e39]images/smiles/icon_razz.gif[/img:acaea16e39] : ln(2)/2 – 1/4.
[/i:acaea16e39]<HR></BLOCKQUOTE>

Вы меня убедили для случая с "длинным куском".

Но - как Вам такой подход: обе точки бросаются на отрезок с равномерным распределением. Нарисуем квадрат 1х1, и покрасим черным те точки, где треугольник получается. Это, очевидно, 1/4 всей площади, а именно - верхний левый треугольник в верхнем левом квадранте и нижний правый треугольник в нижнем правом квадранте. [img:acaea16e39]images/smiles/icon_smile.gif[/img:acaea16e39]

DV · Post by DV » 23 Mar 2001 02:14

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[i:0a52e20f9e]Вы меня убедили для случая с "длинным куском".

Но - как Вам такой подход: обе точки бросаются на отрезок с равномерным распределением. Нарисуем квадрат 1х1, и покрасим черным те точки, где треугольник получается. Это, очевидно, 1/4 всей площади, а именно - верхний левый треугольник в верхнем левом квадранте и нижний правый треугольник в нижнем правом квадранте. [img:0a52e20f9e]images/smiles/icon_smile.gif[/img:0a52e20f9e][/i:0a52e20f9e]<HR></BLOCKQUOTE>

Вероятность поломать длинный кусок спички в этом случае уже не 1/2. Новая задача, однако.