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

Здесь вы можете сформулировать математическую задачу, с которой вам не справиться, или, наоборот, поделиться своим маленьким открытием.
Возможно, другие пользователи помогут вам или порадуются вместе с вами...

Модератор: модераторы

PSP
Администратор сайта
Сообщения: 7157
Зарегистрирован: Вс, 28 дек 2003, 11:47
Откуда: Луга
Контактная информация:

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

Сообщение PSP » Вс, 27 авг 2006, 11:53

Это, конечно, не гипотеза Пуанкаре, поэтому Перельман может не беспокоиться...

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

bot
Сообщения: 38
Зарегистрирован: Вт, 01 фев 2005, 9:00
Откуда: Новосибирск
Контактная информация:

Сообщение bot » Вт, 29 авг 2006, 7:10

Чтобы опровергнуть, думать долго не надо. :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.
Учите матчасть - вдруг вас разбудят ночью, а вам и сказать нечего. :)

PSP
Администратор сайта
Сообщения: 7157
Зарегистрирован: Вс, 28 дек 2003, 11:47
Откуда: Луга
Контактная информация:

Сообщение PSP » Вт, 29 авг 2006, 7:34

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

bot
Сообщения: 38
Зарегистрирован: Вт, 01 фев 2005, 9:00
Откуда: Новосибирск
Контактная информация:

Сообщение bot » Ср, 30 авг 2006, 8:50

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

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

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

PSP
Администратор сайта
Сообщения: 7157
Зарегистрирован: Вс, 28 дек 2003, 11:47
Откуда: Луга
Контактная информация:

Сообщение PSP » Ср, 30 авг 2006, 8:52

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

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

bot
Сообщения: 38
Зарегистрирован: Вт, 01 фев 2005, 9:00
Откуда: Новосибирск
Контактная информация:

Сообщение bot » Ср, 30 авг 2006, 15:21

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

PSP
Администратор сайта
Сообщения: 7157
Зарегистрирован: Вс, 28 дек 2003, 11:47
Откуда: Луга
Контактная информация:

Сообщение PSP » Ср, 30 авг 2006, 18:40

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

bot
Сообщения: 38
Зарегистрирован: Вт, 01 фев 2005, 9:00
Откуда: Новосибирск
Контактная информация:

Сообщение bot » Ср, 06 сен 2006, 6:27

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

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

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

PSP
Администратор сайта
Сообщения: 7157
Зарегистрирован: Вс, 28 дек 2003, 11:47
Откуда: Луга
Контактная информация:

Сообщение PSP » Чт, 07 сен 2006, 7:42

Так всё и есть. Спасибо!


Вернуться в «Доска математических объявлений»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 6 гостей