Fórum: Biliárdgolyók és más méricskélős feladatok

Ezt a cikket találtam:

http://www.sciencedirect.com/science/article/pii/0166218X9200120B

Ebben az van, hogy a feladat mindig megoldható az optimális vagy annál eggyel nagyobb lépésszámban, azaz \(\displaystyle \lceil{\log_2 \binom{n}{2}}\rceil\) vagy \(\displaystyle \lceil{\log_2 \binom{n}{2}}\rceil+1\) méréssel. Sőt, egy későbbi cikkben rövid algoritmust mitatnak arra, hogy eldöntsük melyik igaz: http://www.sciencedirect.com/science/article/pii/0020019095001394

https://www.youtube.com/watch?v=zd6TirAHsk4

13 Kugeln und eine Balkenwaage (Mathe-Song) (német)

> Következésképpen a legjobb stratégia az, hogy -et nagyjából megfelezzük.

Létezik olyan feladat, ahol a legjobb stratégiában az első mérés "rosszul" osztja ketté \(\displaystyle M\)-et, vagy, belátható hogy a kinyert információ mennyisége az tényleg \(\displaystyle M_{i+1}\) mérete?

Véleményem a méricskélős feladatokról: Régen rettenetesen utáltam őket, de most ránézve, tökéletesen értelmesek. Jól fejlesztik a megérzéseket, mert annyira sokféle lehetőség közül lehet választani. Azt viszont fiatalon nagyon kevesen látják, hogy mi a lényeg mögöttük.

A mérési feladatok mögötti kulcsintuíció: A mérendő dolgok milyenléteinek összes lehetséges halmazát, \(\displaystyle M\)-et akarjuk leszűkíteni. Tehát minden \(\displaystyle \mu\in M\) azt jelöli, hogy azt egyes golyók (súlyok, érmék, stb.) milyen nehezek (radioaktívak-e, stb.) Ennél a példánál \(\displaystyle M\)-et olyan \(\displaystyle M_\infty\) halmazra akarjuk leszűkíteni, hogy van olyan golyó, ami \(\displaystyle M_\infty\) minden eleménél radioaktív.

Egy kérdésre kapható \(\displaystyle 2\)-féle (\(\displaystyle k\)-féle) válasz \(\displaystyle 2\) (\(\displaystyle k\)) részre oszthatja \(\displaystyle M\)-et. Következésképpen a legjobb stratégia az, hogy \(\displaystyle M\)-et nagyjából megfelezzük. (Ez alól csak az kivétel, ha a létrejövő részek nehezen felezhetők tovább.)

—–

Ez a feladat húgom nyári szorgalmi feladata volt, így frissen emlékszem a megoldásra. Radioaktív rövidítése R.

Mi legyen az első lépés?-re intuíció: Az \(\displaystyle M\)-et talán akkor tudjuk az első mérésben hatékonyan kettéosztani, ha \(\displaystyle 3\), \(\displaystyle 4\) vagy \(\displaystyle 5\) golyót mérünk. Ha ugyanis \(\displaystyle x\) golyót mérünk, "igen" válaszból kicsi \(\displaystyle x\)-re kapunk sok információt, "nem" válaszból sokra. De ha \(\displaystyle x\approx \frac{12}2\) golyót mérünk, akkor egy "igen" válasz sokkal kevesebb információt ad, vagyis \(\displaystyle M\)-et ennél valamivel kisebb \(\displaystyle x\)-ekre tudjuk jól megfelezni.

Más kulcsötlet: Nézzük meg, mi történik, ha csak \(\displaystyle 1\) golyó R.

Ebből adódó gondolat: \(\displaystyle \le 2^k\) golyóból biztosan kiválasztható \(\displaystyle k\) darab méréssel egy R golyó (nem számít, hány radioaktív van összesen). [Biz.: felezgetés. Ha \(\displaystyle \le 2x\) golyó közül egyik biztos R, két \(\displaystyle \le x\) csoportra oszthatjuk; egyiket lemérve kapunk egy \(\displaystyle \le x\) golyóból álló csoportot, amiben biztos van R.]

A feladat megoldása:

