РЕШУ ОЛИМП, математика: задания, ответы, решения

Поиск
?

в условии в решении в тексте к заданию в атрибутах
Скопировать ссылку на результаты поиска
Класс: 10 11 6 7 8 9
Атрибут

Всего: 114 1–20 | 21–40 | 41–60 | 61–80 | 81–100 …

Добавить в вариант

Тип 0 № 2311 Добавить в вариант

Можно ли все натуральные числа от 1 до 2018 так расставить по кругу, чтобы сумма любых четырёх подряд стоящих чисел была нечётным числом?

Критерии проверки:

Общая схема:

0 баллов  — выставляется, если участник к решению задачи не приступал или начатый ход решения полностью неверен;

1 балл  — выставляется, если участник приступил к решению задачи, указал верное направление решения задачи и получил правильные промежуточные результаты, но при этом не продвинулся настолько, чтобы можно было судить о том, каким образом он собирался получить окончательный ответ (то есть весь ход решения не представлен);

2 балла  — выставляется, если выбранный участником ход решения задачи является в принципе правильным, но при этом участник не смог его реализовать в силу серьёзных ошибок;

3 балла  — выставляется, если решение является в целом правильным, но содержит ошибки, повлиявшие на ответ;

4 балла  — выставляется, если участник решил задачу в целом правильно и получил верный ответ; при этом в решении допускаются незначительные неточности.

Факторы, влияющие на оценку.

1.  Одна из основных целей Олимпиады  — выявление у обучающихся творческих способностей. Поэтому в случае представления участником интересного оригинального подхода к решению задачи, оценка за решение может быть увеличена на 1 балл.

2.  Правильный ответ к задаче, приведенный без достаточных обоснований, либо при наличии ошибок в решении, либо при отсутствии решения, не ведёт к увеличению оценки, которая выставляется участнику за данную задачу.

3.  Если участник не довел задачу до ответа, то итоговая оценка за данную задачу не может превышать 1 балл.

4.  Если задача решена перебором возможных вариантов, и при этом перебор неполный, то за задачу выставляется до 1 балла. Если участник подобрал частное решение без обоснования и проверил его правильность, то в этом случае за задачу выставляется до 0,5 баллов.

5.  Если задача решена при дополнительном предположении, которое отсутствует в условии, то за задачу выставляется

а)  до 1 балла, если это предположение можно доказать;

б)  до 0,5 баллов, если оно не обязано выполняться, но не противоречит условию задачи;

в)  0 баллов, если оно противоречит условию.

6.  Если в работе приведены два решения или ответа к одной задаче, противоречащие друг другу, то за задачу ставится 0 баллов.

Решение · Критерии · Помощь

Тип 0 № 2346 Добавить в вариант

Юный хакер желает изменить оценки в электронном журнале. Но при изменении одних оценок изменяются и другие, а именно:

а)  если он увеличивает на 2 количество пятерок, то при этом количество двоек уменьшится на 1;

б)  если он увеличивает на 1 количество пятерок, то количество двоек увеличивается на 2;

в)  если он уменьшает на 2 количество пятерок, то количество двоек увеличивается на 1;

г)  если он уменьшает на 1 количество пятерок, то количество двоек уменьшается на 2.

Может ли он, совершая такие операции, превратить свои 3 пятерки и 30 двоек в 30 пятерок и 3 двойки?

Критерии проверки:

Вид погрешности или ошибки	Отметка в работе	Баллы
Каждая задача оценивается по 10-балльной шкале и снабжается отметкой в работе 0, −, ∓, ±, + в соответствии с критериями.
Решение задачи верное, выбран рациональный путь решения	+	10
Решение верное, но путь не рационален или имеются один  — три недочета или негрубая ошибка	+	9
Решение верное, но путь не рационален и имеются один  — три недочета или негрубая ошибка	±	7−8
Ход решения верный, но есть несколько негрубых ошибок или решение не завершено	∓	5−6
Допущены грубые ошибки, но ответ получен (неверный)	∓	3−4
Допущены грубые ошибки и ответ не получен либо решение лишь начато, то что начато  — без ошибок	−	2
Решение начато, но продвижение ничего не дает для результата	−	1
Задача не решилась	0	0
Недочеты: незначительные (непринципиальные) арифметические ошибки. Негрубые ошибки: технические ошибки в применении формул и теорем, не влияющие на смысл решения; необоснованность логических (верных) выводов. Грубые ошибки:    I.  Логические, приводящие к неверному заключению.   II.  Арифметические ошибки, искажающие смысл ответа. III.  Неверный чертеж в геометрических задачах. IV.  Принципиальные ошибки в применении элементарных формул и теорем.

