23 septembra 2011

Nemožné?

Použitím cifier 1, 2, 3, ..., 9 (každú najviac raz) a operácii plus, mínus, krát, deleno, druhá odmocnina, umocňovanie, dvojkový logaritmus a zátvoriek napíšte ľubovoľné prirodzené číslo.

To je zadanie úlohy, ktoré mi pred pár dňami poslal Ondrej Budáč. Vzhľadom na to, že na prvý (aj druhý, aj tretí...) pohľad vzbudzuje úloha dojem neriešiteľnosti, uvediem tiež vlastné, trochu podrobnejšie, "informaticky ladené" znenie:

Nájdite spôsob ako konštruovať výrazy v1, v2, ... (v nejakom hypotetickom programovacom jazyku, ktorý počíta úplne presne s reálnymi číslami a má neobmedzenú dĺžku výrazov) také, že hodnota výrazu vi je i. Každý z výrazov vi môže obsahovať maximálne raz každú z cifier 1,2,..,9 a ľubovoľnekrát operátory +,-,*,/,^, funkcie sqrt,log2 a zátvorky (,). (Funkcia sqrt počíta druhú odmocninu a log2 dvojkový logaritmus.) Cifra 0 ani žiadne iné operátory a funkcie (ani premenné a konštanty) nie sú dovolené.

Ja som sa s týmto problémom trápil najprv asi pol hodiny, ale po dlhšej pauze ma napadlo riešenie už veľmi rýchlo. Naozaj to ide, nie je v tom žiadny chyták!

8 komentárov:

goober povedal(a)...

Pekná úloha! Žiaľ, už som ju videl v mierne odlišnej podobe (riešenie ale bolo rovnaké), ale tiež ma to kedysi potrápila :-)

Radoslav Harman povedal(a)...

goober: Ja som to nepoznal. Tou mierne odlišnou podobou si asi myslel, že treba použiť každú z cifier 1,...,9 práve raz, však. (To bolo totiž úplne pôvodné Ondrovo zadanie, ktoré som potom po "dohode" s ním modifikoval na toto veľmi podobné.)

goober povedal(a)...

Ja som poznal ešte inú verziu. Zatiaľ ju ale neprezradím, lebo aj samotné zadanie by trochu pomohlo s riešením tej Ondrovej :-)

Rori povedal(a)...

No je jasne, ze sa bud sqrt alebo log2 alebo oba musia "cyklit".

To co by malo vyhovovat je :

log2 ( 1 / ( log2 ( sqrt[X] (2))))

pricom sqrtX je X vnorenych sqrt (napr. sqrt[3](a) => sqrt(sqrt(sqrt( a)))

no a pre lubovolne cislo i = log2 ( 1 / ( log2 ( sqrt[i] (2))))

btw: ak by sa mali vyuzit vsetky cifry tak sa to da tak, ze k tomu vyrazu hore pripocitame

(9 - 5 - 4) * ( 3 + 6 + 7 + 8)

:)

Radoslav Harman povedal(a)...

Rori: Super! Je to (takmer) presne to iste riesenie, ktore napadlo aj mna a taktiez Ondra Budaca. (Mozno nejake velmi odlisne riesenie ani neexistuje.)

Lev bez hrivy povedal(a)...

Aj ja som na to vynimocne prisiel, klucom bolo prist na to, ako si vyrobit nekonecne vela cisel, ta druha odmocnina dost pomohla :)

Michal povedal(a)...

Táto úloha mi, pripomenula hlavolam, je to rovnica,
ktorej chýbajú plusy a mínusy a zároveň jedno,
z číslic je dvojciferné.

Hlavolam
1_2_3_4_5_6_7_8_9=100
Jedno z možných riešený hlavolamu.
1+2+3-4+5+6+78+9=100

Radoslav Harman povedal(a)...

Michal: To je celkom pekná úloha, ktorá precvičí logické uvažovanie; ďakujeme za návrh. Bola mi inšpiráciou pre nový (ale omnoho ťažší) problém, ktorý publikujem ako samostatný príspevok.