Всего: 96 1–20 | 21–40 | 41–60 | 61–80 | 81–96
Добавить в вариант
Назовем бесконечную числовую последовательность {an} стабилизирующейся, если при некотором k0 для всех 
выполнено 
Тогда k0 назовем временем стабилизации ak (при 
) —
Пусть a, b — натуральные числа. Дана последовательность {xn}, в которой 
и для любого натурального n выполнены равенства 
(здесь 
— это операция взятия целой части при делении на b),
—Какие из последовательностей 
стабилизируются, и чему равны их стабильные значения? Чему равно время стабилизации последовательности 
We call an infinite number sequence 
stabilizing if 
for some 
and for all 
Then will be called stabilization time, and 
(for ) will be called stable value.
Let 
be positive integers. There is a sequence 
which has and for any positive integer n it satisfies the equalities 
(here ob is the operation of taking the whole part when dividing by 
(here 
is the operation of taking the remainder of division by b).
Which of the sequences stabilizes, and what are their stable values? What is the stabilization time for the sequence 
По ее определению имеем 
для всех целых 
ее стабильное значение равно а, а при 
она не стабилизируется.
По определению, если 
то 
для всех целых 
а если 
то 
и, поскольку последовательность — целочисленная, имеем 
для всех n, начиная с 
(целая часть от логарифма, взятая с избытком).
для всех целых 
База индукции 
по определению. Индукционная гипотеза: пусть для некоторого 
вы полнено 
Тогда 
В силу доказанного выше, если 
следовательно, стабильное значение последовательности 
(the ceil function of the logarithm).
by definition. Induction hypothesis: let 
hold for some 
from 
thus the stable value of the sequence 
стабилизируется на а при 
стабилизируется на а при 
и на 
при 
Последовательные нечётные натуральные числа выписывают «по спирали», как показано на рисунке. Числа 3, 15 и остальные, находящиеся вместе с ними на одной прямой, назовём хорошими (на рисунке они выделены серым). Чему равна сумма 2020 наименьших хороших чисел?
(А. Р. Араб)
а хорошее число с номером 2k + 1, наоборот, на 2 меньше, чем отличное с номером 2k + 2. Суммарно получается, что сумма первых 2020 хороших чисел равна сумме отличных чисел с номерами от 2 до 2021, то есть 
Теперь докажем исходное утверждение по индукции. База: подставляя 
что верно. Переход: если уже известно, что 
получаем 
Лемма доказана. 
где 
— натуральные числа. Докажите, что 
делится на произведение 
— это количество способов разбить n объектов на m пронумерованных групп, при котором в первую группу попадёт 
объектов, ..., в m-ю группу 
объектов. Значит, это целое число. Что и требовалось доказать.
оно, очевидно, справедливо. Переход: заметим, что 
Для них организованы кружки, каждый из которых посещают хотя бы двое. Каждые два кружка, у которых есть хотя бы два общих ученика, отличаются по количеству участников. Докажите, что кружков не более 
имеется не более 
кружков, в которые ходят ровно k человек. Действительно, поскольку ни меньше 2, ни больше n человек в кружке не может быть, количество кружков не превосходит 
Таким образом, суммарное количество кружков не будет превосходить 
участников не пересекаются, а всего для них доступно 
учеников. Значит, x может посещать не более 
кружков. Суммарное количество школьников во всех «списках участников кружков» не превосходит 
Так как в каждом таком списке ровно k школьников, всего кружков не более 
что и требовалось доказать.У Миши есть шахматная доска 100 × 100 и мешок со 199 ладьями. За один ход можно либо поставить одну ладью из мешка на левую нижнюю клетку, либо снять две ладьи, стоящие на одной клетке, одну из них поставить на клетку, соседнюю сверху или справа, а другую убрать в мешок. Миша хочет расставить на доске 100 не бьющих друг друга ладей. Любую ли такую расстановку он сможет получить?
ладей. B задуманной Мишей расстановке ладей есть клетка (100, y100) в правом столбце — чтобы поставить туда ладью, потребуется не более 
ладей. После этого для постановки ладьи в клетку (99, у99) потребуется не более 
ладей, и они у Миши есть, даже учитывая, что одна ладья уже стоит на своём месте. И так далее, двигаясь справа налево, можно расставить все ладьи.
выполняется соотношение 
Тогда 
и 
Тогда 
и 
Рассмотрим случай 
Тогда
где 
Для начальных n проверили. Предположим, что для некоторого значения n верно равенство 
и 
Докажем, что 
Действительно, 
База 
проверяется; переход: 
для всех 
Таким образом, имеет смысл искать решения с k в диапазоне от 
до 
то в числе сомножителей n! найдутся k, 2k и 3k, а значит, n! будет делиться на 
Несложно заметить, что тогда 
будет делиться на 
Значит, для 
имеет смысл искать решения для 
где 
—
делится на 
значит, n! делится на 
—
поскольку 
и кратен 
То есть опять-таки число n!, а значит и число 
что, как мы видели выше, противоречит неравенствам в условии задачи. То есть, решений нет.Последовательность слов w0, w1, w2, 
и 
для любого натурального n. Таким образом, 
и так далее. Пусть значение функции L(n) для натурального n равно количеству символов в слове wn. Найдите 
Let infinite sequence of words w0, w1, w2, и for any positive integer n. Thus, 
and so on. Let function L(n) be equal to the number of symbols in wn for any positive integer n. What is 
следовательно, 
(доказывается по индукции).
В ряд записаны 1234 целых числа. За один шаг первый игрок указывает на несколько из них, записанных подряд, а второй игрок либо увеличивает каждое из указанных чисел на 1, либо уменьшает каждое из них на 1. Найдите наибольшее k, такое, для которого первый всегда за несколько шагов сможет добиться, чтобы хотя бы k чисел стали делиться на 3.
There is a row of 1234 integers. In one step, the first player points to several of them written oneby-another, and the second player for each of the numbers increases it by 1 or decreases it by 1. Find the largest k, such that the first player can always make at least k numbers be divisible by 3.
Будем вести доказательство по индукции по количеству n целых чисел в ряду. При 
утверждение 
очевидно. Для произвольного 
рассмотрим два числа, которые стоят по краям отрезка. Если одно из них делится на 3, то будем рассматривать отрезок без этого числа и применим предположение индукции. В противном случае либо у этих чисел разные ненулевые остатки по модулю 3, либо одинаковые. Если остатки одинаковые, то попросим поменять одно из этих чисел. Тогда оно либо станет делиться на 3, либо будет иметь другой ненулевой остаток, что сводит нашу задач к случаю разных остатков на концах отрезка. Но тогда, попросив поменять числа во всем отрезке, мы получим, что одно из чисел на конце отрезка станет делиться на 3.
For an arbitrary В ряд записаны 1200 целых чисел. За один шаг первый игрок указывает на несколько из них, записанных подряд, а второй игрок либо увеличивает каждое из указанных чисел на 1, либо уменьшает каждое из них на 1. Найдите наибольшее k, такое, для которого первый всегда за несколько шагов сможет добиться, чтобы хотя бы k чисел стали делиться на 3.
There is a row of 1200 integers. In one step, the first player points to several of them written oneby-another, and the second player for each of the numbers increases it by 1 or decreases it by 1. Find the largest k, such that the first player can always make at least k numbers be divisible by 3.
Последовательность x1, 
и 
для любого целого неотрицательного n. Докажите, что найдется n0, такое, что 
для Bcex 
Infinite sequence x1, 
for every non-negative integer n. Prove that there is a number n0 such that for every
для всех 
и база индукции доказана. Индукционная гипотеза: пусть для некоторого 
Имеем 
(согласно индукционной гипотезе)
и всех 
выполнено 
Для этого надо показать, что для всех этих n верно 
следует из 
Что требовалось доказать.
that the sequence described in the task coincides with the sequence 
for all non-negative integers n. Base of the induction: let 
и правилом 
если an — четное, 
если an — нечетное. Докажите, что в этой последовательности встретится число, делящееся на 4.
то 
делится на 4.
Последовательно находим: 
делится на 4, значит, далее можно считать, что k нечетно.
Мы обнаружили, что 
нечетно, подставим 
и продолжим вычисления:
чётно, а 
нечётно при всех n. Докажем по индукции следующий факт: если за 2n операций мы так и не смогли ни разу получить число, кратное 4, то a1 даёт остаток 
при делении на 
Но при больших n это неравенство не может быть выполнено, поэтому последовательность все-таки содержит числа, кратные 4. Для краткости вычислений будем писать вместо остатка 
—
Тогда 
даёт остаток −2 при делении на 
значит, 
даёт остаток −2 при делении на 
т. е. 
имеет остаток −3. Тогда a1 имеет остаток −1 при делении на 
—Пусть n > 1 — целое число. В одной из клеток бесконечной белой клетчатой доски стоит ладья. Каждым ходом она сдвигается по доске ровно на n клеток по вертикали или по горизонтали, закрашивая пройденные n клеток в чёрный цвет. Сделав несколько таких ходов, не проходя никакую клетку дважды, ладья вернулась в исходную клетку. Чёрные клетки образуют замкнутый контур. Докажите, что число белых клеток внутри этого контура даёт при делении на n остаток 1.
(Александр Грибалко)
Её площадь равна 
а поскольку сумма внешних углов (с учётом знаков) равна 360°, то внешних углов в 90° на 4 больше, чем внешних углов в −90°, то есть внутренних углов в 90° на 4 больше, чем углов в 270°. Поэтому площадь чёрной каёмки внутри контура меньше суммарной площади полосок на 1. Значит, чёрная площадь внутри многоугольника равна bn − 1, а белая площадь внутри равна тогда 
откуда 
у квадрата, внутри него находится 
белых клеток. Шаг индукции. Пусть периметр больше 
Ron Weasley grew up and realized that at Hogwarts he st udied magic, but did not st udy mathemat ics He began studying mathematics with the theory of sets and natural numbers (non-negative int egers including the number 0). First of all, he thought about how to represent natural numbers as sets. Ron reasoned as follows: zero is nat urally represented by the empty set ∅. Well, if for some integer 
the representation of this number An has already been constructed, then we represent the next number (n + 1) by the set 
Ron Weasley wrot e out the represent at ion of the first three (st art ing from 0) non-negative integers:
— 
— 
— 
Ron noticed that the A0 set is written with 1 character, A1 — with 7 characters, and A2 set — with 19 characters. How many characters are required to write the set A7?
Рон Уизли повзрослел и понял, что в Хогвартсе он изучил магию, но не изучил математики. Изучение математики он начал с теории множеств и натуральных чисел (включая число 0). Первым делом он задумался, как представить натуральные числа множествами. Рон рассуждал следующим образом: ноль естественно представлять пустым множеством ∅. Ну а если для какого-либо натурального числа представление этого числа An уже построено, то попробуем представить следующее число (n + 1) множеством 
Рон Уизли не поленился и выписал представление трех первых (начиная с 0) натуральных чисел:
—
—
—
Рон заметил, что множество A0 записывается 1 символом, множество A1 — 7 символами, множество A2 — 19 символами. А сколько символов требуется для записи множества A7?
(opening curly brace) 
(comma) +1 (opening curly brace) 
Назовем тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность (an) строится следующим образом: a0 = 0, a1 = 1, и при 
число an — такое минимальное натуральное число, большее 
что среди чисел 
нет трёх, образующих триплет. Докажите, что 
(Б. Бутырин)
Обозначим число, троичная запись которого совпадает с b(n), через b(n)3; например, 
дана в определении. Переход: пусть для всех 
троичная запись числа ai совпадает с b(i). Необходимо доказать, что, во-первых, число b(n)3 не образует триплета с какими-нибудь ai и aj для 
и, во-вторых, никакое меньшее число не удовлетворяет этому условию.
и 
Заметим, что при сложении чисел b(i)3 и b(n)3 в троичной системе счисления не возникает переходов через разряд, поэтому, если в результате получилось число 
то на всех позициях, где в строке b(j) стоит единица, в обеих строках b(i) и b(n) также стоят единицы, а на всех остальных позициях в этих строках стоят нули. Таким образом, 
из чего следует, что 
Противоречие.
), образует триплет с какими-нибудь ai и aj. Рассмотрим произвольное число x, удовлетворяющее неравенству 
Поскольку 
и 
то два соседних числа, чья троичная запись состоит из нулей и единиц, в троичной записи числа x есть двойка.
а во-вторых, 
Более того, в тех позициях, где в строке sn стоит двойка, выполняется цепочка строгих неравенств 
Значит, 
и числа 
образуют триплет, что и требовалось доказать. Поскольку 
имеем, что в троичной записи числа 
не больше 11 цифр, ни одна из которых не превосходит 1. Значит, 
образуют триплеты с предыдущими членами последовательности, но не доказано, что 
не образует триплетов: ∓.
но не доказано, что В ряд слева направо стоят N коробок, занумерованных подряд числами 
В некоторые коробки, стоящие подряд, положат по шарику, оставив остальные пустыми. Инструкция состоит из последовательно выполняемых команд вида «поменять местами содержимое коробок №і и №j», где і и j — числа. Для каждого ли N существует инструкция, в которой не больше 100N команд, со свойствам: для лобой начальной раскладки указанного вида можно будет, вычеркнув из инструкции некоторые команды, получить инструкцию, после выполнения которой все коробки с шариками будут левее коробок без шариков?
(И. Митрофанов)
сделать инструкцию для 2k и для 2k – 1, этого будет достаточно. Обозначим N = 2k или 2k – 1.
в любом порядке. Если N нечетно, сюда приходится добавить все пары вида 
при 
(назовём эти команды дополнительными).
в любом порядке.
длина этой инструкции не превышает
нет двух камней основного цвета. Все основные камни тогда перенесем справа налево (тогда камни не основного цвета будут среди первых k камней лежать подряд.