Wikipedia:Reference desk/Archives/Mathematics/2008 October 17

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.

October 17

Logic problem

I'm having difficulty with a problem posed in a newspaper, which as far as I can see has an infeasible definition. In outline, four perfect logicians each have a different number from 1 to 9 on their forehead - they can see each other's but not their own. They announce in turn whether or not they know their number; if not, they give the sum of two of the other ones. Apparently, the sequence is A:No,14; B:Yes; C:No,7: D:No ... My analysis is that B must see exactly one of the numbers (5,6,8,9) on C and D so knows that he has the difference from 14; C must see these numbers adding to 14 on B and D so can't specify his own number; and D, knowing that two numbers from those on B, C and himself sum to 14, sees only one possible component (the number on B) so knows that his number is B's one subtracted from 14. Thus D's "No" is wrong. Have I missed something?…81.154.108.60 (talk) 14:17, 17 October 2008 (UTC)

I agree. Given the answers from the others, I can't see how D could not know his number. Zain Ebrahim (talk) 15:02, 17 October 2008 (UTC)

I agree as well, you analysis looks good. --Tango (talk) 15:26, 17 October 2008 (UTC)

I did an exhaustive search and there were no solutions after the "D:No" condition is added. --71.106.183.17 (talk) 08:29, 19 October 2008 (UTC)

Challenge the newspaper to a wager.Cuddlyable3 (talk) 13:04, 19 October 2008 (UTC)

Sorry. You're all wrong. What you've missed is that each person's calculation should take into account not only the information from a "no" but also from a yes! Here is a simplified problem, once you've gotten your head around this one you'll have the answer to your problem:

“ Three mathematician friends have finished doing some work. Each looks up to see that the other two have funny dirt on their face, and starts laughing at them. As each of the three laughs at the other two, he assumes the other two are laughing at EACH OTHER but not at him. After a while of laughing at the other two, suddenly they all stop laughing! -- they realize they themselves must be dirty too! How do they know? ”

The answer is (SPOILER): after a while each reasons thusly: Suppose I were clean. Then my friends are laughing at each other, and I'm laughing at both of them. But they're mathematicians, and after a while one of them, in this hypothetical scenario in whic I am clean, would reason thusly: "Wait a minute. Suppose I were clean. Then WHO IS THE ONE DIRTY GUY LAUGHING AT?" and stop laughing. But in fact they've been laughing for a long time! So I must be just as dirty as the other two, since the hypothetical scenario in which I am clean would lead them to realize that they're dirty and stop laughing, which hasn't happened!  :(. They come to this realization at the same time and promptly stop laughing.

I think we've taken into account the information gained for a "yes". Can you give an example of a set of numbers that gives the sequence of responses in the newspaper? --Tango (talk) 22:22, 20 October 2008 (UTC)

"My analysis is that B must see exactly one of the numbers (5,6,8,9) on C and D" Whoa! B deduces that A must see the pair 5, 9 or 6, 8. So if A has one of those numbers, for example, the 5, then he must be seeing 6 and 8 and if B can only see one of them then his number is determined. But B might also see 9. So your assumption that he must see exactly one of the numbers on C and D is incorrect. TheMathemagician (talk) 04:22, 21 October 2008 (UTC)

I don't follow. Please give an explicit example of numbers the 4 people could have that would give the response in the newspaper. --Tango (talk) 10:36, 21 October 2008 (UTC)

You really don't get it? Just reread your starting paragraph "My analysis is that B must see exactly one of the numbers (5,6,8,9) on C and D so knows that he has the difference from 14;" is WRONG. He can see TWO of those numbers, per the analysis immediately above.

So suppose A has 5, B has 6, C has 9 and D has 8. B knows that 14 can come only from 6+8, as A couldn't see his own 5, therefore he knows his own 6. C can see the same 14 so can't know his own number. D knows that A's total of 14 must have been 6+8, so is in exactly the same position as B, i.e. does know his number. This arrangement also conflicts with C's total of 7, of course. I believe that the problem was completed by A knowing his number the moment D said "no", and the readers were asked to give D's number. So rather than argue about things, can someone give a specific answer to the problem as posed?—217.43.210.97 (talk) 18:44, 21 October 2008 (UTC)

That's what I asked you. Our conclusion was that the question was wrong, ie. there are no sets of numbers that get those responses. You're saying we're wrong about that (you've shown the argument put forward by the OP doesn't work, but that doesn't mean the conclusion is wrong - not everyone that agreed used the same method) but haven't given a counterexample. --Tango (talk) 23:26, 21 October 2008 (UTC)

I gave you enough information for a counterexample and showed how your argument was wrong. I'm not your grad student. If you want me to go through and give working numbers and show why it works, why don't you offer me $20 for my trouble?

You showed an error in one of the methods used, that's not a counterexample of the conclusion. An anon said he did an exhaustive search and found no solutions, you haven't done anything to show he was wrong. You don't need to go through the working, just give the four numbers and I can work it through. --Tango (talk) 13:17, 22 October 2008 (UTC)

