ile różnych napisów można otrzymać

[karolina182]

Ile różnych napisów czteroliterowych z różnych liter można otrzymać z 24 liter alabetu,zakładając,że litery występujące w każdym napisie należą do grupy składającej się z siedmiu stojących obok siebie w alfabecie liter?Wykonaj odpowiednie obliczenia.W odp.powinno wyjść 9000.

[Wilkołak]

Nie wystarczy podzielić alfabet na 7-literowe bloki i badać ile z nich możemy stworzyć wyrazów bo ten sam wyraz może powtarzać się w sąsiadujących "blokach". Dlatego zbadamy ile możemy stworzyć wyrazów z bloków 7,6,5 i 4 literowych. Ale dodatkowo zakładamy że z każdego takiego bloku bierzemy dwa skrajne elementy i dwa dowolne pomiędzy nimi. Dodatkowo w tych wyrazach mogą one stać w różnej kolejności, to też trzeba brać pod uwagę.

Takich spójnych bloków 7-elementowych w 24-literówym alfabecie mamy 24-7+1=18.

X _ _ _ _ _ X
Nasz blok wygląda jak powyżej. Bierzemy dwa skrajne elementy, do tego dwa różne elementy pomiędzy nimi i "mieszamy" je, czyli:
\(\displaystyle{ 18 \cdot 1 \cdot 1 \cdot {5 \choose 2} \cdot 4!}\)
Podobnie postępujemy dla 6,5 i 4.
Mamy 19 6-elementowych bloków.
X _ _ _ _ X
\(\displaystyle{ 19 \cdot 1 \cdot 1 \cdot {4 \choose 2} \cdot 4!}\)

X _ _ _ X
\(\displaystyle{ 20 \cdot 1 \cdot 1 \cdot {3 \choose 2} \cdot 4!}\)

X _ _ X
\(\displaystyle{ 21 \cdot 1 \cdot 1 \cdot {2 \choose 2} \cdot 4!}\)

Po zsumowaniu powinno dać 9000

[karolina182]

Dziekuje za pomoc!

[thunderja]

czy można prosić o bardziej szczegółowe (zrozumiałe) wytłumaczenie?

[Wilkołak]

Wyrazy czteroliterowe mają składać się z liter, których różnica między pozycjami w alfabecie jest nie większa niż 7. Czyli wyraz abch jest nieprawidłowy, bo a ma numer 1 a h ma numer 8.

Gdybyśmy rozpatrywali 7-elementowe "bloki" alfabetu, np. abcdefg albo cdefghi i liczyli ile z tych liter można stworzyć czteroliterowych wyrazów to byśmy niektóre wyrazy liczyli więcej niż jeden raz (np. słowo defg można stworzyć z liter z obu bloków). Dlatego trzeba liczyć sprytniej.

Odległość między najbardziej odległymi literami w wyrazie może wynosić 7, 6, 5 lub 4. Dlatego rozpatrujemy oddzielnie bloki 7,6,5 i 4 elementowe. Ile jest bloków konkretnej długości napisałem w poprzednim poście. Teraz, żeby mieć pewność, że wyraz nie powtórzy się w żadnym z dwóch bloków, bierzemy dwie skrajne litery z bloku, i dwie dowolne pomiędzy nimi, np. skupmy się na blokach 6 literowych.

Weźmy blok abcdef i bcdefg. Wyrazy z pierwszego bloku mają postać a _ _ f (pomijając permutacje liter w wyrazie), a z drugiego b_ _ g. Tam gdzie kreseczki wstawiamy dowolne ale rożne litery z danego bloku. Teraz nie ma możliwości, żeby jakieś słowo było w pierwszym i w drugim bloku naraz. Żeby było w ogóle w dwóch dowolnych blokach jednocześnie.

Do tego trzeba jeszcze przemieszać litery. z liter adef możemy zrobić 4! wyrazów. Litery mogą stać przecież w różnej kolejności, a będą to przecież niepowtarzające się słowa.

Mam nadzieję, że już nieco jaśniej.

[jimarcin]