Először mérjünk \(\displaystyle 4\) golyót.

Ha "nem" választ kapunk, a maradék \(\displaystyle 8=2^3\) golyóból \(\displaystyle 3\) méréssel kiválasztható az egyik, majd még \(\displaystyle 3\) méréssel a másik R golyó, kész.

Ha "igen" választ kapunk, \(\displaystyle 2\) méréssel megvan a \(\displaystyle 4=2^2\) golyó közül az első R golyó, és a maradék \(\displaystyle 11\le 2^4\) golyó közül \(\displaystyle 4\) méréssel megvan a másik R golyó, kész.

Sziasztok! Láttam, volt pár radioaktív golyós feladat, és megoldás nélkül maradtak. Namost, megoldással én sem szolgálhatok, de feltennék egy kicsit könnyebb kérdést: Van 12, külsőre egyforma golyó, ami közül 2 a radioaktív. 7 méréssel mindenképp meg lehet állapítani, hogy melyik kettő az. Hogy kell ezt bizonyítani? Nyilván lehet egymillió esetre bontani, de egyszerűbb megoldás kellene. Így hátha kicsit frissül a fórum is :)

Bye:Alex :DD

A rádióaktív golyókhoz: (2. feladat) Régen katonaság(1977) alatt volt időm, megoldottam, bonyolult fastruktúra lerajzolása után.(már nincs meg)

A kezdés nyilván 4 db vagy 5 db lehet csak. A 4 kezdés kecsegtetőbb, mert a két aleset száma közelebb van egymáshoz, mint 5 esetén. Mégis a 4 db kezdés nem vezet eredményre.

Később hallottam egy megoldást. az első 3 mérés: 1 közös, 4-4-4 különböző. (1,2,3,4,5);(1,6,7,8,9);(1,10,11,12,13); Innen már egyszerű. Találjátok ki!

Tehát az első 3 méréshez nem kell felhasználni az előzőek mérési eredményét. Kérdésem: van-e olyan megoldás, hogy előre megmondjuk mind a 7 mérést? (nyilván minden mérésben pont 5 db lesz, ha van megoldás) Valószínűleg nincs.

Ahol:

N - az érmék száma

n - a mérések szám

Ez biztosan nem igaz.

Alapvetően HoA felvetésére mutattam egy példát. Általános konstrukció leírása, szabatos megfogalmazása nehezebb, mint a kitalálása.

n mérés esetén 3ⁿ különböző eset fordulhat elő és minden érméhez rendelhetünk egy esetet, hisz az érmék száma egy kicsit kevesebb, mint az esetek fele.

Az első érme csak az első mérésnél szerepeljen és így az n-dikig, majd a következő érme az első két mérésen az egyik oldalon, míg újabb érme két egymás utáni mérésen ellentétes oldalon. Majd a következő két érme az első és harmadik mérésnél az egyik ill. mindkét oldalon, s ennek összes változata. Majd három ... n mérésnél is szerepeltetve az érme, folytatva a vázolt logikával. kn mérésben résztvevő érmék esetében eset lesz lefedve. Így összesen eset adódik, azaz a végén az a változat már nem kell, ahol minden mérésnél egy oldalon van az adott érme. Ügyes kiosztással megoldható, hogy minden mérésnél egyazon mennyiségű érme kerüljön mindkét oldalra.

Köszönöm. Nem néztem végig mind a 25 ( 2 * 12 + 1 ) esetet, de jónak látszik. Éredekes, hogy eddig ahol csak találkoztam vele, mindenhol esetszétválasztós megoldás szerepelt. De most megpróbálkozom az általános, vagy legalább a 120 golyó 5 mérés esettel :-)

Ez k=3-ra valóban megoldás, de hogyan lehetne más esetekre (pl. 120 golyó, 5 mérés) ilyeneket konstruálni?

Itt a kritériumnak megfelelő méréssorozat:

.

.

acfg|bdil

abeh|cdgk

efij|abch

Ennél nem létezik olyan lehetőség, hogy mind a három egy irányba billenjen ki.

