Wikipedia:Reference desk/Archives/Mathematics/2009 April 8

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 8

Combination?

Fellow Wikipedians, I am once again in need of your help on a question from a UIL test. The question reads:

The Mel Ting ice cream store offers 12 different flavors of ice cream. Mel makes banana splits using three scoops of ice cream. How many different three-scoop banana splits can he make?

I got 220 as a result of 12 C 3, but the contest director has ruled that the actual answer is something else. This has been questioned before as well, but the ruling of the answer stood. My question: how is this problem supposed to be worked if it is not 12 C 3. TIA, Ζρς ιβ' ^¡hábleme! 02:03, 8 April 2009 (UTC)

I think you have to realize that you don't have to use three DIFFERENT flavors. What if I use three scoops of same ice cream? It doesn't say anything about using three different flavors everytime. So for each scoop, you have 12 flavors to choose form which gives you 12^3=1728 possibilities. But then there is another twist. If orientation doesn't matter, meaning if V C V is considered the same as C V V then in this above answer, some have been counted multiple times. If orientation does matter, then the above answer is correct, otherwise, divide by the number of repititions.--130.166.52.17 (talk) 02:24, 8 April 2009 (UTC)

1728 is not an answer choice. How do I find the number of repetitions? Ζρς ιβ' ^¡hábleme! 02:24, 8 April 2009 (UTC)

It would help if you would list the answer choices. Depending on the assumptions you make, you can get many possible answers. For example, one could view VCV as different from CVV, while considering CVV to be the same as VVC, since you can just turn the banana split around to go from one to the other. StuRat (talk) 06:19, 8 April 2009 (UTC)

