Електронно ръководство по дискретна математика. Научен форум dxdy. Теорема за четността на броя на нечетните върхове

Здравейте, използвам този форум, за да проверя следното доказателство. Като цяло тази задача е , но чух, че учениците я решават на олимпиада.

Задача.
В страната има 100 града, някои двойки градове са свързани с пътища. За всеки четири града има поне два пътя между тях. Известно е, че няма маршрут, който да минава точно веднъж през всеки град.
Докажете, че е възможно да изберете два града по такъв начин, че всеки от останалите градове да е свързан с път с поне един от двата избрани града.

Доказателство.
Градовете са върхове. Ребрата са пътища.

Нека да разберем дали графиката може да бъде прекъсната. Ако компонентът е по-голям от 3, тогава ще изберем 2 върха от единия, един от другия и още един от третия. Оказва се, че те могат да бъдат свързани най-много с един ръб. Условието на задачата е нарушено.
Нека има два компонента, всеки от които се състои от повече от един връх. Тогава всички трябва да са пълни. Ако това не е така, тогава вземете два несъседни върха от първия и всеки два от другия. Само два града могат да бъдат свързани в такъв комплект. Противоречие. Същото важи и за другия компонент. Така че и двете са пълни. Добре тогава, вземете всеки един връх от първия и всеки един от втория компонент. Условието на задачата е изпълнено.
Сега нека единият компонент е само един връх със степен 0. Тогава се оказва, че другият компонент ще бъде съставен от 99 върха. Ако премахнем повече от две ребра от който и да е връх, тогава условието веднага се нарушава: вземаме връх със степен 0, връх без два ребра и върхове, към които няма ребра от него (ще има 1 ребро). Това означава, че само един ръб може да бъде премахнат от всеки връх. Но ако направите това, тогава всеки връх ще има нечетна степен (преди всеки имаше 98). И може да има само четен брой нечетни степени, така че или премахваме някъде два ръба и ограничението за 4 града се нарушава, или оставяме всички ръбове и тогава има пълен връх.

Ще наричаме градове, от които има пътища до всички останали градове, q и p.

След това доказваме чрез индукция, че за всяка свързана графа с ограничение от 4 града и път условието ще бъде изпълнено.
База. от 4 върха е очевидно: вземете произволно обхващащо дърво и изберете връх в него, който е различен от лист, а вторият е лист.

Преход. Нека има граф от върхове. След това за всички графики по-малък размер, за които условията на задачата са изпълнени, всичко е доказано.

Необходимо е да се докаже, че може да се използва индукционната хипотеза.
Нека назовем върха, който ще бъде изхвърлен като .
Ако има график от връх, където за всеки 4 града трябва да има два пътя, тогава това трябва да е вярно и за градовете: ще разгледаме всички градове без един. Основното е, че графиката не губи свързаност и това винаги може да стане чрез премахване само на висящия връх, ако има такъв.

Ако се окаже, че е образуван g.path, то той не може да бъде свързан с един от неговите краища (в противен случай g.path в графиката). Така че, за изтриване, това е висящ връх в обхващащото дърво. Ако се окаже, че това все още не е възможно: той е бил свързан чрез един връх към края, който е премахнат, тогава ще премахнем другия. В същото време не може да се случи, че един връх е свързан през един връх към двата края: това ще бъде график на 3 върха (и ако има втори път до края, тогава има r.path ), и това може да се докаже за графи с повече от 4 върха.
Очевидно, чрез премахване на висящ връх в обхващащо дърво, свързаността не се губи.

Сега е доказано, че ако има някаква графика, удвоете. условие, тогава можете да изберете връх, след премахването на който ще се получи по-малка графа, която удовлетворява първоначалното условие. Това означава, че можем да използваме индуктивната хипотеза.

Сега има свързан към граф от върхове, тази държава от градове има свои собствени p и q. Ясно е, че ако има ребро от към p или q, тогава няма нужда да се доказва нищо. Тогава нека да няма пътища от към p и към q.
Множеството, към което има пътища от p, ще се нарича A, а множеството, към което има пътища от q, ще се нарича B.
Нека няма път от p до q. Тогава нека градът да не бъде свързан с пътя с града. Но тогава трябва да има пътища както в p, така и в q, в противен случай вземаме върховете , , p и q.
Тогава се оказва, че градът не може да не бъде свързан с пътища с градове от
Но тогава можете да направите града ново p и да оставите q същото (или обратното).

Това означава, че остава само един случай: p и q са свързани с път.
Ще оставим имената на комплектите същите.
По индукционната хипотеза: графиката няма Хамилтонов път.
Още веднъж, ако има пътища от към целия набор или към всичко, тогава всичко вече е доказано.

Сега има двойка върхове и от които няма ръбове до .
Ако има само , то покрива всичко, което q не покрива, тогава p. После – нов голям град.
Ако е празен, значи е свързан с и всичко е доказано.

Ако няма ръб между и, тогава вземаме , , и p - ще има един ръб. Така че съществува. Сега се оказва, че - пълен подграф, обаче, както и (в противен случай вземаме или, p или q, както е необходимо, и несвързани върхове).
Сега разгледайте подграфа на върхове от . Нека се опитаме да покрием целия набор от върхове, използвайки прости пътеки.
Нека резултатът е покритие само на 4 прости пътеки. Нека вземем по един краен връх от всеки: ако има ребро, тогава можем да свържем два крайни върха и да получим по-дълъг път. Резултатът беше антиклика на четири върха. Противоречие.
Сега е известно, че наборът е покрит от най-много 3 прости пътеки. Ще разглеждаме всеки прост като един връх: ако можете да стигнете до някой от краищата, тогава можете да преминете през всеки връх вътре в него веднъж - също е прост и това може да се направи, т.к. всеки връх от може да бъде достигнат както през p, така и през q. Сега има само не повече от 3 върха.
Един път може да се състои от един връх или повече. Ако са повече, тогава идентифицираме целия път с един краен връх.
Нека наречем лявото множество - , дясното - , средното - (пътищата са компресирани във върхове).
Можете да забравите за върха: ако се окаже, че има r.path, тогава вече ще има противоречие с индуктивното предположение.
Случай 1. Средният набор е празен. След това просто (просто чрез върхове) обикаляме лявото множество, започвайки от всеки връх, различен от , завършваме в , след това в p , след това веднага q , след това в и просто обикаляме десния набор. Оказа се градска пътека.
Случай 2. Средното множество има един връх. Всичко е същото, но от p до q минаваме през този връх.
Случай 3. Сега има върхове в средния набор

1. Дъската има формата на кръст, която се получава, ако ъгловите клетки се премахнат от квадратна дъска $4 \times 4$. Възможно ли е да го заобиколите, като преместите шахматен кон и се върнете към първоначалното поле, след като сте посетили всички полета точно веднъж?
2. В страната на цифрите има 9 града с имена 1, 2, 3, 4, 5, 6, 7, 8, 9. Един пътешественик откри, че два града са свързани с авиокомпания тогава и само ако двуцифрено число, съставен от числата-имена на тези градове, се дели на 3. Може ли да се стигне от град 1 до град 9?
3. В град Маленки има 15 телефона. Възможно ли е да ги свържа с кабели, така че всеки телефон да е свързан с точно пет други?
4. В щата има 100 града и всеки от тях има 4 пътя. Колко пътища има в щата?
5. В класа има 30 души. Възможно ли е 9 от тях да имат 3 приятели (в този клас), 11 да имат 4 приятели и 10 да имат 5 приятели?
6. В град Маленки има 15 телефона. Възможно ли е да ги свържем с кабели, така че да има 4 телефона, всеки от които е свързан с три други, 8 телефона, всеки от които е свързан с шест, и 3 телефона, всеки от които е свързан с пет други?
7. Кралят има 19 васални барона. Възможно ли е всяко васално баронство да има 1, 5 или 9 съседни баронства?
8. Може ли щат, в който има 3 пътя, водещи от всеки град, да има точно 100 пътя?
9. Джон, пристигнал от Дисниленд, каза, че има 7 острова на омагьосаното езеро, с 1, 3 или 5 моста, водещи от всеки от тях. Вярно ли е, че поне един от тези мостове задължително стига до брега на езерото?
10. Докажете, че броят на хората, които някога са живели на Земята и направили нечетен брой ръкостискания, е четен.
11. Възможно ли е да се начертаят 9 отсечки в равнина, така че всеки да пресича точно три други?
12. В страната на Седемте има 15 града, всеки от които е свързан с пътища с поне 7 други. Докажете, че от всеки град можете да стигнете до всеки друг (евентуално като минавате през други градове).
13. Докажете, че граф с $n$ върха, всеки от които има степен най-малко $(n - 1)/2$, е свързан.
14. В Далечното кралство има само един вид транспорт - летящ килим. Има 21 килимни линии, напускащи столицата, една от град Dalniy и 20 от всички останали градове.Докажете, че е възможно да летите от столицата до Dalniy (възможно е с прекачвания).
15. В страната всеки град има 100 пътя и от всеки град можете да стигнете до всеки друг. Един път беше затворен за ремонт. Докажете, че сега можете да стигнете от всеки град до всеки друг.
16. а) Дадено е парче тел с дължина 120 см. Възможно ли е, без да се счупи телта, да се направи рамка на куб с ръб 10 см?
    б) Колко пъти най-малко ще трябва да се скъса телта, за да се получи необходимата рамка?
