geometry
probability
AMC
AIME
3D geometry
USA(J)MO
USAMO

MysticTerminator requested it. I won't be around for a while to grade it, though..

[b]Please specify the set from which you are answering problems if you want them graded (which won't be until Sunday 12/3).[/b]

[u]Really Easy Section[/u]
[i]The questions in this section come primarily from AMC 10.[/i]

1.	Let X, Y and Z be distinct positive integers such that the product XYZ = 2001. What is the largest possible value of the sum X+Y+Z?
2.	Each day, Jenny at 20% of the jellybeans that were in her jar at the beginning of that day. At the end of the second day, 32 remained. How many jellybeans were in the jar originally?
3.	Chandra pays an ISP a fixed monthly fee plus an hourly charge for connect time. Her December bill was $12.49, but in January her bill was $17.54 because she used twice as much connect time in December. What is the fixed monthly fee?
4.	The Fibonacci sequence starts with two 1s, and each term afterwards is the sum of its two predecessors. What one of the ten digits is the last to appear in the units position of a number in the Fibonacci sequence?
5.	If |x-2| = p, where x<2, then x-p=?
6.	Mrs. Walter gave an exam in a math class of five students. She entered the scores in random order in a spreadsheet, which recalculated the class average after each score was entered. Mrs. Walter noticed that after each score was entered, the average was always an integer. The scores (listed in ascending order) were 71,76,80,82, and 91. What was the last score entered?

[u]A bit harder[/u]
[i]These questions are from AMC 12 tests[/i]

1.	If :sqrt:(2+:sqrt:(x))=3, then x=?
2.	If M is 30% of Q, Q is 20% of P, and N is 50% of P, then M/N=?
3.	Find the area of the triangle bounded by the lines y=x, y=-x, and y=6.
4.	How many base 10 four-digit numbers, N=[u]a[/u] [u]b[/u] [u]c[/u] [u]d[/u], satisfy all three of the following conditions? (i) 4,000:le:N<6,000 (ii) N is a multiple of 5 (iii) 3:le:b<c:le:6
5.	If f(x)=ax^4-bx^2+x+5 and f(-3)=2 then f(3)=?
6.	If a,b, and c are three (not necessarily different) numbers chosen randomly and with replacement from the set {1,2,3,4,5}, the probability that ab+c is even is?

[u]More difficult[/u]
[i]The following questions are from MMPC tests. No calculator is allowed[/i]

1.	a) The smaller of two concentric circles has radius one unit. The area of the larger circle is twice the area of the smaller circle. Find R, the difference in their radii.
b) The smaller of two identically oriented equilateral triangles has each side one unit long. The smaller triangle is centered within the larger triangle so that the perpendicular distance between parallel sides is always the same number D. If the area of the larger triangle is exactly twice the area of the smaller triangle, find D.
2.	Solve for x and y, if 1/(x^2) + 1/(x*y) = 1/9 and 1/(y^2)+1/(xy)=1/16.
3.	The residents of Andromeda use only bills of denominations $3 and $5. All payments are made exactly, with no change given. What whole-dollar payments are not possible? (Justify your answer)
4.	Let P(x) = x^3 + x^2  1 and Q(x) = x^3  x  1. Given that r and s are two distinct solutions of P(x) = 0, prove that rs is a solution of Q(x)=0.

[u]Getting Tougher[/u]
[i]The following questions are from AIME exams. No calculators are allowed. Answers are integers between 000 and 999 inclusive. I don't have the answers, so confirm each others answers[/i]

1.	Find the minimum value of |x - p| + |x - 15| + |x - p - 15| for x in the range p ≤ x ≤ 15, where 0 < p < 15.
2.	w and z are complex numbers such that w^2 + z^2 = 7, w^3 + z^3 = 10. What is the largest possible real value of w + z?
3.	What is the largest 2-digit prime factor of the binomial coefficient 200C100?
4.	For each non-empty subset of {1, 2, 3, 4, 5, 6, 7} arrange the members in decreasing order with alternating signs and take the sum. For example, for the subset {5} we get 5. For {6, 3, 1} we get 6 - 3 + 1 = 4. Find the sum of all the resulting numbers.
5.	The sequence 2, 3, 5, 6, 7, 10, 11, ... consists of all positive integers that are not a square or a cube. Find the 500th term.
6.	Each angle of a regular r-gon is 59/58 times larger than each angle of a regular s-gon. What is the largest possible value of s?
7.	A fair coin is tossed 10 times. What is the chance that no two consecutive tosses are both heads.
8.	Note that 6! = 8910. What is the largest n such that n! is a product of n-3 consecutive positive integers.
9.	A wooden unit cube rests on a horizontal surface. A point light source a distance x above an upper vertex casts a shadow of the cube on the surface. The area of the shadow (excluding the part under the cube) is 48. Find x.
10.	There is a line of lockers numbered 1 to 1024, initially all closed. A man walks down the line, opens 1, then alternately skips and opens each closed locker (so he opens 1, 3, 5, ... , 1023). At the end of the line he walks back, opens the first closed locker, then alternately skips and opens each closed locker (so he opens 1024, skips 1022 and so on). He continues to walk up and down the line until all the lockers are open. Which locker is opened last?
11.	Find the smallest positive integer n for which (xy - 3x - 7y - 21)^n has at least 1996 terms.
12.	Find the sum of all positive rationals a/30 (in lowest terms) which are < 10.
13.	At the start of a weekend a player has won the fraction 0.500 of the matches he has played. After playing another four matches, three of which he wins, he has won more than the fraction 0.503 of his matches. What is the largest number of matches he could have won before the weekend?
14.	The game of Chomp is played with a 5 x 7 board. Each player alternately takes a bite out of the board by removing a square any and any other squares above and/or to the left of it. How many possible subsets of the 5 x 7 board (including the original board and the empty set) can be obtained by a sequence of bites?
15.	 ABC is a triangle. The points A', B', C' are on sides BC, CA, AB and AA', BB', CC' meet at O. Also AO/A'O + BO/B'O + CO/C'O = 92. Find (AO/A'O)(BO/B'O)(CO/C'O).

[u]These are tough[/u]
[i]The following are USAMO problems. Again, verify each other's answers. I won't be of much (any) help here.[/i]

1.	n digits, none of them 0, are randomly (and independently) generated, find the probability that their product is divisible by 10.
2.	A pentagon is such that each triangle formed by three adjacent vertices has area 1. Find its area, but show that there are infinitely many incongruent pentagons with this property.
3.	Show that if two points lie inside a regular tetrahedron the angle they subtend at a vertex is less than :pi:/3.
4.	Three vertices of a regular 2n+1 sided polygon are chosen at random. Find the probability that the center of the polygon lies inside the resulting triangle.
5.	Show that the cube roots of three distinct primes cannot be terms in an arithmetic progression (whether consecutive or not).

[u]Good Luck[/u]
[i]The following are IMO problems. Consider them... a challenge. As for the few of you that can do these, feel free, and check each other's answers.[/i]

1.	Given any set of ten distinct numbers in the range 10, 11, ... , 99, prove that we can always find two disjoint subsets with the same sum.
2.	Prove that (2m)!(2n)! is a multiple of m!n!(m+n)! for any non-negative integers m and n.
3.	Given four distinct parallel planes, prove that there exists a regular tetrahedron with a vertex on each plane.
4.	f and g are real-valued functions defined on the real line. For all x and y, f(x + y) + f(x - y) = 2f(x)g(y). f is not identically zero and |f(x)| ≤ 1 for all x. Prove that |g(x)| ≤ 1 for all x.
5.	Determine all ordered pairs (m, n) of positive integers for which (n^3 + 1)/(mn - 1) is an integer.
6.	Show that there exists a set A of positive integers with the following property: for any infinite set S of primes, there exist two positive integers m in A and n not in A, each of which is a product of k distinct elements of S for some k :ge: 2.

[u]Misc.[/u]
[i]These questions provided by MysticTerminator[/i]

1. Prove that for every n, there exists an n-digit multiple of 5^n with only odd digits.
2. How many integers n in {1, 2, 3, ... , 1992} are such that m! never ends in exactly n zeros?
3. If y is proportional to x^2 and y is 8 when x is 8, what is y when x is 6?
4. What is the remainder when x^17+1 is divided by x+1?

Where are you going?

[hide]1.) I think it's missing something

2.) 50 jellybeans (32/4*5/4*5)

3.) So setting up two equations you get 12.49-t=17.54-2t where the t stands for the connect time. You get t $5.05

4.) 6, they'll be used 1 2 3 5 8 4 9 7 and 0 in that order.

5.) Not sure what you want there

6.) I somehow got 127 (The scores being 71, 81, 88, 88 and 127)[/hide]

Mmm it looks complicated and "official", what exactly is it? (a brief overview will do)

AMC 10

1. [hide]1+3+667=671[/hide]

2. [hide]32*(5/4)^2=50[/hide]

3. [hide]2(m+x)-(m+2x)=m=2*17.54=$7.44[/hide]

4. [hide]1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5, ans:6[/hide]

5. [hide]2-x=p => x-p=2-2p[/hide]

6. [hide]Their residues mod 4 are 3, 0, 0, 2, 3. Thus, the first 4 must have residues 3, 3, 2, 0 in some order. Thus the last one is either 76 or 80. Their residues mod 3 are 2, 1, 2, 1, 1. The first 3 must be 76, 82, 91 in some order. Thus the last one is 80. [/hide]

AMC 12

1. [hide]after squaring a couple times, x=49[/hide]

2. [hide]M is 3/50 of P while N is 1/2 P. M/N=3/25[/hide]

3. [hide]K=bh/2, b=12, h=6, K=36[/hide]

4. [hide]a is 4, 5; d is 5, 0; 6 choices for (b,c) => 24[/hide]

5. [hide]f(3)-f(-3)=6 => f(3)=8[/hide]

6. [hide]a, b, c odd or ab, c even => (3/5)^3+(2/5)*(2(3/5)(2/5)+(2/5)^2)=59/125[/hide]

MMPC

1. [hide]a. radius of larger circle is sqrt(2), R=sqrt(2)-1 b. sqrt(3)/2+D+2D=sqrt(2)*(sqrt(3)/2) => D=(sqrt(6)-sqrt(3))/6[/hide]

2. [hide]a=1/x, b=1/y => a(a+b)=a^2+ab=1/9, b(a+b)=b^2+ab=1/16 => (a+b)^2=(5/12)^2 => (a,b)=(4/15,3/20), (-4/15,-3/20) => (x,y)=(:pm:15/4,:pm:20/3)[/hide]

3. [hide]ab-a-b=7 is the largest denomination not possible. The payments :le: that which are also not possible are: 1, 2, 4, 7[/hide]

4. [hide]we need to show that if r, s, and t are the three roots of P(x)=0, rs, rt, and st are the three roots of Q(x)=0. However, this is obvious through a bit of Viete's formula (0=0, 1=1^2, -1=1(-1))[/hide]

AIME

1. [hide]using the given information, we find that is (x-p)+(15-x)+(15+p-x)=30-x. This is minimized when x is 15 giving us a minimum value of 15.[/hide]

2. [hide]we let w+z=x. Then 10+3(7x-10)=x^3 => x^3-21x+20=(x-1)(x+5)(x-4)=0. The largest value is 4[/hide]

3. [hide]all primes between 200/2 and 200/3 will be a factor of that thing. any primes bigger than 200/3 will be present twice in 200! but be subtracted once each in the 100!s so will not be present. the largest prime is thus 61[/hide]

4. [hide]7 will be added on 2^6 times. For all the others, you use the identity (1-1)^n (expand it) to see they all get canceled out so the final answer is 448.[/hide]

5. [hide]528. note that [528^(1/2)]=22, [528^(1/3)]=8, and [528^(1/6)]=2, so 528-22-8+2=500.[/hide]

6. [hide]180(r-2)/r=59/58*(180(s-2)/s) => 58(r-2)s=59(s-2)r => rs-118r+116s=0 => (r+116)(118-s)=13688. As s is a positive integer, the largest we can make s is 117, in which case r is 13572. [/hide]

7. [hide]f(n) is the number of ways in which we have no two consecutive tosses heads when we flip n coins.. We see that f(1)=2 and f(2)=3. We also see that f(n)=f(n-1)+f(n-2) because the f(n) either ends with TH in f(n-2) ways or T in f(n-1) ways. We see that f is the fibonacci numbers shifted over a couple so f(10)=144. 144/2^10=9/256[/hide]

8. [hide]n!=(n+4)!/7! => (n+4)(n+3)(n+2)(n+1)=7! => n=6. That is the only positive n as anything different will be either less than or greater than 7!. Okay. n!=(n+3)!/6! => (n+3)(n+2)(n+1)=6! => n=7 is the only positive answer by same reasoning. n!=(n+2)!/5! => (n+2)(n+1)=5! => 120 is between 110 and 132 so no positive solution. n!=(n+1)!/4! gives n+1=4! => n=23. This should be 5*...*24. Note that each of these were the cases where I try to find n! as a multiple of (n-3) consecutive integers starting at 8,7,6,and 5 respectively. The multiplication cannot start at 4 or less because then it would clearly be less than n! So i get n=23 as my greatest answer.[/hide]

9. [hide]similar triangles -> [(x+1)/x]^2=49 => x=1/6[/hide]

10. [hide]there's a pattern. these lockers are left closed after each of his sweeps: 2 mod 2, 2 mod 4, 6 mod 8, 6 mod 16, 22 mod 32, etc. the pattern is that after every other one, we either add the number and the modulus to get the new number or just keep the number the same. in any case, we double the old modulus to get the new modulus. it's pretty intuitive already. using this a couple more times gives us 342 mod 1024 left after his last sweep, which will be the one opened last (342)[/hide]

11. [hide]There should be (n+1)^2 terms, as each x and y can pair in (n+1) ways each (0 to n). So we need n to be at least 44. n=44 works because we should have 2025 terms unless some go away because the coefficient is zerobut they don't do that cause these are nice terms (i'll try to think of a better explanation soon)[/hide]

12. [hide]there will be phi(300)=80 of them. We can pair them off since gcd(a,300)=1 iff gcd(300-a,300)=1. So we have 40 pairs that sum to 300/30=10 each. 40*10=400[/hide]

13. [hide]We are given that (n+3)/(2n+4)>.503 => n<164.6666 => n=164[/hide]

14. [hide]It's a walk from the cell above the upper-right corner to the cell on the left of the lower-left corner using only down and left moves. All the cells in the walk and the cells to the left and above are removed. This can be done in C(14,6) ways = 3003[/hide]

15. ABC is a triangle. The points A', B', C' are on sides BC, CA, AB and AA', BB', CC' meet at O. Also AO/A'O + BO/B'O + CO/C'O = 92. Find (AO/A'O)(BO/B'O)(CO/C'O).

USAMO

1. [hide]We count the complement. There are 4^n ways to choose sequences that are divisible by neither 2 nor 5, 5^n ways that are not divisible by 2, and 8^n ways that are not divisible by 5. Summing with PIE, we have 8^n+5^n-4^n ways to choose digits such that their product is not a multiple of 10. Thus the answer is (9^n-8^n-5^n+4^n)/9^n[/hide]

2. A pentagon is such that each triangle formed by three adjacent vertices has area 1. Find its area, but show that there are infinitely many incongruent pentagons with this property. GAH TOUGH

3. [hide]For any two points, the angle they form between them is invariant with respect to the distance from these points and the vertex. So, for any given vertex, we can project all possible pairs of points down to the opposite face along the path from the vertex to that point. So now we have a vertex and two points on the opposite face. Oaky, it is now easy to show that this angle gets bigger as we "open it up", i.e. move the points along the line connecting them until they are on the sides of the bottom face. Now, fix the point with greater distance from a vertex, and rotate the other toward the nearest vertex. The angle gets bigger by the law of sines. Now, it is clear that this angle will again only get bigger if we "unglue" that previously fixed point and extend it to a vertex. Thus, the maximal angle occurs when the points are the base vertices, or points along the lines between the vertex and the base vertices. In any case, this angle is :pi:/3.[/hide]

4. [hide]It does not matter where the first vertex is. Now, we just take expected probability. By symmetry, we just need to worry about n of the other vertices as a possible position for the second vertex. If the second vertex is at position i (as i goes from 1 to n), there are i possible positions for the third vertex. So the final answer is i/(2n-1) (sum 1 to n) over n which turns out to = (n+1)/2(2n-1).[/hide]

5. Show that the cube roots of three distinct primes cannot be terms in an arithmetic progression (whether consecutive or not). WORK IN PROGRESS

[hide]we examine what "the cube roots are in an arithmetic progression" means. this is equivalent to saying the difference between the first two is a rational multiple of the difference between the second two. If we let a, b, and c be the cube roots of these frisky primes (note that a b and c are not rational), this means m(b-a)=n(c-b) for some integers m and n. Cubing this, we have m:^3:(b:^3:-3b:^2:a+3ba:^2:-a:^3:)=n:^3:(c:^3:-3c:^2:b+3cb:^2:-b:^3:).[/hide]

IMO1. [hide]The maximum possible sum will be less than 10*99=9900. As this is less than 2^10-1=1023, which is the number of non-empty subsets of a set with 10 elements, any set of ten numbers from that range will have two non-empty subsets with the same sum. If they are disjoint, that's great; if they're not, just take off the common elements.[/hide]

2. Prove that (2m)!(2n)! is a multiple of m!n!(m+n)! for any non-negative integers m and n. WORK IN PROGRESS [hide]if m:ge:n, that is a multiple of C(2m,m+n)

For any p, the number of times it divides the former expression is [2m/p]+[2m/p^2]+[2m/p^3]+[2m/p^4]+...+[2n/p]+[2n/p^2]+... The number of times it divides the second equation is [m/p]+[m/p^2]+[m/p^3]+[m/p^4]+...+[n/p]+[n/p^2]+... [(m+n)/p]+[(m+n)/p^2]+[(m+n)/p^3]... [/hide]

3. Given four distinct parallel planes, prove that there exists a regular tetrahedron with a vertex on each plane.

4. f and g are real-valued functions defined on the real line. For all x and y, f(x + y) + f(x - y) = 2f(x)g(y). f is not identically zero and |f(x)| ≤ 1 for all x. Prove that |g(x)| ≤ 1 for all x.

5. Determine all ordered pairs (m, n) of positive integers for which (n^3 + 1)/(mn - 1) is an integer.

6. Show that there exists a set A of positive integers with the following property: for any infinite set S of primes, there exist two positive integers m in A and n not in A, each of which is a product of k distinct elements of S for some k  2.

AIME1.[hide] since x>= p, then abs(x-p) = x-p, and since x<=15, abs(x-15) = 15 - x, and since x-p<= 15, so abs(x-p-15) = 15 - x + p.... so canceling the terms once abs are gone, you are left with 30 - x... and since x can be a most 15, the least value would be 30 - 15 = 15.[/hide]

do you mean because of the variables?  It should be find the maximum of X+Y+Z.  But i think i remember the actual question being i, m, o are positive ints with xyz=2001, find max of i+m+o, so he may have messed up in transcribing the problem, but its all the same.

1) The largest possible sum of 3 undefined variables is  :inf: . ( :inf: + :inf: + :inf: = :inf: )
5) Since x<2, x-2 is negative, therefore |x-2|=-(x-2). Substituting this in, you get -x+2=-p
2=x-p. So the answer is 2.
_______________________________________________
1) Square both sides:  2+ :sqrt: x=9
:sqrt:x=7 square
x=49
2) M=.3(.2(P)) N=.5(P)
.06P/.5P=.06/.5=.12
3)Find verticies: (0,0), (6,6), (-6,6). Base=12, height=6. 12*6/2=36.
4) First, a can be 4 or 5. d can be 0 or 5. Then, the choices for b and c are:

b=3  c=4/5/6
b=4  c=5/6
b=5  c=6
So, 6 choices for b&c. 6*4=24.
5) We find that 81a-9b+2=2. So 81a-9b=0, and 81a=9b, so 9a=b.

Sub in: 81a-81a+2=2, 0=0. All this tells us is that a and b's affects cancel out when working with -3. Since the powers that x is raised to are even, for all practical purposes 3=-3. So f(3)=2.
_____________________________________________________

1) a) So, the area of the little circle is  :pi:. The area of the big circle is then 2 :pi:. Since A= :pi: r^2, solve to find that r= :rt2:. Therefore, the diffrence in radii is  :rt2: -1.

3) 2 3's and needed 5's takes care of all x(mod 5)=1
    4  3's and needed 5's is for x(mod 5)=2
    1 3 and 5's as needed takes care of x(mod 5)=3
    3 3's and 5's as needed takes care of x(mod 5)=4
    x(mod 5)=0 takes care of itself. Find the payments of various mod residues unpayable with given cases, and this is the answer.

These are: $1, $2, $4, \& $7.
_____________________________________________________
Spent a long time writing solutions, didn't see lots of posts.

[quote="JBL"]Come on, you guys are clever enough to figure out that he messed up typing it out and switched variables half way through.  It's supposed to be the same variables throughout.  So replace X, Y, and Z with I, M and O or vice-versa.[/quote]
Indeed, it was a typo, and now it's fixed.

So 1.) [hide]Since if you want to maximize the area you make all the multicants (a vocab word ) as equal as possible so in this case you make them as different as possible so 1+3+667=671.[/hide]

14. The game of Chomp is played with a 5 x 7 board. Each player alternately takes a bite out of the board by removing a square any and any other squares above and/or to the left of it. How many possible subsets of the 5 x 7 board (including the original board and the empty set) can be obtained by a sequence of bites?

Aime 14:[hide]there is a 1-1 correspondence from the number of ways to get to the other end and the sequence, so its easy cheese then, so it twould be C(12,7)=792[/hide]

10. There is a line of lockers numbered 1 to 1024, initially all closed. A man walks down the line, opens 1, then alternately skips and opens each closed locker (so he opens 1, 3, 5, ... , 1023). At the end of the line he walks back, opens the first closed locker, then alternately skips and opens each closed locker (so he opens 1024, skips 1022 and so on). He continues to walk up and down the line until all the lockers are open. Which locker is opened last?

Aime 10:[hide]well, 342, and ill explain it later due to a concert i have to get ready for, even though ill prbly end up solving another more aime and post, heh. um, heh[/hide][/hide]

13. At the start of a weekend a player has won the fraction 0.500 of the matches he has played. After playing another four matches, three of which he wins, he has won more than the fraction 0.503 of his matches. What is the largest number of matches he could have won before the weekend?

Aime 13:[hide]164, pretty easy with algebra[/hide]

[quote="confuted"]Tare, 1 can be solved with the given information, and I'm going to Windsor, Canada, for the Canadian American Security Counsel for Model UN. If anyone's interested, http://mamunonline.com/CASC/CASC.htm has more information. If anyone is going (very unlikely), I'll be the delegate from TC West representing China.[/quote]
sweet, i live in windsor.  btw its freezing here

USAMO 2 (the thing with the pentagon). Let the pentagon be A1A2..A5. We work with indices modulo 5, which means that, for example, A7=A2, A13=A3 etc. S[XYZ] is the area of triangle XYZ.
1=S[A(i-1)AiA(i+1)].

First of all, we can see that A(i-1)A(i+2) || AiA(i+1), because
S[A(i-1)AiA(i+1)] = S[AiA(i+1)A(i+2)], and since these 2 triangles have the same base AiA(i+1), it means that their altitudes corresponding to this side are equal. It's also clear that S[A(i-2)AiA(i+2)] is the same for all i; let this area be S. The area of the pentagon is 2+S.

We draw a triangle which contains the pentagon: A1BC, s.t. A2 is on A1B, A5 is on A1C, A3 is on BC, near to B and A4 is on BC, near to C.
We have BA4/BC=BA2/BA=CA5/CA (because A2A5 || BC) = CA3/CB, so BA4=CA3, and this gives us BA3=CA4=x (notation). Let A3A4=t.

CA4/CA3 = CA5/CA1 = CA3/CB, which translates to x/(x+t) = (x+t)/(2x+t), and after the calculations we get (x+t)/x =  :phi: (the golden ratio ( :rt5: +1)/2), but (x+t)/x = CA3/CA4 = A1A3/A4A5 = S/1 = S, so the total area pf the pentagon is 2+ :phi: .

For that last part: For a pentagon P let f(P) be the maximum of its angles. It's obvious that we can project a pentagon on a plane not parallel to the plane it lies in such a way that f(P) becomes as large as we want it to be, as long as it's <180, where P is the projection of the pentagon. Now let's take a regular pentagon in space. We can project it on the plane to get infinitely many non-congruent pentagons (we could, for example, use that thing with the max angle, and always obtain a pentagon for which f(P) is larger than any of the ones I have already obtained). Since the area of the projection of a triangle is = (area of the initial triangle)*(cos(the angle between the planes), it means that we can choose the dimentions of the regular pentagon in space in such a way that its projection has that property (S[A(i-1)AiA(i+1)] is 1 for all i). The set of all the pairwisely incongruent projections I obtain (infinite set) is an example of an infinite set of such pentagons.

Hope it's clear and I hope someone will have the patience to read it...

[b]AMC 10 Scores[/b]
1 goes to Tare
2 goes to Tare
3 has not been answered correctly
4 goes to Tare
5 has not been answered correctly
6 has not been answered correctly

[b]AMC 12 Scores[/b]
1 goes to Topper
2 goes to Topper
3 goes to Topper
4 goes to Topper
5 has not been answered correctly
6 has not been answered correctly

[b]MMPC[/b]
1 has not been answered correctly according to the answer key
2 Warpedklown gets partial credit. There is another solution, but finding it is rather trivial.
3 goes to Topper
4 has not been answered correctly

[i]PM me if you see any discrepancies about what I just said. Also, solve the remaining problems so I don't feel unloved.[/i]

how bout the aime and USAMOOOOOOOOO ones?

Read the post with the contest again (it's the first one). Pay attention to the sentences [i]in italics[/i]

I graded the AIME ones for you.

[u]AIME:[/u]
1. Chinaboy (1 point)
2. Has not been answered correctly
3. Chinaboy, but his explaination is not good (1/2 point)
4. Chinaboy (1 point)
5. Chinaboy was initially wrong, Syntax Error was correct (1 point to Syntax)
6. Syntax Error (1 point)
7. Syntax Error, but could have had a better explaination (1/2 point)
8. Syntax Error, but no explaination (0 points)
9. Has not been answered correctly
10. Syntax Error, but no explaination (0 points)
11. Chinaboy, but could use a better explaination (1/2 point)
12. Syntax Error, but no explaination (0 points)
13. Syntax Error, but no explaination (0 points)
14. Syntax Error (1 point)
15. Has not been answered correctly

Total so far:
Chinaboy - 3 points
Syntax Error - 3 and 1/2 points

I'll see if I can take a look at the USAMO and IMO ones tomorrow.

ill go back and put explanations on the ones i didnt. first question to do: AIME 7

7. A fair coin is tossed 10 times. What is the chance that no two consecutive tosses are both heads.

basically, i found the recursion-like fibonacci thing of the string of HT without adjacent H's. and it went as a_1=2, a_2=3 and then a_n=a_(n-1)+a_(n-2) and you end up with 144/1024 = 9/64

[quote]11. Find the smallest positive integer n for which (xy - 3x - 7y - 21)^n has at least 1996 terms. [/quote]

to minimize n you could have 44 terms because of (n+1)^2. but then you have to prove that no terms are joined together, but that isnt so, so 44 be the answer

5. If f(x)=ax^4-bx^2+x+5 and f(-3)=2 then f(3)=?

[hide]f(-3) = -3 :^4:a - -3 :^2:b - 3 + 5 = 3 :^4:a - 3 :^2:b - 3 + 5 = 2

f(3) = 3 :^4:a - 3:^2:b + 3 + 5 = 2 + 6 = 8[/hide]

6. If a,b, and c are three (not necessarily different) numbers chosen randomly and with replacement from the set {1,2,3,4,5}, the probability that ab+c is even is ___?

[hide]Scenario 1:

ab is even

c is even

Probability that ab and c are both even: 32/125

Scenario 2:

ab is odd

c is odd

Probability that ab and c are both odd: 27/125

Total probability that ab+c is even, (32 + 27)/125 = 59/125.[/hide]

i'm assuming you mean AIME #5. but no, neal, martin and i all got [hide]528[/hide]


Prove that with each natural number $ n>1$ we can find a natural number $ z$ such that $ z$ can't express in the form $ x^n\minus{}y!$ where $ x,y$ are natural numbers.

Choose a prime $ p\equiv 1\mod n$. Then there is some generator $ g$ mod $ p$. Suppose $ g\equiv a^n\mod p$ for some $ a$. Then $ a\equal{}g^b$ for some $ b$ (because $ g$ is a generator) so

$ g\equiv g^{nb}\mod p$
$ g^{nb\minus{}1}\equiv 1\mod p$.

Then $ n|p\minus{}1$ by the assumption of $ p\equiv 1\mod n$, and $ p\minus{}1|nb\minus{}1$ since $ p\minus{}1$ is the order of $ g$. Then $ n|nb\minus{}1$ which is impossible, so $ g$ cannot be an $ n^{th}$ power $ \mod p$.

Therefore if $ g\equiv x^n\minus{}y!\mod p$ then we must have $ y<p$. Now if we choose $ x$ such that $ x^{n}\minus{}(x\minus{}1)^{n\minus{}1}$ is large enough, then we can pick an integer $ z$ such that $ z\equiv g\mod p$ and $ (x\minus{}1)^n<z<x^n\minus{}(p\minus{}1)!$. Thus $ z$ cannot be written as $ x^n\minus{}y!$ for any $ y<p$, so we are done.


Let  A = (1,3) and B(x,y)be a variable points such that $ |x|\le 2$ and $ AB\le 4$. Find the area of the region in the xy plane B can lie.

[i][b]Please try this one.

At least give some hint.[/b][/i]

Sort of outline...

[hide]Since $ AB\le4$, we can say that B lies in the region that satisfies

$ (x \minus{} 1)^2 \plus{} (y \minus{} 3)^2\le16$ and $ |x|\le2$

The rest should be more or less simple trig and calculation...[/hide]

It's a circle of radius 4 centered at $ (1,3)$ cut by the vertical lines $ x\equal{}2$ and $ x\equal{}\minus{}2$ Which isn't that hard. Just simple triangles and sectors of circles.

The answer I got is very messy. Using the methods described above, I got
[hide]$ 3\sqrt {7} \plus{} \sqrt {15} \plus{} 16\pi\left[\frac {360^\circ \minus{} 2(\arctan (\sqrt {15}) \plus{} \arctan (\sqrt {7}/3))}{360^\circ}\right]$
Can this be simplified somehow?[/hide]

Well, I wrote it as $ \boxed{3\sqrt {7} \plus{} \sqrt {15} \plus{} 16 \text{arccsc} 4 \plus{} 16 \text{arcsin} \frac {3}{4}}$, if that's any better...

Btw, I know you put in the units for the degrees, but just use $ 2 \pi$, since radians do not require units, and stuff cancels out more nicely.


if all the diagonals of a regular octagon are drawn in, how many triangles are formed?

help.

thanks.

mathcounts, no? well, if it is, when our team was doing it, we just counted and used symmetry. i think there is a cleverer approach tho: think: [hide]combinatorics[/hide]

Is the solution 112864?  I might have made some miscalcuations... Its a lot of work, so I'll wait till someone verifies my answer before I post it.

[quote="JBL"]I need to know how you're counting.  Say we have a line ABC and a point D not on the line, and we draw DA, DB, and DC.  Now, that can either give us 2 triangles (DAB and DBC) or 3 (also counting DAC, the union of the other two).   Which way do you want?[/quote]

3.

also, as far as combinatorics go, 8 choose 3 leaves out a massive number of triangles.  or u can find the # of intersections among the diagonals, then use that choose 3, but you would over-count since not all the intersections are connected to one-another.

so....

anyone??

how did u get 112864??

ummm...i doubt taht this is a mathcounts question, i doubt even more that you could have just counted to get the answer

Any you want to count triangles, not total regions?  I would generally think that looking for a pattern is the best way to go, but I didn't see anything . . . and there are way too many to go about it by hand.  Where did this question come from?

Any three of those points do not necessarily form a triangle.  For example, three of them might be collinear, or they might not be connected by diagonals.  That is, if you do this for a pentagon, the three points you choose might be all be points on the inner pentagon formed, which are not the vertices of a triangle defined by the diagonals of the pentagon.  You overcount heavily.

Well I got this number by doing some combinatorics... First, I know that if I can choose 3 points inside the polygon , I can get a triangle.  I think the way to do this is to first count the number of points inside the polygon that intersect each other...  Each diagonal crosses (n-2) or 6 lines.  Next, we count how many diagonals there are... (n(n-3)/2) or 20 lines.  20 lines * 6 crosses per line = 120 points inside the octagon.  Because this is an even sided polygon, we should subtract 3 of the diagonals because 4 go through the center.... Take it from here.

Is my thinking right?

P.S.  My other answer is wrong I think...

Ragingg -- do you have any way of dealing with the difficulties I pointed out?

Sure...  For the diagonal one, what you do is you take C(6,3)*20 because for each line, there is 6 points on it.  Subtract that from one of your numbers to get another step.

Hmm... On a second thought, I need to find a way I can weed out the ones that aren't connected by diagonals...

[quote="MysticTerminator"]may i ask what is wrong with this reasoning? we find all the intersection points of the diagonals. That should be C(8.4), as any 4 distinct points determines an intersection point. Now, we take that (plus all the vertices) choose 3 to get all the triangles. So, I get C(C(8,4)+8,3).[/quote]

8 choose 4 overcounts.  for one, multiple diagonals (four of them)pass through the center point, 8 choose 4 counts that point twice, thus the reasoning is already wrong, plus, like i said before, not all points of intersection in the octagon will be connected, so (total points) choose 3 is not necessarily the number of triangles...

JBL-  it's a question i got from a class. (not like a regular class, more like an enrichment prob. solving class)

Have you tried to find a pattern?  It should probably be a polynomial.  Look at triangles, squares, pentagons, and hexagons.  See if you can make a meaningful sequence of them.  (I couldn't, but this is just a thought.)  The odd ones may follow a different pattern than the even ones, though.


I really like this problem.

Let ABCD be a square and ABM an equilateral triangle with M outside ABCD and BNC with angle N=90 degrees, N is outside ABCD.

Prove that AM, BD and CN are concurent (have one common point) if and only if M, B and N are on the same line.

[hide="solution"]The $\Rightarrow$ implication is simple angle chasing.

For the $\Leftarrow$: clearly $N$ belongs to the circle with diameter $BC$. Let $P$ be the intersection of this circle with $BD$. Since $C, N, B, P$ are cyclic points, then $\measuredangle CPB = 90^{\circ}$, and so $CP$ is a diagonal of $ABCD$. Then $PD$ is the bisector of the isosceles triangle $AQC$ where $Q = AM \cap BD$. Hence $\measuredangle BQN = 15^{\circ}$ and finally $M, B, N$ are collinear.[/hide]


How many three-digit numbers are composed of three distinct digits
such that one digit is the average of the other two?

Note that for this to occur, the first and last digits must both be even, or both be odd.

Let us first take care of the case where they are even. There exist 5 even digits, but we can not use 0 for the first one - otherwise, our "three-digit number" would really be a two-digit number. So, we have $ 4 \times 5\equal{} 20$ ways for this to occur.

Now for the odd case. There are 5 odd digits, so we have $ 5 \times 5\equal{} 25$.

Therefore, the answer is $ 20 \plus{} 25 \equal{} 45$.

Observe that choosing two digits uniquely determines the third digit (the average of the two digits). Use casework.

1) Choose two different odd digits in $ \binom{5}{2}$ ways. Permute each choice in $ 3!$ ways. Total: $ 3!\binom{5}{2}$

2) Choose two different even digits in $ \binom{5}{2}$ ways. Permute each choice in $ 3!$ ways. Yet, by including the numbers that begin with zero, we have overcounted. We have $ 1$ way to select zero as the first digit, $ 4$ ways to select the second even digit, and $ 2!$ ways to arrange the last two digits (the third digit is determined by the first two). Total: $ 3!\binom{5}{2}\minus{}8$

Thus, we have $ 2*3!*\binom{5}{2}\minus{}8\equal{}\boxed{112}$ numbers.

