Manual elektronik për matematikën diskrete. Forumi shkencor dxdy. Teorema mbi paritetin e numrit të kulmeve tek

Përshëndetje, unë po përdor këtë forum për të kontrolluar provën e mëposhtme. Në përgjithësi, ky problem është, por kam dëgjuar që nxënësit e shkollave e zgjidhin atë në olimpiadë.

Detyrë.
Ka 100 qytete në vend, disa palë qytete janë të lidhura me rrugë. Për çdo katër qytete ka të paktën dy rrugë ndërmjet tyre. Dihet se nuk ka asnjë rrugë që kalon në çdo qytet saktësisht një herë.
Vërtetoni se është e mundur të zgjidhen dy qytete në atë mënyrë që ndonjë nga qytetet e mbetura të lidhet me rrugë me të paktën një nga dy qytetet e zgjedhura.

Dëshmi.
Qytetet janë maja. Brinjët janë rrugë.

Le të zbulojmë nëse grafiku mund të shkëputet. Nëse komponenti është më i madh se 3, atëherë do të zgjedhim 2 kulme nga njëra, një nga tjetra dhe një tjetër nga e treta. Rezulton se ato mund të lidhen më së shumti nga një skaj. Është shkelur gjendja e problemit.
Le të ketë dy komponentë, secili i përbërë nga më shumë se një kulm. Atëherë të gjithë duhet të jenë plot. Nëse nuk është kështu, atëherë merrni dy kulme jo ngjitur nga e para dhe çdo dy nga tjetra. Vetëm dy qytete mund të lidhen në një grup të tillë. Kontradikta. E njëjta gjë vlen edhe për komponentin tjetër. Pra të dyja janë plot. Atëherë, merrni një kulm nga i pari dhe cilindo nga komponenti i dytë. Kushti i detyres eshte plotesuar.
Tani le të jetë një komponent vetëm një kulm i shkallës 0. Pastaj rezulton se komponenti tjetër do të përbëhet nga 99 kulme. Nëse heqim më shumë se dy skaje nga çdo kulm, atëherë kushti shkelet menjëherë: marrim një kulm të shkallës 0, një kulm pa dy skaje dhe kulme në të cilat nuk ka skaj prej saj (do të ketë 1 skaj). Kjo do të thotë se vetëm një skaj mund të hiqet nga çdo kulm. Por nëse e bëni këtë, atëherë çdo kulm do të ketë një shkallë tek (përpara se secili të kishte 98). Dhe mund të ketë vetëm një numër çift shkallësh tek, kështu që ose heqim diku dy skaje dhe shkelet kufizimi për 4 qytete, ose i lëmë të gjitha skajet dhe pastaj ka një kulm të plotë.

Qytetet nga të cilat ka rrugë për në të gjitha qytetet e tjera do t'i quajmë q dhe p.

Më pas, vërtetojmë me induksion se për çdo grafik të lidhur me kufizimin e 4 qyteteve dhe një shteg, kushti do të plotësohet.
Baza. nga 4 kulme është e dukshme: merrni çdo pemë që përfshin dhe zgjidhni një kulm në të që është i ndryshëm nga një gjethe, dhe e dyta është një gjethe.

Tranzicioni. Le të ketë një grafik kulmesh. Pastaj për të gjithë grafikët madhësi më të vogël, per te cilen jane te plotesuara kushtet e problemit, gjithcka eshte e vertetuar.

Është e nevojshme të vërtetohet se hipoteza e induksionit mund të përdoret.
Le të emërtojmë kulmin që do të hidhet si .
Nëse ka një grafik nga një kulm, ku për çdo 4 qytete duhet të ketë dy rrugë, atëherë kjo duhet të jetë e vërtetë edhe për qytetet: do t'i konsiderojmë të gjitha qytetet pa një. Gjëja kryesore është që grafiku të mos humbasë lidhjen, dhe kjo mund të bëhet gjithmonë duke hequr vetëm kulmin e varur, nëse ka një të tillë.

Nëse doli se ishte formuar një rrugë g., atëherë ajo nuk mund të lidhej me një nga skajet e saj (përndryshe shtegu g. në grafik). Pra, për fshirje, është një kulm i varur në pemën që përfshin. Nëse rezulton se kjo ende nuk është e mundur: ajo ishte e lidhur përmes një kulmi deri në fundin që u hoq, atëherë ne do të heqim tjetrin. Në të njëjtën kohë, nuk mund të ndodhte që një kulm të lidhet përmes një kulmi me të dy skajet: do të ishte një grafik në 3 kulme (dhe nëse ka një shteg të dytë deri në fund, atëherë ka një rrugë r. ), dhe kjo mund të vërtetohet për grafikë me më shumë se 4 kulme.
Natyrisht, duke hequr një kulm të varur në një pemë që përfshin, lidhja nuk humbet.

Tani është vërtetuar se nëse ka ndonjë grafik, dyfish. kusht, atëherë mund të zgjidhni një kulm, pas heqjes së të cilit do të fitohet një grafik më i vogël që plotëson kushtin fillestar. Kjo do të thotë që ne mund të përdorim hipotezën induktive.

Tani ka një grafik të kulmeve të lidhura, ky vend qytetesh ka p dhe q të vetin. Është e qartë se nëse ka një skaj nga p ose q, atëherë nuk ka nevojë të provohet asgjë. Atëherë le të mos ketë rrugë nga p dhe në q.
Bashkësia në të cilën ka rrugë nga p do të quhet A, dhe grupi në të cilin ka rrugë nga q do të quhet B.
Le të mos ketë rrugë nga p në q. Atëherë le të mos lidhet qyteti me qytetin me rrugë. Por atëherë duhet të ketë rrugë si në p ashtu edhe në q, përndryshe marrim kulmet , , p dhe q.
Pastaj rezulton se qyteti nuk mund të mos lidhet me rrugë me qytetet nga
Por atëherë ju mund ta bëni qytetin të ri p, dhe ta lini q të njëjtë (ose anasjelltas).

Kjo do të thotë se ka mbetur vetëm një rast: p dhe q lidhen me një rrugë.
Emrat e grupeve do t'i lëmë të njëjtë.
Sipas hipotezës së induksionit: grafiku nuk ka një shteg Hamiltonian.
Edhe një herë, nëse ka rrugë nga i gjithë grupi ose tek gjithçka, atëherë gjithçka tashmë është vërtetuar.

Tani ka një palë kulme dhe nga të cilat nuk ka skaje për të .
Nëse ka vetëm , atëherë mbulon gjithçka që q nuk mbulon, atëherë p. Pastaj - një qytet i ri i madh.
Nëse është bosh, atëherë lidhet dhe gjithçka vërtetohet.

Nëse nuk ka buzë midis dhe, atëherë marrim , dhe p - do të ketë një buzë. Pra ekziston. Tani rezulton se - një nëngraf i plotë, megjithatë, si dhe (përndryshe marrim ose, p ose q, sipas nevojës, dhe kulme të palidhura).
Tani konsideroni nëngrafin mbi kulmet nga . Le të përpiqemi të mbulojmë të gjithë grupin e kulmeve duke përdorur shtigje të thjeshta.
Le të jetë rezultati një mbulim i vetëm 4 shtigjeve të thjeshta. Le të marrim një kulm ekstrem nga secila: nëse ka një skaj, atëherë mund të lidhim dy kulme ekstreme dhe të marrim një shteg më të gjatë. Rezultati ishte një anti-klikë në katër maja. Kontradikta.
Tashmë dihet se kompleti mbulohet nga më së shumti 3 shtigje të thjeshta. Ne do ta konsiderojmë secilën të thjeshtë si një kulm: nëse mund të arrini në ndonjë nga skajet, atëherë mund të shkoni përgjatë çdo kulmi brenda saj një herë - është gjithashtu e thjeshtë, dhe kjo mund të bëhet, sepse çdo kulm nga mund të arrihet përmes p dhe q. Tani nuk ka vetëm më shumë se 3 kulme.
Një shteg mund të përbëhet nga një kulm ose më shumë. Nëse më shumë, atëherë ne e identifikojmë të gjithë shtegun me një kulm ekstrem.
Le ta quajmë grupin e majtë - , të djathtën - , mesin - (shtigjet janë të ngjeshura në kulme).
Mund të harroni kulmin: nëse rezulton se ekziston një rrugë r., atëherë tashmë do të ketë një kontradiktë me supozimin induktiv.
Rasti 1. Kompleti i mesëm është bosh. Pastaj ne thjesht (thjesht me kulme) shkojmë rreth grupit të majtë, duke filluar nga çdo kulm përveç , ne përfundojmë në , pastaj në p , pastaj menjëherë q , pastaj në dhe thjesht shkojmë rreth grupit të djathtë. Doli të ishte një shteg qyteti.
Rasti 2. Kompleti i mesëm ka një kulm. Gjithçka është e njëjtë, por nga p në q kalojmë nëpër këtë kulm.
Rasti 3. Tani ka kulme në grupin e mesëm

1. Tabela ka formën e një kryqi, i cili merret nëse qelizat e qosheve hiqen nga një tabelë katrore $4 \ herë 4 $. A është e mundur ta anashkaloni atë duke lëvizur një kalorës shahu dhe të ktheheni në sheshin origjinal, pasi të keni vizituar të gjitha sheshet saktësisht një herë?
2. Në vendin e Digit ka 9 qytete me emrat 1, 2, 3, 4, 5, 6, 7, 8, 9. Një udhëtar zbuloi se dy qytete lidhen me një linjë ajrore nëse dhe vetëm nëse numër dyshifror, i përbërë nga numrat-emrat e këtyre qyteteve, pjesëtohet me 3. A është e mundur të kalojmë nga qyteti 1 në qytetin 9?
3. Ka 15 telefona në qytetin e Malenky. A është e mundur t'i lidhni ato me tela në mënyrë që secili telefon të lidhet saktësisht me pesë të tjerë?
4. Ka 100 qytete në shtet, dhe secili prej tyre ka 4 rrugë. Sa rrugë ka në shtet?
5. Në klasë janë 30 veta. A mund të ndodhë që 9 prej tyre të kenë 3 shokë (në këtë klasë), 11 kanë 4 shokë dhe 10 kanë 5 shokë?
6. Ka 15 telefona në qytetin e Malenky. A ka mundësi t'i lidhim me tela që të jenë 4 telefona, secili me tre të tjerë, 8 telefona, secili me gjashtë dhe 3 telefona, secili me pesë të tjerë?
7. Mbreti ka 19 baronë vasalë. A mund të ndodhë që çdo baroni vasale të ketë 1, 5 ose 9 baroni fqinje?
8. A mundet një shtet në të cilin ka 3 rrugë që të çojnë nga çdo qytet të ketë saktësisht 100 rrugë?
9. John, pasi mbërriti nga Disneyland, tha se kishte 7 ishuj në liqenin e magjepsur, me 1, 3 ose 5 ura që çonin nga secila prej tyre. A është e vërtetë që të paktën një nga këto ura shkon domosdoshmërisht në bregun e liqenit?
10. Vërtetoni se numri i njerëzve që kanë jetuar ndonjëherë në Tokë dhe kanë bërë një numër teke shtrëngime duarsh është çift.
11. A është e mundur të vizatohen 9 segmente në një rrafsh në mënyrë që secili të presë saktësisht tre të tjera?
12. Ka 15 qytete në vendin e Shtatë, secili prej të cilëve është i lidhur me rrugë me të paktën 7 të tjerë. Vërtetoni se nga çdo qytet mund të arrini në ndonjë tjetër (ndoshta duke kaluar nëpër qytete të tjera).
13. Vërtetoni se një grafik me kulme $n$, secila prej të cilave ka shkallë të paktën $(n - 1)/2$, është i lidhur.
14. Në Mbretërinë e Largët, ekziston vetëm një lloj transporti - një qilim fluturues. Janë 21 linja qilimash që largohen nga kryeqyteti, një nga qyteti i Dalniy dhe 20 nga të gjitha qytetet e tjera. Provoni se është e mundur të fluturoni nga kryeqyteti në Dalniy (mundësisht me transferta).
15. Në vend, çdo qytet ka 100 rrugë, dhe nga çdo qytet mund të shkoni në çdo qytet tjetër. Njëra rrugë u mbyll për riparime. Provoni se tani mund të shkoni nga çdo qytet në çdo tjetër.
16. a) Jepet një copë teli 120 cm e gjatë.A është e mundur që, pa e thyer telin, të bëhet korniza e një kubi me buzë 10 cm?
    b) Sa është numri më i vogël i herëve që teli duhet të thyhet në mënyrë që të prodhohet ende korniza e kërkuar?
