Задачки-2

tengiz · Post by **tengiz** » 15 Mar 2001 03:10

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

tengiz · Post by **tengiz** » 15 Mar 2001 03:11

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

moleg · Post by **moleg** » 15 Mar 2001 04:05

Originally posted by Joker:
[i:5ee2c45827]Кстати, из моих студентов-второкурсников за 15 лет никто не был в состоянии решить подобную задачу за разумное время (ну, скажем, за час) - точнее, один парень мог, но это приятное исключение [img:5ee2c45827]http://www.privet.com/ubb/smile.gif[/img:5ee2c45827] мы на вундеркиндов не рассчитываем...[/i:5ee2c45827]

У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!

Это просто, вспомнилось.

COPOKA · Post by **COPOKA** » 15 Mar 2001 04:26

<BLOCKQUOTE>quote:<HR>Originally posted by Nataly:
[i:dcda700c65]COPOKA,

С симетрией не получается, если все проверять по 2 раза, то фальшивая монетка не находится.
[/i:dcda700c65]<HR></BLOCKQUOTE>
(вздох) - Точно. После поста vlad3333 очевидно, что некоторые случаи требуют, чтобы что-то взвешивалось 3 раза... Жаль. [img:dcda700c65]http://www.privet.com/ubb/frown.gif[/img:dcda700c65]

COPOKA · Post by **COPOKA** » 15 Mar 2001 04:30

<BLOCKQUOTE>quote:<HR>Originally posted by moleg:
[i:27b8b32320]
У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.[/i:27b8b32320]<HR></BLOCKQUOTE>
В каком смысле [b:27b8b32320]ВРУЧНУЮ[/b:27b8b32320]??? Надеюсь, просто в смысле возведения двойки в каждую последующую степень путем умножения? (А то мне срочно понадобится рожица "волосы дыбом"!)

moleg · Post by **moleg** » 15 Mar 2001 06:05

Originally posted by COPOKA:
[i:57e8f8456f]В каком смысле [b:57e8f8456f]ВРУЧНУЮ[/b:57e8f8456f]??? [/i:57e8f8456f]

Конечно, умножая и суммируя в столбик. Иначе, он бы до сих пор школу не закончил ... или никогда бы не закончил [img:57e8f8456f]http://www.privet.com/ubb/smile.gif[/img:57e8f8456f]

SuperMax · Post by **SuperMax** » 15 Mar 2001 06:14

<BLOCKQUOTE>quote:<HR>Originally posted by tengiz:
[i:6eb5843a76]Полицейский катер преследует наркодельцов. Скорость полицейского катера Vp в два раза выше скорости катера с преступниками Vc, причём находятся они в прямой видимости друг от друга на расстоянии S, как вдруг случился страшный туман и видимость стала 0 метров.

Задача: что должен делать полицейский, чтобы гарантированно поймать преступников? Если решение существует, найти минимальное и максимальное время, за которое можно их поймать (оказаться в одном и том же месте в одно и тоже время).

Задача несложная, однако для тех, кто никогда не решал подобные этой задачи, будет довольно интересно.[/i:6eb5843a76]<HR></BLOCKQUOTE>

Сдается мне, что надо мчать на звук мотора преступников... раз ни хрена не видать. В пределах прямой видимости звук будет слышен, туман его не поглощает. А если звук затихнет, то в ту точку, откуда звук доносился последний раз.

Tmax = S / (Vp - Vc) - если криминалы делали ноги изо всех сил по прямой...
Tmin = S / (Vp + Vc) - если криминалы развернУт катер навстречу полиции, например, решив сдаться (или пойти лоб в лоб на таран [img:6eb5843a76]http://www.privet.com/ubb/smile.gif[/img:6eb5843a76] - можно ли это считать поимкой? Наверное да, "гггады не ушли" [img:6eb5843a76]http://www.privet.com/ubb/smile.gif[/img:6eb5843a76])

(временем на поворот пренебрежем, криминалам ведь тоже придется вертеться)

Joker · Post by **Joker** » 15 Mar 2001 06:22

Решение DV — отличный пример четкой и аккуратной логики. Браво [img:a61a8c328e]http://www.privet.com/ubb/smile.gif[/img:a61a8c328e]

К решению Натали же — простой комментарий. Каждое взвешивание может дать 3 результата (левая чашка тяжелее, равенство, правая чашка тяжелее). Поэтому три взвешивания порождают 3^3=27 возможных комбинаций. предложенный алгоритм мог бы быть решением, если бы были проанализированы все 27 случаев и показано, что в каждом из них вывод о фальшивой монете однозначный. Что не имеет места быть...
Кстати, из абсолютно элементарной логики, если второе и тем более третье взвешивания не зависят от результатов первого, это не есть оптимально. Поскольку сама задачка составлена как раз оптимально (т.е. число монет нельзя увеличить, а число взвешиваний — уменьшить), то я сомневаюсь, что все 27 вариантов приведут к однозначному выводу. А проверять лень [img:a61a8c328e]http://www.privet.com/ubb/smile.gif[/img:a61a8c328e]

ChickenFromMinsk, это задачка известная, когда-то, лет *дцать назад, я ее решал в числе прочих. По-моему, она даже в книжке Перельмана есть. Разумеется, сейчас я решения не помнил, но оно совсем несложное, если быть аккуратным. Главное сообразить оставить по 4 монеты в первом взвешивании, а дальше уже все само идет как по маслу [img:a61a8c328e]http://www.privet.com/ubb/smile.gif[/img:a61a8c328e]

obormot, привет коллеге [img:a61a8c328e]http://www.privet.com/ubb/wink.gif[/img:a61a8c328e]

Joker · Post by **Joker** » 15 Mar 2001 06:34

<BLOCKQUOTE>quote:<HR>Originally posted by moleg:
[i:acdb43d18d]У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.[/i:acdb43d18d]<HR></BLOCKQUOTE> Мне более поучительной кажется известная история про юного Гаусса. Учительница в школе, желая отвязаться от непослушных восьмилетних шалопаев, дала задание сложить все числа от 1 до 100. После чего спокойно развернула газету. Но не успела надеть очки, как маленький Гаусс выдал ответ - 5050. Умение красиво мыслить — это замечательное умение [img:acdb43d18d]http://www.privet.com/ubb/smile.gif[/img:acdb43d18d]

Или другая история. Не помню уже, кому из великих в шутку задали задачку с мухой, которая стартует с носа одного велосипедиста, летит к носу другого, потом обратно к первому и так далее, пока они не встретились. Надо найти общее расстояние, которое пролетела муха. Известны скорость мухи, скорости велосипедистов, исходное расстояние между ними.
Так вот, мэтр почти мгновенно выдал правильный ответ. Но на уважительное замечание "Вы все-таки и правда очень умный! Большинство людей не понимает простоты этой задачи и начинает пытаться просуммировать ряд" он очень удивился и спросил: "А что, ее можно решить как-то иначе???" [img:acdb43d18d]http://www.privet.com/ubb/biggrin.gif[/img:acdb43d18d]

Joker · Post by **Joker** » 15 Mar 2001 06:38

О задачке Тенгиза. Если я правильно помню, линия, по которой движутся полицейские, назвается в математике "кривая преследования". Наиболее известный частный случай — когда первый объект движется по окружности, а второй догоняет его, начав движение из центра этой окружности.

Joker · Post by **Joker** » 15 Mar 2001 06:42

А куда же Zaphod пропал? Поехал на автобусе кататься? [img:cd1a30fa2d]http://www.privet.com/ubb/wink.gif[/img:cd1a30fa2d]

Joker · Post by **Joker** » 15 Mar 2001 07:30

Все же не удержался и проверил тщательно решение Натали [img:7035ad41a5]http://www.privet.com/ubb/smile.gif[/img:7035ad41a5]
Действительно, 12 монет и 2 варианта для каждой (легче или тяжелее) генерируют 24 возможных результата взвешивания. Среди которых по схеме Натали нет двух одинаковых.
Причем это решение практически оптимально, ибо всего возможных исходов взвешивания, как мы уже знаем, 27, один из них невозможен (когда все три взвешивания дают равновесие), а два оставшихся исхода "<><" и "><>" логически противоречивы.
Так что беру назад свои слова и снимаю шляпу. Молодец!

vlad3333 · Post by **vlad3333** » 15 Mar 2001 15:55

<BLOCKQUOTE>quote:<HR>Originally posted by Sasha K:
[i:4ed4dc1bfa] Vlad,
может я чего не понимаю (что поделать - старею), но "
2)складываем другую пару: 1,2,5,6-3,4,7,8.

Если в первой паре левая быля легче, и левая была легче во второй паре то фальшивй будет монетка в паре 1,2. Если вес поменялся то 3,4." - а что если фальшивая монета содержиться в паре 7,8 и она тяжелее настоящей - разве не тот же результат 1 и 2 взвешиваний будет?

[/i:4ed4dc1bfa]<HR></BLOCKQUOTE>
Я знаю, это решение неверное. В концв концов я сделал другое.

vlad3333 · Post by **vlad3333** » 15 Mar 2001 16:22

.

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

Talya · Post by **Talya** » 15 Mar 2001 17:09

Пожалуйста, вернитесь к задачке про бочку... Было заявлено что есть решение в 4 хода... Я его не знаю. Я знаю в пять, его собственно здесь уже изложили.
bee3313, изложите четерехходовку, пожалуйста.

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