31 янв. 2011 г.

Оптимальные построения

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

Очень многое в окружающем мире сделано так, чтобы работало, а не так, чтобы работало наилучшим образом. И тут я говорю не об оголтелом перфекционизме, а об очевидных мелочах, которые почему-то не стали доводить до ума. Если речь идёт о вещах/процессах, которые встречаются считанное число раз, то это нормально. Но тиражировать миллионами и миллиардам экземпляров идею, которую можно было маленьким усилием сделать лучше?.. Это не злобное вредительство, а плохая и массовая привычка.

В школах обычно решают задачи, чтобы получить ответ, а не чтобы найти хорошее решение. Иногда учителя высказываются о том, что ученик мог бы не исписывать три листа бумаги, а минутку подумать, но на это почти всегда идёт уверенный ответ: «Я же решил задачу!» (мы об этом говорили год назад и рассмотрели забавный пример)

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

Недавно fdo очень дельно высказался о начальном обучении программированию. Развивая его мысль, можно вспомнить о распространённом заблуждении, что если хочешь научить детей логике, то надо учить их логике, а если хочешь научить программированию, то надо учить программированию. Только детям скучно и сложно вникать в правила вывода секвенций и мириться с жёсткими ограничениями среды программирования. Это всё только мешает ребёнку подойти поближе к логике и алгоритмическому мышлению. А раз так, то надо предложить что-то, что можно почувствовать (но при этом оно должно требовать логического мышления и желания стать программистом). Задачи на построение - это прекрасный кандидат на эту роль (тоже недавно обсуждали). Нет, не единственный кандидат. Но уж очень удачный.

Ну а теперь вернёмся к минимальности. Недавно fdo напомнил задачку про построение перпендикуляра. А ведь есть ещё очень близкая к ней формулировка про построение параллельной прямой, поэтому я предложу сразу две задачи (в условии место с отличием выделено курсивом и пунктами (а) и (б)).

На плоскости даны прямая l и точка A. С помощью циркуля и линейки без делений постройте прямую, проходящую через точку A и (а) перпендикулярную, (б) параллельную прямой l, построив при этом минимальное число вспомогательных линий.

Что такое вспомогательные линии? Это все линии, которые вам придётся провести циркулем и линейкой, чтобы найти точки, через которые будете проводить искомую прямую. Например, классическое школьное решение задачи (а) требует три линии:
1) построим окружность с центром в точке A и большим радиусом (чтобы заведомо пересекла прямую l), так мы получим точки пересечения B и C, потратив одну линию.
2) с центрами в точках B и C построим две окружности одинакового радиуса (чтобы они пересеклись друг с другом), так мы получим точки D и E, потратив ещё две линии.
3) ну а теперь через точки D и E проводим искомую прямую.

Как видите, трёх дополнительных линий хватает, чтобы решить первую задачку (а). Но можно ли меньше? А за сколько дополнительных линий вы готовы решить вторую (б)?

Хорошего дня!

P.S.
Да, я знаю, что в школьном решении выше предложены неаккуратные формулировки. Но если писать «академичнее», то текст станет в полтора раза длиннее, а понятность его снизится. Поэтому я считаю, что при решении простых задач вполне допустимы подобные огрубления. Это облегчает понимание и уменьшает пустую трату времени.

Одновременно с этим я пропустил важный этап доказательства того факта, что построенная прямая является перпендикуляром к l, проходящим через точку А. Это очень простое упражнение, поэтому оставляю его для желающих.

