search
LaTeX
algebra
polynomial
linear algebra
matrix
combinatorics solved

Let $ G^{\prime}$ be a $ 4$-regular graph. Arbitrarily add one edge to $ G^{\prime}$, and denote the resulting graph by $ G$. Prove that the graph $ G$ has a $ 3$-regular subgraph.

[i]Note.[/i] A graph is called $ k$-regular if each vertex of the graph has exactly $ k$ neighbours.

I think it is based on the number of edges & its parity.
Let there be n vertex in the graph.
Then initially there are 4*n / 2 = 2*n edges,in G", and in G 2n + 1.(odd)
Also, in the new G, let A & B be the 2 vertexes that have the new edge between them. Counting the number of vertices & knowing that we don't have any triangles, for any 2 that know each other, except A & B, we have
8 neighbours. Counting very carefully I think should give us the result :)))

hello DusT  :) the problem is mor harder than you explain if you are sure that your idea works post it completely then i post the sol :D

Hi!
Sorry, I missunderstood the problem. I considered that we have to prove there is a triangle, not a 3regular graph. Sorry again :). I'll read more carefull next time :D

Hy!
I give up.
Does anybody else think about it ?
I have no starting idea.
Can you at least give a hint?
Btw, where can the Iranian Math Olympiad Problems be found?
Nowhere on the INET i think :)

well Dust, it's simple: search of the forum, after the source of problem only, and type Iran* in the search field. You will find a lot of problems from Iran right here on the forum.

I listened to your advice, Valentin.
Most of the Iranian Problems are at the UNSOLVED section :) :) :D
I was searching for somekind of training :)
Anyway, what about the solution for this problem ?

So, when will we see the solution for this problem?
Sam-n ?

I 'm trying to use Latex it's boring so if there is any eror plz excuse me

now you can see the sol ;) there is useful theorem which its name is shouvale(I am not sure that its dictation is right so if it's wrong don't laugh at me :blush:  :D )

sho... theorem: consider a system of $n$ equations $f_j(x_1,...,x_m)\equiv 0 (modp)$ s.t $j=1,2,...,n  $ and $f_j$ is a polynomial with degree $r_j$ and $p$ is prime number and also $r_1+r_2+...+r_n<m$. if this system has solution (mod $p$) then it has at least two solutions.

suppose that $ v_1,v_2,...,v_n$ are the vertices of $G$ and $ e_1 ,...,e_m$ its edges. since $G'$ is 4-regular graph so

$2m=2.$ number of edges$=\sum deg(v_j)=4n+2$

thus $m=2n+1$.

now define an $m\times n$-matrix $A$ whose entries are $a_{i,j}$
such that $a_{i,j}=1$ if the edge $e_i$ passes through $v_j$ and is $0$ if otherwise.

now we should prove there is a nonempty subset $I\subseteq \left\{e_1,...,e_m\right\}$ s.t. for each $j$ we have $\sum_{e_i\in I} a_{i,j}$ equals $0$ or $3$. on the other hand this sum is between $0$ and $5$, so we should prove that this is $0$ (mod $3$).

now let $f_j(x_1,...,x_m)=\sum a_{i,j}x_i^2$. so the degree of $f_j$ is $2$ and sum of them is $2n$ which is lesser than $m$ , now due to theorem the system $f_j(x_1,...,x_m)\equiv 0$ {mod $3$}   j=1,..,n has a trivial solution $(0,0,..,0)$ so it has another solution. let $J$ be the set of all indices $i$ such that $x_i <> 0$ and  suppose $I=\left\{ e_i\mid i \in J \right\}$. now we have for any $i$ in $J$ the relation $x_i^2\equiv 1$ (mod $3$) so $\sum_{e_i\in I} a_{i,j} \equiv \sum a_{i,j}x_i^2 \equiv 0$.

uh now we are done
isn't it interesting?

Great solution, but about this "Theorem", could you please prove it or post the correct name, so I could seach it on the internet.
Thnx

Here is a little clarification about the "Theorem", DusT. Sam-n is talking about the famous Chevalley-Warning Theorem (now you can Google it  :) .)

By the way, this problem is a special case with $p=3$ of a theorem of Alon:

Theorem (Alon, 1999). Let $p$ be a prime and $G$ be a graph (without multiple edges) of average degree $> 2p-2$ and maximal degree $\leq 2p-1$. Then, $G$ has a $p$-regular subgraph.

It has recently been proved that this assertion also holds for prime powers $p$, although it is an open problem whether this holds for all positive integers $p$.

Also, I cannot resist mentioning the following relevant (or is it?  :lol: ) conjecture of Berge and Sauer proved by Taskinov:

Theorem. (Taskinov).  Every *simple* 4-regular graph has a 3-regular subgraph.

This is not true if we remove the assumption that the graph is simple (check it!), but one additional edge entails the existence of a 3-regular subgraph even in this more general case.

--Vesselin

You may find a proof here :
http://www.kenjioba.net/images/RegSubgraphs.pdf

Pierre.

Thanks a lot.
There is also another problem with a solution like that:
It is another post of another person from Iran. I think they know a lot of theorems. I wonder if they use this theorems in the olympiad.
http://www.mathlinks.ro/viewtopic.php?t=5656
Here is the link to the topic that uses another theorem I don't know.
I would be glad if somebody would explain it to me.
Thanks.

I think the theorem you're referring to was discussed here:

[url]http://www.mathlinks.ro/viewtopic.php?t=5976[/url]

It's equivalent to the problem Darij posted in the first message, and you can find at least $2$ proofs for that ($3$ if you consider mine a proof :)).


modular arithmetic
number theory unsolved
number theory

I believe what you mean is $\frac{1}{a} + \frac{1}{a+b} + \ldots + \frac{1}{1+nb}$

Let $\prod_{i=0}^{n} (a+ib) = M$. Note that $\frac{1}{a} + \frac{1}{a+b} + \ldots + \frac{1}{1+nb} = \frac {\sum_{i=0}^n \frac{M}{a+ib}}{M}$

Note that the integers $a+b, a+2b, \ldots, a + nb$ are each coprime to $a$, thus if $a>1$, then taking mod $p$ for some prime divisor $p$ of $a$, the numerator is $\not\equiv 0 \pmod{p}$ (since for $i = 1, 2, \ldots, n$, the integer $\frac{M}{a+ib}$, being divisible by $a$, is $\equiv 0 \pmod{p}$, while $\frac{M}{a}$ is $\not\equiv 0 \pmod{p}$), while the denominator is $\equiv 0 \pmod{p}$.

Now for the case $a=1$, if $b=1$, it then reduces to proving tt $1+ \frac{1}{2} + \ldots + \frac{1}{n+1}$ is never an integer $\forall$ positive integers $n$, which is a well known result (there are many methods of proving this, a simple way would be to consider powers of $2$ that divide the numerator & denominator). So assuming $b>1$, we note that $a+b = b+1$ is coprime to $a+ib = 1+ib$ for $i = 2, 3, 4, \ldots, n$. By a similar process, we note that for some prime divisor $q$ of $b+1$, the numerator is $\not\equiv 0 \pmod{q}$, while the denominator is $\equiv 0 \pmod{q}$.

[quote]Note that the integers $a+b, a+2b, \ldots, a + nb$ are each coprime to $a$,[/quote]
How about $a+ab, a+2ab,\dots$? :?

For the case of $\frac{1}{a} + \frac{1}{a+ab} + \ldots + \frac{1}{a+nab}$, by taking out the factor of $\frac{1}{a}$, it reduces to the similar case of $1+ \frac{1}{1+b} + \frac{1}{1+2b} + \ldots + \frac{1}{1+nb}$.

[quote="grodij"]n,a,b are natural number and $(a,b)=1$ prove that:
$1/a + 1/a+b + .... +1/a+nb$ isn't natural.[/quote]

I think this it's too easy: if $p$ is the greatest prime less than $n+1$,  then exists one or two integers
$1\le k_1\le n$, $k_2=k_1+p$ uch that $k_1n+1=0 \ mod \ p$ so in the case of one it's clear that the numerator is not divisible by $p$. And in the case of two is harder but an analogous idea shows that numerator is not divisible by $p^2$ (If someone has a nice idea to solve this second case, please write it).

Best Regards.
RX the Crazy Math

[quote="RobertuX"]

I think this it's too easy: if $p$ is the greatest prime less than $n+1$,  then exists one or two integers
$1\le k_1\le n$, $k_2=k_1+p$ uch that $k_1n+1=0 \ mod \ p$ so in the case of one it's clear that the numerator is not divisible by $p$. And in the case of two is harder but an analogous idea shows that numerator is not divisible by $p^2$ (If someone has a nice idea to solve this second case, please write it).

Best Regards.
RX the Crazy Math[/quote]

Please explain again. I don't get it, our denominators are of the form $ib+a$, u used $in+1$ up there, why?

[quote="ikap"]
Please explain again. I don't get it, our denominators are of the form $ib+a$, u used $in+1$ up there, why?[/quote]
Because I simplify the expression original to $\frac 1 a\sum_{k=0}^n \frac 1 {1+kb}$  so I don't care the value of $a$.

what problem are you talking about?
u don't keep $b$ natural this way  :?

Anyway, I got the idea. Still hard to solve the second case.
In fact, the fact that $p^2$ doesn't divide the numerator reduces to $a+ib+a+(i+p)b\neq 0 (\mod p^2)$ which doesn't seem to be generally true.

[quote="Myth"][quote="dblues"]Note that the integers $a+b, a+2b, \ldots, a + nb$ are each coprime to $a$, thus if $a>1$, then taking mod $p$ for some prime divisor $p$ of $a$, the numerator is $\not\equiv 0 \pmod{p}$ (since for $i = 1, 2, \ldots, n$, the integer $\frac{M}{a+ib}$, being divisible by $a$, is $\equiv 0 \pmod{p}$, while $\frac{M}{a}$ is $\not\equiv 0 \pmod{p}$), while the denominator is $\equiv 0 \pmod{p}$.[/quote]
He-he. It is completey wrong...  ;)[/quote] I don't get it..
Why is it [u]completely[/u] wrong? We can modify the solution as such: We now let $p^k \mid \mid a$, so taking $\mod p^k$, each of the terms are divisible by $p^k$ except for $\frac Ma$, so the numerator is $\not \equiv 0 \pmod{p^k}$, while the denominator is $\equiv 0 \pmod{p^k}$.

[quote="dblues"]Wait.. I reread my proof, and it's perfectly correct to me.. u don't even need to consider $p^k$ since $\frac Ma \not \equiv 0 \pmod{p}$.

As for the case when $a=1$, the same idea is used, just that now your $p$ is some prime divisor of the terms $1+b, 1+2b, \ldots, 1+nb$.

It should be correct.[/quote]You haven't understood fedja's remark yet... ;) It is possible $\frac Ma \equiv 0 \pmod{p}$

Oh gosh.. I finally see why my solution is wrong.. I had been too hasty. To [i]fedja[/i], sorry I didn't give a second thought to your post. I originally thought you were referring to a new $b^{\prime} = ab$, which was obviously not what you meant.   :blush:
To [i]Myth[/i], do you have a solution?


ratio geometry incenter circumcircle inradius

Find the ratio of the legs of a right triangle if the half of the hypotenuse (from the vertex to the midopoint) is seen from the incenter at the right angle.

$ \triangle ABC$ has right $ \angle C,$ I is the incenter, O midpoint of AB (the circumcenter) and M the midpoint of AO. By definition, $ \angle AIO$ is right $ \Longrightarrow$ IM = AM = OM, the $ \triangle AMI$ is isosceles with $ \angle MIA \equal{} \angle MAI \equal{} \frac{\angle A}{2} \Longrightarrow$ $ \angle AMI \equal{} \pi \minus{} \angle A,$ $ MI \parallel AC.$ F is foot of a normal from M to AC, MF = r (inradius) and at the same time, $ \frac{MF}{BC} \equal{} \frac{MA}{AB} \equal{} \frac{1}{4},$ $ MF \equal{} \frac{a}{4} \equal{} r \equal{} s \minus{} c,$ where $ s \equal{} \frac{a \plus{} b \plus{} c}{2}$ is the triangle semiperimeter. $ a \plus{} 2b \equal{} 2c,$ $ a^2 \plus{} 4ab \plus{} 4b^2 \equal{} 4c^2 \equal{} 4a^2 \plus{} 4b^2,$ $ 4ab \equal{} 3a^2,$ $ \frac{BC}{CA} \equal{} \frac{a}{b} \equal{} \frac{4}{3}.$


linear algebra
matrix
algebra
polynomial
linear algebra solved

Find all matrices with complex coefficients that have the class of similitude closed.

How did you guys find them?

I figured we could do something like this:

To show that non-diagonalizable matrices don't work, we could turn the matrix we're loking at into its Jordan form, and then, by similarity through matrices of the type $diag(1,\ldots,1,\alpha,1,\ldots,1)$, we could make the $1$'s below the diagonal tend to $0$. This means that the closure of the similairty class of every non-diagonalizable matrix contains a diagonal matrix, meaning that the class is not closed.

To show that diagonalizable matrices work, take such a matrix, and observe that matrices from the closure of the similarity class satisfy the same minimal polynomial as the matrix we chose, and this minimal polynomial has distinct roots, meaning that all matrices in the closure are diagonalizable as well. Since they also have the same eigenvalues with the same multiplicities, the conclusion follows.


induction
inequalities proposed
inequalities
222

If $ x_n\geq 0,x_0\equal{}0,x_n^2\plus{}x_n\minus{}1\equal{}x_{n\minus{}1}^2,$ then $ 1\minus{}\frac{2^n}{3^n}\leq x_n \leq 1\minus{}\frac{1}{3^n}.$

[quote="Ji Chen"]If $ x_n\geq 0,x_0 \equal{} 0,x_n^2 \plus{} x_n \minus{} 1 \equal{} x_{n \minus{} 1}^2,$ then $ 1 \minus{} \frac {2^n}{3^n}\leq x_n \leq 1 \minus{} \frac {1}{3^n}.$[/quote]

The induction works well.  :wink:  :)

