Задачки-2

и задачки для интервью.
sha
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задачки-2

Post by sha »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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]
User avatar
tengiz
Уже с Приветом
Posts: 4468
Joined: 21 Sep 2000 09:01
Location: Sammamish, WA

Задачки-2

Post by tengiz »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задачки-2

Post by sha »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 1449
Joined: 02 Jan 2000 10:01

Задачки-2

Post by ACL »

Из пункта А в пункт Б ведут две дороги, так что для два велосипедиста, выехавшие из А в Б по разным дорогам, смогут добраться до Б даже если они связаны веревкой длины 2R.
Вопрос - смогут ли разъехаться два автомобиля радиуса R [img:1160ba941d]images/smiles/icon_smile.gif[/img:1160ba941d], если они выедут навстречу друг другу ?
sha
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задачки-2

Post by sha »

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

Надо продолжить последовательность
24, 81, 63, 26, 41, 28,...
sha
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задачки-2

Post by sha »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 1211
Joined: 12 Oct 1999 09:01

Задачки-2

Post by DV »

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

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

[ 21-03-2001: Message edited by: DV ]
moleg
Уже с Приветом
Posts: 196
Joined: 07 Jan 2000 10:01
Location: Gainesville, FL, US

Задачки-2

Post by moleg »

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

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

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

Решение:
<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">code:</font><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
Posts: 5
Joined: 20 Mar 2001 10:01
Location: Minneapolis, MN

Задачки-2

Post by PALbTO »

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

Итак, есть три наперстка. Под одним горошина, а под другими двумя, как и водится – ничего. [img:fb390dbe8c]images/smiles/icon_wink.gif[/img:fb390dbe8c]
Я естественно знаю, где горошина и предлагаю играющему указать (но не поднимать) на любой наперсток. После этого, я поднимаю тот из оставшихся двух наперстков, под которым, разумеется, нет горошины и предлагаю играющему либо остаться при своем первоначальном выборе, либо выбрать другой наперсток. Какова вероятность выигрыша если играющий решит не менять свой выбор? Какова вероятность выигрыша, если играющий воспользуется моим предложением?
sha
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задачки-2

Post by sha »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задачки-2

Post by sha »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Posts: 5
Joined: 20 Mar 2001 10:01
Location: Minneapolis, MN

Задачки-2

Post by PALbTO »

Sha, Вы совершенно правы, я действительно поленился прочесть весь топик. Monty Hall Problem здесь уже упоминали. Never mind [img:e16eae97cb]images/smiles/icon_smile.gif[/img:e16eae97cb]
DV
Уже с Приветом
Posts: 1211
Joined: 12 Oct 1999 09:01

Задачки-2

Post by DV »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 882
Joined: 22 Dec 2000 10:01
Location: USA

Задачки-2

Post by COPOKA »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Joker:
[i:2005e087e1]
Вот красивая задачка, которая мне очень нравится.

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

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

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

Жаль, не предложил ты и второй вариант - "ломают мЕньшую часть спички. То-то мы бы попризадумались, в какую же псевдометрику поместить сию спичку.
Zaphod
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by obormot:
[i:e413c7b198]А мои задачки значит никому не нравятся..
[/i:e413c7b198]<HR></BLOCKQUOTE>

Так сложные слишком! Не решаются!
Zaphod
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 281
Joined: 28 Jul 2000 09:01
Location: Minsk > CA > NC > WA > CA

Задачки-2

Post by sha »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by Zaphod:
[i:13d3b0fb62]25[/i:13d3b0fb62]<HR></BLOCKQUOTE>

Ты знал, ты знал [img:13d3b0fb62]images/smiles/icon_smile.gif[/img:13d3b0fb62]
User avatar
tengiz
Уже с Приветом
Posts: 4468
Joined: 21 Sep 2000 09:01
Location: Sammamish, WA

Задачки-2

Post by tengiz »

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
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><HR>Originally posted by sha:
[i:e72d0d3ab6]Ты знал, ты знал [img:e72d0d3ab6]images/smiles/icon_smile.gif[/img:e72d0d3ab6][/i:e72d0d3ab6]<HR></BLOCKQUOTE>

Да нет, не знал, просто с детства цифры люблю. Мой идеал - Рамануджан.
Zaphod
Уже с Приветом
Posts: 992
Joined: 06 Feb 2001 10:01
Location: San Jose, USA

Задачки-2

Post by Zaphod »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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
Уже с Приветом
Posts: 1211
Joined: 12 Oct 1999 09:01

Задачки-2

Post by DV »

<BLOCKQUOTE><font size="1" face="Arial, Verdana, Helvetica, sans-serif">quote:</font><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. Новая задача, однако.

Return to “Головоломки”