Na ile sposóbów można ułożyć klocki> Andrew: Ania ma klocki o rozmiarach 2x1 i 1x2 Chce je ułożyć na planszy o rozmiarach a) 4 na 5 b) 6 na 3 Na ile sposobów może to zrobić? Proszę o pomoc, próbowałem symbolem newtonowskim, ale licząc pierwszy przykład nie wychodzi

Andrew: Dodam że klockow nie mozna obrać

Andrew: Dodam że klocków nie mozna obracać

PW: Klocki o rozmiarach 1×2 i 2×1, ale nie wolno ich obracać − po co takie mącenie w głowie?

Andrew: Taka treść zadania, ja na nią nie wplywam...

Maslanek: Może w taki sposób: 1. Bierzemy klocek 2x1, który towrzy ciąg skończony o wyrazach (2,1) 2. Jak wyżej, tyle, że bierzemy 1x2 i mamy ciąg (1,2) a) Dodajemy klocki do planszy: ilość możliwych ułożeń odpowiada ilości rozwiązań równania x*(2,1)+y(1,2)=(4,5) w liczbach naturalnych Czyli układ: 2x+y=4 x+2y=5 b) podobnie i równanie x*(2,1)+y*(1,2)=(6,3). Czyli układ: 2x+y=6 x+2y=3 Na pewno znajdziemy w ten sposób pewne rozwiązanie (czy wszystkie?) Znając ilość x i y byłoby się trzeba jeszcze zastanowić nad ilością ustawień takich klocków

Maslanek: Coś dziwnego wymyśliłem W ogóle się kupy nie trzyma

jerey:

MQ: Doprecyzuj: 1. Co oznacza 2x1? 2 wiersze 1 kolumna czy odwrotnie? 2. Czy liczba klocków nieograniczona?

