Пусть $%p$% - заданное простое число. Найдите число непустых подмножеств множества $%\{1,2,...,p\}$% таких, что сумма элементов каждого подмножества кратна $%2p$%.

P.S. Например, если $%p=5$%, то существует три таких подмножества $%\{1,2,3,4\}, \{1,4,5\}, \{2,3,5\}$%.

задан 6 Ноя 21:43

изменен 6 Ноя 22:01

10|600 символов нужно символов осталось
4

Всего подмножеств множества $% (1,2,..,p)$% сумма элементов которых делится на $%p: \ \dfrac {2^p-2}{p} +1$%

Разобьет эти подмножество на пары $%(...) \ (...,p)$%

Поэтому число непустых подмножеств сумма элементов которых кратна $%2p : \ \dfrac {2^p-2}{2p}$%

ссылка

отвечен 7 Ноя 1:23

изменен 7 Ноя 2:57

Witold2357's gravatar image


7.3k116

1

@Sergic Primazon: я пришёл к такому же ответу для частного случая, когда 2 является первообразным корнем по модулю p. Для общего случая было видно, что ответ такой же, но я не успел это доказать.

Как я понимаю, Вы берёте все множества кроме пустого и полного, и пользуетесь тем, что там все остатки встречаются одинаково часто (что отдельно проверяется для подмножеств мощности 0 < k < p). То есть реально получается на 2 множества больше, с учётом пустого, а потом делим пополам, и вычитаем 1, так как пустое в условии не рассматривается.

(7 Ноя 2:51) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,027
×1,005
×796
×228
×84

задан
6 Ноя 21:43

показан
58 раз

обновлен
7 Ноя 2:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru