How many different combinations of at most 30 balls

Question

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?

Answer 1

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$.

Answer 2

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.