Matematická sekce
Miroslav Olšák | org | 12. 12. 2011 23:02:33
Uz mi to beha rychleji, otestovano do p=200000033. Ta uloha nejak vzdoruje hrube sile :(
Miroslav Olšák | org | 12. 12. 2011 19:16:57
taky jsem trochu zkousel, a mam podobnou spatnou zpravu:
pokud prvocislo deli
i 
, tak je vetsi nez 14200001. Tim toto testovani koncim, nicmene kdyby nekdo umel rychle (rychleji nez linearne) najit rad dvojky modulo p, dalo by se dostat do vyssich cisel.
pokud prvocislo deli
Olin | org | 12. 12. 2011 18:30:30
Trochu jsem to zkoušel, bohužel mám jen špatnou zprávu:
pro 
.
Mark Daniel | 11. 12. 2011 22:36:05
BakyX: Takže sa nevynašiel. Asi neuspel s touto myšlienkou.
Keď hovoríš, že to ľahko overíš pomocou Euklidovho algoritmu, myslíš tým iba prípad, keď jedna zo zátvoriek je deliteľná číslom 25?
Keď hovoríš, že to ľahko overíš pomocou Euklidovho algoritmu, myslíš tým iba prípad, keď jedna zo zátvoriek je deliteľná číslom 25?
BakyX | 11. 12. 2011 21:52:26
Je to asi nový Fermat.
BakyX | 11. 12. 2011 21:50:58
Kamarát riešil školské kolo a nestíhal, tak k 3. úlohe napísal, že tieto čísla sú nesúdeliteľné, čo ľahko overím pomocou Euklidovho algoritmu. Samozrejme to overiť nevedel a nemal časť zisťovať, či sa to dá...
Mark Daniel | 11. 12. 2011 20:59:12
BakyX: A to zadanie si si vymyslel sám alebo si ho niekde videl?
BakyX | 11. 12. 2011 17:25:05
Zmierme sa s tým, že to pre nejaké horibilne vysoké 
možno neplatí, alebo je to nová "Veľká Fermatová veta" :D
Mark Daniel | 11. 12. 2011 12:09:52
Ano, je fakt blábol. Minimálne ten druhý príspevok. To je ozaj báchorka.
Miroslav Olšák | org | 11. 12. 2011 10:47:21
Aha! Skolni kolo. To mnohe vysvetluje, konkretne 1) kde se ta Bakyxova uloha vzala, 2) proc se snazis ji resit pres posledni cifru.
Ta uloha ze skolskeho kola se resi takto, ze?
+ skrytý text
Jenze, co nam z toho plyne pro Bakyxovu ulohu?
+ skrytý text
Ta uloha ze skolskeho kola se resi takto, ze?
+ skrytý text
Pro dost velka 
uz bude 
prilis velke, aby to mohlo delit samotne 
nebo 
. Proto uz by musely byt delitelne peti obe tyto zavorky. Staci se ovsem podivat na zbytky mocnin dvojky a trojky modulo peti (resp. posledni cifry):
: 1 2 4 3 1
: 1 3 4 2 1
Vidime, ze proti sobe nelicuji spravne zbytky, tedy nemohou byt delitelne peti obe zavorky.
Vidime, ze proti sobe nelicuji spravne zbytky, tedy nemohou byt delitelne peti obe zavorky.
Jenze, co nam z toho plyne pro Bakyxovu ulohu?
+ skrytý text
Ukazali jsme pouze, ze obe zavorky nejsou soucasne delitelne peti (delitelnost dvemi a peti se pres posledni cifru da). Nicmene co ostatni cisla? Napriklad nasobky 13, 17, 521, 769 mohou koncit na uplne jakoukoli cifru.
Anonym | 11. 12. 2011 00:06:32
Nechci přímo psát, že je to blábol, ale tudy cesta nevede.
Mark Daniel | 10. 12. 2011 23:45:18
Mirek: Teraz rozhodne neobhajujem moje riešenie, možno je to celé blbosť.
Iba k tej poznámke, čo sa dá usudzovať z poslednej cifry. Napríklad 3. úloha školského kola MO A sa dala v podstate celá vyriešiť cez to, aká cifra je na konci.
Iba k tej poznámke, čo sa dá usudzovať z poslednej cifry. Napríklad 3. úloha školského kola MO A sa dala v podstate celá vyriešiť cez to, aká cifra je na konci.
Mark Daniel | 10. 12. 2011 23:22:07
Ospravedlňujem sa po druhé, na konci som naozaj niečo prehliadol. Posledný odstavec je celý zlý, takže ešte raz:
Keď sa obe zátvorky končia číslicou 9:
+ skrytý text
Keď sa obe zátvorky končia číslicou 9:
+ skrytý text
Tak potom 2 na n-tú sa končí číslicou 8 a 3 na n-tú sa končí číslicou 7. Vieme, že (2 na n-tú)*(1,5 na n-tú)=(3 na n-tú). A vieme, že ak máme číslo, na ktorého konci je číslica 8 a chceme ho vynásobiť istým číslom A tak, aby výsledný súčin mal konci číslicu 7, tak potom A musí mať za desatinnou čiarkou číslo:......,1/(8/7). Pritom 1//(8/7) je číslo 0,875. A 1,5 na n-tú nikdy nie je číslo, ktoré sa takto končí. Aspoň si to myslím. Možno sa mýlim.
A ak sa prvá zátvorka končí číslicou 5 a druhá číslicou 1, tak 2 na n-tú sa končí číslicou 4 a 3 na n-tú číslicou 9. Teraz teda budeme násobiť číslo 2 na n-tú číslom takým číslom B, aby mal výsledný súčin na konci číslicu 9. To znamená, že číslo A má na konci hodnotu: 1/(4/9), čo je 2,25. Ale môže sa 1,5 na n-tú končiť hodnotou 2,25?
A ak sa prvá zátvorka končí číslicou 7 a druhá číslicou 3, tak 2 na n-tú sa končí číslicou 6 a 3 na n-tú číslicou 1. A opäť, ak chceme vynásobiť 2 na n-tú, tak aby vzniklo 3 na n-tú, musíme 2 na n-tú násobiť takým číslom C, aby C malo za desatinnou čiarkou hodnotu ...,1/(1/6). To znamená, že sa bude končiť takto: ....6,0. Ale 1,5 na n-tú sa nikdy takto nekončí.
A ak sa prvá zátvorka končí číslicou 5 a druhá číslicou 1, tak 2 na n-tú sa končí číslicou 4 a 3 na n-tú číslicou 9. Teraz teda budeme násobiť číslo 2 na n-tú číslom takým číslom B, aby mal výsledný súčin na konci číslicu 9. To znamená, že číslo A má na konci hodnotu: 1/(4/9), čo je 2,25. Ale môže sa 1,5 na n-tú končiť hodnotou 2,25?
A ak sa prvá zátvorka končí číslicou 7 a druhá číslicou 3, tak 2 na n-tú sa končí číslicou 6 a 3 na n-tú číslicou 1. A opäť, ak chceme vynásobiť 2 na n-tú, tak aby vzniklo 3 na n-tú, musíme 2 na n-tú násobiť takým číslom C, aby C malo za desatinnou čiarkou hodnotu ...,1/(1/6). To znamená, že sa bude končiť takto: ....6,0. Ale 1,5 na n-tú sa nikdy takto nekončí.
Miroslav Olšák | org | 10. 12. 2011 23:10:40
Cele jsem to necetl, (protoze to je desne dlouhe), ale obavam se, ze to nefunguje. Z posledni cifry se prece neda nic usuzovat (maximalne tak sudost a delitelnost peti). Ovsem uz vubec, jestli je cislo prvocislem nebo jestli jsou dve cisla nesoudelna. Taky z toho textu mam trochu pocit, ze aby cislo koncilo na jednicku, musi byt mocninou jedenactky.
Nebo jsem prehledl nejakou nosnou myslenku? Jak to vidi ostatni?
Nebo jsem prehledl nejakou nosnou myslenku? Jak to vidi ostatni?
Mark Daniel | 10. 12. 2011 22:22:17
Ospravedlňujem sa Vám, ak som to mal dať do skrytého textu.
Mark Daniel | 10. 12. 2011 22:21:21
Pavel, Mirek: Ďakujem za odpoveď.
BakyX, spoločný násobok: Celkom by ma zaujímalo, kde si našiel tento príklad.
Vychádzam z toho, že 3 na n-tú je presne 1,5 na n-tú viac ako 2 na n-tú:
Vieme, že násobky 1,2,3,4,6,8 určite nebudú spoločným násobkom, lebo toto všetko sú násobky alebo 2, alebo 3 a tým minimálne jedna zo zátvoriek nie je. To znamená, že nejaká zo zátvoriek je násobok 5,7 a ďalších prvočísiel. Z toho vyplýva, že jedna zo zátvoriek sa nepochybne končí číslicami 1,3,5,7 alebo 9 ako aj druhá. A spoločný násobok bude nejaké prvočíslo.
Pre prvú zátvorku:
Ak sa končí číslicou 1: tak potom samotná mocnina 2 sa končí číslicou 0. Ale taká neexistuje.
Ak sa končí číslicou 3: Tak potom samotná mocnina čísla 2 sa končí číslicou 1. Taká neexistuje.
Ak sa končí číslicou 5: Tak potom samotná mocnina 2 sa končí číslicou 4. To je možné. Toto si zatiaľ odložme do šuflíka.
Ak sa končí číslicou 7: Tak potom samotná mocnina 2 sa končí číslicou 6. To je možné.
Ak sa končí číslicou 9: Tak potom samotná mocnina 2 sa končí číslicou 8, čo je možné.
Aj tieto dve možnosti si odložme.
Teda vidíme, že má zmysel uvažovať iba o tých tvaroch prvej zátvorky, ktoré sa končia číslicami: 5,7,9. Keďže 5 a 7 sú prvočísla, tak tu by sa spoločný násobok končil alebo číslicou 5 alebo 7, alebo číslicou 1. U čísla 9 má zmysel uvažovať o tom, že spoločný násobok sa končí číslicou alebo 1, alebo 9, alebo 3.
A teraz sa pozrime na to, kedy sa končí mocnina čísla 2 číslicou 4. To, ako ste isto vypočítali aj v školskom kole MO A, platí vtedy, keď exponent má tvar: 2+4x.
A keď má exponent takýto tvar, potom 3 umocnené týmto exponentom sa končí číslicou 9. Teda jedna zátvorka sa končí číslicou 5, druhá číslicou 9+2=11. To znamená, že spoločný deliteľ by sa musel končiť číslicou 5 alebo 1. Ale pritom neexistuje možnosť, kde ........m*........5=......1(toto je možnosť, kde spoločný násobok, ktorý sa končí číslicou 5 sme vynásobili nejakým číslom, ktorý sa končí číslicou m a dostali druhú zátvorku) , pričom m leží v intervale 1-10. Ešte treba zvážiť možnosť, ak sa spoločný násobok končí číslicou 1. To zatiaľ necháme tak.
Ak sa mocnina čísla 2 končí číslicou 6, tak exponent má tvar n=4+4x. Spoločný násobok sa, samozrejme, končí číslicou alebo 1, alebo 7. Pritom 3 umocnené exponentom v tvare 4+4x sa končí číslicou 1, teda druhá zátvorka sa končí číslicou 1+2=3. Teda opäť sa spoločný násobok musí končiť číslicou 1.
Ak sa mocnina čísla 2 končí číslicou 8, tak exponent má tvar n=3+4x. A číslo 3 umocnené takýmto exponentom sa končí číslicou 7, teda druhá zátvorka sa končí číslicou 7+2=9. Teraz nastal zaujímavý prípad, keď sa obe zátvorky končia rovnakou číslicou. Spoločný deliteľ sa musí končiť číslicami 1,3 alebo 9. Ak sa spoločný násobok končí číslicou 9, znamená to, že aj rozdiel jednej a druhej zátvorky je deliteľný číslom 9. Pritom rozdiel má na konci číslo 0. Ak od tohto čísla odčítame jednu alebo druhú zátvorku, tak výsledné číslo bude mať na konci číslicu 1. Teraz od tohto čísla opäť odčítajme niektorú zo zátvoriek a na konci nám zostalo číslo 2. A tento výsledný rozdeľ musí byť deliteľný číslom, ktoré ma na konci číslicu 9. Ale nie je možné, aby súčin dvoch číslic, kde na konci jedného je 9, dal na číslo, na ktorého konci je číslica 2. Teda túto možnosť tiež vylúčime.
Takže počet možností bol zredukovaný iba možnosti, kde sa spoločný násobok končí číslicou 3 alebo 1. Skúste teda nad týmto pouvažovať.
Zoberme si možnosť, kde sa zátvorky končí číslicou 9. Vieme, že 3 na n-tú je 1,5 na n-tú viac ako 2 na n-tú. Teda sme schopný vynásobiť prvú zátvorku istým číslom tak, aby nám vznikla druhá zátvorka. Vieme, že obe zátvorky sa končia číslicou 9. A o čísle, ktoré sa končí číslicou 9 vieme, že ho musíme vynásobiť aspoň 11x, aby výsledný súčin mal na konci opäť číslicu 9. Teda, násobky čísla, ktoré sa končí číslicou 9, treba násobiť prirodzenými mocninami čísla 11, keď chceme, aby sa výsledný súčin končil číslicou 9. Pritom 1,5 na n-tú nikdy nebude prirodzená mocnina čísla 11. Teda túto možnosť vylúčime.
Zostala posledná možnosť. Keď je spoločný násobok prvočíslo končiace sa číslicou 1.
Ak sa prvá zátvorka končí číslicou 5 a druhá číslicou 1, tak potom:
Ak máme prvé číslo, ktoré sa končí číslicou 5 a chceme, aby po výsledný súčin končil číslicou 1, tak potom číslo, ktorým vynásobíme prvé číslo, musí mať sa desatinnou čiarkou túto hodnotu: .....,20. Ale existuje mocnina čísla 1,5, ktorá sa takto končí? Skúste nad tým pouvažovať.
Ak sa prvá zátvorka končí číslicou 7 a druhá číslicou 3:
Ak máme číslo, ktoré sa končí číslicou 7 a chceme, aby po vynásobení číslom A, bol výsledný súčin číslo končiace sa číslicou 3, tak potom A musí mať za desatinnou čiarou: ......,1/(7/3). Pritom 7/3 je racionálne číslo, teda (aspoň si myslím) aj podiel 1/(7/3) bude iba racionálne číslo. Pritom mocnina 1,5 nikdy nie je racionálne číslo, pretože neustále násobíme číslo, ktoré má ukončený desatinný rozvoj. Teda aj túto možnosť vylúčime. A toto bola posledná možnosť, ktorá zostala. Teda definitívne môžeme povedať, že okrem čísla 1 nemajú tieto dva výrazy spoločného deliteľa.
Niečo som prehliadol?
BakyX, spoločný násobok: Celkom by ma zaujímalo, kde si našiel tento príklad.
Vychádzam z toho, že 3 na n-tú je presne 1,5 na n-tú viac ako 2 na n-tú:
Vieme, že násobky 1,2,3,4,6,8 určite nebudú spoločným násobkom, lebo toto všetko sú násobky alebo 2, alebo 3 a tým minimálne jedna zo zátvoriek nie je. To znamená, že nejaká zo zátvoriek je násobok 5,7 a ďalších prvočísiel. Z toho vyplýva, že jedna zo zátvoriek sa nepochybne končí číslicami 1,3,5,7 alebo 9 ako aj druhá. A spoločný násobok bude nejaké prvočíslo.
Pre prvú zátvorku:
Ak sa končí číslicou 1: tak potom samotná mocnina 2 sa končí číslicou 0. Ale taká neexistuje.
Ak sa končí číslicou 3: Tak potom samotná mocnina čísla 2 sa končí číslicou 1. Taká neexistuje.
Ak sa končí číslicou 5: Tak potom samotná mocnina 2 sa končí číslicou 4. To je možné. Toto si zatiaľ odložme do šuflíka.
Ak sa končí číslicou 7: Tak potom samotná mocnina 2 sa končí číslicou 6. To je možné.
Ak sa končí číslicou 9: Tak potom samotná mocnina 2 sa končí číslicou 8, čo je možné.
Aj tieto dve možnosti si odložme.
Teda vidíme, že má zmysel uvažovať iba o tých tvaroch prvej zátvorky, ktoré sa končia číslicami: 5,7,9. Keďže 5 a 7 sú prvočísla, tak tu by sa spoločný násobok končil alebo číslicou 5 alebo 7, alebo číslicou 1. U čísla 9 má zmysel uvažovať o tom, že spoločný násobok sa končí číslicou alebo 1, alebo 9, alebo 3.
A teraz sa pozrime na to, kedy sa končí mocnina čísla 2 číslicou 4. To, ako ste isto vypočítali aj v školskom kole MO A, platí vtedy, keď exponent má tvar: 2+4x.
A keď má exponent takýto tvar, potom 3 umocnené týmto exponentom sa končí číslicou 9. Teda jedna zátvorka sa končí číslicou 5, druhá číslicou 9+2=11. To znamená, že spoločný deliteľ by sa musel končiť číslicou 5 alebo 1. Ale pritom neexistuje možnosť, kde ........m*........5=......1(toto je možnosť, kde spoločný násobok, ktorý sa končí číslicou 5 sme vynásobili nejakým číslom, ktorý sa končí číslicou m a dostali druhú zátvorku) , pričom m leží v intervale 1-10. Ešte treba zvážiť možnosť, ak sa spoločný násobok končí číslicou 1. To zatiaľ necháme tak.
Ak sa mocnina čísla 2 končí číslicou 6, tak exponent má tvar n=4+4x. Spoločný násobok sa, samozrejme, končí číslicou alebo 1, alebo 7. Pritom 3 umocnené exponentom v tvare 4+4x sa končí číslicou 1, teda druhá zátvorka sa končí číslicou 1+2=3. Teda opäť sa spoločný násobok musí končiť číslicou 1.
Ak sa mocnina čísla 2 končí číslicou 8, tak exponent má tvar n=3+4x. A číslo 3 umocnené takýmto exponentom sa končí číslicou 7, teda druhá zátvorka sa končí číslicou 7+2=9. Teraz nastal zaujímavý prípad, keď sa obe zátvorky končia rovnakou číslicou. Spoločný deliteľ sa musí končiť číslicami 1,3 alebo 9. Ak sa spoločný násobok končí číslicou 9, znamená to, že aj rozdiel jednej a druhej zátvorky je deliteľný číslom 9. Pritom rozdiel má na konci číslo 0. Ak od tohto čísla odčítame jednu alebo druhú zátvorku, tak výsledné číslo bude mať na konci číslicu 1. Teraz od tohto čísla opäť odčítajme niektorú zo zátvoriek a na konci nám zostalo číslo 2. A tento výsledný rozdeľ musí byť deliteľný číslom, ktoré ma na konci číslicu 9. Ale nie je možné, aby súčin dvoch číslic, kde na konci jedného je 9, dal na číslo, na ktorého konci je číslica 2. Teda túto možnosť tiež vylúčime.
Takže počet možností bol zredukovaný iba možnosti, kde sa spoločný násobok končí číslicou 3 alebo 1. Skúste teda nad týmto pouvažovať.
Zoberme si možnosť, kde sa zátvorky končí číslicou 9. Vieme, že 3 na n-tú je 1,5 na n-tú viac ako 2 na n-tú. Teda sme schopný vynásobiť prvú zátvorku istým číslom tak, aby nám vznikla druhá zátvorka. Vieme, že obe zátvorky sa končia číslicou 9. A o čísle, ktoré sa končí číslicou 9 vieme, že ho musíme vynásobiť aspoň 11x, aby výsledný súčin mal na konci opäť číslicu 9. Teda, násobky čísla, ktoré sa končí číslicou 9, treba násobiť prirodzenými mocninami čísla 11, keď chceme, aby sa výsledný súčin končil číslicou 9. Pritom 1,5 na n-tú nikdy nebude prirodzená mocnina čísla 11. Teda túto možnosť vylúčime.
Zostala posledná možnosť. Keď je spoločný násobok prvočíslo končiace sa číslicou 1.
Ak sa prvá zátvorka končí číslicou 5 a druhá číslicou 1, tak potom:
Ak máme prvé číslo, ktoré sa končí číslicou 5 a chceme, aby po výsledný súčin končil číslicou 1, tak potom číslo, ktorým vynásobíme prvé číslo, musí mať sa desatinnou čiarkou túto hodnotu: .....,20. Ale existuje mocnina čísla 1,5, ktorá sa takto končí? Skúste nad tým pouvažovať.
Ak sa prvá zátvorka končí číslicou 7 a druhá číslicou 3:
Ak máme číslo, ktoré sa končí číslicou 7 a chceme, aby po vynásobení číslom A, bol výsledný súčin číslo končiace sa číslicou 3, tak potom A musí mať za desatinnou čiarou: ......,1/(7/3). Pritom 7/3 je racionálne číslo, teda (aspoň si myslím) aj podiel 1/(7/3) bude iba racionálne číslo. Pritom mocnina 1,5 nikdy nie je racionálne číslo, pretože neustále násobíme číslo, ktoré má ukončený desatinný rozvoj. Teda aj túto možnosť vylúčime. A toto bola posledná možnosť, ktorá zostala. Teda definitívne môžeme povedať, že okrem čísla 1 nemajú tieto dva výrazy spoločného deliteľa.
Niečo som prehliadol?
Miroslav Olšák | org | 10. 12. 2011 18:53:01
Ja otazku chapu, Mark chce spocitat GCD v Bakyxove prikladu pomoci Euklidova algoritmu. Problem je, ze nevi, kolikanasobek toho (2^n+1) by mel odecist.
No, ja to taky nevim. Jasne, ze to je zhruba 1,5^n, ale toho vubec neumim vyuzit. Uz treba proto, ze to ani neni cele cislo. Nicmene obecne se mi zda, ze tudy spis cesta nevede.
No, ja to taky nevim. Jasne, ze to je zhruba 1,5^n, ale toho vubec neumim vyuzit. Uz treba proto, ze to ani neni cele cislo. Nicmene obecne se mi zda, ze tudy spis cesta nevede.
Pavel Šalom | 10. 12. 2011 18:34:15
To bude vypadat jako dost odbyta odpoved, ale nenapada me, jak odpovedet lepe.
je priblizne 
-krat vetsi nez a prislusny rozdil je (ac se to mozna nezda) priblizne (ve smyslu 
).
Mozna jsem ale otazku nepochopil spravne.
Mozna jsem ale otazku nepochopil spravne.
Mark Daniel | 10. 12. 2011 17:36:34
Existuje nejaký spôsob ako všeobecne zapísať približne koľkokrát je mocnina čísla 3 umocnená na n-tú, väčšia ako mocnina čísla 2 umocnená na n-tú. Alebo aký je rozdiel týchto dvoch mocnín?
Miroslav Olšák | org | 10. 12. 2011 15:36:45
teorie cisel (stale jen dohady):
+ skrytý text
+ skrytý text
Otestoval jsem, ze pripadne GCD by nebylo delitelne zadnym prvocislem mensim nez milion. A jeste jsem malinko vylepsil Kennyho "protipriklad":
http://www.wolframalpha.com/input/?i=Table[Po...
Nicmene netusim, jestli Bakyxovo tvrzeni plati, ani jak by se na nej dalo jit. V tomhle to je to pro mne trochu jak Collatz.
http://www.wolframalpha.com/input/?i=Table[Po...
Nicmene netusim, jestli Bakyxovo tvrzeni plati, ani jak by se na nej dalo jit. V tomhle to je to pro mne trochu jak Collatz.
Kalendář
Z naší fotogalerie