Here is a more sophisticated proof, but it can tell us where $ 1/3^n$ and $ 2^n/3^n$ comes from.
Denote $ y_n \equal{} 1 \minus{} x_n$, by induction method we have $ y_n$ decrease and $ y_n \in (0,1)$. We have
$ y^2_n \minus{} 3y_n \equal{} y_{n \minus{} 1}^2 \minus{} 2y_{n \minus{} 1}$ so
1) $ 3y_n \equal{} y_n^2 \minus{} y_{n \minus{} 1}^2 \plus{} 2y_{n \minus{} 1} < 2y_{n \minus{} 1} \Rightarrow y_n < y_02^n/3^n,$
2) $ 3y_n \equal{} y_n^2 \minus{} y_{n \minus{} 1}^2 \plus{} 2y_{n \minus{} 1} > y_{n \minus{} 1} \Rightarrow y_n > y_0/3^n.$


AMC
AIME
inequalities
triangle inequality
complex numbers

given thath $a_1+a_2=17$
find the minimum value of
$\displaystyle\sqrt{1^2+a_1}+\sqrt{3^2+a_2}$

the real question was
given that ${a_1,a_2,\dots,a_n\in\{R}$
and $S_n$ is the minimum value of
$\displaystyle\sum_{k=1}^{n}\sqrt{(2k-1)^2+a_k}$
while
$a_1+a_2+a_3+\dots+a_n=17$
find $S_{10}$

this is a fun problem...i believe it is from aime?

anyway, there are a few solutions...here is a complex number solution

say we have

$|a_1+i|+|a_2+3i|+...+|a_n+(2n-1)i|\ge |\sum a_i+n^2i|$

(note that this is equivalent to the sum)

by the complex number triangle inequality, with equality when the complex numbers are scalar multiples to each other, then the min is:

$\sqrt{17^2+n^4}$

i think that there is more to the problem though...

The question was to find the unique $n$ such that $S_n$ was integer, I think.  I've solved it before.

Edit:  This is AIME 1991, Problem 15.  A solution is here:

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=431997#p431997


[quote="Lovasz"]Let $x_i, i=\overline{1,n}$ and $\gamma=(1+\frac{1}{n})^n$, then:
$\sum_{i=1}^n\sqrt[k]{x_1 x_2 ... x_k} < \gamma.\sum_{i=1}^{n}a_k$
... :)[/quote]
Maybe $x_i>0$ and $\gamma=(1+\frac{1}{n})^n, n\in\mathbb N$ then:
$\sum_{i=1}^n\sqrt[k]{x_1 x_2 ... x_k} < \gamma\cdot\sum_{i=1}^{n}x_k$ ?

G.Polya in 1925 found beautiful proof for this inequality.

[quote="arqady"][quote="Cezar Lupu"]Arqady, can you post Polya's proof? :)[/quote]
Polya's hint:
Let $c_{1}\cdot c_{2}\cdot...\cdot c_{k}=(k+1)^k.$ ;)[/quote]
Excuse me, I don't understand what $c_i$ is, arqady.

That's probably $x_i$, and wow, this is a good hint, I would never have thought about that  :blush: !

Maybe  the book had the same idea... but It's not quite natural...

i was just wandering:can we find the smallest constant $\gamma_0$ so that
the first inequality holds with this $\gamma_0$ instead of $\gamma$ for all natural n
the proof that arqady presented above doesnt help much (at least at first sight) eventhough it is really brilliant
 :)


logarithms
real analysis
real analysis unsolved

i hope i have not asked this one before... :maybe:

show :D

$ \dfrac{1^2}{1 \plus{} 1^3} \minus{} \dfrac{2^2}{1 \plus{} 2^3} \plus{} \dfrac{3^2}{1 \plus{} 3^3} \minus{} \dfrac{4^2}{1 \plus{} 4^3} \plus{} \dfrac{5^2}{1 \plus{} 5^3} \minus{} \dfrac{6^2}{1 \plus{} 6^3}\; \plus{} \; \minus{} \;\ldots\; \equal{} \;\boxed{\frac {1}{3}\left(1 \minus{} \ln\,2 \plus{} \pi\cdot\text{sech}\left(\frac {\sqrt 3\,\pi}{2}\right)\right)}$

You asked this one [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=156669]here[/url].   :gleam:


hello all:

during the installation of MikTeX, the MikTex wizard asks me to select a path to the local package repository! Could anyone tell me what that means and what i need to do. Thanks in advance and appreciate the help.

cheers,
natasha

Hi,
The directory you specify as the local repository during installation will hold all the packages that MikTeX downloads and loads at every startup. If, in the future, you need any packages that MikTeX did not download (ie you did not specify), you will have to download them to this directory and then update MikTeX's file name database.
SSN.


My computer is currently not working properly. So I don't have my drawing and PDF answers with me. So, for #2, I hope contestant themselves can demonstrate it.

Or, I'll add the links.  :D

Problem is in [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=40244]here[/url]

I'll write up the inequality part very soon.

For #1, I reduced it to

\[2(a^3+b^3+c^3) \leq a^2(b+c)+b^2(a+c)+c^2(a+b)\]

 :blush: I'm inexperienced with Olympiad inequalities.

Could I ask which ones I got right? Because if I got number 2 right then I'll post it.

I think both of you (you and BornForMath) got number one right..

I will be greatly appreciate if you two post #2 as well because I haven't got time to grade them yet.

Can you post for me please, silverfalcon? I lost my solution for number 2.  :blush: and i am too lazy to type it up again.

I'm going to discribe my general method and hopefully that will be good enough...

Okay. Start with a circle.
Got it?
Yay. Now choose any two points on the circumferance of that circle such that the internal angle is less then 180 but larger then 90. Do that for the other point, with the requirement that the three angles add up to 360.

Yay. Now, the equality holds, because the line segments in question are tangent to the circle, and the angles are acute because the internal angles on the circle are less then 180 but greater then 90.

All lengths are represented because we can change the radius of the circle.
All angles are represented because we can pick our three points to make all combinations.

Done!
Yay!
QED

Can someone please post the solution to Problem 1? :)

Okay, here's number 1.
[hide]
1. We break the inequality into three parts. \vskip .4in

Part 1: $2(pr + ps) \geq 2(pr + ps)$ \vskip .2in

This part is relativly simple. $2(pr + ps) = 2(pr + ps)$, for all $p,s$. Therefore $2(pr + ps) \geq 2(pr + ps)$ for all $p,s$. \blacksquare \vskip .3in

Part 2: $4a^3 + 4b^3 + 4c^3 \geq 2a^2b + 2a^2c + 2ab^2 + 2b^2c + 2ac^2 + 2bc^2$ \vskip .2in

Consider the expression $(a - b)^2(a + b)$ Because $a,b,c$ are all greater then or equal to zero, $a + b$ must be greater then or equal to zero. Also, $(a - b)^2$ is greater then zero by the trivial inequality, which states that a square of real number is greater then or equal to zero. Thus, $(a-b)^2(a+b) \geq 0$. Because $a,b,c \geq 0$, $(a-b)^2(a+b) \geq 0$, $(a-c)^2(a+c) \geq 0$, $(b-c)^2(b+c) \geq 0$. Because all three of these expressions are greater then or equal to zero, the sum of these expressions must be greater then or equal to zero. So we have $(a-b)^2(a+b)+ (a-c)^2(a+c) + (b-c)^2(b+c)\geq 0$
Expanding, we have $2a^3 - a^2b - a^2c + 2b^2 - b^2a - b^2c + 2c^3 - c^2a - c^2b \geq 0$
Or equivalently, $2a^3 + 2b^3 + 2c^3 \geq a^2b + a^2c + b^2a + b^2c + c^2a + c^2b$
Multiplying each side by 2, we have $4a^3 + 4b^3 + 4c^3 \geq 2a^2b + 2a^2c + 2ab^2 + 2b^2c + 2ac^2 + 2bc^2$, as desired. \blacksquare \vskip .3in

Part 3: $2(1 + i)^j \geq 2ij + 2$ \vskip .2in

I'm going to use some calculus here because it's the easiest way to prove it. Okay.
Let $f(x) = x^j$. Then $f'(x) = jx^{j-1}$ and $f''(x) = j(j-1)x^{j-2}$. $f(1) = 1$, $f'(1) = j$, and $f''(x)>0$ if $x > 0$ and $j \geq 1$, meaning the graph is concave for $x \geq 0$. Therefore the graph of $y = f(x)$ is always above the tangent line as long as $x \geq 0$ Making the substitution $i = x - 1$, we know that $(1 + i)^j \geq 1 + ij$ for $i \geq -1$ and $j \geq 0$. Because $i,j \geq 0$ in our problem, the inequality holds. Multiplying by two gives $2(1 + i)^j \geq 2ij + 2$, as desired. \blacksquare \vskip .2in

If you add the previous three inequalities, you get:
   $\displaystyle 2(1+i)^j + 4a^3+4b^3+4c^3+2(pr+qs) \geq 2+2a^2b+2a^2c+2ab^2+2b^2c+2ac^2+2bc^2 + 2(ps+qr) + 2ij$, which we wanted to prove in the first place. QED \vskip .3in
[/hide]
The only problem with this solution is that I had to use calculus for the third part.


Please use a \ before the trig function when typing them in LaTeX.  For example, \sec x gives $\sec x$.

let $z=e^{\frac{2\pi i}{14}}$, and make the appropriate substitutions and mass expand...

alternately, we could develop a linear recurrence that describes the sequence $s_{k}=\sec^{k}\frac{\pi}{7}+\sec^{k}\frac{2\pi}{7}+\sec^{k}\frac{3\pi}{7}$...this leads to a nice generalization, but it is still a lot of work.


vector
abstract algebra
linear algebra
linear algebra unsolved

Suppose that U and V are finite dimensional vector spaces and
that S belong to  L(V,W) , T belongs L(U,V) Prove that

Dim null ST  <=  dim null S +Dim null T

THANK U IN ADVANCE

[quote="julien_santini"]Pick a basis (x1,...,xp) of Ker(T) and complete it into a basis (x1,...,xp,...,xn) of U. Then x is in Ker (ST) <=> x is in Ker (T) or T*(x) in Ker(S). Since the restriction T* of T to vect(x_(p+1),...,xn) is an isomorphism onto Im(T), Im(T) Intersection Ker(S) will be of dimension at most Ker(S). Now E={x; T*(x) in Ker(S)} is of dimension at most Ker(S), and since E and Ker(T) are disjoint, the result follows.[/quote]

Since the restriction T* of T to vect(x_(p+1),...,xn) is an isomorphism onto Im(T),
Can u explain why it that

If $E$ and $F$ are two vector spaces with finite dimension, and $f: E \rightarrow F$ is linear, then:
$rank(f)+dim(Ker(f))=dim(E)$. In particular if you restrict $f$ to a supplementary $S$ of its kernel, then $dim(S)=dim(E)-dim(Ker(f))=rank(f)$, i.e $f$ isomorphism.


find all positive integers $a,b$such that:$5a^{b}-b=2004$

[hide="(Ugly) Solution"]
$5a^{b}=2004+b$
Examining mod 5, we see that $b \equiv 1 \mod 5$.
Let's assume that $b \neq 1$.
Hence $b \geq 6$.
Hence $a < 3$.
Also, if $a=2$, we can see that $b\leq 11$, and by trying the $b=1,6$ we find that there are no solutions with $a=2$.
So $a=1$ if $b \neq 1$. Hence $b=-1999$, which isn't possible. So, $b = 1$.
Plugging this in, we find that $a=401$.

So, the only solution is $a=401, b=1$.

[/hide]


ratio
number theory unsolved
number theory

Let $ S(n)$ denote the sum of all digits of positive integer $ n$.

Prove that there exist infinitely many $ n$ such that $ S(n)>2007S(3n)$

The problem is too easy:
It is sufficient to take
$ 3n\equal{}100\dots011$(we take $ 0$-$ k$ times),then $ S(3n)\equal{}3$,and $ S(n)\equal{}3(k\plus{}1)\plus{}7$.Now by taken any $ k>2004$ we obtain result.


Suppose we are given a quadratic equation with integer coefficients. Can we have a discriminant of 23?
 :D  :D  :D


algebra
polynomial
function
search
geometry
analytic geometry

A sequence consists of the numbers $1$, $3$, $140$, $142$, $144$, $131$...

What is the $17^{th}$ term in the sequence?

No takers yet?

Just in case anyone's wondering, this sequence definitely does work. I've checked it over multiple times to make sure I didn't make any mistakes. ;)

Hmm... I'm getting no results from the Online Encyclopedia of Integer Sequences.

This looks like a tricky one - the terms go up and down. Better get a piece of paper out...

[hide="Hint 1"]It's not found by some super-complex equation. It's rather straightforward once you get the concept.[/hide]

[hide="Hint 2"]It requires lateral thinking to find the answer, but it's purely mathematical. It's just something that you're not very likely to think of. ;)[/hide]

Well there are a lot of solutions, I really don't like these kinds of problems at all.

[quote="JesusFreak197"]There may be a lot of solutions, but there's only one correct solution...[/quote]

Exactly--how are we supposed to know which one it is?

Whatever, somebody else can probably figure it out.

Just tell me if I'm on the right track...
Sums of digits?  Or products of digits?

[quote="JesusFreak197"]There may be a lot of solutions, but there's only one correct solution, as I made this problem up...[/quote]

Disagree, these type of problem consist of infinite number of patterns, as any polynomial with degree > 4 satisfy

P(1)=1st number,
P(2)=2nd number,
P(3)=3rd number,
P(4)=4th number
P(5)=5th number

will work. (and there are infinite number of such polynomials)

So yeah don't post this kind of problem in future.

[quote="beta"][quote="JesusFreak197"]As I said in my first hint, and I will make clear now for any who did not want to read it, the answer is not found by some kind of super-complex function. The method is actually quite simple once you figure out what it is.

And I can still say that there is only one correct solution, even though many other solutions will give answers, since there is one solution that I have in mind.[/quote]

OH YEAH MY ANSWER
$P(x)=-\frac{37}{8}(x-1)(x-2)(x-3)(x-4)(x-5)+\frac{135}{8}(x-1)(x-2)(x-3)(x-4) -45(x-1)(x-2)(x-3) + \frac{135}{2}(x-1)(x-2)+2x-1$

