calculus
derivative
integration
function
real analysis
real analysis unsolved

Let $ f : [0,1] \rightarrow \mathbb{R}$ be differentiable with continuous derivatives and
\[  \int_{0}^1f(x)dx =  \int_{0}^1xf(x)dx = 1.
\]
Prove that there exists $ c \in (0,1)$  s.t. $ f^'(c) = 6$.

Write $ f(x) \equal{} \minus{} 2 \plus{} 6x \plus{} g(x)$.
Then $ f'(x) \equal{} 6 \plus{} g'(x)$
When $ g'$ has positive and negative values (or $ g'\equal{}0$), then there is a $ c$ with $ f'(c) \equal{} 6$, because $ g'$ is continuous.
$ \int_0^1 ( \minus{} 2 \plus{} 6x)\ dx \equal{} \int_0^1 x( \minus{} 2 \plus{} 6x)\ dx \equal{} 1$.

$ 0 \equal{} \int_0^1 g(x)\ dx \equal{} g(1) \minus{} \int_0^1 xg'(x)\ dx$
$ 0 \equal{} \int_0^1 xg(x)\ dx \equal{} \frac {g(1)}{2} \minus{} \int_0^1 \frac {x^2}{2}g'(x)\ dx$
Then $ \int_0^1 (x^2 \minus{} x)g'(x)\ dx \equal{} 0$.
The function $ h: x \mapsto x^2 \minus{} x$ is negative on the interval $ (0,1)$,
So $ \int_0^1 (x^2 \minus{} x)g'(x)\ dx \equal{} 0$ shows that $ g'$ has positive and negative values  (or $ g'\equal{}0$) on $ (0,1)$.


given that $m=a^2+b^2$ and $n=c^2+d^2$

prove that $mn$ can be written as a sum of 2 perfect squares

[quote="Bictor717"]$mn=(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2=(ac-bd)^2+(ad+bc)^2$[/quote]
This is a proof of the two variable Cauchy Inequality.


Okay, the title is kinda confusing but if you have a problem like this: "What is the sum of all possible 3-digit numbers made from 1, 2, and 3?"  I know its like:

$ x(111\plus{}222\plus{}333)\equal{}x(666)$

But I forgot how to find $ x$, or if there is a faster way to do this, can you please post it!

Thankx.

Well, the standard way that works for basically all of these...(for some that have pairs you can find the average and multiply by the number of terms).

We find how many times the 1 digit is the last digit in these numbers. We have 3*3=9 (3 choices for each of the other digits). This is the same amount for each other possible number in any other digit place. So thus we count 1,2,3 (1+2+3=6) in each digit place 9 times each, and our final answer is 9*666=5994 (I think you understand this because you just wanted to know how to find x).

[quote="ajain"]Okay, the title is kinda confusing but if you have a problem like this: "What is the sum of all possible 3-digit numbers made from 1, 2, and 3?"  I know its like:

$ x(111 \plus{} 222 \plus{} 333) \equal{} x(666)$

But I forgot how to find $ x$, or if there is a faster way to do this, can you please post it!

Thankx.[/quote]

Yes, that's all right.  If its an $ x$ digit number, multiply bu $ x!$

[quote="JBoyd"]Find the sum of all the numbers made by using the digits 1,4,and 6

If the numbers are not in a nice sequence make one up that is nice....example 1,2,3.  You always want to work fram a nice pattern to the messy one.  The average of each column has to be 2 (the sum of the digits divided by how many numbers). In this case the average is 222.

Now add up the sum of the digits in both cases and write them as a ratio.  11/6  Which means that your sum will be 11/6 of the nice one.

Since we are looking for a three digit numbers, there 3! ways that any combination of the digits can be written.

Now put all three parts together.   11/6 (222)(3!)[/quote]]

wouldn't it be $ \frac{11}{6}\times{222}\times 3^3$?

Um, I think Mr. Boyd means using exactly one of each of the digits.


L stands for loop. This means that whatever comes out goes back in. You cannot have the same item going in more than once. I will begin: Insert kamikazee watermelon.

recieves a walkingtaco.
inserts a walkingtaco.

recieves the recession.

inserts the recession.

recieves a demolished house
inserts a demolished house
:dry:

Receives Dr. Wilson
Inserts Dr. Wilson

Edit: Hasnt anybody figured out the answer to my topic titled "interesting"?

Recieves Dr. Carlisle Cullen

Inserts Dr. Carlisle Cullen

Receives Edward Cullen
OHMIGOSH!
No... I don't want to ):
Inserts Edward Cullen.

WHOA! Don't insult Edward Cullen.

Receives a brown crayon.
Inserts a brown crayon.

ERROR: NO INSERTION. RECIEVES A WEDGIE.

Inserts a wedgie.

Receives a small, voracious alligator.

Inserts a small, voracious alligator.


calculus
integration
derivative
LaTeX
function
real analysis
real analysis unsolved

Evaluate the integral of arctan(pi*x) - arctan(x))dx from 0 to 2 by first writing the integrand as an integral.

Not sure how to do this one at all.

Over what region R in the xy plane does the double integral of (4-x^2 - 2*y^2)dA have its maximum value?

I'm guessing I integrate wrt x and then wrt y and then take the derivative of the whole thing, set = 0 and solve?

Also I forgot how to do integrals in latex, so I apologize for writing it all out.

[quote="mlok"]I don't understand the first question. $ \arctan$ is normally integrated by parts.

For the second question: you want to include [b]all [/b]of the positive values of $ (4 \minus{} x^2 \minus{} 2y^2)$ and [b]none [/b]of the negative.[/quote]

yes but that expression can be written as just the derivative of arctan, because what is given by the problem is already in the "fundamental theorem of calculus" form, but I dont know where to go from there.

Perhaps this is what is meant by the first one:

$ \arctan(\pi x)\minus{}\arctan(x)\equal{}\int_x^{\pi x}\frac{dt}{1\plus{}t^2}.$

Let's make a change of variables in that. Let $ t\equal{}xu,$ so $ dt\equal{}x\,du.$

$ \arctan(\pi x)\minus{}\arctan(x)\equal{}\int_1^{\pi}\frac{x\,du}{1\plus{}x^2u^2}$

$ \int_0^2\arctan(\pi x)\minus{}\arctan(x)\,dx\equal{}\int_0^2\int_1^{\pi}\frac{x}
{1\plus{}x^2u^2}\,du\,dx$

Of course, I can never write down a double integral without trying to interchange the order of integration.

$ \equal{}\int_1^{\pi}\int_0^2\frac{x}{1\plus{}x^2u^2}\,dx\,du$

$ \equal{}\int_1^{\pi}\left[\left.\frac1{2u^2}\ln(1\plus{}x^2u^2)
\right|_{x\equal{}0}^{x\equal{}2}\,\right]\,du$

$ \equal{}\int_1^{\pi}\frac{\ln(1\plus{}4u^2)}{2u^2}\,du.$

Hmm.... can't say that I like where this is going. Better to just do what mlok says.

$ u \equal{} \arctan x, dv \equal{} dx$.  This can be applied to the other arc trigonometric functions, as well as the logarithm.

[quote="OVB"]and how would you integrate arctan by parts? whats the u and the dv?[/quote]

$ \int \arctan x \,dx \equal{} \int 1 \cdot \arctan x \,dx \equal{} x \arctan x \minus{} \int \frac{x}{1\plus{}x^2}\,dx$.


calculus
linear algebra
matrix
function
real analysis
real analysis solved

Prove that there are neighborhoods $U, V$ in $M_n(R)$ of the identity matrix such that
for every $A\in U$ there exist a unique $X\in V$ such that $X^4=A$

Let see the problem when $A=I_n$

It is an application of Inverse Function Theorem

$F(X)=X^4$ is $C^{\infty}$

$dF(X)H=X^2HX+X^3H+HX^3+XHX^2$

$F(I_n)=I_n$
$dF(I_n)=I_n$ is invertible then there exist $U,V$ neighborhoods of $I_n$

such that $F$ is $C^{\infty}$ diffeomorphism from $U$ to $V$

so it is bijective $X^4=I_n$ has a unique solution.


combinatorics
point set
3D geometry
straight lines
parallel
IMO
IMO 1973

Establish if there exists a finite set $M$ of points in space, not all situated in the same plane, so that for any straight line $d$ which contains at least two points from M there exists another straight line $d'$, parallel with $d,$ but distinct from $d$, which also contains at least two points from $M$.

Yes. Take for $M$ the set of vertices of a cube $ABCDEFGH$ and two points $Y$, $X$ symmetric to the center $I$(we dont take $I$!!!!) of the cube with respect to the laterals $ABCD$ and $EFGH$.

Alternatively, take the vertices of a $3\times 3\times 3$-cube.


Hi guys,

First and foremost, this is not a direct topic concerning AMC itself but it's related to it. So, please do not criticize for putting up this thread.

Second, the main content. I'm posting up this thread to seek ONE high school student to help me with my Hidden Discoveries Math Olympiad contest. The student will be involved in following:

* Creating the problems for the contest
* Verifying the problems made by myself
* Helping with typing in the solutions

The pre-requisite for this offer is following:

* Qualification to AIME. USAMO is not necessary since Hidden Discoveries does not cover up to USAMO.
* At least one course in algebra, geometry, and trigonometry. Calculus or Pre-calculus is not required.
* Computer skills: Ability to create geometric diagrams and type problems in Microsoft Word (no LaTeX).

Third, why. Why am I asking this in AMC forum.

If all goes well, I'll be working as a laboratory assistant for period of 4-weeks this summer for Chemistry Department at my college. Furthermore, with many other things going on, it will be hard for me to write all the problems for Hidden Discoveries Math Olympiad. So I'm asking for help to a student who's interested in this.

Fourth and last, what you will get out of. I am going to try to write some type of official letter of recommendation for the student once this is over. This help-assistance will take place during the summer, and once it ends, I will mail an official letter of recommendation for the student. Note that because Hidden Discoveries is a free contest, you will NOT be paid on any circumstances. It is also beneficial for student to get taste of an official math contest because as some of you know, Hidden Discoveries is not a mock contest. It is an actual math contest that ran this year with large number of interests. So for anyone who is seriously considering mathematics in future, this will be something that will make you stand out bit.

If you are interested in this, please send me a private message. This thread will be locked.

I was glad to see that there was interest in this. Therefore, to make this really official and fair, I'm asking for followings:

1. Approximately 500-words paper based on your most interesting experience with math in general. This can be referred to making to USAMO, solving your first math competition problem, or just the moment that you learned to love math.
2. Your basic information.
*Name
*Grade
*High School
*Possible planned major (if not available, put Undecided)
*Future Goal Career
*Just something interesting about yourself
3. Your favorite math problem. This should come from an actual contest, not something you made. And when you send it, I want to see problem and solution with the source.
4. One-page single spaced (can be very short or fill up the entire page; I'm not looking for certain length) on what you would like to get out of this experience.

The deadline is March 13th, 2009.

You can probably note that as much as I'm heavily into math, I'm looking for usual things as well (papers). This is because writing math problem is like writing a novel. Grammar, clarity, brevity, and critical thinking come in play, and I take it very seriously. You can be the greatest mathematician in the world, and not know how to write.

To be fair, I want it to be emailed to contest email. I do NOT want you to put your AoPS ID on it because of any possible chance of unfairness.

Thank you.

This is not an "announcement" relating to the AMC, so please don't post it as such.  Actually, it doesn't have anything to do with the AMC, so I'm moving it.

This is a reminder that all the information for this must be submitted by this Friday. I haven't received that much of interest so anyone who is interested has a good shot!

I'll be waiting.  :)


When are the results coming out... i mean the qualy list or acceptee list or something...

Last year, we got an email. Why do you want a list? Trying to scope out the competition?  :D

Haha...well a list would be nice to see who made it, I admit. ^_^

I dont think that's likely to happen, but ztbb will give the official word. The email last year was nice, it had a capitalized "congratulations" as the subject.

Will we get emailed regardless whether we are accepted or not? That would quelch any anxiety due to waiting (see MOP threads!  :D )

I'm guessing they send mail to everybody. But anyway, here's what the email looks like:

Dear - -

Congratulations! We are very happy to let you know that you have been
accepted to Canada/USA Mathcamp 2004. The admissions committee enjoyed
reading your application and we look forward to meeting you in person.

Your official acceptance letter and registration package will be mailed
to
you within the next few days.  Before the end of the week, we will also
send you an email with registration instructions.  If you have applied
for
a scholarship, we hope to let you know of a decision within a week.

Meanwhile, we would appreciate it if you would reply to this email to
let
us know whether you are

definitely?
probably?
maybe?
probably not?

coming to Mathcamp this summer. Also, if at some point you decide that
you
are definitely NOT coming to Mathcamp, please let us know right away,
so
we can give your spot to another student.

We hope to see you in Maine!

Best regards,

Mira Bernstein
Executive Director
Canada/USA Mathcamp

David Savitt
Deputy Director
Canada/USA Mathcamp

tetrahedr0n is fully prepared to be hired onto the Mathcamp staff! :D

[quote="probability1.01"]tetrahedr0n is fully prepared to be hired onto the Mathcamp staff! [/quote]

Ha... that's legendarily difficult. Only a small, select group of campers come back as JCs later (or so I hear.)

[quote="xxreddevilzxx"]tetrahedr0n, are u going this year???[/quote]

No, not this year. But I have every intention of returning next year.


geometry
perimeter
inequalities
triangle inequality
combinatorial geometry
combinatorics unsolved
combinatorics

given $n$ points in the plane; prove or disprove, that we can always find a path from a starting point such that we pass all other points and come back to the same, starting point; with the condition that there are no crosses in our path (in other words: the path should not cross itself) .

Yes, I think such a path does exist. Old trick:

Among all cycles with straight edges and having our $n$ points as vertices, choose the one with minimal perimeter. If the segments $xy,zt$ were to intersect, replacing them with one of the pairs $(xz,yt),\ (xt,yz)$ (just one of them works; the proper one has to be chosen; this can be shown by reasoning on an $n$-cycle drawn as a convex polygon, with $xy,zt$ as two of its sides) would keep the graph connected, but would make the perimeter strictly smaller. This contradicts the minimality assumption.

I hope it's Ok.

Changing $(xy,zt)$ to either one of those two pairs decreases the length (yes, by the triangle inequality); however, one of these moves keeps the graph connected, while one does not. This is what I meant when I said that we have to choose properly between the two pairs of edges we want to change the initial pair into.

my initial reaction upon reading this question was to take the biggest convex hull of points of the set and so on.
thus there always exist such path without any crossings.

EDIT: as pointed out to me my "perfect_radio" i dont think this idea works since we are dealing with cycles here.

I disagree: It is not always possible to construct such a path.

E. g. consider the points $(0,0)$, $(1,0)$ and $(2,0)$, which cannot be
choined by a path in the given way. (I suppose that if a bond is contained
in another bond then this counts as a crossing, or doesn't it?)

But I suppose everything is OK if not all points are collinear.

Of course. Since in such problems collinear points give rise to all sorts of pathological examples, I, for one, assumed even more: no three points are collinear. These are the interesting cases anyway :).


It follows immediately from Cauchy-Schwarz inequality:

                                       \[ [(a+1)+(b+1)][\frac{a^{2}}{a+1}+\frac{b^{2}}{b+1}]\geq (a+b)^{2}. \]

 From here, we get the desired result. ;)

[quote=DPopov]Given $a+b=1, a,b>0$

Prove $\frac{a^2}{a+1}+\frac{b^2}{b+1} \geq \frac{1}{3}$[/quote]
this is equivalent to:
$ab(a+b)+(a+b)^2-2ab\geq \frac{1}{3}(ab+2) $
$ab+1-2ab=1-ab\geq \frac{1}{3}(ab+2) \iff $
$ab\leq \frac{1}{4} $ This is true.


Prove or disprove: there is an inner product on $ R^2$ such that the associated norm is given by
$ \parallel{}(x_1, x_2)\parallel{} \equal{} |x_1| \plus{} |x_2|$
for all $ (x_1, x_2) \in R^2$.

The norm in an inner product space must satisfy this identity:

$ \|x\plus{}y\|^2\plus{}\|x\minus{}y\|^2\equal{}2\|x\|^2\plus{}2\|y\|^2$ for all $ x,y.$

For this norm, let $ x\equal{}(1,0)$ and $ y\equal{}(0,1).$

$ \|x\plus{}y\|^2\plus{}\|x\minus{}y\|^2\equal{}2^2\plus{}2^2\equal{}8.$

$ 2\|x\|^2\plus{}2\|y\|^2\equal{}2\plus{}2\equal{}4.$

They don't agree, so this norm cannot be given by an inner product.

For a norm that is given by a (real) inner product, we can recover that inner product by

$ \langle x,y\rangle\equal{}\frac14(\|x\plus{}y\|^2\minus{}\|x\minus{}y\|^2).$


function
floor function
summer program
PROMYS
algorithm
algebra

Every prime of the form 4n + 1 is a sum of two squares.

        If $p = 4n+1$, then by Fermat's Little Theorem each of the numbers $1, 2^{4n}, 3^{4n},\dots, (4n)^{4n}$ is congruent to one modulo $p$. The differences $2^{4n}-1, 3^{4n}-2^{4n}, \dots, (4n)^{4n}-(4n-1)^{4n}$ are therefore all divisible by $p$. Each of these differences can be factored as $a^{4n}-b^{4n}= \left(a^{2n}+b^{2n}\right)\left(a^{2n}-b^{2n}\right).$

Since $p$ is prime, it must divide one of the two factors. If in any of the $4n-1$ cases it divides the first factor, then by the previous step we conclude that $p$ is itself a sum of two squares (since $a$ and $b$ differ by $1$, they are relatively prime). So it is enough to show that $p$ cannot always divide the second factor. If it divides all $4n-1$ differences $2^{2n}-1, 3^{2n}-2^{2n},\dots,(4n)^{2n}-(4n-1)^{2n}$, then it would divide all $4n-2$ differences of successive terms, all $4n-3$ differences of the differences, and so forth. Since the kth differences of the sequence $1^{k}, 2^{k}, 3^{k},\dots$ are all equal to $k!$, the $2nth$ differences would all be constant and equal to $(2n)!$, which is certainly not divisible by p. Therefore, p cannot divide all the second factors which proves that p is indeed the sum of two squares.

This excerpt was taken from the wikipedia article http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares .

Could someone help me understand the part where it gets into differences of differences and k!? Thanks.

Here's another way...
I'll hide it to save space...
[hide]We know $-1$ is a perfect square mod $p$...I don't want to have to type out that proof, but if I have to, I will...So let $k^{2}\equiv-1\mod{p}$...

Let $f(x)$ be the modular residue of $x$ in $\mathbb{Z}_{p}$ ie, $0 \le f(x) \le p-1$, $f(x) \equiv x\mod{p}$, $f(x) \in \mathbb{Z}$.

It is clear that $x^{2}\equiv (f(x))^{2}\mod{p}$.  Thus, $(f(k))^{2}\equiv-1 \mod{p}$.

Notice that \[a^{2}+b^{2}\equiv 0\mod{p},0<|a|<\sqrt{p},0<|b|<\sqrt{p}\]  \[\implies 0<a^{2}+b^{2}<2p \implies a^{2}+b^{2}=p\] So if we can find two such a and b, then we're done.  We will use the function f to do this.

Consider the following sets of multiples of k: \[\pm k, \pm 2k, \pm 3k, ..., \pm \lfloor{\sqrt{p}}\rfloor k\] For a given $ak$, we have \[(ak)^{2}+a^{2}\equiv 0\mod{p}\] But because we have designed the above set of multiples so that $\forall a, 0<|a|<\sqrt{p}$, if $f(ak)<\sqrt{p}$, then \[p=(f(ak))^{2}+a^{2}\] which is exactly what we want.  So now we set out to show there exists such a multiple.

Consider the set of the positive multiples of k from the above set, ie \[k, 2k, 3k, ..., \lfloor{\sqrt{p}}\rfloor k\] If \[\exists a \in \mathbb{Z}s.t. 0<a<\sqrt{p}\implies f(ak)<\sqrt{p}\] then we are done.  In addition, if \[\exists a \in \mathbb{Z}s.t. 0<a<\sqrt{p}\implies f(ak)>p-\sqrt{p}\] then $f(-ak)<\sqrt{p}\implies (f(-ak))^{2}+(-a)^{2}=p$ and we are done.  Thus, assume \[\forall a \in \mathbb{Z}, 0<a<\sqrt{p}\implies \sqrt{p}<f(ak)<p-\sqrt{p}\] Now consider a permutation of $(f(k), f(2k), f(3k), ..., f(\lfloor{\sqrt{p}}\rfloor k))$, namely \[(a_{1}, a_{2}a_{3}, ..., a_{\lfloor{\sqrt{p}}\rfloor})\] so that $a_{1}<a_{2}<...<a_{\lfloor{\sqrt{p}}\rfloor}$.

Clearly, any difference between two multiples of k is again a multiple of k.  But we assumed that any multiple ak, with $-\sqrt{p}<a<\sqrt{p}$ must satisfy \[\sqrt{p}<ak<p-\sqrt{p}\] Thus, because any difference between two consecutive terms in the above permutation is positive, any such different must be greater than $\sqrt{p}$.  And \[a_{r}-a_{r-1}>\sqrt{p}\implies a_{r}-a_{r-1}\ge \lfloor{\sqrt{p}}\rfloor+1\] So \[a_{1}\ge \lfloor{\sqrt{p}}\rfloor+1\]  \[\implies a_{2}\ge \lfloor{\sqrt{p}}\rfloor+1+\lfloor{\sqrt{p}}\rfloor+1=2\lfloor{\sqrt{p}}\rfloor+2\]  \[a_{3}\ge 3\lfloor{\sqrt{p}}\rfloor+3\]  \[\vdots\]  \[a_{\lfloor{\sqrt{p}}\rfloor}\ge \lfloor{\sqrt{p}}\rfloor(\lfloor{\sqrt{p}}\rfloor+1) = \lfloor{\sqrt{p}}\rfloor^{2}+\lfloor{\sqrt{p}}\rfloor\] But \[\lfloor{\sqrt{p}}\rfloor^{2}+\lfloor{\sqrt{p}}\rfloor = \lfloor{\sqrt{p}}\rfloor^{2}+2\lfloor{\sqrt{p}}\rfloor+1-\lfloor{\sqrt{p}}\rfloor-1\]  \[=(\lfloor{\sqrt{p}}\rfloor+1)^{2}-\lfloor{\sqrt{p}}\rfloor-1\]  \[\ge (p+1)-\lfloor{\sqrt{p}}\rfloor-1=p-\lfloor{\sqrt{p}}\rfloor\] Thus, $a_{\lfloor{\sqrt{p}}\rfloor}\ge p-\lfloor{\sqrt{p}}\rfloor$ But then \[\exists a\in\mathbb{Z}, 1 \le a \le \lfloor{\sqrt{p}}\rfloor s.t. p-\lfloor\sqrt{p}\rfloor \le f(ak) \le p-1\] which contradicts our assumption.  Then our assumption was false, and this shows that we have a multiple of k whose residue mod p is below $\sqrt{p}$, showing that there are two squares which add to p.[/hide]

I actually took this from a paper I wrote in PROMYS, and edited it a bit...so there are probably references in there...

Thanks for the proofs guys, but I'm familiar with some of them and I was just asking about the particular section mentioned in the wikipedia article.

[quote="othman"]an other way to proof it is to considere the set $\mathbb{Z}[i]$[/quote]

But you then still have to prove the division algorithm, UPF, etc in $\mathbb{Z}[i]$...

[quote="othman"]yes, but i mean if you admit all of this theorems you will find an other proof, also u don't have to proof some theorems that are already known.
 any way , u can get stronger results by this methode ,for example if u consedere  the primes of $\mathbb{Z}[j]$ u will find an other theorem of composition in the forme $a^{2}-ab+b^{2}$
 :)[/quote]

Yeah, but if you consider the properties of $\mathbb{Z}[i]$ to be arleady known, then the desired fact can be considered already known...the idea is to be thoroughhere ...
In the general $\mathbb{Z}[\sqrt{-d}$ case for $x^{2}+dy^{2}$, we don't necessarily know the properties of that system anyways.  But true: although you DO need to prove the properties of $\mathbb{Z}[i]$, it is a nice, generalizable proof.

But what is $\mathbb{Z}[j]$?

$\mathbb{Z}[j]$is the set of numbers$a+jb$ where $j=\frac{1}{2}(-1+i\sqrt{3})$

this topic was already discussed just recently.

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=107665

WHOA that wiki proof is pretty awesome

so...to actually answer phedelpo's question (seriously why bother spamming up the thread with other stuff; it's all over the place already)

consider the polynomial f(x) = x. If we take a finite difference f(x+1) - f(x), we get the polynomial g(x) = 1. Note that this is constant after 1 difference operator. Now, consider f(x) = x^2. If we take a finite difference one time, we get g(x) = f(x+1) - f(x) = 2x + 1. If we take a finite difference of this, we get h(x) = g(x+1) - g(x) = 2. Ok, let's try f(x) = x^3. Taking finite differences, we find g(x) = f(x+1) - f(x) = 3x^2 + 3x + 1, h(x) = g(x+1) - g(x) = 6x + 9, i(x) = h(x+1) - h(x) = 6. Perhaps you can conjecture what happens in general to the polynomial x^n (and then generalize to all polynomials).


Let $ABCD$ be a convex quadrilateral in which $\angle BAC = 50^{\circ}, \angle CAD = 60^{\circ}$and $\angle BDC = 25^{\circ}$. If $E$ is the point of intersection of $AC$ and $BD$, find $\angle AEB$.

could you explain me please why does Since $\angle BDC=\frac{1}{2}\angle BAC$, $A$ is the circumcenter of $\triangle BCD$?
 thanks  :)

