Задачки-2

COPOKA · Вт мар 20, 2001 6:27 pm

<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 · Вт мар 20, 2001 8:27 pm

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

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

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

COPOKA · Ср мар 21, 2001 2:02 am

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

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

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

McSeem · Ср мар 21, 2001 3:45 am

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

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

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

mmg · Сообщение **mmg** » Ср мар 21, 2001 4:19 am

<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 · Ср мар 21, 2001 10:19 am

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 · Ср мар 21, 2001 11:38 am

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

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

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

PavelM · Ср мар 21, 2001 2:56 pm

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 · Ср мар 21, 2001 4:01 pm

Спички:

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

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

PALbTO · Ср мар 21, 2001 4:10 pm

to: PavelM

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

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

sha · Сообщение **sha** » Ср мар 21, 2001 4:30 pm

<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 · Ср мар 21, 2001 4:58 pm

<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 · Сообщение **sha** » Ср мар 21, 2001 5:10 pm

<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 · Сообщение **ACL** » Ср мар 21, 2001 5:11 pm

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

sha · Сообщение **sha** » Ср мар 21, 2001 5:12 pm

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

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