Of $ 28$ students taking at least one subject the number taking Mathematics and English only equals the number taking Mathematics only.  No student takes English only or History only, and six students take Mathematics and History, but not English.  The number taking English and History only is five times the number taking all three subjects.  If the number taking all three subjects is even and non-zero, the number taking English and Mathematics only is:

$ \textbf{(A)}\ 5 \qquad \textbf{(B)}\ 6 \qquad \textbf{(C)}\ 7 \qquad \textbf{(D)}\ 8 \qquad \textbf{(E)}\ 9$

[hide]
$ 28\equal{}(m)\plus{}(e)\plus{}(h)\plus{}(me)\plus{}(mh)\plus{}(eh)\plus{}(meh)$.

$ (m)\equal{}(me)\equal{}x$

$ (e)\equal{}(h)\equal{}0$

$ (mh)\equal{}6$

$ (meh)\equal{}y\Rightarrow (eh)\equal{}5y$.

$ 28\equal{}2x\plus{}6\plus{}6y\Rightarrow 11\equal{}x\plus{}3y$.

If $ y\geq 4$, $ x$ will have to be negative.  So $ y\equal{}2\Rightarrow x\equal{}5$.
[/hide]


geometry
geometric transformation
reflection
analytic geometry
\/closed

Is there a way that we can change the time to reflect daylight savings time, or would this be too complicated?

Oh, I just realized - alternatively, individual users can change their time settings in their profile.  Perhaps setting the "Time Zone" to 1 hour back would do the trick...

Actually, I don't think it would require too much script to make daylight savings changes. However, we must take into consideration that there are some countries that don't do daylight savings...

right...most iof IN doesn't observe daylight savings time...I know I don't and I live in northern IN...

odd...so how does one side of the state coordinate with the other side?

They don't -- the north-west corner is at a different time than the rest.  Just like poeple in the central time zone are at a different time than people in the eastern time zone.


AMC
AMC 10
AIME
USA(J)MO
USAMO
geometry
FTW

Yay! How did everyone else fail the AMC10/12?
I managed to assume 20+3+6 was 33 on problem six of the AMC10!
Mods please remove if this is considered spam.

[quote="ra5249"]Yay! How did everyone else fail the AMC10/12?
I managed to assume 20+3+6 was 33 on problem six of the AMC10! WOoT for 144!
Mods please remove if this is considered spam.[/quote]

$ 144 \ne \text{failure.}$

Seriously, stop that.

[quote="the future"]dude wtf yea its a bad mistake to make since it cost you a perfect but imagine the people that didnt even pass...

i didnt make any stupid mistakes (like computational) but i didnt finish out 3 problems on the 12 because i assumed they were too hard.  However, after the test, I could do them each in like 4 minutes.  Next time, I should try to at least attempt all the problems and not be intimidated just because its a number 24 or something.[/quote]

First time I took the AIME (2006 II) I bruteforced number 15... and got it right.

the first time i took AIME (2007 AIME II) i brute forced #2 and got it right :D

I failed.
EDIT: I guess I will just remove my score from this post so it will not affect anyone.

have u gotten ur official results back yet????

By saying you guys did terrible, how do you think you're making the people who got lower scores than you feel? I know that many hard-working people at my school would be happy to score anything higher than 100 on the AMC12. Even if you feel that you could have done better, complaining is simply annoying and not productive.

:huh: This chastising of people who enjoy showing off by announcing to the world that they "failed" by getting high scores sounds familiar...  But of course!  We've heard of it during the AMC 8 posts, haven't we?!

But seriously, ra(random numbers), plz stop making others feel bad this way.  It gets really annoying...

Argh- I hate my internet- somehow this didn't post earlier
Rem- I feel your pain to some level. I was an HM last year too, I've aced the AMC 10 twice, and I scored a 117 on the 12A, which is lower than I scored in 7th grade, even after accounting for the change in scoring that has happened.
I also think that working on Olympiad problems rather than focusing on speed/computational accuracy hurt me. At the same time (and I'm addressing this to everyone, not just Rem), these are part of the game. We know the rules, we know that arithmetic counts, and we know that if we make mistakes, we'll lose points no matter how well we understand the problem. I got a 117 because I earned 117 points under the rules that we were playing with, like those rules or not. Congratulations to everyone who did better than that, and to everyone who may have scored less, but made their goal. No matter what your goals are, be they making AIME, being a USAMO winner, or finding a date for a school dance, achieving them is always worthy of celebration. For those of you who didn't make your goals (including me), just remember that a lot of the value in these competitions comes from learning something while you prepare.
-Max

Wow. I agree with you completely. I also think that I did too much olympiad math and forgot how to double check things.
But I think it's still not over - there is still AIME coming up.

Yeah- I think that an 8 (and certainly a 9) would get either of us through, which is basically what would've been required pre-USAMO expansion.

I made a mistake on #9 for the AMC 12.  Apparently, I thought that $ 5.4\times 4 \equal{} 20.4$.  I was devastated when I found out that I guessed #24 and #25 correctly.  So I was praying that there was some other question I got wrong (so that way I didn't mess up what should have been a perfect score).  And I did.  I got #23 wrong, and I thought I did it correctly.  So I guess I'm kind of relieved.

[quote="xpmath"]I got a 123 :(  Misbubbled 6,7, got 16 wrong because of a stupid mistake, and left two blank.[/quote]

how do you know you misbubbled?

ppl, 120-150 don't equal FAIL!!!

SERIOUSLY!!!!!!!!

I found this years 10A VERY CHALLENGING. I skipped three problems, and am not sure how many I missed, but I must have missed about 3.

I was pretty lucky this year, so I can't say anything...but I'll put in a post for the ~10 people at my school who got scores around 95 and are anxious to know whether or not they made it.  Some of them went for 14 correct, 11 blank in the hopes of making it...and messed up one problem.  Others went for 15 and 10...and messed up two.  Etc, etc...

[quote="kimmystar94"]There is only so much room in the top of the pyramid.[/quote]
nice
i totally agree, tho.
i'm taking the 10b cause my school can't do the 10a for some reason
i didn't kno that u could take the 10a and the 10b....
i wish i could do that.

i demand 2 memberships in this club.

i
failed
miserably
-_-

I'm going to leave this discussion open (for now at least), but I suggest that you read this thread:

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

Guys.  Calm down.  If you made it, good for you.  Think about thsoe hopeful people who didn't make it at all.  I got a 144, and I'm completely happy with my score.  Of course I wasn't aiming for a 150... I was aiming for a 120  :rotfl: .  But considering how old most of you ppl are, a 144 is uber-pwnage.

So what you got a 144.  That's life.  Life deals out its cards.  If it gives you a bad hand, you take what you have and you deal with it.

No need to cry over spilled milk...

Seriously, please stop complaining.  It's not like ranting about missing one problem is going to magically change your answer on the bubble sheet and make it a 150.

Chillax  :)

Its not particularly encouraging when you do much better in 7th grade on a harder test than in 8th grade on an easier test.

I got a 120 on the 10 (if i didn't bubble anything wrong)...  :maybe:  at least i passed, but did worse than I expected to. Made a stupid mistake on 7 and 12. x.x And there was too much geometry!

[quote="Twiz"][quote="serialk11r"]Yes, AoPS is a community of some of the best. If you feel bad because you see other people saying they got "bad" scores, then don't visit this forum.[/quote]My impression is that AoPS is a place for students to learn math with and from their peers, not a place for "some of the best" to conglomerate and discuss their greatness. I like to think of AoPS as a community welcoming to new math students eager to learn, but you seem to prefer the idea of a cut-throat environment encouraging those who are not "good enough" to leave. Also, the caps and quadruple exclamation points aren't helping this discussion.[/quote]
I didn't say it was FOR the best, I said it was a community of some of the best. That means there are some really bright people here. What I'm trying to say is it's really really hard to not have those "bragging" posts on a  forum like this so just do your best to ignore. Besides, your own goals are most important.

[quote="infinity4ever"]  Life deals out its cards.  If it gives you a bad hand, you take what you have and you deal with it.[/quote]

[quote="kimmystar94"] There is only so much room at the top of the pyramid. [/quote]

sorry if this is spam, but
you guys have nice quotes...

I failed in that I didn't reach my goal. Oh well.

[quote="Narcissa"]what do u think the usamo cutoff is going to be??[/quote]

I think the AIME would need to occur before we could begin to take a guess at that.

Sometimes these things are memorable. Nearly 10 years later, I still remember exactly how I got #4 on the 1999 AHSME wrong (69 is prime!). That was the only time I ever missed one of the early questions. What was my score? 145, 7 points higher than my second-best.
In honor of that question, 69 is officially my unlucky number.

But... don't use this as an excuse to whine. One question less than an awesome score is still great. I am proud of my sister's school-winning 102 just as I am proud of my state-winning 145.


calculus
integration
logarithms
calculus computations

Misan,
As stated the integral equality is false since the integral is definitely a negative real number while $ \ln(2)-\frac{1}{2}>0$.

Here is what I have:

The integral equals:

$ -\frac{4}{\pi}\sum_{m=0}^{\infty}\frac{(-1)^{m}(2m+1)}{(2m+1)^{2}-4}\ln\left(m+\frac{1}{2}\right)$.

I will use the following formula:

$ \frac{1}{\cosh x}=\sum_{m=0}^{\infty}(-1)^{m}\frac{\pi(2m+1)}{x^{2}+(2m+1)^{2}\frac{\pi^{2}}{4}}$.

Make the substitution $ y=e^{-t}$ and we get that

$ I=-\int_{0}^{\infty}\frac{tdt}{\cosh(t)(\pi^{2}+t^{2})}dt=$

$ =-\sum_{m=0}^{\infty}(-1)^{m}\pi(2m+1)\int_{0}^{\infty}\frac{t}{(t^{2}+\pi^{2})(t^{2}+(2m+1)^{2}\pi^{2}/4)}dt$

and after some calculations

$ =-\frac{4}{\pi}\sum_{m=0}^{\infty}\frac{(-1)^{m}(2m+1)}{(2m+1)^{2}-4}\ln\left(m+\frac{1}{2}\right)$.

Maybe this sum can be expressed in terms of well-known constants.


[quote="arqady"][quote="quykhtn-qa1"]Let $ a,b,c$ be real numbers.Prove that:
$ (a^2 \plus{} 2)(b^2 \plus{} 2)(c^2 \plus{} 2) \ge 3(a \plus{} b \plus{} c)^2$
This inequality easy but nice.I hope you will like it,my friend :)[/quote]
See here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=4830
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=76508[/quote]
Sorry,here is my solution:
Put $ x\equal{}b\plus{}c$ we have: $ (b^2\plus{}2)(c^2\plus{}2) \ge 3\plus{} \frac{3}{2}x^2$
Then$ LHS \minus{} 3(a\plus{}x)^2 \ge \frac{3(ax\minus{}2)^2}{2} \ge 0$
Then,we have Q.E.D :)

[quote="quykhtn-qa1"]Let $ a,b,c$ be real numbers. Prove that

$ (a^2 \plus{} 2)(b^2 \plus{} 2)(c^2 \plus{} 2) \ge 3(a \plus{} b \plus{} c)^2,$[/quote]$ \prod{\left(a^2 \plus{} 2\right)} \minus{} 3\left(\sum{a}\right)^2 \equal{} \frac {8}{9}(bc \plus{} ca \plus{} ab \minus{} 3)^2 \plus{} \frac {4}{9}\sum{(b \minus{} c)^2}$

