C8 (สอวน) ทีม 2011 ทีมแข่งเทนนิสพบกันหมด แต่ละคู่เป็นได้แค่แพ้หรือชนะเท่านั้น เรียก 3 ทีมใดๆว่า "กลุ่มทัดเทียม" ก็ต่อเมื่อแต่ละทีมในกลุ่มจะแพ้หนึ่งทีมในกลุ่ม และชนะหนึ่งทีมในกลุ่ม จงหาค่ามากสุดของจำนวนกลุ่มทัดเทียม
(ข้อนี้ใช้หลักการเดียวกับโจทย์ที่พี่ Passer-by เคยเอามาลงครับ แค่เปลี่ยนจากเป่ายิ้งฉุบ 23 คนเป็นแข่งเทนนิส 2011 ทีมเท่านั้นเอง
)
ให้ cyclic คือกลุ่มทัดเทียมตามโจทย์ และ non-cyclic ก็คือตรงข้ามกัน
ดังนั้นเราจะนับกลุ่ม non-cyclic ที่น้อยสุดที่เป็นไปได้แทน และใช้อสมการ Jensen ที่กล่าวว่า
ถ้า f เป็น convex function (ฟังก์ชันนูน) ในช่วง $I$ แล้ว $\sum f(x_i)\geqslant n\cdot f(\frac{x_1+x_2+...+x_n}{n})$ ทุก $x_i \in I$
ซึ่ง $f(x)=\pmatrix{x\\ 2} =\frac{x(x-1)}{2}$ ก็เป็น convex function ($\frac{d^2}{dx^2}f(x)>0$ ทุก $x>0$)
และค่าต่ำสุดเกิดเมื่อ $x_1,x_2,x_3,...x_n$ มีค่าใกล้เคียงกัน เพราะบางที $\frac{x_1+x_2+...+x_n}{n}$ ไม่เป็นจำนวนเต็ม จึงต้องเลือกค่าที่ใกล้เคียงกันและทำให้ค่าเฉลี่ยเป็นจำนวนเต็ม
กลับมาดูที่ non-cyclic แสดงว่าต้องมี 1 ทีมที่ชนะอีก 2 ทีมหรือมี 1 ทีมที่แพ้อีก 2 ทีม โดยให้ $a_i$ แทนจำนวนครั้งที่ทีมที่ $i$ ชนะ
ดังนั้นจำนวน non-cyclic = $\sum\pmatrix{a_i\\2} $ เพราะในทีมที่ $i$ จะสร้างกลุ่ม non-cyclic ได้จากการเลือกสองทีมที่ $i$ ชนะ
แต่เราสามารถนับอีกแบบได้คือ นับจำนวนทีมที่ $i$ แพ้ ซึ่งมีอยู่ $2010-a_i$ ทีม
ดังนั้นจำนวน non-cyclic = $\sum\pmatrix{2010-a_i\\2} $
รวมสองอันจึงได้ จำนวน non-cyclic = $\frac{1}{2}\left[\,\sum\pmatrix{a_i\\2}+\sum\pmatrix{2010-a_i\\2}\right] $
แต่โดยอสมการเจนเซน, $\pmatrix{a_i\\2}+\pmatrix{2010-a_i\\2}\geqslant 2 \pmatrix{1005\\2}$ และสมการเกิดเมื่อ $a_i=1005$
นั่นคือจำนวน non-cyclic $\geqslant \frac{1}{2}\left(\, 2011\cdot 2 \pmatrix{1005\\2} \right)=2011\cdot \pmatrix{1005\\2}$
ทำให้จำนวน cyclic $\leqslant \pmatrix{2011\\3}-2011\cdot \pmatrix{1005\\2}$
$\therefore$ จำนวนกลุ่มทัดเทียมมากสุดที่เป็นไปได้คือ $\pmatrix{2011\\3}-2011\cdot \pmatrix{1005\\2}$ เกิดเมื่อทุกทีมชนะ 1005 ทีมและแพ้ 1005 ทีมพอดี