17. Vërtetoni se një graf në të cilin çdo dy kulme janë të lidhura saktësisht me një shteg të thjeshtë është një pemë.
18. Vërtetoni se çdo dy kulme në një pemë janë të lidhura saktësisht me një shteg të thjeshtë.
19. Vërtetoni se ka një kulm në pemë nga e cila del saktësisht një skaj (një kulm i tillë quhet kulm i varur).
20. Të gjitha kulmet në grafik kanë shkallën 3. Vërtetoni se ai përmban një cikël.
21. Vërtetoni se heqja e ndonjë skaji nga një pemë e kthen atë në një grafik të shkëputur.
22. Ka 101 qytete në vendin e Drevland, dhe disa prej tyre janë të lidhur me rrugë. Për më tepër, çdo dy qytete janë të lidhura pikërisht nga një rrugë. Sa rrugë ka në këtë vend?
23. Vërtetoni se një graf i lidhur, numri i skajeve të të cilit është një më pak se numri i kulmeve është një pemë.
24. Rrjeta e volejbollit ka formën e një drejtkëndëshi me përmasa 50 $ \ herë 600 $ qeliza. E cila numri më i madh A mund të priten fijet në mënyrë që rrjeta të mos bjerë në copa?
25. Në një vend të caktuar ka 30 qytete, secili i lidhur me secilin nga një rrugë. Cili është numri më i madh i rrugëve që mund të mbyllen për riparime në mënyrë që të jetë e mundur të udhëtohet nga çdo qytet në secilin?
26. Vërtetoni se në çdo grafik të lidhur mund të hiqni një kulm së bashku me të gjitha skajet që vijnë prej tij në mënyrë që të mbetet i lidhur.
27. Ka 100 qytete në vend, disa prej të cilave janë të lidhura me linja ajrore. Dihet që nga çdo qytet mund të fluturosh në çdo tjetër (mundësisht me transferta). Provoni se mund të vizitoni çdo qytet në jo më shumë se
    a) 198 fluturime;
    b) 196 fluturime.
28. Në vendin e Ozernaya ka 7 liqene të lidhur me njëri-tjetrin nga 10 kanale, dhe nga çdo liqen mund të notosh në ndonjë tjetër. Sa ishuj ka në këtë vend?
29. Shënuam 20 pika në katror dhe i lidhëm me segmente jo të kryqëzuara me njëra-tjetrën dhe me kulmet e katrorit në mënyrë që katrori të ndahej në trekëndësha. Sa trekëndësha keni marrë?
30. Një grafik që ka 5 kulme, secila prej të cilave është e lidhur nga një skaj me një tjetër, nuk është planar.
31. A është e mundur të ndërtohen tre shtëpi, të hapen tre puse dhe të lidhet çdo shtëpi me çdo pus me shtigje në mënyrë që shtigjet të mos kryqëzohen?
32. Vërtetoni se një graf me 10 kulme, secila e shkallës 5, nuk është planar.
33. Vërtetoni se një graf planar ka një kulm shkalla e të cilit nuk e kalon 5.
34. Çdo skaj i një grafiku të plotë me 11 kulme ngjyroset një nga dy ngjyrat: e kuqe ose blu. Vërtetoni se grafiku "i kuq" ose "blu" nuk është planar.
35. Heptkëndëshi ndahet në pesëkëndësha dhe gjashtëkëndësha konveks, dhe në atë mënyrë që secila kulme e tij të jetë një kulm në të paktën dy poligone ndarëse. Vërtetoni se numri i pesëkëndëshave në ndarje është të paktën 13.

2. Zgjidh problemin e mëposhtëm të kalimit të grafikut:

Një vend i caktuar ka një kryeqytet dhe 100 qytete të tjera. Disa qytete (përfshirë kryeqytetin) lidhen me rrugë njëkahëshe. Çdo qytet jo-kryeqytet ka 20 rrugë, dhe çdo qytet i tillë ka 21 rrugë. Provoni se është e pamundur të shkosh në kryeqytet nga çdo qytet.

Le të hyjë një rrugë në kryeqytet. Pastaj numri total rrugët "hyrëse" janë të barabarta me 21 100 +a, dhe numri i përgjithshëm i rrugëve "dalëse" nuk është më

20 100 + (100-a ). Prandaj, 21 100 + a 20 100 + (100 - a), domethënë 2a 0.

Kështu a = 0.

3.3.2.1. Digrafi G1 (V,E): V=(a, b, c, d, e, f), përkufizohet si sistem algjebrik.

a) Për relacionin e dhënë, përcakto digrafin gjeometrikisht. b) Ndërtoni matricën e fqinjësisë së digrafit.

0) R = ((a, b), (b, a), (b, c), (c, b), (c, a), (a, c), (d, e), (e, d) );

1) R = ((a, b), (b, a), (b, c), (c, b), (c, d), (d, c), (c, a), (a, c) );

2) R = ((a, b), (b, a), (b, c), (c, b), (c, d), (d, c), (d, e), (e, d) );

3) R = ((a, b), (b, c), (a, c), (b, e), (c, f), (c, d), (d, f), (f, e) );

4) R = ((b, c), (a, d), (b, a), (d, c), (b, d), (c, a), (f, d), (f ,c) );

5) R = ((b, a), (a, a), (b, c), (c, d), (d, c), (d, b), (d, a), (d, e) );

6) R = ((a, b), (a, c), (a, d), (c, a), (d, e), (e, d), (c, c), (d, b) );

7) R=((b, a), (c, c), (a, d), (c, a), (d, e), (e, c), (d, b), (e, f) );

8) R = ((a, b), (a, c), (a, d), (e, a), (d, e), (e, d), (c, b), (d, d) );

9) R = ((a, e), (a, a), (a, d), (c, a), (d, e), (d, d), (c, c), (b, d) ).

3.3.2.2. Digrafi është përcaktuar gjeometrikisht. Specifikoni valencën e kulmeve.

8) 1

3.3.2.3. Është dhënë matrica e fqinjësisë së digrafit. a) Përcaktoni digrafin gjeometrikisht, c) ndërtoni një matricë incidence.

        

001100

001000

3.3.2.4. Është dhënë matrica e incidencës së digrafit. a) Përcaktoni digrafin gjeometrikisht, c) ndërtoni një matricë fqinjësie.

3.3.2.5. Zgjidh problemet e mëposhtme të kalimit të grafikut:

0) Dima, pasi mbërriti nga Vrunland, tha se atje ka disa liqene, të lidhur me lumenj. Nga çdo liqen rrjedhin tre lumenj dhe në secilin liqen rrjedhin katër lumenj. Vërtetoni se e ka gabim.

1) Në një shtet të caktuar, çdo qytet është i lidhur me çdo rrugë. Mbreti i çmendur dëshiron të prezantojë trafikun e njëanshëm në rrugë, në mënyrë që sapo të largoheni nga një qytet, të mos ktheheni në të. A është e mundur të bëhet kjo?

2) Thuhet se në një shoqëri me pesë persona, secili njeh dy të tjerë. A është e mundur një kompani e tillë?

3) Një shtet ka 101 qytete. Të gjitha qytetet janë të lidhura me rrugë njëkahëshe, me 50 rrugë që hyjnë në çdo qytet dhe 50 rrugë që dalin nga çdo qytet. Vërtetoni se mund të shkoni nga çdo qytet në çdo tjetër duke vozitur përgjatë jo më shumë se dy rrugëve.

4) Janë 6 pika të dhëna në një plan të tillë që asnjë tre prej tyre nuk shtrihet në të njëjtën vijë të drejtë. Çdo palë pika është e lidhur me një vijë blu ose të kuqe. Vërtetoni se midis pikave të dhëna mund të zgjidhni tre të tilla që të gjitha anët e trekëndëshit të formuar prej tyre të lyhen me të njëjtën ngjyrë.

5) Një shtet ka 101 qytete. Disa qytete janë të lidhura me rrugë njëkahëshe, me 40 rrugë që hyjnë në çdo qytet dhe 40 rrugë dalin nga çdo qytet. Provoni se mund të shkoni nga çdo qytet në çdo tjetër duke vozitur përgjatë jo më shumë se tre rrugëve.

6) A është e mundur të krijohen 10 linja autobusësh në një qytet dhe të vendosen ndalesa në to në mënyrë që pavarësisht se cilat 8 linja të merren, të ketë një ndalesë që nuk shtrihet në asnjë prej tyre dhe çdo 9 rrugë të kalojë nëpër të gjitha ndalesat.

7) Një brumbull zvarritet përgjatë skajeve të një kubi. A do të jetë në gjendje të përshkojë të gjitha skajet në mënyrë sekuenciale, duke kaluar secilën skaj saktësisht një herë? Këshillë: Mendoni për pyetjen: sa herë mund të vizitojë një brumbull çdo kulm?

8) Artisti pikturoi një fotografi "Skica e një sheshi dhe diagonalet e tij". A mund ta vizatonte fotografinë e tij pa hequr lapsin nga letra ose pa vizatuar dy herë të njëjtën vijë? Udhëzim: Një numër çift rreshtash duhet të dalin nga çdo pikë, me përjashtim të fillimit dhe fundit të shtegut të lapsit.

9) Arkady, Boris. Vladimir, Grigory dhe Dmitry shtrënguan duart kur u takuan (secili shtrëngoi duart me njëri-tjetrin një herë). Sa shtrëngime duarsh janë bërë?

3.3.2.6. Zgjidh problemet e mëposhtme të kalimit të grafikut:

0) Metro Uryupinsk përbëhet nga tre linja dhe ka të paktën dy stacione terminale dhe të paktën dy nyje transferimi, dhe asnjë nga stacionet e terminalit nuk është stacion transferimi. Mund të ndryshoni nga çdo rresht në secilën prej të paktën dy vendeve. Vizatoni një shembull të një diagrami të tillë të metrosë, nëse e dini se kjo mund të bëhet pa hequr lapsin nga letra dhe pa vizatuar dy herë të njëjtin segment. Shënim: Mos harroni se ka vija unazash.

3) Tabela ka formën e një kryqi, i cili fitohet duke hequr kuadratet e qosheve nga një dërrasë katrore 4 × 4. A është e mundur ta anashkaloni atë duke lëvizur një kalorës shahu dhe të ktheheni në sheshin origjinal, pasi të keni vizituar të gjitha sheshet saktësisht një herë?

4) Një këmbësor eci rreth gjashtë rrugëve të një qyteti, duke ecur në secilën prej tyre saktësisht dy herë, por nuk mundi t'i rrethonte, duke ecur nëpër secilën vetëm një herë. A mund të jetë kjo?

5) Ka një brumbull të ulur në qendër të kubit 3 3 3. Vërtetoni se, duke u zvarritur mbi skajet, ai nuk mund t'i rrotullojë të gjithë kubet 1 1 1 një herë.

6) Në një katror 6x6, shënohen disa qeliza në mënyrë që nga çdo e shënuar mund të shkoni në ndonjë tjetër të shënuar, duke kaluar vetëm nëpër anët e përbashkëta të qelizave të shënuara. Një qelizë e shënuar quhet qelizë fundore nëse kufizohet në anën e një qelize të shënuar. Shënoni disa qeliza në mënyrë që të merrni a) 10, b) 11, c) 12 qeliza.

7) Një mizë ulet në një nga kulmet e a) një tetëedri b) një kubi. A mundet ajo të zvarritet përgjatë të gjitha brinjëve të tij saktësisht një herë dhe të kthehet në

kulm origjinal? (Shënim: Një oktaedron është dy piramida katërkëndëshe të ngjitura së bashku në bazat.)

8) Si, pa e hequr lapsin nga letra, të vizatohen gjashtë segmente në atë mënyrë që të kryqëzohen 16 pika të vendosura në kulmet e një rrjeti katror 4 me 4?

9) A është e mundur të vizatoni një diagonale në çdo katror në sipërfaqen e kubit të Rubikut në mënyrë që të fitohet një shteg që nuk kryqëzohet vetë? Shënim: Ka vetëm 54 katrorë në sipërfaqen e një kubi Rubik.

