quadratics
group theory
abstract algebra
Galois Theory
superior algebra
superior algebra unsolved

Prove that the unique quadratic subfield of Q(zeta) where zeta is a pth root of unity is

K= Q(sqrt(p)) if p=1(mod4)
K= Q(sqrt(-p)) if p=3(mod4)

$ \mathbb{Q}(\zeta_p)/\mathbb{Q}$ is galois with galois group $ \cong (\mathbb{Z}/p\mathbb{Z})^\times$, which is cyclic of even order. (as $ \mathbb{F}_p\equal{}\mathbb{Z}/p\mathbb{Z}$ is a field)
So it has a unique subgroup of index $ 2$, and it's fixed field is the unique quadratic subfield of $ \mathbb{Q}(\zeta_p)$.
The rest I proved in the lemma [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=199531]here[/url].


[hide] Since .0625=1/16, we have that $log_{256}(.0625)=log_{16^{2}}(\frac{1}{16})=\frac{-1}{2}.$  Since $logn+logm=logmn$, we have that $log125+log.8=log100$.  Note that whenever we say logx, we mean $log_{10}(x)$, so $log100=log_{10}(100)=2$.  Adding our two values up, we get $\frac{-1}{2}+2=\frac{3}{2}$, which is our answer. [/hide]


If $\sqrt{x+2}=2$, then $(x+2)^2$ equals

$\text{(A)}\ \sqrt{2} \qquad \text{(B)}\ 2 \qquad \text{(C)}\ 4 \qquad \text{(D)}\ 8 \qquad \text{(E)}\ 16$

i think i dont understand the question

if $2=(x+2)^\displaystyle\frac{1}{2}$ then $(x+2)^2=2^4$

Reply by mod: Don't worry, that's correct. :)
Reply by sol: because a strange reason i wasnt able to see the options

[hide="Solution"]Since $\sqrt{x+2}=2$, $(\sqrt{x+2})^2=x+2=4 \Rightarrow x=2$.

$(x+2)^2=4^2=16$ The answer is therefore $E$.[/hide]

[hide]
x has to be 2.
$2^4=16$
So $E$[/hide]

HAHAHAHAHAHAHAHAHAHAHA!!!!!!!

 :rotfl:  :rotfl:  :rotfl:   ....

[hide]
x=2

2+2 =4     and the square root of 4 is 2
2x2= 4^2= 16

[/hide]

[hide]solve the equation and x = 2 so (2+2)(2+2)=4(4)=16=E[/hide]


Determine all function $f : \mathbb{N}\rightarrow \mathbb{R}$ so that for all $k,m,n$ we have $f(km)+f(kn)-f(k) \cdot f(mn) \geq 1$

This was in a book recommended on this website...

Can u tell me where the book is ? Actually, I just want to know the answer..  :maybe:

Let $f(1)=x$, then (k=m=n=1) $x^{2}-2x+1\le 0 \Longrightarrow x=1$.
m=n=1 give $f(k)\ge 1$. From $m=n=k$ we get $f(k^{2})(2-f(k))\ge 1$. Therefore $1\le f(k)<2$.
Let $a_{n}=f(k^{2^{n}})$, then $a_{n+1}\le \frac{1}{2-a_{n}}$. If $1<a_{0}<2$ it give contradition with $a_{n}<2 \ \forall n\in N$. Therefore $f(n)=1 \ \forall n\in N$.

[quote="RDeepMath91"]There's a typo, it must be $a_{n+1}\geq \frac{1}{2-a_{n}}$..
But how can you prove if $a_{0}> 1$ then there exist $n$ so that $a_{n}> 2$ ?
I think it's not that trivial..  :maybe:

How about this,
If $a_{0}> 1$,
$a_{n+1}\geq \frac{1}{2-a_{n}}> a_{n}$
Though I can prove the sequence $a_{n}$ is increasing, is it enough ? Maybe there's a particular value of $a_{0}$ so that the sequence is bounded by 2..[/quote]
Yes $a_{n+1}\ge \frac{1}{2-a_{n}}$. It give contradition with $a_{n}<2$ if $a_{0}>1$.
Exactly, if $a_{0}>1+\frac{1}{k}$, then $a_{1}>1+\frac{1}{k-1}$,...,$a_{k-1}>2$.


In solving the system of equations $ y \equal{} 7$ and $ x^2\plus{} y^2\equal{} 100$, what is the sum of the solutions for $ x$?

[quote="GameBot"]In solving the system of equations $ y \equal{} 7$ and $ x^2 \plus{} y^2 \equal{} 100$, what is the sum of the solutions for $ x$?[/quote]

sum of roots $ \ \equal{}0$

[quote="makar"]sum of roots $ \ \equal{}0$[/quote]
why??

hello, plugging $y=7$ in the given equation we get $x^2=100-49$ thus $x=\pm \sqrt{51}$ therefore the searched sum is zero.
Sonnhard.


calculus
integration
logarithms
function
calculus computations

I don't want to spoil it for someone who could get something out of it.  The answer is:

[hide]$e+(e-1)e^e$[/hide]

[quote="blahblahblah"]It's done by parts; substitute $u=e^x$ and $v=(x+1)\ln x$[/quote]

hum :D

Well, they still have to do the integration themselves.  With a product of 3 functions, that's a lot of integrals to calculate.

$(xe^x\ln x)'=e^x\ln x+xe^x\ln x+xe^x\frac{1}{x}=(x+1)e^x\ln x+e^x$ :D

Very good, kunny :lol: You have many interesting integral exercises  ;)


What is the formula to find the number of faces/edges/vertices based on information given for example:

If the measure of an interior angle of a regular polygon is 160 degrees, and this polygon is the base of a prism, the prism has how many edges?

I know there's a formula relating faces/edges/vertices, i just forgot, and google isn't too helpful

Ok so the formula for the number of degrees in each angle of a regular polygon is
180(n-2)/n=160
180n-360=160n
20n=360
n=18

so it has 18 sides.

If it is a prism,
then it should have
1+1+18 faces
18*2 vertices

I think you are thinking of
V+F=E+2
where v,f and e are vertices, faces, and edges.

so
36+20=E+2

56=E+2
E=54
It has 54 edges

Alternatively, for the first one, b/c the angle is 160 degrees, it's external angle is 20.  External angles sum to 360 degrees, if each external angle is 20, there are 360/20=18 angles, therefore 18 sides.


MATHCOUNTS
percent
ratio
geometry
probability
analytic geometry
trapezoid

I wrote up a Mock MathCounts for the Math Nerds of New Jersey. (Since I noticed that the Illinois Forum has one.) Anyone can participate in the Chapter competition. You can private message your answers to me.

Sprint Round:

1. Triangle ABC is an obtuse, isosceles triangle. Angle A measures 20 degrees. What is the measure of the
largest interior angle of triangle ABC?

2. In Clara county, 25% of households earn less than 30,000 per year, and 65% of households earn less than 80,000 per year. What is the largest possible percent of households that could
earn between 30,000 and 80,000 per year?

3. The mean of four distinct positive integers is 5. If the largest integer is 13, what is the smallest integer?

4. What is the sum of the odd integers from 11 through 39, inclusive?

5. A line contains the points (-1, 6), (6, k) and (20, 3). What is the value of k?

6. A particular convex polygon with seven sides has exactly one right angle. How many diagonals does this seven-sided polygon have?

7. The product of three consecutive odd integers is 1287. What is the sum of the three integers?

8. In square ABCD, point M is the midpoint of side AB and point N is the midpoint of side BC. What is the ratio of the area of triangle AMN to the area of square ABCD? Express your answer as a common fraction.

9. How many non-congruent triangles are there with sides of integer length having at least one side of length 5 units and having no side longer than 5 units?

10. A customer ordered 15 pieces of gourmet chocolate. The order can be packaged in small boxes that contain 1, 2 or 4 pieces of chocolate. Any box that is used must be full. How many different combinations of boxes can be used for the customer’s 15 chocolate pieces? One such combination to be included is to use seven 2-piece boxes and one 1-piece box.

11. The summary of a survey of 100 students listed the following totals:
59 students did math homework
49 students did English homework
42 students did science homework
20 students did English and science homework
29 students did science and math homework
31 students did math and English homework
12 students did math, science and English homework
How many students did no math, no English and no science homework?

12. Grady rides his bike 60% faster than his little brother Noah. If Grady rides 12 miles further than Noah in two hours, how fast does Noah ride?

13. Either increasing the radius or the height of a cylinder by six inches will result in the same volume. The original height of the cylinder is two inches. What is the original radius?

14. Four couples are at a party. Four people of the eight are randomly selected to win a prize. No person can win more than one prize. What is the probability that both members of at least one couple win a prize? Express your answer as a common fraction.

15. New York and Denver are in different time zones. When it is noon in New York, it is 10 a.m. in Denver. A train leaves New York at 2 p.m. (New York time) and arrives in Denver 45 hours later. What time is it in Denver when the train arrives?

16. One type of cat food recommends that a cat have a daily serving of 13 ounce of dry cat food per pound of body weight. If a cat is fed 233 ounces of dry food a day according to these recommendations, how many pounds does the cat weigh?

17. If one quart of paint is exactly enough for two coats of paint on a 9-foot by 10-foot wall, how many quarts of paint are needed to apply one coat of paint to a 10-foot by 12-foot wall? Express your answer as a common fraction.

18. A stock loses 10% of its value on Monday. On Tuesday it loses 20% of the value it had at the end of the day on Monday. What is the overall percent loss in value from the beginning of Monday to the end of Tuesday?

19. Five balls are numbered 1 through 5 and placed in a bowl. Josh will randomly choose a ball from the bowl, look at its number and then put it back into the bowl. Then Josh will again randomly choose a ball from the bowl and look at its number. What is the probability that the product of the two numbers will be even and greater than 10? Express your answer as a common fraction.

20. If a certain negative number is multiplied by six, the result is the same as 20 less than the original number. What is the value of the original number?

21. If 2004 is split after the third digit into a three-digit integer and a one-digit integer, then the two integers, 200 and 4, have a common factor greater than one. The years 2005 and 2006 each have this same property, too. What is the first odd-numbered year after 2006 that has this property?

22. Two consecutive even numbers are each squared. The difference of the squares is 60. What is the sum of the original two numbers?

23. At the beginning of my bike ride I feel good, so I can travel 20 miles per hour. Later, I get tired and travel only 12 miles per hour. If I travel a total of 122 miles in a total time of 8 hours, for how many hours did I feel good? Express your answer as a common fraction.

24. When reading a book, Charlie made a list by writing down the page number of the last page he finished reading at the end of each day. (He always finished reading a page that he started.) His mom thought his list indicated the amount of pages he had read on each day. At the end of the 8th day of reading, she added the numbers on his list and thought Charlie had read 432 pages. If Charlie started reading the book on page one, and he read the same amount of pages each day of this eight-day period, how many pages did he actually read by the end of the 8th day?

25. Suppose that each distinct letter in the equation MATH = COU + NTS is replaced by a different digit chosen from 1 through 9 in such a way that the resulting equation is true. If H = 4, what is the value of the greater of C and N?

26. One gear turns $ 33\frac{1}{3}$ times in a minute. Another gear turns 45 times in a minute. Initially, a mark on each gear is pointing due north. After how many seconds will the two gears next have both their marks pointing due north?

27. It takes 24 minutes for Jana to walk one mile. At that rate, how far will she walk in 10 minutes? Express your answer as a decimal to the nearest tenth.

28. When plotted in the standard rectangular coordinate system, trapezoid ABCD has vertices A(1, −2), B(1, 1), C(5, 7) and D(5, 1). What is the area of trapezoid ABCD?

29. What is the sum of all the distinct positive two-digit factors of 144?

30. The positive difference of the cube of an integer and the square of the same integer is 100. What is the integer?

Good luck!

What about your number theory problems? Stop procrastinating.

what are you talking about, thats in the Math Olympics......
I have noticed that some of the problems you didn't make up.....can I do it?

Revive much? :P

Subtract areas from the square.

#8 is 1/8th! because I'm pretty sure that i did this problem on an aops book because this problem is so popular

what is the answer to #23? NEED IMMEDIATELY.


By the EV-Theorem, it suffices to prove the inequality for $ b\equal{}c\equal{}1$.

[quote="arqady"]Thank you, Vasc! But I still  didn't read a proof of this theorem.  :([/quote]
See http://jipam.vu.edu.au/article.php?sid=828


Hi, I play both the piano and violin, but have always had trouble reading rhythms and playing to the beat of a metronome. Anyone have any ideas on how I can become better at this? My teacher tell me to count, but that's not really helping, because sometimes I have no idea what the song sounds like until someone else plays it. And I just go along with that until i've memorized the rhythm and mastered the notes in the piece and it has really slowed my progress. Just looking for some suggestions, thanks!


Let $ x$ be a real number such that the five numbers $ \cos(2 \pi x)$, $ \cos(4 \pi x)$, $ \cos(8 \pi x)$, $ \cos(16 \pi x)$, and $ \cos(32 \pi x)$ are all nonpositive.  What is the smallest possible positive value of $ x$?

[hide]For $ \cos(2\pi u)$ to be nonpositive, the fractional part of $ u$ must lie between $ \frac{1}{4}$ and $ \frac{3}{4}$.

We will now consider all numbers mod 1 (or the fractional part of all numbers). Call a number valid if (its fractional part) lies in $ [\frac{1}{4},\frac{3}{4}]$ We must have $ x,2x,4x,8x,16x$ be valid. Note that the range $ [\frac{1}{4},\frac{1}{2}]$, when doubled, maps to $ [\frac{1}{2},1]$. The valid part of this range is $ [\frac{1}{2},\frac{3}{4}]$, meaning that only the first half of the range $ [\frac{1}{4},\frac{1}{2}]$ will go to a valid number when doubled, Similarly, only the second half of the range $ [\frac{1}{2},\frac{3}{4}]$ will go to a valid number (in $ [\frac{1}{4},\frac{1}{2}]$) when doubled.

Since we want $ x$ minimized, assume that it lies in $ [\frac{1}{4},\frac{1}{2}]$. For $ 2x$ to be valid, $ x$ must lie within the first half of this range, namely $ [\frac{1}{4},\frac{3}{8}]$. Now, $ 2x$ lies in $ [\frac{1}{2},\frac{3}{4}]$, so for $ 4x$ to be valid, $ 2x$ must lie within the second half of its range, meaning that $ x$ lies within in the second half of $ [\frac{1}{4},\frac{3}{8}]$, which is $ [\frac{5}{16},\frac{3}{8}]$. Repeating this process, we have that $ x$ must lie in $ [\frac{5}{16},\frac{11}{32}]$ for $ 8x$ to be valid, and that $ x$ must lie in $ [\frac{21}{64},\frac{11}{32}$ for $ 16x$ to be valid. Thus, the smallest possible value of $ x$ is $ \boxed{21}{64}$.[/hide]

Right.  Your final box came out a little off.  You mean $ \boxed{\frac{21}{64}}$.


What is the percent probability that a two-digit number selected at random will have its tens digit at least two more than its units digit?

We can start to list the different possibilities from smallest to largest:

\[ 20 \]

\[ 30, 31 \]

\[ 40, 41, 42 \]

\[ 50, 51, 52, 53 \]

\[ ... \]

There's a pattern! Our answer is just 1 + 2 + 3 + 4 + ... + 8 = $ \boxed{36}$.

[quote="Mewto55555"]Thus 36 numbers out of a possible 90 work, so 36/90=6/15=2/5.[/quote]

Gasp! You read incorrectly?

So $ \frac25\implies\boxed{40\%}$. :P


Inverse of f(x) = e^x + x.

Question :

I have heard (many times before) that the function f(x) = e^x + x

has no closed form inverse, in terms of elementary functions like: finite sums, products, exponentiations and compositions of polynomials, rational functions, trigonometric functions, exponential functions, hyperbolic functions and all their inverses.

However, I've never seen a proof for the case at hand.
I was wondering whether there is such a proof and whether or not it's simple enough for me to understand.

This is not a class-assigned problem; it is just for my own curiosity.

Thank you

i just think that it is the fact that you cannot solve for x in this expression

On a related note,

Is it impossible to solve for x in the general form

$f(x)=n^x+x, n \neq 1, n \neq 0 \text{ (ha ha ha)}$

?

Well, think about how an inverse is found. You're basically expressing the equation as $x=N$ (then replacing $x$ with $y$ and vice-versa) instead of $y=N$. However, with an $x$ in an exponent and an $x$... not as an exponent :P, you can't do that. All equations of that type have no inverse that can be expressed by an equation. For example, you can say that the inverse of $y=e^x \Rightarrow x=\ln y$ is $y=\ln x$. The inverse of $y=3x\Rightarrow x=\frac{1}{3}y$ is $y=\frac{1}{3}x$. But the way the equation is laid out, that's impossible to do.

Thank you for your response.

Clearly, if I could solve for x in the equation:

f(x) = e^x + x

I would have found the inverse function. But this again raises the question: How do I know that it can't be done? I could try again and again to solve for x in that equation and fail each time; but how can I prove that this is because it really is impossible, and not because I just haven't come up with an ingenious enough approach?

Thank you again.


limit
integration
real analysis
real analysis unsolved

$(f_{n}(x))$ converges a.e to $\frac{1}{1+|x|}$, and $|f_{n}(x)| \leq 2$. Applying Lebesgue's Bounded Convergence Theorem gives the result $2ln(2)$.


A square ABCD is drawn such that AB=37453 cm.  A point P is randomly chosen inside the square.  What is the probability that APB is acute?  Express your answer to the nearest whole percent.

Let AB=2x. Consider the geometric locus consisting in all Points such that <APB= 90º. Clearly, this locus is a circumpherence centered in the middle of AB with radii x, because if P belong to that circumpherence, angle PAB subtends a diameter, hence =90º. SInce only half of the circumpherence is inside the square, we will consider only this half. If P is on circle, PAB = 90º. If P is inside the circle, the angle becomes obtuse. Then all obtuse angles lie inside the semicircle. The semicircle area is

(pi)(x^2)/2, And the square area is 4x^2. Then the probability is (pi)/8=0.3927= 39.27%. Note that this probability is independent of the square's side length.

So, basically, it's the interior of a semicircle with radius AB. SInce a line has no area, we just find the area of the circle and divide by the area of the square.

I tried to find all the points such that $ APB$ is obtuse.
If $ O$ is the center of the square.
All the points that make $ APB$ obtuse are in triangle $ AOB$.
thus the probability of being obtuse is $ 25%
$.
Thus being acute will be $ 75%
$.
Since I did not use the length of a side of the square, this is true for any square irrespective of length.

Nobody actually posted a correct answer yet...

@Pul de Algodoncito - the question says acute...

@Fraenkel - not exactly a triangle, you can definitely find points outside of the triangle that still make APB obtuse.  (especially in such a huge square)

Just a bit of confusion on Pul's part...

[hide="solution"]No one wants to deal with that number, so let's just call it $ s$. We know that a triangle inscribed in a circle with the diameter as a side is right. So, we can determine that the locus of points with APB obtuse are the points in semicircle with diameter AB, centered at the square's center. This region has area $ \pi\frac{s^2}{8}$. Now, the square's area is $ s^2$. Thus, our desired probability is $ 1-\frac{\pi\frac{s^2}{8}}{s^2}=1-\frac{\pi}{8}=\boxed{\frac{8-\pi}{8}}\approx60.73%
$.[/hide]

Good old mathcounts problems...

I dont get it could someone explain this to me?

[quote="Fraenkel"]Can you give me an example of a point outside that triangle to make angle $ APB$ obtuse?[/quote]

Take a 4x4 square, for example, with O being the center of the square.  Suppose we let the square be ABCD and A=(0,0), B=(0,4), C=(4,4), and D=(4,0).  O=(2,2).  The point P=(1,1.1) is inside AOB, but inside the semicircle with AB as a diameter, So APB is obtuse, yet not in AOB.

In fact, I determinde the probalbility of that angle to be obtuse. The probability of the angle being acute is as perfect628 wrote, is 60.73.

But the circle is not centered at the center of the square, but in the midpoint of segment AB so AB is a diameter and the points belonging to interior arc AB subtend a right angle.

there is an infinity of points P which satisfy that angle APB is obtuse and doesnt belong to triangle AOB. Any point lying in or inside the semicircumpherence with radii AB/2 but not in AOB will make it. Obviously there exist entire regions with these points, the regions correponding to the circumscribed semicircle to AOB that are not AOB.

yeah, i wrote diameter AB and center at the square's center...the latter is not true. can't edit though.


trigonometry
geometry
circumcircle
geometry unsolved

Let $A,B$ be two distinct points on a given circle $O$ and let $P$ be the midpoint of the line segment AB. Let $O_1$ be the circle tangent to the line $AB$ at $P$ and tangent to the circle $O$. Let $l$ be the tangent line, different from the line $AB$, to $O_1$ passing through $A$. Let $C$ be the intersection point, different from $A$, of $l$ and $O$. Let $Q$ be the midpoint of the line segment $BC$ and $O_2$ be the circle tangent to the line $BC$ at $Q$ and tangent to the line segment $AC$. Prove that the circle $O_2$ is tangent to the circle $O$.

Trigonometry finishes off this question very quickly.

Let the center of $O$ be $X$ and let the radii of $O$ and $O_1$ be $R$ and $R_1$ respectively.  Let $XP$ intersect $O$ at $D$.

We see that $O_1$ is tangential to $O$ iff $2R = 2R_1 + PD = 2AP \tan \frac{\alpha}{2} + AP \tan \frac{\gamma}{2} = R(2 \sin \gamma + \tan \frac{\alpha}{2} + \sin \gamma \tan \frac{\gamma}{2})$.  Using the substitution $\tan \frac{\alpha}{2} = t, \tan \frac{\gamma}{2} = u$, this reduces to $tu = \frac{1}{2}$.  Now apply the result to $O_2$.

This is another intresting property involving a triangle with $a+c=3b$ :lol:

Yeah,that triangle has many many good properties.

[quote="ooiler"]what a boring solution
with an inversion on point a with the  AB*AC
it is obviously[/quote]
Congratulations for a [i][b]magnificent[/b][/i] solution!  :rotfl:

[quote="ooiler"]what a boring solution
with an inversion on point a with the  AB*AC
it is obviously[/quote]

How? I don't understand?

[quote="ooiler"]what a boring solution
with an inversion on point a with the  AB*AC
it is obviously[/quote]

[hide="Solution"]
Consider $\sqrt{bc}$ inversion, inversion about a circle with center $A$ with power $bc$.  It is well-known (and derivable by easy tangent arguments) that this brings the mixtillinear incircle to the excircle and vice versa.

Perform this on $\triangle ABC$ with $A$ as the vertex.  Then we have $(AP)s=bc\Rightarrow s=2b$.  Now it is sufficient to prove that the $C$-mixtillinear incircle touches $BC$ at $Q$.  Say it touches it at $Q'$.  With root bc inversion with $C$ as the center, we have $(CQ)s=ab\Rightarrow CQ=\dfrac{ab}{s}=\dfrac{a}{2}$, so $Q=Q'$ as desired.

QED
[/hide]

[quote="Sailor"]Since the circle tangent to $AB$ (at its midpoint) is also tangent to $AC$( uppose at point $Y$) and to $O$, from the Casey's theorem we get:
\[ CY=\frac{a-b}{2}\Longleftrightarrow a+c=3b (1)  \]
(where $a,b,c$ are the sides of $\triangle{ABC}$)
Now if $O_2$ is tangent to $AC$ at $T$ and to $BC$ at $Q$ then, using (1) and the fact that $CT=CQ=\frac{a}{2}$, we obtain:
\[ CT\cdot{c}=b\cdot{BQ}+a\cdot{AT} (2)  \]
However, the only circle which is tangent to $CA,BC$ and the circumcircle of $\triangle{ABC}$ should also satisfy $(2)$ (from the Casey's theorem), therefore $O_2$ is tangent to $O$.[/quote]
Can you just state "by Casey's Theorem..." Is it well-known enough to use without proof? For example, in APMO #3, Wolstenholme's Theorem need proof! Can someone tell me which theorems you need proof for?

Wait you actually don't need anything complicated (it's all straightforward bashing):

*My actual proof's a bit long so I'll just write my thought processes:

1) First you rephrase the problem statement: Triangle ABC is drawn such that the A mixtilinear circle touches AB at the midpoint, P. Prove that the C mixtilinear circle touches BC at the midpoint Q.
2) Then you find a series of equivalent statements. The path I went along used the fact that the tangency pts of mixtilinear circles on the sides of the triangle are bisected by the incenter. Anyways, it suffices to prove that the incenter I bisects C-mixtilinear tangency points $R_2$ and Q, which reduces to $R_2, I, Q$ need to be collinear.
3) After some simplifications you arrive at a+c=3b. This statement is independent of everything I just did and is essentially a much easier problem than the one we started with.
4) Specifically, the new problem states that "the A mixtilinear circle is tangent to AB at the midpoint P. Prove that a+c = 3b". Here, you note that AIP is a right triangle and you length bash. (using [ABC]=rs, and other incircle stuff) This works out in the end and you're done.