$ \plus{} \frac {1}{27}\sum{\left[a \plus{} b \plus{} c \minus{} 3abc \plus{} \sqrt {5}(ca \plus{} ab \minus{} 2bc)\right]^2}\geq0.$

This problem is introduced as Example 2.4.18 on pp. 79-80 in new book :

Ji Chen, Chao-Cheng Ji, [url=http://www.newbooks.com.cn/book/321710.html]Algebraic Inequalities (Mathematical Olympiad Proposition people Lecture)[/url], Shanghai Scientific & Technological Educational Publishing House, 2009, 225p. (ISBN 978-7-5428-4848-2/O·613)

use schur inequality,quykhtn-qa1.
sorry for my bad english!

[url=http://www.artofproblemsolving.com/community/c6h1389087p7737051]Viet Nam TST 2017 MOCK Test[/url]

[quote=quykhtn-qa1]Let $ a,b,c$ be real numbers.Prove that:
$ (a^2\plus{}2)(b^2\plus{}2)(c^2\plus{}2) \ge 3(a\plus{}b\plus{}c)^2$
This inequality easy but nice.I hope you will like it,my friend :)[/quote]

My SOSprogram output an non-symmetric SOS for it.
$$\frac{1}{9} \left( abc-3a+b+c \right) ^{2}+\frac{2}{9} \left( abc-2b+c
 \right) ^{2}+{\frac {5}{18}} \left( 2ab-ac-bc \right) ^{2}+{
\frac {8}{9}} \left( ab+ac+bc-3 \right) ^{2}+\frac{5}{6}c^2 \left( a-b
 \right)^2+\frac{2}{3}c^2 \left( ab-1 \right)^2\ge 0.$$


$ let$  $ f: \mathbb{N}*\mathbb{N}\equal{}\equal{}>\mathbb{N}$

           $ (x,y)\equal{}\equal{}>{\frac{(x\plus{}y)(x\plus{}y\plus{}1)}{2}}\plus{}y$
$ prove$ $ that$ $ f$ $ is$ $ injective$.
 :)

${ \frac{(x+y)(x+y+1)}{2}}+y =k \Longrightarrow x^2+(2y+1)x+y^2+3y-2k=0$
$ x$ have to be integer, so $ (2y+1)^2-4(y^2+3y-2k)=(2u+1)^2$, so $ y=k-\frac{u(u+1)}2\ ,\ x=\frac{u(u+3)}2-k$
We need $ x\geq 0, y\geq 0 \ \Longrightarrow\ u(u+1)\leq 2k\leq u(u+3)\ \Longrightarrow$$ \frac {-3+\sqrt{9+8k}}2 \leq u \leq \frac {-1+\sqrt{1+8k}}2$
But $ \frac {-1+\sqrt{1+8k}}2-\frac{3+\sqrt{9+8k}}2 < 1$ , so there is  only one integer $ u$
So if $ f(x,y)=f(a,b)=k$ then $ x=a\ ,\ y=b$ (injective)
........
An other one . Suppose $ f(x,y)=f(a,b)$
$ x+y=a+b \Longrightarrow y=b \Longrightarrow a=x$ (injective)
If $ x+y\neq a+b$, let we suppose for exemple $ a+b > x+y  \Longrightarrow a+b=x+y+t$ with $ t \geq 1$ . We can write :
$ f(a,b)= \frac{(x+y+t)(x+y+t+1)}2+b >$ $ \frac{(x+y)(x+y+1)}2 + t(x+y) \geq \frac{(x+y)(x+y+1)}2 + y = f(x,y)$ (contradiction !)
  :cool:

[quote="greatestmaths"]$ let$  $ f: \mathbb{N}*\mathbb{N} \equal{} \equal{} > \mathbb{N}$

           $ (x,y) \equal{} \equal{} > {\frac {(x \plus{} y)(x \plus{} y \plus{} 1)}{2}} \plus{} y$
$ prove$ $ that$ $ f$ $ is$ $ injective$.
 :)[/quote]

Let $ x_n\equal{}\frac{n(n\plus{}1)}{2}$
For any real $ a$, there is a unique $ n\in\mathbb{N}\cup\{0\}$ such that $ x_n<a\leq x_{n\plus{}1}$ and, since $ x_{n\plus{}1}\minus{}x_n\equal{}n\plus{}1$ :

For any real $ a$, there is a unique $ n\equal{}h(a)\in\mathbb{N}\cup\{0\}$ and $ p\equal{}k(a)\in[1,n\plus{}1]$ such that $ a\equal{}\frac{n(n\plus{}1)}{2}\plus{}p$

So, we have $ y\equal{}k(f(x,y))$ and $ x\equal{}h(f(x,y))\minus{}k(f(x,y))$ and $ f(x)$ is injective.


Prove that for $a,b,c\geq0$:

$\displaystyle \sum{\frac{a}{a+1}} \leq \sum{a(\frac{1}{2+a+b}+\frac{1}{2+a+c})}$

[quote="Maverick"]Prove that for $a,b,c\geq0$:

[unparseable or potentially dangerous LaTeX formula][/quote]

 :lol: That's a tricky one...


geometry
perimeter
algebra
polynomial
3D geometry
national olympiad

VietnamMO1997
Day1
1.Let $S$be a circle with center $O$ and radius $R$, and $P$ be a fised point in th plane with $OP=d<R$. Let $ABCD$ be a variable quadrilateral whose diagonals $AC$and$BD$ are perpendicular and meet at $P$.Find the maximum and minimum value of the perimeter of the quadrilateral $ABCD$ in terms of $R$and$d$.
2.Let $n>1$ be an integer not diviseble by 1997.  Define $a_i =i+\frac{in}{1997}$, $i=1,2,...1996$;$b_j=j+\frac{1997j}{n}$, $j=1,2,....n-1$;
Let $(c_k)_{k=1}^{n+1995}$ be the increasing sequence formed of the$a_{i}'s$and$b_{j}'s$.Prove that$c_{k+1}-c_k<2$for all$k$. 3.How many fuctions$f: NàN$are there which satisfy$f(1)=1$and$f(n)f(n+2)=f(n+1)^2 +1997$for all$n$?

Day2
1.(a)Find a polynomial$P$with rational coefficients if th minimum degree such that$P(sqrt[3]3+sqrt[3]9)=3+sqrt[3]3$(b)Does there exist a polynomial$Q$with integer coefficients such that$Q(sqrt[3]3+sqrt[3]9)=3+sqrt[3]3$.?
2.Prove that for each positive integer   $n$there is a positive $m$ suchthat $19^m-87$ is diviseble by $2^n$.
3.Letbe given75 points inside a unit cube ,no three of which are collinear.Prove that there exists a triangle with vertices in these points and area not exceeding $\frac{7}{72}$

\[\text{Day 1}\]
1. http://www.mathlinks.ro/Forum/viewtopic.php?p=786131#786131
2. http://www.mathlinks.ro/Forum/viewtopic.php?p=786132#786132
3. http://www.mathlinks.ro/Forum/viewtopic.php?p=786135#786135
\[\text{Day 2}\]
4. http://www.mathlinks.ro/Forum/viewtopic.php?p=786138#786138
5. http://www.mathlinks.ro/Forum/viewtopic.php?p=786139#786139
6. http://www.mathlinks.ro/Forum/viewtopic.php?p=786140#786140


calculus
real analysis
real analysis unsolved

I find these surprising things about $\pi$ and $e$ , I desire to see how to prove them .

[img]http://bbs.pep.com.cn/attachments/Pi-Continued%20fractions_H9T7JRnbF62F.jpg[/img]

[img]http://bbs.pep.com.cn/attachments/E-Continued%20fraction_4f7P6NSuEsYB.jpg[/img]

I think that  you can solve them by writting these formulaes as terms of a sequence $x_{n}$ and the computing it's limit.The recurrence seem easy to be found.

And this is a calculus problem. :roll:

The $\frac{4}{\pi}$ one is obtained from converting the Wallis product formula $\frac{8}{\pi}= \frac{3\cdot 3\cdot 5\cdot 5 \cdot ...}{ 4\cdot 4\cdot 8\cdot 8 \cdot ...}$ into a continued fraction. I am not sure about the details though  :oops:

I have tried to find the proof on the Internet , but could not get my desired answer .  :(

If you know where I can find it . Please tell me .

Thank you so much .


Would the ARML Handbook be good to study for the Mandelbrot competition???

If not, what would???

The best way to study is certainly to do the previous years' contests.  There are books out there with problems and solutions to many of the previous years.  If I could find them I'd tell you what they're called...

I think one of my teachers has bought a mandelbrot book...

TY :lol:

The books for past Mandelbrot problems are sold on AoPS.  The link is below:
[url]http://www.artofproblemsolving.com/Store/contests.php?contest=mandelbrot[/url]


Demonstrati ca ecuatia $x^n-nx+1=0$ are doua radacini reale $a_{n},b_{n}$ si ca : $
\mathop {\lim }\limits_{n \to \infty } a_n  = 0,\mathop {\lim }\limits_{n \to \infty } b_n  = 1$

E usor de aratat ca ecuatia are doua solutii reale (una in $[0,1)$ si una $>1$, pt $n>2$) si ca cea mai mica e in intervalul $[0,\frac 12)$ pt $n$ suficient de mare, deci $na_n=1+a_n^n\to 0$ cand $n\to\infty$, ceea ce inseamna ca $a_n\to 0$.

Avem acum $b_n>1$ si $b_n^n-nb_n+1=0,\ \forall n$. Se arata si aici usor ca pt $n$ suficient de mare avem $b_n<2$, deci $1<b_n=\sqrt[n]{nb_n-1}<\sqrt[n]{2n}\to 1$, si gata :).

Eh....
Cand am vrut sa pun solutia, am vazut ca deja a mai aparut un post, si e solutia :)
"The hand is faster than the eye" :D

Grobber solutia nu este buna ci este perfecta,multumesc mult pentru ajutorul acordat :lol:


algebra
polynomial
linear algebra
matrix
symmetry
blogs
inequalities

Not sure this is the right forum but here it goes:

In a paper I'm currently working through, (the paper being "Salem numbers, Pisot numbers, Mahler Measure, and Graphs" by McKee and Smith) they say in passing that if $ p(t)$ is the characteristic polynomial of a bipartite graph on $ n$ vertices then $ p( \minus{} t) \equal{} ( \minus{} 1)^n p(t)$ (that is, p is either even or odd). I can't seem to find a reference for this anywhere and this being my 4th day studying algebraic graph theory, am having a little bit of trouble proving it myself  :P, any help would be much appreciated!

Show that $ \lambda$ is a root of $ p$ if and only if $ \minus{} \lambda$ is.  One way to do this is to construct the corresponding eigenvector of the adjacency matrix $ \mathbf{A}$ for $ \minus{} \lambda$ in terms of the eigenvector for $ \lambda$; what does bipartiteness mean for the block structure of $ \mathbf{A}$?  Another is the following lemma.

[b]Lemma:[/b]  The number of closed walks of length $ n$ on a graph $ G$ is the sum $ \lambda_1^n \plus{} ... \plus{} \lambda_k^n$ of the $ n^{th}$ powers of its eigenvalues.

This follows from taking the trace of $ \mathbf{A}^n$.  Since a bipartite graph has no closed walks of odd length, it follows that

