Каталог по темам

Задачи

Страница: << 54 55 56 57 58 59 60 >> [Всего задач: 332]

Задача 110030

Темы:	[	Связность и разложение на связные компоненты	]
	[	Вспомогательная раскраска (прочее)	]
	[	Индукция (прочее)	]

Сложность: 5+
Классы: 8,9,10

Авторы: Дольников В.Л., Карпов Д.В., Берлов С.Л.

В стране 2000 городов, некоторые пары городов соединены дорогами. Известно, что через любой город проходит не более N различных несамопересекающихся циклических маршрутов нечётной длины. Докажите, что страну можно разделить на N + 2 республики так, чтобы никакие два города из одной республики не были соединены дорогой.

Прислать комментарий

Решение

Задача 109776

Темы:	[	Процессы и операции	]
	[	Теория алгоритмов (прочее)	]
	[	Индукция (прочее)	]

Сложность: 5+
Классы: 8,9,10,11

Автор: Черепанов Е.

У Ани и Бори было по длинной полосе бумаги. На одной из них была написана буква А, на другой – Б. Каждую минуту один из них (не обязательно по очереди) приписывает справа или слева к слову на своей полосе слово с полосы другого. Докажите, что через сутки слово с Аниной полосы можно будет разрезать на 2 части и переставить их местами так, что получится то же слово, записанное в обратном порядке.

Прислать комментарий Решение

Задача 73590

Темы:	[	Десятичная система счисления	]
	[	Суммы числовых последовательностей и ряды разностей	]
	[	Индукция (прочее)	]

Сложность: 6+
Классы: 8,9,10,11

Все натуральные числа, в десятичной записи которых не больше n цифр, разбили на два множества следующим образом. В первое множество входят числа с нечётной суммой цифр, а во второе — c чётной суммой цифр. Докажите, что для любого натурального числа k £ n сумма k-х степеней всех чисел первого множества равна сумме k-х степеней всех чисел второго множества.

Прислать комментарий Решение

Задача 61526

Темы:	[	Раскладки и разбиения	]
	[	Многочлены Гаусса	]
	[	Производящие функции	]
	[	Индукция (прочее)	]

Сложность: 3
Классы: 10,11

Пусть f_k,l(x) – производящая функция последовательности P_k,l(n) из задачи 61525: f_k,l(x) = P_k,l(0) + xP_k,l(1) + ... + x^klP_k,l(kl).

а) Докажите равенства: f_k,l(x) = f_k–1,l(x) + x^kf_k,l–1(x) = f_k,l–1(x) + x^lf_k–1,l(x).

б) Докажите, что функции f_k,l(x) совпадают с многочленами Гаусса g_k,l(x) (определение многочленов Гаусса смотри здесь).

Прислать комментарий

Решение

Задача 109570

Темы:	[	Процессы и операции	]
	[	Арифметическая прогрессия	]
	[	Геометрия на клетчатой бумаге	]
	[	Индукция (прочее)	]

Сложность: 4-
Классы: 8,9,10

Автор: Карпов Д.В.

Натуральные числа от 1 до 1000 по одному выписали на карточки, а затем накрыли этими карточками какие-то 1000 клеток прямоугольника 1x 1994 . Если соседняя справа от карточки с числом n клетка свободна, то за один ход ее разрешается накрыть карточкой с числом n+1 . Докажите, что нельзя сделать более полумиллиона таких ходов.

Прислать комментарий Решение

Страница: << 54 55 56 57 58 59 60 >> [Всего задач: 332]