مرحله ۲ نزدیکه ...

۱- بزرگترین مجموعه مستقل گراف شهر‌ها رو در نظر می‌گیریم، اندازه‌ی این مجموعه مستقل حداکثر می‌تونه ۱۰ باشه. چون این مجموعه مستقل بیشینه هستش، پس هر راس خارج از اون، حداقل ۱ یال به مجموعه مسقل داره. پس حداقل ۹۰ یال به مجموعه مستقل وارد شده. حالا اگه این مجموعه مستقل رو از گراف حذف کنیم،یه گراف ۹۰ راسی باقی می‌مونه که بازم خواص گراف اولیه رو داره. پس اگه مجموعه مستقلش رو در نظر بگیریم، حداقل ۸۰ یال بهش وارد شده. اگه همین کارو ادامه بدیم، بدست می‌یاد که گراف حداقل

90+80+70+...+10=450

یال داره. می‌شه یه گراف ساخت یه دقیقا همین قدر یال داشته باشه، مثلا اگه ۱۰ تا K10( گراف کامل ۱۰ راسی) کنار هم بزاریم، یه گراف ساخته می‌شه که خواص گفته شده تو مسئله رو داره و ۴۵۰ تا یال داره.

۲- اعداد ۱،۲،۴،۸،۱۶ رو کنار می‌گزاریم. حالا واسه‌ی هر انتخاب از ۹۵ عدد باقی مونده، بود یا نبود این ۵ عدد با توجه به باقی‌مانده‌ی آن بر ۳۲ به طور یکتا تعیین می‌شه( چرا؟) پس جواب مسئله می‌شه ۹۵^۲.

۳- حکم رو با استقرا بر روی i+j اثبات می‌کنیم. پایه به ازای i+j=0 طبق گفته‌ی مسئله درسته! حالا فرض کنید، می‌خوایم حکم رو واسه خونه‌ی (i,j) ثابت کنیم و می‌دونیم به ازای هر خونه‌ی (x,y) که x+y

i xor k = i xor j -> k = j (چرا؟؟)

حالا فقط لازمه بگیم که تمام اعداد کوچیکتر از i xor j، توی سطر یا ستونش اومدن
برای این‌کار فرض کنید، می‌خوایم عدد 

k

رو بسازیم، برای این می‌یایم رقم های i و j رو در مبنای ۲ از سمت چپ پیمایش می‌کنیم. اولین خونه‌ی رو در نظر بگیرید که xor اون رقم توی i و j برابر k نمی‌شه،حتما یکی از بیت های دو عدد، تو این رقم ۱ هستش( چرا؟) بعد می‌یام یکی از اون یک هارو انتخاب می‌کنیم و ۰ اش می‌کنیم و توی رقم های بعد، هر وقت مشکلی پیش اومد، رقم این عدد رو تغییر می‌دیم تا درست بشه. توی راهی که گفته شد، دقیقا یکی از اعداد تغییر می‌کنه و عدد تغییر کرده حتما کوچیک‌تر از مقدار اولیش می‌شه(چرا؟). پس متناظر با یکی از خونه‌های هم سطر یا ستونشه. پس حکم اثبات شد.

۴- یک گراف ۱۰۰ راسی درست می‌کنیم که در آن هر راس نشان‌گر یک عدد است. حالا واسه هر دو عدد که جمعشون گویا می‌شه، یک یال بین رئوسشون می زاریم.حال ادعا می‌کنیم که گراف درست شده، دور فرد ندارد. فرض کنید یک دور فرد شامل راس‌های

x1,x2,....,x(2k+1)

در آن پیدا کردیم. طبق نحوه‌ی ساخت گراف، می‌دونیم که تمام جمع‌های زیر گویاست:
x1+x2
x2+x3
.
.
.
x(2k+1)+x1
پس عبارت زیر نیز گویاست:
(x1+x2)-(x2+x3)+(x3+x4)-.....-(x(2k)+x(2k+1))-(x(2k+1)+x1)
از طرفی مقدار این عبارت برابر 

-2x(2k+1)

می‌شه، که گویا بود اون نتیجه می‌ده که خود (x(2k+1 گویاست، که تناقضه. چون گراف مورد نظر دور فرد نداره، پس ۲ بخشی هستش. پس حداقل یک بخش آن وجود داره که شامل ۵۰ راس باشه.