|
|
Krasnaja Shapka
|
Дата : 15-05-06, Пнд, 10:23:29
док-во:
есть n баков с А_n литрами... едем по часовой стрелке... берем А_1 и пробуем доехать до А_2 если получилось, то можем виртуально слить 1 и 2 бак и оставить в месте где стоял 1 бак.... и сливаем дальше... если первый со вторым не сливается, пробуем слить 2 с 3 и т.д. сливаем пока можно...
конец слива будет знаменовать собой
1. либо точку со 100 литрами в месте k-того первоначального бака...
2. либо определенное кол-во баков в местах, таких что от одного бака нельзя доехать до другого... (т.е. ничего нельзя слить)
2 быть не может ибо иначе общий объем всех баков меньше 100 литров! (очевидно)
значит верно 1 и тогда все можно объехать с k-го бака. ибо, если начиная с k-го мы бы уперлись в отрезок который нельзя проехать, то либо пришли к пункту 2 (которого не может быть) либо нам бы удалось слить k-тый бак с предыдущим и таким образом у нас бы получилось ситуация 1, но со 100 литрами не в njv месте где стоял k-ый бак.
у грызя подобное док-во усвоилось плохо, и он смылся из аськи, поэтому привожу его на суд общественности. а для тех, кто не понял как и грызь и не верит мне на слово, пытаюсь уточнить:
едем по часовой стрелке. у нас n баков, которые стоят на m_n-тых местах (например m_1 это градусы от гринвичевского мередиана у нашего круга до первого бака... или растояние в радианах от какой-то точки окружности до 1 бака который меряется от 0 до 2пи) и в каждом a_n литров бензина. т.е. имеем систему {n, m_i, a_i}, i = 1..n.
берем 1 бак и пробуем доехать до второго, если получилось, берем 2 бак и ставим его около 1 бака (виртуально сливаем). ибо система {n, m_i, a_i} равносильна системе {n, m'_i, a'_i}, где m'_2 = m_1, а остальные m'_i = m_i для i не равно 2. (= таже система но второй бак стоит в точке первого бака)
начинаем сливать с первого (попавшегося  ) бака. если на каком-то этапе 1 с (k-1)-ым слился, а с k-ым не сливается начинаем сливать с k-ого (т.е. k-ый с (k+1)-ым)... доходим до n-ого бака... т.е. либо нам удалось слить его с предыдущими какими-то либо нет. например, нет (чтоб не вводить новых букв попусту). пробуем слить его с 1-ым баком. т.е. пробуем доехать с n-ого места до первого бака и...
1. ...если не получилось, то мы пришли к системе, у которой в s местах стоят кучи баков 1' (тут баки с 1-го по (k-1)-ый), 2' и т.д. до s' (тут n-тый бак, который мы нис кем не смогли слмть), s'>=2. при чем для любого i мы НЕ можем доехать с m'_i-го места до m'_(i+1)-го, ну и с m'_s-го до m'_1-го... в данном случае понятно, что тогда a_1 + a_2 + ... + a_n = a'_1 + a'_2 + ... + a'_s < 100... т.е. общий объем бензина меньше 100, а этого не может быть по условию задачи.
2. ...если получается - мы переставляем все баки от 1-ого до (k-1)-ого (которые мы уже слили) на место m_n к n-ому баку. далее заново пробуем к этой куче присоединить k-ый бак (в начале у нас это не получилось)... опять же если это не получилось то мы еще раз (контрольный, на всякий случай для грызя  ) оббегаем баки и пробуем чего-то с чем-то слить. если не получается, то мы приходим к ситуации 1 и говорим - грызь! ты налил меньше 100 литров в баки!
а если все оk, то в результате мы получим систему {n, m'_i, a'_i} равнозначную с первоначальной (определения равнозначности не даю - надеюсь понятно, если нет... спрашивайте), где m'_i = m_t для любого i, т.е. все баки стоят в одном месте (на месте первоначального бака t)!
все.... расписывать надоело.... работать пора... кто не согласен?
 Автор: yxo Дата : 15-05-06, Пнд, 17:18:30 В любую сторону, да ? Иначе если в канистре у старта один литр и все остальные канистры позади твоей машины то.... блин.... Значит в любую сторону
для любой стороны могут быть свои точки старта... т.е. если с 1-ой канистры можно по часовой все объехать - это не значит, что против часовой это канает |
| | Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
[ 15-05-06, Пнд, 17:24:22 Отредактировано: Krasnaja Shapka ]
[ 15-05-06, Пнд, 17:25:46 Отредактировано: Krasnaja Shapka ]
[ 15-05-06, Пнд, 17:26:10 Отредактировано: Krasnaja Shapka ] |
 |
