Algoritma tabanlı Kombinatorik problemi IMO stili [kopya]
Sorun resimde anlatılmıştır, çözümün yapıcı bir kanıt olduğu varsayılır, bu nedenle çalışma süresi gibi şeylerden bağımsız olarak çalışan bir algoritma bulmanız gerekir. Herhangi bir yardım minnettar olur bunu çözemem ve bir süredir deniyorum
DÜZENLEME: Ana yönüm her ham üzerindeki işareti negatif toplamla değiştirmekti, şimdi her ham tamamlandı ve tüm girişlerin toplamı negatif değil (çünkü tüm hamların toplamı artık negatif değil)
Yanıtlar
Herhangi bir satır veya sütunun toplamı negatifse, birini seçin ve işaretleri tersine çevirin.
Süreci yineleyin.
Her geçişten sonra, matristeki tüm girişlerin toplamı artırılır.
Ancak girişlerin mutlak değeri değişmeden kalır, bu nedenle toplam toplam için yalnızca sonlu sayıda olasılık vardır.
Süreç sonunda sona erecek.
Sadece aşağıdaki basit algoritmayı kullanın: Her dönüşte, rastgele bir satırın veya sütunun işaretlerini negatif toplamla ters çevirin ve bu prosedürün sonlu hareketlerle sona erdiğini kanıtlayacağız: Bu algoritmayı kullanarak tüm sayıların toplamının pano her zaman artacaktır ve bu toplam yukarıdan sınırlı olduğu için ve ayrıca bu toplam için sınırlı olasılıklar olduğu için, algoritmamız bir yerde duracak ve tüm satır ve sütunların toplamının negatif olmadığı bir nokta var.