Олимпиадные задачи по математике
В стране Озёрная семь озер, соединённых между собой десятью непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.
Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее рёбрами так, чтобы он остался связным.
В некоторой стране 30 городов, причём каждый соединён с каждым дорогой.
Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в любой другой?
Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?
Докажите, что связный граф, у которого число рёбер на единицу меньше числа вершин, является деревом.
В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом каждые два города соединяет ровно один путь.
Сколько в этой стране дорог?
Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
В графе все вершины имеют степень 3. Докажите, что в нём есть цикл.
Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется <i>висячей</i>).
Докажите, что в дереве каждые две вершины соединены ровно одним простым путем.
Докажите, что граф, в котором каждые две вершины соединены ровно одним простым путем, является деревом.
В связном графе степени четырёх вершин равны 3, а степени остальных вершин равны 4.
Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.
Верно ли, что два графа изоморфны, если
а) у них по 10 вершин, степень каждой из которых равна 9?
б) у них по 8 вершин, степень каждой из которых равна 3?
в) они связны, без циклов и содержат по 6 рёбер?
Докажите, что существует граф с 2<i>n</i> вершинами, степени которых равны 1, 1, 2, 2, ..., <i>n, n</i>.
Докажите, что не существует графа без петель и кратных рёбер с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.
Дана некоторая тройка чисел. С любыми двумя из них разрешается проделывать следующее: если эти числа равны <i>a</i> и <i>b</i>, то их можно заменить на <img align="absMIDDLE" src="/storage/problem-media/30779/problem_30779_img_2.gif"> и <img align="absMIDDLE" src="/storage/problem-media/30779/problem_30779_img_3.gif"> . Можно ли с помощью таких операций получить тройку <img align="absMIDDLE" src="/storage/problem-media/30779/problem_30779_img_4.gif"> из тройки <img align="absMIDDLE" src="/storage/problem-media/30779/problem_30779_img_5.gif">
В ряд выписаны числа 1, 2, 3, ..., <i>n</i>. За один ход разрешается поменять местами любые два числа.
Может ли после 1989 таких операций порядок чисел оказаться исходным?
На столе лежит куча из 1001 камня. Ход состоит в том, что из какой-либо кучи, содержащей более одного камня, выкидывают камень, а затем одну из куч делят на две. Можно ли через несколько ходов оставить на столе только кучки, состоящие из трех камней?
В задаче 19 выясните, какие карточки можно получить из карточки (5, 19), а какие нельзя.
Круг разделен на 6 секторов и в них по часовой стрелке расставлены числа: 1, 0, 1, 0, 0, 0. Разрешается прибавить по единице к числам в любых двух соседних секторах. Можно ли такими операциями добиться того, чтобы все числа в секторах были одинаковыми?
В вершинах куба расставлены числа: 7 нулей и одна единица. За один ход разрешается прибавить по единице к числам в концах любого ребра куба. Можно ли добиться того, чтобы все числа стали равными? А можно ли добиться того, чтобы все числа делились на 3?
В таблице<i>m</i> × <i>n</i>расставлены числа так, что сумма чисел в любой строке или столбце равна 1. Докажите, что<i>m</i> = <i>n</i>.Примечание. Как ни странно, но в некотором смысле это тоже задача на инвариант.
Фишка ходит по квадратной доске, каждым своим ходом сдвигаясь либо на клетку вверх, либо на клетку вправо, либо по диагонали вниз-влево. Может ли она обойти всю доску, побывав на всех полях ровно по одному разу, и закончить на поле, соседнем справа от исходного?
В пробирке находятся марсианские амебы трех типов:<i>A</i>,<i>B</i>и<i>C</i>. Две амебы любых двух разных типов могут слиться в одну амебу третьего типа. После нескольких таких слияний в пробирке оказалась одна амеба. Каков ее тип, если исходно амеб типа<i>A</i>было 20 штук, типа<i>B</i>- 21 штука и типа<i>C</i>- 22 штуки?