Loading [MathJax]/jax/output/SVG/jax.js

Математикадан 52-ші халықаралық олимпиада, 2011 жыл, Амстердам


Жазықтықта кемінде екі нүктеден тұратын ақырлы нүктелердің S жиыны берілген. S жиынынан алынған кез келген үш нүкте бір түзудің бойында жатпайды. Мынадай үрдісті диірмен деп атаймыз: ол S жиынымен тек қана бір ортақ P нүктесі бар түзуінің көмегімен басталады; біз осы түзуді сағат тілімен P центрін айналдыра, түзу үстінде S жиынының басқа бір нүктесі пайда болған мезетке шейін бұра береміз; бұл нүкте, оны Q деп белгілейік, осы мезеттен бастап жаңа центр ретінде қарастырылып, енді түзуді сағат тілімен Q нүктесін айналдыра, түзу үстінде S жиынының басқа бір нүктесі пайда болғанша бұра береміз. Бұл үрдіс ақырсыз жалғаса береді.
S жиынының бір P нүктесі және осы P нүктесі арқылы өтетін бір түзуі үшін түзуінің көмегімен басталған диірмен үрдісінің орындалу барысында S жиынының әрбір нүктесі ақырсыз көп рет центр рөлін атқаратынын дәлелдеңдер.
посмотреть в олимпиаде

Комментарий/решение:

  2
4 года 5 месяца назад #
  1
1 года 3 месяца назад #

В ютубе есть решение канала 3Blue1Brown

  7
1 года 4 месяца назад #

сначала вы берете выпуклую оболочку и называете этот многоугольник S1, затем вы берете S1 из S, берете выпуклую оболочку и называете этот многоугольник S2, и продолжаете делать это, пока не получите S1,S2,S3,,Sn и осталось 0, 1 или 2 очка. Теперь выберем линию l такую, чтобы она содержала точки внутри S1,S2,,Sn. Теперь мы перемещаем l до тех пор, пока он не встретит одну из точек S, но только одну, если он касается 2 точек в S, мы снова генерируем l под другим углом (у него все равно будут точки внутри многоугольников, в на самом деле он будет содержать сегменты внутри многоугольников) и начните с процесса.

Случай 1: после удаления последней выпуклой оболочки осталось 0 очков:

Sn — многоугольник: легко видеть, что для каждого многоугольника Si линия l всегда будет иметь точки внутри этого многоугольника, потому что единственный способ «выйти» из многоугольника — это встреча двух последовательных точек v1 и v2. многоугольника и выход из многоугольника, но если он касается v1, а затем v2, это означает, что v2 идет первым по часовой стрелке, поэтому линия затем войдет внутрь многоугольника. (Я не очень хорошо объясняю свои решения на английском языке. Если вы чего-то не понимаете, дайте мне знать, и я попытаюсь объяснить это еще раз). Поскольку угол линии будет вращаться вечно по часовой стрелке, то каждая точка в Si будет встречаться линией бесконечно много раз для каждого многоугольника Si, потому что найдется пара точек (v,w) такая, что линия встретится с v и w одновременно бесконечно много раз (после второго раза она встретит их те же движения, что и в первый раз, снова начнутся, приводя к кругу), и в этом цикле каждая точка встретится по крайней мере однажды (это не очень сложно доказать)

Случай 2: после удаления последней выпуклой оболочки осталось 1 или 2 очка:

В этом случае мы используем тот же алгоритм, что и в предыдущем случае, мы забываем об этих 1 или 2 точках и видим, что каждая точка внутри Sn будет встречена хотя бы один раз в процессе. Итак, мы начинаем процесс до тех пор, пока не будет достигнута одна из 1 или 2 точек внутри Sn. Если это всего лишь одна точка, идея та же, потому что линия будет вращаться вечно, и пара точек будет встречена дважды, следовательно, бесконечно много. раз, поэтому каждая точка в каждом многоугольнике будет встречаться бесконечно много раз, и точка внутри тоже. Если внутри есть две точки, то мы должны доказать, что обе точки будут встречены в процессе, но это легко, потому что, поскольку обе точки находятся внутри Sn, а линия в каждый момент имеет отрезок внутри Sn, и линия достигает одной и той же позиции бесконечно много раз, то обе точки будут встречаться бесконечно много раз, потому что между моментами M1 и M2, когда линия имеет одно и то же положение, каждая точка внутри Sn будет встречаться с линией (это легко докажи это, чтобы я не делал этого, пока кто-нибудь не попросит меня об этом).

  0
1 года 4 месяца назад #

Bruh

  0
1 года 4 месяца назад #

Хорошее решение что такого

  0
1 года 4 месяца назад #

закройся