I think the idea is that a banana split = $(n_{1},\ldots ,n_{12})$ where the $n_{k}$ are the number of scoops of flavor k, and $\sum _{k=1}^{12}n_{k}=3.$ (That means most of the n's are zero). So CVV is the same as VCV (both are two scoops of vanilla and one scoop of chocolate), but CVV is not the same as CCV. 207.241.239.70 (talk) 07:20, 8 April 2009 (UTC)

If we take that to be the question, then the answer is ¹⁴C₃=364. Algebraist 17:30, 8 April 2009 (UTC)

A nice example of a question that attempts to be subtle but merely succeeds in being ambiguous. Gandalf61 (talk) 12:44, 8 April 2009 (UTC)

Yes. I don't know who or what UIL might be, but anyone producing this sort of question shouldn't be taken very seriously. Algebraist 17:30, 8 April 2009 (UTC)

A nice example of a question for an experimental approach! Joking apart, I assume this is a problem for young students not necessarily of maths (is that UIL this UIL?). If so, in my opinion, the interesting point of this not completely defined question is the formalization issue (choose a model for the "space" of banana splits, translate the question into an enumeration problem in combinatorics; try to solve it; compare different models &c). For those students, an open question like that may have more appeal and more educative content than solving the direct abstract problem of combinatorics. And for some may be a motivation for the subsequent mathematical aspects. So I wouldn't be that severe... --pma (talk) 18:50, 8 April 2009 (UTC)

The experimental approach is good in its place, but that place is not in a contest where every question has a unique acceptable answer. Algebraist 09:11, 9 April 2009 (UTC)

If it is a question in a contest, I agree with you that a clear definition of banana split should be given. --pma (talk) 10:01, 9 April 2009 (UTC)

I don't think there's any ambiguity so long as you read the banana split article and see that the three scoops are in a straight line, which means that ABC and CBA are equivalent (you can turn the dish around) but ACB is different (there's a different flavor in the middle). As noted, there are 12³ ways to assign the flavors if all three scoops are distinguishable. Of these, 12² have the same flavor at both ends (AAA or ABA) and are being counted once, while the other 12³−12² have different flavors at each end and are being counted twice. So the answer is 12² + (12³−12²)/2 = 936. Is that one of the choices offered? --Anonymous, 08:58 UTC, April 9, 2009.

364 is the correct answer. How is it that this answer (14 C 3) is achieved from the given information? Also, pma, that is the UIL of which I speak. The test from which this question was obtained was a 2009 UIL district competition test for grade levels 9 through 12 (in UIL academics all grade levels compete with each other on the same test). Personally, though, I would rather study the more abstract applications of combinatorics so as to understand them in depth. Ζρς ιβ' ^¡hábleme! 16:16, 10 April 2009 (UTC)

Algebraist gave that answer above. What they were trying to pose was a straightforward combinatorics problem, specifically a combination problem (versus a permutation problem). Given a set of 12 elements, how many different combinations (unordered collections) are there if we allow repetitions? Since repetition is allowed, the formula (given on the combination page) is ${{n+k-1} \choose {k}}={{(n+k-1)!} \over {k!(n-1)!}}$, where n is the number of total elements, k is the number of elements in each collection, and x! is the factorial function. From this we get ${{(12+3-1)!} \over {3!(12-1)!}}=364$. -- 128.104.112.117 (talk) 18:10, 10 April 2009 (UTC)

As it has already pointed out, there is no correct answer to the question as stated, because it is ambiguous; for this reason it is very bad for a competition, but it may be a stimulating topic of discussion for young students. Me, I've already had 3 banana splits as a consequence of the OP -although I mostly focused on the aesthetic aspect rather that the combinatorial. --pma (talk) 13:53, 14 April 2009 (UTC)

Solving Congruences

Hello, I am trying to show that $x^{8}\equiv 16$ (mod p) is always solvable for any prime p. I am not looking for an answer but any hints on how to get started will be appreciated. For a small enough prime, such as p=2 and 3 and so on, we can just see this by inspection but I don't understand how can we show this for ALL prime p. Any insight? Thanks you--130.166.52.17 (talk) 02:10, 8 April 2009 (UTC)

Do you know about the law of quadratic reciprocity? 207.241.239.70 (talk) 07:20, 8 April 2009 (UTC)

Yes I do know about quadratic residues. But we are not supposed to use the Gaussian reciprocity law, only the Legendre symbol and some of its basic properties. We can't even use the Jacobian symbol yet. Here is what I have done so far. We want to show that the congruence $f(x)=x^{8}-16\equiv 0$ (mod p) always has a solution for any prime p. For p=2, zero is a solution. For p=3 and 5, f(x) reduces to an identical congruence so it is solvable. For x=7, by inspection, x=3 and 4 are solutions.

Now consider all primes greater than or equal to 11. I factored $f(x)=(x^{2}-2)(x^{2}+2)(x^{4}+4)\equiv 0$ (mod p). Now I consider the cases where $p\equiv 1,3,5,7$ (mod 8) separately.

I already know that $p\equiv 1,7$ (mod 8) implies that $x^{2}-2\equiv 0$ (mod p) has solutions.

I also know that $p\equiv 1,3$ (mod 8) implies that $x^{2}+2\equiv 0$ (mod p) has solutions.

Now this last case of p=8k+5 is the one I can't get. I want to show that if p is of the form 8k+5 then $x^{4}+4\equiv 0$ (mod p) has a solution. I have reduced it down to where I have to show that $(-4)^{2k+1}\equiv 1$ (mod p). But the only thing I know (from Fermat's little theorem) is that $(-4)^{8k+4}\equiv 1$ (mod p). So how can I show this last step. Thanks!--69.110.132.28 (talk) 08:04, 8 April 2009 (UTC)

You need to show that -4 is a fourth power. It's certainly a square: -4=(2α)², where α is a square root of -1 (which exists since p is congruent to 1 mod 4). So we need that 2α is a quadratic residue. 2 is a quadratic nonresidue, so it's enough to show that α is a nonresidue also, i.e. that -1 is not a fourth power. But a fourth root of -1 would be an 8th root of unity, which can't exist since p is not congruent to 1 mod 8. Algebraist 09:49, 8 April 2009 (UTC)

unique left/right inverses for functions

I don't really get the concept of this yet with respect to function composition. Why would a left inverse be different from a right inverse? And how do you have multiple different left or right inverses for a single function?

e.g. given domain A = {1,2,3} and target set B = {1,2,3,4}, and f={(1,3),(2,4),(3,2)}, the immediate left inverse that strikes me is g_1 = {(3,1),(4,2)(2,3)}, Of course, now g has apparently limited its domain from the original set B to {2,3,4}. Would g_2 = {(1,1),(3,1),(4,2),(2,3)} still be a left inverse? I mean, none of f's output would ever yield 1. John Riemann Soong (talk) 05:25, 8 April 2009 (UTC)

Do the basic definitions at Inverse_function#Left_and_right_inverses not make the difference clear? 207.241.239.70 (talk) 07:35, 8 April 2009 (UTC)

To take familiarity with the concept of right/left inverse, I suggest to check it in the various categories you are familiar with. --78.13.141.144 (talk) 07:59, 8 April 2009 (UTC)

Your function g_1 is not a left inverse to f. An inverse to f (either left or right) must have as its domain the codomain of f and its codomain the domain of f; that is, it must be a function from B to A. Your function g_2 is a left inverse to f, and so is any function from B to A that agrees with g_2 on the image of f, that is {2,3,4}. So f has exactly three left inverses. On the other hand, f has no right inverse, since it is not surjective. Algebraist 09:42, 8 April 2009 (UTC)

Function composition is associative, so if a function has both a left inverse and a right inverse, then these inverse functions will be both equal and unique (see inverse element) - it is an interesting exercise to prove this and see why associativity is required in the proof. If you want to find examples of left and right inverses that are not equal then you will need to look in a non-associative algebra. Gandalf61 (talk) 12:39, 8 April 2009 (UTC)

Ratio and product distributions

A few questions which I could probably solve myself, but wondered if someone else answered them already. It is known that Cauchy distribution Z is a ratio distribution of two normal distributions, X and Y. Is Z independent of X or Y? If I take a Cauchy r.v. Z and normal r.v. X, independent of each other, is Y=X * Z a normal r.v.? (Igny (talk) 23:47, 8 April 2009 (UTC))

Given three normally distributed rv's A,B,C, I think you are asking whether (A*B)/C is normally distributed. Sounds doubtful. 75.62.6.87 (talk) 09:09, 9 April 2009 (UTC)

Yes it seems doubtful. My original thought was actually to find a nontrivial distribution X, which when multiplied by a normal variable yields a normal distribution. Naturally, I thought of Cauchy distribution, but now I doubt that such a distribution exists. (Igny (talk) 17:21, 9 April 2009 (UTC))