[url=http://www.artofproblemsolving.com/Wiki/index.php/2007_AMC_12A_Problems/Problem_16]Alternative Solution[/url]

[hide]The set of the three digits of such a number can be arranged to form an increasing arithmetic sequence. There are 8 possible sequences with a common difference of 1, since the first term can be any of the digits 0 through 7. There are 6 possible sequences with a common difference of 2, 4 with a common difference of 3, and 2 with a common difference of 4. Hence there are 20 possible arithmetic sequences. Each of the 4 sets that contain 0 can be arranged to form $ 2\cdot2!\equal{}4$  different numbers, and the 16 sets that do not contain 0 can be arranged to form $ 3!\equal{}6$ different numbers. Thus there are a total of $ 4\cdot4\plus{}16\cdot6\equal{}\boxed{112}$ numbers with the required properties.[/hide]

There's one thing I don't get- why do use differences? Like how does that help averages or relate to it?

Here's a comprehensive solution:

One of the digits being the average => sum of the other two digits must be even so that the average comes out to an integer, => 2 cases: the two digits are either both even, or they're both odd. If the tens digit is the average of the other two digits, then the two cases sum to 5*4 + 4*4 = 36 possibilities (20 odd+odd, and 16 even+even since 0 is not allowed in the hundreds digit). By symmetry we get the same count if the ones digit is the average of the other two, since the restrictions are exactly the same, so that's another 36 cases. Now the last case is if the hundreds digit is the average of the last two digits: in this case any of the 10 digits including 0 are allowed. Hence there are 10 choices for the tens digit, and only 4 remaining choices having the same parity for the ones digit, which gives 40 possibilities for this case. The sum of the three cases is 36 + 36 + 40 = 112.


Anybody interested in celebrating your graduation from Mathcounts?
You all did such a terrific job at States!
You and/or your parents can PM me.

I definately am interested.

Could you pm me exactly how this would work out (there's only 3 -maybe 4- 8th grade mcounters on this forum-for ct)

i guess dan could come w/ me

-jorian

And 7th and 6th graders are invited to join too!


hi mathlinkers,
I'm sorry because I don't know the box to post my question. I'm very bad in geometry  :( I'm do some geometry problems and most of them I can't solve  :oops: When I saw the solution, I just can do this problem, nomore. I don't know how the solver can think this solution, how can they go to that..... when I see some posts of mathlinkers, they often uses lemma,.... and I don't know why they know :(. who can talk to me how to learn geometry. Next year, I have an olympiad test and I don't know how should I can do now. thanks  :)

Hi rogueknight.

I haven't seen any of the AOPS series so I don't know what the following is like:

http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?item_id=204

However, I have seen

http://www.artofproblemsolving.com/Books/AoPS_B_Item.php?item_id=6002

which has a lot of good stuff in it.

I like

http://www.amazon.com/Geometry-Revisited-Mathematical-Association-Textbooks/dp/0883856190

and "Crossing the Bridge" by Gerry Leversha (which seems excellent for someone starting out or fairly new to geometry problems); see here:

http://www.mathcomp.leeds.ac.uk/publications/list/#ancBooks

I have not seen "New Problems in Euclidean Geometry" by David Monk, see here:

http://www.mathcomp.leeds.ac.uk/publications/list/#ancBooks

but I know it has easy, moderate and hard sections.

More advanced, but starting off with some nice stuff is "Geometry, Ancient and Modern by John Silvester; see here:

http://www.amazon.co.uk/Geometry-Ancient-Modern-John-Silvester/dp/0198508255

I hope this is of some help to you.


$ a, b, c$- real positive  and
$ \frac{1}{a^{2}\plus{}1}\plus{}\frac{1}{b^{2}\plus{}1}\plus{}\frac{1}{c^{2}\plus{}1}\equal{}2$.
prove that $ ab\plus{}bc\plus{}ca\leqslant\frac{3}{2}$

hint:
$ ab \equal{} cos \alpha \ ac \equal{} cos \beta \ bc \equal{} cos \gamma$
$ \alpha \plus{} \beta \plus{} \gamma \equal{} \pi$

Just make the substitution $ a\equal{}\sqrt{\frac{x}{y\plus{}z}} , ...$ and then it is AM-GM .


The nonzero coefficients of a polynomial $ P$ with real coefficients are all replaced by their mean to form a polynomial $ Q$. Which of the following could be a graph of $ y \equal{} P(x)$ and $ y \equal{} Q(x)$ over the interval $ \minus{} 4\le x\le4$?

$ \textbf{(A)}$[img]13457[/img]

$ \textbf{(B)}$[img]13458[/img]

$ \textbf{(C)}$[img]13459[/img]

$ \textbf{(D)}$[img]13460[/img]

$ \textbf{(E)}$[img]13461[/img]

[quote="Tenoreoz"][hide]
Note that $ P(x)$ and $ Q(x)$ must intersect at $ x \equal{} 1$ since this is simply the sum of the coefficients of both polynomials, which is the same. This only happens for graph $ \boxed{B}$. [/hide][/quote]
Wow, so easy for a 25. :)
Sorry, for reviving, but the actual answer is [hide="Answer"]C[/hide] because the letters go below the graphs, not above...

No. In the actual test they match the right graphs, so $\boxed{(B)}$ is correct.


quadratics
number theory unsolved
number theory

These problems seem as if they're probably quite well known, so I apologise if I am repeating past posts, or they are open.

Given $a\in\mathbb{N}, a>1$, is it generally true that:

a) $a$ is a quadratic residue modulo $q$ for infinitely many primes $q$.
b) $a$ is a quadratic nonresidue modulo $q$ for infinitely many primes $q$.
c) $a$ is a primitive root modulo $q$ for infinitely many primes $q$.

Where appropriate, replace "infinitely many" with "one" :). I really don't know much about these problems, but I am interested if anybody knows anything.

a) and b) are easy consequences of the Quadratic Reciprocity Law and the Dirichlet theorem, but note that in b) $a$ can't be square! c) is an open problem, it's called an Artin's conjecture.

Ah thanks. I think I see how those proofs work.


determine the maximum N to satisfy (N is a positive interger and N is greater than 2) and:
  Exist N positive interger:   a(1), a(2), a(3),...., a(N) :

                a(n-1) <=  (a(n+1) - a(n))^2  <= a(n) .   (for all 2 <= n <= (N-1))

$ a_{n \minus{} 1} \le (a_{n \plus{} 1} \minus{} a_n)^2 \le a_n$
$ a_1 \le (a_3 \minus{} a_2)^2 \le a_2$ (1)
$ a_2 \le (a_4 \minus{} a_3)^2 \le a_3$ (2)
$ a_3 \le (a_5 \minus{} a_4)^2 \le a_4$ (3)
$ a_4 \le (a_6 \minus{} a_5)^2 \le a_5$ (4)

$ a_1 \le a_2$
$ a_1 \equal{} 1$ and $ a_2 \equal{} 1$ then from (1) $ a_3 \equal{} 2$ from (2) $ a_4 \equal{} 3$ then from (3) no solution for $ a_5$
$ a_1 \equal{} 1$ and $ a_2 \equal{} 2$ then from (1) $ a_3 \equal{} 3$ from (2) no solution for $ a_4$
$ a_1 \equal{} 1$ and $ a_2 \equal{} 3$ then from (1) $ a_3 \equal{} 4$ from (2) $ a_4 \equal{} 6$ then from (3) $ a_5 \equal{} 8$ then from (4) no solution for $ a_6$
$ (2,2)$ no solution for $ a_3$
$ (2,3)$ no solution for $ a_3$
$ (3,3)$ no solution for $ a_3$

furthermore here come the chains for the other cases:
$ (r,k^2)$ with $ r < \equal{} k^2$ and $ 2 < \equal{} k$
$ (r,k^2,k^2 \plus{} i)$ with $ 0 < i < \equal{} k$ then $ (r,k^2,k^2 \plus{} i,k^2 \plus{} i \plus{} k)$ then no solution for $ a_5$ because $ i \plus{} k \le 2k < 2k \plus{} 1$

$ (r,k^2 \plus{} p)$ with $ 0 < p < 2k \plus{} 1$, $ r < \equal{} k^2 \plus{} p$ and $ 2 < \equal{} k$
$ (r,k^2 \plus{} p,k^2 \plus{} p \plus{} i)$ with $ i < \equal{} k$
if $ p \plus{} i < 2k \plus{} 1$ then no solution for $ a_4$
if $ p \plus{} i \equal{} 2k \plus{} 1$ $ (r,k^2 \plus{} p,(k\plus{}1)^2 ,(k\plus{}1)^2 \plus{} k \plus{} 1)$ then no solution for $ a_5$ because $ k \plus{} 1  < 2(k\plus{}1) \plus{} 1$
if $ p \plus{} i > 2k \plus{} 1$ $ (r,k^2 \plus{} p,k^2 \plus{} p \plus{} i,k^2 \plus{} p \plus{} i \plus{} k \plus{} 1)$ then no solution for $ a_5$ because $ p \plus{} i \plus{} k \plus{} 1 < 2k \plus{} 1 \plus{} k \plus{} k \plus{} 1 < 4k \plus{} 4$

Finally $ N \equal{} 5$ with $ (1,3,4,6,8)$


I know this might seem easy for some of you, but I need to know how to figure it out.

If 7 football games are being played and there can only be one winner and one loser in each game, what is the total number of different combinations of winners.

You can use probability.

[hide]since there can only be a winner in each game, it is one in two times seven. So, it's 2^7.

If you don't understand why, please reply.[/hide]

It's in spoiler in the first one. Highlight all the text and you can see it.


geometry
geometric transformation
reflection
rotation
FTW
articles
symmetry

there are 5 equal white balls and 5 equal black balls.in how many ways can these 10 balls be ordered in a circle?

Is it 5? I just looked at smaller cases, like when you have 1 white and 1 black, and 2 white and 2 black. You get half of the total number of balls.

[hide="Solution"]Fix a white ball at the top, then $ \frac{9!}{4!5!}\equal{}\boxed{126}$ ways to order the rest around it, I think.[/hide]

@modularmarc101: try 4 white and 4 black

@grn_trtle:You're overcounting, for example, the case with 5 black in a row, then 5 white in a row, you count it 5 times in your method.

EDIT: Are we counting reflections as the same case or just rotations?

[quote="grn_trtle"][hide="Solution"]Fix a white ball at the top, then $ \frac {9!}{4!5!} \equal{} \boxed{126}$ ways to order the rest around it, I think.[/hide][/quote]

 nope. :D

[quote="hasan4444"][quote]In how many ways can these 10 balls be ordered in a circle?
[/quote]
I'm not sure about what he exactly means  :(  What is the color sort (1 white and 1 black or what?)?
Could you explain it further please?[/quote]

i´m sorry, i´m not getting what you don´t understand.we have $ 5$ equal white balls and $ 5$ equal black balls.the question is in how many different orders can all of these $ 10$ balls be ordered on a circunference (since it´s a circunference, orderings that can be obtained after rotations are considered the same).

Ok , since no one solved this one until now , i´m going to give another hint:
use congruence mod$ 10$  :wink:  .

[quote="v235711"]Here is a hint:
The answer is $ 26$. :wink:[/quote]

Hm. Seriously? I don't see how a multiple of $ 13$ jumped in there.

[quote="nikeballa96"][quote="v235711"]Here is a hint:
The answer is $ 26$. :wink:[/quote]

Hm. Seriously?[/quote]
Seriously. :)

Can someone explain the solution please?

 :whistling:  :coolspeak:  :pilot:

random smileys, I like.

^tribute to uberyoda and his pwnage of me on FTW

I'd be happy to explain the "big guns" solution, which uses [url=http://en.wikipedia.org/wiki/Burnside%27s_lemma]Burnside's Lemma[/url].  Somebody else should present a more elementary approach, but notice that factorization is really important in this problem, so finding a completely general solution is going to be hard.

If the circle has some fixed orientation, then the number we want is simply $ {10\choose 5} \equal{} 252$.  We want to divide these possibilities into equivalence classes, where two configurations are equivalent if they can be rotated into each other.

Look at $ \mathbb{Z}/10\equal{}\{\overline{0},\overline{1},\overline{2},\overline{3},\overline{4},\overline{5},\overline{6},\overline{7},\overline{8},\overline{9}\}$ under addition.  Think of it as the set of rotations of our circle.  We have 1 element of order 1, namely $ \overline{0}$, which fixes all 252 configurations, we have 1 element of order 2, namely $ \overline{5}$,  which does not fix any configurations, we have 4 elements of order 5, namely $ \overline{2}, \overline{4}, \overline{6}, \overline{8}$, which each fix exactly 2 configurations, and we have 4 elements of order 10, namely $ \overline{1}, \overline{3}, \overline{7},\overline{9}$, which do not fix any configurations.

Burnside's Lemma tells us to calculate the average number of fixed configurations across $ \mathbb{Z}/10$, giving us $ \frac{1\cdot 252 \plus{} 4\cdot 2}{10} \equal{} 26$.

In general, if $ p$ is an odd prime and we want to put $ p$ white and $ p$ black balls into a circle, there are $ \frac{{{2p}\choose p} \plus{} 2(p\minus{}1)}{2p}$ ways.

In case someone still doesn't believe me and v235711, here's the more direct answer:

[b]Clump of 5[/b] (1)

*****ooooo

[b]Clump of 4[/b] (4)

****o*oooo
****oo*ooo
****ooo*oo
****oooo*o

[b]Clump of 3[/b] (10)

***o**oooo
***o*o*ooo
***o*oo*oo
***o*ooo*o
***oo**ooo
***oo*o*oo
***oo*oo*o
***ooo**oo
***ooo*o*o
***oooo**o

[b]2 clumps of 2[/b] (6)

**o**o*ooo
**o**oo*oo
**o**ooo*o
**oo**o*oo
**oo**oo*o
**ooo**o*o

[b]1 clump of 2[/b] (4)

