2

Suppose there are 51 dalmatians and number of dots on each dalmatian is not null. Prove (or dis-prove) there is always a grouping such that at least one group has total number of dots as multiple of 11.

I can easily prove the statement for 101 dalmatians by modulus 11, but have no idea how to start for 51 dalmatians.

kchpchan
  • 179
  • I don't really understand the problem. Are you trying to say that we can always choose some set of the dalmatians whose dots add up to a multiple of $11$? – tomasz May 14 '15 at 20:40
  • 4
    Seems like you could do it with a lot fewer dalmations, like 12. – Thomas Andrews May 14 '15 at 20:41
  • 1
    @ThomasAndrews Why not $11$? Unless a "group" has to have at least two Dalmatians in it. – Mark Bennet May 14 '15 at 20:43
  • You can't do it with $11$ unless a group can have $0$ elements, @MarkBennet For example, if each dog has $1$ spot. – Thomas Andrews May 14 '15 at 20:44
  • @Thomas Andrews: If each dog has $1$ take a set of $11$ dogs – Henry May 14 '15 at 20:46
  • You are supposed to create two groups. If you are allowed a group of zero dogs, then that already is a group of dogs with total spots divisible by $11$. @Henry (Well, I suppose it depends on what OP means by a "grouping.") – Thomas Andrews May 14 '15 at 20:47
  • Right, as I said, it depends on what he means by a "grouping." It's a vague term, and I took it to mean there was always at least two groups. – Thomas Andrews May 14 '15 at 20:49
  • @ThomasAndrews I would read a possible grouping as a set including every dog, with no need for other sets - but apart from that I don't think you disagree with Rev Mark. – Henry May 14 '15 at 20:50
  • @ThomasAndrews I see your point. I was thinking of a generalisation to say that you could put all but at most ten Dalmatians into groupings each of which has a multiple of eleven spots. But on your reading eleven Dalmatians would be an exception. – Mark Bennet May 14 '15 at 20:59

1 Answers1

1

Given 12 dalmations, write their number of dots as $x_1,x_2,\cdots,x_{12}$.

Then two of $0,x_1,x_1+x_2,x_1+x_2+x_3,\cdots, x_1+x_2+\cdots + x_{11}$ are congruent modulo $11$. But that means $x_{n+1}+x_{n+2}+\cdots x_{m}$ must be divisible by $11$ for some $n<m$.

We need $12$ so that the "other" group always contains at least one dalmation - $x_{12}$. But that depends on what you mean by a "grouping."

Thomas Andrews
  • 177,126