6
$\begingroup$

I would appreciate if somebody could help me with the following problem.

Given the set $A=\{1,2,\dotsc,14\}$, calculate the number of distinct sets $M \subset A$ such that $|M| = 7$ and such that the sum of the elements of $M$ is a multiple of $7$.

$\endgroup$

marked as duplicate by Trevor Gunn, ahulpke, Misha Lavrov, José Carlos Santos, user284331 Feb 25 '18 at 23:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Do you know that sum $x1+x2..x7$ doesnt work after $29$ the star and bars problem $\endgroup$ – Archis Welankar Feb 5 '16 at 7:11
  • 2
    $\begingroup$ Find all sets, or just find the number of them? (The title doesn't match the question you asked later.) $\endgroup$ – Christopher Carl Heckman Feb 5 '16 at 7:22
  • $\begingroup$ The program posted at this MSE link will produce the answer $492.$ $\endgroup$ – Marko Riedel Feb 5 '16 at 21:40
1
$\begingroup$

David posted his answer while I was working on mine. His answer is better if you want to count the sets; if you want to generate them, it doesn't help, though.

Here's what I was writing:

This is not a complete answer, but if you put the pieces together, you can answer both of your questions (how to find all of the sets, and how many there are).

The first thing to do is to notice that we can split one of your sets $A$ into $A_1=A\cap\{1,2,\ldots,7\}$ and $A_2=A\cap\{8,9,\ldots,14\}$. Then you will need to find the number $n(m,k)$ of subsets of $A_1$ with size $m$, whose sum is equivalent to $k\pmod7$, for $m=0,\ldots,7$, $k=0,\ldots,6$. Then you can combine a set $A_1$ with $(m,k)=(2,3)$ with a set $A_2$ with $(m,k)=(5,4)$, for instance.

Note that since $A_2$ is $A_1$ shifted up by 7, you can use this table for both $A_1$ and $A_2$.

Now, to calculate $n(m,k)$, notice that the sum of the elements of $\{1,2,\ldots,7\}$ is a multiple of 7; hence, $n(m,k)=n(7-m,7-k)$. That means you only need to find $n(m,k)$ for $m\le 3$; the rest can be calculated in a way similar to my discussion about combining $A_1$ and $A_2$.

$\endgroup$
5
$\begingroup$

Consider the collection $F_a$ of all sets $M \subseteq A$ of cardinality $7$ such that $M \cap \{1,\dots 7\}$ has cardinality $a$.

Let $\sigma$ be the permutation of $A$ given by $\sigma(x) = x+1$ for $x = 1, \dots 6$, $\sigma(7) = 1$, $\sigma(x) = x$ for $x = 8, \dots 14$. Then the mapping $M \mapsto \sigma(M)$ is a permutation of $F_a$. Moreover, if the sum of the elements of $M$ is $b$, then the sum of the elements of $\sigma(M)$ is $b + a$ modulo $7$.

Thus the number of elements of $F_a$ with sum $b$ modulo $7$ is the same as the number with sum $b + a$ modulo $7$. When $a \ne 0,7$, repeated application of this argument shows that this number is independent of $b$. Therefore exactly $1/7$ of the elements of $F_a$ have sum $0$ modulo $7$.

$F_0$ and $F_7$ are the only exceptions to this rule, and they each have one element. Therefore the required number is $\frac{1}{7}\left[\binom{14}{7} - 2\right] + 2 = 492$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.