Вершины правильного n-угольника покрашены несколькими красками (каждая - одной краской) так, что точки одного и того же цвета служат вершинами правильного многоугольника. Докажите, что среди этих многоугольников есть два равных.

Какая-то убойная задача, если решать по-умному, а не технично (переход от геометрии к комплексным числам). Может кто-нибудь рассказать решение и, если это возможно, мотивировку, то есть способ до него(решения) додуматься? Можно ли как-то уйти от геометрии, но при этом не в алгебру полиномов, а в теоретико-множественную комбинаторику?

задан 2 Июн '15 21:24

изменен 2 Июн '15 22:14

Это задача из "Кванта", она упоминалась здесь. Наверное, какое-то более комбинаторное доказательство здесь возможно -- надо подумать.

(2 Июн '15 21:57) falcao

@falcao Спасибо за ссылку.
Ну ничего себе решение... вроде бы по кускам понял, но уверен на все 100, что сам никогда бы такого не придумал. Даже сложно отнести к какой-то конкретной теме, кроме как общее "комбинаторные конструкции". У вас большой кругозор, может, знаете, где поискать похожие задачи, но менее гробовые?

И было бы интересно узнать комбинаторное решение, ну или хотя бы наводку, как его придумать.

(2 Июн '15 23:38) sapere aude

@sapere aude: поскольку задача из "раннего" журнала "Квант", то там всё как бы "штучное", а не "серийное". Аналогов мне не попадалось -- вот разве что @EdwardTurJ придумал новый сюжет на эту тему.

Рассуждение там комбинаторное и есть -- геометрия играет чисто иллюстративную роль. Можно считать, что там просто циклический массив символов.

(2 Июн '15 23:43) falcao

@sapere aude: вот простенькая задача на тему "одномерной геометрии". Даны слова (последовательности символов) X и Y. Известно, что XY=YX. Доказать, что X и Y являются степенями одного и того же слова, то есть существует Z такое, что X=Z...Z, Y=Z...Z какое-то количество раз.

(2 Июн '15 23:46) falcao

@falcao Простите, пожалуйста, но в упор не понимаю, а где именно Вы подразумеваете использование геометрии?

А если считать, что там циклический массив сдвигов, то как тогда противоречие получить через двойной подсчет? То есть если нет углов? Тут больше тригонометрии и комплексных чисел, не вижу как их можно выкинуть из решения?

(13 Июн '15 6:23) sapere aude

@sapere aude: под "одномерной геометрией" я понимаю изучение слов и их подслов. Допустим, мы знаем, что в слове какие-то два подслова равны. Это значит, что одно с другим можно совместить сдвигом: аналогия с конгруэнтными (равными) фигурами. Можно также рассматривать циклические сдвиги. Это эквивалентно тому, что точки лежат на окружности, и рассматриваются повороты. Такой язык, наверное, в чём-то удобнее, но можно всё рассматривать на прямой, и вместо поворота на угол будет циклический сдвиг массива на фиксированное число.

(13 Июн '15 10:52) falcao

Если $% n/d_i $% - число вершин i-го многоугольника, то задача сводится к доказательству: $% \sum 1/d_i =1 (d_i >1) \Rightarrow \exists i,j: d_i=d_j $%.

(13 Июн '15 21:42) Urt
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×967
×40
×23

задан
2 Июн '15 21:24

показан
632 раза

обновлен
13 Июн '15 21:42

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru