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

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 9

Apollonian Circles

Suppose I have a triangle ABC, and I want to construct three circles - one through each vertex - such that they are mutually tangent. How would I do this? Lucas Brown (talk) 02:23, 9 April 2009 (UTC)

This sounds like homework, so I will not give an answer outright. You can start with one edge and the two circles centered at its endpoints. What is the relationship between the length of that edge and radii of those two circles?. Write that as an equation. Do you see where this will take you? -- Tcncv (talk) 03:13, 9 April 2009 (UTC)

It's not homework - I designed one of the San Diego Math Circle logos, but lost the Geometer's Sketchpad file I made it in, so I am attempting to recreate it. Lucas Brown (talk) 04:08, 9 April 2009 (UTC)

There's a less algebraic and more visual answer here. —David Eppstein (talk) 03:27, 9 April 2009 (UTC)

That's actually not all that helpful... unless you can tell me how to get the centers of the black circles in that diagram, given their points of tangency with the circle containing and tangent to them. Lucas Brown (talk) 04:10, 9 April 2009 (UTC)

Huh? The centers of the black circles are the points A, B, and C that your first comment supposed that you already have. So, you tell me how to get the centers. —David Eppstein (talk) 04:32, 9 April 2009 (UTC)

I intended the A, B, and C to be the points of tangency of the three black circles with the circle containing and mutually tangent to them. Lucas Brown (talk) 18:18, 12 April 2009 (UTC)

If you're given those three points of tangency, the center of the red circle is the intersection of any two of the perpendicular bisectors of the three line segments they form. The sides of the black triangle are perpendiculars to the lines through the tangencies and the center of the red circle. And the centers of the black circles are the points where two sides meet. —David Eppstein (talk) 00:25, 16 April 2009 (UTC)

I just clicked on that page. I find this: "...bisect its angles (blue), and drop perpendiculars from the point where the bisectors meet to the three sides (green). The points where these perpendiculars cross the sides are the desired points of tangency. They are also the points where an inscribed circle (red)..." etc. But the picture isn't there. I don't see anything that's blue or black or any other color, except the letters on the page. Michael Hardy (talk) 23:38, 9 April 2009 (UTC)

It's a Java applet. Do you have Java disabled, maybe? There's a static version of the figure here that's supposed to be shown when your browser doesn't understand the applet html tag (I don't know if that happens any more, but this was coded in 1999), but maybe that doesn't help when it does understand the tag but has been set to ignore it. —David Eppstein (talk) 01:09, 10 April 2009 (UTC)

This page contains an algebraic solution. See lines 12, 13, and 14, where s is defined on line 8. Geometrically, David Eppstein's reference provides a solution, but you'll have to use techniques to bisect the angles and then construct the perpendiculars. -- Tcncv (talk) 05:28, 9 April 2009 (UTC)

Inequality and greatest integer function

"For a +ve integer n, prove that

${\sqrt {4n+1}}<{\sqrt {n}}+{\sqrt {n+1}}<{\sqrt {4n+2}}$.

Hence or otherwise prove that

$[{\sqrt {n}}+{\sqrt {n+1}}]=[{\sqrt {4n+1}}]$

where [x] denotes the greatest integer not exceeding x." I proved the first part i.e. the inequality by squaring two times but I am not able to solve the second part which involves the greatest integer function. The book from which I took this question gives the solution to the second part but it is not easy to understand, has mistakes and involves too many manipulations. Please help.--Siddhant (talk) 11:27, 9 April 2009 (UTC)

It's enough to show that there is no integer m such that ${\sqrt {4n+1}}<m<{\sqrt {4n+2}}$. But this is obvious: for such an m, we would have $4n+1<m^{2}<4n+2\,\!$, which is impossible. Algebraist 11:34, 9 April 2009 (UTC)

Hey! Algebraist, this is a wonderfully small and sweet solution! The book I took this question from, provides a half page solution! Capital! Thanks. --Siddhant (talk) 16:47, 9 April 2009 (UTC)

As to the first part notice also that the two inequalities come quite directly from the function $f(x):={\sqrt {x}}$ being a strictly concave function: the first inequality

${\sqrt {n}}+{\sqrt {n+1}}<{\sqrt {4n+2}}$

is just

${\frac {1}{2}}\left(f(a)+f(b)\right)<f({\frac {a+b}{2}})$,

with $\textstyle a:=n,b:=n+1$; the second inequality is

$\textstyle f(b+1)-f(b)<f(a+1)-f(a)$

with $\textstyle a:=n<b:=4n$. --pma (talk) 14:28, 9 April 2009 (UTC)

pma, I must confess that I am unable to understand your approach due to my limited study of functions. Can you simplify it with more words instead of notations and expressions?--Siddhant (talk) 16:47, 9 April 2009 (UTC)

It is just about elementary properties of convex functions, that you can find in the links. But if you do not have a background in one real variable, and on the other hand you already got the inequalities by yourself by squaring, maybe it doesn't matter. I added that remark as I was somehow misled by your user-page ;-) --pma (talk) 18:14, 9 April 2009 (UTC)

Thanks for your effort. I have removed the misleading userbox. Actually I aspire to be an advanced mathematician.--Siddhant (talk) 13:37, 10 April 2009 (UTC)

Of course, I definitely did not mean to underestimate your comprehension; I only meant that the above approach makes sense provided some results are already given as known, otherwise it would sound like a complicated way of proving a simple fact. But since you asked for details, here they are: 1) The arithmetic mean of the values of a (strictly) concave function in two distinct points is less than the value of the function in the arithmetic mean of the two points (this is the "more words" version of the first inequality I wrote). 2) The difference quotient of a (strictly) concave function is (strictly) decreasing wrto both endpoints (that is, (f(b)-f(a))/(b-a) decreases if you increase either a or b). 3) We know that squared root of x is a (strictly) concave function, for instance, because it has a (strictly) negative second derivative. These are basic facts on convex functions that you can find in any elementary textbook (recall that by definition f is concave if and only if -f is convex). --pma (talk) 15:22, 14 April 2009 (UTC)

