Задачки-2

McSeem · Post by **McSeem** » 14 Mar 2001 18:01

Еще задача аналитико-алгоритмическая. На плоскости есть N > 1 точек, заданных координатами (X,Y). Требуется найти параметры окружности минимально возвожного радиуса, такой чтобы все точки находились внутри этой окружности.

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

vlad3333 · Post by **vlad3333** » 14 Mar 2001 18:07

[QUOTE]Originally posted by Talya:
[I]А вот еще одна, с собеседования на работу у мужа. Я, честно сказать, кучу времени убила, но сдалась в конце концов [img:5addb2d67d]http://www.privet.com/ubb/frown.gif[/img:5addb2d67d]
Бочка. В бочке четыре отверстия, в каждом из которых находится выключатель. Расположенная на бочке лампочка загорается, если все выключатели находятся в одинаковом положении. Вы можете одновременно просунуть руки в любые два отверстия и поменять или нет положения находящихся в них выключателей. После чего бочка вращается вокруг своей оси произвольным образом. Вы можете повторить операцию с выключателями. И т.д. Понятно, что каждый раз Вы не знаете с каками выключателями Вы проводили операцию в предыдущий момент. Какое минимальное количество операций и каких обязательно приведет к тому, что лампочка загорится?

Удачи. Талья.

1-2
3-4
1) 1->,4 ->
2) 1->, 2->
3) 2<-,3->
4)3-наоборот, 4-наоборот. (если не откр.)
5)1-наоборот, 4-наоборот [img:5addb2d67d]http://www.privet.com/ubb/smile.gif[/img:5addb2d67d]

[This message has been edited by vlad3333 (edited 14-03-2001).]

bee3313 · Post by **bee3313** » 14 Mar 2001 18:20

<BLOCKQUOTE>quote:<HR>Originally posted by Talya:
[i:1f58af7992]А вот еще одна, с собеседования на работу у мужа. Я, честно сказать, кучу времени убила, но сдалась в конце концов [img:1f58af7992]http://www.privet.com/ubb/frown.gif[/img:1f58af7992]
Бочка. В бочке четыре отверстия, в каждом из которых находится выключатель. Расположенная на бочке лампочка загорается, если все выключатели находятся в одинаковом положении. Вы можете одновременно просунуть руки в любые два отверстия и поменять или нет положения находящихся в них выключателей. После чего бочка вращается вокруг своей оси произвольным образом. Вы можете повторить операцию с выключателями. И т.д. Понятно, что каждый раз Вы не знаете с каками выключателями Вы проводили операцию в предыдущий момент. Какое минимальное количество операций и каких обязательно приведет к тому, что лампочка загорится?[/i:1f58af7992]<HR></BLOCKQUOTE>

Мне нравится другая (не американская/hi-tek) формулировка той же задачи предложенная КОТом (См.:КОТ 2/22/01 в топике "Лететь иль нет"), она содержит ответ: "4". В том топике никто ее не решал, а зря. Я попробовал-мне понравилась.

Его формулировка:Вот, осмелюсь предложить вашему вниманию такую задачку Представте себе, что после того как вы уснули у себя дома на удобной и мягкой постели вы проснулись в страшной и безводной пустыне Брандарболе. Где на сотни миль нет никакой воды. Сон занес вас в самое серце этой пустыни...и вы увидели возле огромной бочкои с надписью "ПЫВО" , огромную корзину пахучей тараньки с надписью "ТАРАНЬКА FREE "....мням, мням, мням... У вас потекли слюньки....и вы тут же сьели большую и вкусную тараньку.
Когда вы ели заодно вы читали надпись сделанную мелким шрифтом и находящуюся под надписью «ПЫВО»,: "О том как открыть бочку..". К тому времени когда вы дочитали до места, где написано, что у вам дано всего 4 попытки на открывание крышки и ни одной больше, вы уже сьели дюжину таранек.. В этом месте вы обратили внимание, что вокруг из песка торчат полузасыпанные человеческие кости.....