3.4. Problemet e optimizimit në grafikë

Nëse një hark i një grafi të drejtuar G 1 (V ,E) shoqërohet me një numër real a (u ,v ), i quajtur peshë, atëherë sekuenca e kulmeve v 0 ,v 1 ,...,v p përcakton një shteg. në G 1 dhe gjatësia e tij

përkufizohet si shuma e peshave:

Nëse në ndonjë

Në grafik, pesha e çdo harku është e barabartë me një, atëherë gjatësia e shtegut është e barabartë me numrin e harqeve. Problemi i rrugës më të shkurtër më së shpeshti lind kur zgjidhet

transporti dhe problemet diskrete programim dinamik etj Gjatësia rruga më e shkurtër shënojmë r (v i,v j) dhe quhen distancë nga v i në v j (distanca mund të jetë negative). Për çdo digraf mund të ndërtohet matrica e distancës R=r(i, j). Matrica plotësohet rresht pas rreshti, duke zgjedhur kulmin në të majtë (djathtas). Vlera është numri më i vogël i harqeve që lidhin kulmin në të majtë me një nga kulmet në rresht.

Nëse nuk ka rrugë nga v i në v j , atëherë vendosim r (v i ,v j ) = . Nëse çdo kontur i grafikut tonë ka një gjatësi pozitive, atëherë shtegu më i shkurtër do të jetë gjithmonë një shteg elementar, d.m.th. nuk do të ketë përsëritje në sekuencën v 1 ,...,v f.

Devijimi mesatar i kulmit vi nga qendra e grafikut D(vi) është i barabartë me:

D(vi)1 r(vi, v),

m v V

ku m është numri i harqeve në grafik, v kalon nëpër kulmet e grafikut, n është numri i kulmeve në grafik, i = 1..n.

Maja për të cilën D(vi ) rezulton të jetë minimale quhet qendra e grafikut (janë të mundshme disa kulme - qendra e grafikut).

Me rrugë ose rrugë në një grafik G1 (V,E) është sekuenca e kulmeve dhe skajeve të tij v1e1v2e2v3…vnen vn+1, në të cilën

çdo dy elemente ngjitur janë incidente. Një shteg quhet i thjeshtë nëse argjendi dhe të gjitha kulmet në të, përveç të parës dhe të fundit, janë të ndryshme.

Një rrugë quhet zinxhir nëse të gjitha skajet e saj janë të dallueshme. Një rrugë quhet një zinxhir i thjeshtë nëse të gjitha kulmet e saj, dhe për rrjedhojë skajet e saj, janë të ndryshme.

Një cikël në një grafik është një shteg në të cilin kulmi fillestar përkon me kulmin përfundimtar dhe që përmban të paktën një skaj.

Një cikël quhet i thjeshtë nëse nuk ka kulme identike përveç të parës dhe të fundit, d.m.th. nëse kulmet janë të ndryshme.

Nëse një grafik nuk ka cikle, atëherë ai quhet aciklik.

Tani mund ta përkufizojmë ndryshe konceptin e një peme. Një graf i lidhur pa cikle quhet pemë.

Shembuj të përfundimit të detyrave

D(2)=D(3)=6/8=3/4;

Pra, qendra e grafikut është kulmet 2 dhe 3.

2. Fshati eshte ndertuar ne formen e nje sheshi 3 blloqe me 3 blloqe (blloqet jane katrore me anen b 9 blloqe gjithsej) Cila eshte distanca me e shkurter qe duhet te kaloje asfaltuesi per te shtruar te gjitha rruget nese nis dhe përfundon rrugën e saj në pikën e këndit A? (Anët e sheshit janë edhe rrugë).

Oriz. 6. Rruga më e shkurtër

Është e qartë se gjatësia e rrugës së shtrimit të asfaltit është të paktën 24, pasi ajo duhet të kalojë përgjatë çdo rruge të paktën një herë. Le të vërtetojmë se ai do të duhet të ecë përgjatë të paktën katër rrugëve dy herë. Një numër tek i rrugëve kryqëzohen saktësisht në tetë kryqëzime.

Prandaj, çdo rrugë rrethore e asfaltimit duhet të udhëtojë dy herë në të paktën 8/2 = 4 rrugë.Gjatesia minimale e një traseje shtrimi është 28; Një nga rrugët e mundshme është paraqitur në Figurën 6.

3. Përcaktoni grafikun gjeometrikisht dhe zgjidhni problemin:

Duke vrapuar në oborr pas shkollës, secili student hodhi një top bore pikërisht ndaj një studenti tjetër. Vërtetoni se të gjithë nxënësit mund të ndahen në tre ekipe në mënyrë që anëtarët e një ekipi të mos i hedhin topa bore njëri-tjetrit.

Le t'i shënojmë me pika nxënësit e shkollës në aeroplan dhe t'i lidhim me një shigjetë nëse njëri i hedh tjetrin. Fotografia që rezulton do të duket si disa cikle me "brirë" (shtigje që çojnë nga një pikë në një cikël). Çdo figurë e tillë mund të ndahet lehtësisht në tre grupe: duke thyer ciklin, vendosim një student në grupin e parë dhe pemët që rezultojnë ndahen në kulme çift dhe tek.

Detyrat për përfundimin e pavarur

3.4.1. Shkruani: 1) çdo shteg që nuk është zinxhir; 2) zinxhir dhe zinxhir i thjeshtë; 3) lak, lak i thjeshtë, nëse ka.

3.4.2. Digrafi është përcaktuar gjeometrikisht. Ndërtoni një matricë të distancës. Llogaritni qendrën e digrafit.

GRAFET EULER.

Vërtetoni se një grup i plotë domino mund të vendoset sipas rregullave të domino-s.

"Lema për vallet e rrumbullakëta". Në disa shoqëri, çdo person ka saktësisht dy miq. Provoni se nëse të gjithë miqtë bashkojnë duart, ata do të formojnë një ose më shumë valle të rrumbullakëta.

Ka më shumë se 101 qytete në vend. Kryeqyteti është i lidhur me linja ajrore me 100 qytete, dhe çdo qytet përveç kryeqytetit është i lidhur me saktësisht dhjetë qytete (linja ajrore operon në të dy drejtimet). Dihet që nga çdo qytet mund të shkosh në ndonjë tjetër (ndoshta me transferta). Vërtetoni se është e mundur të mbyllni gjysmën e linjave ajrore që vijnë nga kryeqyteti, në mënyrë që aftësia për të shkuar nga çdo qytet në çdo të mbetet.

Vërtetoni se një grafik i lidhur me 2n kulme teke mund të vizatohet duke hequr lapsin nga letra saktësisht n–1 herë dhe pa vizatuar asnjë skaj dy herë.

Në vend, 3 hekurudha nisen nga çdo qytet. Dy kompani duan t'i privatizojnë të gjitha. Komiteti Antimonopol kërkon që rrugët e të dyja kompanive të dalin nga çdo qytet. Vërtetoni se kompanitë mund të bien dakord ndërmjet tyre në mënyrë që kërkesa e Komitetit Antimonopoly të përmbushet.

Jepet një graf i lidhur G me k tehe. Vërtetoni se është e mundur të numërohen skajet me të gjithë numrat 1, 2, ..., k në mënyrë që për çdo kulm të shkallës së paku dy, grupi i numrave që shënojnë skajet nga kjo kulm të ketë një gcd të barabartë me 1. .

Në një turne futbolli të zhvilluar mes 20 skuadrave nga qytete të ndryshme, çdo ekip luajti një ndeshje në shtëpi dhe jo më shumë se dy ndeshje jashtë. Vërtetoni se ishte e mundur të planifikoheshin lojëra në mënyrë që çdo ekip të luante jo më shumë se një lojë në ditë dhe i gjithë turneu do të luhej në tre ditë.

NUMRI HAMILTON.

Në sipërfaqen e kubit vizatohet një vijë e mbyllur e thyer me tetë lidhje, kulmet e së cilës përkojnë me të gjitha kulmet e kubit. Cili është numri më i vogël i lidhjeve të kësaj linje të thyer që mund të përkojë me skajet e kubit?

Një kub është bërë nga tetë kube të vegjël. A është e mundur, duke filluar nga qendra e një kubi të madh dhe duke lëvizur përgjatë skajeve të kubeve të vegjël, të kalojmë rreth të gjitha kulmet e kubeve të vogla, duke e vizituar secilin saktësisht një herë?

Jepet një tabelë 55. A mundet një kalorës të shkojë nëpër të gjitha sheshet, duke vizituar çdo shesh një herë dhe të kthehet në pozicionin e tij fillestar?

A është e mundur të lëvizësh një mbret të çalë (një mbret nuk mund të lëvizë përgjatë diagonaleve) të gjitha katrorët e një tabele shahu, duke filluar nga këndi i poshtëm i majtë dhe duke përfunduar në këndin e sipërm të djathtë?

A mundet një kalorës të bëjë 8 lëvizje dhe të kthehet në katrorin e tij origjinal, pasi ka vizituar të gjitha linjat horizontale dhe vertikale të tabelës së shahut?

A). Në dy katrorë të tabelës së shahut vendosen patate të skuqura bardh e zi. Ju lejohet t'i lëvizni ato me radhë, çdo lëvizje duke lëvizur çipin tjetër në çdo fushë të lirë ngjitur vertikalisht ose horizontalisht. Si rezultat i lëvizjeve të tilla, a mund të ndodhin të gjitha pozicionet e mundshme të këtyre dy çipave në tabelë dhe pikërisht një herë? b). Po sikur t'ju lejohet të lëvizni çipat në çfarëdo radhe (jo domosdoshmërisht një nga një)?

Cili nga tre faktet e mëposhtme është më "i fortë"?

Në disa shtete, çdo 2 qytete lidhen me një rrugë. Çdo rrugë lejohet të lëvizë vetëm në një drejtim. Provoni se ekziston një qytet nga i cili mund të udhëtoni nëpër të gjithë shtetin, duke vizituar çdo qytet saktësisht një herë.

Në një vend të caktuar, çdo qytet është i lidhur me çdo qytet me një rrugë njëkahëshe. Provoni se ekziston një qytet nga i cili mund të shkoni në ndonjë tjetër.

Në një shtet të caktuar ka 100 qytete dhe secili është i lidhur me secilin nga një rrugë me një drejtim. Provoni se është e mundur të ndryshoni drejtimin e udhëtimit në një rrugë, në mënyrë që të mund të shkoni nga çdo qytet në një tjetër.

Provoni faktin "më të fortë" dhe të dyja pasojat prej tij.

Në një turne shahu me një raund, secili pjesëmarrës luajti një lojë kundër njëri-tjetrit. Vërtetoni se pjesëmarrësit mund të numërohen në atë mënyrë që asnjëri prej tyre të mos humbasë nga ai që ndodhet menjëherë pranë tij sipas numrit.

Ka N qytete në vend. Midis çdo dy prej tyre ka ose një rrugë ose Hekurudha. Një turist dëshiron të udhëtojë nëpër vend, duke vizituar çdo qytet saktësisht një herë dhe të kthehet në qytetin nga i cili filloi udhëtimin. Vërtetoni se një turist mund të zgjedhë qytetin nga i cili do të fillojë udhëtimin dhe itinerarin, në mënyrë që t'i duhet të ndryshojë mënyrën e transportit jo më shumë se një herë. (Olimpiada Gjith-Ruse, 2003)

Një sekuencë prej 36 zero dhe njësh fillon me 5 zero. Mes pesësheve me radhë gjenden të 32 kombinimet e mundshme. Gjeni pesë shifrat e fundit të sekuencës.

"Kalorësit në oborrin e mbretit Artur" - teorema e Dirakut. 2n kalorës u mblodhën në tryezën e rrumbullakët të Mbretit Artur, secili prej të cilëve nuk ka më shumë se (n–1) armiq mes të tjerëve. Provoni që këshilltari i mbretit Merlin mund t'i ulë kalorësit në mënyrë të tillë që armiqtë të mos ulen afër. Gjeni teoremën e Dirakut në formë të përgjithshme.

Në konferencë erdhën 2n persona, secili prej të cilëve njeh të paktën n të tjerë. Provoni se pjesëmarrësit mund të akomodohen në dhoma dyshe, në mënyrë që njerëzit që e njohin njëri-tjetrin të jetojnë në secilën dhomë.

