Fórum: Valaki mondja meg!

Szerintem 13, de lehet, hogy elszámoltam.

Van két kitérő egyenesünk a térben:

Mekkora a két egyenes távolsága?

Kedves Jonas, köszönöm kedves válaszod, végre láttam egy egyszerűbb megoldást. Nekem ennél bonyolultabb jött ki. Bizonyára azért olyan népszerű, mert egyszerűen megfogalmazható, mégse egyszerű a megoldás.

Nem értem, ez a feladat mitől ilyen népszerű.

gugli(kecske kötél) = {Érdekes matekfeladatok[342], Valaki mondja meg![133], Érdekes matekfeladatok[1315], Érdekes matekfeladatok[1706] ...}

Kedves Mindenki! Van egy aranyos feladatom, amit szeretnék megosztani veletek.

Van egy r sugarú legelő, és az egyik széléhez ki van kötve egy kecske. A kötél hossza R. A kecske mindent lelegel, amit elér. Milyen hosszú a kötél, ha a kecske a legelőnek épp a felét legeli le?

Adjuk meg 10 jegy pontosan!

Én meg tudom csinálni n+1 lakattal is, bármi legyen is a k.

Rögzítsük a barlang egyik oldalához a kincsesládát, ezen legyen egy lakat. A lakat kulcsát rögzítsük egy hosszú láncra a barlang másik végéhez. A láncot n darab lakattal rövidebbre vesszük úgy, hogy minden rablóhoz pontosan egy lakatja van, és ehhez csak neki van kulcsa. Minden lakat két, egymástól d távolságra lévő láncszembe van beakasztva, és a lefogott d hosszú darabok nem fedik át egymást. A lánc hossza úgy van beállítva, hogy ha k lakatot kinyitnak, akkor már a végén lévő kulcs eléri a kincsesláda lakatját, de ha csak k-1-et nyitnak ki, akkor nem.

Még ennél is van jobb, ha nem egy szimplán leüthető lakatról van szó, hanem egy elektronikusról. Legyen N egy nagy pozitiv egész szám, a kulcs ami a széfet nyitja pedig egy random [N/2,N) intervallumba eső R egész. Az i-edik alkalmazott kulcsa az Rmod p_i szám, ahol és p_i prím (különbözőek). Bármely 4 összeáll, akkor ki tudják nyitni a zárat a kínai maradéktétel miatt (az elektronikus zár kiszámolja R-et a kínaiból), de bármely 3 még nem.

Az a feladat ide csak alsó becslést ad. A felső becslése csak arra az esetre vonatkozik, amikor minden zár közvetlenül az egy páncélszekrény ajtaján van.

Bizonyos n,k értékekre jobb konstrukciót lehet adni, ha használhatsz plusz ládákat. (Lehet, hogy az is segíthet, ha csak egy ládád van, de sorba köthetsz lakatokat esetleg láncot is használva, nem tudom.)

Mondok egy példa konstrukciót. Minden (t,v) számpárhoz, ahol 0twn egészek, vegyünk fel egy L(t,w) ládát, amibe majd néhány kulcsot rejtünk. Azt szeretnénk, hogy L(t,w)-t pontosan akkor lehessen kinyitni, ha együttműködik az R(0),R(1),...,R(w-1) rablók közül legalább t fő, meg még az R(w) rabló. Ezt az általános esetben úgy érjük el, hogy az L(t,w) ládán két lakat van, az elsőhöz csak az R(w) rablónak van kulcsa, a másikhoz viszont az L(t-1,t-1),L(t-1,t),...,L(t-1,w-1) ládák mindegyikébe rakunk egy kulcsot. Speciálisan azonban ha 0=t, akkor csak az első lakat legyen a ládán. Végük a kincset rakjuk egy külön ládába, és az ezen lévő egy lakathoz az L(k-1,k-1),L(k-1,k),...,L(k-1,n) ládába rejtsük.

Ezzel a megoldással elég összesen O(n²) láda, O(n²) lakat és O(n³) kulcs. Ez megfelelő n,k esetén olcsóbb lehet, mint a megoldásban leírt lakat.

(Arra vigyázni kell, hogy a ládák elég nehezek legyenek ahhoz, hogy ne lehessen ellopni őket. Vegyük viszont észre, hogy a megadott séma robosztus abban az értelemben, hogy k-nál kevesebb rabló nem tudja kulcsok ellopásával megakadályozni azt, hogy rablóknak másik, az előbbitől diszjunkt halmaza kinyithassa a ládát, így a kulcsokat nem szükséges a ládák belsejéhez láncolni.)

Ez KöMaL-feladat volt egy kicsit általánosabban. Gördíts le a B.3431-ig.

ez matek: Van 10 rabló, akik egy végtelen sok lakattal lezárható kincsesládát akarnak lelakatolni úgy, hogy semelyik 3 ne tudja kinyitni, de bármely 4 igen. Legalább hány lakat kell ehhez, ha egy rabló több kulcsot is kaphat? Légyszi segítsetek!!!