17. Докажете, че граф, в който всеки два върха са свързани с точно един прост път, е дърво.
18. Докажете, че всеки два върха в едно дърво са свързани с точно един прост път.
19. Докажете, че в дървото има връх, от който излиза точно едно ребро (такъв връх се нарича висящ връх).
20. Всички върхове в графа имат степен 3. Докажете, че той съдържа цикъл.
21. Докажете, че премахването на което и да е ребро от едно дърво го превръща в несвързан граф.
22. В страната Древланд има 101 града, като някои от тях са свързани с пътища. Освен това всеки два града са свързани с точно един път. Колко пътища има в тази държава?
23. Докажете, че свързан граф, чийто брой ребра е с едно по-малък от броя на върховете, е дърво.
24. Волейболната мрежа има формата на правоъгълник с размери $50 \ пъти 600$ клетки. Който най-голямото числоМогат ли струните да се режат, за да не се разпадне мрежата?
25. В дадена държава има 30 града, всеки свързан с всеки чрез път. Кой е най-големият брой пътища, които могат да бъдат затворени за ремонт, така че да може да се пътува от всеки град до всеки?
26. Докажете, че във всяка свързана графа можете да премахнете връх заедно с всички ребра, идващи от него, така че да остане свързан.
27. В страната има 100 града, някои от които са свързани с авиолинии. Известно е, че от всеки град можете да летите до всеки друг (евентуално с трансфери). Докажете, че можете да посетите всеки град за не повече от
    а) 198 полета;
    б) 196 полета.
28. В страната Озерная има 7 езера, свързани помежду си с 10 канала, и от всяко езеро можете да плувате до всяко друго. Колко острова има в тази страна?
29. Отбелязахме 20 точки в квадрата и ги свързахме с непресичащи се отсечки една с друга и с върховете на квадрата, така че квадратът да се раздели на триъгълници. Колко триъгълника получихте?
30. Граф, който има 5 върха, всеки от които е свързан с ребро с всеки друг, не е планарен.
31. Възможно ли е да се построят три къщи, да се изкопаят три кладенеца и всяка къща да се свърже с всеки кладенец с пътеки, така че пътеките да не се пресичат?
32. Докажете, че граф с 10 върха, всеки от степен 5, не е планарен.
33. Докажете, че планарен граф има връх, чиято степен не надвишава 5.
34. Всеки ръб на пълен граф с 11 върха е оцветен в един от два цвята: червен или син. Докажете, че нито "червената", нито "синята" графика не е равнинна.
35. Седмоъгълникът е разделен на изпъкнали петоъгълници и шестоъгълници и по такъв начин, че всеки от неговите върхове е връх в понедва преградни полигона. Докажете, че броят на петоъгълниците в преградата е най-малко 13.

2. Решете следната задача за обхождане на графика:

Определена държава има столица и 100 други града. Някои градове (включително столицата) са свързани с еднопосочни пътища. Всеки нестоличен град има 20 пътя, а всеки такъв град има 21 пътя. Докажете, че е невъзможно да стигнете до столицата от който и да е град.

Да влезе път в столицата. Тогава общ брой"входящите" пътища са равни на 21 100 +a, а общият брой на "изходящите" пътища не е повече

20 100 + (100-а). Следователно 21 100 + a 20 100 + (100 – a), тоест 2a 0.

Така a = 0.

3.3.2.1. Диграф G1 (V,E): V=(a, b, c, d, e, f), се дефинира като алгебрична система.

а) За дадената връзка дефинирайте орграфа геометрично. b) Конструирайте матрицата на съседство на диграфа.

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. Орграфът е дефиниран геометрично. Посочете валентността на върховете.

8) 1

3.3.2.3. Дадена е матрицата на съседство на орграфа. а) Дефинирайте орграфа геометрично, в) изградете матрица на инцидентност.

        

001100

001000

3.3.2.4. Дадена е матрицата на инцидентност на диграфа. а) Дефинирайте орграфа геометрично, в) изградете матрица на съседство.

3.3.2.5. Решете следните задачи за обхождане на графика:

0) Дима, пристигнал от Врунланд, каза, че там има няколко езера, свързани с реки. Три реки изтичат от всяко езеро и четири реки се вливат във всяко езеро. Докажете му, че греши.

1) В определена държава всеки град е свързан с всеки път. Лудият крал иска да въведе еднопосочно движение по пътищата, така че след като напуснете който и да е град, да не можете да се върнете в него. Възможно ли е да се направи това?

2) Казват, че в компания от петима души всеки познава още двама. Възможна ли е такава компания?

3) Някой щат има 101 града. Всички градове са свързани с еднопосочни пътища, като 50 пътя влизат във всеки град и 50 излизат от всеки град. Докажете, че можете да стигнете от всеки град до всеки друг, като карате по не повече от два пътя.

4) На една равнина са дадени 6 точки, така че никакви три от тях не лежат на една и съща права линия. Всяка двойка точки е свързана със синя или червена линия. Докажете, че сред дадените точки е възможно да се изберат три такива, че всички страни на образувания от тях триъгълник да са боядисани в един и същи цвят.

5) Някой щат има 101 града. Някои градове са свързани с еднопосочни пътища, като 40 пътя влизат във всеки град и 40 излизат от всеки град. Докажете, че можете да стигнете от всеки град до всеки друг, като карате по не повече от три пътя.

6) Възможно ли е да създадете 10 автобусни маршрута в един град и да инсталирате спирки на тях, така че независимо кои 8 маршрута да се вземат, да има спирка, която не лежи на нито един от тях, а всеки 9 маршрута да минава през всички спирки.

7) Бръмбар пълзи по ръбовете на куб. Ще успее ли той да премине през всички ръбове последователно, преминавайки всеки ръб точно веднъж? Съвет: Помислете върху въпроса: колко пъти един бръмбар може да посети всеки връх?

8) Художникът рисува картина "Очертанията на квадрат и неговите диагонали". Може ли да нарисува своята картина, без да вдига молива си от хартията или да начертае една и съща линия два пъти?Инструкция: Четен брой линии трябва да излизат от всяка точка, с изключение на началото и края на пътя на молива.

9) Аркадий, Борис. Владимир, Григорий и Дмитрий се ръкуваха, когато се срещнаха (всеки се ръкува един с друг по веднъж). Колко ръкостискания бяха направени?

3.3.2.6. Решете следните задачи за обхождане на графика:

0) Метрото в Урюпинск се състои от три линии и има поне две крайни станции и поне два трансферни възела, като никоя от крайните станции не е трансферна станция. Можете да преминете от всеки ред към всеки на поне две места. Начертайте пример за такава диаграма на метрото, ако знаете, че това може да стане, без да вдигате молива от хартията и без да рисувате един и същи сегмент два пъти.Забележка: Не забравяйте, че има пръстени.

3) Дъската има формата на кръст, която се получава чрез премахване на ъгловите квадрати от квадратна дъска 4 × 4. Възможно ли е да го заобиколите, като преместите шахматен кон и се върнете към първоначалното поле, след като сте посетили всички полета точно веднъж?

4) Пешеходец обиколи шест улици на един град, минавайки през всяка точно два пъти, но не можа да ги заобиколи, минавайки през всяка само веднъж. Може ли това да е?

5) В центъра на куба 3 3 3 има бръмбар. Докажете, че пълзейки по ръбовете, той не може да обиколи всички кубове 1 1 1 веднъж.

6) В квадрат 6x6 са маркирани няколко клетки, така че от всяка маркирана можете да отидете до всяка друга маркирана, като минавате само през общите страни на маркираните клетки. Маркирана клетка се нарича крайна клетка, ако граничи от страната на точно една маркирана клетка. Маркирайте няколко клетки, така че да получите а) 10, б) 11, в) 12 клетки.

7) Муха седи на един от върховете на а) октаедър б) куб. Може ли да пропълзи по всичките му ребра точно веднъж и да се върне

оригинален връх? (Забележка: Октаедърът е две четириъгълни пирамиди, залепени заедно в основите.)

8) Как, без да вдигате молива от хартията, да начертаете шест сегмента по такъв начин, че 16 точки, разположени във върховете на квадратна мрежа 4 на 4, да бъдат зачеркнати?

9) Може ли да се начертае диагонал във всеки квадрат от повърхността на кубчето на Рубик, така че да се получи несамосичащ се път?Забележка: На повърхността на кубчето на Рубик има само 54 квадрата.

3.4. Оптимизационни проблеми на графики

Ако дъга от насочен граф G 1 (V ,E) е свързана с някакво реално число a (u ,v), наречено тегло, тогава последователността от върхове v 0 ,v 1 ,...,v p дефинира път в G 1 и неговата дължина

се определя като сбор от теглата:

Ако в някоя

В графиката теглото на всяка дъга е равно на единица, тогава дължината на пътя е равна на броя на дъгите. Проблемът за най-краткия път най-често възниква при решаването

