Вход
Быстрая регистрация
Если вы у нас впервые: О проекте FAQ
2

Как решить задачу про круговую трассу с заправками для автомобиля?

Nasos [106K] более месяца назад

Эта задача не так проста, я не смог её решить, но решение знаю. Задачу эту я встречал у Мартина Гарднера.

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

На мой взгляд это решение - самое парадоксальное из всех решений подобных задач.

И так.

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

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

Нужно доказать следующее.

Сколько бы ни было заправок на этой трассе и как бы они ни были географически расположены на ней, и не зависимо от того, какое бы количество топлива было бы на каждой из этих заправок, всегда найдётся такая заправка, начиная с которой автомобиль, имея изначально пустой бак, мог бы заправиться там и объехать всю круговую трассу, заправляясь по ходу своего движения.

Удачи в решении.

бонус за лучший ответ (выдан): 27 кредитов
вопрос поддержали: Rakurs 19 кредитов, VVAVD 8 кредитов
5

Универсальное решение я уже написала в третий раз говорю:

Нужная заправка всегда та: "...где максимальное количество топлива".

Разбираем вариант: они разбросаны на разных расстояниях друг от друга и в них разное количество топлива. Смотрим рисунок.

Ироха Мудрейшая для БВ.

В самой дальней заправке 1/30 топлива, а в остальных 29/30 топлива поделены как им хочется. Если машина окажется у этой заправки, она никуда не уедет. Топливо кончится раньше.

Тоже самое произойдёт если: "если на всех заправках вдруг окажется равное количество топлива (или максимум его сразу на двух заправках), а разбросаны они на разных расстояниях друг от друга". Смотрим рисунок:

Ироха Мудрейшая для БВ.

Во 2-й заправке всего лишь 1/20 топлива, а в 1-й и 3-й почти всё топливо.

Если автомобиль начнёт путь от 2-й заправки с 1/20 топлива он никуда не доедет.

Условие вашей задачи не верное:

"Сколько бы ни было заправок на этой трассе и как бы они ни были географически расположены на ней, и не зависимо от того, какое бы количество топлива было бы на каждой из этих заправок, всегда найдётся такая заправка, начиная с которой автомобиль, имея изначально пустой бак, мог бы заправиться там и объехать всю круговую трассу, заправляясь по ходу своего движения".

Я доказала, что НЕ ВСЕГДА найдётся такая заправка. Не с любой нужно начинать путь, а только с той в которой больше всего топлива, и не в любую сторону, а в правильном направлении.

Совет: когда списываете задачу в интернете убедитесь, что она имеет правильное условие и имеет единственное решение, а не множество: толи да, толи нет.

автор вопроса выбрал этот ответ лучшим
Nasos [106K]
Вы не правы.
Моё "всегда найдётся такая заправка" означает, что такая заправка существует при любом раскладе. И это прекрасно доказывается. А потому Ваше утверждение "Я доказала, что НЕ ВСЕГДА найдётся такая заправка" не верно.
Об этой задаче я знал за долго то того, как к нам пришёл интернет, а потому я её не списывал с интернета.
Если будет интересно, загляните сюда позже, когда я дам ответ (если, конечно, его не даст кто-то другой).
 более месяца назад
Ироха Мудрейшая [23.8K]
У меня просто нет сил с вами спорить, раз вы не видите очевидного. На моих рисунках это очевидное расписано.  более месяца назад
Nasos [106K]
Ваши рисунки описывают лишь конкретные состояния. В задаче же сказано, что нужно доказать для ВСЕХ ситуаций, а потому никакие конкретные рисунки тут не проходят.
Задача имеет решение.
 более месяца назад
комментировать
5

Всё дело в том, что дорога представляет из себя круг. Шофёр может сделать выбор куда ему ехать: по часовой стрелке, если смотреть сверху на план, или против часовой стрелки.

Начнём с минимальных интервалов. Имеется только одна заправка. На ней много топлива, как раз столько, чтобы заправить полный бак, а с полным баком круг будет пройден.

Усложним задачу. Имеется 2 заправки. Предположим на них равное количество топлива. На каком бы расстоянии они не находились друг от друга. Всё равно топлива хватит, чтобы проехать круг, они же не могут быть дальше середины. Смотрим на скрин:

