2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 00:48 
Аватара пользователя


01/12/11

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


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

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

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

 Профиль  
                  
 
 Re: Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 12:23 


05/09/16
11467
Да вроде норм решение.
Вопрос -- а 59 это наименьшее количество подряд идущих натуральных чисел раскрашенных в три цвета, что найдутся не менее двух одноцветных разность которых полный квадрат?

 Профиль  
                  
 
 Re: Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 15:05 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
Уже для 34 гарантированно найдется. Для 33 - не обязательно, пример раскраски:
1, 2, 7, 8, 9, 14, 15, 21, 22, 28, 29
3, 4, 10, 11, 16, 17, 18, 23, 24, 30, 31
5, 6, 12, 13, 19, 20, 25, 26, 27, 32, 33
Это если не считать единицу квадратом. Если считать, то максимум можно раскрасить 28:
1, 4, 6, 9, 12, 14, 19, 24, 27
2, 5, 7, 10, 15, 17, 20, 22, 25, 28
3, 8, 11, 13, 16, 18, 21, 23, 26

 Профиль  
                  
 
 Re: Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 19:22 


05/09/16
11467
Насчет простого решения -- наверное нужен тот, кто знает что такое модулярная арифметика, мне кажется это по их части.

 Профиль  
                  
 
 Re: Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 20:30 
Заслуженный участник
Аватара пользователя


13/08/08
14429
А мне задача понравилась со школьной стороны. Любознательный школьник может поиграть с покраской, и тем самым прикоснуться к алгебраическим задачам. Я попробовал лишь слегка обобщить (надеюсь, ТС не будет ругаться).
Пусть есть $A\subset N$ и $B\subset A$. Введём отношение $K: aKc\Leftrightarrow \{\exists b\in  B: a+b=c \vee c+b=a\}$
Вообще, можно считать, что дело происходит на множестве с операцией, а можно распространить это дело на группу или линейное пространство. Там есть какая-то теория. Раскраска есть факторизация множества по некоторому отношению эквивалентности $T$. Отношение $K$ может быть в различных отношениях с $T$. Иногда даже и быть им самим, если выполняются известные свойства. Оно может вызывать эквивалентность, запрещать её (как у ТС) и так далее.
Наша задача получить на основе $K$ отношение $T$ с наименьшим количеством классов эквивалентности.
Пример на основе условия ТС. Пусть $A=N; B=\{2\};K: aKc\Leftrightarrow \{\exists b\in  B: |a-b|=1\}$. То есть два одноцветных числа не могут отличаться на $1$. И вот двухцветная подходящая раскраска: чётные красные, нечётные синие. Можно даже запихнуть в $B$ сколько угодно нечётных чисел.
У ТС $A=\{1..100\};B=\{1,4,9,16,25...\}$ и непротиворечащее отношение $T$ не может содержать меньше четырёх классов эквивалентности. То есть трёх красок никак не хватит. А почему? Мне кажется, что тут дело не в самих квадратах, а в том, что существуют квадраты равные разности квадратов: $9K25,16K25$. А в моём примере $\not\exists n,m\in B: nKm$. Если в множестве $B$ есть элементы, которые находятся в отношении $K$ друг к другу, то $K$ вызывает тем больше классов эквивалентности в возможном $T$$T$ всегда существует: можно покрасить все числа в разные цвета).

 Профиль  
                  
 
 Re: Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 23:06 
Аватара пользователя


01/12/11

8634
mihaild
Как Вы доказали?

 Профиль  
                  
 
 Re: Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 23:11 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
Ktina в сообщении #1331110 писал(а):
Как Вы доказали?

код: [ скачать ] [ спрятать ]
Используется синтаксис Python
from ortools.linear_solver import pywraplp

def main():
    for N in range(1, 100):
        solver = pywraplp.Solver('solver', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

        vc = [[solver.IntVar(0, 1, '%s%d' % (color, i + 1)) for color in 'rbg'] for i in range(N)]

        squares = set(i**2 for i in range(1, N))

        for v in vc:
            solver.Add(v[0] + v[1] + v[2] == 1)

        for i in range(N):
            for j in range(i + 1, N):
                if j - i in squares:
                    for k in range(3):
                        solver.Add(vc[i][k] + vc[j][k] <= 1)

        obj = solver.Objective()
        for v in vc:
            for x in v:
                obj.SetCoefficient(x, 1)
        obj.SetMaximization()

        status = solver.Solve()
        if status == solver.INFEASIBLE:
            print("impossible for %d" % (N, ))
            return
        assert status == solver.OPTIMAL

        assert solver.Objective().Value() == N
        colors = {c: [] for c in 'rgb'}
        for v in vc:
            for x in v:
                if x.solution_value() > 0:
                    colors[x.name()[0]].append(int(x.name()[1:]))
        print("colors for %d: %s " % (N, colors, ))

if __name__ == "__main__":
    main()
 

 Профиль  
                  
 
 Re: Натуральные числа от 1 до 100 покрасили в 3 цвета...
Сообщение07.08.2018, 23:50 
Аватара пользователя


01/12/11

8634
mihaild
Большое спасибо!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group