รูปแบบ IMO ที่ใช้อัลกอริทึม Combinatorics [ซ้ำ]

Jan 03 2021

ปัญหาถูกอธิบายไว้ในรูปภาพวิธีแก้ปัญหานั้นเป็นหลักฐานเชิงสร้างสรรค์ดังนั้นคุณต้องหาอัลกอริทึมที่ใช้งานได้โดยไม่คำนึงถึงสิ่งต่างๆเช่นเวลาทำงาน ความช่วยเหลือใด ๆ ที่จะทำให้ฉันไม่สามารถแก้ปัญหานี้ได้และฉันพยายามมาระยะหนึ่งแล้ว

แก้ไข: ทิศทางหลักของฉันคือการเปลี่ยนเครื่องหมายบนทุกดิบด้วยผลรวมเชิงลบตอนนี้ทุกดิบเสร็จสมบูรณ์และผลรวมของรายการทั้งหมดไม่เป็นค่าลบ (เนื่องจากผลรวมของดิบทั้งหมดไม่เป็นค่าลบในขณะนี้)

คำตอบ

1 quasi Jan 03 2021 at 15:30

หากแถวหรือคอลัมน์ใดมีผลรวมเป็นลบให้เลือกหนึ่งรายการและกลับเครื่องหมาย

ทำซ้ำกระบวนการ

หลังจากการเปลี่ยนแปลงแต่ละครั้งผลรวมของรายการทั้งหมดในเมทริกซ์จะเพิ่มขึ้น

แต่ค่าสัมบูรณ์ของรายการยังคงไม่เปลี่ยนแปลงดังนั้นจึงมีความเป็นไปได้มากมายสำหรับผลรวมทั้งหมดเท่านั้น

เป็นไปตามที่กระบวนการจะยุติลงในที่สุด

1 AryanHemmati Jan 03 2021 at 15:33

เพียงใช้อัลกอริทึมง่ายๆต่อไปนี้: ในแต่ละเทิร์นให้ย้อนสัญญาณของแถวหรือคอลัมน์แบบสุ่มด้วยผลรวมลบและเราจะพิสูจน์ว่าขั้นตอนนี้สิ้นสุดลงด้วยการเคลื่อนไหวที่ จำกัด : โปรดทราบว่าการใช้อัลกอริทึมนี้จะทำให้ผลรวมของตัวเลขทั้งหมด บอร์ดจะเพิ่มขึ้นเสมอและเนื่องจากผลรวมนี้มีขอบเขตจากด้านบนและมีความเป็นไปได้ จำกัด สำหรับผลรวมนี้อัลกอริทึมของเราจะหยุดอยู่ที่ใดที่หนึ่งและมีจุดที่ผลรวมของแถวและคอลัมน์ทั้งหมดไม่เป็นลบ