Jepen n patate të skuqura me disa ngjyra, me jo më shumë se n/2 patate të skuqura për secilën ngjyrë. Vërtetoni se ato mund të vendosen në një rreth në mënyrë që të mos qëndrojnë pranë njëra-tjetrës dy pjesë të së njëjtës ngjyrë.

NË shteti federal, i përbërë nga dy republika, secila dy qytete lidhen me një rrugë njëkahëshe; Në të njëjtën kohë, duke lëvizur përgjatë rrugëve, mund të shkoni nga çdo qytet në çdo tjetër. Agjenci turistike“Hamilton” ofron n të ndryshme rrugët turistike sipas qytetit të republikës së parë dhe m– sipas qytetit, e dyta (secila nga këto rrugë përfshin vizitën e secilit qytet të republikës saktësisht një herë dhe kthimin në qytetin origjinal, dhe e gjithë kjo pa u larguar nga republika). Provoni se agjencia Hamilton mund të ofronte jo më pak se mn rrugë të ngjashme turistike në qytete në të gjithë federatën.

Turne - grafikët e plotë.

Në klasë janë 28 nxënës. Mësuesi mund të ndryshojë nxënësit, por secili nxënës brenda dite shkolle ulet me të njëjtin student. Në cilin numër minimal ditësh do të mund të ulet secili student me njëri-tjetrin?

Shuma e 1000 numrave realë është 0. Vërtetoni se të paktën 999 shuma dyshe të këtyre numrave janë jonegative.

Ka 25 gurë në një grumbull. Ndahet në dy pjesë, pastaj njëra pjesë ndahet përsëri në dy etj., derisa të fitohen 25 gurë të shtrirë veçmas. Sa herë që një nga pirgjet ndahet në dy pjesë, prodhimi i numrave të gurëve në këto pjesë shkruhet në tabelë. Vërtetoni se në fund shuma e të gjithë numrave në tabelë do të jetë e barabartë me 300.

Në shkollë studiojnë 1996 fëmijë. Secilit prej tyre i pëlqen saktësisht k nga 1995 studentë të mbetur. Në çfarë vlerash k a mund të themi se do të ketë patjetër dy nxënës nga kjo shkollë që ose të dy pëlqejnë njëri-tjetrin ose të dy nuk e pëlqejnë njëri-tjetrin?

Një astronom vëzhgon 50 yje, shuma e distancave në çift midis tyre është e barabartë me S. Një re doli dhe errësoi 25 yje. Vërtetoni se shuma e distancave në çift midis yjeve të dukshëm është më e vogël se S/2.

Në një vend me 25 qytete, tre linja ajrore duan që për çdo çift qytetesh, të gjitha fluturimet pa ndalesë ndërmjet atyre qyteteve duhet të operohen nga vetëm një prej linjave ajrore, por çdo linjë ajrore mund të fluturojë pasagjerë nga çdo qytet në çdo qytet tjetër me një ndalesë në asnjë qytet. më shumë se një qytet i ndërmjetëm. Provoni se është e realizueshme.

Komisioni përbëhet nga 49 persona. Në çdo mbledhje marrin pjesë saktësisht tre anëtarë të komisionit. A është e mundur të planifikohet puna e një komisioni në mënyrë që çdo dy anëtarë të komisionit të takohen në mbledhje saktësisht një herë?

LIDHJE MINIMUM.

Në qytetin N, mund të udhëtoni nga çdo stacion metroje në ndonjë tjetër (ndoshta me transferta). Vërtetoni se një nga stacionet e metrosë mund të mbyllet për riparime pa të drejtë udhëtimi përmes tij, në mënyrë që nga ndonjë nga stacionet e mbetura të jetë e mundur të udhëtoni në ndonjë tjetër.

Vërtetoni se në çdo grafik të lidhur mund të hiqni një kulm së bashku me të gjitha skajet që vijnë prej tij në mënyrë që të mbetet i lidhur.

Në një grup prej disa personash, disa njerëz e njohin njëri-tjetrin dhe disa jo. Çdo mbrëmje njëri prej tyre organizon një darkë për të gjithë miqtë e tij dhe i prezanton ata me njëri-tjetrin. Pasi secili person kishte shtruar të paktën një darkë, rezultoi se rreth dy persona ende nuk e njihnin njëri-tjetrin. Provoni se ata nuk do të mund të takohen me njëri-tjetrin as në darkën tjetër.

Në një vend të caktuar ka 30 qytete dhe secili qytet është i lidhur me secilin me rrugë. Cili është numri më i madh i rrugëve që mund të mbyllen për riparime në mënyrë që të mund të udhëtohet nga çdo qytet në secilin, ndoshta duke kaluar nëpër qytete të tjera?

Një model i një dhjetëkëndësh është bërë nga tela, nga një kulm i të cilit janë tërhequr të gjitha diagonalet. Dy persona hanë me radhë në një tel. Fituesi është ai pas lëvizjes së të cilit modeli ndahet fillimisht në dy pjesë. Kush fiton kur loja e duhur: ai që shkon i pari, apo partneri i tij?

Fillimisht, në çdo katror të tabelës 1n ka një damë. Lëvizja e parë është të zhvendosni çdo kontrollues në një qelizë ngjitur (një nga dy, nëse kontrolluesi nuk është në buzë), në mënyrë që të formohet një kolonë me dy damë. Pastaj, në lëvizjen tjetër, çdo kolonë mund të zhvendoset në çdo drejtim nga aq qeliza sa ka damë në të (brenda tabelës); Nëse një kolonë ulet në një qelizë jo bosh, ajo vendoset në krye të kolonës që qëndron atje dhe bashkohet me të. Vërtetoni se në lëvizjet n-1 mund të mblidhni të gjitha damët në një katror.

Janë 101 kanaçe me konserva me masa 1001 g, 1002 g, ..., 1101 g. Etiketat me peshoren kanë humbur, por kujdestarit i duket se kujton se cila kanaçe sa peshon. Ai dëshiron të sigurohet për këtë në numrin më të vogël të peshimeve. Ka dy peshore tepsi: njëra është e saktë, tjetra është e trashë. Në një peshim mund të krahasoni dy kanaçe. Peshore të sakta tregojnë gjithmonë se cila kanaçe është më e rëndë, dhe ato të përafërta vetëm nëse diferenca është më shumë se 1g (përndryshe tregojnë ekuilibër). Kujdestari mund të përdorë vetëm një peshore. Cilat duhet të zgjedhë? (A. Shapovalov)

Rrjeta e volejbollit ka formën e një drejtkëndëshi me përmasa 50600 qeliza. Cili është numri më i madh i litarëve të vetëm (midis nyjeve) që mund të priten në mënyrë që rrjeta të mos bjerë në copa?

Ka një rrjetë litari në formën e një katrori 88, i ndarë në 11 qeliza. Cili është litari më i gjatë që mund të pritet prej tij? (Mund të prisni çdo fund të nyjeve pa prishur lidhjen e pjesës tjetër, por nuk mund ta prisni nyjën në mënyrë që të mos krijohen skaje).

Fleta e fletores ishte e ngjyrosur në 23 ngjyra sipas qelizave. Një palë ngjyrash quhet e mirë nëse ka dy qeliza ngjitur të lyera me këto ngjyra. Cili është numri minimal i çifteve të mira?

Le ta quajmë një labirint një tabelë shahu 8x8 ku janë futur ndarje midis disa fushave. Nëse ruku mund të shkojë rreth të gjitha katrorëve pa u hedhur mbi ndarjet, atëherë labirinti quhet i mirë, përndryshe quhet i keq. Cilat labirinte ka më shumë - të mira apo të këqija?

Ka 100 qytete në vend, disa prej të cilave janë të lidhura me linja ajrore. Dihet që nga çdo qytet mund të fluturosh në çdo tjetër (mundësisht me transferta). Provoni se mund të vizitoni çdo qytet duke bërë jo më shumë se: a). 198 fluturime; b). 196 fluturime.

Në një tabelë shahu, fillimisht bosh, vendosen pengjet sipas duke ndjekur rregullat: Përzgjidhen çdo katër katror bosh, qendrat e të cilave janë kulmet e një drejtkëndëshi me brinjë paralele me anët e tabelës, pas së cilës vendoset një peng në njërin prej këtyre katrorëve. Pastaj zgjidhen katër qeliza të ngjashme boshe, një peng vendoset përsëri në njërën prej tyre, e kështu me radhë. Cili është numri më i madh i pengjeve që mund të vendosen në tabelë duke ndjekur këto rregulla?

Zonja e shtëpisë pjek një byrek për të ftuarit. Në tavolinë mund të ketë njerëz p ose q. Per cfare sasi minimale copa (jo domosdoshmërisht të barabarta), ju duhet ta prisni byrekun paraprakisht në mënyrë që në çdo rast të shpërndahet në mënyrë të barabartë midis të ftuarve nëse: a). p dhe q janë të dyfishta; b). a kanë p dhe q pjesëtuesin më të madh të përbashkët d?

Objekti sekret është një katror 88 në plan, i ndarë me korridore në 11 katrorë. Në çdo kulm të një katrori të tillë ka një ndërprerës. Klikimi i çelësit prek menjëherë të gjithë korridoret metërshe që dalin nga kjo majë, duke ndryshuar ndriçimin e tyre në të kundërt. Roja është në cep të një objekti krejtësisht të pandriçuar. Ai mund të ecë vetëm nëpër korridoret e ndriçuara dhe të rrokulliset disa herë. A mundet një roje të sigurojë që ai të mund të kalojë nga çdo çelës në një tjetër pa i kthyer çelësat?

Në një grafik të lidhur 2 n kulme, dhe të gjitha ato janë të shkallës 3. Vërtetoni se është e mundur të zgjidhni këtë mënyrë n+1 buzë, kështu që ngjyrosja e saktë në 3 ngjyra të skajeve të zgjedhura përcakton në mënyrë unike ngjyrosjen e saktë në 3 ngjyra të të gjitha skajeve të grafikut (ngjyrosja është e saktë nëse dy skajet me një kulm të përbashkët kanë ngjyra të ndryshme).

GRAFIKE BIPARITE.

Vërtetoni se një graf është dypalësh nëse dhe vetëm nëse të gjitha ciklet në të janë çift.

Vërtetoni se një pemë (një graf i lidhur pa cikle) është një graf bipartit.

Në një grup të caktuar njerëzish, të gjithë kanë një armik dhe një mik. Vërtetoni se këta njerëz mund të ndahen në dy kompani në mënyrë që në secilën kompani të mos ketë as armiq dhe as miq.

Ka 16 ekipe që luajnë në Kampionatin Ruse të Futbollit. Në raundin e parë të gjitha skuadrat luajtën një ndeshje. Në raundin e dytë të gjitha skuadrat luajtën edhe një lojë. Vërtetoni se është e mundur të identifikohen 8 ekipe të tilla që asnjë prej tyre të mos luajë me njëra-tjetrën.

Në një fletë letre me kuadrate ka një grup të caktuar M të fundme nyjesh. A është gjithmonë e mundur të ngjyrosësh disa pika të grupit M in? Ngjyra e bardhë, dhe pjesa tjetër - me të kuqe, në mënyrë që në secilën linjë të rrjetës, ndryshimi midis numrit të nyjeve të bardha dhe të kuqe në vlerë absolute të mos kalojë 1? (IMO, 1986)

Janë 1997 pikë të dhëna në aeroplan. Dy persona i lidhin me radhë këto pika me segmente dhe një segment nuk mund të vizatohet dy herë. Humbësi është ai lëvizja e të cilit krijon fillimisht një vijë të mbyllur të thyer me një numër tek të lidhjeve. Kush do të fitojë nëse luhet siç duhet?

Ne morëm 10 pikë në rreth. Cili është numri më i madh i segmenteve me skaje në këto pika që mund të vizatohen në mënyrë që asnjë tre prej këtyre segmenteve të mos formojë një trekëndësh me kulme në këto pika?

Në fshatin Martyshkino, çdo djalë, të gjitha vajzat që ai njeh e njohin njëri-tjetrin. Çdo vajzë njeh më shumë djem sesa vajza në mesin e miqve të saj. Vërtetoni se nuk ka më pak djem që jetojnë në Martyshkino sesa vajza.

