1
$\begingroup$

Given are an unlimited amount of red, blue, black and yellow balls. We need to create different combinations of at most 30 balls. Out of every combination, at most one ball is to be replaced by a ball of another color. Is there a strategy to make sure the first 1000 combinations are all different even after the replacements?

$\endgroup$
  • 1
    $\begingroup$ What does " Out of every combination at most one ball is gonna be replaced by a ball of another color. " mean? $\endgroup$ – lulu Feb 24 at 17:13
  • $\begingroup$ @lulu for example, if red-red-blue is a combination, then one of the balls is gonna be replaced by a ball from another color, so the new combination will for example be red-black-blue $\endgroup$ – Phillip Jones Feb 24 at 17:20
  • $\begingroup$ This is not clear. Are you asking how many combinations there are? Are you requiring that any two of your list be connected by a single change of color? Something else? $\endgroup$ – lulu Feb 24 at 17:26
  • $\begingroup$ Suppose one combination is red-red and one is blue-blue. Both of them can be changed to red-blue. Is this allowable? $\endgroup$ – Ross Millikan Feb 24 at 19:01
1
$\begingroup$

Building on InterstellarProbe's answer we are also allowed to have combinations of $29, 28, 27,$ and fewer balls. There are ${9+4-1 \choose 4-1}=220$ combinations for $27$ balls and we can extend all of those to combinations for $28$ and $29$ balls by adding one or two red balls. The swapping of balls maintains the total number of balls so there is no confusion between combinations with different numbers of balls. That is not quite enough, but there are ${8+4-1 \choose 4-1}=165$ combinations with $24$ balls and we are there.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oh! Good point! I completely missed that you could have fewer than 30 balls. $\endgroup$ – InterstellarProbe Feb 24 at 19:07
1
$\begingroup$

Hint: Start with 30 of one color (let's say red). Suppose you want to modify this combination to create a new combination. You take away one red ball and add one blue one. Now, these are distinct combinations, but if you were to take away the blue ball and add the red ball, you would be back where you started.

Suppose you take away two red balls and add two blue or one blue and one black. If you were to take away one blue and add one red, you have 29 red and one (black or blue). Starting with 30 red, if you take away one red and add one (black or blue), you wind up with the same thing.

Therefore, going from 30 red balls, you must move at least three balls to get a "distinct" combination up to replacing a ball of one color.

So, consider the number of solutions to the Diophantine equation:

$$3x_1+3x_2+3x_3+3x_4 = 30$$

There are only $\dbinom{10+4-1}{4-1} = 286$ solutions.

Edit: Now that I see Ross Millikan's response, consider all multiples of 3:

$$3x_1+3x_2+3x_3+3x_4 = 3n, n=1,2,\ldots , 10$$

$$\sum_{n=1}^{10} \dbinom{n+4-1}{4-1} = 1000$$

Edit 2: Here is a possible way to reword the problem:

Define $X = \{(x_1,x_2,x_3,x_4) \in \mathbb{Z}^4 \mid 0\le x_1,x_2,x_3,x_4\text{ and }0 < x_1+x_2+x_3+x_4 \le 30\}$

Define a relation $R$ on $X$ such that $(x_1,x_2,x_3,x_4) R (y_1,y_2,y_3,y_4)$ if and only if there exists $(a_1,a_2,a_3,a_4,b_1,b_2,b_3,b_4) \in \{-1,0,1\}^8$ such that $$|a_1+a_2+a_3+a_4|\le 1, \\ |b_1+b_2+b_3+b_4| \le 1, \\ \left|\left\{ k\in \{1,2,3,4\}: a_k = 0\right\} \right| \ge 2, \\ \left|\left\{ k\in \{1,2,3,4\}: b_k = 0\right\} \right| \ge 2, \text{ and } \\ (x_1+a_1,x_2+a_2,x_3+a_3,x_4+a_4) = (y_1+b_1,y_2+b_2,y_3+b_3,y_4+b_4) \in X$$

Let $A\subset X$ such that $R$ restricted to $A$ is an equivalence relation. Is it possible that $|A| \ge 1000$?

Then, $A = \{(3x_1,3x_2,3x_3,3x_4): x_1,x_2,x_3,x_4 \in \mathbb{Z}, 0\le x_1,x_2,x_3,x_4, 0 < x_1+x_2+x_3+x_4 \le 10\}$ satisfies this property with $|A| = 1000$.

| cite | improve this answer | |
$\endgroup$

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.