zanimljiva matematika

[CPP]

Aj da probam ja nesto na tu temu. 3 merenja nam daju 27 mogucih ishoda ( 3^3). U 14 kuglica ima 28 razlicitih mogucnosti (svaka kuglica moze da bude laksa/teza). Iz ovoga bi sledilo da ne moze u 3 merenja da se nadje i koja je kuglica i da li je laksa ili teza. Dal moze da se nadje samo koja je ne znam.

[Al-Khwarizmi]

3) Znaš koja je kuglica defektna ali neznaš da li je teža ili lakša ako ona koju uzmeš opet bude u ravnoteži.

U pravu si. Ali se i u zadatku sa 12 tražilo da se nađe defektna kuglica, a ne da se odredi da li je teža ili lakša:

...kako pronaci razlicitu kuglicu iz tri merenja? :)

Doduše, sa 12 kuglica se može odrediti i koja je vrsta defekta u pitanju. Sa 13 sigurno može da se odredi koja je to kuglica, i u ovom jednom graničnom slučaju po rešenju koje sam predložio se ne bi znalo da li je ta preostala lakša ili teža. Nisam siguran ni da bi moglo. Ako bi moglo, onda bi i sa 14 kuglica moglo da se pronađe rešenje pri kome nije neophodno znati koja je vrsta defekta u pitanju.

[Anton]

U pravu si. Ali se i u zadatku sa 12 tražilo da se nađe defektna kuglica, a ne da se odredi da li je teža ili lakša:

Ako se samo traži defektna onda jednostavno...Četri naprama četri. Ako su u ravnoteži onda tri od preostalih pet i tri od prethodno izmjerenih osam. Ako su u ravnoteži onda prezadnja kuglica sa bilo kojom i znamo da li je to ta i da li je teža ili lakša, a u slučaju ravnoteže znamo da je zadnja defektna. A u slučaju da su tri od preostalih pet teže nego tri od prethodno izmjerenih osam onda dvije od tri i znamo koja je teža, ili jedna od te dvije ili preostala kuglica. Ovo je lako. ( Edit---Da ne bude zabune. Ako su četri naprama četri u neravnoteži onda postupak poput ovog dolje )Ja sam pokušao sa 13/14 a da doznam koja je i da li je lakša ili teža. Nisam uspio do sada. A vjerojatno je i nemoguće.Pet naprama pet, ako u ravnoteži onda je lako naći iz dva pokušaja između preostalih tri/četri kuglice koja je kuglica defektna i da li je teža ili lakša.Ako neravnoteža pet naprama pet,, ljeva strana vage prividno teža..1 62 73 84 95 10onda kombinacija:1 42 63 117 128 13( 5, 9 i 10 sa strane )Ako ravnoteža onda 9 i 10 na vagu da se vidi koja je lakša, a ako opet ravnoteža onda znamo da je 5 i da je teža.Ako vaga prevagne na desno onda 7 i 8 da se vidi koja je lakša, ako opet ravnoteža onda je 4 i teža je.Ako ostane vaga u istom položaju prividno teža na ljevoj strani onda,1 26 11Ako u ravnoteži onda znamo da je 3 i da je teža, a ako ostane prividno teža na ljevoj strani onda je 1 i teža je, ako prevagne na desnu stranu onda je ili 6 i lakša je ili je 2 i teža je...failure failure failure...Kako zaobići "failure"?kurdi, reci da li postoji rješenje za 13 ili 14 a da se može doznati koja je kuglica i da li je lakša ili teža?Tako da znam da li da još malo pokušam naći rješenje. Edited October 31, 2007 by Anton

[Al-Khwarizmi]

Ako u ravnoteži onda znamo da je 3 i da je teža, a ako ostane prividno teža na ljevoj strani onda je 1 i teža je, ako prevagne na desnu stranu onda je ili 6 i lakša je ili je 2 i teža je...failure failure failure...