It's very easy using bary :D
first note that the problem equivalet to
[b][color=#960000]"$\triangle ABC$ is drawn such that the A-mixtilinear circle touches $AB$ at the midpoint, Prove that the C-mixtilinear circle touches $BC$ at the midpoint [/color][/b]
Let the A-mixtilinear touches $(ABC)$ at $M$ and $E$ the ex-touch point on $BC$
then easitly get  $M(-a:\frac{b^2}{s-b}:\frac{c^2}{s-c})$ (using that $AM$ and $AE$ are isogonal
but $MP$ is the perpindacular bisetor of $AB$ thus $M$ is the midpoint of arc $ACB$
then $M(-a:b:\frac{c^2}{a-b})$
$b=s-b \implies a+c=3b$ which is symmetric in $A,C$  so this is equivalent to "the C-mixtilinear circle touches $BC$ at the midpoint "

It is obvious that  $O_1$ is $A$-mixtilinear circle.
The problem is equivalent to proving that if the $A$-mixtilinear circle touches $AB$ at its midpoint, then $C$-mixtilinear circle touches BC at its midpoint.
Let $F$, $G$ be touchpoints of $A$-mixtilinear and $C$-mixtilinear with $AC$ and $Q$ touchpoint of $C$-mixtilinear and $BC$.
Since $GQ$ and $FP$ intersect each other at middle (the incenter-well-known), we get that FGPQ is parallelogram, thus PQ|| AC.
$P$ is midpoint => $Q$ is midpoint.


geometry
circumcircle
geometric transformation
rotation
congruent triangles
cyclic quadrilateral

Given triangle $ABC$, squares $ABEF, BCGH, CAIJ$ are constructed externally on side $AB, BC, CA$, respectively. Let $AH \cap BJ = P_1$, $BJ \cap CF = Q_1$, $CF \cap AH = R_1$, $AG \cap CE = P_2$, $BI \cap AG = Q_2$, $CE \cap BI = R_2$. Prove that triangle $P_1 Q_1 R_1$ is congruent to triangle $P_2 Q_2 R_2$.

The triangle pairs $\triangle ABI \cong \triangle AFC,\ \triangle BCE \cong \triangle BHA,\ \triangle CAG \cong \triangle CJB$ are congruent by SAS, for example, the 1st pair has the sides AB = AF and AI = AC equal, because ABEF and CAIJ are both squares and the angles $\angle BAI = \angle FAC = \angle A + 90^o$ are also equal. Hence, the other corresponding angles of these congruent triangle pairs are also equal. Moreover, the triangle $\triangle ABI$ is obtained by rotating the triangle $\triangle AFC$ around the vertex A by the angle $\angle FAB = 90^o$ and similarly for the other 2 triangle pairs. Hence, the line pairs $IB \perp FC,\ EC \perp AH,\ GA \perp BJ$ are perpendicular to each other. The angles $\angle P_1Q_1R_1 = \angle P_2Q_2R_2$ are equal, because

$\angle P_1Q_1R_1 = \widehat{(P_1Q_1, R_1Q_1)} \equiv \widehat{(BJ, FC)} =$

$= \widehat{(GA, FC)} \equiv \widehat{(P_2Q_2, R_2Q_2)} = \angle P_2Q_2R_2$

and similarly, the angles $\angle Q_1R_1P_1 = \angle Q_2R_2P_2,\ \angle R_1P_1Q_1 = \angle R_2P_2Q_2$ are also equal. Thus we established that the triangles $\triangle P_1Q_1R_1 \sim \triangle P_2Q_2R_2$ are similar.

Let K, L, M be the diagonal intersections of the squares ABFE, BCGH, CAIJ and X, Y, Z the intersections of the perpendicular line pairs $IB \perp FC,\ EC \perp AH,\ GA \perp BJ$. The quadrilateral AXCI is cyclic, because the angles $\angle AIX \equiv \angle AIB = \angle ACF \equiv \angle ACX$ of the congruent triangles $\triangle ABI \cong \triangle AFC$ are equal. Since the angle $\angle CXI = 90^o$ is right, the circumcenter of this cyclic quadrilateral is the midpoint of the chord CI, the diagonal of the square CAIJ. Hence, the circumcircle of the quadrilateral AXCI is identical with the circumcircle $(M)$ of the square CAIJ and the square vertex J also lies on this circle. Since AJ is a diameter of the circle $(K)$ and the angle $\angle AZJ = 90^o$ is also right, the point Z also lies of this circle. The power of the triangle vertex B to the circle $(K)$ is equal to

$BX \cdot BI = BZ \cdot BJ$, which implies $\frac{BI}{BJ} = \frac{BZ}{BX}$

The right angle triangles $\triangle BXQ_1 \sim \triangle BZQ_2$, because the angles $\angle BXQ_1 = \angle BZQ_2 = 90^o$ are both right and the angles $\angle BQ_1X \equiv \angle P_1Q_1R_1 = \angle P_2Q_2R_2 \equiv \angle ZQ_2B$ of similar triangles $\triangle P_1Q_1R_1 \sim \triangle P_2Q_2R_2$ are equal. Consequently,

$\frac{BQ_2}{BQ_1} = \frac{BZ}{BX} = \frac{BI}{BJ}$

But this means that the triangles $\triangle BQ_2Q_1 \sim \triangle BIJ$ are centrally similar with the similarity center B and thus the lines $Q_1Q_2 \parallel JI \parallel CA$ are parallel. In a similar way, we could show that the lines $P_1P_2 \parallel HG \parallel BC$ and the lines $R_1R_2 \parallel FE \parallel AB$ are also parallel.

Let S be the concurrency point of the lines AL, BM, CK, lying (together with the centroid and the 1st Fermat point of the triangle $\triangle ABC$) on Kiepert's hyperbola. Since the angles $\angle AMC = \angle AYC = 90^o$ are both right, the quadrilateral AYCM is cyclic. Since N is the midpoint of the are AC of its circumcircle opposite to the vertex Y, the line YC bisects the right angle $\angle AYC$. Let $(M_1), (M_2)$ be 2 centrally similar circles on centrally similar diameters $IJ \sim Q_1Q_2$ with the similarity center B. Since the right angle triangle $\triangle IMJ$ with the circumcircle $(M_1)$ is isosceles with IM = JM, the line BM cuts the corresponding arcs $JI, Q_1Q_2$ of the circles $(M_1), (M_2)$ at their midpoints M, S', the right angle triangle $\triangle Q_1S'Q_2$ is also isosceles with $Q_1S' = Q_2S'$ and the angles $\angle Q_2Q_1S = \angle Q_1Q_2S' = 45^o$. Since the angles $\angle Q_1XQ_2 = \angle Q_1ZQ_2 = 90^o$ formed by the perpendicular lines $Q_1X \equiv FC \perp IB \equiv Q_2X$ and $Q_1Z \equiv JB \perp AG \equiv Q_2Z$ are both right, the points $X, Z$ both lie on the circle $(M_2)$. Since the angle $\angle AZK \equiv \angle Q_2ZS = 45^o$, this angle spans the same arc $Q_2S'$ as the angle $\angle Q_2Q_1S' = 45^o$ and as a result, the points $S' \equiv S$ are identical. Thus we proved that the triangle $\triangle Q_1SQ_2$ is isosceles with the angle $\angle Q_1SQ_2 = 90^o$ and $Q_1S = Q_2S$. In a similar way, we could prove that the triangles $\triangle P_1SP_2,\ \triangle R_1SR_2$ are also isosceles with the angles $\angle P_1SP_2 = \angle R_1SR_2 = 90^o$ and $P_1S = P_2S,\ R_1S = R_2S$. As a result, the triangle $\triangle P_2Q_2R_2$ is obtained from the triangle $\triangle P_1Q_1R_1$ by a rotation around the center S by the angle $\angle P_1SP_2 = \angle Q_1SQ_2 = \angle R_1SR_2 = 90^o$, which means that these 2 triangles are congruent.

Yetti

Dear Mathlinkers,
an article concerning the Vecten's figure and its developpement can be seeing on my site
http://perso.orange.fr/jl.ayme , la figure de Vecten  vol. 5 p. 40
Sincerely
Jean-Louis


Let $ D$ be a point on the side $ AC$ of $ \triangle{ABC}$.Let $ E$ and $ F$ be points on the segment $ BD$ and $ BC$,respectively,such that $ \hat{BAE}\equal{}\hat{CAF}$.Let $ P$ and $ Q$ be points on $ BC$ and $ BD$,respectively,such that $ EP \parallel{} DC$ and $ FQ \parallel{} CD$.Prove that $ \hat{BAP}\equal{}\hat{CAQ}$

Apply Céva's theorem for: $ \triangle ABI$ with $ BE,IE,AD$ concurrent we obtain:
$ \frac{\sin{\widehat{DAB}}}{\sin{\widehat{DAC}}}.\frac{\sin{\widehat{EIA}}}{\sin{\widehat{EIB}}}.\frac{\sin{\widehat{EBI}}}{\sin{\widehat{EBA}}}\equal{}1$

Apply Céva's theorem for $ \triangle ABF$ with $ AD,BJ,FJ$ concurrent, we obtain:
$ \frac{\sin{\widehat{DAB}}}{\sin{\widehat{DAC}}}.\frac{\sin{\widehat{JFA}}}{\sin{\widehat{JFB}}}.\frac{\sin{\widehat{JBF}}}{\sin{\widehat{JBA}}}\equal{}1$

Compare these two expressions above, with notice that $ \widehat{EIA}\equal{}\widehat{JFA}\equal{}\widehat{ACB}$ and $ \widehat{EBA}\equal{}\widehat{JFB}$, we obtain:
$ \frac{\sin{\widehat{EBI}}}{\sin{\widehat{EIB}}}\equal{}\frac{\sin{\widehat{JBF}}}{\sin{\widehat{JBA}}}$

On the other hand: $ \widehat{EBI}\plus{}\widehat{EIB}\equal{}\widehat{EBI}\plus{}\widehat{CBI}\equal{}\widehat{EBC}\equal{}\widehat{JBA}\equal{}\widehat{JBF}\plus{}\widehat{JBA}$

Hence, $ \widehat{EBI}\equal{}\widehat{JBF}$ and $ \widehat{EIB}\equal{}\widehat{JBA}$, which ends our proof.


geometry
incenter
inradius
trigonometry
symmetry
ratio
angle bisector

$ I_A$ is incenter of $ AB'C'$ where $ A'$ is feet of height from A.Let $ N_A$ is the point where incircle touches $ BC$.
Prove that $ N_AI_CN_BI_AN_CI_B$   is a hexagon with all sides equal lengths.

[hide]Let $ E$ and $ F$ be the feet of perpendicular from $ B$ and $ C$ to $ AC$ and $ AB$ respectively. Let the incircle of $ \triangle AEF$ touches the side $ AE$ at $ G$. Also let $ \angle BAC=2\alpha$. Note that $ A,I_A,I$ lie on the angle bisector of $ \angle BAC$, and hence are colllinear. It is well known that $ \triangle AEF\sim\triangle ABC$. Hence $ \frac{AI_A}{AI}=\frac{AG}{AN_B}=\frac{AE+AF-EF}{AC+AB-BC}=\frac{AE}{AB}=\cos2\alpha$. Consider the right triangle $ N_BIA$ and a cevian $ N_BI_A$. Let $ r$ be the inradius of $ \triangle ABC$. We have $ IN_B=r$, $ IA=\frac{r}{\sin\alpha}$, $ AN_B=\frac{r}{\tan\alpha}$, $ AI_A=\frac{r\cos2\alpha}{\sin\alpha}$, $ I_AI=\frac{r(1-\cos2\alpha)}{\sin\alpha}=2r\sin\alpha$. By Stewart's Theorem, we have \[ IN_B^2\cdot AI_A+AN_B^2\cdot II_A=AI(I_AN_B^2+AI_A\cdot II_A)\]

\[ r^2\frac{r\cos2\alpha}{\sin\alpha}+\frac{r^2}{\tan^2\alpha}2r\sin\alpha=\frac{r}{\sin\alpha}(I_AN_B^2+\frac{r\cos2\alpha}{\sin\alpha}2r\sin\alpha)\]

\[ \frac{r^3\cos2\alpha}{\sin\alpha}+\frac{2r^3\cos^2\alpha}{\sin\alpha}=\frac{r}{\sin\alpha}(I_AN_B^2+2r^2\cos2\alpha)\]

\[ r^2\cos2\alpha+2r^2\cos^2\alpha=I_AN_B^2+2r^2\cos2\alpha\]

\[ r^2(2\cos^2\alpha-\cos2\alpha)=I_AN_B^2\]

\[ r^2=I_AN_B^2\]

Hence $ I_AN_B=r$. By symmetry, we also have $ N_AI_C=I_CN_B=N_BI_A=I_AN_C=N_CI_B=I_BN_A=r$. Q.E.D.[/hide]

If $ AA'$ and $ BB'$ are altitudes ($ A'$ and $ B'$ on $ BC$, $ AC$ respectively), it is well known that $ \frac{A'B'}{AB}\equal{} cos(\angle C)$, and this is the similitude ratio of the triangles $ CA'B'$ and $ CAB$, hence we have to prove that $ \frac{CI_C}{CI}\equal{}cos(\angle C)$ ( 1 ), $ I_C$ being the symmetrical of $ I$ about $ N_AN_B$.
Let $ P\equal{}CI\cap N_AN_B$. If $ IN_A\equal{}r$ (inradius), from the right-angled $ \triangle IN_AC$ we have $ r^2\equal{}IP\cdot IC$ ( 2 ).
But $ CI_C\equal{}IC\minus{}2\cdot IP$ ( 3 ) and, with (2), $ \frac{CI_C}{IC}\equal{}\frac {IC\minus{}\frac {2\cdot r^2}{IC}}{IC}$ $ \equal{}1\minus{}2\cdot \frac {r^2}{IC^2}\equal{}1\minus{}2\cdot cos^2 \left( \frac {\angle C}{2} \right)\equal{}cos (\angle C)$, hence $ I_C$ IS the incenter of $ \triangle CA'B'$ and $ N_AI_C\equal{}N_BI_C\equal{}r$, and similarly for the other vertices.

Best regards,
sunken rock


1) Find the lowest integer the can be written as the sum of 3 consecutive integers, 4 OTHER consecutive integers, and 5 other consecutive integers.

2) A number that can be written as the product of 2 consecs and 3 consecs...
Either find the lowest one or prove that there are none.

1.
[hide]if by "OTHER" you mean non-overlapping, then it would be 90.  Otherwise it would be 30.[/hide]

Then, since it is integers it would be $-90$

The product of four consecutive integers can't be negative though.
Closest it can get is 0.  ;)

2. [hide="Click here for solution"]
1 x 2 x 3 = 2 x 3 = 6

x=a(a+1)
x=b(b+1)(b+2)

It was kind of a guess n' check process, since, for example, 12 = 2x6 = 2x2x3 where 2x3=6, since it is high likely that wither a=b, a=b+1, or a=b+2.
Through some figuring out, only a=b+2 works out to be an integer, where b=1 and a=2, thus 1x2x3=2x3=6.
[/hide]

Oh, hehe.  :blush: I guess I mixed up the two parts on accident.

But anyways, for #1, I think positive is implied, or any negative multiple of 30 would work once you get past -90.

And same for #2, since 0 can be expressed as the product (and sum) of a whole bunch of consecutive numbers.


Prove that in any triangle $ ABC$ we have

$ sin^22A\plus{}sin^22B\plus{}sin^22C \ge 36(r/R)^4$

[quote="Nebraska boy"]Prove that in any triangle $ ABC$ we have

$ sin^22A \plus{} sin^22B \plus{} sin^22C \ge 36(r/R)^4$[/quote]

$ sin^22A \plus{} sin^22B \plus{} sin^22C \ge \frac{1}{3}(sin 2A \plus{} sin 2B \plus{} sin 2C)^2\equal{}\frac{4s^2r^2}{3R^4} \ge$ $ 18 (\frac{r}{R})^3 \ge 36(\frac{r}{R})^4$


Let $a;b;c$ be positive real numbers.Prove that:
$\sqrt[n]{\frac{a}{b+c}}+\sqrt[n]{\frac{b}{a+c}}+\sqrt[n]{\frac{c}{a+b}}\geq 2$
$(n \geq 2)$

I'm sorry but this inequality is not your. It's too old and I remember that I posted once longtime ago!

$n_{min}=\frac{ln2}{ln3-ln2}$
I have a problem more difficult than yours:
Let a,b,c,d$\geq 0 and n \geq n_{min}=\frac{ln2}{ln3-ln2}$.Prove that:
 $(\frac{a}{b+c+d})^{\frac{1}{n}}+(\frac{b}{c+d+a})^{\frac{1}{n}}+(\frac{c}{d+a+b})^{\frac{1}{n}}+(\frac{d}{a+b+c})^{\frac{1}{n}}\geq 2$
Even,I have a similar problem which has n variables!

Yes, not you :lol: First, not be "$\geq$". It's must be ">"
Suppose $a\geq b\geq c>0$ we prove:
$\sqrt[n]{\frac{a}{b+c}}+\sqrt[n]{\frac{b}{c+a}}+\sqrt[n]{\frac{c}{a+b}}>\sqrt[n]{\frac{a+c}{b+c}}+\sqrt[n]{\frac{b+c}{c+a}}$ (*)
 (*) Equivalent:
