18 decembra 2011

Znamienka


Pre ktoré čísla n existuje n-tica e1,...,en "znamienok" (čiže n-tica pozostávajúca z čísiel -1 a 1) taká, že e11+e22+...+enn=0?

13 komentárov:

goober povedal(a)...

Jéj, Rado je späť... a s ním prišla nová úloha :-)

Anonymný povedal(a)...

Nebudu to take, ktore su delitelne 4 alebo delitelne 4 so zvyskom 3 ?

Ak je to dobre, tak ... spoiler alert! :-)

goober povedal(a)...

Veruže spoiler.

Ale zase treba uznať, že už v prvej triede sme sa učili, že 0=0 a 1+2=3. No a známe porekadlo vraví, že indukciou ďalej zájdeš :-)

Radoslav Harman povedal(a)...

goober: Áno, už som späť v Bratislave a možno sa aj príspevky na blogu začnú vyskytovať časejšie :) Uvažoval som aj tom, že by som niečo preložil do angličtiny pre mojich zahraničných priateľov.

Čo sa týka úlohy, tak samozrejme máte s anonymom pravdu. Už len to nejako veľmi stručne zdôvodniť (je to ľahké).

Zaujímavejšie a potenciálne oveľa ťažšie podobné úlohy by sme dostali, keby sme neuvažovali postupnosť čísiel 1,2,..., ale nejakú inú a_1,a_2,....

Podľa mňa je veľmi ťažké už len nájsť efektívny (lepší ako exponenciálny vzhľadom na n v zmysle worst case) algoritmus, ktorý pre zadané a_1,...,a_n rozhodne, či vôbec existuje n-tica e_1,...,e_n znamienok taká, že e_1*a_1+...+e_n*a_n=0.

goober povedal(a)...

V úplne všeobecnej verzii to znie NP-úplne, hovorí sa tomu Partition problem. To ale nebráni niektorým konkrétnym prípadom, aby boli riešiteľné explicitne -- napríklad Radova verzia s a_i = i je jednoduchá.

Ako by to ale vyzeralo s a_i = i^2 (prípadne s vyššími mocninami, keby toto bolo tiež príliš ľahké)?

Radoslav Harman povedal(a)...

Ja som si bol vedomý toho, že ekvivalentne sa dá úloha zadať ako otázka, či sa dá (multi)množina prirodzených čísiel rozdeliť na dve pod(multi)množiny s rovnakým súčtom, na základe čoho som aj nekreslil ilustračný obrázok. Ale že je to dôležitá úloha, ktorá už bola toľko študovaná (dokonca Karpom), tak to ma teda nenapadlo...

Rori povedal(a)...

Az teraz som pochopil (po poslednom Radovom prispevku :) ) co ten obrazok mal predstavovat :)

Brano povedal(a)...

sice trochu neskoro, ale napadlo ma zdovodnenie preco sa to neda pre n=4k+1 a n=4k+2

nech m je take, ze 2m-1<=n<=2m
potom 1e_1+...+ne_n=m (mod 2)

pekne nie? mod 2 je super kedze e_k=1 (mod 2)

Radoslav Harman povedal(a)...

Je možné ešte elementárnejšie formulovať dôkaz prečo n nemôže byť tvaru 4k+1 a 4k+2, kde k je celé nezáporné číslo. Ak k obom stranám rovnosti e_1*1+...+e_n*n=0 pričítame dvojnásobok každého čísla, ktoré sa v tejto rovnosti vyskytuje so záporným znamienkom, dostaneme 1+...+n=t, kde t je nutne párne číslo. Je ale veľmi jednoduché presvedčiť sa, že súčet 1+...+n je nepárny pre čísla 1,2,5,6,9,10,...

Zdôvodnenie, že pre ostatné čísla n požadovaný výber znamienok existuje, je taktiež jednoduché (ak sa niekomu chce, budem rád, keď nám ten dôkaz napíše do komentárov).

Komplikovanejšie už bude nájsť vzťah pre počet rôznych n-tíc znamienok, ktoré spĺňajú požadovanú rovnosť.

Prajem Vám všetkým krásne Vianoce.

goober povedal(a)...

Tak tak, tiež som chvíľu to Braňovo riešenie spracovával :-)

Ja som tiež išiel podobnou cestou ako Rado, súčet čísel s kladným a súčet čísel so záporným znamienkom je rovnaký => súčet všetkých je párny. No ale n(n+1)/2 je párne len pokiaľ n alebo (n+1) je násobok 4.

No ale teraz ma normálne navnadil ten príklad s počtom rôznych oznamienkovaní :-)

Rori povedal(a)...

Je reklama tak co by som nenapisal (pred tym som bol lenivy :) )

Staci jednu vec dokazat - ked mam urcite riesenie pre x = ( a - 1), a pridam 4 dalsie cisla tak je to tiez riesenie (cize x + 4 bude tiez OK) - cize ak predtym sucet bol 0 tak
0 (+/-) a (+/-) a + 1 (+/-) a + 2 (+/-) a + 3 musi byt tiez 0 co sa da napr.
0 - a + (a + 1) + ( a + 2) - ( a + 3)

no a potom nam staci preskumat prve 4 moznosti (ostatne odvodime z tych prvych troch) - a tam dostavame 3 a 4.

Z toho sice nevyplyva neexistencia 4k+1 a 4k+2 ale dokaz na to uz tu bol :)

a snad uz reklama skoncila :)

goober povedal(a)...

Fuj, ten počet oznamienkovaní zatiaľ vyzerá pomerne tyčkato :-)

"Explicitne" mi to zatiaľ vychádza rádovo na Theta(N^3) operácií s algebraickými číslami.

Zvoľme si M ako celé číslo ostro väčšie ako N(N+1)/2. Potom sa ten počet oznamienkovaní dá vyrátať takto (áno, tie kosínusy sú algebraické :-) ):

Pocet[N] = (2^N/M) * SUM[k=0..M-1, PROD[t=1..N, cos(2*Pi*k*t/M)]]

Formulka samotná vzišla z kombinácie generujúcej funkcie (stadiaľ ten súčin) a kombinatorického hmatu na vymlátenie nepohodlných polynómov (=> suma).

Radoslav Harman povedal(a)...

Možno skrátka neexistuje jednoduchý predpis udávajúci ten počet oznamienkovaní pre zadané n.

Ak by sa niekto s tým ešte chcel zabávať, tu sú príslušné počty oznamienkovaní pre n=1,...,24:

0, 0, 2, 2, 0, 0, 8, 14, 0, 0, 70, 124, 0, 0, 722, 1314, 0, 0, 8220, 15272, 0, 0, 99820, 187692