[quote="aznluster"][quote="frt"][hide]
Since $\angle BDC=\frac{1}{2}\angle BAC$, $A$ is the circumcenter of $\triangle BCD$.

Hence $AC=AD\Longleftrightarrow\angle ACD=\angle ADC$

$\angle ACD=\angle ADC=\frac{1}{2}(180^\circ-60^\circ)=60^\circ$

$\therefore\angle ADE=\angle ADC-\angle BDC=60^\circ-25^\circ=35^\circ$

$\therefore\angle AEB=\angle CAD+\angle ADB=\boxed{95^\circ}$[/hide][/quote]

Can you direct me to the proof of your first statement?[/quote]

It is actually a false statement. It is true that if a central angle and inscribed angle of a circle both cut the same arc, the central angle has twice the value of the inscribed angle. However, his statement is false because there are many other points that satisfy such constraints. Indeed, if you draw a diagram, A is clearly not the circumcenter.

Draw the circle $\odot (ABC)$, take $O$ the midpoint of its arc $BC$ containing $A$, draw the circle $(O, OB)$.
From $A$, draw a halfline $(Ax)$, directed to the halfplane not containing $B$, such as $\angle CAx=60^\circ$, it will intersect the second circle at $D$; see that for [b]many[/b] $A$ on the first circle will find a $D$ on the second one, and the required angle is not constant.

Best regards,
sunken rock

I believe this problem does not give enough information. Perhaps this is the real one: [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?f=150&t=451779[/url]

Surprisingly, it turns out that $A$ IS indeed the circumcenter of $\triangle BCD$ even with the additional information! :what?:

EDIT: Yes, the additional information is [b]necessary[/b] because I was able to construct two different quadrilaterals with Rushil's conditions.

No extra condition is necessary. A trigonometric approach shows that $\angle AEB = 95^\circ$

@Sayan - what trig approach did you use?

A would be the circumcentre because DC chord and BC chord subtend double angle at A....

Not a proper solution has been posted here, so I'm posting, sorry for bumping this thread.

Extend $CA$ to a point $K$ such that $2\angle BKD=\angle BAD=55^\circ$ and as $\angle BCD=125^\circ$. So, $BCDK$ is a cyclic quadrilateral. So, $\angle BKC=25^\circ\implies \angle KBA=25^\circ$. So, $KA=AB$. Similarly $KA=AD$. So, $AB=AD$. So,$\angle ADB=35^\circ\implies \angle AEB=95^\circ$.

Sorry for bumping this thread again, but in the book [b]An Excursion in Mathematics[/b] an extra condition is given: $\angle CBD=30^{\circ}$, which is not there in the question, mods kindly add it.
P.S:- The source (the book) is really authentic. :)

This is tough for early student , but legend first notice that angle BDC=1/2CAB >> A is centre now you feel easy


superior algebra
superior algebra solved

Is there a ring extension $S/R$ of commutative rings with $1$ such that $S\setminus R$ is multiplicatively closed?

Sure. Take $R=\mathbb Z_{p}$, the ring of $p$-adic integers, and $S=\mathbb Q_{p}$, the field of fractions of $\mathbb Z_{p}$.


limit
trigonometry
algebra unsolved
algebra

Ok I had to prove the following limits exists, and were equal

Take $a_0,b_0>0$

Let

$a_n = \frac{a_{n-1}+b_{n-1}}{2}$

$b_n = \sqrt{a_n b_{n-1}}$

How do I actually find a value of
$\lim_{n \to \infty} b_n$? Apparantly a solution can be found in terms of inverse trig functions. It is obivously equal to $\lim_{n \to \infty} a_n$ but I have no idea how to actually find it