Hidrat përbëhen nga koka dhe qafa (çdo qafë lidh saktësisht dy koka). Me një goditje të shpatës mund të presësh të gjitha qafat që dalin nga një kokë A e hidrës. Por në të njëjtën kohë, nga koka e A, një qafë rritet menjëherë në të gjitha kokat me të cilat A nuk është e lidhur. Herkuli e mposht hidrën nëse arrin ta presë në dy pjesë që nuk lidhen me qafat e tyre. Gjeni N-në më të vogël në të cilën Herkuli mund të mposhtë çdo hydra me njëqind qafë me jo më shumë se N goditje. (RosOl, 2002)

Në një shoqëri prej 2n+1 personash, për çdo n persona do të ketë një person të ndryshëm nga ata që e njeh secilin prej tyre. Provoni se ka një person në këtë kompani që i njeh të gjithë. (RosOl, 2002)

GRAFAT E SHFESË.

Ka 5 pika në një aeroplan, asnjë prej të cilave nuk shtrihet në të njëjtën linjë. Vërtetoni se rreth katër prej tyre shtrihen në kulmet e një katërkëndëshi konveks.

Ka 5 rrathë në një aeroplan, çdo dy prej të cilëve kryqëzohen. Vërtetoni se çdo tre prej tyre ka një pikë të përbashkët.

Ka 6 pika në aeroplan (3 blu dhe 3 të kuqe), asnjë prej të cilave nuk shtrihet në të njëjtën vijë të drejtë. Vërtetoni se 2 pika blu dhe 2 të kuqe ndodhen në kulmet e një katërkëndëshi konveks.

Në një fushë me kuadrate ka një grup të plotë domino (secila domino zë 2 katrorë). Le të thërrasim Rajon shumë qeliza që u goditën numra të njëjtë domino. Le të thërrasim zonën ndërlidhës, nëse nga ndonjë qelizë e tij një gur i çalë mund të futet në ndonjë tjetër. Cili është numri më i madh i zonave të lidhura që mund të jenë në terren?

URDHËRI I PJESËRISHËM.

Ka 12 vajza dhe 12 djem në klasë, të gjithë me lartësi të ndryshme. Gjatë mësimit të edukimit fizik, ata u rreshtuan në dy rreshta (njëra pas tjetrës): djemtë - sipas lartësisë nga e majta në të djathtë dhe vajzat - sipas lartësisë nga e djathta në të majtë. Pastaj më i gjati thirrej nga çdo çift djalë-vajzë. Provoni se keni thirrur dymbëdhjetë studentët më të lartë.

Janë dhënë disa numra të ndryshëm natyrorë. Dihet se nga çdo tre prej tyre, dy mund të zgjidhen në mënyrë që njëra të ndahet me tjetrën. Vërtetoni se të gjithë numrat mund të ngjyrosen me dy ngjyra në mënyrë që për çdo dy numra të së njëjtës ngjyrë, njëri të pjesëtohet me tjetrin.

Vërtetoni se nga 17 numra të ndryshëm natyrorë, ose ka 5 numra a, b, c, d, e të tillë që secili nga numrat e kësaj pesëshe, përveç atij të fundit, është i pjesëtueshëm me numrin pas tij, ose janë pesë. numra të tillë që asnjëri prej tyre nuk është i pjesëtueshëm me tjetrin.

Numrat 1, 2, 3, ..., 101 janë renditur në një rresht në një rend të caktuar. Vërtetoni se gjithmonë mund të kaloni 90 numra nga kjo seri në mënyrë që 11 të mbeturit të renditen në rend rritës ose zbritës.

ALGORITME.

Vërtetoni se kulmet në një pemë që përfshin mund të ngjyrosen në një model shahu.

Në një grup njerëzish, të gjithë njohin dikë. Vërtetoni se ky grup mund të ndahet në dy, në mënyrë që secili person të ketë një të njohur nga grupi tjetër.

Në fshat disa shtëpi janë të lidhura me tela. Fqinjë janë dy persona, shtëpitë e të cilëve janë të lidhur me tela. A do të jetë gjithmonë e mundur të vendosni një person në çdo shtëpi - një gënjeshtar ose një kalorës - në mënyrë që të gjithë të mund t'i përgjigjen pyetjes: "A ka ndonjë gënjeshtar midis fqinjëve tuaj?" – u përgjigj pozitivisht. (Të gjithë e dinë për secilin nga fqinjët e tij, nëse ai është gënjeshtar apo jo).

Vërtetoni se në kulmet e një poliedri mund të vendoset numra të plotë në mënyrë që në çdo dy kulme të lidhura me një buzë ka numra që nuk janë të dyfishtë, dhe në çdo dy kulme që nuk lidhen me një skaj ka numra të dyfishtë.

NË Port Aventura 16 agjentë sekretë u braktisën. Secili prej tyre monitoron disa nga kolegët e tyre. Dihet se nëse një agjent A mban një sy te agjenti NË, pastaj agjenti NË nuk e ndjek agjentin A. Çdo 10 agjentë mund të rinumërohet në atë mënyrë që i pari monitoron të dytin, i dyti - i treti, ..., i dhjeti - i pari. Vërtetoni se rreth 11 agjentë mund të numërohen në të njëjtën mënyrë.

Në çfarë n ju mund të ngjyrosni të gjitha skajet n- prizmi i karbonit (baza - n-gons) në tre ngjyra në mënyrë që në secilën kulm skajet e të tre ngjyrave të takohen dhe secila faqe (përfshirë bazat) të ketë skajet e të tre ngjyrave?

A). Vërtetoni se kulmet e një prizmi 3n-këndor mund të ngjyrosen me tre ngjyra në mënyrë që çdo kulm të lidhet me anë të kulmeve të të tre ngjyrave. b). Vërtetoni se nëse kulmet e një prizmi n-gonal mund të ngjyrosen me tre ngjyra në mënyrë që secila kulm të lidhet me skaje me kulmet e të tre ngjyrave, atëherë n pjesëtohet me 3.

"ANTIGRAF".

Në një shoqëri prej 2n+1 personash, për çdo n persona do të ketë një person të ndryshëm nga ata që e njeh secilin prej tyre. Provoni se ka një person në këtë kompani që i njeh të gjithë.

GRAFAT DHE POLINOMET.

Jepet një numër natyror k dhe polinomet R(x) Dhe S(x) me koeficientë të plotë. Dihet se për çdo numër të plotë x numri R(S(x)) – x i ndarë nga k. Vërtetoni se numri S(R(x)) – x pjesëtohet edhe me k për çdo tërësi x.

A ka katër polinome të tillë që shuma e çdo tre prej tyre të ketë të paktën një rrënjë, dhe shuma e çdo dy të mos ketë rrënjë?

CIKLICITETI.

NË qytet lulesh 2000 shorties jetojnë. Çdo shorty i bën një dhuratë çdo miku të tij çdo ditë. Për të shmangur shkatërrimin, dhurata mund t'i jepet më tej, por jo atij që ju ka bërë dhuratën. Znayka llogariti se asnjë nga dhuratat e bëra të premten nuk mund t'i kthehej më herët se të premten e ardhshme. Provoni se një djalë i shkurtër nuk ka më shumë se 13 miq. (E. Cherepanov)

Ka 100 qytete në shtet. Disa çifte qytetesh janë të lidhura me rrugë, me të paktën katër rrugë ciklike. Vërtetoni se ka një rrugë ciklike që kalon nëpër jo më shumë se 51 qytete.

Ka 100 qytete në vend, disa palë qytete janë të lidhura me rrugë, me gjithsej 200 rrugë. Doli se çdo rrugë ciklike ka një gjatësi prej të paktën pesë. Vërtetoni se ekzistojnë dy rrugë ciklike të ndara.

Në ndërtesën e Universitetit të Moskës ka shumë ashensorë dhe çdo ashensor transporton pasagjerë vetëm midis dy kateve (por në çdo kat mund të shkoni në çdo ashensor që ndalon në të). Dihet që mund të udhëtoni nga çdo kat në çdo përdorim tjetër numër çift ashensorë, dhe pa kaluar dy herë në asnjë kat. Vërtetoni se nëse dëshironi, e njëjta gjë mund të bëhet duke përdorur një numër tek të ashensorëve.

Në tokën e Ozit ka disa kështjella, nga secila prej të cilave ka tre shtigje. Kalorësi endacak la kështjellën e tij stërgjyshore dhe u nis për një udhëtim nëpër vend. Kalorësi e do shumëllojshmërinë, kështu që kur arrin në kështjellën tjetër, ai kthehet majtas çdo herë nëse kthehej djathtas herën e mëparshme dhe kthehet djathtas nëse kthehej majtas më parë. (Kur kalon kështjellën e parë në rrugën e tij, kalorësi mund të kthehet në çdo drejtim). Provoni se një ditë kalorësi do të kthehet në kështjellën e tij.

Një sekuencë e pafund numrash nga 1 deri në 9 është shtypur në një shirit pa fund. Vërtetoni se ose një kombinim i numrave do të përsëritet 10 herë rresht, ose 10 numra qindrashifrorë mund të priten prej tij në rend zbritës.

TEOREMA MBI PARITETIN E NUMRIT TË KRESHTVE TEKT.

Kulmet e një poliedri konveks, të gjitha fytyrat e të cilit janë trekëndësha, u pikturuan me tre ngjyra. Vërtetoni se numri i fytyrave, tre kulmet e të cilave janë të gjitha ngjyra të ndryshme është çift.

Numri i brinjëve.

Në një fletë të bardhë letre me kuadrate vizatoni një katror me përmasa 1212. Dy qeliza konsiderohen ngjitur nëse kanë anën e përbashkët. Sasha pikturon një qelizë në të njëjtën kohë, duke futur në secilën qelizë të pikturuar numrin e fqinjëve të saj të pikturuar më parë. Sa do të jetë shuma e të gjithë numrave kur të gjitha qelizat janë të ngjyrosura? (A. Shapovalov)

Ngjyrosëm një fletë letre me kuadrate pa fund, përveç një katrori 77. Në këtë shesh, Vasya ngjyrosi një qelizë në të cilën është ngjyrosur saktësisht një qelizë ngjitur (në anën), pastaj një qelizë tjetër në të cilën tani është ngjyrosur saktësisht një qelizë ngjitur, e kështu me radhë. E cila numri më i madh A mundet Vasya të pikturojë qelizat në këtë mënyrë?

Në çfarë n>1 mund të ndodhë që në një kompani nga n+1 vajza dhe n djemtë me të cilët janë njohur të gjitha vajzat numra të ndryshëm djem, dhe të gjithë djemtë me të njëjtin numër vajzash?

PËRZIERJE.

Mori pjesë në një takim n Njerëzore. Dihet se çdo dy të njohur nuk kanë asnjë njohje të përbashkët, dhe çdo dy të panjohur kanë saktësisht dy të njohur të përbashkët. A). Vërtetoni se të gjithë të pranishmit kanë të njëjtin numër të njohurish. b). Në çfarë n gjendje e mundshme e problemit?

Në qytetin e “Diversitetit” jetojnë 10 mijë banorë, çdo dy prej të cilëve ose në hasmëri ose miq me njëri-tjetrin. Çdo ditë, jo më shumë se një banor i qytetit mund të “fillojë jete e re", d.m.th. grindeni me të gjithë miqtë tuaj dhe bëni miq me të gjithë armiqtë tuaj; Për më tepër, çdo tre banorë mund të bëhen miq me njëri-tjetrin. Për të vërtetuar se të gjithë banorët, pa përjashtim, mund të bëjnë miq me njëri-tjetrin. Cili është numri më i vogël i ditëve që ka të ngjarë të jetë i mjaftueshëm për këtë?

k Dhe n– numra natyrorë më të mëdhenj se 1. Në një grup prej knçdo person është i njohur me më shumë se ( k–1)n nga pjesa tjetër. Provoni se mund të zgjidhni k+1 person në mënyrë që të gjithë ta njohin njëri-tjetrin. ( Lojërat Olimpike Polake, 68)

Në aeroplan janë shënuar 100 pika. Dy veta luajnë dhe ndërrohen. Me një lëvizje, ju mund të lidhni dy pika me një shigjetë nëse ato nuk janë lidhur më parë. Në këtë rast, është e ndaluar të vizatoni një shigjetë, pas së cilës do të jetë e mundur të kaloni nga çdo pikë duke përdorur shigjetat në ndonjë tjetër. Ai që nuk mund të bëjë një lëvizje tjetër pa shkelur rregullat, humbet. Kush fiton nëse loja luhet si duhet: ai që shkon i pari apo partneri i tij? ( PO. Rostovsky)

