Задачки-2
-
- Уже с Приветом
- Posts: 196
- Joined: 07 Jan 2000 10:01
- Location: Gainesville, FL, US
Задачки-2
Originally posted by Joker:
[i:5ee2c45827]Кстати, из моих студентов-второкурсников за 15 лет никто не был в состоянии решить подобную задачу за разумное время (ну, скажем, за час) - точнее, один парень мог, но это приятное исключение [img:5ee2c45827]http://www.privet.com/ubb/smile.gif[/img:5ee2c45827] мы на вундеркиндов не рассчитываем...[/i:5ee2c45827]
У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.
[i:5ee2c45827]Кстати, из моих студентов-второкурсников за 15 лет никто не был в состоянии решить подобную задачу за разумное время (ну, скажем, за час) - точнее, один парень мог, но это приятное исключение [img:5ee2c45827]http://www.privet.com/ubb/smile.gif[/img:5ee2c45827] мы на вундеркиндов не рассчитываем...[/i:5ee2c45827]
У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.
-
- Уже с Приветом
- Posts: 881
- Joined: 22 Dec 2000 10:01
- Location: USA
Задачки-2
<BLOCKQUOTE><font size="1" face="Arial">quote:</font><HR><font face="Arial" size="2">Originally posted by Nataly:
[i:dcda700c65]COPOKA,
С симетрией не получается, если все проверять по 2 раза, то фальшивая монетка не находится.
[/i:dcda700c65]</font><HR></BLOCKQUOTE>
(вздох) - Точно. После поста vlad3333 очевидно, что некоторые случаи требуют, чтобы что-то взвешивалось 3 раза... Жаль. [img:dcda700c65]http://www.privet.com/ubb/frown.gif[/img:dcda700c65]
[i:dcda700c65]COPOKA,
С симетрией не получается, если все проверять по 2 раза, то фальшивая монетка не находится.
[/i:dcda700c65]</font><HR></BLOCKQUOTE>
(вздох) - Точно. После поста vlad3333 очевидно, что некоторые случаи требуют, чтобы что-то взвешивалось 3 раза... Жаль. [img:dcda700c65]http://www.privet.com/ubb/frown.gif[/img:dcda700c65]
-
- Уже с Приветом
- Posts: 881
- Joined: 22 Dec 2000 10:01
- Location: USA
Задачки-2
<BLOCKQUOTE><font size="1" face="Arial">quote:</font><HR><font face="Arial" size="2">Originally posted by moleg:
[i:27b8b32320]
У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.[/i:27b8b32320]</font><HR></BLOCKQUOTE>
В каком смысле [b:27b8b32320]ВРУЧНУЮ[/b:27b8b32320]??? Надеюсь, просто в смысле возведения двойки в каждую последующую степень путем умножения? (А то мне срочно понадобится рожица "волосы дыбом"!)
[i:27b8b32320]
У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.[/i:27b8b32320]</font><HR></BLOCKQUOTE>
В каком смысле [b:27b8b32320]ВРУЧНУЮ[/b:27b8b32320]??? Надеюсь, просто в смысле возведения двойки в каждую последующую степень путем умножения? (А то мне срочно понадобится рожица "волосы дыбом"!)
-
- Уже с Приветом
- Posts: 196
- Joined: 07 Jan 2000 10:01
- Location: Gainesville, FL, US
Задачки-2
Originally posted by COPOKA:
[i:57e8f8456f]В каком смысле [b:57e8f8456f]ВРУЧНУЮ[/b:57e8f8456f]??? [/i:57e8f8456f]
Конечно, умножая и суммируя в столбик. Иначе, он бы до сих пор школу не закончил ... или никогда бы не закончил [img:57e8f8456f]http://www.privet.com/ubb/smile.gif[/img:57e8f8456f]
[i:57e8f8456f]В каком смысле [b:57e8f8456f]ВРУЧНУЮ[/b:57e8f8456f]??? [/i:57e8f8456f]
Конечно, умножая и суммируя в столбик. Иначе, он бы до сих пор школу не закончил ... или никогда бы не закончил [img:57e8f8456f]http://www.privet.com/ubb/smile.gif[/img:57e8f8456f]
-
- Уже с Приветом
- Posts: 1309
- Joined: 03 Nov 1999 10:01
- Location: West End, Surrey, England
Задачки-2
<BLOCKQUOTE><font size="1" face="Arial">quote:</font><HR><font face="Arial" size="2">Originally posted by tengiz:
[i:6eb5843a76]Полицейский катер преследует наркодельцов. Скорость полицейского катера Vp в два раза выше скорости катера с преступниками Vc, причём находятся они в прямой видимости друг от друга на расстоянии S, как вдруг случился страшный туман и видимость стала 0 метров.
Задача: что должен делать полицейский, чтобы гарантированно поймать преступников? Если решение существует, найти минимальное и максимальное время, за которое можно их поймать (оказаться в одном и том же месте в одно и тоже время).
Задача несложная, однако для тех, кто никогда не решал подобные этой задачи, будет довольно интересно.[/i:6eb5843a76]</font><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])
(временем на поворот пренебрежем, криминалам ведь тоже придется вертеться)
[i:6eb5843a76]Полицейский катер преследует наркодельцов. Скорость полицейского катера Vp в два раза выше скорости катера с преступниками Vc, причём находятся они в прямой видимости друг от друга на расстоянии S, как вдруг случился страшный туман и видимость стала 0 метров.
Задача: что должен делать полицейский, чтобы гарантированно поймать преступников? Если решение существует, найти минимальное и максимальное время, за которое можно их поймать (оказаться в одном и том же месте в одно и тоже время).
Задача несложная, однако для тех, кто никогда не решал подобные этой задачи, будет довольно интересно.[/i:6eb5843a76]</font><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])
(временем на поворот пренебрежем, криминалам ведь тоже придется вертеться)
-
- Уже с Приветом
- Posts: 2180
- Joined: 13 Aug 1999 09:01
- Location: Tomsk, Russia --> Bay Area, CA, USA
Задачки-2
Решение 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]
К решению Натали же — простой комментарий. Каждое взвешивание может дать 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]
-
- Уже с Приветом
- Posts: 2180
- Joined: 13 Aug 1999 09:01
- Location: Tomsk, Russia --> Bay Area, CA, USA
Задачки-2
<BLOCKQUOTE><font size="1" face="Arial">quote:</font><HR><font face="Arial" size="2">Originally posted by moleg:
[i:acdb43d18d]У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.[/i:acdb43d18d]</font><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]
[i:acdb43d18d]У нас учительница по математике рассказывала, что когда в одном из ее классов начали изучать геометрическую програссию, она, как обычно, привела пример с зернами на шахматной доске (помните, наверное). Так один ученик, кстати не отличавшийся хорошим прилежанием, провел все 5 уроков, вручную пересчитывая количество зерен. И ведь посчитал!
Это просто, вспомнилось.[/i:acdb43d18d]</font><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]
-
- Уже с Приветом
- Posts: 2180
- Joined: 13 Aug 1999 09:01
- Location: Tomsk, Russia --> Bay Area, CA, USA
Задачки-2
О задачке Тенгиза. Если я правильно помню, линия, по которой движутся полицейские, назвается в математике "кривая преследования". Наиболее известный частный случай — когда первый объект движется по окружности, а второй догоняет его, начав движение из центра этой окружности.
-
- Уже с Приветом
- Posts: 2180
- Joined: 13 Aug 1999 09:01
- Location: Tomsk, Russia --> Bay Area, CA, USA
Задачки-2
Все же не удержался и проверил тщательно решение Натали [img:7035ad41a5]http://www.privet.com/ubb/smile.gif[/img:7035ad41a5]
Действительно, 12 монет и 2 варианта для каждой (легче или тяжелее) генерируют 24 возможных результата взвешивания. Среди которых по схеме Натали нет двух одинаковых.
Причем это решение практически оптимально, ибо всего возможных исходов взвешивания, как мы уже знаем, 27, один из них невозможен (когда все три взвешивания дают равновесие), а два оставшихся исхода "<><" и "><>" логически противоречивы.
Так что беру назад свои слова и снимаю шляпу. Молодец!
Действительно, 12 монет и 2 варианта для каждой (легче или тяжелее) генерируют 24 возможных результата взвешивания. Среди которых по схеме Натали нет двух одинаковых.
Причем это решение практически оптимально, ибо всего возможных исходов взвешивания, как мы уже знаем, 27, один из них невозможен (когда все три взвешивания дают равновесие), а два оставшихся исхода "<><" и "><>" логически противоречивы.
Так что беру назад свои слова и снимаю шляпу. Молодец!
-
- Уже с Приветом
- Posts: 240
- Joined: 04 Dec 2000 10:01
Задачки-2
<BLOCKQUOTE><font size="1" face="Arial">quote:</font><HR><font face="Arial" size="2">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]</font><HR></BLOCKQUOTE>
Я знаю, это решение неверное. В концв концов я сделал другое.
[i:4ed4dc1bfa] Vlad,
может я чего не понимаю (что поделать - старею), но "
2)складываем другую пару: 1,2,5,6-3,4,7,8.
Если в первой паре левая быля легче, и левая была легче во второй паре то фальшивй будет монетка в паре 1,2. Если вес поменялся то 3,4." - а что если фальшивая монета содержиться в паре 7,8 и она тяжелее настоящей - разве не тот же результат 1 и 2 взвешиваний будет?
[/i:4ed4dc1bfa]</font><HR></BLOCKQUOTE>
Я знаю, это решение неверное. В концв концов я сделал другое.
-
- Уже с Приветом
- Posts: 419
- Joined: 11 Dec 2000 10:01
- Location: MA, USA
Задачки-2
Пожалуйста, вернитесь к задачке про бочку... Было заявлено что есть решение в 4 хода... Я его не знаю. Я знаю в пять, его собственно здесь уже изложили.
bee3313, изложите четерехходовку, пожалуйста.
Удачи. Талья.
bee3313, изложите четерехходовку, пожалуйста.
Удачи. Талья.