از 2 گانه شماری حل میشه

n=10

یک نفر a رو فرض میکنیم که با 3 نفر d={a1,a2,a3}وسته و با {a4,..an }=cدوست نیست

با 2 گانه شماری روی یالهای بین این 2 دسته میگیم هر شخص در d باید با 3 تا از دسته c دوست باشه چون با a نباید دوست مشترک داشته باشه

پس یک طرف گراف 2 بخشی برابر 2*3=6 شد

و چون هر نفر در c باید با 1 نفر از d دوست باشه چون با a دوست نیست و 1 دوست مشترک دارن که از یک طرف میشه n-4)*1=n-4)

پس n-4=6 پس n=10 است

ادعا میکنیم اگر حداقل یک دانش آموز در کلاس باشد، آنگاه $N=10$ (اگر هم کسی نباشد خوب $N=0$ !!!)

دانش آموزان را از $S_1$ تا $S_n$ برچسب میزنیم. همچنین کلاس را مانند یک گراف درنظر میگیرم که در آن هر راس نماینده ی یک دانش آموز و هر یال نماینده ی یک رابطه ی دوستی است به طوری که دو راس $S_x$ و $S_y$ به هم یال دارند اگر و فقط گر دانش آموز $S_x$ با دانش آموز $S_y$ دوست باشد.

لم 1: $10\le N$

اثبات: فرض کنید $S_1$ با افراد $S_2 , S_3, ,S_4$ دوست است. چون $S_2 , S_3, ,S_4$ بین هم یال ندارند (با هم دوست نیستند) و هردوتای آنها دارای یک دوست مشترک مشترک ($S_1$) هستند، پس هر کدام دقیقا با دو تا از دانش آموزان $S_x$ به طوری که $ 4 < x $ دوست هستند. پس علاوه بر این چهار راس حداقل 6 راس دیگر وجود دارد. پس $10\le N$.

لم 2: $N\le 10$

اثبات: شراط لم 1 را در نظر بگیرید و همچنین فرض کنید $S_2$ به $S_5$ و $S_6$، $S_3$ به $S_7$ و $S_8$ و همچنین $S_4$ به $S_9$ و $S_{10}$ یال دارد.حال فرض میکنیم $N>10$. در نتیجه راسی مانند $S_x$ وجود دارد که $x > 10$. حال چون $S_x$ نمیتواند به $S_1$ متصل باشد پس باید به دقیقا یکی از همسایه های آن یال داشته باشد. چون تمام همسایه های $S_1$ به سه یال متصلند در نتیجه $S_x$ نمیتواند به هیچ کدامشان متصل شود که این تناقض است و امکان ندارد. پس $N\le 10$.

حال با توجه به لم 1 و لم 2 $N=10$ که مثال زیر نیز درستی وجود حالتی برای $N=10$ را اثبات میکند. (بعد از هر دو نقطه رئوسی را نشان میدهد که راس پشت دو نقطه به آنها یال دارد)

$S_1: S_2, S_3, S_4$

$S_2: S_1, S_5, S_6$

$S_3: S_1, S_7, S_8$

$S_4: S_1, S_9, S_{10}$

$S_5: S_2, S_7, S_9$

$S_6: S_2, S_8, S_{10}$

$S_7: S_3, S_5, S_{10}$

$S_8: S_3, S_6, S_9$

$S_9: S_4, S_5, S_8$

$S_{10}: S_4, S_6, S_7$