Проверьте, существует ли подмножество с суммой, делимой на m

Question

Учитывая набор неотрицательных различных целых чисел и значение m, определите, существует ли подмножество данного набора с суммой, делимой на m.

Решение для geeksforgeeks гласит, что -

1. Если n > m, то всегда будет подмножество с суммой, кратной сумме m (что легко доказать с помощью принципа голубя). Таким образом, нам нужно разобраться только со случаями n <= m.

Может кто-нибудь объяснить, что означает этот случай и как он связан с принципом голубиных ям? Кроме того, как этот случай отличается от n <= m?

Answer 1

Делая это немного более многословным: https://math.stackexchange.com/questions/2614458/proving-that-a-set-of-2016-natural-numbers-contain-a-non-empty-set-with-a-sum-di

Маркируйте числа a1, a2, ... an в любом порядке. Теперь рассмотрим суммы:

b1=a1
b2=a1+a2
b3=a1+a2+a3
...
bn=a1+a2+...+an

Это либо все уникальные числа, либо один из a s равен 0 (который делится на m).

1) Теперь, если любой из b делится на m, мы закончим.

2) В противном случае:

Остатки some non-divisible number/m могут находиться в диапазоне 1...(n-1). Таким образом, существует n-1 число возможных остатков m.

Поскольку числа b1...bn не делятся на m, они должны иметь остатки в диапазоне 1...(n-1). Таким образом, вы должны спарить n количество b s (голубей) с n-1 количеством остатков (голубиных отверстий).

У нас больше голубей, чем голубых = = должно быть не менее двух голубей в то же самое отверстие.

Это означает: должно быть по крайней мере два b с одним и тем же остатком: назовите их bi, bj (i<j). Поскольку все наши b уникальны и bi % m == bj % m (остатки bi/m и bj/m одинаковы) => bi - bj = x * m (где x - положительное целое число). Следовательно, bi - bj делится на m и bi - bj = ai+1 + ... + aj. Следовательно, ai+1 + ... + aj делится на m, и это именно то, что мы хотели доказать.

Answer 2

Вам следует создать новый набор чисел:

(из соображений комфорта будет записываться как код, извините. Также вызовет набор n)

a[0] = n[0]
a[1]=n[0] + n[1]
a[len(n)-1] = n[0]+...+n[len(n)-1]

Теперь у вас есть n новые номера. если любой из них делится на м, вы сделали. В противном случае на основе квадратного отверстия существует два числа 0<=i,j<=n в таком, что a[i] mod(m) == a[j] mod(m). Выберите i> j и по определению a [i] -a [j] делится на m. В этом сценарии, поскольку a[i] = a[j] + a[j+1]+...+a[i-1] сумма подмножества a[j]- a[i-1] делится на m по запросу.