Итак вам уже нестерпимо хочется пить. Перед вами стоит 300 литровая бочка, прохладного пива. Но вот проблема бочка имеет секрет... В верхней части бочки "крышке" имеется четыре одинаковых отверстия. Вы не можете заглянуть внутрь, чтоб посмотреть, что в этих отверстиях происходит. Единственно, что вы знаете, так это то, что под крышкой на некой оси вращается крестовина. На концах крестовины имеются поворачивающиеся "рыбки". эти рыбки и есть ключ к открытию бочки. Каждая рыбка может быть повернуты только в два положения, носом вверх или хвостом верх. Как только все четыре рыбки повернуты одинаково крышка бочки открывается и вы можете напится пива. Но вот беда, в тот момент как вы вытащили две руки из бочки эта крестовина повернулась в самом неблагоприятном для вас положении. Вы не можете нашупать никаких других рыбок внутри кроме двух находящихся непосредственно под отверстием. Вы не можете одной рукой подержать рыбки, а второй полезть и повернуть остальные. И такой вариант как к примеру вы всунули руки в отверстия находящиеся по диагонале повернули рыбки одинаково, а потом засунули руки в другие отверстия и повернули две оставшиеся рыбки. По закону как только вы вытащили руки крестовина вращается и выставляет рыбки в найболее невыгодном для вас положении.
.......

[This message has been edited by bee3313 (edited 14-03-2001).]

VR · Post by VR » 14 Mar 2001 18:21

[QUOTE]Originally posted by Talya:
[I]Доброго дня!

Натали, про булочку классная задачка, хорошо я не каждые полчаса на форум заглядываю и Джокер не успел мне помешать получить удовольствие [img:e7b22c60ef]http://www.privet.com/ubb/smile.gif[/img:e7b22c60ef]

У меня тоже есть. Мне она симпатичной кажется, хоть и про лампочки, а не про булочки.

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

А руками потрогать лампочки дозволено? [img:e7b22c60ef]http://www.privet.com/ubb/wink.gif[/img:e7b22c60ef]

Zaphod · Post by **Zaphod** » 14 Mar 2001 18:21

<BLOCKQUOTE>quote:<HR>Originally posted by McSeem:
[i:830f3e0055]To Joker:

3D решение задачи не работает для случая, когда полученная прямая пересекает окружности. То есть, представим 2 больших мыльных пузыря (разного диаметра) и один маленький. Так вот - если этот находится внутри конуса, образованного двумя большими пузырями, то плоскость на 3 шара мы никак не положим.

[/i:830f3e0055]<HR></BLOCKQUOTE>

[img:830f3e0055]http://www.privet.com/ubb/smile.gif[/img:830f3e0055] А доказать это очень спорное утверждение слабО?

Впрочем, верно - есть еще один интересный вырожденный случай, когда центры окружностей лежат на одной прямой. Его надо рассматривать отдельно, хотя там, собственно, и рассматривать нечего.

С другой стороны, можно слегка модифицировать решение, и плоскость класть не касательную, которая так наглядна, а... ну вы поняли.

bee3313 · Post by **bee3313** » 14 Mar 2001 18:22

//оорс

[This message has been edited by bee3313 (edited 14-03-2001).]

Zaphod · Post by **Zaphod** » 14 Mar 2001 18:33

<BLOCKQUOTE>quote:<HR>Originally posted by VR:
[i:9a54a2e64e]А руками потрогать лампочки дозволено? [img:9a54a2e64e]http://www.privet.com/ubb/wink.gif[/img:9a54a2e64e][/i:9a54a2e64e]<HR></BLOCKQUOTE>

Да без этого она не решается...

Zaphod · Post by **Zaphod** » 14 Mar 2001 18:35

<BLOCKQUOTE>quote:<HR>Originally posted by vlad3333:
[i:90e18e1ff9]1-2
3-4
1) 1->,4 ->
2) 1->, 2->
3) 2<-,3->
4)3-наоборот, 4-наоборот. [img:90e18e1ff9]http://www.privet.com/ubb/smile.gif[/img:90e18e1ff9]

[/i:90e18e1ff9]<HR></BLOCKQUOTE>

Объясните тормозу.

ChickenFromMinsk · Post by **ChickenFromMinsk** » 14 Mar 2001 18:39

Вот еще одна. Имеется 12 монет, одна из которых фальшивая. Нужно 3 взвешиваниями найти фальшивую монету или доказать, что задача не имеет решения.

