inequalities
number theory unsolved
number theory

Let $(a,b,c)$ be a Pythagorean triple, i.e. a triplet of positive integers with $ a^2\plus{}b^2\equal{}c^2$.

$a)$ Prove that $\left(\frac{c}{a}\plus{}\frac{c}{b}\right)^2>8$.
$b)$ Prove that there are no integer $n$ and Pythagorean triple $(a,b,c)$ satisfying $\left(\frac{c}{a}\plus{}\frac{c}{b}\right)^2\equal{}n$.

hello, for a) your inequality is equivalent to
$ c^2\left(\frac{1}{a}\plus{}\frac{1}{b}\right)^2>8$
$ c^2\left(\frac{a\plus{}b}{ab}\right)^2>8$
$ (a^2\plus{}b^2)(a\plus{}b)^2>8a^2b^2$
$ (a\minus{}b)^2(a^2\plus{}4ab\plus{}b^2)>0$
The last inequality is obviously true.
Sonnhard.

By the Generalized Holder's inequality we have

$ (ca^2 \plus{} cb^2)(\frac {c}{a} \plus{} \frac {c}{b})(\frac {c}{a} \plus{} \frac {c}{b})>(c \plus{} c)^3 \equal{} 8c^3$
or
$ (\frac {c}{a} \plus{} \frac {c}{b})^2>8$.

b)

Let $ q\equal{}\frac ab \plus{} \frac ba\equal{}\frac {c^2}{ab}$
We have \[ \left(\frac c a \plus{}\frac c b\right)^2\equal{}(a^2\plus{}b^2)(a^2\plus{}b^2\plus{}2ab)(ab)^{\minus{}2}\]
\[ \equal{}(a^4\plus{}b^4\plus{}2a^2b^2\plus{}2a^3b\plus{}2b^3a)(ab)^{\minus{}2}\equal{}\left(\frac ab\right)^2\plus{}2\plus{}\left(\frac ba\right)^2\plus{}2\frac ab\plus{}2\frac ba\]
\[ \equal{}q^2\plus{}2q\]
This is an integer iff $ q^2\plus{}2q\plus{}1\equal{}(q\plus{}1)^2$ is an integer. Since this is a rational number, $ q\plus{}1$ and therefore $ q$ must also be integers. So $ c^2\equal{}kab$ for some integer $ k$ so we have that:

$ c^2\equal{}kab\equal{}a^2\plus{}b^2$, $ a^2\minus{}kab\plus{}b^2\equal{}0$, $ a\equal{}\frac{kb\plus{}\sqrt{k^2b^2\minus{}4b^2}}{2}\equal{}\frac{kb\plus{}b\sqrt{k^2\minus{}4}}{2}$
So $ k^2\minus{}4$ is a perfect square, k=2, and $ a\equal{}b$, but clear then $ a^2\plus{}b^2$ is not a perfect square, contradiction.

Assume that there are $ a,b,c$ be positive integers satisfying $ (\frac {c}{a} \plus{} \frac {c}{b})^2 \equal{} n$ with the lowest possible $ a \plus{} b \plus{} c$
Easy to show that $ gcd(a,b,c) \equal{} d \equal{} 1$.Indeed, let $ a \equal{} da',b \equal{} db',c \equal{} dc'$
$ \Rightarrow (\frac {c}{a} \plus{} \frac {c}{b})^2 \equal{} (\frac {c(a \plus{} b)}{a \plus{} b})^2 \equal{} (\frac {c'(a' \plus{} b')}{a' \plus{} b'})^2 \equal{} n$
$ \Rightarrow a',b',c'$ also satisfy our problem's condition and $ a' \plus{} b' \plus{} c' < a \plus{} b \plus{} c$, contradiction.
Moreover , we have $ a^2 \plus{} b^2 \equal{} c^2 \Rightarrow gcd(a,b)|c \Rightarrow gcd(a,b) \equal{} 1$
$ a | c^2(a \plus{} b)^2 \equal{} (a^2 \plus{} b^2)(a \plus{} b)^2 \Rightarrow a|b^4$,contradiction with $ gcd(a,b) \equal{} 1$
Q.E.D

[hide="Solution to a)"]$a)$ $(\frac{c}{a}+\frac{c}{b})^{2}$

$=\frac{c^2}{a^2}+\frac{c^2}{b^2}+\frac{2c^2}{ab}$

$=\frac{c^2b^2}{a^2b^2}+\frac{c^2a^2}{a^2b^2}+\frac{2abc^2}{a^2b^2}$

$=\frac{c^2(a+b)^2}{a^2b^2}$

$=\frac{(a^2+b^2)(a+b)^2}{a^2b^2}$

Since for a Pythagorean Triplet, $a\not=b$, $a^2+b^2>2ab$ by AM-GM, and $(a+b)^2>2ab+2ab=4ab$. Multiplying these two together gives \[(\frac{c}{a}+\frac{c}{b})^2=\frac{(a^2+b^2)(a+b)^2}{a^2b^2}>\frac{2ab\times4ab}{a^2b^2}=8\][/hide]

[hide="Solution to b)"]$b)$ Let $\frac{c}{a}+\frac{c}{b} = m$ for some integer $m$. Since $(\frac{c}{a}+\frac{c}{b})^2$ is an integer, $\frac{c}{a}+\frac{c}{b}$ itself must be an integer. Let $gcd(a,b) = 1$ (thus this is a primitive Pythagorean Triplet). This means that $a,b$ have opposite parities, and so $a^2+b^2=c^2$ is odd, and so $c$ is odd. From $\frac{c}{a}+\frac{c}{b} = m \Rightarrow c(a+b)=mab$. Since $odd+even = odd$ and $c$ is odd, the left-hand side overall is odd. However, one of $a,b$ must be even, so the right-hand side is even. Contradiction, and thus there is no solution to $(\frac{c}{a}+\frac{c}{b})^{2}=n.$[/hide]

Solution for a) by C-S:

[hide]By Cauchy,    $2(\frac{c}{a} + \frac{c}{b}) \ge (\sqrt{\frac{c}{a}} + \sqrt{\frac{c}{b}})^{2}$. The RHS is equal to $LHS + \frac{2c}{\sqrt{ab}}$, so we have:
$$LHS \ge \frac{2c}{\sqrt{ab}} \implies LHS^2 \ge \frac{4c^2}{ab}$$ and the RHS here is greater than or equal to 8 by AM-GM. Because a Pythagorean triple can't have $a=b$, we're done.[/hide]

[hide=a)]
Note that $a\ne b$ because otherwise, $c=a\sqrt{2}$, which is not an integer. Then by the trivial inequality, we have $a^2+b^2>2ab$. Since $a$ and $b$ are positive, we have
\begin{align*}
\frac{a^2+b^2}{ab}&> 2\\
\frac{c^2}{ab}&> 2
\end{align*}By AM-GM, we have
\begin{align*}
\frac{a+b}{2}&\ge \sqrt{ab}\\
(a+b)^2&\ge 4ab\\
\frac{(a+b)^2}{ab}&\ge 4.
\end{align*}Since $a$ and $b$ are positive, we can multiply the equations to get
\begin{align*}
c^2\left(\frac{a+b}{ab}\right)^2&>8\\
\left(\frac{c}{a}+\frac{c}{b}\right)^2&>8,
\end{align*}as desired.
[/hide]
[hide=b)]
We know that $a\ne b$ from part a, so WLOG let $a>b$.

[b]Lemma:[/b] $a$ cannot be an integer multiple of $b$.

[i]Proof:[/i] Let $b=qa$ for $q\in \mathbb{Z^+}$. Then, we have
\begin{align*}
a^2+(qa)^2&=c^2\\
(1+q^2)a^2&=c^2.
\end{align*}Since the RHS is a perfect square, the LHS must be such as well. However, $1+q^2$ is not a perfect square because it is bounded between two consecutive squares: $q^2<1+q^2<(q+1)^2$. Thus, $a$ cannot be an integer multiple of $b$.

Now,
\begin{align*}
\left(\frac{c}{a}+\frac{c}{b}\right)^2&=n\\
(a^2+b^2)\left (\frac{a+b}{ab}\right )^2&=n
\end{align*}From the lemma, we know that $b\nmid a$, so $b\nmid a+b$ and $ab\nmid a+b$. Similarly, we have $ab\nmid a^2+b^2$, so $n$ cannot be an integer. Thus, no integer and Pythagorean triple satisfies the given equation.
[/hide]


[size=150][b]Note: ANYONE may hurt and heal, not just the participants. This game is spicy like that.[/b][/size]

[b]Signups were in the other thread, DO NOT add yourself here[/b]

Hurt and Heal. Each post you hurt someone and you heal someone (this decreases and increases their health by 1 point, respectively). When someone reaches 0 HP they die.

Also, I will be here as the ever-loving god to keep rule-breakers in control.

1. You cannot heal yourself.
2. You cannot hurt yourself.
3. You cannot double-post in this thread.
4. Once you hurt and heal, you must recharge (wait) for 1 hour (at least) before hurting & healing again.

I will try starting with 20 HP in this game; if it takes too long (I'm talking about TOW proportions here, don't worry) people's HP will begin to drain.

randomdragoon: 20
#H34N1: 20
bubka: 20
jackdillon: 20
lingomaniac88: 20
junggi: 20
CheeseIsGood: 20
Klebian: 20
InsanelyBored: 20
pianoforte: 20

hurt InsanelyBored, heal CheeseIsGood

randomdragoon: 20
#H34N1: 20
bubka: 20
jackdillon: 20
lingomaniac88: 20
junggi: 20
CheeseIsGood: 21
Klebian: 20
InsanelyBored: 19
pianoforte: 20

hurt anirudh, heal bubka
randomdragoon: 20
#H34N1: 19
bubka: 21
jackdillon: 20
lingomaniac88: 20
junggi: 20
CheeseIsGood: 21
Klebian: 20
InsanelyBored: 19
pianoforte: 20

let's go people, kill anirudh!

hurt anirudh, heal bubka
randomdragoon: 20
#H34N1: 18
bubka: 22
jackdillon: 20
lingomaniac88: 20
junggi: 20
CheeseIsGood: 21
Klebian: 20
InsanelyBored: 19
pianoforte: 20

Hurt pianoforte, heal junggi.

randomdragoon: 20
#H34N1: 18
bubka: 22
jackdillon: 20
lingomaniac88: 20
junggi: 21
CheeseIsGood: 21
Klebian: 20
InsanelyBored: 19
pianoforte: 19

hurt #H34N1, heal CheeseIsGood

randomdragoon: 20
#H34N1: 17
bubka: 22
jackdillon: 20
lingomaniac88: 20
junggi: 21
CheeseIsGood: 22
Klebian: 20
InsanelyBored: 19
pianoforte: 19

Hurt #H34N1, heal InsanelyBored

randomdragoon: 20
#H34N1: 16
bubka: 22
jackdillon: 20
lingomaniac88: 20
junggi: 21
CheeseIsGood: 22
Klebian: 20
InsanelyBored: 20
pianoforte: 19

wait... if someone hurts and heals, does he/she enter the game?

If yes,

1=2: 20

Hurt #H34N1, heal CheeseIsGood

randomdragoon: 20
#H34N1: 15
bubka: 22
jackdillon: 20
lingomaniac88: 20
junggi: 21
CheeseIsGood: 23
Klebian: 20
InsanelyBored: 20
pianoforte: 19

Hurt #H34N1, heal Klebian

randomdragoon: 20
#H34N1: 14
bubka: 22
jackdillon: 20
lingomaniac88: 20
junggi: 21
CheeseIsGood: 23
Klebian: 21
InsanelyBored: 20
pianoforte: 19

hurt anirudh heal lingomaniac

randomdragoon: 20
#H34N1: 13
bubka: 22
jackdillon: 20
lingomaniac88: 21
junggi: 21
CheeseIsGood: 23
Klebian: 21
InsanelyBored: 20
pianoforte: 19

i love you people

Hurt Aniruddh heal junggi
randomdragoon: 20
#H34N1: 12
bubka: 22
jackdillon: 20
lingomaniac88: 21
junggi: 22
CheeseIsGood: 23
Klebian: 21
InsanelyBored: 20
pianoforte: 19

Hur #H34N1 heal pianoforte

randomdragoon: 20
#H34N1: 11
bubka: 22
jackdillon: 20
lingomaniac88: 21
junggi: 22
CheeseIsGood: 23
Klebian: 21
InsanelyBored: 20
pianoforte: 20

Like a pack of wolves...

hurt anirudh heal randomdragoon
randomdragoon: 21
#H34N1: 10
bubka: 22
jackdillon: 20
lingomaniac88: 21
junggi: 22
CheeseIsGood: 23
Klebian: 21
InsanelyBored: 20
pianoforte: 20

Hurt #H34N1, heal InsanelyBored.

randomdragoon: 21
#H34N1: 9
bubka: 22
jackdillon: 20
lingomaniac88: 21
junggi: 22
CheeseIsGood: 23
Klebian: 21
InsanelyBored: 21
pianoforte: 20

Why is everyone teaming against me? :blush:

I dunno. It just feels safer when everyone else is doing it.

Hurt klebian twice, heal junggi

Klebian: 18
junggi: 64

Hurt klebian twice, heal junggi

Klebian: 16
junggi: 65

hurt klebian twice heal junggi.

Klebian: 14
Junggykuh: 66

Hurt Klebian and Heal Junggi

Klebian: 13
Junggi: 67

[quote="now a ranger"]imagenius, physics man, haha1, and haha2, are the same person, obviously according to IP address. And all were posted in a time frame of 4 minutes.  :rotfl:[/quote]

cough cough cough

Hurt klebian twice, heal junggi

Klebian: 11
Junggi: 68

hurt klebian heal junggai HUH YAUH!!!

Klebian: 9
Junggi: 69

Hurt klebian twice, heal a fellow cool korean

Klebian: 7
Junggi: 70 back to 70!

