szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 26 paź 2016, o 20:23 
Użytkownik
Avatar użytkownika

Posty: 572
Lokalizacja: Kraków
Nie wiem czy to dobry dział, ale chyba kombinatoryka pasuje.

Niech A będzie takim zbiorem, że a _{i}\in A. Niech teraz ciąg (a_{1},a_{2},a_{3},\ldots ,a_{n}) będzie nazywany słowem i oznaczany jako
a_{1}a_{2}a_{3} \cdot \ldots \cdot a_{n}.
Dwa słowa
a=a_{1}a_{2}a_{3} \cdot \ldots \cdot a_{n} oraz b=b_{1}b_{2}b_{3} \cdot \ldots \cdot b_{m} możemy "mnożyć" w ten sposób, że
a \cdot b = a_{1}a_{2}a_{3} \cdot \ldots \cdot a_{n}b_{1}b_{2}b_{3} \cdot \ldots \cdot b_{m}. Muszę scharakteryzować takie pary ciągów (a,b), że ab=ba.

Jeżeli m=n, to widać, że aby słowa (ciągi) były równe, musi zachodzić a_{i}=b_{i} dla każdego i\in I.

Załóżmy jednak że n>m. Trochę się tu gubię w mnogości przypadków:

dla n=5 i m=3 łatwo zauważyć, że wszystkie elementy muszą być sobie równe (to znaczy dla każdego i,j a_{i}=b_{j}.
ale już dla n=10 i m=2 to nie zachodzi. z kolei dla k+m nieparzystego wydaje mi się, że znów wszystko będzie się sobie równało.

Pomoże ktoś to ogarnąć? :wink:
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 26 paź 2016, o 20:47 
Użytkownik

Posty: 227
Lokalizacja: Warszawa
Ja bym zaryzykował, że obydwa ciągi muszą być cykliczne z cyklem o długości k i te cykle muszą mieć takie same. A k jest dowolnym wspólnym dzielnikiem długości tych ciągów.

Czyli:

k|n \wedge k|m

dla i=1,2,...,k:
a_{i}=a_{i+jk}, i+jk \le n
b_{i}=b_{i+lk}, i+lk \le m
a_i=b_i

\\j,l \in \mathbb{N}
Góra
Mężczyzna Offline
PostNapisane: 27 paź 2016, o 19:17 
Użytkownik
Avatar użytkownika

Posty: 572
Lokalizacja: Kraków
Zrobiłem to na piechote i oto moje rezultaty:

Jeżeli oba słowa są tej samej długości to u_{i}=v_{i}, dla każdego i.

Niech u=u_{1},\ldots ,u_{k} będzie dłuższym słowem, a v=v_{1},\ldots ,v_{m} krótszym. Czyli zakładamy bez straty ogólności, że k>m.

Jeżeli k jest wielokrotnością m, to wtedy mamy m różnych liter, które tworzą te oba wyrazy.

Jeżeli k nie jest wielokrotnością m, ale obie są parzyste, to są dwie różne litery tworzące oba wyrazy.

Jeżeli jedna z liter m i k jest nieparzysta, druga parzysta, wtedy wszystkie litery są sobie równe, czyli jest jedna litera, która buduje oba słowa.

Jeżeli obie są nieparzyste, to wydaje mi się, że zachodzi to, co przy obu parzystych.

Może to ktoś zweryfikować? :wink:
Góra
Mężczyzna Offline
PostNapisane: 28 paź 2016, o 14:12 
Użytkownik

Posty: 227
Lokalizacja: Warszawa
Jeszcze zabrakło kilku przypadków.

Jeżeli k nie jest wielokrotnością m, ale obie są podzielne przez 3... przez 5...przez 7... itd.

Co wtedy?
Góra
Mężczyzna Offline
PostNapisane: 29 paź 2016, o 11:31 
Użytkownik
Avatar użytkownika

Posty: 3272
Lokalizacja: blisko
Cytuj:
Ja bym zaryzykował, że obydwa ciągi muszą być cykliczne z cyklem o długości k


Jak rozumiesz tę tezę bo ja ni hu hu.

Całe to zadanie przypomina mi generowanie grupy wolnej za pomocą jakiegoś tam alfabetu.
Ale w tym przypadku i tak nie jest to działanie grupowe.

Poza tym cały czas trwa tu dyskusja typu kiedy dwa ciągi są równe.
Dla mnie są równe wtedy gdy są równe i nie szukam jakiś innych rzeczy, które tworzą mocno naciąganą teorię do zdefiniowania kiedy dwa ciągi o różnych długościach są równe, może nie jestem aż na takim poziomie abstrakcji żeby sobie dopasowywać teorię do dziwnych sytuacji.
Ale jestem człowiekiem prostym, bardzo prosto myślącym wręcz ocieram się o prymitywizm.
I dlatego w moim ograniczonym umyśle te dywagacje są albo za mądre albo naciągane do granic możliwości.
Góra
Mężczyzna Offline
PostNapisane: 2 lis 2016, o 14:52 
Użytkownik
Avatar użytkownika

Posty: 572
Lokalizacja: Kraków
karakuku napisał(a):
Jeszcze zabrakło kilku przypadków.

Jeżeli k nie jest wielokrotnością m, ale obie są podzielne przez 3... przez 5...przez 7... itd.

Co wtedy?


Faktycznie, czyli to co napisałem działa tylko dla liczb względnie pierwszych. W przypadku o którym wpomniałeś, szukaną liczbą różnych liter jest chyba NWD obu długości.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 tworzenie słów w danym alfabecie  maciekstodulski  1
 Ile jest ciągów długości 2n...  pavel3643  4
 Ilość różnych kombinacji k jednakowych ciągów?  TomASS  7
 ile słów można utworzyć...  Mehow90  6
 ilość możliwych ciągów z danego zbioru  davidd  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl