Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
ack! The first step is similar. you prove that it's divisible by 5 and 401 by normal methods. then I get to the second step 2005 = 16 mod 17 or 58 mod 59. from then it always seems I'm left with a remainder of some sort.
I give up on this one.
I solved 5) again. Interestingly, despite my mistake, the proposition is true for both 2005 and 2011. Fermat's little theorem is not necessary, just modular arithmetic. I'll solve it for 2011.
1 + 2 + 3 + ... + 2011 = 2011*1006
By Euclid's algorithm, gcd(2011,1006) = gcd(1006,1005) = gcd (1005,1) = 1
Thus, 2011 and 1006 are coprime. To prove that the sum is a multiple of the product, it suffices to prove that it's divisible by 2011 and 1006.
The sum 1^2011 + 2^2011 + ... + 2009^2011 + 2010^2011 + 2011^2011 can be expressed in mod 2011 by 1^2011 + 2^2011 + ... + (-2)^2011 + (-1)^2011 + 0^2011.
Since 2011 is odd, k^2011 = - (-k)^2011, so k^2011 + (-k)^2011 = 0, and this proves that the sum is a multiple of 2011.
For 1006, we get the sum mod 1006 as 1^2011 + 2^2011 + ... + (-2)^2011 + (-1)^2011 + 0^2011 + 1^2011 + ... + (-1)^2011.
It's similar to the previous case, this sum is 0 and 1006 divides the sum. It's an exercise to prove for 2005 :)
I'll give a hint for 4):
There are basically two properties that allow us to evaluate a sum. One was used in 5), it's when we can pick to terms that have some symmetry and evaluate it. The other is when it's a telescoping sum, that is, its general term can be expressed as f(n) - f(n-k) or something like that. This technique is used in 4). Also, note that k^2 + 3k + 1 = (k+1)(k+2) - 1.
Additionally, andymac, I've seen Fermat's little theorem when I was in high school. It was stated without proof, though, so I had to wait until university to see its demonstration. You can get a very good background on number theory with this book. IIRC the most complicated chapters demanded only the knowledge of finite fields, which most institutes offer at the first year of the course.
Joined: 11/30/2008
Posts: 650
Location: a little city in the middle of nowhere
k^2 + 3k + 1 = (k+1)(k+2) - 1
It's all so simple now!
2004's prime factors are 2^2 * 3 * 167. Therefore any term past the 167th term = 0 mod 2004, because it has factors of 4, 3, and 167, inside k!
The factorisation makes things a lot easier as well. The kth term is therefore k!((k+1)(k+2) - 1) or (k+2)! - k!. and the k+2th term = (k+4)! - (k+2)!. adding these two together gives k! + (k+4)!, and the (k+2)! term is cancelled out.
basically if we add al the odd terms together, we get 199! - 1!, because all the intermediate terms are cancelled out, and since 199! has factors of 167, 4 and 3, 1! + 199! = 2003 mod 2004. Similarly, the even terms will be 2! + 200!, which is then 2002 mod 2004. therefore, the remainder when dividing the terms by 2004 is 2001.
EDIT: my uni library has that book in stock, I might take a look at it.
This is a quite easy one, but I was thinking about it and couldn't come up with the most obvious answer. (It has been too long since my last math class with derivatives and such... I can't remember almost anything about it because of lack of need and usage.)
Demonstrate that the area of the unit circle is 3.14159265...
(Obviously you can't use pi itself, nor any function defined in terms of pi, because that would be a circular proof.)
Just wanted to point out there's an easier way to do this one. Actually, I remember this problem coming up in a math contest I did in high school.
1) Show that, if p is a prime larger than 3, then p^2 - 1 is divisible by 24.
p^2 - 1 = (p+1)(p-1)
Since p is odd, both p+1 and p-1 must be even, and as they are consecutive even numbers, one of them must be divisible by 4. So p^2 - 1 is divisible by 8.
Further, since p-1, p, and p+1 are three consecutive integers, 3 must divide one of them. Since p is prime and greater than 3, it must be p+1 or p-1, and so 3 divides p^2 - 1.
p^2 - 1 is divisible by 3 and 8, and thus is divisible by 24.
Warp wrote:
This is a quite easy one, but I was thinking about it and couldn't come up with the most obvious answer. (It has been too long since my last math class with derivatives and such... I can't remember almost anything about it because of lack of need and usage.)
Demonstrate that the area of the unit circle is 3.14159265...
(Obviously you can't use pi itself, nor any function defined in terms of pi, because that would be a circular proof.)
Inscribe and circumscribe a hexagon in the circle, then keep doubling the number of sides. You can recalculate the area each time using the half-angle formulae. It doesn't converge particularly fast, and the algebra gets really nasty, but it will converge in the end.
This is how Archimedes came up with 223/71 < pi < 22/7. He used a 96-sided polygon for this, though. A hexagon gives the much worse approximation of 1.5*sqrt(3) < pi < 2*sqrt(3), which in rational terms is about 18/7 < pi < 7/2.
Consider a regular polygon inscribed in a unit circle. The semiperimeter times the "apótema" (don't know the name in English, it's the segment that connects the center of the circle to the midpoint of the regular polygon's side) gives the area.
The side of the regular polygon of 2n sides is L(2n) = sin (180º/2n). Notice that L(2n)^2 = sin^2 (180º/2n) = 1/2 (1 - cos (180º/n) ) = 1/2 - sqrt(1 - L(n)^2).
So, L(2n) = sqrt(1/2 - sqrt(1 - L(n)^2)). If we substitute L(4) = sqrt(2)/2, we get a formula, that's not very pretty. Take a look:
L(8) = sqrt(2 - sqrt(2))
L(16) = sqrt (2 - sqrt(2 + sqrt(2))
L(32) = sqrt (2 - sqrt(2 + sqrt(2 + sqrt(2)))
Basically, a polygon with 2^(n+1) sides has n nested radicals in the formula. Its semiperimeter is the sum of the lengths of half its sides, so 2^n * L(2^(n+1)). Since a regular polygon tends to the circle and the "apótema" tends to the radius, when n goes to infinity the area will be:
A = lim (n-> infty) 2^n * sqrt(2 - sqrt(2 + sqrt(2 + sqrt ( 2 + ... )))) {n radicals}
Notice that there are many ways to compute pi, I posted this method because Warp seemed to want a geometric argument, this limit is not trivial, in fact, much time passed before a proof of its irrationality was found, and it's also transcedental, meaning there's no way to represent it with finite radicals or any polynomial root.
My above analysis leads to the following. If I is the area of the inscribed polygon, and c is the cosine of half the central angle of the polygon, then
I' = I/c
c' = sqrt((1+c)/2)
Starting with a triangle has I = 3*sqrt(3)/4 and c = 1/2. Starting with a square has I = 2 and c = 1/sqrt(2). At any stage of the iteration, I/c < pi < I/c^2
Starting with a triangle, this gives...
2.598, 3.000, 3.106, 3.133, 3.139, 3.141
5.196, 3.464, 3.215, 3.160, 3.146, 3.142
As you can see, we're getting about 1 digit every 2 repetitions. Note that the last pair is approximately (223/71,22/7) and corresponds to a polygon of 96 sides, as before.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
A friend told me about this problem, and it's been driving me crazy - I feel like there is a simple solution to it, but I simply can't find it. I thought maybe you guys would find it a fun (and maybe challenging) problem!
Here's the problem:
*Draw a circle C1 with radius 3 with center at (0,0).
*Draw a circle C2 with radius 2 with center at (1,0).
*Draw a circle C3 with radius 1 with center at (-2,0).
Your task is now to find the biggest circle (in terms of radius) that is completely inside the green zone shown in the picture below. Bonus points if you can give the coordinates of the centroid.
I realize that it wouldn't be too hard to find a numerical solution to this, but I'm looking for an exact analytical solution (if it exists).
Shouldn't the center of the new circle have a distance of R + 1 from (-2, 0), R +2 from (1, 0), and 3 - R from (0, 0)? Two of those should give you two legs of a triangle, the remaining leg of which is known already (lying on the X axis); from there you ought to be able to do some trig to get the triangle's angles.
Or am I off?
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Wow, that theorem works perfectly! I'm impressed that you could pull up that theorem just 10 minutes after I posted the problem. :) Using that theorem, I found the radius to be r=6/7. Thanks for the help.
Obviously Stewart's theorem is faster, but...
Derakon wrote:
Shouldn't the center of the new circle have a distance of R + 1 from (-2, 0), R +2 from (1, 0), and 3 - R from (0, 0)? Two of those should give you two legs of a triangle, the remaining leg of which is known already (lying on the X axis); from there you ought to be able to do some trig to get the triangle's angles.
Easier to solve for the x and y coordinates of the center.
(R+1)2 = (x+2)2 + y2
(R+2)2 = (x-1)2 + y2
(3-R)2 = x2 + y2
Subtract the third equation from the first two.
(R+1)2 - (3-R)2 = x2 + 4x + 4 + y2 - x2 - y2
(R+2)2 - (3-R)2 = x2 - 2x + 1 + y2 - x2 - y2
Simplify
8R - 8 = 4x +4
10R - 5 = -2x + 1
Add double the second equation to the first
28R - 18 = 6
Solve and back-substitute
R = 6/7
x = -9/7
y = 12/7
That doesn't looks like an easy integration to do. Why do you think that Wolfram Alpha is wrong and there's a trivial anti-derivative to that function?
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
p4wn3r wrote:
Prove that Wolfram Alpha is complete crap and determine
I have tried to solve this today, but without much luck. I've tried several variable substitutions, considered integration by parts, and generally searching for a method that could work. Can you provide a hint how to solve this? I think I'm drawing blank.
It's right. You need to do another change of variable now:
The more straight forward would work too, and it's how I first integrated the function, while rearranging the resulting terms, I noticed the previous one would get the job done sooner.
Now finish her.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
That integral can be split into
which we can split further into (I forgot to add dv in the integrals, so assume that they are there)
All these three integrals are now easily solvable, and the solution is
(plus a constant c if you like). This can be expressed in x by backtracking (using v=(coth u)^(2/3) and x = (sinh u)^2/3) but the expression would look so tangled up I will leave it expressed in v if that's ok.
I actually found it fun to put x back into the formula. It turned out much prettier than I thought it would. A fast way to get x is:
It's a good exercise to simplify the expression and put x in it, we eventually get:
Eat that Mathematica! To make sure it was correct, I plugged it in Mathematica itself and...
OmnipotentEntity wrote:
That doesn't looks like an easy integration to do. Why do you think that Wolfram Alpha is wrong and there's a trivial anti-derivative to that function?
Because there's a criterion that I can apply to that function that will say it has an elementary primitive shortly after looking at it, it's an obscure technique that I didn't offer a solution that used it to show it wasn't necessary, but I'll tell it now.
Look at the change of variable that ultimately solved the integral, namely v in terms of x. To find it through normal means, we had to apply two changes of variables that required some experience with integrals and some algebra. The question is: is there a method that would determine right off the bat the transform that would make the integral solvable by the common methods (integration by parts, partial fractions, etc) ? The answer is yes, for that function it's relatively easy.
This is called Chebyshev's finite integrability theorem.
Functions of the form f(x) = x^m ( a + b x^n )^p , where m,n,p are rational numbers, admit an elementary primitive if, and only if at least one of the following is satisfied:
1) p is an integer. For this case, expand the binomial and integrate the function.
2) (m+1)/n is an integer. For this case, apply the change of variable a + b x^n = u^s , where s is the denominator of the irreducible fraction of p.
3) (m+1)/n + p is an integer. For this case, apply the change of variable a x^(-n) + b = u^s, where s is the same as in (2).
If you look at the function, it satisfies case (3), so it must have an elementary primitive, and you could get it done much sooner with this, but I wanted to show it wasn't necessary. I'm surprised this simple procedure was missed by the integrator's programmers.
The more straight forward 
would work too, and it's how I first integrated the function, while rearranging the resulting terms, I noticed the previous one would get the job done sooner.
Now finish her.
All these three integrals are now easily solvable, and the solution is
It's a good exercise to simplify the expression and put x in it, we eventually get:
Eat that Mathematica! To make sure it was correct, I plugged it in Mathematica itself and...
