$r\geq2$ bir pozitif tamsayı olmak üzere, tüm pozitif tamsayılar $r$ farklı renkten birine boyanıyor. $(a,b)$ bir renk çifti olmak üzere, herhangi bir $n$ pozitif tamsayısı için bu tamsayının $a$ rengine boyanmış pozitif tam bölenlerinin sayısı ile $b$ rengine boyanmış pozitif tam bölenlerinin sayısı arasındaki farkın en fazla $1$ olmasını sağlayan tüm mümkün $r$ değerlerini bulunuz.
Çözüm:
$r\geq 4$ için boyamanın mümkün olmadığını gösterelim. Kullanılan renkler $a,b,c,d$ olsun. $p$ ve $q$ farklı asal olmak üzere, $n=pq$ ise $1,p,q,pq$ pozitif bölenlerinin her biri farklı renkte olmalıdır. Aksi taktirde, bir renk en az iki defa kullanılacak, bir renkse hiç kullanılmayacaktır. Yani farklı asal sayılar farklı renkte olmalıdır, bu da sadece $4$ renk olmasıyla çelişir.
Şimdi $r=2$ ve $r=3$ için örnek durum bulalım.
$r=2$ için $a$ ve $b$ renklerini ele alalım. Genelliği bozmadan $1$'i $a$'ya boyayalım. Bu durumda, $n$ asal sayı seçilirse, $n$'nin kendisi $b$'ye boyanmak zorundadır. Yani tüm asal sayılar $b$ rengindedir. Eğer farklı $p,q$ asalları için $n=pq$ formatında ise $1,p,q,pq$ bölenlerinden $pq$ da $a$'ya boyanmalıdır, aksi takdirde istenilen şart sağlanmaz. Bir örnek boyama bulmamız yeterli olduğundan, tahmin yürütebiliriz. Eğer $n$'nin asal bölenlerinin sayısı (tekrarları da sayarak) çiftse $a$'ya, tekse $b$'ye boyayalım. Yani 1,2,3,4,5,6,7,8,9,10 şeklinde boyayalım. Bu boyama işe yarayacaktır. Yaradığını göstermek için $\Omega(n)$ fonksiyonunu kullanabiliriz. Bu fonksiyon $n$'nin tekrarlı asal bölenlerinin sayısını verir. $$f(n)=\sum_{d\mid n}(-1)^{\Omega(d)}=\text{"}a \text{ rengine boyanan pozitif bölen sayısı }- b\text{ rengine boyanan pozitif bölen sayısı }\text{"}$$ şeklinde tanımlayalım. $\Omega$ toplamsal bir aritmetik fonksiyon olduğundan, $(-1)^{\Omega(\cdot)}$ da çarpımsal bir fonksiyondur. Dolayısıyla, $f$ de çarpımsaldır. $$f(p^a)=\sum_{d\mid p^a}(-1)^{\Omega(d)}=\sum_{k=0}^{a}(-1)^{\Omega(p^k)}=\sum_{k=0}^{a}(-1)^{k}=1-1+1-1+\cdots+(-1)^a$$ olacaktır. Bu toplam ya $0$'dır, ya da $\pm 1$'dir. Dolayısıyla, $n=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}$ şeklinde çarpanlarına ayrılıyorsa, $$f(n)=f(p_1^{a_1})f(p_2^{a_2})\cdots f(p_m^{a_m})=0,1,-1$$ olacaktır. Yani istenilen şart sağlanmaktadır.
$r=3$ için yine benzer bir boyama yapabiliriz. Eğer $\Omega(n)\equiv 0\pmod{3}$ ise $a$'ya, $\Omega(n)\equiv 1\pmod{3}$ ise $b$'ye, $\Omega(n)\equiv 2\pmod{3}$ ise $c$'ye boyarız. Bu boyamanın işe yaradığını göstermek için $n$'yi $w^{\Omega(n)}$ ile eşleyelim, burada $w\neq 1$ ve $w^3=1$'dir. Yani tamsayı çıkanlar $a$'ya, bir tamsayının $w$ katı çıkanlar $b$'ye $w^2$ katı çıkanlar ise $c$'ye boyanacaktır. $$g(n)=\sum_{d\mid n}w^{\Omega(d)}$$ toplamı $x+yw+zw^2$ formatında olacaktır, burada $x,y,z$ sayıları da sırasıyla, $a$,$b$,$c$ rengine boyanmış bölen sayılarıdır. $w^{\Omega(\cdot)}$ çarpımsal olduğundan $g$ de çarpımsaldır. $$g(p^k)=w^{\Omega(1)}+w^{\Omega(p)}+w^{\Omega(p^2)}+\cdots +w^{\Omega(p^k)}$$ $$=1+w+w^{2}+\cdots +w^{k}$$ $$=0,1,1+w.$$ Dolayısıyla, $$g(n)=g(p_1^{a_1})g(p_2^{a_2})\cdots g(p_m^{a_m})$$ çarpımı sonucunda ya $0$, ya $1$, ya da $(1+w)$'nin bir kuvvetini elde ederiz. $(1+w)$'nin kuvvetleri, $1+w,w,1$ olduğundan bir $N$ tamsayısı için $$g(n)=x+yw+zw^2= N(w^2+w+1),1+N(w^2+w+1),w+N(w^2+w+1),w+1+N(w^2+w+1)$$ formatlarındadır. Bu da bu boyamanın istenilen şartı sağladığını gösterir.