Në Qarkun e Njëanshëm, ka rrugë me një drejtim midis disa (por për fat të keq jo të gjitha) pronave. Për më tepër, kur ka rrugë e re(gjithashtu me trafik në një drejtim) midis pronave të palidhura me rrugë më parë, rezulton se mund të shkosh nga çdo pasuri në ndonjë tjetër pa shkelur rregullat. Provoni që një mundësi e tillë ekziston tani. ( PO. Rostovsky; Shën Petersburg, qyteti 2000)

Takova disa miq. Secili prej tyre shtrëngoi dorën me të gjithë, përveç Fedot Burcheev, i cili, duke qenë i jashtëzakonshëm, u shtrëngoi dorën disave dhe jo me të tjerët. Janë bërë gjithsej 197 shtrëngime duarsh. Sa shtrëngime duarsh bëri Fedot? ( I.S. Rubanov)

Ka 100 qytete në vend, dhe çdo qytet ka të paktën një rrugë. Vërtetoni se është e mundur të mbyllen disa rrugë në mënyrë që të ketë ende të paktën një rrugë që të çon jashtë secilit qytet, dhe në të njëjtën kohë të paktën 67 qytete të kenë saktësisht një rrugë që del prej tyre. ( E.A. Girsh, S.V. Ivanov, D.V. Karpov)

Shkolla ka 40 klasa që mund të hapen me 5 çelësa tipe te ndryshme, dhe numri i çelësave të llojeve të ndryshme është i ndryshëm. Të 40 çelësat ishin të kyçur në dhoma, kështu që në çdo dhomë kishte një çelës që nuk mund të përdorej për të hapur atë dhomë. Rojtari Sergeev ka një çelës dublikatë në njërën nga dhomat. Provojë se ai mund të hapë të gjitha dhomat. ( )

Shkolla ka 40 klasa që mund të hapen me 4 lloje të ndryshme çelësash. Të 40 çelësat ishin të kyçur në dhoma në mënyrë që në çdo dhomë të kishte një çelës të kyçur që nuk mund të përdorej për të hapur atë dhomë. Rojtari Sergeev e di se ku është secili çelës. Vërtetoni se rojtari Sergeev mund të bëjë çelësa dublikatë për dy zyra, me të cilat mund të hapni të gjitha dhomat. ( R.A. Ismailov, S.L. Berlov, D.V. Karpov)

(S. Berlov, Shën Petersburg, qytet, 2001, 6-1) Në shfaqjen e maceve, 19 mace dhe 10 mace meshkuj u ulën me radhë, dhe pranë çdo maceje u ul një mace që ishte më e trashë se ajo. Vërtetoni se pranë çdo maceje ishte ulur një mace që ishte më e hollë se ai.

(S. Berlov)Kontinenti katror është i ndarë në 19 vende në formën e poligoneve konveks, dhe nuk ka pika në të cilat kufijtë e katër ose më shumë vende. Nga çdo tre kufij që konvergojnë në një pikë, një është i mbyllur dhe dy janë të hapur për të udhëtuar. Vërtetoni se është e pamundur të udhëtoni nëpër të gjitha këto vende, duke vizituar secilin një herë dhe të ktheheni në vendin origjinal.

Në vendin e Falkersonia, disa qytete lidhen me linja ajrore dhe është e pamundur të shkosh nga qyteti A në qytetin B me më pak se dhjetë transferta. Provoni se të gjitha linjat ajrore mund t'u shiten 11 linjave ajrore në mënyrë të tillë që çdo rrugë nga A në B të kalojë përgjatë linjave në pronësi të të 11 kompanive. (Folklor, 100)

Çdo nxënës në klasë është i përfshirë në dy klube, dhe për çdo tre nxënës ka një klub në të cilin ata shkojnë së bashku. Vërtetoni se ekziston një klub në të cilin studiojnë të gjithë studentët. (Olimpiada DalFO 2001, 104)

. Dhjetë veta erdhën për vizitë me galoshe. Ata u larguan një nga një dhe secili veshi një palë galloshe të rastësishme që mund t'i futej (d.m.th., jo më të vogla se të tijat). Cili është numri më i madh i njerëzve që nuk kanë mundur të veshin galoshe?

NË vend i zanave Perra Terra, mes banorëve të tjerë, është shtëpia e karabaseve dhe barabaseve. Secili Karabas është i njohur me gjashtë Karaba dhe nëntë Baraba. Çdo daulle është e njohur me dhjetë karabase dhe shtatë daulle. Kush është më i shumtë në këtë vend - Karabas apo Barabas?

Në një grup prej 100 personash, në mesin e çdo tre është një person që i njeh të dy të tjerët. Vërtetoni se nga ky grup mund të zgjidhni një kompani prej 50 personash në të cilën të gjithë e njohin njëri-tjetrin. (S. Berlov)

Në klub erdhën 20 zotërinj: disa me kapele, disa pa. Më pas, herë pas here, njëri prej zotërinjve hiqte kapelën dhe ia vinte në kokë një zotëri tjetër, i cili në atë moment nuk kishte kapele. Një orë më vonë, 10 zotërinj thanë: "Kam dhënë një kapele më shpesh sesa kam marrë!" Sa zotërinj erdhën në klub me kapele? ( SLB, Yu.M. Lifshits; SPb-02)

Në një kompani të caktuar ka më shumë se 10 persona dhe numri i të njohurve të çdo personi pjesëtohet me 10. Vërtetoni se ka të paktën 11 persona me të njëjtën sasi të njohurit ( SLB bazuar në Moldavi)

Në Olimpiadë u propozuan 8 (6) problema. Secili pjesëmarrës zgjidhi saktësisht 3 prej tyre, dhe asnjë nga dy pjesëmarrës nuk zgjidhi më shumë se një detyrë e përbashkët. Cili është numri më i madh i pjesëmarrësve në Olimpiadë? ( Rruga Baltike, 01)

Për një kompani nga n një person plotëson kushtin e mëposhtëm: nëse çdo 2 persona kanë një numër të barabartë të njohurish, atëherë secili nga të tjerët njihet saktësisht me njërin prej tyre. Në çfarë n a eshte e mundur? ( Rruga Baltike, 2000)

19 të ftuar erdhën në festë. Në çdo 3 prej tyre ka 2 të njohur. Vërtetoni se të ftuarit mund të ndahen në 5 grupe, në secilën prej të cilave të gjithë e njohin njëri-tjetrin në çifte. ( V.L. Dolnikov, SLB, SVI)

(Folklori) Ka disa qytete dhe disa rrugë njëkahëshe në vend. Çdo rrugë lidh dy qytete dhe nuk kalon nga të tjerët. Në të njëjtën kohë, pavarësisht nga dy qytete që merrni, mund të vozitni nga të paktën njëri prej tyre në tjetrin pa shkelur rregullat e trafikut. Provoni se ekziston një qytet nga i cili mund të shkoni me makinë në ndonjë tjetër pa shkelur rregullat e trafikut.

Mes 11 njerëzve, çdo dy ka saktësisht një mik të përbashkët. Vërtetoni se të paktën njëri prej tyre i njeh të gjithë të tjerët.

(Lapok) Ndër 5 persona, çdo dy ka saktësisht një mik të përbashkët. Vërtetoni se të paktën njëri prej tyre i njeh të gjithë të tjerët.

(Juriabazuar në fakte klasike) Ka 120 qytete në vend. Disa çifte qytetesh lidhen me rrugë që nuk kalojnë nëpër qytete të tjera. Çdo qytet ka të paktën tre rrugë. Vërtetoni se ekziston një rrugë ciklike që nuk kryqëzohet vetë, e përbërë nga më së shumti 11 qytete.

(Yu.M. Lifshits) Në vendin e Jurland, disa qytete janë të lidhura me rrugë (duke mos kaluar nëpër qytete të tjera), dhe nga çdo qytet mund të shkoni në ndonjë tjetër. Një ditë fatkeqe, një fis i keq subçikësh pushtoi një qytet të caktuar. Çdo ditë tjetër, nënçikët ose kapën një qytet ngjitur me një prej të kapurve, ose çliruan një qytet të kapur, të gjithë fqinjët u kapën. Për më tepër, asnjë qytet nuk u pushtua më shumë se një herë. Vërtetoni se nëse subchiks nuk mund të kapin më asgjë, atëherë nga çdo dy qytete fqinje të paktën një është kapur.

(Yu.M. Lifshits) 14 anëtarë jurie ishin të pranishëm në banket dhe pinë 17 shishe limonadë. Katër anëtarë të jurisë pinin çdo shishe limonadë. Vërtetoni se janë dy anëtarë jurie që nuk kanë pirë limonadë nga e njëjta shishe.

(Folklori) Secili nga 7 anëtarët e ekipit nuk ka më shumë se dy miq të ngushtë. Pasi në të njëjtën dhomë, dy miq të ngushtë fillojnë të bisedojnë pandërprerë dhe e gjithë puna në këtë dhomë ndalon. Vërtetoni se tre dhoma janë të mjaftueshme për kapitenin për të siguruar funksionimin normal të të gjithë ekipit.

(Yu.M. Lifshits) 10 shahistë luajtën një turne me një raund, dhe secili fitoi, humbi dhe barazoi 3 ndeshje. Dihet se nuk ka tre shahistë që kanë shënuar saktësisht 1 pikë në ndeshjet kundër njëri-tjetrit. Vërtetoni se të dhjetë shahistët mund të vendosen në një rreth në mënyrë që secili prej tyre të mundë atë që qëndron në të djathtën e tij. Për fitore në shah jepet 1 pikë, për barazim jepet 0,5 pikë dhe për humbje 0 pikë.

(Yu.M. Lifshits) 10 shahistë luajtën një turne me një raund, dhe secili fitoi dhe humbi 4 ndeshje dhe barazoi një ndeshje. Provoni se mund të zgjidhni tre shahistë dhe t'i vendosni në një rreth në mënyrë që secili prej tyre të mundë atë që qëndron në të djathtën e tij.

Oktapodët jetojnë në Detin e Shirave, secili me një ose dy miq. Kur dielli lindi, të gjithë ata oktapodë që kishin dy miq u bënë blu dhe të gjithë ata që kishin një mik u bënë të kuq. Doli se çdo dy miq janë me ngjyra të ndryshme. Më pas 10 oktapodë blu u rilyen me ngjyrë të kuqe, dhe në të njëjtën kohë 12 oktapodë të kuq u rilyen me të kuqe. Ngjyra blu, pas së cilës çdo dy miq u bënë të njëjtën ngjyrë. Sa oktapodë ka në Detin e Shirave?

Ka 12 shtylla në oborr. Elektricisti Petrov iu dha detyra të lidhte shtyllat me tela në atë mënyrë që çdo tel të lidhte saktësisht dy pole, dy pole të mos lidheshin dy herë dhe, më e rëndësishmja, që për çdo katër pole të kishte saktësisht tre tela të shtrirë ndërmjet këto pole. Vërtetoni se elektricisti Petrov nuk do të jetë në gjendje të përballojë këtë detyrë.

Secili nga 24 personat njeh të paktën 11 nga të tjerët. A është gjithmonë e mundur që ato të vendosen në dhoma dyshe të hotelit në mënyrë që të gjithë të akomodohen me dikë që njohin?

Planeti Thor ka formë si një donut. Ka 5 qytete në të. A është e mundur që çdo palë e këtyre qyteteve të lidhet me rrugë në mënyrë që rrugët të mos kryqëzohen askund?

Në ishullin e Babilonisë së Re fliten 45 gjuhë, ku çdo banor di të paktën pesë prej tyre. Dihet se çdo dy banorë mund të zhvillojnë një bisedë me njëri-tjetrin, mundësisht me ndërmjetësimin e disa përkthyesve. Provoni se atëherë çdo dy banorë të ishullit mund të flasin me njëri-tjetrin duke përdorur shërbimet e jo më shumë se 15 përkthyesve.

Në një grup prej 100 personash, disa e njohin njëri-tjetrin dhe secili anëtar i grupit njeh të paktën 20 të tjerë. Vërtetoni se mund të zgjidhni 40 anëtarë të grupit dhe t'i ndani në 20 çifte në mënyrë që në secilën çift njerëzit të jenë të njohur.

