|
Вершины правильного n-угольника покрашены несколькими красками (каждая - одной краской) так, что точки одного и того же цвета служат вершинами правильного многоугольника. Докажите, что среди этих многоугольников есть два равных. Какая-то убойная задача, если решать по-умному, а не технично (переход от геометрии к комплексным числам). Может кто-нибудь рассказать решение и, если это возможно, мотивировку, то есть способ до него(решения) додуматься? Можно ли как-то уйти от геометрии, но при этом не в алгебру полиномов, а в теоретико-множественную комбинаторику? задан 2 Июн '15 21:24 
sapere aude
показано 5 из 7
показать еще 2
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
2 Июн '15 21:24
показан
1243 раза
обновлен
13 Июн '15 21:42
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Это задача из "Кванта", она упоминалась здесь. Наверное, какое-то более комбинаторное доказательство здесь возможно -- надо подумать.
@falcao Спасибо за ссылку.
Ну ничего себе решение... вроде бы по кускам понял, но уверен на все 100, что сам никогда бы такого не придумал. Даже сложно отнести к какой-то конкретной теме, кроме как общее "комбинаторные конструкции". У вас большой кругозор, может, знаете, где поискать похожие задачи, но менее гробовые?
И было бы интересно узнать комбинаторное решение, ну или хотя бы наводку, как его придумать.
@sapere aude: поскольку задача из "раннего" журнала "Квант", то там всё как бы "штучное", а не "серийное". Аналогов мне не попадалось -- вот разве что @EdwardTurJ придумал новый сюжет на эту тему.
Рассуждение там комбинаторное и есть -- геометрия играет чисто иллюстративную роль. Можно считать, что там просто циклический массив символов.
@sapere aude: вот простенькая задача на тему "одномерной геометрии". Даны слова (последовательности символов) X и Y. Известно, что XY=YX. Доказать, что X и Y являются степенями одного и того же слова, то есть существует Z такое, что X=Z...Z, Y=Z...Z какое-то количество раз.
@falcao Простите, пожалуйста, но в упор не понимаю, а где именно Вы подразумеваете использование геометрии?
А если считать, что там циклический массив сдвигов, то как тогда противоречие получить через двойной подсчет? То есть если нет углов? Тут больше тригонометрии и комплексных чисел, не вижу как их можно выкинуть из решения?
@sapere aude: под "одномерной геометрией" я понимаю изучение слов и их подслов. Допустим, мы знаем, что в слове какие-то два подслова равны. Это значит, что одно с другим можно совместить сдвигом: аналогия с конгруэнтными (равными) фигурами. Можно также рассматривать циклические сдвиги. Это эквивалентно тому, что точки лежат на окружности, и рассматриваются повороты. Такой язык, наверное, в чём-то удобнее, но можно всё рассматривать на прямой, и вместо поворота на угол будет циклический сдвиг массива на фиксированное число.
Если $% n/d_i $% - число вершин i-го многоугольника, то задача сводится к доказательству: $% \sum 1/d_i =1 (d_i >1) \Rightarrow \exists i,j: d_i=d_j $%.