[Kombinatoryka] ustawianie klocków

[robin5hood]

Mamy \(\displaystyle{ \frac{n(n+1)}{2}}\) klocków z liczbami: jeden klocek z "1", dwa klocki z "2", ..., n klocków z "\(\displaystyle{ n}\)".

Dla jakich \(\displaystyle{ n}\) można te klocki tak ustawić by
między każdymi dwoma \(\displaystyle{ n}\)-ami był jeden klocek,
między kazdymi dwoma klockami z \(\displaystyle{ n-1}\) dwa inne klocki, itd.
wreszcie między klockami z dwójkami \(\displaystyle{ n-1}\) klocków ??

[silvaran]

nie ma napisanego warunku dla n więc
dla \(\displaystyle{ n=2}\) zachodzi ten warunek, a ciąg wygląda tak:
\(\displaystyle{ 212}\)
nie poddaje się i szukam dalej

[Swistak]

nie ma napisanego warunku dla n więc

Nie ma napisanego, bo mamy go wymyśleć .

[silvaran]

no ale powinni zaznaczyć, że n>0 albo od 2
a nie zaznaczyli, czyli znalazłem jedno rozwiązanie

[silvaran]

jeszcze udało mi się ustalić, że od 3 do 7 nie pasują, ponieważ po napisaniu na kartce ( ) wszystkich np 7 i dopisaniu zazębiających się 6 zostaje wolnych miejsc 14 a potrzeba 15. a robiąc niezazebione, mamy 16 a potrzeba 15 (bo tyle jeszcze zostało klocków-cyfr do wpisania). z poprzednimi jest podobnie.
a dla 8 i 9 próbowałem i też nie pasuje. aż jestem ciekaw, czy jest taka liczba dla której to zachodzi.
najlepszym sposobem jest chyba powycinanie sobie takich pasków liczbami i przykładanie ich do siebie i sprawdzanie kiedy pasuje

[atimor]

Zauważmy, że każdy z wymienionych warunków możemy zapisać w następujący sposób:
"Aby każdymi dwoma klockami z (napisaną liczbą) \(\displaystyle{ k}\) było \(\displaystyle{ n-k+1}\) innych klocków...", gdzie \(\displaystyle{ n \ge k \ge 2}\) i oczywiście \(\displaystyle{ k \in N}\).

1' Teraz załóżmy, że istnieje takie ułożenie klocków, że ich "ciąg" rozpoczyna się i kończy klockiem z liczbą \(\displaystyle{ k}\), a w odstępie między każdymi dwoma znajduje się \(\displaystyle{ n-k+1}\) klocków. Takich odstępów jest \(\displaystyle{ k-1}\), zatem 'innych' klocków będzie \(\displaystyle{ (k-1)(n-k+1)}\). Zatem jeśli do ilości tych klocków dodamy ilość klocków z liczbą \(\displaystyle{ k}\), to otrzymamy liczbę wszystkich klocków, czyli:

\(\displaystyle{ k+(k-1)(n-k+1)= \frac{n(n+1)}{2}}\)

Przekształcamy zatem nasze równanie dalej i otrzymujemy kolejno:
\(\displaystyle{ k+kn-k^{2}+k-n+k-1= \frac{n(n+1)}{2}}\)
\(\displaystyle{ 2(-k^{2}+kn+3k-n-1)=n^{2}+n}\)
\(\displaystyle{ -2k^{2}+2kn+6k-2n-2=n^{2}+n}\)
\(\displaystyle{ -k^{2}+6k-(3n-2)=k^{2}-2kn+n^{2}}\)
\(\displaystyle{ -k^{2}+6k-(3n+2)=(k-n)^{2}}\)

Teraz zastanówmy się nad liczbą \(\displaystyle{ k}\). Z ostatniego równania wiemy, że liczby \(\displaystyle{ -k^{2}}\) oraz \(\displaystyle{ -(3n+2)}\) są ujemne, zaś liczba \(\displaystyle{ (k-n)^{2} \ge 0}\). Stąd mamy:

\(\displaystyle{ 6k \ge k^{2}+3n+2 \Leftrightarrow k(6-k) \ge 3n+2}\)

Ponieważ \(\displaystyle{ n,k \in N}\), więc lewa strona ostatniej nierówności jest dodatnia, czyli \(\displaystyle{ k<6}\). Zatem \(\displaystyle{ k}\) może przyjmować wartości 2,3,4 lub 5.