Since all three numbers are positive, the inequality is true if and only if it is true of their squares. So square them:

$4n+1<n+2{\sqrt {n}}{\sqrt {n+1}}+(n+1)<4n+2,$

and then ask whether that is true. Subtracting 2n + 1 from all three and dividing by 2 does not disturb the validity (or lack of validity) of the two inequalities:

$n<{\sqrt {n(n+1)}}<n+{\frac {1}{2}}.$

The first of these two inequalities is trivial.

The second one just says that the geometric mean of n and n + 1 is less than their arithmetic mean. In this connection, see inequality of arithmetic and geometric means. Michael Hardy (talk) 17:42, 9 April 2009 (UTC)

Number of combinations with constraints

I'm trying to figure the number of combinations in a given system when there are multiple constraints. They are:
I) Exactly 16 characters long
II) Character space is: A-Z (uppercase) + 0-9
III) At least 6 numbers and 6 letters
IV) No adjacent characters are the same
V) Any character at most 4 times in the sequence.

I'm figuring it this way (character # and number of characters to choose from):

01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  16
36  35  35  35  35  35  35  35  34  34 <-- this is where I get stuck

I don't think I'm getting it right. While I'm bound by (V) to have at most 4 characters of the same type, leaving me with 34 characters to pick from when I reach the 9th one (because I can only use the same character every other slot, given IV), it doesn't really mean I'll use the same character.

What's the usual, faster approach in this case? Thanks! 189.112.59.185 (talk) 13:13, 9 April 2009 (UTC)

At first I was tempted to say you should write a computer program to try every possibility and reject those which violate any of the rules. Unfortunately, the number of cases you'd need to try would be so huge that even a computer couldn't handle it. StuRat (talk) 19:12, 9 April 2009 (UTC)

If you don't care about the exact value, you can get a pretty close upper bound by ignoring rules IV and V. Then the total is $\sum _{i=6}^{10}26^{i}10^{16-i}{\tbinom {16}{i}}\approx 2^{80.8}$. So these passwords have less than 81 bits of security, which might be cutting it a bit close these days (depending on the application).

