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

Задачи

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 44]

Задача 78533

Темы:	[	Обратный ход	]
	[	Индукция (прочее)	]
	[	Процессы и операции	]

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

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

Решение

Ответ: при n=2^k , k – целое. Если n является степенью двойки, то алгоритм переливания легко строится по индукции. Докажим, что при остальных n перелить всю воду в один стакан нельзя. Предположим, что нам удалось перелить всю воду в один стакан. Примем за единицу измерения объема начальный объем воды в каждом стакане. Тогда после любого числа переливаний объем воды в любом стакане будет выражаться целым числом. Обратим наш процесс. Тогда в начальный момент у нас есть n единиц объема воды в одном стакане, а в конечный момент – но одной единице в каждом стакане. Одна операция заключается в переливании из одного стакана половины имеющейся в нем воды в любой из остальных стаканов. Пусть p - любой простой нечетный делитель числа n . В начальный момент количество воды в каждом стакане делится на p , в процессе переливаний это свойство сохраняется. Значит, в конечный момент количество воды в каждом стакане должно делиться на p , то есть 1 делится на p – противоречие.

Ответ

При n=2^k , k – целое.

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

Задача 78249

Темы:	[	Обратный ход	]
Темы:	[	Примеры и контрпримеры. Конструкции	]

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

В автобусе без кондуктора едут 4k пассажиров. У каждого из них есть только монеты в 10, 15, 20 копеек. Доказать, что если общее число монет меньше 5k, то пассажиры не смогут правильно расплатиться за проезд. Для числа монет 5k построить пример, когда возможен правильный расчет. Примечание. Проезд в автобусе стоит 5 копеек.

Решение

Так как проезд в автобусе стоит 5 копеек, а ни у кого из пассажиров, по условию, нет монет мельче 10 копеек, то после оплаты проезда каждый пассажир должен получить сдачу, т. е. после оплаты проезда у каждого на руках должна остаться хотя бы одна монета. Таким образом, после оплаты на руках у пассажиров должно остаться не меньше, чем 4k монет. Вместе с тем стоимость проезда 4k пассажиров составляет 20k копеек, и для её оплаты даже 20-копеечными монетами (самыми крупными из имеющихся) потребовалось бы не меньше, чем k монет. Значит, в кассу автобуса будет опущено не меньше k монет, и общее необходимое количество монет равно 5k. Нам осталось построить пример правильной оплаты проезда при наличии у пассажиров ровно 5k монет. Разобьём пассажиров на k групп по 4 человека и пусть в каждой группе деньги распределены следующим образом:

1-й пассажир: 15 коп.;

2-й пассажир: 10 + 10 коп.;

3-й пассажир: 15 коп.;

4-й пассажир: 20 коп.

(5 монет на каждую группу из 4 человек; всего, значит, 5k монет). Расчёт в группе происходит следующим образом:

1-й получает 10 коп. взамен 15 коп.;

2-й '' 15 коп. '' 20 коп.;

3-й '' 10 коп. '' 15 коп.;

4-й '' 15 коп. '' 20 коп.