Sa ovakvim drugim korakom ne možeš da izbegneš problem nikako. Zato što ti je jedan moguć slučaj da ti ostanu 3 kuglice koji su kandidati za težu (1, 2, 3), i jedna koja je kandidat za lakšu (6). Sa tim ne možeš nikako iz jednog merenja da lociraš defektnu, tražio se tip defekta ili ne.Ako sa X označimo nemerenu kuglicu za koju ne znamo da li je ispravna, sa L kuglicu kandidata za lakšu, sa T kuglicu kandidata za težu, a sa I kuglicu za koju znamo da je ispravna, pravila za poslednje merenje su sledeća (nadam se da nisam nešto zaboravio):1) na istom tasu ne smeju biti dve T kuglice (ili L, svejedno). U tom slučaju ako vaga prevagne na njihovu stranu (za T), nećemo znati koja od te dve je defektna.2) na suprotnim tasovima se ne smeju naći suprotni kandidati (na jednom T a na drugom L). Ako prevagne na T stranu, ne znamo da li je T teža ili L lakša.3) Ako se X nalazi na tasu, nijedna druga kuglica se ne sme nalaziti na istom tasu, i sa suprotne strane mora biti I. Mislim da je ovo jasno - inače se uvek može naći situacija u kojoj ne znamo da li je X tražena kuglica ili neka druga.4) pored merenih, sa strane može da ostane samo još jedna kuglica koja nije I (T ili L ako se mora znati težina, ako ne onda može i X). I ovo je jasno, pretpostavljam.Kod tebe je narušeno drugo pravilo, jer ti se u trećem merenju na suprotnim stranama nalaze 6 i 2.Iz gornjih pravila zaključujem da za poslednje merenje sme ostati samo jedan od dole nabrojanih slučajeva, ili jednostavniji. Podrazumeva se da su sve ostale kuglice I. Naravno, T i L svuda mogu zameniti mesta, pa nećemo to pisati:- 2 T + 1 L- 3 TAko ne treba znati težinu defektne, onda dodajemo i ovo:- 2 T + 1 X - 2 X (inače, ako se traži tip defekta, onda samo 1 X)Sledeće situacije u poslednjem koraku su nerešive:- 3 X- 2 T + 2 L- 3 T + 1 L- 4 T...Polazeći od ovoga, mislim da bi se moglo dokazati da ne možemo u prvom koraku meriti 5 naspram 5 kuglica. Ako merimo 4 naspram 4, ostaje nam 6 nemerenih kuglica. Ako se dobije ravnoteža u prvom, zbog nerešivosti situacije 3 X za poslednje merenje, u drugom merenju možemo sa strane ostaviti najviše 2 nemerene kuglice, tako da nam ostaje za drugo merenje 4 Y + 2 X (i 8 I na raspolaganju), gde su sa Y označene X kuglice koje se moraju iskoristiti u toku drugog merenja. Mislim da bi se uz malo truda moglo dokazati da ni to nije rešivo.To bi onda značilo da slučaj sa 14 kuglica nije rešiv bez obzira da li se traži tip defekta ili ne. Kao što rekoh, nisam se udubljivao i pokušavao da izvededem dokaz do kraja. A prilično sam ubeđen i da bi kombinatorika mogla da ponudi mnogo elegantniji dokaz, ali sam trenutno previše lenj čak i da pokušam... Edited October 31, 2007 by Al-Khwarizmi

[kurdi]

trazi se naravno da se odredi koja je i da li je laksa ili teza.(mislim to je standardna verzija zadatka, podrazumevao sam da podrazumevamo, mada moguce da nije lepo receno na pocetku)nemam sada vremena da citam sve i trazim konkretne rupe, ali nemoguce je za 13, ne trudite se dzabe.ja ovo nisam znao dok al nije tvrdio da je resio, morao da razmislim.elem:svako merenje ima 3 ishoda (levo, desno, ravnoteza)tri merenja ima samo 3*3*3 = 27 mogucih razlicitih ishoda (od kojih u jednostavnim zadacima mnogi vode istom zakljucku).sa 14 kuglica ima 28 mogucnosti i ociglkedno ih nije moguce sve razluciti.za 13 ukupno ima 26 i to deluje na prvi pogled moguce.medjutim prvo merenje bi moralo da bude dizajnirano tako da nijedan ishod ne ostavlja vise od 9 mogucnosti (kolko se moze razluciti is preostala dva merenja).jedino resenje bi daklem bilo 9+9+8 (znaci 9 ako je levo/desno, 8 ako je ravnoteza, posto levo i desno ovigledno daju analogne zakljucke)medjutim (kad razmislis) posle prvog merenja svaki ishod ostavlja paran broj mogucnosti, tako da je ovo nemoguce.onog trenutka kada je al ostavio u prvom merenju 5 sa strane vec je propao, jer ravnoiteza ostavlja 10 mogucnosti.medjutim i da je merio 5 protiv 5, onda bi levo/desno ostavljalo 10 mogucnosti (tipa ili je jedna od ovoh 5 laksa kili jedna od ovoih 5 teza)12 je max broj za koji je resivo.

[Al-Khwarizmi]

trazi se naravno da se odredi koja je i da li je laksa ili teza.(mislim to je standardna verzija zadatka, podrazumevao sam da podrazumevamo, mada moguce da nije lepo receno na pocetku)nemam sada vremena da citam sve i trazim konkretne rupe, ali nemoguce je za 13, ne trudite se dzabe.

Nema rupa - ja za 13 nisam ni rešio ako se traži tip defekta (kao što napisah ranije, verovao sam da nema rešenja, a ti si to sad i dokazao). Rešio sam samo za slučaj gde nije neophodno saznati vrstu defektne kuglice.Ako je postavka takva, onda lovorike za verziju sa 14 kuglica idu CPP-u:

Aj da probam ja nesto na tu temu. 3 merenja nam daju 27 mogucih ishoda ( 3^3). U 14 kuglica ima 28 razlicitih mogucnosti (svaka kuglica moze da bude laksa/teza). Iz ovoga bi sledilo da ne moze u 3 merenja da se nadje i koja je kuglica i da li je laksa ili teza. Dal moze da se nadje samo koja je ne znam.

Dobar primer kako je nekad naizgled teške probleme relativno lako rešiti ako se samo sagledaju iz drugog ugla.

za 13 ukupno ima 26 i to deluje na prvi pogled moguce.medjutim prvo merenje bi moralo da bude dizajnirano tako da nijedan ishod ne ostavlja vise od 9 mogucnosti (kolko se moze razluciti is preostala dva merenja).jedino resenje bi daklem bilo 9+9+8 (znaci 9 ako je levo/desno, 8 ako je ravnoteza, posto levo i desno ovigledno daju analogne zakljucke)medjutim (kad razmislis) posle prvog merenja svaki ishod ostavlja paran broj mogucnosti, tako da je ovo nemoguce.onog trenutka kada je al ostavio u prvom merenju 5 sa strane vec je propao, jer ravnoiteza ostavlja 10 mogucnosti.medjutim i da je merio 5 protiv 5, onda bi levo/desno ostavljalo 10 mogucnosti (tipa ili je jedna od ovoh 5 laksa kili jedna od ovoih 5 teza)12 je max broj za koji je resivo.

Nicely done. :)Elem, sad bi bilo zanimljivo pozabaviti slučajem kada se ne traži da li je kuglica lakša ili teža, samo se mora naći iz 3 pokušaja. Već rekoh, prilično sam siguran da ni sa takvom postavkom za 14 kuglica ne postoji rešenje. Zadatak mi izgleda dosta teži za dokazivanje ako bi se pokušao primeniti pristup koji je sasvim lepo odradio posao kada se tražio tip defekta, jer se više ne može osloniti na to da imamo 28 mogućnosti koje treba pokriti (pošto nije bitno da li je teža/lakša).

[kurdi]

Aj da probam ja nesto na tu temu. 3 merenja nam daju 27 mogucih ishoda ( 3^3). U 14 kuglica ima 28 razlicitih mogucnosti (svaka kuglica moze da bude laksa/teza). Iz ovoga bi sledilo da ne moze u 3 merenja da se nadje i koja je kuglica i da li je laksa ili teza. Dal moze da se nadje samo koja je ne znam.

izvini, u brzini nisam ni video da si vec napisao dokaz, bezveze ponavljam.@al, jesi resio naravno, nema rupa ako se tako interpretira, ali sam podrazumevao da se tradicionalno interpretira.

[CPP]

izvini, u brzini nisam ni video da si vec napisao dokaz, bezveze ponavljam.@al, jesi resio naravno, nema rupa ako se tako interpretira, ali sam podrazumevao da se tradicionalno interpretira.

A jesam? Aj neko drugi jer1) nisam resio originalni (rosbacherov) zadatak2) nem ideju sta da turim

[Al-Khwarizmi]

@al, jesi resio naravno, nema rupa ako se tako interpretira, ali sam podrazumevao da se tradicionalno interpretira.