транспортни и дискретни проблеми динамично програмиранеи др Дълж най-краткия пътозначават r (v i,v j) и се наричат ​​разстояние от v i до v j (разстоянието може да бъде отрицателно). За всеки орграф може да се конструира матрица на разстоянието R=r(i, j). Матрицата се попълва ред по ред, като се избира върха отляво (вдясно). Стойността е най-малкият брой дъги, свързващи върха отляво с един от върховете в редицата.

Ако няма път от v i до v j , тогава задаваме r (v i ,v j ) = . Ако всеки контур на нашата графика има положителна дължина, тогава най-късият път винаги ще бъде елементарен път, т.е. няма да има повторения в последователността v 1 ,...,v p.

Средното отклонение на върха vi от центъра на графиката D(vi) е равно на:

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

m v V

където m е броят на дъгите в графиката, v минава през върховете на графиката, n е броят на върховете в графиката, i = 1..n.

Върхът, за който D(vi ) се оказва минимален, се нарича център на графа (възможни са няколко върха - център на графа).

По пътя или маршрутана граф G1 (V,E) е последователността от неговите върхове и ръбове v1e1v2e2v3…vnen vn+1, в която

всеки два съседни елемента са инцидентни. Пътят се нарича прост, ако среброто и всички върхове по него, с изключение на първия и последния, са различни.

Маршрутът се нарича верига, ако всичките му ръбове са различни. Маршрутът се нарича проста верига, ако всичките му върхове и следователно неговите ръбове са различни.

Цикълът в графа е път, в който началният връх съвпада с крайния връх и който съдържа поне едно ребро.

Цикълът се нарича прост, ако няма еднакви върхове с изключение на първия и последния, т.е. ако върховете са различни.

Ако графиката няма цикли, тогава тя се нарича ациклична.

Сега можем да дефинираме концепцията за дърво по различен начин. Свързан граф без цикли се нарича дърво.

Примери за изпълнение на задачи

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

И така, центърът на графиката е върхове 2 и 3.

2. Селото е построено под формата на квадрат от 3 блока на 3 блока (блоковете са квадрати със страна b, общо 9 блока). Какво е най-краткото разстояние, което асфалтополагачът трябва да измине, за да асфалтира всички улици, ако започне и завършва пътя си в ъглова точка А? (Страните на площада също са улици).

Ориз. 6. Най-краткият път

Ясно е, че дължината на трасето на асфалтополага е най-малко 24, тъй като трябва да премине по всяка улица поне веднъж. Нека докажем, че той ще трябва да кара по поне четири улици два пъти. Точно осем кръстовища се пресичат нечетен брой улици.

Следователно, всеки кръгъл път на павета трябва да премине два пъти по най-малко 8/2 = 4 улици.Минималната дължина на маршрут на павета е 28; Един от възможните маршрути е показан на фигура 6.

3. Дефинирайте графиката геометрично и решете задачата:

Изтичайки на двора след училище, всеки ученик хвърли снежна топка точно по един ученик. Докажете, че всички ученици могат да бъдат разделени на три отбора, така че членовете на един отбор да не хвърлят снежни топки помежду си.

Нека отбележим учениците в самолета с точки и да ги свържем със стрелка, ако единият хвърли другия. Получената картина ще изглежда като няколко цикъла с „рога“ (пътеки, водещи от точка към цикъл). Всяка такава фигура може лесно да бъде разделена на три групи: прекъсвайки цикъла, поставяме един ученик в първата група и получените дървета се разделят на четни и нечетни върхове.

Задачи за самостоятелно изпълнение

3.4.1. Запишете: 1) всеки път, който не е верига; 2) верижна и проста верига; 3) цикъл, прост цикъл, ако има такъв.

3.4.2. Орграфът е дефиниран геометрично. Изградете матрица на разстоянието. Изчислете центъра на диграфа.

ГРАФИКИ НА ОЙЛЕР.

Докажете, че пълен набор от домино може да бъде подреден според правилата на доминото.

"Лема за кръглите танци."В някои компании всеки човек има точно двама приятели. Докажете, че ако всички приятели се хванат за ръце, те ще образуват един или повече кръгли танци.

В страната има повече от 101 града. Столицата е свързана с авиолинии със 100 града, като всеки град с изключение на столицата е свързан с точно десет града (авиокомпанията работи и в двете посоки). Известно е, че от всеки град можете да стигнете до всеки друг (може би с трансфери). Докажете, че е възможно да затворите половината от авиокомпаниите, идващи от столицата, така че възможността да стигнете от всеки град до всеки ще остане.

Докажете, че свързана графа с 2n нечетни върха може да бъде начертана, като вдигнете молива от хартията точно n–1 пъти и без да начертаете ребро два пъти.

В страната от всеки град тръгват по 3 ж.п. Две компании искат да ги приватизират. Антимонополната комисия изисква пътищата на двете компании да излизат от всеки град. Докажете, че компаниите могат да се договорят помежду си, така че изискването на Антимонополния комитет да бъде изпълнено.

Дадена е свързана графа G с k ребра. Докажете, че е възможно да се номерират ръбовете с всички числа 1, 2, ..., k, така че за всеки връх от степен най-малко две, множеството от числа, които маркират ръбовете от този връх, да има НОД равно на 1 .

Във футболен турнир, проведен сред 20 отбора от различни градове, всеки отбор изигра по една среща у дома и не повече от две срещи като гост. Докажете, че е възможно да се планират игри така, че всеки отбор да играе не повече от една игра на ден и целият турнир да се играе за три дни.

Хамилтън Каунт.

Върху повърхността на куба е начертана затворена прекъсната линия с осем звена, чиито върхове съвпадат с всички върхове на куба. Какъв е най-малкият брой връзки на тази начупена линия, които могат да съвпадат с ръбовете на куба?

Един куб е направен от осем малки кубчета. Възможно ли е, като се започне от центъра на голям куб и се движи по ръбовете на малки кубчета, да се обиколят всички върхове на малки кубчета, като се посети всеки точно веднъж?

Дадена е дъска 55. Може ли конят да обиколи всички квадрати, като посети всеки квадрат веднъж и да се върне в началната си позиция?

Възможно ли е да преместите куц крал (царят не може да се движи по диагонали) на всички полета на шахматната дъска, започвайки от долния ляв ъгъл и завършвайки в горния десен ъгъл?

Може ли конят да направи 8 хода и да се върне на първоначалното си поле, след като е посетил всички хоризонтални и вертикални линии на шахматната дъска?

А). Черните и белите чипове се поставят на две полета на шахматната дъска. Имате право да ги премествате на свой ред, като всяко движение премества следващия чип във всяко свободно съседно поле вертикално или хоризонтално. В резултат на такива ходове могат ли всички възможни позиции на тези два чипа да се появят на дъската и точно веднъж? б). Какво става, ако ви е позволено да местите чиповете в произволен ред (не непременно един по един)?

Кой от следните три факта е най-силният?

В някои щати всеки 2 града са свързани с път. Всеки път има право да се движи само в една посока. Докажете, че има град, от който можете да пътувате из целия щат, като посетите всеки град точно веднъж.

В дадена държава всеки град е свързан с всеки град чрез еднопосочен път. Докажете, че има град, от който можете да стигнете до всеки друг.

В определен щат има 100 града и всеки е свързан с всеки с еднопосочен път. Докажете, че е възможно да промените посоката на движение по един път, така че да можете да стигнете от всеки град до всеки друг.

Докажете „най-силния“ факт и двете последствия от него.

В еднокръгов турнир по шах всеки участник изигра по една партия всеки срещу всеки. Докажете, че участниците могат да бъдат номерирани по такъв начин, че никой от тях да не губи от този, който е непосредствено до него по номер.

В страната има N града. Между всеки два от тях има или път, или Железопътна линия. Туристът иска да обиколи страната, като посети всеки град точно веднъж и се върне в града, от който е започнал пътуването. Докажете, че туристът може да избере града, от който ще започне своето пътуване и маршрута, така че да не трябва да сменя вида на транспорта не повече от веднъж. (Всеруска олимпиада, 2003)

Поредица от 36 нули и единици започва с 5 нули. Сред петте подред се намират всичките 32 възможни комбинации. Намерете последните пет цифри от редицата.

"Рицари в двора на крал Артур" - теорема на Дирак. 2n рицари се събраха на кръглата маса на крал Артур, всеки от които няма повече от (n–1) врагове сред останалите. Докажете, че съветникът на краля Мерлин може да настани рицарите по такъв начин, че враговете да не седят наблизо. Изложете теоремата на Дирак в общ вид.

На конференцията дойдоха 2n души, всеки от които познава поне n други. Докажете, че участниците могат да бъдат настанени в двойни стаи, така че хора, които се познават, да живеят във всяка стая.

Дадени са n чипа от няколко цвята, с не повече от n/2 чипа от всеки цвят. Докажете, че те могат да бъдат поставени върху кръг, така че да няма две парчета от един и същи цвят една до друга.

IN федерална държава, състоящ се от две републики, като всеки два града са свързани с еднопосочен път; В същото време, движейки се по пътищата, можете да стигнете от всеки град до всеки друг. Туристическа агенция"Хамилтън" предлага нразлични туристически маршрутипо град на първата република и м– по град, вторият (всеки от тези маршрути включва посещение на всеки град на републиката точно веднъж и връщане в първоначалния град и всичко това, без да напускате републиката). Докажете, че агенция Хамилтън може да предложи не по-малко от мнподобни туристически маршрути в градове в цялата федерация.

