$[ x]$ ile $x$ i aşmayan en büyük tamsayıyı gösterelim.
$k\le n$ için kişi başına düşen kek bir parçadan az olmadığından, kekleri $1$ den $n$ ye kadar numaralandırdığımızı düşünürsek, her $1\le i\le k$ için sadece $[i.\dfrac{n}{k}]$ numaralı kekleri bir kez kesmemiz yeterli olacaktır. Dolayısıyla böyle bir paylaşımın yapılabileceği açıktır.
Şimdi $k>n$ durumunu inceleyelim. $k$ istenen şekilde bir paylaşımı olanaklı kılsın. Kişi başı düşen kek bir parçadan az olacağından hiç kesilmemiş bir kek olamaz. Demek ki her kek tam olarak bir kez kesilmiş ve bu parçalar iki kişi arasında paylaştırılmıştır. Köşeleri $A_1,A_2,\dots ,A_k$ ile isimlendirilmiş bir graf düşünelim. $A_1,A_2,\dots ,A_k$ burada kekleri bölüştüreceğimiz $k$ kişiyi temsil ediyor. $n$ parça kekten her biri için o kek $i.$ kişi ile $j.$ kişi arasında bölüştürülmüşse $A_iA_j$ kenarını çizelim. Her kek tam olarak iki kişi arasında bölüştürüldüğünden grafımızda tam olarak $n$ kenar bulunmaktadır.
İlk olarak, bu grafta hiç çevrim bulunmadığını gösterelim. Genelliği bozmadan, diyelim ki grafta $A_1A_2\dots A_mA_1$ grafta yer alan bir çevrim olsun. Bu durumda bu $m$ kişi kendi aralarında en az $m$ kek paylaşmış olur. Öyleyse bu $m$ kişiden öyle birisi vardır ki en az $1$ kek almıştır. Fakat $k>n$ olduğundan, kişi başı düşen kek miktarı $1$ den az olmalıdır ki bu çelişkidir. Demek ki grafımızda çevrim yoktur.
Lemma: İçerisinde hiç çevrim bulundurmayan bir grafın köşeleri kesişmeyen bağlantılı ağaçların bir birleşimi olarak ifade edilebilir. Yani grafın köşeleri her bir grup bağlantılı ağaç oluşturacak şekilde gruplara ayıracağız ve kenarlar sadece aynı grup içerisinde yer alan köşeler arasında olacaktır.
İspat: Bir köşe alalım ve bu köşeden ulaşabileceğimiz tüm köşeleri bu köşe ile aynı gruba dahil edelim. Eğer dışarıdan bu gruba kenar olamaz, yoksa biz ilk seçtiğimiz köşeden ulaşabileceğimiz tüm köşeleri o köşe ile aynı gruba dahil etmiş olmazdık. Ayrıca grafta hiç çevrim bulunmadığından ilk grup bağlantılı bir ağaçtır. Her defasında kalan köşeler içinden bir tane seçip aynı işlemi tekrarlarsak, grafın köşelerini kesişmeyen bağlantılı ağaçların birleşimi olarak ifade etmiş oluruz, Lemma'nın ispatı tamamlandı.
Şimdi sorumuza dönelim.
Başlangıçtaki grafımızı $G$ ile isimlendirelim. Bu grafı ayırdığımız kesişmeyen bağlantılı ağaçları da $G_1{,G}_2,\dots ,G_s$ ile isimlendirelim. $G_i$ deki köşe sayısı $v_i$, kenar sayısı da $e_i$ olsun.
Teorem: Bağlantılı bir ağacın kenar sayısı köşe sayısından bir eksiktir.
Yukarıdaki teoremden $e_i=v_i-1$ diyebiliriz. Öte yandan $G$ grafı $k$ köşe ve $n$ kenara sahip olduğundan $v_1+v_2+\dots +v_s=k$ ve $e_1+e_2+\dots +e_s=n$ bulunur. Son eşitlikte $e_i=v_i-1$ yazarsak $v_1+v_2+\dots v_s-s=n$ buluruz ve dolayısıyla $k-s=n$ yani $s=k-n$ elde ederiz. Her bir $G_i$ grafı için o grafta toplam $e_i$ kenar vardır, yani $e_i$ kek dağıtılmıştır. Herkesin eşit miktarda kek alması gerektiğinden, bu grafta her köşe $\dfrac{e_i}{v_i}$ kek almıştır. Dolayısıyla $e_i=v_i-1{\rm \ }$olduğundan ve herkesin eşit miktarda kek alması gerektiğinden $\dfrac{v_i-1}{v_i}=1-\dfrac{1}{v_i}$ ifadelerinin her biri eşit olmalıdır. Yani $v_1=v_2=\dots =v_s$ olmalıdır. $v_1+v_2+\dots +v_s=k$ ve $s=k-n$ olduğundan $v_i=\dfrac{k}{k-n}$ olmalı. Öyleyse $k-n|k$ yani $k-n|n$ olmalıdır. Bu da ancak, uygun bir $d|n$ için $k=n+d$ sağlanırken mümkündür. Böyle $d$ lerin sayısı da $d(n)$ olduğundan $k$ ların sayısı en fazla $n+d(n)$ dir.
Geriye sadece, her $d|n$ için $k=n+d$ değerlerinin sağladığını göstermek kaldı. $n=dm$ olsun. Kişi başı düşen kek miktarı $\dfrac{n}{k}=\dfrac{m}{m+1}$ parça olmalı. $n$ parça keki yan yana dizip bütün bir kek gibi düşünelim. Ve bu keki en soldan başlayarak, her $n$ parçanın $\dfrac{m}{m+1}$ i büyüklüğünde parçalara ayıralım. $\dfrac{pm}{m+1}$ ve $\dfrac{qm}{m+1}$ tamsayı değilken $[\dfrac{pm}{m+1}]\ne [\dfrac{qm}{m+1}]$ olduğunu ispatlarsak, zaten $\dfrac{pm}{m+1}$ ifadesi $p<m+1$ için tamsayı olmadığından, her kek tam olarak bir parçaya ayrılmış olur ve ispat biter.
Aksini varsayalım, bir $(p,q)$ ikilisi ve tam sayı olmayan bir $k$ rasyonel sayısı için $k=[\dfrac{pm}{m+1}]=[\dfrac{qm}{m+1}]$ olsun. Öyleyse $km+k\le pm,\ qm\le km+k+m$ olur. Genelliği bozmadan $p<q$ kabul edelim. $qm\ge pm+m$ olacağından $km+k+m\le qm\le km+k+m$ olur, yani $qm=km+k+m$ olmalıdır. $pm\le qm-m$ olacağından $km+k\le pm\le km+k$ olur, yani $\left[\dfrac{pm}{m+1}\right]=k=\dfrac{pm}{m+1}$ olmalıdır. Fakat bu durumda da $\dfrac{pm}{m+1}$ tamsayı olur ki bu varsayımımızla çelişkidir. Demek ki $\dfrac{pm}{m+1}$ ve $\dfrac{qm}{m+1}$ tamsayı değilken $[\dfrac{pm}{m+1}]\ne [\dfrac{qm}{m+1}]$ olur.
Böylece örneğimiz istenen şartı sağlar, tam olarak $n+d(n)$ tane $k$ değeri için uygun bir kesim mümkündür.
