modular arithmetic
number theory unsolved
number theory

A prime which satisfies 2^(p-1) = 1 (mod p^2) is called a Wieferich prime. It is not known if their number is infinite.
It is also not known if there are infinitely many integers which satisfy the congruence.
A book I have says that these two open problems are actually equivalent. My question is, why is this? Is this because every integer satisfying the congruence must be prime? or for some other reason?
Thanks :)

It is clear that $ 1\implies 2$.
If $ 2^{k\minus{}1}\equiv 1(mod\ k^2)$ and $ q$ is the smallest prime divisor of $ k$, we have $ 2^{q\minus{}1}\equiv 1(mod\ q^2)$ since $ (q, k\minus{}1)\equal{}1$.

@ Abel
So what about infinitely many even numbers?? :lol:

[quote="Abel"]If  and  is the smallest prime divisor of , we have  since .[/quote]
Can someone explain me why???
I can't see it.

Abel, I just proved that what you said is true for every prime divisor, not just the smallest one:

If 2^(n-1) = 1 (mod n^2), then for every prime divisor p of n, 2^(p-1) = 1 (mod p^2).

Can this be used to prove that there is no composite n for which 2^(n-1) = 1 (mod n^2) ?

Here is a proof that if $ 2^{k \minus{} 1}\equiv 1\pmod{k^2}$ and prime $ q$ divides $ k$ then $ 2^{q \minus{} 1}\equiv 1\pmod{q^2}$:
If $ 2^{k \minus{} 1}\equiv 1\pmod{k^2}$ and $ q$ is a prime divisor of $ k$, then $ 2^{k \minus{} 1}\equiv 1\pmod{q^2}$. On the other hand, $ 2^{q(q \minus{} 1)}\equiv 1\pmod{q^2}$ by Euler's Totient Theorem. The latter two congruences imply that $ 2^{(k \minus{} 1,q(q \minus{} 1))}\equiv 2^{(k \minus{} 1,q \minus{} 1)}\equiv 1\pmod{q^2}$ (the prime factor $ q$ is dropped since it cannot divide $ k \minus{} 1$). But since $ (k \minus{} 1,q \minus{} 1)$ divides $ q \minus{} 1$, we have also  $ 2^{q \minus{} 1}\equiv 1\pmod{q^2}$ as required.

Now suppose that there is infinite number of solutions that have only a finite number of distinct prime factors. Therefore, the degrees of some primes in the solutions infinitely grow. But it is easy to see (similarly to the above proof) that if $ 2^{k \minus{} 1}\equiv 1\pmod{k^2}$ and $ q^s|k$ then $ 2^{q \minus{} 1}\equiv 1\pmod{q^{2s}}.$ However, it is clear that for each particular prime $ q$, there exists a positive integer $ t$ such that $ 2^{q \minus{} 1}\not\equiv 1\pmod{q^t}.$ Therefore, all the degrees of the primes in the solutions are bounded. This contradiction proves that an infinite number of solutions must have an infinite number of distinct prime factors.


Given triangle $ABC$. Prove that: $\sqrt{2}\sin A+\sin B+\sin C<3$

[hide]
With Cauchy it reduces to proving that \[\sin^{2}A+\sin^{2}B+\sin^{2}(C) \leq \frac{9}{4}\]
and I think that's Jensen's (a great source is [url=http://mathcircle.berkeley.edu/trig.pdf]here[/url].)[/hide]

sin^2 x is not only concave or only convex on (0,pi)

why would have such a weak inequality then?

not sure why the inequality would be so weak, but it works:

[hide]
$\sin^{2}A+\sin^{2}B+\sin^{2}C\leq \frac{9}{4}$ is equivalent to $a^{2}+b^{2}+c^{2}\leq 9R^{2}$, or $OH^{2}\geq 0$.
[/hide]


algebra
polynomial
quadratics
system of equations

Here's a problem I can't figure out that is to do with remainder theorem.

"When P(x) is divided by x-1, the remainder is 1. When divided by (x-2)(x-3), the remainder is 5. Find the remainder when P(x) is divided by (x-1)(x-2)(x-3)."

This is as far sa I get:

P(x) = (x-1)(x-2)(x-3)Q(x) + ax^2 + bx + c
P(x) = (x-2)(x-3)Q(x) + ax^2 + bx + c
P(1) = a + b + c = 1

ax^2 + bx + c = 5 (from line 2)

I'm not sure if the second line is correct in my equations though. Please help me quickly :)

the second line is only $Ax+B$, because when you divide by a second degree polynomial, the most degree you'll have is 1.

and I think you should:
[hide]
first find $P(2)$ and $P(3)$ in terms of some variable $t$, and then use the normal LaGrange way to do it.
[/hide]

[b]nebffa[/b]: This is how you should interpret this problem:

$P(1)=1$, and $P(2)=P(3)=5$

$P(x)=(x-1)(x-2)(x-3)Q(x)+R(x)$, where $R(x)$ is the remainder you are looking for. This $R(x)$ has at most degree 2, so $R(x)$ is a quadratic, ie $R(x)=ax^{2}+bx+c$

Now,
$P(1)=R(1)=a+b+c=1$

$P(2)=R(2)=4a+2b+c=5$

$P(3)=R(3)=9a+3b+c=5$

Solve this system and you will find the remainder $R(x)$

[b]pkerichang[/b]: what Lagrange? Lagrange interpolation? Because the numbers are nice, we can do the special case Newton's interpolation much faster and easier interpolating method:

[hide="See this pkerichang"] \[\begin{array}{ccccc}1&&5&&5\\ &4&&0&\\ &&-4&& \end{array}\] $R(x)=1+\frac{4}{1!}(x-1)+\frac{(-4)}{2!}(x-1)(x-2)$ :D[/hide]

[quote="pkerichang"]Well...somehow I thought the system of equations way is call LaGrange method...

Also, how do you know that $P(2) = P(3) = 5$??? is it just because you can't solve it the way he said it???[/quote]Are you kidding, right?

$P(x)=(x-2)(x-3)Q_{2}(x)+5$ so $P(2)=P(3)=5$...

Also, what do you mean I can't solve the way he said it? He doesn't even have a coherent idea as to what's going on! If you read carefully, every step there has used the Remainder Theorem. If you can't see it, I can't help it.

wahaha nvm forget what I was saying....being extra dumb today... :blush:


geometry
trigonometry
cyclic quadrilateral
geometry unsolved
U sviti matematyky

The incircle of triangle $ ABC$ touches $ BC,CA,AB$ at $ K,L,M$ respectively. The perpendiculars at $ K,L,M$ to $ LM,KM,KL$ interesect the incircle again at $ P,Q,R$ respectively.

Prove that $ AP,BQ,CR$ concur.

Well, can you show the proof, dear Nemion?

Dear Mathlinkers,
this problem, as it had been said, is a particular case of the Steinbart's theorem, the converse being the Rabinowitz's theorem.
For a general entirely synthetic prove see : http://perso.orange.fr/jl.ayme   (vol. 3, les points de Steinbart et de Rabinowitz) where some reference are given.
Sincerely
Jean-Louis

[quote="Nemion"]In fact I think this problem can be generalized:

The incircle of triangle $ \triangle{ABC}$  touches $ BC,CA,AB$  at $ K,L,M$  respectively. Consider any point $ X$ in the plane and let $ P,Q,R$ be the second intersection points of $ KX,LX,MX$ with the incircle.

Prove that $ AP,BQ,CR$ concur.[/quote]
[hide="Proof of another problem...but almost same"]Absolutely!  :)
Using sin law we get that,
\[ \frac {\sin \angle LAP}{\sin \angle APL} \equal{} \frac {PL}{AL} \ \ \ \textbf{and } \ \ \ \frac {\sin \angle PAM}{\sin \angle APM} \equal{} \frac {PM}{AM}
\]
Note that, $ AL \equal{} AM$
So, we get $ \frac {\sin \angle CAP}{\sin \angle PAB} \equal{} \frac {PL}{PM}$
So, in the same way get three equations, and multiplying them we get,
\[ \frac {\sin \angle CAP }{\sin \angle PAB} \cdot \frac {\sin \angle ABQ }{\sin \angle QBC}\cdot \frac {\sin \angle BCR }{\sin \angle RCA} \equal{} \frac {PL}{PM} \cdot \frac {MQ}{QK}\cdot \frac {KR}{RL}
\]
At last from ceva and Trig ceva it should be clear that, $ AP,BQ,CR$ concur if and only if $ KP,LQ,MR$ concur.

EDIT: oups...I didn't see the word intersection with incircle...I thought that,$ P,Q,R$ were on the sides of $ \triangle KLM$...in that case my proof is correct. :oops:[/hide]

Anyway, the proof of the fact is also same in general,
As we have, $ \frac{\sin \angle CAP}{\sin \angle PAB}\equal{}\frac{PL \cdot \sin \angle ALP}{PM \cdot \sin \angle AMP}\equal{}$
Using the cyclic quadrilateral $ LPMK$ we get,
$ \angle ALP\equal{}\angle PKL$ and $ \angle AMP\equal{}\angle MKP$
and also, $ \frac{PL}{PM}\equal{}\frac{\sin \angle PKL}{\sin \angle PKM}$

So, we get $ \frac{\sin \angle CAP}{\sin \angle PAB}\equal{}\left( \frac{\sin \angle PKL}{\sin \angle PKM} \right)^2$

Again, in the same way get three equations, and multiplying them we get,
\[ \frac{\sin \angle CAP }{\sin \angle PAM} \cdot \frac{\sin \angle ABQ }{\sin \angle QBC}\cdot \frac{\sin \angle BCR }{\sin \angle RCA}\equal{}\left( \frac{\sin \angle PKL }{\sin \angle PKM} \cdot\frac{\sin \angle KMR }{\sin \angle RML} \cdot\frac{\sin \angle MLQ }{\sin \angle QLK} \right) ^2\]
so,by trig ceva those lines concur. :)

If the three lines meet at one point then
sin∠MAX/ sin∠LAX * sin∠KBZ/ sin∠MBZ * sin∠LCY/ sin∠KCY =1  (1)

sin∠MAX/ sin∠LAX=MP*sin∠AMP / PL* sin∠ALP=MP/PL * sin∠AMP/ sin∠ALP=(MP/PL)^2
the same way
sin∠KBZ/ sin∠MBZ=(KQ/QM)^2    sin∠LCY/ sin∠KCY=(LR/RK)^2

But we have MP/PL* KQ/QM* LR/RK=1

(1)is  true
done!


algebra
polynomial
geometry
inequalities
floor function
3D geometry
pyramid

Some one can post all problem from Austrian Polish 2006 ?

In german you fint the problems at [url]http://www.oemo.at/index.php?page=intern/bsps.htm[/url] under "Österreichisch-Polnische Mathematikwettbewerbe".

I'll try to translate them to english in the next few days.

Not neccessary, I'll do it ;)

[size=150]Austrian Polish 2006, Single Competition, Day 1[/size]

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=107525]Problem 1:[/url]
Let $M(n)=\{n,n+1,n+2,n+3,n+4,n+5\}$ be a set of 6 consecutive integers. Let's take all values of the form \[\frac{a}{b}+\frac{c}{d}+\frac{e}{f}\] with the set $\{a,b,c,d,e,f\}=M(n)$.
Let \[\frac{x}{u}+\frac{y}{v}+\frac{z}{w}=\frac{xvw+yuw+zuv}{uvw}\] be the greatest of all these values.

a) Prove that for all odd $n$ holds: $\gcd (xvw+yuw+zuv, uvw)=1$ iff $\gcd (x,u)=\gcd (y,v)=\gcd (z,w)=1$.
b) For which positive integers $n$ does $\gcd (xvw+yuw+zuv, uvw)=1$ hold?

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=107523]Problem 2:[/url]
Find all polynomials $P(x)$ with real coefficients satisfying the equation \[(x+1)^{3}P(x-1)-(x-1)^{3}P(x+1)=4(x^{2}-1) P(x)\] for all real numbers $x$.

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=107527]Problem 3:[/url]
$ABCD$ is a tetrahedron.
Let $K$ be the center of the incircle of $CBD$.
Let $M$ be the center of the incircle of $ABD$.
Let $L$ be the gravycenter of $DAC$.
Let $N$ be the gravycenter of $BAC$.

Suppose $AK$, $BL$, $CM$, $DN$ have one common point.
Is $ABCD$ necessarily regular?

[size=150]
Austrian Polish 2006, Single Competition, Day 2[/size]

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=110142]Problem 4:[/url]
A positive integer $d$ is called [i]nice[/i] iff for all positive integers $x,y$ hold: $d$ divides $(x+y)^{5}-x^{5}-y^{5}$ iff $d$ divides $(x+y)^{7}-x^{7}-y^{7}$ .
a) Is 29 nice?
b) Is 2006 nice?
c) Prove that infinitely many nice numbers exist.

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=110143]Problem 5:[/url]
Prove that for all positive integers $n$ and all positive reals $a,b,c$ the following inequality holds: \[\frac{a^{n+1}}{a^{n}+a^{n-1}b+\ldots+b^{n}}+\frac{b^{n+1}}{b^{n}+b^{n-1}c+\ldots+c^{n}}+\frac{c^{n+1}}{c^{n}+c^{n-1}a+\ldots+a^{n}}\ge \frac{a+b+c}{n+1}\] [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=110144]Problem 6:[/url]
Let $D$ be an interior point of the triangle $ABC$.
$CD$ and $AB$ intersect at $D_{c}$,
$BD$ and $AC$ intersect at $D_{b}$,
$AD$ and $BC$ intersect at $D_{a}$.
Prove that there exists a triangle $KLM$ with orthocenter $H$ and the feet of altitudes $H_{k}\in LM, H_{l}\in KM, H_{m}\in KL$, so that
$(AD_{c}D) = (KH_{m}H)$
$(BD_{c}D) = (LH_{m}H)$
$(BD_{a}D) = (LH_{k}H)$
$(CD_{a}D) = (MH_{k}H)$
$(CD_{b}D) = (MH_{l}H)$
$(AD_{b}D) = (KH_{l}H)$

[size=150]Austrian Polish 2006, Team Competition[/size]

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=110145]Problem 7:[/url]
Find all nonnegative integers $m,n$ so that \[\sum_{k=1}^{2^{m}}\lfloor \frac{kn}{2^{m}}\rfloor\in \{28,29,30\}\] [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=110146]Problem 8:[/url]
Let $A\subset \{x|0\le x<1\}$ with the following properties:
1. $A$ has at least 4 members.
2. For all pairwise different $a,b,c,d\in A$, $ab+cd\in A$ holds.
Prove: $A$ has infinetly many members.

[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=110147]Problem 9:[/url]
Given is an 8x8 chessboard with 64 squares. Then we have 3x1 dominoes which cover exactly 3 squares. Such dominoes can only be moved parallel to the borders of the chessboard and also only if the passing squares are free. If no dominoes can be moved, then the position is called stable.
a. Find the smalles number of covered squares neccessary for a stable position.
b. Prove: There exist a stable position with only one square uncovered.
c. Find all Squares which are uncoverd in at least one position of b).

[url=http://www.mathlinks.ro/Forum/viewtopic.php?p=625798#625798]Problem 10:[/url]
Let $ABCDS$ be a (not neccessarily straight) pyramid with a rectangular base $ABCD$ and acute triangular faces $ABS,BCS,CDS,DAS$. We consider all cuboids which are inscribed inside the pyramid with its base being in the plane $ABCD$ and its upper vertexes are in the triangular faces (one in each).
Find the locus of the midpoints of these cuboids.


function
algebra
functional equation
algebra solved

Hey, did anyone solve the functional equation from shortlist 2002? Man, I love functional eqns! :D

Find f:R->R such that f(f(x)+y)= 2x+f(f(y)-x).

i dont know if my soln is ne different from the one posted on the kalva website (the site duznt seem to show the 2002 shortlist solutions :? ) but here goes my solution neway :D
Suppose that f is such a function. Let f(0) = c. Setting
y = −f(x) gives:
c = 2x + f(f(−f(x)) − x).
Since c − 2x takes on all real values as x runs over the reals, this shows
that f is surjective (onto). In particular, choose a such that f(a) = 0.
With x = a we get:
f(y) = 2a + f(f(y) − a),
or equivalently,
f(y) − a = f(f(y) − a) + a.
Since f is surjective, for each real x there is a y with x = f(y) − a.
Therefore:
x = f(x) + a
for all real x, or f(x) = x − a. It is easily checked that any such function
is a solution.

Thanks. That's exactly the sane as my soln.


[quote="toanhocmuonmau"]Let $a,b,c,d$ be nonnegative real numbers satisfying $a+b+c+d=4$. Prove that
\[a^{2}bc+b^{2}cd+c^{2}da+d^{2}ab \leq 4 \]
:)[/quote]
See here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=100960


inequalities
search
number theory unsolved
number theory

Let $ a,b,n \in N*$such that $ a^n|b$. Prove that : $ a^{n\plus{}1}|[(a\plus{}1)^b\minus{}1]$

[quote="conan_naruto236"]Let $ a,b,n \in N*$such that $ a^n|b$. Prove that : $ a^{n \plus{} 1}|[(a \plus{} 1)^b \minus{} 1]$[/quote]
It is pretty obvious...isn't it? :maybe:
[b]Proof:[/b]
If $ a \equal{} 1$ then problem is obvious.

So we may assume that $ a,n\geq 2$.
It seems to me that main idea here is to consider the number $ (a \plus{} 1)^b$,so let's do it:
$ (a \plus{} 1)^b \equal{} a^{b} \plus{} \binom{b}{1}\cdot a^{b \minus{} 1} \plus{} \dots \plus{} \binom{b}{b \minus{} 1}\cdot a \plus{} 1$.
Our goal is to show that
$ a^{k}\cdot \binom{b}{k}$ is divisible by $ a^{n \plus{} 1}$
If $ k > n$ then we are done,therefore,$ k\leq n$
\[ a^{n \plus{} 1 \minus{} k}\Big|\binom{b}{k}
\]
Suppose that $ a^{m}\parallel{}k!$ and $ a^{l}\parallel{}k$.As we know $ k\leq n$,therefore $ k\leq a^{n \minus{} 1}$(because by our asumption $ a\geq 2$).
Then $ b(b \minus{} 1)(b \minus{} 2)\dots(b \minus{} k \plus{} 1)(b \minus{} k)$ is divisible by at least $ a^{n \plus{} m}$.(here we use that if for some $ 1\leq i\leq k$,$ a^{j}\parallel{}i$ then $ a^{j}\parallel{}b \minus{} i$ and due to the statement $ a^{n}|b$).
Therefore $ a^{n \minus{} l}$ divides $ \binom{b}{k}$,and we need to show that $ n \minus{} l\geq n \plus{} 1 \minus{} k$,or
$ k\geq l \plus{} 1$,which is equivalent to $ a^{k \minus{} 1}\geq a^{l}$.
But as we know
\[ a^{k \minus{} 1}\geq k\geq a^{l}
\]
In last inequality we use that $ a\geq 1$
$ \blacksquare$

This is [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1170875116&t=205928]lifting the exponent[/url] with $ k \equal{} 1$.


if A + B + C= pi , and cosA=cosBcosC
find the value of tanBtanC

We have $ \tan B \tan C \equal{} \frac{\sin B \sin C}{\cos B \cos C} \equal{} \frac{\sin B \sin C}{\cos A}$.

We substitute in $ A \plus{} B \plus{} C \equal{}\pi$ and get $ \frac{\sin B \sin C}{\cos (\pi \minus{} (B \plus{} C))} \equal{} \frac{\sin B \sin C}{\minus{}\cos (B \plus{} C)} \equal{} \frac{\sin B \sin C}{\minus{}\cos B \cos C \plus{} \sin B \sin C}$.

Let $ \alpha \equal{} \tan B \tan C \equal{}  \frac{\sin B \sin C}{\minus{}\cos B \cos C \plus{} \sin B \sin C}$. So $ \frac{1}{\alpha} \equal{} \minus{}\cot B \cot C \plus{} 1 \equal{} \minus{}\frac{1}{\alpha} \plus{} 1$. So $ \alpha \equal{} 2$.

tanB tanC = sinBsinC / cosBcosC

                = sinBsinC / cosA

                = [cos(B-C) - cos(B+C)] / 2cosA

                = [cos(B-C) + cos(A)] / 2cosA

                = cos(B-C)/2cosA + 1/2

                = 1/2 - cos(B-C)/2cos(B+C)....................(1)

now, cos(B-C)/cos(B+C)

      = [(cosBcosC + sinBsinC)/(cosBcosC - sinBsinC)]

      = [(1 + tanAtanB) / (1 - tanAtanB)]

put this into (1) and set tanAtanB = x

x = 1/2 - (1+x)/2(1-x)

   = 1/2 [1 - (1+x)/(1-x)]

   = 1/2 [-2x / (1-x)]

   = x / (x-1)

x(x - 1) = x

x^2 - 2x = 0

x(x - 2) = 0

x = 0 or x = 2.

therefore, tanAtanB = 0 or tanAtanB = 2.

$ \ A + \ B + \ C = \pi$

$ \ tanB\ tanC$

=$ \frac {\ sinB\ sinC}{\ cosB\ cosC}$

= $ \frac {\ sinB \ sinC} {\ cosA}$

= $ \frac {\ cos(B-C) - \ cos(B+C)} {\ 2cosA}$

= $ \frac {\ cos(B-C) + \ cosA} {\ 2cosA}$

= $ \frac {1}{2} - \frac {\ cos(B-C)}{\ 2cos(B+C)}$

= $ \frac {1}{2} - \frac {\ cosB\ cosC + \ sinB\ sinC}{2(\ cosB\ cosC - \ sinB\ sinC)}$

= $ \frac {1}{2} - \frac {1 + \ tanB\ tanC}{2(1 - \ tanB\ tanC)}$

$ \ Therefore,
\ tanB\ tanC$ = $ 2$  or  $ 0$

Latexified :)

[hide="Shorter Answer"]
$ cosA\equal{}cosBcosC$
$ \minus{}cos(B\plus{}C)\equal{}cosBcosC$
$ sinBsinC\equal{}2cosBcosC$
Hence $ tanBtanC\equal{}2$

[/hide]


The edges of a cube are each 14 inches long. What is the ratio of the number of square inches in the total surface area of the cube to the number of cubic inches in its volume? Express your answer as a common fraction.

The surface area is $ 14^2 \times 6$, while the volume is $ 14^3$, so the ratio is $ \frac{14^2 \times 6}{14^3}$, or $ \boxed{\frac37}$.


There are two concentric spheres of radii 3 units and 6 units. What is the volume, in cubic units, of the region within the larger sphere and not within the smaller sphere? Express your answer in terms of $ \pi$.

R=6,r=3
Volume of the big sphere is $ \frac{4}{3}R^3\pi\equal{}288\pi$ and the volume of the small one is then $ 36\pi$.
The wanted volume $ 252\pi$


i have heard about normalization in inequalities and cant understand how it works.by normalising an inequality we are setting a condition which cannot be true for all  positive real nos.then what is the main point of normalisation?

Let the inequality be homogeneous. Then if we prove it holds for some (a,b,c) (or any number of variables) we can prove it holds for (ak,bk,ck) where k isn't 0. Why? Because it's homogeneous, all of the exponents of k can be left out and you are left with the inequality for a,b,c

Now you can assume abc=1 (or a+b+c=1 or any other condition) because if you prove the inequality for abc=1, you can prove it for any product abc

Example:

Prove $ a^2\plus{}b^2\plus{}c^2\ge ab\plus{}bc\plus{}ca$

The inequality is homogeneous, so let's assume $ abc\equal{}1$, now prove it for $ abc\equal{}1$ (I KNOW THIS IS A VERY BAD EXAMPLE)

Now, how to prove it for every a,b,c? For example, how to prove it for $ a\equal{}1,b\equal{}2,c\equal{}3$?
$ abc\equal{}6$, so if we divide every number by $ \sqrt[3]6$, we are left with the same inequality for numbers which product is 1, and we have proven it for such numbers, so it's true...


analytic geometry
Triangle
coordinate geometry
Divisibility
IMO Shortlist

Let $p$ be an odd prime and $n$ a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length $p^{n}$. Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by $p^{n+1}$.

[i]Proposed by Alexander Ivanov, Bulgaria[/i]

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in $\LaTeX$. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)

there seems to be one here who wants to solve it... i didn't really want to post the solution i found in oberwolfach because it's so long... but here it goes:

Consider the 8 given points as the vertices of a $K_8$ and color an edge $AB$ in color 1 if $AB^2$ is not divisible by $p$, in color 2 if $AB^2$ is divisible by $p$, but not by $p^{n+1}$ and in color 3 if $AB^2$ is divisible by $p^{n+1}$. If the statement is wrong, there is no triangle of color (3,3,3).

Let $A,B$ be two of the 8 points, let $O$ be the center of the circle and let $R=\frac{p^n}2$. We know by the cosine theorem that $AB^2=2R^2(1-\cos \gamma)$ where $\gamma=\sphericalangle AOB$. Therefore $\cos \gamma$ is a rational number which has at most $p^{2n}$ in the denominator. Now, add an additional point $C$ and let $\alpha=\sphericalangle BOC, \beta=\sphericalangle COA$. We know that $2\cos \alpha \cos \beta \cos \gamma=1-\cos ^2 \alpha - \cos ^2 \beta - \cos ^2 \gamma$. Therefore $v_p(\cos \alpha) + v_p(\cos \beta) + v_p(\cos \gamma) \geq 2\min \{ v_p(\cos \alpha), v_p(\cos \beta), v_p(\cos \gamma) \}$ (here $v_p(x)$ denotes the $p$-adic valuation; it is clear that $v_p(\cos \alpha) \leq 0$). Wlog assume that $v_p(\cos \alpha)$ is minimal. then we know that $v_p(\cos \beta) + v_p(\cos \gamma)\geq v_p(\cos \alpha)$; if $v_p(\cos \beta),v_p(\cos \gamma) > v_p(\cos \alpha)$ we even have equality. This shows that triangles of color (1,1,1), (1,1,2), (2,2,2) and (1,3,3) may not exist.
If there were no triangles of color (1,1,3), every triangle would contain an edge of color 2 and an edge of color 1 or 3 - this is impossible as there has to be in conclusion a triangle consisting only of color 2 or only of color 1 or 3(this was true even in any 6-element subset of the 8 points); therefore we have a triangle $ABC$ of color (1,1,3). Then wlog we have $v_p(\cos \alpha)=v_p(\cos \beta)=-2n$; it follows that $v_p(\cos \gamma)=0$, therefore $\cos \gamma$ is an integer. it may not be 1; therefore it is 0 or -1; but 0 is not possible since in that case we had $AB^2=\frac{p^{2n}}2$ which is not an integer. Therefore $AB$ is a diameter; summing up, all triangles of color (1,1,3) include a diameter. From now on, fix a diameter $AB$ and $C$ such that $AC$ and $BC$ have color 1.

If for all $D,E\neq A,B$ we had that $DE$ is of color 2 or 3, there would necessarily be a triangle of color (2,2,2) or color (3,3,3), contradiction. Therefore we have some $DE$ of color 1.
If, say $D=C$, then $ACE$ is of color (1,1,*), therefore of color (1,1,3), which means that AE is a diameter and it follows that $E=B$, contradiction; analogously for $E=C$. To finish, consider the cyclic quadrilateral $ACDE$. By the ptolemaus theorem, we know that $\pm AC\cdot DE \pm AE\cdot CD \pm AD\cdot CE=0$ with suitably chosen signs. This implies $(- AC^2\cdot DE^2 + AE^2\cdot CD^2 + AD^2\cdot CE^2)^2=4AD^2\cdot AE^2\cdot CD^2\cdot CE^2$. Now, look at both sides $\mod p$ to get a contradiction(remember that we just showed that $v_p(CD^2)>0, v_p(CE^2)>0$; but we know that $v_p(AC^2\cdot DE^2)=0$ and $v_p(AD^2\cdot CD^2)>0$ as the triangle $ACD$ may not be of color (1,1,1)).

QED

Sorry for possible nonsense..
Define $exp(a)$ be the biggest power of $p$ dividing the integer $a$ ($exp(0)=+\infty$).
For rational $\frac ab$ define ${exp(\frac ab})=exp(a)-exp(b)$.
It's obvious that ${exp(a+b)\geq min\{exp(a),exp(b)}$ and if $exp(a)\neq exp(b)$ then ${exp(a+b)=min\{exp(a),exp(b)}$.
We say that $u|v$ if $u\neq 0$ and ${exp(\frac vu})\geq 0$.
Now let's pass to the solution of the problem.
Let the $8$ points be $A_1, \cdots, A_8$ have coordinates $u_i, v_i$ and let the center have rational coordinates $s,t$. Define $x_i=u_i-s, y_i=v_i-t$. Then $x_i^2+y_i^2=\frac {p^{2n}}{4}$.
IF $exp(x_i)\geq n$ then we have $exp(y_i^2)=exp(\frac {p^{2n}}4-x_i^2)\geq 2n$ so $exp(y_i)\geq 2n$.
However we cannot have three points with this property, because they would form then a desired triangle. Thus there are at most two points with this property and removing them there are at least $6$ points left with $exp(x_i)<n$.
Let $r_i=exp(x_i)<n$. It's obvious that $exp(y_i)=r_i$.
Now $A_iA_j^2=(x_i-x_j)^2+(y_i-y_j)^2=x_i^2+x_j^2+y_i^2+y_j^2-2(x_ix_j+y_iy_j)$
$=\frac {p^{2n}}2-2(x_ix_j+y_iy_j)$.
In order $A_iA_j^2$ to be divisible by $p^{n+1}$ it's nesessary and sufficient to have $exp(x_ix_j+y_iy_j)\geq n+1$.
Let's connect two points $A_i, A_j$ with an edge iff $p^{n+1}|A_iA_j^2$.
We claim that from any three points, there is at least one edge connecting them.
Let them be, WLOG $A_1,A_2,A_3$ and suppose this fails.
Then $exp(x_1x_2+y_1y_2)\leq n$.
However $\frac {(x_1x_2+y_1y_2)(x_1y_2+x_2y_1)}{y_1y_2}=\frac {(x_1^2+y_1^2)x_2y_2+(x_2^2+y_2^2)x_1y_1}{y_1y_2}=\frac {\frac \frac {p^{2n}}(x_1y_1+x_2y_2) }{4y_1y_2}$.
Now we see that the greatest power of $p$ dividing this number is at least $2n+2 min\{r_1,r_2)-r_1-r_2=2n-|r_1-r_2|\geq n+1$ because $0\leq r_1,r_2\leq n-1$.
Since $exp(x_1x_2+y_1y_2)\leq n$ it follows that $exp(\frac {x_1y_2+x_2y_1}{y_1y_2})\geq 1$ or
$exp(\frac {x_1}{y_1}+\frac {x_2}{y_2})\geq 1$.
Analogously we get $exp(\frac {x_1}{y_1}+\frac {x_3}{y_3})\geq 1$ and $exp(\frac {x_3}{y_3}+\frac {x_2}{y_2})\geq 1$.
Now adding the first two relations, substracting the second and dividing by $2$ we get
$exp(\frac {x_1}{y_1})\geq 1$ which is impossible since $exp(\frac {x_1}{y_1})=r_1-r_1=0$.
This contradiction guarantees the claim.
Now, by Ramsey's Theorem in our graph having at least $6$ vertices, we must have either a $K_3$, or a $\overline{K_3}$. The last is impossible due to the claim hence there is a triangle.
QED

From IMO shortlist 2004 booklet..

[b]Solution.[/b]  A point with integer coordinates will be called an integer point. It is clear that if $A$ and~$B$ are integer points then $AB^{2}$ is a positive integer. The highest power of the given prime $p$ dividing $AB^{2}$ is denoted by $\alpha (AB)$ (i. e. ${\alpha (AB)=k}$ if $AB^{2}$ is divisible by $p^{k}$ but not by $p^{k+1}$). Note also that if $S$ is the area of a triangle with vertices at integer points, then $2S$ is an integer. The solution below is based on the following formulas involving the area $S$ of a triangle $ABC$ whose circumcircle has diameter $p^{n}$:
\begin{align*}
2AB^{2}\cdot BC^{2}+2BC^{2}\cdot CA^{2}+2CA^{2}\cdot
AB^{2}-AB^{4}-BC^{4}-CA^{4}=16S^{2},  \tag{1} \\
AB^{2}\cdot BC^{2}\cdot CA^{2}=(2S)^{2}p^{2n}.  \tag{2}
\end{align*}
[b]Lemma. [/b] Let $A,B$ and $C$ be integer points on a circle of diameter  $p^{n}$. Then either at least one of ${\alpha (AB),\alpha (BC),\alpha (CA)}$ is greater than $n$, or ${\alpha (AB),\alpha (BC),\alpha (CA)}$ are the numbers $n,n,0$, taken in some order.

[b]Proof.[/b] Let ${m\!=\!\min \{\alpha (AB),\alpha (BC),\alpha (CA)\}}$. By (1), $p^{2m}$ divides $(2S)^{2}$, so $p^{m}$ divides $2S$. Combined with (2), this implies ${\alpha (AB)+\alpha (BC)+\alpha (CA)\geq 2m+2n}$. Let ${\alpha (AB)\leq n}$, ${\alpha (BC)\leq n}$, ${\alpha (CA)\leq n}$. Then ${\alpha (AB)+\alpha (BC)+\alpha (CA)\leq m+2n}$, and hence ${2m+2n\leq m+2n}$, which means that ${m=0}$. So one of ${\alpha (AB),\alpha (BC),\alpha (CA)}$ is 0, and it is clear that the other two are equal to $n$.

Next, we prove that among every four integer points on a circle of diameter $p^{n}$ there exist two, $P$ and $Q$, such that ${\alpha (PQ)\geq n+1}$}. Assume that this is false for some points $A,B,C,D$ occurring on such a circle in this order. The lemma implies that $\alpha $ takes on value $0$ for two segments determined by $A,B,C,D$ without common endpoints, and value $n$ for the remaining 4 segments. So we may assume that there are positive integers $a,b,c,d,e,f$ not divisible by $p$ such that ${AB^{2}=a}$, ${CD^{2}=c}$, ${BC^{2}=bp^{n}}$, ${DA^{2}=dp^{n}}$, ${AC^{2}=ep^{n}}$, ${BD^{2}=fp^{n}}$. Then Ptolemy's theorem for the inscribed quadrilateral $ABCD$ yields ${\sqrt{ac}=p^{n}(\sqrt{ef}-\sqrt{bd})}$. Squaring both sides, we obtain ${ac=p^{2n}(\sqrt{ef}-\sqrt{bd})^{2}}$, so ${(\sqrt{ef}-\sqrt{bd})^{2}}$ is rational. However, ${(\sqrt{ef}-\sqrt{bd})^{2}=ef+bd-2\sqrt{bdef}}$, and this can be a rational number only if $\sqrt{bdef}$ is an integer. But then ${(\sqrt{ef}-\sqrt{bd})^{2}}$ itself is an integer, and ${ac=p^{2n}(\sqrt{ef}-\sqrt{bd})^{2}}$ implies that $p^{2n}$ divides $ac$, a contradiction.

Now label the eight given points $A_1,A_2,\dots,A_8$, draw the line segments they determine, and color black all segments $A_iA_j$ such that ${\alpha(A_iA_j)\ge n+1}$. The number of black segments with endpoint $A_i$ will be called the degree of $A_i$.

[b]Case 1.[/b] There is a point of degree at most 1, say $A_8$. Then at least 6 of the remaining points are not connected to $A_8$ by a black segment. Let such points be $A_1,A_2,\dots,A_6$. It is a popular fact that if the line segments joining 6 points are colored in two colors then this coloring contains a triangle with sides of the same color. Here this implies that either some triangle with vertices among $A_1,A_2,\dots,A_6$ has three black sides, and the claim follows, or some triangle has three uncolored sides, say $A_1A_2A_3$. But in the latter case the four points $A_1,A_2,A_3,A_8$ do not determine any black segment, a contradiction.

[b]Case 2.[/b] All points have degree 2. Clearly, then the black segments partition into cycles. The proof is complete if there is a black cycle of length 3, so let all cycles have length at least 4. Then there are two possibilities: two 4-cycles, say  $A_1A_2A_3A_4$ and $A_5A_6A_7A_8$, or one 8-cycle,  $A_1A_2A_3A_4A_5A_6A_7A_8$. In both cases, the four points $A_1,A_3,A_5,A_7$ do not determine any black segment, a contradiction.

[b]Case 3.[/b] There is a point of degree at least 3, say $A_1$. Suppose that $A_1A_2$, $A_1A_3$ and $A_1A_4$ are black. We claim that at least one segment among~$A_2A_3$, $A_3A_4$, $A_4A_2$ is black, which will complete the solution. If not, by the lemma $\alpha(A_2A_3),\alpha(A_3A_4)\alpha(A_4A_1)$ are $n,n,0$, taken in some order. Assuming that ${\alpha(A_2A_3)=0}$, denote by $S $ the area of the triangle $A_1A_2A_3$ and look again at the formulas (1) and (2). By (1), $2S$ is not divisible by $p $. On the other hand, since ${\alpha(A_1A_2)\ge n+1}$ and ${\alpha(A_1A_3)\ge n+1}$, (2) shows that $2S$ is divisible by $p$, a contradiction.

[b]Comment by the proposer.[/b] Let $p$ be a prime of the form ${p=4k+1}$. Consider the circle with diameter $OA$, where $O(0,0)$ and $A(p^{n},0)$. For ${i=1,\dots ,n}$ there are integers $x_{i},y_{i}$ not divisible by $p$ such that ${p^{i}=x_{i}^{2}+y_{i}^{2}}$. It is easy to check that $(p^{n- i}x_{i}^{2},p^{n-i}x_{i}y_{i})$ is an integer point on the given circle, ${i=1,\dots ,n}$. Therefore eight points on a circle with diameter $p^{n}$ do exist for large $n$.