Турнири – пълни графики.

В класа има 28 ученици. Учителят може да сменя учениците, но всеки ученик вътре учебен денседи със същия ученик. След какъв минимален брой дни всеки ученик ще може да седне един до друг?

Сборът от 1000 реални числа е 0. Докажете, че най-малко 999 сбора по двойки на тези числа са неотрицателни.

Има 25 камъка в една купчина. Разделя се на две части, след което една от частите отново се разделя на две и т.н., докато получите 25 отделно лежащи камъка. Всеки път, когато една от купчините се разделя на две части, произведението от броя на камъните в тези части се записва на дъската. Докажете, че накрая сборът от всички числа на дъската ще бъде равен на 300.

В училището се обучават 1996 деца. Всеки от тях харесва точно кот останалите 1995 студенти. На какви стойности кможем ли да кажем, че определено ще има двама ученика от това училище, които или двамата се харесват, или и двамата не се харесват?

Астрономът наблюдава 50 звезди, като сумата от разстоянията по двойки между тях е равна на S. Издигна се облак и скри 25 звезди. Докажете, че сумата от разстоянията по двойки между видимите звезди е по-малка от S/2.

В държава с 25 града три авиокомпании искат за всяка двойка градове всички директни полети между тези градове да се изпълняват само от една от авиокомпаниите, но всяка авиокомпания може да превозва пътници от който и да е град до всеки друг със кацане в повече от един междинен град. Докажете, че е осъществимо.

Комисията се състои от 49 души. Във всяко заседание участват точно трима членове на комисията. Възможно ли е да се планира работата на една комисия така, че всеки двама членове на комисията да се събират на заседания точно веднъж?

МИНИМАЛНА СВЪРЗАНОСТ.

В град N можете да пътувате от всяка метростанция до която и да е друга (възможно с прекачване). Докажете, че една от метростанциите може да бъде затворена за ремонт без право на пътуване през нея, така че от всяка от останалите станции да е възможно да се пътува до всяка друга.

Докажете, че във всяка свързана графа можете да премахнете връх заедно с всички ребра, идващи от него, така че да остане свързан.

В група от няколко души някои хора се познават, а други не. Всяка вечер един от тях организира вечеря за всичките си приятели и ги запознава един с друг. След като всеки беше домакин на поне една вечеря, се оказа, че някои двама души все още не се познават. Докажете, че няма да могат да се срещнат и на следващата вечеря.

В дадена държава има 30 града и всеки град е свързан с всеки по шосе. Кой е най-големият брой пътища, които могат да бъдат затворени за ремонт, така че човек да може да пътува от всеки град до всеки, евентуално преминавайки през други градове?

Модел на десетоъгълник се прави от тел, от един връх на който са изчертани всички диагонали. Двама души се редуват да хапват една жица. Победител е този, след чийто ход моделът първи се раздели на две части. Кой кога печели правилна игра: този, който върви първи, или неговият партньор?

Първоначално на всяко поле от дъската 1n има пул. Първият ход е да преместите произволен пул в съседна клетка (една от две, ако пулът не е на ръба), така че да се образува колона от два пула. След това, в следващия ход, всяка колона може да бъде преместена във всяка посока с толкова клетки, колкото има пулове в нея (в рамките на дъската); Ако колона попадне върху непразна клетка, тя се поставя върху колоната, която стои там, и се слива с нея. Докажете, че с n-1 хода можете да съберете всички пулове на едно поле.

Има 101 кутии консерви с маси 1001 г, 1002 г, ..., 1101 г. Етикетите с везните са изгубени, но на гледача изглежда, че помни коя консерва колко тежи. Той иска да се увери в това с най-малко претегляния. Има две везни: едната е прецизна, другата е груба. При едно претегляне можете да сравните две кутии. Прецизни везните винаги показват коя кутия е по-тежка, а грубите само ако разликата е повече от 1g (иначе показват равновесие). Пазачът може да използва само една везна. Кои да избере? (А. Шаповалов)

Волейболната мрежа е с формата на правоъгълник с размери 50600 клетки. Какъв е най-големият брой единични въжета (между възли), които могат да бъдат срязани, така че мрежата да не се разпадне на парчета?

Има въжена мрежа под формата на квадрат 88, разделен на 11 клетки. Кое е най-дългото въже, което може да се отреже от него? (Можете да отрежете всеки край на възлите, без да нарушавате връзката на останалите, но не можете да отрежете възела така, че да не се образуват краища).

Листът от тетрадката беше оцветен в 23 цвята според клетките. Двойка цветове се нарича добра, ако има две съседни клетки, боядисани с тези цветове. Какъв е минималният брой добри чифтове?

Нека наречем лабиринт шахматна дъска 8x8, където между някои полета са вмъкнати дялове. Ако топът може да обиколи всички квадрати, без да прескача преградите, тогава лабиринтът се нарича добър, в противен случай се нарича лош. Кои лабиринти има повече - добри или лоши?

В страната има 100 града, някои от които са свързани с авиолинии. Известно е, че от всеки град можете да летите до всеки друг (евентуално с трансфери). Докажете, че можете да посетите всеки град, като не направите повече от: a). 198 полета; б). 196 полета.

На шахматна дъска, първоначално празна, се поставят пешки според следвайки правилата: Избират се всеки четири празни полета, чиито центрове са върховете на правоъгълник със страни, успоредни на страните на дъската, след което върху едно от тези полета се поставя пешка. След това се избират подобни четири празни клетки, върху една от тях отново се поставя пешка и т.н. Какъв е най-големият брой пешки, които могат да бъдат поставени на дъската, следвайки тези правила?

Домакинята опече баница за гостите. На масата може да има p или q души. За какво минимално количествопарчета (не непременно равни), трябва да нарежете пая предварително, така че във всеки случай да може да се разпредели по равно между гостите, ако: а). p и q са взаимно прости; б). имат ли p и q най-голям общ делител d?

Тайният обект представлява квадрат с размери 88 в план, разделен от коридори на 11 квадрата. Във всеки връх на такъв квадрат има превключвател. Щракването на превключвателя незабавно засяга всички метрови коридори, излизащи от този връх, променяйки осветлението им на обратното. Пазачът е в ъгъла на напълно неосветен обект. Той може само да ходи по осветени коридори и да превключва превключвателите произволен брой пъти. Може ли един пазач да гарантира, че може да премине от който и да е ключ към който и да е друг, без да натиска ключовете?

В свързана графика 2 н върхове и всички те са от степен 3. Докажете, че е възможно да изберете този начин н+1 ребро, така че правилното оцветяване в 3 цвята на избраните ребра еднозначно определя правилното оцветяване в 3 цвята на всички ребра на графа (оцветяването е правилно, ако две ребра с общ връх имат различни цветове).

БИПАРИТНИ ГРАФИ.

Докажете, че даден граф е двуделен тогава и само тогава, когато всички цикли в него са четни.

Докажете, че едно дърво (свързан граф без цикли) е двуделен граф.

В определена група хора всеки има един враг и един приятел. Докажете, че тези хора могат да бъдат разделени на две компании, така че във всяка компания да няма нито врагове, нито приятели.

В руското първенство по футбол участват 16 отбора. В първия кръг всички отбори изиграха по един мач. Във втория кръг всички отбори също изиграха мач. Докажете, че е възможно да идентифицирате 8 отбора, така че нито един от тях да не играе помежду си.

Върху лист карирана хартия има определен краен набор M от възли. Винаги ли е възможно да оцветите някои точки от множеството M в бял цвят, а останалите - в червено, така че на всяка линия на мрежата разликата между броя на белите и червените възли по абсолютна стойност да не надвишава 1? (IMO, 1986)

На самолета са дадени 1997 точки. Двама души се редуват, свързвайки тези точки с отсечки, като една отсечка не може да бъде начертана два пъти. Губещият е този, чийто ход първо създава затворена прекъсната линия с нечетен брой връзки. Кой ще спечели, ако се играе правилно?

Взехме 10 точки на кръга. Какъв е най-големият брой сегменти с краища в тези точки, които могат да бъдат начертани така, че нито три от тези сегменти да не образуват триъгълник с върхове в тези точки?

В село Мартишкино всяко момче, всички момичета, които познава, се познават. Всяко момиче познава повече момчета, отколкото момичета сред приятелите си. Докажете, че в Мартишкино живеят не по-малко момчета, отколкото момичета.

Хидрите се състоят от глави и шии (всяка шия свързва точно две глави). С един удар на меча можете да отрежете всички шии, излизащи от някоя глава А на хидрата. Но в същото време от главата на А една шия моментално прераства във всички глави, с които А не е свързана. Херкулес побеждава хидрата, ако успее да я разреже на две части, които не са свързани с вратовете си. Намерете най-малкото N, при което Херкулес може да победи всяка стоврата хидра с не повече от N удара. (РосОл, 2002)

В компания от 2n+1 души за всеки n души ще има човек, различен от тях, който познава всеки от тях. Докажете, че в тази компания има човек, който познава всички. (РосОл, 2002)

ПЛОСКИ ГРАФИКИ.