PW: a) Każde rozwiązanie zadania można utożsamić z macierzą o 5 wierszach i 4 kolumnach, której wyrazy są zerami lub jedynkami, np. 0000 1111 1111 1111 1111 jest macierzą odpowiadająca rozwiązaniu "w pierwszym wierszu dwa poziome klocki, reszta zapełniona klockami pionowymi". Pola zapełnione zerami oznaczają klocki poziome, pola zapełnione jedynkami − klocki pionowe. Przy takiej interpretacji zadanie sprowadza się do znalezienia liczby macierzy, których wiersze składają się z wektorów (1) [0000], [0011]. [1100], [1001], [1111] i jednocześnie kolumny składają się z wektorów (zapiszę je poziomo): (2) [00000], [01111], [11011], [11110], [00011], [00110], [011000], [11000]. Takie ograniczenia wynikają z treści zadania − pola oznaczone zerami muszą występować kolejno parzyście w poziomie, a pola oznaczone jedynkami − kolejno parzyście w pionie Wypisanie "ręczne" wszystkich macierzy o wierszach ze zbioru (1) i kolumnach ze zbioru (2) wymagałoby skupienia i czasu wartego lepszej sprawy, dlatego sądzę, że jest to zadanie dla informatyka. Na przykład wygenerować wszystkie możliwe macierze o wierszach ze zbioru (1) − jest ich raptem 5⁵ = 3125 − a następnie weryfikować kolejne kolumny tych macierzy (czy spełniają warunek należenia do zbioru (2), co daje najwyżej 4 sprawdzenia dla każdej macierzy). Mój komputer podaje wynik 95, ale byłoby interesujące jak to wyliczyć bez komputera i bez wypisywania. Na wszelki wypadek podaję uzyskane macierze: 1. − same poziome klocki 0000 0000 0000 0000 0000 2. − dwa pionowe klocki, reszta poziome 0000 0000 0000 0011 0011 3. − dwa pionowe klocki 0000 0000 0000 1001 1001 4. 0000 0000 0000 1100 1100 5. 0000 0000 0000 1111 1111 6. 0000 0000 0011 0011 0000 7. 0000 0000 0011 1111 1100 8. 0000 0000 1001 1001 0000 9. 0000 0000 1100 1100 0000 10. 0000 0000 1100 1111 0011 11. 0000 0000 1111 1111 0000 12. 0000 0011 0011 0000 0000 13. 0000 0011 0011 0011 0011 14. 0000 0011 0011 1001 1001 15. 0000 0011 0011 1100 1100 16. 0000 0011 0011 1111 1111 17. 0000 0011 1111 1100 0000 18. 0000 0011 1111 1111 0011 19. 0000 1001 1001 0000 0000 20. 0000 1001 1001 0011 0011 21. 0000 1001 1001 1001 1001 22. 0000 1001 1001 1100 1100 23. 0000 1001 1001 1111 1111 24. 0000 1001 1111 1111 1001 25. 0000 1100 1100 0000 0000 26. 0000 1100 1100 0011 0011 27. 0000 1100 1100 1001 1001 28. 0000 1100 1100 1100 1100 29. 0000 1100 1100 1111 1111 30. 0000 1100 1111 0011 0000 31. 0000 1100 1111 1111 1100 32. 0000 1111 1111 0000 0000 33. 0000 1111 1111 0011 0011 34. 0000 1111 1111 1001 1001 35. 0000 1111 1111 1100 1100 36. 0000 1111 1111 1111 1111 37. 0011 0011 0000 0000 0000 38. 0011 0011 0000 0011 0011 39. 0011 0011 0000 1001 1001 40. 0011 0011 0000 1100 1100 41. 0011 0011 0000 1111 1111 42. 0011 0011 0011 0011 0000 43. 0011 0011 0011 1111 1100 44. 0011 0011 1001 1001 0000 45. 0011 0011 1100 1100 0000 46. 0011 0011 1100 1111 0011 47. 0011 0011 1111 1111 0000 48. 0011 1111 1100 0000 0000 49. 0011 1111 1100 0011 0011 50. 0011 1111 1100 1001 1001 51. 0011 1111 1100 1100 1100 52. 0011 1111 1100 1111 1111 53. 0011 1111 1111 0011 0000 54. 0011 1111 1111 1111 1100 55. 1001 1001 0000 0000 0000 56. 1001 1001 0000 0011 0011 57. 1001 1001 0000 1001 1001 58. 1001 1001 0000 1100 1100 59. 1001 1001 0000 1111 1111 60. 1001 1001 0011 0011 0000 61. 1001 1001 0011 1111 1100 62. 1001 1001 1001 1001 0000 63. 1001 1001 1100 1100 0000 64. 1001 1001 1100 1111 0011 65. 1001 1001 1111 1111 0000 66. 1001 1111 1111 1001 0000 67. 1100 1100 0000 0000 0000 68. 1100 1100 0000 0011 0011 69. 1100 1100 0000 1001 1001 70. 1100 1100 0000 1100 1100 71. 1100 1100 0000 1111 1111 72. 1100 1100 0011 0011 0000 73. 1100 1100 0011 1111 1100 74. 1100 1100 1001 1001 0000 75. 1100 1100 1100 1100 0000 76. 1100 1100 1100 1111 0011 77. 1100 1100 1111 1111 0000 78. 1100 1111 0011 0000 0000 79. 1100 1111 0011 0011 0011 80. 1100 1111 0011 1001 1001 81. 1100 1111 0011 1100 1100 82. 1100 1111 0011 1111 1111 83. 1100 1111 1111 1100 0000 84. 1100 1111 1111 1111 0011 85. 1111 1111 0000 0000 0000 86. 1111 1111 0000 0011 0011 87. 1111 1111 0000 1001 1001 88. 1111 1111 0000 1100 1100 89. 1111 1111 0000 1111 1111 90. 1111 1111 0011 0011 0000 91. 1111 1111 0011 1111 1100 92. 1111 1111 1001 1001 0000 93. 1111 1111 1100 1100 0000 94. 1111 1111 1100 1111 0011 95. − osiem klocków pionowych i dwa poziome 1111 1111 1111 1111 0000

Dziadek Mróz: PW napisał algorytm w C bo wątpię aby tyle wyklepał

PW: No pewnie, obojętne w jakim języku, ale na ręczne wklepywanie szkoda życia (nie mówiąc o dużym prawdopodobieństwie pomyłki).

PW: Trochę poczytałem, nie uczyłem się matematyki dyskretnej, więc nie dziwota, że nie umiałem znaleźć rozwiązania. Zadanie jest niebanalne − dla pokrycia prostokąta 2×n rozwiązaniem jest ponoć ... ciąg Fibonacciego. Co dla innych rozmiarów − strach pomyśleć. Ładnie to tak − na forum dla licealistów wrzucić zadanie dla gigantów i nawet się nie nakierować na źródła?

PW: Przepiękny, powalający na kolana wzór jest np. pod http://warsztatywww.wdfiles.com/local--files/www10:kafelkowania-drzewa-wyznaczniki/domino