If $(a_n)$, $(b_n)$ converges to $l$ and $l'$ then $l=\frac{l+l'}{2}$ and $l=\sqrt{ll'}$ then $l=l'$, take $a_0=b_0>0$ and you have $l$ and $l'$ as you want

Sorry I could show the limits were equal. I was looking for a nice closed form of the limit (ie in terms of a/b)

I guess it can't be done simply:

http://en.wikipedia.org/wiki/Arithmetic_geometric_mean

To Rodolphe: I believe you have not answered the question. How do you find the limits?


Let $ a,b,c$ positive reals and $ k\geq\minus{}2$. Prove that

$ \sum\frac{3a^2\plus{}(4k^2\plus{}18k\plus{}17)bc}{b^2\plus{}kbc\plus{}c^2}\geq\frac{4k^2\plus{}24k\plus{}29}{k\plus{}2}$

[quote="Ligouras"]Let $ a,b,c$ positive reals and $ k\geq \minus{} 2$. Prove that

$ \sum\frac {3a^2 \plus{} (4k^2 \plus{} 18k \plus{} 17)bc}{b^2 \plus{} kbc \plus{} c^2}\geq\frac {4k^2 \plus{} 24k \plus{} 29}{k \plus{} 2}$[/quote]

The following inequality is equivalent to

$ 3(k \plus{} 2)\sum{a^4(a \minus{} b)(a \minus{} c)} \plus{} 3(k \plus{} 2)(k \plus{} 1)\sum{a^3(b \plus{} c)(a \minus{} b)(a \minus{} c)} \plus{}$

$ ( \minus{} 17 \minus{} 12k \minus{} k^2)(a \minus{} b)^2(b \minus{} c)^2(c \minus{} a)^2 \plus{} 3(k \plus{} 2)(k \plus{} 1)^2abc\sum{a(a \minus{} b)(a \minus{} c)}$

$ \plus{} (4k^2 \plus{} 15k \plus{} 17)(k \plus{} 2)^2abc\sum{(b \plus{} c)(a \minus{} b)(a \minus{} c)}$

$ \plus{} (8k^2 \plus{} 30k \plus{} 31)(k \plus{} 2)^3c^2a^2b^2\geq 0$

we only to prove

$ 3(k \plus{} 2)\sum{a^4(a \minus{} b)(a \minus{} c)} \plus{} 3(k \plus{} 2)(k \plus{} 1)\sum{a^3(b \plus{} c)(a \minus{} b)(a \minus{} c)} \plus{}$

$ ( \minus{} 17 \minus{} 12k \minus{} k^2)(a \minus{} b)^2(b \minus{} c)^2(c \minus{} a)^2\geq 0$

(1)$ k\geq \minus{} 1$
easy to prove

$ \sum{a^4(a \minus{} b)(a \minus{} c)}\geq 5(a \minus{} b)^2(b \minus{} c)^2(c \minus{} a)^2$ and $ \sum{a^3(b \plus{} c)(a \minus{} b)(a \minus{} c)}\geq 2(a \minus{} b)^2(b \minus{} c)^2(c \minus{} a)^2$

so.......

(2) $ \minus{}2\le k <\minus{}1$  ??


Hi, I am new to this forum, (I found it by searching on Google), and was wondering if someone could help me with the following problems, because I am running out of ideas to help me solve them...

Here is the first problem:

A geometric sequence has a non-zero first term and a non-zero ratio. An arithmetic sequence has a first term equal to zero. A third term is formed by adding corresponding terms of the two given sequences. If the first three terms of the third sequence are 2,2,4, compute the fourth term of the third sequence.

Here is the second problem:

A bicycle shop has a display of bicycles, tricycles and unicycles. a total of 200 wheels, 95 seats, and 144 handle grips (one on each side) can be counted in the display. How many types of each cycle are on display? Note: Unicycles do not have handle grips.

Thanks!

[quote]
A geometric sequence has a non-zero first term and a non-zero ratio. An arithmetic sequence has a first term equal to zero. A third term is formed by adding corresponding terms of the two given sequences. If the first three terms of the third sequence are 2,2,4, compute the fourth term of the third sequence. [/quote]

[hide]

Call the first sequence $a,ar,ar^2,ar^3, \ldots$. Call the second $0,d,2d,3d, \ldots$. Now we have that

$a+0=2$
$ar+d=2$
$ar^2+2d=4$

Thus, $a=2$ and we plug it into our other two equations. Substituting $d=2-2r$ into the third equation gives us $r=2, d=-2$. The fourth therm will then be $ 2^4 - 6=10$.

[/hide]

[quote="math_rules"]A bicycle shop has a display of bicycles, tricycles and unicycles. a total of 200 wheels, 95 seats, and 144 handle grips (one on each side) can be counted in the display. How many types of each cycle are on display? Note: Unicycles do not have handle grips.[/quote]

[hide]We can start by using these equations

3t+2b+u=200
t+b+u = 95
2t+2b+0u = 144

We get
t+b = 72
from the third equation

If we plug that into the second equation we get
72+u = 95
u = 23

We can plug both t+b = 72 and u = 23 into the first equation
t+2(72)+23 = 200
t = 33

And if we put u = 23, and t = 33 into the second equation we have
33+b+23 = 95
b = 39

So there are 33 tricycles, 39 bicycles, and 23 unicycles.

And btw, there are many other ways you can manipulate the equations to get the answer.[/hide]

I know this is way off topic, but how is this intermediate  :? ?


Euler
geometry
circumcircle
incenter
geometry solved

If $ r>0 , D:=\{ (x,y,z) \in {\mathbb R}^{3} \; \; |\; \;  x^{2}+y^{2}+z^{2} \le r \} \;  ,\;  $  let $ \;  A_{i}=(x_i,y_i,z_i) \; ,\; i=1,2,3 , \; $ distinct points  from $ {\mathbb  R}^{3} $ such that $  x_i^{2}+y_i^{2}+z_i^{2} = r  \; ,\;  i=1,2,3 $  (and triangle $\Delta A_1A_2A_3 $ exists) .
[b]QUESTION:[/b] [i]Find the locus of all points $ M , M \in D \;  ,\;  $ having property that  the Euler lines of triangles
\[\Delta A_{1}A_{2}A_{3}\;  ,\; \; \Delta MA_{1}A_{2} \; , \;\;  \Delta MA_{2}A_{3}\; \; ,\; \; \;  \Delta MA_{3}A_{1}\]
are concurrent.
[/i]

Why are your problems always so clumsy? Again, this one irritates me a lot! An Euler line of a triangle lies in the same plane as the triangle itself; hence, if the point M doesn't lie in the plane of triangle $A_1A_2A_3$, then the Euler lines of triangles $A_1A_2A_3$, $MA_1A_2$, $MA_2A_3$, $MA_3A_1$ lie in the planes $A_1A_2A_3$, $MA_1A_2$, $MA_2A_3$, $MA_3A_1$, respectively, and since these planes don't have a common point, the Euler lines can never concur. Hence it remains only to consider points M which lie in the plane of triangle $A_1A_2A_3$. So why on earth do you pose the problem in 3D space? In any case, the locus of all points M in the plane of triangle $A_1A_2A_3$ such that the Euler lines of the triangles $A_1A_2A_3$, $MA_1A_2$, $MA_2A_3$, $MA_3A_1$ concur is the so-called [i]Neuberg cubic[/i] of triangle ABC (this was proven in the paper Antreas P. Hatzipolakis, Floor van Lamoen, Barry Wolk, Paul Yiu, [i]Concurrency of Four Euler Lines[/i], Forum Geometricorum 1 (2001) p. 59-68; the link is http://forumgeom.fau.edu/FG2001volume1/FG200109index.html ). Since you restrict yourself to points M inside D, of course, the required locus is the part of the Neuberg cubic of triangle ABC lying inside the circumcircle of triangle ABC.

I hope I have understood your problem correctly.

  Darij

Indeed, in case when M is in the incircle the solution was found by Walther Janous.
After some days I send you the precise reference (now I visit another city where there is'nt Math.library ). regrads, Alex

[quote="flip2004"]Indeed, in case when M is in the incircle the solution was found by Walther Janous.[/quote]

Yes, in the case when M is the incenter of triangle $A_1A_2A_3$, the Euler lines of triangles $A_1A_2A_3$, $MA_2A_3$, $MA_3A_1$, $MA_1A_2$ concur at the so-called [i]Schiffler point[/i] of triangle ABC. Here is a reference: http://faculty.evansville.edu/ck6/tcenters/recent/schiff.html .

What I wrote in my message before solved the problem for general M.

  Darij


number theory
greatest common divisor
modular arithmetic

Let $ d,k,n$ be integers with $ n>d>1$. If $ d\equal{}gcd(k,n)$, prove there exists an integer $ e$ such that $ 1<e<n$ and $ ke\equiv 0\ (\bmod\ n)$.

Let $ k\equal{}ad$ and $ n\equal{}bd$, $ gcd (a, b)\equal{}1$.

$ ade \equiv 0 \pmod {bd} \implies ae \equiv 0 \pmod {b}$

Thus $ e\equal{}\{b, 2b, 3b, ... \; (d\minus{}1)b\}$, so such integer exists.

In case $ b\equal{}1$, we will not include $ e\equal{}b$.


Try this one, interesting and easy.
Given 100 10-element sets, such that every two sets have precisely 1 element in common. Prove that there is an element that is shared by all sets.

Hmmm.. I might be wrong, but I think $92$ sets re enough: Take one of the sets (call it $A$). Assume each element of $A$ is in at most $9$ other sets. Then there are at most $91=10*9+1$ sets, but we have $\geq 92$ sets, so we have a contradiction. Then there is an element $a$ of $A$ which belongs to $11$ sets ($A$ and at least $10$ more). Take another set, different from the sets which contain $a$ (assume such sets exist). It must have an element $\neq a$ in common with at least $11$ sets, each two of which intersect in $a$ alone. This means that our set has at least $11$ elements, which is false, so we've got the contradiction we were looking for.

I think that if we use sets with $n$ elements, then $n(n-1)+2$ sets are enough to solve the problem in the same way.

Grobber, I wonder when you've become a beginner :D  :D

Sorry :).. However, I think there are some problems in the beginner subforum which aren't at all meant for beginners. This wasn't one of them, as it was easy enough, but there are others.

:) Sorry  :blush:  I'll try to post problems at the appropriate level next time :P . I have been real busy with applications and deadlines, they are killing me!!! I'll check back later on grobber's solution, it looks correct, I'm just skimming thru it.


Find number of sequences $(a_{1},a_{2},\cdots a_{n})$, $a_{i}\in \{0,1,2\}$, for which $\exists k \quad a_{k}=0 \quad a_{k+1}=1$

Let $A_{n}$ be the number of sequences with length $n$ such that there does not exist a $k$ with the desired property.  Then we have the recursion, $A_{1}=3$, $A_{2}=8$, and

$A_{n}=3A_{n-1}-A_{n-2}$ for $n\ge 3$.

Call a sequence "good" if it doesn't contain the subsequence $01$.  Then to prove the recurrence formula: we can add a $0$ or $2$ to any good sequence and get another good sequence, and if we add a $1$, there are $A_{n-2}$ good sequences that end with $0$ out of $A_{n-1}$ total.  This gives the result above.

We can solve this and then the number of sequences is $3^{n}-A_{n}$.


graph theory
Ramsey Theory
Extremal Graph Theory
combinatorics
Extremal combinatorics
IMO
IMO 1978

An international society has its members from six different countries.  The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$.  Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.

http://www.kalva.demon.co.uk/imo/isoln/isoln786.html

[b]Alternate (killing) solution :[/b]
So, in this probem, we're asked to prove that any partition $\{P_1, P_2, \ldots, P_6\}$ of the set $\{1, 2, \ldots, 1978\}$ is such that there exists $i \in \{1, 2, 3, 4, 5, 6\}$, and numbers $a, b, c \in P_i$ such that $a + b = c$. But, by a well-known result (for any integer $k \ge 2$, $R_k \le \lfloor k!e\rfloor + 1$), we have :
\[ R_6 \leq \lfloor 6! \times e \rfloor + 1 = 1958, \]
so, we can even replace 1978 with 1957.

[quote="mathmanman"]http://www.kalva.demon.co.uk/imo/isoln/isoln786.html
[/quote]
Repaired link: http://mks.mff.cuni.cz/kalva/

Consider a complete graph $K_{1979}$ with $1979$ vertices numbered as $1, \ldots, 1979$. Consider  the vertices $a,b \in K_{1979}$, if  the number $|a-b| $ is from country $c_i$, color the edge joining them by color $c_i$. By Ramsey number theorem, on $6$ coloring the graph $K_{1979}$, there will be a monochromatic sub graph with $3$ edges. Since $1979 > \lfloor {e\cdot 6!} \rfloor + 1 \ge R_6(3)$.

So let the edges joining the vertices $a,b,c$ of $K_{1979}$ have same color. WLOG $a>b>c$. Then $a-b , b-c, a-c$ are from the same country and $a-b + b-c = a-c$, so we are done.

Can someone expand on this? I don't understand what $R_k \le \lfloor k!e\rfloor + 1$ signifies and how it relates to the problem.

I think [b]Learner94[/b] has already explained it pretty well.
Anyway, here $R_k$ denotes the [url=http://www.cut-the-knot.org/Curriculum/Combinatorics/ThreeOrThree.shtml]Ramsey number[/url] $R(3, 3, \ldots, 3),$ with $k$ $3,$ and the IMO problem asks for a proof of Schur's theorem, with a bound on the cardinality of the set which is to be $k$-coloured (in the problem, $k = 6$).
You might also want to read the following thread (and follow the links therein):
[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=456057]Partition N s.t. a1 + a2 in B and b1*b2 in A[/url]
The "twice as large as the number of one member from his own country" in the statement comes from the 'issue' raised in the above thread.

I'm wondering how we get the bound $R_k<k!e$. Here is my attempt to prove that. There is a mistake somewhere but I can't see where.

We attempt to partition $S={1,...,n}$ into $k$ disjoint sets each of which is sum-free. One of the $k$ sets $A$ contains at least $n/k$ elements of $S$. The elements of $A$ generate at least $n/k-1$ distinct differences, so there are $n/k-1$ elements of $S$ not lying in $A$. Thus one of the remaining $k-1$ sets $B$ has at least $(n/k-1)/k$ numbers, which generates at least  $(n/k-1)/k--1$ differences, which can't lie in $A$ or $B$. Continuing like this $k-1$ times, we end up with at least $(n-1)/k!-2!/k!-...-k!/k!$ numbers which can't lie in any of the sets. If this number is at least $1$, then any partition of $S$ into $k$ subsets contains a set which is not sum free. This suggests $R_k \le n <k!/(1!+...+k!)$.

We know $1/0!+1/1!+1/2!+...+1/k!$ tends to $e$, so I am close but I obviously made a silly mistake somewhere.

My solution: Suppose the opposite. We have $1978=6*329+4$, thus there is at least one country containing at least $330$ members (call it $A$).
Let $330$ members of $A$ be $a_{1}<a_{2}<...<a_{330}$ ($i-th$ member is labeled with $a_i$). Consider people labeled with $a_2-a_1,...,a_{330}-a_1$. There are $329$ of them and none of them belong to $A$ (If so, then we have $a_i-a_1=a_j$ thus $a_j=a_i+a_1$, which is contradiction with my assumption). But $329=65*5+4$, thus there is country $B$ containing at least $66$ members. Let those members we labeled with $b_{1}<...<b_{66}$. Now consider numbers $b_2-b_1,...,b_{66}-b_1$. None of them belong to $A$ or $B$ thus they are contained in rest of $4$ countries. Also $66=4*16+2$ thus there is country $C$ containing at least $17$ members say $c_1,...,c_{17}$. Consider numbers $c_2-c_1,...,c_{17}-c_1$ (they don't belong to $A,B$ or $C$). There are $16$ of them and $16=3*5+1$ thus there is at least $6$ members in country $D$, say $d_1<...<d_6$. Consider $d_2-d_1,...,d_6-d_1$. There are $5$ of them, contained in rest of $2$ countries. There's a country containing at least $2$ of them, say numbers $e_1<e_2$. Then consider number $e_2-e_1$. It belongs nowhere, but we have $e_2-e_1 \in \{1,2,3,...1978 \}$. Thus, contradiction, so there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country. Q.E.D


Consider a regular polygon with 1000 sides, whose vertices are colored with red, yellow, blue. A [i]move [/i]consists of choosing two neighboring vertices, having different colors, and recoloring them with the third color.

Prove that there exists a finite number of moves such that the resulting polygon is monocolor.

I think the conclusion holds for any $n$-gon where $n = 0$mod[4] and $n \neq 0$mod[3].

In the following, I will use small letters for the vertices, and big ones for the blocks of 4 consecutive vertices which have the same color (Thus R will denote a block rrrr).

Let's give a coloring of the $n$-gon, which is assumed to be not monochromatic, unless we are done...

First step : If the three colors are used, we eliminate the yellow one.

This can be made as follow : Choose a non-yellow vertex, say A, as origin and turn in the clockwise sense. When we reach the first yellow vertex, say B, then go to the end of the block of consecutive yellow vertices which contains B. Then the next vertex after B, say C, is not yellow, so use the rule to change the colors of B and C. Then, use the same reasoning backward from B to eliminate each of the yellow vertices which belong to the same yellow block as B.
Then, continue along the $n$-gon to the next yellow block, and so on...

Thus, we may assume that all the vertices are now colored with one from two colors, say red and blue.
Now, we divide the $n$ vertices into $ \frac {n} {4}$ blocks of 4 vertices.

Note that we have :
(1) rrbb - > ryyb - > bbyb - > brrb - > yyyy and rbrb - > yyyy,
thus since colors play symmetric parts, any block with 2 vertices from one color and two vertices from another one can be changed into a block of 4 vertices of the third color (rbbr is considered in the first case).
(2) rrrb - > rryy - > bbbb (using (1)) and rrbr - > ryyr - > bbbb (idem)
thus, as above, any block with 3 vertices from one color and one vertex from another one can be changed into a block of 4 vertices of the color of the single vertex.

It follows that each block of 4 consecutive vertices can be changed into a monochromatic one.
Then (second step) we transform each block to obtain only monochromatic ones (but in that case, we may have blocks from the three colors).

Claim 1 : In terms of colors, we may commute two consecutive blocks.

Proof : Consider two consecutive blocks with different colors (otherwise there is nothing to do...), say BR.
Then, using (1) :
BR = bbbbrrrr = bb|bbrr|rr - > bbyyyyrr = bbyy|yyrr - > rrrrbbbb = RB, which proves the claim.

Claim 2 : On the blocks, the initial rule is satisfied.

Proof :
We only have to prove that BR - > YY since the colors are playing symmetric parts.
But, using (2) :
bbbbrrrr = bbbyyrrr = bbby|yrrr - > yyyy|yyyy = YY, thus the claim is proved.

Third step : From claim 2, as in the first step, if the three colors are used for the blocks, we may eliminate one. Thus, we may assume that there are only red blocks and blue blocks. Moreover, (1) and (2) remains true for the blocks. If all blocks have the same color, we are done. Otherwise, use claim 1 to group red blocks to form an unique string of red blocks and blue blocks to form an unique string of blue blocks. Wlog, we may assume that there are at least 3 red blocks.
Now use (2) to change blue blocks into red one by RBBB - > BBBB. Thus we may assume that there are only red blocks (in which case we are done) or that there are no more than 2 blue blocks.
Note that RBRR -> YYRR thus, we only have to overlook the case of two blue blocks.
If $n = 2$ mod[3] then $ p = \frac{n} {4} = 2$ mod[3], thus we have $p-2$ red blocks, which can be changed into blue ones using (2) that is RRRB - > BBBB. Since $p-2 = 0$ mod[3] we then obtain a monochromatic blue configuration and we are done.
If $n = 1$ mod[3] then first use (1) to obtain 4 consecutive Y (RBBR - > YYYY) so that there are exactly $p-4 = 0$ mod[3] red blocks. Then transform the red blocks into yellow ones similarly as above.

Pierre.

my soln. follows basically the same arguments, only that I have taken more cases. I feel that this problem was very difficult considering that students ages 13-14 years were to solve it.
i found my soln (without actually writing it nicely) in about 30-40 mins. i assume I would have needed between 1h - 2h in the actual contest to give a full solution for a full mark.
how long did it took you pierre?

Hi all!
This problem resembles the following russian problem (Informatics Problem)
Given n lamps, 3 colors, same condition, make a sequence of moves that will make all of one color.
This is what I meant by a programming section, problems and ideas, not actual evaluating and so on....
Now, the solution is the same.
Color in the same color last 4, then the first n-4 (recursion), and then make all of the same color. :)))

I used a long time (not considering the writing here) because I realized I made an error during the writing. I was using a descending argument which turned to be untrue and that I really wanted to be working!!! After at least one hour I finally saw that it was much easier and that the solution can be completed as in the end (the cases $n=1$ mod[3] or $n=2$ mod[3]....).
Thus I would say at least three hours.
In another hand, I use to be slow....

Did a candidate solve it during the competition?

Pierre.

I think that one student got 8 points and anoher 7 (out of 10 max)...

both of them were pretty close to solving the problem: they were kinna left with the case when you have all of them of one color except one of another...

the rest had only 0's, 1's and 2's...

i also think that the problem was way to difficult for juniors, but then again there's one like this every year, or at least when i was junior there was one/year....

Hi all!

I forgot to write the solution till the end, and I have 1 mistake, it must be n-3
Color in the same color last 4, then the first n-3 (recursion), and then make all of the same color. :)))
How, would you ask?
Take a move on n-3 and n-2, then n-2 and n-1, then n-1 and n-4. The trick is that first n-3 are of the same color.
Could somebody write if this is correct?


hi,

I think its ask to much...  :blush:  but I would like if someone give me one diofantine equation and its solution to do a kind of joke to a special friend of mine... I already use some problems of old imo's (pre-historic ones) but he always find very quickly the solution... which is very irritating...  :wallbash_red:

one more request, the solution has to be a finite group (not an infinite group)

thank you

i hope there still exist, in this world, real gentlemen to save me

