I thought it'd be cool to bring back the daily math challenge threads. We'll start off with something easy today.
How many ways can n distinguishable balls be painted with white, black, red, and blue if an even number of balls must be painted white?
There are two possible answers, one is in summation notation and the other is not. They're the same (obviously) and for this problem both are ok.
Pic not really related
Is 0 an even number in this case?
Yes
Not much of a mathematician here, but could not you pick a set comprised of an endless number of balls, paint two of them white and just swap the colors around for the others, thus making an infinite number of color combinations for an infinite number of balls?
I specified n distinguishable balls
Math undergrad here... No probability classes yet... plz no bully.
So can I set this problem up as:
n = 2m
or
n = 2m + 1
and k = 2j, where k is the number of white balls.
Any hint as to how k relates to the combinations of n?
Forgot to mention that j is a natural number, and m is a positive integer including zero.
Jk, j is also a positive integer including zero.
I find your logic disarmingly well-thought-out.
First choose any 2i balls to be chosen as white, then the total is given by:
[math]\sum_{i=0}^{\floor{n/2}} \binom{n}{i} 2^{n - i} [/math]
Gonna look for a closed form now, since you say it is possible
I mean:
[math]\sum_{i=0}^{\lfloor n/2 \rfloor} \binom{n}{2i} 2^{n-2i} [/math]
The black background made me think her arms were chopped off at first...
I'm not exactly sure where you're trying to go, seems like you're just making a bunch of variables. All I can say is don't do it this way?
On the right track, i should be 2i though, also there are 4 colors not 3.
ah yes my bad,
[math]\displaystyle \sum_{i=0}^{\lfoor n/2 \rfloor} \binom{n}{2i} 3^{n-2i} [/math]
For a general n, first pick the amount of white balls and then paint the rest.
First start with only 2 white balls. There are n choose 2 different configuration of 2 painted white balls. This always leaves (n-2) unpainted balls that we can color however we like. Given any configuration of painted white balls, there are then (n-2) balls that can be painted in any configuration of black/red/blue. Which for 1 remaining ball would be 3 configurations, for 2 remaining balls it would be 9, for 3 remaining it would be 27, etc.
Then you repeat this step by choosing 4 white balls, which would be n choose 4. And then also repeat the process of painting the remaining balls.
My general formula is:
[eqn] f(n) = \sum_{k=1}^{\frac{n}{2}} {n \choose 2k} 3^{n - 2k} [/eqn] for even values of n and:
[eqn] f(n) = \sum_{k=1}^{\frac{n-1}{2}} {n \choose 2k} 3^{n - 2k} [/eqn] for odd values of n
Obviously, the odd formula doesn't work for 1 as this problem does not make sense for n=1.
Please tell me if this is correct. I haven't taking any number theory course yet so it would be nice to have my intuition checked.
Wrong.
Counter example, for n=2 you would have
(2 choose 0 )times 3 squared
+
(2 choose 1 ) times 3^0
=
9
+
2
=
11
Which is way off
Yep this is correct, you can turn the two formulas into one if you use the floor function like did.
The form that does not use a summation does use the floor function, however.
Fuck I meant to say it does not use the floor function
>2 choose 1
>1 is now even
choose 1
Fine. It is 2 choose 2, which is 1.
You still get 9+1 = 10.
And 10 is the correct answer for n = 2.
>you can turn the two formulas into one if you use the floor function
Right. Unfortunately as I was typing I hadn't updated the thread and I don't tend to use the floor function much.
>The form that does not use a summation does use the floor function, however.
Can you share?
and closed form I have found is:
[math]\frac{4^n + (-2)^n}{2} [/math]
This is gotten by summing the binomial series:
[math] \frac{1}[2}((1+3)^n + (1 - 3)^n)[/math]
I'm not sure of a nice combinatoric argument for this though
10?
The fuck? If you only have two balls and you need an even number of white balls then you have to paint both the balls white. That is all you can do. There are not 10 ways to paint 2 balls white.
It does _not_ use the floor function, that was a typo. Sorry about that.
It's 2 not -2. I have a combinatoric argument, but it's kinda hard to explain. I'll try to write it out in a future post.
Choosing 0 creates 9 more colorings. 0 is even in this case, it was the first question I answered.
Ah. pff. That is a bit dumb but sure, whatever.
I see, must have made a small error
pic related is my contribution, might be a bit easy
Ok I tried my best.
Let a binary string be even if it has an even number of 1's. I claim that in the set of all binary strings of length n, exactly half of the strings will be even.
This can be proven with induction, for our base case consider n = 1, then the possible strings are 0 and 1. 0 is even, 1 is odd. To get the next n, we prepend 0 and 1 to both strings, getting 00, 01, 10, and 11. Just like addition, for these strings odd + odd = even, even + even = even, and odd + even = odd. It's easy to see that half of the n + 1 strings are even, and then by induction this works for all n.
Summary: Half of the binary strings of length n have an even number of 1's.
For our problem, we want to find the number of even colorings, except now we have 4 "digits" instead of 2. Let white = 1 and black = 0. If we pick only colorings that use white and black, 2**(n - 1) of 2**n colorings will be even.
Now this part is where it gets kinda hard to explain. Let's say we pick m balls to color white and black, then we can color the remaining n - m balls with red and blue. The number of even colorings here is still half, so that's 4**n / 2, or 2**(2n - 1). I have no good intuitive explanation for this.
So the total number of colorings is the sum, which is 2**(n - 1) + 2**(2n - 1)
Part *: Draw lines from A to P, A to B, C to R, C to B, A to C, B to Q, the horizontal line going through B and parallel to PQR, and similar for the line going through C.
Pythagorean theorem on the top small triangle and the two on the sides gets (*).
Part **: Tried but was too messy and gave up.
Sorry for potato cam.
Followup to the original question. The balls are now indistinguishable.
Again, there's a summation form using the choose operation and a closed form that doesn't. The closed form is very difficult to get (unless there is some cool way to do it that I do not know of).
where is the solution demonic one
seems like it is good to me user, source of the question is from the STEP exam paper 2016 paper 1
oh and the solution to the second part, it is just some algebra