Решение · Критерии · Помощь

Тип 0 № 3141 Добавить в вариант

Даны m натуральных чисел, не превосходящих n, расположенные в порядке неубывания: $a_1 меньше или равно a_2 меньше или равно ... меньше или равно a_m.$ Аналогично n натуральных чисел, не превосходящих m, расположены в порядке неубывания: $b_1 меньше или равно b_2 меньше или равно ... меньше или равно b_n.$ Верно ли, что всегда найдутся два номера i и j такие, что $a_i плюс i=b_j плюс j.$

Баллы
20	Обоснованно получен правильный ответ.
15	В целом решение правильное, но имеются недостатки в обосновании.
10	В решении указаны общие границы для чисел $ai плюс i левая круглая скобка i =1, \ldots, m правая круглая скобка$ и $bj плюс j левая круглая скобка j =1, \ldots, n правая круглая скобка ,$ но не получен обоснованный ответ (например, нигде не указано, что числа $ai плюс i$ все различны, как и числа $bj плюс j правая круглая скобка .$
5	Построены цепочки чисел.
0	Решение не соответствует ни одному из критериев.

Решение · Критерии · Помощь

Тип 0 № 3214 Добавить в вариант

а)  Можно ли занумеровать ребра куба числами 1, 2, ..., 12 так, чтобы для каждой вершины сумма номеров трёх выходящих из неё ребер была одной и той же?

б)  Можно ли вычеркнуть одно из чисел 1, 2, ..., 12, 13 и оставшимися занумеровать ребра куба так, чтобы выполнялось то же условие?

Решение · Помощь

Тип 0 № 3422 Добавить в вариант

Можно ли из 37 ниток сплести сетку так, чтобы каждая нитка была связана ровно с пятью другими?

Решение · Помощь

Тип 0 № 3574 Добавить в вариант

Можно ли на клетчатой бумаге расположить восьмиугольник так, чтобы все его вершины находились в узлах клетки, если известно, что этот многоугольник: а) равносторонний; б) равноугольный; в) правильный.

Решение · Помощь

Тип 0 № 3946 Добавить в вариант

Дан параллелограмм $ABCD.$ Можно ли утверждать, что ABCD  — прямоугольник, если известно, что:

а)  радиусы вписанных окружностей треугольников ABC и ABD совпадают;

б)  радиусы описанных окружностей треугольников ABC и ABD совпадают.

Решение · Помощь

Тип 0 № 3956 Добавить в вариант

Имеется n гирек, каждая весит целое число граммов, а суммарный их вес равен 100 гр. Верно ли, что все гирьки всегда можно разложить на две чаши весов так, чтобы они уравновесились, если а) $n =50;$ б) $n =51?$

Решение · Помощь

Тип 0 № 3960 Добавить в вариант

Имеется n гирек, каждая весит целое число граммов, а суммарный их вес равен $2k$ (гр). Верно ли, что все гирьки всегда можно разложить на две чаши весов так, чтобы они уравновесились, если а) $n=k;$ б) $n=k плюс 1?$

Решение · Помощь

Тип 0 № 4027 Добавить в вариант

Имеется n гирек весом 1, 2, ..., n (гр) и двухчашечные весы. Можно ли все гирьки разложить на весах так, чтобы на одной чаше было вдвое больше гирек, чем на другой, и весы уравновесились: a) при $n = 90;$ б) при $n = 99?$

Решение · Помощь

Тип 0 № 4155 Добавить в вариант

Можно ли переставить цифры в 30-значном числе 11...122...233...3 (в котором 10 единиц, 10 двоек и 10 троек) так, чтобы получился квадрат натурального числа?

Критерии проверки:

Каждая из четырёх задач данной олимпиады оценивается, исходя из максимума в 25 баллов. Таким образом, максимальный результат участника может быть 100 баллов. Соответствие правильности решения и выставляемых баллов приведено в таблице.

Символы-баллы	Правильность (ошибочность) решения
+25	Полное верное решение
+20	Верное решение. Имеются небольшие недочеты, в целом не влияющие на решение.
±16	Решение в целом верное, но содержит мелкие ошибки, либо пропущены случаи, не влияющие на логику рассуждений.
+/2 13	Верно рассмотрен один (более сложный) из существенных случаев, верно получена основанная оценка.
±10	Доказаны вспомогательные утверждения, помогающие в решении задачи.
−5	Рассмотрены только отдельные важные случаи или имеются начальные продвижения.
0	Решение неверное, продвижения отсутствуют.
0	Решение отсутствует (участник не приступал).

Если в задаче два пункта, то только за один решенный пункт максимальная оценка 13 баллов. Рекомендуется сначала оценивать задачу в символах («плюс-минусах»); при необходимости оценку в символах можно дополнить значком-стрелкой вверх или вниз, что скорректирует соответствующую оценку на один балл. Например, символ $\pm \uparrow$ будет соответствовать 17 баллам.

Решение · Критерии · Помощь

Тип 0 № 4160 Добавить в вариант

а)  Даны натуральные числа a и b, такие, что $3 a плюс b$ и $3 b плюс a$ дают одинаковые остатки при делении на 10. Верно ли, что сами числа a и b дают одинаковые остатки при делении на 10?

б)  Верно ли, что натуральные числа a, b и c дают одинаковые остатки при делении на 10, если три числа $2a плюс b,$ $2b плюс c$ и $2c плюс a$ дают одинаковые остатки при делении на 10?

Критерии проверки:

Символы-баллы	Правильность (ошибочность) решения
+25	Полное верное решение
+20	Верное решение. Имеются небольшие недочеты, в целом не влияющие на решение.
±16	Решение в целом верное, но содержит мелкие ошибки, либо пропущены случаи, не влияющие на логику рассуждений.
+/2 13	Верно рассмотрен один (более сложный) из существенных случаев, верно получена основанная оценка.
±10	Доказаны вспомогательные утверждения, помогающие в решении задачи.
−5	Рассмотрены только отдельные важные случаи или имеются начальные продвижения.
0	Решение неверное, продвижения отсутствуют.
0	Решение отсутствует (участник не приступал).

Решение · Критерии · Помощь

Тип 0 № 4168 Добавить в вариант

а)  Докажите, что существует возрастающая геометрическая прогрессия, из которой можно выбрать три члена (не обязательно соседние), образующие арифметическую прогрессию.

б)  Может ли знаменатель такой геометрической прогрессии быть больше 1,9?

Критерии проверки:

Символы-баллы	Правильность (ошибочность) решения
+25	Полное верное решение
+20	Верное решение. Имеются небольшие недочеты, в целом не влияющие на решение.
±16	Решение в целом верное, но содержит мелкие ошибки, либо пропущены случаи, не влияющие на логику рассуждений.
+/2 13	Верно рассмотрен один (более сложный) из существенных случаев, верно получена основанная оценка.
±10	Доказаны вспомогательные утверждения, помогающие в решении задачи.
−5	Рассмотрены только отдельные важные случаи или имеются начальные продвижения.
0	Решение неверное, продвижения отсутствуют.
0	Решение отсутствует (участник не приступал).

Решение · Критерии · Помощь

Тип 0 № 4172 Добавить в вариант

Из 25 натуральных чисел 1, 2, ..., 25 требуется выбрать несколько различных чисел и расположить их по кругу так, чтобы сумма квадратов любых трех подряд идущих чисел делилась на 10. Можно ли выбрать а) 8 чисел?; б) 9 чисел?

Решение.

а)  Предположим, от противного, что такое расположение возможно. Возьмём соседние тройки чисел и вычтем из суммы квадратов первой тройки сумму квадратов второй. Получим, что квадрат каждого числа на круге даёт тот же остаток при делении на 10, что и квадрат числа, расположенного по кругу через два. (Другими словами, (a_i)² и (a_i + 3)² оканчиваются одной и той же цифрой при всех i.) «Прыгая» от любого числа на круге через два (на третье), мы обойдём весь круг (так как 8 взаимно просто с тройкой). Значит, квадраты всех восьми чисел оканчиваются одной и той же цифрой. Но в каждой десятке подряд идущих натуральных чисел есть не более двух чисел, квадраты которых оканчиваются одинаковой цифрой (а именно, такими парами являются числа, оканчивающиеся на 1 и 9, на 2 и 8, на 3 и 7, на 4 и 6). Поэтому от 1 до 25 будет не более 6 чисел с одинаковыми последними цифрами квадрата (точнее, их не более пяти, т. к. от 21 до 25 таких пар не будет.) Противоречие.

