Cztery zamiany
Jedno z zadań konkursowych zamieszczonych w lipcowym „Świecie Nauki” dotyczyło sortowania:
Zaczynamy od liczby 12345678. Ruch jest zamianą miejscami dwóch duetów, tercetów lub kwartetów sąsiednich cyfr. W ten sposób w co najwyżej siedmiu ruchach należy odwrócić liczbę, czyli zmienić ją w 87654321.
Znałem rozwiązanie tego zadania w 6 ruchach – trochę podstępne, bo operujące wyłącznie duetami cyfr:
12345678 (23-78) > 17845623 (84-23) > 17235684 (17-84) > 84235617 (35-17) > 84217635 (21-35) > 84357621 (43-76) > 87654321.
Okazało się, że w sześciu ruchach można sobie poradzić także bez podstępu, czyli nie ograniczając się do zamieniania miejscami równolicznych grup cyfr.
Kompletnym zaskoczeniem było jednak dla mnie nadesłane przez kilku czytelników rozwiązanie w czterech ruchach. Czy komuś z Państwa uda się je znaleźć? Dodam dla ułatwienia, że jest trochę podstępne.
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co kilka dni.
Komentarze
Będąc nauczony doświadczeniem (nie pamiętam już o jakie zadanie chodziło) mam pytanie: czy ciąg cyfr musi być spójny, czy też możliwe są przerwy pomiędzy cyframi w czasie zamian? Tak gwoli uściślenia reguł. A może właśnie na tym polega owy podstęp 😉
Jeszcze się nie zabrałem za to zadanie i nie wiem czy to pytanie ma sens, ale tak mi intuicja podpowiada.
To może dopowiem, choć może nie powinienem 🙂 : podstęp jest oczywiście analogiczny (co nie znaczy, że identyczny) do opisanego.
mp
Aha, jeszcze jedno: czy w trakcie przenoszenia, można przenosić także przerwę? To znaczy duet cyfr z przerwą wstawić/nałożyc na cyfrę z wolnymi miejscami po obu jej stronach?
To ja proponuję w 3 ruchach 🙂
12345678
1-3-5-7 2-4-6-8
21436587
21–65 43–87
43218765
4321 8765
87654321
Jak zwykle, dopiero teraz doczytałem: „…sąsiednich cyfr…”
…kurcze… jak zwykle 🙁
Zrobiłem sobie przerwę w pracy i przy śniadaniu poszło jak z płatka 🙂 Podpowiedź była zbyteczna:) bo nie mogło być innego podstępu niż zamiana tylko samych trójek:)
A żeby rozwiązać to zadanie w 4 ruchach, automatycznie nasuwał się sposób symetrycznych zamian i zadanie pękło w minutkę.
(123)45(678)
6(784)(512)3
(651)27(843)
8(432)(765)1
87654321
P.S. Komputer musiałby sie uporać tylko z 1296 kombinacjami, co zajęłoby mu ułamek sekundy pewnie… ale czy programista byłby na tyle szybki by spłodzić równie szybko algorytm i go zaprogramować? Myślenie w tym wypadku popłaca, ale zastanawiam się ile jest możliwych rozwiązań w 4 ruchach, dlatego wspomniałem wcześniej o programie.
od razu wpadlem na drugie rozwiazanie:
12345678
15672348
34872156
32154876
87654321
… a teraz … do pracy! 🙂
Już wiem dlaczego nie mogłem wcześniej rozwiązać tego zadania w mniej (być może było to niemożliwe) niż ośmiu ruchach.
Po prostu rozwiązywałem inną łamigłówkę.
Sugerując się przykładem innej przemiany (tej, która miała rozjaśnić problem) podanej w „Umyśle giętkim”, myślałem, że pod pojęciem „sąsiednie cyfry” należy rozumieć nie tylko cyfry tworzące układy duetów, tercetów i kwartetów, ale i same położenie układów (bloków) względem siebie. Gdyby w podanym przykładzie zamieniane układy (bloki) cyfr nie wszystkie były sąsiadami, to myślę, że nie dałbym się „wpuścić w maliny” niepotrzebnie nakładając na zadanie dodatkowy warunek i być może podałbym jako rozwiązanie na przykład taką przemianę:
12345678 (123-678)
67845123 (784-512)
65127843 (651-843)
84327651 (432-765)
87654321
Nie wiem czy mi te „podstępności” za bardzo nie namieszały w głowie, gdyż zaczynam zgrzytać zębami, a póki co udało mi się znaleźć tylko takie pół-rozwiązanie:
1. (234-678) 16785234
2. (167-852) 85216734
3. (521-734) 87346521
4. (34-65) 87653421
I tylko jeszcze muszę zamienić miejscami 3 z 4…
🙂
mp
Z pomocą arkusza kalkulacyjnego i uwzględnieniu tylko tercetów:
12345678 (123-678)
67845123 (784-512)
65127843 (651-843)
84327651 (432-765)
87654321
i
12345678 (234-567)
15672348 (156-348)
34872156 (487-215)
32154876 (321-876)
87654321
Ładne te rozwiązania. Rotują brzegi, środek, brzegi, środek lub na odwrót.
wow, szacun dla tych, którym udało się to zadanie rozwiązać..