$ \lambda_1^n \plus{} ... \plus{} \lambda_k^n \equal{} 0$

for all odd $ n$.  Can you see why this implies the desired result?

Edit:  Incidentally, this paper seems closely related to some ideas I've been having.

Your second approach was something that I had tried to play around with for a while but I was worried about imparting "directed-ness" into the graph when I started considering walks (which, as far as I understand, would alter the form of the adjacency matrix considerably; the first big issue being that we would lose symmetry)? I guess a way to resolve this would be to show that they're co-spectral (if this is even the case...). I'll toy around with the first approach for now and see where that gets me, thanks  :) !

and yes, I thought it was kind of funny that your blog recently has been addressing these issues and I just started a summer research term in a similar field of study! I think your blog will come in handy as a reference.

Come on, let's not use eigenvalues when there is no need to. (Eigenvalue arguments tend to require particular care when talking about discrete objects like graphs - multiple eigenvalues can occur, and since there are only finitely many adjacency matrices of graphs on $ n$ vertices, we cannot invoke continuity or polynomiality unless we pass from graphs to weighted graphs or any other richer structure.)

Number the vertices of the graph in such a way that the vertices of the left shore come first and those of the second shore come last. Then, the adjacency matrix of the graph takes the form

$ \left(\begin{array}{cc}0 & U \\
U^T & 0\end{array}\right)$

for some rectangular matrix $ U$ (here, the two $ 0$'s are square matrices), so we have to prove that

$ \det\left(\begin{array}{cc}tI_p & U \\
U^T & tI_q\end{array}\right)$

is an even or odd (depending on the parity of $ n \equal{} p \plus{} q$) polynomial in $ t$. Now notice that

$ \left(\begin{array}{cc}tI_p & U \\
U^T & tI_q\end{array}\right) \equal{} \left(\begin{array}{cc}tI_p & 0 \\
U^T & I_q\end{array}\right)\left(\begin{array}{cc}I_p & \frac {1}{t}U \\
0 & tI_q \minus{} \frac {1}{t}U^TU\end{array}\right)$.

(Proof idea stolen from Schur complement theory.)

  darij

[quote="max_tm"]I was worried about imparting "directed-ness" into the graph when I started considering walks (which, as far as I understand, would alter the form of the adjacency matrix considerably; the first big issue being that we would lose symmetry)?[/quote]
What do you mean?  The result is true whether or not the graph is directed, and walks are defined the same way in both the directed and undirected cases.  As far as adjacency matrices are concerned, an undirected graph just means a symmetric adjacency matrix, i.e. every edge is two edges.

[quote="max_tm"]and yes, I thought it was kind of funny that your blog recently has been addressing these issues and I just started a summer research term in a similar field of study! I think your blog will come in handy as a reference.[/quote]
This is a very interesting paper.  I'll probably write another post about it since it justifies my suspicion that I was looking at an interesting question and it has a lot of stuff in it that I should've known before writing that post :)  I was just thinking about a graph-theoretic approach to Mahler measure too, so this is perfect.

[quote="darij grinberg"]Come on, let's not use eigenvalues when there is no need to. (Eigenvalue arguments tend to require particular care when talking about discrete objects like graphs - it could always theoretically happen that the respective matrices are non-diagonalizable, and since there are only finitely many adjacency matrices of graphs on $ n$ vertices, we cannot invoke continuity or polynomiality unless we pass from graphs to weighted graphs or any other richer structure.)[/quote]
The lemma is true by the existence of Jordan normal form regardless of whether $ \mathbf{A}$ is diagonalizable.  For example, it gives the right result in the case that $ \mathbf{A}$ is nilpotent.

Edit:  If you're talking about the first approach, then you're right - it's a continuity argument on block matrices of the form you gave because the eigenvector argument fails if the dimensions of the eigenspaces are troublesome without some modification (one must instead show that eigenspaces correspond to eigenspaces, I suppose).  On the other hand, the second approach depends only on the multiplicity of the eigenvalues, so it carries through.

[quote="t0rajir0u"][quote="max_tm"]I was worried about imparting "directed-ness" into the graph when I started considering walks (which, as far as I understand, would alter the form of the adjacency matrix considerably; the first big issue being that we would lose symmetry)?[/quote]
What do you mean?  The result is true whether or not the graph is directed, and walks are defined the same way in both the directed and undirected cases.  As far as adjacency matrices are concerned, an undirected graph just means a symmetric adjacency matrix, i.e. every edge is two edges.[/quote]

I should have noticed it myself...

$ \left(\begin{array}{cc}tI_p & U \\
V & tI_q\end{array}\right) \equal{} \left(\begin{array}{cc}tI_p & 0 \\
V & I_q\end{array}\right)\left(\begin{array}{cc}I_p & \frac {1}{t}U \\
0 & tI_q \minus{} \frac {1}{t}VU\end{array}\right)$.

[quote="t0rajir0u"]Edit:  If you're talking about the first approach, then you're right - it's a continuity argument on block matrices of the form you gave because the eigenvector argument fails if the dimensions of the eigenspaces are troublesome without some modification (one must instead show that eigenspaces correspond to eigenspaces, I suppose).  On the other hand, the second approach depends only on the multiplicity of the eigenvalues, so it carries through.[/quote]

Yes, I was talking about your first proof.

  darij

[quote]What do you mean? The result is true whether or not the graph is directed, and walks are defined the same way in both the directed and undirected cases. As far as adjacency matrices are concerned, an undirected graph just means a symmetric adjacency matrix, i.e. every edge is two edges. [/quote]

hm... I guess I got thrown off because the textbook I was reading through defined walks solely on directed graphs, so I began my reasoning by saying "randomly direct the graph somehow" and then relate the number of cycles in a bipartite graph to the number of closed walks, but then the characteristic polynomials wouldn't be the same. If the results about $ tr(A^r)$ hold for undirected graphs (which I'm pretty sure takes no modifications to the proofs for the directed graphs), then there's no need to screw everything up by directing it.

As for how the last line of the proof, I'm not seeing it right now but I have been staring at this paper for something like 6 hours and I should probably take a look at it tomorrow (same goes for your proof darij, but thank you!).

[quote="max_tm"]the textbook I was reading through defined walks solely on directed graphs[/quote]
Walks on directed graphs include walks on undirected graphs as a special case:  an undirected edge is the same thing as two directed edges, one pointing one way and one pointing the other, at least for the purposes of walks.

Here is the matrix part of my argument, en detail:

[color=blue][b]Theorem.[/b] Let $ R$ be a commutative ring with unity. Let $ X$ be an indeterminate over $ R$, and let $ U\in R^{n\times m}$ and $ V\in R^{m\times n}$, where $ n$ and $ m$ are nonnegative integers. Then, the block matrix $ \left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right) \in\mathrm{M}_{n + m}\left( R\left[ X\right] \right)$ satisfies $ X^{n}\det\left( X^{2}I_{m} - VU\right) = X^{m}\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$.[/color]

[i]Proof of the Theorem.[/i] We have

$ \left( \begin{array} [c]{cc} XI_{n} & 0 \\
V & I_{m} \end{array} \right) \left( \begin{array} [c]{cc} XI_{n} & U \\
0 & X^{2}I_{m} - VU \end{array} \right) = \left( \begin{array} [c]{cc} XI_{n}\cdot XI_{n} + 0\cdot0 & XI_{n}\cdot U + 0\cdot\left( X^{2}I_{m} - VU\right) \\
V\cdot XI_{n} + I_{m}\cdot0 & V\cdot U + I_{m}\cdot\left( X^{2}I_{m} - VU\right) \end{array} \right)$
$ = \left( \begin{array} [c]{cc} X^{2}I_{n} + 0 & XU + 0 \\
VX + 0 & VU + \left( X^{2}I_{m} - VU\right) \end{array} \right) = \left( \begin{array} [c]{cc} X^{2}I_{n} & XU \\
VX & X^{2}I_{m} \end{array} \right)$
$ = X\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$.

Thus,

$ \det\left( \left( \begin{array} [c]{cc} XI_{n} & 0 \\
V & I_{m} \end{array} \right) \left( \begin{array} [c]{cc} XI_{n} & U \\
0 & X^{2}I_{m} - VU \end{array} \right) \right) = \det\left( X\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right) \right)$
[color=green][b](1)[/b][/color] $ = X^{n + m}\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$.

But $ \left( \begin{array} [c]{cc} XI_{n} & 0 \\
V & I_{m} \end{array} \right)$ and $ \left( \begin{array} [c]{cc} XI_{n} & U \\
0 & X^{2}I_{m} - VU \end{array} \right)$ are block-triangular matrices; thus, their determinants are

$ \det\left( \begin{array} [c]{cc} XI_{n} & 0 \\
V & I_{m} \end{array} \right) = \det\left( XI_{n}\right) \det I_{m}$

and

$ \det\left( \begin{array} [c]{cc} XI_{n} & U \\
0 & X^{2}I_{m} - VU \end{array} \right) = \det\left( XI_{n}\right) \det\left( X^{2}I_{m} - VU\right)$.

Thus,

$ \det\left( \left( \begin{array} [c]{cc} XI_{n} & 0 \\
V & I_{m} \end{array} \right) \left( \begin{array} [c]{cc} XI_{n} & U \\
0 & X^{2}I_{m} - VU \end{array} \right) \right)$
$ = \underbrace{\det\left( \begin{array} [c]{cc} XI_{n} & 0 \\
V & I_{m} \end{array} \right)}_{= \det\left( XI_{n}\right) \det I_{m}}
\underbrace{\det\left( \begin{array} [c]{cc} XI_{n} & U \\
0 & X^{2}I_{m} - VU \end{array} \right)}_{= \det\left( XI_{n}\right) \det\left( X^{2}I_{m} - VU\right)} $
$ = \underbrace{\det\left( XI_{n}\right) }_{\substack{ = X^{n}\det I_{n} \\
= X^{n}\cdot1 = X^{n}}}\underbrace{\det I_{m}}_{ = 1}\underbrace{\det\left( XI_{n}\right) }_{\substack{ = X^{n}\det I_{n} \\
= X^{n}\cdot1 = X^{n}}}\det\left( X^{2}I_{m} - VU\right)$
$ = X^{2n}\det\left( X^{2}I_{m} - VU\right)$.

Thus, [color=green][b](1)[/b][/color] becomes

$ X^{2n}\det\left( X^{2}I_{m} - VU\right) = X^{n + m}\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$.

We can divide this equation by $ X^{n}$ (since $ X^{n}$ is not a zero-divisor in $ R\left[ X\right]$), and obtain

$ X^{n}\det\left( X^{2}I_{m} - VU\right) = X^{m}\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$.

This proves the Theorem.

[i]By the way...[/i]
Does the Theorem remind us of anything? It should - it is a lemma in the proof of the known relation between the determinants of $ XI_m - VU$ and $ XI_n - UV$:

[color=blue][b]Corollary 1.[/b] Let $ R$ be a commutative ring with unity. Let $ X$ be an indeterminate over $ R$, and let $ U\in R^{n\times m}$ and $ V\in R^{m\times n}$, where $ n$ and $ m$ are nonnegative integers. Then, $ X^{n}\det\left( XI_{m} - VU\right) = X^{m}\det\left( XI_{n} - UV\right)$.[/color]