б)  Учитывая предыдущие рассуждения, нетрудно привести пример расположения 9 чисел: 1, 2, 5, 11, 12, 15, 21, 22, 25, для этого достаточно подобрать всего одну тройку с нужным свойством, а затем использовать периодичность с периодом 3.

Ответ: а) нельзя; б) можно.

Критерии проверки:

Символы-баллы	Правильность (ошибочность) решения
+25	Полное верное решение
+20	Верное решение. Имеются небольшие недочеты, в целом не влияющие на решение.
±16	Решение в целом верное, но содержит мелкие ошибки, либо пропущены случаи, не влияющие на логику рассуждений.
+/2 13	Верно рассмотрен один (более сложный) из существенных случаев, верно получена основанная оценка.
±10	Доказаны вспомогательные утверждения, помогающие в решении задачи.
−5	Рассмотрены только отдельные важные случаи или имеются начальные продвижения.
0	Решение неверное, продвижения отсутствуют.
0	Решение отсутствует (участник не приступал).

Решение · Критерии · Помощь

Тип 0 № 4177 Добавить в вариант

б)  Может ли знаменатель такой геометрической прогрессии быть рациональным числом?

Критерии проверки:

Символы-баллы	Правильность (ошибочность) решения
+25	Полное верное решение
+20	Верное решение. Имеются небольшие недочеты, в целом не влияющие на решение.
±16	Решение в целом верное, но содержит мелкие ошибки, либо пропущены случаи, не влияющие на логику рассуждений.
+/2 13	Верно рассмотрен один (более сложный) из существенных случаев, верно получена основанная оценка.
±10	Доказаны вспомогательные утверждения, помогающие в решении задачи.
−5	Рассмотрены только отдельные важные случаи или имеются начальные продвижения.
0	Решение неверное, продвижения отсутствуют.
0	Решение отсутствует (участник не приступал).

Решение · Критерии · Помощь

Тип 0 № 4178 Добавить в вариант

Может ли длина одной из медиан прямоугольного треугольника составлять а) 51% от длины гипотенузы? б) 49% от длины гипотенузы?

Критерии проверки:

Символы-Баллы	Правильность (ошибочность) решения
+20	Полное верное решение
+.16	Верное решение. Имеются небольшие недочеты, в целом не влияющие на решение
±12	Решение в целом верное, но содержит ошибки, либо пропущены случаи, не влияющие на логику рассуждений
+/2 10	Верно рассмотрен один (более сложный) из существенных случаев, верно получена основная оценка
∓8	Доказаны вспомогательные утверждения, помогающие в решении задачи
−.4	Рассмотрены только отдельные важные случаи или имеются начальные продвижения
−0	Решение неверное, продвижения отсутствуют
0	Решение отсутствует (участник не приступал)

Если в задаче два пункта, то только за один решенный пункт максимальная оценка 10 баллов, а другие (промежуточные) оценки соответствуют половинкам баллов приведенной таблицы. Рекомендуется сначала оценивать задачу в символах («плюс-минусах»); при необходимости оценку в символах можно дополнить значком–стрелкой вверх или вниз, что скорректирует соответствующую оценку на один балл. Например, символ ±↑ будет соответствовать 13 баллам.

Решение · Критерии · Помощь

Тип 0 № 4409 Добавить в вариант

У Васи есть камень (однородный, без внутренних полостей), имеющий форму выпуклого многогранника, у которого есть только треугольные и шестиугольные грани. Вася утверждает, что он разбил этот камень на две части так, что можно сложить из них куб (без внутренних полостей). Могут ли слова Васи быть правдой?

Решение · Помощь

Тип 0 № 4447 Добавить в вариант

Детектив Ниро Вульф расследует преступление. В деле замешаны 80 человек, среди которых один  — преступник, ещё один  — свидетель преступления (но неизвестно, кто это). Каждый день детектив может пригласить к себе одного или нескольких из этих 80 человек, и если среди приглашённых есть свидетель, но нет преступника, то свидетель сообщит, кто преступник. Может ли детектив заведомо раскрыть дело за 12 дней?

Решение.