before i will leave you in peace i want to apologize for my "english" (if we can call it that...) but i'm not english...

What about [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=28590]this one?[/url]  :D

i just saw your message, i copy down the problem and the solution (i'm not very good at math...) it seems fairly good... thank you.

Sorry, I know this is spam, but I just could not stop:  :rotfl:  :rotfl:  :rotfl:  :rotfl: . I will delete my message after a while, of course. By the way, give him another difficult one (extremely difficult, I think): find all integers $a,b,c,x,y,z$ with $a,b,c$ positive, $ab+bc+ca\geq x^{2}+y^{2}+z^{2}$ and $ax^{2}+by^{2}+cz^{2}=2xyz+abc-1$.  :D  :D

here you are  :find all natural number $a;b$ such $5^{a}-3^{b}=2$.
and also $a^{m}+1=(b^{k}+1)^{n}$ :ninja:  :D

ok! thank you very much for yours replies but i have to have the solutions because i'm not very good at math... without solutions, there is no point...


Find the number of positive integer solutions of $ (x^{2}\plus{}2)(y^{2}\plus{}3)(z^{2}\plus{}4)\equal{}60xyz$.


limit
floor function
number theory unsolved
number theory

Prove that exist real number a such as 1 < 3{$ {a^n }$}< = 2 for every n is possible natural number
-------------------------------------

It is not true.
Because
$ a>1\Longrightarrow\lim_{n\to\infty}|a^n|\equal{}\plus{}\infty$
$ a<1\Longrightarrow \lim_{n\to\infty}3|a^n|\equal{}0$
$ |a|\equal{}1$ then it is not true.
So there is not a such number.

Undoubtedly by $ \{ a^n \}$ he means the fractional part of $ a^n$, i.e. $ a^n \minus{} \lfloor a^n \rfloor$.

[quote="aviateurpilot"]we have to prove that $ \bigcap_{n\in\mathbb{N}^*}S_n\neq \emptyset$
where $ S_n \equal{} \bigcup_{k\in\mathbb{N}}]\sqrt [n]{k \plus{} \frac {1}{3}},\sqrt [n]{k \plus{} \frac {2}{3}}]$[/quote]
Why it is not empty?
I think we can find a, suth that $ a^3\minus{}pa^2\plus{}qa\pm 1\equal{}0, p,q\in Z$.
If it had one real root a and 2 complex root $ z_1,z_2$ and p is odd, then these a work.

[quote="Rust"][quote="aviateurpilot"]we have to prove that $ \bigcap_{n\in\mathbb{N}^*}S_n\neq \emptyset$
where $ S_n \equal{} \bigcup_{k\in\mathbb{N}}]\sqrt [n]{k \plus{} \frac {1}{3}},\sqrt [n]{k \plus{} \frac {2}{3}}]$[/quote]
Why it is not empty?
I think we can find a, suth that $ a^3 \minus{} pa^2 \plus{} qa\pm 1 \equal{} 0, p,q\in Z$.
If it had one real root a and 2 complex root $ z_1,z_2$ and p is odd, then these a work.[/quote]
$ \exists a\in\mathbb{R},\forall n\in\mathbb{N}^*: \ 1 < 3\{a^n\}\le 2$
$ \iff \exists a\in\mathbb{R}^ \plus{} ,\forall n\in\mathbb{N}^*: \ 1 < 3\{a^n\}\le 2$
$ \iff \exists a\in\mathbb{R}^ \plus{} ,\forall n\in\mathbb{N}^*,\exists k\in\mathbb{N}: \ k \plus{} \frac {1}{2} < a^n\le k \plus{} \frac {2}{3}$
$ \iff \exists a\in\mathbb{R}^ \plus{} ,\forall n\in\mathbb{N}^*: \ a\in S_n$
$ \iff \bigcap_{n\in\mathbb{N}^*}S_n\neq \emptyset$


geometry
geometric series
number theory
calculus
calculus computations

I was just wondering how all the tests (nth term test, geometric series, telescoping, etc.) and Sequences and Series in general is helpful in the real world? Just like Statistics (which is actually applicable), there must be a reason.

You don't think it's significant to know whether certain infinite series diverge or converge?  I can easily imagine plenty of situations where that might be important.

[quote="Magnara"]They aren't.  Most pure math isn't.[/quote]
Every type of mathematics was developed for a reason, and since it deals with something in nature, it defines something in nature and thus it is useful for many things.  Even indirectly, all of these pure mathematics has applications in sciences.

Masoud Zargar

That is more philosophical doublespeak than a correct historical account.  It is perfectly possible to develop theory before any real world applications become available (e.g, algebraic geometry, number theory :!: ) or have no real world applications at all.


Hello Everyone,

Recently there has been a lot of spam. Moderators are locking the topics, which is now unfortunately necessary to stop spam right in its tracks, but we shouldn't have to have them locked in the first place. I realize that I have been spamming my share as well, not only in this forum, but other forums as well. However, I have made a resolution to stop spamming. I hope others will as well.

I have decided the create some guidelines to follow. I may be incorrect on certain things, and please correct me if I am.

1. Do not post a second solution to a problem unless

-- You arrived at a different answer.

-- You have a different way of getting to the answer.

-- You noticed a mistake someone made.

-- You wish to clarify something that was unclear in someone else's post.

2. If you think that someone wrote a great explanation,

-- Rate the post 4, 5, or 6 cubes.

-- Private message the person if you want to, and tell them you like the explanation.

-- Do not make a post saying, "Nice explanation, _____________!"

3. If someone posts spam,

-- Rate the post 1 cube.

-- Private message the person detailing why it is spam, in case they did not know, and ask them to kindly abstain from spamming in the future.

-- Do not make a post saying, "Hey! That's spamming! Don't do it, __________!"

4. Keep in mind that each thread is only, and I repeat, only, for purposes of solving the problem shown.

-- Be careful not to stray off topic.

-- Before posting, think hard whether your post is necessary or not. Remember, you do not have to press the "Submit" button.

-- Do not post for a higher post count. What's the point of having a 1000 posts if they're all spam?

5. When you see a problem that involves a "broad" concept, which you do not understand,

-- Try not to make a new post and ask. For example, if a problem involves, say, proportions, and you do not know anything about proportions, there are two things you can do. One, you can private message the person who answered the problem and ask for details on proportions, or better yet, two, start a new thread in Classroom Math on Proportions.

-- If somebody ignores this guideline, and asks anyway, and you wish to answer their question, private message them and answer their question, or bring this guideline to their attention.

Thank you for taking the time to read this. If I missed anything, or you disagree with something, please let me know so I can correct this post.  :)

i completely agree with this, however, this statement,
[quote]Be careful not to stray off topic. [/quote]
might be a little harder

threads stray off topic slowly, and some people might not even notice it
first, one person says something related to the topic, and the second person replies, and could make it a little off topic
but, after a few more posts, it gets extremely off the topic of the first post
unfortunately, this kind of things move slowly off topic, therefore, people might not know that they're going off topic
they are, after all, just reponding to posts made earlier

but, that's where you can help
if you see that topics have gone off topic, just post saying that the thread has gone off topic and then try to post something that can help if get back on topic
this way, people will repond to the post, and hopefully will stay on topic this way

That's a very good idea, vallon.

In addition:

The best thing for this is to think very very very hard whether this post is absolutely necessary. Would it be better to press submit, or to talk to the person privately about whatever you want to say? Remember: each thread is for that problem, and that problem only!

And this reminds of something I neglected, so I edited my original post. Please look at #5 if you have not already done so.

Also, I would like to add, if someone answers a question, just private message the person thanks or rate it. Don't actually post thanks

yes, i agree

but just to clarify, izzy, u said to look at #5,
do u mean the fifth bullet first or what?
there's no actual 5 on the first post....

dragon brings up a good point. If someone breaks the guidelines, do not respond to it on the thread. You can thank them privately.

@vallon

I just edited it.

oh, ok
and might be treated as spam, but

[quote]dragon brings up a good point. [b]If someone breaks the guidelines[/b], do not respond to it on the thread. [b]You can thank them privately[/b]. [/quote]

why would u thank someone for breaking the guidelines?

Sorry for not being clear. I meant that if they broke the guidelines for telling in a post, "Good explanation!" But in any case, if someone breaks the guidelines, tell them so in private.


If the ratio of $2x-y$ to $x+y$ is $\frac{2}{3}$, what is the ratio of $x$ to $y$?

$\text{(A)} \ \frac{1}{5} \qquad \text{(B)} \ \frac{4}{5} \qquad \text{(C)} \ 1 \qquad \text{(D)} \ \frac{6}{5} \qquad \text{(E)} \ \frac{5}{4}$

[hide]$\text{Answer: (E)}$

Set up the equations and do some simplification.
$\frac{2x-y}{x+y}=\frac{2}{3}$
$6x-3y=2x+2y$
$4x=5y$
$\frac{x}{y}=\frac{5}{4}$[/hide]


Can someone who worked thru "Art and Craft Problem Solving"

and " Problem Solving Strategies" give me some suggestions

on "how to work thru them"?

