Pytanie :
Jesteś na dole szybu windy w 100-piętrowym budynku.
Widzisz 21 przewodów oznaczonych 1 2 3… 21.
Przewody prowadzą na 100. piętro, gdzie końce są oznaczone A B C… U, ale nie wiadomo, jak odpowiadają końcówkom na dole.
Masz baterię, żarówkę i wiele małych przewodów.
Jaka jest minimalna liczba podróży wymagana do znalezienia pary pomiędzy literami i cyframi?
Należy pamiętać, że połączenie małych przewodów w celu utworzenia przewodu o długości 21 pięter nie wchodzi w grę.
Rozwiązanie :
Pamiętaj, że bateria, żarówka i małe przewody służą w zasadzie do testowania połączenia, a „podłączony” jest relacją równoważności.
Na dole zostaw 1 niepodłączony, połącz ze sobą 2 i 3, połącz ze sobą 4–6, 7–10 itd., Abyśmy mieli „klasy równoważności” powiązań rozmiarów 1, 2, 3, 4, 5 i 6.
Teraz udaj się na górę i dowiedz się, które litery nie są połączone z niczym innym, z jedną inną literą, z dwoma innymi itd., dopóki nie wymyślisz klas równoważności.
Teraz połącz pierwsze litery z każdej klasy równoważności (jest ich 6) w nowej klasie równoważności, drugie z każdej (5 z nich) w drugiej itd. Zejdź na dół, usuń pierwotne połączenia i znajdź nowe klasy równoważności w podobny sposób.
Wiemy teraz z pierwszego zestawu klas, które grupy n liter (dla n=1 do 6) na górze odpowiadają jakim grupom n liczb na dole. Z drugiego zestawu klas wiemy teraz, które litery i cyfry były „pierwsze” w swoich pierwotnych klasach, które były „drugimi” itd., więc mamy pełne parowanie.
To rozwiązanie działa czysto dla dowolnej trójkątnej liczby drutów, ale można je łatwo dostosować do pracy dla wszystkich liczb naturalnych większych niż 2.
Dziękuje za przeczytanie
Placewit rozwija najlepszych inżynierów, zapewniając interaktywne zajęcia w klasie oraz pomagając im rozwijać swoje umiejętności i dostać się do niesamowitych firm.
Więcej informacji znajdziesz na Placewit. Śledź nas na Instagramie i Facebooku, aby codziennie się uczyć.
