Задача № 130795
В стране Озёрная семь озер, соединённых между собой десятью непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?
Олимпиадные задачи по математике — страница 915
Найдите задачу для себя, урока или математического кружка.
Задача № 130794
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.
Задача № 130793
Докажите, что в любом связном графе можно удалить вершину вместе со всеми выходящими из нее рёбрами так, чтобы он остался связным.
Задача № 130792
В некоторой стране 30 городов, причём каждый соединён с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в любой другой?
Задача № 130791
Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?
Задача № 130790
Докажите, что связный граф, у которого число рёбер на единицу меньше числа вершин, является деревом.
Задача № 130789
В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом каждые два города соединяет ровно один путь. Сколько в этой стране дорог?
Задача № 130788
Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.
Задача № 130787
В графе все вершины имеют степень 3. Докажите, что в нём есть цикл.
Задача № 130786
Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).
Задача № 130785
Докажите, что в дереве каждые две вершины соединены ровно одним простым путем.
Задача № 130784
Докажите, что граф, в котором каждые две вершины соединены ровно одним простым путем, является деревом.
Задача № 130783
В связном графе степени четырёх вершин равны 3, а степени остальных вершин равны 4. Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.
Задача № 130782
Верно ли, что два графа изоморфны, если а) у них по 10 вершин, степень каждой из которых равна 9? б) у них по 8 вершин, степень каждой из которых равна 3? в) они связны, без циклов и содержат по 6 рёбер?
Задача № 130781
Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, ..., n, n.
Задача № 130780
Докажите, что не существует графа без петель и кратных рёбер с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.
Задача № 130779
Дана некоторая тройка чисел. С любыми двумя из них разрешается проделывать следующее: если эти числа равны a и b, то их можно заменить на и . Можно ли с помощью таких операций получить тройку из тройки
Задача № 130778
В ряд выписаны числа 1, 2, 3, ..., n. За один ход разрешается поменять местами любые два числа. Может ли после 1989 таких операций порядок чисел оказаться исходным?
Задача № 130777
На столе лежит куча из 1001 камня. Ход состоит в том, что из какой-либо кучи, содержащей более одного камня, выкидывают камень, а затем одну из куч делят на две. Можно ли через несколько ходов оставить на столе только кучки, состоящие из трех камней?
Задача № 130776
В задаче 19 выясните, какие карточки можно получить из карточки (5, 19), а какие нельзя.
Задача № 130775
Круг разделен на 6 секторов и в них по часовой стрелке расставлены числа: 1, 0, 1, 0, 0, 0. Разрешается прибавить по единице к числам в любых двух соседних секторах. Можно ли такими операциями добиться того, чтобы все числа в секторах были одинаковыми?
Задача № 130774
В вершинах куба расставлены числа: 7 нулей и одна единица. За один ход разрешается прибавить по единице к числам в концах любого ребра куба. Можно ли добиться того, чтобы все числа стали равными? А можно ли добиться того, чтобы все числа делились на 3?
Задача № 130772
В таблицеm × nрасставлены числа так, что сумма чисел в любой строке или столбце равна 1. Докажите, чтоm = n.Примечание. Как ни странно, но в некотором смысле это тоже задача на инвариант.
Задача № 130771
Фишка ходит по квадратной доске, каждым своим ходом сдвигаясь либо на клетку вверх, либо на клетку вправо, либо по диагонали вниз-влево. Может ли она обойти всю доску, побывав на всех полях ровно по одному разу, и закончить на поле, соседнем справа от исходного?
Задача № 130770
В пробирке находятся марсианские амебы трех типов:A,BиC. Две амебы любых двух разных типов могут слиться в одну амебу третьего типа. После нескольких таких слияний в пробирке оказалась одна амеба. Каков ее тип, если исходно амеб типаAбыло 20 штук, типаB- 21 штука и типаC- 22 штуки?
0–0 из 23247