I don't know about PSS, but A&CoPS can be a little frustrating because there are no solutions. In the preface and first couple chapters, the author says that you won't be able to solve every problem. Just attack every one (remember, they're all "exercises"), and if you can't solve it go back later.

PSS is great in that it has solutions, as well as weaker problems at the beginning of each chapter problem section, so you can work your way up to doing the olympiad stuff. Just pick something you can work with and stick at it; don't get stuck on one problem for more than an hour to 1.5 hours...you learn the most before that, and afterwards it's usually fruitless.

Thanks a lot for the replies!

Any more suggestions?


hi

i'm trying to solve these linear equations using R-REF but it keep giving me wrong results .. please any one help ..

here's the tree equations

2x+3y+4z=5
3x+5y+7z=9
4x+7y+11z=18

and here is the operation that i made to solve this system
1/2 * R1
-3R1+R2
-4R1+R3
2R2
-R2+R3
-2R3+R2
-2R3+R1
-3/2R2+R1

the results that i get is ( x = -18 , y = 7 ,z = 5)

correct ( x = 3 , y = -7 , z = 5 )

Whers is the problem ?

There's a better way, to my opinion.

[hide="My solution"]
We solve it directly:

2x+3y+4z=5
3x+5y+7z=9
4x+7y+11z=18

4x+6y+8z=10
4x+7y+11z=18

8=y+3z

12x+20y+28z=36
12x+21y+33z=54

y+5z=18

2z=10, z=5

We plug z into all three equations to get:

2x+3y=-15
3x+5y=-26
4x+7y=-37

4x+6y=-30
4x+7y=-37

y=-7

We plug it into the equation

2x+3y=-15

and we get x=3[/hide]

Questions about matrix computations belong in the [url=http://www.artofproblemsolving.com/Forum/index.php?f=353]Matrix Algebra - Computations and Tutorials[/url] section of this site.

Also, the problem is that you screwed up your arithmetic somewhere and you should double-check it.

i have to solve it using matrices because i'm studying this topic .. but i got it  :lol:

i forget to add [b]-[/b] sign in some step ..

now i get correct results

Having alternated between teaching linear algebra and teaching numerical analysis a decade or so ago, I wound up having the habits of the numerical analysis affect the way I thought about linear algebra. With Gaussian elimination, I picked up two habits. (1) Don't bother making the pivots 1 - leave them as you found them. (2) Don't clean up above the main diagonal. Get to upper triangular (or nonreduced row-echelon) form and then solve the rest of the way by back-substitution.

It goes faster that way, and I make fewer mistakes (although, I'll admit that it took me two tries to get to what's shown below).

$\begin{bmatrix}2&3&4&5\\3&5&7&9\\4&7&11&18\end{bmatrix}\longrightarrow \begin{bmatrix}2&3&4&5\\0&\frac12&1&\frac32\\0&1&3&8\end{bmatrix}$

$\longrightarrow\begin{bmatrix}2&3&4&5\\0&\frac12&1&\frac32\\0&0&1&5\end{bmatrix}$

And now the back substitution:

$z=5.$

$y=2\left(\frac32-z\right)=2\left(\frac32-5\right)=-7$

$x=\frac12(5-3y-4z)=\frac12(5+21-20)=3$

And the check:

$\begin{bmatrix}2&3&4\\3&5&7\\4&7&11\end{bmatrix}\begin{bmatrix}3\\-7\\5\end{bmatrix}=\begin{bmatrix}5\\9\\18\end{bmatrix}.$ It checks.

You'll notice that I did many fewer row operations than those listed by 3070. Fewer row operations, fewer ways to go wrong.


Find the largest constant $ t$ for which the following inequality holds for $ a,b,c\geq 0$:

$ \frac {a^{2}}{b \plus{} c} \plus{} \frac {b^{2}}{a \plus{} c} \plus{} \frac {c^{2}}{a \plus{} b}\geq t(a \plus{} b \plus{} c)$

(inspired by [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=148725]this one[/url])

$a=b=c=1$ we have $t\leq 1/2.$

But $LHS+a+b+c=(a+b+c)(\frac{a}{b+c}+\frac{b}{c+a}+\frac{c}{a+b})\geq \frac{3}{2}(a+b+c)$, so maximum of $t$ is $1/2$.


How many of you have experience doing Fermi Questions?

How can I prepare for this event?

You don't.

Seriously.

And yes, I'm in Science Olympiad as well, so this isn't mindless spam -_- .


If $x=\sqrt{17+\sqrt{17+\sqrt{17+\sqrt{17+...}}}}.$ Then $x= \frac{k+\sqrt{w}}{2}$ where $k$ and $w$ are positive integers. Find the value of $k+w$.

I just understood the ans. I can't delete this so I'll leave it up  :blush:

try squaring it..remember it goes to infinity..see what you get

[hide="Here is the method, for those who do not know how to do this:"]
\[x= \sqrt{17+\sqrt{17+\sqrt{17+\sqrt{17+...}}}}\implies x= \sqrt{ 17+x}\implies \boxed{k+w=70}\] [/hide]


Solve in positive integer numbers  the equation $\sqrt{x+2\sqrt{3}}=\sqrt{y}+\sqrt{z}.$

Squaring gives $x+2\sqrt{3}=y+z+2\sqrt{yz}$

Assume $2\sqrt{yz}=a+2\sqrt{3}$. Then squaring gives $4yz=a^2+12+4a\sqrt{3}$. Obviously, $a=0$, hence we get

$yz=3\land y+z=x$

Taking all the possible values for $y,z$, we get the solutions

$(4,1,3),(4,3,1)$

$x-y-z=2(\sqrt{3}-\sqrt{yz})$,
LHS $\in \mathbb{Z} \implies$ RHS $\in \mathbb{Z}$
then $\sqrt{3}-\sqrt{yz}=0$, since $\sqrt{z}$ in initial equation, $z\ge 0$, $y=\frac{3}{z}$, and then $z|3\implies z \in \{1,3\}$, and $x-y-z=0$,
$z=1\implies y=3\implies x=4$ or $z=3\implies y=1\implies x=4$


I am currently applying to the [url=http://www.mccme.ru/mathinmoscow/]Math in Moscow[/url] program.  Does anyone know anything about it?

I work in this program, feel free to ask me about anything you are interested in. Our official website
[url]http://www.mccme.ru/mathinmoscow/index.php[/url]
and our Facebook group
[url]http://www.facebook.com/group.php?gid=2204798557[/url]

A post of one of the current semester students descibes very well one of the features of the program
[url]http://pgadey.wordpress.com/2010/02/16/math-gab/[/url]

Guess that my answer might be  late, sorry. Hope it will be helpful to someone else as well.

Best,
Vladimir.


Let $ p$ be a prime number and $ k,n$ positive integers so that $ \gcd(p,n)\equal{}1$. Prove that $ \binom{n\cdot p^k}{p^k}$ and $ p$ are coprime.

I see another approach.
Let us denote $ v_{p}(n)$ the exponent of $ p$ in the prime representation of the natural number $ n$.It is trvial the fact that for $ a,b \in \mathbb{N}$ we have $ v_{p}(ab)\equal{}v_{p}(a)\plus{}v_{p}(b)$ and also $ v_{p}(\frac{a}{b})\equal{}v_{p}(a)\minus{}v_{p}(b)$.It is also known the fact that : \[ v_{p}(n!)\equal{}\sum_{k\equal{}1}^{\infty} \left[ \frac{n}{p^{k}} \right]\equal{}\left[\frac{n}{p}\right]\plus{}\left[\frac{n}{p^{2}}\right]\plus{}...\]
In order to prove $ \dbinom {np^{k}}{p^{k}}$ and $ p$ are coprime , we must show that $ v_{p}(\dbinom{np^{k}}{p^{k}})\equal{}0$.
But this is true because:\[ v_{p}(\dbinom{np^{k}}{p^{k}})\equal{}v_{p}(\frac{(np^{k})!}{p^{k}!(np^{k}\minus{}p^{k})!})\equal{}v_{p}((np^{k})!)\minus{}\left(v_{p}(p^{k}!)\plus{}v_{p}((np^{k}\minus{}p^{k})!)\right)\]
\[ \equal{}\sum_{i\equal{}1}^{\infty} \left[\frac{np^{k}}{p^{i}}\right]\minus{} \sum_{i\equal{}1}^{\infty} \left(\left[\frac{p^{k}}{p^{i}}\right]\plus{}\left[\frac{(n\minus{}1)p^{k}}{p^{i}}\right]\right)\]
\[ \equal{}n(p^{k\minus{}1}\plus{}p^{k\minus{}2}\plus{}...\plus{}p\plus{}1)\minus{}(p^{k\minus{}1}\plus{}p^{k\minus{}2}\plus{}...\plus{}p\plus{}1)\minus{}(n\minus{}1)(p^{k\minus{}1}\plus{}p^{k\minus{}2}\plus{}...\plus{}p\plus{}1)\plus{}\sum_{i\equal{}1}^{\infty} \left[\frac{n}{p^{i}}\right]\minus{}\sum_{i\equal{}1}^{\infty} \left[\frac{n\minus{}1}{p^{i}}\right]\equal{}\sum_{i\equal{}1}^{\infty} \left[\frac{n}{p^{i}}\right]\minus{}\sum_{i\equal{}1}^{\infty} \left[\frac{n\minus{}1}{p^{i}}\right]\]
Because $ \gcd(n,p)\equal{}1$ it follows that $ \sum_{i\equal{}1}^{\infty} \left[\frac{n}{p^{i}}\right]\equal{}\sum_{i\equal{}1}^{\infty} \left[\frac{n\minus{}1}{p^{i}}\right]$ so $ v_{p}(\dbinom{np^{k}}{p^{k}})\equal{}0$ meaning $ \gcd(p,\dbinom{np^{k}}{p^{k}})\equal{}1$.

[quote="ZetaX"]Trivial by Lucas theorem.
Or write the binomial coefficient out and look how often each term is divisible by $ p$.
You even have (for $ p > 3$) the much stronger property $ \binom{n \cdot p^k}{p^k} \equiv n \mod p^{k \plus{} 3}$ for arbitrary $ n$.[/quote]
It is true only for Wolstenholm's prime.
Exactly $ \binom{np^k}{p^k}\equiv n\mod p^{k\plus{}2}, p>3.$

[i]A good solution , Vrajitoarea Andrei :)[/i]


[quote="nguoivn"]Given $ a, b, c \geq\ 0$ satisfy $ a \plus{} b \plus{} c \equal{} 3$. Prove that:
$ 8 \sum\ a^2b^2 \plus{} 21abc \plus{} 4\sum\ ab^2 \plus{} 8 \sum\ a^2b \leq\ 81$[/quote]
$ a\equal{}1,582740502 ; b\equal{}1,417259498 ; c\equal{}0$
 ;)

What a pity! I have just lost something with it :(
But thanks, my brother   :oops:


Everybody here knows this problem.

There is a problem "similar".

Supose there is $ 2 n$ doors and behind only one door there is a prize, the others don't have nothing.
There rules for the game are:

1 - The Guest choose one door, say 1.
2 - The Host OPEN a door that there isn't the prize, say 3.
3 - The Guest choose a door that he had not choose yet, say 2.
4 - The Host ....

In the end the Host had opened $ n$ doors and the guest had choosed $ n$ different doors.

After that the Host says "You can now chose your door at freedom. what door do you choose?"

What is the door that a inteligent Guest would choose? The first door that he had choosen? the second? the n-th door?

This game is different from Monty Hall in an important way: we must allow the host to be able to open doors the guest has chosen (or, for $ n \equal{} 1$, even the door the guest is currently holding) -- perhaps it would be better with $ 2n \plus{} 1$ doors in total, so $ n \plus{} 1$ left to choose from?  (Otherwise, answering the question seems very much to depend on which doors the guest chose [i]and[/i] the host opened.)

In my variation, if $ p_k$ is the probability that the prize is behind the $ k$th door we picked (with $ p_{n \plus{} 1}$ the probability that it's behind the last, unpicked door) then $ p_1 \equal{} \frac {1}{2n \plus{} 1}$, $ p_{k \plus{} 1} \equal{} (1 \minus{} p_1 \minus{} \ldots \minus{} p_k)\frac {1}{2n \plus{} 1 \minus{} 2k}$ for all $ k \in [1, n]$.  But then it's simple to check that $ p_{k \plus{} 1} \equal{} \frac {2n \minus{} 2k \plus{} 2}{2n \minus{} 2k \plus{} 1} \cdot p_k$ (unless I've messed up the arithmetic) and so in particular $ p_{k \plus{} 1} > p_k$, so the best bet is to take the last door.  (Note that the case $ n \equal{} 1$ is exactly the Monty Hall problem.)

Suppose there is $ n\equal{}3$ doors. This is Monty Hall.

But if the number of doors is Odd, in the end, there is a door that the guest did not had chosen! can you see? And the probability of this door to have the prize is greater than the others. Is a easy task to prove that.

But if $ n$ is Even, the first door that the guest had chosen is the door with high probability to have a prize.

But in essence is the same. The last door or the first door.

this problem I solved for the 2 alternatives, odd and even. It's fairly simple if you make a tree.

The more difficult problem would be if the host CAN eliminate a door that the guest had chosen.  :o !

So in the end the sum of the eliminated doors and the doors chosen are different than the number of doors.

This problem I had not yet solved.

[quote="EulerIntegral"]The more difficult problem would be if the host CAN eliminate a door that the guest had chosen.  :o ![/quote]
Let me restate: the way you've described the game, the host may be [i]forced[/i] to open a door the guest has already chosen.  For the most trivial case, take $ n \equal{} 1$ (so two doors): if the guest chooses the door without the prize, the host [i]must[/i] open the door the guest chose.  This is true for any even number of doors: if the guest never chooses a door with the prize behind it, in his final act the host must either open the door with the prize or open a door the guest has already chosen.  In the odd-size game there is one door left over at the end and we don't have this problem (and this last door is always the best choice, as I showed and you asserted), but you haven't explained what to do in this case in the even-size game.  (And I don't believe your assertation that the first door chosen will always be best, either.)

ignore my last post, this last problem is really simple, I missed the mark without think about it carefully.

I forget (I didn't even thougth) to say that if the host can open a chosen door, it will ever terminate if strange things.

So the host need to stop after some steps before it.

But don't mind. I already made a better proof for this. just forget. I was mislead by the grow of probability.


algebra polynomial calculus integration function geometry derivative

I believe that polynomials of the form Z^N where Z is a complex-valued variable, can still be derived as though they are real-valued variables, in this case, D/DZ = NZ^(N-1). Or its integral, Z^(N+1) + C divided by (N+1) where C can also be complex.

And e^Z could be integrated as a dual integral e^(X + iY) DX DY, where your first variable is bound by the real component and the second variable is bound by the imaginary component. And D/DZ = e^Z.

I always regarded e^Z in the complex plane as being e^X (cos Y + i sin Y) so del Z/del X = e^X (cos Y + i sin Y) and del Z/del Y = e^X (i cos Y - sin Y) Correct me if I'm wrong but this is when only the real (or imaginary) components change. But I do know these are holomorph functions, i.e. differentiable in the complex plane.

[quote="CEM_College_Champ"]I believe that polynomials of the form Z^N where Z is a complex-valued variable, can still be derived as though they are real-valued variables, in this case, D/DZ = NZ^(N-1). Or its integral, Z^(N+1) + C divided by (N+1) where C can also be complex.[/quote]Yes, the calculus of complex algebra works exactly like the calculus of real algebra. If it didn't, we wouldn't spend so much time on it.
[quote="CEM_College_Champ"]And e^Z could be integrated as a dual integral e^(X + iY) DX DY, where your first variable is bound by the real component and the second variable is bound by the imaginary component.[/quote]No. Integrating with respect to a complex variable is a single integral; we have antiderivatives and we have line integrals, but area integrals are not a major subject.

[quote="CEM_College_Champ"]I always regarded e^Z in the complex plane as being e^X (cos Y + i sin Y) so del Z/del X = e^X (cos Y + i sin Y) and del Z/del Y = e^X (i cos Y - sin Y)[/quote]The right place to take that idea is that it's a function from $ \mathbb{R}^2$ to $ \mathbb{R}^2$. That derivative is the matrix $ \begin{bmatrix}e^x\cos y&\minus{}e^x\sin y\\e^x\sin y&e^x\cos y\end{bmatrix}$. Matrices of the form $ \begin{bmatrix}a&\minus{}b\\b&a\end{bmatrix}$ act exactly like complex numbers under multiplication; the derivative being of this form is exactly the same as the derivative making sense as a complex number.


calculus
integration
logarithms
calculus computations

Calculate

$ \displaystyle\int\limits^{e^{e^{e^e}}}_{e^{e^e}} \dfrac{1}{xlnxln(lnx)ln(ln(lnx))}dx$.

\[u=ln(ln(ln(x))) \implies du=\dfrac{dx}{xln(x)ln(ln(x))}\]

Therefore

\[\displaystyle\int_{e^{e^{e}}}^{e^{e^{e^{e}}}} \dfrac{dx}{xln(x)ln(ln(x))ln(ln(ln(x)))} = \displaystyle\int \dfrac{du}{u} = ln(u) = ln(ln(ln(ln(x)))) \Bigg|_{e^{e^{e}}}^{e^{e^{e^{e}}}} = 1 - 0 = 1\]

Generalizing for

\[\displaystyle\int \dfrac{dx}{xln(x)ln(ln(x)) \cdots \underbrace{ln(ln(ln(\cdots (ln(x))\cdots))}_{n \text{ times }}}\]

\[u = \underbrace{ln(ln(\cdots (ln(x)) \cdots )}_{n \text{ times }} \implies du = \dfrac{dx}{xln(x)ln(ln(x))\cdots \underbrace{ln(ln(\cdots (ln(x)) \cdots))}_{n-1 \text{ times }}}\]
Therefore

\[\displaystyle\int \dfrac{dx}{xln(x)ln(ln(x)) \cdots \underbrace{ln(ln(ln(\cdots (ln(x))\cdots))}_{n\text{ times }}} = \displaystyle\int \dfrac{du}{u} = ln(u) = \underbrace{ln(ln(\cdots (ln(x)) \cdots ))}_{n+1 \text{ times }}\]


Senior Division No. 15

How many different pairs of 2-digit numbers multiply to give a 3-digit number with all digits the same?

Is the answer 6 or 7? My answer is 6, but apparently the official answer is 7. Can someone please show me the solution? Thanks.

Since $111=3\cdot 37$, you can write $3n\cdot 37$ for $n=4,5,6,7,8,9$, and those are basic 6 solutions. But observe that for $n=8$ you have $24\cdot 37=12\cdot 74$, which is the 7th solution.


Prove n! is not a perfect square for all integers n.

Actually, n! is a perfect square for n=0 and n=1.  :)  Above that, Bertrand's postulate does it. Any prime between n/2 and n can only appear once in the factorisation of n!.

Fine.  I meant all integers n>=2 :)

Can you find a solution without using Bertrand's Postulate?  There is one.


algebra polynomial ARML Duke college AMC AIME

Did anybody get this one?  It was something like:

$P(x)$ is a polynomial of degree 2006 such that $P(k) = \frac{1}{k}$ for integers k, $1 \leq k \leq 2007$.  Find $P(2008)$.

This looked pretty much impossible, and it may well be impossible the way I've written it here.  If anybody has the exact question, please post it.  Also, I would appreciate a solution to #30 and #28 (I didn't get a chance to look at USC).

(Edited, thanks gauss202)

The problem stated that $P(x)$ is a polynomial of degree 2006 such that $P(k) = \frac{1}{k}$ for integers k, $1 \leq k \leq 2007$. That being said:

[hide]The key is to use the given information to make a polynomial with known [i]roots[/i]. Then you could factor it and manipulate it more easily. You can't simply subtract 1/x from $P(x)$ because that wouldn't give you a polynomial in x.

So instead multiply both sides by x and subtract 1 to get $xP(x)-1 = 0$. Call this polynomial g(x). This polynomial is of degree 2007 and has roots {1, 2, 3, ..., 2007}. So $g(x) = a(x-1)(x-2)\cdots(x-2007)$ for some constant a.

To find the value of a, let $x = 0$.
By the definition of g, $g(0) =-1$, and by the factorization of g, $g(0) =-a(2007!)$
Therefore $a = \frac{1}{2007!}$.

Now let $x = 2008$,
$g(2008) = 2008 P(2008)-1 = a(2007!) = 1$
So $P(2008) = \frac{2}{2008}$.[/hide]

They've already updated the [url=http://www.math.sc.edu/contest/2006-2007/]website[/url].  Solutions aren't up yet.

Numbers 28 and 29 are fairly common, popular contest problems.

I've seen very closely related variants of 28 on the 2002 USC (see in the hide tag below) and in the USSR Olympiad Problems book.

Number 29 has shown up just about everywhere.  There was an ARML problem about which I remember putting in my ARML marathon (though, a LOT of ARML problems have been in my marathons :D ).

I'm pretty sure there was a Mandelbrot problem about it (I know there's a Mandelbrot team round on Lagrange Interpolation which is basically what you do with that problem...it's very good practice if you get a chance).

[url=http://www.math.duke.edu/dumu/contests/problems/team_round_2005.pdf]Duke Team Round 2005[/url] problem 9 is basically the same idea.

There was a problem on a WOOT test last year which asked a more generalized question.

[hide="Number 28"]
We have \[x = \sqrt{3+\sqrt{3+\sqrt{3+x}}}.\]

Now what happens if we plug the whole RHS of this equation back in for the $x$ which is inside the nested radical?  We get:

\[x = \sqrt{3+\sqrt{3+\sqrt{3+\sqrt{3+\sqrt{3+\sqrt{3+x}}}}}}.\]

What if we keep doing this (i.e. what's the limit as we go to infinity)?  Well, we'll have:

\[x = \sqrt{3+\sqrt{3+\cdots}}.\]

Thus $=\sqrt{3+x}\Rightarrow x^{2}-x-3=0$ which gives $x = \frac{1\pm\sqrt{13}}2.$  So we have two possible values of $x$.  But notice that one of these roots is positive and the other is negative.  Looking back at the original equation we see that $x$ is the square root of something which means $x$ must be nonnegative.  So there is only one possible value of $x$.

[hide="Comment 1"]
Notice that using the same reasoning, all of the following have the same roots:

\begin{eqnarray*}x &=& \sqrt{3+x}\\ x &=& \sqrt{3+\sqrt{3+x}}\\ x &=& \sqrt{3+\sqrt{3+\sqrt{3+x}}}\\ x &=& \sqrt{3+\sqrt{3+\sqrt{3+\sqrt{3+x}}}}\\ &\vdots& \end{eqnarray*}[/hide]

[hide="Comment 2"]
Even for people who have been exposed to problems such as 'evaluate $\sqrt{1+\sqrt{1+\cdots}}$', this tweak to the problem can still be very hard to figure out on one's own.  I suspect many of those who got this right had seen something like it before.  Except, well, I heard Harry considered the graph of the function.  So it was possible to still get it, though the graphing approach probably leaves you with less certainty.[/hide][/hide]

If you look back at the 2002 USC exam, this was problem 17:

What is the sum of all the solutions to the following equation:

\[{x = 1+\frac 1{1+\frac 1{1+\frac 1{1+\frac 1{1+\frac 1{1+\frac 1{1+\frac{1}{x}}}}}}}}.\]

See also: [url=http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=1991]AIME 1991[/url] #7

EDIT: yea i just checked, 29 is indeed like the same problem from chess64's mock amc.

I can't find the problems or the winners.  In fact, I don't see anything new on the website.  Where should I look?

Joe:
Yeah, I also noticed that every tough problem I had seen a variant of before.  So I was kind of surprised there were no perfect scores, but 146 is still amazing.  I missed #11 because I misread a less than sign as a greater than sign.  :rotfl:   I was so excited when I saw that problem, too, because I knew exactly how to do it...  :(

[quote="joml88"]Keep refreshing your browser until you see it.  If you're using Google Accelerator that's why you have to refresh so much.[/quote]

Wow, that's a really big problem.  I'm gonna uninstall Google Accelerator because of it.

But Seva, how did you get that for #30?

EDIT: WOW the team scores were close.  LOL, one more ciphering question...

what level would you say these contests are mathcounts wise?

Hm, well the easiest problems are MathCounts level.  Anything past #10 is probably state or national level, and anything past #15 is probably national level.

The problems posted here are the hardest ones from USC, and probably harder than anything on MathCounts.


[quote="mathdog15"]Hey can someone help me with this problem?

Six distinct integers are randomly chosen between 1 and 2006, inclusive.  What is the probability that some pair of these integers has a difference that is a multiple of 5?  (source: AMC 10A 2006 #20)

Thanks[/quote]

[hide]For it to be a multiple of 5, the difference of the two numbers must end in 5 or 0.  Therefore, we already know that it will be a multiple of 5 if two numbers end in the same digit.  Therefore, we will consider the cases in which no two numbers end in the same digit or subtract to give 5.  Also, we will only consider the last digit of each integer.  We will count using complementary counting, counting what we DON'T want, or the cases in which there is not a difference of 5 or 0 in any of the 6 numbers.  Therefore, we begin the list.  We start with $ 1$.  Now that $ 1$ is in the list, we cannot have $ 6$.  We continue with $ 2$.  Now that $ 2$ is in the list, we cannot have $ 7$.  We continue with $ 3$.  Now that $ 3$ is in the list, we cannot have $ 8$.  We continue with $ 4$.  Now that $ 4$ is in the list, we cannot have $ 9$.  We continue with $ 5$.  Now that $ 5$ is in the list, we cannot have $ 0$.  As of now, we cannot repeat any numbers or use any number that subtracts to $ 5$.
Therefore, for the last and final number, we cannot use  $ 1, 6, 2, 7, 3, 8, 4, 9, 5, or 0.$  That is all ten digits, so there MUST be a pair of integers that has a difference that is a multiple of $ 5$.

Therefore, the probability is $ 1.$
[/hide]
[hide][quote="pinkmuskrat"]Numbers that have a difference of a multiple of 5 are both x mod 5. All numbers are either 0 mod 5, 1 mod 5, 2 mod 5, 3 mod 5, or 4 mod 5. This is a total of 5 possibilities, and we have 6 numbers. Therefore, two of the numbers will be congruent mod 5.

So, there will always be two numbers of difference a multiple of 5, and the answer is $ \boxed{1}$.

For AMC specific questions, post in "American Mathematics Competitions".[/quote][/hide]

^ Great solution.


geometry
algebra
polynomial
induction
calculus
integration
complex analysis

[quote="mlok"]This problem is well-known, but I could not find it in the forum. If $ p$ is a nonconstant monic polynomial, then the set $ \{z\in\mathbb C\colon |p(z)|\le 1\}$ has area at most $ \pi$.[/quote]
Can you give a hint? Does it use any deep result?

There is an elementary proof. Try induction on the degree of $ p$.

Another hint: $ \iint_{\{|p(z)|\le 1\}}|p'(z)|^2 \equal{} \pi n$, because the integral represents the area of image of the set $ \{|p(z)|\le 1\}$ under $ p$ (counting the multiplicity with which the image is covered).


geometry
probability
USAMTS
trigonometry
vector
analytic geometry
invariant

Which problem did you guys think was the hardest?  In order of easiest to hardest, I think it went:  2, 1, 5, 4, 3.  I didn't have a clue about #3, but I got #1, #2, and #5 right away.  But then again, combinatorics is my weakest area of mathematics.

I'd say from easiest to hardest it would be 2,1,3,5,4. I had to write a program to start getting any idea on #4. And #5 also took a while to figure out. The other ones, I got pretty much right away.

Number 3. It was the only one I didn't get.  ;)

I thought #5 was pretty hard, but then, I suck at geometry.  3 was actually really simple, once you see the method (which is a little unintuitive at first).

The only one that really gave me troubles was #5...boy did I spend a lot of time on that one :D

[quote="4everwise"][quote="zanttrang"]3 was actually really simple, once you see the method (which is a little unintuitive at first).[/quote]:(  I need to go over every transcript of the Int. Probability class again.[/quote]
Actually, what helped me was the paper they put out on Expected Value at the beginning of the contest.  The method (for example) for the washer problem is identical to the method for #3.

Sandor asked me something very close to #5 a few months ago (just asked what the point is in the plane of the triangle).  Clever problem, I thought.  Then I turned it into something much more evil :diablo:.  Then I figured it was way too hard and essentially changed it back to Sandor's version.  In my evil version, one of the angles is 120 degrees, and you're asked to construct the foot of the perpendicular with straightedge and compass.

I started a couple days ago on the problems... so i didnt get to finish much   :roll:

Number 3... then again i kind of looked at it for two days then gave up.

I figured out number 5... but i couldnt remember how i got the solution... lol

Number 1 was very easy... but i completely forgot something while doing it... screwing me over completely... put down the wrong solution

Number 2 was also really easy... but i didnt solve it until after i turned in my answers

Number 4 was actually quite simple as well... took me a little while to notice how that worked.

Order of difficulty
easy to hard
21453

Easyest to hardest i thought it was 2,1,4,3,5 but I'm horrible at geometry. 2 was also easy to check with calculator approximations.

2<1<4<3<5 probably. Participation in USAMTS is seriously lowering my opinion of my geometry abilities.

I disovered I am really, really, really bad at probability, and not patient enough in geometry.

5 is by far the hardest. I got all the others reasonably easily (although I made a stupid mistake on #1), but I still don't understand how to do #5.

Oh man! I thought this round was going to be easy for everybody and I didn't get number 3, so I didn't turn in solutions for the rest of them, even though I got them. :wallbash_red:

[quote="zanttrang"][quote="mathisfun1"]Were we permitted to express the solution to the second problem as an infinite sum? The question did not require the sum to consist of only a finite number of terms. (perhaps I am being too hopeful)[/quote]Ah, yeah, you used a McLaurin expansion. I suppose, for example, if you transform it as follows

$\frac{1}{\sqrt{2} - \sqrt[3]{2}} = \frac{1/\sqrt{2}}{1 - 2^{-1/6}} = \frac{1}{\sqrt{2}} \sum_{k=0}^{\infty} 2^{-k/6} = \sum_{k=0}^{\infty} 2^{-k/6 - 1/2}$

Is that what you did?  It's an interesting question - the problem didn't explicitly state that the answer had to be a finite sum...[/quote]
Looks like we will have a long discussion at the grading table this round. We graders will have to come to a consensus on this issue. Until then, the question of whether infinite sums can earn full credit is unanswered. You students were more inventive than we problem evaluators were.

Erin Schram
USAMTS Grader

In order from easiest to hardest:

1: Casework, but simple because there were so few solutions (also, just like a sudoku problem)  :lol: [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=40794]Click here[/url]

3: At first I assumed the probabilities were dependent on eachother, but I checked a simple case and realized that it wasn't.  (Question: Is this always true for expected value?)Actually, I was pretty skeptical of my solution for a while.

2: So simple, I'm surprised I had never seen it before.

4: I spent a lot of time looking for a better way to express my answer

5: I couldn't figure it out - I decided to try to solve it one way (which didn't work) and I convinced myself that there couldn't be any other way.

How I rank them: 1<3<2<4<5.

1: Break it into cases...nothing tricky there.
2: tricky, but I'm pretty good at algebra and figured it out without too much frustration.
3: I thought this problem was pretty easy.  It scared me when everyone was talking about how hard it was and stuff.  The AoPS Intermediate Counting/Probability really helped out ;)
4: Wording the solution for this one was the trickiest part for me.
5: Well, I was pretty much convinced of going the trig route on this one the whole time.  I got stuck for a while because I knew where to go but the expressions were getting just plain UGLY.  I thought about plowing through the algebra...but after using my calculator to approximate everything I found the answer came out to a nice 140.  So I knew there had to be some nice way around it.  Finally figured it out but it took a lot of work (specifically, the majority of one period of Latin :D )

[quote="joml88"]The AoPS Intermediate Counting/Probability really helped out ;) [/quote]

Yeah, towersfreak2006 told me that they posted a similar problem with squares in week 3... :mad:

[quote]E^(pi*i)=-1 wrote:
I'm starting to get worried. I thought 3 was trivially easy, but you all think it is so hard that I must have made a mistake.

In my job I frequently work with heavily interdependent probabilities. When I looked over Problem 3, my reflex was to calculate how each circle affected the odds of other circles forming. Then I reminded myself that that was not necessary for expected value, and I could calculate the expected value by combining simple pointwise calculations. But it was hard to believe that, so I had to stop and prove that the interdependence did not matter before I would trust my answer. So Problem 3 is one of those problems where knowing too much can be a handicap.

Don't worry, I won't expect such a proof in when grading solutions.

Erin Schram
USAMTS Grader[/quote]

Good, I don't have one  :P .

Also, I had an infinite sum for #2.  I hope it is alright, it works very well.

[quote="joml88"]
5: Well, I was pretty much convinced of going the trig route on this one the whole time.  I got stuck for a while because I knew where to go but the expressions were getting just plain UGLY.  I thought about plowing through the algebra...but after using my calculator to approximate everything I found the answer came out to a nice 140.  So I knew there had to be some nice way around it.  Finally figured it out but it took a lot of work (specifically, the majority of one period of Latin :D )[/quote]

I figured out I could use trig 30 minutes before the deadline. Then I got three equations that seemed unsolveable, so I stopped (and I had to install the fax machine). But I didn't know we could use a calculator on 5, for it would only yield "approximations". Right :?:

[quote="no_one_2000"][quote="4everwise"]In my opinion, the order from easiest to hardest was: 2,1,5,4,3

Through USAMTS, I've discovered that I'm really bad at probability, and am pretty good at geometry.(At least good enough to solve the problems :))[/quote]

Hey good, somebody agrees with me about the problem difficulties! :-D[/quote] :D

I wish I would have had that flash of insight on number three.  After getting a 25 in the first round it looks like I will get at best a 15 in this round.  I just never got enough time to the work on the problems I guess.  I also found the infinite Series for problem number 2 and used that as a solution but added and showed that if an infinite number of terms was undesirable that it could be written as the finite series that many people found.

if you read the article on expected value, and read the solution for boy standing next to girl probelm, #3 is quite simple.

I'd give this order: 2 4 1 3 5 (the 2 and 4 might be reversed)

I didn't solve #5, though that was in part since I procrastinated and didn't get to spend much time on it.
And geometry is my weakest area.

#1 - This was pretty easy once I figured out which boxes to give the possible values of and go from there. I found 8 possibilities for the bottom right 2x2 box and went from there.

#2 - This one turned out to be quite easy once I played around with it, all I needed to use were the factorizations of $x^3-1$ and $x^2-1$, use them to simplify the denominator and I was done.

#3 - I agree that this one might seem the hardest if you didn't figure out the method. I was thinking about how are the different circles dependent of each other, then realized that none of that mattered and the problem wasn't that hard....

#4 - This one was pretty straightforward. I just figured out what conditions had to apply for the nth to stay in, and how many people would be there after everyone had been tapped. See a pattern, write rules, write equations, easy.

#5 - This one, I didn't have enough time on. I managed to find all the angles of the pyramid but didn't get much further.

[quote="jb05"][quote="asquared"]Easiest to hardest i thought it was 2,1,4,3,5 but I'm horrible at geometry. 2 was also easy to check with calculator approximations.[/quote]

ditto. I was kind of annoyed by the extremes here: 2 and 1 were trivial, 3 and 5 were extremely difficult, and 4 was straightforward but not [i]too[/i] easy.[/quote]
I think that means that the writers did a pretty good job with the problems - some were easy, some were hard, some were in the middle, so that students of all skill levels can take and enjoy the contest.

I got everything but #1 -_-.

Each solution is 1 page except for #1, which was a little over, and that's completely wrong too; blah.

[quote="zanttrang"][/quote][quote="4everwise"][quote="zanttrang"][quote="mathisfun1"]Were we permitted to express the solution to the second problem as an infinite sum? The question did not require the sum to consist of only a finite number of terms. (perhaps I am being too hopeful)[/quote]
How exactly did you manage to do that?  Did you do some sort of McLaurin series expansion?[/quote]One of my friends got it into an infinate geometric series. You just make it look like $\frac{t_1}{1-r}$.[/quote][quote="zanttrang"]
Ah, yeah, you used a McLaurin expansion. I suppose, for example, if you transform it as follows

$\frac{1}{\sqrt{2} - \sqrt[3]{2}} = \frac{1/\sqrt{2}}{1 - 2^{-1/6}} = \frac{1}{\sqrt{2}} \sum_{k=0}^{\infty} 2^{-k/6} = \sum_{k=0}^{\infty} 2^{-k/6 - 1/2}$

Is that what you did?  It's an interesting question - the problem didn't explicitly state that the answer had to be a finite sum...[/quote]
That's what I did at first, but then I found a nice way to find the finite sum.


function
integration
number theory
complex analysis
complex analysis theorems

Let $f$ be a real-valued nonnegative and decreasing function defined on $[0,\infty)$ such that $L(s)=\int_{0}^{\infty}{f(t)e^{-st}}dt$ converges in the region $Re(s)>1$ and $L(s)-\frac{1}{s-1}$ is continuous for $Re(s)\geq 1$. Then $f(t)$ is equivalent to $e^{t}$ at infinity. Has anyone a relatively simple proof? The one that I read in a book of analytic number theory spans over 5 pages.

You want to prove the prime number theorem? :)

[quote="harazi"]I started to read more on analytic number theory and after some quite long proofs involving complex analysis I was told about this one. But this tauberian theorem seems extremely difficult, so I was wondering whether an easier solution was found recently.[/quote]

There is an 'easier' version of this theorem aimed specifically at proving the PNT by D.J. Newman.  The following article is a good exposition of it.

J. Korevaar, On Newman's quick way to the prime number theorem, Math. Intelligencer 4 (1982), 108-115

I know that version. Indeed, it is much easier, but the strong version has some other very nice implications in analytic number theory. By the way, why is this moved in the complex analysis forum? As I said, this strong version has a purely elementary (but long and complicated) proof.


geometry
circumcircle
power of a point
radical axis
geometry proposed

Let $ M$ be an arbitrary point on $ (O)$ and $ P$ be a point outside $ (O)$. Circle $ (\omega)$ with center $ I$ and diameter $ PM$ intersects $ (O)$ at the second point $ N$. Tangent of $ (\omega)$ at $ P$ intersects $ MN$ at $ Q$. The line passes through $ Q$ and perpendicular to $ OP$ intersects $ PM$ at $ A$. $ AN$ intersects $ (O)$ again at $ B$. $ BM$ intersects $ OP$ at $ C$. Prove that $ AC \bot OQ$.

$ PM$ cuts $ (O)$ again at $ R.$ $ MN$ is radical axis of $ (O), \omega,$ tangent $ PQ$ of $ \omega$ at $ P$ is radical axis of $ P, \omega$ $ \Longrightarrow$ $ Q$ is radical center of $ (O), P, \omega$ and $ QA \perp OP$ is radical axis of $ (O), P.$ The angle $ \angle MNP$ is right, let :D be circle with diameter $ PQ,$ passing through $ N.$ Tangent $ PA$ of :D at $ P$ is radical axis of $ P,$ :D $ \Longrightarrow$ $ A$ is radical center of $ (O), P,$ :D $ \Longrightarrow$ $ AN$ is radical axis of $ (O),$ :D and $ B$ their intersection other than $ N$ $ \Longrightarrow$ $ AP^2 \equal{} \overline{AB} \cdot \overline{AN} \equal{} \overline{AR} \cdot \overline{AM}.$ From inversion in circle :lol: with center $ A$ and radius $ AP,$ we get $ \angle PBR \equal{} \angle PBA \plus{} \angle ABR \equal{} \angle APN \plus{} \angle AMN \equal{} 90^\circ.$ Circumcircle :blush: of the right $ \triangle PBR$ is centered at the midpoint of $ PR$ and therefore tangent to $ PQ$ at $ P.$ Again, $ Q$ is radical center of $ (O), P,$ :blush: and radical axis $ BR$ of $ (O),$ :blush: goes through $ Q.$ $ A \equiv MR \cap NB,$ $ Q \equiv MN \cap BR$ are intersections of the opposite sides of cyclic $ MNBR.$ Its diagonal intersection $ C \equiv MB \cap NR$ is pole of $ AQ \perp OP$ WRT $ (O),$ therefore $ O, C, P$ are collinear. Intersection $ Q \equiv MN \cap BR$ is pole of $ AC$ WRT $ (O),$ therefore $ AC \perp OQ.$

Let $ X$ the be second intersection of $MP$ with $ (O).$ Inversion with center $Q$ and power $QP^2$ takes $ (O)$ and $\omega$ into themselves and takes circle $(T)$ with diameter $\overline{PQ}$ into line $PM.$ Hence, $ X, B,Q$ are collinear and $B \in (T).$ $ XMNB$ is cyclic and line $ AQ$ passing through the intersection of its opposite sidelines is the polar of the intersection of its diagonals WRT $(O)$ $\Longrightarrow$ $N,C,X$ are collinear $\Longrightarrow$ $ AC$ is the polar of $Q$ WRT $(O)$ $\Longrightarrow$ $AC \perp OQ.$

Suppose, $ QA\cap OP=X $. Note that $ QX.QA=QP^2=QR^2 $ where $ QR $ and $ QS $ is tangent to $ (O) $. Note that $ QXOR $ is cyclic. So $A $ lies on $ RS $. Suppose, the second intersection point of $ QB $ and $ (O) $ is $ B' $. Note that, polar of $ Q $ pass through the intersection point of $ B'M $ and $ BN $, but it also pass through $ A $ which lies on $ BN $. So $ B'M\cap BN=A $. So $ B',M,A $ are collinear. Suppose, $ BM\cap B'N=C' $. Note that polar of $ C' $ is $ AQ $. Also pole of $ AQ $ lies on $ OP $ since $ OP\perp AQ $. So $ C'\equiv C $. Pole of $ AC $ is $ Q $. So $ OQ\perp AC $.

Let QA intersect OP at point X
QX*QA = QP*QP = QN*QM , so XNMA is cyclic
angle MXO = 90 - AXM = 90 - ANM = MBO , so BOMX is cyclic
Let Perpendicular from O on CA is OH
Easy to see that XHOA is cyclic , so HC*CA = OC*CX = MC*BC , so BHMA is cyclic
angle MHA = MBA = 90 - MNO , so HOMN is cyclic
Q is Radical center of (HOMN) (O) and (XHOA) , so H is on OQ C is Orthocenter of triangle QOA . done