[i]Proof of Corollary 1.[/i] The Theorem yields $ X^{n}\det\left( X^{2} I_{m} - VU\right) = X^{m}\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$. But the Theorem (applied to $m$, $n$, $V$ and $U$ instead of $n$, $m$, $U$ and $V$) also yields $ X^{m}\det\left( X^{2}I_{n} - UV\right) = X^{n} \det\left( \begin{array} [c]{cc} XI_{m} & V \\
U & XI_{n} \end{array} \right)$.

Let $ \left( e_{1},e_{2},...,e_{n + m}\right)$ be the standard basis of the free $ R$-module $ R^{n + m}$. Then, the endomorphism of the $R$-module $ R^{n + m}$ which is represented by the matrix $ \left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$ in the basis $ \left( e_{1},e_{2},...,e_{n + m}\right)$ is identic to the endomorphism of the $R$-module $ R^{n + m}$ which is represented by the matrix $ \left( \begin{array} [c]{cc} XI_{m} & V \\
U & XI_{n} \end{array} \right)$ in the basis $ \left( e_{n + 1},e_{n + 2},...,e_{n + m},e_{1},e_{2},...,e_{n}\right)$. Hence, the matrix $ \left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)$ is similar to the matrix $ \left( \begin{array} [c]{cc} XI_{m} & V \\
U & XI_{n} \end{array} \right)$. Thus, $ \det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right) = \det\left( \begin{array} [c]{cc} XI_{m} & V \\
U & XI_{n} \end{array} \right)$. Consequently,

$ \left( X^{2}\right) ^{n}\det\left( X^{2}I_{m} - VU\right) = X^{2n}\det\left( X^{2}I_{m} - VU\right)$
$ = X^{n}\cdot \underbrace{X^{n}\det\left( X^{2}I_{m} - VU\right)}_{= X^{m}\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)}$
$ = X^{n}\cdot X^{m}\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right) = X^{m}\cdot X^{n}\underbrace{\det\left( \begin{array} [c]{cc} XI_{n} & U \\
V & XI_{m} \end{array} \right)}_{= \det\left( \begin{array} [c]{cc} XI_{m} & V \\
U & XI_{n} \end{array} \right)}$
$ = X^{m}\cdot \underbrace{X^{n}\det\left( \begin{array} [c]{cc} XI_{m} & V \\
U & XI_{n} \end{array} \right)}_{= X^{m}\det\left( X^{2}I_{n} - UV\right)} = X^{m}\cdot X^{m}\det\left( X^{2}I_{n} - UV\right)$
$ = X^{2m}\det\left( X^{2}I_{n} - UV\right) = \left( X^{2}\right) ^{m}\det\left( X^{2}I_{n} - UV\right)$.

In other words,

$ \Phi\left( X^{n}\det\left( XI_{m} - VU\right) \right) = \Phi\left(X^{m}\det\left( XI_{n} - UV\right) \right)$,

where $ \Phi: R\left[ X\right] \rightarrow R\left[ X\right]$ is the map which transforms every polynomial $ p\left( X\right) \in R\left[ X\right]$ into the polynomial $ p\left( X^{2}\right)$.

But this map $ \Phi$ is injective (since for any polynomial $ p\left( X\right) = \sum\limits_{i = 0}^{k}a_{i}X^{i}\in R\left[ X\right]$, we have $ \Phi\left(p\left( X\right) \right) = p\left( X^{2}\right) = \sum\limits_{i = 0}^{k}a_{i}\left( X^{2}\right) ^{i} = \sum\limits_{i = 0}^{k}a_{i}X^{2i}$, so that $ a_i$ is the coefficient of the polynomial $ \Phi\left(p\left( X\right) \right)$ before $ X^{2i}$ for every $ i\in\left\{0,1,...,k\right\}$, and thus
$ p\left( X\right) = \sum\limits_{i = 0}^{k}a_{i}X^{i} = \sum\limits_{i = 0}^{k}\left(\text{the coefficient of the polynomial }\Phi\left(p\left( X\right) \right)\text{ before }X^{2i}\right)X^i$,
and hence $ p\left( X\right)$ can be reconstructed from $ \Phi\left( p\left( X\right) \right)$, so that $ \Phi$ is injective). Hence,

$ \Phi\left( X^{n}\det\left( XI_{m} - VU\right) \right) = \Phi\left(X^{m}\det\left( XI_{n} - UV\right) \right)$

yields

$ X^{n}\det\left( XI_{m} - VU\right) = X^{m}\det\left( XI_{n} - UV\right)$,

and Corollary 1 is proven.

[color=blue][b]Corollary 2.[/b] Let $ R$ be a commutative ring with unity. Let $ X$ be an indeterminate over $ R$, and let $ U\in R^{n\times n}$ and $ V\in R^{n\times n}$, where $ n$ is a nonnegative integer. Then, $ \det\left( XI_{n} - VU\right) = \det\left( XI_{n} - UV\right)$.[/color]

[i]Proof of Corollary 2.[/i] Corollary 1 (applied to $ m=n$) yields $ X^{n}\det\left( XI_{n} - VU\right) = X^{n}\det\left( XI_{n} - UV\right)$. We can divide this equation by $ X^{n}$ (since $ X^{n}$ is not a zero-divisor in $ R\left[ X\right]$), and obtain $ \det\left( XI_{n} - VU\right) = \det\left( XI_{n} - UV\right)$. This proves Corollary 2.

