Category: авто

Category was added automatically. Read all entries about "авто".

Решение задачи о бензоколонках

На кольцевой дороге есть n заправочных станций А1, А2, ..., An. Суммарного количества бензина, имеющегося на станциях, хватает ровно на то, чтобы проехать по всей дороге. Доказать, что существует станция Ai, начиная с которой машина с пустым бензобаком может проехать по всей кольцевой дороге, подзаправляясь по пути на станциях.

Задача допускает разные решения - например, решение по индукции.
Однако самое цивилизованное, на мой взгляд, решение таково.

Вообразим мысленно, что бензобак достаточно большой, и в нем есть количество бензина Х, которого хватает на круг без дозаправок. Отправимся с произвольного места дороги, собирая по дороге бензин из колонок, и совершим один круг. Количество бензина в баке в ходе поездки то уменьшается (между колонками), то увеличивается (на колонках). Рассмотрим минимальное количество бензина в баке по ходу круга. Очевидно, это было на какой-то колонке Ai. Тогда, если мы с пустым баком начнем движение с этой колонки Ai в том же направлении, то сможем проехать весь круг, как того требует условие задачи. В самом деле, если количество бензина в нашей поездке ни разу не падало ниже указанного минимума при старте с количеством бензина Х, то при старте с пустым баком оно ни разу не упадет ниже нуля. (Если вы начертите ломаные графики уровня бензина в баке, то для этих двух поездок линии будут идти параллельно, одна ниже другой, а разница в высоте будет соответствовать исходному количеству бензина Х).

Кстати, из этого решения вытекает, что ехать можно в обе стороны (хотя, требуемые начальные колонки, конечно, могут оказаться разными).

Задача о бензоколонках

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

На кольцевой дороге есть n заправочных станций А1, А2, ..., An. Суммарного количества бензина, имеющегося на станциях, хватает ровно на то, чтобы проехать по всей дороге. Доказать, что существует станция Ai, начиная с которой машина с пустым бензобаком может проехать по всей кольцевой дороге, подзаправляясь по пути на станциях.
(Автор задачи - венгерский математик Ласло Ловас)

UPD для особо придирчивых.
Естественно, подразумевается, что бензобак машины вмещает количество бензина, необходимое для проезда по дороге.

Чужие загадки - 2

Ну вот одна задача из книжки. Истинно ли это американское мышление - вопрос к американцам :)

Человек с коллегами по работе тщательно исследовали с секундомером в руках режим работы светофоров на загруженном перекрестке. Затем человек купил старый пикап и много раз проехал через перекресток. Когда это закончилось, он был обрадован.

Объяснение - выделите мышкой.
  Человек получил повреждение спины, а медицицинские расходы могли бы серьезно повредить маленькому бизнесу его работодателя. Поэтому работодатель предложил человеку выехать на перекресток на грани зеленого света и остановиться. Если сделать это несколько раз, рано или поздно кто-то врежется в него, поехав на красный. Тогда второй водитель будет виноват и на него можно возложить лечение человека, освободив от этих выплат его работодателя. А пикап ему нужен, чтобы было побезопаснее при столкновении.

Да, это воистину замечательное решение!