Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 09. 03. 2018 12:09

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Uspořádej čísla

Ahoj. Na internetu jsem narazila na příklad, snad zajímavý...
Uspořádej čísla 1 až 305 tak, aby součet každých dvou sousedů byl třetí mocninou celého čísla.


What does a drowning number theorist say?
'log log log log ...'

Offline

  • (téma jako vyřešené označil(a) Andrejka3)

#2 09. 03. 2018 17:11

check_drummer
Příspěvky: 4766
Reputace:   105 
 

Re: Uspořádej čísla

↑ Andrejka3:
Ahoj. A lze to? Nebo se má dokázat, že to nejde? :-)


"Máte úhel beta." "No to nemám."

Offline

 

#3 09. 03. 2018 17:37 — Editoval check_drummer (09. 03. 2018 21:05)

check_drummer
Příspěvky: 4766
Reputace:   105 
 

Re: Uspořádej čísla


"Máte úhel beta." "No to nemám."

Offline

 

#4 09. 03. 2018 18:13

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ check_drummer:


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#5 10. 03. 2018 14:57

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

Řešení je  tady, bez komentáře, jak k němu dojít.
↑ check_drummer:


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#6 10. 03. 2018 17:00 — Editoval laszky (10. 03. 2018 17:00)

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

Pokud si vytvorime graf majici 305 vrcholu odpovidajicich cislum 1-305 a dva vrcholy budou spojene hranou, paklize je soucet odpovidajich cisel treti mocninou celeho cisla, potom se jedna o problem z teorie grafu - nalezeni Hamiltonovske cesty v grafu. Tzn. cesty, ktera projde po hranach grafu pres vsechny jeho vrcholy, pricemz kazdy navstivi prave jednou. Zkousel jsem to v programu wxmaxima, ale trva mu to hodne dlouho. Graf ma 305 vrcholu a 399 hran. Jeden jediny vrchol ma stupen 1, a to vrchol cislo 256, takze musi byt na kraji. Dalsich 173 vrcholu ma stupen 2, takze maji jiste sousedy.

Offline

 

#7 10. 03. 2018 17:05 — Editoval Andrejka3 (10. 03. 2018 17:07)

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#8 10. 03. 2018 17:29 — Editoval laszky (10. 03. 2018 17:30)

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

Problem si celkem zjednodusis, pokud si nejdriv najdes tech 173 cisel, ktere maji jasne sousedy. Jestlize problem spociva v nalezeni 304 "sousedstvi" (hran v grafu), potom minimalne 174 (pokud by vsechny byly za sebou) mas jasnych. Velmi pravdepodobne jich bude vic nez 174 - tipnul bych tak kolem 220-230. Takze ti zbyde uz jen vhodne vybrat dalsich 70-80 hran.

Offline

 

#9 10. 03. 2018 18:46

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:
No, teď mi zbývá 100 hra, pokud nemám někde chybu. Sousední vrcholy stupně dva jistě musí být propojeny hranou. Ale nevím, proč by vrchol stupně dva nemohl být konec Hamiltonovy cesty. Nemůže?
Díky za rady!


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#10 10. 03. 2018 19:11

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

To asi muze byt... Jeste bych zkusil vyhledat tyhle situace.

//forum.matweb.cz/upload3/img/2018-03/05249_grafhamil.png

Offline

 

#11 10. 03. 2018 23:09

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:
Tomu nerozumím. Čím je ta situace zajímavá?

Jako obvykle, když programuju, dělám spoustu chyb. Nový pokus: program by měl:
1) přidat hranu mezi vrcholem stupne 1 a sousedem
2) přidat hranu mezi dvema (sousednimi) vrcholy stupne 2
3) pridat hranu mezi vrcholem, ktery uz ma jednu pouzitou hranu, jednu zbyvajici a
    a) sousednim vrcholem stupne 2
    b) sousednim vrcholem stejne vlastnosti.
A vzdycky, kdyz uz mam vrchol se dvema pouzitymi hranami, tak ho odeberu a vytvorim si podgraf. Cestu si zapisuju zvlast.

Tak ted mi to pise, ze zbyva 223 hran do 304 cesty. Takže nic moc.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#12 10. 03. 2018 23:56

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

Ja uz to zvladnul ;)  Ale muj postup asi nebude vhodny, pokud by v grafu bylo mnohem vice hran...

Offline

 

#13 11. 03. 2018 00:11 — Editoval Andrejka3 (11. 03. 2018 00:15)

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:
Gratuluju! A zavidim :)
Znamena to, ze sis (sikovne) tipoval?

Edit: Na obrázku, jak jsou škrtnuté ty tři cesty. Proč by nemohla jedna z nich nebýt škrtnutá? Jednu neškrtnutou bychom škrtli a vytvořil by se jeden konec -- což je ok, ne?


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#14 11. 03. 2018 00:33 — Editoval laszky (11. 03. 2018 00:34)

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