If this proof is correct, then it seems that the result actually holds when there are 7 points instead of 8. (This is essentially a strengthened version of iura's solution.)

[hide]For a rational $n$, let $v_p(n)$ be $-|n|_p$, that is, the additive inverse of the $p$-adic norm of $n$. In the context of this proof, we will say that $a$ divides $b$ if and only if $v_p(b) \geq v_p(a)$.

(Until otherwise stated, "for all $i$ will be taken to mean for all integers $i$ between 1 and 7." Also, if a variable is used in a statement without any quantifier, the statement is taken to be true whenever that variable is an integer between 1 and 7.)

Let our 7 points be $(x_1, y_1), \ldots, (x_7, y_7)$, and suppose our circle is centered at $(h,k)$. We have that $(x_i - h)^2 + (y_i - h)^2 = \frac{p^{2n}}{4}$. Let $a_i = 2x_i - 2h$ and $b_i = 2y_i - 2h$. Then $a_i^2 + b_i^2 = p^{2n}$. We observe that $h$ and $k$ are rational, since $(h,k)$ is the intersection of the perpendicular bisectors of the segments with vertices $(x_1, y_1),(x_2,y_2)$ and $(x_2,y_2),(x_3,y_3)$, and the perpendicular bisectors of line segments joined by lattice points have rational slopes and rational $y$-intercepts. It follows that $(a_i, b_i)$ are all rational.

The square of the length of the side with vertices $(x_i, y_i)$ and $(x_j, y_j)$ is $(x_i - x_j)^2 + (y_i - y_j)^2$. This is divisible by $p^{n+1}$ if and only if 4 times this value is divisible by $p^{n+1}$, that is, if and only if
\begin{align*}
4(x_i - x_j)^2 + 4(y_i - y_j)^2
&= ((2x_i - 2h) - (2x_j - 2h))^2 + ((2y_i - 2k) - (2y_j - 2k))^2 \\
&= (a_i - a_j)^2 + (b_i - b_j)^2 \\
&= a_i^2 + b_i^2 + a_j^2 + b_j^2 - 2(a_i a_j + b_i b_j) \\
&= 2p^{2n} - 2(a_i a_j + b_i b_j)
\end{align*}
is divisible by $p^{n+1}$, which is true if and only if $a_i a_j + b_i b_j$ is divisible by $p^{n+1}$.

In the first case, suppose that $v_p(a_n) < 0$ for some $n$. $(a_i - a_j, b_i - b_j) = (2x_i, 2y_i) \in \mathbb{Z}$, so $v_p(a_i) = v_p(a_j) = v_p(b_i) = v_p(b_j) = -k$ for some positive $k$. Let $a_i' = p^k a_i$, $p^k b_i' = p^k b_i$, and $c_i = \frac{a_i'}{b_i'}$. Then $a_i'^2 + b_i'^2 = p^{2n+2k}$, where $v_p(a_i'), v_p(b_i') = 0$, and we wish to find $i,j,k$ such that $p^{n+2k+1} | a_i' a_j' + b_i' b_j', a_j' a_k' + b_j' b_k', a_k' a_i' + b_k' b_i'$. Since $n + 2k + 1 \leq 2n + 2k$, taking the equations $a_i'^2 + b_i'^2 = p^{2n+2k}$ modulo $p^{n+2k+1}$ and rearranging yield $c_i^2 \equiv -1 \pmod{p^{2n+2k}}$ for all $i$. Finding $i,j,k$ such that $p^{n+2k+1} | a_i' a_j' + b_i' b_j', a_j' a_k' + b_j' b_k', a_k' a_i' + b_k' b_i'$ is equivalent to finding $i,j,k$ such that $c_i c_j \equiv c_j c_k \equiv c_k c_i \equiv -1 \pmod{p^{n+2k+1}}$. Since there are only two residues that $c_i$ can be congruent to (by Hensel's lemma, the polynomial $x^2 + 1$ has exactly two roots modulo $p^{n+2k+1}$), the pigeonhole principle gives us distinct $i,j,k$ such that $c_i \equiv c_j \equiv c_k \pmod{p^{n+2k+1}}$, which completes our proof of this case.

We will now suppose that $v_p(a_i) \geq 0$ for all $i$. We first observe that if $v_p(a_i) < n$, then $v_p(a_i) = v_p(b_i)$; that if $v_p(a_i) \geq n$, then $v_p(b_i) \geq n$; and that the result holds when $a_i$ is swapped with $b_i$.

Call a pair $(a_i, b_i)$ unfortunate if $v_p(a_i),v_p(b_i) \geq n$. If there are three unfortunate pairs, then we are clearly done. Otherwise, we may assume that at most two tuples are unfortunate. (Henceforth, quantifiers such as "for all'' will include exactly the non-unfortunate pairs.)

Let $(a_i, b_i) = (p^{e_i} a_i', p^{e_i} b_i')$, $e_i \geq 0$, where each $a_i', b_i'$ is not divisible by $p$, and let $c_i = \frac{a_i'}{b_i'}$. We wish to find distinct $i,j,k$ such that $c_i c_j \equiv -1 \pmod{p^{n+1-e_i-e_j}}$, $c_j c_k \equiv -1 \pmod{p^{n+1-e_j-e_k}}$, and $c_k c_i \equiv -1  \pmod{p^{n+1-e_k-e_i}}$.

$a_i'^2 + b_i'^2 = p^{2n-e_i}$, so $c_i^2 \equiv -1 \pmod{p^{2n-e_i}}$. The equation $x^2 + 1 \equiv 0 \pmod{p}$ has exactly two solutions, $m$ and $n$, so each $c_i$ must be congruent to one of them modulo $p$.

Since we have at least 5 non-unfortunate $c_i$'s, by the pigeonhole principle, we can find some distinct $i,j,k$ such that $c_i \equiv c_j \equiv c_k \pmod{p}$. Note that for all $i$ and $j$, $2n - 2e_i \geq n+1 - e_i - e_j$ since $n \geq e_i + 1 \geq e_i + 1 - e_j$. Hence, $c_i^2, c_j^2 \equiv -1 \pmod{p^{n+1-e_i-e_j}}$ (with the same holding when $(i,j)$ is replaced with $(j,k)$ and $(k,i)$.) But since $c_i \equiv c_j \pmod{p}$, and there are exactly two square roots of -1 modulo $p^{n + 1 - e_i - e_j}$ both of which are distinct modulo $p$,  $c_i \equiv c_j \pmod{p^{n+1-e_i-e_j}}$. It follows that $c_i c_j \equiv -1 \pmod{p^{n+1-e_i-e_j}}$. We can reach the same conclusion when $\{i,j\}$ is replaced with $\{j,k\}$ or $\{k,i\}$, so our proof is complete. [/hide]

Here's another proof for $m=7$ points (which I believe is optimal when $p\equiv1\pmod4$). Let the $m$ points be $(x_k,y_k)\in\mathbb{Z}^2$ ($1\le k\le m$), $d_{j,k}$ be the distance between $(x_j,y_j),(x_k,y_k)$, and the center of the circle be $(X,Y)$, so $(x_k-X)^2 + (y_k-Y)^2 = p^{2n}/4$ for every $k$. Since $m\ge3$, $X,Y$ must be rational. If $p\equiv 3\pmod4$, we must have $v_p(x_k-X),v_p(y_k-Y) \ge n$ for all $k$, so any three points will work (note that $2n\ge n+1$).

Otherwise, if $p\equiv1\pmod4$, take integers $a,b$ with $p = a^2+b^2$. From now on, we work in $\mathbb{Q}[i]$; since $\mathbb{Z}[i]$ is a UFD, we can define, for any fixed prime $q\in\mathbb{Z}[i]$, a $q$-adic valuation $v_q$ on $\mathbb{Q}[i]$ satisfying $v_q(r/s) = v_q(r) - v_q(s)$ for any $r,s\in \mathbb{Z}[i]$ (where for $x\in \mathbb{Z}[i]$, $v_q(x)$ is the largest $t\ge0$ with $q^t\mid x$)---observe that each element of $\mathbb{Q}[i]$ can be written in the form $r/s$ for some $r\in\mathbb{Z}[i]$ and $s\in\mathbb{Z}$. Define $z_k = x_k + y_k i$, $Z = X+Yi$, and the primes $\alpha = a+bi$, $\beta = \overline{\alpha} = a-bi$. Then $p=\alpha\beta$, $(z_k-Z)(\overline{z_k-Z}) = p^{2n}/4$, and $v_\alpha(z_k-Z) = v_\beta(\overline{z_k-Z})$ by conjugation (the same holds with $\alpha,\beta$ swapped), so
\[ v_\alpha(z_k-Z)+v_\beta(z_k-Z) = v_\beta(\overline{z_k-Z}) + v_\beta(z_k-Z) = v_\beta(p^{2n}/4) = 2n \]for each $k$.

Now note that if $v_\alpha(z_k-Z)<0$ for some $k$, then $v_\alpha(z_j-Z) = v_\alpha((z_j-z_k)+(z_k-Z)) = v_\alpha(z_k-Z)$ for all $j\ne k$, since $z_j-z_k = (x_j-x_k)+(y_j-y_k)i\in\mathbb{Z}[i]$ implies $v_\alpha(z_j-z_k) \ge 0$. (Of course, the analogous statement for $\beta$ also holds.) Hence by pigeonhole, there must exist 3 indices $l_1,l_2,l_3$ with
\[ v_\alpha(z_{l_1}-Z) \le v_\alpha(z_{l_2}-Z) \le v_\alpha(z_{l_3}-Z) < v_\alpha(z_{l_1}-Z)+n. \](The "nontrivial case" is when $0\le v_\alpha(z_k-Z) = 2n-v_\beta(z_k-Z)\le 2n$ for all $k$.) Then
\[ v_\alpha(z_{l_j} - z_{l_k}) \ge \min(v_\alpha(z_{l_j}-Z),v_\alpha(z_{l_k}-Z)) \ge v_\alpha(z_{l_1}-Z)\]and similarly,
\[ v_\beta(z_{l_j} - z_{l_k}) \ge v_\beta(z_{l_3}-Z) = 2n - v_\alpha(z_{l_3}-Z) \ge n+1-v_\alpha(z_{l_1}-Z).\]But $v_\beta(\overline{z_{l_j}-z_{l_k}}) = v_\alpha(z_{l_j} - z_{l_k})$ and $v_\alpha(\overline{z_{l_j}-z_{l_k}}) = v_\beta(z_{l_j} - z_{l_k})$ by conjugation, so
\[ v_\alpha(d_{j,k}^2) = v_\alpha(z_{l_j}-z_{l_k}) + v_\alpha(\overline{z_{l_j}-z_{l_k}}) = v_\alpha(z_{l_j}-z_{l_k}) + v_\beta(z_{l_j} - z_{l_k}) \ge n+1. \]We similarly obtain $v_\beta(d_{j,k}^2) \ge n+1$, so because $d_{j,k}^2\in\mathbb{Z}\subset\mathbb{Z}[i]$, we must have $\alpha^{n+1},\beta^{n+1}\mid d_{j,k}^2$. Thus $p^{n+1} = \alpha^{n+1}\beta^{n+1}\mid d_{j,k}^2$ (as $\alpha,\beta$ are distinct primes and therefore coprime), and we're done. (More precisely, the rational number $d_{j,k}^2/p^{n+1}$ must be an algebraic integer and thus an integer itself.)

What a wonderful problem; here is a solution similar in spirit to the above.

The $p \equiv 3\pmod 4$ case is trivial so assume henceforth that $p\equiv 1\pmod 4$.

Note that the center $(c,d)$ is at half-integer coordinates, so a homothety centered at $0$ with ratio $2$ maps the circle to one centered at an integer and with radius $p^n$, then shift so that the center is $(0,0)$ and toss on the complex plane. Work in $\mathbb Z[i]$ with norm $N(z) = |z|^2$.

Take Gaussian integer $s = x+yi$, $t = u+vi$ lying on the circle $N(z) = p^{2n}$. We see that $N(s-t) = N(s)+N(t) - 2 (xu+vy)$ by properties of the dot product, so since $p^{n+1}\mid N(s)+N(t)$, $p^{n+1}\mid N(s-t)$ if and only if $p^{n+1} \mid 2(xu+vy) = 2\Re(s\overline t) = s\overline t + t\overline s) = p^{2n} \left(\frac st + \frac ts\right)$. On the other hand, the last term is real and so is divisible by $p$ if and only if \[
p^{2-2n} \mid N\left(\frac st + \frac ts\right) = N(s^2+t^2)/N(st) \iff p^{2n+2}\mid N(s^2+t^2).
\] Next, recall that $p = u^2+v^2$ by Christmas; so $(u+vi)(u-vi) = p$, and $r = u+vi$, $s = v+ui$ have prime norm, ergo they are also prime in $\mathbb Z[i]$. By unique factorization of $\mathbb Z[i]$ this means that $(u,v)$ is (up to permutation/negation) the only pair such that $u^2+v^2 = p$.

We now show that if $N(s) = p^k$, then $s = r^\ell t^{k-\ell} u$ for some integer $\ell \in [0,k]$ and unit $u \in \{\pm 1, \pm i\}$. Indeed, it suffices to show that if $N(s) = p^k$, $k > 1$, then $s$ is not prime. Indeed, say $s = a+bi$ and suppose by contradiction that it is prime; then $a,b$ are both not divisible by $p$, or else $u+vi\mid p\mid s$, contradiction. Otherwise, we have that, modulo $p$, $ub = va$ or $vb = ua$. In the first case, $a/b = u/v = -v/u\pmod p$, so $p\mid au+vb$, and so if $c = (au+vb)/p$, $d = \frac{bu-av}{p}$, then $(u+vi)(c+di) = a+bi$. Similarly in the other case we can find $c,d$ with $(v+ui)(c+di) = a+bi$, so either way $s$ is not prime since $N(v+ui) = N(u+vi) = p$, and so $N(c+di) > 1$.

Now, we note that if $a = r^{\ell}t^{2n-\ell}u$, $b = r^{m} t^{2n-m} v$ for units $u,v$ and $\ell \leq m$, then \[
N(a^2+b^2) = N\left(r^{2\ell} t^{4n-2\ell} + r^{2m} t^{4n-2m}\right) = N(r^{2\ell} t^{4n-2m})N(t^{2m-2\ell} + r^{2m-2\ell}) \geq (4n-2m+2\ell).
\]This is at least $2n+2$ when $m \leq \ell+(n-1)$. Now, say that our points have $r$-exponent $r_1\leq \cdots \leq r_8$. If $r_{k+2} \leq r_k + (n-1)$ for any $n$ we are done. Otherwise, we would have $r_{k+2} \geq r_k + n$ for all $k$, but then $r_5 \geq r_1 + 2n \geq 2n$, so $r_5 = r_6 = r_7 = 2n$ and we are done again. (Note that we do not use $r_8$, which is as observed above.)

My solution (which holds for $7$ points too):
First of all, we double the coordinates of each of the points, and the squares of distances of the newly changed points is $4$ times the square of the previous corresponding respective distance, so it is equivalent to the original problem if we find three points here. We break down the problem into two cases, proving each case with using at most $7$ of the $8$ vertices.
Consider the centre of the circle $(a,b)$. $(a,b)$ is clearly rational. Suppose $c$ is the smallest number such that upon scaling the coordinates by $c$, the coordinates of the centre $(ac,bc)$ are integer coordinates.
Case $1$: $v_p(c)>0$. Let $v_p(c)=t$. Note that this can happen only in the case $p=4s+1$ for some $s$, since if $p=4s+3$ and $x^2+y^2$ is a multiple of $p^{n}$ then $x^2,y^2$ are multiples of $p^n$ themselves.
Thus, if we shift the points so that the centre of the circle is now $0,0$(it preserves distance between the points), any of the rescaled chosen points is of the form $k,l$ such that $k,l$ are integers with $k^2+l^2=c^2*p^{2n}$. So, we need to find a triangle of $3$ chosen vertices such that $p^{n+1+2t}$ divides all of the sides of the triangle. We claim that we can find $3$ such points among any $5$ points for this case.
Sketch of proof: Using Pell equations one can show that  there exists a unique unordered pair $(r,s)$ of co-prime integers for which $p^d=r^2+s^2$, for any positive integer $d$, and any prime of the form $p=4k+1$.Thus, one can show from here, that if two integers $k^2$ and $l^2$ satisfy that $p^d|k^2+l^2$ and $k,l$ are not multiples of $p$ then the ordered pair $(k,l)$ is either congruent to $(rq,sq)$ mod $p^d$ for some integer $q$, or it is congruent to $(sq,rq)$ for some integer $q$. Note that if $(k,l)$ is congruent to $(rq,sq)$ mod $p^d$ then it isn't congruent mod $p^d$ to any pair of the form $(sq,rq)$ which we can show by mod $p$ things.( We will call this as Lemma 1. This lemma is the key lemma which helps us to solve the problem.) Accordingly, we divide such pairs $(k,l)$ into either $rs$ type or $sr$ type, taking $d=2n+2t$ here. Since there are at least $5$ points, by PHP, three of the points are of the same type. Now by using definitions we can trivially see that the square of sides of the three triangles formed by three points of the same type, are all divisible by $p^{2n+2t}$, which proves this case.
Case $2$: Now we come to case $2$, where $v_p(c)=0$. We again do the shifting of the centre $(ac,bc)$ to $0,0$ so any of the chosen rescaled shifted points satisfies that it is of the form $k,l$ for integers $k,l$ with $k^2+l^2=c^2p^{2n}$. We show that for this case we can make the suitable choice for the $3$ points from any $7$ of the given points. This case is again trivial for $p=4s+3$ due to the observation noted above, so we assume $p=4s+1$ for some $s$.
Sketch of proof: If at least three of the $7$ points satisfy $min(v_p(k), v_p(l)) \geq \frac{n+1}{2}$ then we can choose those $3$ points and we are trivially done. So there are at most $2$ points satisfying that both $k,l$ are multiples of $p^{\lceil{\frac{n+1}{2}}\rceil}$. Now, suppose there are at least $5$ points satisfying $min(v_p(k),v_p(l)) \leq \frac{n}{2}$, then we can use the techniques used in Lemma $1$, take $d=n+1$, divide into types again and finish in a similar way as case $1$. Thus, we are done as there are at least $7$ chosen points. Proved.
P.S.: The exponent $p^{n+1}$ can be strengthened to $p^{\lceil \frac{4n}{3} \rceil}$ for sufficiently large $n$ using the method in my proof and optimizing it, while still using only $7$ points.

[quote=Muriatic]Note that the center $(c,d)$ is at half-integer coordinates[/quote] Why so?

This is quite a nice problem. Let $A_1,A_2,A_3$ be three integer points on the circle, and let $O$ be the center of the circle. Let $d_{ij} = A_iA_j^2$.
[rule]
[b]Claim.[/b] Suppose that $v_p(d_{12}) \le v_p(d_{13}) \le v_p(d_{23}) \le n$. Then $v_p(d_{12}) = 0$ and $v_p(d_{13}) = v_p(d_{23}) = n$.

[i]Proof.[/i] Let $\theta = \angle A_1OA_2$, and suppose $v_p(d_{12}) = k \le n$. Then we have $A_1A_2 = p^n \sin(\theta/2)$, so $d_{12} = p^{2n}\sin^2(\theta/2)$, which implies $2d_{12} = p^{2n}(1-\cos\theta)$. Thus $\cos\theta$ is a rational number, and $v_p(1-\cos\theta) = k-2n$, which is equivalent to $v_p(1+\cos\theta) = k-2n$. By law of cosines,
\[d_{12}=d_{13}+d_{23}-2\sqrt{d_{13}d_{23}}\cos\angle A_1A_3A_2.\]
Thus
\[(d_{12}-d_{13}-d_{23})^2 = 4d_{13}d_{23}\cos^2(\theta/2) = 2d_{13}d_{23}(1+\cos\theta).\]
Therefore,
\[k-2n = v_p(1+\cos\theta) = 2v_p(d_{12}-d_{13}-d_{23})-v_p(d_{13})-v_p(d_{23}) \ge 2k - 2n\]
which happens if and only if $k=0$ and $v_p(d_{13}) = v_p(d_{23}) = n$. $\square$
[rule]
In the original problem, construct a graph $G$, in which we connect two lattice points $A_1,A_2$ on the circle with a red edge if $v_p(d_{12}) \ge n+1$, and otherwise connect them with a blue edge. Suppose for contradiction that there does not exist a red $K_3$.

[b]Lemma. [/b]There cannot exist a blue $K_4$.

[i]Proof. [/i]Suppose that there exist four lattice points $A_1,A_2,A_3,A_4$ on the circle such that $v_p(d_{ij})\le n$ for each $1\le i\ne j\le 4$. Applying the claim, we conclude that a pair of opposite edges (WLOG $d_{12}, d_{34}$) have $v_p$ equal to 0, and the other four edges all have $v_p$ equal to n. But by Ptolemy's theorem,
\[(d_{12}d_{34} \pm d_{14}d_{23} \pm d_{13}d_{24})^2 = 4d_{14}d_{23}d_{13}d_{24},\]
so taking $v_p$ of both sides gives $n=0$, contradiction. $\square$

Back to the original problem, we divide into cases based on $G$.

[b]CASE 1: [/b]All vertices are incident to at most 2 red edges. WLOG each vertex is incident to exactly 2 red edges, then the graph is the union of red cycles. Because no red $K_3$ exist, it can only be a cycle of length 8 or two cycles of length 4. Both cases gives a blue $K_4$, contradiction.

[b]CASE 2:[/b] Some vertex is incident to at least 3 red edges. Since there are no blue $K_4$ or red $K_3$, it is incident to exactly 3 red edges. Thus the $v_p$ of these edge lengths squared is as labeled below:

[asy]
size(5cm);
pair A = (0,0), B = (0,1), C = (1,1), D = (1,0);
draw(A--B--C--D--cycle);
draw(A--C);
draw(B--D);
label("$\ge n+1$", (B+C)/2, N);
label("$\ge n+1$", (A+B)/2, W);
label("$\ge n+1$", (2B+D)/3, N);
label("$n$", (2A+C)/3, S);
label("$n$", (A+D)/2, S);
label("0", (D+C)/2, E);
label("$A_1$", A, SW);
label("$A_2$", B, NW);
label("$A_3$", C, NE);
label("$A_4$", D, SE);
[/asy]

Consider the triangle $A_2A_3A_4$. By law of cosines,
\[(d_{34}-d_{23}-d_{24})^2 = 4d_{23}d_{24}\cos^2(\angle A_3A_2A_4/2) = 2d_{13}d_{23}(1+\cos\angle A_3OA_4).\]
The left side has $v_p$ equal to zero. But we also know that $v_p(1+\cos\angle A_3OA_4) = -2n$, so the right side has $v_p$ at least 2, contradiction.


On the forum, I posted a message yesterday, and I can't see it today. But it is just my posts. Why?

I cannot find them on the Classroom, Moems, and Mathcounts forum.

Can you think of any reason why a moderator might have chosen to delete or move some of your posts?

No, It shows that my posts are there in the thread. But when I click on the Thread, my posts on that thread do not appear.

Yeah, Firefox can suck at times.  I have 2.0.0.2 on Mac OS X version 10.3.9 and firefox works for me.  Do you have a windows or a mac?

[quote="hunter34"]I found out that it only happens on Firefox. I have Firefox 2.0.0.6[/quote]

Did you try refreshing your cache? Also, try clearing all personal settings. If all else fails, then reinstall firefox.

I already did that. I still get the error.

I don't see how it could be a PHP error if it's browser specific. Could you post screenshots of Firefox and no-Firefox?

[quote="hunter34"]I don't know how to take a screenshot.[/quote]

Press the key "Print Screen" (or "Prt Scr", or "Print Scrn", or "Prnt Scrn", depending on your keyboard) on your keyboard. It should be above the "Insert" key. Then go to MS Paint, or any program that can handle graphics, and press Crtl-v, or simply RightClick and then "Paste". Thus you have a screen shot, and now you simply have to save...

On a Mac: Command-Shift-Three
Hold them down in that order.
On your desktop, you should see a jpeg named Picture1.
Hope this helps!


I'm doing a project, in which I have to write a research paper about whether Microsoft's dominance is good or bad for society.  I have to come up with 45 questions that I have to try to answer (for my research), and I only have 36.  Can anyone help me come up with some questions?  Two example questions: WHat is Microsoft's explanation for all of its security glitches?  What foreign countries are investigating Microsoft for abusing its power?

What are some alternatives to Windows?

Why do people prefer Microsoft to other operating systems?

Easy Bill Gates is a friendly Democrat who has given the most money to charity of the world's richest men.  He is very equal and not corrupt like many rich men. He has criticized Bush's extravagant tax cut on the  rich.


$a,b$ are natural number and $ab+1$ is a perfect square.Prove that there exist $c$ in natural number such that $ac+1$ and $bc+1$ are perfect square.

Please, do not post problems in the 'solved section'... :(

Pierre.


Marie owns 103 department stores. Each store has 106 shelves for towels. What is the total number of shelves for towels?

The total number of shelves for towels is just $ 103(106)\equal{}(100\plus{}3)(100\plus{}6)\equal{}10000\plus{}900\plus{}18\equal{}\boxed{10918}$ shelves for towels.


How about the area satifying the following graph represented by

$ (x^2\plus{}y^2\minus{}1)(x^2\plus{}y^2\minus{}2y\minus{}3)\le0$ ?

 :P  :blush:

Solve the inequality for equality, seeing that the factors can be arranged into circles. Then test points in the regions.


I think that formula should be $A_{n}= 2A_{n-1}+2A_{n-3}-A_{n-5}$.


1. Let $p(x) = ax^2+bx+c$ for certain coefficients $a,b,$ and $c$. If $p(1) = 1, p(2) = 2,$ and $p(3) = 4$, what is $p(5)$?

2. Five lines parallel to the base of a triangle divides each of the other sides into six equal segments and the area into six distinct parts. If the area of the largest of these parts is 33, then what is the area of the original triangle?

3. You have 2003 switches, numbered from 1 to 2003, arranged in a circle. Initially, each switch is either ON or OFF, and all configurations of switches are equally likely. You perform the following operation: for each switch S, if the two switches next to S were initially in same position, then you can set S to ON; otherwise, you set S to OFF. What is the probability that all switches will now be ON?

The answer for 1 is as follows.

[hide] From the given condition,we can set $p(x)=a(x-1)(x-2)+x$,so $p(3)-3=a\cdot2\cdot1=1\Longleftrightarrow a=\frac{1}{2}$.

Therefore we obtain $p(x)=\frac{1}{2}(x-1)(x-2)+x$.The desired answer is $p(5)=11$.[/hide]

1. [hide] Its just a parabola, so 1,2,4,8,16.  f(5) of whatever wil be 16.[/hide]

2.  [hide]Imagine that the first segment has one small triangle in in.  The next smaller one would have 3 of these, 5,7,9,11,  using some algebra you can say the largest area is 33 sq units and there are 11 triangles in it so each triangle is 3 sq units.  That means that the 36 total triangles*3=108sq units.[/hide]

3.  [hide]All the switches would have to start as on or off.  2003 total switches, and the first one doesn't matter... so I think it is 2^2002.  I'm not gonna write that out though, lol[/hide]

for 2

[hide]
the height of the triangle is divided into 6 equal parts as well.
there is a triangle with 5/6 the height and 5/6 the base of the triangle we are trying to find

$\frac{bh}{2}- \frac{25bh}{72} = 33$

solving that for $\frac{bh}{2}$ will give something like $\frac{33 \cdot 36}{7}$ which seems weird.  maybe some math is wrong.

[/hide]

for number 1, i think we can difference it out

[quote="eryaman"]Somedude, remmber that that only works without coefficients, constants, etc.[/quote]

for one or what... and I'm confused how my 1 is wrong, cause I can think of a graph namely y=x^2 that that applies to...

3.[hide]If their all going to be on at the end, then each one has to have the ones next to it be the same.  This can be done by having them start either: ON-OFF-ON-OFF-ON-...; OFF-ON-OFF-ON-...; ON-ON-ON-ON-ON...; OFF-OFF-OFF-OFF-OFF-OFF.  The first two however aren't possible since there are an odd number, meaning that when they're arrnaged in a circle the start and end ones will be the same.  So they have to be all ON or all OFF.  Number of total ways=2^2003, so answer is 2/2^2003=(1/2)^2002.[/hide]


This is a funny problem

Assume there are $ n$ men and $ m$ women. and they infected different diseases. make it more precisely, there are $ m\times n$ different diseases. and there is a relationship between people and disease, and the relationship is $ 1\minus{}1$.
OK, now every men need to kiss everyone of the women, because we must stop cross infection. so how many respirators we need at least?
and we assume respirator can be used one on top of another. the virus can't through respirator.

 :ninja:

[quote="JBL"]I don't really understand this question, but it reminds me very much of [url=http://blog.tanyakhovanova.com/?p=168]The Dirtiest Math Problem Ever (Rated R)[/url] (from Tanya Khovanova's math blog).[/quote]

Yes, I mean this [quote]Another fun variation of this problem is when you have two men and two women and two condoms. Every woman wants to have sex with every man. How can they do that[/quote]

and I want to know if the number of men is $ m$, and the number of women is $ n$, then How many condoms we need at least to stop  cross infection....


quadratics
number theory unsolved
number theory

(a) Let $ p \equiv 3 (mod 8)$ be a prime number.
Show that there exist $ x,y \in Z$ such that
\[ x^{2}\plus{}2y^{2}\equal{}p\]

(b) Let $ p \equiv 1 (mod 4)$ be a prime number.
Show that there exist $ x,y \in Z$ such that
\[ x^{2}\plus{}y^{2}\equal{}p\]

b) is solved in several ways [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=219017]here[/url]; the methods can be adapted to a).  You will want to show that $ \minus{}2$ is a quadratic residue $ \bmod p$ when $ p \equiv 3 \bmod 8$.

