Натуральные числа от 1 до 100 покрасили в 3 цвета...

[Ktina]

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


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

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

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

[wrest]

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

[mihaild]

Уже для 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

[wrest]

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

[gris]

А мне задача понравилась со школьной стороны. Любознательный школьник может поиграть с покраской, и тем самым прикоснуться к алгебраическим задачам. Я попробовал лишь слегка обобщить (надеюсь, ТС не будет ругаться).
Пусть есть $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$ всегда существует: можно покрасить все числа в разные цвета).

[Ktina]

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

[mihaild]

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()
 

[Ktina]

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