หมากรุก

[ฟินิกซ์เหินฟ้า]

วางหมากรุก $6$ ตัว ในตาราง $4\times4$ พิสูจน์ว่ามีวิธีเลือก 2 rows and columns ซึ่งเมื่อหลังจากตัด
2 rows and columns ออกไป จะไม่มีหมากบนกระดานเลย

[passer-by]

ข้อความเดิมเขียนโดยคุณ ฟินิกซ์เหินฟ้า

วางหมากรุก $6$ ตัว ในตาราง $4\times4$ พิสูจน์ว่ามีวิธีเลือก 2 rows or columns ซึ่งเมื่อหลังจากตัด
2 rows or columns ออกไป จะไม่มีหมากบนกระดานเลย

โจทย์น่าจะเป็น 2 rows and 2 columns มากกว่านะครับ

วิธีพิสูจน์ ก็ใช้หลักรังนกพิราบ อ้างว่ามีบางแถว ที่มีหมาก อย่างน้อย 2 ตัว

Take 2 แถวที่มีหมาก มากสุด ออกไป ซึ่งพิสูจน์ได้ไม่ยากว่า หมาก 2 แถวนี้ รวมกัน $ \geq 4$ ตัว

จากนั้น มันก็จะเหลือหมาก อีกไม่เกิน 2 ตัว ก็เลือก 2 columns ที่ cover หมากที่เหลือ

[analysisway]

เอิ่ม ใช้ Rook Polynomial รึเปล่าครับ ผมเคยเห็นว่าจัดปัญหาแบบนี้ในการแก้โจทย์น่ะครับ

[polsk133]

ตอนแรกมี 6 ตัว จะได้ว่ามีอย่างน้อย1แถวมีอย่างน้อย2ตัว ตัดแถวนั้นออก

เหลืออย่างมาก 4 ตัวกับ 3 แถว จะได้ว่ามี1แถวที่มีอย่างน้อย2ตัว ตัดแถวนั้นออก(คิดกรณีแย่สุด)

เหลือ2ตัวกับ 2แถว*4คอลัม ก็ตัดคอลัมที่มีแต่ละตัวออกไป