vlad3333 · Post by **vlad3333** » 14 Mar 2001 19:24

<BLOCKQUOTE>quote:<HR>Originally posted by ChickenFromMinsk:
[i:18d1b9c787]Вот еще одна. Имеется 12 монет, одна из которых фальшивая. Нужно 3 взвешиваниями найти фальшивую монету или доказать, что задача не имеет решения.[/i:18d1b9c787]<HR></BLOCKQUOTE>

Если я правильно понял, то извесен вес монеты не подделки. К примеру подделка весит больше чем оригинал.
1) сравниваем вес 4 и 4 Монет.

если равен то фальшивка в 3 четверке.
Если нет то в той где больше вес. Дальше понятно.

[This message has been edited by vlad3333 (edited 14-03-2001).]

ChickenFromMinsk · Post by **ChickenFromMinsk** » 14 Mar 2001 19:28

Что легче или тяжелее, неизвестно [img:943cd18c82]http://www.privet.com/ubb/biggrin.gif[/img:943cd18c82]

<BLOCKQUOTE>quote:<HR>Originally posted by vlad3333:
[i:943cd18c82] Если я правильно понял, то извесен вес монеты не подделки. К примеру подделка весит больше чем оригинал.
[/i:943cd18c82]<HR></BLOCKQUOTE>

vlad3333 · Post by **vlad3333** » 14 Mar 2001 19:43

<BLOCKQUOTE>quote:<HR>Originally posted by ChickenFromMinsk:
[i:a268ea07eb]Что легче или тяжелее, неизвестно [img:a268ea07eb]http://www.privet.com/ubb/biggrin.gif[/img:a268ea07eb]

[/i:a268ea07eb]<HR></BLOCKQUOTE>
Значит все таки известен вес одной монеты, не фальшивки. К примеру 1n.
1)Кладем на одну чашку груз 4n и 4 монеты, а на вторую 4 монеты. Если весы покажут вес 4n , то фальшивка в 3 четверке. [img:a268ea07eb]http://www.privet.com/ubb/biggrin.gif[/img:a268ea07eb]

[This message has been edited by vlad3333 (edited 14-03-2001).]

Joker · Post by **Joker** » 14 Mar 2001 19:51

Влад, а ты упрямый [img:898fd90242]http://www.privet.com/ubb/smile.gif[/img:898fd90242] Нет никаких других грузов, кроме монет. Неизвестно, сколько весят монеты. Неизвестно, тяжелее или легче фальштвая монета. И все равно легко решается.

P.S. Я уж теперь молчу, а то совсем запинали [img:898fd90242]http://www.privet.com/ubb/frown.gif[/img:898fd90242] И про счастливые билеты так никто и не решил [img:898fd90242]http://www.privet.com/ubb/tongue.gif[/img:898fd90242]

ChickenFromMinsk · Post by **ChickenFromMinsk** » 14 Mar 2001 19:53

<BLOCKQUOTE>quote:<HR>Originally posted by vlad3333:
[i:ee01deaa41] Значит все таки известен вес одной монеты, не фальшивки. К примеру 1n.
[/i:ee01deaa41]<HR></BLOCKQUOTE>

Разумеется, вес монеты неизвестен. И их общая масса неизвестна тоже. Вы, конечно, можете взвесить отдельную монету, если вам не жалко одно взвешивание на этом потерять...

Lis · Post by **Lis** » 14 Mar 2001 22:12

Какие-то все больно уж известные задачи [img:270a1d74c8]http://www.privet.com/ubb/smile.gif[/img:270a1d74c8]

