zadanie zadanie: Mamy do dyspozycji pary uporzadkowane o wspolrzednych nalezacych do zbioru {1, 2, 3, ..., n}. Ukladamy je w ciag, przy czym sasiednie wspolrzedne musza byc rowne np. (1,2)(2,3). Chodzi o to, zeby zaczynajac od dowolnej pary dla danego n ulozyc je w ciag skladajacy sie ze wszystkich mozliwych par dla danego n. W jaki sposob obliczyc liczbe takich ciagow? A ile bedzie takich, ktorych nie da sie ulozyc ze wszystkich par?

wredulus_pospolitus: nie bardzo rozumiem zapis: (1,2)(2,3)

wredulus_pospolitus: rozumiem, że jak mamy jedną parę (1,2) to następna musi się zaczynać od 2 ... czyli np. (2,3) tak?

zadanie: chcialem podac przyklad, ze pierwsza wspolrzedna kolejnej pary musi byc taka sama jak druga wspolrzedna poprzedniej pary np. (1,2)(2,3)(3,1)(1,1)

jc: Czy chodzi o takie ciągi? (1,1)(1,2)(2,3)(3,3)(3,2)(2,2)(2,1)(1,3)(3,1)

wredulus_pospolitus: Jeżeli może być tak jak jc napisał to należy zauważyć następującą rzecz: 1) WYWALAMY z tego ciągu wszystkie pary (a,a) otrzymujemy ciąg: (1,2)(2,3)(3,2)(2,1)(1,3)(3,1) 2) Liczba ciągów która może powstać z tych par jest równa liczbie tych elementów (więc mamy ich 6) 3) teraz dorzucamy pary (a,a) które mogą być w 'dowolnym miejscu' gdzie mamy (b,a)(a,c), dodatkowo zauważamy że każdy ten ciąg zaczyna się i kończy na tą samą cyfrę więc mamy: 3*2*2 = 12 możliwości co daje nam łącznie 6*12 = 72 możliwości Ale to było dla n=3 Dla n=4 sytuacja będzie trudniejsza (1,2)(2,3)(3,4)(4,3)(3,2)(2,1)(1,3)(3,1)(1,4)(4,3)(3,4)(4,2)(2,4)(4,1) bo tutaj możemy wewnętrzne 'podciągi' (chodzi mi o np. (1,3)(3,1) oraz (1,4)(4,3)(3,4)(4,2)(2,4)(4,1) ) które można spokojnie zamienić ze sobą miejscami I wydaje mi się, że w tym zadaniu trzeba by było stworzyć ciąg rekurencyjny.

zadanie: Dziekuje. Czy mozna to odniesc do liczby sciezek w grafie? 1 ciag to 1 sciezka

jc: Tak. W pełnym grafie skierowanym z pętelkami.

zadanie: Ok. A czy jest tez mozliwosc obliczenia tych ciagow umieszczajac te punkty w ukladzie wspolrzednych i przekladajac to geometrycznie?

wredulus_pospolitus: Wybacz ... dawno miałem do czynienia z zadaniami 'grafowymi', ale o co Ci chodzi z 'przekładając to geometrycznie' Jeżeli przedstawisz pary geometrycznie i zaczniesz robić ścieżkę (czyli de facto będziesz budował graf) to będzie to cholernie nieczytelne

zadanie: Zalozmy,ze mamy ciag (3,a)...(b, 3), gdzie pomiedzy (3,a) oraz (b,3) sa wszystkie mozliwe pary z trojka (dla daneg n) z wczesniej opisana zasada ukladania. Czy taki ciag, ktory jest juz nieprzedluzalny musi taki byc?

Pytający: Wredulus, dla n=3 jest 216 takich ciągów: https://ideone.com/xlenaB . "Czy taki ciag, ktory jest juz nieprzedluzalny musi taki byc?" Nie rozumiem, o co pytasz.

zadanie: Dziekuje. A gdyby (a,b)=(b,a) (wtedy nie bylyby juz to pary uporzadkowane) to jak pozliczac te ciagi?

zadanie: Czyli wtedy mozemy rozwazac pary uporzadkowane (a,b), ale takie, ze a≤b.

jc: Jeśli utożsamimy (a,b) z (b,a) to rozwiązanie będzie możliwe tylko dla nieparzystych n. Dla n=7 mamy ułożenia domina w cykl. W każdym wypadku zadanie wydaje się bardzo trudne, a pomysł, aby spojrzeć na pary, jak na punkty bardzo mi się spodobał.

zadanie: A z czego wynika to, ze tylko dla nieparzystych n jest rozwiazanie?

zadanie: Sądze, ze chodzi o twierdzenie Eulera odnosnie cykli.

zadanie: Dlaczego w każdym wypadku zadanie wydaje się bardzo trudne?

zadanie: W sensie, ze zalezy od n czy ogolnie zadanie jest trudne?

zadanie : Czyli podsumowujac mamy takie warunki: 1. Pierwsza współrzędna kolejnej pary musi być taka sama jak druga współrzędna poprzedniej pary 2. Rozważamy pary (a, b) takie, że a≤b Jak obliczyć liczbę takich ciągów dla {1,2,3}? Jak do tego podejść kombinatorycznie np. wykorzystując grafy?

Pytający: Elementy (wyrazy ciągu) mogą się powtarzać? Ciągi dowolnej długości?

zadanie: Chodzi o to, zeby zaczynajac od dowolnej pary dla danego n ulozyc je w ciag skladajacy sie ze wszystkich mozliwych par dla danego n. Elementy nie moga sie powtarzac.

Pytający: Więc: • dla n=1 jest 1 taki ciąg: ((1, 1)), • dla n=2 jest 1 taki ciąg: ((1, 1), (1, 2), (2, 2)), • dla n≥3 jest 0 takich ciągów, przecież jest tylko jedna para postaci (a, 1), natomiast par postaci (1, b) dla b≠1 jest n−1≥2.

zadanie: Ok. Dziekuje. Warunek: rozważamy pary (a, b) takie, że a≤b zamieniam na: utożsamiamy (a,b) z (b,a). Wowczas: Dla n=3 mamy np.: 1) (1,1)(1,2)(2,2)(2,3)(3,3)(3,1) 2) (1,1)(1,3)(3,3)(3,2)(2,2)(2,1) 3) (1,2)(2,2)(2,3)(3,3)(3,1)(1,1) itd. wyszlo mi 12 takich ciagow. Jak je zliczyc kombinatorycznie? Jak obliczyc te ciagi dla pozostalych n?

zadanie: Zrobie nowy temat, zeby bylo czytelniej.

zadanie: https://matematykaszkolna.pl/forum/388116.html