wieże na szachownicy

[Zordon]

Na szachownicy \(\displaystyle{ n \times m}\) dla \(\displaystyle{ n \le m}\) umieszczono \(\displaystyle{ m(k-1)+1}\) wież. Pokaż, że istnieje \(\displaystyle{ k}\) wież, które nie atakują się wzajemnie.

[Dumel]

przy ustalnym m udowodnie to indukcyjnie po n. (w dalszej czesci: m-wiersze, n-kolumny)
dla n=1 wiadomo
załóżmy że jest ok dla \(\displaystyle{ 1,2,...,n-1}\)
mamy \(\displaystyle{ m(k-1)+1}\) wież wiec w pewnym wierszu jest co najwyżej k-1 (aha no to sobie załóżmy że m>1 bo inaczej nie działa). (możemy założyć że w tym wierszu jest co najmniej jedna wieża bo puste wiersze i kolumny możemy sobie wywalić)
weźmy dowolną z tych wież, usuńmy jej kolumnę i wiersz
usunęliśmy co najwyżej m+k-2 wież i teraz mamy szachownice \(\displaystyle{ m-1 \ \times n-1}\) i co najmniej \(\displaystyle{ (m-1)(k-2)+1}\) wież czyli ok i z założenia indukcyjnego mamy teze

aha to właściwie troche źle sformułowałem, ale łatwo to przerobić (nie chce mi sie tego robić) na poprawny dowod z indukcją np po \(\displaystyle{ m+n}\)

[Zordon]

Ja to widze jako indukcja po porządku leksykograficznym \(\displaystyle{ (n,m,k)}\). Myślałem, że da się tego uniknąć w tym zadaniu ;D