В една равнина има 5 точки, нито три от които не лежат на една права. Докажете, че някои четири от тях лежат във върховете на изпъкнал четириъгълник.

В една равнина има 5 кръга, всеки два от които се пресичат. Докажете, че всеки три от тях имат обща точка.

На равнината има 6 точки (3 сини и 3 червени), нито три от които не лежат на една права линия. Докажете, че някои 2 сини и 2 червени точки лежат във върховете на изпъкнал четириъгълник.

Върху карирано поле има пълен комплект домино (всяко домино заема 2 квадрата). Да се ​​обадим регионмного клетки, които са били ударени същите числадомино. Да се ​​обадим в района връзкар, ако от някоя негова клетка куц топ може да влезе във всяка друга. Какъв е най-големият брой свързани зони, които могат да бъдат на терена?

ЧАСТИЧНА ПОРЪЧКА.

В класа има 12 момичета и 12 момчета, всички с различен ръст. По време на урока по физкултура те бяха подредени в две линии (една зад друга): момчета - по ръст от ляво на дясно, а момичета - по ръст от дясно на ляво. Тогава по-високият беше извикан от всяка двойка момче-момиче. Докажете, че сте повикали дванадесетте най-добри ученици.

Дадени са няколко различни естествени числа. Известно е, че от всеки три от тях могат да бъдат избрани две, така че едното да се дели на другото. Докажете, че всички числа могат да бъдат оцветени в два цвята, така че за всеки две числа от един и същи цвят едното да се дели на другото.

Докажете, че от 17 различни естествени числа или има 5 числа a, b, c, d, e, така че всяко от числата от тази петица, с изключение на последното, се дели на числото зад него, или има пет такива числа, че никое от тях не се дели на другото.

Числата 1, 2, 3, ..., 101 са подредени в редица в някакъв ред. Докажете, че винаги можете да задраскате 90 числа от тази серия, така че останалите 11 да са подредени във възходящ или низходящ ред.

АЛГОРИТМИ.

Докажете, че върховете в обхващащото дърво могат да бъдат оцветени в шахматен ред.

В група от хора всеки познава някого. Докажете, че тази група може да се раздели на две, така че всеки човек да има познат от другата група.

В селото някои къщи са свързани с жици. Съседите са двама души, чиито къщи са свързани с жици. Винаги ли ще бъде възможно да поставите по един човек във всяка къща - лъжец или рицар - така че всеки да може да отговори на въпроса: „Има ли лъжци сред вашите съседи?“ – отговори положително. (Всеки знае за всеки свой съсед, независимо дали е лъжец или не).

Докажете, че във върховете на полиедър може да се постави цели числатака че във всеки два върха, свързани с ребро, има числа, които не са взаимно прости, а във всеки два върха, несвързани с ребро, има взаимно прости числа.

IN Порт Приключение 16 тайни агенти бяха изоставени. Всеки от тях следи някой от колегите си. Известно е, че ако агент Аследи агента IN, след това агентът INне следва агента А. Всеки 10 агента могат да бъдат преномерирани по такъв начин, че първият да наблюдава втория, вторият – третия, ..., десетият – първия. Докажете, че някои 11 агенти могат да бъдат номерирани по същия начин.

При какво нможете да оцветите всички ръбове н-въглеродна призма (основа – н-gons) в три цвята, така че във всеки връх ръбовете на трите цвята да се срещат и всяко лице (включително основите) има ръбове на трите цвята?

А). Докажете, че върховете на 3n-ъгълна призма могат да бъдат оцветени с три цвята, така че всеки връх да е свързан с ребра с върхове и от трите цвята. б). Докажете, че ако върховете на n-ъгълна призма могат да бъдат оцветени с три цвята, така че всеки връх да е свързан с ръбове с върхове от трите цвята, тогава n се дели на 3.

"АНТИГРАФ".

В компания от 2n+1 души за всеки n души ще има човек, различен от тях, който познава всеки от тях. Докажете, че в тази компания има човек, който познава всички.

ГРАФИКИ И ПОЛИНОМИ.

Дадено е естествено число к и полиноми Р(х) И С(х) с цели коефициенти. Известно е, че за всяко цяло число хномер Р(С(х)) – хразделена на к. Докажете, че числото С(Р(х)) – хсъщо се дели на кза всяко цяло х.

Има ли четири полинома, така че сборът от всеки три от тях да има поне един корен, а сборът от всеки два да няма корени?

ЦИКЛИЧНОСТ.

IN цветен град 2000 шорти на живо. Всеки късец дава подарък на всеки свой приятел всеки ден. За да избегнете разруха, подаръкът може да бъде даден допълнително, но не и на човека, който ви е дал подаръка. Знайка изчисли, че нито един от подаръците, които му е подарил в петък, не може да му бъде върнат по-рано от следващия петък. Докажете, че някой нисък човек има не повече от 13 приятели. (Е. Черепанов)

В щата има 100 града. Някои двойки градове са свързани с пътища с поне четири циклични маршрута. Докажете, че има цикличен маршрут, минаващ през не повече от 51 града.

В страната има 100 града, някои двойки градове са свързани с пътища, като общо пътищата са 200. Оказа се, че всеки цикличен маршрут има дължина поне пет. Докажете, че има два несвързани циклични маршрута.

В сградата на Московския университет има много асансьори и всеки асансьор превозва пътници само между два етажа (но на всеки етаж можете да отидете до всеки асансьор, който спира на него). Известно е, че можете да пътувате от всеки етаж до всеки друг четен бройасансьори и без да минавате два пъти през всеки етаж. Докажете, че ако желаете, същото нещо може да се направи с нечетен брой асансьори.

В страната на Оз има няколко замъка, от всеки от които има три пътеки. Скитащият рицар напуснал замъка на предците си и тръгнал на пътешествие из страната. Рицарят обича разнообразието, така че когато стигне до следващия замък, той завива наляво всеки път, ако е завил надясно предишния път, и завива надясно, ако е завил наляво преди това. (Когато минава през първия замък по пътя си, рицарят може да се обърне във всяка посока). Докажете, че някой ден рицарят ще се върне в замъка си.

На безкрайна лента е отпечатана безкрайна редица от числа от 1 до 9. Докажете, че или някаква комбинация от числа ще се повтори 10 пъти подред, или от нея могат да се изрежат 10 стоцифрени числа в низходящ ред.

ТЕОРЕМА ЗА ЧЕТНОСТТА НА БРОЯ НА НЕЧЕТНИТЕ ВЪРХОВЕ.

Върховете на изпъкнал многостен, чиито лица са триъгълници, бяха боядисани в три цвята. Докажете, че броят на лицата, чиито три върха са с различни цветове, е четен.

Брой ребра.

Върху бял лист карирана хартия нарисувайте квадрат с размери 1212. Две клетки се считат за съседни, ако имат обща страна. Саша рисува клетка по клетка, като въвежда във всяка боядисана клетка номера на нейните предварително боядисани съседи. Какъв ще бъде сборът на всички числа, когато всички клетки са оцветени? (А. Шаповалов)

Нарисувахме безкраен лист карирана хартия, с изключение на квадрат 77. В този квадрат Вася оцвети клетка, в която е оцветена точно една съседна (отстрани) клетка, след това друга клетка, в която сега е оцветена точно една съседна клетка и т.н. Който най-голямото числоМоже ли Вася да рисува клетките по този начин?

При какво н>1 може да се случи, че във фирма от н+1 момичета и нмомчета, с които всички момичета са запознати различни числамомчета и всички момчета с еднакъв брой момичета?

СМЕС.

Присъства на някаква среща н Човек. Известно е, че всеки двама познати нямат общи познати, а всеки двама непознати имат точно двама общи познати. А). Докажете, че всички присъстващи имат еднакъв брой познати. б). При какво нвъзможно състояние на проблема?

В града на "Разнообразието" живеят 10 000 жители, всеки двама от които са или враждуващи, или приятели помежду си. Всеки ден не повече от един жител на града може да „стартира нов живот“, т.е. карайте се с всичките си приятели и се сприятелявайте с всичките си врагове; Освен това всеки трима жители могат да станат приятели помежду си. Да докаже, че всички жители без изключение могат да се сприятеляват помежду си. Какъв е най-малкият брой дни, който е вероятно да е достатъчен за това?

кИ н– естествени числа по-големи от 1. В група от кнвсеки човек е запознат с повече от ( к–1)нот останалите. Докажете, че можете да избирате к+1 човек, така че всички да се познават. ( Полска олимпиада, 68)

На равнината са отбелязани 100 точки. Двама души играят и се редуват. С един ход можете да свържете две точки със стрелка, ако не са били свързани преди. В този случай е забранено да се рисува стрелка, след което ще бъде възможно да се стигне от всяка точка с помощта на стрелките до всяка друга. Този, който не може да направи друг ход, без да наруши правилата, губи. Кой печели, ако играта се играе правилно: този, който е първи или неговият партньор? ( ДА. Ростовски)

В едностранния окръг има еднопосочни пътища между някои (но за съжаление не всички) имоти. Освен това, когато има нов път(също с еднопосочен трафик) между имоти, които преди не са били свързани с път, се оказва, че можете да стигнете от всяко имение до всяко друго, без да нарушавате правилата. Докажете, че такава възможност съществува сега. ( ДА. Ростовски; Санкт Петербург, град 2000 г)

Срещна няколко приятели. Всеки от тях се ръкува с всички, с изключение на Федот Бурчеев, който, тъй като не е настроен, се ръкува с едни, а с други не. Бяха направени общо 197 ръкостискания. Колко ръкостискания направи Федот? ( И.С. Рубанов)

В страната има 100 града и всеки град има поне един път. Докажете, че е възможно да затворите няколко пътя, така че все още да има поне един път, водещ от всеки град, и в същото време най-малко 67 града имат точно един път, водещ от тях. ( Е.А. Гирш, С.В. Иванов, Д.В. Карпов)

Училището разполага с 40 класни стаи, които се отварят с 5 ключа различни видове, а броят на ключовете от различните типове е различен. Всичките 40 ключа бяха заключени в стаите, така че във всяка стая имаше един ключ, който не можеше да се използва за отваряне на тази стая. Пазачът Сергеев има дубликат на ключ от една от стаите. Докажете, че може да отвори всички стаи. ( )

Училището разполага с 40 класни стаи, които се отварят с 4 различни вида ключове. Всичките 40 ключа бяха заключени в стаите, така че във всяка стая имаше един заключен ключ, който не можеше да се използва за отваряне на тази стая. Пазачът Сергеев знае къде е всеки ключ. Докажете, че пазачът Сергеев може да направи дубликати на ключове за два офиса, с които можете да отворите всички стаи. ( Р.А. Исмаилов, С.Л. Берлов, Д.В. Карпов)

(С. Берлов, СПб, гр., 2001, 6-1) На изложбата на котки 19 котки и 10 мъжки котки седяха в редица, а до всяка котка седеше котка, която беше по-дебела от нея. Докажете, че до всяка котка е седяла котка, която е по-слаба от него.

(С. Берлов) Квадратният континент е разделен на 19 държави под формата на изпъкнали многоъгълници и няма точки, в които границите на четири или повече държави. От всеки три граници, които се събират в една точка, една е затворена, а две са отворени за пътуване. Докажете, че е невъзможно да обиколите всички тези страни, като посетите всяка от тях веднъж и се върнете в първоначалната страна.

В страната Фалкерсония някои градове са свързани с авиокомпании и е невъзможно да стигнете от град А до град Б с по-малко от десет прекачвания. Докажете, че всички авиокомпании могат да бъдат продадени на 11 авиокомпании по такъв начин, че всеки маршрут от А до Б да минава по линии, притежавани от всички 11 компании. (Фолклор, 100)

Всеки ученик от класа участва в два клуба, като за всеки трима ученика има клуб, в който ходят заедно. Докажете, че има клуб, в който учат всички ученици. (Олимпиада ДалФО 2001, 104)

. Десет души дойдоха на гости в галоши. Тръгнаха един по един и всеки си сложи произволен чифт галоши, в които можеше да влезе (т.е. не по-малък от неговия). Кой е най-големият брой хора, които не могат да си сложат галоши?

IN приказна страна Perra Terra, наред с други обитатели, е дом на карабаси и барабаси. Всеки Карабас познава шест Караба и девет Бараба. Всеки барабан е запознат с десет карабаса и седем барабана. Кой е по-многоброен в тази страна - Карабас или Барабас?

В група от 100 души сред всеки трима има човек, който познава и двамата. Докажете, че от тази група можете да изберете компания от 50 души, в която всички се познават. (С. Берлов)

В клуба дойдоха 20 господа: някои с шапки, други без. Тогава от време на време някой от господата сваляше шапката си и я слагаше на главата на друг господин, който в този момент нямаше шапка. Един час по-късно 10 господа казаха: „Подарявах шапка по-често, отколкото получавах!“ Колко господа дойдоха в клуба с шапки? ( SLB, Yu.M. Лифшиц; СПб-02)

В определена компания има повече от 10 души, като броят на познатите на всеки човек се дели на 10. Докажете, че има поне 11 души с същата сумапознати ( SLB базиран в Молдова)

На олимпиадата бяха предложени 8 (6) задачи. Всеки участник реши точно 3 от тях и двама участници не решиха повече от една обща задача. Какъв е най-големият брой участници на олимпиадата? ( Балтийски път, 01)

За фирма от нчовек изпълнява следното условие: ако всеки 2 души имат равен брой познати, то всеки от останалите се познава точно с един от тях. При какво нвъзможно ли е? ( Балтийски път, 2000 г)

На партито дойдоха 19 гости. Сред всеки 3 от тях има 2 познати. Докажете, че гостите могат да бъдат разделени на 5 групи, във всяка от които всеки се познава по двойки. ( В. Л. Долников, SLB, SVI)

(фолклор) В страната има няколко града и няколко еднопосочни пътя. Всеки път свързва два града и не минава през останалите. В същото време, без значение кои два града вземете, можете да шофирате от поне единия до другия, без да нарушавате правилата за движение. Докажете, че има град, от който можете да шофирате до всеки друг, без да нарушавате правилата за движение.

Сред 11 души всеки двама имат точно един общ приятел. Докажете, че поне един от тях познава всички останали.

(Лапок) Сред 5 души всеки двама имат точно един общ приятел. Докажете, че поне един от тях познава всички останали.

(журибазирани на класически факти) В страната има 120 града. Някои двойки градове са свързани с пътища, които не минават през други градове. Всеки град има поне три пътя. Докажете, че има несамосичащ се цикличен маршрут, състоящ се от най-много 11 града.

(Ю.М. Лифшиц) В страната Юрланд някои градове са свързани с пътища (без да минават през други градове) и от всеки град можете да стигнете до всеки друг. Един злополучен ден зло племе от субчици превзе определен град. Всеки следващ ден субчиките или превземат град, съседен на един от превзетите, или освобождават превзет град, всички съседни са заловени. Освен това нито един град не е превзет повече от веднъж. Докажете, че ако подчиците вече не могат да уловят нищо, то от всеки два съседни града поне един е бил заловен.

(Ю.М. Лифшиц) 14 членове на журито присъстваха на банкета и изпиха 17 бутилки лимонада. Четирима членове на журито изпиха всяка бутилка лимонада. Докажете, че има двама членове на журито, които не са пили лимонада от една бутилка.

(фолклор) Всеки от 7-те члена на екипа има не повече от двама близки приятели. Веднъж в една и съща стая, двама близки приятели започват да чатят непрекъснато и цялата работа в тази стая спира. Докажете, че три стаи са достатъчни на капитана, за да осигури гладкото функциониране на целия отбор.

(Ю.М. Лифшиц) 10 шахматисти играха еднокръгов турнир и всеки спечели, загуби и завърши наравно по 3 партии. Известно е, че няма трима шахматисти, които да са отбелязали точно 1 точка в мачове един срещу друг. Докажете, че всичките десет шахматисти могат да бъдат поставени в кръг, така че всеки от тях да победи стоящия отдясно. За победа в шахмата се дава 1 точка, за равенство се дават 0,5 точки, а за загуба - 0 точки.

(Ю.М. Лифшиц) 10 шахматисти играха еднокръгов турнир и всеки спечели и загуби по 4 партии и завърши една игра наравно. Докажете, че можете да изберете трима шахматисти и да ги поставите в кръг, така че всеки от тях да победи този, който стои отдясно.

Октоподите живеят в Морето на дъждовете, всеки с един или двама приятели. Когато слънцето изгря, всички онези октоподи, които имаха двама приятели, станаха сини, а всички, които имаха един приятел, станаха червени. Оказа се, че всеки двама приятели са с различни цветове. След това 10 сини октопода бяха пребоядисани в червено и в същото време 12 червени октопода бяха пребоядисани в червено. Син цвят, след което всеки двама приятели станаха с един и същи цвят. Колко октоподи има в Морето на дъждовете?

В двора има 12 стълба. Електротехникът Петров получи задачата да свърже стълбовете с проводници по такъв начин, че всеки проводник да свързва точно два полюса, два полюса да не се свързват два пъти и най-важното, че за всеки четири полюса да има точно три опънати проводника тези стълбове. Докажете, че електротехникът Петров няма да се справи с тази задача.

Всеки от 24-те души познава поне 11 от останалите. Винаги ли е възможно да ги настаним в двойни хотелски стаи, така че всеки да бъде настанен при някой познат?

Планетата Тор има формата на поничка. На него има 5 града. Възможно ли е да свържем всяка двойка от тези градове с пътища, така че пътищата да не се пресичат никъде?

На остров Нова Вавилония се говорят 45 езика, като всеки жител знае поне пет от тях. Известно е, че всеки двама жители могат да водят разговор помежду си, вероятно чрез посредничеството на няколко преводачи. Докажете, че тогава всеки двама жители на острова могат да разговарят помежду си, като използват услугите на не повече от 15 преводачи.

В група от 100 души някои се познават, а всеки член на групата познава поне 20 други. Докажете, че можете да изберете 40 членове на групата и да ги разделите на 20 двойки, така че във всяка двойка хората да са познати.

На кнкартите имат числа от 1 до нпо 2 бр кведнъж всеки. Докажете, че тези карти могат да се поставят на масата така, че всяко число да е написано точно отгоре кведнъж.

