Две геометрические задачки, которые попадались на собеседовании, и где они обитают

    Когда программист ходит на собеседования, то рано или поздно сталкивается с математическими задачками. В этом посте я рассмотрю две геометрические задачи и их решения.

    Задача №1


    Первая задача звучит так:
    Есть прямоугольник, в нем вырезали кружок, сколько прямых можно провести,
    которые разделят на равновеликие части получившуюся фигуру.
    Решение:
    Равновеликие фигуры — это фигуры, которые имеют одинаковые площади. Помним, что круг делится пополам в случае прохождения прямой через его центр. Прямоугольник делится пополам линиями, проходящими через его центр пересечения диагоналей. Ну и капитан очевидность нам подсказывает, что мы получим равновеликие части фигуры, если проведем прямую через центры прямоугольной фигуры и вырезанной круглой части. Такая прямая одна, если центры прямоугольника и круга не совпадают. В случае совпадения центров фигур, количество прямых будет бесконечное множество. Сделано.



    Задача №2


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

    Решение:
    Если еще раз внимательно прочитать условие, то можно обратить внимание на то, что четыре точки не лежат на одной плоскости. Эта информация сокращает количество возможных расположений точек, удовлетворяющих условию равноудаленности от искомой плоскости:

    1) три точки лежат по одну сторону от рассматриваемой плоскости, четвертая — по другую;
    2) по каждую сторону от плоскости лежат по две точки.

    Рассматривая первый случай, сразу же исключается возможность расположения трех точек на одной прямой, поскольку тогда через эти три точки и четвертую можно будет провести плоскость, а это противоречит условию задачи. Итак, искомая плоскость должна быть равноудалена от трех выбранных точек (например, A, B и C), а значит она должна быть параллельна плоскости ABC, проведенной через эти точки. Но искомая плоскость также должна быть равноудалена от точки D, поэтому проводим плоскость, параллельную плоскости ABC через середину перпендикуляра DP, опущенного из точки D на плоскость ABC.



    Относительно четырех точек получим четыре искомые плоскости, равноудаленные от этих точек и такие, что по одну сторону от них расположена только одна точка, а по другую — оставшиеся три.

    Приступим к рассмотрению второго случая.

    Пусть точки A и B лежат по одну сторону от искомой плоскости, а точки C и D — по другую. Так как искомая плоскость равноудалена от точек A и B, то она должна быть параллельна прямой AB. И поскольку эта плоскость равноудалена от точек C и D, то она должна быть параллельна прямой CD. Точки A, B, C и D не лежат в одной плоскости, то прямые AB и CD — скрещивающиеся.

    Определение скрещивающихся прямых
    Две прямые называются скрещивающимися, если они не лежат в одной плоскости.



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

    Теорема
    Через каждую из двух скрещивающихся прямых проходит плоскость, параллельная другой прямой, и притом только одна.

    Таким образом, существуют три плоскости, равноудаленные от данных четырех точек и такие, что по одну сторону находятся две из четырех точек, а по вторую сторону — остальные две(AB и CD, AC и BD, AD и BC).

    Итак, получаем общее число плоскостей, равноудаленных от данных четырех точек, равно семи (четыре при рассмотрении первого случая и три — второго случая). Вторая задача решена.

    Каково было мое удивление, когда через полтора месяца, как мне попалась эта задача, я наткнулась в интернете на книжку “Неэлементарные задачи в элементарном изложении” А.М. Яглом и И.М. Яглом 1954 года издания, которая содержит школьные олимпиадные задачи.



    Задача про плоскости в этом сборнике идет под номером один. Так что кому интересно, могут ознакомиться с другими задачами и решениями.

    Вот так всегда: учишься в школе, поступаешь в институт, а в институте говорят “забудь, что учил в школе”, затем идешь работать и слышишь “забудь, чему тебя учили в институте”, потом идешь на какое-то собеседование, а тебе дают задачку из школьных олимпиад =) Как ни крути, а знания лишними не бывают.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 59
    • +9
      на самом деле, в первой задаче линий будет бесконечное множество в том случае, если центры кружка и прямоугольника совпадают.
      • 0
        Спасибо за замечание
        • +16
          Более того, их будет бесконечное множество даже тогда, когда центры не совпадают. Другое дело, что построить такую прямую будет не просто.
          • +2
            В случае, если секущую брать параллельно сторонам прямоугольника, довольно просто получить точное решение.
            • +1
              Построить прямую — это не «другое дело». Это другая задача. В данной задаче спрашивается количество таких прямых и не более того. Не уверен, инженерное это было интервью или научное, но для инженера неверная постановка или понимание задачи — серьёзная проблема.

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

              Интересно, что это было за интервью.
              • 0
                Не соглашусь с первым абзацем. Автор статьи привел один из вариантов решения, а значит наличие способа построить такую прямую как минимум приветствуется.
                • 0
                  Угу. То есть то, что автор, сконцентрировавшись на построении прямой, пришла к неправильному ответу вас не смущает. *sarcasm*

                  Почему у меня глаз сразу зацепился за «подковерное» изменение задачи — в современном программостроении очень трудно найти проект сложнее Hello World в котором это не сыграло бы ощутимую роль. Чаще всего — негативную.
            • +15
              Да даже если центры не совпадают, мы же не обязаны через центр круга линию проводить, в условии ведь про это не сказано. Допустим, сдвинули ту точку, что внутри круга, чуть выше его центра, разница площадей внутри круга перераспределилась, компенсировали эту разницу сдвигом точки внутри прямоугольника чуть ниже центра. В итоге получается бесконечное множество точек. Поправьте, если ошибаюсь.
            • +35
              В первой задаче будет бесконечное число таких линий, делящих фигуру на две с равными площадями, в любом случае, а не только при совпадении центров. Доказать это сложнее.проведите линию под любым углом и начните ее двигать параллельно самою себе. Интегралы слева и справа(или сверху снизу) в определенный момент будут неизбежно равны
              • 0
                del
                • –1
                  И все эти прямые будут проходить через «центр масс», который будет где-то на отрезке между центрами прямоугольника и круга?
                  • +2
                    Неа, так это не работает. Легко можно проверить на треугольнике: медианы проходят через центр масс и делят площадь пополам, а вот прямые, проходящие через него параллельно сторонам, делят площадь в отношении 4:5.
                    • –1
                      Неа, так это не работает
                      Я и не утверждал, что все прямые, проходящие через центр масс, делят площадь пополам.
                      Я преполагал обратное (не противоположное): все прямые, делящие площадь пополам, проходят через центр масс. (Доказать этого я не могу, так что это тоже может быть неверно.)
                • +29
                  Первая задача не правильно решена. Описанная прямая является решением. Но не единственным.
                  Возьмем произвольную прямую. Пересечение одной полуплоскости, ограничеваемой этоий прямой, с прямоугольником с дыркой назовем фигурой А, другой полуплоскости фигурой Б. Будем двигать эту прямую вдоль нормали к ней, и рассмотрим разность площадей А и Б. очевидно что она меняет знак, а значит есть точка где разность равна нулю.

                  Чуть-чуть не успел.
                  • +2
                    Ваша формулировка аккуратней. Снимаю шляпу. :)
                    • +3
                      Что-то мне кажется, я написала статью, комментарии к которой будут полезнее, чем сама статья ))
                      • +2
                        Добавьте к формулировке первой задачи дополнительное условие « с помощью циркуля и линейки постройте прямую линию ...» и далее по тексту.
                        • +2
                          Будут пол дня центр окружности искать.
                          Сейчас вообще в школе проходят задачи с циркулем и линейкой?
                          • 0
                            Квадратура круга? Жена (учитель математики ) утверждает что только факультативно. Правда эти сведения устарели лет на 15. Так что не знаю как сейчас, но собеседование вроде не для школьников?
                            • 0
                              Факультативно? Вообще-то это одна из трёх знаменитых задач циркулем и линейкой не решаемых. Хоть факультативно, хоть по программе.
                              • 0
                                Квадратура не решаема, а центр окружности циркулем и линейкой находится в рамках школьной программы.
                                • +1
                                  Решение квадратуры круга тоже есть, но оно секретно. Его объясняют только на факультативе в школе. Это секретный способ узнать — ходил ли человек на факультатив, а слух о неразрешимости запущен специально для этой цели :)
                                  • 0
                                    Видимо я не ходил, да.
                                    • 0
                                      Квадратриса не тайна.
                                      • +1
                                        Построите её при помощи линейки и циркуля?
                                        • +3
                                          Не построю, даже Чак Норрис не построит.
                                          • 0
                                            Ему для этого не нужны циркуль и линейка.
                            • –1
                              Добавьте к формулировке первой задачи дополнительное условие «… прямых, проходящих через центр прямоугольника ...» и далее по тексту. Тогда Ваш ответ станет корректным.
                          • –2
                            а вообще неважно какой размер прямоугольника и круга?
                            если круг очень маленький, а прямоугольник большой, то IMHO вообще неважно где круг.
                            • +1
                              Соотношение размеров не существенно. Качественная разница появится только тогда, когда круг выродится в точку.
                          • +7
                            Это все конечно интересно, но что показывает навык решения подобных геометрических задач? Разве что работа будет напрямую связана с конструкциями, архитектурой?
                            • –1
                              Показывает не навык решения, а навык поиска решения.
                              • +1

                                Навык? Наличие навыка показывает умение решать шаблонные задачи. Тут, скорее, я бы заподозрил попытку проверить умеет ли человек решать как раз нетиповые задачи (исходя из предположения, что большинство соискателей вышли из школьно-студенческого возраста и олимпиадные навыки успешно утратили со временем). Но, боюсь, это слишком сложная конспирология и большинство просто решило, — а почему бы и нет. И, как ни странно, оно даже так работает :). Полезно, если у вас в работе, конечно, встречаются нетиповые задачи. Если не встречаются и нужно тупое производство шаблонного кода с незначительными вариациями, то да, это всё лишнее, а подобный работник будет overqualified, быстро заскучает и уйдёт.

                                • 0
                                  Полезно, если у вас в работе, конечно, встречаются нетиповые задачи.

                                  Много таких. Ок, возьму на вооружение =)

                                • 0
                                  Многие топ компании нанимают работника не особо принимая в расчет его текущие навыки, а учитывая далекую перспективу. Поэтому иногда выбираются задачи не особо связанные с кодом, но больше с мышлением и логикой.
                                  Решение подобной задачи покажет, может ли человек разбираться с незнакомыми поставленными задачами.
                                • +1

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


                                  Мои не совсем трезвые и почти самостоятельные размышления по задачам

                                  Задача 1.
                                  Легко увидеть, что через любую точку на периметре прямоугольника (при условии что вычитаемый круг находится полностью внутри прямоугольника, не касаясь его сторон) можно провести только одну прямую, которая разделит фигуру пополам.
                                  Кстати, если для каждой точки периметра P провести прямую, делящую фигуру пополам, найти вторую точку её пересечения с периметром прямоугольника, и найти точку Q середины отрезка прямой между данными двумя точками… то если точка P пробегает множество всех точек периметра прямоугольника, должна получиться замкнутая фигура из множества точек Q… Интересно, как выглядит данная фигура? :)
                                  Впрочем, мне кажется, надо меньше расстояния по периметру пробегать, но это будет не половина периметра — надо провести через начальную точку P0 прямую, делящую фигуру пополам, определить вторую точку пересечения данной прямой с периметром P1, а затем пробегать по периметру от P0 до P1 в любом направлении :)
                                  В любом случае ответ я бы дал так: бесконечное количество прямых, соизмеримое с [бесконечным] количеством точек на периметре прямоугольника...


                                  Задача 2.
                                  Из того, что 4 точки не лежат на одной плоскости, сразу следует вывод: эти точки образуют объёмную фигуру с ненулевым объёмом, т.е. тетраэдр.
                                  Соответственно, следует искать множество точек, которые будут равноудалены от всех вершин данного тетраэдра.
                                  Надо полагать, что все плоскости, удовлетворяющие условиям задачи, должны пересекаться с этим тетраэдром, и ни одна точка снаружи тетраэдра не будет равноудалена от всех его вершин.
                                  Как именно пересекаться? Совершенно очевидно, что любое ребро тетраэдра, пересекаемое искомой плоскостью, будет делиться ею ровно пополам, иначе нарушится условие равноудалённости.
                                  Пожалуй, надо провести высоту из вершины к противоположной грани, и через середину этой высоты провести плоскость, параллельную той грани, к которой проводили высоту.
                                  Значит, ответ (предварительный) будет таков: 4 (по количеству вершин тетраэдра)


                                  На этом мои самостоятельные мысли по задаче 2 закончились, и я воспользуюсь тем, в тексте указано наличие 2-х разных случаев (4+3) и окончательный ответ 7 :)
                                  Мои мысли дали только 1-й случай, когда по одну сторону плоскости лежит одна точка, а по другую — три. Значит, я упустил случай, когда две точки по одну сторону искомой плоскости и две по другую.
                                  Что ж, давайте подумаем, как проводить плоскость через тетраэдр по 2-му случаю… Бррр, как тяжело на нетрезвую голову представить такие варианты, но я таки справился :) Всё отличие в том, что вместо 3-х рёбер искомая плоскость будет пересекать 4 ребра. А каково количество различных сочетаний по 4 ребра из 6? Ага, 6!/(4!(6-4)!) = 56/2! = 30/2 = 15… Э-э-э, ошибка, 15 — это много… Загуглим слово "тетраэдр" и посмотрим картинки… А-а-а, ведь надо брать не любые 4 ребра, а только такие, чтобы оставшиеся 2 ребра не имели общих точек… А сколькими способами можно взять 2 ребра, чтобы они не имели общих точек? Ну да, если точки пронумеровать: 0,1,2,3, то "вручную" считаем комбинации — (0+1; 2+3), (0+2; 1+3), (0+3; 1+2), и всё! Ровно три "недостающих" комбинации и получили :)) Ура!!!
                                  Ответ: 4 + 3 = 7 штук!

                                  • +1
                                    Спрячьте решения под спойлер, пожалуйста. Не то чтобы меня сильно затруднила првая задача, но поясняющий рисунок я увидел раньше, чем успел начать думать.
                                    • +6
                                      В первой задаче:
                                      1)Находим центры прямоугольника и круга.
                                      2)Соединяем центры отрезком. На этом отрезке находится центр тяжести получившейся фигуры. (его просто вычислить, но одного циркуля с линейкой скорее всего не хватит)
                                      Через этот центр можно провести бесконечное количество секущих.
                                      • +1
                                        Поправка: заменить слово отрезок на слово прямая, либо луч из центра круга.
                                        • +1
                                          Для произвольной фигуры это не верно, а для данного случая совершенно не очевидно. Подозреваю, что тоже не верно.
                                          • +1
                                            Вы правы. Получились равновесные секущие, а не равновеликие.
                                            Однако в большинстве случаев существуют точки на… прямоугольника, через которые можно провести бесконечное количество равновеликих секущих.
                                            • +1
                                              * В большинстве случаев существуют точки на средних линиях прямоугольника, через которые можно провести бесконечное количество равновеликих секущих.
                                              • –1
                                                Сразу подумал про центр масс. Разве равновесные в данном случае не равновеликие? Ведь прямоугольник, насколько я понял, однородный и следовательно масса прямо пропорциональна площади. Поэтому ваше решение считаю верно.
                                                • +1
                                                  К сожалению, это не так. Получившаяся фигура неправильная, и то, что применимо к прямоугольнику, к ней не применимо.
                                                  При определении центра масс нужно оперировать такими понятиями как радиус-вектор/момент силы тяжести/плечо. Можно уравновесить абсолютно разные массы, если подобрать плечи разной длины.
                                                  Сделал на скорую руку иллюстрацию. Средние линии обозначены серым цветом. Равновеликие — красным. При перемещении круга внутри красного правого нижнего прямоугольника центр масс будет смещаться (так как будут меняться радиус-векторы), а равновеликие секущие — нет (так как площадь правого нижнего красного прямоугольника останется постоянной).
                                                  Нетрудно заметить, что если точки X и Y не принадлежат кругу, то через каждую из них можно провести бесконечное количество равновеликих секущих. (но не равновесных!)
                                                  image
                                                  • 0
                                                    Согласен тупанул
                                                    • 0
                                                      Тут больше подходит идея о прохождении функции через ноль при смене знака. Выше уже такую высказали.
                                            • 0
                                              А зачем в задаче 2 вариант 2? По моему это тот же вариант 1 «вид сбоку», не?
                                              Из 4 точек не лежащих в одной плоскости можно выбрать 3 не лежащих на одной прямой и посторить по ним плоскость из варианта 1.
                                              Или я что-то упускаю?
                                              • +2
                                                1) три точки лежат по одну сторону от рассматриваемой плоскости, четвертая — по другую;
                                                2) по каждую сторону от плоскости лежат по две точки.
                                                Я не могу представить, как можно спутать эти варианты или преобразовать один в другой. В этих вариантах совершенно разные построения.
                                                • 0
                                                  Эммм…
                                                  Мы искомую плоскость проводим, ее нет. Изначально у нас есть только 4 точки и все.
                                                  Поэтому я предположил такой алгоритм:
                                                  — берем 3 любые точки (они не могут лежать на 1 прямой, иначе все 4 точки окажутся в одной плоскости)
                                                  — строим по этим 3 точкам плоскость
                                                  — строим от 4 точки перпендикуляр до этой плоскости
                                                  — искомая плоскость — по центру перпендикуляра (параллельно 3-х точковой)
                                                  — повторяем с другим набором из 3 точек (итого: сколько не повторяющихся наборов из 3 точек из всего множества 4 точек — столько и плоскостей)
                                                  • +2
                                                    Это вы решили только первый вариант. (1+3)
                                                    Вариант 2 совсем другой. (2+2)
                                                    • 0
                                                      Да, все, я понял теперь, спасибо.
                                                • +1
                                                  Упускаете. В варианте 1 по разные стороны от исковой плоскости три и одна точки, а в варианте два — две и две. Значит вариант два не сводится к варианту один.
                                                • +3
                                                  Первую задачу я слышал в другой формулировке, к которой как раз и подходит решение из статьи: на кусок хлеба (прямоугольник) положили кусок колбасы (круг); как одним прямолинейным разрезом разделить данный бутерброд так, чтобы обе части содержали одинаковое количество хлеба и одинаковое количество колбасы.
                                                  • +2
                                                    Вот в этом случае кстати решение предложенное автором будет верным, так как явно нужно и прямоугольник и кружок разделить пополам.

                                                    В формулировке автора (с дыркой) количество прямых будет бесконечным независимо от расположения кружка, как описали выше.
                                                  • 0
                                                    В 1967 это была моя настольная книга. Как раз хотел ее поискать в сети.
                                                    • +2
                                                      Мое решение задачи про число плоскостей, равноудаленных от четырех точек, методом аналитической геометрии
                                                      Исходные точки обозначим через K, L, M, N.
                                                      Существует движение пространства, при котором координаты точек будут иметь вид (иначе все точки лежат в одной плоскости):
                                                      K(0, 0, 0), M(x[m], 0, 0), L(x[l], y[l], 0), N(x[n], y[n], z[n]), причем x[m] * y[l] * z[n] != 0 (иначе все точки лежат в одной плоскости)
                                                      Пусть уравнение искомой плоскости П в данной системе координат имеет вид:
                                                      A * x + B * y + C * z + D = 0, D >= 0 (это всегда можно сделать так)
                                                      Пусть n = Sqrt[A^2 + B^2 + C^2]
                                                      dist(П, K) = D / n
                                                      dist(П, M) = Abs[A * x[m] + D] / n
                                                      dist(П, L) = Abs[A * x[l] + B * y[l] + D] / n
                                                      dist(П, L) = Abs[A * x[n] + B * y[n] + C * z[n] + D] / n
                                                      Тогда имеем систему уравнений:
                                                      {Abs[A * x[m] + D] == D, Abs[A * x[l] + B * y[l] + D] == D, Abs[A * x[n] + B * y[n] + C * z[n] + D] == D}
                                                      Всевозможными способами раскрывая модуль, получаем решения системы (8 семейств).
                                                      Одно из них не подходит, т. к имеет вид A = B = C = 0
                                                      Каждое другое задает соответствующую плоскость. Значит, существует всего 7 искомых плоскостей.
                                                      • 0
                                                        Как ни крути, а знания лишними не бывают

                                                        Знания лишними не бывают. Но ты решаешь эти задачи на собеседовании (легко и слету), а на работу тебя все равно не берут. Потому что Google.
                                                        • +4
                                                          Как ни крути, а знания лишними не бывают

                                                          Даже если предположить, что возможности мозга не ограничены, и человек (без потери, а вроде как с пользой) способен впитать в себя огромное количество знаний — то остается, как минимум, еще один фактор: время. Оно крайне лимитировано. Поэтому знания, как и всё остальное, стоит выбирать с точки зрения целесообразности.

                                                          Нужна ли программисту математика? Вечный холиварный вопрос. Хочу отметить, на один из комментариев выше, что в реальной жизни проекты не делятся на «тупой кодинг» и наукоемкие, с кучей математики. 99% задач где-то между ними. Программисту в первую очередь нужна computer science, которая частично пересекается с математикой (построена на ней), но большинство задач реального мира далеки от олимпиадных задач.

                                                          На собеседованиях любят давать олимпиадные задачи. Сложилась такая практика. Но, честно говоря, непонятно, что положено в основу. Это какое-то очень общее представление о том, что у человека, который хорошо решает задачи на логику, комбинаторику, геометрию, условно говоря, хорошо работает мозг. Так смотреть на работу мозга — это как всех, от web-дизайнера до DBA называть «компьютерщик». Понятно, что когда человек его не напрягает, то когнитивные способности в целом падают. Мозг надо нагружать. Но чем? Если я прорешаю 100 подобных задачек, мне это поможет в написании сложной программы? Если очень обще — то да, тут мозг задействован, там задействован, тут логика, там логика и пр. Но фактически, с КПД близким к единице, мне это поможет лишь для решения 101-й задачи такого же типа. Это примерно как с IQ, высокий — о, да он гений! А по факту, этот коэффициент показывает умение проходить тесты. Это не значит, что человек сможет изобрести что-то полезное, слишком разная для мозга эта задача. В общем, не хочу никого обидеть, просто я не вижу оснований (проведенные исследования) для сложившегося многолетнего хайпа по поводу олимпиадных задачах. Кому-то оно интересно само по себе, людям нравится решать задачки — отлично! Какая-то часть мозга очень развивается. Но почему это рассматривается как обязательная часть реального программирования?
                                                          • 0
                                                            Задачи подобного рода отношения к программированию не имеют. Лично я бы вместо этого посмотрел бы в диплом, если по математике / физике оценка отлично, значит человек усидчивый, может зацепиться и вникнуть. Это очень важно.

                                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.