28 комментариев:

  1. а) Можно двумя.
    1. Через точку A проводим окружность с центром на прямой. Она пересекает l в двух точках, одна из них пусть будет B.
    2. С центром в B проводим окружность через A. она пересечет первую окружность в еще одной точке C.
    3. AC - искомый перпендикуляр.

    ОтветитьУдалить
  2. Пока получается две линии для (а) и три линии для (б), но нутром чую, что (б) тоже можно решить с двумя линиями.

    По поводу одной линии для задачи (а), является ли такое решение корректным?

    Через точку А строим окружность, для которой прямая l является касательной и через точку касания и точку А проводим прямую, которая явлется решением задачи.

    Мне такое решение не нравится, потому что точку касания на глаз не нарисуешь, но если решения проводят мегамозги с braingames.ru то почему нет?

    ОтветитьУдалить
  3. б) Две линии.
    1. Через точку A проводим окружность с центром на прямой. Она пересекает l в двух точках, одна из них пусть будет B, а вторая - D.
    2. С центром в D проводим окружность радиуса AB, она пересечет первую окружность в двух точках с разных сторон l пусть точка C с той же стороны, что и A.
    3. AC - искомая параллельная прямая.

    ОтветитьУдалить
  4. Name_No, нет, построение такой окружности, чтобы прямая стала касательной - это неконструктивное действие, поэтому так делать нельзя.

    ОтветитьУдалить
  5. по задаче а) у меня решение, которое зависит от линейки. если у нее есть шкала с делениями и человек может считать. тогда:
    1. чертим окружность с центром в А с заведомо большим радиусом, чтобы расстояние между точками пересечения с линией было достаточным для вычисления линейкой. получаем точки B и C.
    2. делим расстояние между B и С пополам и откладываем от B. получаем точку N.
    3. AN - искомый перпендикуляр.

    ОтветитьУдалить
  6. Sergey, спасибо, что предложили эту идею. Я совсем забыл напомнить, что обычно задачи на построение предполагают, что линейка не имеет делений (сейчас это явно указано в тексте задачки).

    Rostik, есть одна важная тонкость в задаче (а), поэтому можно сказать, что задача решена частично.

    ОтветитьУдалить
  7. Илья Весенний:
    В чем тонкость? В доказательстве минимальности или доказательстве правильности?
    От выбора центра первой или второй окружности правильность построения при идеальных инструментах не зависит.
    Формально нужно пункт 1. писать так:
    Выберем произвольную точку O на l, проведем окружность с центром в O и радиусом OA.
    От выбора центра второй окружности из двух точек пересечения тоже ничего не зависит.

    ОтветитьУдалить
  8. Да нет, речь не о доказательстве минимальности или правильности. Речь о том, что возможны ситуации, в которых точки A и C совпадут, что не позволит провести искомую прямую.

    ОтветитьУдалить
  9. Илья Весенний
    Первая и вторая окружность имеют как минимум одну общую точку по построению.
    Следовательно они могут либо касаться либо пересекаться в двух точках, либо совпадать.
    Совпасть они могут только тогда когда B совпадет с O, но B принадлежит первой окружности по построению, то есть совпадение возможно только тогда когда первая окружность вырождается в точку, что невозможно, т.к. ее радиус OA отличен от нуля (A не принадлежит l по условию).
    O и B лежат на l по построению. Точка касания окружностей лежит на прямой, проходящей через их центры. Если бы A была точкой касания наших окружностей, то она лежала бы на l, что противоречит условию. Следовательно, две построенные нами окружности пересекаются в двух точках. Одна из них по построению - A. Вторая - C.

    ОтветитьУдалить
  10. Rostik:
    >>A не принадлежит l по условию
    я не вижу такого условия.

    ОтветитьУдалить
  11. Аха, да, меня сбила стандартная формулировка таких задач.
    Тогда для случая точки на прямой решение:
    1. Выберем произвольную точку О вне прямой и проведем окружность проходящую через А с центром в О, она пересечет прямую в еще одной точке В.
    2. Проведем прямую ОВ, она пересечет окружность в еще одной точке С.
    3. АС - перпендикуляр к l. (CAB опирается на диаметр).

    ОтветитьУдалить
  12. Стремительно задачки разобрали :) Уважаю!

    Вот придумать бы что-нибудь, чтобы желающие самостоятельно порешать, но случайно открывшие заметку, не прочитали решение раньше времени. Хочется сохранить свободный доступ к комментариям заметки, но как-то предупредить читателя об опасности. Что думаете об этом? Или проблема случайного прочтения решения надумана?

    ОтветитьУдалить
  13. Илья Весенний:
    большинство читает решение других уже после обдумывания и придумывания своего решения. да и постить решение, которое уже было упомянуто не имеет смысла. так что, я думаю, что и так хорошо.

    ОтветитьУдалить
  14. Следует заметить, что решение задачи б) с двумя линиями, предложенное Rostik, не совсем корректно - если в первом пункте через точку A будет проведена окружность с центром в пересечении перпендикуляра из точки A и прямой - то построение не даст прямой - точка C совпадет с A.

    ОтветитьУдалить
  15. Строятся две окружности с центрами на прямой и радиусами большими чем расстояние/2 между прямыми, по этим окружностям строим и перпендикуляр и параллель.

    ОтветитьУдалить
  16. сорри, условие невнимательно прочел...

    ОтветитьУдалить
  17. А вот мне кажется или (без лишней академичности) можно найти с помощью циркуля (меняя его раствор) точку, находящуюся на прямой и ближайшую к заданной? И перпендикуляр провести через эту точку? Тогда достаточно одной линии.

    Для задачи б) в этом случае чертим дугу того же радиуса, но из другой точки на прямой. Касательная к дуге, проходящая через заданную точку и будет параллельной.

    Или это слишком вольные решения?

    ОтветитьУдалить
  18. SpectrosKop, эти решения нельзя назвать конструктивными. Я согласен, что это не самое очевидное возражение, но в задачах на построения давно сложился набор техник, которыми можно пользоваться (кстати, в данной заметке была ссылка на перечень этих техник). И эти техники хороши своей элементарностью. А искать такой раствор циркуля, чтобы окружность касалась - это какое-то итерационное действие, которое невозможно выполнить элементарным путём.

    ОтветитьУдалить
  19. строим оружность, с центром в точке, касающуюся прямо. радиус к точке касания вроде как перпендикуляр к прямой.

    ОтветитьУдалить
  20. прошу прощения, "касающуюся прямой" имел ввиду

    ОтветитьУдалить
  21. Илья, этот ваш конкурс на поиск самого оптимального и самого изобретательного решения известной и уже решенной задачи напомнил мне следующую забавную историю.

    Вы когда-нибудь пробовали писать авторучкой лежа на кровати, держа авторучку пером вверх? Авторучка, если она даже шариковая, перестает писать через короткое время - нетрудно понять почему. Зная об этом, умные и предприимчивые Американцы заранее изобрели для своих будущих астронавтов космическую авторучку, которая могла бы писать безотказно в невесомости. После того как Американцы наконец слетали в космос и затем обнаружили, что советские космонавты и здесь их переплюнули своей изобретательностью, им пришлось с неохотой признать это факт и переключиться на советскую космическую авторучку, т. е. карандаш.

    Когда вы смотрите в зеркало и машете весело правой рукой, ваше изображение машет вам в ответ с не меньшей улыбкой, но только левой рукой. Но почему-то оно не переворачивается головой вниз, а ногами вверх. Многие считают, что зеркало совсем не переворачивает лево на право, а скорее выворачивает наизнанку. Если так, то почему изображение черной перчатки с белым подбоем не выглядит белой перчаткой с черным подбоем? Какую самую простую оптическую систему вы можете предложить, которая переворачивает изображение с ног на голову?

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

    ОтветитьУдалить
  22. Должности и звания подписантов посмотрите.Много ли среди них малограмотных?

    ОтветитьУдалить
  23. Можно управиться за 1 линию.
    1) Складываем лист пополам перпендикулярно начальной линии, причем точка не должна находиться на месте сгиба
    2) протыкаем острым концом циркуля точку А.
    3) разворачиваем лист и рисуем линию между т.А и отверстием

    ОтветитьУдалить
  24. Добавление: сложить лист пополам перпендикулярно можно на просвет, совмещением линий.

    ОтветитьУдалить
  25. dp, Вы пишете: "строим окружность, с центром в точке, касающуюся прямой". Но вопрос именно в том, как построить такую окружность. Это можно сделать, например, итерационно (увеличивая радиус, если окружность не пересекает прямую, или уменьшая радиус, если окружность пересекает прямую в двух точках). Если мы не ограничены в числе итераций, то сможем сколь угодно близко подойти к искомому радиусу. Но такой процесс всё же трудно назвать построением с одной дополнительной линией, так как линий придётся построить столько же, сколько будет итераций.

    Arthur Baraov, спасибо за подборку хороших вопросов!

    Ольга Неклеса, к какому сообщению относится Ваш комментарий?

    homyak2, известно ли достоверно, что бесконечная плоскость, которую складывают пополам, является прозрачной? Если это не так, то совместить линии, глядя на просвет, не получится.

    ОтветитьУдалить
  26. Илья, плоскость ни при чем. Я предложил решение-хак для обычного тетрадного листа :)

    Но все же если мы имеем дело с "непрозрачной плоскостью", то решение может быть таким: складываем по нарисованной линии пополам, а потом еще раз пополам, чтобы края сгиба сошлись. Затем разворачиваем "непрозрачную плоскость" получаем что то вроде креста, складываем его пополам, но не по первоначальному сгибу, а по второму, прокалываем, разворачиваем, рисуем линию между проколом и точкой - все, параллельная прямая готова, начальное требование - минимизация линий, выполнено, так как "потрачена" всего одна - непосредственно на прорисовку параллельной линии.

    ОтветитьУдалить
  27. Ну да, неплохо получается. Конечно, операции сгибания бесконечной плоскости не входят в список допустимых, но решение забавное, спасибо!

    ОтветитьУдалить
  28. Анонимный06.02.2011, 10:54

    Решение полностью совпало с Rostik-ом, но хотел бы отметить следующее, при необходимости построить (а)и (б) в одном решении. Доп. построений 3... или полтора доп. построения на пункт, вот она где оптимизация :-D
    PS: Навевает старую детскую загадку: в которой, чтобы поместить жирафа в холодильник, необходимо предварительно извлечь оттуда бегемота :-)

    ОтветитьУдалить