МАЛЫЙ МЕХМАТ МГУ

Кружок 6 класса

Занятие 6 (29.10.2011). Задачи с n

1.

Найдите количество натуральных чисел, которые не меньше 5 и не больше n (n ≥ 5).

Решение Ответ

Решение. От 1 до n количество чисел равно n. Из них 1, 2, 3, 4 не подходят, поэтому ответ n − 4.

Ответ. n − 4.

2.

Клетки доски покрашены в шахматном порядке так, что левый верхний угол черный. Найдите число черных клеток, если доска имеет размер а) n×n; б) m×n.

Решение

Решение. а) Всего клеток n². Если n — чётное, то каждого цвета поровну, поэтому чёрных клеток

n²	.
2

Если n — нечётное, то чёрных клеток на одну больше, чем белых, то есть, их

n² − 1	+	1.
2

б) Аналогично пункту а), чёрных и белых клеток будет поровну, если всего клеток чётное число, и непорвну, если всего клеток нечётное число. То есть, если хотя бы одно из чисел m и n чётное, то ответ

mn	,
2

и

mn − 1	+	1,
2

если m и n нечётные.

3.

В стране n городов, один из которых Таганрог. Некоторые пары городов соединены дорогами, при этом между любыми двумя городами их не более одной. Какое наибольшее количество дорог может быть в этой стране, если из Таганрога выходит только одна дорога?

Решение Ответ

Решение. Любые два города, кроме Таганрога, можно соединить дорогой. Получится не больше (n − 2) + (n − 3) + ... + 1

=	(n − 1)(n − 2)
	2

дорог. И ещё одна дорога соединяет Таганрог с одним из городов, т.е. всего

(n − 1)(n − 2)	+	1.
2

Ответ.

(n − 1)(n − 2)	+	1.
2

4.

В Андорре m футбольных команд (по 11 футболистов в каждой). Все футболисты собрались в аэропорту для поездки в другую «страну» на турнир. Самолёт сделал 10 рейсов, перевозя каждый раз по m пассажиров. Ещё один футболист Юра полетел на турнир сам на веротолёте. Докажите, что хотя бы одна команда прилетела полностью.

Решение

Решение. Было сделано 10 рейсов по m пассажиров, т.е. перевезено 10m пассажиров. Ещё Юра приехал сам — всего 10m + 1. Если бы ни одна из команд не приехала полностью, то из каждой команды приехало бы не больше 10 футболистов, а значит, общее количество приехавших футболистов было бы не больше 10m.

5.

Существует ли такое натуральное число, что при умножении его на любое другое натуральное число у полученного произведения будет нечётная сумма цифр?

Решение

Решение. Не существует, потому что для любого натурального числа найдётся другое натуральное число такое, что их произведение будет иметь чётную сумму цифр.
Возьмём произвольное число, у которого количество цифр равно k. Умножим его на число 100...01, где количество нулей равно k. Десятичная запись произведения будет два раза повторять исходное число. Значит, сумма цифр будет у него в два раза больше, чем у исходного числа, т.е. чётная.

6.

Докажите, что для любого n числа 1, 2, ..., 2n можно записать по кругу так, чтобы любые два соседних отличались не более, чем на 2.

Решение

Решение. Можно это сделать, например, так:

3, ..., 2n − 3, 2n − 1, 2n, 2n − 2, 2n − 4, ..., 2, 1

1 замыкает круг.

7.

В военную часть приехали n незнакомых друг с другом новобранцев. Прапорщик сообщил каждому новобранцу натуральное число так, что сумма всех n чисел равна 2n − 2. Докажите, что можно познакомить некоторых из них друг с другом так, чтобы у каждого новобранца было количество знакомых, равное числу, которое ему сообщил прапорщик.

Решение

Решение. Среди чисел, которые сообщили новобранцам, точно есть единица, иначе сумма всех чисел была бы не меньше 2n. Знакомим новобранца с единицей с любым другим, у которого число больше одного (такой точно есть, если n > 2). После этого про первого новобранца «забываем», а у второго число уменьшаем на 1. Тогда осталось n − 1 солдат, у каждого из которых число натуральное, и сумма всех чисел равна 2n − 4 = 2(n − 1) − 2. Т.е. ситуация свелась к предыдущей, но число новобранцев стало на 1 меньше. Повторяем эту процендуру до тех пор, пока не останется два новобранца. Сумма их чисел равна 2·2 − 2 = 2, т.е. у каждого из них осталась единица — знакомим их друг с другом. (Если солдат изначально было только 2, т.е. n = 2, то проделываем это сразу.)

8.

Известно, что сумма цифр натурального числа N равна 100, а сумма цифр числа 5N равна 50. Докажите, что N четно.

Решение

Решение. Обозначим через s(A) сумму цифр числа A. Из рассмотрения сложения в столбик двух чисел A и B следует, что s(A + B) ≤ s(A) + s(B), причем равенство достигается в том и только в том случае, когда при сложении нет переносов через разряд. Тем самым, из условия задачи вытекает, что при сложении 5N + 5N = 10N нет переносов через разряд, поскольку s(10N) = s(N) = 100. Но число 5N оканчивается на 5 или на 0 в случае соответственно нечетного и четного N. Первый случай отпадает, так как возникает перенос в последнем разряде.