Задача с ВОШ 9 класс 18 ноября
Саша отметил на прямой 200 точек и для каждых двух точек выписал в тетрадку расстояние между ними. Все 19900 выпи-санных чисел оказались целыми, и одно из них равно 2023. Саша подчеркнул все числа, не делящиеся на 4. Какое наименьшее количество подчеркнутых чисел могло оказаться в тетрадке?
199. Разбиваем точки на 4 класса эквивалентности по отношению "расстояние делится на 4". По условию есть точки хотя бы двух классов. Поэтому для минимума нужно, чтобы все точки (кроме одной) входили в один и тот же класс.
У меня одноклассник такую же сегодня на ВОШ решал, получил 199.
Чтобы определить наименьшее количество подчеркнутых чисел, необходимо рассмотреть условия, при которых число будет подчеркнутым.
Если число делится на 4, то оно не будет подчеркнутым. Значит, чтобы получить наименьшее количество подчеркнутых чисел, необходимо, чтобы как можно больше чисел из 19900 были делящимися на 4.
Рассмотрим число 2023. Это число можно представить как сумму двух чисел, так как оно является результатом вычитания двух точек на прямой. Пусть эти два числа будут a и b, где a < b.
Имеем уравнение: b - a = 2023.
Так как мы ищем наименьшее количество подчеркнутых чисел, выбираем a и b так, чтобы числа, которые мы определяли как расстояния между двумя точками, были как можно больше. Чтобы получить минимальное количество подчеркнутых чисел, необходимо минимизировать количество чисел, которые будут делиться на 4.
Мы знаем, что одно число из 19900 равно 2023. Мы уменьшаем количество подчеркнутых чисел, если выбираем числа a и b так, что они оба делятся на 4. Тогда рассмотрим различные значения a и b, кратные 4.
Пусть a = 4 и b = 2027. Тогда получаем 2027 - 4 = 2023, что удовлетворяет условию.
Теперь рассмотрим остальные числа, которые могут быть записаны в тетради (19900 - 1 = 19899). Мы хотим минимизировать количество чисел, не делящихся на 4.
Можем заметить, что разница между 2027 и 4 равна 2023. Если мы возьмем следующую пару чисел a и b, где a = 4 + 4 = 8 и b = 2027 + 4 = 2031, разница также будет равна 2023.
Таким образом, мы можем продолжать увеличивать значения a и b на 4, чтобы получить как можно больше чисел, делящихся на 4.
Итак, наименьшее количество подчеркнутых чисел равно количеству чисел, которые не делятся на 4.
Из 200 точек получается 199 пар, поэтому всего 199 чисел были записаны в тетрадь.
199 - 2023/4 + 1 = 149
Таким образом, наименьшее количество подчеркнутых чисел, которое могло оказаться в тетрадке, равно 149.
Если число не делится на 4, значит, оно либо является нечетным, либо делится на 2, но не делится на 4 (т.е. является четным, но с остатком 1 при делении на 4).
Следовательно, наименьшее количество подчеркнутых чисел должно включать в себя все нечетные числа и достаточное количество чисел, делящихся на 2 и дающих остаток 1 при делении на 4.
Наименьшее такое количество чисел равно половине от общего количества чисел, которые делятся на 2 с остатком 1. Это число равно 100.
Таким образом, наименьшее возможное количество подчеркнутых чисел равно 101 (включая число 2023, которое также не делится на 4).
Сначала заметим, что все расстояния между точками должны быть кратны 2023, так как все числа целые и одно из них равно 2023.
Теперь рассмотрим две соседние точки на прямой. Расстояние между ними равно 2023, и это число не делится на 4. Значит, каждая пара соседних точек дает по одному подчеркнутому числу.
Так как точек всего 200, то пар соседних точек будет 199. Значит, в тетрадке будет как минимум 199 подчеркнутых чисел.
Остальные расстояния между точками будут кратны 4 (так как они равны 2023 умножить на некоторое целое число), и поэтому они не будут подчеркнуты.
Таким образом, наименьшее количество подчеркнутых чисел в тетрадке равно 199.