logoChat01.ai

Аня заменила каждое натуральное число от 1 до 100...

作成日: 2026年4月22日

使用モデル GPT-5.4 Thinking by Chat01

質問

Аня заменила каждое натуральное число от 1 до 100 на одну из трех букв
У, Р или А. Докажите, что найдутся две одинаковых буквы такие, что разность
соответствующих им чисел является квадратом натурального числа

Python

python
import itertools, math
n=100
squares=[i*i for i in range(1,int(math.isqrt(n-1))+1)]
adj={i:set() for i in range(1,n+1)}
for i in range(1,n+1):
    for s in squares:
        if i+s<=n:
            adj[i].add(i+s); adj[i+s].add(i)
# backtracking find chromatic number >3? obviously maybe.
order=sorted(range(1,n+1), key=lambda x: len(adj[x]), reverse=True)
len(adj[1]), squares[:10], order[:10]


(9,
 [1, 4, 9, 16, 25, 36, 49, 64, 81],
 [50, 51, 17, 18, 19, 26, 27, 28, 29, 30])

Python

python
import networkx as nx, math, itertools, random
G=nx.Graph()
G.add_nodes_from(range(1,n+1))
for i in range(1,n+1):
    for j in adj[i]:
        if i<j: G.add_edge(i,j)
# chromatic number lower bound? try algorithm?
print(nx.number_of_nodes(G), nx.number_of_edges(G))
# Use approximation? Search cliques
print(nx.graph_clique_number(G))

Python

python
import itertools, math, networkx as nx
n=100
squares=[i*i for i in range(1,int(math.isqrt(n-1))+1)]
G=nx.Graph()
G.add_nodes_from(range(1,n+1))
for i in range(1,n+1):
    for s in squares:
        if i+s<=n: G.add_edge(i,i+s)

from networkx.algorithms.clique import find_cliques
print(max(len(c) for c in find_cliques(G)))

Python

python
import math,itertools,random
n=100
squares=[i*i for i in range(1,int(math.isqrt(n-1))+1)]
adj={i:set() for i in range(1,n+1)}
for i in range(1,n+1):
    for s in squares:
        if i+s<=n:
            adj[i].add(i+s); adj[i+s].add(i)
def can3(vertices):
    verts=sorted(vertices, key=lambda x: len(adj[x]&vertices), reverse=True)
    colors={}
    def bt(idx):
        if idx==len(verts): return True
        v=verts[idx]
        used={colors[u] for u in adj[v] if u in colors}
        for c in range(3):
            if c not in used:
                colors[v]=c
                if bt(idx+1): return True
                del colors[v]
        return False
    return bt(0)

V=set(range(1,101))
print(can3(V))

Python

python
import math, random
n=100
squares=[i*i for i in range(1,int(math.isqrt(n-1))+1)]
adj={i:set() for i in range(1,n+1)}
for i in range(1,n+1):
    for s in squares:
        if i+s<=n:
            adj[i].add(i+s); adj[i+s].add(i)

def can3(vertices):
    vertices=set(vertices)
    verts=sorted(vertices, key=lambda x: len(adj[x]&vertices), reverse=True)
    colors={}
    def bt(idx):
        if idx==len(verts): return True
        # choose uncolored with saturation maybe
        best=None; bestkey=None
        for v in verts:
            if v not in colors:
                used={colors[u] for u in adj[v] if u in colors}
                key=(len(used), len(adj[v]&vertices))
                if best is None or key>bestkey:
                    best=v; bestkey=key
        v=best
        used={colors[u] for u in adj[v] if u in colors}
        for c in range(3):
            if c not in used:
                colors[v]=c
                if bt(idx+1): return True
                del colors[v]
        return False
    return bt(0)

V=set(range(1,101))
changed=True
while changed:
    changed=False
    for v in list(V):
        if not can3(V-{v}):
            V.remove(v); changed=True; print("removed",v,"size",len(V)); break
print("final size",len(V),sorted(V))

Python

python
V=[72,74,75,81,83,84,88,90,91,92,97,99,100]
for v in V:
    print(v, sorted(adj[v] & set(V)))

Python