В страната има 201 града, всеки с точно 10 пътя и от всеки град можете да стигнете до всеки друг. Докажете, че можете да изберете 20 града, два от които не са свързани с път.

В двора има няколко стълба, някои двойки са свързани с жици. Тотално разтегнато мнпроводници и тези проводници са боядисани нцветове и нито един проводник от същия цвят не излиза от който и да е полюс. Докажете, че можете да преоцветите тези жици, така че да има равен брой жици от всички цветове и пак да няма две жици от един и същи цвят от който и да е стълб. (130, Украйна 1989г)

В двора има 36 стълба, като първоначално между всеки два стълба се опъва тел. Всяка сутрин на път за училище побойникът Вася къса 35 жици. Всяка вечер електротехник Петров възстановява кабелите, излизащи от даден стълб. Докажете, че Вася може да действа по такъв начин, че една сутрин след поредния акт на вандализъм да останат по-малко от 18 жици. (135, А.В. Пастор, Санкт Петербург 2000 г)

На равнината са отбелязани 100 точки. Двама души играят и се редуват. С един ход можете да свържете две точки със стрелка, ако не са били свързани преди. В този случай е забранено да се рисува стрелка, след което ще бъде възможно да се стигне от всяка точка с помощта на стрелките до всяка друга. Този, който не може да направи друг ход, без да наруши правилата, губи. Кой печели, ако играта се играе правилно: този, който е първи или неговият партньор?

Бяха избрани няколко различни числа от числата от 1 до 100. Нека наречем индекс на делимост на дадено число броя на избраните числа, с които дадено числосе разделя изцяло. Оказа се, че всички избрани числа имат различни индекси на делимост. Какъв е най-големият брой числа, които могат да бъдат избрани?

нКръговете са подредени така, че центърът на всеки от тях да лежи точно в един от другите, а вътре във всеки от тях да лежи центърът точно в един от другите. Намерете всички числа н, в които това е възможно.

В конгреса на младите писатели участваха 22 ученици. След конгреса всеки от тях прочете творбите на трима млади писатели, присъствали на конгреса. Докажете, че е възможно да се състави комисия от 4 човека от делегатите на конгреса, така че никой от комисията да не чете трудовете на останалите членове.

Във вилата има 1999 почиващи. Някои от тях се познават, и всеки двама непознатиимат общ приятел сред почиващите. Кое е най-малкото възможно число паралетовници познавате?

На планетата има 1000 града, включително столиците на щатите. Някои градове са свързани с пътища по такъв начин, че всеки път свързва точно два града и от всеки град до всеки друг може да се стигне по пътища. Освен това, за да стигнете от една столица до друга, трябва да изминете поне 21 пътя. Докажете, че на планетата няма повече от 90 столици.

В дъската има забити 1997 пирона. Двамата се редуват да правят ходове. Ходът се състои в това, че играчът свързва два пирона, които преди това не са били свързани с тел. Губещият е този, след чийто ход става възможно за първи път да се премине през жиците от който и да е пирон до всеки друг. Кой ще спечели, ако играта се играе правилно: този, който направи първия ход, или неговият партньор?

Свързана графика Жостава свързан, когато бъдат премахнати 18 върха (заедно с всички ръбове, излизащи от тях). Да се ​​обадим разрезвсеки набор от 19 върха, когато бъде премахнат, графиката губи свързаност и парчевсеки компонент на свързаност, който се формира, когато разрезът бъде премахнат. Известно е, че всяко парче, съдържащо по-малко от 10 върха, не се съдържа в нито един разрез. Докажете, че нито едно парче не се съдържа в разреза.

Графика Жсвързан Да се ​​обадим разрезминималният набор от върхове за включване, когато се премахне (заедно с всички ръбове, излизащи от тях), графът губи свързаност. Известно е, че при премахване на изрязани върхове Рвърхове от среза Сзавършват в същия свързан компонент. Докажете, че при премахване на върховете на разрез Свърхове от среза Рзавършват в същия свързан компонент.

Върху карираната хартия има маркирани 49 точки от мрежата, подредени в квадрат 66. Какъв е минималният брой единични сегменти с краища в маркирани възли, които трябва да бъдат начертани, така че между всяка двойка съседни възли да има път не по-дълъг от 3?

Във фирма от нчовек, при който всеки познава поне един от другите, всеки има равен брой познати (смята се, че ако Ае запознат с IN, тогава INе запознат с А). Докажете, че от членовете на тази компания е възможно да избирате поне н/3 несвързани двойки познати.

В една компания всеки двама души имат точно петима общи познати. Докажете, че броят на познатите (двойки познати) е кратен на три. ( Ю.М. Лифшиц)

В единичния кръгов турнир двама участници напуснаха надпреварата след петия кръг. В крайна сметка в турнира бяха изиграни 38 партии. Тези двамата имаха ли време да играят един с друг? ( България, 1982г)

В единичния кръгов турнир шестима участници напуснаха надпреварата след шестия кръг. В крайна сметка в турнира бяха изиграни 67 партии. Докажете, че поне двама от елиминираните играчи не са играли един срещу друг. ( К.А. копче)

Какъв е най-малкият възможен брой ребра в граф със 100 върха, така че сред всеки 11 върха да има един, свързан с останалите 10 от тях? ( Р. Федоров)

В свързаната графика 2 нвърхове, степента на всеки връх е три. Докажете, че броят на начините за оцветяване на ръбовете на тази графика в три цвята, така че ръбове с различни цветове да се събират във всеки връх, не надвишава 32 н .

В някакво състояние 4 нлетища, от всяко летище тръгват точно 3 авиокомпании (една авиокомпания свързва две летища). От всяко летище можете да летите до всяко друго (възможно е с трансфери). Позволявам ДА СЕ -брой начини за продажба всичкоавиокомпании на три авиокомпании по такъв начин, че три авиокомпании на различни авиокомпании да излитат от всяко летище. Докажи това ДА СЕ 32 3 н .

Осем шахматисти изиграха турнира в един кръг. Известно е, че във всеки трима шахматисти имаше двама, които играха реми помежду си. Какъв е най-малкият брой равенства, които могат да се случат в този турнир?

В върховете на квадрата има 4 компютъра, свързани със своите съседи от страните на квадрата. В началния момент всеки компютър получи важна новина (всеки със своята). Всяка секунда компютърът може или да предава всички новини, които знае, на съседен компютър, или да получава подходяща информация от съседен компютър, или да не прави нищо. Как за най-малко времемогат ли всички компютри да получават всички новини, налични в системата?

В страната на Еления нжители. Обединяват се в групи по интереси. Във всеки кръг има точно трима души и всеки двама са членове на точно един кръг едновременно. Докажи това нКогато се раздели на 6, остатъкът е 1 или 3.

Пристигнахме в лагера ммомчета и дмомичета. Всяко момиче познава не повече от 10 момчета, а всяко момче познава не по-малко от едно момиче. Оказа се, че всяко момче познава повече момичета, отколкото всяко момиче, което познава, познава момчета. Докажи това д 1.1 м. (Д.В. Карпов)

Дайте пример за четиринадесетстранна структура, всяко лице на която е или квадрат, или правилен триъгълник? (ДА. Крамаренко)

В пространството има 2000 черни точки, нито четири от които не лежат в една и съща равнина. Някои от точките са свързани със стрелки. Известно е, че няма път, който да следва стрелките и да минава през всички точки (дори и да е възможно да се премине през една точка няколко пъти). Докажете, че някои от точките (поне една, но не всички) могат да бъдат преоцветени в синьо, така че нито една стрелка да не води от синята точка към черната. ( Беларус, 1992 г)

Графиката има обхващащо дърво с точно нвисящи върхове и покриващо дърво точно с мвисящи върхове, н  к  м. Докажете, че тази графика съдържа обхващащо дърво с точно квисящи върхове.

В компания от 200 души могат да бъдат затворени петима кръгла масатака че всеки от тях да седи между двама познати (предполага се, че ако Ае запознат с б, Че бе запознат с А). Какъв е най-малкият брой двойки познати, които може да има в тази компания?

Докажете, че всеки полиедър може да има две червени лица, а другите две сини, така че червените лица да имат равни страни и сините също.

В свързана графика 3 квърхове, всички те имат степен 3, като всеки връх е включен в точно един триъгълник. Някои ръбове на графа бяха премахнати, така че се получи дърво. Докажете, че това дърво има най-много к+2 върха от степен 1.( Д.В. Карпов)

В кралството нградове и rпътища (всеки път свързва два града и от всеки град можете да стигнете до всеки един по пътищата). Пратениците живеят в градовете. В началото на всяка година един от градовете изпраща пратеник до всички съседни (т.е. свързани с него чрез пътища) градове. (Такъв град трябва да има достатъчен брой пратеници за това.) След няколко (повече от нула) години всеки град имаше същия брой пратеници, както първоначално. Какъв е най-малкият брой пратеници, които едно кралство може да има? ( И.И. Богданов)

Даден е график, чиято степен на всеки връх е най-малко к(Където к2). Докажете, че тази графика съдържа най-малко прост цикъл с дължина к+1. ()