Igen, gondolom ezt sokan ismerjük. Így aztán különösen kíváncsi vagyok arra az előre összeállított 3 mérésre, ahol a második mérés nem függ az első eredményétől, a harmadik meg az előző kettőétől.

A k=3 speciális eset a közismert 12 golyós feladat.

A. 512.' Van , látszólag egyforma pénzérménk, amik között legalább n-1 valóban egyforma. Lehetséges, hogy az egyik érme ,,hamis'', könnyebb vagy nehezebb a többinél.

Egy kétkarú mérleg segítségével szeretnénk meghatározni, hogy van-e az érmék között hamis, és melyik az.

Mutassuk meg, hogy k alkalmasan kiválasztott mérés elvégzésével biztosan eldönthetjük, hogy van-e hamis az érmék között, megtalálhatjuk a hamis érmét, azt is meg tudjuk határozni, hogy könnyebb avagy nehezebb. Sőt, lehetséges a mérések sorozatát előre összeállítani, az egyes mérések eredményének ismerete nélkül.

Nem abc-sorrend, a cs előbb lenne (eggyel), mint az s.

Érdekes, én azt hittem, hogy azért különbözik a szerzők sorrendje az egyes kiadásokon, mert ábécérendben vannak.

Köszönöm, hogy utánanéztél. Én mostanában nem könnyen jutok könyvtár közelébe.

Az orosz szövegben természetesen ott van, hogy hatosával. A fordító egyébként nem csak a feladatot nem értette, hanem a bizonyítást sem, mert a mindegyik súly páros esetet "osszuk el kettővel" helyett "osszuk fel két csoportra" fordulattal intézte. Valószínű, hogy a hatvanas évek "szúk levegője" miatt maradt ki a könyv előszavának fordításából az első szerző életrajzi adata, ezt most szeretném pótolni. D. O. Skljarszkij (1918-1942) huszonnégy évesen halt meg a világháborúban. A címlapon a szerzőtársak tiszteletéből került az ő neve az első helyre.

A feladatnak van megoldása, ezt most leírom: Mérjünk meg 3x4+1=13 golyót úgy, hogy a +1-es golyót mérjük hozzá a másik 4-4-hez (3 mérés összesen eddig). A mérési végeredmények a következők lehetnek:

0 esetben jelez a mérés Ekkor a 2 keresett golyó a nem mért 2 golyó, tehát összesen 3 mérés kell.

1 esetben jelez a mérés Ekkor mérjük meg a maradék 2 golyót (+1 mérés, összesen már 4). Ha az nem jelez, akkor a 2 kereset golyó a 4 között van (az 5., ami a másikakhoz is hozzá van mérve nem lehet az), ehhez 3 mérés elég, tehát összesen 7 mérés. Ha az is jelez, akkor a 4 között 1 van (2 mérés) és a 2 között is 1 van (1 mérés), összesen 7 mérés

2 esetben jelez a mérés Ekkor 1-1 golyó van a két 4-es között, tehát 2+2 mérés kell, azaz összesen 7 mérés.

3 esetben jelez a mérés Ekkor a +1-es biztosan az egyik keresett, a maradék 14-ből kell a másikat kiválasztani, ami 4 mérés, azaz összesen 7 mérés.

Könyvtárban megvan oroszul a katalógusok szerint.