IS RIGHT(PROVE ME WRONG) AND YEAH I AM ALWAYS RIGHT

but seriously you can't claim that the particular function you are thinking of is correct when there are infinite number of them .

Okay here's my problem: find $x+y$.

 [hide="answer"]2 because the value of x and y I have in mind is 1 and 1. ANY OTHER ANSWER IS WRONG WRONG WRONG [/hide][/quote]

I understand what you're saying.  But the solution he has in mind does not use a polynomial.  The idea is not to use math skills really, but to use lateral thinking.  For example, take the series

$1, 11, 21, 1211, 111221, ...$

Of course, we could find a polynomial to describe this sequence.  However, there is a way which is not associated with a polynomial, a simple one with little math (which I'm sure most of you know).  The idea is to get something like that.  So, in truth, JesusFreak's problem is NOT a math problem, having no one defined answer.  But then, does any problem in life have a defined answer?  There is always some fuzziness.

Yeah exactly, that's why this type of pattern problems should not be posted, at least not in this forum, as you can find infinite number of functions/patterns describing this sequence.  And it's a matter of opinion which sequence is the "best" one (you can be really cheap and say
 f(x) =0 for x>6, which is a perfectly okay function to describe this sequence).

I'd actually have to agree.  These types of problems are always very annoying because, mathematically speaking, while it's true you want the simplest pattern, there are literally an infinity of patterns to search through, so it's just a matter of whether you manage to get the one the problem-giver asks for.

Or another argument:  There isn't any way to attack these types of problems generally other than guess-and-check, so they don't contribute anything significant mathematically.

[quote="K81o7"][quote="Hokkage"][quote="K81o7"]For example, take the series
$1, 11, 21, 1211, 111221, ...$[/quote]Next term is 312211. Read the sequences out loud. one, then describe it. one one. Then describe that, two ones. Describe: one two one one. one one one two two ones. Fun problem.[/quote]

Exactly.  Even if I had some other way of describing the sequence than you did, your answer wouldn't be wrong.  The idea is of course to find a non-polynomial solution.[/quote]
Hmm what's wrong with a polynomial solution that works lol :D
Well the ability to recognize patterns is important in math, as you can make conjectures based on your pattern. But then I don't like the idea of making contrived pattern problems.

I'm sorry if I posted this in the wrong forum. I thought the answer would be more interesting for this one than the Puzzles/Brainteasers Forum once someone found it.

Also, another hint: it's even more mathematical than the sequence that K81o7 gave. ;)

[quote="beta"]
Hmm what's wrong with a polynomial solution that works lol :D
Well the ability to recognize patterns is important in math, as you can make conjectures based on your pattern. But then I don't like the idea of making contrived pattern problems.[/quote]

There IS nothing wrong with a polynomial solution.  A polynomial solution usually doesn't take much thinking or creativity.  I'm sure JesusFreak's solution isn't the only non-polynomial one.

[quote="K81o7"]

There IS nothing wrong with a polynomial solution.  A polynomial solution usually doesn't take much thinking or creativity.  I'm sure JesusFreak's solution isn't the only non-polynomial one.[/quote]

Finding a polynomial(without a calculator) is not that easy, at least when you have like 4+ terms, although I figured out an algorithm(see my polynomial for this problem) that will work for any sequence

[url=http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html]Lagrange interpolation[/url] is another way to fit a polynomial function to a given set of points.  It looks a lot like what beta wrote (similar reasoning I would believe).

Anyway, problems of this type should almost always go in the Puzzles & Brainteasers forum.  I don't know how his sequence is constructed though so I can't really say if it OK to be in this forum (I'll trust him though).  Although we know that this type of question should be avoided at all costs on competitions (*ahem*iTest*ahem) and standardized tests, it should be OK to pose it as a challenge on a math forum.

Oh, and JesusFreak, it would be better to say something like "that answer works but it's not the intended answer" or "look for a simpler pattern" instead of saying that there is only one correct answer because you said so.  It's like giving someone a geometry problem and they prove it using a really messy coordinate approach when there is a nice synthetic approach.  You wouldn't tell them they're wrong just that there is a more elegant approach they should try to find.

JF197, can you just tell us what it is, because apparently nobody feels like figuring it out. :D

One non-polynomial possibility: Maybe it has something to do with the digits themselves, like if we concatenate them, we get $13140142144131$, and this seems like being periodical, with the period $13140142144$. So, if we decide that all the following terms are at most three-digit, we'll get $1, 3, 140, 142, 144, 131, 401, 421, 441, 314, 14, 214, 413, 140, 142, 144, 131$, and the 17th is $131$.

Heh, I didn't even notice that similarity. Nice try, but not the answer I have in mind.

Try something with bases. That should help someone get it. ;)

[hide="Possibility"]I think it's $243$.[/hide]

Yep, that's correct. ;) Want to say how you got that?

[hide="Explanation"]Well, I've played with bases before this, but never thought of a negative one :)

In base $(-5)$ (but with digits $0, 1, 2, 3, 4$ - just imagine! :) ) we have $1=1_{10}, 3=3_{10}, 140=5_{10}, 142=7_{10}, 142=9_{10}, 131=11_{10}$. Hence, 17th member should be $33_{10}$ and that would be $243$ in the base $(-5)$ (Calculation: If $\overline{abc}_{(-5)}=33_{10}$, then $25a-5b+c=33$. Hence $5|c-3\Rightarrow c=3$. Now $5a-b=6\Rightarrow 5|b+1\Rightarrow b=4$. Now $a=2$.)[/hide]


[color=blue][size=150]PERU TST IMO - 2006[/size]
Sabado, 20 de mayo.[/color]

[b]Pregunta 04[/b]
En un triangulo acutangulo $ABC$ se trazan: su circunferencia
circunscrita $w$ con centro $O$, la circunferencia circunscrita
$w_1$ del triangulo $AOC$ y el diametro $OQ$ de $w_1$. Se eligen
los puntos $M$ y $N$ sobre las rectas $AQ$ y $AC$,
respectivamente, de tal manera que el cuadrilatero $AMBN$ sea un
paralelogramo. Probar que el punto de interseccion de las rectas
$MN$ y $BQ$ pertenece a la circunferencia $w_1.$

$\text{\LaTeX}{}$ed by Carlos Bravo 2006 - MathLinks AoPS

Alguna idea ..??

Carlos Bravo ;)
LIMA - PERU

yo lo acabo de hacer pero son las 12:15 am en mexico y tengo el suficiente sueño para resistirme y escribirlo mañana

pero me gustaria ver otras respuestas, tu como lo resolviste carlos bravo


[color=blue]No logro hacer el cálculo siguiente:
$\mathop{\lim }_{n \to \infty }\frac{{\left({1+\sqrt 5 }\right)^{n+1}-\left({1-\sqrt 5 }\right)^{n+1}}}{{\left({1+\sqrt 5 }\right)^{n}-\left({1-\sqrt 5 }\right)^{n}}}$
Según mi parecer, debería dar el siguiente resultado:
$\frac{{\left({1+\sqrt 5 }\right)}}{2}$
¿Podría alguien ayudarme?
Gracias por adelantado.[/color]

[quote="R.G.A.M."][color=blue]bueno creo que seria lo mismo que:$\mathop{\lim }_{n \to \infty }\frac{F_{n+1}}{F_{n}}$
.[/color][/quote]

Sea $L=\mathop{\lim}_{n \to \infty}\frac{F_{n+1}}{F_{n}}$ entonces, también tenemos que $L=\mathop{\lim}_{n \to \infty}\frac{F_{n+2}}{F_{n+1}}$, luego (multiplicando) tenemos que $L^{2}=\mathop{\lim}_{n \to \infty}\frac{F_{n+2}}{F_{n}}$, como $F_{n+2}=F_{n+1}+F_{n}$ : \[L^{2}=\mathop{\lim}_{n \to \infty}\frac{F_{n+2}}{F_{n}}=\mathop{\lim}_{n \to \infty}( 1+\frac{F_{n+1}}{F_{n}})=1+L\] Ahora, como $L\geq 1$, ya se puede obtener el valor de $L$.

$Tipe$

[color=blue]Una idea similar había tenido.

Hallé la ecuación característica de la sucesión de Fibonacci para dar con la fracción escrita en el primer post.

Agradezco mucho por la solución. No sabía cómo trabajar con límites cuando el valor del exponente tiende a infinito. ¿Existe algún método general para ello?

Muchas gracias, nuevamente.[/color]


Let $ \{a_n\}$ be a sequence given by the formulas:
$ a_1 \equal{} 1$;
$ a_{n \plus{} 1} \equal{} a_n \plus{} \frac {1}{a_n}$; $ n \equal{} 1,2,...$
Prove that $ 14 < a_{100} < 18$.

square the relation and sum it over $ n \equal{} 2, ..., 100$, to get $ a_{100}^2 \equal{} 1 \plus{} 2\cdot 99 \plus{} \frac {1}{a_1^2} \plus{} \cdots \frac {1}{a_{99}^2} \equal{} 199 \plus{} \frac {1}{a_1^2} \plus{} \cdots \frac {1}{a_{99}^2}$. since  $ 0 < \frac {1}{a_1^2} \plus{} \cdots \frac {1}{a_{99}^2} < 99$ (because $ a_i\geq 1$ for all $ i$, the result follows.


Let X be a complete Hausdoff space and f:X -> R is continuous. Prove that the function P: x -> (x, f(x)) is continuous.

If $ f: A\to B$ is continuous, the map $ A\to A\times B, x\mapsto (x,f(x))$ is always continuous. One need not to assume hausdorff or completeness
(by the way: what should that mean? There is no notion of completeness for topological spaces. Did you forget to mention that $ X$ is metric or uniform?)

So why is that? It's an easy consequence of the definition of product. Just check it yourself. There is no trick or hidden catch, everythings straight foreward. You can do it by yourself.

I'm sorry. X is metric space. I'm still quite confused on how to prove it to be continuous. Can you help me a little bit more? Thanks

Take the definition of "continuous" and of the product. That's all you need and as I said: There is no hidden catch, everthing's straight foreward. Just try it...

Although it's going to be a bit more of a kludge if you are chasing distances around using that $ X$ is a metric space. I assure you, it's not necessary.

I think you do not need the completeness condition in here. And I do not see the need to use $ T_{2}$. The proof is like, suppose $ L \equal{} U\times V$ is an open set in $ A\times B$, we need to prove $ P^{ \minus{} 1}L$ is open. However if $ y\in V \minus{} f(U)$, then $ P^{\minus{}1}(U,y)$ is empty(which is open), and the same is $ (x,y)$ with $ x\in U \minus{} f^{ \minus{} 1}(V)$. So only the points as $ (W,f(W)$ is there, $ W$ is $ U\cap f^{ \minus{} 1}(V)$. Since $ W$ is open, $ L \equal{} W$ is also open. I think we only need to deal with basis of product topology, then the desired open set can come out of inverse mapping and union of open sets quite easily.

The whole point of the product topology is that a map from $ X$ to $ A \times B$ is continuous iff it is continuous in each coordinate. :)


function
limit
algebra
polynomial
trigonometry
calculus
calculus computations

If the function f is continuous for all real numbers and if f(x) = [x^2 - 7x + 12] / [x-4] when x does not = 4, then f(4) = ?

a) 8/7
b) -1
c) 0
d) undefined
e) 1

The key is that the function is continuous.  For a function to be continuous, it must meet three criterion, it is defined at the point, the limit exists to that point, and the limit and actual value agree with each other.  Our function is
$ f(x)\equal{}\frac{x^{2}\minus{}7x\plus{}12}{x\minus{}4}$
This can be broken down into
$ f(x)\equal{}\frac{(x\minus{}4)(x\minus{}3)}{(x\minus{}4)}\equal{}x\minus{}3$
So now, we need only take the limit as $ x$ approaches 4.
$ \lim_{x\rightarrow 4}x\minus{}3\equal{}1$
So in order for the function to be continuous,
$ \boxed{f(4)\equal{}1}$

let $ f(x)\equal{}x^2\minus{}7x\plus{}12$ & $ g(x)\equal{}x\minus{}4$, note that $ \frac{f(4)}{g(4)}$ is indeterminate, then:
$ \displaystyle\lim_{x\to4}\frac{f(x)}{g(x)}\equal{}\lim_{x\to4}\frac{f\prime(x)}{g\prime(x)}\equal{}2(4)\minus{}7\equal{}1$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=176952]This topic[/url] has the same kind of language - a continuous function given by a certain formula except at one point - but I pushed a little harder by asking for not just the value but also the third derivative.

As for igiul's solution - why use that technique? There's nothing wrong with using straightforward polynomial algebra when it's appropriate.

igiul's solution is just an application of L'Hopital's rule and I like such solutions (I just used the one with less calculus).  If I recall Kent, didn't you give a L'Hopital's Rule problem on your final that most people answered wrong?

I actually love the rule myself.  Used it to beat a nasty limit on my AB semester final just a few days ago.

From my L'Hôpital is not everything campaign:

Find $ \lim_{x\to0}\frac{1\minus{}\cos(x^3)}{\sin^3 (x^2)}.$

Bear in mind that there are a significant number of regular readers here who knew the answer in 10 seconds or less, without writing anything down - and they're not doing L'Hôpital in their heads. There are other ways of thinking.

[quote="Kent Merryfield"]From my L'Hôpital is not everything campaign:

Find $ \lim_{x\to0}\frac {1 \minus{} \cos(x^3)}{\sin^3 (x^2)}.$

Bear in mind that there are a significant number of regular readers here who knew the answer in 10 seconds or less, without writing anything down - and they're not doing L'Hôpital in their heads. There are other ways of thinking.[/quote]