В една банда терористи всеки подозира поне 10 други в предателство.. Докажете, че в тази банда е възможно да идентифицирате поне 11 терористи и да ги номерирате така, че първият да заподозре втория, вторият, третият, ..., предпоследният подозира последния, а последният подозира първия. ( базиран наKözepiskolai Matematikai Lapok)

В една графика всеки два прости цикъла с нечетна дължина нямат общи ръбове. Докажете, че върховете на този график могат да бъдат оцветени в два цвята, така че всеки връх да е свързан с ребро с най-много един връх от същия цвят.( S.L. Берлов)

В страната има 100 града. Някои двойки градове са свързани с пътища, но нито един град не е свързан с всички тях. Можете да стигнете от всеки град до всеки друг, като посетите не повече от един град по пътя. Какъв е най-малкият брой пътища, които тази страна може да има? ( )

В страната има 25 града. Някои двойки градове са свързани с пътища, но нито един град не е свързан с всички тях. Можете да стигнете от всеки град до всеки друг, като посетите не повече от един град по пътя. Докажете, че в тази страна има поне 35 пътя. ( Közepiskolai Matematikai Lapok)

В страната има 9 града. Някои двойки градове са свързани с пътища, но нито един град не е свързан с всички тях. Можете да стигнете от всеки град до всеки друг, като посетите не повече от един град по пътя. Може ли тази държава да има не повече от 13 пътя?( S.L. Берлов, Д.В. Карпов, базиран на Közepiskolai Matematikai Lapok)

Степени на всички върхове на графа Жпо-малко (къде н> 2), и сред всички н+ 1 има два несъседни върха. Да се ​​обадим блокмного от нпо двойки съседни върхове на графа Ж.Известно е, че всеки два блока имат общ връх. Докажете, че всички блокове имат общ връх.( S.L. Берлов)

Ребра на пълна графа с нвърховете са боядисани в няколко цвята, а цветовете са не по-малко от н. Докажете, че има три върха, всички ръбове между които са оцветени в различни цветове. ( П.А. Кожевников)

Ребра на пълна графа с нвърховете са боядисани в няколко цвята по такъв начин, че всеки цвят да се среща най-много н- 2 пъти. Докажете, че има три върха, всички ръбове между които са оцветени в различни цветове.( AMM)

В колоната Жнабори от избрани върхове С 1 , С 2 , С 3 със 100 върха всеки. Известно е, че когато всички върхове на който и да е от тези три набора (и всички ребра, идващи от тях) бъдат премахнати, останалите върхове на графа се разделят на точно два свързани компонента и когато бъдат премахнати 99 върха, графът остава свързан. Докажете, че всички тези, които не са включени в комплектите С 1 , С 2 и С 3 върхове на графа Жмогат да бъдат разделени на 6 групи по такъв начин, че върховете на една група да завършват в един и същ свързан компонент, когато върховете на който и да е от наборите се премахнат от графиката С 1 , С 2 или С 3 .(Д.В. Карпов)

Крал Горох има 20 придворни. Плетейки интриги един срещу друг, те създадоха редица тайни общества. Шефът на тайната полиция, изучавайки тези общества, откри три модела. Първо, за всеки две тайни общества, всички придворни, които са едновременно членове на двете общества, образуват тайно общество. Второ, за всеки две тайни общества всички придворни, които са членове на поне едно от тях, образуват тайно общество. Трето, за всяко тайно общество всички придворни, които не са част от него, образуват тайно общество. Може ли да е точно 2002 г. в Pea Court? тайни общества? (Преизказване на Putnam от 1961 г)

По ръбовете на додекаедъра има числа от 1 до 30 без повторения. Нека преброим броя на прекъснатите линии, съставени от три ръба на додекаедъра и така, че числата на връзките да са във възходящ ред. Намерете минималния възможен брой такива прекъснати линии. (И.И. Богданов, Г.Р. Челноков въз основа на проблема от полската олимпиада-89/90 )

По ръбовете на куба има числа от 1 до 12 без повторения. Нека преброим броя на прекъснатите линии, съставени от три ръба на куб и така, че числата на връзките да са във възходящ ред. Намерете минималния възможен брой такива прекъснати линии. (Полша-89/90)

В компания от 20 души за всеки трима има човек, който ги познава всичките. Докажете, че има човек, който има поне девет познати. ( S.L.Berlov, I.I.Bogdanov)

В компания от 10 човека за всеки трима има човек, който ги познава всичките. Докажете, че има човек, който има поне шест познати.

На симпозиума дойдоха 100 души. От тях 15 бяха французи, всеки от които познаваше поне 70 участници в симпозиума, и 85 германци, всеки от които познаваше не повече от десет участници. Те бяха настанени в 21 стаи. Докажете, че в нито една от стаите няма нито една двойка познати. ( Ю. Лифшиц)

В дружеството има 22 състезатели. Има четиринадесет двойки спортисти, които са приятели един на друг. Оказа се, че сред всеки 11 спортисти има поне една двойка приятели. Докажете, че всеки може да бъде разделен на две футболен отбортака че всяка двойка приятели да се окаже в един отбор. ( Опростяване на проблем от Висшата лига 10)

В колона с 4 квърхове 3 кребра Известно е, че сред всеки 2 кима два негови върха, свързани с ръб. Докажете, че върховете на графиката могат да бъдат разделени на две групи от по 2 квърхове във всеки, така че да няма два върха от различни групине е свързан с ръб. (Р.А.Бруалди, С.Мелендорф)

Пиян шахматен крал никога не прави два последователни хода в една и съща посока. Започвайки от ъгъла, той обиколи карираната дъска 99, посещавайки всяко поле веднъж и се върна на първоначалното поле. Какъв е най-малкият брой диагонални ходове, които може да направи? ( S.L. Берлов въз основа на проблема на О.Ю. Ланина, Олимпиада по ФМЛ № 239, 2002 гЖ.)

В страната има 7 града, между които летят 7 самолета. Самолетът лети от всеки град до всеки друг точно 1 час и веднага след кацане може да лети до следващия град (докато транзитните пътници остават в самолета). Направете разписание на полетите, така че всеки пътник, без да сменя самолети по пътя, да може да лети от всеки град до който и да е друг не повече от 5 часа след пристигането на летището. (Олимпиада Гросман)

Петте върха на куба са боядисани в червено. Вярно ли е, че определено ще има три ръба с двата края червени?

Федя има несвързана графика. Той е всеки възможни начиниПремахнах един връх от тази графика и начертах всяка от получените графики на отделен лист, след което дадох всички тези листове на Дима. Докажете, че Дима може да възстанови оригиналната графика с помощта на тези листа. ( Д.В. Карпов, въз основа на хипотезата на Улам)

Федя има няколко кутии с топки. Редува се да изважда по една топка от кутиите, записва набор от числа на отделен лист хартия - броя на топките, останали във всяка кутия, ако има нещо останало там (без да уточнява кое число на коя кутия отговаря), и след това връща топката на мястото й. След като извади всяка топка веднъж, той дава всички листа на Дима. Докажете, че Дима може да определи колко топки има във всяка кутия. ( Д.В. Карпов)

н- нечетно число. Върховете на изпъкналите н-ъгълниците са боядисани в няколко цвята, така че всеки два съседни върха - различен цвят. Докажете, че това н-gon може да бъде разделен на триъгълници чрез непресичащи се диагонали, нито един от които няма еднакви цветни краища. ( Kurszak-1978, No2)

Дадена е графика на нвърхове. Докажете, че всички негови ръбове могат да бъдат разделени на най-много н 2/4 комплекта, всеки от които се състои от един ръб или е триъгълник. ( Богданов, Карпов)

Градовете A, B, C са свързани с полети. Между всеки два града има поне един полет и всички полети са двупосочни (ако можете да летите от А до Б, тогава същият полет може да лети от Б до А). Освен това знаем, че общият брой начини да стигнете от точка А до точка В (включително маршрути с прекачване в точка Б) е 11, а общият брой начини да стигнете от точка А до точка Б (включително маршрути с трансфер в C) е 13. Колко са директните полети между тези градове?

Като се има предвид кариран квадрат, чиято страна съдържа нвъзли Път без връщане е път по ръбове, чието пресичане с всяка хоризонтална или вертикална линия е сегмент, точка или празно множество. Какъв е най-малкият брой пътища без връщане, които могат да покрият всички върхове? ( И. Пушкарев, И. Богданов, Г. Челноков)

Даден е свързан граф, който остава свързан, когато който и да е връх бъде премахнат. Известно е, че съдържа триъгълник. Всеки връх, с изключение на един, има токен (всички токени са различни). Разрешено е да се премести фигура от връх, съседен на празен, в празен. Докажете, че като направите това, можете да получите всяка конфигурация от чипове. ( М. Мазин)

В града 10 улици минават от север на юг и 11 от запад на изток, образувайки 110 кръстовища. Със заповед на кмета всеки автобусен маршрут в града може да се движи в не повече от две посоки (изток-юг, изток-север, запад-юг или запад-север). Възможно ли е да се свържат всички кръстовища в града със седем автобусни линии? (По И. Пушкарев, И. Богданов, Г. Челноков)

Какъв е най-малкият брой върхове, които може да има изпъкнал многостен, точно три от чиито лица са петоъгълници? ( USAMTS 2003)