Задачки-2

COPOKA · Post by **COPOKA** » 21 Mar 2001 00:27

<BLOCKQUOTE>quote:<HR>Originally posted by McSeem:
[b:a95a2fd3ce] Что-то мне навеяло, может еще кому будет интересно.
Берем большой лист бумаги и расчерчиваем его равноудаленными параллельными прямыми. Расстояние между прямыми равно длине спички. Бросаем спички на наш лист. Какова вероятность того, что спичка пересечет одну из прямых?
[/b:a95a2fd3ce]<HR></BLOCKQUOTE>

My kid says it's aforementioned "Boufon's needle" and it's common knowledge the probability is 2/pi . Also, it's one of the ways to find Pi experimentally.

PavelM · Post by **PavelM** » 21 Mar 2001 02:27

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[b:14cdd1b7ed] Да-да, пожалуйста. И объясните, в чем там парадокс. Не сводится ли он к сараю с надписью ..., а там дрова?[/b:14cdd1b7ed]<HR></BLOCKQUOTE>

Специально для Zaphod-a - задача Кантора связанная с данным парадоксом.

Пусть имеется квадратная таблица размера NxN, каждая строка и каждый столбец которой занумерованы числами от 1 до N. Известно, что в каждой строке таблицы нарисован один из двух символов — 1 или 0, причем расстановка 1 и 0 в таблице совершенно произвольна. Написать оптимальный алгоритм нахождения бинарной строки длиной N такой, чтобы она не совпадала целиком ни с одной строкой нашей таблицы, не прибегая к полному перебору.

COPOKA · Post by **COPOKA** » 21 Mar 2001 08:02

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

[/i:1950e1673a]<HR></BLOCKQUOTE>

А мне можно? Какое-то решение очень уж элементарное получается, даже ребенок мне не нужен... Кэч, что ли?

McSeem · Post by **McSeem** » 21 Mar 2001 09:45

<BLOCKQUOTE>quote:<HR>[i:4f9ee8756c]Originally posted by Joker:
Начну с формулировки исходной задачи.
[b:4f9ee8756c]Дана окружность. Какова вероятность того, что наугад взятая хорда отсечет дугу, длина которой меньше одной трети длины окружности?[/b:4f9ee8756c]
[/i:4f9ee8756c]<HR></BLOCKQUOTE>

Что-то мне навеяло, может еще кому будет интересно.
Берем большой лист бумаги и расчерчиваем его равноудаленными параллельными прямыми. Расстояние между прямыми равно длине спички. Бросаем спички на наш лист. Какова вероятность того, что спичка пересечет одну из прямых?

------------------
McSeem

mmg · Post by **mmg** » 21 Mar 2001 10:19

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

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

А вот такая "простая" задачка.
Доказать, что следующий алгоритм завершается (он действительно завершается [img:f5429d34c6]images/smiles/icon_smile.gif[/img:f5429d34c6] для любого положительного числа X:

пока X не равен 1 повторять:
если X четное, то X = X/2,
иначе (X - нечетное) X=3*X+1

PALbTO · Post by **PALbTO** » 21 Mar 2001 16:19

To: moleg

Oлег, спасибо. Верно, конечно… причем, во втором варианте Вы приблизились к «красивому» решению так близко, что мне даже вспомнилась детская игра «горячо-холодно» [img:0f3343d90d]images/smiles/icon_smile.gif[/img:0f3343d90d] ..

Вот простое решение: 19² = 361
Откладываем 19 уголов по 19º и последний перекроет первый на 1º.

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

Joker · Post by **Joker** » 21 Mar 2001 17:38

Эй, народ, а теория вероятности вам что, надоела?
Вот красивая задачка, которая мне очень нравится.

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

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

PavelM · Post by **PavelM** » 21 Mar 2001 20:56

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

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

Спички:

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

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

PALbTO · Post by **PALbTO** » 21 Mar 2001 22:10

to: PavelM

Не торопитесь [img:481be5b16e]images/smiles/icon_smile.gif[/img:481be5b16e]

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

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,...