Köszönöm! Ez az! Ezért emlékeztem ennyi év után a feladatra. A könyvben egyszerűen hibásan volt kitűzve. ( Adalék a mű dicséretéhez , ld: http://www.komal.hu/forum/forum.cgi?a=to&tid=7&st=25&dr=0&sp=24 ) . Nincs meg véletlenül valakinek oroszul? Kíváncsi lennék, a szerző vagy a fordító a ludas.

Csak olyan felezést szabad megengedni, amikor mind a két serpenyőbe ugyanannyi darab kerül.

Baráti körben előkerült egy régi feladat, úgy emlékeszem benne volt a "Válogatott feladatok és tételek az elemi matematikából" című "szovjetből" fordított könyvben. Emlékszik-e valaki a megoldásra, vagy tud egy újat? Tehát a feladat:

Van 13 darab tárgyunk, mindegyiknek a súlya egész dekagaramokkal fejezhető ki. Tudjuk, hogy bármelyik 12-t kiválasztva ezek elhelyezhetők egy kétkarú mérleg serpenyőibe úgy, hogy a mérleg egyensúlyban van. Bizonyítsuk be, hogy ez akkor és csak akkor lehetséges, ha minden tárgy azonos súlyú.

Sziasztok!

A 2. feladathoz szeretnek hozzaszolni. Szerintem nincs megoldasa, amit talan sikerult bizonyitani. A hatvanyozast **-al jelolom.

Ha 15-bol kivalasztunk k golyot (k=1..15), azokat lemerjuk es a meres pozitiv eredmenyt ad, akkor a ket sugarzo golyo

k(k-1)/2 + k(15-k)

fele keppen helyezkedhet el, hiszen biztosak lehetunk abban, hogy legalabb az egyik golyo a k-kupacban van (de lehet, hogy mindketto).

Mivel egy merest elhasznaltunk es 6 meressel legfeljebb 2**6 kombinaciot irhatunk le, ezert kikothetjuk, hogy

k(k-1)/2 + k(15-k) <= 2**6 = 64 (1)

Ebbol adodik, hogy k<=5.

Ha azonban a k golyonal a muszer nem jelez, akkor a maradek 15-k kozott kell lenni a ket sugarzo golyonak. Ez

(15-k)(14-k)/2

fele keppen valosulhat meg, amit ismet csak 6 meressel fedhetunk le, tehat

(15-k)(14-k)/2 <= 2**6 = 64 (2)

Ebbol az kovetkezik, hogy k>=4. osszesitve azt kaptuk, hogy k = 4..5

1. Tegyuk fel, hogy k = 5 es az elso 5-os csoportnal jelez a muszer.

Az 5-os csoportban lehet ket sugarzo golyo, amihez legalabb 4 meres kell (5*4/2 <= 2**j -bol kovetkezik, hogy j>=4). Egy merest mar elhasznaltunk, tehat a maradek 10 golyora legfeljebb 2 merest fordithatunk. 2**2=4 < 10, ezert 10 golyo kozul meg egyet sem tudunk 2 meressel kivalasztani. Lehetoseg van meg arra, hogy a maradek 10 golyot egyszerre lemerjuk, igy vizsgalva meg, hogy az elso 5-os csoportban egy vagy ket sugarzo golyo van-e. Ha azt kapjuk, hogy az 5-os csoportvan csak egy radioaktiv golyo van, akkor a ket golyo 5*10=50 fele keppen helyezkedhet el, amire nem eleg a maradek 5 meres (2**5=32 < 50).

2. Tegyuk fel, hogy k = 4 es az elso 4-es csoportban nem jelez a muszer.

A maradek 11 golyora csak 6 meres jut. Az (1)-hez hasonloan felirhatjuk:

k(k-1)/2 + k(11-k) <= 2**5 = 32

Ebbol az jon ki, hogy k<=3. A (2)-nek megfelelo egyenlotlenseg:

(11-k)(10-k)/2 <= 2**5 = 32

Ez azt koveteli meg, hogy k>=3. Vegul is azt kapjuk, hogy k = 3.

2.1. Tegyuk fel, hogy az elso harmas csoportban nincs radioaktiv golyo.

Marad 8 golyo es 5 meres.

Az (1) tipusu egyenlotlenseg:

k(k-1)/2 + k(8-k) <= 2**4 = 16

Megoldas: k<=2

A (2) tipusu egyenlotlenseg:

(8-k)(7-k)/2 <= 2**4 = 16

Megoldas: k>=2

A kettot osszevetve k = 2.

2.1.1. Tegyuk fel, hogy az elso ket elemu csoportban nincs radioaktiv golyo.

Marad 6 golyo es 4 meres.

A szokasos ket egyenlotlenseg:

k(k-1)/2 + k(6-k) <= 2**3 = 8 --> k<=1

(6-k)(5-k)/2 <= 2**3 = 8 --> k>=2

Latszik, hogy ezen az agon sem tudunk tovabb menni, tehat a feladatnak nincs megoldasa.