В кассу опущено 20 коп. за четырёх пассажиров. (Решение из книги [#!Leman!#].)

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

Задача 78253

Тема:

[

Обратный ход

]

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

k человек ехали в автобусе без кондуктора, и у всех них были монеты только достоинством в 10, 15, 20 копеек. Известно, что каждый уплатил за проезд и получил сдачу. Доказать, что наименьшее число монет, которое они могли иметь, равно k + $\left[\vphantom{\frac{k+3}{4}}\right.$ ${\frac{k+3}{4}}$ $\left.\vphantom{\frac{k+3}{4}}\right]$ , где значок [a] означает наибольшее целое число, не превосходящее a. Примечание. Проезд в автобусе стоит 5 копеек.

Решение

Для каждой использованной монеты нарисуем стрелку от того человека, у которого она была до выплат, к тому человеку, у которого она оказалась после выплаты (некоторые стрелки будут вести к автомату по оплате). Количество получившихся стрелок равно количеству использованных монет, а значит, достаточно доказать, что проведено не менее k + $\left[\vphantom{\dfrac{k+3}{4} }\right.$ ${\dfrac{k+3}{4}}$ $\left.\vphantom{\dfrac{k+3}{4} }\right]$ стрелок. Поскольку никто не мог заплатить за проезд без сдачи, к каждому человеку ведёт хотя бы одна стрелка (уже k стрелок). Так как одной монетой можно оплатить проезд не более четырёх человек, к автомату ведёт не менее ${\dfrac{k}{4}}$ стрелок. Но наименьшее целое число, не меньшее ${\dfrac{k}{4}}$ , и есть $\left[\vphantom{\dfrac{k+3}{4} }\right.$ ${\dfrac{k+3}{4}}$ $\left.\vphantom{\dfrac{k+3}{4} }\right]$ , а значит, всего проведено не менее k + $\left[\vphantom{\dfrac{k+3}{4} }\right.$ ${\dfrac{k+3}{4}}$ $\left.\vphantom{\dfrac{k+3}{4} }\right]$ стрелок. Замечание. На самом деле, при всех k > 1 эта оценка точная, т. е. указанного в условии количества монет достаточно. Докажем это индукцией по числу k. Сначала проверим базу индукции при k = 2, 3, 4, 5. При k = 2 первый пассажир платит 10 копеек в кассу и 10 копеек второму пассажиру, а второй платит 15 копеек первому. При k = 3 первые двое расплачиваются как в предыдущем примере, но 10 копеек отдают не в кассу а третьему, который кладёт в кассу 15 копеек. При k = 4 первые трое расплачиваются как в предыдущем примере, но 15 копеек отдают четвёртому, который кладёт в кассу 20 копеек. При k = 5 первые двое и остальные трое расплачиваются по отдельности, как это описано в предыдущих примерах. Пусть теперь k $\ge$ 6 и при всех меньших k утверждение доказано. Выделим четырёх пассажиров. Пусть все остальные расплачиваются как в соответствующем примере для k - 4, а выделенные четверо — как в примере для четырёх. Проверка того, что истраченное количество монет будет равно k + $\left[\vphantom{\dfrac{k+3}{4} }\right.$ ${\dfrac{k+3}{4}}$ $\left.\vphantom{\dfrac{k+3}{4} }\right]$ , оставляется читателю в качестве упражнения.

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

Задача 87936

Темы:	[	Арифметика. Устный счет и т.п.	]
Темы:	[	Обратный ход	]

Сложность: 2
Классы: 5,6,7

Дедка вдвое сильнее Бабки, Бабка втрое сильнее Внучки, Внучка вчетверо сильнее Жучки, Жучка впятеро сильнее Кошки, Кошка вшестеро сильнее Мышки. Дедка, Бабка, Внучка, Жучка и Кошка вместе с Мышкой могут вытащить Репку, а без Мышки — не могут. Сколько надо позвать Мышек, чтобы они смогли сами вытащить Репку?

Подсказка

Скольких Мышек заменяет Кошка? А Внучка?

Решение

Кошка заменяет 6 Мышек. Жучка заменяет 5•6 Мышек. Внучка заменяет 4•5•6 Мышек. Бабка заменяет 3•4•5•6 Мышек. Дедка заменяет 2•3•4•5•6 Мышек. Итого потребуется:
(2•3•4•5•6) + (3•4•5•6) + (4•5•6) + (5•6) + 6 + 1 = 1237 Мышек.

Ответ

1237 Мышек.

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

Задача 103836

Темы:	[	Арифметика. Устный счет и т.п.	]
Темы:	[	Обратный ход	]

Сложность: 2
Классы: 7,8

Автор: Калинин Д.А.

На прямой отметили несколько точек. После этого между каждыми двумя соседними точками отметили ещё по точке. Такое ''уплотнение'' повторили ещё дважды (всего 3 раза). В результате на прямой оказалось отмечено 113 точек. Сколько точек было отмечено первоначально?

Подсказка

Найдите, сколько точек было перед последним уплотнением, т. е. решайте задачу ''с конца''.

Решение

Если (до уплотнения) было отмечено n точек, то после уплотнения будет отмечено 2n - 1 точек (из которых n старых и n - 1 новая). Если после уплотнения получилось k точек, то 2n - 1 = k или n = (k + 1)/2. Таким образом, до последнего уплотнения было (113 + 1)/2 = 57 точек, до второго — (57 + 1)/2 = 29 точек и в самом начале — (29 + 1)/2 = 15 точек.

Ответ

15 точек.

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

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 44]