Rozwiążmy równanie \(\displaystyle{ -k^{2}+6k-(3n+2)=(k-n)^{2}}\) dla \(\displaystyle{ k=2}\):
\(\displaystyle{ -4+12-3n-2=(n-2)^2 \Leftrightarrow 6-3n=(n-2)^2 \Leftrightarrow n^{2}-n-2=0 \Leftrightarrow n=-1 \vee n=2}\) (-1 odrzucamy, gdyż n jest liczbą naturalną)
Czyli warunek "Między każdymi dwoma klockami z liczbą 2 (k) jest 1 inny klocek." jest spełniony dla \(\displaystyle{ n=2}\). Oczywiście jest to prawdziwe (jak już wcześniej dowodzono).

Teraz załóżmy, że \(\displaystyle{ k=3}\). Mamy więc:
\(\displaystyle{ -9+18-3n-2=(n-3)^{2} \Leftrightarrow n^{2}-3n+2=0 \Leftrightarrow n= \frac{3 \pm 1}{2} \Leftrightarrow n=2 \vee n=1}\). Otrzymujemy jednak sprzeczność, gdyż z założenia \(\displaystyle{ k \le n}\).

Dla \(\displaystyle{ k=4}\) mamy:
\(\displaystyle{ -16+24-3n-2=(n-4)^{2} \Leftrightarrow n^{2}-5n+10=0 \Leftrightarrow n \notin R}\) (delta jest ujemna). Podobnie w przypadku, gdy \(\displaystyle{ k=5}\).

Jeśli zatem nasz układ klocków wygląda tak, że na jego obu końcach są klocki z tymi samymi liczbami, to jedynym rozwiązaniem jest \(\displaystyle{ n=2}\), które spelnia tylko jeden (jedyny) warunek (ten ostatni)

---

2' Załóżmy teraz, że ilość klocków jest parzysta, tj. że 'ciąg' klocków rozpoczyna się klockiem z liczbą k, kończy zaś inną. Wtedy "odstępów" między klockami z liczbą k jest właśnie \(\displaystyle{ k}\) (rozumując analogicznie, jak w przypadku pierwszym). Czyli ilość 'innych' klocków i ilość klocków z \(\displaystyle{ k}\) dają razem ilość wszystkich klocków. Mamy:

\(\displaystyle{ k+(k)(n-k+1)= \frac{n(n+1)}{2} \Leftrightarrow k(n-k+2)= \frac{n(n+1)}{2}}\)

Po przekształceniach mamy:

\(\displaystyle{ -k^{2}+4k-n=(n-k)^{2}}\)

Rozumujemy tak samo, jak w przypadku pierwszym i dochodzimy do wniosku, że \(\displaystyle{ k<4}\). Zatem k może być równe 2 lub 3.

Dla \(\displaystyle{ k=2}\) równanie ma postać:
\(\displaystyle{ -4+8-n=(n-2)^{2} \Leftrightarrow n(n-3)=0 \Leftrightarrow n=0 \vee n=3}\). (wynik 0 odrzucamy z wiadomych przyczyn). Zatem (pozornie) mamy spełniony warunek dla k=2 i n=3.

Dla \(\displaystyle{ k=3}\) jest:
\(\displaystyle{ -9+12-n=(n-3)^{2} \Leftrightarrow n^{2}-5n+6=0 \Leftrightarrow n=2 \vee n=3}\). Pierwszy wynik przeczy założeniu, że \(\displaystyle{ k \le n}\). Zatem (pozornie) mamy spełniony warunek dla k=3 i n=3.

Udowodnimy jednak, że bezpośrednie sprawdzenie wyklucza n=3:
W poniższej linijce przedstawimy ciąg klocków dla n=3 (klocków będzie 6). Każda kropka oznacza jeden klocek, a liczba zamiast kropki bedzie oznaczała liczbę, znajdującą się na klocku:
\(\displaystyle{ ......}\)
Połowa liczb w tym 'ciągu' to trójki, a skoro mają być one z założenia odległe od siebie o 1 (między nimi ma być jeden klocek), to w takim razie ciąg klockow będzie miał postać:
\(\displaystyle{ 3.3.3.}\)
Ale zajmijmy się dwójkami. Z założenia są one odlegle od siebie o 2 klocki, więc do powyższego ciągu z trójkami trzeba 'wpleść' taki kawałek: \(\displaystyle{ 2..2}\). Jest to NIEMOŻLIWE (wynika to bezpośrednio z różnej parzystości liczb 2 i 3 oraz tego, że w ciągu mamy tylko 6 klocków.)

---

Zatem jedynym \(\displaystyle{ n}\), spełniającym wyjściowe założenia zadania jest \(\displaystyle{ n=2}\).

Rozwiązania można dowieść na inny, bardziej logiczny? sposób, właśnie metodą kropek i wstawiania w ciągi klocków mniejszych, wynikających z założeń (tak jak w przypadku dowodzenia, że n=3 nie spelnia obydwu warunków). Można opierać się na faktach, że dla n>3 wśród liczb naturalnych, mniejszych od n znajdzie się co najmniej para liczb względnie pierwszych, co utrudnia znalezienie odpowiedniego ciągu klocków lub skorzystać z właściwości liczb trójkątnych. Ja jednak nie będę tego rozwiązania wprowadzał, gdyż myślę, że i to jest dobre (i mam nadzieję, że jest dobre, bo inaczej zmarnowałem ponad pół godziny pisania ).