Aktiv kn kartat kanë numra nga 1 në n 2 secili k një herë secili. Vërtetoni se këto karta mund të vendosen në tryezë në mënyrë që secili numër të shkruhet saktësisht sipër k një herë.

Ka 201 qytete në vend, secili me saktësisht 10 rrugë, dhe nga çdo qytet mund të shkosh në çdo qytet tjetër. Provoni se mund të zgjidhni 20 qytete, asnjë prej të cilëve nuk është i lidhur me një rrugë.

Në oborr ka disa shtylla, disa palë janë të lidhura me tela. Gjithsej i shtrirë mn telat, dhe këto tela janë të lyer n ngjyrat dhe asnjë tel me të njëjtën ngjyrë nuk shtrihet nga asnjë shtyllë. Vërtetoni se mund t'i ringjyroni këto tela në mënyrë që të ketë numër të barabartë telash të të gjitha ngjyrave dhe prapëseprapë të mos vijnë dy tela me të njëjtën ngjyrë nga asnjë pol. (130, Ukraina 1989)

Në oborr ka 36 shtylla; fillimisht, një tel shtrihet midis dy shtyllave. Çdo mëngjes rrugës për në shkollë, ngacmuesi Vasya thyen 35 tela. Çdo mbrëmje, elektricisti Petrov rikthen telat që vijnë nga një shtyllë e caktuar. Vërtetoni se Vasya mund të veprojë në atë mënyrë që një mëngjes pas një akti tjetër vandalizmi të mbeten më pak se 18 tela. (135, A.V. Pastor, Shën Petersburg 2000)

Në aeroplan janë shënuar 100 pika. Dy veta luajnë dhe ndërrohen. Me një lëvizje, ju mund të lidhni dy pika me një shigjetë nëse ato nuk janë lidhur më parë. Në këtë rast, është e ndaluar të vizatoni një shigjetë, pas së cilës do të jetë e mundur të kaloni nga çdo pikë duke përdorur shigjetat në ndonjë tjetër. Ai që nuk mund të bëjë një lëvizje tjetër pa shkelur rregullat, humbet. Kush fiton nëse loja luhet si duhet: ai që shkon i pari apo partneri i tij?

Disa numra të ndryshëm u zgjodhën nga numrat e plotë nga 1 në 100. Le ta quajmë indeksin e pjesëtueshmërisë së një numri të caktuar numrin e numrave të zgjedhur me të cilin numri i dhënëështë e ndarë tërësisht. Doli se të gjithë numrat e përzgjedhur kanë indekse të ndryshme pjesëtueshmërie. Cili është numri më i madh i numrave që mund të zgjidhen?

N Rrathët janë të rregulluar në mënyrë që qendra e secilit prej tyre të shtrihet saktësisht brenda njërit prej të tjerëve, dhe brenda secilit prej tyre qëndron pikërisht qendra e njërit prej të tjerëve. Gjeni të gjithë numrat N, në të cilën kjo është e mundur.

Në kongresin e shkrimtarëve të rinj morën pjesë 22 nxënës. Pas kongresit, secili prej tyre lexoi veprat e tre shkrimtarëve të rinj që morën pjesë në kongres. Vërtetoni se është e mundur të formohet një komision prej 4 personash nga delegatët e kongresit në mënyrë që askush në komision të mos lexojë punimet e anëtarëve të tjerë.

Në shtëpi pushimi janë 1999 pushues. Disa prej tyre e njohin njëri-tjetrin, dhe çdo dy të huajt kanë një mik të përbashkët mes pushuesve. Cili është numri më i vogël i mundshëm avulli pushuesit i njeh?

Ka 1000 qytete në planet, duke përfshirë kryeqytetet e shteteve. Disa qytete janë të lidhura me rrugë në atë mënyrë që çdo rrugë lidh saktësisht dy qytete, dhe nga çdo qytet në çdo qytet mund të arrihet me rrugë. Për më tepër, për të shkuar nga një kryeqytet në tjetrin, duhet të udhëtoni të paktën 21 rrugë. Vërtetoni se nuk ka më shumë se 90 kryeqytete në planet.

Janë 1997 gozhda të ngulitura në tabelë. Të dy bëjnë lëvizje me radhë. Lëvizja konsiston në atë që lojtari lidh çdo dy gozhdë që nuk ishin lidhur më parë me një tel. Humbësi është ai, pas lëvizjes së të cilit bëhet e mundur për herë të parë të kalojë telat nga çdo gozhdë në një tjetër. Kush do të fitojë nëse loja luhet si duhet: ai që bën lëvizjen e parë apo partneri i tij?

Grafiku i lidhur G mbetet i lidhur kur hiqen çdo 18 kulme (së bashku me të gjitha skajet që dalin prej tyre). Le të thërrasim prerjeçdo grup prej 19 kulmesh, kur hiqet, grafiku humbet lidhjen dhe copëçdo komponent i lidhjes që formohet kur hiqet prerja. Dihet se çdo pjesë që përmban më pak se 10 kulme nuk përmbahet në asnjë prerje. Vërtetoni se asnjë pjesë nuk gjendet brenda prerjes.

Grafiku G lidhur Le të thërrasim prerje grupi minimal i përfshirjes së kulmeve, kur hiqet (së bashku me të gjitha skajet që dalin prej tyre), grafiku humbet lidhjen. Dihet se gjatë heqjes së kulmeve të prera R kulme nga prerja S përfundojnë në të njëjtin komponent të lidhur. Vërtetoni këtë kur hiqni kulmet e një prerjeje S kulme nga prerja R përfundojnë në të njëjtin komponent të lidhur.

Janë të shënuara 49 pika rrjeti në letrën me kuadrate, të renditura në një katror 66. Cili është numri minimal i segmenteve të njësive me skaje në nyjet e shënuara që duhet të vizatohen në mënyrë që midis çdo çifti nyjesh ngjitur të ketë një shteg jo më të gjatë se 3?

Në një kompani nga n një person ku të gjithë njohin të paktën një nga të tjerët, të gjithë kanë një numër të barabartë të njohurish (besohet se nëse Aështë i njohur me NË, pastaj NËështë i njohur me A). Vërtetoni se nga anëtarët e kësaj kompanie është e mundur të zgjidhni të paktën n/3 çifte të ndara të të njohurve.

Në një kompani, çdo dy njerëz kanë saktësisht pesë njohje të përbashkëta. Vërtetoni se numri i të njohurve (çiftet e të njohurve) është shumëfish i tre. ( Yu.M. Lifshits)

Në turneun e vetëm të rrumbullakët, dy pjesëmarrës u larguan nga gara pas raundit të pestë. Në fund u luajtën 38 ndeshje në turne. A patën kohë këta të dy të luanin me njëri-tjetrin? ( Bullgaria, 1982)

Në turneun e vetëm të rrumbullakët, gjashtë pjesëmarrës u larguan nga gara pas raundit të gjashtë. Në fund u luajtën 67 ndeshje në turne. Vërtetoni se të paktën dy nga lojtarët e eliminuar nuk luajtën kundër njëri-tjetrit. ( K.A. Knop)

Cili është numri më i vogël i mundshëm i skajeve në një grafik me 100 kulme të tilla që midis çdo 11 kulmesh të jetë njëra e lidhur me 10 të tjerat? ( R. Fedorov)

Në grafikun 2 të lidhur n kulme, shkalla e çdo kulmi është tre. Vërtetoni se numri i mënyrave për të ngjyrosur skajet e këtij grafiku në tre ngjyra në mënyrë që skajet e ngjyrave të ndryshme të konvergojnë në secilën kulm të mos kalojë 32 n .

Në disa shtete 4 n aeroportet, nga secili aeroport largohen saktësisht 3 linja ajrore (një linjë ajrore lidh dy aeroporte). Nga çdo aeroport mund të fluturosh në çdo aeroport tjetër (mundësisht me transferta). Le TE - numri i mënyrave për të shitur Të gjitha linja ajrore në tre linja ajrore në mënyrë të tillë që tre linja ajrore të linjave ajrore të ndryshme të nisen nga secili aeroport. Vërtetoni këtë TE 32 3 n .

Tetë shahistë luajtën turneun në një raund. Dihet se në çdo tre shahistë ishin dy që luanin një barazim me njëri-tjetrin. Cili është numri më i vogël i barazimeve që mund të ndodhë në këtë turne?

Në kulmet e sheshit ka 4 kompjuterë të lidhur me fqinjët e tyre në anët e sheshit. Në momentin fillestar, çdo kompjuter mori një lajm të rëndësishëm (secili me të tijën). Çdo sekondë, një kompjuter ose mund të transmetojë të gjitha lajmet që di te një kompjuter fqinj, ose të marrë informacione përkatëse nga një kompjuter fqinj, ose të mos bëjë asgjë. Si për më pak kohë a mund të marrin të gjithë kompjuterët të gjitha lajmet e disponueshme në sistem?

Në vendin e Elenias n banorët. Ata bashkohen në grupe interesi. Ka saktësisht tre persona në secilin rreth, dhe çdo dy janë anëtarë të saktësisht të një rrethi në të njëjtën kohë. Vërtetoni këtë n Kur ndahet me 6, pjesa e mbetur është ose 1 ose 3.

Arritëm në kamp m djem dhe d vajzat. Çdo vajzë njeh jo më shumë se 10 djem dhe çdo djalë njeh jo më pak se një vajzë. Doli se çdo djalë njihte më shumë vajza se çdo vajzë që njihte njihte djem. Vërtetoni këtë d 1.1 m. (D.V. Karpov)

Jepni një shembull të një strukture me katërmbëdhjetë anë, secila faqe e së cilës është ose një katror ose trekëndëshi i rregullt? (PO. Kramarenko)

Ka 2000 pika të zeza në hapësirë, asnjë prej të cilave nuk shtrihet në të njëjtin plan. Disa nga pikat janë të lidhura me shigjeta. Dihet se nuk ka asnjë shteg që ndjek shigjetat dhe kalon nëpër të gjitha pikat (edhe nëse është e mundur të kalohet disa herë nëpër një pikë). Vërtetoni se disa nga pikat (të paktën një, por jo të gjitha) mund të ringjyrohen blu në mënyrë që asnjë shigjetë të mos çojë nga pika blu në atë të zezë. ( Bjellorusia, 1992)

Grafiku ka një pemë që përfshin saktësisht n kulme të varura dhe një pemë që shtrihet pikërisht me m majat e varura, n  k  m. Vërtetoni se ky grafik përmban një pemë që përfshin saktësisht k majat e varura.

Në një shoqëri prej 200 personash, çdo pesë mund të burgoset tryezë të rrumbullakët në mënyrë që secili prej tyre të ulet midis dy të njohurve (supozohet se nëse Aështë i njohur me B, Kjo Bështë i njohur me A). Cili është numri më i vogël i çifteve të të njohurve që mund të ketë në këtë kompani?

Vërtetoni se çdo shumëfaqësh mund të ketë dy faqe të kuqe dhe dy të tjerat blu, në mënyrë që faqet e kuqe të kenë anët e barabarta dhe ato blu gjithashtu.

Në një grafik të lidhur 3 k kulme, të gjitha kanë shkallën 3, me çdo kulm të përfshirë saktësisht në një trekëndësh. Disa skaje të grafikut u hoqën në mënyrë që të fitohej një pemë. Vërtetoni se kjo pemë ka më së shumti k+2 kulme të shkallës 1.( D.V. Karpov)

Në mbretëri N qytetet dhe r rrugë (secila rrugë lidh dy qytete, dhe nga çdo qytet mund të shkosh në cilindo përgjatë rrugëve). Lajmëtarët jetojnë në qytete. Në fillim të çdo viti, një nga qytetet dërgon një lajmëtar në të gjitha qytetet fqinje (d.m.th., të lidhura me të me rrugë). (Një qytet i tillë duhet të ketë një numër të mjaftueshëm të dërguarish për këtë.) Pas disa (më shumë se zero) vitesh, çdo qytet kishte të njëjtin numër të dërguarish siç kishte në fillim. Cili është numri më i vogël i lajmëtarëve që mund të ketë një mbretëri? ( I.I. Bogdanov)

Jepet një grafik shkalla e të cilit e çdo kulmi është të paktën k(ku k2). Vërtetoni se ky grafik përmban të paktën një cikël të thjeshtë gjatësie k+1. ()