|
|
|
Хуги
|
Дата : 15-05-06, Пнд, 12:01:08
Автор: Большой Грызь Доказать, что при любом расположении канистр и при любом распределении бензина в оных всегда можно начать движение от одной из них и совершить полный круг.
Две канистры по диаметру: в одной 1 литр, в другой 99. Начав движение от первой круг не сделаешь. |
| | Nicht Kluven klatz-klatz! |
|
|
|
|
Большой Грызь
|
Дата : 15-05-06, Пнд, 13:05:18
Автор: Хуги Дата : 15-05-06, Пнд, 19:01:08 Автор: Большой Грызь Доказать, что при любом расположении канистр и при любом распределении бензина в оных всегда можно начать движение от одной из них и совершить полный круг.
Две канистры по диаметру: в одной 1 литр, в другой 99. Начав движение от первой круг не сделаешь.
Внимательно прочитай выделенное.. Требуется доказать, что от ОДНОЙ из канистр, МОЖНО сделать круг. Читай - "от какой-то из канистр". Нигде нет требования доказать возможность круга от ЛЮБОЙ из канистр.. В твоем примере круг можно сделать, начиная с канистры, в которой 99 литров. |
| | ...everything is possible cause noone has to hide beyond the invisible... |
|
|
|
|
Krasnaja Shapka
|
Дата : 16-05-06, Втр, 03:22:16
Автор: Большой Грызь Дата : 15-05-06, Пнд, 17:29:17 Усложним задачу Укажи точно, с какого бака начинать 
ту эвриван.... не обращайте внимания.... грызь издевается...  |
| | Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно.
[ 16-05-06, Втр, 10:22:35 Отредактировано: Krasnaja Shapka ] |
|
|
|
|
Krasnaja Shapka
|
Дата : 16-05-06, Втр, 06:43:54
Автор: Большой Грызь Дата : 16-05-06, Втр, 11:03:27 В моём решении стартовая бочка находится намного нагляднее
кх...кх... не верьте ему! у меня красивше... если тока начало читать...
|
| | Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно. |
|
|
|
|
madoldman
|
Дата : 17-05-06, Срд, 00:21:29
Вот это - деиствительно классика! Я слышал штук пять решений, самое простое, на мой взгляд, следуюшее:
Предположим что имеется машина с 200 литровым баком в котором 100 литров бензина. Начинаем поездку с любой канистры в любом направлении и по дороге из каждои канистры заливаем весь бензин что там есть.
По дороге, следим за количеством бензина в баке. Около какои-то канистры, назовем ее
С(тарт) (если несколько - выбираем любую) кол-во будет минимальным. Эта канистра и есть ответ - надо начать поездку с нее.
Красота этого решения так же в том, что мы не просто доказали сушествование такой канистры, мы так же показали как ее найти! |
| |
[ 17-05-06, Срд, 07:23:25 Отредактировано: madoldman ] |
|
|
|
|
Krasnaja Shapka
|
Дата : 17-05-06, Срд, 02:45:35
Автор: madoldman Дата : 17-05-06, Срд, 07:21:29 Красота этого решения так же в том, что мы не просто доказали сушествование такой канистры, мы так же показали как ее найти!
хочу не согласиться.... это решение не очевидно... в смысле доказательства нужны, что это действительно так.... а у меня бери сливай и не парься. более того, необходимый бак точно так же находится...
|
| | Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно. |
|
|
|
|
madoldman
|
Дата : 17-05-06, Срд, 22:11:39
Автор: Krasnaja Shapka Дата : 17-05-06, Срд, 09:45:35 хочу не согласиться.... это решение не очевидно... в смысле доказательства нужны, что это действительно так....
"Решение очевидно" и "нужны доказательства" это две больших разницы!
1. Конечно, решение не очевидно, не все его находят! 
2. А вот чего этого нужны до-ва, непонятно! Вам нужно док-во что кусочно-линеиная функция (кол-во бензина в баке в зависимости от проиденного пути) имеет минимум на интервале? Так это же матан, первый семестр...
Автор: Krasnaja Shapka Дата : 17-05-06, Срд, 09:45:35 а у меня ... необходимый бак точно так же находится...
Конечно находится, но где-то через неделю упорных вычислении
|
|
|
|
|
Krasnaja Shapka
|
Дата : 19-05-06, Птн, 04:03:50
Автор: madoldman Дата : 18-05-06, Чтв, 05:11:39 1. Конечно, решение не очевидно, не все его находят!
я имел ввиду что ваши с грызем рассуждения не очевидно являются решением
Автор: madoldman Дата : 18-05-06, Чтв, 05:11:39 2. А вот чего этого нужны до-ва, непонятно! Вам нужно док-во что кусочно-линеиная функция (кол-во бензина в баке в зависимости от проиденного пути) имеет минимум на интервале? Так это же матан, первый семестр...
с матаном, то как раз все понятно.... а вот чего минимум и будет требуемым баком ясно далеко не сразу.
ну да и ладно... фиг с ними, решениями...
|
| | Если ясность вашего объяснения исключает ложное толкование, все равно кто-то поймет вас неправильно. |
|
|
|
|
Паша
|
Дата : 20-05-06, Сбт, 13:42:12
Очевидно, что решение Мадолдмана короткое, простое, понятное и чёткое. Что тут ещё доказывать, если сразу понятно, что количество бензина при подъезде к очередной бочке не может опуститься ниже нуля. |
|
|
Новости
Чаты
88:88 