edit; ok, jeszcze pare razy przeczytam i zlapie bo coraz jasniej wyglada to rozwiazanie; )

ponizej tlumaczenie niektorych spraw, ktore sa niezbedne (przynajmniej byly dla mnie) dla zrozumienia ; )
1. Dlaczego bierzemy dwa skrajne elementy? gwarantuje nam to unikatowość każdego zbioru z ktorego tworzymy wyrazy. W takim razie dlaczego nie możemy brać tylko jednego elementu? np pierwszego lub ostatniego? z prostej przyczyny; po "dojechaniu" blokiem do konca alfabetu nie skorzystalibysmy z wszystkich liter (gwarantuje nam to wybor skrajnych liter) ; )
2. jakim prawem bierzemy pod uwage bloki 4,5,6-elementowe? przeciez w zadaniu sa 7-mio elementowe..
ano dlatego, ze nasz w/w sposob nie bierze pod uwage sytuacji kiedy wyraz beda tworzyc np. cztery pierwsze litery lub druga, trzecia i piąta : )
i wlasnie dlatego musimy pojsc za ciosem i rozwazac przypadki mniejszych bloczków..

ps. na jakims innym forum pojawilo sie pytanie dlaczego mnozymy razy 4!. robimy tak dlatego, ze wybrane dowolnie 4 elementy mozemy jeszcze rozmiescic w roznym polozeniu wzgledem siebie (abcd, abdc,adbc itd) i jest ich 4! mozliwosci x )

mam nadzieje ze pomoglem : )

ps2; robilem to zadanie innym sposobem i wyszedl inny wynik. Czy moglby ktos powierdziec dlaczego jest on zly/przeocza jakies mozliwosci?
zakładał on podobnie jak wyzej, ze mamy 18 bloków z 7literami i tak; w pierwszym 7x6x5x4 mozliwosci, w drugim 7x6x5x1 ponieważ mamy do wyboru jedna litere ktora zagwarantuje nam ze wyrazy beda inne od tych z poprzedniej grupy. nastepny blok to znow 7x6x5x1 i tak aż do końca..

[losie0]

Przyłączam się do pytania kolegi wyżej , również robiłem tym 2 sposobem i nie wychodzi tak samo
Pozdrawiam

[borekd]

W pierwszym mamy owszem 7*6*5*4 możliwości. W każdym nastęnym mamy:
4 (litera którą wybieramy musowo, może znaleźć się na 4 miejscach)*6(skoro jedna wybrana przymusowo, to zostaje tylko 6itd..)*5*4*17 (mamy 17 takich segmentów )

czyli: \(\displaystyle{ 7*6*5*4 + 4*6*5*4*17=9000}\)

[DominekGo]

Dlaczego nie można "budować" napisów czteroliterowych tym sposobem:
Najpierw wybieramy jedną z \(\displaystyle{ 24}\) liter alfabetu, następną literę wybieramy już spośród grupy siedmiu liter stojących obok siebie, w której zawiera się nasza litera, którą wybraliśmy jako pierwszą. Jest takich liter \(\displaystyle{ 6}\). Następną możemy wybrać na \(\displaystyle{ 5}\) sposobów, ponieważ już dwie zużyliśmy itd. Idąc tym tokiem rozumowania, możliwych napisów jest łącznie \(\displaystyle{ 24\cdot 6\cdot 5\cdot 4}\) czyli \(\displaystyle{ 2880}\). Ktoś powie dlaczego takie myślenie jest błędne?

[Jan Kraszewski]

Najpierw wybieramy jedną z \(\displaystyle{ 24}\) liter alfabetu, następną literę wybieramy już spośród grupy siedmiu liter stojących obok siebie, w której zawiera się nasza litera, którą wybraliśmy jako pierwszą. Jest takich liter \(\displaystyle{ 6}\).

No nie. Jeżeli jako pierwszą wybierzesz np. literę h, to w grę wchodzi wiele różnych siódemek liter: bcdefgh, cdefghi, defghij, efghijk, fghijkl, ghijklm, hijklmn.

JK

[DominekGo]

Dziękuję za pomoc! Teraz rozumiem