hurt klebian twice heal junggi

Klebian: 5
Junggi: 71

hurt klebian twice, heal junggi

Klebian: 3
Junggi: 72

hurt klebian twice, heal junggi

Klebian: 1
Junggi: 73

[quote="iamagenius"]kill klebian

Junggi: 73

game over[/quote]
whoa, betrayal. nice.  :lol:

:P i was just trying to end the game. let's start a new hurt and heal

And all because no one has character to stick with Klebian, like me.

junggi, I'll have my revenge as well as Klebian. :mad:


Let S be the set of integers from 1 to 2^2009 and D be the sum of the odd divisors of each of the element of S. Find D. Express in the form (a^b +c)/d

this sum is equal to\[ S\equal{}1\plus{}3\plus{}5\plus{}...\plus{}(2^{2008}\minus{}1)\]
\[ \Leftrightarrow S\equal{}2^{2^{2007}}\]
HE HE ....HOW DO YOU FEEL?
 :rotfl:

Hm.

We can "take out all of the odd numbers". The sum of those is $ 1 + 3 + 5 + ... + (2^{2008} - 1) = {2{}^{2007}{}^2}$

Now, divide the remaing numbers by 2. Now take out the even ones. The sum of these is $ 1 + 3 + ... + (2^{2007} - 1) = (2^{2006})^2$

And so on.

Our sum is then $ D = 1 + 2^2 + ... + 2^{5014}$

$ 4D=D+2^{5016}-1$

Thus, $ D=\frac{2^{5016}-1}{3}$

Hey when it says sum of odd divisors, for say, 30, does it want 1+3+5+15, or just 15?


Suppose that the sequence {a_n} converges to a.  Define the sequence {b_n} by
b_n=(a_1+a_2+...+a_n)/n  for every index n.  I need someone to help me prove that
b_n converges to a

[quote="RohanSingh"]write c_n = a_n - a[/quote]
after that u can aplly post 6 in
[url]http://www.mathlinks.ro/Forum/topic-76576.htmlfor%20the%20sequence[/url]
c_n :roll:


So we still have two spots open on the Wootlings team.  If you want to join, send me a PM with your name, nickname, and the individual tests you want to take.  Please only sign up if you are serious about coming.

Incidentally, when I added the latest member, they were labeled a "Waitlisted Student" instead of an "Accepted Student" even though the team has been accepted.  Does anyone know what's going on?

Heh... it's after the deadline now, and all students after the deadline are "waitlisted" and have to pay 5 bucks extra. (It's bad for our team too)

I still don't get it. If a team signs up, doesn't that mean they intend to bring 8 people? This is all just ending up being a pain.


trigonometry
geometry
videos
LaTeX
Pythagorean Theorem
trig identities
Law of Cosines

Does anyone know how to prove the Pythagorean Theorem?

I use it every day but I don't know how it works.

You could use trigonometry to prove it.

[hide="trig proof"] From a well known identity, $ \sin^2\theta\plus{}\cos^2\theta\equal{}1$.
[asy]dot((0, 0));
dot("$\theta$", (0, 2), NW);
dot((3, 0));

draw("$a$", (0, 0)--(0, 2), W);
draw("$b$", (0, 0)--(3, 0));
draw("$c$", (0, 2)--(3, 0), NE);[/asy]
So $ \sin^2\theta\plus{}\cos^2\theta\equal{}1$, substituting-ish, $ \left(\frac{b}{c}\right)^2\plus{}\left(\frac{a}{c}\right)^2\equal{}1\implies\frac{a^2\plus{}b^2}{c^2}\equal{}1\implies a^2\plus{}b^2\equal{}c^2$.
$ Q.E.D.$
[/hide]

[hide="geometric proof"]
[asy]dot((0, 0));
dot((4, 0));
dot((4, 4));
dot((0, 4));
dot((3, 0));
dot((4, 3));
dot((1, 4));
dot((0, 1));

draw((0, 0)--(4, 0));
draw((4, 0)--(4, 4));
draw((4, 4)--(0, 4));
draw((0, 4)--(0, 0));
draw((3, 0)--(4, 3));
draw((4, 3)--(1, 4));
draw((1, 4)--(0, 1));
draw((0, 1)--(3, 0));

label("$a$", (0, 4)--(1, 4), N);
label("$b$", (0, 4)--(0, 1));
label("$c$", (1, 4)--(0, 1), E);[/asy]

The area of the large square is $ (a\plus{}b)^2\equal{}a^2\plus{}2ab\plus{}b^2$. The area of the small square is $ c^2$. Another way to find the area of the small square is to subtract the combined areas of the triangles, which each have area $ \frac{ab}{2}$. There are $ 4$ of them so their combined area is $ 2ab$. Subtracting, we have $ a^2\plus{}2ab\plus{}b^2\minus{}2ab\equal{}c^2\implies a^2\plus{}b^2\equal{}c^2$.

$ Q.E.D.$
[/hide]

In addition to these proofs, there are MANY MANY more. Try to find some of them by yourself!

Thank you. That was really helpful and now I can understand it.

To learn more you may click the link below and go through video lesson on ‘Pythagorean Theorem'.

http://www.winpossible.com/lessons/Geometry_Getting_Started_-_Pythagorean_theorem.html

[quote="RoFlLoLcOpT"]You could use trigonometry to prove it.

From a well known identity, $ \sin^2\theta \plus{} \cos^2\theta \equal{} 1$.[/quote]

You cannot prove pythagorean theorem using this identity, because identity is proved by using pythagorean theorem.

[asy]dot("A", (0,0));
dot("B", (0,3));
dot("C", (4,0));
dot("M", (1.44,1.92));
draw((0,0)--(0,3));
draw((0,0)--(4,0));
draw((0,3)--(4,0));
draw((0,0)--(1.44,1.92));[/asy]
Ok. $ M$ is projection of $ A$ on $ BC$.
$ \angle CAB \cong \angle AMB$
$ \angle ABC \cong \angle MBA$
You get $ \triangle ABC \sim \triangle MBA$
And from that you get $ \frac {CB}{AB} \equal{} \frac {AB}{MB}$ and from that
$ AB^2 \equal{} MB\times BC$
Similarly, you do the same stuff and you get
$ AC^2 \equal{} CM\times CB$
Now add the two equations and you get
$ AB^2 \plus{} AC^2 \equal{} MB\times BC \plus{} CM\times CB$
now since $ CB$ is $ BC$, you get
$ AB^2 \plus{} AC^2 \equal{} MB(BC) \plus{} CM(BC)$
now factoring out $ BC$ gives
$ AB^2 \plus{} AC^2 \equal{} (MB \plus{} CM)(BC)$
Now since $ MB \plus{} CM \equal{} BC$, you get
$ \boxed{AB^2 \plus{} AC^2 \equal{} BC^2}$
$ Q.E.D$ :)

(First time using asymptote. It takes a long time to type. Also, I came up with this proof using Alt. on Hyp. theorems myself. Not that I'm saying I'm the first or anything)

How is $ AB^2 \plus{} AC^2 \equal{} BC^2 \equal{} A^2 \plus{} b^2 \equal{} C^2$.

Or am I just being stupid?

And what is QED? You and RofLoc... whatever... use it all the time.