Вот еще весьма актуальная для этого форума задачка, которую, быть может, не все слышали ( во всяком случае я не слышал точно [img:270a1d74c8]http://www.privet.com/ubb/wink.gif[/img:270a1d74c8] ). Задачка с другого форума, которую там опубликовал пользователь с ником Ли.
<BLOCKQUOTE>quote:<HR>
[b:270a1d74c8]"русские в Америке" [/b:270a1d74c8]

Одному крупному Нью-Йоркскому бизнесмену пришла телеграмма следующего содержания: "акции фирмы Compaq на следующей неделе повысятся". И действительно, прошла неделя и акции Compaq повысились. Затем пришла вторая телеграмма "акции фирмы General Motors на следующей неделе упадут". Так оно и вышло. Эти телеграммы приходили еще 5-6 раз и каждый раз содержали правильный прогноз относительно поведения курса акций какой-нибудь компании. Последняя телеграмма гласила: "Через неделю акции фирмы N. резко повысятся в цене". Мужик, конечно, проникся и накупил их на все деньги, на чем собственно и разорился, поскольку цена этих акций затем окончательно и бесповоротно упала. Каким образом жулики умудрялись в течение нескольких недель делать правильные прогнозы? (понятно, что это было основной причиной, почему он им, в конце концов, поверил )
<HR></BLOCKQUOTE>

[This message has been edited by Lis (edited 14-03-2001).]

bee3313 · Post by **bee3313** » 14 Mar 2001 22:33

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:0675011660]Номер автобусного билета состоит из 6 цифр. Известно, что счастливый билет - это такой, у которого сумма первых трех цифр совпадает с суммой трех последних. Найти общее число счастливых билетов и таким образом оценить вероятность легко и быстро стать счастливым [img:0675011660]http://www.privet.com/ubb/smile.gif[/img:0675011660][/i:0675011660]<HR></BLOCKQUOTE>

Я думаю, что я решил ее, но ответ состоит из суммы разных факториалов. И я не уверен, что такой ответ устраивает задававшего и публику.

Talya · Post by **Talya** » 14 Mar 2001 22:43

Задачки, конечно, известные... Ну не знаю я неизвестных задачек (простите за каламбур).
А на Вашу у меня два варианта ответов.

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

Удачи. Талья.

Zaphod · Post by **Zaphod** » 14 Mar 2001 22:56

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:f14569d1d3]Влад, а ты упрямый [img:f14569d1d3]http://www.privet.com/ubb/smile.gif[/img:f14569d1d3] Нет никаких других грузов, кроме монет. Неизвестно, сколько весят монеты. Неизвестно, тяжелее или легче фальштвая монета. И все равно легко решается.

P.S. Я уж теперь молчу, а то совсем запинали [img:f14569d1d3]http://www.privet.com/ubb/frown.gif[/img:f14569d1d3] И про счастливые билеты так никто и не решил [img:f14569d1d3]http://www.privet.com/ubb/tongue.gif[/img:f14569d1d3][/i:f14569d1d3]<HR></BLOCKQUOTE>

Джокер, хрен ли тут решать-то про счастливые билеты? На втором курсе на вероятности всю эту чушь проходят. Сказать ответ? Или пусть подумает народ...

Насчет же фальшивой монеты - я что-то пас в условиях, когда неизвестно, легче или тяжелее. Что-то сдается мне, что оно не решается за три хода.

Да, и я бы еще раз попросил vlad20260 разъяснить свое решение насчет бочки с пивом и выключателями.

[This message has been edited by Zaphod (edited 14-03-2001).]

COPOKA · Post by **COPOKA** » 14 Mar 2001 23:28

<BLOCKQUOTE>quote:<HR>Originally posted by ChickenFromMinsk:
[i:296d8e27e4] Разумеется, вес монеты неизвестен. И их общая масса неизвестна тоже. Вы, конечно, можете взвесить отдельную монету, если вам не жалко одно взвешивание на этом потерять...

[/i:296d8e27e4]<HR></BLOCKQUOTE>
Минуточку, что значит "взвесить отдельную монету"? Обычно в таких задачах речь не идет о весах, дающих возможность [b:296d8e27e4]измерить[/b:296d8e27e4] вес. Я думала, задача о весах с двумя чашками, позволяющими только [b:296d8e27e4]сравнить[/b:296d8e27e4] вес в одной из них с весом в другой... Если весы цифровые, [img:296d8e27e4]http://www.privet.com/ubb/smile.gif[/img:296d8e27e4] это же совсем другая задача.

Nataly · Post by **Nataly** » 14 Mar 2001 23:34

По поводу бочки с пивом и выключателями. Подобную этоы задачку можно посмотреть в компьютерной детской игре "Следствие ведут колобки", там еше написано, что это для детей от 7 до 12 лет [img:be8b618e0d]http://www.privet.com/ubb/wink.gif[/img:be8b618e0d]. Самое смешное то, что дети "проходят" все уровни в этоы игрушке за час, в то время как взрослые дяди и тети программисты тратят на это пару-тройку дней [img:be8b618e0d]http://www.privet.com/ubb/biggrin.gif[/img:be8b618e0d].

Относительно монеток, всебы хорошо, но вот есть один случай при котором получается 4 взвешивания. Может я что-то не так делаю. В принципе проверить больше или меньше весит фальшивая монета можно во время 2-ого взвешивания и сравнения с уже известными не фальшивыми монетами, но если вес равен, то фальшивка в оставшейся кучке из 3-х манет и в этом случае одного третьего взвешивания не достаточно...

------------------
Nataly

Nataly · Post by **Nataly** » 15 Mar 2001 00:18

Пронумируем монетки
ABCD EFGH IJKL

Теперь взвешиваем одну четверку против другой
BEHK - CDFJ, DEOT - AFGH, ABCD - FGIK.
К примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "B", которая легче других. Дальше можно рассматреть другие результаты взвешиваний...

------------------
Nataly

Joker · Post by **Joker** » 15 Mar 2001 01:01

1. Задача с монетками решается. За ровно три взвешивания. Весы безусловно с двумя чашками. Никаких цифр. Могу спорить на свою годовую зарплату. И решение несложное.

2. В счастливых билетах никаких факториалов не надо. Ответ могу сказать, это не проблема (если я его не забыл за эти годы [img:333de69594]http://www.privet.com/ubb/smile.gif[/img:333de69594]) - 55251. Т.е. вероятность стать счастливым за одну поездку в автобусе - примерно 1/18. А вот как этот ответ получается - вопрос другой [img:333de69594]http://www.privet.com/ubb/wink.gif[/img:333de69594]
Алгоритмически (на компьютере) эту задачу решить много проще, чем вручную. Но и вручную вполне по силам школьнику. Мы когда-то давно об этом заметку в "Квант" писали, они даже статейку сделали...
Zaphod, у тебя ответ сходится?
Кстати, из моих студентов-второкурсников за 15 лет никто не был в состоянии решить подобную задачу за разумное время (ну, скажем, за час) - точнее, один парень мог, но это приятное исключение [img:333de69594]http://www.privet.com/ubb/smile.gif[/img:333de69594] мы на вундеркиндов не рассчитываем...

vlad3333 · Post by **vlad3333** » 15 Mar 2001 01:41

.

[This message has been edited by vlad3333 (edited 15-03-2001).]

vlad3333 · Post by **vlad3333** » 15 Mar 2001 01:46

<BLOCKQUOTE>quote:<HR>Originally posted by Nataly:
[i:5dad72ede3]Пронумируем монетки
ABCD EFGH IJKL

Теперь взвешиваем одну четверку против другой
BEHK - CDFJ, DEOT - AFGH, ABCD - FGIK.
К примеру, если результаты взвешивания были: слева легче, равно, слева легче, [b:5dad72ede3]то фальшивой может быть только монета "B", которая легче других.[/b:5dad72ede3] Дальше можно рассматреть другие результаты взвешиваний...

[/i:5dad72ede3]<HR></BLOCKQUOTE>Это я уже предлагал. А если фальшивая монета окажется тяжелее? О том легче она или тяжелее в условиях ничего не было сказано.

[This message has been edited by vlad3333 (edited 14-03-2001).]

Nataly · Post by **Nataly** » 15 Mar 2001 01:50

<BLOCKQUOTE>quote:<HR>Originally posted by vlad3333:
[i:83d06933fa]

Originally posted by Nataly:
Пронумируем монетки
ABCD EFGH IJKL

Теперь взвешиваем одну четверку против другой
BEHK - CDFJ, DEOT - AFGH, ABCD - FGIK.
К примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "B", которая легче других. Дальше можно рассматреть другие результаты взвешиваний...

[/i:83d06933fa]<HR></BLOCKQUOTE>Это я уже предлагал. А если фальшивая монета окажется тяжелее?

А какая разница то?... Если "B" фальшивая и тяжелее, то результат взвешивания, слева тяжелее, равно, слева тяжелее.

------------------
Nataly