Very easy problems  :rotfl:

a) x=1,y=1:

$ 1^2\plus{}2\cdot1^2\equal{}1\plus{}2\equal{}3$

b) x=0, y=1:
$ 0^2\plus{}1^2\equal{}0\plus{}1\equal{}1$

[quote="t0rajir0u"]The problem statements ask to prove that such $ x, y$ exist for [i]all[/i] primes of the given form.  And $ 1$ is not prime.[/quote]

That's $ 10^{10^{10^{10}}}$ times harder than I thought  :D

[quote="Bachukas"]Very easy problems  :rotfl:

a) x=1,y=1:

$ 1^2 \plus{} 2\cdot1^2 \equal{} 1 \plus{} 2 \equal{} 3$

b) x=0, y=1:
$ 0^2 \plus{} 1^2 \equal{} 0 \plus{} 1 \equal{} 1$[/quote]

 :rotfl:  very nice solution  :D

(Just a joke)  :blush:

[quote="t0rajir0u"]b) is solved in several ways [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=219017]here[/url]; the methods can be adapted to a).  You will want to show that $ \minus{} 2$ is a quadratic residue $ \bmod p$ when $ p \equiv 3 \bmod 8$.[/quote]
Yeah, I know that $ \minus{} 2$ is a quadratic residue $ \bmod p$ when $ p \equiv 3 \bmod 8$.
But, for a long time, I can not focus the idea that can be adapted to (a).  :(


Recunosc ca am o varsta cam inaintata ptr.matematica si probabil de aceea m-am si impotmolit. Am doua probleme si va rog foarte mult sa nu ma ocoliti."Se arunca doua zaruri de 3 ori. Care este probabilitatea ca dubla 6,6 sa apara cel putin o data?" si "Zece bile numerotate de la 1 la 10 se aseaza la intamplare una dupa alta intr-un sir. Care este probabilitatea ca dupa bila nr.5 sa urmeze bila cu nr.6?"
Le-am rezolvat dar nu sunt sigura pe rezultat : 1-(25/36)la puterea a treia (doar paranteza ridicata la putere) si 9x8!/10! sau 9!8/10! (nu sunt sigura care). Ma poate ajuta cineva?

1. $\left( \frac{35}{36} \right)^3$, pentru ca-s $36$ de cazuri, numai unul e bun.

2. $\frac{9 \cdot 8!}{10!}$, pentru ca bilele $1,2,3,4,7,8,9,10$ se aseaza mai intai la intamplare, apoi se pun $5,6$ intr-unul dintre cele noua spatii disponibile: $- 1 - 2 - 3 - 4 - 7 - 8 - 9 - 10 -$. Sper sa fie bine.

Cu raspunsul la intrebarea doi sunt de acord, dar nu sunt lamurita la prima. In manualul de cls.a X a este o poblema asemanatoare doar ca se arunca un zar de doua ori iar raspunsul este [b]1-(5/6)³[/b]. Dupa cum spui tu ar trebui sa fie doar[b] (5/6)³[/b].

ca sa apara cel putin o data inseamna: apare la una din cele 3 aruncari sau la doua din cele 3 aruncari sau la toate trei. Daca notam cu A evenimentul sa nu apara dubla 6,6 atunci avem da calculat nonA, adica P(nonA)=1-P(A)=1-$(\frac{35}{36})^3$


Let $a+b+c=2$ abd $ax+by+cz=6$, find minimum value of:
\[ T=a\sqrt{16+x^2}+b\sqrt{16+y^2}+c\sqrt{16+z^2}  \]
if $a \geq 0$.

Does it require that a, b, c are positive ?

[quote="Lovasz"]Let $a+b+c=2$ abd $ax+by+cz=6$, find minimum value of:
\[ T=a\sqrt{16+x^2}+b\sqrt{16+y^2}+c\sqrt{16+z^2}  \][/quote]

[hide="One-liner"]
$T = \sqrt{ (4a)^2 + (ax)^2 } + \sqrt{ (4b)^2 + (by)^2 } + \sqrt{ (4c)^2 + (cz) ^2} \ge \sqrt{ (4a + 4b + 4c)^2 + (ax + by + cz)^2} = \sqrt{ 8^2 + 6^2} = \boxed{10}$

(Minkowski's Inequality.  :) ) [/hide]

When you absorb the $a$ into the square root sign, it is necessary that $a \geq  0$:?:  :!:

Yes, you're right, it's necessary. I saw this problem, like this:

[quote]Let $a+b+c=2$ abd $ax+by+cz=6$, find minimum value of:
\[ T=\sqrt{16a^2+a^2x^2}+\sqrt{16b^2+b^2y^2}+\sqrt{16c^2+c^2z^2}  \][/quote]
But I moved $a$ out of the square root symbol, without condition $a \ge 0$, when posted. Sorry for mistake.


Hi, I'm wondering what I should do to get better at the AIME. I can currently do most AMC 12 problems with ease, so making the AIME shouldn't be hard.

However, I'd really like to qualify for USAMO, so I'm wondering what I should practice for doing well on the AIME. I can do some of the problems I see on it, but not all of them and it can take me a bit of time. As well, I find I make a lot of mistakes on AIME problems.

So, does anyone have any recommendations for what I should do? And particular stratgies/methods for practicing? Like, are there particular problems I should focus on more? Anything that anyone would recommend I study?

PS:  Geometry is the area I find the hardest (but I still find AIME problems of other types hard too)


function
combinatorics proposed
combinatorics

There are n people labeled from 1 to n respectively standing in a circle.Find the maximum f(n) such that  always exist three consecutive peple with the sum of the their labeled numbers is greater than f(n)
The orginal problem of mine is that twenty people with their labeled numbers from 1 to 20 and stand in a circle.Prove that there are three consecutive people such that the sum of their number is equal to or greater than 20.

[quote="nkht-tk14"]Find the minimum f(n) such that  always exist three consecutive peple with the sum of the their labeled numbers is greater than f(n)[/quote]

I think you mean to say "maximum". "minimum" is trivial.


function
algebra
domain
calculus
derivative
linear algebra
matrix

Let
$ u \equal{} 1 \plus{} \frac {x^3}{3!} \plus{} \frac {x^6}{6!} \plus{} \frac {x^9}{9!}...$
$ v \equal{} x \plus{} \frac {x^4}{4!} \plus{} \frac {x^7}{7!} \plus{} \frac {x^{10}}{10!} \plus{} ...$
$ w \equal{} \frac {x^2}{2!} \plus{} \frac {x^5}{5!} \plus{} \frac {x^8}{8!} \plus{} ...$
It can be shown that each of these series converges for all x, so u, v, and w can be thought of as functions of x whose domain is all real numbers.
Show that $ u^3 \plus{} v^3 \plus{} w^3 \minus{} 3uvw \equal{} C$ for some constant C. What is C?

\begin{eqnarray*} u^3 + v^3 + w^3 - 3uvw & = & (u + v + w)(u + \omega v + \omega^2 w)(u + \omega^2 v + \omega w) \\
& = & e^x e^{\omega x} e^{\omega^2 x} \\
& = & 1. \\
\end{eqnarray*}

An argument with more calculus and no complex numbers:

Note that $ u' \equal{} w,v' \equal{} u,$ and $ w' \equal{} v.$

Define $ f(x) \equal{} u^3 \plus{} v^3 \plus{} w^3 \minus{} 3uvw.$

$ f'(x) \equal{} 3u^2u' \plus{} 3v^2v' \plus{} 3w^2w' \minus{} (3u'vw \plus{} 3uv'w \plus{} 3uvw')$

$ \equal{} 3u^2w \plus{} 3v^2u \plus{} 3w^2v \minus{} 3vw^2 \minus{} 3u^2w \minus{} 3uv^2 \equal{} 0.$

Hence $ f(x)$ is constant. Since $ u(0) \equal{} 1,v(0) \equal{} 0$ and $ w(0) \equal{} 0$, we have that $ f(0) \equal{} 1$ and hence $ f(x) \equal{} 1$ for all $ x.$

Those three derivative identities (you mean $ u' \equal{} w, v' \equal{} u, w' \equal{} v$) highlight an interesting point:  $ u^3 \plus{} v^3 \plus{} w^3 \minus{} 3uvw$ is precisely the determinant of the Wronskian of $ (u, v, w)$, which is a [url=http://en.wikipedia.org/wiki/Circulant_matrix]circulant matrix[/url].  The factorization I gave is really diagonalization, and one finds that the eigenvalues of this matrix are $ e^x, e^{\omega x}, e^{\omega^2 x}$.  In other words, $ u, v, w$ are linearly independent over $ \mathbb{C}$.

Shouldn't it be $ u' \equal{} w \minus{} x$, $ v' \equal{} u$, $ w' \equal{} v \plus{} 1$?  I think the assertion that $ f$ is constant is incorrect; I haven't worked through the algebra, but just an eyeball estimate in a neighborhood of $ 0$ shows $ f(x)\approx 1\minus{}3x^2$.

I'm pretty sure the $ x$ in the definition of the last function (which should be called $ w$) shouldn't be there.

I read what aahmadi should have said, not what he actually said. This problem looks very familiar - I'm sure it's in Stewart's calculus book.

The actual definition should be

$ w\equal{}\frac{x^2}{2!}\plus{}\frac{x^5}{5!}\plus{}\frac{x^8}{8!}\plus{}\cdots.$

aahmadi made two transcription errors: not calling it $ w$, and adding the extraneous $ x$ term.

Looking at what t0rajiro0u wrote, I see that he also read what should have been there rather than what was actually there.

Take a look at B7 from the 1939 Putnam Exam:

[url]http://web.archive.org/web/20040602050437/www.kalva.demon.co.uk/putnam/psoln/psol3914.html[/url]

And yes, [b]Kent[/b]... The problem appears in Stewart's book, too. No mention whatsoever to the Putnam Exam therein, though.

Regards.

[quote="t0rajir0u"]$ u^3 \plus{} v^3 \plus{} w^3 \minus{} 3uvw$ is precisely the determinant of the Wronskian of $ (u, v, w)$[/quote]
As $ \{u,v,w\}$ forms a fundamental system of solutions for the equation $ y'''\minus{}y\equal{}0,$ where the 2nd leading coefficient - the coefficient of $ y''$ - is zero, the Wronskian determinant satisfies the equation $ W'\plus{}0\cdot W\equal{}0.$

In this case $ u,v,$ and $ w$ are elementary functions. Each of them can be written as linear combinations of $ e^x,e^{\minus{}x/2}\cos\left(\frac{\sqrt{3}}2\,x\right),$ and $ e^{\minus{}x/2}\sin\left(\frac{\sqrt{3}}2\,x\right).$


linear algebra
matrix
linear algebra unsolved

Find all $ n\times n$ matrix $ A$ ($ n\ge 2$) such that $ \det\left(A\plus{}B\right)\equal{} \det A\plus{}\det B$ for all $ n\times n$ matrix $ B$.


Find all prime number $p$ such that for any $x,y\in{\mathbb Q}_p$ we must have $|x^2+y^2|_p=\min\{|x|_p^2,|y|_p^2\}$

Enjoy~  ;)

Are you sure that you dont want to have $|x^2+y^2|_p=\max\{|x|_p^2,|y|_p^2\}$ instead¿
(otherwise take $x=p,y=1$)
Then it reduces to the existence of $\sqrt{-1}$ in $\mathbb{Q}_p$, and that only occurs for $p \equiv 1 \mod 4$.

I think it's quite the contrary: the primes we're looking for are those for which $-1$ is [b]not[/b] a square (i.e. those of the form $4k+3$). Otherwise just take $x=1$ and $y$ a square root of $-1$ modulo $p$. We have $|x|^2_p=|y|^2_p=1$, but $|x^2+y^2|_p\le\frac 1p$.

yes i mean $|x^2+y^2|_p=\max\{|x|_p^2;|y|_p^2\}$ that's why i said it seems old  ;)


Let  $x,y,z$ be positive real numbers satisfying  $x^2+y^2+z^2=3$. Prove that

$\frac{x}{x^2+3}+\frac{y}{y^2+3}+\frac{z}{z^2+3}\le \frac{3}{4}$

Observe that $\frac{4x}{x^2+3} \le 1/4 \cdot x^2+ 3/4$, which follows by the factorization $(3/4 + 1/4 \cdot x^2)(x^2+3)-4x = \frac{1}{4}(x-1)^2(9+2x+x^2) \ge 0$. Adding this cyclicly gives the desired.


calculus
floor function
limit
trigonometry
function
algebra unsolved
algebra

In Principle , Limits is a topic in calculus and should come in that forum. However, this particular question appeared in an Algebra textbook and that is why I am putting it here (hoping there is a non- calculus solution) I will be happy to shift my post if the administrator find so.

The problem is :-

$ If\ a\ > 0\ find\  lim _{ x \rightarrow 0^{+} } \frac{x}{a} [ { \frac{b}{x} }] $

$ If\ a\ > 0\ find\  lim _{ x \rightarrow 0^{-} } [ \frac{x}{a}] { \frac{b}{x} } $

where $ [x] $ is the greatest integer function.

[quote="ali"]a)b/a

b) +inf[/quote]

First is correct but second is wrong. Can you give detailed method/ solution plz.

Unfortunately, second one is not wrong!
Clearly the limit is +infinity.

[b]The book gives the 2nd answer as 0[/b].

Can you post soln. plz

The correct answer is $+\infty$ if $b$ is positive, $-\infty$ if $b$ is negative. For $x$ close enough to zero and negative, $\lfloor \frac xa\rfloor=-1$. Clearly, $\lim_{x\to0^-}\frac bx$ is $-\infty$ if $b$ is positive and $+\infty$ if $b$ is negative. Multiplying the two limits, we are done.

But we can multiply 2 limits to get the limit of their product if and o0nly if both limits exist and are finite. Isn't that right??

Also, we are effectively evaluating one part of the limit and then the other to get the answer. Shouldn't we evaluate both parts simultaneously.

e.g.in $ \lim _ { x \rightarrow 0 }\frac{\sin{x} \cos{x}}{x} $.

We cant evaluate $ \lim \frac{\sin{x}}{x} $ first and then multiply it by $ \cos{0} $ . We need to evaluate $ \sin{2x}$ etc. to get limit.

[quote="Rushil"]We cant evaluate $\lim \frac{\sin{x}}{x}$  first and then multiply it by $\cos{0}$  . We need to evaluate $\sin{2x}$ etc. to get limit.[/quote]
Actually, you can do just that. If $\lim g(x)=k$, where $k$ is finite and nonzero, then $\lim f(x)g(x)=k\lim f(x)$. There are some conventions about multiplication involving $\infty$ that I'm folding in. For calculus purposes, we can define $a\cdot b$ for all pairs $a,b$ in the extended real numbers unless one of $a$ and $b$ is zero and the other is infinite.

In the case I was dealing with, we can even replace the first factor by -1 and not change it at all in the region we care about. The behavior of the function for $x<-a$ doesn't affect the limit at all.

[quote="Rushil"]But we can multiply 2 limits to get the limit of their product if and o0nly if both limits exist and are finite. Isn't that right??[/quote]
No, it is not. Yet:

[quote="Rushil"]e.g.in $ \lim \frac{\sin{x} \cos{x}}{x} $
We cant evaluate $ \lim \frac{\sin{x}}{x} $ first and then multiply it by $ \cos{0} $ . We need to evaluate $ \sin{2x}$ etc. to get limit.[/quote]
This contradicts a bit the previous quote, right?

yes it does I couldn't think of a counterexample then so I put this in. Anyways, it's not possible to multiply 2 limits if they are not defined. That was my point


We have all seen the error message "There's no line here to end" whenever we had put something like

"Hello world \\ \\" to try to get two blank lines following Hello World.

So, \\ means end the line. So Why would "Hello \\ World" work? Because the parser is adding a hidden "start a new line" when it interprets "World". You are never informed that it is.

Well, by that logic "Hello \\ \\", when the parser see the second \\, it means End the Line, but shouldn't it get the same treatment "World" did? And become (implicit newline) + End The Line?. Well, just because there was no content on that line doesn't mean its not a valid line. (A contentless line still is a line.) But yet it returns the error message.

So the failure of LaTeX is that interprets a blank line that has no content as "Not a Line". But that simply isn't true. There are plenty of examples in text everywhere you look where a line that has zero content but is still considered a line. In HTML we have

. Notice the Lack of content between first
 and the second
.

"Hello \newline \\ World" works. \newline breaks the current line and tells the parser it wants a newline as well. Well guess what we have for hte first thing as a new line? You guessed it, \\. And it takes it. Well then, if "Hello \\ World" means "World"  is what it takes as the next line then "Hello \\ \\ World" should work too. If it doesn't, then it is inconsistent that
"Hello \newline \\ World" works.

Hello \\ \\ World
Hello \newline \\ World
Hello \newline \newline World
all produce exactly the same result. But there is a difference between \newline and \\ as the latter can take an extra parameter. Thus \\*[10cm] produces vertical spacing before the next line [i]and[/i] prevents a page break occurring between the 2 lines, putting it before the first line if necessary. A page break is however possible after \newline.

I agree \\ just means 'end the line here'. There's more on this topic at [url=http://www.tex.ac.uk/cgi-bin/texfaq2html?label=newlineargs]Start of line goes awry[/url].


calculus
derivative
integration
calculus computations

Suppose that $ f$ be two times differentiable and its image be in $ \mathbb{R}$ and $ f(0)=0 , f^'(0)>0$ and $ \forall x\geq 0 ; f^{''}(x)>f(x)$. Prove that $ \forall x>0 ; f(x)>0$.

[hide]
First let $ f(x)\equal{}e^xg(x)$. Then $ f^{\prime \prime }(x)>f(x)$ implies
\[ e^{x}g^{\prime \prime} (x)\plus{}2e^xg^\prime (x)\plus{}e^xg(x)>e^xg(x)\]
\[ \Rightarrow g^{\prime \prime}(x)\plus{}2g^\prime (x)>0\]
Now letting $ g^\prime (x)\equal{}e^{\minus{}2x}h(x)$, we get $ h^\prime (x)>0$. (This is true for all $ x\geq 0$.)

So $ h$ is strictly increasing for $ x\geq 0$, and $ h(0)\equal{}g^\prime (0)$. By isolating $ g$ in terms of $ f$,
\[ g^\prime (x)\equal{}(f^\prime (x)\minus{}f(x))e^{\minus{}x}\Rightarrow g^\prime (0)\equal{}f^\prime (0)>0\]
As a result, $ h(x)>0$ for $ x\geq 0$, so $ g$ is strictly increasing for $ x\geq 0$.

Since $ g(0)\equal{}f(0)\equal{}0$, $ g(x)>0$ for $ x>0$ implying $ f(x)>0$ for $ x>0$.
[/hide]

we write f''-f=h where h>0 on R+

f is solution of differential equation  (E) y''-y=h
solve (E) with f(0)=0  and f'(0)>0 we have

$ y(x)\equal{}2a\sinh(x)\plus{}\int_{0}^{x}\sinh(x\minus{}t)h(t)dt$  with a>0

$ y(x)\equal{}2a\sinh(x)\plus{}\int_{0}^{x}\sinh(u)h(x\minus{}u)du>0$ for all x>0

[quote="Jane_Bennet"]If $ \mathrm{f}(0) \equal{} 0$ and $ \mathrm{f}'(0) > 0$, then there is a $ \delta > 0$ such that $ \mathrm{f}(x)$ is positive for all $ x$ with $ 0 < x < \delta$. (The proof is elementary using the $ \epsilon$–$ \delta$ definition of the derivative of f.) Suppose the set $ S \equal{} \{\delta > 0: 0 < x < \delta\Rightarrow\mathrm{f}(x) > 0\}$ is bounded above. Let $ s \equal{} \textrm{sup}\,{S}$. Hence $ \mathrm{f}(x) > 0$ for all $ x$ with $ 0 < x < s$. Now let’s see what happens with $ \mathrm{f}(s)$.

Suppose $ \mathrm{f}(s) < 0$. Since $ \mathrm{f}\left(\frac {s}{2}\right) > 0$, by the intermediate-value theorem, $ \exists\,b\in\left(\frac {s}{2},s\right)$ such that $ \mathrm{f}(b) \equal{} 0$ – contradiction. Now suppose $ \mathrm{f}(s) \equal{} 0$. By Rolle’s theorem, $ \exists\,c\in(0,s)$ such that $ \mathrm{f}'(c) \equal{} 0$. Then by the mean-value theorem, $ \exists\,d\in(0,c)$ such that $ \mathrm{f}''(d) \equal{} \frac {\mathrm{f}'(c) \minus{} \mathrm{f}'(0)}{c} < 0$. Since $ \mathrm{f}''(d) > \mathrm{f}(d)$, this would imply that $ \mathrm{f}(d) < 0$, another contradiction. Thus, we must have $ \mathrm{f}(s) > 0$.

But $ \mathrm{f}(s) > 0\ \Rightarrow$ (by the continuity of f) $ \mathrm{f}(x) > 0$ for all $ x$ in some interval containing $ s$, say the interval $ (s \minus{} \alpha,s \plus{} \alpha)\ (\alpha > 0)$. It follows that $ s \plus{} \alpha\in S$, contradicting the definition of $ s$ as the supremum of $ S$.

Therefore the set $ S$ is not bounded above – in other words, $ \mathrm{f}(x) > 0$ for all $ x > 0$. :thumbup:[/quote]

Neat solution!!  :lol:
I had a scorpius-type solution to this, but your proof is really nice. :D


algebra
polynomial
superior algebra
superior algebra unsolved

Hi all

It was mentioned today in my algebra class that all finite dimensional associative division algebras over a field K are equal to K. I was thinking about how to prove this, and I thought of the following: Assume the dimension over K is n, for any element d, take the set {1,d,d^2,...,d^n}. Then this is a K-linearly dependent set so we can create a polynomial of degree <= n that is satisfied by d. Since k is algebraically closed, then d is in k.

Since this proof didn't use that our algebra is a division algebra, there must be something wrong with it but I can't figure out what. Thanks

You have used the following theorem: If $ K$ is algebraically closed and $ R$ is a finite-dimensional $ K$-algebra, and if $ d\in R$ satisfies some polynomial over $ K$, then $ r\in K$.  Unfortunately, this is false.  Take $ R\equal{}K\times K$, for example, then elements of either component easily satisfy polynomials in $ K$, but are not both "in $ K$".

The above theorem is only true when $ R$ is a field.  The right way to do it is to let $ R\equal{}K(d)$, which is a commutative division algebra, hence a field.

Ah yes I see now. It is because only over a field can we assume a polynomial of degree n has at most n solutions. Thanks very much.


hey guys,
i'm going into junior this sept, and i haven't taken biology yet..
and i'm planning to take ap bio in my senior year (iam not going to take regular class). I signed up for ap comp. sci. and i'll self study for ap physics C in my junior year..
however, i heard from my friends that there is a disadvantage if i take bio in my senior year......
Is there???
Thanks,

I doubt it, I'm taking it senior year too (next year).

I think its worse to take bio junior year because you'd look like a slacker taking bio instead of ap physics, physics honors or ap chem.

Eh?  Are you implying that AP Bio is the easiest of AP Chem and Physics?  At my school it's the hardest...

Yeah, at our school it is.

The seniors take it and the juniors who did not do so well in honors chem take it.

I guess its different from school to school.

I'm not familiar with any disadvantage in taking AP Biology senior year.

I took it as a sophomore and the only other student to make a five in the class was a senior.

bio<chem<physics (c)

that was my experience (easier to harder)

I don't know about the class, as I never took it.  I'm sure it varies quite a bit from school to school.

In my experience, however, the actual AP test is a joke.


I noticed that a lot of registered users haven't posted any posts. Actually, 2410 to be exact. What happens to their accounts?

Nothing - I don't think this is that uncommon.  Many boards have very high percentages of 'lurkers'.

A real-world estimate for most online discussion groups (email, Web-based, or whatever) is that roughly 10 percent of the readers do almost all the posting. Over time, a few of the lurkers will post once in a while, but meanwhile some new members have joined, and old members have left active reading of the group behind.

Since some parts of the forum are open to registered users only, there should be no wonder why many people register without posting anything. It's not everybody's hobby to write down mathematical proofs!

  Darij

One time, in one of my friend's boards, I posted about 1/3 of all of the posts.


AMC
USA(J)MO
USAMO
geometry proposed
geometry

call $ O_k$ the center of $ \omega_k$ for k=1,2,3,4,5.

We have: $ \angle O_5A_1A_2 \equal{} 180 \minus{} \hat{A_1} \minus{} (180 \minus{} \hat{A_2} \minus{} (180 \minus{} \hat{A_3} \minus{} (180 \minus{} \hat{A_2} \minus{} \angle O_1A_2A_1))) \equal{}$

$ \equal{}  \angle O_1A_2A_1 \plus{} \hat{A_2} \plus{} \hat{A_4} \minus{} \hat{A_1} \minus{} \hat{A_3}$

Then $ \angle O_5A_1A_2 \equal{} \angle O_1A_2A_1 \ \Longleftrightarrow \ \hat{A_2} \plus{} \hat{A_4} \equal{} \hat{A_1} \plus{} \hat{A_3} \equal{} 180$

[quote="calc rulz"]Let $ A_1A_2A_3A_4$ be a quadrilateral and let $ \omega_1$ be a circle in its plane passing through $ A_1$ and $ A_2.$ Suppose there exist circles $ \omega_2, \omega_3, \dots, \omega_5$ such that for $ k \equal{} 2, 3, \dots, 5,$ $ \omega_k$ is externally tangent to $ \omega_{k \minus{} 1}$ and passes through $ A_k$ and $ A_{k \plus{} 1},$  where $ A_{n \plus{} 4} \equal{} A_{n}$ for all $ n \ge 1$. Prove that $ \omega_5 \equal{} \omega_1$ if and only if $ A_1 A_2 A_3 A_4$ is cyclic.

[hide="Remark"]
This is an extension of USAMO 2000 #5
[/hide][/quote]
[hide="Solution"]
Invert around $ A_1$ to map figure $ F$ to $ F'$.  Hence, $ \omega_1'$ turns into a line through $ A_2'$.  $ \omega_2'$ turns into a circle tangent to $ \omega_1'$ at $ A_2'$ and passing through $ A_3'$.  $ \omega_3'$ turns into a circle through $ A_3'$ and $ A_4'$, tangent to $ \omega_2'$.  $ \omega_4'$ turns into a line tangent to $ \omega_3'$ at $ A_4'$.  Finally, $ \omega_5'$ turns into a line through $ A_2'$ parallel to $ \omega_4'$.

Now, if $ \omega_1 \equal{} \omega_5$, then we see that $ \omega_1'\parallel \omega_4'$.  Let $ O$ be the center of $ \omega_2'$ and $ P$ be that of $ \omega_3'$  Thus, $ OA_2'\perp \omega_1'$ and $ PA_4'\perp \omega_4'\implies OA_2'\parallel PA_4'$.  This means that since $ \omega_2'$ and $ \omega_3'$ are tangent, $ \angle OPA_4' \equal{} \angle POA_2'$.  Since $ OA_2' \equal{} OA_3'$ and $ PA_3' \equal{} PA_4'$, we see that $ \triangle A_2'OA_3'\sim \triangle A_4'PA_3'$ and it follows that $ \angle PA_3'A_4' \equal{} \angle OA_3'A_2'$, which means that $ A_4'$, $ A_3'$, and $ A_2'$ are collinear, and we conclude that $ A_1A_2A_3A_4$ is cyclic.

If $ A_1$, $ A_2$, $ A_3$, and $ A_4$ are concyclic, then we notice that $ \angle PA_3'A_4' \equal{} \angle OA_3'A_2'$ since $ A_2'$, $ A_3'$, and $ A_4'$ are collinear.  It follows that $ \angle PA_4'A_3' \equal{} \angle OA_2'A_3'\implies \angle A_2'OA_3' \equal{} \angle A_3'PA_4'$.  Let $ X$ be a point on $ \omega_4'$ and $ Y$ be a point on $ \omega_1'$.  From the tangencies, it follows that $ \angle A_3'A_4'X \equal{} \frac {\angle A_3'PA_4'}{2} \equal{} \frac {\angle A_2'OA_3'}{2} \equal{} \angle A_3'A_2'Y$, and it follows that $ \omega_1'\parallel \omega_4'$, so $ \omega_1 \equal{} \omega_5$.  [/hide]


trigonometry
function
geometry proposed
geometry

[color=darkred]Let $ABC$ be an isosceles triangle with $AB=AC$, such that $\angle{BAC}=100^{\circ}$. Given are the points $D\in (BC)$ and $E\in (AB)$.
Prove that if the measures of two from the angles $\angle BAD$, $\angle ACE$, $\angle CED$ are equally to $30^{\circ}$, then and the another angle has the same measure.[/color]

I think we can have solution by calculation, let $AB=AC=a$ and $O$ is mid point of $BC$, $CH$ is altitude $\Rightarrow AO=a\sin 40,DA=\frac{AO}{cos(DAO)}=\frac{a\sin 40}{\cos(50-BAD)}(1)$
Similar we have $CE=\frac{CH}{\cos(ACE+10)}(2)$
$BD^{2}=a^{2}+AD^{2}-2aAD\cos 40(3)$
$AE^{2}=CE^{2}+CA^{2}-2CACE\cos(ACE)(4)$
$BE=a-AE(5)$
$DE^{2}=BD^{2}+BE^{2}-2BEBD\cos 40(6)$
$CD=2a\cos 40-BD(7)$
$\cos(DEC)=\frac{DE^{2}+DC^{2}-EC^{2}}{2DEDC}(*)$
Now we take seven equation in we will get the function
$f(BAD,ACE,DEC)=0$ when we have two number in three we will get the orher.

Is it not essentially the same problem as [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=82733]Ascertain an angle in a triangle[/url] ?

Assuming $\angle BAD = \angle ACE = 30^\circ,$ then from the solutiuon of the above problem, $DE \parallel CA$ and $\angle CED = \angle ACE = 30^\circ.$

Assuming $\angle ACE = \angle CED = 30^\circ,$ then $DE \parallel CA$ and from the solutiuon of the above problem, $\angle BAD = \angle ACE = 30^\circ.$

Assuming $\angle BAD = \angle CED = 30^\circ,$ then $\angle DAC = \angle BAC-\angle BAD = 70^\circ,$ $\angle ADC = 180^\circ-(\angle DAC+\angle DCA) = 70^\circ,$ $\triangle ACD$ is isosceles with CD = CA. Let circle (C) with this radius meet AB again at F. $\angle DCF = 360^\circ-2 \angle DAF = 60^\circ,$ $\triangle CDF$ is equilateral. Since $\angle CED = 30^\circ,$ circle (F) with radius FC = FD cuts the segment AB at E. $\triangle DEF$ is isosceles with FD = FE, $\angle EFD = 180^\circ-(\angle BAC+\angle BDF) = 20^\circ$, $\angle FED = 80^\circ,$ $\angle BED = 180^\circ-\angle FED = 100^\circ.$ Consequently, $DE \parallel CA$ and $\angle ACE = \angle CED = 30^\circ.$


Let $ a, b \in R$ and $ \sin{\frac{a}{2}} \neq 0$.

Find $ S\equal{}\sin{b}\plus{}\sin{(a\plus{}b)}\plus{}\sin{(2a\plus{}b)}\plus{}...\plus{}\sin{(na\plus{}b)}$

We use
\[ \sum_{k \equal{} 0}^n \sin(\alpha \plus{} kh) \equal{} \left\{\begin{array}{ll}\frac {\sin\left(\alpha \plus{} \frac {n}{2}h\right)\sin\frac {n \plus{} 1}{2}h}{\sin\frac {h}{2}} & (h \neq 2m\pi) \\
(n \plus{} 1) \sin \alpha & (h \equal{} 2m\pi) \end{array}\right.
\]

[hide="Complex numbers"]\begin{eqnarray*}
S&=&\sum_{k=0}^{n}\sin ka\cos b+\cos ka\sin b\\
&=&\cos b\sum_{k=0}^{n}\sin ka+\sin b\sum_{k=0}^{n}\cos ka\\
&=&\cos b\cdot\text{Im}\left(\sum_{k=0}^{n}\cos ka+i\sin ka\right)+\sin b\cdot\text{Re}\left(\sum_{k=0}^{n}\cos ka+i\sin ka\right)
\end{eqnarray*}

Let's consider $ \sum_{k=0}^{n}\cos ka+i\sin ka$. By De Moivre's theorem, it is equal to $ \sum_{k=0}^{n}(\cos a+i\sin a)^k=\sum_{k=0}^{n}e^{iak}$.

Suppose $ S_2=1+e^{ia}+e^{2ia}+\cdots+e^{nia}$.
Then $ e^{ia}\cdot S_2=e^{ia}+e^{2ia}+\cdots+e^{(n+1)ia}$.
So that $ e^{ia}\cdot S_2-S_2=S_2(e^{ia}-1)=e^{(n+1)ia}-1$.

And $ S_2=\frac{e^{(n+1)ia}-1}{e^{ia}-1}$.

For simplicity, let $ w=\cos((n+1)a)$, $ x=\sin((n+1)a)$, $ y=\cos a$, and $ z=\sin a$.

$ \frac{(w-1)+xi}{(y-1)+zi}\cdot\frac{(y-1)-zi}{(y-1)-zi}=\frac{((w-1)+xi)((y-1)-zi)}{(y-1)^2+z^2}$
$ =\frac{(w-1)(y-1)+xz}{(y-1)^2+z^2}+\frac{i((w-1)z+(y-1)x)}{(y-1)^2+z^2}$
$ =\frac{(\cos((n+1)a)-1)(\cos a-1)+(\sin((n+1)a))(\sin a)}{(\cos a-1)^2+\sin^2 a}+i\cdot\frac{(\cos((n+1)a)-1)(\sin a)+(\cos a-1)(\sin((n+1)a))}{(\cos a-1)^2+\sin^2 a}$.

And I really don't feel like simplifying it any more, but you can see where it's going.[/hide]

Sorry I got lazy at the end...  :|


Các bạn ơi,

chúng tôi đang xây dựng các tuyển tập đề thi để giúp các em HS có nhiều cơ hội tiếp cận với đề thi bình thường lẫn nâng cao. Các bạn hãy cùng giúp post các đề thi, đề kiểm tra mà bạn có tại

http://www.thuvienkhoahoc.com/dethi/

Rất mong nhận được sự giúp đỡ dù là rất ít.

điều này có ích cho hệ thống giáo dục Việt Nam,vì vậy tôi kêu gọi các bạn thể hiện sự giúp đỡ tích cực  :)

cho em hỏi nếu mình muốn post đề thi lên trang này thì phải làm thế nào ạ???em không biết cách!!!hix hix!!! :(

Huong dan post de thi co the xem tai

http://www.thuvienkhoahoc.com/dethi/Tr%E1%BB%A3_gi%C3%BAp:Nh%E1%BA%ADp_d%E1%BB%AF_li%E1%BB%87u_%C4%91%E1%BB%81_thi_m%E1%BB%9Bi

Mong cac ban ung ho,


Determine maximum resistance between $A$ and $B$ in figure below!

[hide="EXTRA PROBLEM"]
  Wat is the minimum resistance between the points?

[/hide]

No wrong (correct : $15 \Omega$)
What about minimum?

[b]Thaakisfox[/b]
Perhaps your method was right, please present it.

Also as far as I an concerned, this problem is not solved yet so others
are welcome to contribute with solutions.


Can anyone please answer the following?

Let $ Z_n$ be a branching process with $ Z_0\equal{}1$ i.e. $ Z_n\equal{}\sum_{j \equal{} 1}^{Z_{n\minus{}1}}\xi_{nj}, n\ge 1$ and offspring distribution $ \{p_k\}$ with $ m\equal{}\sum_{k \equal{}0}^{\infty}kp_k \ne 1$ where $ \xi_{nj}$ are i.i.d. r.v's with $ P[\xi_{nj}\equal{}j]\equal{}p_j, j\ge 0$

Show that $ lim_{n\to \infty} Z_n\equal{}0 a.s.$ if $ m<1$ and is either $ 0$ or $ \infty$ if $ m>1$.

I think that once you notice that $ m^{\minus{}n} Z_n$ is a positive martingale, and thus converges almost everywhere, the conclusion easily follows. Isn't it ..

Ya,   $ m^{ \minus{} n}Z_n$ is a positive martingale hence by Martingale convergence theorem  $ m^{ \minus{} n}Z_n$ converges a.s. But how does the conclusion follow from this?

Moreover, it is clear that $ {Z_n}$ is a Markov chain and 0 is an absorbing state. But can anyone show that the nonzero states are transient?

If you are in state $ n$, the probability to return to this state is strictly less than $ 1$ if $ p_0> 0$ (because there is a non-zero probability for the process to immediately die out), which shows that in this case the state $ n$ is transient. The case $ p_0\equal{}0$ is even simpler: then $ Z_n$ is monotone and increases during each step with probability at least $ 1\minus{}p_1>0$.

Thank you very much fedja. Now I could understand the complete picture of what is going on. You people are helping a lot thru' Mathlinks for first time learners like me.


I have been using the alcumus program and find it magnficent. In accordance with my enjoyment, I have begun to entertain the idea of a number theory alcumus or intermediate geometry. My question should be obvious up to this point but just in case: will Alcumus expand and if so, will it continue to be free?
Thanks


quadratics
pigeonhole principle
number theory
relatively prime

Find all positive integers $n$ with the property that the set \[\{n,n+1,n+2,n+3,n+4,n+5\}\] can be partitioned into two sets such that the product of the numbers in one set equals the product of the numbers in the other set.

[quote="Peter"]Find all positive integers $ n$ with the property that the set
\[ \{n,n+1,n+2,n+3,n+4,n+5\}\]
can be partitioned into two sets such that the product of the numbers in one set equals the product of the numbers in the other set.[/quote]
[hide]
Mod 7, Wilson's gives us that the value is -1 if none of the terms has 7 as a factor. -1 isn't a quadratic residue. So, one of the terms must have a 7, but then the other one can't. No values.[/hide]

from piegonhole we know that if there are six numbers one of them must be divisible by 5.

but we need product and so 2 numbers must be divisible by 5 and those numbers are $n,n+5$

so $n$ and $n+5$ are in the diferent subsets ,
we have 6 cases :

[b]1°[/b]  ${n,n+2,n+4}$  , and ${n+1,n+3,n+5}$

[b]2°[/b]  ${n,n+3,n+4]}$  , and ${n+1,n+2,n+5}$

[b]3°[/b]  ${n,n+1,,n+4}$  , ${n+2,n+3,n+5}$

[b]4°[/b]  ${n,n+1,n+2}$  ,  ${n+3,n+4,n+5}$

[b]5[/b]  ${n,n+1,n+3}$     ,  ${n+2,n+4,n+5}$

[b]6[/b]  ${n,n+3,n+4}$  , ${n+1,n+2,n+5}$

from now just a litle work on inequalitles  and none of these cases workt

Not so nice way (but better than the mod 5):
[hide]We know that consecutive numbers are always relatively prime. We also know that consecutive odd numbers are always relatively prime. Thus, let's consider two cases: one where n is even, and one where n is odd. If n is even, consider n+3. This is relatively prime to both n+2 and n+4, since they are consecutive numbers, and it is also relatively prime to both n+1 and n+5, since they are all consecutive odd numbers. Thus, if n+3 is placed in one group, n must be in the other group, and must contain all of the factors of n+3, a contradiction. Next, if n is odd, consider n+2. By the same argument, it's relatively prime to all the numbers except n+5, so that means that n+2 must divide n+5. This is only possible if n is 1. We can check that this case is not possible. Thus, there exist no n.[/hide]

Nice way:
[hide]It's clear that none of the numbers can be divisible by 7, since then only one number will be divisible by 7, and 7 will be in one product, but not the other. Thus, n, n+1, n+2, n+3, n+4, n+5 must be 1, 2, 3, 4, 5, and 6 in Z/7Z. That means their product is 6, or -1, in Z/7Z. However, (-1/7)=-1, so this product cannot satisfy the conditions of the problem statement.[/hide]

More generally, for any sequence of consecutive positive integers $n, n+1, \ldots, n+k$ there exists a prime $p$ such that $p$ divides $n+i$ for some $i$ with $0 \le i \le k$, but $p$ does not divide any of the other integers. This general statement implies that for any partition of a set of consecutive integers into at least two sets, there exists one set such that the product of the numbers in this set is different from any product of numbers in other sets.

[b]Proof.[/b] If $n > k+1$ we have Sylvester's Theorem that one element of our sequence is divisible by a prime $p > k+1$. None of the other elements can be divisible by $p$, since $p$ is larger than the length of the interval. For $n \le k+1$ we have a prime $p$ with $n \le \left \lceil(n + k)/2 \right\rceil < p \le n + k$ by Bertrand's Postulate and no other integer in the sequence can be divisible by $p$, since $2p > n + k$.


I was just wondering why nobody seems to talk a lot about the famous  'mature' cartoons.
I personally think the simpsons are the most intelligent cartoon ever, with tons of musical snacks ,references, clever jokes, hidden references to other episodes etc...   check snpp.com  for each episode

however after about the seventh season it became a drag

south park really knows how to laugh at typical ways parents and kids act, but the creators  have a political view that is sometimes way too obvious, instead of subtle

futurama is refreshing compared to late simpsons episodes,  the idea of being in the future opens a lot of doors
however some eps have a weak scenario

then there is family guy
extremely rude (and sometimes touches to racist, although it may be seen as criticism on racism, but where is the line) but very very very original
the creator seth mcfarlane is the best at imitating typical stuff (like annoying parts) from all sorts of shows and movies, however you really need to know a lot of those shows, and as i am not american i have to look it up often

[url=http://www.familyguyfiles.com/main.php]family guy references[/url]
is a good site about those references
another difficult thing is that they do so much flashbacks "hey it's just like the time dad hit that deer, just like the time i was a guard at george harrison's house,..." that you often don't know in which episode a joke was done and how it was brought up

So any other shows like this that need be discussed
you hate or love one of these shows for a particular reason
or just wanna scream out full of enthusiasm that you love them?
then reply!

South Park is the best show ever!
You should add wonder showzen, it's pretty funny and almost all animated

This interesting topic isn't talked about in the Music and Art Forum because it belongs in Fun and Games, where I will move it.

[quote="JesusFreak197"]Don't like any of them. I find that most of the stuff that comes on TV regularly is junk, IMO, so I only use my TV for videos and games. In fact, it isn't even hooked up to be able to watch normal TV. :P[/quote]

No even sports?

i like simpsons....they help me to unterstand how stupid human beings could be :lol:

[quote="juicybooty911"]No even sports?[/quote]

I generally watch the Superbowl at someone else's house, and that's it. I'm not a big sports person. *shrug*

[b][color=#00f000]J[/color][color=#0ce80c]e[/color][color=#18e018]s[/color][color=#24d824]u[/color][color=#30d030]s[/color][color=#3cc83c]F[/color][color=#48c048]r[/color][color=#54b854]e[/color][color=#60b060]a[/color][color=#6ca86c]k[/color][color=#78a078]1[/color][color=#849884]9[/color][color=#909090]7[/color][/b]

South Park shows me what twisted adults would be like if they were put in a bunch of stupid 3rd graders bodies.

i think the simpsons is hugely underestimated
most complaints come from people who don't know the simpons
some say it is just a silly cartoon, others say it uses profanity, others say that it is just filth ,meant to make our children politically incorrect

the simpsons just do this blend of parody, great story, and criticism

It also breaks with the 'all american family' image.  The family comes home and eats before the tv.  It's not perfect.  But it's realistic.  The father is no half preacher.

For the record, when i say which show you like best, I do mean the episodes in general not the current ones!

You young people like fourteen year old or something, you guys do see the reruns right?

I barely watch tv anymore... the one that I like most out of all of them would have to be futurama. Great concept, jokes, and the scifi theme rocks
Simpsons is close second.

Family guy I'm sure has some great jokes, but the flashbacks like you said, are kinda overused, and a friend mentioned that the format for each episode is a bit formulaic.

And I just despise huge fanbases and over-merchandise-ation in general. (Everyone at my school owns a family guy article of clothing and I can't go a day without hearing some quote from the show)

South Park? Even more so.

I will now don my flame-retardant suit.

I find them all to be awesome...i'll watch whichever i get time for.

Well, in truth, I don't like South Park nearly as much as the others...maybe because i haven't watched it much before, and it really has to "sink in"/one has to know the characters.

Flame?  Thou must not fear from me.  None of them is perfect, I gave arguments myself against every one of them.  Hmm I am not completely against merchandise but I try to refrain from buying it.  In my opinion you have to like a movie or a show for the most important thing : the show or movie.  I have a simpsons pillow (got it as a present) and all of the bongo strip cartoons (the first ones are very good but you can see it decline along with the episodes).

Interestingly, the simpsons even spoof their own franchise : when Krusty organises a kids camp with himself, that turns out to be shady business as he doesn't show up at first and where the kids make wallets for Hong Kong, Bart says : I would never give my name to an inferior product. ;)

[quote="fredbel6"]I was just wondering why nobody seems to talk a lot about the famous  'mature' cartoons.
I personally think the simpsons are the most intelligent cartoon ever, with tons of musical snacks ,references, clever jokes, hidden references to other episodes etc...   check snpp.com  for each episode
[/quote]

What he said. SIMPSONS 4 LYF. I love you Homer

Oh man, it's a close call between the Simpsons and Family Guy for me.  I went with The Simpsons though.  I've watched that show during a greater portion of my life and it never failed to entertain me.  Family Guy is awesome as well.  The last episode I saw, quite frankly, stunk.  I don't know what it was, but I just did not find it funny.  But that's just one episode, so of course I haven't given up on Family Guy yet :D

That said, I rarely watch tv.  During the first semester of school this year I watched maybe 10 hours total.  Over Christmas break though, I probably averaged at least 10 a week.  Now I'm back to school and usually only watch tv on weekends for a few hours or during the week if something really important (to me at least :P) is on.  A lot of it's the news though.

South Park for me. It's unbelievable how stupid just about everybody is in that show. And how they always come up with different ways to kill Kenny is incredible.

DOnt watch tv at all..... well, sometimes.....

Why watch TV when you can get ahead in your schoolwork :?:  (Im homeschooled through CAVA)  TV seems to me like a waste of time.

Uhm you serious?  As much as people find me a freak that I adore mathematics, temptation to watch some tv is always present? :oops:

And tv is not necessarily a waste of time, people like Matt groening and Seth mcfarlane are the few optimists who don't go along wtih mainstream and make something else than reality tv, plastic surgery shows,.....
Although Matt groening should have ended the simpsons instead of letting it go to waste.
:cleaning:   We must not give up the battle!


Could you please help me on this example: :oops:

Suppose the temperature at a certain location t hours after noon on a certain day is
(T degree Celsius), where $ T\equal{}\frac{1}{3}t^3\minus{}3t^2\plus{}8t\plus{}10$
a) How fast is temperature rising or falling at 1.00 p.m, i.e. (t=1)
b) At what instant is the temperature stationary?

I guess I should use derivation here. But can't figure out what and where.   :?:

$ T'(t) \equal{} \frac {dT}{dt} \equal{} t^2 \minus{} 6t \plus{} 8$

[b](a)[/b] $ T'(1) \equal{} 1 \minus{} 6 \plus{} 8 \equal{} 3$ grad/sec
Because $ T'(1) > 0$ the temperature is rising.

[b](b)[/b] $ T'(t) \equal{} 0\rightarrow t_{1} \equal{} 2$ sec, $ t_{2} \equal{} 4$ sec
$ T(t_1) \equal{} \frac {50}{3}\approx 16.67$ grad.
$ T(t_2) \equal{} \frac {46}{3}\approx 15.33$ grad.

to Yuriy Solovyov...

So you mean when you make derivation of the function (temperature function) you get the speed of temperature changing?
And why the temperute is stationary in critical points? What is the difference between them and any other point? I know that the temperature gets the maximum and minimum values in these critical points, but why is it stationary?

[quote="Yuriy Solovyov"]Yes, when I make derivation of the function (temperature function) I get the speed of temperature changing.
Temperute is stationary in critical points because the speed of it`s changing is $ 0$. Temperature become a constant for a small period of time $ dt$.
In the other points this speed $ \ne 0$.[/quote]

I got it. Thank you very much  :)