Страница 1 из 1

Докажите или опровергните.

Добавлено: Вс, 27 авг 2006, 11:53
PSP
Это, конечно, не гипотеза Пуанкаре, поэтому Перельман может не беспокоиться...

Докажите или опровергните утверждение (формулировка откорректирована):
Пусть в 102-элементной последовательнсти целых чисел количество элементов с попарно различными остатками при делении на 100 равно 81, пусть A - множество этих попарно различных чисел, а S - сумма всех 102 элементов данной последовательности.
Тогда в A существуют такие два различных элемента x и y, что числа x+y и S дают одинаковые остатки при делении на 100.

Добавлено: Вт, 29 авг 2006, 7:10
bot
Чтобы опровергнуть, думать долго не надо. :D
Пусть 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.

Добавлено: Вт, 29 авг 2006, 7:34
PSP
Приношу свои извинения. В формулировке оказалась пропущено то, что под попарной различностью 81 элементов понималась их попарная различность по модулю 100.
Формулировка исправлена. Спасибо!

Добавлено: Ср, 30 авг 2006, 8:50
bot
PSP писал(а):В формулировке оказалась пропущено то, что под попарной различностью 81 элементов понималась их попарная различность по модулю 100.
Догадывался об этом, потому и предложил самый крайний вариант - всего два числа по модулю 100.

А теперь, думаю, надо отвечать на другой вопрос.
Множество M различных по модулю m целых назовём накрывающим модуль m, если попарные суммы элементов из М исчерпывают (быть может с повторениями) все вычеты по модулю m.
К примеру, полная система вычетов по модулю m заведомо является накрывающей модуль m.
Теперь вопрос: какое наименьшее число G(m) гарантирует, что любое множество M различных по модулю m чисел мощности G(m) будет накрывать модуль m?

Что-то мне кажется, хотя и не просчитывал, что G(100) заведомо меньше 81.

Добавлено: Ср, 30 авг 2006, 8:52
PSP
bot писал(а):Что-то мне кажется, хотя и не просчитывал, что G(100) заведомо меньше 81.
Очень похоже на правду... Но как просто (во всяком случае, без громоздких вычислений) доказать хотя бы то, что G(100) не более 81 ? Есть серьёзное подозрение, что это можно сделать совсем легко. Но как?

Безусловно, решение вопроса в общем виде, сформулированном Вами, весьма интересно.

Добавлено: Ср, 30 авг 2006, 15:21
bot
PSP писал(а):Но как?
Понятия не имею. На малых порядках можно глянуть на компутере, а в общем случае ... пока не знаю, потому что всерьёз ещё и не думал. Наверно это не очень простая задача по затыканию дыр. Чисто эвристически: чем больше модуль - тем проще их затыкать, то есть с ростом m функция G(m) должна всё больше отставать от m.
А откуда задача-то?

Добавлено: Ср, 30 авг 2006, 18:40
PSP
bot писал(а):А откуда задача-то?
Из темы, над которой работали мои ученики на Международной конференции Турнира городов в августе 2006 года. Точнее, это кусочек одной из задач, которую они не решили; потом решение, вроде бы, объяснили, но про сформулированное мною выше утверждение сказали так: "нетрудно подобрать два числа". Вот я и задумался над тем, сколь же это "нетрудно"... :)

Добавлено: Ср, 06 сен 2006, 6:27
bot
bot писал(а):
PSP писал(а):Но как?
Понятия не имею.
Немного слукавил. :D
Идея-то была верная - принцип Дирихле. Хотел даже сразу ответ дать, но решил воздержаться. И правильно сделал - так сказать, полуошибался на единичку в прогнозе. Вчера только удосужился проверить.

Ответ: G(m)=[m/2]+2 (для m > 2 естественно)

ЗЫ. Поскольку G(100)=52, то в исходной задаче среди 81 различных чисел наверно действительно нетрудно подобрать нужную пару, хотя остаётся только гадать, каким образом это предполагалось.

Добавлено: Чт, 07 сен 2006, 7:42
PSP
Так всё и есть. Спасибо!