[url=http://lmgtfy.com/?q=Q.E.D.]google is your friend[/url]

you're being stupid :P jk

This is the pythagorean theorem...

$ \text{leg}_1^2\plus{}\text{leg}_2^2\equal{}\text{hypotenuse}^2$. In this case, $ \text{leg}_1\equal{}AB, \text{leg}_2\equal{}AC, \text{hypotenuse}\equal{}BC$

[quote="muks"][quote]
Ok. M is projection of A on BC.
$ \angle CAB$  $ \cong$ $ \angle AMB$
$ \angle ABC$ $ \cong$ $ \angle MBA$
You get $ \triangle ABC$  $ \cong$ $ \triangle MBA$[/quote]

How can triangle CAB be congruent to AMB?Did you not mean they are similar?[/quote]
Yeah i meant similar sorry $ \text{\LaTeX}$ error thanks for catching that

[geogebra]a5a888ddf7df4fe2a9d9d0d00263958df6f1fb70[/geogebra]

I think this is a good explanation.

oops, I accidentally cut off the equations. they say 5^2+12^2=169 and 169 ^.5 = 13   :oops:

It is a good explantation but it only proves the 5-12-13 triangle.

ummm that 'explanation' doesn't really explain anything. 5-12-13 is a well-known pythagorean triple, but that applet doesn't show anything about the pythagorean theorem other than an example. It doesn't even prove that the triangle is a right triangle.

I'm pretty sure everyone knows the square proof...

When you prove something, you can't use an example. The Pythagorean Theorem must be proved for all numbers $ a, b, c,$ not just certain example lengths.

sorry I thought you were just looking for the example. here is a great NLVM manipulative that explains the Pythagorean theorem:
http://nlvm.usu.edu/en/NAV/frames_asid_164_g_4_t_3.html?open=instructions&from=category_g_4_t_3.html
 :oops:

one question. why cant the theorem $ [sin^2]$+$ [cos^2]$=$ 1$ be a proof of the pythag theorem. i guess the pythag proves that theorem but it works vice versa as well

You [b]can[/b] prove the pythagorean theorem using that trigonomic identity but you have to prove that identity first, without using the pythagroean theorem. It would be hard since a lot of trigonometry is based on the pythag theorem

Wait, isn't there a little animation in the AOPS website that explains the Pythagorean Theorem? It's under all the line of words at the left. I think it explains it pretty clearly.

by the way, its relatively trivial to prove that $ \sin^2x\plus{}\cos^2x\equal{}1$ with the equation of a circle and a unit circle.

People, please. Stop arguing over who's spamming. Then YOU'RE the ones who are spamming.
Back to the Theorem. There's a proof on page 135 of the Introduction to Geometry book (2nd edition). It's sort of like mathboy101's proof, in a way. You don't even need to use sine and cosine (but they are too advanced for this forum, by the way.)

It's circular logic, one of the biggest dangers in geometry.

There are several proofs here [url=http://en.wikipedia.org/wiki/Pythagorean_theorem#Proofs]here[/url].

[hide="random proof(well... not really a proof)"] Plugging 90 in to the law of cosines for the angle gives us c^2=a^2+b^2. Short and sweet, but not really a proof. [/hide]


calculus
function
real analysis
real analysis unsolved

In a problem at chapter 7 of his [i]Calculus[/i] Spivak ask the reader to prove that if a function $ f$ satisfies the conclusion of the Intermediate Value Theorem, and if $ f$ takes on each intermediate value only once, so $ f$ is continuous (sorry for the lack of rigour in the statement, I just repeated Spivak's one).

Well, he gives a nice proof of this in the answer book, but I think I have found a counterexample. It must be wrong, but I can't find out the error. Please help me.

Consider the interval $ [a,b]$. WLOG assume $ a<b$ and $ f(a)<f(b)$. Let $ g$ be a function that is not continuous at any point, and that $ g(x)>f(b)$ for all $ x$. Let $ a<c<b$. Consider the function $ f$ such that

$ f(x)={\frac{f(b)-f(a)}{b-a}}(x-a)+f(a)$ if $ a\le{x}<c$

$ f(x)=g(x)$ if $ c\le{x}<b$

$ f(x)=f(b)$ if $ x=b$

It obeys the Intermediate Value Theorem, as all the values between $ a$ and $ b$ are taken by the "line part" of the function. All the values are taken only once, since $ g(x)>f(b)$. But if we take any point in $ [c,b)$ the function is not continuous at this point.  :(

That's not a counterexample. Choose some $ p\in (c,b)$; the value $ f(b)$ is not attained on $ [a,c]$.


please help. can somebody explain the shoelace theorem to me??


abstract algebra
group theory
superior algebra
superior algebra unsolved

A commutator in a group is any element $ [x, y]\equal{}xyx^{\minus{}1}y^{\minus{}1}$ for $ x, y \in G$. If $ K$ is subgroup of $ G$, prove $ K$ contains all the commutators of $ G$ iff $ K \triangleleft G$ and $ G/K$ is abelian.
Attempt
($ \Rightarrow$) $ K \triangleleft G$ is trivial. To show $ G/K$ is abelian, take $ g_1 \plus{}K$ and $ g_2\plus{}K$ and show they commute, how do I do this?
($ \Leftarrow$) This is the harder direction. I don't see how to prove this way.

Thanks for any help.

Try writing multiplicatively, since you wrote the commutator that way.

Suppose $ K\triangleleft G$ and $ G/K$ is abelian. Let $ x, y\in G$.

Claim: $ xyx^{\minus{}1}y^{\minus{}1}\in K$.

Well, $ (xK)(yK)\equal{}(yK)(xK)$ since the quotient is commutative. So $ xyK\equal{}yxK$. But this means $ x^{\minus{}1}y^{\minus{}1}xyK\equal{}K$. Thus $ x^{\minus{}1}y^{\minus{}1}xy\in K$. Oops. I got it backwards, so replace x and y with $ x^{\minus{}1}$ and $ y^{\minus{}1}$ respectively.

So $ K$ contains all commutators.


function
floor function
SFFT
algebra
polynomial
rotation
analytic geometry

Welcome to DMAT, a new intermediate forum competition.

I am not going to explain to much because you can read all about the rules, prizes, problems, points, etc . . . in the attached pdf, but, I do want to point out our (I and my co-writer of the competition) goals.

(1) We wish to hone our problem solving and creating skills via the our writing of these questions and solving of them.

(2) By creating this friendly competition, we wish that everyone will take pride in, and have fun doing these questions over the summer holidays and continue to do them on into the school year.

The first two questions count for points, but, they are pretty easy because we are taking this first week as sort of a practice round.  Be sure to read the attachment!

Here you go . . .

Hello, everybody, I'm the other guy. Since we began somewhat later than anticipated, let's just put Monday and Tuesday's questions together. Trust me, they aren't that hard (well not the first one at least).

[b]1-A.[/b] (2 pts) Find the product of the four smallest prime factors of $ 62^{32} \minus{} 29^{32}$.

[b]1-B.[/b] (6 pts) Consider the following functions:
$ f(x \minus{} y) \equal{} g(x)g(y) \plus{} f(x)f(y)$
$ g(x \minus{} y) \equal{} g(x)f(y) \minus{} f(x)g(4)$

Given $ f( \minus{} 4) \equal{} 15$ and $ g(4)$ is a non-zero real, compute the numerical value of $ \left(f(2)\right)^{2} \plus{} \left(g(2)\right)^{2}$. Partial credit will be awarded to those that submit nontrivial statements (for example, equalities which are useful in solving the problem).

[b]Please submit answers to gfour84 or Caelestor by 12:01 A.M. EDT, Thursday 7/9 (9:01 P.M. PDT, Wednesday 7/8)[/b]

Platinum: darkmage2009
Gold: sj0201
Silver: zserf, narik
Bronze: cyanredyellow

Hello, a reminder that answers to the first 2 problems are due in about 24 hours. Since quite a few have already solved these questions, you may continue on and solve the next problem.

[b]1-C.[/b] (4 pts) How many integers between 1 and 1000 inclusive do not satisfy $ x\minus{}\lfloor\frac{x}{3}\rfloor \equal{}\lfloor\frac{3x}{4}\rfloor\minus{}\lfloor\frac{x}{12}\rfloor$

Please feel free to discuss the DMAT on this thread!

Hello everybody, let's take a look at the scorings so far.

[hide="1-A"]
Scoring Rubric: 1 point awarded for 3 correct prime factors; 2 points awarded for all correct prime factors. [hide="Solution:"]
Yes, it's just factoring of squares: $ (62^{16} \plus{} 29^{16})(62^8 \plus{} 29^8)(62^4 \plus{} 29^4)(62^2 \plus{} 29^2)(62 \plus{} 29)(62 \minus{} 29)$.

We notice $ 91 \equal{} 7*13$ and $ 33 \equal{} 11*3$ are factors.
[hide="Trick Answer:"]
$ 3*7*11*13 \equal{} 3003$. Did you forget some prime factors?
[/hide]
[hide="Correct Answer:"]
$ 3*5*7*11 \equal{} 1155$. Also note that $ 5|(62^2 \plus{} 29^2)$.
Note: this is not mean at all; you should've expected it.
[/hide]

[/hide]
[/hide]
[b]1-B Announcement[/b]
Apparently there's a lot of confusion (in fact, I realized a typo, so sorry about that), so I've decided to extend the deadline for this problem by two days. Try it again:

Consider the following equations:
$ f(x \minus{} y) \equal{} g(x)g(y) \plus{} f(x)f(y)$, where $ f(\minus{}4)\equal{}15$
$ g(x \minus{} y) \equal{} g(x)f(y) \minus{} f(x)g(4)$, which is not defined when $ x\equal{}y\equal{}4$

If $ g(4)$ is a nonzero real, compute the numerical value of $ \left(f(2)\right)^{2} \plus{} \left(g(2)\right)^{2}$. [b]Now due 12:01 A.M. EDT Saturday 7/11 (9:01 P.M. PDT Friday 7/10).[/b]

[hide="Current Scores"]
abcak: +1
Bugi: +2
Brut3Forc3: +2
cyanredyellow: +1
mercenary90: +2
narik: +1

[/hide]
Question 1-D to come soon.

[b]1-D.[/b] (4 pts) There exist quite a few positive integers m and n such that $ \frac {2}{m} \plus{} \frac {3}{n} \equal{} \frac {1}{16}$. What is the sum of all possible odd values of n?

[b]Announcement:[/b] A typo in 1-B has been fixed. My sincerest apologies.

Hello, this is a reminder that the following problem is due in about 9.5 hours.

[b]1-C.[/b] How many integers between 1 and 1000 inclusive do not satisfy $ x\minus{}\lfloor\frac{x}{3}\rfloor \equal{}\lfloor\frac{3x}{4}\rfloor\minus{}\lfloor\frac{x}{12}\rfloor$?

Upcoming: Tomorrow's problem is a simple proof. You will get the whole weekend to write it up.

[b]Submissions for 1-C have closed.[/b]

[hide="1-C"]
Submissions: 2

[b]Solution, No tricks today:[/b]
Assume the equation can be represented by $ f(x) \equal{} x \minus{} \lfloor\frac {x}{3}\rfloor \minus{} \lfloor\frac {3x}{4}\rfloor \plus{} \lfloor\frac {x}{12}\rfloor$.
Thus, $ f(x \plus{} 12) \equal{} x \plus{} 12 \minus{} \lfloor\frac {x \plus{} 12}{3}\rfloor \minus{} \lfloor\frac {3(x \plus{} 12)}{4}\rfloor \plus{} \lfloor\frac {x \plus{} 12}{12}\rfloor \longrightarrow$
$ x \plus{} 12 \minus{} \lfloor\frac {x}{3}\rfloor \minus{} 4 \minus{} \lfloor\frac {3x}{4}\rfloor \minus{} 9 \plus{} \lfloor\frac {x}{12}\rfloor \plus{} 1 \equal{} f(x)$.

This function has a period of 12; there are 83 groups of 12 integers in 1000, with 4 extra integers. We need to find values of x such that $ f(x) \not \equal{} 0$. All we have to do is consider values between 1 and 12. 1, 2, 5, 13, 14, 17, ..., 997, 998 do not work, so the answer is $ 83*3 \plus{} 2 \equal{} \boxed{251}$.

EDIT: Thanks to narik for pointing out a typo. Someone must be jealous of you to call you a nub. :rotfl:

[b]Rubric:[/b]
4 points for the correct answer, otherwise:
3 pts for proving the periodicity
2 pts for noticing the full pattern
1 pt for noticing a partial pattern
[/hide]

[hide="Scoring"]
Brut3Forc3: +4
narik: +1 ("Someone who's awesomer than narik" asked me to call you a nub. Not sure why.)
[/hide]

[b]Problems due Tomorrow: 1-B, 1-D[/b] (look back at previous posts).

1-E, which serves as the proof for this round (every round's problem E is a proof), will be posted later. You will have the entire weekend to write up a solution.

Sorry for the delay, a particularly big spider distracted me. Let's take a break from the usual type of problems!

[b]1-E.[/b] (6 pts) Two circles intersect at $ R$ and $ S$. A tangent line lying closer to $ R$ touches Circle 1 at $ M$ and Circle 2 at $ N$. Point $ T$ lies on Circle 2 such that segment $ MT$ passes through $ R$. Prove $ NS$ bisects $ \angle MST$.

Yeah I was nubbish for thinking that there were 4 per 12 opposed to 3 per 12. T__T.

But yeah, he's definitely jealous of my awesomeness. >:D

Hello, the astonishing pace of some participants in solving these problems has led gfour84 and I to wonder: should we take a break from posting problems this weekend or just continue straight on and end this round two days early? (Too bad he's busy with something, so I have to speak for him a lot.)

[b]Submissions for 1-B & 1-D have closed.[/b]

[hide="1-D"]
Submissions: 1 (I'm surprised, it's the second easiest question so far) :huh:

[b]Solution:[/b]
$ 32n \plus{} 48m \equal{} mn \longrightarrow mn \minus{} 48m \minus{} 32n \equal{} 0 \longrightarrow (m \minus{} 32)(n \minus{} 48) \equal{} 1536 \equal{} 2^9*3$.
It is now obvious that there are only 2 possible odd factors of 1536: 1 and 3. Thus n is $ 48 \plus{} 1 \equal{} 49$ or $ 48 \plus{} 3 \equal{} 51$, and the sum of those values is $ \boxed{100}$.

[b]Rubric:[/b]
4 points for the correct answer, otherwise:
2 pts for SFFT (+1 for correct prime factorization)
[/hide]

[hide="1-B"]
There exist multiple issues with the problem as pointed out by various people, so 1-B' will replace it if you couldn't solve 1-B. Don't expect 1-B' to be put up immediately; I'm busy tonight (and gfour84's internet is broken).
[/hide]

[hide="Scoring"]
Brut3Forc3: +4
[/hide]

[b]No Problems due Tomorrow. Work on 1-B', 1-E[/b] (look back at previous posts).

[b]1-B'.[/b] (6 pts) A polynomial $ P$ satisfies $ P(8) \equal{} 144$, and the following expression is true for all $ x\not \equal{} 0, \frac {1}2$:

$ \frac {8P(x^2 \plus{} 2)}{P(4x)} \equal{} 1 \plus{} \frac {x^3 \plus{} 1}{2x \minus{} 1}$

Evaluate $ P(10)$.

Hello, problems 1-B' and 1-E are due in about 4 hours. If you haven't submitted solutions, please do so quickly!

If you're bored, try this [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=286054]problem.[/url] 1-F will come later tonight.

[b]1-F[/b] (5 pts) Before gfour84 created this thrilling competition, Billie Jean used to play games with his gridboard, which consists of integer points such that $ 1\le x, y \le 10$. In one such game, Billie Jean's marker started at $ (1,1)$, facing $ (1,2)$. e rolls a number n on a non-rigged 8 sided die containing integer values between 0 and 7. The ball rotates $ \pi/4$ clockwise radians and moves in that direction towards the first point with integer coordinates. If that point lied outside the bounds of the grid, the ball was removed and its complete path up to the last point was measured. Otherwise, Billie Jean continued to roll numbers and move the marker. To beat the game, the path of the ball must form the shape of an M. This M must have two parallel segments of equal length, each forming a 45 degree angle with either one of two segments that are not only perpendicular to each other but also of equal length (but not necessarily equal to that of the parallel ones). For example, the path $ (1,1), (2,2), (2,1), (3,2), (3,1)$ does not form an acceptable M. The probabibility that Billie Jean beat it is equal to $ j(\frac {1}{8})^{k}(l*8^{7m} \plus{} 2l*8^{5m} \plus{} 3l*8^{3m} \plus{} 4l*8^{m} \plus{} \frac {l}{n})$. Given all variables are distinct positive integers, calculate $ j \plus{} k \plus{} l \plus{} m \plus{} n$.

[b]1-F[/b] (5 pts) Before gfour84 created this thrilling competition, Billie Jean used to play games with his gridboard, which consists of integer points such that $ 1\le x, y \le 10$. In one such game, Billie Jean's marker started at $ (1,1)$, facing $ (1,2)$. He rolls a number n on a non-rigged 8 sided die containing integer values between 0 and 7. The marker rotates $ n*\pi/4$ radians clockwise and proceeds in that direction, stopping at the first point with integer coordinates along the way. If that point lies outside the bounds of the grid, the marker is removed and its complete path up to the last point inside the grid is measured. Otherwise, Billie Jean continues to roll numbers and move the marker. To beat the game, the path of the ball must form the shape of an M. This M must have two parallel segments of equal length, each forming a 45 degree angle with either one of two segments that are not only perpendicular to each other but also of equal length (but not necessarily equal to that of the parallel ones). For example, the path $ (1,1), (2,2), (2,1), (3,2), (3,1)$ does not form an acceptable M. The probabibility that Billie Jean beat it is equal to $ a(\frac {1}{8})^{b}((8^{c - 3} + d*8^{5e}) + 2(8^{c - 1} + d*8^{4e}) + 3(8^{c + 1} + d*8^{3e}) + 4({8^{c + 3} + d*8^{2e}))}$. Given all variables are distinct positive integers, calculate $ a + b + c + d + e$.

[b]Submissions for 1-B' and 1-E are now closed.[/b] Scoring update will be available later.

Is the $ n$ in the final answer different from the $ n$ that he rolls?

[b]Update: Look at 1-F again, it has been revised.[/b]

[hide="1-B prime"]

Submissions: 1 (Guess who)

[b]Solution:[/b]

Combine the right side, then multiply out to get $ P(x^2 \plus{} 2)(16x \minus{} 8) \equal{} P(4x)(x^3 \plus{} 2x)$. If $ P$ has degree $ n$, then $ 2n \plus{} 1 \equal{} n \plus{} 3\iff n \equal{} 2$, so $ P$ is a quadratic. Now,
$ \frac {P(x^2 \plus{} 2)}{P(4x)} \equal{} \frac {1}8 \plus{} \frac {x^3 \plus{} 1}{8(2x \minus{} 1)} \equal{} \frac {(2x \minus{} 1) \plus{} x^3 \plus{} 1}{8(2x \minus{} 1)} \equal{} \frac {x(x^2 \plus{} 2)}{4(4x \minus{} 2)} \equal{} \frac {x^2(x^2 \plus{} 2)}{4x(4x \minus{} 2)}$

$ P$ can now easily be seen as $ n*(x)(x \minus{} 2)$. $ P(8) \equal{} 144 \equal{} n*48 \longrightarrow n \equal{} 3 \longrightarrow P(10) \equal{} 3(10)(8) \equal{} \boxed{240}$
[/hide]

[hide="1-E"]
Submissions: 4

[b]Solution:[/b]
$ \angle NST \equal{} \angle NRT \equal{} \angle MNR \plus{} \angle RNM$ since $ \angle NRM \plus{} \angle NRT \equal{} 180. (1)$
$ \angle NSR \equal{} \angle MNR$ since $ MN$ is a tangent line to Circle 2, which contains the point $ S$.
$ \angle MSR \equal{} \angle RMN$ since $ MN$ is a tangent line to Circle 1, which contains $ S$ as well.
Therefore, summing both sides of equations, we get $ \angle MSR \plus{} \angle NSR \equal{} \angle MNR \plus{} \angle RMN \equal{} \angle NRT$ because of $ (1)$.
So, $ \angle MSN \equal{} \angle NRT$, and thus $ \angle NS$ bisects $ \angle MST$ (Q.E.D)
[/hide]

[hide="Scoring"]
Brut3Forc3 + 12
Bugi +6
ghjk +6
sjcamath + 6
[/hide]

[hide="Scoreboard"]
abcak: 1 (0/1)
Bugi: 8 (2/2)
Brut3Forc3: 22 (5/5)
cyanredyellow: 1 (0/1)
mercenary90: 2 (1/1)
narik: 2 (0/2)
ghjk: 6 (1/1)
sjcamath: 6 (1/1)
[/hide]

If you would like to participate in DMAT Round 2, please be sure to inform gfour84 or Caelestor prior to its start on 7/19 (we're trying to be more organized).

[hide]

typo in line 1 of solution for 1E: I think it should be:

angle NRT = angle RMN + angle RNM.

the way you have it now states that angle NRT = 2 angle RNM.[/hide]

Um, nevermind. I see it now. However, your proof is still unclear. I'm not quite sure what you meant, so
is this what you're trying to say? :

[hide]

0.5 angle RSN = 0.5 angle RNM because they are both half the same arc, thus they are equal.

(same logic for NMR and MSR).[/hide]

[b]1-G.[/b] (5 pts) Compute: $ {\sum_{n \equal{} 2}^{\infty}\ \frac {2^{n \plus{} 1}\cdot n^{2} \plus{} 2n\cdot 2^{n \plus{} 1} \plus{} 2^{n \plus{} 1} \minus{} 2^{n}(n^{2})}{2^{2n}\cdot (n^{4} \plus{} 2n^{3} \plus{} n^{2})}}$

Also check out [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=288549]Round 2.[/url]

EDIT: Clarified, thanks to Bugi.

Well, I guess I can substitute that for a more straightforward problem. Solve either one to get a correct question in the score tally. You get bonus points for completing both problems.

[b]1-F'[/b]. (6 pts) Tomorrow happens to be both Jude and Jerry's birthday! Millinova decides to invite them and 13 other friends to a fantabulous birthday party. The round table at the party contains seats with numbers 1-16, arranged clockwise. Jude and Jerry sit together, and Millinova sits next to one of them. A group of three adjacent seats contains gfour84, Rolloway, and Caelestor (though not necessarily in that order). Cyleura sits across the table from Caelestor. There are a total of $ n*9!$ possible distinct arrangements of people sitting at the table (two arrangements are distinct if one person is not sitting in the same-numbered seat). Calculate n.

This problem's due date is the same as 1-G. The original 1-F is now also 6 pts too.

[quote="Caelestor"][b]1-G.[/b] (5 pts) Compute: $ {\sum_{k \equal{} 2}^{\infty}\ \frac {2^{n \plus{} 1}\cdot n^{2} \plus{} 2n\cdot 2^{n \plus{} 1} \plus{} 2^{n \plus{} 1} \minus{} 2^{n}(n^{2})}{2^{2n}\cdot (n^{4} \plus{} 2n^{3} \plus{} n^{2})}}$

Also check out [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=288549]Round 2.[/url][/quote]

You probably meant n=2 in sum :)

[quote="Caelestor"]
[hide="1-B prime"]

Submissions: 1 (Guess who)

[b]Solution:[/b]

Combine the right side, then multiply out to get $ P(x^2 \plus{} 2)(16x \minus{} 8) \equal{} P(4x)(x^3 \plus{} 2x)$. If $ P$ has degree $ n$, then $ 2n \plus{} 1 \equal{} n \plus{} 3\iff n \equal{} 2$, so $ P$ is a quadratic. Now,
$ \frac {P(x^2 \plus{} 2)}{P(4x)} \equal{} \frac {1}8 \plus{} \frac {x^3 \plus{} 1}{8(2x \minus{} 1)} \equal{} \frac {(2x \minus{} 1) \plus{} x^3 \plus{} 1}{8(2x \minus{} 1)} \equal{} \frac {x(x^2 \plus{} 2)}{4(4x \minus{} 2)} \equal{} \frac {x^2(x^2 \plus{} 2)}{4x(4x \minus{} 2)}$

$ P$ can now easily be seen as $ n*(x)(x \minus{} 2)$. $ P(8) \equal{} 144 \equal{} n*48 \longrightarrow n \equal{} 3 \longrightarrow P(10) \equal{} 3(10)(8) \equal{} \boxed{240}$
[/hide]

[/quote]
I don't think this is completely rigorous because the solution has not proved $ P(10)$ is unique (such that there might be another P(x) that satisfies all the conditions but has a different P(10))...

(Also why did you guys cancel the original 1-B? What's wrong with that problem?)

@mathwizard:

If you can find another P(10), I'd be glad to accept it.

Here was the original solution to [hide="1-B:"]

It's easy to see $ f(2\minus{}2)\equal{}g(2)^2\plus{}f(2)^2$.
Now note that $ g(4\minus{}0)\equal{}g(4)\equal{}g(4)f(0)\minus{}f(4)g(4) \longrightarrow 1\equal{}f(0)\minus{}f(4)$
$ f(4)\equal{}\minus{}f(4)\equal{}15$ since f is an even function (doesn't that look like the difference of cosines)?
Thus, $ 1\plus{}15\equal{}16\equal{}f(0)\equal{}g(2)^2\plus{}f(2)^2$.

Unfortunately, many people exploited the fact that if $ x\equal{}y\equal{}4, g(0)\equal{}0$, which is not what we wanted.

[/hide]

Good to see active discussion on this forum. gfour needs to talk more though.

We did mean $ n\equal{}2$.  In regards to that 1-B' solution, I did not guess the value of $ P(x)$, but, rather, when I was discussing the question with Caelestor created a system which only led to one function.  So, I am thinking that it is unique (although, I have no proof-proof. )

You know it's quadratic, and you can easily find 3 fixed values. (I found P(8), P(6), P(-8).) Therefore, it's unique.

[quote="Caelestor"]Unfortunately, many people exploited the fact that if $ x \equal{} y \equal{} 4, g(0) \equal{} 0$, which is not what we wanted.

[/quote]
I see; actually it can be easily brute-forced by solving the coefficients once we know it's a quadratic. :lol:
Regarding the original problem, I thought it said it's undefined for $ x\equal{}y\equal{}4$; also why can't g(0)=0 anyways?

[quote="mathwizarddude"][quote="Caelestor"]Unfortunately, many people exploited the fact that if $ x \equal{} y \equal{} 4, g(0) \equal{} 0$, which is not what we wanted.

[/quote]
I see; actually it can be easily brute-forced by solving the coefficients once we know it's a quadratic. :lol:
Regarding the original problem, I thought it said it's undefined for $ x \equal{} y \equal{} 4$; also why can't g(0)=0 anyways?[/quote]

Also, it doesn't work if $ x \equal{} y \equal{} \minus{} 4$. By then, editing it was a pain (and nobody got it right). Hopefully, no one will submit answers to the original 1-F (that would create an imbalance).

[b]And just some reminders: 1-F' and 1-G are due in about 26 hours. 1-H will come later tonight. And be sure to sign up for Round 2 (if you want a medal or the 1337 award, you must).[/b]

[b]1-H.[/b] (4 pts) Positive real numbers $ g, f, o, u, r$ satisfy $ \frac {g}3 \plus{} o \plus{} 2f \plus{} 6u \plus{} 7r \equal{} 20$. Maximizing the product $ gfour$ gives the product $ m/n$, where m and n are relatively prime integers. Find $ m \plus{} n$. Note: If the product is an integer x, then $ m \equal{} x$ and $ n \equal{} 1$.

[size=59]No extra credit for anybody today.  :P [/size]

1-F' and 1-G are due tonight at the usual deadline (midnight eastern).

Also, please feel free to give some feedback as this round is winding down.

Yea guys.  And, if you would PM us both your solutions, it might be easier on us :) .

[b]1-I.[/b] (6 pts) Let $ a_0 \equal{} \cos{\frac {\pi}{2010}} \plus{} i\sin{\frac {\pi}{2010}}$ and for all positive integers $ n, a_n \equal{} (a_{n \minus{} 1})^{\frac {13n \plus{} 2}{n \plus{} 1}}$. What is the smallest n that makes $ a_n$ both positive and real?

I-F' and 1-G are now closed. We'll post solutions for them if somebody actually wants me to (not many submissions for these two). Besides, I'm busy tonight.

[hide="Scoring"]
Brut3Forc3: +11
[/hide]

[b] Question 1-H submissions are closed.

1-J. Last problem![/b] (7 pts) The statement "$ n^8 - 1$ is a multiple of 35" is true for some integers n between 2 and 1001 inclusive. How many such integers are there?

[hide="Scoring"]
Brut3Forc3: +4
ghjk: +4 (right on time!)

[/hide]

[hide="1-H"]By AM-GM,
${ 4=\dfrac{\dfrac{g}{3}+2f+o+6u+7r}{5}\geq }\sqrt[5]{28gfour}$, or$ \frac{4^5}{28}=\frac{256}{7}\geq gfour$, so $ m+n=\boxed{263}$.[/hide]

gfour84 and I will work on making Round 2 problems tomorrow.

Hello all, the problems will now start posting [url=http://www.artofproblemsolving.com/Forum/weblog.php?w=1597]here[/url]. According to Sunehra, now it won't be pushed down.

Meanwhile, Round 1 is almost over! (And Round 2 will start!)

Go to my blog (see signature), I'll update the scoring.

[quote="Caelestor"][b]1-F'[/b]. (6 pts) Tomorrow happens to be both Jude and Jerry's birthday! Millinova decides to invite them and 13 other friends to a fantabulous birthday party. The round table at the party contains seats with numbers 1-16, arranged clockwise. Jude and Jerry sit together, and Millinova sits next to one of them. A group of three adjacent seats contains gfour84, Rolloway, and Caelestor (though not necessarily in that order). Cyleura sits across the table from Caelestor. There are a total of $ n*9!$ possible distinct arrangements of people sitting at the table (two arrangements are distinct if one person is not sitting in the same-numbered seat). Calculate n.[/quote]
If we assign the seats numbered $ 1,2,3,...,16$ and we fix Caelestor to seat $ 1$, then Cyleura must sit in seat $ 9$. Rolloway and gfour may sit in $ 2,3$ or $ 2,16$ (we do not count $ 16,15$ because it's symmetric to $ 2,3$)

CASE 1: the two sit in $ 2,3$ Then between $ 3$ and $ 9$ there are $ 5$ seats exclusively. If Millinova, Jude, Jerry sit in $ [4,8]\equal{}[1',5']$, then for the case Jude, Jerry sit in $ [2',3'],[3',4']$ there are $ 2\cdot2\cdot2$ possible arrangements in total. If Jude, Jerry sit in $ [1',2'],[4',5']$ then there are $ 2\cdot2$ ways in total. So for this subcase we have $ \boxed{2(2\cdot2\cdot2\plus{}2\cdot2)\cdot9!}$ (the 2 outside the parenthesis is for Rolloways and gfour sitting at $ 2,3$)
If Jude,Jerry,Millinova sit in $ [10,16]\equal{}[1',7']$, and for Jude, Jerry sitting in $ [2',3'],[3',4'],[4',5'],[5',6']$ there are $ 4\cdot2\cdot2$ ways; if Jude, jerry sit in $ [1',2'],[6',7']$ then there are $ 2\cdot2$ ways. So for this subcase we have $ \boxed{2(4\cdot2\cdot2\plus{}2\cdot2)\cdot9!}$

CASE 2: the two sit in $ 2,16$ (note that we only count one way for the two sit in the two seats because if we count two, then we have to divide by 2 because one of those is the mirror to the other one) Then between $ 3$ and $ 8$ there are $ 6$ seats inclusively. If Millinova, Jude, Jerry sit in $ [3,8]\equal{}[1',6']$, then for the case Jude, Jerry sit in $ [2',3'],[3',4'],[4',5']$ there are $ 3\cdot2\cdot2$ ways. If Jude, Jerry sit in $ [1',2'].[5',6']$ there are $ 2\cdot2$ ways. Note that if Jude,Jerry,Millinova sit in $ [10,15]$ then the number of ways is exactly the same as the three in $ [3,8]$. So the total number of ways for Case 2 is $ \boxed{2(3\cdot2\cdot2\plus{}2\cdot2)\cdot9!}$

Adding we get $ 82\cdot9!$ but this does not agree with the official answer...

I had some trouble at first too...

I think the problem is that you can't fix Caelestor to seat 1. Each placement of Caelestor counts as a different permutation, that's why he multiplied by 16.

First of all, it is not given Caelestor is necessarily in seat 1. So multiply by the final answer by 16.

Furthermore, $ 2(12\plus{}4\plus{}16\plus{}4\plus{}8\plus{}4)\equal{}96$, so please check that.

It's late at night and I'm having trouble following your reasoning (It looks like you're either overthinking or leaving out some combinations though). I'll respond to you tomorrow, or post a comment on the blogx so Brut3Forc3 can read it).

Yep you are right it sums to $ 96$ (I got too many parenthesis on the paper and I forgot to distribute the second terms :( ) plus when i did the problem it was alread 11pm - right now it's 1 AM!!!!)

I think we can fix Caelestor to sit 1 because I thought the problem said it's counted the same for rotations and reflections (if I didn't misread the problem, which is possible because English was not used to be my native language)...

EDIT: I just looked at the official solution (from Brut3forc3???) and it seems he (and the problem) counted rotations and reflections, in which case it would be $ 96\cdot16\cdot2 \equal{} 3072$... :) ... and mystery SOLVED!!! :D


${ \text {A square matrix is said to be orthogonal if } QQ^T = I ,}$
$ Q^T \text { is the transpose matrix of Q , I is identity matrix.}$

 $ \text{Suppose that A,B are two nonsingular square matrices and }A^TA = B^TB.$

 $ \text{Show that there exists an orthogonal matrix Q such that A = QB.}$

So you have to prove that $ AB^{\minus{}1}$ is orthogonal. Do you know how orthogonality is defined? An idea how to derive it from $ A^TA \equal{} B^TB$ ?

  darij


Two points determine one line and three noncollinear points determine three lines. How many lines are determined by  12  points, no three of them are collinear?

a line segment is 2 connected points. If no 3 are collinear, you need to chose 2 points form 12 points which is 12*11/2 (sorry my latex isnt good) which is 66

i don't really get why you are dividing by two   :maybe:

Consider if we label the points 1, 2, 3, 4, ... 12.

Then the possible combinations are formed by choosing two points from the above points. If we set "1" as point #1, there are 11 other points we can choose to be point #2 and thus form a line. The same can be said of the other 11 points, so we multiply 12 by 11 to get 132.

Notice, however, that we overcounted. Surely, for example, drawing a line from "1" to "2" is the same as the line from "2" to "1", isn't it? That's why we divide by 2. To get rid of the duplicates.

In general, if the order matters (e.g. "1"-"2" is not the same as "2"-"1"), then 132 is the right answer (if the lines were rays, for example). This is known as [i]permutations[/i]. The general formula for a permutation of choosing $ r$ elements from $ n$ elements (like 2 points from 12 points) is $ \frac {n!}{(n \minus{} r)!}$, or in other words, $ n(n \minus{} 1)(n \minus{} 2)\dots(n \minus{} r \plus{} 1)$. So if $ r$ was 2 and $ n$ was 12 (like in the problem), we have $ \frac {12!}{(12 \minus{} 2)!} \equal{} 12(12 \minus{} 1) \equal{} 132$.

However, as you may have noticed, the lines are not rays, so "1"-"2" is the same as "2"-"1". For every pair "x"-"y", there is another "y"-"x" that must be eliminated. So we just divide by 2 (in this case, as we were choosing two points) to get $ 66$, the desired answer.

Now, watch out, because if we were to choose three points, we don't divide by 3, but rather by 6. This is because we are dividing by the number of permutations of duplicates, so if we had 123 and that was the same as 132, 213, 231, 312, 321, we have to divide by 6 to get rid of all those duplicates.

In my opinion, counting and probability is the hardest subject of all MATHCOUNTS subjects because it is the most "abstract". I once had trouble with this kind of stuff and still have trouble with counting and probability! :dry:

Well you *are* in 5th grade, right? Three years to catch up! :D

NOPE, GOING TO SIXTH GRADE! i suck don't i?

I didn't really know about real math competitions at all until I got into 6th grade...

But I know that I probably couldn't have solved that in 6th grade because I sucked...
[hide="Proof"]
6th grade-19th at chapter  :o  :cursing: (albeit, there were many factors other than math that affected that, but still...)
This year-3rd at chapter, 5th at states, 1st state countdown :wink: [/hide]

Hint: You can improve a lot...

i live in florida  :D

thanks for the encouragement  :)


Perfect Squares
perfect cube
number theory
Perfect Powers
Subset
Sum

Show that there is a set of $2002$ distinct positive integers such that the sum of one or more elements of the set is never a square, cube, or higher power.

let $p$ one prime with $p \ge 1001.2003$.
let $S = (p, 2p, 3p, ... , 2002p)$.
all sums of the subsets of $S$ are in the form $pk$, with $k \leq (1+2+..+2002) = 1001.2003$.
so, $k$ isn´t divisible by $p$, and problem is solved. (the sums aren't perfect powers)

Since the [url=https://en.wikipedia.org/wiki/Natural_density]asymptotic density[/url] of the set of perfect powers is $0$, there are infinitely many translates of any finite set of positive integers which don't contain any perfect power, and so our $2002$ numbers can be generated inductively.

Choose a prime $p \geq 6942069$. Let the set be $\{p,2p, \dots, 2002p\}$. For any sum involving the numbers in this set, $\nu_p = 1$ since $p$ is big.


Euler
group theory
abstract algebra
number theory
relatively prime
superior algebra
superior algebra solved

Where phi is the Euler phi function.  Can someone check if this is valid, and then shoot me if it isn't.?  Also, is there an easier way of doing it?

$\mbox{Proof: Since }d | n \mbox{, }n=kd \mbox{ for some }k \epsilon Z$
$\mbox{Let }d=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}}\mbox{ for some }s \epsilon Z \mbox{ where }p_{t}\mbox{ is prime for all }1 \leq t \leq s$
$\mbox{Then }\varphi(d) = p_{1}^{\alpha_{1}-1}(p_{1}-1)p_{2}^{\alpha_{2}-1}(p_{2}-1) \ldots p_{s}^{\alpha_{s}-1}(p_{s}-1)$
$\mbox{Let }l = k*\Pi_{t=1}^{s}\frac{1}{p_{t}^{m_{t}}}\mbox{ where }m_{t}\mbox{ is the maimum integer such that }p_{t}^{m_{t}}| k$
$\mbox{So }n = p_{1}^{\alpha_{1}+m_{1}}p_{2}^{\alpha_{2}+m_{2}}\ldots p_{s}^{\alpha_{s}+m_{s}}*l \mbox{ and }l \mbox{ is relatively prime to }p_{t}^{\alpha_{t}+m_{t}}\mbox{ for }1 \leq t \leq s$
$\mbox{So }\varphi(n) = \varphi(p_{1}^{\alpha_{1}+m_{1}}p_{2}^{\alpha_{2}+m_{2}}\ldots p_{s}^{\alpha_{s}+m_{s}}*l) = \varphi(p_{1}^{\alpha_{1}+m_{1}})\varphi(p_{2}^{\alpha_{2}+m_{2}})\ldots \varphi(p_{s}^{\alpha_{s}+m_{s}})\varphi(l)$
$= p_{1}^{a_{1}+m_{1}-1}(p_{1}-1)p_{2}^{a_{2}+m_{2}-1}(p_{2}-1)\ldots p_{s}^{a_{s}+m_{s}-1}(p_{s}-1)\varphi(l)$
$= (p_{1}^{m_{1}}p_{2}^{m_{2}}\ldots p_{s}^{m_{s}})(p_{1}^{\alpha_{1}-1}(p_{1}-1)p_{2}^{\alpha_{2}-1}(p_{2}-1) \ldots p_{s}^{\alpha_{s}-1}(p_{s}-1))\varphi(l) = (p_{1}^{m_{1}}p_{2}^{m_{2}}\ldots p_{s}^{m_{s}})\varphi(d)\varphi(l)$

$\mbox{Therefore, }\varphi(d) | \varphi(n)$

For an easy proof, remark that the ring $\mathbb{Z}/d$ can be embedded in  the ring $\mathbb{Z}/n$, hence also their groups of units.

[quote="Ricky"]Where phi is the Euler phi function.  Can someone check if this is valid, and then shoot me if it isn't.?.....  [/quote]

It's ok. Not the easiest way, but a correct way.

-oo-, I understand now that phi(n) is the number of units in Z/nZ, but I don't see why if d | n, that the number of units in Z/dZ divides the number of units in Z/nZ.

(Z/d)* is isomorphic to a subgroup of (Z/n)*, so that the order of (Z/d)* divides the order of (Z/n)* (Lagrange!).

[quote](Z/d)* is isomorphic to a subgroup of (Z/n)*...[/quote]

But (Z/n)* is not always a group.

... R* is the group of units of R.

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

Ah, multaplicative group.  Got it now, and that makes sense.  Thanks.


The LaTeX guide on this site is very nice and I'm glad you have it.  However, there is persistent confusion among new members to the site about the difference between downloading software to produce LaTeXed documents on their own computer and just using LaTeX on the forum, and I think the guide exacerbates this problem.  Do you think it would be possible to add a section at the beginning of the guide (say, a paragraph in the introduction) which explains more clearly that difference?  Basically, it would be nice if there were a convenient place to refer new members so that we do not have to type a thousand times, "... place your code between dollar signs.  If you want to see other people's code, mouse over it.  Here is the forum you can go to practice blah blah blah."

You mean something like [url=http://mathlinks.ro/Forum/viewtopic.php?t=123690]this[/url]?

Can we add a sentence to the beginning of the LaTeX guide saying that for posting on this forum, there is no need to download anything?  Then maybe add a link to stevem's FAQ?

Yes, I think that would be very helpful.


Find all $ f: \mathbb R\to\mathbb R$ such that \[ f(xy) = f(f(x)+f(y))\] for all $x,y\in\mathbb R$.

[quote="MJ GEO"]Find all functions $ f(x)$ from $ \mathbb R\to\mathbb R$ such that $ f(xy)\equal{}f(f(x)\plus{}f(y))$ $ \forall x,y$[/quote]

Let $ P(x,y)$ be the assertion $ f(xy)\equal{}f(f(x)\plus{}f(y))$

1) $ \exists a\ne 0$ such that $ f(a)\equal{}f(0)$
==========================
if $ f(0)\ne 0$, then $ P(0,0)$ $ \implies$ $ f(0)\equal{}f(2f(0))$ and $ a\equal{}2f(0)\ne 0$ fullfills the requirement
If $ f(0)\equal{}0$, then let $ u\ne 0$
If $ f(u)\equal{}0$, then $ f(u)\equal{}f(0)$ and $ u\ne 0$ fullfills the requirement
If $ f(u)\ne 0$, $ P(u,0)$ $ \implies$ $ f(0)\equal{}f(f(u))$ and $ f(u)\ne 0$ fullfills the requirement
Q.E.D.

2) $ f(1)\equal{}f(0)$
===========
Let $ a\ne 0$ such that $ f(a)\equal{}f(0)$ (such a real exists, according to point 1. above)

$ P(a,\frac 1a)$ $ \implies$ $ f(1)\equal{}f(f(a)\plus{}f(\frac 1a))$

$ P(0,\frac 1a)$ $ \implies$ $ f(0)\equal{}f(f(0)\plus{}f(\frac 1a))$

And since $ f(a)\equal{}f(0)$, we get $ f(0)\equal{}f(1)$
Q.E.D.

3) $ f(x)\equal{}f(0)$ $ \forall x$
==============
$ P(0,x)$ $ \implies$ $ f(0)\equal{}f(f(0)\plus{}f(x))$
$ P(1,x)$ $ \implies$ $ f(x)\equal{}f(f(1)\plus{}f(x))$
And since $ f(0)\equal{}f(1)$, according to point 2. above, $ f(x)\equal{}f(0)$
Q.E.D

Hence the unique solution : $ \boxed{f(x)\equal{}c}$ constant, $ \forall x$


Princeton college Harvard Duke geometry MIT Stanford

As far as I know most of the better US universities are unfriendly for outsiders (for undergraduate).  But their graduate programs are fine.

Princeton University is very friendly to Canadian students. They even treat them the same as Americans when it comes to financial aid.

Well, most of the elite US schools give Canadians an equal or pretty good deal when it comes to financial aid.  But Princeton seems to admit a significantly larger number of Canadians than its peers.

Hmm, didn't know that.

But isn't it still like at least 20k US per year, even after finaicial aid, no matter where you're from?

It depends on how much your family makes and how many other siblings you have in school.

its pretty expensive, like more than 200 k for the 4 years of bachelor

I was accepted to Princeton last year, and I would have had to pay about 13000 (USD) after financial aid.  I come from an upper-middle class family; my parents make a fair bit over 100000 (CDN) per year, we live in a large house, etc.

Anecdotes from Canadian friends who applied to other Ivy League schools and comparable institutions give me the impression that

1) Princeton and Harvard are significantly more generous than everyone else
2) MIT/Yale trail by a few thousand a year in most cases
3) Cornell, Brown, UPenn, and Duke give about 10000-15000 a year less than Harvard and Princeton

[quote="8th Army"]Do most of the Canadian IMO team people go to Waterloo or the states for university? I think waterloo would probably give you huge scholarships[/quote]

You know, Waterloo's scholarships are actually kinda small compared to other universities.  Waterloo's largest scholarship covers about...3 semesters?  Well, that's what my friend said this year when he got his National Scholarship.

You misspelled 'tiny'.  Waterloo is lucky that it is a top-notch university, because neither its financial aid nor its location are exactly incentives to go there.

[quote="8th Army"]Do most of the Canadian IMO team people go to Waterloo or the states for university? I think waterloo would probably give you huge scholarships[/quote]

Certainly they would get top scholarships at Waterloo, but as far as I know the States gives scholarships on need more than merit.  The merit students of the States get their huge scholarships nationally instead of from the university itself.  But Canadian students obviously can't apply for the national ones.

[quote="opple"][quote="8th Army"]What SAT (new SAT) scores are usually needed for universities like Princeton?[/quote]

i think for the new SAT they only need 1800 and above.[/quote]

Dream on  :sleeping:

[quote="blahblahblah"][quote="8th Army"][quote="Sunny"]the one with full scholarship had 95%, the other without had a 93%

They both had one impressive list of extracurricular, volunteer activites and tons of awards (math, music, whatever)[/quote]

Wow...Now my only concern is my SAT then, I got 800 on math ok, but still the English part is hard.

Anybody got any advices for applying to Princeton or other universities similar to Princeton?[/quote]

Yes.  If you are not a member of an olympiad team, you had better:

a) be able to write excellent essays
b) be involved in extracurriculars
c) be an otherwise exemplary student