The exact value is going to be pretty difficult to calculate. You can't do it by multiplying together a choice count for each position because the number of choices at each position depends on previous choices. Here's one possible approach (too complicated to do by hand, but feasible on a computer). There are $\sum _{i=6}^{10}{\tbinom {16}{i}}$ = 51,766 different ways of interleaving letters and numbers in the password. For a given interleaving the number of passwords is the number of letter choices times the number of number choices. Those counts depend only on the length of the letter/number subsequences (6 to 10) and on the positions in them that are still adjacent after interleaving (since rule IV applies only at those places). You can find the counts with a recursive function like

     BigInt password_count(int length, unsigned rule_IV_mask, int last_char_uses_left, int num_chars_with_4_uses_left, ..., int num_chars_with_1_use_left) {
         if (length == 0)
             return 1;
         if ((rule_IV_mask & 1) == 0)
             last_char_uses_left = 0;
         BigInt total = 0;
         int n = num_chars_with_4_uses_left;
         if (n > 0)
             total += n * password_count(length - 1, rule_IV_mask >> 1, 3, num_chars_with_4_uses_left - 1, num_chars_with_3_uses_left + 1, ...);
         n = num_chars_with_3_uses_left - (last_char_uses_left == 3 ? 1 : 0);
         if (n > 0)
         ... etc
     }

You will want to memoize the return values of this (or use dynamic programming). There are only ~10⁶ possible argument values, so it should be doable. BigInt needs to be at least 81 bits long. -- BenRG (talk) 19:44, 9 April 2009 (UTC)

If one really wants an exact computation, I think one should make successive partitions in classes, taking into account the constraints. Then one counts separately the number of strings in each class. The first partition is according to the number of ciphres/numbers, that is: 6 ciphres + 10 numbers;or 7+9;or 8+8 ;or 9+7 ;or 10+6 (the last two gives the same number of strings as the first two of course). One works separately the three main classes, making a further partition. For instance, for the first class, the choice of 6 ciphres may be, according to their multiplicities, of N₆=9 types, that is: 1+1+1+1+1+1 (all different); 1+1+1+1+2 (4 different, 2 equal);...; 2+4. Similarly, 10 numbers may be: all different;.. &c: N₁₀ types = additive partitions of 10 into numbers not larger than 4). A program should list these N₆ x N₁₀ types (not a big number); for each of them compute the corresponding number of strings of that type (a huge number but I think it should have an easy formula). --pma (talk) 20:49, 9 April 2009 (UTC)

The first partition here is between BenRG's five values of i in $\sum _{i=6}^{10}26^{i}10^{16-i}{\tbinom {16}{i}}$, e.g. i=6 for 6 letters + 10 numbers. Perhaps it is quickest to calculate this overestimate then subtract the count of passwords which fail tests IV and V. Certes (talk) 12:31, 14 April 2009 (UTC)

Right, definitely better! --pma (talk) 14:41, 14 April 2009 (UTC)

Rule of Three expressed as a Mathematical Formula

The (military) Rule of Three has, as a chain of command, three subordinates and one leader, that leader being one of three subordinates to a higher ranking leader and advancing likewise up the chain of command to the commander in chief. I tried to express this as a mathematical formula but found that I did not know how. (((3+1)*3+1)*3+1)...)*3+1=A would be the only way I'd do it, but I'm hoping there is a more elegant way to express the concept. --66.188.139.156 (talk) 22:43, 9 April 2009 (UTC)

Geometric progression. --Icek (talk) 22:57, 9 April 2009 (UTC)

I don't think it is as simple as that. The problem transforms to

${\begin{aligned}f(0)&=0\\f(1)&=1\\f(n)&=f(n-1)+3(f(n-1)-f(n-2))\\&=4f(n-1)-3f(n-2)\end{aligned}}$

which seems to have some properties similar to the Fibonacci numbers, which leads me to believe there is no simple formula. (But someone may come along and prove me wrong.) -- Tcncv (talk) 23:08, 9 April 2009 (UTC)

It's just summing a finite geometric series:

$1+3+3^{2}+3^{3}+\cdots +3^{n}={\frac {3^{n+1}-1}{3-1}}.$

The number of levels below the commander-in-chief is n. For example, if n = 10, then then the sum is

${\frac {3^{11}-1}{3-1}}=88573.$

Michael Hardy (talk) 23:26, 9 April 2009 (UTC)

I stand corrected (and guilty of not thoroughly reading the reference from Icek's first answer). -- Tcncv (talk) 23:38, 9 April 2009 (UTC)

Thanks, guys! --66.188.139.156 (talk) 01:06, 10 April 2009 (UTC)

BTW, although the natural way is Icek's, notice that your linear recurrence has general solution f(n)=3ⁿa+b, that gives the correct answer using the initial conditions. --pma (talk) 09:31, 10 April 2009 (UTC)