Ma razumeli smo se. Nego, sad mi pade na pamet - tvoj dokaz za slučaj sa 13 kuglica se može upoterbiti da se dokaže da sa 14 kuglica ne može da se uvek nadje defektna čak ni ako se ne traži težina!Naime, ako se koncentrišemo na broj kuglica koji može ostati neizmeren posle prva dva kruga, lako se može pokazati da on iznosi 1 u slučaju da se tip defekta traži, odnosno 2 ako nije bitan (vidi neki od mojih prethodnih postova). Te nemerene kuglice postaju bitne samo ako su tasovi u oba merenja u ravnoteži.Ako u bilo kom od prethodna dva merenja tasovi ne budu u ravnoteži, određivanjem defektne kuglice odredili smo i da li je ona teža ili laša. Te se u tim slučajevima oba zadatka svode na isti!Ovim smo dokazali da kada se ne traži da odredimo da li je kuglica teža ili lakša, smemo imati samo jednu kuglicu više od maksimalnog broja kuglica za koje je uvek moguće pronaći i poziciju i tip defekta. Zaključak - sa 14 kuglica ne možemo ni samo locirati defektnu kuglicu!

[Al-Khwarizmi]

1) nisam resio originalni (rosbacherov) zadatak

Ali si rešio teži. :)

2) nem ideju sta da turim

Pa onda bi mogao Despot_Stefan nešto da zada, sad sam se setio da sam mu nekulturno oteo red dok još nisam bio skapirao da su i ovde pravila da onaj ko reši postavlja sledeći zadatak.

[Anton]

Kada smo već kod elegantnih rješenja evo jednog starog ali simpatičnog problema. Nadam se da ima netko ovdje kome nije poznat.Imamo šahovsku ploču kojoj je uklonjeno polje A 1 te H 8.Imamo 31-nu domino pločicu od kojih svaka pokriva dva šahovska polja.Da li je moguće prekriti cjelu šahovsku ploču sa tim domino pločicama i zašto?

Edited November 1, 2007 by Anton

[CPP]

Ali si rešio teži. :)

Pazi kad je to sasma relativno; smorio sam se popisujuci taksativno sta se sve desava sa 12 kuglica, pogubio se u bespucima staakologije i poceo da gledam stvari iz pticje perspektive. Pre lucky insight nego nekakav dokaz.

[Al-Khwarizmi]

Kada smo već kod elegantnih rješenja evo jednog starog ali simpatičnog problema. Nadam se da ima netko ovdje kome nije poznat.Imamo šahovsku ploču kojoj je uklonjeno polje A 1 te H 8.Imamo 31-nu domino pločicu od kojih svaka pokriva dva šahovska polja.Da li je moguće prekriti cjelu šahovsku ploču sa tim domino pločicama i zašto?

Do malopre sam pokušavao da izvedem nešto sa brojem stranica, ali to se pokazalo kao ćorsokak.Kad sam (više iz očajanja nego što sam mislio da će pomoći) pogledao pravu šahovsku tablu, sve je bilo mnogo jasnije! :)Naime, uklonjena su polja iste boje (crne)! To znači da imamo više belih nego crnih polja. Svaka domina mora da pokriva dva susedna polja, t.j. jedno belo i jedno crno. To znači da moramo imati isti broj belih i crnih polja!Znači odgovor je - nije moguće! :) Edited November 1, 2007 by Al-Khwarizmi

[Al-Khwarizmi]

Varijacija na temu: ako se nasumice uklone bilo koja dva polja različite boje, mogu li se uvek sva preostala polja šahovske table prekriti 31 dominom?

[Anton]

Do malopre sam pokušavao da izvedem nešto sa brojem stranica, ali to se pokazalo kao ćorsokak.Kad sam (više iz očajanja nego što sam mislio da će pomoći) pogledao pravu šahovsku tablu, sve je bilo mnogo jasnije! :)Naime, uklonjena su polja iste boje (crne)! To znači da imamo više belih nego crnih polja. Svaka domina mora da pokriva dva susedna polja, t.j. jedno belo i jedno crno. To znači da moramo imati isti broj belih i crnih polja!Znači odgovor je - nije moguće! :)

Je li to elegantno rješenje or what? :) Nego, da li i tvoja varijacija ima elegantno rješenje?