Corollary 2 can be regarded as a generalization of [url=https://en.wikipedia.org/wiki/Sylvester's_determinant_identity]Sylvester's determinant identity[/url].

  darij

[quote="max_tm"]Sorry, I'm still not seeing the last step of the proof (that is, how to progress past the point where we have that the odd powers of the roots sum to zero).[/quote]

Given $ n$ elements $ x_1$, $ x_2$, ..., $ x_n$ of a field $ k$ with characteristic $ 0$. You know that $ \sum_{i\equal{}1}^nx_i^r\equal{}0$ for every odd $ r\in\left\{1,2,...,n\right\}$. You want to prove that $ x_1$, $ x_2$, ..., $ x_n$ are the roots of an even or odd polynomial.

It is clearly enough to show that for every odd $ r\in\left\{1,2,...,n\right\}$, the $ r$-th elementary symmetric polynomial of $ x_1$, $ x_2$, ..., $ x_n$ is zero (because then, you can apply Viete).

How to show this? The power sums generate the algebra of all symmetric polynomials in $ n$ variables over $ k$ (here we need $ \mathrm{char}k\equal{}0$), so in particular, the elementary symmetric polynomials are polynomials of the power sums. Look deeper - what can you say about odd-degree elementary symmetric polynomials?

  darij

Equivalently, let $ s_r \equal{} \sum_{i \equal{} 1}^{n} x_i^r$.  Then

$ \sum_{r \equal{} 0}^{\infty} s_r t^r \equal{} \sum_{i \equal{} 1}^{n} \frac {1}{1 \minus{} x_i t}$

is a power series with only even powers of $ t$.  What does this tell you about the denominator of the RHS, written as a single fraction?

Here's a third argument:  if the largest positive eigenvalue is strictly larger in absolute value than the largest negative eigenvalue, $ \lim_{r \to \infty} s_r \equal{} \plus{} \infty$, which contradicts $ s_{2r \plus{} 1} \equal{} 0$.  Thus the largest positive and negative eigenvalues must have the same multiplicity and absolute value.  Now if the second largest positive eigenvalue and the second largest negative eigenvalue...

Bah, I seem to have a very serious mental block (and probably a gap in basic knowledge as well  :blush: ) that's just not letting me make a break through with the rest of this proof. I went back to t0rajir0u's first method (that is, explicitly constructing an eigenvector that corresponds to $ \minus{}\lambda$) which you can show would be the vector $ (a,\minus{}b)$ (imagine these as being column vectors) where $ (a,b)$ is an eigenvector corresponding to $ \lambda$ (here the first "block component" corresponds to values of $ f$ at each node in one bi-partition and the second "block component" to the values of $ f$ in the second bi-partition where $ f$ is a function that maps the points in the vertex set to real numbers and $ A$ is interpreted as a linear operator on the vector space of these functions $ f$). Then I noticed your discussion about this method (which, unfortunately went over my head  :P) so now I'm wondering if this suffices?

[quote="max_tm"]Bah, I seem to have a very serious mental block (and probably a gap in basic knowledge as well  :blush: ) that's just not letting me make a break through with the rest of this proof. I went back to t0rajir0u's first method (that is, explicitly constructing an eigenvector that corresponds to $ \minus{} \lambda$) which you can show would be the vector $ (a, \minus{} b)$ (imagine these as being column vectors) where $ (a,b)$ is an eigenvector corresponding to $ \lambda$ (here the first "block component" corresponds to values of $ f$ at each node in one bi-partition and the second "block component" to the values of $ f$ in the second bi-partition where $ f$ is a function that maps the points in the vertex set to real numbers and $ A$ is interpreted as a linear operator on the vector space of these functions $ f$). Then I noticed your discussion about this method (which, unfortunately went over my head  :P) so now I'm wondering if this suffices?[/quote]

It suffices for the problem, because:
[b](1)[/b] the adjacency matrix of a graph is symmetric, and thus diagonalizable (i. e., the algebraic multiplicities of the eigenvalues equal to their geometric multiplicities);
[b](2)[/b] you have explicitely constructed an [i]isomorphism[/i] between the eigenspaces of $ \lambda$ and $ \minus{} \lambda$ for any eigenvalue $ \lambda$.

But without any of [b](1)[/b] and [b](2)[/b], your argument would not suffice:
If [b](1)[/b] would not be fulfilled, your argument would fail for the matrix $ \left(\begin{array}{ccc}1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1\end{array}\right)$, which has both minimal and characteristic polynomial equal to $ \left(X \minus{} 1\right)^2\left(X \plus{} 1\right)$; in this case, the eigenspaces for the eigenvalues $ 1$ and $ \minus{} 1$ would still be isomorphic, but the characteristic polynomial is obviously neither odd nor even.
If [b](2)[/b] would not be fulfilled, the matrix $ \left(\begin{array}{ccc}1 & 0 & 0 \\
0 & \minus{} 1 & 0 \\
0 & 0 & \minus{} 1\end{array}\right)$ would be a counterexample - it is symmetric, and whenever $ \lambda$ is an eigenvalue, so is $ \minus{} \lambda$. But the eigenspaces are of different size.

There is a good reason why proofs using Jordan form and eigenvalues are considered tasteless...

@t0rajir0u: Could you please explain the last step in your power series argument in more detail? I don't see where $ \mathrm{char}k\equal{}0$ can be applied (or is it unnecessary if we take into account [i]all[/i] odd power sums)?

  darij

[quote="darij grinberg"]@t0rajir0u: Could you please explain the last step in your power series argument in more detail?[/quote]
In hindsight, it's easier to argue as follows:  the fact that the power series is even implies that

$ \sum_{r\equal{}0}^{\infty} s_r t^r \equal{} \sum_{i\equal{}1}^n \frac{1}{1 \plus{} x_i t}$

and then one uses the uniqueness of partial fraction decompositions.  This argument clearly fails in characteristic $ 2$ and I don't think it's true in general characteristic either, but over $ \mathbb{C}$ it's very easy to prove uniqueness:  just look at the limiting behavior as $ t \to \frac{1}{x_i}$ for any $ x_i \neq 0$ and as $ t \to 0$ for any $ x_i \equal{} 0$.

I think we can keep the ideas in Qiaochu's original proof without getting overly technical as follows:

We know from linear algebra that the characteristic polynomials of $ A$ and $ PAP^{ \minus{} 1}$ are the same. So let $ A$ be the adjacency matrix and let $ D$ be the diagonal matrix with $ D_{ii} \equal{} 1$ if vertex $ i$ is in one side of the bipartition and $ D_{ii} \equal{} \minus{} 1$ if $ i$ is on the other side. Then $ DAD^{ \minus{} 1} \equal{} DAD \equal{} \minus{} A$ (this is really the part that requires some work, but I think the easiest way to do it is to note that every edge has exactly one endpoint in each side of the bipartition).

So the characteristic polynomial of $ DAD^{ \minus{} 1}$ is the characteristic polynomial of $ \minus{} A$. On the other hand, it is also the characteristic polynomial of $ A$, so $ p(A,t) \equal{} p( \minus{} A,t)$, if $ p(M,t)$ is the characteristic polynomial of $ M$. But $ p( \minus{} A,t) \equal{} ( \minus{} 1)^n p(A, \minus{} t)$, so $ p(A,t) \equal{} ( \minus{} 1)^n p(A, \minus{} t)$, which is what we wanted.

What we are doing is basically making use of the self-symmetry of the eigenspaces that Qiaochu noted to gain an algebraic identity using the invariance of the characteristic polynomial under conjugation.


trigonometry
AMC
AIME
USA(J)MO
USAMO
ARML
AMC 10
\/closed

This is just a list of some classes I'd like offered as problem series classes. Please feel free to add to it if you guys wish. I think it's pretty important that the instructors know what type of competitions we're looking forward to attending and which ones we'd like courses on.

AMC 10 and 12 (seperate classes for both since 12 has more challenging concepts like Trig involved. Late Fall/Winter would be my preference.)

AIME I and II (I for easier problems and II for harder ones since AIME has problems of all sorts of difficulties. I ASAP and II probly in the spring before AIME is my recommendation.)

USAMO (Also probly spring b/c if it was in the summer as was suggested on another log, it really might not help those of us who are preparing this year. I'm interested in having these classes before another chance goes by for the USAMO.)

Harvard/MIT/Stanford/Rice competition (http://web.mit.edu/hmmt/) (This class would probably also be best in spring)

ARML (for those doing ARML... late spring)

Remember, those were just the times and classes I'd like. Please feel free to add your opinions and convient times as they will most likely be different from mine.

Now my other idea which would have to be approved by the instructors is "AoPS Weeks"...allow me to explain...

During the school year, many of us are busy with the courses we already have and wouldn't be able to attend them. AoPS Weeks would solve their problems. There are specific weeks in the year when almost everybody in the nation is our of school (Thanksgiving, 2 weeks for Christmas, Spring Break, etc). On these weeks, we could have 6-day Problem Series classes with 2 1.5-hour sessions a day (I think a 3-hr session may be too long. So perhaps two 1.5-hr sessions with like a few hours in between. Perhaps the instructor could leave us with some problems at the end of the first session and we could discuss solutions in the second session). Just my idea. Since most AoPSer's would be spending quite a bit of time on math during vacations anyways, why not spend it in an organized discussion?

Please point out faults to me (as im sure there are quite a few since this is a last-minute idea). However, I'd like to see some form or another of something like what I just described above.

We will over time build many more Problem Series classes - thanks for the suggestions on where we should focus.

As for the AoPS week classes - we would certainly look into doing it *if there was sufficient interest*  (i.e. if we could enroll at least a couple dozen students).  We would also consider such 'crash courses' during the summer, again if there is sufficient interest.

As we are just getting started, a lot of these ideas/classes may have to wait until next year (or later), but we are happy to hear suggestions.


function
inequalities
inequalities proposed

Prove that if $g(x)=f(\frac{1}{x^2})$ is a convex function on $(0,\infty)$, then $h(x)=xf(x^2)$ is also a convex function on $(0,\infty)$.

It is case p=3 in the EV Theorem(I mean in the proof). Is it correct? I can post a solution, but firs i would like to see if my intuition is correct

It's actually pretty easy.

Let $ f :\left( 0,\infty\right)\to\left( 0,\infty\right)$ be a convex function and define $ g(x) \equal{} x\cdot f\left(\frac{1}{x}\right)$.

I want to prove that $ t\cdot g(a)\plus{}(1\minus{}t)\cdot g(b)\geq g\left( ta\plus{}(1\minus{}t)b\right)$, for all $ t\in [0,1]$.

Let's fix the $ LHS$. How can we make the $ RHS$ bigger? By increasing $ f\left(\frac{1}{ta\plus{}(1\minus{}t)b}\right)$ of course. Since $ \frac{1}{b}\leq\frac{1}{ta\plus{}(1\minus{}t)b}\leq\frac{1}{a}$, the biggest value that $ f\left(\frac{1}{ta\plus{}(1\minus{}t)b}\right)$ can take lies on the line passing through $ \left( a, f\left(\frac{1}{a}\right)\right)$ and $ \left( b, f\left(\frac{1}{b}\right)\right)$.

Hence, we may assume that $ f(x) \equal{} ux\plus{}v$. Then, $ x\cdot f\left(\frac{1}{x}\right) \equal{} u\plus{}vx$, which is indeed convex. Hence, the $ g$ "convex inequality" holds for the [i]arbitrary[/i] triple $ (a,b,t)$.

So $ g$ is convex.

Yes, indeed. I thought that instead of f, it was the derivate of function f. It would change the proof, but the main ideea is still the same. That is why i was thinking about the EV-theorem. I do believe that mr. Vasc was thinking about the derivate of function f.


Hi,

I've been trying to solve the contact problem (USACO - Section 2) but am having severe time issues.

I go over the time limit for test case 5.

My current algorithm is as follows:

1. Scan all strings (in the given string) of a given length while maintaining a count for each one.
2. Sort this and pick out the highest few (exact number is decided on the basis of problem input)
3. Put all the strings of different lengths in a single array and then sort again
4. Output

I have attached my c++ program.

Please help!!!

Thanks

Hm... Sorting is not necessary here...

The "main" problem here is to convert a string of 0 and 1 to a integer... For example:

01101 can be converted to 0 * 16 + 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1 = 13.

But, there's still a little problem... 1101 is also converted to the same integer!

But, by adding a "1" in front of the string, i.e. 101101 instead of 01101, and 10 instead of 0, all such strings will be unique...

So, how can this help you?

Well, create a variable named "int stringCount[]" and for every string with length between A and B, increase stringCount[stringToIntID]... :D

This is my first problem where i got stuck. yes! weebie is right. i saught help from rob and he gave me that!

I'm stuck here right now, too! But I got stuck a while back, and then started school + math practice so USACO kind of got lost.

I was thinking of converting the strings into ints last night just didn't want to take the trouble of implementing it without being sure.

Anyway, I'll try this and see what happens.

Thanks

well i advise u to use bit wise operation. it is quite ezer and handy. and it will make ur code ez! :D

I tried what you guys suggested.

When I ran my new program the first time it ran in 1.13 secs but now it takes 1.22 secs (god knows why!)

Anyway can you please help me cut this down further??

And how do I use bitwise operations (and what are they)

Thanks a ton

P.S. - I have attached my new code

well, if u r making binary to integer conversion by mathematics (by multiplying by 2 and then...) then it must get TLE. u have to use bit wise operation!

but i can't give u details of it. u know tomorrow is my exam and it will be very tough Chemistry 2nd part (including organics :( )

Anyhow, i just give some of them that u need to use at this coding:

<< (shift left) 5<<1 means: 5=101, so add another 0 bit on the last: 101<<1 = 1010. that means: 5<<1 = 10. same way: 5<<2 means 10100 in binary and ... in decimal

>> (shift right), same as above but this time one bit from right will be deleted.

(note if u use 5<<1 u will get the resul in decimal not in bin)

| (bitwise or), & bitwise and

i think these four r enough. now plz make a search over yahoo. or google. or consult a book. i hope u will be claer more!

I apologise for my time problem :blush:

Ok, i tried using the bitwise shift as mahbub suggested, it reduced execution time from 0.12 secs to 0.3 secs for the 4th test case.

BUT, for the fifth case the program now takes more than 2 SECONDS (God knows why!).
However, if I add a simple diagnostic cout statement somewhere the program runs and ENDS in 1.82 seconds.

This is driving me crazy!!!

PLEASE HELP
P.S - I have written a mail to Rob Kolstad too.

The zip file contains 3 code files - one with the normal power function (runs in 1.22 for last case), one with bitwise shifts (time gets exceeded at 2 secs) and one with bitwise shifts and diagnostic cout statement (runs in 1.83 for the last case)

umm.. sorry! tomorrow is my exam. so i will help u after that! plz don't mind. even i can't continue my usaco for it! :mad:

ok, thanks a lot anyway

are u going to ioi too?

i have been selected for my country's camp (India, i see that v r neighbours) which will take place from 15th to 30th June.

I have holdiays right now so am relatively free

anyway will wait for u

Well say thanks to your creator. You have made such mistakes (not actually mistake but unefficiency) which were very easy to locate. So I can show you the right path now(without thinking much)!

Well, you have taken input entirely. No don’t do this. Look it is sufficient if u manage taking B digits at a time. How can you do this?

Say B=3. and in input file you are given:

1001001

now you are talking input one digit by one digit:
1-10-100-001-010-100-001 OK? Just keeping 3 digits in your hand!

Each time (after first B digits) you look for digits A to B. and update your counter. Then sort and print.

Another think you have checked A to B separately. You don’t need to that as well!

Say you are given A=2, B=5 and in input: in=11011011, now when you take first B 11011 now take every 2 to 5 from top. Then update your in by taking next digit and deleting first digit. And take care about beginning and ending!

I know you may not understand every thing clearly. But sorry I can’t spend much time on it now! Sorry!

***r u indian? so why ur flag says england?

well, i will be glad if u post indian IOI selection test problems!

yes i am going to IOI (IMO too)

Hm... Posted my solution, if you want some hints... :D

Btw, do NOT use iostream to read big inputs... You are reading it "character for character" with iostream which must be avoided. The "reading part" itself might be too slow for the biggest test case... Try to learn the C style to read/write data instead (scanf/printf). :D

mahbub: Nice! Will see you twice then. ;)

Weeblie: your code is way too complex for me too understand!!!
I will look into the scanf, printf thing too.

mahbub: Take your time. You can tell me tomorrow (or i hope so, if u don't have another exam!).
I am not sure I quite understand what u r saying but i think it something like this -
i take in the first b digits and process it for all strings with length from a to b. then do a bitwise left shift and then take in another digit and reprocess the string?

ohh and you can find the problems from the indian olympiads on http://www.iarcs.org.in

I also had a more general question - is it useful for IOI to know things like queues, stacks, linked lists etc?
I ask this because the person who coaches the Indian team for IOI said that we don't need to learn any 'fancy' things and arrays will do fine. But lots of things like BFS,DFS seem to use queues and stacks.

P.S. - my flag says england b/c i am using somebody else's login - i was too lazy to make my own

Thanks once again

The STL classes (vector/queue/stack/deque/list, etc) is not 100% necessary, but can save a lot of time. Especially if you know how to use hash_map/hash_set (different on VC++ and GCC!).

A lot of people is still writing C code in IOI, without all these nice classes... :D

mahbub: can u please explain again in detail what i have to do as i am not yet clear what you said

or weeblie: can u explain what to do?

thanks


inequalities function symmetry algebra domain

given $0\le a,b,c\le 1$,
prove:
$\frac{a}{1+bc}+\frac{b}{1+bc}+\frac{c}{1+ab}\le 2$

yes, it should be. :wink:

[hide="big hint"]
wlog, assume: $0\le a\le b\le c\le 1$
$\Rightarrow 0\le (1-a)(1-b)$
$\Rightarrow a+b\le 1+ab\le 1+2ab$
$\Rightarrow a+b+c\le a+b+1\le 2+2ab$[/hide]

[b]Solution.[/b] The function
\[f(a,b,c)=\frac{a}{1+bc}+\frac{b}{1+ac}+\frac{c}{1+ab}\]
is a sum of convex functions (by symmetry, consider $\frac{\partial^{2}}{\partial a^{2}}\frac{a}{1+bc}$ and $\frac{\partial^{2}}{\partial b^{2}}\frac{a}{1+bc}$) so $f(a,b,c)$ is convex.
By Weierstrass' Theorem, a continuous function defined on a closed and bounded domain assumes its maximum and minimum.
For a convex function, maximum value is obtained at at least one of the $2^{3}$ vertices.  Considering $f(0,0,0),f(0,0,1),\hdots,f(1,1,1)$ by symmetry, a maximum of $2$ is obtained.

And the conclusion follows.$\blacksquare$

Masoud Zargar

[hide="what? calc?!"]
WLOG let $a\geq b\geq c$, which we can assume since the expression is symmetric. And now we just...
\[\frac{a}{1+bc}\leq a\leq 1\]
\[\frac{b}{1+ac}\leq \frac{b}{1+bc}=\frac{b}{b+c+(1-b)(1-c)}\leq \frac{b}{b+c}\]
\[\frac{c}{1+ab}\leq \frac{c}{1+bc}=\frac{c}{b+c+(1-b)(1-c)}\leq \frac{c}{b+c}\]
Add them up!  :D
[/hide]

[hide="its really easy"]
from my previous "big" hint.

$LHS\le\frac{a}{1+ab}+\frac{b}{1+ab}+\frac{c}{1+ab}=\frac{a+b+c}{1+ab}\le 2$

 :wink: [/hide]


$F_{n}$ is fibonacci 's $n^{th}$ number: $F_{1}=F_{2}=1$, $F_{n+1}=F_{n}+F_{n-1}$ Prove that if and if only $F_{n}^{2}\mid{F_{m}}$ then $nF_{n}\mid{m}$.

$F_{n}=\frac{\alpha^{n}-\beta^{n}}{\sqrt 5 }, \ \alpha=\frac{1+\sqrt 5 }{2}, \ \beta=\frac{1-\sqrt 5 }{2}.$
Therefore $F_{n}^{2}|F_{m}\to F_{n}|F_{m}\to n|m$ and $m=nk, \ \frac{F_{m}}{F_{n}}=\sum_{i=0}^{k-1}\alpha^{n(k-1-i)}\beta^{ni}\equiv k\alpha^{n}\mod F_{n}$, because $\alpha^{n}=\beta^{n}(mod F_{n})$.
Therefore $F_{n}^{2}|F_{m}\to F_{n}|\frac{m}{n}$. It is easy to check, that $nF_{n}|F_{m}\to F_{n}^{2}|F_{m}$.


A student has six textbooks, each with a thickness of 4.0 cm and a weigh of 30 N. What is the minimum work the student would have to do to place all the books in a single vertical stack, starting with all the books on the surface of the table?

[hide="Hint"]The first book is already on the table so we don't have to move it. The second book must be raised to a height of 4 cm. The third book must be raised to a height of 8 cm. And so on. Now a question: in each raising operation, to which is equal the work done?[/hide]


probability
function
search
logarithms
conics
ellipse
geometric series

How many ways for 12 people to seat at a round table?
How many ways for 12 different colored beads placed on a bracelet?
Is above two questions same?

For the first question, fix any one person. Seats aren't numbered, so the remaining people can be arranged in $ 11!$ ways.

For the bracelet, it is $ \frac {11!}{2}$ because mirror images are the same as the bracelet can be flipped around. However, the relative positions of the beads matter and the absolute positions do not.

[quote="linj"]Another Question:
How many generations must you go back before you have at least one million ancestors, assuming that there were no intermarriages among relatives?(Use log(2)=0.30)[/quote]
One more question:
Why hyperbolic function is too similar to trigonometric function? Is not is confuse? How you distinct them?

[quote="aidan"]Does your definition of ancestors include all generations? Or just the current generation we are considering? (E.g. in going back 2 generations I have only 4 ancestors: grandparents on mother's and father's side, while if you consider parents included, I have 4 + 2 = 6 ancestors).

You can search "hyperbolic functions" in http://en.wikipedia.org and check it out  :D[/quote]
I think of when two generation come back is 6 ancestors.

[quote="aidan"]In that case, we want to know when $ 2 \plus{} 2^2 \plus{} 2^3 \plus{} \ldots \plus{} 2^n \geq 1,000,000$. By the geometric series formula, this is equivalent to $ \frac {2(2^n \minus{} 1)}{2 \minus{} 1} \geq 1,000,000$. So $ 2^n \geq 500,001$ and taking logs on both sides, $ n \log 2 \geq \log 5 \plus{} 5 \log 10$ (approximately). So $ n \geq \frac {5.699}{0.301} \equal{} 18.9$. Therefore we must go back at least $ \boxed {19}$ generations.[/quote]
your answer is same as mine, however, the answer key has answer: 20.

If the answer is 20, it means ancestors in the generations before the 20th are not considered.. Only the ancestors of 20 generations ago (not 19, 18, etc) are counted

[quote="linj"]1.The sides of triangle ABC lie on the lines:
   3x+4y=0
   4x+3y=0
   x=3
   Let (h,k) be the center of the circle inscribed in triangle ABC.
   Find h+k.
2. A chessboard is an 8*8 grid. If a chessman is onthe bottom left square, how many paths may he take to the top right square if he moves only up and to the right.
    Given the 4*6 grid shown, in how many way can one go from the bottom left corner to the upper right corner along the lines if one can only go up and right?
Are these two question same?
3. How many times does the graph of the function f(x) = 2*x^8-3*x^5-2*x^3-2 cross the x-axis? (without the calculator)[/quote]
One more:
A tunnel in the shape of a semi-ellipse is sixty feet wide and twelve yards high in the center. Find its height (in feet) six feet from the edge.

@ linj - Each question should have it's own topic. If a topic has several unanswered questions at once, discussion can get very confusing.

@ mods - If it's not too tedious, please split the unanswered questions into separate topics.


Is there a nonempty perfect set in $ \mathbb{R}^1$ which contains no rational number?

A set is perfect if it is closed  and if every point is a limit point of the set, and $ \mathbb{R}^1$ has the standard topology.

Yes, see [url=http://planetmath.org/encyclopedia/ANonemptyPerfectSubsetOfMathbbRThatContainsNoRationalNumber.html]here[/url].

Alternatively, I believe the previous problem contains a clue as to how you would construct another one.


Let $C_1,C_2$ be tangent together at $M$. Let $M$ be a point on $C_1$ . Draw the tangents from $M$ to $C_2$ at $A,B$ . Let $AM$ intersect $C_1$ at $E$ and $BM$ intersect $C_1$ at $F$ . Let the tangent from $M$ to $C_1$ intersect $EF$ at $D$ . find the locus of $D$ if $M$ be variant on $C_1$ .

Could you please clarify it? You have two different definitions for $M$ (first it's the point where the circles touch each other, and then it's a variable point).

[quote="behzad"]...Let $M$ be a point on  ...[/quote]
I think it must be $N$.

If  2nd $M$ is $N$. I just solve the problem
It is easy and not nice.
 :D

the locus of D is on line tangent at two circles at $M$.

tangent two lines at E and F on $C_1$ let them intesect at $N'$ .
It's easy to see that $N,M,N'$ are collinear.
$\frac{N'M}{NM}$ is constant.so the locus of N' is a circle tangent to $C_1$ at $M$.
so the problem bacome this(as darig):

[color=blue][b]Extendedproblem.[/b] two circles $C,C'$ tangent together at M. from a variable point N on C draw tangent $\ell$ at C and NM intersect C' at N'. from N draw two tangent NE and NF to C .find that locus of $D=EF\cap \ell$[/color]

[i]Solution.[/i]polar of N' pass through D so the polar of D pass trough N'.therefore DM is tangent to two circles.


search
number theory unsolved
number theory

Show that if x, y, z are positive integers , and (xy+1)(yz+1)(zx+1) is a perfect square then  xy+1, yz+1 and zx+1 are all perfect squares.

plz search before posting
it is PEN A1,go there...http://www.mathlinks.ro/viewtopic.php?t=150369


prove for every positive a,b,c

3^(1/2)*((a+b)(a+c)(b+c))^1/3 >= 2(ab+ac+bc)^1/2

You can use the inequality:
9(a+b)(b+c)(c+a) \geq 8(a+b+c)(ab+ac+bc) to prove this one....

let f =27[(a+b)(b+c)(c+a)] 2 -64(ab+bc+ca)^3
      g=27 [(b+ \sqrt ac)^2(2 \sqrt ac]^2-64(ac+2b \sqrt ac)^3
 we prove g \geq 0 f-g \geq 0 then f \geq 0


Your best friend, your lover, and yourself are trapped on a deserted island out in the middle of nowhere. The relationship between your best friend and you is a truly deep one: you have known each other for many years, and you both trust and can depend on each other very greatly. Your lover is a person whom you really adore, and he/she has a similar affection for you.

One day, you are captured by a tribe of cannibals. They are hungry and want to eat, but they are also nice cannibals and do not like to capture more humans than necessary for each meal (I know, this sounds weird, but play along with me here). They say that you (and you alone), must choose one of your two companions to sacrifice. This companion will be slaughtered and eaten by the cannibals, while your other companion and yourself will be free to leave.

Who would you choose to sacrifice?

You know, I realized how stupid this question is right after I posted it, since you can't possibly decide without being given two specific companions. So why don't we make this change:

Replace the friend with three random students from your school. You are barely acquainted with them. They are not your friends, but not your enemies either.

[quote="Fierytycoon"]Replace the friend with three random students from your school. You are barely acquainted with them. They are not your friends, but not your enemies either.[/quote]

now we've got ourselves a dilemma, I'm definately saw this ethics question on Mathlinks, with Mother Teresa versus 5 teenagers.

Let's see, in the original case I'd kill my best friend, in the second one I'll slaughter the three random kids, and in the third one I'd butcher the five teenagers if Mother Teresa doesn't kill herself before then.

this question isn't that hard
just think about it: without your lover, what are you going to do for the rest of your days on this deserted isle. all of you are going to die eventually anyway.

yes, but does your lover have any more right to live than the three kids?

i was kind of joking and, no, my lover doesn't have any more right to live than the three kids. ethics questions are kind of irrelevant without actual people.

I'd have to say that the three kids I don't know have less meaning to me than my lover. After all to the kids' parents their kids would probably mean more to them, but since it's me choosing and not them, the lover it is.


haha, funny topic.

In what frame of reference?

regular frame I guess.

My vertical is 34 inches.

Regular frame, eh?  Now what does that mean?
In some frames of reference, I've jumped several meters.  In other, I've jumped negative distances.  In some frames, I've jumped in a circle of radius one mile.

[quote="juicybooty911"]54inches, i dunk better than jordan[/quote]

Yeah right.

[quote="juicybooty911"]54inches, i dunk better than jordan[/quote]

Interesting fantasy you have there.

Mines about 15 inches(not bad for a 12 year old!!!!!!!!!!!!!)

[quote="robinhe"][quote="K81o7"]I'm finding it hard to measure here, and I'm too lazy to get all of the equipment and all, but I guess the height my feet come off of the ground when legs are straight is somewhere between 2 and 3 feet...

Okay, upon measurement, about 30 inches...[/quote]

That's very unnatural...[/quote]

How so?

Unless you're training for the Olympics...

Do you realize how much 30 inches is?  That means that if you are about 5'10, you can dunk on a standard 10' basketball hoop.

@robinhe: nice 1000 posts!

to _____: u prob beneded ur legs when u measured 30 inches :wink:
jorian

[quote="K81o7"]I'm finding it hard to measure here, and I'm too lazy to get all of the equipment and all, but I guess the height my feet come off of the ground when legs are straight is somewhere between 2 and 3 feet...

Okay, upon measurement, about 30 inches...[/quote]

Supernatural......

mine is only about 10

Wait...are you sure?  I checked it and confirmed what it was.  Maybe I'll take a video and use that to make sure I'm measuring correctly...

Besides, mdk said 34 inches.  That I can believe...

Edit: Okay, I think I may have found a feasible solution.  Maybe my spine is bending over a little bit...and my feet are going out...

In any case, it's probably not less than 2 feet.

I'm a track runner: I can believe that...

I'll try instead jumping and then marking where the top of my head reached, and then measuring the distance to that and subtracting my height...then I'll get back to you all...

Edit 2: Okay, after measurement with this method, about 25 inches.  I'll get back to you if I can do better than that (track season starts on wednesday, so in a couple months, that may be up a few inches).

Besides, you say that 30 inches is crazy?  I can jump about 25 inches, and my brother can probably jump a couple inches higher than that: probably about 30.

[quote="k8reindeer"]use lo-tack masking tape. stick a peice where your fingertips touch, stick another peice at the height of your jump, and then use a stool and measure.

how high of a wall are you doing this on, by the way?[/quote]

If you're asking me, it was a gym wall so naturally it was about 50 ft high or so.

[quote="robinhe"]You're probably getting a running start.

That doesn't count.  Stand against the wall and then just jump.  See how much that is.[/quote]

I'm standing still and jumping.  Am I not allowed to bend my knees or something?  Do you guys want me to make a video of this if you don't believe it?

[quote="mustafa"]That's probably it. You aren't supposed to bend your knees. Try reaching up and touching the wall, figuring out how high that is, then jumping and seeing how much higher you can reach.

I'm at about 18 inches I think.[/quote]

ie jumping by only using your ankles?  I'm talking about the jump itself.  Is that what you mean?  Read my previous posts before posting...

Trust me, I'm making an accurate measurement...
And yes, by using the hand reaching method, I'm still getting 25-26 inches.

You are allowed to bend down, or no one will have a 50 inch vert because it will require too much power.

I find it funny that people are doubting a 25 inch jump, but are unfazed by a 34 inch jump.

Vince Carter has s a 42 inch vertical, and he is 6'6''. Talk about hangtime and crazy dunks.

mine is 28. I had it measured in a physical thing. I am tall and 5'10 and way 125 pounds, and I run like... tons.  :D

running's just my way of life.

strong legs.

Mine should be around a foot - not bad at 5'7.5", eh?


topology
function
calculus
derivative
linear algebra
matrix
analytic geometry

I'm completely stuck on this problem:

Show that the image of {(x0,..xn): x0^k+...+xn^k=0} in CP^n is a smooth manifold.
Is is connected/simply connected?   At least, can you help me understand some special cases of these questions.

Could you maybe give me a reference for  a proof that CP^n is  a smooth, resp. a complex analytic manifold? (I'd like to see the explicit charts, etc)

Thanks

$ \mathbb C P^n$ is the set of equivalence classes $ (z_0 : z_1 : \cdots : z_{n})$ where not all $ z_i$s are simultaneously zero. Let $ U_i$ be the (open) subset where $ z_i\ne 0$. There is a complex-analytic diffeomorphism $ U_i\to\mathbb C^n$ given by $ (z_0 : z_1 : \dots : z_{n})\mapsto (z_0/z_i, z_1/z_i, \dots , z_{n}/z_i)$ where you skip $ i$th term in parantheses on the right. These are the charts that you asked about.

When $ n \equal{} 1$, the set is neither connected nor simply connected: it's the union of two disjoint circles $ z_0 \equal{} z_1$ and $ z_0 \equal{} \minus{} z_1$.

When $ n > 1$, the set is connected, which can be seen from the structure of its intersections with $ U_i$. Not sure about being simply-connected, but I guess it is.

shouldn't one evoke lefschetz' hyperplane theorem to show simple connectedness?

ma_go: What's the statement of Lefschetz's Hyperplane Theorem?

hm.. probably it works just for homology/cohomology (as wikipedia states it: [url]http://en.wikipedia.org/wiki/Lefschetz_hyperplane_theorem[/url]), but i was quite sure there was something on homotopy groups as well...

Thanks for the answer.
I am not sure how connectedness follows from the charts,..could you please give me some details? Is it jsut trivial or am I not seeing something more subtle?

CP^n is not simply connected, sinc eit doesn't have trivial fundamental group.

I was asking about the image of {(x1,..xn)|x1^k+..xn^k=0} in CP^n?
How can I show that this is a smooth manifold?
Is this connected and is it simply connected?

Thanks again!

I'll expand my answer. Let $ M$ be your set. Claim: $ M\cap U_i$ is a smooth manifold for each $ i$. (See the definition of $ U_i$ above, along with a map of $ U_i$ onto $ \mathbb C^n$). Writing $ w_k\equal{}z_k/z_i$ for $ k\ne i$, we find that the image of $ M\cap U_i$ in $ \mathbb C^n$ is the set
$ A: \equal{}\{w\in\mathbb C^n\colon w_0^k\plus{}\dots \plus{} w_n^k \equal{}\minus{}1\}$. (The ith term is not there). Naturally, we want to use the Inverse Function Theorem to show that this set if a smooth manifold. the condition of IFT is that the derivative matrix has maximal rank 1 (we are working over $ \mathbb C$). The derivative matrix is $ (kw_0^{k\minus{}1},\dots kw_n^{k\minus{}1})$ and it indeed has rank 1 because not all entries are zeroes.

So now you have coordinate charts on $ M$. Note that each of them covers "almost all" $ M$, and any two charts overlap. Thus, if you can prove that $ A$ is connected, then $ M$ is also connected as the union of $ M\cap U_i$. When writing my first post, I was for some reason convinced that $ A$ is connected, but now don't see why.  :maybe:

Thanks a lot. I'm gonna try to think about it some more...


I need a book for my studying
You can post  through my email: lhp_tphcm@yahoo.com.vn

Are you looking to self-teach yourself calculus?  Stewart seems to be pretty good but I didn't use it so I don't know.

I am going to be a member of Auckland University business schoool and I want to find out how math 's difficult, can you help me with some files about calculus and statistics?. Thank you very much!

I can't help you with the statistics part.  I took AP Calculus in HS so I have no experience with Calc I or II at the college level.  However, I have taken Calc III (Honors actually).  Honestly, I don't see how much harder than AP it could be.  It's basically just a bunch of algorithms.


geometry
3D geometry
sphere
geometric transformation
rotation
advanced fields
advanced fields unsolved

hi eveybody, i really need help with the following problem: By considering the levi-civita connection, show that the holonomy group at x in the n-sphere is isomorphic to O(n,R).  any help will be highly appreciated.

That doesn't sound right.  The sphere is orientable, so it has to be SO(n,R).  This group is generated by rotations around codimension 2 planes in R^n.  Try to come up with a "simple" path in S^n whose holonomy realizes such a rotation.  (Think about S^2 first, since it's easy to visualize.)


geometry
geometric transformation
rotation
reflection
probability
pifinity is ze best

How many ways are there to put 9 differently colored beads on a $ 3\times3$ grid if the purple bead and the green bead cannot be adjacent (either horizontally, vertically, or diagonally), and rotations and reflections of the grid are considered the same?

[hide="Solution"]If the purple bead is on a corner ($ 4$ ways), then there are $ 5$ places for the green bead. If the purple bead is on an edge ($ 4$ ways), then there are $ 3$ places for the green bead, for a total of $ 4\cdot5\plus{}4\cdot3\equal{}32$ ways to arrange the purple and green beads. After this, there are $ 7!$ ways to arrange the remaining beads. Finally, we divide by $ 4\cdot2\equal{}8$ to account for rotations and reflections. Our final answer is $ \frac{32\cdot7!}8\equal{}\boxed{20160}$.[/hide]

[color=#FF0000]Mod: [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=540&t=394734]Please hide all solutions.[/url][/color]

I struggle to perform these problems correctly!

[hide="Solution"]Alternate solution using total probability:

There are $ 9!$ total arrangements, but only a proportion of them are valid.  In $ \frac{1}{9}$ of cases, the purple bead is in the center, with no legal place to put the green bead.  In $ \frac{4}{9}$ of cases, the purple bead is on a corner, which leaves $ \frac{5}{8}$ remaining places to put the green bead.  In the final $ \frac{4}{9}$ of cases, the purple bead is on an edge, which leaves $ \frac{3}{8}$ of remaining places to put the green bead.  Again, we need to divide by $ 4$ to account for rotations and by $ 2$ to account for reflections.  Result: $ 9!\cdot(\frac{1}{9}\cdot0\plus{}\frac{4}{9}\cdot\frac{5}{8}\plus{}\frac{4}{9}\cdot\frac{3}{8})\div4\div2\equal{}\boxed{20160}$.[/hide]

[color=#FF0000]Mod: [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=540&t=394734]Please hide all solutions.[/url][/color]

[hide]There are $9!$ ways to put the beads on the grid, not taking rotations, reflections, and the restriction on the purple and green beads into account. We need to subtract off the number of arrangements where the purple and green beads are adjacent from this number. There are $2\cdot3=6$ horizontally adjacent pairs of locations, $3\cdot2=6$ vertically adjacent ones, and $2\cdot2+2\cdot2=8$ pairs of diagonally adjacent locations. For each of these pairs, there are two ways to put the purple and green beads in them, and $7!$ ways to put the rest of the beads on the grid, giving a total of $2(6+6+8)7!=40\cdot7!$ invalid arrangements. So, the number of valid arrangements not counting rotations and reflections is $9!-40\cdot7!=(9\cdot8-40)7!=32\cdot7!$. The grid can be rotated onto itself in four different ways, by rotations of 0, 90, 180, and 270 degrees. It can also be reflected onto itself in four different ways, by reflecting across its two diagonals and through horizontal and vertical lines through its center. So, the arrangements come in groups of $4+4=8$ equivalent arrangements, and the number of different arrangements is $32\cdot7!/8=4\cdot7!=\boxed{20160}$.

[quote=kuelshammer]I cannot find my error:

[hide="Solution"]It is always possible to place the green bean into the left top corner or in the middle top row by using rotations and reflections.

Case 1: green=(1/1)
purple=(1/3), (2/3) or (3/3)

Case 2: green=(2/1)
purple=(1/3) or (2/3)[/hide]

Now I got 5 and not four possible locations for purple and green on the board :-(

Which purple position is counted a second time?[/quote]

I got the same.  Did you ever get a satisfactory answer for which we seem to be counting twice?

I think direct is more natural than complementary for this one.
[hide=Solution] Rotation and reflection preserve adjacency so divide by 8 at end.  4 ways to put purple in corner with 5 non-adjacent for green and 7! for rest, plus 4 ways to put purple on edge with 3 non-adjacent for green and 7! for rest, so total (4x5+4x3)x7!/8 = 4x7! = 20160.[/hide]

I also have the same problem.
What is wrong with this?
[hide = 'Click here.']
Case 1: The Purple is set in the top left corner of the grid, as shown:
To make our lives easier, we set the purple in the top-left corner of the grid(so we don't have to account for rotations). Then the Green only has 5 valid spaces(top right corner, middle right spot, bottom right corner, bottom middle, and bottom left corner). However, we must account for reflections, so we only have 3 valid spaces(bottom right corner, bottom middle, and bottom left corner due to reflection across diagonal). Then there are $3 \cdot 7!$ cases for this case.

Case 2: The Purple is set in the top middle spot.
Then the Green has 3 valid spots(bottom-left,bottom middle, and bottom right). However, the bottom-right is invalid due to reflections), meaning that there are $2 \cdot 7!$ ways for this case.

In all, there should be $5 \cdot 7!$ cases, but the answer says $4 \cdot 7!$ ways. What am I missing here?

How are you accounting for reflections? Could you please explain again?

@lexd and everyone else with the same problem:

[hide] My guess is that the fact that you are accounting for double counting for green and purple separate from accounting for double counting for the rest of the grid throws the system off. For example, in Case 1, where you say there are 5 places to insert the green square is correct. Then; however, you also say that rotations and reflections reduces this number to 3. This is confusing because, as said before, you are accounting for rotations and reflections in the green and purple squares separately than the rest of the grid.

My suggestion is to first count every possibility without the thought of reflections and rotations, and account for it at the end.

[/hide]

I have a different question.

[hide = My question]
This regards counting for reflections and rotations. I get for rotations that you must divide by 4. For reflections; however, aren't you supposed to consider both vertical and horizontal reflections, meaning that you have to divide by 4, and not 2? Please help.
[/hide]

I have a question: why don't you have to use Burnside's Lemma for this?

I do understand the problem? Is there a way to not count from the wrong perspective and get the problem wrong?

the total number of arrangements for purple on top middle and green on bottom middle is 7!/2, not 7!.  similarly when the two are on the same diagonal it's 7!/2.  So you have 4x7! overall.

This was a fun problem! Here's my solution: [hide=Solution]
Think about it like this—how many ways can you put the purple and green beads side by side?

This is pretty easy to count, and when you do it you get $20$. We have to multiply this by $2$, as the beads can be arranged as green purple or purple green. We get $40$ through that, and we have to multiply this by $7!$ to count the arrangements of the other $7$ beads. We can subtract this from the total $9!$ cases and call it a day

—but wait! We forgot to account for the reflections and rotations!

We can rotate a corner onto itself $4$ ways, so we have to divide our total by $4$. We can also reflect it two ways, so we again divide it by $2$.

This leads us to the answer $\frac{9!-40\cdot7!}{2\cdot4}=\boxed{20160}$.

[hide=Alternate solution but a bit unclear]Including the restrictions, there are 8! ways to be done. Whom there are 4 cases (not ways because of the restrictions) where the two squares are adjacent. 2 for the diagonals. 2 for the vertical and horizontal ones. Therefore, the answer is 8! - (4)7! = 20160.[/hide]

I have another solution:
Try assigning a location for the purple bead in the 3x3 grid. You will quickly notice that the bead cannot go in the center as there is nowhere for the green bead to go. Therefore, the purple bead has to either go on  a corner or an edge. Since rotations/reflections are considered the same, you only have to consider 2 cases:
1: The purple bead is in a corner. Here, notice that there are 5 different spots to put the green bead (since the purple bead is adjacent to 3 other spots). With the remaining 7 spots, there are 7! ways to arrange the beads. However, in those arrangements, there is a hidden reflection. Some of the arrangements are reflected over the diagonal (running through purple) of other ones. As a result, we divide by 2 here. The total count in this case is 5*7!/2
2: The purple bead is on an edge. There are only 3 options for where the green bead can go this time. Again, there are 7! ways to arrange the remaining beads. Then, we divide the total by 2 as some arrangements are others reflected over the vertical line running through the center of the grid. As a result, there is 3*7!/2 ways to arrange beads in this case
Finally (yay), add up the count for both cases to get a result of (3+5)*7!/2=4*7!=4*5040=20160 ways to arrange the beads

In all honesty the problem should have noted that reflections may also be over one of the diagonals...

[hide=this problem was easier than expected]We do casework on the green bead:
The green bead is in a corner:

There are 5 ways to place the purple bead and $7!$ ways to do the others, but we have to divide by two for reflection. That is a total of $\frac{5\cdot7!}{2}$ ways.

The green bead is on a side:

There are $\frac{3\cdot7!}{2}$ ways, for similar reasons.

Thus, there are $\frac{(5+3)7!}{2}=\frac{8!}{2}=\boxed{20160}$ ways.
[/hide]


can someone please help me with the following two proofs using mathematical induction? i can get to the n=1 proof stage, but i'm stuck on proving n+1 is true.

1 + 3/2 + 2 + 5/2 + ... + 1/2(n+1) = n/4(n+3)

and

1/3 + 1/15 + 1/35 + ... + 1/(2n-1)(2n+1) = n/(2n+1)

please help me!

[quote="stevenmeow"]well as a side note, you should learn how to represent fractions is LaTeX
the code:[code]$\frac{x}{y}$[/code]
gives $ \frac {x}{y}$ where x and y can be expressions, numbers, almost anything

anyway, ill do the first one for you, maybe then you can do the second one...
ok
so you replace n with n+1
$ 1 \plus{} \frac {3}{2} \plus{} 2 \plus{} \cdots \plus{} \frac {1}{2}(n \plus{} 1 \plus{} 1) \equal{} \frac {n \plus{} 1}{4}(n \plus{} 1 \plus{} 3)$ * i think you meant this
this is equal to
$ 1 \plus{} \frac {3}{2} \plus{} 2 \plus{} \cdots \plus{} \frac {1}{2}(n \plus{} 1) \plus{} \frac {1}{2}(n \plus{} 1 \plus{} 1) \equal{} \frac {n^2 \plus{} 5n \plus{} 4}{4} \equal{} \frac {n^2 \plus{} 3n}{4} \plus{} \frac {2n \plus{} 4}{4}$
subtracting the equation
$ 1 \plus{} \frac {3}{2} \plus{} 2 \plus{} \cdots \plus{} \frac {1}{2}(n \plus{} 1) \equal{} \frac {n}{4}(n \plus{} 3)$
from this gives
$ \frac {1}{2}(n \plus{} 2) \equal{} \frac {2n \plus{} 4}{4}$
$ \frac {n \plus{} 2}{2} \equal{} \frac {n \plus{} 2}{2}$
Q. E. D.[/quote]This is not induction. What you just did is to show that the statement is true for $ n$. What the induction step is to assume the statement is true for $ n$, and use that to imply that it is also true for $ n\plus{}1$.

So assume it is true for $ n$:

$ 1 \plus{} \frac {3}{2} \plus{} 2 \plus{} \cdots \plus{} \frac {1}{2}(n \plus{} 1) \equal{} \frac {n}{4}(n \plus{} 3)$.

Now try to add the sum with the next term in the sequence:

$ 1 \plus{} \frac {3}{2} \plus{} 2 \plus{} \cdots \plus{} \frac {1}{2}(n \plus{} 1) \plus{} \frac {1}{2}((n \plus{} 1) \plus{} 1)$

Use your assumption above, substitute, and simplify, you should get it down to:

$ \frac {(n\plus{}1)}{4}((n \plus{} 1) \plus{} 3)$

So, by induction hypothesis, blah blah blah, done. That's how induction is done.

ahem i did do that but srry if it seems a bit confusing
look it through completely and you'll see i rly did prove n+1 given n

first you must prove the equation is true for n=1, then you assume that n= k , k = any integer) then you prove that the equation holds for k+1 and if it does then it works for all numbers greater than or equal to 1


Is there a page where all the LaTeX formulas are?

What do you mean by [i]all the LaTeX formulas[/i]?
You will find a list of symbols at [[LaTeX:Symbols]] and commands at [[LaTeX:Commands]] in the AoPSWiki.

PS I moved your post here as you had put it in the wrong thread.


quadratics
LaTeX
algebra
quadratic formula
special factorizations

Sample probs of what is expecting this week...I did then already, but since i cant check them i would like to see what you guys come up with..Thank You

1. Solve by factoring:
x2 – 9x = -8

2. Solve using the square root property:
2x2 – 5 = 93

3. Solve using the square root property:
(x + 4)2 = 81

4. Solve by completing the square:
x2 + 6x + 2 = 0

5. Solve using the quadratic formula:
x2 – 3x = -6x – 1

6. Solve using the quadratic formula:
x2 – 10x – 1 = -10

First of all, you should use $ \text{\LaTeX}$ (the AoPS site should tell you how) or at least use the ^ symbol for exponents because expressions like 2x2 can be a little confusing.

Anyway, most of your questions can be solved using a standard algebra or algebra II textbook.
Try [url]http://en.wikipedia.org[/url], too. It should give you some good explanations.

Lastly, these problems are a bit too easy on the Intermediate Topics forum. Take a look at the other topics to see why.

Let me know if this helps; if it doesn't I can give you some answers.

As the above poster said, these problems are too easy for the Intermediate forum. Try posting them in the Classroom Math forum, and keep in mind that AoPS is not for daily homework, but for challenging problems that are above regular school level.


Hola!  :)

I haven't been in this forum for a while until now because I'm stuck with this hard journal issue.  :mad:

We have to write about the fair (the place where there is rollercoaster, merry-go-round and etc).

I got one sentence down but I can't think of any other four.

[b]La feria es divertida y tienen buena comida. [/b]

Is that correct? I said, "The fair is divertida and there are good food."

I'll be greatly appreciate if anyone can come up with four simple sentences on fair! Thank you!!

Can anyone give 4 more simple sentences about fair?

I really need this help.  :(


$N$ markaze dayere 9 noghteye mosalase $ABC$ ast.

$A',B',C'$ marakeze dayere 9noghteye mosalas haye $BNC,CNA,ACN$ be tartib hastand.

sabet konid $AA',BB',CC'$ hamresand.

$\mbox{Good Luch in solving this problem}$

[quote="Behsan"]masale faghat tajanose [/quote]

mishe rahe haleto kamel benevisi?

[quote="Jensen"]rasti to akhar sar be man nagofti in soalaye khafan ro az koja miari? :rotfl: [/quote]
Shak dari ke in soal khafane Milad ;) .mitooni emtehanesh koni.

fekr nakonam ba tajanos hal  beshe  :roll:

tajanos ?         in faghat ye nazare shakhsie ?? :lol: [/quote]