$\sqrt[n]{\frac{c}{a+b}}>\frac{\sqrt[n]{a+c}-\sqrt[n]{a}}{\sqrt[n]{b+c}}+\frac{\sqrt[n]{b+c}-\sqrt[n]{a}}{\sqrt[n]{c+a}}$(**)
We have:
$\sqrt[n]{a+c}-\sqrt[n]{a}=\frac{a+c-a}{(\sqrt[n]{a+c})^{n-1}+(\sqrt[n]{a+c})^{n-2}\sqrt[n]{a}+...+(\sqrt[n]{a})^{n-1}}<\frac{c}{n\sqrt[n]{a^{n-1}}}$
$\Rightarrow \frac{\sqrt[n]{a+c}-\sqrt[n]{a}}{\sqrt[n]{b+c}}<\frac{c}{n\sqrt[n]{a^{n-1}}}.\frac{1}{\sqrt[n]{b+c}}=\frac{c}{n\sqrt[n]{a^{n-1}(b+c)}$
Because $a^{n-1}(b+c)=a^{n-2}(b+c)=a^{n-2}a(b+c)\geq c^{n-2}c(a+b)=c^{n-1}(a+b)$ so $\frac{\sqrt[n]{a+c}-\sqrt[n]{a}}{\sqrt[n]{b+c}}<\frac{c}{n\sqrt[n]{a^{n-1}(b+c)}}\leq \frac{c}{n\sqrt[n]{c^{n-1}(a+b)}}=\frac{1}{n}.\sqrt[n]{\frac{c}{a+b}}$
Similar $\frac{\sqrt[n]{b+c}-\sqrt[n]{a}}{\sqrt[n]{c+a}}\leq \frac{1}{n}.\sqrt[n]{\frac{c}{a+b}}$
From 2 inequality we have:
$\frac{\sqrt[n]{a+c}-\sqrt[n]{a}}{\sqrt[n]{b+c}}+\frac{\sqrt[n]{b+c}-\sqrt[n]{a}}{\sqrt[n]{c+a}}<\frac{2}{n}\sqrt[n]{\frac{c}{a+b}}\leq \sqrt[n]{\frac{c}{a+b}}$
So (**) is right.


The number of distinct points common to the curves $x^2+4y^2=1$ and $4x^2+y^2=5$ is:

$\text{(A)} \ 0 \qquad \text{(B)} \ 1 \qquad \text{(C)} \ 2 \qquad \text{(D)} \ 3 \qquad \text{(E)} \ 4$

I have a hint, cause I like this problem. :)

[hide]Try adding to two equations. You get a nice circle.

What's special about it?[/hide]

Is it that they their center is on the origin?

what does it mean by "distinct points"
a circle results from manipulating equations but no answer is one of the choices

$x^2+4y^2-1=0$
Multiplying the second equation by 4 gives
$16x^2+4y^2-20=0$

Subtracting the first from the second:
$x^2=\frac{19}{15}$
So $x$ can have 2 values
Answer [b]$2$[/b]

[b]BUT[/b] this of course means $y$ has to be complex.  So on the real axes, there are [b]NO[/b] distinct points.

[hide]so we add them, and get $x^2+y^2=\frac{6}{5}$.  if some $x$ and $y$ satisfied those two original equations, they satisfy the circle equation too.

but if you subtract this equation from $x^2+4y^2=1$, you get $3y^2=\frac{-1}{5}$, so $y$ is imaginary.  so no real solutions.[/hide]

[quote="4everwise"][quote="Altheman"]it is not that hard to just solve the system...[/quote]Yeah, but where's the fun it that? :D[/quote]

I would do the same. But you are right: there is no fun.
But what is the logic to add the two equations? We get the expression of a circle.

[quote="4everwise"][quote="Altheman"]it is not that hard to just solve the system...[/quote]Yeah, but where's the fun it that? :D[/quote]

Math is never fun  :P

what's so special about that circle you mentioned in your hint?

Sorry to post on this old topic,

but according to [b]Contest Problem Book III[/b] published by the MAA, the question should be as follows:

[hide="original"]

The number of distinct points common to the cruve $ x^2\plus{}4y^2\equal{}1$ and $ 4x^2\plus{}y^2\equal{}4$ is:

A. 0
B. 1
C. 2
D. 3
E. 4

[/hide][/b]

in that case, you can just graph the eclipses and its pretty clear that there are two solutions at x=$ \pm 1$ and y=0

[quote="fishythefish"]You mean ellipses.

An eclipse is when the Earth passes between the moon and the Sun (Lunar), or the moon passes between the Earth and the Sun (Solar).[/quote]

thank you so much


trigonometry
inequalities proposed
inequalities

what's conditions of $A$ and $B$ ?
$A=B=0$
$0\geq\frac{2}{\sqrt{3}}$


By placing a 2 at both ends of a number its value increases by 2137.what is the number

[hide]I don't really know how to formally prove this first part, but you know that we're looking for a 2-digit number.  So when a two is added to the front and back, the number will be 2_ _2 and will increase by around $ 2000$. That said, call the original number $ X$

$ 2000\plus{}10X\plus{}2\equal{}2137\plus{}X \Longrightarrow
9X\equal{}135 \Longrightarrow
X\equal{}15$[/hide]


inequalities
logarithms
number theory unsolved
number theory

Show that there exists an absolute constant $a>1$ with the property that for any $n$ and any system of natural numbers $ x_1<x_2<...<x_n$ such that $x_i-x_j$ divides $x_i+x_j$ for all different $i,j$, we have $ x_1> a^n$.

can $n$ be equal to $2$ ? ( $x_1=1$ and $x_2=2$ implies $a=1$)

What about $x_1=1,x_2=2,x_3=3$? The estimate needs to be more complicated than you stated.

Sorry, indeed, we must assume that $x_1>1$.

But then we can choose $x_1=2,x_2=4,x_3=6$.Are you sure that we don't need any additon? :?

So what, in this case $ a=\sqrt[10]{2}$ works very well. I don't understand your question.

I'm sorry,I thought $a\in\mathbb N$ :blush: .Nice looking-problem!

Here's a solution:

Step 1: Since $x_k-x_1|2x_1$ for all $k$, $x_n\le3x_1.$
Step 2: For each integer $m,$ at most two of the $x_k$ can be divisible by $3^m$ but not by $3^{m+1}.$ If two of the $x_k$ are congruent mod $3^{m+1},$ both must be divisible by $3^{m+1}.$

If $n=2m+1$, there is at least one $x_k$ which is divisible by $3^m$ and hence greater than or equal to $3^m.$ If $n=2m+2,$ there are at least two $x_k$ divisible by $3^m$ and therefore one is at least $2\cdot3^m.$ Combining these two cases, $x_n\ge3^{\frac{n-1}2}.$ Using the inequality in the first step, $x_1\ge3^{\frac{n-3}2}.$
Since we restrict to cases where $x_1\ge2$, we ignore all $n\le3.$ For $n\ge4,$ $n-3\ge\frac n4,$ so $x_1\ge\sqrt[8]{3}^n.$ Equality is only possible for $n=4$; since $2>\sqrt{3}$ this does not occur.

The maximal $a$ for which $x_1\ge a^n$ is in fact $\sqrt[4]{2}$. We can show that for $n\ge5$, $x_1\ge3^{\frac n5}$, and $\sqrt[5]{3}>\sqrt[4]{2}.$ For $n=4,$ we have the example $2,3,4,6.$

Jmerry's nice ideas can be used to prove a stronger lower bound $x_1\geqslant e^{cn\ln n}$ for some $c>0$. To prove it, one has to run jmerry's argument for all primes $p$ between $3$ and $n/2$. The result is that there are not more than $p-1$ numbers not divisible by $p$, not more than $p-1$ numbers divisible by $p$ but not by $p^2$ and so on. So, the average power of $p$ in $x_j$ is at least $c\frac n{p}$. Thus, there exists at least one $x_j$ that is not less than
$\prod_{p\text{ prime},3\leqslant p\leqslant n/2}p^{c n/p} =\exp\left\{cn\sum_{p\text{ prime},3\leqslant p\leqslant n/2}\frac{\ln p}p\right\}$ but the last sum is known to be approximately $\ln n$. Since all $x_j$ must be the same up to a factor not exceeding $3$, the inequality follows for large $n$. I don't know whether this new lower bound is the best possible one.


Find all pairs of prime numbers $ (p,q)$ such that the number $ (p\plus{}1)^q$ is a perfect square.

If $ q\equal{}2$ then the number $ (p\plus{}1)^q$ is always a square for every $ p$. If $ q>2$ then $ (p\plus{}1)^q$ is a perfect square only if $ p\plus{}1$ is a perfect square (remenber that $ q$ is odd): $ p\plus{}1\equal{}n^2$, namely $ p\equal{}n^2\minus{}1$, $ p\equal{}(n\plus{}1)(n\minus{}1)$. Since $ p$ must be prime, $ n\minus{}1\equal{}1$ and $ n\equal{}2$ and $ p\equal{}3$. Thus, the solutions are $ (\forall p,2)$ and $ (3,\forall q)$.


Is there a fast way to do this problem without actually graphing the lines?
(If not please still give a solution.)

Planet Nowt and Sonemenid have two-dimensional orbits, described by the equations x squared + y squared= 1296 and x squared +y squared= 4225, respectively. How many more units does planet Sonemenid travel than plant Nowt in one orbit.

[hide="Hint"]
Remember, $x^2+y^2=r^2$ describes a circle centered at the origin with radius $r$.
[/hide]

[hide]They're equations of circle. $x^2+y^2=a^2$ where a is radius.

radius of Nowt: $\sqrt{1296}=36$

radius of Sonemenid: $\sqrt{4225}=65$

circumference of Nowt orbit$=72\pi$

circumference of Sonemenid orbit$=130\pi$

$130\pi-72\pi=58\pi$[/hide]

Haha this did some "WAKE UP" to me. I thought i was messing with an linear equation


I wonder when the equality occurs. It seems that you use analytic tools to get the inequality.


trigonometry
inequalities
algebra
polynomial
function
combinatorics proposed
combinatorics

Prove that
$ \sum_{k\geq 0}\binom{2n}{k}f_{2k}\equal{}5^nf_{2n}$
Where $ f_{0}\equal{}f_1\equal{}1$ and $ f_{n\plus{}1}\equal{}f_n\plus{}f_{n\minus{}1}$

\begin{eqnarray*}
(\cos \theta + 1 + i \sin \theta)^n
& = & (1 + e^{i\theta})^n \\
& = & \sum_{k=0}^n\binom{n}{k}e^{ik\theta} \\
& = & \sum_{k=0}^n\binom{n}{k}\cos k\theta + i\sum_{k=0}^n\binom{n}{k} \sin k\theta
\end{eqnarray*}

Let, $ x=2\cos \theta$,
\[ (x+2+\sqrt{x^2-4})^n = 2^{n-1}\left( \sum_{k=0}^n\binom{n}{k} t_k(x) + \sqrt{x^2-4}\sum_{k=0}^n\binom{n}{k}u_{k-1}(x)\right).\]

$ \left(\begin{array}{l}
t_n(x)=2T_n\left( \frac{x}{2} \right), u_n(x)=U_n\left( \frac{x}{2} \right) \\
\text{and} \\
T_n(x): \text{Chebyshev Polynomial of the First Kind}, \\
U_n(x): \text{Chebyshev Polynomial of the Second Kind}
\end{array}\right)$

And let $ x=3$,
\begin{eqnarray*}
2^{n-1}\left( \sum_{k=0}^n\binom{n}{k} L_{2k} + \sqrt{5}\sum_{k=0}^n\binom{n}{k} F_{2k} \right)
& = & (5+\sqrt{5})^n \\
& = & \left(2\sqrt{5} \cdot \frac{1+\sqrt{5}}{2}\right) \\
& = & 2^n \cdot (\sqrt{5})^n \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n \\
& = & 2^n \cdot (\sqrt{5})^n \cdot \frac{L_{n} + \sqrt{5}F_{n}}{2}
\end{eqnarray*}