Pres ty hrany u vrcholu stupne 2 cesta vest musi, takze do toho vrcholu (napr. stupne 5 jako na obrazku) vedou urcite dve hrany z vrcholu stupne 2. Treti hrana z jednoho vrcholu vest nemuze, takze vsechny ostatni muzeme skrtnout ;-)

Offline

 

#15 11. 03. 2018 00:38

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:
Nemusí. V jednom z nich může končit (i když s 'malou pravděpodobností').


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#16 11. 03. 2018 00:58

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

Nj, to je asi pravda... v tom pripade by mi to nefungovalo. Nicmene, vzhledem k tomu, ze se to behem tech 5 iteraci ani jednou nestalo, tak za tim asi bude nejake pravidlo, proc to fungovalo :-)

Offline

 

#17 11. 03. 2018 14:13

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

Napadlo me, ze pokud nejaky z vrcholu, ktery ma stupen 2 (cerveny vrchol na obrazku), bude nakonec koncovy, potom urcite lezi na nejake kruznici. Takze muzeme tu Hamiltonovskou cestu zvolit i jinak - tak aby tento vrchol koncovym nebyl (viz obrazek). Ale pravda je, ze ten muj postup selze, pokud nektera z tech hran, ktere odebiram, bude mostem - tj, pokud po odebrani te hrany vznikne nesouvisly graf. To bych tam mel nejak ohlidat.

//forum.matweb.cz/upload3/img/2018-03/73762_hamiduk.png

Offline

 

#18 11. 03. 2018 14:28

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:
Popřemýšlím o tom. Určitě se k tomu ještě vrátím. 3 dny mi to nedalo spát. Přitom to je taková blbost.

Ještě bych ráda věděla, jestli to tvé řešení je stejné jako na webu ↑ Andrejka3:.


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#19 11. 03. 2018 14:35

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

Ano, vyslo to stejne.

Offline

 

#20 11. 03. 2018 14:57

check_drummer
Příspěvky: 4766
Reputace:   105 
 

Re: Uspořádej čísla

Ahoj, já čekal nějaký elegantní důkaz, v tomto směru je škoda, že má úloha řešení. :-) Možná by bylo vhodné ji přesunout do "Algoritmy a programování". :-)


"Máte úhel beta." "No to nemám."

Offline

 

#21 11. 03. 2018 16:00 — Editoval laszky (11. 03. 2018 19:29)

laszky
Příspěvky: 2372
Škola: MFF UK, FJFI CVUT
Reputace:   197 
 

Re: Uspořádej čísla

↑ Andrejka3:

Ahoj, ale zjistil jsem, ze je vice reseni... napr. pokud se podivas na konec toho reseni, na ktere jsi dala odkaz, potom lze namisto

$\dots 34, 30, 186, \dots, 248, 95$

pouzit

$\dots 34, 30, 95, 248, \dots, 186$.

ale taky

$\dots 4, 121, 95, 248, \dots, 222$.

Offline

 

#22 11. 03. 2018 18:52

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:
Dobrý objev.

Vymyslela jsem vzory, které když se vyskytnou v grafu, řekne to, kterou hranou jít. Má to háček - v tom grafu nejsou :)
Ještě mě to baví, takže to nevzdávám.

↑ check_drummer:
Třeba se něco najde. Přesouvám...


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#23 11. 03. 2018 22:28

Stýv
Vrchní cenzor
Příspěvky: 5693
Reputace:   215 
Web
 

Re: Uspořádej čísla

↑ check_drummer: Objevil jsem opravdu podivuhodný důkaz; bohužel tohle okénko na psaní příspěvků je příliš malé, aby se do něj vešel.

Offline

 

#24 13. 03. 2018 00:17

Andrejka3
Moderátor
Příspěvky: 1994
Škola: PŘF UP Olomouc (2015)
Reputace:   119 
 

Re: Uspořádej čísla

↑ laszky:
Jasně. Hledal jsi všechny vrcholy takové, že když přidáš nějakou hranu do konstruované cesty a počítáš s vrcholem jako s koncem, jestli dostaneš těmi jednoduchými pravidly cestu délky 304.
Aspoň tak jsem to napsala v C.
Nebo jsi to dělal jinak?

Velké díky za trpělivost a že jsi všechny podrobnosti neprozradil! Díky tomu se můžu cítít, jako bych to vyřešila :D


What does a drowning number theorist say?
'log log log log ...'

Offline

 

#25 13. 03. 2018 17:22

check_drummer
Příspěvky: 4766
Reputace:   105 
 

Re: Uspořádej čísla

↑ Stýv:
Požádej admina, ať okénko zvětší. Máme více možností než za středověku. :-)


"Máte úhel beta." "No to nemám."

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson