Это, конечно, не гипотеза Пуанкаре, поэтому Перельман может не беспокоиться...
Докажите или опровергните утверждение (формулировка откорректирована):
Пусть в 102-элементной последовательнсти целых чисел количество элементов с попарно различными остатками при делении на 100 равно 81, пусть A - множество этих попарно различных чисел, а S - сумма всех 102 элементов данной последовательности.
Тогда в A существуют такие два различных элемента x и y, что числа x+y и S дают одинаковые остатки при делении на 100.
Докажите или опровергните.
Модератор: модераторы
-
- Администратор сайта
- Сообщения: 7200
- Зарегистрирован: Вс, 28 дек 2003, 11:47
- Откуда: Луга
- Контактная информация:
Докажите или опровергните.
Последний раз редактировалось PSP Чт, 07 сен 2006, 7:42, всего редактировалось 4 раза.
Чтобы опровергнуть, думать долго не надо.
Пусть a и b - произвольные числа, с разными остатками при делении на 5.
Рассмотрим последовательность
x_k = 100k+a, для k=0,1,...,79
x_k = b, для k=80,82,...,101.
Тогда эта последовательность
1) содержит ровно 81 различных чисел - это b и первые 80 членов последовательности.
2) никакие два (различные или одинаковые элементы даже не из А, а из всей последовательности) не дадут одинаковых остатков с S при делении на 100.
Пусть a и b - произвольные числа, с разными остатками при делении на 5.
Рассмотрим последовательность
x_k = 100k+a, для k=0,1,...,79
x_k = b, для k=80,82,...,101.
Тогда эта последовательность
1) содержит ровно 81 различных чисел - это b и первые 80 членов последовательности.
2) никакие два (различные или одинаковые элементы даже не из А, а из всей последовательности) не дадут одинаковых остатков с S при делении на 100.
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего.
Догадывался об этом, потому и предложил самый крайний вариант - всего два числа по модулю 100.PSP писал(а):В формулировке оказалась пропущено то, что под попарной различностью 81 элементов понималась их попарная различность по модулю 100.
А теперь, думаю, надо отвечать на другой вопрос.
Множество M различных по модулю m целых назовём накрывающим модуль m, если попарные суммы элементов из М исчерпывают (быть может с повторениями) все вычеты по модулю m.
К примеру, полная система вычетов по модулю m заведомо является накрывающей модуль m.
Теперь вопрос: какое наименьшее число G(m) гарантирует, что любое множество M различных по модулю m чисел мощности G(m) будет накрывать модуль m?
Что-то мне кажется, хотя и не просчитывал, что G(100) заведомо меньше 81.
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего.
-
- Администратор сайта
- Сообщения: 7200
- Зарегистрирован: Вс, 28 дек 2003, 11:47
- Откуда: Луга
- Контактная информация:
Очень похоже на правду... Но как просто (во всяком случае, без громоздких вычислений) доказать хотя бы то, что G(100) не более 81 ? Есть серьёзное подозрение, что это можно сделать совсем легко. Но как?bot писал(а):Что-то мне кажется, хотя и не просчитывал, что G(100) заведомо меньше 81.
Безусловно, решение вопроса в общем виде, сформулированном Вами, весьма интересно.
Понятия не имею. На малых порядках можно глянуть на компутере, а в общем случае ... пока не знаю, потому что всерьёз ещё и не думал. Наверно это не очень простая задача по затыканию дыр. Чисто эвристически: чем больше модуль - тем проще их затыкать, то есть с ростом m функция G(m) должна всё больше отставать от m.PSP писал(а):Но как?
А откуда задача-то?
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего.
-
- Администратор сайта
- Сообщения: 7200
- Зарегистрирован: Вс, 28 дек 2003, 11:47
- Откуда: Луга
- Контактная информация:
Из темы, над которой работали мои ученики на Международной конференции Турнира городов в августе 2006 года. Точнее, это кусочек одной из задач, которую они не решили; потом решение, вроде бы, объяснили, но про сформулированное мною выше утверждение сказали так: "нетрудно подобрать два числа". Вот я и задумался над тем, сколь же это "нетрудно"...bot писал(а):А откуда задача-то?
Немного слукавил.bot писал(а):Понятия не имею.PSP писал(а):Но как?
Идея-то была верная - принцип Дирихле. Хотел даже сразу ответ дать, но решил воздержаться. И правильно сделал - так сказать, полуошибался на единичку в прогнозе. Вчера только удосужился проверить.
Ответ: G(m)=[m/2]+2 (для m > 2 естественно)
ЗЫ. Поскольку G(100)=52, то в исходной задаче среди 81 различных чисел наверно действительно нетрудно подобрать нужную пару, хотя остаётся только гадать, каким образом это предполагалось.
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего.
Вернуться в «Доска математических объявлений»
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 11 гостей