alternately, you could be an excellent athlete - they're always looking for rowers or whatnot.[/quote]

Do they actually force you to join their teams though if they bring you in as an athlete?  Because I've asked a lot of people who say joining university sports doesn't actually get you anywhere; you'd only be doing it for fun.

What kind of activities? Do you need like many community service hours or do you need many executive positions like president of student council?

If there is some cookie cutter formula for getting into Ivy League universities, I don't yet know it.  And if I did, I wouldn't tell you - I'd write a book and get rich instead.  Anyways, I think that in the extracurricular department, the three things that count are dedication - that is, ECs that you have pursued with unusual vigor or for a long period of time, excellence - that is, doing well - preferably at a national level - in the ECs you pursue, and leadership.

If anyone here is applying for the big schools good luck!

As for me, hehehe I'm happy here in Canada.  Heh, I'm waiting for waterloo.

Darn, i just moved. So all of my activities from the previous 8,9,10 grades were cancelled and the other activities just started

Yeah, most likely I will end up in Waterloo too; it's undergraduate program is in similar league anyway :D But this information is good to know, esp. for graduate, thanks! :)

[quote="8th Army"]If I apply for engineering and physics, do they look at my biology marks?[/quote]
your bio mark? no way. well i mean they will look at it but they won't play a factor