Thus,
\[ \sum_{k=0}^n\binom{n}{k} L_{2k}
=\left\{\begin{array}{ll}
5^{n/2}L_{n} & \text{(n: even)} \\
5^{(n+1)/2}F_{n} & \text{(n: odd)}
\end{array}\right.\]

\[ \sum_{k=0}^n\binom{n}{k} F_{2k}
=\left\{\begin{array}{ll}
5^{n/2}F_{n} & \text{(n: even)} \\
5^{(n-1)/2}L_{n} & \text{(n: odd)}
\end{array}\right.\]
And,
\[ \sum_{k=0}^n\binom{n}{k} L_{k^2}
=\left\{\begin{array}{ll}
5^{n/2}L_{n} & \text{(n: even)} \\
5^{(n+1)/2}F_{n} & \text{(n: odd)}
\end{array}\right. \ \left(\because \ L_{2n} = L_{n}^2+(-1)^{n-1}2, \ \sum_{k=0}^n\binom{n}{k}(-1)^k = (1-1)^k = 0\right)\]

\[ \sum_{k=0}^n\binom{n}{k} F_{k}^2
=\left\{\begin{array}{ll}
5^{(n-2)/2}L_{n} & \text{(n: even)} \\
5^{(n-1)/2}F_{n} & \text{(n: odd)}
\end{array}\right. \ \left(\because \ L_{n}^2 = 5F_{n}^2+(-1)^n 4\right)\]

Let $ F(x) \equal{} \sum f_{2k} \frac {x^k}{k!} \equal{} \frac {e^{\phi^2 x} \minus{} e^{\varphi^2 x}}{\phi \minus{} \varphi}$.  The generating function of the desired sequence is (see the lemma [url=http://www.artofproblemsolving.com/Forum/weblog.php?w=634]here[/url])

$ e^x F(x) \equal{} \frac {e^{ (\phi^2 \plus{} 1)x} \minus{} e^{(\varphi^2 \plus{} 1)x} }{\phi \minus{} \varphi}$.

Now note that $ \phi^2 \plus{} 1 \equal{} \phi \plus{} 2 \equal{} \sqrt {5} \phi$ and the same for $ \varphi$ and we have our result.

Edit:  I'd be interested in a combinatorial proof using tilings, though.


geometry
trapezoid
combinatorial geometry
circles
IMO Shortlist

- Let $ \omega_1$ and $ \omega_2$ be the given circles and $ w$ is tangent to $ \omega_1$,$ \omega_2$ at $ B,A$,respectively.Note that $ w$ is tangent either internally,or externally to both of $ \omega_1$ and $ \omega_2$,otherwise it can not be intersected by $ XY$.Suppose that $ w$ is externally tangent to $ \omega_1$ and $ \omega_2$. Denote intersection points of $ XY$ with $ w$,as $ C$ and $ D$,such that $ D$ lies between $ l_1$ and $ l_2$ and $ C$ doesn't lie there and distance between $ C$ and $ l_2$ is greater than distance between $ C$ and $ l_1$.Let $ K\in DB\cap\omega_1$,$ N\in DA\cap\omega_2$,$ M\in CA\cap\omega_2$ and $ L\in CB\cap\omega_1$.Now if we prove that  $ KN$ and $ LM$ are common tangent lines to $ \omega_1$ and $ \omega_2$,we will be done.
-Consider the homothety with center at $ B$,which turns $ w$ to $ \omega_1$.Then obviously $ D\rightarrow K$ and $ C\rightarrow L$,thus $ KL\| CD$.As we know $ CB\cdot CL \equal{} CX\cdot CY \equal{} CA\cdot CM$,hence quadrilateral $ CBLM$ is cyclic,so $ \widehat{MLB} \equal{} \widehat{BAC} \equal{} \widehat{LKB}$.From where we conclude that $ LM$ is tangent to $ \omega_1$.In similar way we prove that $ LM$ is also tangent to $ \omega_2$,so $ LM$ and $ KN$ are common tangent lines to $ \omega_1$ and $ \omega_2$ and obviously $ K,L,M,N$ are fixed points.So we are done.
-The case when $ w$ is internally tangent to $ \omega_1$ and $ \omega_2$ is totally similar to the previous case.

I want to understand your solution and I don't understand who's $ l_1$ and $ l_2$. Please answer me !

Here's a fix for the typos (I think this solution is the same?)
Let CA intersect the circle tangent at A again at E, CB intersect the other circle again at F. Let BA intersect the circle containing E again at B'. EB'A ~ CBA, so mABC=mEB'A. C is on the radical axis of the 2 circles, so EABF is cyclic, and we have mABC=mFEA, and EF is a tangent to the circle containing E.

Applying the same argument 4 times over, or extending DA, DB and taking note of the chords being parallel to the radical axis gives us that the given lines intersect the 2 circles at the points of tangency of the common tangents.

Too many circles. Invert!

Invert about a circle centered at X. Then the the two circles intersecting at X become lines intersecting the radical axis at Y.

Easy to show that AC always makes the same angle with the radical axis since A,B,C,D move uniformly with the circle, so then we can easily construct one of our points P so as to make a trapezoid XPAC, where P lies on what is now the inverted first circle. Then XPAC is cyclic, and is always cyclic, corresponding to the desired condition in the original diagram. Repeat with the other 3 lines/circles in the inverted diagram, and we have the result.

Hm... 90% perspiration (drawing the diagram :P), 10% inspiration (oh yeah, the four points obviously are the common tangents' tangency points :D)

Let $MN$ be a common tangent of the two given circles $\omega_1$ and $\omega_2$, and call $\omega$ the third circle. Homotheties taking $\omega_1$, $\omega_2$ to $\omega$ take $M, N$ to $D_1, D_2$ respectively and $MN$ to a tangent of $\omega$ parallel to $MN$, $l$. Because there is only one such tangent $l$, we have $D_1 = D_2$.

If $F$ is a point on $l$ such that $\angle MND = \angle NDF$, then incidentally $\angle D_1 AB = \angle ND_1 F$, so $MNBA$ is cyclic. Thus $D_1$ lies on $XY$ by radical axis theorem, so $D_1 = D$ or $C$. Similar result holds for other common tangent.

[hide=Solution]
We claim that the four points are the tangency points of the two common external tangents with each circle.

Let \(H=AC\cap \omega_1\), \(I=BC\cap \omega_2\), \(F=AD\cap \omega_1\), \(G=BD\cap \omega_2\). We show that \(HI\) and \(FG\) are the common external tangents.

First note that due to homothety, \(IG\), \(HF\) and \(CD\) are parallel. Now, observe that
\begin{align*}
\measuredangle GFH &= \measuredangle AFH + \measuredangle GFD \\
&= \measuredangle ADC + \measuredangle DBA \\
&= \measuredangle ABC + \measuredangle DBA \\
&= \measuredangle DAC = \measuredangle FAH \\
\end{align*}
so that \(FG\) is tangent to \(\omega_1\). We can similarly prove the other tangencies, so we are done.
[/hide]

[hide=Solution][quote=ISL 2000 G1]In the plane we are given two circles intersecting at $ X$ and $ Y$. Prove that there exist four points with the following property:

(P) For every circle touching the two given circles at $ A$ and $ B$, and meeting the line $ XY$ at $ C$ and $ D$, each of the lines $ AC$, $ AD$, $ BC$, $ BD$ passes through one of these points.[/quote]
[b][color=#000]Solution:[/color][/b] Let the given circles be $\omega_1, \omega_2$. Define: $AC \cap \omega_1$ $=$ $K$, $BC $ $\cap$ $ \omega_2$ $=$ $L$, $BD$ $\cap$ $\omega_2$ $=$ $M$ and $AD$ $\cap$ $\omega_1$ $=$ $N$
--------------------------------------------------
By Homothety at $A,B$, $NK||XY||LM$ and using the fact that $KABL$ is cyclic ($\because CA \times CK=CX \times CY$ $=$ $CB$ $\times$ $CL$),
$$\angle AKL=\angle CBA=\angle CDA=\angle CNK$$
And similarly $\angle BLK=\angle BML$ $\implies$ we get $KL$ is the common tangent of $\omega_1, \omega_2$. Similarly, show $MNAB$ is cyclic and using this $\angle MNA=\angle AKN$ & $\angle NMB=\angle MLB$ $\implies$ $MN$ is the other common tangent of $\omega_1,$ $\omega_2$. Hence, as a result $M,N,K,L$ are fixed $\qquad \blacksquare$
[/hide]

No one has posted a diagram yet so I'll post mine(my solution uses the same ideas):

[asy]
size(10cm);
path circ1, circ2, dcirc1, dcirc2, circ, radaxis;
real r1=5, r2=4.2, h=2, r=3.8, e=.7;
pair O1= (-sqrt(r1^2-h^2),0), O2=(sqrt(r2^2-h^2),0);
circ1=circle(O1,r1);
circ2=circle(O2,r2);
dcirc1=circle(O1,r1+r);
dcirc2=circle(O2,r2+r);
pair [] x=intersectionpoints(circ1, circ2);
radaxis=(0,10^7) -- (0,-10^7);
pair [] z=intersectionpoints(dcirc1, dcirc2);
circ=circle(z[1],r);
pair A=r1*dir(z[1]-O1)+O1, B=r2*dir(z[1]-O2)+O2;
pair [] c=intersectionpoints(radaxis, circ);
pair H=(r1*O2-r2*O1)/(r1-r2);
pair M1=conj((O1-H)^2/(O1+(0,r1)-H))+H, M2=conj((O2-H)^2/(O2+(0,r2)-H))+H;
pair N2=(O2-H)^2/(O2+(0,r2)-H)+conj(H), N1=(O1-H)^2/(O1+(0,r1)-H)+conj(H);
draw(circ1); draw(circ2); draw(x[0]+(0,e) -- c[1]-(0,e),mediumred); draw(circ,heavyblue); draw(M1--M2,heavygray); draw(N2--N1,heavygray);
draw(M1--c[1]--M2,heavygreen); draw(N1--c[0]--N2,heavygreen);
draw(circumcircle(A,B,M1),dashed+heavycyan);
dot("$A$", A, 1.5*dir(80)); dot("$B$", B, 1.5*dir(110)); dot("$C$", c[0], dir(310)); dot("$D$", c[1], dir(220)); dot("$X$", x[0], dir(165)); dot("$Y$", x[1], dir(190)); dot("$O$", z[1], dir(60)); dot("$M_1$", M1, dir(120)); dot("$N_1$", N1, dir(260)); dot("$M_2$", M2, dir(40)); dot("$N_2$", N2, dir(300));
[/asy]

Call the two original circles $\omega_1$ and $\omega_2$, with $A$ on $\omega_1$ and $B$ on $\omega_2$. Let $M_1$ be the second intersection of $\overline{AD}$ with $\omega_1$, and let $M_2$ be the second intersection of $\overline{BD}$ with $\omega_2$. Define $N_1$ and $N_2$ analogously, with point $D$ replaced with point $C$.

Since $A$ is the center of the homothety with negative scale factor sending $\omega$ to $\omega_1$, and this homothety sends $\overline{CD}$ to $\overline{N_1M_1}$, $\angle ACD=\angle AN_1M_1$. Notice that $\overline{XY}$ is the radical axis of $\omega_1$ and $\omega_2$, so $DA\cdot DM_1=DB\cdot DM_2$ and it follows that quadrilateral $ABM_2M_1$ is cyclic. Thus,
$$\angle M_2M_1A=\angle ABD=\angle ACD=\angle AN_1M_1,$$
so $\overline{M_1M_2}$ is tangent to $\omega_1$. We can repeat this three times to find $\overline{M_1M_2}$ and $\overline{N_2N_2}$ are tangent to $\omega_1$ and $\omega_2$, so points $M_1$, $M_2$, $N_1$, and $N_2$ are fixed. These are the desired four points and we are done. (This is another configuration where the circles are internally tangent, but the same proof still holds.)

Let $\omega_1, \omega_2$ be the names of the two circles with $A$ corresponding to $\omega_1$ and $B$ corresponding to $\omega_2$. Let $E$ and $F$ be the intersection of $BD$ and $BC$ respectively with $\omega_2$. Lastly, let $O_1,O_2,O_3$ be the centers of $\omega_1,\omega_2,$ and the circle tangent to both, respectively. We claim that $E$ and $F$ are fixed, this will solve the problem because we can apply a similar thing to the other two points.

Notice that by homothety triangles $CBD$ and $FBE$ are similar, and we get that $CD\parallel FE$. In addition, by [url=https://artofproblemsolving.com/community/c5h2484038p20872596]2021 AIME I #13[/url], we get that given the two circles $\omega_1$ and $\omega_2$, the angle $\angle CO_3D$ is fixed, which means that by homothety, the angle $\angle EO_2F$ is fixed. Therefore minor arc $FE$ of $\omega_2$ is fixed. Combined with the parallel condition and the fact that $E$ and $F$ lie on $\omega 2$, this proves that $E$ and $F$ are fixed, and we are done.

Let our circles be $\omega_1$ and $\omega_2$ and their common tangents touch them at point's $S,T$ and $K,M$ respectively. Let common tangents meet at $P$.

Step1 : $SKBA$ is cyclic.
By Homothety of circles $\omega_1$ and $\omega_2$ we have $SK$ and $AB$ both meet at $P$ and $\angle PBK = \angle PSA$.

Step2 : $C,A,S$ and $C,B,K$ are collinear.
Let tangents to $\omega_1$ and $\omega_2$ at $A$ and $B$ meet at $Q$.
$\angle QAC = \angle ABC = \angle ASK \implies C,A,S$ are collinear.
$\angle QBC = \angle BAC = \angle BKS\implies C,B,K$ are collinear.

So now we have $S$ and $K$ are two of those 4 points and same way we can prove $T$ and $M$ are other points.
we're Done.

Thought inversions first, but unforunately don't know how inversions work.

[img width=50]https://media.discordapp.net/attachments/925784397469331477/949510510099988540/Screen_Shot_2022-03-04_at_8.35.30_PM.png?width=1602&height=1170[/img]

Let the two given circles be $S_1,S_2,$ with the new circle $C$ touching $S_1,S_2$ at $A,B$ respectively. Let $C$ be closer than $D$ to $Y.$ Let $CA$ intersect $S_1$ at $E,$ $CB$ intersect $S_2$ at $F,$ $DA$ intersect $S_1$ at $G$ and $DB$ intersect $S_2$ at $H.$ We claim that $EF,GH$ are always the common tangents.Note that since $C,D$ are on the radical axis of $S_1,S_2,$ $ABFE$ and $ABHG$ are cyclic quadrilaterals.

Thus $\angle GEA=\angle DCA$ (famous lemma, to prove use homothety about $A$) and so $\angle DCA=\angle DBA=\angle HGA,$ so $HG$ tangent to $S_1$ Similarly, $GH$ tangent to $S_2.$

On the other hand, $\angle BHF=\angle CDB=\angle CAB=\angle CFB$ so $EF$ tangent to $S_2,$ and similarly to $S_1,$ as desired.

Let $\measuredangle$ denote a directed angle.
Let $\omega_1, \omega_2$ be the original two circles and let $\omega$ be a circle that is tangent to them at $A, B$ respectively. We claim that the four distinct points $P_1, P_2, P_3, P_4$ such that $P_1P_2$ and $P_3P_4$ are each tangent to both $\omega_1$ and $\omega_2$ satisfy the problem statement.

Let $C$ be an intersection of $XY$ and $\omega$. Let $A'$ be the second intersection of $AC$ with $\omega_1$ and let $B'$ be the second intersection of $BC$ with $\omega_2$. (Note that $CA$ cannot be tangent to $\omega_1$ at $A$, since then it would have to tangent to $\omega$ as well.) We claim $A'B'$ is tangent to $\omega_1$ and $\omega_2$ at $A'$ and $B'$.

Because $C$ is on the radical axis of $\omega_1$ and $\omega_2$, $CA\cdot CA'=CB\cdot CB'$. Therefore, $AA'BB'$ is cyclic. So, we have $\measuredangle B'A'A=\measuredangle B'BA=\measuredangle CBA$. Similarly, $\measuredangle A'B'B=\measuredangle CAB$.

Let $O$ be the radical center of the three circles. Note $OA$ is tangent to $\omega_1, \omega$ and $OB$ is tangent to $\omega_2, \omega$.  So, we have $\measuredangle CAO=\measuredangle CBA=\measuredangle B'A'A$. Let $P$ be a point on $\omega_1$ not equal to $A$ or $A'$. Since $OA$ is tangent to $\omega_1$, we have $\measuredangle A'PA=\measuredangle A'AO=\measuredangle CAO=\measuredangle B'A'A$. Since $\measuredangle A'PA=\measuredangle B'A'A$, we know $A'B'$ is tangent to $\omega_1$ at $A'$. By the same logic $A'B'$ is tangent to $\omega_2$ at $B'$. Thus $A', B'\in\{P_1, P_2, P_3, P_4\}$, which completes the proof since $CA$ and $CB$ pass through $A'$ and $B'$, respectively.

Does this work? Not sure if I fakesolved.

Consider the diagram as shown below. I claim that the four points $E$, $F$, $G$, and $H$ which we require are the four points which are the intersections of the two external tangents of the circles, which we call $\omega_1$ and $\omega_2$. Also, define $M$ to be the intersection of $XY$ and $GH$. Obviously $A$, $B$, $G$, and $H$ are concyclic which means that $$\measuredangle DCA=\measuredangle DBA=\measuredangle HGD$$ which implies that $A$, $C$, $M$, and $G$ are concyclic. By Reim's Theorem, $CD\parallel EG$, which implies that $$\measuredangle HGA=\measuredangle DCA=\measuredangle GEA$$ so that $GH$ is tangent to $\omega_1$. The final result immediately follows. $\blacksquare$

this is extremely similar to 2021 aime i 13 and actually trivializes it (angle between external tangent and line connecting centers is 30 degrees)
very nice

Let $\odot (AXY)$ meets rays $AC,AD$ again at $P,Q$ and $\odot (BXY)$ meets $BC,BD$ again at $R,S.$ Since $C$ lies on radical axis of given circles, points $A,B,P,R$ are concyclic, so by Reim's theorem $\overline{PR}$ is parallel to tangent to $\odot (ABC)$ at $C.$ Thus by homothety $PR$ is tangent to $\odot (AXY),\odot (BXY),$ which yields that points $P,R$ (and similarly $Q,S$) are fixed.


[quote="Kent Merryfield"]$\sqrt{x}$ makes no sense for $-2\le x\le-1.$[/quote]

it is 3 sq.rt of X  or 1/3X

Maybe s/he means $\sqrt[3]{x}$? In which case you just divide through and integrate term by term.

[quote="jmerry"]If that's the case- it's an improper integral. Don't blindly integrate across a singularity.[/quote]

I don't follow. Where is the singularity in $\frac{x^{2}-x+3}{\sqrt[3]{x}}$ for $-2 \le x \le-1$?


function
analytic geometry
LaTeX
factorial
algorithm
induction
floor function

Like in the numbertheory section,zetax,mathmanman,etc have made a collection of all theorems and formulas,any such thing here?

Calatan numbers:

$C_n = \frac{\binom{2n}{n}}{n+1}$
$C_0 = 1, C_n = C_0C_{n-1}+C_1C_{n-2}+C_2C_{n-3}+...+C_{n-1}C_0$
$C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, C_6 = 132$

Bijections of catalan: number of ways to draw diagonals of polygon without crossing, number of ways to fully parenthesize expression, number of paths along a line never going behind starting point and ending at starting point.

Graphs:

A graph is Eulerian iff every node has in-degree equal to out-degree, or if by drawing one extra edge we can make this so.

In an undirected graph, the condition of even degree for each node is equivalent.

So can we start a collection of all formulas,like done for number theory [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=76610]here[/url]

I hope i get lots of cooperation,it'll be pretty cool(if its okay with pbornsztein,megus adn the other mods  :) )

Let $f$ be a function from $S$ finite to $T$ finite.
We then have :
\[ |f(S)| \le \min{(|S|,|T|)}. \]
[i]In particular, if $f$ is injective $|S| \le |T|$; if it's surjective $|T| \le |S|$ and if it's bijective $|S| = |T|$.[/i]

The number of ways to go from $(0, 0)$ to $(m, n)$ through a path where, in each step, one of the coordinates increases from one unity is :
\[ \binom {m+n}m = \binom {m+n}n. \]

The number of sub-sets with $k$ elements of $\{1, 2, \ldots, n\}$ which does not contain consecutive integers is :
\[ \binom {n+1-k}k. \]

Elementary ones...

[b]Sum Of Numbers Formed by n non-zero digits[/b]

$=(Sum\ of\ digits)(n-1)!(\frac{10^n-1}{10-1})$

[b]Exponent Of PRIME p In n![/b]
[i]Let[/i] $E_p(n)$ [i]denote the exponent of the prime[/i] $p$ [i]in the positive integer[/i] $n$.Then,

$E_p(n!)=[\frac{n}{p}]+[\frac{n}{p^2}]+\cdots+[\frac{n}{p^s}]$

where $s$ is the largest positive integer such that $p^s\leq n \leq p^{s+1}$

[b][size=150]SELECTION OF ONE OR MORE ITEMS[/size][/b]

[b]Selection from different items[/b]
[i]The number of ways of selecting one or more items from a group of[/i] $n$ [i]distinct items is  [/i]$2^n-1$

[b]Selection from identical items[/b]

[i]The total number of selections of some or all out of[/i] $p+q+r$

[i]items where [/i]$p$ [i]are alike of one kind[/i],$q$ [i]are alike of

second kind and rest are alike of third kind is[/i]

$[(p+1)(q+1)(r+1)]-1$

[b][size=150]DIVISION OF ITEMS INTO GROUPS[/size][/b]

[b]Division of items into groups of unequal size[/b]

[i]The number of ways to distribute [/i]$(m+n+p)$ [i]items among

[/i]$N$ [i]persons in the groups containing [/i]$m,n$ and $p$ [i]items is[/i]

$\frac{(m+n+p)!}{m!n!p!}*N!$

[b]Division of items into groups of equal size[/b]

[i]The number of ways in which[/i] $mn$ [i]different items can be

divided equally into[/i] $m$ [i]groups,each containing [/i]$n$ [i]

objects and the order of the groups is not important is[/i]

$(\frac{(mn)!}{(n!)^m})\frac{1}{m!}$

when order of groups is important

$\frac{(mn)!}{(n!)^m}$

A friend and I wrote up two lecture-type thingies with a whole lot of formulas. Unfortunately most of the formatting is lost here, so if someone wants to tell me how to get the LaTeX code to be interpreted, I shall be very happy.

Here they are (from http://www.tjhsst.edu/~dschafer/VMT/CombTut/CombTutExpl.pdf and http://activities.tjhsst.edu/vmt/arml-lectures/2006/11a-advancedcombolecture.pdf):

\begin{enumerate}

\item How many ways can one arrange the elements of a set of size $n$?

\par \fbox{$\displaystyle n!$}
\par You can place the first element in any of $n$ places. You can place the second element in any of $n-1$ places. You can place the $k$th element in any of $n-k+1$ places. Thus there are a total of $n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 3 \cdot 2 \cdot 1 = n!$ possibilities.

\item How many ways can one choose $k$ out of $n$ items (order does matter)?

\par \fbox{$\displaystyle \frac{n!}{(n-k)!}$}
\par Use the same argument as before, except stop just before the $k+1$st element. Then you get $n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}$ possibilities.

\item How many ways can one choose $k$ out of $n$ items (order doesn't matter)?
\par \fbox{$\displaystyle \frac{n!}{k!(n-k)!}$}
\par This is the definition of combination, so it is clearly ${n \choose k} = \frac{n!}{k!(n-k)!}$.  This can be easily  derived; there are $n$ choices for the first item, $(n-1)$ for the second, until eventually there are $(n-(k-1))$ for the  $k$th.  However, there are $k!$ orderings of these $k$ items, there must be $\frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!}$ total combinations.

\item How many sequences $a_1,a_2,\ldots,a_k$ of positive integers exists such that $a_i < a_{i+1} \leq n$?
\par \fbox{$\displaystyle {n \choose k}$}
\par Clearly, each of the $a_i$ is distinct.  Also, given any $k$ distinct  numbers, there will be exactly $1$ sequence of $a_i$  with those $k$ numbers in it that satisfies the requirement.  This creates a  bijection\footnote{An over-simplified explanation of a bijection is that it is a one-to-one relationship between two sets created by a function.  Their main use  in combinatorics is that the sizes of the two sets must be the  same, so if one set's size is known, both sizes are known.} between sequences $a_1,\ldots,a_k$ and sets of $k$ numbers chosen from the numbers  $1$,$2$,\ldots,$n$.  The number of sets for the latter is clearly ${n \choose k}$, so there are ${n \choose k}$ such sequences.

\item How many ways can $n$ distinct items be partitioned into $k$ groups?
\par \fbox{$\displaystyle n^k$}
\par Consider each item individually.  For each item, there are $k$ options of what group to put it in.  There are $n$ such choices, each of which is independent, so there are $n^k$ ways to perform the partition.

\item How many ways can one travel from $(0,0)$ to $(x,y)$ traveling only to the right and up and only between adjacent lattice points.
\par \fbox{$\displaystyle {{x+y} \choose x}$}
\par Consider representing each path with a list of what direction was travelled, either right (R) or up (U).  Clearly, any path can be  represented by a distinct arrangement of the sequence $RR\cdots RUU \cdots U$,  where there are $x$ $R$s and $y$ $U$s.   This creates a bijection, so the number of paths is the same as the number of arrangements, which is ${{x+y} \choose x}$.

\item How many ways can $n$ distinct items be partitioned into $k$ groups of sizes $s_1,s_2,\ldots,s_k$, where $s_1+\ldots+s_k = n$?
\par \fbox{$\displaystyle \frac{n!}{s_1!s_2!\cdots s_k!}$}
\par Consider selecting each group seperately.  For the first group, there are  ${n \choose s_1}$ options, for the second,  ${{n-s_1} \choose s_2}$, etc.   Multiplying these out, there is a total of ${n \choose s_1}{{n-s_1} \choose s_2}{{n-s_1-s_2} \choose s_3}\cdots = \frac{n!}{s_1!s_2!\cdots s_k!}$.   This value is often expressed as ${n \choose {s_1,s_2,\ldots,s_k}} = \frac{n!}{s_1!s_2!\cdots s_k!}$, and is refered to as \textit{multinomial}  coefficients.  Note that these have a relationship  with the term  $a_1^{s_1}\cdots a_k^{s_k}$ in the expansion of $(a_1+\ldots+a_k)^n$  similar to that of binomial coefficients  to the expansion of $(x+y)^n$.  Also note that if $s_1+\ldots+s_k < n$, one can add a pseudo-set $s_{k+1}$ which contains all of the items not in any of the first $k$ sets (so its size will be $n-(s_1+\ldots+s_k)$), and calculate the coefficient from there.  Note that this value is also the number of ways to arrange $n$ objects in $k$ indistinct groups of sizes $s_1, s_2, \ldots, s_k$, where the sizes again sum to $n$.

\item Simplfify $\binom{n}{k}+\binom{n}{k+1}$.
\par \fbox{$\displaystyle \binom{n+1}{k+1}$}
\par \textbf{Method one}.  Writing out the factorial notation and simplifying quickly yields the desired reuslt.  $\frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!} = \frac{n!(k+1)}{(k+1)!(n-k)!} + \frac{n!(n-k)}{(k+1)!(n-k)!} = \frac{n!(n+1)}{{(k+1)!(n-k)!}} = \binom{n+1}{k+1}$.  This is the basis of Pascal's Triangle.
\par \textbf{Method two}.  Consider selecting $k+1$ items from $n+1$.  Either the first item is chosen, in which case there are $\binom{n}{k}$ ways to select the remaining $k$, or the first item is not chosen, in which case there are $\binom{n}{k+1}$ ways to choose the remaining $k+1$.  Thus, $\binom{n+1}{k+1} = \binom{n}{k}+\binom{n}{k+1}$.

\item Simplfify $\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n-1}+\binom{n}{n}$.
\par \fbox{$\displaystyle 2^n$}
\par This can be derived easily by counting in two ways.  This is the total number of subsets of a set of size $n$; for each element of the original set, there are two options: in the set, or not in the set.  Thus, there are $2^n$ subsets, and the expression above simplifies to $2^n$.

\item How many positive integer solutions exist to the system $a_1 + a_2 + \ldots + a_k = n$?
\par \fbox{$\displaystyle {{n-1} \choose {k-1}}$}
\par Draw $n$ circles in a row, and consider drawing $k-1$ lines in the $n-1$  gaps between the circles.  Let $a_1$ be the number  of circles before the  first line, $a_2$ be the number of circles between the first and second  lines, etc.  Clearly, there  will be $k$ total $a_i$ (if there are $k-1$  lines), all $a_i$ will be at least $1$ (since there is at least $1$ circle   between each gap) and the sum of the $a_i$ will be $n$ (since each circle  is counted exactly once).  Thus, there is a  bijection between the sequence  $a_1,\ldots,a_k$ and the drawing; as the drawing was generated by choosing  $k-1$ lines from  $n-1$ gaps, there are ${{n-1} \choose {k-1}}$ drawings,  and thus ${{n-1} \choose {k-1}}$ sequences.  This algorithm is  sometimes  refered to as ``Stars and Bars.''

\item How many non-negative integer solutions exist to the system $a_1 + a_2 + \ldots + a_k = n$?
\par \fbox{$\displaystyle {{n+k-1} \choose {k-1}}$}
\par Draw $n+k-1$ circles in a row, and cross out $k-1$ of them.  Let $a_1$ be  the number of circles before the first crossed-out  one, $a_2$ be the number  of circles between the first crossed-out one and the second crossed-out  one, etc.  Clearly, there  will be $k$ total $a_i$ (if there are $k-1$  crossed out circles), all $a_i$ will be at least $0$ (since there may be  two  consecutive crossed-out circles) and the sum of the $a_i$ will be $n$  (since each remaining circle is counted exactly once,  and there are  $(n+k-1)-(k-1)=n$ remaining circles).  Thus, there is a bijection between  the sequence $a_1,\ldots,a_k$ and  the drawing; as the drawing was generated  by choosing $k-1$ circles from $n+k-1$ choices, there are ${{n+k-1} \choose {k-1}}$ drawings, and thus ${{n+k-1} \choose {k-1}}$ sequences.  Note that  this algorithm can be used to determine the  number of ways to partition $n$  indistinct objects into $k$ sets.

\item How many integer solutions exist to the system $a_1 + a_2 + \ldots + a_k = n$ if $a_i > m$?
\par \fbox{$\displaystyle \binom{n-km-1}{k-1}$}
\par \textbf{Method one}.  Use algebraic manipulation. Subtract $km$ from both sides, so that now we have $b_1 + b_2 + \ldots + b_k = n-km$ with $b_i > 0$ (we subtracted $m$ from each of the $a_i$'s). Now apply the previous argument and arrive at $\binom{n-km-1}{k-1}$.
\par \textbf{Method two}.  Use a bijection. This is the same as dividing up a set of size $n$ into $k$ groups, all of size greater than $m$. But this means we can remove $m$ items from each group and still have a positive number of items in each group, yielding a scenario in which we divide up the set of size $n-km$ into $k$ non-empy groups. Also, for every scenario with this smaller set we can add $m$ items to each group to get back to what we had in the larger set. This means there is a one-to-one correspondence between the number of possibilities in both cases. We count the easier quantity (the set of size $n-km$). To ensure that all sets are non-empty, we simply place $k-1$ dividing lines between elements of the set to divide the set into $k$ subsets. There are $\binom{n-km-1}{k-1}$ ways to do this, as there are $n-km-1$ spaces between successive elements of the set.

\item How many ways can one arrange $n$ of one object and $k$ of another if none of the $k$ objects may be next
to each other?
\par \fbox{$\displaystyle {{n+1} \choose k}$}
\par First, lay out the first objects in a row of length $n$.  There are now $n+1$ gaps to place the $k$ other objects in (there are $n-1$ gaps between the layed-out objects and $1$ on both ends of the row).  Thus, there are ${{n+1} \choose k}$  arrangements of these objects to avoid having any of  the $k$ objects touch each other.

\item How many ways can one place $k$ indistinct items between $n$ other indistinct items? (Any number of the
first type can go between the sucessive items of the second type).
\par \fbox{$\displaystyle {{n+k-2} \choose {k}}$}
\par Draw $n+k$ circles in a row, and mark $k$ of them as objects of the second  type.  Clearly, one cannot mark either the first  or the last, as the  problem specifies that the second objects go between objects of the first  type.  Thus, there are  $n+k-2$ markable objects, and $k$ marks, so there  are ${{n+k-2} \choose {k}}$ arrangements.

\item Simplify $\binom{n}{0}+\binom{n+1}{1}+\ldots+\binom{n+k}{k}$.
\par \fbox{$\displaystyle \binom{n+k+1}{k}$}
\par The proof of this is trivial by induction.  The base case is $k=1$, and it is clear that $\binom{n}{0}+\binom{n+1}{1}=1+n+1 = \binom{n+2}{1}$.  For the induction, $\binom{n}{0}+\binom{n+1}{1}+\ldots+\binom{n+k-1}{k-1}+\binom{n+k}{k} = \binom{n+k}{k-1}+\binom{n+k}{k} = \binom{n+k+1}{k}$.  This is known as the \textit{Hockey-stick Identity}, due to its appearance when drawn on Pascal's Triangle.  Note that replacing $\binom{n}{i}$ with $\binom{n}{n-i}$ throughout the problem yields an alternative form of the identity.

\item How many paths of length $n$ can be made using only left or right moves of length 1, starting on the left side of a line segment of length $n$?
\par \fbox{$\displaystyle \binom{n}{\lfloor\frac{n}{2}\rfloor}$}
\par Consider the number of ways one can return to the origin with a path of length $2n$ (note that there is clearly no way to return to the origin with a path of length $2n+1$); let this value be $g(n)$.  Clearly, the first move and the last move are preordained; the first move is invariably a move to the right and the last move a move to the left.  Thus, if the path never returns to the origin until the last move, there are $g(n-1)$ options.  If the path returns on the second move, then there are $g(n-2)$ options; on the fourth move, $g(1)g(n-3)$, etc.  Thus, there are $g(n) = g(n-1)+g(n-2)+g(1)g(n-3)+g(2)g(n-4)+\ldots+g(n-4)g(2)+g(n-2)g(1)+g(n-2)+g(n-1)$ options.  This is a well-known recurrance relation for the Catalan numbers, so $g(n)$ is the $n$th Catalan number, which is $\frac{(2n)!}{(n)!(n+1)!}$.
\par Now, consider $f(n)$ to be the number of paths possible after $n$ moves (without the return to the origin restriction placed on $g$.)  A recurrance relation can be easily found; any path of length $x-1$ that does not end at the origin has two child paths of length $x$, and any path of length $x-1$ that does end at the origin has one child path of length $x$.  Thus, for even numbers ($2n+2$), the recurrance is $f(2n+2)=2f(2n+1)$, as no odd path can end at the origin.  For odd numbers ($2n+1$), the recurrance is $f(2n+1)=2f(2n)-g(n)$.
\par The proof will be completed through induction.  Assume the solution is $f(n) = \binom{n}{\lfloor\frac{n}{2}\rfloor}$.  The base cases are $n=1 \rightarrow f(n)=1$ and $n=2 \rightarrow f(n)=2$, so the base case is complete.  For any odd number $2n+1$, $f(2n+1) = 2f(2n)-g(n)$.  Testing this, $2f(2n)-g(n) = 2\binom{2n}{\lfloor\frac{2n}{2}\rfloor} - \frac{1}{n+1}\binom{2n}{n} = 2\binom{2n}{n} - \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n}(2-\frac{1}{n+1}) = \binom{2n}{n}(\frac{2n+1}{n+1}) = \binom{2n+1}{n+1} = \binom{2n+1}{n} = f(2n+1)$, so the induction works for all $2n+1$.  For any even number $2n+2$, $f(2n+2)=2f(2n+1)$.  Testing this in the induction, $2f(2n+1) = 2\binom{2n+1}{\lfloor\frac{2n+1}{2}\rfloor} = 2\binom{2n+1}{n} = \binom{2n+1}{n}+\binom{2n+1}{n+1} = \binom{2n+2}{n+1} = f(2n+2)$, so the induction works for all $2n+2$.  Thus, the induction is complete, and $\binom{n}{\lfloor\frac{n}{2}\rfloor}$ is the number of paths possible.

\item How many ways can one place in order a total of $n$ elements of two different types if one can at no point have placed down more elements of the first type than of the second type?

\par \fbox{$\displaystyle \binom{n}{\lfloor\frac{n}{2}\rfloor}$}
\par If one considers placing items of the second type moves to the right and items of the first type moves to the left, there is a clear bijection to the scenario of the previous problem.

\end{enumerate}

\begin{enumerate}

\item \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

\item \[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]
\noindent Go through the elements of the $n$-element set in order. You can either take or not take each one.

\item Number of positive integer solutions to
\[ a_1 + a_2 + ... + a_k = n \]
\noindent Treat this as having $n$ items that you wish to partition into $k$ groups. Then you must place $k-1$ dividing lines into $n-1$ possible places between items. So there are $\binom{n-1}{k-1}$ ways to do this.

\item \[ \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + ... + \binom{n}{n}^2 = \binom{2n}{n} \]

Consider walking from $(0,0)$ to $(n,n)$ on a grid and only being able to follow grid lines. How many ways can this be done? The left-hand side counts this exhaustively by considering possible ways to cross the diagonal. The right-hand side makes a more clever argument by stating that you must go down $n$ times and right $n$ times, so there are $\binom{2n}{n}$ ways to do this. As the same entity is being counted in both cases, we can place an equals sign between them.

An alternate solution with generating functions: note that $(1+x)^{2n} = ((1+x)^n)^2$. Now equate the coefficients of $x^n$ in each equation and you arrive at the same identity.

\end{enumerate}

\begin{enumerate}

\item Sometimes a problem will have a really big number in it but still require recursion. In this case a recursion with linear coefficients can be solved explicitly. Example:

\[ f_n = f_{n-1} + 2*f_{n-2} \]

Some long-dead mathematician was kind enough to prove for us that such a recurrence will always result in a closed form exponential equation (i.e. $f_n = A*B^{n}+C*D^{n}$ if $f_n$ is based only on $f_{n-1}$ and $f_{n-2}$, with more exponents if there are more terms in the recurrence). We would probably like to know $B$ and $D$, so we solve the equation $x^{2} = x + 2$ (note that this works because we can simply factor out all necesarry constants that appear). We solve the quadratic and have $x = -1,2$, so $B = -1$ and $D = 2$. $A$ and $C$ are determined by the base cases.

\item It will also be useful if one ever does Olympiad Combinatorics to know about the Pigeonhole Principle, which states that if I have $n$ pigeons and $k$ holes then there must be at least $\lceil\frac{n}{k}\rceil$ pigeons in one hole and at most $\lfloor\frac{n}{k}\rfloor$ pigeons in another hole.

\item It is often easier to find the average value of something and then multiply by however many of that something there are than to count the value outright.

\item Sums often lead to binomial coefficients. For example:

\[ 1 = \binom{n}{0} \]

\[ \sum_{i=1}^n1 = \binom{n}{1} \]

\[ \sum_{i=1}^{n-1}\sum_{j=i+1}^n1 = \binom{n}{2} \]

\[ \sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^n1 = \binom{n}{3} \]

and so on. From these and a few other identities one can derive some stranger but still very useful identities:

\item \[ \binom{n}{k} = \sum_{i=1}^{n-k+1}\binom{n-i}{k-1} = \sum_{i=0}^a\binom{a}{i}\binom{n-a}{k-i} \]

\end{enumerate}

A \textit{graph} is defined as a collection of points, called \textit{vertices}, and a collection of \textit{edges} collecting those points. Examples of a graph are a hexagon, a tetrahedron, and every other shape you know of, with edges and vertices fitting the definition given in Euclidean Geometry. These are known as \textit{planar graphs}. There are also \textit{non-planar graphs}, which are, in the most intuitive sense, graphs that cannot be drawn in Euclidean space without edges crossing each other. Edges can have values associated with them, usually referred to as \textit{weights}, and can also have directions (such a graph is called a \textit{directed graph}).

The \textit{in-degree} of a vertex is the number of edges pointing to an edge in a directed graph. Similarly the \textit{out-degree} is the number of edges pointing from an edge in a directed graph.

An \textit{Eulerian cycle} is a path through the graph that visits every edge exactly once. In a directed graph this is possible iff the in-degree equals the out-degree for every edge. In an undirected graph this is possible iff every edge has an even degree (why are these equivalent?).

A \textit{Hamiltonian cycle} is a path through the graph that visits every vertex exactly once. There are several theorems stating when a Hamiltonian cycle exists. While they are admittedly useful they will not be discussed here, as they are not biconditional like the theorem for Eulerian cycles.

A \textit{complete graph} is one in which all possible edges are drawn. By convention the complete graph with $V$ vertices is referred to as the $K_V$ graph. A \textit{simple graph} has no more than one edge between any two vertices and no edges from a vertex to itself. By convention all graphs are simple and undirected unless otherwise stated.

Also note that the number of paths $N(A,B)$ from $A$ to $B$ is $\displaystyle\sum_{v \in C(A)}N(v,B)$, where $C(X)$ denotes the set of vertices that $X$ has an edge to.

those are nice JSteinhardt  :lol:  thanks a lot

[b][size=150]SOME IMPORTANT RESULTS[/size][/b]

[b][u]Result 1[/u][/b]  [i]If n items are arranged in a row,then the number of wasy in which they can be rearranged so that no one of them occupies the place assigned to it is[/i]
$n![ 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}]$

[b][u]Result 2[/u] [/b]  [i]If there are m items of one kind,n items of another kind and so ion,then the number of ways of choosing ritems out of these items is[/i]
$Coeff.\ of\ x^r\ in\ (1+x+x^2+x^3+\cdots+x^m)(1+x+x^2+\cdots+x^n)\cdots$

[b][u]Result 3[/u][/b]    [i]If there are m items of one kind,n items of another kind and so on,then the number of ways of choosing r items out of these items such that at least one item of each kind is included in every selection is[/i]

$Coeff.\ of\ x^r\ in\ (x+x^2+\cdots+x^m)(x+x^2+\cdots+x^n)\cdots$

$\displaystyle\binom{n}{x_1,x_2\cdots x_k}$ is the number of ways of choosing k subsets, each with $x_i$ elements, out of n elements. Define $x_0=0$
\begin{eqnarray*} \displaystyle\binom{n}{x_1,x_2\cdots x_k} &=& \displaystyle\frac{n!}{(n-\sum x_i)!\displaystyle\prod_{i=1}^k x_i!}\\ &=& \displaystle\prod_{i=1}^k \binom{n-\sum_{j=0}^{i-1} x_{j}}{x_i}\\ &=& \binom{n}{\sum_{i=1}^k x_i} \binom {\displaystyle\sum_{i=1}^k x_i}{x_1,x_2\cdots x_k} \end{eqnarray*}

Does anyone know a formula for $\displaystyle\sum\binom{n}{x_1,x_2\cdots x_k}$ for all $\displaystyle\sum_{i=1}^k x_i = n$ ?

[quote="felipeochoa"]Does anyone know a formula for $\displaystyle\sum\binom{n}{x_1,x_2\cdots x_k}$ for all $\displaystyle\sum_{i=1}^k x_i = n$ ?[/quote]

For a given k, it's just $N = k^n$. (Each item goes in one of k subgroups). For all k such that $1 \leq k \leq n$, you get the sum $N = \sum^{n}_{r=1}{r^n}$... I'm not sure how to write that explicitly.

[color=blue]Result 1[/color] If n items are arranged in a row,then the number of wasy in which they can be rearranged so that no one of them occupies the place assigned to it is

$n![1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^{n}\frac{1}{n!}]$

i dont get this, can someone help plz

cane some one prove this:

Result 2 If there are m items of one kind,n items of another kind and so ion,then the number of ways of choosing ritems out of these items is
$ Coeff.\ of\ x^{r}\ in\ (1\plus{}x\plus{}x^{2}\plus{}x^{3}\plus{}\cdots\plus{}x^{m})(1\plus{}x\plus{}x^{2}\plus{}\cdots\plus{}x^{n})\cdots$

A few mistakes I have just spotted seem to be really popular:

[quote="JSteinhardt"]There are also \textit{non-planar graphs}, which are, in the most intuitive sense, graphs that cannot be drawn in Euclidean space without edges crossing each other.[/quote]

Space $ \to$ plane.

[quote="JSteinhardt"]An \textit{Eulerian cycle} is a path through the graph that visits every edge exactly once. In a directed graph this is possible iff the in-degree equals the out-degree for every edge. In an undirected graph this is possible iff every edge has an even degree (why are these equivalent?).[/quote]

You forgot to require that the graph is connected. Many people tend to forget this condition. Keep in mind that in some cases - for instance, in the proof of the existence of [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=17342]generalized de Bruijn sequences[/url] - this condition is the harder one of the two to check!

[quote="JSteinhardt"]Also note that the number of paths $ N(A,B)$ from $ A$ to $ B$ is $ \sum_{v\in C(A)}N(v,B)$, where $ C(X)$ denotes the set of vertices that $ X$ has an edge to.[/quote]

Depending on your definition of path, this is either wrong or nonsense... Are paths to pass any vertex only once? Any edge only once? If not, than $ N\left(A,B\right)$ will most often happen to be $ \infty$. If yes, then the above is wrong.

  Darij


Prove the inequality for numbers $x_1,x_2,...,x_n \in [a;b]$ where a is positive:

$(x_1+x_2+...+x_n)(\frac{1}{x_1}+\frac{1}{x_2}+...+\frac{1}{x_n})\leq n^2\cdot \frac{(a+b)^2}{4ab}$

To view all the problems of Uzbekistan Undergraduate Olympiad problems visit
[url]http://www.mathlinks.ro/Forum/viewtopic.php?t=81099[/url]

This is a special case of the Polye--Szegoe inequality.


search
number theory unsolved
number theory

I think posted before in Pre-Olympiad (can't search now).


[quote="Stokes93"]Solve:

$ (log_2 (x))^2 \plus{} log_2 (x) \plus{} 1 \equal{} \frac {7}{log_2 (.5x)}$[/quote]
[hide]Set $ log_{2}(x)\equal{}a$ and note that $ log_{2}(.5x)\equal{}log_{2}(x)\minus{}log_{2}(2)\equal{}log_{2}(x)\minus{}1$
Now we have that $ a^{2}\plus{}a\plus{}1\equal{}\frac{7}{a\minus{}1}$
You can multiply both sides by $ a\minus{}1$ or note that $ \frac{a^{3}\minus{}1}{a\minus{}1}\equal{}a^{2}\plus{}a\plus{}1$, so setting $ a^{3}\minus{}1\equal{}7$, you get that $ a\equal{}2$, there $ x\equal{}4$.[/hide]

hello, rewriting your equation in the form
$ \left(\frac {\ln(x)}{\ln(2)}\right)^2 \plus{} \frac {\ln(x)}{\ln(2)} \equal{} \frac {7}{\frac {\ln(1/2x)}{\ln(2)}}$
using $ \ln(1/2x) \equal{} \ln(x) \minus{} \ln(2)$
we get after some simplifications
$ \ln(x)^3 \minus{} \ln(x)^2\ln(2)^2 \minus{} 7\ln(2)^3 \equal{} 0$
solving this we get
$ x \equal{} {2}^{ \minus{} {\frac {1}{72}}\,{12}^{2/3} \left( 63 \plus{} \sqrt {3957} \right) ^{2/3 }\sqrt {3957} \plus{} {\frac {7}{8}}\,{12}^{2/3} \left( 63 \plus{} \sqrt {3957} \right) ^{2/3} \plus{} 1/6\,\sqrt [3]{12}\sqrt [3]{63 \plus{} \sqrt {3957}}}$
Sonnhard.
oh, i have forgotten the number $ 1$ in your equation, sorry.

hello, no the original equation
$ \left(\frac {\ln(x)}{\ln(2)}\right)^2 \plus{} \frac {\ln(x)}{\ln(2)} \plus{} 1 \equal{} \frac {7}{\frac {\ln(1/2x)}{\ln(2)}}$
simplifying this we get
$ \ln(x)^2\ln(1/2x) \plus{} \ln(x)\ln(2)\ln(1/2x) \plus{} \ln(2)^2\ln(1/2x) \minus{} 7\ln(2)^3 \equal{} 0$
$ \ln(x)^3 \minus{} 8\ln(2)^3 \equal{} 0$
$ \ln(x) \equal{} \ln(4)$
$ x \equal{} 4$
Sonnhard.

[quote="Stokes93"]Solve:

$ (log_2 (x))^2 \plus{} log_2 (x) \plus{} 1 \equal{} \frac {7}{log_2 (.5x)}$[/quote]

[i]Denote[/i] $ \log_{2}(x) \equal{} y \implies log_{2}^2 (x) \equal{} y^2$

$ log_{2}(\frac {x}{2}) \equal{} log_{2}(x) \minus{} \log_{2}(2) \equal{} y \minus{} 1, \implies (y \minus{} 1)(y^2 \plus{} y \plus{} 1) \equal{} 7$

$ \implies y \equal{} 2$ , [i]therefore[/i] $ x \equal{} 2^y \implies x \equal{} 4$


probability
combinatorics unsolved
combinatorics

1. A and B play a series of games. Each game is independently won by A with probability p and by B with probability 1-p. They stop when the total number of wins of one of the players is two greater than that of the other player. The player with the greater number of total wins is declared the winner.  Find the probability that A is the match winner.

2. A stock market investor owns shares in stock whose present value is 25. She has decided that she must sell her stock if it either goes down to 10 or up to 40. If each change of price is either up 1 point with probability .55 or down 1 point with probability .45, and the successive changes are independt, what is the probability that the investor retires a winner?

You seem to be unable to decide if your questions belong in the intermediate forum or the olympiad forum, which suggests that in fact they are best-suited to [url=http://www.artofproblemsolving.com/Forum/index.php?f=151]Pre-Olympiad[/url].

[quote="wly3298456"]1. A and B play a series of games. Each game is independently won by A with probability p and by B with probability 1-p. They stop when the total number of wins of one of the players is two greater than that of the other player. The player with the greater number of total wins is declared the winner.  Find the probability that A is the match winner.[/quote]

A simple probability state diagram is the best way to go.  There are five states: A wins (happy state), A + 1, Tied, B + 1, B wins (unhappy state).  With these states we associate probabilities $p_{1}, p_{2}, p_{3}, p_{4}$ and $p_{5}$ that A wins starting in the given state, and we want to calculate $p_{3}$.  Then we have $p_{1}= 1$, $p_{2}= p+(1-p)p_{3}$, $p_{3}= p\cdot p_{2}+(1-p)p_{4}$, $p_{4}= p\cdot p_{3}$ and $p_{5}= 0$.  This is straightforward to solve.


function
real analysis
real analysis unsolved

given f(x), g(x) defined in a neighbourhood of c,
is it true that:
$ o_{c}(f)\equal{}o_{c}(g)\iff f \thicksim_{c}g$ ?

(I have proved the reverse implication, but I'm not sure about the direct one)

True. For example, if $ \liminf_{x\to c}f(x)/g(x)\equal{}0$, then you can construct a function $ h$ that is equal to $ f$ when $ f(x)/g(x)$ is "small" and is zero otherwise, so that $ h\in o_c(g)\setminus o_c(f)$.


On a plane are given finitely many red and blue lines, no two parallel, such that any intersection point of two lines of the same color also lies on another line of the other color. Prove that all the lines pass through a single point.

[b]Solution [/b]We shall start the process of drawing the lines in the following fashion. We first draw two red(or blue) lines, then draw a blue line so that it passes through the intersection. Then draw a blue line if the number of blue line is greater than 1 and so on. In case we have more than 2 red lines and just one blue line then we have draw the red line through the same intersection point and the process continues. Suppose we go on like this till we exhaust all our lines and build a system according to the condition of the problem. We are assured that at least one such system exists : consider all the red and blue points passing through a point.

Let the last line that was drawn be red wlog. It had to be drawn so that it passed through the intersection point of every pair of red lines drawn previously. For any three non parallel lines we get three distinct intersection points (a triangle) or else all of them pass through a same point. The only option was the latter and we conclude that all the red lines meet at a common point. By the condition of the problem, all the blue lines also pass through this common point.

I understand virtually nothing from your proof, such as

[quote="srikanth"] Then draw a blue line if the number of blue line is greater than 1 and so on. [/quote]

Draw it where, and what do you mean by "so on"?

I was actually giving a method to construct a set of finite red and blue lines according to condition of the problem.

Let $ r$ and $ b$ be the number of red and blue lines respectively. Intent of the solution is to explicitly construct a system ( of red and blue lines with the required conditions) by drawing one line at a time. We use the finiteness property later. Say we started by drawing two red lines wlog. This is not a system yet, we have to draw a blue line through the intersection point of the two red lines. The next line we draw can be either red or blue (your quote from my last post- I said we can draw a blue line at this stage only if $ b$>1) and [b]so on[/b]. We observe that that drawing lines will give rise to more intersections, and we need to draw more lines through the intersection points. So we impose following the condition when the last line is drawn (finiteness property).

Last line in a construction (either red or blue) has to pass through the intersection of every pair of lines ( previously drawn) of same colour. The required result follows immediately.

Ps: Referring to [i]so on[/i]- If you put pen to paper and start constructing a system (without finiteness property) like this you will find that there different ways in which one can proceed. The solution speaks about the terminating step in the finite case and solution does not intend to describe the possible (infinite) constructions in the case without finiteness condition.

Is the solution clear ?

check this topic so amazing proof:

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=446298&p=2512211#p2512211


calculus
derivative
function
calculus computations

If all the n-th derivatives of a function are bounded on an interval ]-a,a[ then it has a series development.
This is a sufficient condition , but it seems to me that all $C^\infty$functions  have this property including the classical couter example $e^{-\frac{1}{{x^{2}}}}$ ; am i missing something ?

A sufficient condition for analyticity is that the derivatives are [b]uniformly[/b] bounded, that is, there is $C$ such that $|f^{(n)}(x)|\le C$ for all $x\in (-a,a)$ and all $n\ge 1$.

You could weaken what mlok said to

$|f^{(n)}(x)|\le\frac{Cn!}{a^{n}}$ for all $x\in(-a,a)$ and for all $n\ge 1.$

That would still be a sufficient condition; it would still not be a necessary condition.


For $n>2k$, show that \[2^{k}n!>n^{k}\left(n-k\right)!.\]


conics
parabola
geometry proposed
geometry

[quote="Michael Niland"]The normals at the three points A, B, C on a parabola are concurrent.

A line is drawn through each vertex of the triangle ABC , parallel to the opposite side (the line through A is parallel to BC, and so on).

Prove that the three lines formed touch a fixed parabola.[/quote]

Let $A(at_1 ^2 ,\,2at_1 ),\,\,B(at_2 ^2 ,\,2at_2 ),\,\,A(at_3 ^2 ,\,2at_3 )$ are three points on the parabola $y^2=4ax$ normals at which are concurrent at (h, k).

Then there are three well known relations
$t_1  + t_2  + t_3  = 0$,     $\sum {t_1 t_2 }  = \frac{{2a - h}}{a}$,    $t_1 t_2 t_3  = \frac{k}{a}$.

Line through $A$ and parallel to $BC$ is given by $2x - y(t_2  + t_3 ) = 2at_1 ^2  - 2at_1 (t_2  + t_3 )$
Using first of the above three relations, we can write this equation as

$2x + yt_1 = 4at_1 ^2$
$\Rightarrow y =  - \frac{2}{{t_1 }}x + 4at_1$

which is the standard equation to the tangent to the parabola $y^2=-8ax$.

It can be shown that the other two lines too touch the same parabola.


inequalities
Digits
algebra
binary representation
combinatorics
Sequence
IMO Shortlist

Let $ \alpha(n)$ be the number of digits equal to one in the binary representation of a positive integer $ n.$ Prove that:

(a) the inequality $ \alpha(n) (n^2 ) \leq \frac{1}{2} \alpha(n)(\alpha(n) + 1)$ holds;
(b) the above inequality is an equality for infinitely many positive integers, and
(c) there exists a sequence $ (n_i )^{\infty}_1$ such that $ \frac{\alpha ( n^2_i )}{\alpha (n_i }$
goes to zero as $ i$ goes to $ \infty.$

[i]Alternative problem:[/i] Prove that there exists a sequence a sequence $ (n_i )^{\infty}_1$ such that $ \frac{\alpha ( n^2_i )}{\alpha (n_i )}$

(d) $ \infty;$
(e) an arbitrary real number $ \gamma \in (0,1)$;
(f) an arbitrary real number $ \gamma \geq 0$;

as $ i$ goes to $ \infty.$

a) We prove that $ \alpha(n^2)\leq\alpha(n)(\alpha(n)\plus{}1)/2$.
Let $ k\equal{}\alpha(n)$; $ n\equal{}2^{u_1}\plus{}\cdots{2^{u_k}}$. Thus $ n^2\equal{}\sum_{i\equal{}1}^{k}{2^{2u_i}}\plus{}\sum_{i<j}2^{u_i\plus{}u_j\plus{}1}$ and $ \alpha(n^2)\leq{k\plus{}(_2^k)}\equal{}k(k\plus{}1)/2$.
b) If $ n\equal{}2^u\plus{}1$, $ u\geq{2}$,  then the above inequality is an equality because $ \alpha(n)\equal{}2$ and $ \alpha(n^2)\equal{}3$.

Hi mszew,
$ \alpha(n_i^2)/\alpha(n_i)$ goes to $ 1$.

Here's a solution for part (c).

Let $k$ be a sufficiently large positive integer, and $a > 2^k \cdot 10^{10^{10^{10}}}$ be an even larger positive integer. Let $n= 2^{a-1} - 2^{a-2} - 2^{a-4} - \cdots - 2^{a-2^k}.$ Observe that $\alpha (n) = 2^k - k.$ On the other hand, we can easily find that

$$n^2 = 2^{2(a-2^k)} + 2 \sum_{1\le i,j \le k, i \neq j} 2^{a-2^i} \cdot 2^{a-2^j},$$

which implies that $\alpha(n^2) \le 1 + \binom{k}{2}$ since it's a sum of that many powers of two. From here, we are clearly done since

$$\lim_{k \rightarrow \infty} \frac{1 + \binom{k}{2}}{2^k-k} = 0.$$

$\square$

The part a as stated here is false and there's a typo. In IMO compendium it stated the correct inequality that is $ \alpha(n^2) \leq \frac{1}{2} \alpha(n)(\alpha(n) + 1)$ and not $ \alpha(n) (n^2 ) \leq \frac{1}{2} \alpha(n)(\alpha(n) + 1)$