Mam nadzieję, że pomogłem w rozwiązaniu problemu.

[silvaran]

ale to jest chyba błędnie
nie możesz (znaczy możesz, ale to nie jest pełne założenie, brak jeszcze kolejnych) założyć sobie, że ciąg się zaczyna i kończy taką samą liczbą. w tym wypadku zawsze wyjdzie tylko 2. spróbuj sobie rozpisać swoim sposobem dla np 3:
\(\displaystyle{ 3\underline{ }3\underline{ }3}\) ciężko miedyz to wpisać dwie 2 z przerwami o 2, ale można zrobić tak:
\(\displaystyle{ 3\underline{ }323\underline{ }2}\) i jest po jednym odstępie między 3 i po dwa między 2. czyli razem między 3 są 2 odstępy a nie tak jak Ty pisałeś, że między k kolckami jest k przerw.

no i taki podstawowy błąd w rozumowaniu i według mnie straciłeś pół godziny, gdyż jest to źle
znaczy dla Twoich założeń, moze i rozwiązałeś dobrze, ale musisz jeszcze uwzględnić kolejne przypadki, tak jak ten mój drugi który napisałem

PS. cieszę się, że ktoś poza mna ruszył ten temat jeszcze ;P

[atimor]

ale to jest chyba błędnie
\(\displaystyle{ 3\underline{ }3\underline{ }3}\) ciężko miedyz to wpisać dwie 2 z przerwami o 2, ale można zrobić tak:
\(\displaystyle{ 3\underline{ }323\underline{ }2}\) i jest po jednym odstępie między 3 i po dwa między 2. czyli razem między 3 są 2 odstępy a nie tak jak Ty pisałeś, że między k kolckami jest k przerw.

Ale w tym, przedstawionym ciągu 3_323_2 mamy aż 7 cyfr, a przecież klocków jest 6...

[Sylwek]

Pierwszy przypadek jest OK. Drugi jest źle, a to był ten znacznie ważniejszy przypadek.

Załóżmy teraz, że ilość klocków jest parzysta, tj. że 'ciąg' klocków rozpoczyna się klockiem z liczbą k, kończy zaś inną.

Te warunki nie są równoważne - tzn. ominąłeś przypadek, gdy ilość klocków jest nieparzysta i ciąg rozpoczyna się klockiem z liczbą \(\displaystyle{ k}\), kończy zaś inną.

Wtedy "odstępów" między klockami z liczbą k jest właśnie k (rozumując analogicznie, jak w przypadku pierwszym).

Jak coś to odstępów jest \(\displaystyle{ k-1}\), gdyż te klocki nie są ustawione na okręgu, tylko jeden za drugim w prostej linii.

Czyli ilość 'innych' klocków i ilość klocków z k dają razem ilość wszystkich klocków.

Zatem: \(\displaystyle{ k+(k-1)(n+1-k) + z =\frac{n(n+1)}{2}}\), gdzie \(\displaystyle{ z}\) to ilość klocków znajdujących się "za" ostatnim klockiem z liczbą \(\displaystyle{ k}\).

[silvaran]

ale to jest chyba błędnie
\(\displaystyle{ 3\underline{ }3\underline{ }3}\) ciężko miedyz to wpisać dwie 2 z przerwami o 2, ale można zrobić tak:
\(\displaystyle{ 3\underline{ }323\underline{ }2}\) i jest po jednym odstępie między 3 i po dwa między 2. czyli razem między 3 są 2 odstępy a nie tak jak Ty pisałeś, że między k kolckami jest k przerw.

Ale w tym, przedstawionym ciągu 3_323_2 mamy aż 7 cyfr, a przecież klocków jest 6...

tak, dlatego kilka postów wyżej pisałem:

jeszcze udało mi się ustalić, że od 3 do 7 nie pasują, ponieważ po napisaniu na kartce ( ) wszystkich np 7 i dopisaniu zazębiających się 6 zostaje wolnych miejsc 14 a potrzeba 15. a robiąc niezazebione, mamy 16 a potrzeba 15 (bo tyle jeszcze zostało klocków-cyfr do wpisania). z poprzednimi jest podobnie.
a dla 8 i 9 próbowałem i też nie pasuje. aż jestem ciekaw, czy jest taka liczba dla której to zachodzi.
najlepszym sposobem jest chyba powycinanie sobie takich pasków liczbami i przykładanie ich do siebie i sprawdzanie kiedy pasuje