Докажем, что Ниро Вульф заведомо сможет найти преступника за 12 дней. Людей, замешанных в деле, будем называть подозреваемыми. Сопоставим каждому из 80 подозреваемых свой упорядоченный набор (a, b, c, d) из четырех не обязательно различных цифр a, b, c и d, каждая из которых может принимать значения 0, 1 или 2. Это возможно, поскольку всего таких различных наборов $3 в степени левая круглая скобка 4 правая круглая скобка =81.$ Пусть в день расследования под номером k $левая круглая скобка k=1, 2, \ldots, 12 правая круглая скобка$ Ниро Вульф пригласит к себе тех и только тех подозреваемых, набор цифр которых удовлетворяет k-му из равенств:

$a=0,$ $a=1,$ $a=2,$ $b=0,$ $b=1,$ $b=2,$ $c=0,$ $c=1,$ $c=2,$ $d=0,$ $d=1,$ $d=2.$

Тогда в один из этих дней он пригласит к себе свидетеля, но при этом не пригласит преступника, так как их наборы отличаются хотя бы в одной цифре. Значит, преступление будет раскрыто за 12 дней.

Ответ: да, может.

Приведем другое решение.

Разобьем подозреваемых на 16 групп по 5 человек. При этом каждой из групп сопоставим свой упорядоченный набор (a, b, c, d) из четырех не обязательно различных цифр a, b, c и d, каждая из которых может принимать значения 0 или 1 (это возможно, поскольку всего таких различных наборов $2 в степени левая круглая скобка 4 правая круглая скобка =16 правая круглая скобка ,$ а ее членов занумеруем числами от 1 до 5.

Пусть в день расследования под номером $k левая круглая скобка k=1, \ldots, 8 правая круглая скобка$ Ниро Вульф пригласит к себе тех и только тех подозреваемых, набор цифр которых удовлетворяет k-му из равенств:

$a=0,$ $a=1,$ $b=0,$ $b=1,$ $c=0,$ $c=1,$ $d=0,$ $d=1.$

Если преступник и свидетель попали в разные группы, то преступление будет раскрыто в один из этих дней, так как наборы цифр группы свидетеля и группы преступника отличаются хотя бы в одной цифре.

Предположим, что свидетель находится в одной группе с преступником. Обозначим через m и n номера свидетеля и преступника в этой группе соответственно. Пусть на 9-й день Ниро Вульф пригласит из каждой группы подозреваемых с номерами 1 и 2, на 10-й день  — подозреваемых с номерами 3 и 4, на 11-й день  — подозреваемых с номерами 1, 3 и 5, на 12-й день  — подозреваемых с номерами 2, 4 и 5. Тогда найдется один из этих дней, в который из каждой группы были приглашены подозреваемые с номером m, но при этом не были приглашены подозреваемые с номером n. Значит, в этот день преступление будет раскрыто.

Приведем еще одно решение.

Покажем, что Ниро Вульф сможет найти преступника даже за 9 дней. Для этого сопоставим каждому подозреваемому свой код  — упорядоченный набор из девяти цифр, четыре из которых единицы, а пять нули (это можно сделать, так как всего таких кодов $C_9 в степени левая круглая скобка 4 правая круглая скобка =126 больше 80 правая круглая скобка .$

Пусть Ниро Вульф в k-й день $левая круглая скобка k=1, 2, \ldots, 9 правая круглая скобка$ пригласит к себе тех и только тех подозреваемых, k-я цифра кода которых равна 1. Поскольку все коды содержат ровно по 4 единицы, найдется такое число m от 1 до 9, что на m-м месте у свидетеля стоит единица, а у преступника  — ноль. Значит, в m-й день свидетель будет приглашен к Ниро Вульфу без преступника, и преступление будет раскрыто.

Комментарий.

Пользуясь методом, использованным в третьем способе решения, можно показать, что за 12 дней детектив сможет раскрыть дело, если в нем замешаны не более $C_12 в степени левая круглая скобка 6 правая круглая скобка =924$ подозреваемых.

Более того, эта оценка точная, что вытекает из следующего факта. Пусть A  — множество всех подмножеств некоторого n-элементного множества. Рассмотрим такое подмножество B множества A, что никакие два элемента из B не вложены друг в друга (такое подмножество B называется антицепью). Доказанная в 1928 году теорема Шпернера (https://en.wikipedia.org/wiki/Sperner's_theorem) утверждает, что максимальное число элементов, которое может содержать B, равно $C_n в степени левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка .$ Здесь $левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка$ обозначает наибольшее целое число, не превосходящее $дробь: числитель: n, знаменатель: 2 конец дроби .$

Из этой теоремы следует, что максимальное число подозреваемых, среди которых заведомо можно выявить преступника за n дней, равно $C_n в степени левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка .$ Действительно, сопоставим каждому из подозреваемых код из нулей и единиц длины n, в котором на k-м месте стоит 1, если в k-й день он был приглашен к Ниро Вульфу, и 0 в противном случае. Такой код однозначно определяет подмножество дней, в которые подозреваемый побывал у детектива. Чтобы дело было раскрыто, в какой-то день свидетель должен побывать у Ниро Вульфа без преступника. Это произойдет, если существует такое число $k левая круглая скобка k=1, 2, \ldots, n правая круглая скобка ,$ что на k-м месте в коде свидетеля стоит 1, а в коде преступника стоит 0. Максимальное число кодов, при котором это можно гарантировать, в соответствии с теоремой Шпернера как раз равно $C_n в степени левая круглая скобка левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка правая круглая скобка$ (при этом в каждом коде будет ровно $левая квадратная скобка дробь: числитель: n, знаменатель: 2 конец дроби правая квадратная скобка$ единиц).

Из полученного результата можно сделать и такой вывод: минимальное число дней, за которое можно заведомо выявить преступника среди 80 подозреваемых, равно девяти, так как за 8 дней преступника можно найти лишь среди не более $C_8 в степени левая круглая скобка 4 правая круглая скобка =70$ человек.

Решение · Помощь

Тип 0 № 4500 Добавить в вариант

В ряд лежат 100N бутербродов, каждый с колбасой и сыром. Дядя Федор и кот Матроскин играют в игру. Дядя Федор за одно действие съедает один бутерброд с одного из краев. Кот Матроскин за одно действие может стянуть колбасу с одного бутерброда (а может ничего не делать). Дядя Федор каждый ход делает по 100 действий подряд, а кот Матроскин делает только 1 действие; дядя Федор ходит первым, кот Матроскин вторым, далее ходы чередуются до тех пор, пока дядя Федор не доест все бутерброды. Дядя Федор выигрывает, если последний съеденный им бутерброд был 8 с колбасой. Верно ли, что при каждом натуральном N он сможет выиграть независимо от ходов кота Матроскина?

Решение.

Докажем, что при $N=3 в степени левая круглая скобка 100 правая круглая скобка$ выиграет кот Матроскин. Для этого необходимо, чтобы на последнем шаге дяди Федора все оставшиеся 100 бутербродов оказались без колбасы (иначе он сможет выбрать последовательность действий так, чтобы закончить на бутерброде с колбасой). Пронумеруем бутерброды по порядку. Стратегию кота Матроскина разделим на несколько стадий. Сначала покажем, что он может действовать так, чтобы к моменту, когда останется треть от исходного количества бутербродов, все бутерброды, номер которых дает остаток 1 при делении на 100, были без колбасы.

Отметим в каждой сотне бутербродов тот бутерброд, номер которого дает остаток 1 при делении на 100. Пусть за первые 3⁹⁹ ходов кот Матроскин стянет колбасу с каждого отмеченного бутерброда среди центральной трети бутербродов. Так как дядя Федор за это время съедает $3 в степени левая круглая скобка 99 правая круглая скобка умножить на 100$ бутербродов, никакие бутерброды среди центральной трети съедены не будут. Следующие 3⁹⁹ ходов кот Матроскин будет забирать колбасу с произвольного отмеченного бутерброда, а если отмеченных бутербродов с колбасой не останется  — ничего не делать. Так как за один ход дядя Федор съедает не более одного отмеченного бутерброда (см. замечание 1), то еще через 3⁹⁹ ходов все оставшиеся отмеченные бутерброды будут без колбасы.

На следующей стадии своей стратегии кот Матроскин аналогичным образом добьется того, чтобы все бутерброды, номер которых дает остаток 2 при делении на 100, оказались без колбасы; при этом количество бутербродов снова уменьшится в 3 раза. На каждой следующей стадии он будет освобождать от колбасы очередной остаток от деления на 100; через сто стадий, когда останется ровно 100 бутербродов, они все будут без колбасы.

Ответ: нет.

Комментарии.

1.  Каждым ходом дядя Федор будет съедать бутерброды с номерами, дающими различные остатки от деления на 100, даже если съедает их с двух сторон. Это можно понять, заметив, что до его хода количества бутербродов для каждого остатка одинаковы, так как общее их количество кратно 100 ; и после его хода ситуация такая же.

2.  Можно уточнить стратегию кота Матроскина, показав, что при $N=2 в степени левая круглая скобка 100 правая круглая скобка$ он тоже выигрывает; на каждой стадии количество бутербродов при этом будет уменьшаться в два раза. Для этого колбасу ему нужно стягивать только с тех бутербродов (с номерами, дающими данный остаток от деления на 100), до которых дядя Федор на данной стадии гарантированно не доберется. Нетрудно понять, что такой бутерброд действительно всегда будет находиться.

А вот при $N=2 в степени левая круглая скобка 100 правая круглая скобка минус 1$ уже выигрывает дядя Федор. Действительно, первыми $2 в степени левая круглая скобка 99 правая круглая скобка минус 1$ ходами он съест любые $2 в степени левая круглая скобка 99 правая круглая скобка минус 1$ сотен бутербродов; за это время усилиями соперника появится не более $2 в степени левая круглая скобка 99 правая круглая скобка минус 1$ бутербродов без колбасы. Далее, если перед дядей Федором лежит $2 в степени левая круглая скобка k правая круглая скобка$ сотен бутербродов, из которых не более $левая круглая скобка 100 минус k правая круглая скобка умножить на 2 в степени левая круглая скобка k правая круглая скобка минус 1$ без колбасы, то при $k больше 0$ он может съесть ту половину ряда (правую или левую), в которой бутербродов без колбасы больше. Тогда их в ряду останется не более $левая круглая скобка 100 минус k правая круглая скобка умножить на 2 в степени левая круглая скобка k минус 1 правая круглая скобка минус 1$ плюс, благодаря коту Матроскину, не более $2 в степени левая круглая скобка k минус 1 правая круглая скобка$ новых - всего не более $левая круглая скобка 100 минус k плюс 1 правая круглая скобка 2 в степени левая круглая скобка k минус 1 правая круглая скобка минус 1.$ Продолжая так и далее, при $k=0$ дядя Федор получит сто бутербродов, из которых не более 99 будут без колбасы.

Решение · Помощь

Тип 0 № 4511 Добавить в вариант

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

Решение.

Представим описанную в условии сеть дорог в виде графа, вершинами которого являются города, раз вилки и перекрестки, а ребрами  — дороги. Покажем, что этот граф является деревом, то есть связным графом без циклов. Связность следует из того, что из любого города можно проехать в любой другой, а любая развилка или перекресток должны быть соединены с каким-либо городом. Допустим, что в нашем графе есть цикл. Он не содержит двух и более вершин-городов, так как в этом случае, двигаясь в противоположных направлениях по циклу, мы могли бы получить два различных пути из одного города в другой. Далее, пусть между некоторыми городами A и B существует путь, содержащий какую-то вершину цикла. Он обязательно найдется, так как иначе эта вершина не могла бы быть в нашей сети. Но тогда, добавляя к этому пути «кольцо» вдоль цикла, мы получим еще один путь между A и B. Значит, циклов в нашем графе быть не может и это действительно дерево.

По условию задачи все концевые вершины дерева  — города. Назовем эти города концевыми. Назовем также концевой город B следующим за концевым городом A, если по пути из A в B на каждой развилке выбирается самая правая дорога. Выберем какой-нибудь концевой город A₁ и измерим расстояние между ним и следующим за ним концевым городом A₂. Потом измерим расстояние между A₂ и следующим за ним концевым городом A₃ и так далее. После не более чем 100 таких измерений мы вернемся в исходный город A₁.

Покажем, что при этом каждая дорога нашей сети будет пройдена ровно два раза в противоположных направлениях. Рассмотрим произвольную дорогу. При удалении из дерева любого ребра оно распадается на две компоненты связности K₁ и K₂, причем каждая из них содержит города. Пусть изначально мы находились в K₁. Поскольку необходимо обойти все города сети, мы должны пройти по этой дороге два раза: первый раз  — когда движемся из K₁ в K₂, а второй  — когда возвращаемся обратно. Процедура обхода устроена таким образом, что мы посетим все вершины компоненты K₂ до того, как покинем ее, поэтому больше проходить по дороге из K₁ в K₂ не потребуется.

Наконец, сложив измеренные величины и разделив сумму пополам, мы получим длину всей сети.

Ответ: да, можно.

Решение · Помощь

Всего: 114 1–20 | 21–40 | 41–60 | 61–80 | 81–100 …