https://arca.live/b/math/6823177

오랫만에 와봤다가 갑자기 생각나서 까먹기 전에 해설 올림

두 집합을 A, B라 하고 B에 1이 있다고 하자. 이때 그림처럼 격자를 그린다(100*100 정사각형 대각선 아래만 남긴 모양). 이때 임의의 a, b∈A에 대해 좌표가 (x, y)(x≠y)이고 x+y=a+b인 모든 칸 생각 시 이 칸들 중 x, y가 모두 B의 원소가 되는 칸 있다면 증명이 끝남. 따라서 그 칸들의 x, y 좌표 중 적어도 하나는 A 원소인 경우만 보면 되는데, A의 최소원소를 a, 두 번째로 작은 원소를 b라 하고 (a-1, b+1) 칸 생각 시 a가 최소원소니 b+1이 A의 원소. 이를 반복하면 b, ..., 100이 모두 A의 원소니 A의 원소합은 a+b+...+100=5050-b(b-1)/2+a=2525. 이때 2<=a<=b-1에 의해 a=31, b=72인데 그러면 B에 32, 71이 있으니 그런 두 쌍 존재.

따라서 항상 존재함을 알 수 있다.

자세히 쓰다보니 장황해졌는데 아이디어는 간단함

또 잘 생각해 보면 a=b-2, b-1일 때는 합 같은 두 쌍이 없는 반례가 있고, a≠b-2, b-1이면 항상 합 같은 두 쌍이 존재함. 그걸 쓰면 n과 b의 관계식이 나와 특정 n에서만 반례가 있음을 알 수 있음. 예를 들어 n=20이면 a=15, b=16인 경우가 반례.