Problem kombinatoryki oparty na algorytmie w stylu IMO [duplikat]

Jan 03 2021

Problem jest opisany na rysunku, rozwiązanie ma być konstruktywnym dowodem, więc musisz znaleźć algorytm, który będzie działał niezależnie od rzeczy, takich jak czas działania. Jakakolwiek pomoc byłaby ogromna. Nie mogę tego rozwiązać i próbuję przez jakiś czas

EDYCJA: Moim głównym kierunkiem była zmiana znaku na każdym surowym z sumą ujemną, teraz każdy nieprzetworzony jest kompletny, a suma wszystkich wpisów jest nieujemna (ponieważ suma wszystkich surowych jest teraz nieujemna)

Odpowiedzi

1 quasi Jan 03 2021 at 15:30

Jeśli jakikolwiek wiersz lub kolumna ma sumę ujemną, wybierz jeden i odwróć znaki.

Powtórz proces.

Po każdym przejściu suma wszystkich wpisów w macierzy jest zwiększana.

Ale bezwzględna wartość wpisów pozostaje niezmieniona, stąd możliwości uzyskania całkowitej sumy jest tylko skończenie wiele.

Wynika z tego, że proces ostatecznie się zakończy.

1 AryanHemmati Jan 03 2021 at 15:33

Po prostu użyj następującego prostego algorytmu: w każdej turze odwróć znaki losowego wiersza lub kolumny z sumą ujemną, a udowodnimy, że ta procedura kończy się ruchami skończonymi: Zauważ, że używając tego algorytmu, suma liczb we wszystkich tablica zawsze będzie rosła, a ponieważ ta suma jest ograniczona od góry, a także istnieją skończone możliwości dla tej sumy, nasz algorytm gdzieś się zatrzyma i chodzi o to, że suma wszystkich wierszy i kolumn jest nieujemna.