Натуральные числа от 1 до 100 покрасили в 3 цвета. Докажите, что найдутся два одноцветных числа, разность которых — точный квадрат.

У меня получилось как-то длинно и надуто:

Ясно, что 1, 10 и 26 должны быть разных цветов, так как разность между любыми двумя из них - точный квадрат. Также ясно, что 1, 17, и 26 должны быть разных цветов по той же причине. Но тогда 10 и 17 должны быть одного цвета. Аналогично, того же цвета, что 10 и 17, будут числа 24, 31, 38, 45, 52, и 59. Ну а разность между 59 и 10 как раз и есть точный квадрат.

Может, я какое-то более простое решение в лоб не вижу?

задан 7 Авг 1:50

1

@Казвертеночка: по-моему, весьма естественное и понятное решение. Интересно разве что понять, для какого наименьшего числа верен сам факт. Скажем, пусть даны числа от 1 до 58. Можно ли их раскрасить? Подозреваю, что нет.

(7 Авг 16:49) falcao

@falcao, Вы не поверите, но у меня тоже возник именно этот вопрос :) Ответ: для 58 тоже нельзя! Подсказка: Первые числа от начала - это последние числа от конца :)

(8 Авг 0:04) Казвертеночка
1

@Казвертеночка: к такому выводу можно прийти, скорее всего, разными способами. Интересно, можно ли тут получить исчерпывающее решение (пусть и при помощи компьютера)? Я пока не пробовал, но надо посмотреть.

(8 Авг 9:21) falcao
10|600 символов нужно символов осталось
1

Я составил небольшую программу для Maple. Вычисление (очень быстрое) показало, что можно раскрасить числа от 1 до 28. Вот один из вариантов:

[1, 2, 3, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 3, 1, 2, 3, 1, 3, 1, 2, 3, 2, 3, 1].

Если заменить взаимно 2 на 3 и прочитать в обратную сторону, то получится то же самое (это для сокращения прямой проверки).

Это "рекорд", то есть числа от 1 до 29 уже не раскрасить. Не знаю, можно ли это доказать "ручным" способом.

Добавление. Оказывается, есть простое "ручное" доказательство, что 29 чисел раскрасить нельзя. Предполагая, что можно, мы по Лемме Казвертеночки заключаем, что 10~17, 11~18, 12~19, 13~20 (числа 10 и 20 находятся на расстоянии 10 от краёв). Пусть цвет(10)=a=цвет(17), цвет(11)=b=цвет(18). У числа 14 цвет отличен от цвета 10 и 18, откуда цвет(14)=c. Тогда цвет(15)=a, так как он соседствует с цветом c и находится на расстоянии 4 от цвета b. Далее, цвет(13)=b, так как по соседству есть цвет c, а на расстоянии 4 есть a. Отсюда цвет(20)=b. По тому же принципу, цвет(16)=с. Значит, цвет(12)=a, но он совпадает с цветом 19, и тогда числа 15, 19 раскрашены в один цвет.

Тут хорошо то, что всё делается форсированно, без разветвлений и рассмотрения случаев.

ссылка

отвечен 8 Авг 15:23

изменен 8 Авг 20:30

@falcao, большое спасибо!

(8 Авг 16:30) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

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

по почте:

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

по RSS:

Ответы

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

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