А вторая задача верно сформулирована? Потому, что если верно, то сразу напрашивается контр-пример: 0,10,19,27,34,40,45 - точки на прямой, все попарные расстояния различны, точки соединены так, как написаны. Прямая не принципиальна - малым шевелением можно выйти в плоскость и точки общего положения.
В первой тоже непонятно, по делу ли квадрат. Скорее всего это верно для любого измеримого множества конечной меры.
Видимо, я неточно написал. Наверное, вы под "в итоге соединена" поняли, что есть путь к не более чем 5 точкам, а я всего лишь имел в виду: "после того, как мы соединим ребром каждую точку с ближайшим соседом, окажется в итоге, что каждая точка соединяется - одним ребром, а не длинным путем - с не более чем пятью другими".
Естественно, первая - это теорема о деревенских свадьбах. Можно выдать замуж всех девушек за тех, кто им нравится, если для каждого подмножества девушек есть как минимум столько же парней, которым нравится хотя бы одна из них. Соответственно, в этой задаче нужно показать, что для любого множества частей из первого набора есть как минимум столько же частей из второго набора, пересекающихся хотя бы с одной из них. То есть, что для фигуры площадью n/100 найдётся хотя бы n частей из второго набора, её пересекающих. То есть, что для фигуры площадью n/100 объединение всех частей из второго набора, пересекающихся с ней, имеет площадь не менее n/100. Что очевидно, так как это объединение эту фигуру полностью покрывает.
по 2-й задаче контрпример: 7 точек, 1-я центр, 2-я на радиусе (расстояние 1 от 1-й), 3-я на расст. 1+делта, ... ,7-я на расст. 1+6делта от центра. углы между радиусами 60 градусов, т.е. выходит 6 точек соединенных с 1-й, нет?
1. У любого неравностороннего треугольника самый большой его угол превосходит 60 градусов.
2. Напротив наибольшей стороны треугольника находится его самый большой угол.
3. Если в условиях задачи точка B соединена с A и С соединена с A, то BC - наибольшая сторона треугольника ABC (иначе или B соединялась бы с С, или C соединялась с B)
4. Если A соединена с B, а C - с A, то BC - наибольшая сторона треугольника ABC (так как AB < AC и CB > CA)
5. Если какая-то точка A соединена отрезками не менее чем с шестью другими, то среди этих отрезков найдутся два (AB и AC) с углом между ними не большим 60 градусов. Что противоречит максимальности угла A треугольника ABC.
Построим двудольный граф: его вершинами будут части двух разбиений (всего 200 вершин). Соединим две вершины ребром если соответствующие части пересекаются. Условие теоремы Холла выполнено - выбрав k частей первого разбиения обнаруживаем, что количество частей второго разбиения, пересекающихся с какой-то частью из этих k, не меньше k (так как иначе объединение этих к частей было бы покрыто множеством меньшей площади). Значит есть такое паросочетание A_1-B_1, A_2-B_2, ... A_100-B_100, что пересечение A_k с B_k непусто.
Выберем 100 точек из этих 100 непустых пересечений.
Comments 30
В первой тоже непонятно, по делу ли квадрат. Скорее всего это верно для любого измеримого множества конечной меры.
Reply
Убрал слово "в итоге", может, оно только путает.
Reply
Первую же задачу, скорее всего, можно свести к задаче о паросочетаниях.
Reply
Естественно, первая - это теорема о деревенских свадьбах. Можно выдать замуж всех девушек за тех, кто им нравится, если для каждого подмножества девушек есть как минимум столько же парней, которым нравится хотя бы одна из них. Соответственно, в этой задаче нужно показать, что для любого множества частей из первого набора есть как минимум столько же частей из второго набора, пересекающихся хотя бы с одной из них. То есть, что для фигуры площадью n/100 найдётся хотя бы n частей из второго набора, её пересекающих. То есть, что для фигуры площадью n/100 объединение всех частей из второго набора, пересекающихся с ней, имеет площадь не менее n/100. Что очевидно, так как это объединение эту фигуру полностью покрывает.
Я на тему теоремы о деревенских свадьбах сделал игрушку в рамках haskell tiny game jam: https://github.com/haskell-game/tiny-games-hs/blob/main/prelude/matchmaking/matchmaking.hs
Reply
углы между радиусами 60 градусов, т.е. выходит 6 точек соединенных с 1-й, нет?
Reply
Reply
( ... )
Reply
Утверждение задачи 2 вытекает из следущих фактов:
1. У любого неравностороннего треугольника самый большой его угол превосходит 60 градусов.
2. Напротив наибольшей стороны треугольника находится его самый большой угол.
3. Если в условиях задачи точка B соединена с A и С соединена с A, то BC - наибольшая сторона треугольника ABC (иначе или B соединялась бы с С, или C соединялась с B)
4. Если A соединена с B, а C - с A, то BC - наибольшая сторона треугольника ABC (так как AB < AC и CB > CA)
5. Если какая-то точка A соединена отрезками не менее чем с шестью другими, то среди этих отрезков найдутся два (AB и AC) с углом между ними не большим 60 градусов. Что противоречит максимальности угла A треугольника ABC.
Reply
Reply
Reply
Первая задача - забавное следствие теоремы Холла https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem
Построим двудольный граф: его вершинами будут части двух разбиений (всего 200 вершин). Соединим две вершины ребром если соответствующие части пересекаются. Условие теоремы Холла выполнено - выбрав k частей первого разбиения обнаруживаем, что количество частей второго разбиения, пересекающихся с какой-то частью из этих k, не меньше k (так как иначе объединение этих к частей было бы покрыто множеством меньшей площади). Значит есть такое паросочетание A_1-B_1, A_2-B_2, ... A_100-B_100, что пересечение A_k с B_k непусто.
Выберем 100 точек из этих 100 непустых пересечений.
Reply
Reply
Leave a comment