এটা একটা graph theory এর problem। এটার solution টা originally publish হয়
The Mathematical Gazette নামক জার্নালে যার writer ছিলেন Paul Erdős-University college of London . এই solution তাও অনেকটা ওখান থেকেই নেওয়া। আর এটা মূলত
rafayaashary01 AoPS এ যে solution দিয়েছে তাই একটু ব্যাখ্যা করে দেওয়া। তাছাড়া এটা জন্য Ahsan Al Mahir Lazim, Swarup Siddharth Mondol তারা অনেক help করেছে।
সবার আগে আমাদের এই প্রশ্নটাকে বুঝতে হবে। আর এই প্রশ্নটা বুঝাটা কিছুটা কঠিনও। এখানে বলা হয়েছে যে $k$ কে $n-good$ বলা হবে যদি $n$ সংখ্যক খেলোয়াড়ের টুর্নামেন্টে খেলোয়াড়রা এমনভাবে খেলে যাতে $n$ সংখ্যক খেলোয়াড় থেকে যেকোনো $k$ সংখ্যক খেলোয়াড়কে আলাদা করে দেখা হয় দেখা যাবে যে সেই $k$ সংখ্যকই একই খেলোয়াড়ের বিপক্ষে হেরেছে। এখানে একটা জিনিস মনে রাখতে হবে যে সকল টুর্নামেন্টেই এমন হতে হবে তা না, যেকোনো একটা তে হলেই হবে। অর্থাৎ টুর্নামেন্টে কে কার সাথে জিতবে বা হারবে তা তুমি নিজেই নিয়ন্ত্রণ করতে পারবা।
Solution of i: এটার উত্তর আমরা induction ব্যবহার করে করব। প্রথমে বুঝাই যাচ্ছে $k=1$, হলে $n=3$ হতে হবে। আবার $k=2,$ হলে $n=7$ এগুলো $n≥2^{k+1}-1$। ধরি এই সূত্রটা $k=1,2…,m-1$ এর জন্য সত্য। এখন যদি আমরা প্রমান করতে পারি যে এটা $k=m$ এর জন্য সত্য তাহলেই আমাদের কাজ শেষ। ধরি,
“$n$ সংখ্যক খেলোয়াড়ের টুর্নামেন্ট তাকে যেখানে যেকোনো $k$ সংখ্যক খেলোয়াড়ের জন্য এমন আর একজন খেলোয়াড় থাকে যে ঐ $k$ সংখ্যক খেলোয়াড়ের প্রত্যেকের বিপক্ষেই জয়ী হয়।” এই বৈশিষ্টটা $=S_k$। অর্থাৎ আমরা ধরে $S_1$ থেকে $S_{m-1}$ এর জন্য প্রশ্নের শর্তটি সত্য অর্থাৎ $S_{m-1}$ এর জন্য $n≥2^m-1$ এবং দেখাতে হবে $S_m$ এর জন্যও $n≥2^{m+1}-1$। ধরি, $n$ সংখ্যক খেলোয়াড় বিশিষ্ট টুর্নামেন্টকে $\zeta^{n}$ দ্বারা প্রকাশ করি। এখন contradiction এর জন্য ধরে নেই, $S_m$ এর জন্য $n≤2^(m+1)-2$ এটা সত্য। আবার কোনো খেলোয়াড় $x$ যে যে খেলোয়াড়ের সাথে হেরেছে তাদের সেটকে $\zeta^{n}(x)$ দ্বারা প্রকাশ করি।
এখন contradiction এর জন্য এমন একটি টুর্নামেন্ট $\zeta^{n}$ তৈরী করা হল যাতে খেলোয়াড় সংখ্যা $n≤2^{m+1}-2$ এর জন্য $S_m$ শর্তটি মানে। দেখ এই গ্রাফে সর্বোচ্চ জেতা খেলোয়াড়(ধর সে হল $\xi$) নূন্যতম জিতবে $\frac{n-1}{2}$ ($\xi$ বাদে বাকি খেলোয়াড়ের অর্ধেক) টি খেলোয়াড়ের সাথে। অর্থাৎ $\xi$ হেরেছে সর্বোচ্চ,
$⌊\frac{1}{2}(n-1)⌋=⌊\frac{1}{2}(2^{m+1}-2-1)⌋=⌊2^m-1.5⌋=2^m-2$
যেহেতু $\xi$ হেরেছে সর্বোচ্চ $2^m-2$ জনের সাথে তাই $\zeta^n(\xi)$ সেটের খেলোয়াড় সংখ্যা $N≤2^m-2$ এখন দুইটা case হতে পারে,
- $N ≥m-1$;
- $N<m-1$
যদি আমরা এখন দেখাতে পারি এগুলো হওয়া সম্ভব না তাহলেই আমরা contradiction পেয়ে যাব এবং আমাদের প্রমাণ শেষ।
Case 01($N≥m-1$): যদি আমরা দেখাতে পারি $\zeta^n(\xi)$ সেটটি $S_{m-1}$ কে মেনে চলে তাহলে $N≥2^m-1$ হবে তবে যেহেতু $N≤2^m-2$ তাই আমরা contradiction পেয়ে যাব। তাই $\zeta^n(\xi)$ সেট্টি $S_{m-1}$ কে মেনে চলে তা দেখানোর try করা যাক।
$\zeta^n(\xi)$ সেটটির $m-1$ খেলোয়াড় বিশিষ্ট যেকোনো উপসেট $E_i$ নেই। যেহেতু $\zeta^n$ টুর্নামেন্টটি $S_m$ শর্তটি মানে তাই $\zeta^n$ টুর্নামেন্টটিতে এমন একটি খেলোয়াড় $μ_i∉E_i$ অবশ্যই পাওয়া যাবে যাতে তা $E_i∪\xi$ এই সেটটির প্রতিটি খেলোয়াড়ের ($∵ E_i∪\xi$ সেটে খেলোয়াড় সংখ্যা $m$ এবং $\zeta^n$ টুর্নামেন্টটি $S_m$ শর্তটি মানে) সাথে জিতবে। তার মানে $\xi$ খেলোয়াড় $μ_i$ এর বিপক্ষে হেরেছে। যেহেতু $\zeta^n(\xi)$ সেটটি $\xi$ যে যে খেলোয়াড়ের সাথে হেরেছে তাদের সেট তাই $μ_i∈\zeta^n(\xi)$। আর এই ঘটনা যেহেতু সকল উপসেট $E_i$ এর জন্য তাই $\zeta^n(\xi)$ সেটটির $m-1$ খেলোয়াড় বিশিষ্ট যেকোনো উপসেটের জন্য এমন একটি খেলোয়াড় $\zeta^n(\xi)$ সেটটির মাঝে পাওয়া যাবে যেন তা ঐ সকল $m-1$ খেলোয়াড়ের বিপক্ষে বিজয়ী। অর্থাৎ $\zeta^n(\xi)$ সেটটি $S_{m-1}$ কে মেনে চলে। অর্থাৎ induction hypothesis(যা প্রথমে induction এর আগে ধরে নিয়েছি) থেকে $\zeta^n(\xi)$ সেটটির খেলোয়াড় সংখ্যা $N≥2^m-1$ তবে আবার দেখানো হয়েছে $N≤2^m-2$. অর্থাৎ contradiction। তার মানে এমন case হওয়া সম্ভব না।
Case 02($N<m-1$): $\zeta^n$ টুর্নামেন্টটি থেকে $\zeta^n(\xi)$ সেটে নাই এমন যেকোনো $m-1-N$ সংখ্যক খেলোয়াড় $\zeta^n(\xi)$ সেটটির মাঝে যুক্ত করে নতুন সেট $\zeta^n(\xi)'$ তৈরী করি। অর্থাৎ $\zeta^n(\xi)'$ এর উপাদান সংখ্যা $m-1$। এখন পূর্বের মত, $\zeta^n$ টুর্নামেন্টটি $S_m$ শর্তটি মানে তাই $\zeta^n$ টুর্নামেন্টটিতে এমন একটি খেলোয়াড় $μ_i∉\zeta^n(\xi)'$ অবশ্যই পাওয়া যাবে যা $\zeta^n(\xi)'∪\xi$ এই সেটটির প্রতিটি খেলোয়াড়ের ($∵ \zeta^n(\xi)'∪\xi$ সেটে খেলোয়াড় সংখ্যা $m$ এবং $\zeta^n$ টুর্নামেন্টটি $S_m$ শর্তটি মানে) সাথে জিতবে। অর্থাৎ $μ_i∈\zeta^n(\xi)$; আবার, $\zeta^n (\xi)⊆\zeta^n(\xi)'⟹μ_i∈\zeta^n(\xi)'$. তবে প্রথমেই বলা হয়েছিলো $μ_i∉\zeta^n(\xi)'$। অর্থাৎ contradiction। তার মানে এমন case হওয়া সম্ভব না।
যেহেতু কোনো case এ সম্ভব না তাই $N≰2^m-2$ অর্থাৎ $N≥2^m-1$
মানে $n≰2^{m+1}-2$ তাহলে $n≥2^{m+1}-1$।
Solution of ii: i) থেকে পাই $k,n-good$ হলে $n≥2^{k+1}-1$ $k=2$ হলে $n≥7$ লক্ষ কর, $n=7$ এর জন্য $2 ,n-good$. একটা graph আকি যাতে খেলোয়াড় $n=7$ এবং তাদের কে $p_0,p_1,… ,P_6$ নাম করন করি। যদি খেলোয়াড় $p_i$ খেলোয়াড় $p_j$ কে হারায় তাহলে তাকে $p_i⟶p_j$ দ্বারা প্রকাশ করি। এখন এই টুর্নামেন্টে খেলোয়াড়রা যদি নিচের মত করে একে অপরের সাথে খেলে তাহলে $2,n-good$ হবে।
- $p_0⟶p_1⟶p_2⟶p_3⟶p_4⟶p_5⟶p_6⟶p_0$
- $p_0⟶p_2⟶p_4⟶p_6⟶p_1⟶p_3⟶p_5⟶p_0$
- $p_0⟶p_4⟶p_1⟶p_5⟶p_2⟶p_6⟶p_3⟶p_0$
- national p8.png (40.43KiB)Viewed 4406 times
এখন দেখাতে হবে কেন এই construction এর জন্য $2,n-good$ হবে। যেহেতু প্রতিটা খেলোয়াড় অন্য তিনজন খেলোয়াড়ের বিপক্ষে হেরেছে, তাই এই সাতটি খেলোয়াড় থেকে যেকোনো দুইজন খেলোয়াড় $p_a$ ও $p_b$ যারা যথাক্রমে $p_{a_{1}},p_{a_{2}},p_{a_{3}} এবং p_{b_{1}},p_{b_{2}},p_{b_{3}}$ খেলোয়াড় দ্বারা পরাজিত হয়।
প্রমাণ করতে হবে ${p_{a_{1}},p_{a_{2}},p_{a_{3}}}∩{p_{b_{1}},p_{b_{2}},p_{b_{3}}}≠∅$ যদি ${p_{a_{1}},p_{a_{2}},p_{a_{3}}}∩{p_{b_{1}},p_{b_{2}} ,p_{b_{3}}}=∅$ হয় তবে $p_{a_{1}},p_{a_{2}},p_{a_{3}}$ এবং ${p_{b_{1}},p_{b_{2}} ,p_{b_{3}}}$ এরা সবাই আলাদ অর্থাৎ এখানে আছে $6$ জন খেলোয়াড়। আর আছে ${p_a ,p_b}∉{p_{a_{1}},p_{a_{2}},p_{a_{3}}}∩{p_{b_{1}},p_{b_{2}},p_{b_{3}}}$ অর্থাৎ তাহলে মোট খেলোয়াড় হল $6+2=8$ জন। তবে তা সম্ভব না কেননা টুরনেমেন্টে খেলোয়াড়ই হল $7$ জন। অর্থাৎ ${p_{a_{1}},p_{a_{2}},p_{a_{3}}}∩{p_{b_{1}},p_{b_{2}},,p_{b_{3}}}=∅$ হতে পারবে না। তাহলে ${p_{a_{1}},p_{a_{2}},p_{a_{3}}}∩{p_{b_{1}},p_{b_{2}},,p_{b_{3}}}≠∅$
এখন $n>7$ এর ক্ষেত্রে নতুন সকল $p_7,p_8,…,p_{n-1}$ খেলোয়াড় যদি পূরবের সকল খেলোয়াড়ের সাথে হারে তাহলে $2,n-good$ হবে। কেননা যেকোনো দুইজন খেলোয়াড় নিলেই তাদেরকে একজন অবশ্যই হারিয়েছে।