Man you guys are ambitious. I just take plain old Math, at Dalhousie University. I doubt our math program is very good because I'm doing really well in it and I don't work very hard. I woudln't recommend conming here simply because it is the most expensive university in Canada. Halifax is a good city to live in though.

I wouldn't like to go to school in the States simply because I don't like their foreign policy at all, plus they are trying to take away a lot of civil liberties. These are things you should also keep in mind. My roommate first year was American and he is so glad he's going to school in Canada.  If you're into alcohol, also remember that their legal drinking age is 21 while ours is 19, for the most part, plus they are bigger nazis when it comes to controlling your lives.

[quote="annabelle's temptation"][quote="bubala"][quote="annabelle's temptation"]
I wouldn't like to go to school in the States simply because I don't like their foreign policy at all, plus they are trying to take away a lot of civil liberties. These are things you should also keep in mind. My roommate first year was American and he is so glad he's going to school in Canada. If you're into alcohol, also remember that their legal drinking age is 21 while ours is 19, for the most part, plus they are bigger nazis when it comes to controlling your lives.[/quote]

LOL :)  The whole country didn't vote for Bush, you know.  In addition, the best universities in the U.S. (Harvard, MIT, Princeton, Stanford, etc)  are in Democratic strongholds.  Boston, home of Harvard and MIT (ok actually cambridge, but whatever) is the home of the liberal intelligentsia. Also, from what I've heard, everyone drinks in college anyway.[/quote]

