- actualizare
- Sarcini de cântărire
- Sarcinile de transfuzie
- concluzie
- literatură
Problemele matematice pentru transfuzie și cântărire sunt cunoscute încă din antichitate. Acum pot fi găsite în probleme de olimpiadă sau în jocuri pe calculator - puzzle-uri. Problema clasică a monedelor contrafăcute (FM) a găsit recent o aplicație în teoria codării și a informațiilor - pentru a detecta erorile din cod. Scopul lucrării noastre este de a găsi și descrie algoritmi pentru rezolvarea unor astfel de probleme. Sarcinile pentru transfuzie și cântărire sunt legate de tipul de probleme de căutare combinatorie; soluția lor este de a lucra cu informații.
În cursul cercetării, s-a dovedit că există multe părți diferite ale acestor sarcini. Prin urmare, am revizuit cele mai frecvente povești pentru fiecare specie.
Sarcini de cântărire.
Sarcinile care urmează să fie cantarite este tipul de sarcini pe care doriți să instalați un anumit fapt (monede falsificate, printre acestea, sortați setul de greutatea încărcăturii ascendente și așa mai departe. N.) Prin cântărire pe Bârnă fără cadran. Cele mai multe ori, monedele sunt folosite ca ponderi. Mai puține ori există, de asemenea, un set de cilindri cu masa cunoscută.
Foarte des se folosește formularea problemei, care necesită determinarea fie a numărului minim de cântăriri necesare pentru a stabili un anumit fapt, fie a algoritmului de determinare a acestui fapt pentru un anumit număr de cântăriri. Mai puțin obișnuită este formularea, care necesită răspunsul la întrebare, este posibil să se stabilească un anumit fapt pentru un anumit număr de cântăriri. Adesea, o astfel de afirmație nu este foarte reușită, deoarece, cu un răspuns pozitiv la întrebare, problema cel mai adesea coboară la construirea algoritmului, iar cea negativă este aproape niciodată găsită.
Căutarea unei soluții se realizează prin operații de comparație, nu numai de elemente unice, ci de grupuri de elemente între ele. Problemele de acest tip sunt rezolvate cel mai adesea prin metoda raționamentului.
După ce am studiat literatura de specialitate pe această temă, am ajuns la concluzia că toate sarcinile de cântărire pot fi împărțite în următoarele tipuri:
Sarcini de comparare prin intermediul greutăților.
Sarcini de cântărire pe cântare cu greutăți.
Sarcini de cântărire pe cântare fără greutăți.
Problema 1.1 Cel mai clasic puzzle.
Una dintre cele 9 monede este falsă, cântărește mai ușor decât cea reală. Cum se identifică o monedă contrafăcută (FM) pentru 2 cântăriri?
Soluția. Ideea cheie de rezolvare a unor astfel de probleme este triajul corect. adică divizarea succesivă a setului de variante în trei părți egale. După prima triază, nu mai rămân mai mult de trei monede suspecte, după prima triuză nu ar trebui să fie mai mult de un PM, care este FM.
Cântăim monedele 123 și 456. amânăm 789.
Dacă este mai ușor 123, atunci FM este printre ei; mai greu, apoi FM printre 456; sunt egale, apoi FM între 789.
Apoi, cântărește prima și a doua monedă din grămadă, unde există un FM. Dacă balanța este în echilibru, atunci a treia monedă este falsă. Dacă nu este în echilibru, atunci moneda FM se află pe acea ceașcă care este mai ușoară.
Ipoteză. Există algoritmi pentru determinarea FC în cel puțin suma de măsurători de greutate, în cazul, în cazul în care se știe că FM mai mare sau mai ușoare decât aceasta (algoritmul 1), iar în cazul în care nu se cunoaște (algoritmul 2).
Generalizare 1. Să presupunem că există monede K, iar una dintre ele este falsă (K este mai mare de două). Se știe că este mai ușor decât real. Care este cel mai mic număr de cântăriri pentru care se poate găsi FM?
1. ALGORITMUL suprapus pe vasul K 3 monede decaleze rămase (în cazul în care numărul de monede nu este un multiplu de 3, apoi pune același număr de monede egal cu (K-1) pe vasul de 3 sau (K + 1): 3, în funcție de faptul dacă , care este una naturală). Mai mult, dacă unul dintre boluri depășește greutatea, atunci FM pe celălalt castron și în caz de echilibru - FM între amânată. Apoi repetăm acest lucru pentru un grup de monede, dintre care FM.
FM în condiție poate fi mai greu decât în prezent, în acest caz și noi susținem că numai moneda FM va fi pe acel vas care a depășit.
Luați în considerare problema cu kettlebells, unde puteți aplica și această regulă.
Sarcina 1.2 Există 9 gabarituri cu o greutate de 100.200, ..., 900 grame. Unul dintre ei a vizitat mâinile negustorilor necinstiți și acum cântărește 10 gr. mai puțin. Cum se găsește pentru 2 cântărire?
Să găsim două triple diferite de greutăți, care au aceeași greutate. De exemplu, vom cântări 100 + 500 + 900 și
200 + 600 + 700 și va rămâne 300 + 400 + 800. Argumentând, de asemenea, vom găsi un grup cu greutăți rasfatate. Apoi puteți găsi greutățile rătăcite, adăugând cele reale. De exemplu, 200 + 600 și 700 + 100.
Următoarea sarcină este diferită prin faptul că nu se știe în prealabil dacă este mai ușor sau mai greu decât FM decât cel real.
Problema 1.3 Din cele trei monede, una este falsă și nu se știe dacă este mai ușoară sau mai greoaie decât cea reală. Cum să-l găsiți pentru două cântărire și să determinați dacă este mai ușor sau mai greu decât cel prezent?
În această problemă există 6 răspunsuri (fiecare dintre cele trei monede poate fi fie mai ușoară, fie mai greu decât cea reală).
Răspuns: da, este posibil, cu cel mai mic număr de cântăriri fiind egal cu 2.
Sarcina 1.4 Există 4 greutăți cu marcajele 1r, 2r, 3d, 4d. Unul dintre ele este defect - mai ușor sau mai greu. Este posibil să găsim această greutate în două cântăriri și să determinăm dacă este mai ușoară sau mai greoaie decât cea reală?
Sunt 8 răspunsuri aici. Să cântărim 1r + 2r și 3r, apoi 1r + 3r și 4g greutăți.
Obțineți următorul tabel de opțiuni:
Generalizarea 2. Să presupunem că există monede K, iar una dintre ele este falsă. Care este cel mai mic număr de cântăriri care poate fi determinat de FM și este mai ușor sau mai dificil?
Mai întâi trebuie să aflați numărul de răspunsuri. K * 2, deoarece fiecare monedă poate fi mai ușoară sau mai greoaie. Apoi determinați numărul de cântăriri. O cântărire determină trei opțiuni. =. Două cântărire determină 9 opțiuni. =. <>,> =, >>, == (există 3 * 3 dintre ele, dar în această problemă opțiunea == nu este posibilă). Trei cântărire determină 3 * 3 * 3 = 27 opțiuni etc.
ALGORITMUL 2. Împărțim monedele în trei grupe. Dacă K nu este divizibil cu 3, atunci fie (K-1) este divizibil cu 3, apoi se pune pe cântar pe (K-1): 3 monede rămân (K-1): 3 monede și 1 monedă. Sau (C-2) este divizibil cu 3, apoi se pune pe cântar pe (K-2): 3 monede rămân (K-2): 3 monede și 2 monede. Cântărirea primului și a celui de-al doilea grup, apoi a celui de-al doilea și al treilea, încheiem grupul în care se află FM-ul. În cazul în care soldul au fost în ambele cazuri, în echilibru, atunci FM în monede amânate și apoi, în funcție de numărul de monede amânate de una sau două de cântărire, vom găsi FM și mai ușoare sau mai grele decât prezent (comparându-le cu monede reale). Mai mult, dacă FM nu a apărut în monedele amânate, atunci putem deja determina dacă este mai ușor sau mai greu decât acesta. Apoi, acționăm conform algoritmului 1. Cuvintele grupurilor de monede 1, 2, 3 indică greutățile 1 și 2, apoi 1 și 3 din acest tabel.
Știind dacă FM-ul real este mai greu sau mai ușor, putem folosi algoritmul1 descris în generalizarea 1. După cum vedem aici, împărțirea în trei părți la fel de posibile.
Să verificăm algoritmul cu mai multe monede.
Sarcina 1.5 Există 80 de monede, dintre care unul este fals. Care este cel mai mic număr de cântăriri pe scale fără greutăți, puteți găsi o monedă contrafăcută?
Soluția. Ne petrecem prima cântărire: punem pe boluri (80-2): 3 = 26 de monede. În cazul echilibrului, FM se numără printre restul de 28; cântărind aceste 26 de monede cu 26 „suspecte“, vom determina FM mai ușor sau mai greu să prezinte (în cazul de echilibru, este în cei doi rămași și atunci trebuie să cântărească, de asemenea, 2). Dacă balanța nu se află în echilibru în timpul primei cântăriri, atunci soldul contrafăcut se află într-una din cântarele scalei. Comparați primul grup de monede cu cele din prezent din cea de-a treia și trageți o concluzie. Apoi împărțim acel grup de monede în care există un fals pentru 9, 9, 8, cântărește, apoi cântărește 3 monede și apoi - unul câte unul.
Răspuns: pentru 5 cântărire.
Algoritmul 1. Se cântăresc primele două grupe de monede (evidențiate în culori).
* În cea de-a doua cântărire găsim un grup de monede conținând FM. Dacă în 1 și 2 cântăriri soldul a fost în echilibru, atunci FM între restul sau doi. Dacă rămâne o monedă, atunci FM și cântărind-o cu prezentul, aflăm că este mai ușoară sau mai greoaie decât moneda adevărată. Dacă au rămas 2, apoi le cântărește între ele, iar apoi unul dintre ele cu cel prezent, răspundem la problema problemei. Dacă în primul sau al doilea caz soldul nu era în echilibru, este posibil să se determine grupul de monede cu conținut de FM și, de asemenea, să se concluzioneze dacă acesta este mai ușor sau mai greu decât o adevărată monedă.
- Dacă există 2 monede, atunci Problema 2 nu are nicio soluție.
- Dacă monedele sunt 3, atunci pentru a găsi printre ele o monedă contrafăcută, sunt necesare 2 cântăriri.
- Dacă monedele sunt de la 4 la 9 inclusiv, atunci cel mai mic număr de cântăriri pentru a găsi o monedă contrafăcută este de 3.
- În cazul în care monedele sunt de la 10 la 27 inclusiv, atunci este de 4.
- Dacă monedele sunt de la 28 la 81 inclusiv (datorită faptului că 81 = 3 * 27), atunci cel mai mic număr de cântăriri este egal cu 5.
Să însumăm sarcinile.
- Fie ca numărul de monede k să satisfacă inegalitatea
și între ei există un fals, despre care se știe dacă este mai ușor sau mai greu decât cele reale. Apoi, cel mai mic număr de cântăriri pe scale fără greutățile necesare pentru a găsi moneda contrafăcută este n. - Fie ca numărul de monede k să satisfacă inegalitatea
și între ei există un fals, despre care nu se știe dacă este mai ușor sau mai greu decât cele reale. Apoi, cel mai mic număr de cântăriri pe scale fără greutățile necesare pentru a găsi moneda contrafăcută este n.
Ipoteza a fost confirmată. Vom descrie algoritmi pentru determinarea FC în cel puțin suma de măsurători de greutate, în cazul, în cazul în care se știe că FM mai mare sau mai ușoare decât reală (algoritmul 1), iar în cazul în care nu se cunoaște (algoritmul 2).
Sarcinile de transfuzie.
Descriere: având mai multe vase cu un volum diferit, dintre care unul este umplut cu lichid, este necesar să-l împărțiți într-o oarecare măsură sau să-i turnați o parte din acesta cu ajutorul altor vase pentru cel mai mic număr de transfuzii.
În sarcinile de transfuzie, este necesar să se indice secvența acțiunilor la care se efectuează transfuzia necesară și sunt îndeplinite toate condițiile de sarcină. Dacă nu se spune altceva, se consideră acest lucru
- toate navele fără divizare,
- Nu puteți vărsa lichide "pe ochi"
- Este imposibil să adăugați lichide oriunde și nicăieri pentru a se scurge.
Putem spune cu siguranță cât lichid este în vas decât în următoarele cazuri:
- știm că nava este goală,
- știm că nava este plină, iar în sarcină este dată capacitatea sa,
- problema este dată de cantitatea de lichid din vas și transfuzii care utilizează acest vas nu au fost efectuate,
- Două vase de sânge au participat la transfuzie, fiecare dintre ele știe cât de mult lichid a fost și după transfuzie tot lichidul a fost plasat într-unul dintre ele,
- transfuzii implicate două nave, fiecare dintre care este bine cunoscut, așa cum a fost capacitatea de lichid cunoscută a navei, care este turnat, și este cunoscut faptul că tot lichidul în ea nu este potrivit pe care o putem găsi, așa cum rămâne într-un alt vas.
Metoda cea mai frecvent folosită pentru soluții verbale (adică descrierea fluxului de lucru) și o metodă de utilizare soluții tabele în care, în prima coloană (sau rând) indică cantitatea de recipiente, și în fiecare următor - rezultatul transfuzia regulate. Astfel, numărul de coloane (cu excepția primului) arată numărul de transfuzii necesare. Aceleași metode (verbale și tabele) au fost utilizate în rezolvarea problemelor de cântărire. Cu toate acestea, am găsit o altă modalitate interesantă de a rezolva astfel de probleme. Aceasta este o metodă de biliard matematic. Ya Perelman, în cartea sa "Diverse geometrie", a propus să rezolve problema transfuziei cu ajutorul unei "inteligente" bile. Pentru fiecare caz a fost propus să se construiască o masă de biliard cu un design deosebit, din triunghiuri echilaterale, lungimile a căror două laturi sunt numeric egale cu volumul a două vase mai mici. Mai mult, unghiul ascuțit al mesei de-a lungul uneia dintre laturile trebuie să „înceapă“ minge care prin lege „de incidență este egal cu unghiul de un unghi de reflexie“ se va confrunta cu laturile mesei, indicând astfel transfuzii de secvență. Pe marginea mesei există o scală, a cărei diviziune corespunde cu unitatea de volum aleasă. Ca urmare a mișcării, bila atinge marginea la punctul dorit (atunci problema are o soluție) sau nu lovește (atunci se consideră că problema nu are o soluție). Bilele de biliard se pot deplasa numai de-a lungul liniilor care formează o rețea pe o paralelogramă. După ce a lovit laturile mingea paralelogram reflectat și continuă să se miște de-a lungul plăcilor provenind din punctul în care a existat o coliziune, caracterizează complet cât de mult de apă este în fiecare dintre vasele.
O misiune veche de divertisment.
Se obțin 7 transfuzii. Cu toate acestea, dacă se toarnă mai întâi într-un vas de 5 pini, atunci vor fi necesare 18 transfuzii.
Sarcini de acest tip au întotdeauna soluții?
Metoda unei mingi de biliard poate fi aplicată la problema transfuzării unui lichid cu ajutorul a cel mult trei vase. În cazul în care volumul celor două nave mai mici nu au un divizor comun (m. E. Relativ prim) și volumul celui de al treilea vas este mai mare sau egală cu suma cantităților de două mai mici, cu ajutorul celor trei vase pot masura orice număr întreg l, începând cu 1 litru și se termină cu volum a vasului mijlociu. Cu, de exemplu, vase cu o capacitate de 15, 16 și 31 de litri, puteți măsura orice cantitate de apă de la 1 la 16 litri. O astfel de procedură este imposibilă dacă volumele celor două nave mai mici au un divizor comun. [10] Atunci când volumul unei nave mai mari este mai mic decât suma volumelor celorlalte două, apar noi restricții. Dacă, de exemplu, volumele vaselor sunt 7, 9 și 12 litri, atunci la masa rombică este necesar să se taie colțul din dreapta jos. Apoi, mingea poate ajunge în orice punct de la 1 la 9, cu excepția punctului 6. În ciuda faptului că 7 și 9 sunt relativ simple, măsurarea a 6 litri de apă este imposibilă deoarece cea mai mare navă are un volum prea mic. Este ușor de observat că punctele cu cifra 6 formează un triunghi regulat pe diagramă și nu putem ajunge la acest triunghi din nici un alt punct situat în afara acestuia. De asemenea, observăm că generalizarea metodei biliardului matematic la cazul a patru vase reduce la mișcarea unei sfere într-un domeniu spațial (paralelipiped). Dar dificultățile rezultate din imaginea traiectoriilor fac metoda incomodă.
Avantajul acestei metode elegante de biliard matematic este, în primul rând, vizibilitatea și atractivitatea acesteia.
Rezumând, putem spune că în cursul cercetării:
1. Au fost colectate materiale teoretice și practice privind problematica cercetării.
2. Ca rezultat al acestei lucrări, am sistematizat sarcinile de transfuzie și de cântărire.
3. Algoritmi de soluție sunt compilați.
4. Sa făcut o prezentare pentru a familiariza colegii de clasă cu aceste sarcini și a le ajuta să se pregătească pentru Jocurile Olimpice.
Astfel, se poate concluziona că munca noastră a fost fructuoasă, studenții s-au familiarizat cu căile și metodele de rezolvare a problemelor de cântărire și transfuzie. Am învățat cum să aplicăm corect cele mai bune modalități de a le rezolva. Conform feedbackului studenților, munca efectuată le-a permis să stăpânească metodele de rezolvare a problemelor de transfuzie, și-a lărgit orizonturile. Studenții au menționat posibilitatea și caracterul practic al utilizării metodei de biliard în rezolvarea acestui tip de problemă. Continuând acest studiu în viitor, puteți încerca în continuare să găsiți o formulă pentru calcularea celui mai mic număr de cântăriri (transfuzii).
Lista surselor utilizate
2. Galperin G.A. Miscarea periodica a mingii de biliard / Quantum. 1989. № 3.
3. FF Nagibin, ESKanin Caseta matematică M. Prosveshchenie, 1988
4. Ya. I. Perelman Dirijarea geometriei M. GIFML, 1959
11. Bayif JK. Sarcinile logice. M. Mir, 1983. 171 p.
12. Balk M.B. Balk G.D. Matematică după lecții. M. Education, 1971.
13. Barabanov A.I. Chernyavsky I.Ya. Sarcini și exerciții în matematică. Saratov: Universitatea din Saratov, 1965. 234 p.
14. Puzzle-urile lui Barr S. Placer. M. Mir, 1978. 414 p.
15. Berrondo M. Sarcinile de divertisment. M. Mir, 1983. 229 p.
16. Ball U. Coxeter G. Eseuri matematice și divertisment. M. Mir, 1986. 472 sec.
17. Perelman Ya.I. Dirijarea aritmetică.
18. Perelman Ya.I. Algebra interesantă.
19. Perelman Ya.I. Geometrie interesantă.
20. Perelman Ya.I. Matematică vie.
Semnături în diapozitive:
Soluția de sarcini pentru cântărire și transfuzie