รูปแบบ IMO ที่ใช้อัลกอริทึม Combinatorics [ซ้ำ]
ปัญหาถูกอธิบายไว้ในรูปภาพวิธีแก้ปัญหานั้นเป็นหลักฐานเชิงสร้างสรรค์ดังนั้นคุณต้องหาอัลกอริทึมที่ใช้งานได้โดยไม่คำนึงถึงสิ่งต่างๆเช่นเวลาทำงาน ความช่วยเหลือใด ๆ ที่จะทำให้ฉันไม่สามารถแก้ปัญหานี้ได้และฉันพยายามมาระยะหนึ่งแล้ว
![](https://post.nghiatu.com/assets/images/s/Oetzk.jpg)
แก้ไข: ทิศทางหลักของฉันคือการเปลี่ยนเครื่องหมายบนทุกดิบด้วยผลรวมเชิงลบตอนนี้ทุกดิบเสร็จสมบูรณ์และผลรวมของรายการทั้งหมดไม่เป็นค่าลบ (เนื่องจากผลรวมของดิบทั้งหมดไม่เป็นค่าลบในขณะนี้)
คำตอบ
หากแถวหรือคอลัมน์ใดมีผลรวมเป็นลบให้เลือกหนึ่งรายการและกลับเครื่องหมาย
ทำซ้ำกระบวนการ
หลังจากการเปลี่ยนแปลงแต่ละครั้งผลรวมของรายการทั้งหมดในเมทริกซ์จะเพิ่มขึ้น
แต่ค่าสัมบูรณ์ของรายการยังคงไม่เปลี่ยนแปลงดังนั้นจึงมีความเป็นไปได้มากมายสำหรับผลรวมทั้งหมดเท่านั้น
เป็นไปตามที่กระบวนการจะยุติลงในที่สุด
เพียงใช้อัลกอริทึมง่ายๆต่อไปนี้: ในแต่ละเทิร์นให้ย้อนสัญญาณของแถวหรือคอลัมน์แบบสุ่มด้วยผลรวมลบและเราจะพิสูจน์ว่าขั้นตอนนี้สิ้นสุดลงด้วยการเคลื่อนไหวที่ จำกัด : โปรดทราบว่าการใช้อัลกอริทึมนี้จะทำให้ผลรวมของตัวเลขทั้งหมด บอร์ดจะเพิ่มขึ้นเสมอและเนื่องจากผลรวมนี้มีขอบเขตจากด้านบนและมีความเป็นไปได้ จำกัด สำหรับผลรวมนี้อัลกอริทึมของเราจะหยุดอยู่ที่ใดที่หนึ่งและมีจุดที่ผลรวมของแถวและคอลัมน์ทั้งหมดไม่เป็นลบ