Задачу по Олимп математике)
1. Саша отметил на прямой 200 точек и дня каждых двух точек выписано расстояние между ними. Все 19900 чисел оказались целыми, и одно из них равно 2023. Саша подчеркнул все числа, не делящиеся на 4.Какое наименьшее количество чисел по шло оказаться в тетрадке?
Модель задачи. Задачу можно вполне описать последовательностью из 199 чисел (это расстояния между соседними точками); причём числа берём из множества {0, 1, 2, 3} (т.к. важны только их остатки от деления на 4). Известно, что среди этих чисел есть хотя бы одно, не равное 0.
Для удобства "частичной суммой" будем называть всякую сумму любого количества (от 1 до 199) последовательно расположенных чисел из нашей последовательности. Частичная сумма может делиться на 4 ("красивая сумма") и не делиться на 4 ("некрасивая сумма").
Требуется найти последовательность с наименьшим количеством некрасивых сумм (или с наибольшим количеством красивых сумм).
Ответ легко угадать, взяв последовательность из одного, двух, трёх чисел. Доказать легко мат. индукцией по количеству чисел в последовательности.
199. Разбиваем точки на 4 класса эквивалентности по отношению "расстояние делится на 4". По условию есть точки хотя бы двух классов. Поэтому для минимума нужно, чтобы все точки (кроме одной) входили в один и тот же класс
Автор вопроса посчитал, что ответ не является полезным. Свернуть ответ
Давайте обозначим расстояния между точками как (a_1, a_2, \ldots, a_{19900}), где каждый (a_i) - целое число. Мы знаем, что одно из этих чисел равно 2023.
Также известно, что Саша подчеркнул все числа, не делящиеся на 4. Это означает, что в каждой паре расстояний хотя бы одно число не делится на 4.
Исходя из этого, давайте рассмотрим 199 пар соседних точек (так как у нас 200 точек, и мы имеем 199 интервалов между ними). Поскольку в каждой паре хотя бы одно число не делится на 4, у нас есть два случая:
Оба числа не делятся на 4.
Одно число делится на 4, а другое нет.
Если оба числа не делятся на 4, то в паре есть одно число, которое делится на 2, и, следовательно, в каждой паре у нас есть хотя бы одно число, которое делится на 2.
Теперь рассмотрим второй случай. Если одно число делится на 4, а другое нет, то оно точно делится на 2.
Таким образом, в каждой паре у нас есть хотя бы одно число, которое делится на 2. Поскольку у нас есть 199 пар, значит, у нас есть как минимум 199 чисел, делящихся на 2.
Теперь у нас есть 199 чисел, делящихся на 2, и одно число, равное 2023, которое не делится на 2. Таким образом, общее количество чисел, не делящихся на 4 (поскольку 2023 не делится на 4), равно 199 + 1 = 200.
Итак, наименьшее количество чисел, которое могло оказаться в тетрадке, равно 200.
Давайте обозначим расстояния между точками как (a_1, a_2, \ldots, a_{19900}), где каждый (a_i) - целое число. Мы знаем, что одно из этих чисел равно 2023.
Также известно, что Саша подчеркнул все числа, не делящиеся на 4. Это означает, что в каждой паре расстояний хотя бы одно число не делится на 4.
Исходя из этого, давайте рассмотрим 199 пар соседних точек (так как у нас 200 точек, и мы имеем 199 интервалов между ними). Поскольку в каждой паре хотя бы одно число не делится на 4, у нас есть два случая:
Оба числа не делятся на 4.
Одно число делится на 4, а другое нет.
Если оба числа не делятся на 4, то в паре есть одно число, которое делится на 2, и, следовательно, в каждой паре у нас есть хотя бы одно число, которое делится на 2.
Теперь рассмотрим второй случай. Если одно число делится на 4, а другое нет, то оно точно делится на 2.
Таким образом, в каждой паре у нас есть хотя бы одно число, которое делится на 2. Поскольку у нас есть 199 пар, значит, у нас есть как минимум 199 чисел, делящихся на 2.
Теперь у нас есть 199 чисел, делящихся на 2, и одно число, равное 2023, которое не делится на 2. Таким образом, общее количество чисел, не делящихся на 4 (поскольку 2023 не делится на 4), равно 199 + 1 = 200.
Итак, наименьшее количество чисел, которое могло оказаться в тетрадке, равно 200.