3
$\begingroup$

John has $100$ marbles and wants to split them into $4$ groups $A,B,C,$ and $D$ such that the greatest common divisor of the number of marbles in all of the groups is $1$. Find the number of ways John can do this.

This question is equivalent to finding all nonnegative solutions to $x+y+z+w = 100$ if $\gcd({x,y,z,w}) = 1$. I am unsure how to solve such an equation in general or if there is a way to do it easily.

$\endgroup$
13
  • $\begingroup$ Step 1: Forget about the $\gcd$ restriction and find the number of ways to split the marbles into four groups. Step 2: Count the number of ways to split the marbles into four groups such that the $\gcd$ of the group sizes is larger than $1$. $\endgroup$ – Daniel Fischer Jan 21 '16 at 23:24
  • $\begingroup$ @DanielFischer Step 1: We have $\binom{103}{3}$ number of ways. Step 2: We must count the number of solutions where they all share a common factor greater than $1$. Thus, $A = kx, B = ky, C = kz, D = kw$. Thus, $k(x+y+z+w) = 100$. Here $k$ must be a multiple of $100$, thus $k = 2,5,10,25,50,100$. We also have the added condition that $\gcd(x,y,z,w) = 1$. $\endgroup$ – John Ryan Jan 21 '16 at 23:29
  • $\begingroup$ That's one way, to use all divisors of $100$. You could also use the inclusion-exclusion principle (which makes for less work here). $\endgroup$ – Daniel Fischer Jan 21 '16 at 23:31
  • $\begingroup$ @DanielFischer How do I deal with the restriction of $\gcd(x,y,z,w) = 1$? $\endgroup$ – John Ryan Jan 21 '16 at 23:35
  • $\begingroup$ @DanielFischer For example, $x+y+z+w = 50$ if $\gcd(x,y,w,z) = 1$. I don't see an easy way to count that. $\endgroup$ – John Ryan Jan 21 '16 at 23:49
4
$\begingroup$

To count the number of solutions to problem $X$ that satisfy the additional condition $C$, it is often easier/more efficient to count all solutions of $X$ and then subtract the number of solutions that violate condition $C$. This is also the case here.

When we partition $n$ marbles into $k$ groups of sizes $s_1,\dotsc, s_k$, then $d := \gcd(s_1,\dotsc,s_k)$ is a divisor of $n$. If $d > 1$, then there is at least one prime $p$ that divides $d$. For a given prime $p$ dividing $n$, to count the number of partitions of $n$ marbles into $k$ groups such that the greatest common divisor of the group sizes is a multiple of $p$ amounts to counting the number of partitions of $n/p$ marbles into $k$ groups without any restriction on the group sizes.

Here, we have $n = 100$, with the only primes dividing $n$ being $2$ and $5$. So if the greatest common divisor of the group sizes is not $1$, it must be a multiple of $2$, or a multiple of $5$.

To find the number of partitions such that the greatest common divisor of the sizes is $1$, we take the number of all partitions of $100$ marbles into four groups and subtract the number of partitions of $\frac{100}{2} = 50$ marbles into four groups, and the number of partitions of $\frac{100}{5} = 20$ marbles into four groups. But now we have subtracted the partitions such that the greatest common divisor of the group sizes is a multiple of both, $2$ and $5$, twice. Hence we must then add the number of partitions of $\frac{100}{2\cdot 5} = 10$ marbles into four groups to get the final result.

In formulae:

$$N_1(100,4) = N(100,4) - N(100/2,4) - N(100/5,4) + N(100/10,4),$$

where $N(n,k)$ denotes the number of partitions of $n$ marbles into $k$ groups, and $N_1(n,k)$ denotes the number of partitions such that the greatest common divisor of the group sizes is $1$.

Generally:

$$N_1(n,k) = \sum_{d\mid n} \mu(d)\cdot N(n/d,k)$$

where $\mu$ is the Möbius function.

$\endgroup$
2
  • $\begingroup$ I get the answer to be $151940$. $\endgroup$ – John Ryan Jan 22 '16 at 0:46
  • $\begingroup$ Looks good, that's what I get too. $\endgroup$ – Daniel Fischer Jan 22 '16 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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