python
import itertools, math
V=[72,74,75,81,83,84,88,90,91,92,97,99,100]
tri=[]
for a,b,c in itertools.combinations(V,3):
    if b in adj[a] and c in adj[a] and c in adj[b]:
        tri.append((a,b,c))
tri


[(72, 81, 97),
 (72, 88, 97),
 (74, 83, 99),
 (74, 90, 99),
 (75, 84, 100),
 (75, 91, 100)]

Python

python
V=set([72,74,75,81,83,84,88,90,91,92,97,99,100])
verts=sorted(V)
sol=[]
colors={}
def bt():
    if len(colors)==len(verts):
        sol.append(colors.copy()); return
    # choose next with saturation
    un=[v for v in verts if v not in colors]
    best=max(un,key=lambda v:(len({colors[u] for u in adj[v] if u in colors}), len(adj[v]&V)))
    used={colors[u] for u in adj[best] if u in colors}
    for c in range(3):
        if c not in used:
            colors[best]=c
            bt()
            del colors[best]
bt()
len(sol)


0

思考

Working on creating proof with casework

I’m trying to create an elegant proof using casework on these 13 numbers, identifying any patterns or structures. It seems like a smaller subset might help, even down to 12. I'll generate logical contradictions by forcing color assignments on certain triangles. Using colors U, R, and A may help structure my reasoning.

Thought for 2m 35s

回答

Предположим противное: Аня раскрасила числа от 11 до 100100 буквами У, Р, А так, что никакие два одинаково отмеченных числа не отличаются на квадрат натурального числа.

Рассмотрим только следующие 13 чисел:

72,74,75,81,83,84,88,90,91,92,97,99,100.72,74,75,81,83,84,88,90,91,92,97,99,100.

Тогда любые два из них, разность которых равна 1,4,9,161,4,9,16 или 2525, должны иметь разные буквы.

Теперь заметим:

72,81,9772,81,97

образуют тройку, у которой попарные разности равны

81−72=9,97−81=16,97−72=25,81-72=9,\quad 97-81=16,\quad 97-72=25,

то есть все три разности — квадраты. Значит, на числах 72,81,9772,81,97 стоят три разные буквы.

Точно так же тройка

72,88,9772,88,97

тоже имеет попарные разности 16,9,2516,9,25, значит, на ней тоже стоят три разные буквы. Поскольку числа 7272 и 9797 в обеих тройках те же самые, число 8888 должно иметь ту же букву, что и 8181.

Итак,

81 и 88 отмечены одинаково.81 \text{ и } 88 \text{ отмечены одинаково.}

Аналогично, из троек

74,83,99и74,90,9974,83,99 \qquad \text{и} \qquad 74,90,99

получаем, что

83 и 90 отмечены одинаково.83 \text{ и } 90 \text{ отмечены одинаково.}

Из троек

75,84,100и75,91,10075,84,100 \qquad \text{и} \qquad 75,91,100

получаем, что

84 и 91 отмечены одинаково.84 \text{ и } 91 \text{ отмечены одинаково.}

Теперь посмотрим на числа 88,90,9188,90,91.

  • 90−81=990-81=9, а 8181 и 8888 имеют одинаковую букву, значит, 9090 имеет не ту букву, что 8888.
  • 91−90=191-90=1, значит, 9191 имеет не ту букву, что 9090.
  • 9191 имеет ту же букву, что 8484, а 88−84=488-84=4, значит, 9191 имеет не ту букву, что 8888.

Следовательно, числа 88,90,9188,90,91 отмечены тремя разными буквами.

Но 8383 имеет ту же букву, что 9090, значит, числа

83,88,9183,88,91

тоже отмечены тремя разными буквами.

Теперь число 9292 отличается от них на квадраты:

92−83=9,92−88=4,92−91=1.92-83=9,\qquad 92-88=4,\qquad 92-91=1.

Значит, буква на 9292 должна отличаться и от буквы на 8383, и от буквы на 8888, и от буквы на 9191. То есть она должна быть отлична сразу от всех трёх букв У, Р, А — невозможно.

Получили противоречие.

Значит, обязательно найдутся два числа с одинаковой буквой, разность которых является квадратом натурального числа.

Что и требовалось доказать.

このQ&Aを共有