Ироха Мудрейшая для БВ.

Не важно от какой заправки начнёт двигаться автомобиль. Он будет двигаться по кратчайшему пути в сторону заправки, а не наоборот. Заправив полбака, он проедет 1/6 часть пути. Ему нужно проехать ещё 5/6. Дозаправившись на второй Ему как раз хватит до конца пути. Предположим заправок 10 и на них равное количество топлива. Нужно начать с той до которой ему хватит и дозаправляться по пути. Помним, что это круг, а не прямая линия. И выбор за водителем первого пункта:

Ироха Мудрейшая для БВ.

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

Ироха Мудрейшая для БВ.

Нужно устроить ему каверзу. На 10-й заправке залить 1/2 топлива, а на остальных по 1/18, оставшуюся половину поделить на 9:

1/2 : 9 = 1/18. И что же? Доехав до 9-й заправки, он доберёт половину топлива:

1/18 х 9 = 1/2.

Решение сей загадки весьма простое, какую часть пути проехал столько и потратил топлива, но суть круга в том, что можно начать с любой точки и ехать в двух направлениях или по часовой или против часовой стрелки.

Нереальность задачи - как он начнёт путь с пустым баком? Банально: его доставили на вертолёте, привезли на прицепе, вручную катил вместе с 3-мя пассажирами, и ещё масса вариантов.

Почему невозможно решить задачу? Нет плана, неизвестно количество заправок, на каком расстоянии они друг от друга и сколько топлива на каждой.

В третьем варианте, если водитель начнёт с 1-й или 9-й и поедет в сторону 10-й с 1/9 топлива он там и останется.

Ему надо начинать путь с той заправки где максимальное количество топлива, но в третьем варианте он может и с 1-й начать, но двигаясь в верном направлении.

Nasos [106K]
Я так и не понял, с одной стороны:
"Решение сей загадки весьма простое", а с другой стороны:
"Почему невозможно решить задачу? Нет плана, неизвестно количество заправок, на каком расстоянии они друг от друга и сколько топлива на каждой."
Так как?
 более месяца назад
Ироха Мудрейшая [23.8K]
Сейчас картинки не видно. Придётся объяснять на пальцах. Берём оптимальный вариант 3 заправки. Они все расположены на равном расстоянии друг от друга = 1/3 окружности. Считаем по часовой стрелке. 1-я заправка вверху и в ней 1/2 топлива. 2-я заправка справа круга имеет 1/4 топлива. И 3-я заправка слева круга и имеет 1/4 топлива. В сумме на всех трёх заправках «1» топлива. Хватит на весь путь. 1/2 + 1/4 + 1/4 = 1
Для понимания впишите равносторонний треугольник в круг: его вершины будут заправки.
Разбираем ситуацию со 2-й заправкой. Водителю как до 1-й против часовой стрелки, так и до 3-й по часовой стрелке, ехать 1/3 пути. 1/3 > 1/4 - ему не хватит топлива.

Разбираем ситуацию с 3-й заправкой. Водителю как до 1-й по часовой, так и до 2-й против часовой, ехать 1/3 пути. 1/3 > 1/4 - ему не хватит топлива.

С первой не разбираемся и так понятно. 1/2 > 1/3 он проедет круг. Вероятность правильного выбора 33%.
 более месяца назад
Ироха Мудрейшая [23.8K]
Резюме: не имея плана можно попасть впросак. Имея план и знания в какой заправке больше всего топлива 100%: прохождение круговой трассы.  более месяца назад
Nasos [106K]
Задача решается для любого случайного количества заправок, любой их случайной расстановки и случайного количества топлива в них. И безо всякого плана, ибо нужно только доказать, что нужная для старта заправка всегда найдётся.  более месяца назад
Ироха Мудрейшая [23.8K]
Я и доказала. Нужная заправка всегда та:
"...где максимальное количество топлива"
 более месяца назад
все комментарии (еще 5)
комментировать
Знаете ответ?
Есть интересный вопрос? Задайте его нашему сообществу, у нас наверняка найдется ответ!
Делитесь опытом и знаниями, зарабатывайте награды и репутацию, заводите новых интересных друзей!
Задавайте интересные вопросы, давайте качественные ответы и зарабатывайте деньги. Подробнее..
регистрация