Кръг 6 клас
Ръководител Дмитрий Александрович Коробицин
2011/2012 учебна година
Урок 3 (08.10.2011). Градове и пътища
В някоя страна а) 6; б) 20 града, всеки два от които са свързани с път. Колко пътища има в тази държава? в) Докажете, че ако броят на градовете е n, тогава има n (n − 1) / 2 пътя. Любознателен турист иска да се разходи по улиците на Стария град от гарата (точка А на плана) до хотела си (точка Б). Той иска маршрутът му да е възможно най-дълъг, но не го интересува два пъти да бъде на едно и също кръстовище и не го прави. Начертайте на плана най-дългия възможен маршрут и докажете, че вече няма такъв.Решение.Нека променим малко правилата за точкуване: ще даваме 2 точки за победа и 1 точка за равенство. Ясно е, че след такава замяна всички условия на проблема ще бъдат запазени и всеки от участниците ще получи цяло число. Да приемем, че в този турнир има n участници. Тогава всички участници събраха общо n (n − 1) точки. Нека участниците, които са събрали равен брой точки, имат k точки, а Гоша има G точки. Тогава
n (n − 1) = k (n − 1) + G .
Обърнете внимание, че G е кратно на n − 1. Но общият брой точки може да бъде 2(n − 1) (n − 1 рунда, всеки с максимум две точки). Следователно, G = 0, n − 1 или 2(n − 1). В първия и третия случай получаваме това, което трябва да докажем, във втория получаваме n = k + 1, или k = n − 1, но тогава всички, включително Гош, отбелязаха n − 1 точки, но това противоречи на състояние на проблема.
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), се дефинира като алгебрична система.
а) За редуцираната връзка дефинирайте орграф геометрично. б) Постройте матрицата на съседство на орграфа.
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) Няколко клетки са маркирани в квадрат 6×6, така че човек може да премине от всяка маркирана към всяка друга маркирана, като минава само през общите страни на маркираните клетки. Маркирана клетка се нарича крайна, ако граничи отстрани точно с една маркирана. Маркирайте няколко клетки, така че да получите а) 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 и неговата дължина
дефиниран като сбор от теглата:
a(vi 1, vi | |
Ако в произволен
колона, теглото на всяка дъга е равно на единица, тогава дължината на пътя е равна на броя на дъгите. Проблемът за най-краткия път възниква най-често при решаването
транспортни и дискретни проблеми динамично програмиранеи т.н. Дължината на най-късия път се обозначава с 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, в която
всеки два съседни елемента са инцидентни. Пътят се нарича прост, ако среброто и всички върхове по него, с изключение на първия и последния, са различни.
Маршрутът се нарича верига, ако всичките му ръбове са различни. Маршрутът се нарича прост път, ако всички негови върхове, а оттам и ръбовете, са различни.
Цикълът в граф е път, в който началният връх съвпада с крайния връх и който съдържа поне едно ребро.
Цикълът се нарича прост, ако няма еднакви върхове, с изключение на първия и последния, т.е. ако върховете са различни.
Ако в графиката няма цикли, тогава тя се нарича ациклична.
Сега можем да дефинираме концепцията за дърво по различен начин. Свързан граф без цикли се нарича дърво.
Примери за изпълнение на задачи
1. Орграфът е даден геометрично. | ||||||||||
Изграждане | ||||||||||
разстояния. | ||||||||||
Изчислете центъра на диграфа. | ||||||||||
Здравейте, използвам този форум, за да тествам следното доказателство. Като цяло този проблем е, но чух, че учениците го решават на олимпиадата.
Задача.
В страната има 100 града, някои двойки градове са свързани с пътища. За всеки четири града има поне два пътя между тях. Известно е, че няма маршрут, който да минава точно веднъж през всеки град.
Докажете, че е възможно да изберете два града по такъв начин, че всеки от останалите градове да е свързан с път с поне един от двата избрани града.
Доказателство.
Градовете са върхове. Ребрата са пътища.
Разберете дали графиката може да бъде прекъсната. Ако компонентът е по-голям от 3, тогава избираме 2 върха от единия, един от другия и още един от третия. Оказва се, че те могат да бъдат свързани най-много с един ръб. Условието на задачата е нарушено.
Нека има два компонента, всеки от които се състои от повече от един връх. Тогава те трябва да са пълни. Ако това не е така, тогава вземаме два несъседни върха от първия, всеки два от другия. Само два града могат да бъдат свързани в такъв комплект. Противоречие. Същото и за другия компонент. Така че и двете са завършени. Е, тогава вземаме всеки един връх от първия и всеки един от втория компонент. Условието на задачата е изпълнено.
Нека сега единият компонент е само един връх със степен 0. Тогава се оказва, че другият компонент ще бъде от 99 върха. Ако повече от две ребра са премахнати от който и да е връх, тогава условието незабавно се нарушава: вземаме връх със степен 0, връх без два ребра и върхове, към които няма ребра от него (ще има 1 ребро). Това означава, че само един ръб може да бъде премахнат от всеки връх. Но ако направите това, тогава всеки връх ще има нечетна степен (преди това всеки имаше 98). И може да има само четен брой нечетни степени, така че или премахваме две ребра някъде и ограничението за 4 града се нарушава, или оставяме всички ребра и след това пълния връх.
Нека наречем градовете, от които има пътища до всички други градове, q и p.
След това доказваме чрез индукция, че за всяка свързана графа с ограничение от 4 града и r.path условието ще бъде изпълнено.
База. от 4 върха е очевидно: вземаме произволно обхващащо дърво и избираме връх в него, който е различен от лист, а вторият е лист.
Преход. Нека има граф от върхове. Тогава за всички графи, по-малки от размера, за който е изпълнено условието на проблема, всичко е доказано.
Трябва да докажем, че можем да използваме индукционната хипотеза.
Нека наречем върха, който ще бъде изхвърлен като .
Ако има графика отгоре, където за всеки 4 града трябва да има два пътя, тогава това трябва да е вярно и за градовете: ще разгледаме всички градове без един. Основното е, че графиката не губи свързаност и това винаги може да стане чрез премахване само на висящия връх, ако има такъв.
Ако се окаже, че r.path е образуван в , тогава той не може да бъде свързан с един от неговите краища (в противен случай r.path в графиката). Така че, за изтриване, това е висящ връх в обхващащото дърво. Ако се оказа, че това все още е невъзможно: той е свързан през един връх към края, който е премахнат, тогава премахваме другия. В същото време не може да се окаже, че върхът е свързан чрез един връх към двата края: това ще бъде график на 3 върха (и ако има втори път до края, тогава има r. път), но е доказано за графи повече от 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 върха.
Един път може да има един или повече върхове. Ако са повече, тогава идентифицираме целия път с единия му краен връх.
Нека наречем лявото множество - , дясното - , средното - (пътищата са компресирани във върхове).
Можем да забравим за върха: ако се окаже, че i-път има, тогава вече ще има противоречие с индукционната хипотеза.
Случай 1. Средният набор е празен. След това просто (просто по протежение на върховете) обикаляме лявото множество, започвайки от всеки връх, различен от , завършваме в , след това в p , след това веднага q, след това в и просто обикаляме десния набор. Оказа се пътека.
Случай 2. В средното множество има един връх. Всичко е същото, но от p до q минаваме през този връх.
Случай 3. Сега има върхове в средния набор 
ГРАФИКИ НА ОЙЛЕР.
Докажете, че пълен набор от домино може да бъде подреден според правилата на доминото.
„Лема за кръглите танци“.В някои компании всеки човек има точно двама приятели. Докажете, че ако всички приятели се хванат за ръце, те образуват един или повече кръгли танци.
В страната има повече от 101 града. Столицата е свързана с авиолинии със 100 града, като всеки град с изключение на столицата е свързан с точно десет града (авиокомпанията работи и в двете посоки). Известно е, че от всеки град можете да стигнете до всеки друг (може би с трансфери). Докажете, че е възможно да затворите половината от авиокомпаниите, идващи от столицата, така че да остане възможността да стигнете от всеки град до всеки.
Докажете, че свързана графа с 2n нечетни върха може да бъде начертана, като се свали моливът от хартията точно n–1 пъти и без да се начертае ребро два пъти.
От всеки град в страната тръгват 3 железопътни линии. Две компании искат да ги приватизират. Антимонополният комитет изисква пътищата на двете компании да напуснат всеки град. Докажете, че компаниите могат да се договорят помежду си, така че да бъде изпълнено изискването на Антимонополната комисия.
Дадена е свързана графа G с k ребра. Докажете, че е възможно да се изброят ребра с всички числа 1, 2, …, k, така че за всеки връх от степен най-малко две, наборът от числа, които маркират ребра от този връх, да има gcd равно на 1.
Във футболен турнир, проведен сред 20 отбора от различни градове, всеки отбор изигра по една среща у дома и не повече от две срещи като гост. Докажете, че е възможно да планирате игрите така, че всеки отбор да играе не повече от една игра на ден и целият турнир да се играе за три дни.
ГРАФИКА НА ХАМИЛТЪН.
Върху повърхността на куба е начертана затворена полилиния от осем сечения, чиито върхове съвпадат с всички върхове на куба. Какъв е най-малкият брой връзки на тази полилиния, които могат да съвпадат с ръбовете на куба?
Един куб е съставен от осем малки кубчета. Възможно ли е, излизайки от центъра на големия куб и движейки се по ръбовете на малките кубчета, да обиколите всички върхове на малките кубчета, като посетите всеки един точно по веднъж?
Дадена дъска 55. Може ли рицарят да обиколи всички клетки, като посети всяка от тях веднъж и да се върне в първоначалната си позиция?
Може ли куц крал (царят не може да се движи по диагонал) да обиколи всички клетки на шахматната дъска, започвайки от долния ляв ъгъл и завършвайки в горния десен ъгъл?
Може ли конят да направи 8 хода и да се върне на първоначалното си поле, докато посещава всички хоризонтали и вертикали на шахматната дъска?
а). Черните и белите чипове са поставени на две клетки на шахматната дъска. Позволено е да ги местите на свой ред, като всяко движение премества следващия чип във всяко свободно съседно поле вертикално или хоризонтално. В резултат на такива ходове могат ли всички възможни позиции на тези две фигури да се срещнат на дъската точно веднъж? б). И дали е позволено да местите чипове в произволен ред (не непременно на свой ред)?
Кой от следните три факта е най-"силен"?
В някои щати всеки 2 града са свързани с път. На всеки път е разрешена само една посока. Докажете, че има град, от който е възможно да обиколите целия щат, като посетите всеки град точно 1 път.
В някои държави всеки град е свързан с всеки еднопосочен път. Докажете, че има град, от който можете да стигнете до всеки друг.
Има 100 града в определен щат и всеки е свързан с всеки еднопосочен път. Докажете, че е възможно да промените посоката на движение по един път, така че да можете да стигнете от всеки град до всеки друг.
Докажете най-"силния" факт и двете следствия от него.
В еднокръгов турнир по шах всеки участник изигра по една партия с всеки. Докажете, че участниците могат да бъдат номерирани по такъв начин, че никой да не загуби директно от следващия номериран играч.
В страната има N града. Между всеки два от тях е положен път или железопътна линия. Туристът иска да обиколи страната, като посети всеки град точно веднъж и се върне в града, от който е започнал пътуването си. Докажете, че туристът може така да избере града, от който ще започне своето пътуване и маршрута, че трябва да смени вида транспорт най-много веднъж. (Всеруска олимпиада, 2003 г.)
Поредица от 36 нули и единици започва с 5 нули. Сред петте последователни числа има всички 32 възможни комбинации. Намерете последните пет цифри от редицата.
"Рицари в двора на крал Артур" - теорема на Дирак.На кръглата маса на крал Артур има 2n рицари, всеки от които има не повече от (n–1) врагове сред останалите. Докажете, че съветникът на краля Мерлин може да разположи рицарите по такъв начин, че враговете да не седят един до друг. Формулирайте теоремата на Дирак в общ вид.
На конференцията дойдоха 2n души, всеки от които познава поне n други. Докажете, че участниците могат да бъдат настанени в двойни стаи по такъв начин, че във всяка стая да живеят хора, които се познават.
Дават ви n чипа от няколко цвята и няма повече от n/2 чипа от всеки цвят. Докажете, че те могат да бъдат подредени в кръг по такъв начин, че да няма две парчета от един и същи цвят една до друга.
Във федерална държава от две републики всеки два града са свързани с еднопосочен път; в същото време, движейки се по пътищата, можете да стигнете от всеки град до всеки друг. Туристическа агенция "Хамилтън" предлага нразлични туристически маршрути из градовете на първата република и м- по градове на втория (всеки от тези маршрути включва посещение на всеки град на републиката точно веднъж и връщане в първоначалния град и всичко това, без да напускате републиката). Докажете, че агенция Хамилтън може да предложи не по-малко от мнподобни туристически маршрути през градовете на цялата федерация.
Турнирите са пълни графики.
В класа има 28 ученици. Учителят може да прехвърля ученици, но всеки ученик седи със същия ученик през учебния ден. Какъв е най-малкият брой дни, в които всеки ученик ще може да седи един с друг?
Сборът от 1000 реални числа е 0. Докажете, че най-малко 999 сбора по двойки на тези числа са неотрицателни.
Има 25 камъка в една купчина. Разделя се на две части, след което едната част отново се разделя на две и т.н., докато се получат 25 отделно лежащи камъка. Всеки път, когато една от купчините се разделя на две части, произведението от броя на камъните в тези части се записва на дъската. Докажете, че накрая сумата от всички числа на дъската ще бъде 300.
В училището се обучават 1996 деца. Всеки от тях харесва точно кот останалите 1995 студенти. На какви стойности кможе ли да се твърди, че непременно има двама ученика от това училище, които или двамата се харесват, или и двамата не се харесват?
Астрономът наблюдава 50 звезди, сумата от разстоянията между които по двойки е равна на S. Облак се вдигна и покри 25 звезди. Докажете, че сумата от разстоянията по двойки между видимите звезди е по-малка от S/2.
В държава с 25 града три авиокомпании искат за всяка двойка градове всички директни полети между тези градове да се изпълняват само от една от авиокомпаниите, но всяка авиокомпания може да доставя пътници от всеки град до всеки друг със кацане в не повече от един междинен град. Докажете, че може да се направи.
Комисията се състои от 49 души. Във всяко заседание участват точно трима членове на комисията. Възможно ли е да се планира работата на комисията така, че всеки двама членове на комисията да се събират на заседания точно веднъж?
МИНИМАЛНА СВЪРЗАНОСТ.
В град N от всяка метростанция можете да отидете до всяка друга (възможно е с прекачване). Докажете, че една от метростанциите може да бъде затворена за ремонт без право на преминаване през нея, така че човек да може да стигне от всяка от останалите станции до всяка друга.
Докажете, че във всеки свързан граф е възможно да се премахне връх заедно с всички ребра, излизащи от него, така че той да остане свързан.
В група от няколко души някои хора се познават, а други не. Всяка вечер един от тях организира вечеря за всичките си приятели и ги запознава един с друг. След като всеки си уреди поне по една вечеря, се оказа, че някои двама все още не се познават. Докажете, че на следващата вечеря те също няма да могат да се срещнат.
В една държава има 30 града и всеки град е свързан с всеки път. Какъв е максималният брой пътища, които могат да бъдат затворени за ремонт, за да може да се пътува от всеки град до всеки, евентуално преминавайки през други градове?
От тел е направен модел на единадесетстранен триъгълник, от единия връх на който са изчертани всички диагонали. Двамата се редуват да ядат тел по тел. Победител е този, след който моделът пръв се раздели на две части. Кой печели, когато се играе правилно: този, който се движи първи, или неговият партньор?
Първоначално има пул на всяко поле на дъската 1n. Първият ход има право да премести всеки пул в съседна клетка (един от двата, ако пулът не е на ръба), така че да се образува колона от два пула. След това, със следващия ход, всяка колона може да бъде преместена във всяка посока с толкова клетки, колкото пулове има в нея (в рамките на дъската); ако колоната попадне на непразна клетка, тя се поставя върху стоящата там колона и се слива с нея. Докажете, че при n-1 хода е възможно да се съберат всички пулове на една клетка.
Има 101 кутии консерви с тегло 1001 г, 1002 г, ..., 1101 г. Етикетите с грамажи са загубени, но на отговорника по доставките изглежда, че помни коя консерва колко тежи. Той иска да провери това с най-малко претегляния. Има две пан везни: едната е точна, другата е груба. Две кутии могат да бъдат сравнени с едно претегляне. Точните везни винаги показват кой буркан е по-тежък, а грубите - само ако разликата е повече от 1g (иначе показват равновесие). Мениджърът по доставките може да използва само една везна. Кое да избере? (А. Шаповалов)
Волейболната мрежа има формата на правоъгълник с размер 50600 клетки. Какъв е най-големият брой единични въжета (между възли), които могат да бъдат срязани, така че мрежата да не се счупи на парчета?
Има въжена мрежа под формата на квадрат 8x8, разделен на клетки 1x1. Кое е най-дългото въже, което можете да изрежете от него? (Всеки край може да бъде отрязан от възли, без да се прекъсва връзката на другите, но не можете да отрежете възел, така че да не се образуват краища).
Листът от тетрадката беше боядисан в 23 цвята по клетки. Двойка цветове се нарича добра, ако отстрани има две съседни клетки, изпълнени с тези цветове. Какъв е минималният брой добри чифтове?
Нека наречем лабиринт шахматна дъска 8x8, където между някои полета са вмъкнати дялове. Ако топът може да обиколи всички квадрати, без да прескача прегради, тогава лабиринтът се нарича добър, в противен случай се нарича лош. Кои лабиринти са повече - добри или лоши?
В страната има 100 града, някои от които са свързани с авиолинии. Известно е, че от всеки град можете да летите до всеки друг (евентуално с трансфери). Докажете, че е възможно да посетите всеки град, като направите най-много: a). 198 полета; б). 196 полета.
На шахматна дъска, първоначално празна, пешките се поставят по следните правила: избират се всеки четири празни клетки, чиито центрове са върховете на правоъгълник със страни, успоредни на страните на дъската, след което се поставя пешка на една от тези клетки. След това се избират подобни четири празни клетки, върху една от тях отново се поставя пешка и т.н. Какъв е най-големият брой пешки, които могат да бъдат поставени на дъската, следвайки тези правила?
Домакинята опече торта за гостите. На масата може да има p или q души. Какъв е минималният брой парчета (не непременно равни), на които тортата трябва да се нареже предварително, за да може във всеки случай да се разпредели по равно между гостите, ако: а). p и q са взаимно прости; б). p и q имат най-голям общ делител d?
Тайният обект е квадрат с размери 8x8 в план, разделен от коридори на квадрати 1x1. Във всеки връх на такъв квадрат има превключвател. Щракването върху превключвателя действа незабавно върху всички метрови коридори, излизащи от този връх, променяйки тяхното осветление на противоположните. Пазачът е в ъгъла на напълно неосветен обект. Той може само да ходи по осветени коридори и да превключва превключвателите произволен брой пъти. Може ли пазачът да му позволи да премине от всеки превключвател към който и да е друг, без да натиска превключвателите?
В свързана графика 2 н върхове и всички те са от степен 3. Докажете, че е възможно да се избира н+1 край, така че правилното 3-оцветяване на избраните ръбове уникално определя правилното 3-оцветяване на всички ръбове на графиката (оцветяването е правилно, ако две ребра с общ връх имат различни цветове).
ДВУДАЛНИ ГРАФИ.
Докажете, че даден граф е двуделен тогава и само тогава, когато всички цикли в него са четни.
Докажете, че едно дърво (свързан граф без цикли) е двуделен граф.
В определена група хора всеки има един враг и един приятел. Докажете, че тези хора могат да бъдат разделени на две компании, така че всяка компания да няма нито врагове, нито приятели.
В руското първенство по футбол участват 16 отбора. В първия кръг всички отбори играха по един мач. Във втория кръг всички отбори също изиграха мач. Докажете, че е възможно да се назоват 8 отбора така, че двама от тях да не играят помежду си.
Някакво крайно множество M от възли е отбелязано върху лист карирана хартия. Винаги ли е възможно някои точки от множеството M да бъдат оцветени в бяло, а останалите в червено, така че на всяка линия на мрежата разликата между броя на белите и червените възли да не надвишава 1 по абсолютна стойност? (IMO, 1986)
На самолета се дават 1997 точки. Двама души се редуват, свързвайки тези точки с отсечки, като една отсечка не може да бъде начертана два пъти. Губещият е този, след който за първи път се образува затворена прекъсната линия с нечетен брой връзки. Кой печели с правилна игра?
На кръга бяха взети 10 точки. Какъв е най-големият брой отсечки с краища в тези точки, които могат да бъдат начертани така, че никакви три от тези отсечки да не образуват триъгълник с върхове в тези точки?
В село Мартишкино всяко момче познава всички момичета, които познава. Всяко момиче сред своите познати има повече момчета, отколкото момичета. Докажете, че в Мартишкино няма по-малко момчета от момичета.
Хидрите се състоят от глави и шии (всяка шия свързва точно две глави). Един удар на меча може да отсече всички вратове, излизащи от някоя глава А на хидрата. Но в същото време една шия моментално израства от главата на А във всички глави, с които А не е свързана. Херкулес побеждава хидрата, ако успее да я разреже на две части, които не са свързани с вратовете си. Намерете най-малкото N, така че Херкулес да може да победи всяка хидра със 100 шии с най-много 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 да са във възходящ или низходящ ред.
АЛГОРИТМИ.
Докажете, че върховете на обхващащо дърво могат да бъдат разположени шахматно.
В група от хора всеки има познат. Докажете, че тази група може да бъде разделена на две, така че всеки човек да има познат от друга група.
В селото някои къщи са свързани с жици. Съседите са двама души, чиито къщи са свързани с жици. Винаги ли ще бъде възможно да се установи във всяка къща по един човек - лъжец или рицар - така че всеки да отговори на въпроса: „Има ли лъжци сред вашите съседи?“ - отговори положително. (Всеки знае за всеки свой съсед, независимо дали е лъжец или не).
Докажете, че естествените числа могат да бъдат подредени във върховете на полиедър по такъв начин, че на всеки два върха, свързани с ребро, има числа, които не са взаимно прости, но на всеки два върха, които не са свързани с ребро, те са взаимно прости.
AT порт Приключение 16 тайни агенти бяха изоставени. Всеки от тях хвърли око на някой от колегите си. Известно е, че ако агент НОследвайки агента AT, след това агентът ATне следва агента НО. Всеки 10 агента могат да бъдат преномерирани по такъв начин, че първият да следва втория, вторият - третия, ..., десетият - първия. Докажете, че някои 11 агенти могат да бъдат номерирани по същия начин.
При какво нможете да оцветите всички ръбове н- въглищна призма (основа - н-gons) в три цвята, така че ръбовете и на трите цвята да се събират във всеки връх и всяко лице (включително основите) има ръбове и на трите цвята?
а). Докажете, че върховете на 3n-ъгълна призма могат да бъдат оцветени с три цвята, така че всеки връх да е свързан с ребра с върхове и от трите цвята. б). Докажете, че ако върховете на n-ъгълна призма могат да бъдат оцветени с три цвята, така че всеки връх да е свързан с ръбове с върховете на трите цвята, тогава n се дели на 3.
"АНТИГРАФ".
В компания от 2n+1 души за всеки n души има различен човек, който е запознат с всеки от тях. Докажете, че в тази компания има човек, който познава всички.
ГРАФИКИ И ПОЛИНОМИ.
Дадено е естествено число к и полиноми Р(х) и С(х) с цели коефициенти. Известно е, че за всяко цяло число хномер Р(С(х)) – хразделена на к. Докажете, че числото С(Р(х)) – хсъщо се разделя на кза всяко цяло х.
Има ли четири полинома, така че сборът на всеки три от тях да има поне един корен, а сборът на всеки два от тях да няма корени?
ЦИКЪЛ.
В Града на цветята има 2000 късчета. Всеки шорт дава подарък на всеки от своите приятели всеки ден. За да избегнете разруха, подаръкът е позволено да бъде даден допълнително, но не и на този, който ви е дал този подарък. Знайка пресметна, че нито един от подаръците, които му е подарил в петък, не може да му бъде върнат по-рано от следващия петък. Докажете, че някой шорт има не повече от 13 приятели. (Е. Черепанов)
В щата има 100 града. Някои двойки градове са свързани с пътища и има поне четири циклични маршрута. Докажете, че има цикличен маршрут, преминаващ през най-много 51 града.
В страната има 100 града, някои двойки градове са свързани с пътища, а пътищата са общо 200. Оказа се, че всеки цикличен маршрут има дължина поне пет. Докажете, че има два циклични маршрута, които не се пресичат.
В сградата на Московския университет има много асансьори и всеки асансьор превозва пътници само между два етажа (но на всеки етаж можете да отидете до всеки асансьор, който спира на него). Известно е, че е възможно да стигнете от всеки етаж до всеки друг, като използвате четен брой асансьори и без да минавате два пъти през който и да е етаж. Докажете, че при желание същото може да се направи с нечетен брой асансьори.
В Оз има няколко замъка, всеки с по три пътеки. Скитащият рицар напуснал замъка на предците си и тръгнал на пътешествие из страната. Рицарят обича разнообразието, така че когато стигне до следващия замък, той завива наляво всеки път, ако е завил надясно предишния път, и завива надясно, ако е завил наляво преди това. (Преминавайки първия замък по пътя си, рицарят може да се обърне във всяка посока). Докажете, че един ден рицарят ще се върне в замъка си.
На безкрайна лента е отпечатана безкрайна редица от числа от 1 до 9. Докажете, че или някаква комбинация от числа се повтаря 10 пъти подред, или от нея могат да се изрежат 10 стоцифрени числа в низходящ ред.
ТЕОРЕМА ЗА ЧЕТНОСТТА НА БРОЯ НА НЕЧЕТНИТЕ ВЪРХОВЕ.
Върховете на изпъкнал многостен, чиито лица са триъгълници, са боядисани в три цвята. Докажете, че броят на лицата, от които и трите имат различни цветове, е четен.
Броят на ребрата.
Начертайте квадрат 12 х 12 върху бял лист хартия. Две клетки се считат за съседни, ако имат обща страна. Саша рисува клетка по клетка, като въвежда във всяка защрихована клетка броя на нейните съседи, които преди това са боядисани. Какъв ще бъде сборът на всички числа, когато всички клетки са попълнени? (А. Шаповалов)
Оцвети безкраен лист карирана хартия, с изключение на квадрата 77. Вася в този квадрат рисува клетка, която има точно една съседна (отстрани) оцветена клетка, след това друга клетка, която сега има точно една съседна оцветена клетка и т.н. Какъв е най-големият брой клетки, които Вася може да оцвети по този начин?
При какво н>1 може да се случи така, че във фирма от н+1 момичета и нмомчета, всички момичета познават различен брой момчета и всички момчета познават еднакъв брой момичета?
СМЕС.
На някаква среща присъства н човек. Известно е, че всеки двама познати от тях нямат общи познати, а всеки двама, които не се познават, имат точно двама общи познати. а). Докажете, че всички присъстващи имат еднакъв брой познати. б). При какво нвъзможно условие на задачата?
Градът на "Разнообразието" е дом на 10 000 жители, всеки двама от които са или враждебни, или приятели помежду си. Всеки ден не повече от един жител на града може да "започне нов живот", т.е. карайте се с всичките си приятели и се сприятелявайте с всичките си врагове; докато всеки трима жители могат да се сприятеляват помежду си. Да докаже, че всички жители без изключение могат да се сприятеляват помежду си. Какъв е най-малкият брой дни, който със сигурност ще бъде достатъчен за това?
ки нса естествени числа по-големи от 1. В групата на кнвсеки човек е по-запознат, отколкото с ( к–1)нот останалите. Докажете, че можете да избирате к+1 човек, така че всички да се познават. ( Полски олимпиади, 68)
На равнината са отбелязани 100 точки. Двама души играят, редуват се. С един ход можете да свържете две точки със стрелка, ако не са били свързани преди. В същото време е забранено да се рисува стрелка, след появата на която от всяка точка ще бъде възможно да стигнете до всяка друга точка по стрелките. Този, който не може да направи следващия ход, без да наруши правилата, губи. Кой печели с правилната игра: този, който се движи първи, или неговият партньор? ( ДА. Ростов)
В One-Side County има еднопосочни пътища между някои (но за съжаление все още не всички) чифлици. В същото време, когато всеки нов път (също с еднопосочно движение) се появи между имоти, които преди не са били свързани с път, се оказва, че човек може да стигне от всеки имот до всеки друг, без да нарушава правилата. Докажете, че такава възможност вече съществува. ( ДА. Ростов; Санкт Петербург, град 2000 г)
Срещнах няколко приятели. Всеки от тях се ръкува с всички, с изключение на Федот Бурчеев, който, тъй като не е настроен, се ръкува с едни, а с други не. Имаше общо 197 ръкостискания. Колко ръкостискания направи Федот? ( И.С. Рубанов)
В страната има 100 града, от всеки град тръгва поне един път. Докажете, че е възможно да затворите няколко пътя, така че все още да има поне един път, напускащ всеки град и поне един път, напускащ поне 67 града. ( Е.А. Гирш, С.В. Иванов, Д.В. Карпов)
В училището има 40 класни стаи, които се отварят с 5 различни вида ключове, като броят на ключовете от различните видове е различен. Всичките 40 ключа бяха заключени в стаите, така че във всяка стая е заключен по един ключ, който не може да се използва за отваряне на тази стая. Пазачът Сергеев има дубликат на ключа за една от стаите. Докажете, че може да отвори всички стаи. ( )
Училището разполага с 40 класни стаи, които се отварят с 4 различни вида ключове. Всичките 40 ключа бяха заключени в стаите, така че във всяка стая е заключен един ключ, който не може да се използва за отваряне на тази стая. Пазачът Сергеев знае къде е ключът. Докажете, че пазачът Сергеев може да дублира ключовете на два шкафа, които могат да се използват за отваряне на всички стаи. ( Р.А. Исмаилов, С.Л. Берлов, Д.В. Карпов)
(С. Берлов, СПб, гр., 2001, 6-1) На изложбата на котки 19 котки и 10 котки седяха в редица, а до всяка котка имаше котка, която беше по-дебела от нея. Докажете, че до всяка котка имаше котка, която беше по-слаба от него.
(С. Берлов) Квадратният континент е разделен на 19 държави под формата на изпъкнали многоъгълници и няма точки, в които да се събират границите на четири или повече държави. От всеки три граници, събиращи се в една точка, една е затворена, а две са отворени за движение. Докажете, че е невъзможно да обиколите всички тези страни, като посетите всяка от тях веднъж и се върнете в първоначалната страна.
В страната Фулкерсония някои градове са свързани с авиокомпании и е невъзможно да стигнете от град А до град Б с по-малко от десет прекачвания. Докажете, че всички авиокомпании могат да бъдат продадени на 11 авиокомпании по такъв начин, че всеки маршрут от А до Б ще използва линии, притежавани от всичките 11 авиокомпании. (Фолклор, 100)
Всеки ученик в класа е в два кръга, като за всеки трима ученици има кръг, в който отиват заедно. Докажете, че има кръг, в който участват всички ученици. (DalFO Olympics 2001, 104)
. Десет души дойдоха на гости в галоши. Тръгнаха един по един и всеки си сложи произволен чифт галоши, в които можеше да влезе (т.е. не по-малки от неговите). Кой е най-големият брой хора, които не могат да носят галоши?
В приказната страна Perra-Terra, сред другите жители, живеят Карабас и Барабас. Всеки карабас познава шест караба и девет бараба. Всеки барабас познава десет караба и седем бараба. Кой е повече в тази държава - Карабас или Барабас?
В група от 100 души сред всеки трима има човек, който познава и двамата. Докажете, че от тази група е възможно да се избере компания от 50 души, в която всички се познават. (С. Берлов)
В клуба дойдоха 20 господа, някои с шапки, други без. Тогава от време на време някой от господата сваляше шапката си и я слагаше на главата на друг господин, който в този момент нямаше шапка. Един час по-късно 10 господа казаха: „Подавах шапката си по-често, отколкото я получавах!“ Колко господа дойдоха в клуба с шапки? ( SLB, Yu.M. Лифшиц; СПб-02)
Някоя компания има повече от 10 души и всеки от тях има брой познати, кратен на 10. Докажете, че има поне 11 души с еднакъв брой познати. ( SLB базиран в Молдова)
На олимпиадата бяха предложени 8 (6) задачи. Всеки участник реши точно 3 от тях, а двама участници не решиха повече от една обща задача. Какъв е най-големият брой участници в олимпиадата? ( Балтийски път, 01)
За фирма от нчовек е изпълнено следното условие: ако някои 2 души имат еднакви познати, то всеки от останалите познава точно един от тях. При какво нвъзможно ли е? ( Балтийски път, 2000 г)
На партито дойдоха 19 гости. Сред всеки 3 от тях има 2 познати. Докажете, че гостите могат да бъдат разделени на 5 групи, във всяка от които всички са познати по двойки. ( V.L.Dolnikov, 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 до 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 възела на мрежата, подредени под формата на квадрат 66. Какъв е минималният брой единични сегменти с краища в маркираните възли, които трябва да бъдат начертани, така че между всяка двойка съседни възли да има път не по-дълъг от 3?
Във фирма от нчовек, при който всеки е запознат с поне един от другите, всички еднакво познати (смята се, че ако НОе запознат с AT, след това и ATе запознат с НО). Докажете, че между членовете на тази компания можете да избирате поне н/3 незастъпващи се двойки познати.
В една компания всеки двама души имат точно петима общи познати. Докажете, че броят на познатите (двойки познати) е кратен на три. ( Ю.М. Лифшиц)
В еднокръговия турнир двама участници напуснаха състезанието след петия кръг. В резултат на това в турнира бяха изиграни 38 игри. Тези двамата успяха ли да играят помежду си? ( България, 1982г)
В еднокръговия турнир шестима участници напуснаха надпреварата след шестия кръг. В резултат на това в турнира бяха изиграни 67 игри. Докажете, че поне двама от отпадналите не са играли помежду си. ( К.А. копче)
Какъв е най-малкият възможен брой ребра в граф от 100 върха, така че сред всеки 11 върха да има един, който е свързан с останалите 10 от тях? ( Р. Федоров)
В свързаната графика 2 нвърхове, степента на всеки връх е три. Докажете, че броят на начините за оцветяване на ръбовете на тази графика с три цвята, така че ръбовете с различни цветове да се събират във всеки връх, не надвишава 32 н .
В някакво състояние 4 нлетища, всяко летище оставя точно 3 авиокомпании (една авиокомпания свързва две летища). От всяко летище можете да летите до всяко друго (евентуално с трансфери). Позволявам ДА СЕ -брой начини за продажба всичкоавиокомпании на три авиокомпании, така че три авиокомпании на различни авиокомпании да излитат от всяко летище. Докажи това Да се 32 3 н .
Осем шахматисти изиграха турнира в един кръг. Известно е, че във всяка тройка шахматисти имаше двама, които играха реми помежду си. Какъв е най-малкият брой равенства, който можеше да има в този турнир?
В върховете на квадрата има 4 компютъра, свързани със своите съседи от страните на квадрата. В началния момент важна новина дойде на всеки компютър (за всеки - собствен). Всяка секунда компютърът може или да предаде всички новини, които знае, на съседен компютър, или да получи подходяща информация от съседен компютър, или да остане неактивен. Как всички компютри могат да получат всички новини в системата за най-кратко време?
В земята на Еления нжители. Обединяват се в кръгове по интереси. Във всеки кръг има точно трима души и всеки двама от тях са членове на точно един кръг едновременно. Докажи това нКогато се раздели на 6, остатъкът е 1 или 3.
Пристигна в лагера ммомчета и дмомичета. Всяко момиче познава не повече от 10 момчета, а всяко момче познава поне едно момиче. Оказа се, че всяко момче има повече момичета, които познава, отколкото всяко момиче, което познава, познава момчета. Докажи това д 1.1 м. (Д.В. Карпов)
Дайте пример за четиринадесетоъгълник, всяко лице на който е или квадрат, или правилен триъгълник? ( ДА. Крамаренко)
В пространството има 2000 черни точки, нито четири от които не лежат в една и съща равнина. Някои от точките са свързани със стрелки. Известно е, че няма път, следващ стрелките и минаващ през всички точки (дори и да е възможно да се премине през една и съща точка няколко пъти). Докажете, че някои от точките (поне една, но не всички) могат да бъдат преоцветени в синьо, така че нито една стрелка да не води от синята точка към черната. ( Беларус, 1992 г)
Графиката има обхващащо дърво с точно нвисящи върхове и обхващащо дърво с точно мвисящи върхове, н к м. Докажете, че тази графика има обхващащо дърво с точно квисящи върхове.
В компания от 200 души всеки пет души могат да бъдат настанени на кръгла маса, така че всеки от тях да седне между двама познати (приема се, че ако Ае запознат с б, тогава бе запознат с А). Какъв е най-малкият брой двойки познати, които могат да бъдат в тази компания?
Докажете, че за всеки полиедър е възможно да оцветите две лица в червено, а другите две в синьо, така че червените лица да имат равни страни, а сините лица да имат еднакви страни.
В свързаната графика 3 квърхове, всички те имат степен 3 и всеки връх е включен в точно един триъгълник. Някои ръбове на графиката са премахнати, така че се получава дърво. Докажете, че това дърво има най-много к+2 върха от степен 1.( Д.В. Карпов)
В кралството нградове и rпътища (всеки път свързва два града и от всеки град можете да стигнете до всеки от пътищата). Пратениците живеят в градовете. В началото на всяка година един от градовете изпраща пратеник до всички съседни (т.е. свързани с него чрез пътища) градове. (Такъв град трябва да има достатъчен брой пратеници за това.) След няколко (повече от нула) години всеки град имаше същия брой пратеници, както първоначално. Какъв е най-малкият брой пратеници, които едно кралство може да има? ( И.И. Богданов)
Даден е график, чиято степен на всеки връх е най-малко к(където к2). Докажете, че тази графика съдържа най-малко прост цикъл с дължина к+1. ()
В една банда терористи всеки подозира поне 10 други в предателство.. Докажете, че в тази банда поне 11 терористи могат да бъдат идентифицирани и номерирани, така че първият да заподозре втория, вторият, третият, ..., предпоследният подозира последния, а последният подозира първия. ( основан наKozepiskolai Matematikai Lapok)
В една графика всеки два прости цикъла с нечетна дължина нямат общи ръбове. Докажете, че върховете на този график могат да бъдат оцветени с два цвята, така че всеки връх да е свързан с ребро с най-много един връх от същия цвят.( S.L. Берлов)
В страната има 100 града. Някои двойки градове са свързани с пътища, но нито един град не е свързан с всички. Възможно е да стигнете от всеки град до всеки друг, като се обадите по пътя до не повече от един град. Какъв е най-малкият брой пътища в тази страна? ( )
В страната има 25 града. Някои двойки градове са свързани с пътища, но нито един град не е свързан с всички. Възможно е да стигнете от всеки град до всеки друг, като се обадите по пътя до не повече от един град. Докажете, че в тази страна има поне 35 пътя. ( Kozepiskolai Matematikai Lapok)
В страната има 9 града. Някои двойки градове са свързани с пътища, но нито един град не е свързан с всички. Възможно е да стигнете от всеки град до всеки друг, като се обадите по пътя до не повече от един град. Може ли в тази държава да има не повече от 13 пътя? S.L. Берлов, Д.В. Карпов, базирано на Közepiskolai Matematikai Lapok)
Степени на всички върхове на графа Жпо-малко (къде н> 2), и сред всички н+ 1 има два несъседни върха. Да се обадим блокнабор от нпо двойки съседни върхове на графа Ж.Известно е, че всеки два блока имат общ връх. Докажете, че всички блокове имат общ връх.( C.L. Берлов)
Ребра на пълна графа с нвърховете са боядисани в няколко цвята, като цветовете са не по-малко от н. Докажете, че има три върха, всички ръбове между които са оцветени в различни цветове. ( П.А. Кожевников)
Ребра на пълна графа с нвърховете са оцветени в няколко цвята по такъв начин, че всеки цвят да се среща най-много н- 2 пъти. Докажете, че има три върха, всички ръбове между които са оцветени в различни цветове.( AMM)
В графиката Жсе избират набори от върхове С 1 , С 2 , С 3 със 100 върха всеки. Известно е, че когато всички върхове на който и да е от тези три набора (и всички ребра, излизащи от тях) бъдат премахнати, останалите върхове на графа се разделят на точно два свързани компонента и когато бъдат премахнати 99 върха, графът остава свързан . Докажете, че всички не са включени в комплектите С 1 , С 2 и С 3 върхове на графа Жмогат да бъдат разделени на 6 групи по такъв начин, че върховете на една група да завършват в един и същ свързан компонент при премахване на който и да е от наборите от графа на върховете С 1 , С 2 или С 3 .(Д.В. Карпов)
Цар Грах има 20 придворни. Плетейки интриги един срещу друг, те създадоха редица тайни общества. Шефът на тайната полиция, изучавайки тези общества, откри три модела. Първо, за всеки две тайни общества, всички придворни, които са едновременно членове на двете общества, образуват тайно общество. Второ, за всеки две тайни общества всички придворни, които са членове на поне едно от тях, образуват тайно общество. Трето, за всяко тайно общество всички придворни, които не са членове, образуват тайно общество. Може ли да има точно 2002 тайни общества в двора на Грах? ( Putnam 1961, преформулиране)
Ръбовете на додекаедъра са номерирани от 1 до 30 без повторение. Нека преброим броя на прекъснатите линии, съставени от три ръба на додекаедъра и така, че числата на връзките да са във възходящ ред. Намерете минималния възможен брой такива прекъснати линии. (И.И. Богданов, Г.Р. Челноков въз основа на задачата от полската олимпиада-89/90 )
Числата от 1 до 12 са поставени по ръбовете на куба без повторения. Нека преброим броя на прекъснатите линии, съставени от три ръба на куба и така, че числата на връзките да са във възходящ ред. Намерете минималния възможен брой такива прекъснати линии. (Полша-89/90)
В компания от 20 души за всеки трима има човек, който ги познава всичките. Докажете, че има човек, който има поне девет познати. ( S.L. Берлов, I.I. Богданов)
В компания от 10 човека за всеки трима има човек, който ги познава всичките. Докажете, че има човек, който има поне шест познати.
В симпозиума участваха 100 души. От тях 15 са французи, всеки от които е запознат с най-малко 70 участници в симпозиума, и 85 са германци, всеки от които е запознат с не повече от десет участника. Те бяха настанени в 21 стаи. Докажете, че в нито една от стаите няма двойки познати. ( Й. Лифшиц)
В дружеството има 22 състезатели. Двойки спортисти, които са приятели един на друг - четиринадесет. Оказа се, че сред всеки 11 спортисти има поне една двойка приятели. Докажете, че всеки може да бъде разделен на два футболни отбора, така че всяка двойка приятели да е в един отбор. ( Опростяване на задачата на 10 висши лиги)
В колона 4 квърхове 3 кребра. Известно е, че сред всеки 2 кима два негови върха, свързани с ребро. Докажете, че върховете на графа могат да бъдат разделени на две групи от по 2 квърхове във всяка, така че да няма два върха от различни групи, свързани с ребро. (Р.А.Бруалди, С.Мелендорф)
Пиян шахматен крал никога не прави два последователни хода в една и съща посока. Започвайки от ъгъла, той обиколи шахматната дъска 9x9, като посети всяка клетка веднъж и се върна в първоначалната клетка. Какъв е най-малкият брой диагонални ходове, които може да направи? ( S.L. Берлов въз основа на проблема на О.Ю. Ланина, Олимпиада по ФМЛ № 239, 2002 гЖ.)
В страната има 7 града, между които летят 7 самолета. Самолетът лети от всеки град до всеки друг точно за 1 час и веднага след кацане може да лети до следващия град (докато транзитните пътници остават в самолета). Направете разписание на полета, така че всеки пътник, без да сменя самолета по пътя, да може да лети от всеки град до който и да е друг не повече от 5 часа след пристигането на летището. (Олимпиада Гросман)
Петте върха на куба са оцветени в червено. Вярно ли е, че задължително има три ръба, които имат червени краища и в двата края?
Федя има несвързана графика. Той премахна един връх от този график по всички възможни начини и начерта всеки от получените графики на отделен лист хартия, след което даде всички тези листове на Дима. Докажете, че Дима може да възстанови оригиналната графика с помощта на тези листа. ( Д.В. Карпов, въз основа на хипотезата на Улам)
Федя има няколко кутии с топки. Взема една по една топка от кутиите, записва набор от числа на отделен лист хартия - броя на топките, останали във всяка кутия, ако има нещо останало (без да уточнява кое число на коя кутия отговаря) и след това връща топката на мястото й. Изваждайки всяка топка веднъж, той дава всички листа на Дима. Докажете, че Дима може да определи колко балона има във всяка кутия. ( Д.В. Карпов)
н- нечетно число. Изпъкнали върхове н-ъгълниците са оцветени в няколко цвята, така че всеки два съседни върха да са с различен цвят. Докажете, че това н-gon може да бъде разделен на триъгълници чрез непресичащи се диагонали, нито един от които няма еднакви цветни краища. ( Kurszak-1978, №2)
Дадена е графика на нвърхове. Докажете, че всички негови ръбове могат да бъдат разделени на най-много н 2/4 комплекта, всеки от които се състои от един ръб или е триъгълник. ( Богданов, Карпов)
Градовете A, B, C са свързани с полети. Между всеки два града има поне един полет и всички полети са двупосочни (ако можете да летите от А до Б, тогава същият полет може да лети от Б до А). Освен това е известно, че общият брой начини за стигане от точка А до точка С (включително маршрути с прекачване в точка Б) е 11, а общият брой начини за стигане от точка А до точка Б (включително маршрути с промяна в C) е 13. директни полети между тези градове?
Като се има предвид кариран квадрат, чиято страна съдържа нвъзли. Път без връщане е път по ръбове, чието пресичане с всяка хоризонтална или вертикална линия е сегмент, точка или празно множество. Какъв е най-малкият брой нерекурсивни пътища, които могат да покрият всички върхове? ( И. Пушкарев, И. Богданов, Г. Челноков)
Даден е свързан граф, който остава свързан, когато който и да е връх бъде премахнат. Известно е, че има триъгълник. Във всеки връх, с изключение на един, има жетон (всички жетони са различни). Разрешено е преместване на жетон от връх, съседен на празен, в празен. Докажете, че чрез такива действия можете да получите всяка конфигурация на чипове от всяка конфигурация. ( М. Мазин)
В града 10 улици минават от север на юг и 11 от запад на изток, образувайки 110 кръстовища. Със заповед на кмета всеки автобусен маршрут в града може да се движи в не повече от две посоки (изток-юг, изток-север, запад-юг или запад-север). Възможно ли е да се свържат всички кръстовища в града със седем автобусни линии? (По И. Пушкарев, И. Богданов, Г. Челноков)
Какъв е най-малкият брой върхове, които може да има изпъкнал многостен, точно три от чиито лица са петоъгълници? ( USAMTS 2003)
броя ...
теория на графите
ДокументПолучени резултати. Някои видове броиОйлерграфикиЗа задачи по Ойлерграфикивключват пъзели, които изискват... всички ръбове брояи дори веднъж. Графика, притежаващ Ойлерцикъл се нарича Ойлерброя. Затворен...
Името на програмата на теорията на графиките на дисциплината се препоръчва за посоката (ите) на обучение (специалност (и)
програмаХарактеристики брои. Подграфи. Операциите приключиха брои. Двусемеделни графики. Първо търсене в широчината. дървета. Ойлерграфики. Хамилтонов графики. Ойлерначин...
- Дъската има формата на кръст, която се получава чрез премахване на ъгловите квадратчета от квадратната дъска $4 \times 4$. Възможно ли е да го заобиколите с хода на шахматния кон и да се върнете към първоначалното поле, като сте посетили всички полета точно веднъж?
- В страната на цифрите има 9 града с имена 1, 2, 3, 4, 5, 6, 7, 8, 9. Пътешественикът открива, че два града са свързани с авиокомпания тогава и само ако имената на тези градове се дели на 3. Възможно ли е да се стигне от град 1 до град 9?
- В град Малък има 15 телефона. Могат ли да бъдат свързани с жици, така че всеки телефон да е свързан точно с пет други?
- В щата има 100 града и от всеки от тях излизат по 4 пътя. Колко пътища има в щата?
- В класа има 30 души. Възможно ли е 9 от тях да имат 3 приятели (в този клас), 11 да имат 4 приятели и 10 да имат 5 приятели?
- В град Малък има 15 телефона. Могат ли да бъдат свързани с жици, така че да има 4 телефона, всеки свързан с три други, 8 телефона, всеки свързан с шест, и 3 телефона, всеки свързан с пет други?
- Кралят има 19 васални барона. Възможно ли е всяко васално баронство да има 1, 5 или 9 съседни баронства?
- Може ли да има точно 100 пътя в състояние, в което 3 пътя излизат от всеки град?
- Джон, пристигнал от Дисниленд, каза, че на омагьосаното езеро има 7 острова, всеки от които води до 1, 3 или 5 моста. Вярно ли е, че поне един от тези мостове непременно води до брега на езерото?
- Докажете, че броят на хората, които някога са живели на Земята и са се ръкували с нечетно число, е четен.
- Възможно ли е да се начертаят 9 сегмента в равнина, така че всеки да пресича точно три други?
- В страната на Седемте има 15 града, всеки от които е свързан с пътища с поне 7 други. Докажете, че е възможно да стигнете от всеки град до всеки друг (може би като минавате през други градове).
- Докажете, че граф с $n$ върха, всеки от степен най-малко $(n - 1)/2$, е свързан.
- Във Far Far Away има само един вид транспорт - летящото килимче. Има 21 килимни линии от столицата, една от Dalniy и 20 от всички останали градове.Докажете, че е възможно да се лети от столицата до Dalniy (възможно е с прекачвания).
- Има 100 пътя, водещи от всеки град в страната и от всеки град можете да стигнете до всеки друг. Един път беше затворен за ремонт. Докажете, че дори и сега е възможно да стигнете от всеки град до всеки друг.
- а) Дадено е парче тел с дължина 120 см. Възможно ли е, без да се счупи телта, да се направи рамка на куб с ръб 10 см?
б) Колко пъти най-малко ще трябва да се скъса жицата, за да се направи необходимата рамка? - Докажете, че граф, в който всеки два върха са свързани с точно един прост път, е дърво.
- Докажете, че всеки два върха в едно дърво са свързани с точно един прост път.
- Докажете, че в дървото има връх, от който излиза точно едно ребро (такъв връх се нарича висящ).
- Всички върхове в графа имат степен 3. Докажете, че има цикъл.
- Докажете, че премахването на което и да е ребро от едно дърво го превръща в несвързан граф.
- В страната Treeland има 101 града и някои от тях са свързани с пътища. В същото време точно един път свързва всеки два града. Колко пътища има в тази държава?
- Докажете, че свързан граф, чийто брой ребра е с едно по-малък от броя на върховете, е дърво.
- Волейболната мрежа изглежда като правоъгълник от $50 \пъти 600$ квадратчета. Какъв е най-големият брой струни, които могат да бъдат срязани, без мрежата да се разпадне?
- В дадена държава има 30 града, всеки свързан с всеки път. Кой е най-големият брой пътища, които могат да бъдат затворени за ремонт, така че да може да се пътува от всеки град до всеки?
- Докажете, че във всеки свързан граф е възможно да се премахне връх заедно с всички ребра, излизащи от него, така че той да остане свързан.
- В страната има 100 града, някои от които са свързани с авиолинии. Известно е, че от всеки град можете да летите до всеки друг (евентуално с трансфери). Докажете, че е възможно да посетите всеки град с не повече от
а) 198 полета;
б) 196 полета. - В страната Озерная има 7 езера, свързани помежду си с 10 канала, и от всяко езеро можете да плувате до всяко друго. Колко острова има в тази страна?
- В квадрата бяха отбелязани 20 точки и свързани с непресичащи се сегменти помежду си и с върховете на квадрата, така че квадратът беше разделен на триъгълници. Колко триъгълника получихте?
- Граф, който има 5 върха, всеки от които е свързан с ребро с всеки друг, не е планарен.
- Възможно ли е да се построят три къщи, да се изкопаят три кладенеца и да се свържат пътеки от всяка къща до всеки кладенец, така че пътеките да не се пресичат?
- Докажете, че граф с 10 върха, всеки от степен 5, не е планарен.
- Докажете, че планарен граф има връх, чиято степен не надвишава 5.
- Всеки ръб на пълен граф с 11 върха е оцветен в един от двата цвята: червен или син. Докажете, че нито "червената", нито "синята" графика не е равнинна.
- Седмоъгълникът е разделен на изпъкнали петоъгълници и шестоъгълници по такъв начин, че всеки от неговите върхове е връх на поне два многоъгълника на преградата. Докажете, че броят на петоъгълниците в преградата е най-малко 13.
