สำหรับคนอยากฝึก double counting
1. พิจารณากลุ่มของคน $n$ คน ใดๆ กำหนดให้ $a$ รู้จักกับ $b$ ก็ต่อเมื่อ $b$ รู้จักกับ $a$ ให้ $S=\{\{a,b\}\mid a\ รู้จักกับ\ b\}$ ถ้า $$|S|> \dfrac{n}{4}(1+\sqrt{4n-3})$$ จงพิสูจน์ว่า มี $a,b,c,d$ ในกลุ่มนี้ ที่ทำให้ $a$ รู้จัก $b$, $b$ รู้จัก $c$, $c$ รู้จัก $d$ และ $d$ รู้จัก $a$ (APMO 1989)
2. ให้ $N\in\mathbb{N}$ และให้ $S$ เป็นระบบส่วนตกค้างบริบูรณ์ $\pmod {N^2}$
ให้ $A\subset S$ ที่ $|A|=N$ จงพิสูจน์ว่ามี $B\subset S$ ที่ทำให้
(i) $|B|=N$
(ii) ถ้า $A+B=\{a+b\mid a\in A, b\in B\}$ แล้ว $|A+B|\ge 0.6N^2$ (ยากกว่า IMO SL 1999 C4)
3. พิจารณาจุด $n$ จุดใดๆ ในกระดาษ A4 ที่เมื่อลากเชื่อม 2 จุดใดๆ เส้นที่ได้จะต้องไม่ขนานกับด้านทั้ง 4 ของกระดาษ และไม่มีจุดใดๆ อยู่ตรงมุมหรือขอบกระดาษ
จงพิสูจน์ว่าถ้าเราตัดกระดาษเป็นรูปสี่เหลี่ยมผืนผ้าหลายๆ ชิ้น โดยที่จุดทุกจุดจะต้องเป็นมุมหรือขอบของกระดาษที่ถูกตัด แล้วเราจะต้องตัดกระดาษออกเป็นอย่างน้อย $n+1$ ชิ้น
(IMO SL 2014 C1)
4. ในกลุ่มคนที่มี $2n+1$ คน ซึ่งมีสมบัติว่า ทุกๆ เซต $S$ ของคน $n$ คน จะมีอย่างน้อย $1$ คนนอก $S$ แต่เป็นเพื่อนกับทุกคนใน $S$
จงพิสูจน์ว่ามีอย่างน้อย $1$ คน ที่เป็นเพื่อนกับทุกๆ คนใน $S$
|