Touche. I forgot about the good colleges being in the blue states. Hahaha it makes sense though. Voting for Bush or no, You're still stuck with him for 3 years. Who knows he might bring back the draft. Yes everyone drinks in college, except me but they have harsher punishment for getting caught in the states, well maybe just the red ones. There is basically no punishment, if you live in residence here for underage drinking.[/quote]

I hate it when people divide our country into blue states and red states.  It's far more complicated.  [edit] I posted a really long explanation, but it's not relevant to the thread so gone it is now.

If I put on my application to a university in the states like princeton "invited to the 2005 USAMO" does that count as an important award or contribute a lot to me being accepted?
hope for response soon......

[quote="8th Army"]If I put on my application to a university in the states like princeton "invited to the 2005 USAMO" does that count as an important award or contribute a lot to me being accepted?[/quote]

Yes, it is an important award - in fact, a very important one.


[hide]

a straightforward induction. the base case is evident, so we assume it holds for n=k. multiply both sides of the inequality at n=k by (1 + a_(k+1)).  now we show that the RHS of this is greater than the RHS of the inequality at n=k+1 by letting a_(k+1) = 1 + epsilon, for some positive epsilon.

[/hide]

[quote="Fierytycoon"]If [tex]a_i \geq 1[/tex] for [tex]i = 1,...,n[/tex], prove that

[tex]
\displaystyle (1+a_1)...(1+a_n) \geq \frac{2^n}{n+1} (1+a_1+...+a_n)
[/tex][/quote]

The condition hints for the substitution [tex]a_i = b_i + 1[/tex]. Then the ineq becomes
[tex]
(1+\frac{b_1}{2}) \cdots (1+\frac{b_n}{2}) \geq 1 + \frac{b_1 + \cdots + b_n}{n+1}
[/tex]
Now,
[tex]
\begin{array}
 ((1+\frac{b_1}{2}) \cdots (1+\frac{b_n}{2}) = 1 + \frac{b_1}{2} + \cdots + \frac{b_n}{2} + \textrm{something non-negative} \\ \geq  1 + \frac{b_1}{n+1} +  \cdots + \frac{b_n}{n+1}
\end{array}
[/tex]

I've seen this one before, and the solution that I came up with is the one Yufei posted... interesting how that seems more natural to me than induction...

[quote="billzhao"]There is a similar inequality:

if x_i's are non-negative, then
[tex]
\displaystyle (1+x_1) \cdots (1+x_n) \geq (1+ \sqrt[n]{x_1 \cdots x_n})^n
[/tex]

(There's a name for this inequality, but I can't remember what it is.)[/quote]

Isn't that just a specific case of Holder's inequality?

[quote="Nukular"]Isn't that just a specific case of Holder's inequality?[/quote]

Now I look at it, yeah.

It's interesting that once you've seen a nice proof of something, you tend to stop thinking about it.

Anyways, it's basically all the symmetric means inequalities added up together.

...but some are less equal than others.

[quote="belenos"][quote="billzhao"]
if x_i's are non-negative, then
[tex]
\displaystyle (1+x_1) \cdots (1+x_n) \geq (1+ \sqrt[n]{x_1 \cdots x_n})^n
[/tex]
[/quote]

An alternative solution may be to see that ln (1+e^x) is convexe and to use Jensen.[/quote]

I'm not seeing that solution. Holder is more 'obvious', if only because this one looks like Cauchy.

since xi > 0, xi = e^yi

Taking log on both sides and using Jensen :

1/n  :Sigma: ln(1+e^yi) >= ln(1+e( (:Sigma: yi)/n)

then take e^ on both sides

>> ...but some are less equal than others.

???

Do you mean that AoPS is an other "Animal Farm" ? Who are the pigs and the dogs  :wink: ?


linear algebra
matrix
function
induction
vector
algebra
polynomial

Let $A$ be a unitary commutative ring and $A_1,...,A_{2n}$ some $nxn$ matrices with elements in $A$. Prove that if $\epsilon(\sigma)$ is the signature of the permutation $\sigma$ then  $\sum_{\sigma\in S_{2n}}{\epsilon(\sigma)\cdot A_{\sigma(1)}\cdot...\cdot A_{\sigma(2n)}}=O_n$

That would be the zero matrix, which I usually just write 0.

really nice problem but unfortunatly i saw this problem in "Graph Theory" Bella Bollobas i do not like to copy the idea,any way this problem for exam is no suitable atall :(

As if it were the first extremely difficult problem given in oral examinations... :(

[quote="sam-n"]really nice problem but unfortunatly i saw this problem in "Graph Theory" ...[/quote]

Is there a proof without graph theory (I hate graph theory)

For $n=2$ I have a nice proof using multilineaire function, but general case is still missing. :(

actualy it seems that it is originaly graph problem in linear algebra language but maybe someone like you ,Harazi,Grobber,Myth ,Leva and other master will yield purely algebraic solution. :)

I've just read extremely beautiful proof of this theorem, which also presents some magnificient identities and a general method to obtain them. Since it is not a file, I will try to organise it well and to post on the site. Now I am in a hurry, but this evening I will post the complete proof. :)

Let's go for the longest post I've ever made on mathlinks (surely, It won't depass Darij's posts  :D ):
  The following results are due to Almkvist (the first few theorems) and the proof of Amitsur-Levitski theorem is due to Rosset:
  1) Almkvist's theorem
   Let $A$ be a commutative ring and $f$ be a $nxn$ matrix with elements in $A$ and suppose that $ f^{m+1}=0$.  Then $ (tr f)^{mn+1}=0$ and $mn+1$ is the smallest with this property.

    Proof:
    The fact that $mn+1$ is optimal can be deduced by taking $ f$ be a diagonal matrix with entries $x_1,...,x_n$ such that $x_i^{m+1}=0$ and $ x_i^m$ is non-zero...
    So, let's prove the hard part now. Take $e_1,...,e_n$ the standard basis in $A^n$ and observe that $ f(e_i)=\sum_{j=1}^{n}{f_{ij}e_j}$.
    Introduce now an algebra generated by $e_1,...,e_n$ and characterized by associativity, distributivity and $e_i*e_i=0$ and $e_i*e_j=-e_j*e_i$. It is thus clear that if in the product $ e_{i_1}*e_{i_2}*...*e_{i_s}$ we have two indices equal, the whole product is 0.
   Now, observe that  from the above observation we have $(tr f) (e_1*...*e_n) =\sum_{i=1}^{n}{ e_1*e_2*...*f(e_i)*...*e_n}$ and this can be extended by multilinearity to $ (tr f) (v_1*v_2*...*v_n)=\sum_{i=1}^{n}{ v_1*v_2*...*f(v_i)*...*v_n}$. Observe that multiplying by $tr f$ is the same as multiplying by $x_1+...+x_n$ and thus one can prove by induction the following multinomial formula:
   $ (tr f)^N (e_1*...*e_n)=\sum_{k_1+...+k_n=N} {\frac{N!}{k_1!...k_n!}\cdot  f^{k_1}(e_1)*...*f^{k_n}(e_n)}$. Now, for $N=mn+1$, each term in the sum of the multinomial formula is 0, since there is at least one $k_i$ greater than $m$. This ends the proof of the theorem.\\

   By the way, here is a rapid proof of the fact that $ detAB=detA\cdot det B$. Observe that $ (det AB)( e_1*...*e_n)=AB(e_1)*...*AB(e_n)=(detA B(e_1))*..*(detA B(e_n))=detA detB e_1*...*e_n$.\\

 2) The general Almkvist's theorem

   Let $ a_r(f)$ be the sum of all principal minors $rxr$  taken from the matrix $f$. Then
  a) If $ k_1+2k_2+...+nk_n>mn$ then $ a_1(f)^{k_1}...a_n(f)^{k_n}=0$.
  b) $\sum_{r=0}^{m}{ (-1)^r\cdot a_r(f)\cdot tr(f^{m-r})=0}$. \\

   Proof:
    It is not difficult to see that the equality $ (a_r(f)) (e_1*...*e_n)=\sum_{1\leq i_1< i_2<...< i_r\leq n}{ e_1*...*f(_{i_1})*...*f(e_{i_r})*...*e_n}$ and next by multilinearity that the same is true when we replace $e_i$ by arbitrary vectors $v_1,...,v_n$. Iterating, we find that $ a_1(f)^{k_1}\cdot...\cdot a_n(f)^{k_n}$ is a linear combination of terms of the form $ f^{s_1}(e_1)*...*f^{s_n}(e_n)$ with $s_1+...+s_n=mn+1$ and thus again it is 0.\\
     \\ Now, observe that multiplying by $ a_r(f)$ is equivalent to multiplying by $ S_r(x_1,...,x_n)$, the $r$-th elementary symmetric polynomial in $x_1,...,x_n$. Also, multiplying by $ tr(f^r)$ is the same as multiplying by $ x_1^r+...+x_n^r$. This means that any polynomial identity in $tr(f^r)$ and $ a_r(f)$ is true if we have checked it by replacing $ a_r(f)$ with $S_r(x_1,...,x_n)$ and $ tr(f^r)$ with $ x_1^r+...+x_n^r$. But it suffices to observe that in this case b) is verified, since it is nothing else than Newton's formulae. \\

    Now, the proof of Amitsur theorem. Consider the matrix $f$ having as elements linear combinations of $e_i$: $ (f_1) e_1+...+(f_n) e_n$. The Amitsur theorem is equivalent to $f^{2n}=0$. We claim that $tr(f^{2r})=0$ for all $r>0$. Since $tr(AB)=tr(BA)$, we observe that the trace is not modified in a product of matrices if we put the leftmost matrix to the extreme right. If we apply this operation to permutation of even length, we will transform even permutations into odd ones (since the even-length cycle is odd). Since the coefficient of a typical term $e_{i_1}*...*e_{i_{2r}}$ in $tr(f^{2r})$ is $\sum_{\pi\in S_{2r}}{\epsilon(\pi) f_{i_{\pi (1)}}...f_{i_{\pi(2r)}}}$, we can arrange the terms in mutually cancelling terms and thus the trace is 0. Now, the elements of $f^2$ are linear combinations of terms of the form $e_i*e_j$ and all these pairs commute. Since $ tr((f^2)^r)=0$ for all $r$, we find using b) from the general Almkvist’s theorem that $ a_r(f^2)=0$ and by Hamilton-Cayley theorem we find $ f^{2n}=0$.
    I still have some questions about the proof, but I will let you read it first. :)


linear algebra
matrix
vector
combinatorics unsolved
combinatorics

Enumerate and generate the number of invertible matrices (n*n) with each entry either 0 or 1.

Example: For n=2, we have a set of 6 matrices.(see image)
Intrestingly,these matrices form a group under matrix multiplication.

A much more harder problem would be to enumerate and generate all invertible (n*n) matrices with enrites from the set { 0,1,...,n-1 }.

Your question is hard.  An easier question is to find the number of elements $ \textrm{GL}_n({\bf F}_q)$, where $ {\bf F}_q$ is the finite field with $ q$ elements (in particular, $ q \equal{} 2$).  Then we have straightforward linear algebraic techniques to apply.  What complicates the situation here is matrices whose determinant is $ 0$ in $ {\bf F}_2$ but not zero in $ \bf Z$: for example, there are three $ 3 \times 3$ matrices with determinant 2.  These matrices do not correspond to invertible matrices in $ \textrm{GL}_3({\bf F}_2)$.  The sequence corresponding to your question is [url=http://www.research.att.com/~njas/sequences/A055165]A055165[/url] in the [url=http://www.research.att.com/~njas/sequences/]OEIS[/url].  (The fact that all the $ 2 \times 2$ 0-1 matrices have determininant $ 0$ or $ \pm 1$ helps explain why they form a group under matrix multiplication.)

a multiplicative group ? $ \left(\begin{array}{cc}1 & 1\\
0 & 1\end{array}\right)^2\equal{}\left(\begin{array}{cc}1 & 2\\
0 & 1\end{array}\right)$ is apparently not a group member, since you stated to not work modulo $ 2$

@hjbrasch :sorry I forgot to mention, we are working mod2   :wink:

@JBL : (In reference to your last line) we do not have have all the \[ 2*2\] matrices, we have 6 out of 8. Does the set of \[ n*n\] matrices form a group too ?

That comment actually didn't make any sense since, as hjbrasch noted, they don't actually form a group :).

