Drevni kineski zadatak

[ filmil @ 01.05.2003. 18:47 ] @

Evo jednog „drevnog“ kineskog zadatka kog je postavio Vang Čang.

Sad, ne znam baš da li je zadatak stvarno drevan, pošto se pominju lampe koje po svoj prilici rade na struju a ni Vang Čang nije neki kineski mudrac koji je živeo u doba dinastije Ming, već radi za stolom preko puta, ali se svejedno nadam da je zanimljiv.

Dakle u Zabranjenom gradu postoji dugaaačak zid na kome je okačeno hiljadu lampi. Na početku su sve lampe isključene. Svaka lampa ima po prekidač (iz doba dinastije Ming :) ) kojim se može ugasiti ako je upaljena i upaliti ako je ugašena. Jednog dana pored zida prođe hiljadu Kineza (sitnica, naći hiljadu Kineza za ovakvu svrhu) i tako da Kinez sa rednim brojem i pritisne prekidač lampe broj i i sve celobrojne umnoške svog rednog broja. Dakle prvi Kinez će upaliti prvu, drugu, treću i tako sve do hiljadite. Drugi će pritisnuti dugme na drugoj (time je ugasivši), četvrtoj, šestoj, osmoj i sve tako do hiljadite. Petstoti će pritisnuti dugme na lampama broj 500 i 1000, a hiljaditi će napokon samo da pritisne prekidač na lampi broj 1000.

Pošto se svih 1000 Kineza izređaju, koliko lampi će biti upaljeno i koje su lampe u pitanju?

f

[ kristina perlas @ 02.05.2003. 01:12 ] @

prvo nesto samo mi je nejasno...koje lampe pale i gase 501, 502 ..dali samo po jednu...kako i 1000ti kinez?
kako i da je..ostace da svete samo 1, 4, 9, 16,25...i svi drugi do 1000 sto su puni kvadrati nekog prirodnog broja...zato sto ako se svaki broj razgleda posebno koji ce ga kinez paliti ili gasiti...onda se podrede svi njegovi delioci, i sigurno su ukupno paran broj, sem u slucaju kada je pun kvadrat, jer ako ih poredjamo u nizi onda na prvom odgovara zadnji...pr: za 18: 1,2,3,6,9,18(parovi su 1 i 18, 2 i 9, 3 i 6) i tako bi bili uvek paran broj, sem ako je na primer 25: 1,5,25 (ovde 5 je sam sebi par) pa su zato neparan broj ukupno...i zato bi na kraju gorela ta lampa...
izvinite ako ima gramaticke greske...ipak sam ja iz makedonije..pa ne govorim bas najsjajnije srpski
cao...

[ pixelmania @ 10.05.2003. 22:30 ] @

sledeci program u pascalu definitivno dokazuje da su u pitanju redom kvadrati prirodnih brojeva. e sad zasto, don't ask me...

Code:

for i:=1 to 1000 do
  for j:=1 to 1000 do
   if j mod i = 0 then a[j]:=not a[j];

for i:=1 to 1000 do
  if a[i]=true then write(i,' ');

[ filmil @ 10.05.2003. 22:34 ] @

Oba rešenja su ispravna naravno, jedno je dato „van sistema“ a jedno „u sistemu“, ali to nisu sva moguća. Postoji barem još jedno originalno rešenje.

f

[ chupcko @ 12.05.2003. 10:18 ] @

Citat:

pixelmania:
sledeci program u pascalu definitivno dokazuje da su u pitanju redom kvadrati prirodnih brojeva. e sad zasto, don't ask me...

Pa dokazuje ako rec dokaz uzmemo u bas onako jednom sirem znacenju :)).

Jel znate kako biolozi dokazuju da su svi neparni brojevi prosti:

1 pa prost je
3 prost je
5 prost je
7 prost je
9 hmmmmmmmmmmmmmmm ovo je eksperimetalna greska
11 je prost
13 je prost

dosta, svi neparni brojevi su prosti :)

P.S. Umesto reci "biolozi" mozemo lako staviti "elektrotehnicari", "fizicari" ...

[ salec @ 12.05.2003. 12:55 ] @

A zar nije to ustvari algoritam "Eratostenovo sito"? Sto ce reci, na kraju bi ostale da gore samo lampe ciji redni broj je prost broj (OK, znam, to je vec receno...)

[ chupcko @ 12.05.2003. 13:39 ] @

pa nije, ostaju brojevi koji su kvadrati nekog broja, pa samim tim i nisu prosti, eto ko ne veruje neka dokaze sledece tvrdjenje:

brojevi koji su kvadrati nekog broja nisu prosti :)

nego ajde da se skoncentrisemo na neki kao dokaz da ostaje taki broj koji je kvadrat ...

posmatrajmo lampu sa rednim brojem l

nju su palili i gasili (menjali stanje) svi kinezi koji imaju broj koji je neki faktor broja l.

takvih je bilo bar dvoje, onaj jadnik sa brojem 1 (koji je sve lampe morao da pogasi) i onaj kinez sa brojem l, ali mozda ih je bilo i jos koji

Ako ovako posatvimo stvari videcemo da ...

e sada videh da je kristina perlas ustvari odgovorila, ali sam malo bio zbunjen citajuci :(.

Idem da nadjem jos koje resenje :)

A uzgred sto nije bar bilo 1024 lampi ...

[ pixelmania @ 12.05.2003. 23:50 ] @

Evo opet mene sa svežim znanjem, a tu je i dr_voja (the brain) pored mene (muahahaha)

Elem, sledeća lema: prirodan broj ima neparan broj delilaca akko je u stvari potpun kvadrat prirodnog broja.

Dokaz:

, pri čemu je a_i prosti činilac broja n.

Kako je broj delilaca broja n jednak:

(elementarna kombinatorika)

Ako je broj potpun kvadrat, znači da su svi eksponenti parni brojevi, pa je proizvod gore neparan broj. Lako se vidi da važi i obrnuto.

Dakle, sada da se vratimo na kineski zadatak.
Kada prođe hiljaditi kinez, sve lampe koje će biti ukjučene, bile su neparan broj puta uključivan/isključivane (lako se vidi). Zbog toga, lampe koje će svetleti su lampe koje imaju redni broj potpunog kvadrata (ko ne zna šta je to, čisto zbog onog Eratostenovog sita, to su brojevi 1,4,9,16,25,36...)

pozdrav od mene i dr_voje.

[ istok77 @ 15.06.2003. 12:04 ] @

Citat:

filmil:

Oba rešenja su ispravna naravno, jedno je dato „van sistema“ a jedno „u sistemu“, ali to nisu sva moguća. Postoji barem još jedno originalno rešenje.

Dobro, mozemo li da cujemo to "originalno" resenje, posto sam ja bas zainteresovan?

[ filmil @ 15.06.2003. 12:55 ] @

Pixelmania je dao odgovor na koji sam mislio.

f