If the unsigning poster two up can give a valid solution in "working numbers", I'll gladly give $20.→86.155.184.133 (talk) 17:50, 23 October 2008 (UTC)

Tangents to circles

I have two questions regarding tangents to circles: 1) Given a circle and a point outside it, how is it shown that the point has two tangents through it? The article Tangent lines to circles makes this claim but does not prove it. 2) How is it shown that given any two circles not contained within each other, there exists two common external tangents? --146.95.224.114 (talk) 15:32, 17 October 2008 (UTC)

1) The system of circle and external point is symmetrical about the line joining the point to the centre of the circle, thus every feature has a mirror image by reflection in this line. 2) The system of two circles is symmetrical about the line joining their centres, so ...—81.154.108.60 (talk) 15:54, 17 October 2008 (UTC)

Another way to show 1) is to work out the formula for determining the lines through a point that are tangent to a circle. I'll leave out the details, but it will produce a quadratic equation with two roots (if the point is outside the circle). - Rainwarrior (talk) 16:07, 17 October 2008 (UTC)

Two circles may have four common tangents. Bo Jacoby (talk) 18:43, 17 October 2008 (UTC).

Complex Function

Hello. I'm working through an exam question and have just completed one part but the next part depends on this part, so it's fairly important that I'm right. If I give the question and my answer, could someone please check it for me please?

'The function f is defined, for any complex number, by $f(z)={\frac {iz-1}{iz+1}}$. Suppose that x is a real number. Find expressions for Re f(f(x)) and Im f(f(x)).'

I get $Ref(f(x))={\frac {3x^{2}+2}{x^{2}+2}}$ and $Imf(f(x))={\frac {2x}{x^{2}+2}}$

Is this correct? Thanks. 92.2.207.16 (talk) 18:18, 17 October 2008 (UTC)

Try a simple example. x = 0. f(x) = f(0) = −1. f(f(x)) = f(f(0)) = f(−1) = (−i−1)/(−i+1) = −(1+i)/(1−i) = −(1+i)²/2 = −i. Re(f(f(0))) = Re(−i) = 0. BUT (3x²+2)/(x²+2) = (3·0²+2)/(0²+2) = 1 ≠ 0. Sorry, your result seems to be incorrect. Bo Jacoby (talk) 18:38, 17 October 2008 (UTC).

Attempt two. $Ref(f(x))=0\,\!$ and $Imf(f(x))={\frac {x+1}{x-1}}$. Any better? It fits your example but that's not a guarantee. Thanks 92.2.207.16 (talk) 18:51, 17 October 2008 (UTC)

Why are you making attempts. just do it. Let us pretend that you are going to be executed by the wikipedia agents if the result is not correct... I am sure that you would then produce an absolutely correct solution. Seems OK anyway :) PMajer (talk) 19:06, 17 October 2008 (UTC)

Cheers PMajer. The next part of the question is to determine expressions for $Ref(f(f(x)))$ and $Imf(f(f(x)))$. Using my previous answer, I get $Ref(f(f(x)))={\frac {2x}{x^{2}+1}}$ and $Imf(f(f(x)))={\frac {x^{2}-1}{x^{2}+1}}$. Is this correct? Thanks again. 92.2.207.16 (talk) 19:32, 17 October 2008 (UTC)