Ah!! Yes! We used to get those in our final exams(mostly involving a 1/sin x term that always used to stick around if we used l'hospitals rule). We could almost always solve the problem by using power series more elegantly :D

[quote="Kent Merryfield"]From my L'Hôpital is not everything campaign:

Find $ \lim_{x\to0}\frac {1 \minus{} \cos(x^3)}{\sin^3 (x^2)}.$

Bear in mind that there are a significant number of regular readers here who knew the answer in 10 seconds or less, without writing anything down - and they're not doing L'Hôpital in their heads. There are other ways of thinking.[/quote]

lol kent, I'm in high school!


Suppose  S⊂R^n  is compact, f : S -> R^n is continuous, and f(x) > 0 for every x∈S . Show that there is a number
c > 0 such that f(x) >= 1/c for every x∈S. I tried to use the definition of compactness but i'm not sure i solved the problem.

The big theorem on compactness: The continuous image of a compact set is compact.

Now, the set $\{f(x): x\in S\}$ is compact as a set of real numbers. A compact subset of $\mathbb{R}$ has a minimum (and it has a maximum, and it's closed). This minimum is $\frac1c$.

well we have $Imf=[\alpha, \beta]$ with $\alpha >0$ thus we can choose $c$ such as ${\frac{1}{c}=\alpha}$ and that's it   :thumbup:


algebra
polynomial
inequalities
algebra unsolved

I believe this follows from Maclaurin's inequalities.

http://en.wikipedia.org/wiki/MacLaurin's_inequality

But MacLaurin's inequality only works for positive reals!

Derive the polynomial $3$ times, and know this has $2$ distinct real roots, using the mean value theorem.

yes Olorin i have the same idea but i do not find the desirid condition :|

[quote="arkhammedos"]prove that the equation $x^{5}+ax^{4}+bx^{3}+cx^{2}+dx+e=0$ have $5$ reel roots then
$2a^{5}<5b$.[/quote]
It is tupo. Consider $(x+t)(x+2t)(x+3t)(x+4t)(x+5t)=x^{5}+15tx^{4}+85t^{2}x^{3}+...$
But $2a^{5}-5b=2*15^{5}t^{5}-425t^{2}>0$ for $t>0$.
Condition must be unique deg, were $deg(a)=1, deg(b)=2,deg(c)=3,deg(d)=4,deg(e)=5$, for example $a^{5}-bc+e$.

[quote="olorin"]:lol: The correct condition is $2a^{2}>5b$. Didn't see that.[/quote]
No.
Let $x\to x+t$, then
$a\to a+5t,b\tob+4at+10t^{2},c\to c+3bt+6at^{2}+10t^{3},d\to d+2ct+3bt^{2}+4at^{3}+5t^{4},e\toe+dt+ct^{2}+bt^{3}+at^{4}+t^{5}$.
Condition must be invariant.

$2a^{2}>5b$ needed, because $f'''(x)=6(10x^{2}+4ax+b)$ must had real roots. But it is not sufficiently condition.


inequalities
geometry
perimeter
induction
algorithm
combinatorics unsolved
combinatorics

In a small town, there are $n \times n$ houses indexed by $(i, j)$ for $1 \leq i, j \leq n$ with $(1, 1)$ being the house at the top left corner, where $i$ and $j$ are the row and column indices, respectively. At time 0, a fire breaks out at the house indexed by $(1, c)$, where $c \leq \frac{n}{2}$. During each subsequent time interval $[t, t+1]$, the fire fighters defend a house which is not yet on fire while the fire spreads to all undefended [i]neighbors[/i] of each house which was on fire at time t. Once a house is defended, it remains so all the time. The process ends when the fire can no longer spread. At most how many houses can be saved by the fire fighters?
A house indexed by $(i, j)$ is a [i]neighbor[/i] of a house indexed by $(k, l)$ if $|i - k| + |j - l|=1$.

I personally think that it takes 20 minutes to read and understand the question completely. :(

[quote="siuhochung"]to be frank, i still dun really understand this question till now............. :(
does it mean that, only ONE random house broke out of fire at first?[/quote]

Yes, I believe that $c$ is a fixed number. Only house is on fire initially. And we seek for an answer in terms of $n$ and $c$.

Answer: $n^2 - n$

[hide]
There are a maximum of 4 neighbouring houses for any given house:
one just above and one just below , one to the right and one to the left.  (Similar to all the positions in which a king can move on a chess board at any given time)

Assume that at time t=0 the fire started on house (1,1).

In time [0,1]
defend the house (1,2) while the fire spreads to house (2,1)

In time [1,2]
defend the house (2,2) while the fire spreads to house (3,1)

In time [2,3]
defend the house (3,2) while the fire spreads to house (4,1)

 .
 .
 .
continue as above till time [n-1,n] during which you defend the house (n,2).

Thus you have defended all the houses in the 2nd column, and the fire cannot spread to 3rd ,4th , etc columns.

So you have defended $n^2 - n$ houses.[/hide]

Answer: $(n-c)*n$

The trick is to first defend the house (1,c+1) then (2,c+1) , then (3,c+1) and so on ... till (n,c+1).

Thus you would have defended all the houses in the coloumn $c+1$

hence total number of houses defended would be $(n-c)*n$

Well, symmetricmean, of course you could defend some more houses (namely $c-2$ ) once you've saved $(1, c+1), ..., (n, c+1)$, so it would be $n^2-cn+c-2$, but that isn't optimal. I didn't get this problem at the APMO but other contestants told me that saving $(2, c)$ first, one would get the fire spreading in 2 directions and could save houses on each side alternately giving a V-like pattern (this is easier to see in a diagram), which is more efficient. However, no one I know gave a rigorous proof that this was optimal, either.

I agree with Severius; this v-shaped pattern yields the formula $n(n-c)+c^2-c$, which is larger than $n(n-c)$.  However, I do not have a rigorous proof that this is optimal either.

It isn't hard at all to show that the fighters can save at least $n(n-c)+c(c-1)$ houses...  But then, why can't they save mor houses? Here are some ideas i thought, although i don't know if they work because it is very dificult to formally prove them. In the test i did a solution, but asumming this two lemmas were true  :lol:
 (1) First name the houses with numbers, acording to their minimal distance (how many houses they have to walk) to the house $(1,c)$. Then it would help a lot if we could prove that "the more convenient" thing to do is to save houses with different numbers.. i.e. not to save a house with number 5 in the fourth turn, because saving a house with number 4 would "help" also to protect that house with number 5.
 (2) In an optimal pattern, it is "not convenient" to save two houses in the same column. This is intuitively right, because how could it be convenient to save two houses from the same column, if we want to make an "horizontal barrier"?? (well, we can make a vertical barrier with $c=1$, but in the other cases is almost evident that the best thing to do is a conected barrier that covers from row 1 to $n$).

It can be easily proved that we must have at least one saved house per column. So here we can also think about the number of turns the fire can spread.

 If anyone has solved the problem i would like him/her to post some hints to formalize things here...

I have not solved the problem, but it seems like the following logic is workable:

1) Show that after the kth rescue (defending a house at time k), there are at least k dangerous houses (a dangerous house is a house on fire that can still spread to at least one of its neighbours)

2) Using 1), show that after the kth rescue, at least k+1 more houses will be lit up on fire.

3) Using 2), we can effectively calculate the rest of the problem.

Now of course, 1) wouldn't be true for big k (namely k>c) but for the time being, we can suppose that c is sufficiently large for us to recognize and formally prove the above patterns.

Does this help anyone?

I triedo some inequalities with the perimeter of the endangered zone and the longest walk of house on fire....It could work but i reallly screwed everything in this exam... :(

Can someone post a valid solution please?

This isn't something I came up with myself, it's the official solution.

Label the houses according to their "distance" from (1,c) as suggested by RaMlaF:  say that house (i, j) is at level t if $\mid i - 1\mid + \mid j - c\mid = t $.  Let d(t) be the number of houses at level t defended by time t, p(t) the number of houses at level t + 1 or greater defended by time t.  Clearly $p(t + 1) + d(t + 1) \leq p(t) + 1. $ (*)

Let s(t) be the number of houses at level t which are not burning at time t.  We prove by induction that $s(t) \leq t - p(t)$ for $1\leq t \leq n-1$.  The base case t = 1 is clearly true, so suppose it is true when t = k.  At time k + 1, consider the set M(k+1) of the s(k+1) - d(k+1) houses at level k+1 that do not burn but are not themselves defended.  These houses survive because all their neighbours at level k do not burn.  There are at least s(k+1) - d(k+1) houses at level k that are neighbours of at least one house in M(k+1), so there must be at least s(k+1) - d(k+1) houses at level k that do not burn; that is, $s(k) \geq s(k+1) - d(k+1).$  But by the inductive hypothesis $s(k) \leq k - p(k)$, so $s(k+1) - d(k+1) \leq k - p(k)$.  Hence, using (*), $s(k+1) \leq k - p(k) + d(k+1) \leq k + 1 - p(k+1)$ also.

$p(t) \geq 0$ for all t, so from that it follow that $s(t) \leq t$ for all $1\leq t \leq n-1$. Summing, we find that at most $\frac 12 n(n-1)$ houses at levels n-1 or below can be defended.  It is easy to see that the v-shaped algorithm described by Severius and others saves exactly this many houses at levels n-1 and below, and every house at level n and above, so this must be the optimal algorithm, and at most $n(n-c) + c(c-1)$ houses can be saved.

the Solution : n^2+c^2-nc-c

I have a hard copy of the APMO solutions

but  I  can't  post  to  here ,I can't  use the system

Can we extend the problem with arbitary (i, j). Anyone has some idea for it ?


geometry
Asymptote
FTW
similar triangles

In the diagram, RECT and LONG are rectangles. How many square units are in the area of LONG?

[asy]pair L,O,N,G,R,E,C,T; unitsize(.5cm);
T = (0,7); C = (13,7); E = (13,0);
L = (0,4); O = (1,7); N = (13,3); G= (12,0);
draw(R--E--C--T--R); draw(L--O--N--G--L);
label("R",R,W);label("E",E,dir(0));label("C",C,NE);label("T",T,NW);
label("L",L,W);label("O",O-(3.5,0),N);label("N",N-(3,0),E);label("G",G,S);
label("3",(T+L)/2,W); label("1",(T+O)/2-(3.5,0),N);[/asy]

[quote="james4l"]Triangle OCN ~ Triangle LTO
So OC/CN=3

OC=3x
CN=x

TC=3x+1, TR=3+x
OL=sqrt(10)
ON=sqrt(10)*x

So area of LONG=10x
area of RECT=3x^2+10x+3

I do not think this can be solved.

[geogebra]ceeb7d8f9a711d6da8aaf24d771deb7d21074510[/geogebra]
Slide C. We cannot determine the area given what we currently know.

ACCORDING to the asymptote file, x=4.
Therefore area=40.[/quote]
I did this problem on FTW and it said the answer was 70.
I dont know how to do it. can someone show me?

In the original problem, CN is given as 7.
Side OC  is then 21.  Use similar triangles to calculate.
Segment ON is 7sqrt 10
Segment LO is sqrt 10
The product is 70


convex polygon
geometry
pentagon
angles
IMO Shortlist

In the convex pentagon $ ABCDE,$ the sides $ BC, CD, DE$ are equal. Moreover each diagonal of the pentagon is parallel to a side ($ AC$ is parallel to $ DE$, $ BD$ is parallel to $ AE$ etc.). Prove that $ ABCDE$ is a regular pentagon.

Let $DE$ meet $AB$ at $M$ and $DC$ meet $AB$ at$N$.
$EC$ parallel to $AB$=>$EC$ parallel to$MN$,but $ED=DC$=>$DM=DN$=> $EM=CN$.
$AE$paralel to $BD$ =>$MA/AB=ME/ED$and $BC$paralel $AD$=>$NB/AB=NC/CD$,but
$ME/ED= NC/CD$=>$MA/AB=NB/AB$=>$MA=NB$
$MA=NB$,$EM=CN$and$<EMA=<BNC$=>$AE=BC$
Respectiveli $BC=AB$=>$BA=ED$=>$MA=ME$=>$<A=<E$
Respectiveli $<A=<B=<C=<D=<E$
and $AB=BC=CD=DE=EA$so  $ABCDE$ is regular. :)


calculus
integration
calculus computations

I'm starting to learn calculus and I need help with some problems.

1 - $ \int x \sqrt{x}\,dx$

2 - $ \int (6x^2 \minus{} x\plus{}1)\,dx$

3- $ \int \frac{dx}{\sqrt[3]{4x}}$

$ \forall a\in\mathbb{R}, \int x^a dx \equal{} \left\{\begin{array}{ll}\frac{1}{a\plus{}1}x^{a\plus{}1}\plus{}C & (a \neq \minus{}1) \\ \log|x|\plus{}C & (a\equal{}\minus{}1)\end{array}\right.$

If you don't see the point of Kouichi Nakagawa's post, then fill in the correct numbers as exponents for these question marks:

$ x\sqrt{x}\equal{}x^?$

$ \frac1{\sqrt[3]{4x}}\equal{}\frac1{\sqrt[3]{4}}\cdot\frac1{\sqrt[3]{x}}\equal{}\frac1{\sqrt[3]{4}}\cdot x^?$


algebra
polynomial
number theory unsolved
number theory

[quote="Arne"]Prove that the sum of the squares of two consecutive positive integers cannot be equal to a sum of the fourth powers of two consecutive positive integers.[/quote]

Here is a boring sols.
We need to prove the equation $x^2+(x+1)^2=y^4+(y+1)^4$ has no sols. in positive integers $(x,y)$.
If $x\leq y^2$ then $x^2+(x+1)^2\leq y^4+(y^2+1)^2<y^4+(y+1)^4$, so $x>y^2$. Put $x=y^2+k$ where $k$ is positive integer. We have
$(y^2+k)^2+(y^2+k+1)^2=y^4+(y+1)^4$  so then
$k(2y^2+k)=(2y-k)(2y^2+2y+k+2)$ so $k<2y$ and $(2y-k)(k+2)-2yk-k^2$ is divisible by $2y^2$. This implies $4y-2k^2-2k$ is divisible by $2y^2$ and  then $2y=k^2+k$ or $4y-2(k^2+k)\geq 2y^2$ or $-4y+2(k^2+k)\geq 2y^2$

The second is fail! So
1) If $2y=k^2+k$ then $2y^2+k=k(2y^2+2y+k+2)$ which is fail cause the LH<RH
2) If $-4y+2(k^2+k)\geq 2y^2$ then $y\mid k^2+k$ so $k^2+k=ty$ and $2y\mid 2t-4$ so $t=1,2$ or $t-2\geq y$. If  $t=2$ then check as in 1). If $t\geq y+2$ then $k^2+k\geq y(y+2)$ so $k>y$ which gives $x\geq y^2+y+1$ then
$x^2+(x+1)^2\geq (y^2+y+1)^2+(y^2+y+2)^2>y^4+(y+1)^4$
The left is $t=1$ and then
$y=k^2+k$ and then $2y^2+k=(2k^2+k)(2y^2+2y+k+2)>2y^2+k$ , i think  :D
So we are done!

You could also write the equation as:

((y+1)^2 - x)*((y+1)^2 + x) = (x+1 - y^2)*(x+1 + y^2)

From here we see that y^2 <= x < (y+1)^2. So write x = y^2 + r, where 0 <= r < 2y + 1. Then the equation becomes

(2y + 1 - r)*(2y^2 + 2y + r + 1) = (r + 1)*(2y^2 + r + 1)

From here one can see that when r > y then the RHS > LHS and when r <= y then RHS < LHS, so the equation can never hold.

Thank you!   I had already derived this solution in Pre-Olympiad and I was wondering why the first two were so much uglier  :)

Those solutions were so ugly because they are correct. :wink:

Are you implying that RafaCD's solution is incorrect?

Nope, his solution is the best, actually.

The expansion $ y^4 \plus{} 2y^3 \plus{} 3y^2 \plus{} 2y \plus{} 1 \equal{} (y^2 \plus{} y \plus{} 1)^2$ is easy enough to verify by hand...

generalization:if $f(x),g(x)$ are two distinct even-degree polynomials with leading coefficients $1$,then there only exist finititely many integers $x,y$ such that $f(x)=g(y)$.


Let $ A \equal{} \underbrace {444...444}_{2{\rm{n}}\,\,number\,4}$, $ B \equal{} \underbrace {222...222}_{{\rm{n}}\,{\rm{ \plus{} }}\,{\rm{1}}\,\,number\,2}$

$ C \equal{} \underbrace {888...888}_{{\rm{n}}\,\,number\,8}$.

Prove that $ A \plus{} B \plus{} C \plus{} 7$ is a perfect square number.


In how many different arrangements can the digits 1, 2, 3, 4,
5, 6 be placed in the boxes below, one per box and without
repetition, so that the numbers in each row decrease from left to
right and the numbers in each column decrease from top to
bottom?
\begin{tabular}{c c c}
$ \square&\square&\square\\
\square&\square&\square$
\end{tabular}

The 6 must go in the top left corner.  Use logic to break down into cases, and we find that the answer is $ \boxed{5}$.


a) let triangle ABC such that AB perpendicular to AC.  Prove Euler's nine-point circle is tangent in A to the circumcircle of triangle ABC

b) Let H be the orthocenter of triangle ABC.  Prove that triangle ABC, AHB, BHA, CHA have the same nine-point circle

a) Let D be the midpoint of BC, which is also the circumcenter of ABC. What we need to prove is that the nine-point center of ABC lies on AD. Recall the nine-point center is the midpoint of the circumcenter and orthocenter of a triangle. Now it is obvious since we have O=D and A=H.

b) Since nine-point circle is actually the circumcircle of the medial triangle, we just have to prove the nine-point circle of ABC passes through the midpoint of AH,BH,CH. But it is just a well known property of nine-point circle (or just the definition :? )

For [b]b)[/b], there is a much simpler proof: It is well-known that the nine-point circle of a triangle is the circumcircle of its orthic triangle. Now, the triangles ABC, AHB, BHC, CHA all have the same orthic triangle. Hence, they must have the same nine-point circle.

  darij


If $ x$, $ y$ and $ z$ are reals in $ [1;2]$, prove that : $ (x \plus{} y \plus{} z)(\frac {1}{x} \plus{} \frac {1}{y} \plus{} \frac {1}{z}) \geq 6 \left( \frac {x}{y \plus{} z} \plus{} \frac {y}{x \plus{} z} \plus{} \frac {z}{x \plus{} y}\right)$.

you see hear: http://www.mathlinks.ro/viewtopic.php?p=487332#p487332
 :lol:


I solved all the other problems, but there is one I can't figure out

$ xdy\minus{}ydx\equal{}(x^2\plus{}y^2)dx$

I think I have to multiple it by an integration factor, but I can't figure out what to multiply it by.

Rewrite the differential equation,

$ x^2\left(\frac {y}{x}\right)' \equal{} x^2 \plus{} y^2$, yielding $ \left(\frac {y}{x}\right)' \equal{} 1 \plus{} \left(\frac {y}{x}\right)^2$.

hello
$ (xdy\minus{}ydx)\equal{}(x^2\plus{}y^2)dx$
$ \frac{xdy\minus{}ydx}{x^2\plus{}y^2}\minus{}dx\equal{}0$
$ d(tan^{\minus{}1}(\frac{y}{x}))\minus{}dx\equal{}0$
$ tan^{\minus{}1}(\frac{y}{x})\equal{}x\plus{}C$
thank u


Find $ n \in \mathbb{N}$ such that the conditions are all true:

$ 8n\plus{}1\equal{}k^2, k \in \mathbb{N}$, $ 24n\plus{}1\equal{}p^2, p \in \mathbb{N}$ and $ 8n\plus{}3$ is a prime number.

I don't get any 'n' except 1 and 10, I'm sure there are many!

[quote="linker"]Find $ n \in \mathbb{N}$ such that the conditions are all true:

$ 8n \plus{} 1 \equal{} k^2, k \in \mathbb{N}$, $ 24n \plus{} 1 \equal{} p^2, p \in \mathbb{N}$ and $ 8n \plus{} 3$ is a prime number.[/quote]
Lets $ l\equal{}8n\plus{}3$ then $ (2k)^2\equal{}4l\minus{}8$ and $ p^2\equal{}3l\minus{}8$ so difference of 2 squares is prime so $ 2k\minus{}p\equal{}1$ so $ 2\sqrt{8n\plus{}1}\minus{}\sqrt{24n\plus{}1}\equal{}1$ so n=1 or n=0

OH GOD! Another silly mistake, i overlooked the second condition entirely!!!!!

[quote="Fermat's Little Turtle"]why is the difference of 2 squares prime?[/quote]
because l=8n+3 prime


The radius of a particular circle inscribed in an equilateral triangle is 2 units.  What is the perimeter of the triangle?  Express your answer in simplest radical form.

Answer: $ 12\sqrt3$

My answer: $ 6\sqrt3$; Why:

[geogebra]19e4eb74c6ec07ea0b08dbe0c8aba1f22fe9482f[/geogebra]
$ 2\sqrt{3} \cdot 6 \equal{} \boxed{12\sqrt{3}}$.


\documentclass[11pt]{article}

I am using that with respect to the size of letter for all the document, but only accepts the sizes [10pt] and [12pt] in addition… is there another way to be able and increase or diminish the size of the letter?

The easiest way to increase the number of sizes you can use is to add the extsizes package (available in MiKTeX). The sizes available are 8pt, 9pt, 10pt, 11pt, 12pt, 14pt, 17pt, and 20pt. If you want for example 14pt then replace \documentclass[11pt]{article} by \documentclass[[b]14pt[/b]]{[b]ext[/b]article}. Very easy to use.

The complete, and very simple instructions can be found [url=http://tug.ctan.org/tex-archive/macros/latex/contrib/extsizes/readme.extsizes]here[/url].

[img]http://www.imagehosting.com/out.php/i649173_le.PNG[/img]

I really liked that kind of letter, how do I generate it?

Look at where you got that from. If it's a pdf or a book it may say what font it uses. In pdfs look at file->document properties->fonts. Don't forget that fonts sometimes have to be paid for.

Also have a look at the examples at [url=http://www.tug.dk/FontCatalogue/]The LaTeX Font Catalogue[/url]


function
probability
complex analysis
complex analysis unsolved

I'd like to see different  solutions for this problem:
suppose $ f_{1}(t)$ and $ f_{2}(t)$ is coresponding  characteristic function of independent random variables  $ \xi_{1},\xi_{2}$
if $ f_{1}(t)f_{2}(t) \equal{} e^{\minus{}t^{2}}$
then $ f_{1}$ and $ f_{2}$ is analytical on $ \mathbb{C}$.

The shortest one I know is the following: $ P(\xi_1\plus{}\xi_2>t\plus{}C)\ge P(\xi_1\ge C)P(\xi_2>t)$. Thus, since $ \xi_1\plus{}\xi_2$ is Gaussian, the probability that $ \xi_2>t$ decays like $ e^{\minus{}c t^2}$ as $ t\to\plus{}\infty$ (just choose $ C\in\mathbb R$ such that $ P(\xi_1\ge C)>0$). Similarly, the probability that $ \xi_2<t$ has the same kind of decay as $ t\to\minus{}\infty$. This is enough to ensure analyticity (and, moreover, to ensure that $ f_{2}$ is of order $ 2$ and finite type).


function
real analysis
real analysis unsolved

How to prove that if $f\in L^{1}(\mathbb{R}^{n})$ then $M(f)<\infty$ a.e?

Cover the set $\{x\colon M_{f}(x)>\lambda\}$ with appropriately chosen balls, and apply the basic covering lemma.


Determine all the natural number pairs of $ a$ and $ b$ such that $ \frac{a\plus{}1}{b}$ and $ \frac{b\plus{}1}{a}$ are also natural numbers.

The only solutions are $ (1,1),(1,2),(2,1),(2,3),(3,2)$.

Let $ b \plus{} 1 \equal{} ma$ and $ a \plus{} 1 \equal{} nb$ for positive integers $ m$ and $ n$. Then $ b \equal{} ma \minus{} 1$, so we have $ a \plus{} 1 \equal{} n(ma \minus{} 1) \equal{} mna \minus{} n \implies a(1 \minus{} mn) \equal{} \minus{} n \minus{} 1$. Therefore, $ a \equal{} \frac {n \plus{} 1}{mn \minus{} 1}$. Similarly, $ b \equal{} \frac {m \plus{} 1}{mn \minus{} 1}$,

Looking at $ a$, if $ m \equal{} 1$, then we have $ n \equal{} 2,3$. If $ m \equal{} 2$, we have $ n \equal{} 1$. If $ m \equal{} 3$, we also have $ n \equal{} 1$, and for $ m\geq 4$, we have no solution. The same can be said of $ b$.

So our only solutions are the ones stated above.

[quote="modularmarc101"]Determine all the natural number pairs of $ a$ and $ b$ such that $ \frac {a \plus{} 1}{b}$ and $ \frac {b \plus{} 1}{a}$ are also natural numbers.[/quote]

Clearly $ a\plus{}1 \ge b$ and $ b\plus{}1 \ge a$

So $ a\plus{}1 \ge b \ge a\minus{}1$

When $ b\equal{}a\plus{}1$ we get $ a|[(a\plus{}1)\plus{}1]$, gives $ a\equal{}1,2 \Rightarrow (a,b)\equal{}(1,2),(2,3)$

When $ b\equal{}a$ we get $ a|(a\plus{}1)$, gives $ a\equal{}1 \Rightarrow (a,b)\equal{}(1,1)$

When $ b\equal{}a\minus{}1$, we get $ (a\minus{}1)|(a\plus{}1)$, gives $ a\equal{}2,3 \Rightarrow (a,b)\equal{}(2,1),(3,2)$


Do they exist positive number solution of
$ a^4 \plus{} b^4 \plus{} c^4 \plus{} d^4 \plus{} e^4 \equal{} 3333^{3333}$.
If there are exist give some example of solution.

$ LHS\equiv 5(8)$ so $ a,b,c,d,e$ are all odd.
Because of $ LHS\equiv 9(16)$, and $ odd^4\equiv 1,9(16)$, we get that there are not solutions.

I don't understand what pelao wrote.
First, it seems there's confusion between the $ LHS$ and the $ RHS$.
Second, $ RHS\equiv 5(\text{ mod }16)$ and not $ 9$ which gives no contradiction.

Aaaaargh. $ 3333^{3333}$ is a sum of [b]six [/b]fourth powers, but I'm still not sure about 5  :maybe:

To make 6, notice that

$ 3333 \equal{} 3^4\plus{}3^4\plus{}5^4\plus{}5^4\plus{}5^4\plus{}6^4$

so

$ 3333^{3333} \equal{} 3333^{3332} \times 3333 \equal{} (3333^{833})^4(3^4\plus{}3^4\plus{}5^4\plus{}5^4\plus{}5^4\plus{}6^4) \equal{}$

$ \equal{} (3m)^4\plus{}(3m)^4\plus{}(5m)^4\plus{}(5m)^4\plus{}(5m)^4\plus{}(6m)^4$ where $ m \equal{} 3333^{833}$.

I don't think there's any simple argument that shows that 5 fourth-powers are impossible by reducing modulo some $ m$. By mod 16 you can see that $ a,b,c,d,e$ are all odd, and by mod 5 you can see that two of them are divisible by 5 and three aren't. But that doesn't get you very far.


Color all points in plane with RED or GREEN .
Let $ABC$ be a triangle .
Prove that There exists a triangle $MNP$~$ABC$ such that $M,N,P$ are the same color.

Hi,Minh! :)
I think it's a combinatoric's problem,not algebra.Look: http://www.mathlinks.ro/Forum/topic-26773.html


calculus
integration
geometry
calculus computations

that would be a nice new year problem =P

after simplifying, you get the (area of quartercircle with radius 1003  -  area of quartercircle with radius 1002)/(area of quartercircle with radius 1)
answer: 2005


geometry incenter circumcircle trapezoid inradius algebra function

Dear Mathlinkers,
let ABCD a square, M a point on segment CD, I, X, Y the incenters wrt MAB, MAD, MBC,
P, Q the meetpoints of the parallel to AD passing through X with BI, AC,
S, R the meetpoints of the parallel to AD passing through Y with AI, BD.
We know, from another problem that M, X, P, S and Y are concyclic.
Let be (1) this circle, U, V the second meetpoints of AC, BD with (1) and W the meetpoint of PU and SV.
Prove (perhaps with polar) that QW and PS are parallel.
Sincerely
Jean-Louis

$ (2)$ is circumcircle of isosceles trapezoid $ XQRY$ with center $ O.$ $ \triangle PSW, \triangle QRO$ are both isosceles right with $ PW \equal{} SW, QO \equal{} RO.$ From another problem, we also know that $ PS \parallel QR$ and $ O \in PS$ $ \Longrightarrow$ the isosceles right $ \triangle PSW \cong QRO$ are congruent and $ W \in QR.$

Dear Yetti and Mathlinkers,
I was waiting your answer and was a little bit certain that you will used that O is on PS...
My question is : can we prove first that W is on QR, then it follows that O is on PS.
Thank you and sincerely
Jean-Louis

Dear Mathlinkers,
sorry, I come back withe the same question:

can we prove first that W is on QR, then it follows that O is on PS.

Sincerely
Jean-Louis

$ K, L$ are midpoints of $ XQ, YR.$ $ a$ is the square side, $ x, y, r$ are radii of incircles $ (X), (Y), (I).$ $ XQ \equal{} a \minus{} 2x,$ $ YR \equal{} a \minus{} 2y,$ $ KL \equal{} \frac {_1}{^2}(XQ \plus{} YR) \equal{} a \minus{} (x \plus{} y).$ By the infamous inradii problem (see [url]http://www.mathlinks.ro/viewtopic.php?t=123243[/url],  [url]http://www.mathlinks.ro/viewtopic.php?t=270926[/url], etc.),

$ \left(1 \minus{} \frac {2x}{a}\right)\left(1 \minus{} \frac {2y}{a}\right) \equal{} 1 \minus{} \frac {2r}{a}\ \Longrightarrow$ $ \color{blue}\boxed{r \equal{} x \plus{} y \minus{} \frac {2xy}{a}}$

On the other hand, for a square (see [url]http://www.mathlinks.ro/viewtopic.php?t=264276[/url]),

$ \frac {1}{r} \equal{} \frac {1}{a \minus{} 2x} \plus{} \frac {1}{a \minus{} 2y} \equal{} \frac {1}{XQ} \plus{} \frac {1}{YR} \equal{} \frac {2\ KL}{XQ \cdot YR}.$

From similar triangles $ \triangle ASY \sim \triangle AXD,$ $ \triangle BPX \sim \triangle BYC$ (see [url]http://www.mathlinks.ro/viewtopic.php?t=273356[/url]),

$ \color{blue}\boxed{PQ \equal{} RS \equal{} a \minus{} \left(2x \plus{} 2y \minus{} \frac {2xy}{a}\right) \equal{} a \minus{} (x \plus{} y \plus{} r)}$

$ 2\ PQ \cdot KL \equal{} 2\ KL^2 \minus{} 2r \cdot KL \equal{} KL^2 \plus{} \frac {_1}{^4} (XQ \plus{} YR)^2 \minus{} XQ \cdot YR \equal{}$ $ KL^2 \plus{} \frac {_1}{^4} (XQ \minus{} YR)^2 \equal{} QR^2$

Since the triangles $ \triangle QRO, \triangle PSW$ are both isosceles right, it follows that

$ \color{blue}\boxed{[PQRS] \equal{} PQ \cdot KL \equal{} \frac {_1}{^2}QR^2 \Longleftrightarrow O \in PS \Longleftrightarrow W \in QR}$

As synthetic as it can be. I do not see anything simpler than this calculation. Using inradius $ r$ simplifies it a lot, but is not really necessary.

Dear Vladimir,
thank you very much for your help and your new idea with area...
Now, I begin to think that we are in a limiting situation concerning two domains : calculation which appears to be necessary and "shape" which apparently doesn't work.
I will continue to investigate this intersting parallelism...
Sincerely
Jean-Louis

Well, I think the two domains here are:

1. The first equation for inradius $ r$ holds, when $ ABCD$ is just a parallelogram, with $ a$ as the distance between $ AB, CD,$ [color=red]but $ \color{red}M$ must be on $ \color{red}CD.$[/color]

2. The second equation for inradius $ r$ holds even for $ M \not\in CD,$ (when $ M_1 \equiv MA \cap CD, M_2 \equiv MB \cap CD$ and $ x, y$ are inradii of $ \triangle M_1AD, \triangle M_2BC$), [color=red]but $ \color{red}ABCD$ must be a square.[/color]

Properties the 2 configurations cannot lead to a conclusion, which is beyond the capabilities of either of them, hence the shape does not work. But the full constraint for $ a, x, y$ with $ ABCD$ a square and $ M \in CD$ is factorable into the above two simple equations for $ r,$ hence calculation works:

$ a \equal{} MD \plus{} MC \equal{} \frac {2x(a \minus{} x)}{a \minus{} 2x} \plus{} \frac {2y(a \minus{} y)}{a \minus{} 2y} \equal{}$

$ \equal{} \frac {2a \left(x \plus{} y \minus{} \frac {2xy}{a}\right)(a \minus{} x \minus{} y)}{(a \minus{} 2x)(a \minus{} 2y)} \equal{} a \left(x \plus{} y \minus{} \frac {2xy}{a}\right) \left(\frac {1}{a \minus{} 2x} \plus{} \frac {1}{a \minus{} 2y}\right)$

[hide="geogebra test"] [geogebra]72ddc082d9c2aba9317c6a9a54cd93fd26f61dfa[/geogebra] [/hide]

[quote="armpist"]I think you make it much more complicated than it is.
  In fact, the trapezoid  XQRY  is a pseudosquare  (it's diagonals
  are congruent and orthogonal). The midpoints of the sides are
  vertices of a square, PWSZ  are square vertices as well.
  Thus there are plenty of squares inscribed into XQRY.
  One of the diagonals of these squares envelopes a parabola,
  while the other passes thru a fixed point - it's focus.
  Miquel theorem must be right there.

  Hope this removes the last stumbling block on the path to a nice
  article in French on your wonderful site, jayme !

  Do not forget to include a historical note on Jules Mathot's point,
  or Anti-center as we know it presently.

  M.T.[/quote]

The parabola with focus O, in this case for an isosceles right pedal triangle rotated about its pedal point O, it exists in any triangle for any pedal point. It proves nothing about W, unless you already know that O is on PS, and then you do not need the parabola. After[quote="jayme"]
... can we prove first that W is on QR, then it follows that O is on PS...[/quote] then from the definition of P, S, you are supposed to prove either "W is on QR" or "O is on PS", not their trivial equivalence, which is all you did. Maybe you should cut such pretense of insight.

Many thanks for an educated advice, sorry for the trivial stuff.

    Hope the following will be a bit  more complicated.

    From Yaglom we know that incircle (I) of AMB  and the incircles (X)  and (Y) have
    a common tangent.  When a variable circle tangent to side AB and this common tangent
    moves along, the lines from A and B thru it's center intersect the verticals XQ and YR
    in 4 points. Lines connecting these points envelope two ellipses with some tangent lines easily
    available.  Have to show that when this circle is in the position of AMB incircle,  this tangent to one
    ellipse is in position PR.

    Still immaterial?

    M.T.

Dear Ruby,
what is the sense of your message?
Sincerely
Jean-Louis


inequalities
geometry
circumcircle
trigonometry
complex numbers
inequalities solved

In  any  triagle  ABC  prove that
R/2r >=ma/ha>=(b/c+c/b)/2
Thanks!!

I've only worked out the first part:

R/2r>=ma/ha iff pR/2S>=ma/ha=a*ma/a*ha=a*ma/2S iff p*R>=a*ma. Let z1, z2, z3 be the complex numbers corresponding to A, B, C, respectively. Let O (the circumcenter) be the origin. We thus have |z1|=|z2|=|z3|=R. We must prove R(|z1-z2|+|z2-z3|+|z3-z1|)>=|z2-z3|*|z2+z3-2z1| (do the calculations and you'll see) iff R(|z1-z2|+|z2-z3|+|z3-z1|)>=|z2^2-z3^2-2z1*z2+2z1*z3|.

We have |z2^2-z3^2-2z1*z2+2z1*z3|=|(z2^2-z1*z2)+(z1*z3-z3^2)+(z1*z3-z1*z2)|<= |z2||z1-z2|+|z3||z3-z1|+|z1||z2-z3| = R(|z1-z2|+|z2-z3|+|z3-z1|) Q.E.D.

For the second part:

It's easy (LOTS of computations) to see that 4a^2*ma^2=(b^2-c^2)^2+16S^2. We know that 4a^2*ha^2=16S^2, so ma^2/ha^2=(b^2-c^2)^2/16S^2 + 1 = (b^2-c^2)^2/(2bc)^2*sinA^2 + 1 >= (b^2-c^2)^2/(2bc)^2 + 1 = (b^2+c^2)^2/(2bc)^2 iff ma/ha>=(b^2+c^2)/2bc = (b/c+c/b)/2, Q.E.D.

The nasty thing about inequalities like these is that one should know things like 4a^2*ma^2=(b^2-c^2)^2+16S^2 practically by heart, since it's VERY boring to deduce stuff like this. I saw this particular formula in a book and realized I could use it here, but that's not a nice way to solve a problem...

I have nice approach for the second part:

Let take triangle ABC with M is midpoint of BC. The line AM meets circumcircle again at D. We have
       AM.MD = MB.MC = a^2/4
But  MD = AD - AM <= 2R - AM and we have
       m_a(2R - m_a) >= a^2/4
=> 2Rm_a >= m_a^2 + a^2/4 = (b^2+c^2)/2   (1)
But  h_a = 2S/a = bcsinA/a = bc/2R and (1) is exactly the required ineq.

This approach can be use for other special lines in triangle to get the interesting ineq.

Namdung

[quote="grobber"]It's easy (LOTS of computations) to see that 4a^2*ma^2=(b^2-c^2)^2+16S^2.[/quote]

Well, the idenitity $4a^2m_a^2=\left(b^2-c^2\right)^2+16S^2$, where S is the area of triangle ABC and $m_a$ is the median from the vertex A, can be proven geometrically:

Let $h_a$ be the altitude of triangle ABC from the vertex A. Then, the area of triangle ABC equals $S=\frac12\cdot a\cdot h_a$. Hence, we can equivalently transform the identity in question as follows:

$4a^2m_a^2=\left(b^2-c^2\right)^2+16S^2$ is equivalent to
$4a^2m_a^2=\left(b^2-c^2\right)^2+16\cdot\left(\frac12\cdot a\cdot h_a\right)^2$ is equivalent to
$4a^2m_a^2=\left(b^2-c^2\right)^2+4a^2h_a^2$ is equivalent to
$4a^2m_a^2-4a^2h_a^2=\left(b^2-c^2\right)^2$ is equivalent to
$\left(2a\right)^2\left(m_a^2-h_a^2\right)=\left(b^2-c^2\right)^2$ is equivalent to
$m_a^2-h_a^2=\left(\frac{b^2-c^2}{2a}\right)^2$.

Now, in order to prove this equality, we consider the midpoint M of the side BC of triangle ABC, and the foot H of the altitude from the vertex A. Then, $AM=m_a$ and $AH=h_a$, and the triangle AHM is right-angled, so that the Pythagoras theorem yields $AM^2=AH^2+HM^2$. Consequently,

$HM^2=AM^2-AH^2=m_a^2-h_a^2$.

On the other hand, since M is the midpoint of the side BC of triangle ABC, we have $BM=\frac{BC}{2}=\frac{a}{2}$, and since the point H is the foot of the altitude from the vertex A, the triangle BHA is right-angled, and thus $BH=AB\cdot\cos\measuredangle ABH=c\cdot\cos B$. Thus,

$HM=\left|BM-BH\right|=\left|\frac{a}{2}-c\cdot\cos B\right|=\left|\frac{a}{2}-c\cdot\frac{c^2+a^2-b^2}{2ca}\right|=\left|\frac{a}{2}-\frac{c^2+a^2-b^2}{2a}\right|$
$=\left|\frac{a^2-\left(c^2+a^2-b^2\right)}{2a}\right|=\left|\frac{b^2-c^2}{2a}\right|$,

and thus $HM^2=\left|\frac{b^2-c^2}{2a}\right|^2=\left(\frac{b^2-c^2}{2a}\right)^2$. Comparing this with $HM^2=m_a^2-h_a^2$, we get $m_a^2-h_a^2=\left(\frac{b^2-c^2}{2a}\right)^2$, and the proof is complete.

  darij


Let $f(x)$ be a function which satisfies \[f(x+29)=f(29-x)\] for all real values of $x$. If $f(x)$ has exactly three real roots $\alpha$, $\beta$, $\gamma$, determine the value of $\alpha + \beta + \gamma$

$f(x)$ is symmetric about $x=29$.
hence one root must be $29$, and the sum of the other two is $29\cdot 2=58$.
hence $\alpha+\beta+\gamma = 29+58=87$.


Solve the equation

$ \cos^{\minus{}1} x\sqrt{3} \plus{} \cos x \equal{} \dfrac {\pi}{2}$

[quote="corps0507"]Solve the equation

$ \cos^{ \minus{} 1} x\sqrt {3} \plus{} \cos x \equal{} \dfrac {\pi}{2}$[/quote]

[color=darkblue]Can you  give us exact of your problem $ \cos^{ \minus{} 1} (x\sqrt {3}) \plus{} \cos x \equal{} \dfrac {\pi}{2}$ OR $ (\cos^{ \minus{} 1}x). \sqrt {3} \plus{} \cos x \equal{} \dfrac {\pi}{2}$[/color]

actually that is the exact question ^^

i'm still struggling to solve it, but i find it hard, and i think that the second term is really $ \cos^{\minus{}1} x$.

hello, let $ f(x)=arccos(x\sqrt{3})+\cos(x)-\frac{\pi}{2}$, then is $ f^'(x)=-\frac{\sqrt{3}}{\sqrt{1-3x^2}}-\sin(x)$ and $ f^'(x)$ is negative for all $ x$ with $ -\frac{\sqrt{3}}{3}<x<\frac{\sqrt{3}}{3}$, additionally is
$ f\left(\frac{\sqrt{3}}{3}\right)=\cos(\frac{\sqrt{3}}{3})-\frac{\pi}{2}<0$ and $ f\left(\frac{-\sqrt{3}}{3}\right)=\cos(\frac{\sqrt{3}}{3})+\frac{\pi}{2}>0$. It follows that $ f(x)$ is strictly monotonic decreasing and we have only one intersection point with the $ x$-axis it is nearly $ 0.4520877966566117605650938111977306975578144064999181181478659087703923167869282588990606060510949004$.
Sonnhard.


calculus
integration
geometry
parameterization
function
abstract algebra
algebra

I also think it seems too late for a 23-year-old man to start university life from 2005, eventhough his major is math!
Part 2 of the 2-paged paper is achived on 2007-02-02, and part 3 is achived 2008-04-24. I submitted it to JAMS online.I am not sure whether it is suitable or not. It's my wishes to make everyone believe Fermat and to be a mathman accepted by Wiles.Would you please do me a favour to help me check it and send me your review please?

The first proof is absurd.  You appear to be abusing the Chinese Remainder Theorem and conflating equality $ \bmod uvw$ with equality.  The fact that there are an infinite number of solutions to a modular system doesn't mean there are an infinite number of solutions over $ \mathbb{Q}$ (which I assume is your base field) of an algebraic curve.

As for the second proof, $ \gcd(z \minus{} y, x) \equal{} 1$ does not imply $ z \minus{} y \equal{} 1$.

[b]Check your work.[/b]  Very good mathematicians have been working on Fermat's Last Theorem for 350 years, and if you think a proof that simple hasn't been found by now, you don't understand any of the work that's been done in the 1800s alone.  And you are just one in a [b]long line[/b] of mathematicians who think they've found proofs that turn out to be flawed.  And the flaws here are very obvious.

about part 3 ,z-y is the factor of x^n.
about part 2,there are an infinite number of solutions over  a straight line .   so it's my argument.

Thank you. I have no idea how to express these details.

[quote="Taoli"]about part 3 ,z-y is the factor of x^n.[/quote]

Sorry, I pointed out the wrong error.  (I believe there are several, one of which is that your proof that $ (z \minus{} y, x) \equal{} 1$ is wrong.)  Here is another:  you assume there exists $ b$ such that $ z^b \plus{} y^b \equiv 0 \bmod x$, but all you can really deduce is that $ z^n \minus{} y^n \equiv 0 \bmod x$.  You have done nothing to prove that $ b$ exists.

[quote="Taoli"]about part 2,there are an infinite number of solutions over  a straight line .[/quote]

That's what I'm saying.  There aren't.  You've abused the Chinese Remainder Theorem.  When you write $ (ua \plus{} t)^n \plus{} (vb \plus{} t)^n \equal{} (wc \plus{} t)^n$, you are applying CRT to a particular solution $ x, y, z$.  If you change the value of $ t$, you also change the value of $ a, b, c$ (assuming $ u, v, w$ is fixed) - in other words, the infinite number of solutions by CRT $ \bmod uvw$ give [b]the same solution $ x, y, z$ over the integers.[/b]

My argument is that:

no (x,y,z) over N whose b doesnot exist is the solution of Fermat equation.

the infinite number of solutions by CRT  are given by the same solutionover the integers whose existance is supposed.

I think that is the point.

[quote="Taoli"]the infinite number of solutions by CRT  are given by the same solutionover the integers whose existance is supposed.[/quote]

Those solutions do not constitute an infinite number of solutions in the sense of Siegel's theorem.  The infinite number of solutions in $ \mathbb{Z}_{uvw}$ (which is not a field) translate to a finite number of solutions in $ \mathbb{Z}$.

Most mathematicians believe that it is highly unlikely that Fermat's original proof was correct.  One common proposal is that Fermat incorrectly supposed that the ring of integers of a [url=http://mathworld.wolfram.com/CyclotomicField.html]cyclotomic field[/url] has unique prime factorization (which would imply FLT, but it isn't true); work in this direction led to the notion of [url=http://mathworld.wolfram.com/ClassNumber.html]class number[/url].

[quote="t0rajir0u"]
Most mathematicians believe that it is highly unlikely that Fermat's original proof was correct.  One common proposal is that Fermat incorrectly supposed that the ring of integers of a [url=http://mathworld.wolfram.com/CyclotomicField.html]cyclotomic field[/url] has unique prime factorization (which would imply FLT, but it isn't true); work in this direction led to the notion of [url=http://mathworld.wolfram.com/ClassNumber.html]class number[/url].[/quote]

I have learned some historical details. You are my first kindhearted friend here! Glad to see you! Many details are passed over since I am not able to express them exactly.  I try to verify that there are an infinite number integral points both over an algebraic curve and a straight line. I refer to the geometry the sense of Siegel's theorem.

I am a green hand. There is a long way,and I need a teacher to speed my study up.

[quote="Taoli"]I try to verify that there are an infinite number integral points both over an algebraic curve and a straight line. [/quote]

Try to write the equation of the line.

The only way I open this address is to go to the netbar outside my campus, so I usually log here once a week.
I am eager to learn further math.Thank you for your help.

[quote="Taoli"]One of its forms is ua-vb-x+y=0.[/quote]

Think about what your variables are.  $ ua, vb$ are expressions that came from your use of CRT, so the only way this can be interpreted as a line is if $ x, y$ are your variables and $ ua, vb$ are fixed.  But if $ ua, vb$ are fixed then $ t$ is fixed.  This is not the equation of an algebraic curve at all; it is a trivial consequence of the way you defined $ t$.  Do you see your error now?

[quote="t0rajir0u"]When you write $ (ua \plus{} t)^n \plus{} (vb \plus{} t)^n \equal{} (wc \plus{} t)^n$, you are applying CRT to a particular solution $ x, y, z$.  If you change the value of $ t$, you also change the value of $ a, b, c$ (assuming $ u, v, w$ is fixed) - in other words, the infinite number of solutions by CRT $ \bmod uvw$ give [b]the same solution $ x, y, z$ over the integers.[/b][/quote]

We can treat u,v,x,y as constant and a,b as variable. I use x,y,z as the solution of Fermat equation traditionally.

Yes, but when you change $ a, b$ you also change $ t$.  I have yet to figure out how you got rid of $ t$ in your algebra but there is clearly something wrong in that pile of combinatorial expansions.

Through a parameter transformation from one space to another space.

Nonsense.  The point is that you cannot legitimately use CRT to generate an infinite number of distinct integer solutions to a plane algebraic curve.  What you'll end up doing (and this has to have happened in your proof - don't ask me to point out where because I'm not willing to sift through that mess of algebra) is generating an infinite number of distinct integer solutions to an algebraic variety of degree greater than $ 1$, which is no contradiction.

I am enjoying the feelings of thinking. But I am such an anxious fool that I have made one mistake after one. Ha, who are my mates? Let's learn more.

Thank you! I think I understand you now.

\section{an elementary proof}
Lemma: If $ x^{n}\plus{}y^{n}\equal{}z^{n}(n>2), x, y, z\in \mathbb{Q}(w), w^{n\plus{}1}\equal{}\minus{}1, n$
is odd, there is the solution of the following equations: $ z^b\plus{}y^b\equiv0, (modx)$.
\newline Proof: Since $ z^{n}\plus{}w(wy)^{n}\equal{}x^{n}$, hence $ z^{n(n\plus{}1)}\plus{}y^{n(n\plus{}1)}\equiv0, (modx)$.$ \Box$
\newline There is an elementary proof of the following form of Fermat's last
theorem: there is no positive integer solution over $ \mathbb{Q}(w), w^{n\plus{}1}\equal{}\minus{}1$ meeting Fermat
equation $ x^{n}\plus{}y^{n}\equal{}z^{n}(n>2), n$ is odd.
\newline Proof: Suppose $ (x,y,z)$ is one such solution of Fermat
equation and $ (x,y)\equal{}1, (y,z)\equal{}1, (z,x)\equal{}1, x$ is odd. Considering $ n$ is odd we let $ z>y, x\equiv r, 1<r, (modn)$.
Suppose $ b$ is the solution of the following equations: $ z^b\plus{}y^b\equiv0, (modx)$.
Let $ (z\minus{}y,x)\equal{}t$. Since $ b\equal{}n(n\plus{}1)\equal{}2c$, we get
$ z^{2c}\plus{}y^{2c}\equal{}(z^c\minus{}y^c)^2\plus{}2z^cy^c\equiv0, (modx)$. Then we have
$ t\mid 2z^cy^c$. Since $ (x,2z^cy^c)\equal{}1$, we get $ t\equal{}1$. Hence we get
$ z\equal{}y\plus{}1$. Then $ x^n\equal{}C^1_ny^{n\minus{}1}\plus{}\cdots\plus{}C^1_ny^{n\minus{}1}\plus{}1$. According to
Fermat little theorem, we have $ x\equiv x^n\equiv1,(modn)$. This is contradictory.$ \Box$

Don't make fun of the boy who teaches himself number theory if he has spreaded in a wrong way.

I am anxious enough to keep awake tonight.

Roots of unity?  The problem with working in the ring of algebraic integers over $ \mathbb{Q}[w]$ is that you're not guaranteed that the greatest common divisor is unique, which is related to the fact that unique prime factorization can fail.  Work in this area (which is very old already) led to the notion of [url=http://mathworld.wolfram.com/ClassNumber.html]class number[/url].

Don't feel too bad about repeating the mistakes of past mathematicians- mistaken approaches to FLT have inspired a large proportion of modern number theory.
Do realize that a problem which was famously unsolved for hundreds of years is very hard. People have tried the easy ways, and found that they didn't work.

There are books out there detailing the history of the problem, and describing many of the failed approaches. Read some of that, and see where your work fits.

I see the former mistake in the lemma. help me check the following, I need some time to master the background knowledge.

\section{an elementary proof}
There is an elementary proof of the following form of Fermat's last
theorem: there is no positive integer solution meeting Fermat
equation $ x^n\plus{}y^n\equal{}z^n(n>2), x\in \mathbb{N}, y, z\in \mathbb{Q}(r,
w), r\equal{}(n\plus{}1)^{\frac{1}{n}}, w^{n\plus{}1}\equal{}\minus{}1, n$ is odd.
\newline Proof: Suppose $ (x,y,z)$ is one such solution of Fermat
equation and $ (x, y)\equal{}1, (y, z)\equal{}1, (z, x)\equal{}1$.  Since
$ z^n\plus{}w_i(w_iy)^n\equal{}x^n$, hence $ z^{n(n\plus{}1)}\plus{}(w_iy)^{n(n\plus{}1)}\equiv0,
(modx^n)$. Then we get $ w_i^nz^{n(n\plus{}1)}\plus{}y^{n(n\plus{}1)}\equiv0,
(modx^n)$. It follows that
$ \Sigma_0^nw_i^nz^{n(n\plus{}1)}\plus{}(n\plus{}1)y^{n(n\plus{}1)}\equiv0, (modx^n)$. Since
$ w^{n\plus{}1}\plus{}1\equal{}0$, hence $ \Sigma_0^nw_i^n\equal{}0$. It follows that
$ (n\plus{}1)y^{n(n\plus{}1)}\equiv0, (modx^n)$. Since $ (x, y)\equal{}1$, hence
$ x|(n\plus{}1)^{\frac{1}{n}}$. This is contradictory.$ \Box$

[quote="t0rajir0u"][quote="Taoli"]
$ z^n \plus{} w_i(w_iy)^n \equal{} x^n$, hence $ z^{n(n \plus{} 1)} \plus{} (w_iy)^{n(n \plus{} 1)}\equiv0, (modx^n)$[/quote]
It seems to me that this is true only when $ n$ is even, not odd.  And you're still using the greatest common divisor.[/quote]

Considering $ n$ is odd, we get $ n\plus{}1$ is even.
Since $ z^n \plus{} w_i(w_iy)^n \equal{} x^n$, hence $ z^{n(n \plus{} 1)} \plus{} (w_iy)^{n(n \plus{} 1)}\equiv z^{n(n \plus{} 1)} \minus{}(w_i)^{n \plus{} 1} (w_iy)^{n(n \plus{} 1)}\equiv0, (modx^n)$.

Could coprime be defined with any common divisor equal to 1?

For deeper studies, I can recommend J. Neukirch: Algebraic Number Theory (especially the first chapter). But it requires a good knowledge in superior algebra (rings, ideals, modules, fields, Galois theory). For superior algebra itself (including unique factorisation domains, euclidean domains), maybe S. Lang: Algebra is a good choice (up to what I've heard, I don't have that book).

Thank you! I need some chance to enter a good graduate school.
I will work hard for it!

[quote="t0rajir0u"]One way to define a "greatest common divisor" is a divisor such that every other common divisor divides it.  Over a ring with prime factorization, this divisor exists and is unique up to multiplication by units.  Over a ring without prime factorization, this is no longer true.

The problem remains that you're assuming things like "if $ \gcd(a, b) \equal{} 1$ and $ a | bc$ then $ a | c$," which don't hold when the class number is greater than $ 1$.  You would probably benefit significantly from a text on algebraic number theory, although I'm afraid I don't have the experience to recommend you one.[/quote]

I haven't looked up the following lemmas:
Lemma1:If $ a^n|b^n$, then $ a|b$.
Lemma2:$ ye$ has the same factor $ y_i(\neq e)$ as $ y$, here $ e$ is unity.

Perhaps they works.

I will go for summer vocation.

I will not be back until this September.

Good luck, everyone!

[quote="Taoli"]I see the former mistake in the lemma. help me check the following, I need some time to master the background knowledge.

\section{an elementary proof}
There is an elementary proof of the following form of Fermat's last
theorem: there is no positive integer solution meeting Fermat
equation $ x^n \plus{} y^n \equal{} z^n(n > 2), x\in \mathbb{N}, y, z\in \mathbb{Q}(r, w), r \equal{} (n \plus{} 1)^{\frac {1}{n}}, w^{n \plus{} 1} \equal{} \minus{} 1, n$ is odd.
\newline Proof: Suppose $ (x,y,z)$ is one such solution of Fermat
equation and $ (x, y) \equal{} 1, (y, z) \equal{} 1, (z, x) \equal{} 1$.  Since
$ z^n \plus{} w_i(w_iy)^n \equal{} x^n$, hence $ z^{n(n \plus{} 1)} \plus{} (w_iy)^{n(n \plus{} 1)}\equiv0, (modx^n)$.

 Then we get $ w_i^nz^{n(n \plus{} 1)} \plus{} y^{n(n \plus{} 1)}\equiv0, (modx^n)$.

[/quote]This is wrong.

Fermat's last theorem: there is no solution of Fermat equation $ x^n \plus{} y^n \equal{} z^n, x,y,z\in \mathbb{Z},xyz\neq0,n$ is odd prime.
Proof: Suppose $ (x,y,z)$ is one such solution of Fermat equation and $ (x, y) \equal{} 1, (y, z) \equal{} 1, (z, x) \equal{} 1$.
Let $ z^n\equal{} w^p,y^n\equal{} v^p,x^n\equal{} u^p,p\equal{}\phi(n), n\equiv r \bmod p$.
Since $ n$ is odd prime, we can suppose $ (n,xy)\equal{}1$.
Over $ \mathbb{Q}(d^{r/p}),d\neq 0$, we get $ w^p\equal{}u^p \plus{} v^p \equiv 1\plus{}1 \bmod n$.
This is contradictory.$ \Box$


function
induction
combinatorics unsolved
combinatorics

Let $ A$ be a finite set and $ f: A\to A$ a function.
Prove that there exists $ A_0,A_1,A_2,A_3$ pairwise disjoint subsets of $ A$ so that $ A\equal{}A_0\cup A_1\cup A_2\cup A_3$ with the property that $ f(x)\equal{}x,\forall x\in A_0$ and $ f(A_i)\cap A_i\equal{}\emptyset,i\equal{}1,2,3$.
Is this true if $ A$ is infinite?

Use induction on the number $ n$ of elements of $ A$.

Consider the directed graph whose vertices are the element of $ A$, and the edge $ xy$ is drawn iff $ f(x)=y$.

Wlog, we may assume that the undirected graph with same vertices and edges is connected, otherwise just follow the reasoning on each connected component and form the desired sets from those found on each of these components (with respect that $ A_0 = \{x\in A/ f(x)=x\}.$)
- If there is some $ x\in A$ which is the endpoint of at least two edges of the directed graph, then there is at least one vertex, say $ y$, which is the endpoint of none of the edges (and the converse is true). Note that $ f(y) \neq y.$
Use the induction hypothesis on $ A-\{y\}$. Now according to the set which contains $ f(y)$, it leaves at least two of the sets for $ y$.

- If each vertex is the endpoint of exactly one edge, then the graph is a cycle, which can always be $ 3$-coloured (use two colours alternatively until you reach the last vertex and give it the third colour). this colouration leads to the desired partition.

Note that in the case of some isolated vertices ($ f(a)=a$) and triangles ($ f(a)=b,f(b)=c,f(c)=a$), the partition cannot be realised into less than four sets.

Pierre.


algebra function domain logarithms inequalities

[quote="vishalarul"][quote="ordinary boy"]Let $ n$ be a positive integer.  If the number of integers in the domain of $ y=\log ((1-x)(x-n))$ is $ 2n-6$, the what is $ n$?[/quote]

I'm assuming base 10.

[hide]The domain of that is all $ x\in \mathbb{R}$ such that

$ (1-x)(x-n) > 0.$

Solving this inequality for $ x$ yields:
$ 1<x<n \text{ or }n<x<1.$

However, since $ n$ is a positive integer, the latter case is impossible. Hence, we must have:
$ 1<x<n.$

Therefore, there are $ n-2$ integers in this interval, and we are given that there are $ 2n-6$. Hence, these two quantities must be equal:
$ n-2 = 2n-6$

Solving for $ n$, $ \boxed{n=4}$.[/hide][/quote]
yea thats right..although log can be any base..and its still 4 (that is by definition any base a>0, not equal to 1)


function
integration
algebra
domain
Functional Analysis
complex analysis

Hi! I have two problems on approximating a function $ 1/z$ on a unit circle $ \mathbb{T} : \equal{} \{z \in \mathbb{C} | |z| \equal{} 1\}$ with polynomials.

1. Let $ \ A \subsetneq \mathbb{T}$ be a compact subset. Prove that for $ \epsilon > 0$ there exist $ \ a_0, \ldots, a_n \in \mathbb{C}$ such that
\[ \sup_{z \in A} \left|\frac {1}{z} \minus{} \sum_{j \equal{} 0}^{n}a_jz^j\right| < \epsilon.
\]
2. Prove that for any $ \ a_0, \ldots, a_n \in \mathbb{C}$
\[ \sup_{z \in \mathbb{T}} \left|\frac {1}{z} \minus{} \sum_{j \equal{} 0}^{n}a_jz^j\right| \geq 1.
\]

#2:
$ 2\pi\equal{}\left|\int_{\mathbb{T}}p(z)\minus{}\frac1z\,dz\right|\le \int_{\mathbb{T}}\left|p(z)\minus{}\frac1z\right|\,|dz|\le 2\pi\max_{z\in \mathbb{T}}\left|p(z)\minus{}\frac1z\right|$
Actually, this applies to any approximation with a function analytic on the closed disk.

I can do #1 with a standard functional analysis argument (something like a functional analysis oriented proof of runge's theorem), but maybe there is a much simpler argument for the particular domain in question.

edit: Ohps, #1 is in fact a direct application of Runge's theorem. I forgot exactly what the theorem said in more precise versions :P


$\overline{AB}$ and $\overline{ED}$ are parallel tangents of the circle $O$ at points $A$ and $E$, respectively, cutting a third tangent $\overline{BCD}$ at points $B$ and $D$, respectively. If $AB = 8$ and $ED = 18$, what is the radius of the circle?


Could Someone proof the NERNST EQUATION?

consider the equation:
$aA+bB\leftrightharpoons cC+dD$
we know:
$Q=\frac{[C] ^c[D]^d}{[A]^a[B]^b}$
$\Delta G =\Delta G^{\circ} +RT\ln{Q}$
and
$\Delta G=-nF\Delta E$
$\Rightarrow -nF\Delta E=\Delta G^{\circ} +RT\ln{Q}\Rightarrow \Delta E=\Delta E^{\circ} -\frac{RT}{nF}\ln{\frac{[C] ^c[D]^d}{[A]^a[B]^b}}$
$\mathbb{QED}$ :)

note that in equilibrium $\Delta E^{\circ}=0, Q_{eq}=K$


Team A and team B play a series.  The first team to win three games wins the series.  Each team is equally likely to win each game, there are no ties, and the outcomes of the individual games are independent.  If team B wins the second game and team A wins the series, what is the probability that team B wins the first game?

Thanks for the help!

[hide="Counting"]Team B only won 1 game: well, only 1 case - ABAA
Team B wins twice, then there's 3 places to put the second game: BBAAA, ABBAA, ABABA

So, it's a $ \frac{1}{4}$ chance.[/hide]

pascal, you missed the fact that they aren't equally likely. You have to weight them appropriately.

[hide="Solution"] We have one of the following two cases, where _ denotes an unknown:

_ B _ _ A
_ B _ A

In the first case, we have to fill in the blanks with an A, another A, and a B. The probability that the first is a B is $ \frac {1}{3}$.

In this case, A must win all the games, so the only possibility is ABAA. So the probability for this case is $ 0$.

We add to get $ 0 \plus{} \frac13 \equal{} \boxed{\frac {1}{3}}$.[/hide]

EDIT: I realized my mistake. Ignore this solution.

@PowerOfPi: You're right that the cases have to be weighted, but I don't think you did it exactly right.
[hide="My Solution"]By the rule for conditional probability, $ P(A|B) \equal{} \frac {P(A\&B)}{P(B)}$ ($ P(A|B)$ is the probability of event $ A$ given event $ B$ occurs). In this case, $ A$ is the event that team B wins the first game, and $ B$ is the event that team B wins the first game and team A wins the series.

$ P(A\&B)$
The only possibility if team B wins the first and second games but team A wins the series is BBAAA. This occurs with probability $ \left(\frac {1}{2}\right)^5 \equal{} \frac {1}{32}$, since there is a 1/2 chance that a given game will match this pattern. Thus, $ P(A\&B) \equal{} \frac {1}{32}$.

$ P(B)$.
As mentioned in the previous solutions, the only possibilities are ABAA, ABABA, ABBAA, and BBAAA. The probability that ABAA will occur is $ \left(\frac {1}{2}\right)^4$, and the probability for each of the remaining possibilities is $ \left(\frac {1}{2}\right)^5$. Thus, $ P(B) \equal{} \frac {1}{16} \plus{} \frac {3}{32} \equal{} \frac {5}{32}$.

Now, we just divide:
$ P(A|B) \equal{} \frac {P(A\&B)}{P(B)} \equal{} \frac {1/32}{5/32} \equal{} \boxed{\frac {1}{5}}$.[/hide]

Another solution:
[url]http://www.artofproblemsolving.com/Wiki/index.php/2005_AMC_10A_Problems/Problem_18[/url]

EDIT: Changed answer to 1/5 instead of 5/32, as grn_trtle pointed out.

Ugh, great, we now have 4 differing solutions?
Mine's probably wrong, since I didn't take into account that they're weighted differently.

MathWise:
It's already a given that B won the 2nd game, so wouldn't $ P(A\&B) \equal{} \left(\frac{1}{2}\right)^{4}  \equal{} \frac{1}{16}$?
So then ABAA would be $ \left(\frac{1}{2}\right)^{3}$ and so the total would then be $ \frac{5}{16}$

Intriguingly, none of your answers is right :lol:

[hide="Solution"]
The only possibilities are: ABAA, BBAAA, ABBAA, ABABA
ABAA will happen 1/16 of the time, the rest 1/32 of the time.

In only one of these does B win the first game, so $ \frac {1/32}{3/32 \plus{} 1/16} \equal{} \boxed{\frac {1}{5}}$.
[/hide]

EDIT: Actually, MathWise was right but the very last computation is wrong (try multiplying by $ \frac{32}{32}$). However, conditional probability is really not necessary.

[hide="@pascal12"][quote="pascal12"]It's already a given that B won the 2nd game, so wouldn't $ P(A\&B) \equal{} \left(\frac {1}{2}\right)^{4} \equal{} \frac {1}{16}$?
So then ABAA would be $ \left(\frac {1}{2}\right)^{3}$ and so the total would then be $ \frac {5}{16}$[/quote]

We are trying to calculate $ P(A\&B)$, not $ P(A\&B|B)$. Basically, instead of trying to find $ P(A|B)$ we are trying to find $ \frac{P(A\&B)}{P(B)}$, as this is often easier to find. However, when we calculate $ P(A\&B)$ and $ P(B)$, we do not assume that B is a given. If you do assume that B is a given, then $ P(A\&B)\equal{}P(A|B)$, and $ P(B)\equal{}1$, so it's the same as just trying to calculate $ P(A|B)$.

Thus, if we assume B is given, then $ P(A\&B)\equal{}\frac{5}{16}$ and $ P(B)\equal{}1$. (In order to calculate $ P(A\&B)$ when B is given, we have to solve the problem, as this is what the problem is asking for.)[/hide]


pigeonhole principle
MIT
college
Putnam
arithmetic sequence

Let $A$ be any set of $19$ distinct integers chosen from the arithmetic progression $1, 4, 7, \cdots 100$. Prove that there must be two distinct integers in $A$ whose sum is $104$.

Oops, sorry about the typo  :blush:, should be $104$.

I got this from the website for a problem-solving course at MIT, and the worksheet where I saw it stated that the $20$ could be replaced by a $19$.

[quote="Fraxia"]Let $A$ be any set of $19$ distinct integers chosen from the arithmetic progression $1, 4, 7, \cdots 100$. Prove that there must be two distinct integers in $A$ whose sum is $10$.[/quote]

I don't think this is possible, since you can have the set of

${13,16,...,67}$  and none of them add up to 10.

[quote="boxedexe"]The problem that is of this type on Putnam 1978 is
[i]Let S = {1, 4, 7, 10, 13, 16, ... , 100}. Let T be a subset of 20 elements of S. Show that we can find two distinct elements of T with sum 104.[/i][/quote]

Well, that explains it

Let us break the subsets in the following manner.

{1}, {4,100}, {7,97},...{49,55}, {52}

There are 18 sets here, so let us assume that after 18 pulls one element from each set is pulled to enforce maximization.  Then this means that we have two draws remaining.  It can't be from {1} or {52} since they are already drawn.  So the two remaining elements have to be drawn from the 16 sets remaining, and hence there will be a set with two elements pulled by the pigeonhole principle.

Which implies that the sum is going to be 104 for any drawing of 20 integers.

QED


[quote="AndrewTom"]A square $ PQRS$ has sides of length $ x$. $ T$ is the midpoint of $ QR$ and $ U$ is the foot of the perpendicular from $ T$ to $ QS$. What is the length of $ TU$?[/quote]
[hide]Triangle QTU is a 45-45-90 with hypotenuse length being $ \frac{x}{2}$. Thus the length of $ TU$ is $ \frac{x\sqrt{2}}{4}$.[/hide]


Suppose that for any number $a$ there is a point on the graph of $y=f(x)$ closest to the point $(a,0)$ (this is guaranteed when $f$ is continuous, but that's not important). Define $g(a)$ as the distance from $(a,0)$ to that point, and prove that for all $c$ and $d$, $g(c)-g(d)\le|c-d|$.

We will call $C$ and $D$ the points of the graph of $f$ achieving the required minimal distances.
Assume the result to be false. Then $\exists c,d, g(c) > |c-d| + g(d)$. That means $C$ must lie outside the circle with center $(c,0)$ and radius $|c-d|+g(d)$. But every point $D$ must lie inside this circle (by the triangle inequality); in particular, $d((c,0),D) \leq |c-d|+g(d)$, which is absurd.

Right. It's easier to give a direct proof though.

Let $s$ be the distance from $(c,0)$ to $D$. By the triangle inequality, $s\le{g}(d)+|c-d|$. But $g(c)\le{s}$ by the definition of $g(c)$.