Задача №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 года издания, которая содержит школьные олимпиадные задачи.
Задача про плоскости в этом сборнике идет под номером один. Так что кому интересно, могут ознакомиться с другими задачами и решениями.
Вот так всегда: учишься в школе, поступаешь в институт, а в институте говорят “забудь, что учил в школе”, затем идешь работать и слышишь “забудь, чему тебя учили в институте”, потом идешь на какое-то собеседование, а тебе дают задачку из школьных олимпиад =) Как ни крути, а знания лишними не бывают.
Комментарии (56)
Sdima1357
20.01.2018 23:28В первой задаче будет бесконечное число таких линий, делящих фигуру на две с равными площадями, в любом случае, а не только при совпадении центров. Доказать это сложнее.проведите линию под любым углом и начните ее двигать параллельно самою себе. Интегралы слева и справа(или сверху снизу) в определенный момент будут неизбежно равны
ainoneko
22.01.2018 07:41И все эти прямые будут проходить через «центр масс», который будет где-то на отрезке между центрами прямоугольника и круга?
Sirion
22.01.2018 10:11+1Неа, так это не работает. Легко можно проверить на треугольнике: медианы проходят через центр масс и делят площадь пополам, а вот прямые, проходящие через него параллельно сторонам, делят площадь в отношении 4:5.
koldyr
20.01.2018 23:34+2Первая задача не правильно решена. Описанная прямая является решением. Но не единственным.
Возьмем произвольную прямую. Пересечение одной полуплоскости, ограничеваемой этоий прямой, с прямоугольником с дыркой назовем фигурой А, другой полуплоскости фигурой Б. Будем двигать эту прямую вдоль нормали к ней, и рассмотрим разность площадей А и Б. очевидно что она меняет знак, а значит есть точка где разность равна нулю.
Чуть-чуть не успел.
AnROm Автор
20.01.2018 23:53Что-то мне кажется, я написала статью, комментарии к которой будут полезнее, чем сама статья ))
Sdima1357
21.01.2018 00:00Добавьте к формулировке первой задачи дополнительное условие « с помощью циркуля и линейки постройте прямую линию ...» и далее по тексту.
koldyr
21.01.2018 00:05Будут пол дня центр окружности искать.
Сейчас вообще в школе проходят задачи с циркулем и линейкой?Sdima1357
21.01.2018 00:13Квадратура круга? Жена (учитель математики ) утверждает что только факультативно. Правда эти сведения устарели лет на 15. Так что не знаю как сейчас, но собеседование вроде не для школьников?
GlukKazan
21.01.2018 16:35Факультативно? Вообще-то это одна из трёх знаменитых задач циркулем и линейкой не решаемых. Хоть факультативно, хоть по программе.
koldyr
21.01.2018 16:49Квадратура не решаема, а центр окружности циркулем и линейкой находится в рамках школьной программы.
Sdima1357
21.01.2018 18:13Решение квадратуры круга тоже есть, но оно секретно. Его объясняют только на факультативе в школе. Это секретный способ узнать — ходил ли человек на факультатив, а слух о неразрешимости запущен специально для этой цели :)
OLS
21.01.2018 01:26Добавьте к формулировке первой задачи дополнительное условие «… прямых, проходящих через центр прямоугольника ...» и далее по тексту. Тогда Ваш ответ станет корректным.
saboteur_kiev
21.01.2018 05:09а вообще неважно какой размер прямоугольника и круга?
если круг очень маленький, а прямоугольник большой, то IMHO вообще неважно где круг.koldyr
22.01.2018 20:27Соотношение размеров не существенно. Качественная разница появится только тогда, когда круг выродится в точку.
KvanTTT
21.01.2018 00:42Это все конечно интересно, но что показывает навык решения подобных геометрических задач? Разве что работа будет напрямую связана с конструкциями, архитектурой?
avost
22.01.2018 00:02Навык? Наличие навыка показывает умение решать шаблонные задачи. Тут, скорее, я бы заподозрил попытку проверить умеет ли человек решать как раз нетиповые задачи (исходя из предположения, что большинство соискателей вышли из школьно-студенческого возраста и олимпиадные навыки успешно утратили со временем). Но, боюсь, это слишком сложная конспирология и большинство просто решило, — а почему бы и нет. И, как ни странно, оно даже так работает :). Полезно, если у вас в работе, конечно, встречаются нетиповые задачи. Если не встречаются и нужно тупое производство шаблонного кода с незначительными вариациями, то да, это всё лишнее, а подобный работник будет overqualified, быстро заскучает и уйдёт.
KvanTTT
22.01.2018 00:07Полезно, если у вас в работе, конечно, встречаются нетиповые задачи.
Много таких. Ок, возьму на вооружение =)
PavelGatilov
22.01.2018 13:23Многие топ компании нанимают работника не особо принимая в расчет его текущие навыки, а учитывая далекую перспективу. Поэтому иногда выбираются задачи не особо связанные с кодом, но больше с мышлением и логикой.
Решение подобной задачи покажет, может ли человек разбираться с незнакомыми поставленными задачами.
yizraor
21.01.2018 00:54Всего две задачки, но насколько интересные…
Спасибо, что дали повод немножко подумать :)
Мои не совсем трезвые и почти самостоятельные размышления по задачамЗадача 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 штук!Sirion
21.01.2018 03:44Спрячьте решения под спойлер, пожалуйста. Не то чтобы меня сильно затруднила првая задача, но поясняющий рисунок я увидел раньше, чем успел начать думать.
ITMatika
21.01.2018 09:45+4В первой задаче:
1)Находим центры прямоугольника и круга.
2)Соединяем центры отрезком. На этом отрезке находится центр тяжести получившейся фигуры. (его просто вычислить, но одного циркуля с линейкой скорее всего не хватит)
Через этот центр можно провести бесконечное количество секущих.ITMatika
21.01.2018 09:53+1Поправка: заменить слово отрезок на слово прямая, либо луч из центра круга.
koldyr
21.01.2018 11:19+1Для произвольной фигуры это не верно, а для данного случая совершенно не очевидно. Подозреваю, что тоже не верно.
ITMatika
21.01.2018 11:41+1Вы правы. Получились равновесные секущие, а не равновеликие.
Однако в большинстве случаев существуют точки на… прямоугольника, через которые можно провести бесконечное количество равновеликих секущих.ITMatika
21.01.2018 11:50+1* В большинстве случаев существуют точки на средних линиях прямоугольника, через которые можно провести бесконечное количество равновеликих секущих.
qvytr452
24.01.2018 10:10-1Сразу подумал про центр масс. Разве равновесные в данном случае не равновеликие? Ведь прямоугольник, насколько я понял, однородный и следовательно масса прямо пропорциональна площади. Поэтому ваше решение считаю верно.
ITMatika
24.01.2018 12:15К сожалению, это не так. Получившаяся фигура неправильная, и то, что применимо к прямоугольнику, к ней не применимо.
При определении центра масс нужно оперировать такими понятиями как радиус-вектор/момент силы тяжести/плечо. Можно уравновесить абсолютно разные массы, если подобрать плечи разной длины.
Сделал на скорую руку иллюстрацию. Средние линии обозначены серым цветом. Равновеликие — красным. При перемещении круга внутри красного правого нижнего прямоугольника центр масс будет смещаться (так как будут меняться радиус-векторы), а равновеликие секущие — нет (так как площадь правого нижнего красного прямоугольника останется постоянной).
Нетрудно заметить, что если точки X и Y не принадлежат кругу, то через каждую из них можно провести бесконечное количество равновеликих секущих. (но не равновесных!)
CDK
21.01.2018 11:59А зачем в задаче 2 вариант 2? По моему это тот же вариант 1 «вид сбоку», не?
Из 4 точек не лежащих в одной плоскости можно выбрать 3 не лежащих на одной прямой и посторить по ним плоскость из варианта 1.
Или я что-то упускаю?ITMatika
21.01.2018 12:201) три точки лежат по одну сторону от рассматриваемой плоскости, четвертая — по другую;
2) по каждую сторону от плоскости лежат по две точки.
Я не могу представить, как можно спутать эти варианты или преобразовать один в другой. В этих вариантах совершенно разные построения.CDK
21.01.2018 14:12Эммм…
Мы искомую плоскость проводим, ее нет. Изначально у нас есть только 4 точки и все.
Поэтому я предположил такой алгоритм:
— берем 3 любые точки (они не могут лежать на 1 прямой, иначе все 4 точки окажутся в одной плоскости)
— строим по этим 3 точкам плоскость
— строим от 4 точки перпендикуляр до этой плоскости
— искомая плоскость — по центру перпендикуляра (параллельно 3-х точковой)
— повторяем с другим набором из 3 точек (итого: сколько не повторяющихся наборов из 3 точек из всего множества 4 точек — столько и плоскостей)
koldyr
21.01.2018 12:21Упускаете. В варианте 1 по разные стороны от исковой плоскости три и одна точки, а в варианте два — две и две. Значит вариант два не сводится к варианту один.
Yurdr
21.01.2018 13:07+1Первую задачу я слышал в другой формулировке, к которой как раз и подходит решение из статьи: на кусок хлеба (прямоугольник) положили кусок колбасы (круг); как одним прямолинейным разрезом разделить данный бутерброд так, чтобы обе части содержали одинаковое количество хлеба и одинаковое количество колбасы.
burdakovd
21.01.2018 13:59Вот в этом случае кстати решение предложенное автором будет верным, так как явно нужно и прямоугольник и кружок разделить пополам.
В формулировке автора (с дыркой) количество прямых будет бесконечным независимо от расположения кружка, как описали выше.
Janycz
21.01.2018 18:21Мое решение задачи про число плоскостей, равноудаленных от четырех точек, методом аналитической геометрииИсходные точки обозначим через 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 искомых плоскостей.
dkuzminov
21.01.2018 20:52Как ни крути, а знания лишними не бывают
Знания лишними не бывают. Но ты решаешь эти задачи на собеседовании (легко и слету), а на работу тебя все равно не берут. Потому что Google.
TimeCoder
22.01.2018 10:23+1Как ни крути, а знания лишними не бывают
Даже если предположить, что возможности мозга не ограничены, и человек (без потери, а вроде как с пользой) способен впитать в себя огромное количество знаний — то остается, как минимум, еще один фактор: время. Оно крайне лимитировано. Поэтому знания, как и всё остальное, стоит выбирать с точки зрения целесообразности.
Нужна ли программисту математика? Вечный холиварный вопрос. Хочу отметить, на один из комментариев выше, что в реальной жизни проекты не делятся на «тупой кодинг» и наукоемкие, с кучей математики. 99% задач где-то между ними. Программисту в первую очередь нужна computer science, которая частично пересекается с математикой (построена на ней), но большинство задач реального мира далеки от олимпиадных задач.
На собеседованиях любят давать олимпиадные задачи. Сложилась такая практика. Но, честно говоря, непонятно, что положено в основу. Это какое-то очень общее представление о том, что у человека, который хорошо решает задачи на логику, комбинаторику, геометрию, условно говоря, хорошо работает мозг. Так смотреть на работу мозга — это как всех, от web-дизайнера до DBA называть «компьютерщик». Понятно, что когда человек его не напрягает, то когнитивные способности в целом падают. Мозг надо нагружать. Но чем? Если я прорешаю 100 подобных задачек, мне это поможет в написании сложной программы? Если очень обще — то да, тут мозг задействован, там задействован, тут логика, там логика и пр. Но фактически, с КПД близким к единице, мне это поможет лишь для решения 101-й задачи такого же типа. Это примерно как с IQ, высокий — о, да он гений! А по факту, этот коэффициент показывает умение проходить тесты. Это не значит, что человек сможет изобрести что-то полезное, слишком разная для мозга эта задача. В общем, не хочу никого обидеть, просто я не вижу оснований (проведенные исследования) для сложившегося многолетнего хайпа по поводу олимпиадных задачах. Кому-то оно интересно само по себе, людям нравится решать задачки — отлично! Какая-то часть мозга очень развивается. Но почему это рассматривается как обязательная часть реального программирования?
leshqow
22.01.2018 22:54Задачи подобного рода отношения к программированию не имеют. Лично я бы вместо этого посмотрел бы в диплом, если по математике / физике оценка отлично, значит человек усидчивый, может зацепиться и вникнуть. Это очень важно.
radarlog
на самом деле, в первой задаче линий будет бесконечное множество в том случае, если центры кружка и прямоугольника совпадают.
AnROm Автор
Спасибо за замечание
andreybotanic
Более того, их будет бесконечное множество даже тогда, когда центры не совпадают. Другое дело, что построить такую прямую будет не просто.
andreybotanic
В случае, если секущую брать параллельно сторонам прямоугольника, довольно просто получить точное решение.
DeeKey
Построить прямую — это не «другое дело». Это другая задача. В данной задаче спрашивается количество таких прямых и не более того. Не уверен, инженерное это было интервью или научное, но для инженера неверная постановка или понимание задачи — серьёзная проблема.
Причем доказать, что существует требуемая прямая, параллельная произвольно выбранной довольно примитивно через параллельный сдвиг прямой и функцию разности площадей справа и слева как сумму нескольких непрерывных функций, принимающую значения А и -А с разных сторон от прямоугольника, а следовательно принимающую и значение 0 хотя бы в одной позиции.
Интересно, что это было за интервью.
andreybotanic
Не соглашусь с первым абзацем. Автор статьи привел один из вариантов решения, а значит наличие способа построить такую прямую как минимум приветствуется.
DeeKey
Угу. То есть то, что автор, сконцентрировавшись на построении прямой, пришла к неправильному ответу вас не смущает. *sarcasm*
Почему у меня глаз сразу зацепился за «подковерное» изменение задачи — в современном программостроении очень трудно найти проект сложнее Hello World в котором это не сыграло бы ощутимую роль. Чаще всего — негативную.
agnithegreat
Да даже если центры не совпадают, мы же не обязаны через центр круга линию проводить, в условии ведь про это не сказано. Допустим, сдвинули ту точку, что внутри круга, чуть выше его центра, разница площадей внутри круга перераспределилась, компенсировали эту разницу сдвигом точки внутри прямоугольника чуть ниже центра. В итоге получается бесконечное множество точек. Поправьте, если ошибаюсь.