$ \textrm{GL}(n, {\bf F}_q)$ refers to the set of invertible $ n \times n$ matrices with entries in the field $ {\bf F}_q$.  This set is a group.  When $ q$ is prime, we can identify this with the set of invertible matrices with entries in $ \{0, 1, \ldots, p \minus{} 1\}$ taken modulo $ p$, so the answer to your last question is "yes."  Counting this set is straightforward:  we have any vector other than the zero vector to choose for the first column, then any vector not parallel to the first vector to choose for the second column, then any vector not contained in the subspace spanned by the first two vectors to choose for the third column, etc.  Since we're working over a field, linear algebra works -- the span of one nonzero vector has $ q$ elements, the span of two independent vectors has $ q^2$ elements, etc.

See also http://www.artofproblemsolving.com/Forum/viewtopic.php?t=171637 which is a problem in a similar vein.


For $ n$ natural numbers x1...xn no one of them equals 0 Prove that:

$ 240| \sum_{i \equal{} 1}^{n} x_{i}^{5} \Leftrightarrow 240| \sum_{i \equal{} 1}^{n} x_{i}^{9}$

$ \forall h\in\mathbb{N}: \ h^5\equiv h^9[240]$

It suffices to prove that $ 240 | \sum_{i \equal{} 1}^{n} {x_i}^9 \minus{} {x_i}^5$.
We will prove that $ {x_i}^9 \equiv {x_i}^5 (mod 240)$ for all natural numbers $ x_i$

It suffices to prove that $ {x_i}^9 \equiv {x_i}^5 (mod 16)$
$ {x_i}^9 \equiv {x_i}^5 (mod 3)$
$ {x_i}^9 \equiv {x_i}^5 (mod 5)$

The first equation is true because for all odd $ x_i$, $ {x_i}^4 \equiv 1 (mod 16)$; therefore, both sides are equivalent to $ x_i$ mod 16; for all even $ x_i$, both sides are multiples of 16.

The second equation is true because for all $ x_i$ that are coprime with 3, $ {x_i}^2 \equiv 1 (mod 3)$; therefore, both sides are equivalent to $ x_i$ mod 3; for all $ x_i$ that are multiples of 3, $ {x_i}^9 \equiv {x_i}^5 \equiv 0 (mod 3)$ is obviously true.

The third equation is true because for all $ x_i$ that are coprime with 5, $ {x_i}^4 \equiv 1 (mod 5)$; therefore, both sides are equivalent to $ x_i$ mod 5. For all $ x_i$ that are multiples of 5, both sides are equivalent to 0 mod 5.


Βοηθείστε με σε μια άσκηση με ισουπόλοιπα
 Να λυθεί το σύστημα :
 4x Ξ 3 (mod7)
 5x Ξ 4 (mod6)
 Επειδή τώρα άρχισα με τέτοιες ασκήσεις, παρακαλώ λιγο αναλυτικά για να την καταλάβω.

 Ευχαριστώ[/hide][/u][/list]

Ζητώ συγνώμη που επανέλαβα το ιδιο θέμα ...έγινε κατά λάθος και δεν ξέρω πως να το σβήσω.

ευχαριστώ για την κατανόησή σας

Αρχικά για να λύνεις γραμμικές ισοτιμίες υποχρεωτικό εργαλείο είναι το κινέζικο θεώρημα των υπολοίπων. Ας κάνουμε μια μικρή αναφορά σε αυτό. Λοιπόν, έστω $ n_{1},n_{2},...,n_{k}$ θετικοί ακέραιοι ανα δύο σχετικά πρώτοι μεταξοί τους και $ a_{1},a_{2},...,a_{k}$ ακέραιοι. Το σύστημα των γραμμικών ισοτιμιών:

$ x\equiv a_{1}(modn_{1})$
$ x\equiv a_{2} (modn_{2})$
                 $ \vdots$
$ x\equiv a_{k} (modn_{k})$

έχει μοναδική λύση $ (mod(\prod^{k}_{i \equal{} 1}n_{i}))$.

Όσον αναφορά τώρα τις ισοτιμίες $ ax\equiv b (modn)$ για να διώξουμε το $ a$ ψάχνουμε τον μοναδικό αντίστροφο $ c$ τέτοιον ώστε $ ac\equiv 1 (modn)$. Έτσι έχουμε ότι $ ax\equiv b (modn)\Longleftrightarrow (ac)x\equiv bc (modn)\Longleftrightarrow x\equiv bc (modn)$.
Προσοχή όμως! Εαν $ gcd(a,n) \equal{} d$ και το $ d$ δεν διαιρεί το $ b$ τότε η ισοτιμία είναι αδύνατη, ενώ έχει μοναδική λύση εαν και μόνο εαν $ gcd(a,n) \equal{} 1$.

Αυτά πιστεύω πως είναι αρκετά για να λύσεις ισοτιμίες. :)

Ευχαριστώ Γιώργο για τη βοήθεια, αν και δυσκολευομαι λίγο με το κινέζικο θ.των υπολοίπων.
 Παντως ψάχνοντας για τον αντίστροφο πρέπει να προσθέτω και να αφαιρώ από τους α, β το mod
μεχρι αυτά να απλοποιηθούν?

Ο αντιστροφος υπολογίζεται πολλές φορές με τη βοήθεια του αλγορίθμου του Ευκλείδη. Να μερικά παραδείγματα...

Να βρεθεi οι αντίστροφος $ modulo19$ του αριθμού $ 3$.

$ i$) Αναζητούμε ένα αριθμό $ k$ τέτοιον ώστε $ 3k\equiv 1 (mod19)$.
Απο τον αλγόριθμο του Ευκλείδη έχουμε ότι $ 1\cdot 19 \plus{} ( \minus{} 6)\cdot 3 \equal{} 1$ άρα $ \minus{} 6\cdot 3\equiv 1 (mod19)$. Συνεπώς, ο αντίστροφος του $ 3$ είναι ο $ \minus{} 6(mod19)$ ή ο $ 13(mod19)$.

$ ii$)Άρα για το σύστημα στο οποίο αναφέρεσαι έχουμε ότι:

$ 4x\equiv 3 (mod7)$. Όμως $ 2\cdot 4\equiv 1 (mod7)$. Άρα $ (2\cdot 4)\cdot x\equiv 2\cdot 3 (mod7)\Longleftrightarrow x\equiv 6 (mod7)$.

$ 5x\equiv 4 (mod6)$. Όμως $ 5\cdot 5\equiv 1 (mod6)$. Άρα $ (5\cdot 5)\cdot x\equiv4\cdot 5 (mod6)\Longleftrightarrow x\equiv 2 (mod6)$.

Πάλι σε ευχαριστώ Γιώργο,
αυτη τη φορά ήταν πολυ κατανοητό για μένα.
Λοιπόν για τη λύση στο σύστημα, εχουμε :
από την πρωτη: x Ξ 6(mod7)
                       x= 6+7t

αντικαθιστώ στη δεύτερη και έχω :
                      5(6+7t) Ξ 4(mod6)
                       30+35t Ξ 4 (mod6)
                      35t Ξ -26(mod6)

μπορείς να μου πεις σε παρακαλώ πως συνεχίζω?
το βιβλίο δίνει τη  λυση χ Ξ 20(mod 42)

Βασικά Κώστα αυτό που γράφεις δεν είναι σωστο καθώς $ 30 \plus{} 35t\equiv4(mod6) \Rightarrow 30\equiv0(mod6) \Rightarrow 35t\equiv4(mod6)$ και από εδώ παίρνουμε ότι $ t\equiv2(mod6)$

Σημείωση : Οι πράξεις στα modula δεν είναι όπως είναι με αριθμούς . Μπορείς να κάνεις πρόσθεση και αφαίρεση μεταξύ modulwn όχι μεταξύ  modulou και αριθμού.(Ο πολλαπλασιασμός ορίζεται κανονικά και η  διαίρεση μόνο που η διαίρεση έχει κάποιες ιδιαιτερότητες)

Λοιπόν θα λύσω ένα σύστημα γραμμικών ισοτιμιών για να κατλάβεις πιο καλά τη διαδρομή που ακολουθούμε κάθε φόρα.

Να λυθεί το σύστημα:
$ x\equiv 1 (mod3)$   (1)
$ 3x\equiv 1 (mod4)$  (2)
$ 4x\equiv 2 (mod5)$  (3)

Λύση:

Η πρώτη ισοτιμία (1) δεν χρειάζεται περισσότερο ανάλυση οπότε την αφήνουμε όπως είναι.

Για τη δεύτερη (2) έχουμε ότι $ 3x\equiv 1 (mod4)$. Όμως $ 3\cdot 3\equiv 1 (mod4)$. Οπότε $ (3\cdot 3)\cdot x\equiv 1\cdot 3 (mod4)\Longleftrightarrow x\equiv 3 (mod4)$.

Τέλος για την τρίτη (3) έχουμε $ 4x\equiv 2 (mod5)$. Όμως $ 4\cdot 4\equiv 1 (mod5)$. Έτσι $ (4\cdot 4)\cdot x\equiv 2\cdot 4 (mod5)\Longleftrightarrow x\equiv 3 (mod5)$.

Οπότε αρκεί τώρα να λύσουμε το σύστημα:

$ x\equiv 1 (mod3)$
$ x\equiv 3 (mod4)$
$ x\equiv 3 (mod5)$

το οποίο έχει μοναδική λύση $ (mod3\cdot 4\cdot 5)$ ή $ (mod60)$

Υπολογίζουμε τους αντιστρόφους των αριθμών $ 60/3(mod3)$, $ 60/4(mod4)$ και $ 60/5(mod5)$ οι οποίοι είναι οι $ 2,3,3$ αντίστοιχα αφού $ 2\cdot 20\equiv 1 (mod3)$ και $ 3\cdot 15\equiv 1 (mod4)$ και $ 3\cdot 12\equiv 1 (mod5)$.

Άρα σύμφωνα με το κινέζικο θεώρημα η μοναδική λύση του συστήματος είναι η $ x\equiv20\cdot 2\cdot 1 + 15\cdot 3\cdot 3 + 12\cdot 3\cdot 3(mod60)\equiv 43(mod60)$.

Όσον αναφορά το κινέζικο θεώρημα αυτό στο οποίο αναφέρθηκα χτες δεν ήταν γενικευμένο. Οπότε η γενίκευση του κινέζικου θεωρήματος μας λέει ότι:

Οι γραμμικές ισοτιμίες $ x\equiv a_{i}(modn_{i})$, με $ i = 1,2,...,k$ έχουν κοινή λύση αν και μόνο εάν $ gcd(n_{i},n_{j})|(a_{i} - a_{j})$ για κάθε $ i\neq j$. Στην περίπτωση που υπάρχει λύση, αυτή είναι  μοναδική $ (mod(lcm(n_{1},n_{2},...,n_{k})))$.

Εδώ βάζω και τη λύση της δικιά σου άσκησης...

[hide]$ x\equiv 6 (mod7)$
$ x\equiv 2 (mod6)$

Απο το κινέζικο θεώρημα το σύστημα έχει μοναδική λύση $ (mod6\cdot 7)$ ή $ (mod42)$. Υπολογίζουμε τους αντιστρόφους των αριθμών $ 42/7(mod7)$ και $ 42/6(mod6)$.Με δοκιμές βρίσκουμε ότι είναι οι $ 6,7$ αντίστοιχα αφού $ 6\cdot 6\equiv 1 (mod7)$ και $ 7\cdot 7\equiv 1 (mod6)$. Άρα το σύτημα έχει μοναδική λύση την $ x\equiv 6\cdot 6\cdot 6 + 7\cdot 7\cdot 2(mod42)\equiv 314(mod42)\equiv 20 (mod42)$. :wink: [/hide]

Γειά σου Γιώργο,
διάβασα λίγο και μπορώ να πω ότι είμαι σε θέση να λύσω μερικές ασκήσεις.
Μου αρεσε πολυ ο τρόπος που έλυσες το δικό σου συστηματάκι. το προσπάθησα κι εγώ και στο στέλνω να μου πεις αν ο τρόπος μου είναι σωστός.
(έχει αλλο αποτέλεσμα αλλά σαν υπόλοιπο μπορει να θεωρηθεί πιστεύω σωστό)
1) χ Ξ 1 (mod3)
2) χ Ξ 3 (mod4)
3) χ Ξ 3 (mod5)