MMM.. no... It means that either you are doing too many distractions in the computation, or you are not writing correctly the composite functions. In the first case you probably have to do more exercise. It is like in a gym: what is important is not quantity but quality. Write it in a clean sheet of paper, use a pencil and rubber, not a pen, write all passages in a way that you can check them at a glance. Do this way, at the end you will spare time. In the second case, it is probably more instructive if you reflect at the general composition f(g(z) of functions like f(z)=(az+b)/(cz+d) and g(z)=(Az+B)/(Cz+D). These are named linear fractional maps or Möbius transformations. The result of the composition is of the same kind, and you can check that the rule for the coefficients is the same of multiplication of the 2x2 matrices of coefficients. This should speed up the computations. In your case you just have to compute powers of

${\begin{pmatrix}i&-1\\i&1\end{pmatrix}}$.

Check that the cube of this matrix is $\lambda I$. Doesn't matter what is $\lambda$, because it does not affect the corresponding function. So your Möbius transformation f has period 3: $f(f(f(z)=z$ for all $z$, and you can conclude. PMajer (talk) 08:16, 18 October 2008 (UTC)

You may find life simpler if you multiply numerator and denominator by −i to get

$f(z)={\frac {z+i}{z-i}}$

and, if you want to find real and imaginary parts, make the denominator real as follows

$f(z)={\frac {(z+i)(z^{*}+i)}{(z-i)(z^{*}+i)}}={\frac {|z|^{2}+2iRe(z)-1}{|z|^{2}-2Im(z)+1}}$

$=\left({\frac {|z|^{2}-1}{|z|^{2}-2Im(z)+1}}\right)+i\left({\frac {2Re(z)}{|z|^{2}-2Im(z)+1}}\right)$

where z^* is the complex conjugate of z. With a little thought you can see that this function maps the circle |z|=1 to the imaginary axis; the imaginary axis to the real axis; and the real axis to the circle |z|=1. On the Riemann sphere it is a 120-degree rotation about the axis through its two fixed points. Gandalf61 (talk) 10:46, 18 October 2008 (UTC)

It's no biggie. My discipline is to keep complex numbers in the form A + iB where A or B can go negative but the + is sacred. So

f(z) = (-1 + iz)  /  (1  + iz)

Then from my toolbox I whip out my trusty "difference of two squares" widget which says in general:

(F^2 - G^2) = (F - G)(F + G)

That works for complex numbers so I make F = 1 and G = - iz. Why, I hear you ask, does he want to do that?
Ah grasshopper, it is my plan to convert the denominator of f(z) from complex to real like this:

f(z) = (-1 + iz)(1 - iz)
       -----------------
       ( 1 + iz)(1 - iz)

     =  z^2 - 1   +   i 2z
        ------------------
            1 + z^2

     =  z^2 - 1   +   i   2z
        -------         -------          [Equation 1]
        z^2 + 1         z^2 + 1

Having got f(z) into disciplined form, I shall plug it into itself to get the answer f(f(z)).
Before taking that plunge note that z^2 appears 3 times above so let's evaluate (f(z))^2 once by itself
to save repetitions later:

(f(z))^2 = ( z^2 - 1   +   i   2z   ) ( z^2 - 1   +   i   2z   ) 
           ( -------         -------) ( -------         -------) 
           ( z^2 + 1         z^2 + 1) ( z^2 + 1         z^2 + 1)

         = z^4 - 2z^2 + 1 - 4z^2   +   i 2(   -2z    z^2 - 1 )
           ---------------------          ( -------  ------- )
               (z^2 + 1)^2                ( z^2 + 1  z^2 + 1 )

         = z^4 - 6z^2 + 1   +  i  -4z^3 - 4z
           --------------        -------------
           z^4 + 2z^2 + 1        z^4 + 2z^2 +1

         = z^4 - 6z^2 + 1   +  i  (-4( z^3 +z ) )
           --------------         (-------------)
           z^4 + 2z^2 + 1         (z^4 + 2z^2 +1)

Now in equation 1 you know what to do: you have substitutes for z and z^2, and I will let you use my widget
to deal with a complex denominator. The rest is left as an exercise for the grasshopper.

Cuddlyable3 (talk) 13:02, 18 October 2008 (UTC)

My discipline is to keep complex numbers in the form A + iB: concerning the problem above, I fear this is a completely loosing approach. Think what happens to poor f(z) when you replace three times Equation 1 into itself. An explosion. Compare it with the simple 2x2 matrix multiplication

${\begin{pmatrix}i&-1\\i&1\end{pmatrix}}{\begin{pmatrix}i&-1\\i&1\end{pmatrix}}{\begin{pmatrix}i&-1\\i&1\end{pmatrix}}=\lambda {\begin{pmatrix}1&0\\0&1\end{pmatrix}}$,

(or also, with the more theoretic argument by Gandalf), that immediately tells you $f(f(f(z)))=z$ for any $z$. Only at the end one takes Re and Im of $z$. The moral is: (1) the cartesian form is not always the best for doing computation with complex numbers, and (2) better not to add noise when a question has already been answered PMajer (talk) 14:07, 18 October 2008 (UTC)

I think what I presented is a practical approach for User 92.2.207.16 to check their answer to their first question, especially if that did not use a cartesian form. PMajer I am sorry that you consider mine a "completely loosing[sic] approach", "added noise" or even immoral. The arbiter who matters is 92.2.207.16. Cuddlyable3 (talk) 12:55, 19 October 2008 (UTC) --I am very sorry, Cuddlyable. I really did not mean to offend you. Now I read what I wrote and I agree that the form is unpleasant. My remark about noise is also quite stupid. I did not see the point of that computation, but never thought it as immoral (why). Please accept my excuses. Let me add that in my place, when we discuss of mathematics we use to insult each other for joke and we laugh a lot, but of course I forgot that here it's different PMajer (talk) 13:12, 19 October 2008 (UTC)

Diophantine Equation

Given an arbitrary linear diophantine equation ax + by = c, it's supposed to be solvable if gcd(a, b) | c , however, this is always true as all numbers can be divided by 1, which is a divider for any two numbers. Is it supposed to be gcd(a, b) | c, gcd(a,b) != 1 or are all diophantine equations solvable? 90.230.54.138 (talk) 22:28, 17 October 2008 (UTC)

No, it's not always true. Suppose a = 4 and b = 6 and c = 3. Then the gcd of a and b is 2, and 2 DOES NOT divide 3. Since the gcd of a and b does not divide c in this case, there are no integer solutions of the Diophantine equation. If the gcd of a and b does divide c, then solutions exist. In particular, if the gcd of a and b is 1, then solutions exist since 1 divides every integer. What you say is "always true" is NOT true when the gcd is not 1 and c is not one of its multiples. Michael Hardy (talk) 22:55, 17 October 2008 (UTC)

I see, thank you. 90.230.54.138 (talk) 23:08, 17 October 2008 (UTC)