• Nếu $n$ là lũy thừa của 2 thì coi như xong. Nếu $n$ không là lũy thừa của $2$ ta chọn một lũy thừa của 2 nhỏ hơn $n$ và gần $n$ nhất, giả sử là $2^{a_k}$. Ta có $2^{a_k} < n < 2^{a_k+1}$.
• Tiếp theo áp dụng thuật toán cho số $n-2^k$, rõ ràng thuật toán dừng vì ta có dãy giảm và bị chặn bởi 0.
• Khi đó ta có $n = 2^{a_1} + \cdots +2^{a_k}$.
• Ta chứng minh sự biểu diễn này là duy nhất. Giả sử tồn tại hai cách biểu diễn $2^{a_k} + \cdots + 2^{a_1} = 2^{b_m} + \cdots 2^{b_1}$. Nếu $a_k >b_m \Rightarrow a_k \geq b_m+1$. Khi đó $a^k >a^{b_m+1}-1=\geq 2^{b_m}+2^{b_m-1} + \cdots 2^{1} + 1$
• Do đó $VT > VP$ (vô lí)
• Nếu $a_k = b_m$, chứng minh tương tự cũng có 2 dãy $a_1,\cdot a_k$ và $b_1,\cdots b_m$ là trùng nhau. Nên sự biểu diễn là duy nhất.

• Giả sử các màu được đánh số từ 1 đến $d+1$. Ta thực hiện cách tô màu như sau
• Chọn 1 đỉnh ta tô màu nhỏ nhất mà không xuất hiện trong các đỉnh lân cận với đỉnh đó. Việc tô màu này luôn thực hiện được vì bậc của mỗi đỉnh không hơn hơn $d$.

• Ta có thể làm ngược lại, tô màu các số sao cho với mỗi tập $A_i$ có ít nhất một số được tô màu, ta chứng minh là số phần tử cần tô không vượt quá $1348$ số.
• Ta thực hiện cách tô sau: Chọn phần tử xuất hiện nhiều nhất trong các tập, tô màu phần tử đó. Lặp lại thuật toán đến khi không có tập hợp nào không có phần tử được tô màu
• Ta chứng minh số phần tử được tô màu không vượt quá 1348 phần tử
• Giả sử ta tô được $k$ phần tử, và các tập còn lại đều phân biệt rời nhau, có $m$ tập hợp. Rõ ràng vì mỗi bước thực hiện đều giảm được ít nhất 2 tập nên $k \leq \dfrac{2022}{2} = 1011$. (Vì cách chọn số phần từ xuất hiện trong nhiều tập nhất nên ít nhất là 2). Và các tập còn lại phân biệt rời nhau, mỗi tập có 3 phần tử nên $m \leq 1011/3 = 337$.\\
• Khi đó ta tô màu mỗi phần tử trong $m$ tập còn lại thì sẽ thỏa đề bài, do đó số phần tử cần tô màu là $k+m \leq 1011+ 337 = 1348$.
• Do đó ta có cách tô màu thỏa đề bài.

Ta sắp xếp từ trái sang phải theo thứ tự tăng dần các số ở hàng thứ nhất $a_1 \leq a_2 \leq \cdot \leq a_n$, hàng dưới tương ứng là $1-a_1, 1-a_2, \cdots, 1-a_n$.

Ta chọn các số ở hàng trên từ trái qua, nhiều nhất sao cho tổng $S$ không lớn hơn $\dfrac{n+1}{4}$. Ta chứng minh tổng các số ở hàng dưới trong các cột còn lại không lớn hơn $\dfrac{n+1}{4} – S$.

Giả sử chỉ số $i$ lớn nhất thỏa $a_{1}+a_{2}+\cdots+a_{i} \leq \frac{n+1}{4} .$ Ta cần chứng minh
$$
\dfrac{n+1}{4} \geq\left(1-a_{i+1}\right)+\left(1-a_{i+2}\right)+\cdots+\left(1-a_{n}\right)=(n-i)-\left(a_{i+1}+a_{i+2}+\cdots+a_{n}\right)
$$

$$
a_{i+1}+a_{i+2}+\cdots+a_{n} \geq \frac{3 n-1}{4}-i
$$
Từ $a_{1} \leq a_{2} \leq \cdots \leq a_{i+1}$, ta có
$$
\dfrac{a_{1}+a_{2}+\cdots+a_{i+1}}{i+1} \leq a_{i+1}
$$

và từ $a_{i+1} \leq a_{i+2} \leq \cdots \leq a_{n}$, ta có
$$
\dfrac{a_{i+1}+a_{i+2}+\cdots+a_{n}}{n-i} \geq a_{i+1}
$$
Từ đó ta có
$$
\dfrac{a_{i+1}+a_{i+2}+\cdots+a_{n}}{n-i} \geq \frac{a_{1}+a_{2}+\cdots+a_{i+1}}{i+1}
$$

$$
a_{i+1}+a_{i+2}+\cdots+a_{n} \geq(n-i) \cdot \frac{a_{1}+a_{2}+\cdots+a_{i+1}}{i+1}>(n-i) \cdot \frac{\frac{n+1}{4}}{i+1}
$$
do cách chọn $i$ lớn nhất.

Ta cần chứng minh $\dfrac{n-i}{i+1} \dfrac{n+1}{4} \geq \dfrac{3 n-1}{4}-i .$

hay $(n-1)^{2} \geq 4 i(n-i-1)$, áp dụng AM-GM $2 \sqrt{i(n-i-1)} \leq i+(n-i-1)=n-1$, ta có điều cần chứng minh.

Ta thấy có 2 trường hợp là $z=y=b, y-x=a$ hoặc $z-y=a, y-x=b$ hay tập có tính chất $P$ sẽ có một trong hai dạng {x, x+a, x+a+b} hoặc {x, x+b, x+a+b} với $x$ nguyên dương.

Với mỗi tập có tính chất $P$ là {x, y, z} ta tô màu $x$ đỏ, $y$ xanh $z$ vàng.

Ta tô màu các số nguyên dương như sau:

• Xét số dương $k$ nhỏ nhất chưa được tô màu.
• Nếu $k+a$ chưa được tô màu thì ta tô màu cho tập {k, k+a, k+a+b}.
• Nếu $k+b$ chưa được tô màu thì ta tô màu cho tập {k, k+b,k+a+b}.

Ta chứng minh với cách tô màu như trên thì các tập đều phân biệt và số nào cũng được tô màu. Giả sử ta đã thực hiện tới bước thứ $n$ với phần tử $x_n$ là nhỏ nhất được tô màu. Ta tiếp tục thực hiện với kế tiếp với phần tử $x_{n+1}$ chưa được tô màu. Ta cần chứng minh các phần tử $x_{n+1}+a$ hoặc $x_{n+1}+b$ chưa được tô màu và $x_{n+1}+a+b$ chưa được tô màu trước đó.

• Thật vậy rõ ràng là $x_{n+1}+a+b$ chưa được tô màu vì nó lớn hơn tất cả các số được tô màu. (Ở bước thứ $n$ thì $x_n$ được tô màu, nên $x_n+a+b $ là số lớn nhất được tô màu.
• Nếu $x_{n+1} +b$ được tô màu thì không thể là màu đỏ, nếu xanh thì $x_{n+1}+b-a$ được tô màu đỏ, vô lí. Nếu màu vàng thì $x_{n+1}+b-a-b = x_{n+1}-a$ được tô màu đỏ, khi đó $x_{n+1}$ được tô màu, vô lí.