Në një bandë terroristësh, secili dyshon të paktën 10 të tjerë për tradhti. Vërtetoni se në këtë bandë është e mundur të identifikohen të paktën 11 terroristë dhe të numërohen ata në mënyrë që i pari të dyshojë të dytin, të dytën, të tretën, ..., i parafundit i dyshuari i fundit, dhe i fundit dyshon i pari. ( bazuar nëKözepiskolai Matematikai Lapok)

Në një grafik, çdo dy cikle të thjeshta me gjatësi tek nuk kanë skaje të përbashkëta. Vërtetoni se kulmet e këtij grafiku mund të ngjyrosen me dy ngjyra në mënyrë që secila kulm të lidhet me anë të një skaji më së shumti me një kulm të së njëjtës ngjyrë. S.L. Berlov)

Ka 100 qytete në vend. Disa çifte qytetesh janë të lidhura me rrugë, por asnjë qytet nuk është i lidhur me të gjitha. Ju mund të shkoni nga çdo qytet në çdo tjetër duke vizituar jo më shumë se një qytet gjatë rrugës. Cili është numri më i vogël i rrugëve që mund të ketë ky vend? ( )

Ka 25 qytete në vend. Disa çifte qytetesh janë të lidhura me rrugë, por asnjë qytet nuk është i lidhur me të gjitha. Ju mund të shkoni nga çdo qytet në çdo tjetër duke vizituar jo më shumë se një qytet gjatë rrugës. Vërtetoni se ka të paktën 35 rrugë në këtë vend. ( Közepiskolai Matematikai Lapok)

Ka 9 qytete në vend. Disa çifte qytetesh janë të lidhura me rrugë, por asnjë qytet nuk është i lidhur me të gjitha. Ju mund të shkoni nga çdo qytet në çdo tjetër duke vizituar jo më shumë se një qytet gjatë rrugës. A mund të ketë ky vend jo më shumë se 13 rrugë? S.L. Berlov, D.V. Karpov, bazuar në Közepiskolai Matematikai Lapok)

Shkallët e të gjitha kulmeve të grafikut G më pak (ku n> 2), dhe në mesin e ndonjë n+ 1 ka dy kulme jo ngjitur. Le të thërrasim bllokoj shumë prej n kulmet ngjitur në çift të grafikut G.Dihet se çdo dy blloqe kanë një kulm të përbashkët. Vërtetoni se të gjitha blloqet kanë një kulm të përbashkët. S.L. Berlov)

Skajet e një grafiku të plotë me n majat janë pikturuar me disa ngjyra, dhe ngjyrat nuk janë më pak se n. Vërtetoni se ka tre kulme, të gjitha skajet ndërmjet të cilave janë të ngjyrosura me ngjyra të ndryshme. ( P.A. Kozhevnikov)

Skajet e një grafiku të plotë me n kulmet janë lyer me disa ngjyra në mënyrë të tillë që çdo ngjyrë të shfaqet më së shumti n- 2 herë. Vërtetoni se ka tre kulme, të gjitha skajet ndërmjet të cilave janë me ngjyra të ndryshme. AMM)

Në kolonë G grupe kulmesh të zgjedhura S 1 , S 2 , S 3 me 100 kulme secila. Dihet se kur hiqen të gjitha kulmet e njërës prej këtyre tre grupeve (dhe të gjitha skajet që vijnë prej tyre), kulmet e mbetura të grafikut ndahen saktësisht në dy komponentë të lidhur dhe kur hiqen çdo 99 kulme, grafiku mbetet i lidhur. Vërtetoni se të gjithë ata që nuk përfshihen në grupe S 1 , S 2 dhe S 3 kulmet e grafikut G mund të ndahet në 6 grupe në mënyrë të tillë që kulmet e një grupi të përfundojnë në të njëjtin komponent të lidhur kur kulmet e cilësdo prej grupeve hiqen nga grafiku S 1 , S 2 ose S 3 .(D.V. Karpov)

Mbreti Gorokh ka 20 oborrtarë. Duke intriguar kundër njëri-tjetrit, ata krijuan një sërë shoqërish sekrete. Shefi i policisë sekrete, duke studiuar këto shoqëri, zbuloi tre modele. Së pari, për çdo dy shoqëri sekrete, të gjithë oborrtarët që janë njëkohësisht anëtarë të të dyja shoqërive formojnë një shoqëri sekrete. Së dyti, për çdo dy shoqëri sekrete, të gjithë oborrtarët që janë anëtarë të të paktën njërës prej tyre formojnë një shoqëri sekrete. Së treti, për çdo shoqëri sekrete, të gjithë oborrtarët që nuk janë pjesë e saj formojnë një shoqëri sekrete. A mund të jetë pikërisht viti 2002 në gjykatën e bizeleve? shoqëritë sekrete? (Rideklarim i Putnam 1961)

Në skajet e dodekaedrit ka numra nga 1 deri në 30 pa përsëritje. Le të numërojmë numrin e vijave të thyera të përbëra nga tre skajet e dodekaedrit dhe të tilla që numrat në lidhje të jenë në rend rritës. Gjeni numrin minimal të mundshëm të vijave të tilla të thyera. (I.I. Bogdanov, G.R. Chelnokov bazuar në problemin e Olimpiadës Polake-89/90 )

Në skajet e kubit ka numra nga 1 deri në 12 pa përsëritje. Le të numërojmë numrin e vijave të thyera të përbëra nga tre skajet e një kubi dhe të tillë që numrat në lidhje të jenë në rend rritës. Gjeni numrin minimal të mundshëm të vijave të tilla të thyera. (Poloni-89/90)

Në një shoqëri prej 20 personash, për çdo tre persona ka një person që i njeh të gjithë. Provoni se ekziston një person që ka të paktën nëntë të njohur. ( S.L.Berlov, I.I.Bogdanov)

Në një shoqëri prej 10 personash, për çdo tre, është një person që i njeh të gjithë. Vërtetoni se ekziston një person që ka të paktën gjashtë të njohur.

Në simpozium erdhën 100 veta. Prej tyre, 15 ishin francezë, secili prej të cilëve njihte të paktën 70 pjesëmarrës në simpozium dhe 85 gjermanë, secili prej të cilëve njihte jo më shumë se dhjetë pjesëmarrës. Ata ishin vendosur në 21 dhoma. Vërtetoni se nuk ka asnjë palë të vetme të njohur në asnjë nga dhomat. ( Yu Lifshits)

Në kompani janë 22 atletë. Janë katërmbëdhjetë çifte sportistësh që janë miq me njëri-tjetrin. Doli se në mesin e çdo 11 atletësh ka të paktën një palë miq. Vërtetoni se të gjithë mund të ndahen në dysh skuader futbolli në mënyrë që çdo çift miqsh të përfundojë në të njëjtin ekip. ( Thjeshtimi i problemit 10 të Ligës së Madhe)

Në kolonën me 4 k kulmet 3 k brinjët Dihet se në mesin e çdo 2 k ka dy kulme të saj të lidhura me një buzë. Vërtetoni se kulmet e grafikut mund të ndahen në dy grupe me nga 2 k kulme në secilën në mënyrë që të mos ketë dy kulme nga grupe të ndryshme nuk lidhet me një skaj. (R.A.Brualdi, S.Mellendorf)

Një mbret i dehur shahu nuk bën kurrë dy lëvizje rresht në të njëjtin drejtim. Duke u nisur nga këndi, ai eci rreth dërrasës 99 me damë, duke vizituar çdo shesh një herë dhe u kthye në sheshin origjinal. Cili është numri më i vogël i lëvizjeve diagonale që mund të bënte? ( S.L. Berlov bazuar në problemin e O.Yu. Lanina, Olimpiada FML nr 239, 2002G.)

Ka 7 qytete në vend, me 7 avionë që fluturojnë mes tyre. Avioni fluturon nga çdo qytet në çdo qytet tjetër saktësisht 1 orë, dhe menjëherë pas uljes mund të fluturojë në qytetin tjetër (ndërsa pasagjerët transit mbeten në aeroplan). Bëni një orar fluturimi në mënyrë që çdo pasagjer, pa ndryshuar aeroplan gjatë rrugës, të mund të fluturojë nga çdo qytet në një tjetër jo më shumë se 5 orë pas mbërritjes në aeroport. (Grossman Olimpiada)

Pesë kulmet e kubit janë lyer me të kuqe. A është e vërtetë që patjetër do të ketë tre skaje me të dy skajet e kuqe?

Fedya ka një grafik të shkëputur. Ai është të gjithë mënyrat e mundshme Unë hoqa një kulm nga ky grafik dhe vizatova secilin nga grafikët që rezultuan në një copë letre të veçantë, pas së cilës ia dhashë të gjitha këto copa letre Dima. Vërtetoni se Dima mund të rivendosë grafikun origjinal duke përdorur këto gjethe. ( D.V. Karpov, bazuar në hipotezën e Ulamit)

Fedya ka disa kuti që përmbajnë topa. Ai merr me radhë një top nga kutitë, shkruan një grup numrash në një copë letre të veçantë - numrin e topave të mbetur në secilën kuti, nëse ka mbetur diçka atje (pa specifikuar se cili numër i korrespondon cilës kuti), dhe më pas e kthen topin në vendin e tij. Pasi ka nxjerrë çdo top një herë, ai ia jep të gjitha gjethet Dimës. Vërtetoni se Dima mund të përcaktojë sa topa janë në secilën kuti. ( D.V. Karpov)

n- numër i rastësishëm. Kulmet e konveksit n- goncat janë pikturuar me disa ngjyra në mënyrë që çdo dy kulme ngjitur - ngjyra të ndryshme. Vërtetoni këtë n-gon mund të ndahet në trekëndësha me diagonale jo të kryqëzuara, asnjëra prej të cilave nuk ka skaje të njëjta me ngjyrë. ( Kurszak-1978, nr 2)

Jepet një grafik në n majat. Vërtetoni se të gjitha skajet e tij mund të ndahen më së shumti në n 2/4 grupe, secila prej të cilave përbëhet nga një skaj ose është një trekëndësh. ( Bogdanov, Karpov)

Qytetet A, B, C lidhen me fluturime. Midis çdo dy qytetesh ka të paktën një fluturim, dhe të gjitha fluturimet janë me dy drejtime (nëse mund të fluturoni nga A në B, atëherë i njëjti fluturim mund të fluturojë nga B në A). Përveç kësaj, ne e dimë se numri i përgjithshëm i mënyrave për të shkuar nga pika A në pikën C (duke përfshirë rrugët me një transferim në B) është 11, dhe numri i përgjithshëm i mënyrave për të shkuar nga pika A në pikën B (duke përfshirë rrugët me një transferta në C) është 13. Sa janë fluturime pa ndalesë ndërmjet këtyre qyteteve?

Jepet një katror me kuadrate, ana e të cilit përmban n nyjet Një shteg pa kthim është një shteg përgjatë skajeve, kryqëzimi i së cilës me çdo vijë horizontale ose vertikale është një segment, pikë ose grup bosh. Cili është numri më i vogël i shtigjeve pa kthim që mund të mbulojnë të gjitha kulmet? ( I. Pushkarev, I. Bogdanov, G. Chelnokov)

Jepet një grafik i lidhur që mbetet i lidhur kur hiqet ndonjë kulm. Dihet se përmban një trekëndësh. Çdo kulm, përveç njërit, ka një shenjë (të gjitha shenjat janë të ndryshme). Lejohet të zhvendoset një pjesë nga një kulm ngjitur me një bosh në një bosh. Provoni se duke bërë këtë ju mund të merrni çdo konfigurim të çipave. ( M. Mazin)

Në qytet, 10 rrugë shkojnë nga veriu në jug dhe 11 nga perëndimi në lindje, duke formuar 110 kryqëzime. Me urdhër të kryetarit të bashkisë, çdo rrugë autobusi në qytet mund të shkojë në jo më shumë se dy drejtime (lindje-jug, lindje-veri, perëndim-jug ose perëndim-veri). A është e mundur të lidhen të gjitha kryqëzimet në qytet me shtatë linja autobusësh? (Bazuar në I. Pushkarev, I. Bogdanov, G Chelnokov)

Cili është numri më i vogël i kulmeve që mund të ketë një shumëfaqësh konveks, saktësisht tre nga fytyrat e të cilit janë pesëkëndësh? ( USAMTS 2003)