**o*o*o*oo
**o*o*oo*o
**o*oo*o*o
**oo*o*o*o

[b]No clumps[/b] (1)
*o*o*o*o*o

That was amazing.. I've tried to solve this by brute forcing. But if you have some time, can you explain this further..
[quote="LydianRain"]
Look at $ \mathbb{Z}/10 \equal{} \{\overline{0},\overline{1},\overline{2},\overline{3},\overline{4},\overline{5},\overline{6},\overline{7},\overline{8},\overline{9}\}$ under addition.  Think of it as the set of rotations of our circle.  We have 1 element of order 1, namely $ \overline{0}$, which fixes all 252 configurations, we have 1 element of order 2, namely $ \overline{5}$,  which does not fix any configurations, we have 4 elements of order 5, namely $ \overline{2}, \overline{4}, \overline{6}, \overline{8}$, which each fix exactly 2 configurations, and we have 4 elements of order 10, namely $ \overline{1}, \overline{3}, \overline{7},\overline{9}$, which do not fix any configurations.
[/quote]
What does 4 elements of order 5, 4 elements of order 10 mean? I couldn't understand it. :(
Thanks.

:)

[quote="darthfader"]What does 4 elements of order 5, 4 elements of order 10 mean? I couldn't understand it. :(
Thanks.
:)[/quote]
Think of these elements as rotations of the circle.  There are 10 rotations that move the balls around, including the trivial rotation. (keeping it still)

"Order" basically means, the number of times you have to do that rotation to get back where you started.  So a 180-degree rotation has order 2.  The smallest rotation, a 36-degree rotation, has order 10.

It may be easier to think about it modulo 10.  When I talk about the order of rotation $ \overline{3}$, for example, it's the smallest positive integer $ k$ such that $ 3k\equiv 1\ (\rm{mod}\ 10)$, which happens to be $ 10$.

The reason I brought up order was to find the configurations fixed by some given rotation.  If we take a configuration of balls and keep performing rotation $ \overline{3}$, for example, every ball will eventually pass through every position.  This means that if $ \overline{3}$ fixes our configuration, every ball would need to have the same color.  Similarly, $ \overline{5}$ does not fix any configurations, because it would pair up opposite vertices, giving an even number of balls of each color.

The only rotations fixing some configurations are $ \overline{0}$, the trivial rotation, which fixes everything, and the elements of order $ 5$, which fix only the two configurations with alternating white and black.

Why any of this works is another story--the Wikipedia article I linked to has the shortest proof I know of. :)

Since nobody's stepped forward with an elementary interpretation, here's mine.  We can avoid Burnside's lemma completely, or at least only use it implicitly... :)

We have $ {10\choose 5} \equal{} 252$ configurations, some of which can be rotated into each other.  Let's divide them into two categories: those which have some rotational symmetry, and those that don't.

For those that do, we can see that the rotational symmetry has to be $ \frac{360}{k}$, where $ k$ is a divisor of $ 10$.  But if $ k\equal{}10$, all the balls would be the same color, and if $ k\equal{}2$, then opposite balls would need to be the same color, leading to an even number of black balls.

So we would have $ k\equal{}5$, or alternating black and white balls.  There are $ 2$ such configurations, which can be rotated into each other, giving $ 1$ possibility.  This leaves $ 250$ configurations with no rotational symmetry, which we can divide up into groups of $ 10$ that can be rotated into each other, giving $ \frac{250}{10} \plus{} 1 \equal{} 26$ total possibilities.

Would you mind explaining Burnside's lemma in the stupidest terms possible? I've looked it up but all the technical group theoretic Wikipedia explanations are making my eyes bleed. (Or is a deep understanding of group theory really necessary to understand it?)

You do need a tiny bit of group theory, but it's not too bad.  If you had to repeat the proof when solving a problem like this, you could do something like my last post, which is very much a Burnside-type idea, but completely elementary.

Here's the general proof, I'll do my best to make it understandable.

The basic problem is that you have some big set of configurations $ C$, and some set of symmetries $ G$, and you want to figure out how many equivalences $ E$ there are, taking into account symmetry. (I called equivalences "possibilities" earlier, but this is probably a better term)

Consider the set $ S\equal{}\{(g,x), g\in G, x\in C | g(x) \equal{} x \}$.  In other words, the set of ordered pairs of symmetries and configurations, such that the configuration is invariant under that symmetry.  Our goal is to count this set in two different ways.

The first way: For each $ g$, we have a number of elements in $ S$ equal to the number of configurations fixed by $ g$.  So $ |S|$ is just the total sum of all fixed points across $ G$.  If $ A$ is the average number of fixed configurations over $ G$, this gives us $ |S| \equal{} |G| A$.

The second way: Consider a single equivalence $ y$, and write $ \overline{x}\equal{}y$ if the configuration $ x$ belongs to the equivalence $ y$.  Then let $ S_y \equal{} \{(g,x), g\in G, \overline{x}\equal{}y | g(x) \equal{} x \}$.  Let $ G_x$ be the set of $ g$ fixing $ x$--notice that $ G_x$ is the same size for all $ x$ with $ \overline{x}\equal{}y$. (that's one part where you would normally use group theory, but it's also not hard to see intuitively)  So, picking some $ x$, we find that $ |S_y| \equal{} |y| |G_x|$.

Now, let $ F_{x'}$ be the set of $ G$ sending $ x$ to $ x'$: $ F_{x'} \equal{} \{g\in G | g(x) \equal{} x'\}$.  Clearly $ |G|$ is the sum of the $ |F_{x'}|$ for all $ x'$ with $ \overline{x'} \equal{} y$.  But each $ F_{x'}$ is the same size, (again, you can use a little group theory or see this intuitively) namely $ |F_x| \equal{} |G_x|$, so we find that $ |S_y| \equal{} |y| |G_x| \equal{} |G|$.  Since we picked just one equivalence, it follows that $ |S| \equal{} |G| |E|$.

And we conclude that $ |G| |E| \equal{} |G|A$, or $ |E| \equal{} A$, which is Burnside's lemma.

It's a shame - problems like this get asked a lot at the Mathcounts and HSB level and the best way of understanding them (group actions) requires concepts that are simple once you understand them but that are intimidating.  I think what's necessary is a totally "visual" demonstration of the orbit-stabilizer theorem and Burnside's theorem - they're very intuitive, just phrased in difficult language.

[quote="LydianRain"]In general, if $ p$ is an odd prime and we want to put $ p$ white and $ p$ black balls into a circle, there are $ \frac {{{2p}\choose p} \plus{} 2(p \minus{} 1)}{2p}$ ways.[/quote]
Hey!  Combinatorial proof that $ {2p \choose p} \equiv 2 \bmod p$!

[quote="t0rajir0u"]It's a shame - problems like this get asked a lot at the Mathcounts and HSB level and the best way of understanding them (group actions) requires concepts that are simple once you understand them but that are intimidating.  I think what's necessary is a totally "visual" demonstration of the orbit-stabilizer theorem and Burnside's theorem - they're very intuitive, just phrased in difficult language.  [/quote]
This is a very good point.  I think it's going to be hard to find a purely visual proof for the general form of Burnside, as you really do need the group structure, but...

The more I'm thinking about it, the more it seems that Burnside for cyclic groups is very simple.  My elementary proof above uses this idea--it's much easier to talk about the symmetry type in this case, and I think it should be possible to give a visual proof.  The basic idea is that we'd like to group configurations in bunches of 10, but that we have to be careful to notice when symmetries make these bunches smaller than they should be.


linear algebra
matrix
geometry
rectangle
algorithm
logarithms

Given a N by N matrix of numbers in [-127,127] (1<=N<=8000). Find the maximum sum of a submatix of the given one. Submatrix is any rectangle which is in our matrix.

for example:
-3 1
1 4

the max sum is 5

This problem can probably be solved in efficient way using DP, but can someone tell me the idea of the algorithm?

1) DP = Dynamic Programming

2) NO in this case the maximal matrix is the given one and its sum is 3

   submatrix is any rectangle that our matrix contains.

[quote="fedja"]Two stupid questions:

1) What is DP?

2) If the matrix is
$\begin{matrix}
1 & 0 & 1 \\
0 & -1 & 0  \\
1 & 0 & 1
\end{matrix}$
can we choose
1 1
1 1
as a submatrix (taking the first and the third row and the first and the third column) or such submatrices are not taken into account when looking for the maximum?[/quote]

The best algorithm I can think of has the running time about $N^3$, which is much better than the $N^6$ of the trivial algorithm that just considers all possible rectangles and computes the sum in each rectangle in the most straightforward way, but still unacceptably long for $N=8000$ (at least for my PC, which can do about $10^6$ simple operations per second). So, the algorithm I'm going to describe doesn't solve the problem completely.

Compared to the trivial algorithm, one can make two major improvements. The first one is to replace the given matrix $(a_{ij})_{1\leq i,j\leq N}$ by the matrix of the partial sums $(S_{mn})_{0\leq m,n\leq N}$ where $S_{mn}=\sum_{i\leq m,j\leq n}a_{ij}$. This can be done in $N^2$ time replacing the row elements by row partial sums first and then doing the same operation with columns. The point is that the sum of $a_{ij}$ over a rectangle $m'< i\leq m'', n'< j\leq n''$ can be computed now as $S_{m''n''}+S_{m'n'}-S_{m''n'}-S_{m'n''}$. This improvement alone reduces the running time of the trivial algorithm from $N^6$ to $N^4$.

Now, assume that $m'$ and $m''$ are fixed (about $N^2$ possible choices) and our task is to find the best $n'$ and $n''$. Let $B_n=S_{m''n}-S_{m'n}$. We need to find $n'\leq n''$ such that $B_{n''}-B_{n'}$ is as large as possible. To this end, for every $k$, find $M_k=\max_{n\geq k}B_n$ and $\mu_k=\min_{n\leq k}B_n$. Also, record the positions where the maximum and the minimum are attained. This can be done in linear time. After that it remains to find the maximum of $M_k-\mu_k$, which can also be done in linear time. So, the total time is about $N^2\cdot N=N^3$.

Unfortunately, as I said, it is still too slow  :( . Maybe somebody comes up with a better idea.

By the way, this is not exactly calculus. Now there is a special subforum for Computer Science and Informatics. I think you have a better chance  posting such questions there, so I'm moving this thread :)

Thank you :)

These days I've been thinking a lot about this problem. Deadline is in 4 weeks. Later I will post my final program here :) , but for now any idea(optimization) is welcomed.

Well, it is very well known problem in programming. There are 2 algos for it. One N^3 and another N^4.

I think these two are already described above. But you know my exam is tomorrow so I can’t read that and try to understand. So I am brefly saying about those two algo.

N^4: you need to keep S[a][b] where it is the sum of all the position from (0,0) to (m,n). now run N^4 algo I mean select starting left up node and select down right node. And compute the sum.

N^3: it keeps track on the sum of rows. I mean S[m][n] means (m=row n=col) S[m][n]=sum(i=1 to m) S[i][n]. now select any two col. And go through the rows. If the sum becomes negative any time exclude the last row and update your maximum if necessary. Then go to next row and thus continue running. Same for minimum!

If you need the codes for this two tell me I have both of those in my computer!

I want to see the n^3 code, i cant quite understand your algorithm. :(

This should be an implementation of fedja's algorithm:

[code]
for i = 1 to N
	sum[i][0] = 0
	for j = 1 to N
		sum[i][j] = matrix[i][j] + sum[i][j - 1]
best = 0
for i = 1 to N
	for j = i to N
		max[0] = 0
		min[0] = 0
		result = 0
		for k = 1 to N
			result = result + sum[k][j] - sum[k][i]
			if result > max[k - 1] then max[k] = result else max[k] = max[k - 1]
			if result < min[k - 1] then min[k] = result else min[k] = min[k - 1]
		if max[N] - min[N] > best then best = max[N] - min[N]
return best
[/code]

I don't understand why best = MAX(max[n] - min[n], best);
I simply write a program using your algorithm, but it returns a wrong answer
This is my n^4 code:
[code]
#include <iostream>
using namespace std;

#define MAXN 102
int map[MAXN][MAXN], sum[MAXN][MAXN];
int n, maxsum;

int read()
{
	int i, j;
	if(cin >> n)
	{
		for(i=0;i<n;++i)
		{
			sum[i][0] = 0;
			sum[0][i] = 0;
		}

		maxsum = -10000;
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
		    {
			    cin >> map[i][j];
				sum[i][j] = map[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
				if(sum[i][j] > maxsum) maxsum = sum[i][j];
			}
		int x1,y1, x2,y2, curr_sum;
		for(x1=1;x1<=n;++x1)
			for(y1=1;y1<=n;++y1)
			    for(x2=x1;x2<=n;++x2)
			        for(y2=y1;y2<=n;++y2)
		            {
			            curr_sum = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
						if(curr_sum > maxsum) maxsum = curr_sum;
					}

		return 1;
	}
	else return 0;
}

int main()
{
	while(read()) printf("%d\n", maxsum);
	return 0;
}
[/code]
It's a ac code.

And this is the code using your algorithm:
[code]
#include <iostream>
using namespace std;

#define MAX(a, b) (a>b ? a : b)
#define MIN(a, b) (a>b ? b : a)
int const maxn = 102;
int map[maxn][maxn], sum[maxn][maxn];
int n;

int read()
{
	int i, j;
	if(cin >> n)
	{
		for(i=1;i<=n;++i)
		{
			sum[i][0] = 0;
			for(j=1;j<=n;++j)
		    {
			    cin >> map[i][j];
				sum[i][j] = map[i][j] + sum[i][j-1];
			}
		}
		return 1;
	}
	return 0;
}

void solve()
{
	int i, j, k, sub_row, max[maxn], min[maxn], best;
	best = 0;
	for(i=1;i<=n;++i)
	{
		for(j=i;j<=n;++j)
	    {
		    sub_row = 0;
			max[0] = 0;
			min[0] = 100000;
		    for(k=1;k<=n;++k)
			{
		        sub_row = sum[k][j] - sum[k][i];
				max[k] = MAX(max[k-1], sub_row);
				min[k] = MIN(min[k-1], sub_row);
			}
			best = MAX(max[n] - min[n], best);
		}
	}

	cout << best << endl;
	/*for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
		    cout << map[i][j] << " " << endl;*/
}

int main()
{
	while(read()) solve();
	return 0;
}
[/code]
Seems wrong.
Anyone can help me?

OK. So first I'll show you your bugs and then I'll show you my bugs :-).

min[0] = 0 and not 100000.

Also,

sub_row = sum[k][j] - sum[k][i];

is wrong, it should be

sub_row += sum[k][j] - sum[k][i];

because sum[k][j] - sum[k][i] is only a sum of a certain part of row k but in sub_row we actually want to hold a sum of a submatrix which we get by adding subrows 1 to k. Here also comes an error I made - it should actually be

sub_row += sum[k][j] - sum[k][i - 1];

and not sum[k][j] - sum[k][i] but this is of lesser importance. The worst thing is that best = MAX(max[n] - min[n], best); is also wrong; what I should have done is this:

for(k=1;k<=n;++k) {
 sub_row = sum[k][j] - sum[k][i];
 max[k] = sub_row; <-- this is different
 min[k] = MIN(min[k-1], sub_row);
 best = MAX (max[k] - min[k], best); <-- and this is also a little different because you do it n times and not only once
}

So this is the whole code with corrected mistakes (hopefully all of them):

[code]for (int i = 1; i <= n; i ++) {
	for (int j = 1; j <= n; j ++) {
		sub_matrix = 0;
		min = 0;
		for (k = 1; k <= n; k ++) {
			sub_matrix += sum[k][j] - sum[k][i - 1];
			min = MIN (min, sub_matrix);
			best = MAX (sub_matrix - min, best);
		}
	}
}[/code]
I'm sorry for all the confusion I've created :). And by the way, what this code does is that it calculates sums of submatrices with columns i to j and rows 1 to k and then it substracts the one with the smallest sum from the one with the greatest sum and the difference is a sum of submatrix with rows from k1 to k2. (k1 - 1, k2 are the ending rows of the two submatrices we've substracted.)

There still something wrong in your algorithm i think.
See my code, Maybe I could express my idea better by codes.

[code]
#include <iostream>
#include <stdlib.h>
using namespace std;

#define MAX(a, b) (a>b ? a : b)
#define MIN(a, b) (a>b ? b : a)
#define INFINITY 100000
int const maxn = 102;
int map[maxn][maxn], sum[maxn][maxn];
int n;

int read()
{
	int i, j;
	if(cin >> n)
	{
		for(i=1;i<=n;++i)
		{
			sum[i][0] = 0;
			for(j=1;j<=n;++j)
		    {
			    cin >> map[i][j];
				sum[i][j] = map[i][j] + sum[i][j-1];
			}
		}
		return 1;
	}
	return 0;
}

void solve()
{
	int i, j, k, sub_row[n+1], best;
	best = -INFINITY;
	for(i=1;i<=n;++i)
	{
		for(j=i;j<=n;++j)
	    {
			//memset(sub_row, 0, sizeof(sub_row));
			for(k=0;k<n+1;++k)sub_row[k]=0;
		    for(k=1;k<=n;++k)
			{
		        sub_row[k] = sum[k][j] - sum[k][i-1];
				if(sub_row[k-1] < 0) sub_row[k-1] = 0;
				sub_row[k] += sub_row[k-1];
				best = MAX(sub_row[k], best);
			}
		}
	}

	cout << best << endl;
	/*for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
		    cout << map[i][j] << " " << endl;*/
}

int main()
{
	while(read()) solve();
	return 0;
}

[/code]

First I calculate the sum of all the left sum of a row, then calculate all the sum of any i to j columns, the accumulate to a sub matrix, meanwhile, update maxsum.

Don't hesitate to say your view.

Hm.... this could work too. And what do you think is wrong about my code?

I can not tell your problem too, but I just feel something wrong.
Maybe something I'll think it out :(

Hi
         I think it should be below.

for (int i = 1; i <= n; i ++) {
   for (int j = [b]i[/b]; j <= n; j ++) {     // ---just modify 1 to i
      sub_matrix = 0;
      min = 0;
      for (k = 1; k <= n; k ++) {
         sub_matrix += sum[k][j] - sum[k][i - 1];
         min = MIN (min, sub_matrix);
         best = MAX (sub_matrix - min, best);
      }
   }
}

I found the problem.... If all value of original matrix < 0, The answer will be 0.
thanks anyway for your code.  :D

[quote="BabyThief"]I found the problem.... If all value of original matrix < 0, The answer will be 0.[/quote]
To fix this, initialize the maximum to one of the elements of the set instead of 0 at first.

Also, reviving old threads (especially ones [i]this[/i] old) is frowned upon.

[quote="BabyThief"]If all value of original matrix < 0, The answer will be 0.[/quote]  This is not a problem if the empty matrix counts as a matrix.  This is just definitional.

There is an algorithm by Takaoka with a slightly better asymptotic performance, $ \sim n^3\sqrt{{\log \log n}\left/{\log n}\right.}$. But probably the standard $ O(n^3)$ algorithm is more practical.

fedja, modern PCs should perform much more than $ 10^6$ operations per second, roughly $ 10^9$ operations per second.

[quote="Yury"]
fedja, modern PCs should perform much more than $ 10^6$ operations per second, roughly $ 10^9$ operations per second.[/quote]
Perhaps that's what the advertisements say, but I tried to write a simple C++ program like

void main(void)
{
real a=30,b=40, c;
int N=30000;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
c=a*b;
}

and didn't have enough patience to see it finish either on my home PC, or on my office computer (my patience usually lasts up to 5 minutes). So, sorry, the truth is between $ 10^6$ and $ 10^7$  (which quite agrees with the usual exaggeration factor in the computer PR industry; the file transfer speed is another good example of how what we are promised differs from what we see by a factor of about 100). This is still very impressive, of course, but not good enough for running the $ O(N^3)$ algorithms with $ N\equal{}8,000$ :P.

fedja, you are mistaken, Yury's estimate is much closer to the reality. Nowadays, 10^9 instructions per second is indeed a good estimate of a processor's running speed. (Keep in mind that 10^9 instructions can be something like 10^8 simple algorithmic steps.

As for the code you claim to use for benchmarking, I fixed it slightly (so that the cycle doesn't get optimized away completely) and below is how it ran on my ordinary notebook:

[code]
[misof@permonik]:~/SANDBOX$ cat speed.cc

#include <cstdio>
using namespace std;
int main(void) {
  double a=30, b=40, c=0;
  int N=30000;
  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
      c+=a*b;
  printf("%g\n",c);
}

[misof@permonik]:~/SANDBOX$ g++ -O2 speed.cc -o speed.cc.bin
[misof@permonik]:~/SANDBOX$ time ./speed.cc.bin
1.08e+12

real    0m1.787s
user    0m1.751s
sys     0m0.010s
[/code]

In words, the N^2 floating point multiplications and additions finished in under 2 seconds for N=30,000.

I got the same numbers as misof did. Even when I disabled optimization, the running time was still reasonable ~4 seconds (I tried both GNU C++ and Visual C++).   :roll:

According to Fedja's algorithm and Bus' implementation, how can i determine the elements of the submatrix, i mean the top-left and the bottom-right corners?
Thanks in advance.


logarithms
limit
ratio
real analysis
real analysis unsolved

Can i use Dirichlet for 1/n and 1/a_n ????
[]´s

would u please tell me how u find out that the $a_n$ is equvalient To$(2006n)^{1/2006}$ and what follows from it? :(

To solve the problem it is sufficient to prove that $a_n>n^\alpha,\forall n>N$.

Assume the contrary. For any $\epsilon$ there exists $N(\epsilon)$ such that $a_n\le n^\epsilon, \forall n>N(\epsilon)$ which means that $\frac{\ln a_n}{\ln n} \to 0.$ Aplying Cesaro-Stolz theorem we get:

\[ 0=\lim \frac{\ln a_n}{\ln n}=\lim \frac{n \ln(\frac{a_{n+1}} {a_n})} {\ln (1+\frac 1 n)^n}=\lim n\ln (1+\frac 1 {a_n^{2006}})=\lim \frac n {a_n^{2006}}> \lim \frac n {(n^{\frac 1 {3000}})^{2006}}=\infty \]

Contradiction.

Hey! I am freshman, xirti why u claim that it is sufficient to prove $a_n>n^\epsilon,\forall n>N$?

If $a_n \ge n^\alpha$ then the series converges by comparision with $\sum_{n=N}^\infty \frac{1}{n^{\alpha+1}}$.

We can generalise the problem $ a_{n+1}= a_n+\frac{1}{{a_n}^{\alpha}} $ with ${\alpha}> 0$.

$lim  a_{n}$ must exist because the sequence is increasing.

remark that $ a_{n}\to\infty $,let $b_{n}=a_{n}^{\alpha+1}$ then:

                                               $ b_{n+1}=b_{n}(1+\frac{1}{{b_n}})^{\alpha+1}$

                                               $ b_{n+1}=b_{n}(1+\frac{{\alpha+1}}{{b_n}}+o(\frac{1}{{b_n}}))$

 by Cesaro's lemma:                           $ b_n\sim\ ({\alpha+1})n$

and                                              ${\frac{1}{n a_{n}} \sim\ \frac{1}{{C}n^\frac{\alpha+2}{\alpha+1}}}$

with ${{C}=({\alpha+1})^\frac{1}{\alpha+1}}$,so the serie converges by comparison with Riemann series!

Check out problem V3-4 of March issue of Asymmetry [url=http://akotronismaths.blogspot.gr/p/asymmetry-electronic-mathematical.html]here[/url].

Why is this not trivialized by the ratio test? $\frac{\frac{1}{(n+1)a_{n+1}}}{\frac{1}{na_n}} = \frac{na_n}{(n+1)a_{n+1}} < \frac{a_n}{a_{n+1}} = \frac{1}{1+\frac{1}{a_n^{2006}}} < 1$.

edit: TY Kent, idk what came over me, looking back, this is obviously false XP.

Because that's not what the ratio test says. To use the ratio test, you must take the limit as $n\to\infty$ of that ratio, and since $a_n\to\infty,$ the limit of the ratio is $1$ and the test is inconclusive.

Look at what everyone else is saying on this thread about estimating how fast $a_n$ grows. They're estimating it as something like $n^s$ for some fixed power $s.$ Which is not geometrically fast, which means that the ratio test was always a waste of time.


limit
geometry
3D geometry
sphere
number theory unsolved
number theory

let $ r(n) \equal{} \#\{(x,y,z,t)\in Z^4: x^2 \plus{} y^2 \plus{} z^2 \plus{} t^2 \equal{} n\}$, it is known that
\[ r(n) \equal{} \sum_{m|n\land 4\nmid m}m\]
und let $ R(N) \equal{} \sum_{n \equal{} 1}^Nr(n)$

find  $ \lim_{N\to\infty}\frac {R(N)}{N^2}$

$ R(N) \equal{} \#\{(x,y,z,t)\in Z^4: x^2 \plus{} y^2 \plus{} z^2 \plus{} t^2 \le N\}$

$ R(N) \equal{} V_4(\sqrt {N}) \plus{} O(N^\frac {3}{2})$ where $ V_4(r) \equal{} \frac {1}{2}\pi^2r^4$ is the volume of a sphere in 4-dimensions of radius $ r$.

$ \frac {R(N)}{N^2} \equal{} \frac {1}{2}\pi^2 \plus{} O(N^{ \minus{} \frac {1}{2}})$

[quote="jens18"][quote="PhilG"]
$ R(N) \equal{} V_4(\sqrt {N}) \plus{} O(N^\frac {3}{2})$ [/quote]
could you justify this equality?
Thanks in advance![/quote]

$ R(N)$ is the combined volume of all the unit cubes centred on points $ (x,y,z,t)$ that fall inside a sphere of radius $ \sqrt{N}$

You just have to show that a slightly smaller sphere of radius $ \sqrt{N} \minus{} C$ is inside all the cubes for some constant $ C$
and that a slightly larger sphere of radius $ \sqrt{N} \plus{} C$ contains all the cubes.
This gives you upper and lower bounds for the sum which imply $ R(N) \equal{} V_4(\sqrt {N}) \plus{} O(N^\frac {3}{2})$


A true account of an ill-fated travel agent who had to deal with the current gov's stupidity

Subject: Why our government may be in trouble

I vote for teaching Geography again and having all candidates recite the alphabet!!!

Subject: Why our Gov't may be in trouble

I have been a Travel Agent for thirty years in Washington, D.C. Here are examples why we might just be in trouble!

I had a New Hampshire Congresswoman ask for an aisle seat so that her hair wouldn't get messed up by being near the window.

I got a call from a candidate's staffer, who wanted to go to Cape Town.  I started to explain the length of the flight and the passport information, then she interrupted me with, "I'm not trying to make you

look stupid, but Cape Town is in Massachusetts." Without trying to make her look like the stupid one, I calmly explained, "Cape Cod is in Massachusetts, Cape Town is in Africa." Her response (click).

A senior Vermont Congressman called, furious about a Florida package we did.  I asked what was wrong with the vacation in Orlando. He said he was expecting an ocean-view room. I tried to explain that is not possible, since Orlando is in the middle of the state. He replied, "Don't lie to me.  I looked on the map, and Florida is a very thin state!"

I got a call from a lawmaker's wife who asked, "Is it possible to see England from Canada?"  I said, "No." She said, "But they look so close on the map."

An aide for a Bush cabinet member once called and asked if he could rent a car in Dallas. When I pulled up the reservation, I noticed he had only a 1-hour layover in Dallas. When I asked him why he wanted to rent a car, he said, "I heard Dallas was a big airport, and we will need a car to drive between the gates to save time."

An Illinois Congresswoman called last week. She needed to know how it was possible that her flight from Detroit left at 8:20 a.m. and got into Chicago at 8:33am. . I tried to explain that Michigan was an hour ahead of Illinois, but she could not understand the concept of time zones.  Finally, I told her the plane went very fast, and she bought that!

A New York lawmaker called and asked, "Do airlines put your physical description on luggage tags? I said, "No, why do you ask?" She replied, "Well, when I checked in with the airline, they put a tag on my luggage that said (FAT), and I'm overweight. I think that is very rude?" After putting her on hold for a minute while I 'looked into it' (I was actually laughing) I came back and explained the city code for Fresno, CA is (FAT), and that the airline was just putting a destination tag on her luggage.

A Senator's aide called to inquire about a trip package to Hawaii. After going over all the cost info, she asked, "Would it be cheaper to fly to

California and then take the train to Hawaii?"

I just got off the phone with a freshman Congressman who asked, "How do I know which plane to get on?" I asked him what exactly he meant, to which he replied, "I was told my flight number is 823, but none of these darn planes have numbers on them."

A lady Senator called and said, "I need to fly to Pepsi-Cola , FL. Do I have to get on one of those little computer planes?" I asked if she meant fly to Pensacola,FL on a commuter plane. She said, "Yeah, whatever!"

A senior Senator called and had a question about the documents he needed in order to fly to China. After a lengthy discussion about passports, I reminded him that he needed a visa. "Oh, no I don't. I've been to China many times and never had to have one of those." I double checked and sure enough, his stay required a visa. When I told him this he said,"Look, I've been to China four times and every time they have accepted

my American Express!"

Now you know why Government is in the shape that it's in.

Try this link to Snopes.com for the truth: http://www.snopes.com/travel/trap/congress.htm


Guess and check: 3 and 11.

Now how do you really solve it?

Mod 11, I think, does it.

EDIT: Wait, that doesn't tell us much.  Nevermind.


geometry
3D geometry
sphere
prism
integration
Gauss
geometry unsolved

Hello all,

I have a problem at work that I need to solve. It involves the volume of intersection of a sphere and a rectangular prism. The only restrictions is that the sphere have radius smaller than or equal to the largest linear dimension of the prism, and that the centre of the sphere is always inside the cube. I need to find the volume of there sphere that lies within the prism for every possible case.

For the following:
let a = the distance between the centre of the sphere and the edge of the prism in the x direction
let b = the distance between the centre of the sphere and the edge of the prism in the y direction
let c = the distance between the centre of the sphere and the edge of the prism in the z direction

Case I: Sphere is completely contained by the cube.
Solution: V = (4/3)*pi*r^3

Case II: Sphere intersects with only one face of the prism
Solution: V = (4/3)*pi*r^3 - pi * integral(r^2-x^2)dx from a (or b or c) to r OR V = pi * integral(r^2-x^2)dx from -a (or -b or -c) to r.

Case III: Sphere intersects with two faces of the prism
Solution: No idea, any help would be appreciated

Case IV: Sphere intersects with all three faces of the prism
Solution: Help? :P

Also, did I miss any cases?

OK, I hope I got it right.

First of all, you can consider 8 octants separately. I'll also assume that the sphere is centered at the origin and has radius $ 1$ (I leave trivial scaling and shifts for you to take care of). Thus, we need to find the volume of the set where $ 0\le x\le a,0\le y\le b,0\le z\le c,x^2\plus{}y^2\plus{}z^2\le 1$ with some positive $ a,b,c$.

If $ a^2\plus{}b^2\plus{}c^2\le 1$, then the answer is $ abc$.

Otherwise, it is $ \frac\pi 6\minus{}V_a\minus{}V_b\minus{}V_c\plus{}V_{ab}\plus{}V_{bc}\plus{}V_{ac}$ where

$ \frac \pi 6$ is the volume of the unit spherical octant.

$ V_a\equal{}0$ if $ a\ge 1$, otherwise
$ V_a\equal{}\frac\pi 4\int_a^1(1\minus{}t^2)\,dt\equal{}\frac\pi 4\cdot \frac{2\plus{}a^3\minus{}3a}3$ is the volume of the spherical cap $ x>a,y,z>0,x^2\plus{}y^2\plus{}z^2\le 1$ ($ V_b$ and $ V_c$ are defined similarly).

$ V_{ab}\equal{}0$ if $ a^2\plus{}b^2\ge 1$, otherwise
$ V_{ab}\equal{}\frac 13\left\{
\text{arccos\,}\frac{ab}{\sqrt{1\minus{}a^2}\sqrt{1\minus{}b^2}}\minus{}
\frac{3b\minus{}b^3}{2}\text{arccos\,}\frac{a}{\sqrt{1\minus{}b^2}}
\minus{}\frac{3a\minus{}a^3}{2}\text{arccos\,}\frac{b}{\sqrt{1\minus{}a^2}}
\plus{}ab\sqrt{1\minus{}a^2\minus{}b^2}
\right\}$ is the volume of the spherical segment $ x>a,y>b,z>0,x^2\plus{}y^2\plus{}z^2\le 1$ ($ V_{bc}$ and $ V_{ac}$ are defined similarly).

The formula expressing the volume in terms of $ V$'s is just the standard inclusion-exclusion principle. The computation of $ V_a$ should be clear. The computation of $ V_{ab}$ is rather unpleasant and I would like somebody to check the formula independently, so I am not posting its proof now (I did it using Gauss-Bonnet).

Feel free to ask as many questions as you need :).

Sorry to bring up an old topic, but I missed this post - gave up on anyone answering. This was for a computer code, so I actually ended up just redoing the code so that the sphere would never intersect more than one face. With this, I might be able to do better. On the offchance that you still have the details of the computation, do you think you could walk me through your derivation? :)


calculus
integration
function
ratio
real analysis
absolute value
calculus computations

Can any of you tell the result when zero times infinity?
zero and infinity are both ideal values. We can neither obtain a quantity of absolute zero in actual life nor a quantity of infinity. Can we proof this? How?
Thank you.

[quote="jmerry"]In most contexts, like the calculus one you're probably thinking of, the answer is "not a number".

In measure theory, it's zero; a union of infinitely many (countably infinite) sets of measure zero has measure zero, and the integral of the constant function $ \infty$ on a set of measure zero is zero.

This sort of thing has no intrinsic answer; it's just a question of what convention you want to put in the definitions.[/quote]

I appreciate that you have made this answer so quickly.
But I doubt if a chick said that the egg which it was hatched was laid by itself?
proofs with calculus and "measure theory" are on analogy of chick?

Evaluate
lim (cos x)(tan x)  = 1 ?
x-> pi/2

why not 2 or other numbers?
then what is the difference between 2 and 1? and so on?
I doubt if we declared zero and infinite, then there is no difference between 2 and 1?
things are not discrete and uncountable if there exist zero and infinity in mathematics.

That is a completely different question. That is not $ 0\cdot \infty$; it's a limit, and an easy one.

From your other responses, I'll tweak my answer: $ 0\cdot\infty$ is [url=http://en.wikipedia.org/wiki/NaN]not a number[/url].
That's the most common and most useful definition.

Etiquette note: Never quote the entire post immediately preceding yours. You're assumed to be replying to it, so there's no good reason.

Thanks for the link to the NaN (may be due to the limitations of computing machines)
frankly I am no good in maths.
I used to be confused by 0 and infinity as they are widely used in calculus. i.e. lim and integration

if infinity is not a number?
or there is something still remains undeclared?

I learned about NaN from the original author of the standard. It's there because it's better than breaking programs with a generic error, and it's a useful concept in general.

How do we look at numbers? Start with the natural numbers; everyone agrees there. We like to subtract, so put the rest of the integers in. Division is nice, and that gets us the field of rationals. Limits are nice, and filling in the holes gets us the real numbers, which are still a field.

$ \infty$ is not one of these numbers. It comes in when we think about dividing by zero, or considering a limit of things that get big. It's not worth considering it as a number because it breaks the field properties. On the other hand, we can still do some computations with it- $ \infty\plus{}1\equal{}\infty$, for example. Even in this extended world, some things like $ \infty\cdot 0$ and $ \infty\minus{}\infty$ don't work. Not a Number is a good name for this, but it's fundamentally all just semi-arbitrary conventions.

Now, in the calculus world, you're not really looking at $ \infty\cdot 0$; you actually have "something that goes to $ \infty$" times "something that goes to zero". Depending on the details, that could be anything, nd we call it an indeterminate form.

when evaluating the following

lim (cos x)(tanx)
x->pi/2

nothing appear to be in indeterminate form.

let us make it simple:

lim (cos x)(tanx)   may be equal to
x->pi/2

lim (cos x)(sin x / cosx)
x->pi/2

subs x-> pi/2 into (cos x) results in 0
subs x-> pi/2 into (sin x / cos x) result in 1/0 which is a real number with infinity big

both of them are not indeterminate...maybe I am wrong?

when I go back to the numbers again...
I doubt if the biggest number on the world is integer 1 (the unity) which could be the absolute value of -1 or +1? All valid real numbers x is represented by
0< |x| <= 1?
the existence of infinity is due to continuous magnification of the upper limit (1)? by human factor.
and the existence of bigger integers such as 2 is due to the magnification of any real number between 0 and 1 to a certain ratio (k-which is not a number at this time. it maybe some kind of relativity).  all numbers |y| bigger than 1 may be one of the abstracts to |x| on different level of view relative to 0. So I guess this could be the reason that we could never reveal the value of so called infinity. But if we cross infinity with zero (which is thought by me to eliminate the magnification) we get 1 (which is the ultimate number in the world).
0 is simply an imaginary pivot (if both -1 and +1 coexist) between -1 and +1, otherwise it may be an arbitrary end of the real numbers. (Maybe I am crazy this time?)

I gotta state that, I am not a maths graduate and nothing above has been proofed.
If I am wrong/thought to be stupid.  Please accept my excuse that I am no good in maths.
That's why keep asking :P

And forget to tell you that, umm...

I am a Chinese guy in Hong Kong with limited education and quite poor in English.
Don't blame me if my post is filled with mistakes.


Find the smallest triangle(in area) which can cover completely any triangle whose sides are less than unity.

If you have seen the prob and its solution earlier please dont post it...
I want to know how many people get it deductively rather than guessing the correct triangle and proving it is the one...

Did you actually deduce that? :huh:
If so, would you mind posting it? :)

i have been able to show that an equilateral triangle of  altitude 1 or area 3^(-1/2) satisfies i dont know whether it is the smallest :?:  :maybe:

this is infact the smallest
consider triangles with 2 sides =1 and angle be6tween them less than 60 :D

Your answers are wrong...

It is actually a quite unsymmetrical triangle
(neither equilateral nor isosceles , nor does it have cool angles like,30,45,90 or for that matter 15,75,etc..)

I guess I have already given a small hint above...

:blush: sorry i get that my connjencture is wrong could you please post the soln to this it is eating my head? :D

[quote="SOUMYASHANT NAYAK"]ANS:

It is a triangle ABC:
<BAC = 60
AC=1
Altitude to AC = cos 10....

Now prove the result...[/quote]
Altitude to AC = cos 10....
what does ... stand for after cos 10 :?:   :(


A (hasty) try for n1 :

By induction a(n) < 1/n:sqrt:n  a1

Now int (dt/t:sqrt:t, t=1..+oo) = 1

Hence sum a(i) < 2 a1 = 1.

An elementary proof maybe ? (Hint : telescope)

Telescope how? I'm trying but I can't see a pattern in the terms I'm telescoping.

Nice problem (I mean 1):

[hide]We write the recurrence like this: 2ka_k=(2k-2)a_(k-1)-a_(k-1) or a_(k-1)=2(k-1)a_(k-1)-2ka_k. It's easy to see the telescoping sum now. In the end we get a_1+..+a_n = 2a_1-2(n+1)a_(n+1)=1-2(n+1)a_(n+1). I don't think it's too hard from here.[/hide]


AMC
USA(J)MO
USAMO
AIME
calculus
geometry
analytic geometry

How does one go about improving his or her skill on the USAMO? I've been doing the old tests off of Kalva, and I haven't managed to fully complete a single problem yet. So no, I really can't wait until Friday to start.

I'm experiencing the same problem but I'm not taking the USAMO at all since I can't even solve an AIME problem....

any help would be greatly appreciated...

I have the same problem, and I really wish I had someone to tell me if I was on the right path without giving me any hints or peeks at the solutions.

Knowing if you're on the right path ruins the fun.  It's best not to know.  It's more fun when you reach the end then, because your crazy ideas end up working out.

I've seen USAMO problems before. After looking at some of the solutions, all you really have to do is experimenting and fooling around with ideas.
(That's how I solved 2 USAMO problems)

It might help to start with some easier and less time-consuming, but also olympiad-type problems. Take a look at our Canadian MO, for example.

Just think about it for a while. All the recent USAMO problems ive solved (which barely breaks into double digits) Ive solved just thinking about it at night when I was trying to sleep.

You're right that different routes lead to the same end -- but this is true in AMC and AIME as well as USAMO.  If you write a correct proof, your train of logic will lead straighforwardly to the desired result.  I do agree with you that judging the "goodness" of proofs is difficult.  It's something that comes largely with practice.

[quote="mathnovice"]If USAMO is completely proof based, then isn't there going to be more than one possible answer or proof? I've looked at some past USAMO questions and their solutions, and I cannot even conceive of how someone could solve something like that nevermind come up with the official solution. Is it likely that when you do a USAMO proof that yours matches up exactly or even close to the official answer? If not, how can you be sure that yours is correct? For numericals, this isn't a problem because all methods lead to one correct solution, but, for proofs, you can have "good" proofs and "bad" proofs. How do you know that yours is of the former category? Isn't it difficult to assess when it is not likely that you will write something similar to the official solution?[/quote]

I believe that, even if your answer isn't similar to (one of) the official solution(s), you can still get full credit if your method works (and it uses only precalculus methods.)

From what I've read in Count Down, that's the way it works at IMO, and I have no reason to think it should be different for USAMO.

[quote="Magnara"][quote="Fermatprime"]
(and it uses only precalculus methods.)[/quote]

All they say is it can be solved with precalculus methods, not that it must be ;-)[/quote]

But it should be added that a particularly sloppy solution, such as a few pages of calculus, or pages of algebra from doing a geometry problem with coordinates (where coordinates <i>don't</i> simplify the problem), won't please the graders and they will probably be a lot more strict with your score.

It's not too important to me, cause I'm not taking the USAMO, but how much work is one expected to show?  Can you just say something reduces to something else after factoring, canceling, and other basic algebraic operations, or should you show each step of these steps?

As far as I know, you should show all nontrivial steps in algebra.

There is a Math Jam on this very topic on Friday.


calculus
integration
limit
calculus computations

Let $ F,f: R\rightarrow R,F'\equal{}f$ and if $ T$ be period of $ f(x)$ then prove that $ \lim_{x\to \infty}\frac{F(x)}{x}\equal{}\frac{1}{T}\int_{0}^Tf(x) dx$

First, since $ f$ has a period of $ T$, it is easy to conclude $ F(kT)-F(0)=\int_{0}^{kT}f(x) dx=\sum_{i=0}{k-1}{\int_{iT}^{(i+1)T}f(x) dx=k\cdot\int_{0}^{T}f(x) dx=k(F(T)-F(0))}$. So, $ F(kT)=kf(T)-(k-1)F(0)$ for all $ k\in\mathbb{N}$. When $ k\rightarrow +\infty$, $ kT\rightarrow +\infty$ so $ \frac{F(kT)}{kT}=\frac{f(T)}{T}-\frac{F(0)}{T}+\frac{F(0)}{kT}\rightarrow \frac{f(T)-F(0)}{T}=\frac{1}{T}\int_{0}^{T}f(x) dx$.

All that's left to prove now is that there exists $ \lim_{x\rightarrow +\infty}\frac{F(x)}{x}$, then we'll know that that limit is indeed $ \int_{0}^{T}f(x) dx$. We'll prove that by squeeze theorem:
let $ n\in\mathbb{N}$ be such that $ (n+1)T>x\geq nT$ ($ n$ is obviously unique).

Let's assume $ F(x)\geq 0$. Now, $ F(x)=F(nT)+\int_{0}^{x-nT}f(t) dt$. So, $ \frac{F(x)}{x}\leq\frac{F(x)}{nT}=\frac{F(nT)}{nT}+\frac{\int_{0}^{x-nT}f(t) dt}{nT}$. We've already proved that $ \frac{F(nT)}{nT}\rightarrow \frac{1}{T}\int_{0}^{T}f(t) dt$, and, since $ \int_{0}^{x-nT}f(t) dt$ is bounded, $ \frac{\int_{0}^{x-nT}f(t) dt}{nT}\rightarrow 0$. So, $ \frac{F(nT)}{nT}+\frac{\int_{0}^{x-nT}f(t) dt}{nT}\rightarrow \frac{1}{T}\int_{0}^{T}f(t) dt$.

Similarly, $ F(x)=F((n+1)T)-\int_{x-nT}^{T}f(t) dt$, so $ \frac{F(x)}{x}\geq\frac{F(x)}{(n+1)T}=\frac{F((n+1)T)}{(n+1)T}+\frac{\int_{x-nT}^{T}f(t) dt}{(n+1)T}$. With absolutely the same argument as before, we get $ \frac{F((n+1)T)}{(n+1)T}+\frac{\int_{x-nT}^{T}f(t) dt}{(n++1)T}\rightarrow \frac{1}{T}\int_{0}^{T}f(t) dt$.

(If $ F(x)$ is negative, we'll have $ \frac{F(x)}{nT}\leq\frac{F(x)}{x}\leq\frac{F(x)}{(n+1)T}$ but we again have the squeeze theorem with the same argument and the same limits as before, so it doesn't matter.)

Either way, using squeeze theorem, we've proved $ \frac{F(x)}{x}\rightarrow \frac{1}{T}\int_{0}^{T}f(t) dt$.

It is already given by "vergil nicola"
under the title
"A remarkable relations in integral calculus"
Classic
Should try your own


I can not created *pdf if use MikTex 2.7. Can you help me?
Here is picture  http://tuan.nguyentrung.googlepages.com/test.JPG . I cann't upload. The forum is wrong!

The easiest thing is to install the complete MiKTeX system rather than the Basic one. I know it is a very large download but it installs loads of packages you might need and saves trying to install them later.


salaam ! :D

can you sum

$ \sum_{k\equal{}1}^\infty\;\dfrac{(\minus{}1)^{k\plus{}1}\cdot k^4}{1\plus{}k^5}$

it's same as to calculate
$ \sum \frac{x^{k}}{1\plus{}k^{5}}$


Find all triples $(x,y,z)$ of real numbers that satisfy \[ \begin{aligned} & x\left(1 - y^2\right)\left(1 - z^2\right) + y\left(1 - z^2\right)\left(1 - x^2\right) + z\left(1 - x^2\right)\left(1 - y^2\right) \\ & = 4xyz \\ & = 4(x + y + z). \end{aligned}  \]

Since $x+y+x=xyz$, we can assume that $x=\tan A,y=\tan B,z=\tan C$ for some triangle $ABC$. But then
\[ \tan{2A}=\dfrac{2x}{1-x^2} \] hence
\[ \sum {\dfrac{x}{1-x^2}}=\frac12 \sum {\tan{2A}}=\frac12 \tan{2A}\cdot \tan{2B} \cdot \tan{2C}=\dfrac{4xyz}{(1-x^2)(1-y^2)(1-z^2)}. \] We obtain
\[ \sum x(1-y^2)(1-z^2)=4xyz, \]
so the solution is indeed $x=\tan A,y=\tan B,z=\tan C$ for some triangle $ABC$.

Can also be solved by just multiplying out the brackets


It doesn’t work for $ a\equal{}1,\,b\equal{}c\equal{}\frac12.$ :huh:

[quote="ValentineA"]It doesn’t work for $ a \equal{} 1,\,b \equal{} c \equal{} \frac12.$ :huh:[/quote]
Sory, i edited  :blush:

It still doesn’t work when $ a\equal{}b\equal{}c\equal{}0.$ :P

[quote="Victory.US"]let$ a,b,c \ge0$ such that $ ab \plus{} bc \plus{} ca\ge a \plus{} b \plus{} c$ prove that:

$ \frac {1}{a \plus{} b \plus{} 1} \plus{} \frac {1}{b \plus{} c \plus{} 1} \plus{} \frac {1}{c \plus{} a \plus{} 1} \le 1$  :wink:[/quote]
For $ a\plus{}b\plus{}c\neq0$ it's obvious after homogenization.

$ \sum \frac{1}{a\plus{}b\plus{}1}\leq 1$

$ \Leftrightarrow \sum (a\plus{}b\plus{}1)(b\plus{}c\plus{}1)\leq \left ( a\plus{}b\plus{}1 \right )\left ( b\plus{}c\plus{}1 \right )\left ( c\plus{}a\plus{}1 \right )$

$ \Leftrightarrow 2(a\plus{}b\plus{}c) \leq ab(a\plus{}b)\plus{}bc(b\plus{}c)\plus{}ca(c\plus{}a)$

Suppose $ a\geq b\geq c$

We have $ ab(a\plus{}b)\plus{}bc(b\plus{}c)\plus{}ca(c\plus{}a)\geq \frac{1}{3}(ab\plus{}bc\plus{}ca)(2a\plus{}2b\plus{}2c)$ ( Chebyshev ineq )
$ \Rightarrow ab(a\plus{}b)\plus{}bc(b\plus{}c)\plus{}ca(c\plus{}a)\geq 2(a\plus{}b\plus{}c)$ (because $ ab\plus{}bc\plus{}ca\geq a\plus{}b\plus{}c$ so $ ab\plus{}bc\plus{}ca\geq 3$)

Note that : $ (a\plus{}b\plus{}c^2)(a\plus{}b\plus{}1) \ge (a\plus{}b\plus{}c)^2$, so we have :

$ \frac{1}{a\plus{}b\plus{}1} \le \frac{a\plus{}b\plus{}c^2}{(a\plus{}b\plus{}c)^2}$

summing up this inequalities cyclically, we get :

$ \sum_{cyc} \frac{1}{a\plus{}b\plus{}1} \le \frac{a^2\plus{}b^2\plus{}c^2\plus{}2(a\plus{}b\plus{}c)}{(a\plus{}b\plus{}c)^2} \le \frac{a^2\plus{}b^2\plus{}c^2\plus{}2(ab\plus{}bc\plus{}ca)}{(a\plus{}b\plus{}c)^2}\equal{}1$

Proved :lol: