Zadanie 6
2021
Etap I
★★★☆☆Kombinatoryka
Logika
Tablica ze strzałkami
Treść zadania
W każdym polu tablicy znajduje się strzałka skierowana w górę, w dół, w lewo lub w prawo. Wykaż, że można tak usunąć z tablicy 50 strzałek, aby żadne dwie z pozostałych nie wskazywały na siebie nawzajem.
*Uwaga:* Strzałki wskazują na siebie nawzajem także wtedy, gdy ich pola nie sąsiadują lub gdy pomiędzy nimi są inne strzałki.
*Uwaga:* Strzałki wskazują na siebie nawzajem także wtedy, gdy ich pola nie sąsiadują lub gdy pomiędzy nimi są inne strzałki.
Umiejętności (3)
Wymagane umiejętności:
Grafy
Zdobywane umiejętności:
Grafy
Konstrukcja przykładu
Wskazówki (0/4)
Wskazówka 1
Zastanów się, czy strzałka pozioma może kiedykolwiek 'wskazywać' na strzałkę pionową? Zauważ, że konflikty (wzajemne wskazanie) mogą zdarzyć się tylko między strzałkami leżącymi w tym samym wierszu lub w tej samej kolumnie.
Wskazówka 2
Skoro strzałki poziome nie wchodzą w konflikt z pionowymi, możesz podzielić problem na dwie niezależne części. Rozważ osobno zbiór wszystkich strzałek w wierszach (lewo/prawo) i osobno zbiór strzałek w kolumnach (góra/dół).
Wskazówka 3
Skup się na pojedynczym wierszu. Konflikt powstaje, gdy strzałka w prawo 'patrzy' na strzałkę w lewo. Jak w najprostszy sposób wyeliminować WSZYSTKIE konflikty w tym wierszu, decydując się na zachowanie tylko jednego rodzaju strzałek?
Wskazówka 4
W każdym wierszu zostaw tylko te strzałki, których jest więcej (np. same w lewo). Zrób to samo niezależnie dla każdej kolumny. Wykaż, że sumując te wybory, zachowasz łącznie co najmniej połowę wszystkich strzałek.