Από την (1) => χ=1+3t (4)
βάζω την τιμή στη (2)=> 1+3t Ξ 3((mod4) =>3t Ξ 2(mod4)=>3.3t Ξ 3.2(mod4)=>t Ξ 6(mod 4)=> t =6+4s
"        "           "    (4)=> x = 1+3(6+4s)=19+12s
"        "           "    (3)=> 19+12s Ξ 3 (mod5)=> 12s Ξ 16(mod5)=>3.12s Ξ 3.16(mod5)=> s Ξ 48(mod5) Ξ 3(mod5)

Μπορεί να κάνω λάθος, γιαυτό πεσμου αν κάπου δεν βγαινει... Δεν έχω μάθει ακόμα το κινέζικο.
Παντως ο δικός σου τρόπος με τα mod.mod.mod είναι πιστεύω ο σωστός.

Στέλνω άλλη μια ασκηση , να λυθεί όμως με modules , einai :6x +4y +8z=2 ( οχι με αντικατασταση του 3χ+2υ=ω) κι αυτό γιατι θέλω να καταλάβω
3χ +2y +4z =1 (mod2)=> x Ξ 1 (mod2) => x=1+2t
ετσι 3(1+2t)+2y +4z=1=>3+6t+2y+4z=1 => 2y+4z=-2-6t  πως συνεχίζω απο εδώ ? ποιό mod ?

Ξέρεις να μου πεις κάποιο πρόγραμμα για να μπορώ να γράφω τους μαθηματικους τύπους, τα σύμβολα κλπ, ? γιατι είναι μεγάλος μπελας...χιχι

Σε ευχαριστώ και πάλι για τη βοήθεια
Κώστας

[quote="Kostas M"]
Ξέρεις να μου πεις κάποιο πρόγραμμα για να μπορώ να γράφω τους μαθηματικους τύπους, τα σύμβολα κλπ, ? γιατι είναι μεγάλος μπελας...χιχι
[/quote]

Εδώ στο forum είναι πολύ χρήσιμο να μάθεις να γράφεις με το $ LaTex$ (δεν χρειάζεται να κατεβάσεις κανένα πρόγραμμα :wink: ). Για πληροφορίες κοίτα εδώ:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=102567[/url]

Πολύ καλό bilot4 ,  ευχαριστώ.


[quote="Lovasz"]Prove the inequality for positive reals,
$4(x^{2}y^{2}+y^{2}z^{2}+z^{2}x^{2})+20(x^{3}y+y^{3}z+z^{3}x) \ge \\ \ge 16(xy^{3}+yz^{3}+zx^{3})+8xyz(x+y+z).$[/quote]
I think it is wrong. Try $x=3,$ $y=1$ and $z=2.$ :wink:


Provide methods for making the following transformations:

1) Cyclopentanone ----> cyclohexanone

2) Cyclohexanone ----> cyclopentanone

Ring expansion can be achieved via reaction with diazomethane $ : CH_2 \minus{} N \equiv N$ (where the positive charge resides on the $ N$ atom and negative charge resides on the $ C$) in ether.

Is this process used exclusively for the ring expansion of cyclic ketones?

[quote="BanishedTraitor"]Ring expansion can be achieved via reaction with diazomethane[/quote]

It can, but that method is almost never used because of a major drawback: there is also the formation of a considerable amount of a by-product. Can you find which?

The ring expansion can be achieved through a 3 step clean method.

[quote="BanishedTraitor"]Is this process used exclusively for the ring expansion of cyclic ketones?[/quote]

That process is not used for ketones expansion, but it used in a very important "expansion". Can you find out which?

I only know that Nitrogen is produced.

What about using Favorskii Reaction to achieve ring contraction of cyclohexanone? Then reduction using $ LiAlH_4$ followed by acid hydrolysis to achieve an alcohol. Then using concentrated sulphuric acid to dehydrate it. Finally ozonolysis to obtain cyclopetanone.

[quote="BanishedTraitor"]I only know that Nitrogen is produced.[/quote]

I was referring to another organic product that is also produced. As an hint, check the mechanism of the reaction.

[quote="BanishedTraitor"]What about using Favorskii Reaction to achieve ring contraction of cyclohexanone?[/quote]

That's right, that is also my first step. A note: the reaction is more correctly called the Favorskii rearrangement. However, in order to use this rearrangement we have to do something first on our starting molecule.

[quote="BanishedTraitor"]Then reduction using LiAlH4 followed by acid hydrolysis to achieve an alcohol. Then using concentrated sulphuric acid to dehydrate it. Finally ozonolysis to obtain cyclopetanone.[/quote]

Humm, that dehydration would not probably yield the alkene you are thinking. Check again. Also, one can use less steps (my proposal uses two steps after the Favorskii rearrangement).

Yeah didn't think that the primary alcohol will be dehydrated. It will form an ether instead right? So is it actually possible to dehydrate primary alcohols?

While an ether might also form, what besides that can also happen? Assuming the primary alcohol is dehydrated what might happen under the acidic reaction conditions?

To perform Favorskii Rearrangement we must first halogenate the cyclohexanone and obtain $ \text{ o \minus{} halocyclohexanone}$.

What about $ \alpha$-halogenation under acidic conditions? Then we can perform Favorskii Rearrangement.

That's right, we must first halogenate the ketone. The conditions of halogenation are not important, as long as we obtain a mono-alpha-halogen ketone. Then the rearrangement is performed under basic conditions. Then what?

My idea was to transform it into a primary amide first. Then we can perform Hofmann Rearrangement (or Curtis Rearrangement) to obtain aminocyclopentanone. Then we can perform Hofmann Elimination Reaction to get cyclopetene and finally oxymercuration and oxidation.

Problem, according to my text book the Hofmann Elimination reaction is not widely used.

If your idea is to make the conversion R-COOH ----> R-NH2, then you can use the Schmidt rearrangement - treatment of the acid with hydrazoic acid and heating - converts directly the acid into the amine without having to isolate an intermediate.
Anyway, your synthetic path is correct. For a shorter alternative, how to make the conversions R-COOH -----> R-CH2OH -----> R-OH ?

Can't we use the Demjenov Rearrangement ?
Refer http://en.wikipedia.org/wiki/Tiffeneau-Demjanov_rearrangement

[quote="Madness"]Can't we use the Demjenov Rearrangement ?[/quote]

Very good, that was the purpose. But how to synthesize the intermediate amino alcohol?

Well we could use the cyanohydrin formation method .
1. Use HCN and  H+
2. Use Na and C2H5OH
 :)

That's right (it should be NaCN and H+). How about the ring contraction? (My proposal uses four steps)


geometry
circumcircle
rotation
angle bisector

Consider triangle $ ABC$.  The angle bisector of $ C$ intersects the circumcircle of $ ABC$ at $ D$.  Draw the perpendicular from $ D$ to $ BC$ and let the intersection be $ X$.  Prove that $ CX$ is the average of $ a$ and $ b$.

($ a$ and $ b$ are the sides opposite of $ A$ and $ B$)

[asy]size(200);
defaultpen(fontsize(8));
pair A=(0,0), B=(10,0), C=(3,7), D, X, E;
D=intersectionpoint(circumcircle(A,B,C),(A+B)/2--40*expi(angle(B-A)-pi/2)+(A+B)/2);
X=foot(D,B,C);E=intersectionpoints(Circle(D,abs(D-B)),B--C)[1];
draw(circumcircle(A,B,C));draw(A--B--C--A--D--B);draw(C--D--E);draw(D--X);
draw(Circle(D,abs(D-B)));
dot(A^^B^^C^^D^^E^^X);label("A",A,(-1,0));label("B",B,(1,0));
label("C",C,(0,1));label("D",D,(0,-1));label("E",E,(1,1));label("X",X,(1,1));[/asy]Let the circle centered at $ D$ and passing through $ A$ and $ B$ intersect $ BC$ at $ E$. Since $ \triangle DBE$ is isosceles with $ DE\equal{}DB$, we have $ \angle DEB\equal{}\angle DBE\implies \angle CAD\equal{}\angle CED\implies \triangle CAD\cong\triangle CED$ which means $ CE\equal{}CA$. Since $ X$ is the midpoint of $ EB$, we are done.

How did you get
$ \angle DEB \equal{} \angle DBE\implies \angle CAD \equal{} \angle CED$ ?

Because $ ABCD$ is cyclic so $ \angle CAD \plus{} \angle CBD\equal{}180 \equal{} \angle CAD \plus{}(180\minus{}\angle CED)$ so $ \angle CAD\equal{}\angle CED$

Nice problem! Here is a different solution:
[asy]size(200);
defaultpen(fontsize(8));
pair A=(0,0), B=(10,0), C=(3,7), E=(15.38516,-5.38516), D, X;
D=intersectionpoint(circumcircle(A,B,C),(A+B)/2--40*expi(angle(B-A)-pi/2)+(A+B)/2);
X=foot(D,B,C);
draw(circumcircle(A,B,C));draw(A--B--C--A--D--B);draw(C--D);draw(D--X);draw(B--E--D);
label("A",A,(-1,0));label("B",B,(1,0));
label("C",C,(0,1));label("D",D,(0,-1));label("X",X,(1,1));label("E",E,(1,1));[/asy]
Rotate $ \triangle ADC$ about D so AD lies on BD. C,B,E are collinear since ABCD is cyclic. Since CD=DE and $ DX \perp CE$, DX bisects CE.

By the way, misoens's proof can be nicer by reflecting $ \triangle ACD$ over CD. Then DEB is isoceles, so X bisects EB!
Similarly, I used a SAS congruence argument at first, but then turned it into a rotation.


geometry
incenter
circumcircle
geometry unsolved

points $ A,B,C,$ divide the circumcircle of triangle $ ABC$ in three arcs.let $ X$ be a variable point on the arc $ AB$ and let $ O_1$ and $ O_2$ be the incenters of the triangles $ CAX$ and $ CBX$ .prove that the circumcircle of the triangle $ XO_1O_2$ intersects the circumcircle of triangle $ ABC$ in a fixed point

There is a resources section you might want to check it out!
Your problem:
http://www.mathlinks.ro/viewtopic.php?p=131844#131844


Let $S$ be a non-empty set of $k$ elements. Prove that there is atleast one element in $S$ that is less than or equal to the average of all the elements of $S$.

[hide="Proof"]We know that $\left|S\right|=k$ so the average is $a=\frac{1}{k}\sum_{x_{i}\in S}x_{i}$.  Assume that for all $i\in I$, we have $x_{i}>a$.  Then \[\sum_{x_{i}\in S}x_{i}>ka\implies \frac{1}{k}\sum_{x_{i}\in S}x_{i}>a\implies a>a,\] which is a contradiction.[/hide]

Awful, unnessecarily long, nonrigorus, abstract, confusing proof.  :P

[hide]Let $k=1$. Then that one element (lets call it $e$) is the average and $e=average$. If we let $k$ be a number greater than one, then we know that in order to obtain the average in a set of, lets say, $2$, then if the elements of the set are $e_{1}$ and $e_{2}$, the average will be in between $e_{1}$ and $e_{2}$.

If $k$ is greater than $2$, then the first element $e_{1}$ of $k$ must be less than the average, since the average $A=\frac{e_{1}+e_{2}+...+e_{k}}{k}$, and in a "number line" point of view, $e_{1}$ must be "paired" with a $e_{n}$ for some $n$. Thus, $e_{1}\le A \le e_{n}$.[/hide]


If the exponentiated expression $ a$ in $ x^a$ for $ a, x \in \mathbb{ R}$ is defined to be $ e^{a ln x}$ for $ x > 0$, then what would the definition be for $ x \in \mathbb{R^{\minus{}}}$ U $ \{0\}$?

PS: How to type the formulas union and intersection?

Regarding your last question, study the symbols $ \cup, \cap, \bigcup, \bigcap$.

[quote="t0rajir0u"]$ x^a$ cannot be assigned a real value when $ x < 0$ and $ a$ is rational with even denominator.  If $ a$ is rational with odd denominator, the definition of exponentiation for rational $ a$ applies, and if $ a$ is irrational we run into real trouble.  For more information, see [url=http://en.wikipedia.org/wiki/Complex_logarithm]complex logarithm[/url].[/quote]

Yes, that's exactly what I was worrying about (btw, this question was inspired by my PDE professor when he mistakely wrote the expression $ (\minus{}1)^{\pi}$ instead of the intended $ (\minus{}1)^n$ for $ \cos n\pi$ and I wonder what that's gonna equal to  :D).

So in $ \mathbb{R},$ irrational exponents aren't defined for $ x < 0,$ are they?

But if we have, say, $ x^0, x \in \mathbb{R^\plus{}},$ which is obviously $ 0$; but when using the definition $ x^a \equal{} e^{a \log x}$, then the $ \log$ isn't going to be defined.  So how are we going to account for that?

PS: I found some silly typos in my first post, but when I tried to edit, I'm not allowed to do so; why is this so, plus what harm would it cause to edit one's post?  :huh:

[quote="mathwizarddude"]But if we have, say, $ x^0, x \in \mathbb{R^ \plus{} },$ which is obviously $ 0$; but when using the definition $ x^a \equal{} e^{a \log x}$, then the $ \log$ isn't going to be defined.  So how are we going to account for that?[/quote]
You mean $ 0^a$.  The value of $ e^{a \ln x}$ at $ x \equal{} 0$ (and for $ a > 0$) is a removable discontinuity: the observation that $ \lim_{x \to 0^{ \plus{} }} e^{a \ln x} \equal{} 0$ can be used to fill it in.

The time limit on editing posts appears to be to stop certain posters (that is, spammers) from erasing evidence of bad posts they make after they make them.

More importantly, from changing posts after they've been responded to.  (There are lots of old posts in which the original question was deleted only after answers were posted ... this renders the entire thread useless, unless you can reconstruct the question from the answer (which is not always possible).)

In $ \bf R$, irrational exponents are not defined for negative bases, as you surmised: you take limits through the rationals with odd denominators and this will give you a real value equal to one of the infinitely many values that the expression has in $ \mathbb C$, but this doesn't make the function $ x^a$ "nice" for negative $ x$ because it's still undefined when $ a$ is rational and has even denominator.


calculus
integration
LaTeX
function
calculus computations

I am having trouble figuring out this integral if some one could point me in the write direction... i'm assuming integration by parts but im not sure so any help would be much appreciated

the integral of ((e^x)(x-1)dx)/x^2

Compiling thauber's integral into $\LaTeX$ form: $\int \frac{e^x(x-1)\,dx}{x^2}$

Wait a minute... this integral does not have an elementary function as antiderivative... are you sure you typed in the correct function, thauber?

yes im positive....

integrals.com says the answer is e^x/x

but i have no idea how they got there.

In using integral by parts, let's start $\int \frac{1}{x^2}e^x dx$, thauber.

$\int \frac{e^x(x - 1)}{x^2} \text dx = \int \frac{e^x}{x} \text dx - \int \frac{e^x}{x^2} \text dx =$

(do the 1st integral by parts and do not touch the 2nd one)

$= \frac{e^x}{x} + \int \frac{e^x}{x^2} \text dx - \int \frac{e^x}{x^2} \text dx = \frac{e^x}{x} + C$

Yeh!  Your solution is more natural than mine,yetty.