Kurczak Mały
Znajoma matematyczka stwierdziła, że zadanie w poprzednim wpisie było trywialne. Zależy dla kogo. Dla licealisty lubiącego matematykę, jak komentator Michał, zapewne tak. Znam jednak główkołamaczy, którzy długo kombinowali, jak to ugryźć.
Tworzenie wzoru na ciąg zaproponowałem przy okazji innego tematu (powrócę do niego w następnych wpisach), ponieważ przypadkiem trafiłem na podobne zadanie na forum matematyka.pl. Autor postu szukał wzoru na ciąg:
…, 91, 152, 238, 352, 503, 700, 958, 1296, 1744, 2351, 3194, 4416, …
Ściśle rzecz biorąc, jest to fragment ciągu, zaczynający się od piątego wyrazu (stąd wielokropek na początku).
W tym przypadku szukanie wzoru jest z pewnością nietrywialne. Właściwie zadanie jest nierozwiązywalne, jeśli nie wiemy, czego ciąg dotyczy albo jak powstał. Zresztą gdybyśmy nawet wiedzieli, mogłoby się okazać, że żadnego wzoru podać nie sposób. Na forum jest propozycja poradzenia sobie z problemem, ale związana z tzw. linearyzacją, czyli podany jest wzór przybliżony. Dokładny wzór można by wprawdzie wyprowadzić, zakładając, że jest on wielomianem, ale byłby to wielomian jedenastego stopnia i prawdziwy tylko dla podanych wyrazów (nie ma pewności, czy także dla czterech poprzednich i kolejnych), a jego wyprowadzenie wymagałoby rozwiązania układu 12 równań jedenastego stopnia z 12 niewiadomymi. To niezbyt zachęcające.
Korzystając z programu komputerowego spróbowałem utworzyć taki wielomianowy wzór dla sześciu początkowych wyrazów podanego fragmentu:
…, 91, 152, 238, 352, 503, 700, …
Oto on:
an = – 0,05n^5 + 2n^4 – 30,25n^3 + 232,5n^2 – 853,2n + 1232
Dla n od 5 do 10 wszystko pasuje, ale następne wyrazy, liczone według tego wzoru, będą już odbiegać od oryginalnych.
Pozostając przy ciągach, proponuję pogłowić się nad czymś prostszym:
Kilka chwil po wykluciu się Kurczak Mały pisnął – PI, a po sekundzie – PIIP, po następnej sekundzie – PIIPIPPI, po kolejnej – PIIPIPPIIPPIPIIP – i rozświergotał się na dobre: każde następne piśnięcie było, tak jak dotąd, dwa razy dłuższe od poprzedniego i zgodne ze „schematem”, wynikającym z czterech początkowych piśnięć (jaki to „schemat” – to także zagadka).
Jaka litera była 2011 w tym ciągu piśnięć, zaczynających się od PI – P czy I? Krótkie przedstawienie sposobu rozwiązania będzie mile widziane. Chodzi oczywiście o uniwersalny i w miarę prosty sposób, a więc inny, niż wypisanie odpowiedniej liczby piśnięć i policzenie.
Zagadnienie wiąże się z pewnym mało znanym ciągiem. Kto zna ten ciąg i jego własności, dla tego zadanie będzie zapewne trywialne; dla nieobeznanych – raczej przeciwnie.
Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.
Komentarze
2011 literą będzie P
Powtarza się ciąg złożony z 12 liter: PIIPIPPIIPPI. Litery I tworzą ciąg II,I,II,I,II,I,… i są oddzielone literami P o takim ciągu: P,P,PP,PP,P,P,PP,PP,…
2011:12=16 reszta 7. Siódmą literą w dwunastoliterowym ciągu jest P.
Następne, czyli piąte piśnięcie (piąty wyraz ciagu) wygląda tak:
PIIPIPPIIPPIPIIPIPPIPIIPPIIPIPPI
mp
PS I jeszcze szóste, a co tam…:
PIIPIPPIIPPIPIIPIPPIPIIPPIIPIPPIIPPIPIIPPIIPIPPIPIIPIPPIIPPIPIIP
(już niewiele piśnięć zostało do 2011 literki)
Bierzemy sobie jakąś liczbę i zapisujemy ją w układzie dwójkowym. Następnie sumujemy cyfry w tym zapisie. Jeśli wynik sumowania będzie liczbą parzystą, to otrzymamy ‚P’. Dla nieparzystego wyniku sumowania otrzymamy ‚I’.
Liczba 2011 w układzie dwójkowym to 11111011011. Suma cyfr daje 9, zatem otrzymamy ‚I’.
Przyznaję bez bicia, że nie znałem tego wcześniej. Zastanawia mnie tylko który ornitolog był w stanie usłyszeć to piskanie no powiedzmy po minucie.
Pozdrawiam,
Jazz
🙂 mała wskazówką może być rozwikłanie znaczenia owych ‚P’ i ‚I’ 😉
P to positive
I to Inverse
😉
jakby nie było bardzo mądry ten kurczaczek, że ledwo od wyklucia bawi się w ten sposób? hmmm 2011 to jakby 2048 – 37
czyzby juz ktoś podał rozwiązanie?
P.S. aha, chyba trzeba zanegować 37 znak z powodu nieparzystej potegi dwójki dla 2048 🙂
Przy drugim, czwartym, szóstym, ósmym piśnięciu litery jednakowo odległe od początku i końca są jednakowe.
Przy pierwszym, trzecim, piątym, siódmym, dziewiątym, jedenastym litery jednakowo odległe od początku i końca są różne.
2011 literę mamy przy jedenastym piśnięciu. Będzie 2048 liter. 2011 litera to 38 od końca. Od początku trzydziesta ósma to I, więc od końca będzie P
To jest dobry trop, jeśli chodzi o zasadę tworzenia ciągu. Po zastosowaniu tego sposobu do wyrazu zawierającego 2011 literę w ciągu – a nie w wyrazie złożonym z 2048 liter – odpowiedź będzie oczywiście poprawna. Jednak sposób sprowadza się – niestety – do odliczania.
mp
Małe uściślenie, a właściwie zwrócenie uwagi na pewien szczegół, który – jak wynika z nadsyłanych rozwiązań – umyka Państwa uwadze:
chodzi o 2011 literę w CIĄGU PIŚNIĘĆ, a nie o 2011 w piśnięciu złożonym z 2048 liter.
mp
P.S. Hmm, po uwolnieniu odpowiedzi zastanowilem sie chwilke dluzej i wyszlo mi, że bedzie to znak przeciwny do 38 znaku (licząc od początku) 🙂 co prawda 2048-2011=37, ale to da na różnicę a nie 2011-ty znak licząc od 2048 🙂
Ciągu nie znałem wcześniej, ale widać, że rozwija sie on jakby sam z siebie od poczatkowej wartości PI
dla P wstawia, jak napisalem wczesniej ‚pozytyw’ czyli PI bez zmian, natomiast I wstawia ‚inwersje’ czyli IP, dlatego PI generuje (P)PI (I)IP=PIIP
a dalej (P)PI(I)IP(I)IP(P)PI = PIIPIPPI
Łatwo zauważyc, że dla długości ciągu równego nieparzystej potędze dwójki, jest on antysymetryczny (czyli P=>I oraz I=>P, nie wiem czy to dobre słowo, ale mi pasuje i chyba oddaje to o co mi chodzi) względem środka, natomiast dla parzytej potęgi dwójki wyrazy ciągu sa całkowicie symetryczne względem środka.
Nie zastanawiałem się na pomysłem Jazza, ale na intuicje może być to bardzo ciekawe i poprawne patrząc jak rozwija sie ten ciąg w potęgach dwójki.
Po przeczytanie Pana uwagi:
2011-2-4-8-16-32-64-128-256-512=989
czyli 989 znak z ciągu 1024
a więc 1024-989=35
to oznacza 36 znak ciągu 1024 lub 256 lub 64
lub też 4-ty zanegowany znak ciagu 4
a co dalej idzie , jesli dobrze wnioskuję na bieżąco: znak numer 1 czyli P.
Moge sie mylić, bo z braku czasu dowód prowadzilem piszac ta odpowiedz.
Ale mysle, ze idea jest poprawna.
Tak, idea jest z grubsza OK, ale z literką się Pan kropnął.
mp
Znam ten ciag, wiec tylko wyliczylem, ze trzeba ustalic, jaka jest 989 litera w 10 pisnieciu, bo to będzie wlasnie szukana 2011 litera. Aby to zrobic trzeba zapisac 988 w systemie binarnym i policzyc jedynki w tym zapisie. Jest ich 7, czyli liczba nieparzysta, wiec szukana litera to „I”. Gdyby była parzysta, to by było P.
a
Jak zwykle coś pokręciłem.
Prawidłowo powinno być tak:
Bierzemy sobie jakąś liczbę, dodajemy do niej 1 i wynik zapisujemy w układzie dwójkowym. Następnie sumujemy cyfry w tym zapisie. Jeśli wynik sumowania będzie liczbą parzystą, to otrzymamy „I”. Dla nieparzystego wyniku sumowania otrzymamy „P”.
Liczba 2011+1 w układzie dwójkowym to 11111011100. Suma cyfr daje 8, zatem otrzymamy „I”.
Och, rzeczywiście, miało być liczone od pierwszego piśnięcia.
2+4+8+16+32+64+128+256+512+1024=2046
Czyli w piśnięciu złożonym z 1024 liter będzie 2011.
2046-2011=35, więc więc zostaje 36. litera od końca w tym piśnięciu. jest ona równa 36. literze od początku, czyli jednak I
kazde kolejne (n-te) pisniecie jest dlugosci 2^n – w zwiazku z tym ciag n pisniec ma dlugosc 2^(n+1)-2
2, 6, 14, …, 254, 519, 1022, 2046 – te liczby za chwile sie przydadza
jesli chcemy ustalic jaka litera jest kolejny znak (2011) musimy najpierw ustalic ktorym jest znakiem w kolejnym pisnieciu, czyli odejmujemy najwieksza wartosc 2^(n+1)-2 jaka jest mniejsza od numeru znaku – w naszym przypadku
2011 – 1022 = 989
od tak otrzymanej pozycji bedziemy odejmowac kolejne potegi 2, ktore sa mniejsze od otrzymywanych roznic, czyli:
989 – 512 = 477
477 – 256 = 221
221 – 128 = 93
93 – 64 = 29
29 – 16 = 13
13 – 8 = 5
5 – 4 = 1
odejmowanie konczymy gdy uzyskujemy wartosc 1 (ktorej odpowiada P) lub 2 (to jest I) – kazde wykonane odejmowanie powodowalo zmiane litery (bo oznaczalo, ze w danym ciagu liter przy kolejnym pisnieciu litera znajdowala sie w drugiej polowce) – czyli parzysta ilosc oznacza ze to ta sama litera, nieparzysta – ze „przeciwna”.
W naszym wypadku mamy 7 roznic, ostateczny wynik P – czyli 2011 litera jest I.
I (jesli nic nie pomylilem we wzorze ponizej i w liczeniu 😉
Wzor ogolny dla N: jesli liczba jedynek w rozwinieciu binarnym liczby N – 2^[lg(N+1)] + 1 jest parzysta to P, w przeciwnym wypadku I. lg to logarytm przy podstawie 2, a [x] najwieksza liczba calkowita nie wieksza od x.
Wynika to z budowania kolejnego pisniecia o dlugosci 2^k, do polowy (do 2^(k-1) sa liczby o jakiejs parzystosci jedynek, a po polowie o odwrotnej parzystosci – zmienia sie najbardziej znaczacy bit. Czyli zeby policzyc litere w ciagu trzeba odpowiednio odjac sume dlugosci wszystkich poprzednich pisniec.
Ciagi znam, ale nie byly tu specjalnie potrzebne 🙂
A P i I to bardziej mi pasuje do francuskich okreslen na parzystosc 😉
PS. Do znalezienia wielomianu w tresci wpisu trzeba faktycznie rozwiazac uklad 12 rownan z 12 niewiadomymi, ale sa to chyba rownania liniowe, a nie 11 stopnia 🙂
ad PS: racja, zagalopowałem się z 11 stopniem.
mp
‚Studiując’ pewne sekwencje zainspirowany małym kurczaczkiem, skonstruowałem pytanie:
Mamy sekwencje:
0, 10, 1110, 3110, 132110, 1113122110… itd
proszę odkryć zasadę rządzącą kolejnymi wyrazami ciągu
i podać następny wyraz ciągu, który pojawiłby sie po takim oto wyrazie:
‚2220’… start!
Każde kolejne piśnięcie powstaje przez skopiowanie poprzedniego piśnięcia, poddanie tej kopii inwersji (zamiana litery P na I, i odwrotnie) i doklejenie tej zmienionej kopii z prawej strony oryginału. Można, więc przyjąć, że litera znajdująca się w piśnięciu na pozycji n, jest kopią pierwszej litery poddaną inwersji k razy. Jeśli znajdziemy tę liczbę k, to wystarczy sprawdzić jej parzystość.
Zauważmy też, że każde kolejne piśnięcie jest dłuższe od poprzedniego o kolejną potęgę liczby dwa. Nasza szukana litera znajduje się więc na swojej pozycji dlatego, że k razy „wepchnęliśmy” przed nią fragment o długości równej jakiejś potędze dwójki. Wystarczy więc litery poprzedzające tę szukaną podzielić na fragmenty o długościach równych różnym potęgom dwójki.
Inaczej:
Jeśli interesuje nas litera na pozycji n, to należy liczbę n-1 zamienić na postać dwójkową i policzyć ile jedynek występuje w tym binarnym zapisie. To jest szukana liczba inwersji k.
2011 = 2+4+8+16+32+64+128+256+512+989
Szukana litera jest więc 989. w 10. piśnięciu, które liczy 1024 litery.
Zamieniamy więc liczbę o jeden mniejszą na postać binarną.
988=512+256+128+64+16+8+4 = 1111011100(2)
Zapis zawiera 7, czyli nieparzystą liczbę jedynek.
2011 literą w ciągu piśnięć kurczaka jest więc „I”.
Oops! Trochę mi nie wyszło formatowanie (:. Jeszcze raz.
Każde kolejne piśnięcie powstaje przez skopiowanie poprzedniego piśnięcia, poddanie tej kopii inwersji (zamiana litery P na I, i odwrotnie) i doklejenie tej zmienionej kopii z prawej strony oryginału. Można, więc przyjąć, że litera znajdująca się w piśnięciu na pozycji n, jest kopią pierwszej litery poddaną inwersji k razy. Jeśli znajdziemy tę liczbę k, to wystarczy sprawdzić jej parzystość.
Zauważmy też, że każde kolejne piśnięcie jest dłuższe od poprzedniego o kolejną potęgę liczby dwa. Nasza szukana litera znajduje się więc na swojej pozycji dlatego, że k razy „wepchnęliśmy” przed nią fragment o długości równej jakiejś potędze dwójki. Wystarczy więc litery poprzedzające tę szukaną podzielić na fragmenty o długościach równych różnym potęgom dwójki.
Inaczej:
Jeśli interesuje nas litera na pozycji n, to należy liczbę n-1 zamienić na postać dwójkową i policzyć ile jedynek występuje w tym binarnym zapisie. To jest szukana liczba inwersji k.
2011 = 2+4+8+16+32+64+128+256+512+989
Szukana litera jest więc 989. w 10. piśnięciu, które liczy 1024 litery.
Zamieniamy więc liczbę o jeden mniejszą na postać binarną.
988=512+256+128+64+16+8+4 = 1111011100(2)
Zapis zawiera 7, czyli nieparzystą liczbę jedynek.
2011 literą w ciągu piśnięć kurczaka jest więc „I”.
Zadanie trywialne nie było, ale jako informatykowi, było mi chyba łatwiej je rozwiązać (zakładając, że mi się to udało 🙂 )
Ponieważ wycofano aprobatę zastosowanej przeze mnie metody, dlatego czuję się w obowiązku uzasadnienie tej metody.
Wypiszmy kolejno piśnięcia Kurczaka:
PI,PIIP,PIIPIPPI, PIIPIPPIIPPIPIIP,…
Przez dopisanie na początku dodatkowego IP otrzymamy ciąg:
IP,PI,PIIP,PIIPIPPI, PIIPIPPIIPPIPIIP,…
który ma tę własność, że każde nowe piśnięcie jest negatywem wszystkich wcześniejszych piśnięć, łącznie z dodanym na początku IP.
Ponumerujmy teraz litery tego ciągu kolejnymi binarnymi liczbami, poczynając od 0. Po takim ponumerowaniu możemy zauważyć, że litery każdego nowego piśnięcia mają przypisane liczby z przedziału [2^n ; 2^(n+1)-1], gdzie n oznacza n-te piśnięcie. Liczby zapisane dwójkowo z tego przedziału różnią się od liczb z przedziału [0 ; 2^n-1] dodatkową jedynką na najstarszej pozycji. Dzięki temu możemy z binarnego zapisu przypisanego dowolnej literze określić, jaka to litera. Jeśli suma cyfr dwójkowej liczby przypisanej danej literze jest parzysta, to mamy „I”, jeśli nieparzysta, to „P”. Ponieważ do ciągu piśnięć dodaliśmy dwie litery IP a liczenie rozpoczynamy od 0, dlatego do odgadnięcia n-tej litery musimy użyć dwójkowego zapisu liczby n+1.