inequalities
linear algebra
matrix
function
algebra
polynomial

Let $ k_1,k_2,..,k_n \in R$, not all equal. Prove that:
$ a_1e^{k_1x}\plus{}a_2e^{k_2x}\plus{}...\plus{}a_ne^{k_nx}, \forall x\in R \Leftrightarrow a_1\equal{}a_2\equal{}...\equal{}a_n$

[quote="seamusoboyle"]Is it supposed to be equal to something?  :maybe:[/quote]
Sorry for my bad english: $ k_1 \ne k_2,k_1 \ne k_3,....,k_1 \ne k_n, k_2 \ne k_3,....$ :blush:

That's not the problem: you have, "Show that [some expression]."  Presumably, you meant to write "Show that [some formula]."  Go reread your original post carefully and you should see the problem.

I'm sorry, but I mean that: $ k_i \ne k_j \forall i \ne j$ :blush:

[quote="bertram"][quote="NguyenDungTN"]Let $ k_1,k_2,..,k_n \in R$, not all equal. Prove that:
$ a_1e^{k_1x} \plus{} a_2e^{k_2x} \plus{} ... \plus{} a_ne^{k_nx}, \forall x\in R \Leftrightarrow a_1 \equal{} a_2 \equal{} ... \equal{} a_n$[/quote]
In your original post you forgot the RHS of this (in)equality:$ a_1e^{k_1x} \plus{} a_2e^{k_2x} \plus{} ... \plus{} a_ne^{k_nx}$

Without it, this satement makes no sense, as the LHS of the iff is not a true/false statement but a number.[/quote]
I'm sorry about my mistakes :(  I didn't realize that it's wrong. Problem:
Let $ k_1,k_2,..,k_n, k_i \ne k_j \forall i\ne j$. Prove that:
$ a_1e^{k_1x} \plus{} a_2e^{k_2x} \plus{} ... \plus{} a_ne^{k_nx}\equal{}0,\forall x\in R$ if and only if $ a_1\equal{}a_2\equal{}...\equal{}a_n\equal{}0$

In other words, $ e^{k_i x}$ are a set of linearly independent functions.

[hide="Large hint"] The Wronskian takes the form of a Vandermonde matrix (I think) when $ x \equal{} 0$.  :) [/hide]

[hide="A not-so-rigorous solution"]
First, analize the case $ \max_{i} k_i > 0$ and $ a_i\equal{}0$. WLOG $ k_1 \equal{} \max_{i} k_i$. Then $ a_1e^{k_1x}\plus{}\cdots\plus{}a_ne^{k_nx} \equal{} e^{k_1x}\left(a_1\plus{}a_2e^{(k_2\minus{}k_1)x}\plus{}\cdots\plus{}a_ne^{(k_n\minus{}k_1)x}\right)$ and if we take $ x\to\infty$ the function will diverge since the 2nd factor converges to $ a_1$. This clearly acontradiction.

I think we can extend the proof if we assume that $ |k_1| \equal{} \max_{i} |k_i|$ and then multiply each $ k$ by $ \pm 1$ so that the maximal $ k$ is positive. We can also just cut away every $ a_i \equal{} 0$ and analize the remaining funtion, so $ a_i \equal{} \ldots \equal{} a_n \equal{} 0$.
[/hide]

[hide]
If a function $ f$ is identically zero, $ f^{(m)}(0)\equal{}0$ for all nonnegative integers $ m$. So we get
\[ \sum_{j\equal{}1}^n a_jk_j^m\equal{}0\]
By taking linear combinations,
\[ \sum_{j\equal{}1}^n a_jP(k_j)\equal{}0\]
for every polynomial $ P$. But for each $ j$, we can choose the polynomial
\[ P_j(t)\equal{}\prod_{r\neq j} \frac{t\minus{}k_r}{k_j\minus{}k_r}\]
Plugging in $ P_j$ into the above gives $ a_j$ on the left hand side. So all $ a_j$ are zero.
[/hide]

Essentially a neater version of the argument to which I hinted (that is, the Wronskian is invertible at $ x \equal{} 0$).  :)


Show that the equation $ 3y^2\equal{}x^4\plus{}x$ has no solutions in positive integers

[quote="maruemu"]Show that the equation $ 3y^2 \equal{} x^4 \plus{} x$ has no solutions in positive integers[/quote]
$ 3y^2 \equal{} x(x^3\plus{}1)$ but $ (x,x^3\plus{}1)\equal{}1$ so either $ x\equal{}a^2$ and $ x^3\plus{}1 \equal{} 3b^2$ or $ x\equal{}3b^2$ and $ x^3\plus{}1 \equal{} a^2$.
Case $ x\equal{}a^2$ and $ x^3\plus{}1\equal{}3b^2$ gives $ x^3 \equal{} a^6$ so $ x^3\plus{}1\minus{}x^3 \equal{} 3b^2\minus{}a^6 \equal{} 1$, which has no solution $ \bmod 3$.
Case $ x\equal{}3b^2$ and $ x^3\plus{}1 \equal{} a^2$ gives $ x^3 \equal{} 27b^6$ so $ x^3\plus{}1\minus{}x^3 \equal{} a^2 \minus{} (3b^2)^3 \equal{} 1$ Or $ (a\minus{}1)(a\plus{}1) \equal{} (3b^2)^3$. which clearly has no solution! :)


$\frac 23$.  For some strange reason this fraction is shown in "text style" while other fractions (like good old $\frac 12$, say) would be shown in "display style". Any explanation? :?

Hi,
Your observation is correct for all fractions with numerator 1.
$\frac 19$ $\frac 13$ $\frac 17$ $\frac 15$
That's only on this forum though, and I can't say why. However, using brackets will not cause this problem.
$\frac{1}{2}$
$\frac{2}{3}$
SSN.

[quote="ssn116"] However, using brackets will not cause this problem.
[/quote]
This makes it even stranger because the display style is supposed to be the default one on this forum and, with braces, many other fractions with small one-digit numerator and denominator become displayed in the text style... $\frac{1}{2}$, $\frac{1}{3}$, $\frac{2}{3}$, $\frac{1}{4}$, $\frac{3}{4}$, $\frac{5}{6}$  but $\frac{7}{8}$, $\frac{2}{4}$, etc. Also, if you add a space between the numerator and the denominator, this strange behavior disappears: $\frac{2} {3}$. Or, if your fraction is a part of a longer formula, you don't see anything abnormal either: $\frac{2}{3}x$.

It's just that some of the images are taken from the cache...Valentin addressed the problem [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=55207]here[/url].


Ok, I called MathCounts (703-299-9006) about 10 minutes ago, and here's all the info I have summarized:

MathCounts Nationals to be held in Ft. Worth Texas at the Renaissance Worthington Hotel (nice hotel - I got this from the MathCounts press release mid-last year).

The Guest Registration Form (I call it GRF now since I've been driving people nuts about it the past two days) is on [url]https://www.ptfassociates.com/secure/mathcounts/Registration.htm[/url] (online) and [url]http://www.mathcounts.org/webarticles/articlefiles/2007_Guest_Registration_Form.pdf[/url] (mail-in or fax). And [url]http://www.mathcounts.org/webarticles/articlefiles/2007_Info_Book.pdf[/url] has more info! [url]http://www.mathcounts.org/webarticles/anmviewer.asp?a=536&z=5[/url] lists all of these links as well!

Yes, you have to book the hotel and flight separately (I'm pretty sure you enter in when your flight is on the GRF for the shuttle), but the hotel part is easy. When you call up the Renaissance Hotel, ask to be in the MathCounts wing so you won't have to pay the hefty 300 dollar a night fee when you get the remaining rooms on the website.

I think this sums it up nicely,
Jorian Hoover

Other Information:

800-433-5677 is the phone number for the hotel (remember to ask for the MathCounts Block, as it is 100 dollars cheaper).

[url]http://marriott.com/hotels/travel/dfwdt-renaissance-worthington-hotel-fort-worth/[/url] is the website for the hotel if further information is needed.

Thanks to Jhredsox for summarizing this, I think some might find it helpful as a sticky until nationals.

just a reminder: remember not to book past march!!!

-jorian


induction
group theory
abstract algebra
real analysis
real analysis theorems

I'm now teaching a beginner's course in analysis and we went over the axioms of real numbers and decided to believe that the set of real numbers exists. The next topic in the course is integers (proof by induction, etc.). Of course, once one believes that the set of real numbers exists, it should be possible to [b]construct[/b] integers and to [b]prove[/b] all their properties. The cheapest way to define the set of integers seems to be to define them as the additive subgroup generated by $1$.   Then everything can be done in a very short way if one can prove that there are no integers between $0$ and $1$ but, to my shame, I do not see a simple way to do it, so currently I plan to define the set of non-negative integers first (as the smallest set containing $0$ and containing $x+1$ together with every $x$) and proceed from there, which is quite a long  way.  Am I missing something? :?

Since "between" doesn't even make sense without the order axioms, we need to incorporate them from the start.
An important lemma: any element in this subgroup is either a sum of copies of 1, a sum of copies of -1, or 0. The problem is, I don't see how to get this without already having induction.

This is exactly the division into positive, negative, and zero. If $0<x<1$, then $x$ is a sum of at least one 1, and $1-x$ is as well. There's a contradiction, and there is no integer between 0 and 1.

It might be easier to start with the nonnegative integers. The approach above lets you embed the integers into the real numbers, but that's not where you want to be when you're trying to "define" integers.

Another way to construct positive integers:

\[ 0=\#S_0=\#\{\phi\}  \]
\[ 1=\#S_1=\#\{\phi,\{\phi\}\}  \]
\[ 2=\#S_2=\#\{S_1,\{S_1\}\}  \]
and so on. Does it helps you or this condtruction is also inductive? :D


Let $ A_1A_2A_3$ be a triangle which is not right.Prove that there are circles $ C_1,C_2,$ and $ C_3$ such that $ C_2$ is tangent to $ C_3$ at $ A_1$,$ C_3$ is tangent to $ C_1$ at $ A_2$,and $ C_1$ is tangent to $ C_2$ at $ A_3$.

[hide]
Construct the circumcircle of triangle $ A_1A_2A_3$, say circle $ O$. Then draw a tangent line past each of $ A_1, A_2, A_3$, say $ l_1, l_2, l_3$. Since $ A_1A_2A_3$ is not a right triangle, $ A_1, O, A_2$ are not collinear. Thus $ l_1, l_2, l_3$ intersect pairwise, forming a triangle $ C_1C_2,C_3$ whose vertices are the centers of circles satisfying the given.[/hide]


calculus
integration
real analysis
real analysis unsolved

Hi,

My friend recently asked me for help on this question.  I am not sure if calculus is actually required to solve this problem, so if this is an inappropriate forum for this problem, sorry!

Suppose there are four freshmen at the corners of a square of side length 1km. Counting counterclockwise, label the freshmen 1 through 4 starting with the one at the bottom right corner of the square. All four freshmen start running at the same time and the same constant speed, with freshmen #1 chasing freshmen #2, #2 chasing #3, #3 chasing #4, and #4 chasing #1.

Question 1: All four freshmen will collide at one point. Where is this point in the square?
Question 2: How long does it take for the freshmen to collide if each runs at 15km/h (they're really fast)?

I thought that the students would move in a spiral-like manner, colliding at the center of the square.  But in order to determine the amount of time it takes for the freshmen to collide, I would have to determine the length of the spiral-like curve.  How would I determine the appropriate integral to do so?  Or am I just stupid and the students don't move with curved patterns at all?

Thanks for your help!

This problem appears, with solution, on p. 72  (example 3.1.6) of The Art and Craft of Problem Solving, by Paul Zeitz.

There is in fact a clever way to do this problem without Calculus.

[hide]To quote from Zeitz (who uses bugs instead of freshmen):

"The situation is rotationally symmetric in that there is no one "distinguished" bug.  If their starting configuration is that of a square, then they will always maintain that configuration.  This is the key insight, believe it or not, and it is a very profitable one!"[/hide]

[hide]At any point in time, how fast is each bug (or freshman) approaching the center?  What is the radial component of its (his) velocity?[/hide]

[hide="The way I would have phrased the second hint."]Don't look at the rate at which they are approaching the center. How fast is the distance between two bugs (freshmen) changing at any moment? The first is moving directly towards the second, so the full speed applies there. And the second is moving at right angles to the line between them.[/hide]

[hide]Is it 4 minutes?[/hide]

heh yeah, caught the mistake while arguing with my dad over the answer.


4x -1                 x +3

_____________ - _____________

2x^ +5x - 3         6x^ + x - 2

^ means squared

I've gotten it down to

  11x^ + 14x - 18

____________________

(2x-1) (x+3) (3x+2)

but 11x bla bla doesn't seem factorable.. or i haven't figured it out yet, but 2 peices of paper later and i'm about ready to give up.

Edit - x + 3 OVER 6x^ + x -2 should be on the far side of the equation... for some reason the forum won't let it space out

I can't understand your syntax but use the quadratic formula:
For $ ax^{2}\plus{}bx\plus{}c\equal{}0$, $ x\equal{}\frac{\minus{}b\pm\sqrt{b^{2}\minus{}4ac}}{2a}$.

[quote="suave"]
$ \frac {4x \minus{} 1}{2x^2 \plus{} 5x \minus{} 3} \minus{} \frac {x \plus{} 3}{6x^2 \plus{} x \minus{} 2}$
[/quote]

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

which means I probably can't do my arithmetic right ..

Edit: it doesn't factor, by the way. Is it supposed to factor?

[quote="azjps"][quote="suave"]
$ \frac {4x \minus{} 1}{2x^2 \plus{} 5x \minus{} 3} \minus{} \frac {x \plus{} 3}{6x^2 \plus{} x \minus{} 2}$
[/quote]

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

which means I probably can't do my arithmetic right ..[/quote]

damn you got really friggin close.. maybe i'm the one that screwed up in the arithmetic because if you can facrotor 11x^ - x - 11

that SHOULD be it.

I got $ 11x^2 \minus{} x \minus{} 11$ also, and the quadratic formula easily confirms that the roots are irrational. So that's as far as you can go.

[quote="suave"]$ \frac{4x\minus{}1}{2x^2\plus{}5x\minus{}3}\minus{}\frac{x\plus{}3}{6x^2\plus{}x\minus{}2}$

$ \frac{11x^2 \plus{} 14x \minus{} 18}{(2x\minus{}1)(x\plus{}3)(3x\plus{}2)}$

but 11x bla bla doesn't seem factorable.. or i haven't figured it out yet, but 2 peices of paper later and i'm about ready to give up.[/quote]

If you need two pieces of paper, then there is some sort of trick that you are missing.

[hide="mine"]$ \frac{4x\minus{}1}{2x^2\plus{}5x\minus{}3}\minus{}\frac{x\plus{}3}{6x^2\plus{}x\minus{}2}\equal{}\frac{4x\minus{}1}{(2x\minus{}1)(x\plus{}3)}\minus{}\frac{x\plus{}3}{(2x\minus{}1)(3x\plus{}2)}$

\[ \equal{}\frac{(4x\minus{}1)(3x\plus{}2)\minus{}(x\plus{}3)^2}{(2x\minus{}1)(x\plus{}3)(3x\plus{}2)}\]

\[ \equal{}\frac{11x^2\minus{}x\minus{}11}{(2x\minus{}1)(x\plus{}3)(3x\plus{}2)}\][/hide]

Proof by Funding: How can three different national corporations be wrong?


modular arithmetic
induction
geometry
combinatorics unsolved
combinatorics

As a first guess, I would say that the first plauer has a winning strategy iff $n$ is not $3\pmod 4$, but I'll have to check this out.

[quote="orl"]We say that a pile is a set of four or more nuts. Two persons play the following game. They start with one pile of $n \geq 4$ nuts. During a move a player takes one of the piles that they have and split it into two nonempty sets (these sets are not necessarily piles, they can contain arbitrary number of nuts). If the player cannot move, he loses. For which values of $n$ does the first player have a winning strategy?[/quote]

I think the first player has a winning strategy for all $n\neq 7$. However, it's the first game theory problem I have ever solved, so I can only hope my proof is correct...

[quote="orl"]I see Christian Sattler participated. What about the other IMO2004 members who are still eligible for the Baltic Way contest ? Who determines the German team and how ?  :)[/quote]

Actually, I believe the German participants must live in the north of Germany. However, currently Christian Sattler himself is trying to establish a plan that next year, 5 of the German IMO 2004 participants will go to Hamburg for the duration of the contest. Well, let's see.

  Darij

How about checking the case $n=11$ more carefully?  ;)

If $A$ (the first player) breaks it into $1,10$ or $2,9$ or $3,8$, then $B$ wins. If he breaks it into $4,7$, then $B$ breaks $7$ into $3,4$, and he wins, and if $A$ breaks $11$ into $5,6$, then $B$ breaks $6$ into $1,5$, and it's not hard to see that he wins again after a few moves.

Yes, I analyzed $n=11$ too, but I couldn't move further, except following conjecture: if we initially have two piles $4k+1>4$ and $4l+2>4$ then first player wins.
Is that true?  :maybe:

Sorry... so there was indeed a gap in my logics.

  Darij

Little correction to my conjecture: two piles of $4k+1$ and $4l+2$ nuts, and $4k+1<4l+2$; then first player wins.

Am I as blind as before right now, or does the game start with one pile?

  dg

Game starts with one pile.
Actually, mentioned conjecture devoted to proof of grobber's conjecture that is $4k+3$ is only bad case for first player.

Indeed, I think we need something like Myth's conjecture in order to employ induction. The only clue I have is that the only bad cases for $A$ and $n\ge 14$ are $n=7,n=11$. I'd have to analyze $n=15$ next, but I'm a bit too lazy to do that :).

In case $n=15$ we have to analyze situation after first move: 15 -> 5+10.
Then second player makes 4, 5 and 6. And it is easy (;)) to see that first player will lose.

If we show that $B$ has a winning strategy in the case $4k+3$, then the fact that $A$ has a winning strategy when $n\ne 4k+3$ follows easily.

Actually, I think we could use the following inductive step, but I'm not sure it works (and I don't have a proof, or anything that looks like one :)):

If $n=4k+3$ and $A$ separates a $4$, then $B$ should break down that $4$, and leave $A$ with $4k-1$ as the first player, after which we could use the induction hypothesis. If $A$ separates a $1,2$ or $3$, then the inductive step is done, because $A$ leaves $B$ as the first player with a number $\not\equiv 3\pmod 4$, and since this number is $<4k+3$, we can use the induction hypothesis. The only case left, when $A$ splits the pile in to piles, both with $>4$ elements, I think (this is the thing which I haven't proved) $B$ should separate $4$ elements from one of the piles. Could this be true?

@Darij and others

BTW is Christian also a math linker ?  :)  Hmm. Obviously Christian kills the Combinatorics problems, Darij the geometry ones. I don't know about Peter Scholze. Maybe number theory. The algebra problems could be a joint job.

Regarding the participants. If Saint-Petersburg participates you also may have one half or one third of the Russian IMO team....  ;)  :)

Finally, I have done it!

We will prove by induction that positions
$4k+3$, $(4k,4l)$, $(4k+1,4l+1)$ and $(4k+2,4l+2)$ are losing.

As grobber said before, it is easy to derive that $4k$, $4k+1$ and $4k+2$ are winning positions if $4l+3$ are losing for all $l<k$.

Suppose $A$ has position $4k+3$. There are two possibilities of dividing this pile:
1) $4k$, $4l+3$. Then $B$ makes $(4k-1,4l+3)$.
2) $4k+1$, $4l+2$.
	2.1 If $k,l>0$ then $B$ makes position $(4k+1,4l+1)$ and wins.
	2.2 If $k=0$, $l> 0$ then $B$ makes position $4l-1$ and wins.
	2.3 If $k>0$, $l=0$ then $B$ makes position $4k-1$ and wins.

Suppose $A$ has position $(4k+1,4l+1)$. Possible turns are
1) $4k$, $4m+1$, $4l+1$.
	1.1 If $m=0$ then $B$ makes position $(4k,4l)$.
	1.2 If $m>0$ then $B$ makes position $(4k-1,4m+1,4l+1)$ and wins.
2) $4k+2$, $4m+3$, $4l+1$.
	2.1 If $k=0$, $m>0$ then $B$ makes $(4m+1,4l+1)$.
	2.2 If $k=0$, $m=0$ then $B$ makes $4l-1$.
	2.3 if $k,m>0$ then $B$ makes $(4m+3,4k+1,4l+1)$.
	2.4 If $k>0$, $m=0$ then $B$ makes $(4k+1,4l+1)$.

Suppose $A$ has postion $(4k+2,4l+2)$. Possible turns are
1) $4k$, $4m+2$, $4l+2$.
	1.1 If $m=0$ then $B$ makes $(4k,4l)$.
	1.2 If $m>0$ then $B$ makes $(4k-1,4m+2,4l+2)$.
2) $4k+1$, $4m+1$, $4l+2$.
	1.1 If $k=0$, $m>0$ then $B$ makes $(4m+1,4l+1)$.
	1.2 if $k,m>0$ then $B$ makes $(4k+1,4m+1,4l-1)$.

Suppose $A$ has position $(4k,4l)$. Possibleturns are
1) $4k$, $4m$, $4l$. Then $B$ makes $(4k-1,4m,4l)$.
2) $4k+1$, $4m+3$, $4l$.
	2.1 If $k>0$ then $B$ makes $(4k,4l,4m+3)$.
	2.2 If $k=0$, $m>0$ then $B$ makes $(4m+1,4l+1)$.
	2.3 If $k=0$, $m=0$ then $B$ makes $(4l-1)$.
3) $4k+2$, $4m+2$, $4l$.
	3.1 If $k=0$, $m>0$ then $B$ makes $(4m,4l)$.
	3.3 If $k=m=0$ then $B$ makes $4l-1$.
	3.3 If $k,m>0$ then $B$ makes $(4k+2,4m+2,4l-1)$.

Hope it is correct :)

Call a set of piles a 'game'. If the player moving next in a game can win, the game is called 'winning' otherwise 'losing'.
We have a clue observation:
If set A is losing and set B is losing then the union of these two sets is also losing.
This observation helps us proving by induction that if the set consists of two $piles$ containing the same number of nuts $mod$ $4$ then it's losing.

Particularly this proves Myth's conjencture:
B can move $4k+2,4l+1$ into the losing $4k+1,4l+1$.
But Myth's conjencture proves that the losing piles are only those with $4k+3$ nuts.
QED I think

Sorry, Myth, I opened this topic before you sent your solution, so I wrote the same solution as yours second time..

Actually, after [url=http://www.cut-the-knot.org/ctk/May2001.shtml]some reading[/url], I can see that this is elementary Sprague-Grundy theory. It should be easy to show by induction that the nim number corresponding to a game starting with a pile of $n$ elements is $0$ iff $n=4k+3$. Actually, starting from $n=4,5,6,7,8,9,10,11,\ldots$, the nim numbers are, I think, $1,2,3,0,1,2,3,0,\ldots$.

Some more info can be found [url=http://sps.nus.edu.sg/~limchuwe/cgt/cgt3.htm]here[/url], for example.


Let $ x$ and $ y$ be positive integers. The least possible value of $ |11x^5 \minus{} 7y^3|$ is

A. 1
B. 2
C. 3
D. 4
E. None of these

[hide="solution"]Looking for equality, we try $ x\equal{}7^a11^b$ and $ y\equal{}7^c11^d$. Substituting, $ 7^{5a}11^{5b\plus{}1}\equal{}7^{3c\plus{}1}11^{3d}$. Setting the powers equal, we have $ 5a\minus{}3c\equal{}1$ and $ 5b\minus{}3d\equal{}\minus{}1$. These are just diophantine equations over the positive integers - solving, $ a \equiv 2 \pmod 3$, $ c\equiv 3 \pmod 5$, $ b\equiv 1 \pmod 3$, and $ d\equiv 2\pmod 5$. The smallest solution to this gives $ x\equal{}7^211^1$ and $ y\equal{}7^311^2$. This checks to $ 7^{10}11^6\minus{}7^{10}11^6$, so we have that 0 is reachable and therefore the answer is $ \boxed{\text{E}}$.[/hide]

[hide="Solution Without Modular Arithmetic"]

The problem is done if we can find values of $ x$ and $ y$ such that $ 11x^5 \minus{} 7y^3$ is zero because that's the least possible value of [i]any[/i] absolute value.

So, let $ k \equal{} 11x^5 \equal{} 7y^3$. Then

$ x \equal{} \sqrt [5] {\frac {k}{11}}, y \equal{} \sqrt [3] {\frac {k}{7}}$

Simple playing with numbers show that one possible way to do this is when $ x \equal{} 11 \cdot 7^2$ and $ y \equal{} 11^2 \cdot 7^3$. So, 0 is attainable and the answer is E. [/hide]


Euler
email
inequalities
number theory unsolved
number theory

Euler conjectured that: "For any integer $ n \ge 3$, the equation $ x^{n}_1 \plus{} x^{n}_2 \plus{} \cdots \plus{} x^n_{n \minus{} 1} \equal{} x^n_n$ has no positive integer root."

 I have just found a counter example for the case $ n \equal{} 6$ :

$ 94829650^{6} \plus{} 6943812^{6} \plus{} 6235824^{6} \plus{} 405486666^{6} \plus{} 256051472^{6} \equal{} 409672964^{6}$

; $ n \equal{} 8$ :
[img]http://i142.photobucket.com/albums/r110/namvk/n8.jpg[/img]

; $ n \equal{} 11$ :
$ 106034^{11} \plus{} 3^{11} \plus{} 57^{11} \plus{} 8^{11} \plus{} 62^{11} \plus{} 46^{11} \plus{} 34^{11} \plus{} 254^{11} \plus{} 40300^{11} \plus{} 177090^{11} \equal{} 177147^{11}$

if you are interested, please contact me through my email: vkhoanam@gmail.com

How way did you find these inequalityes?
Why you don't use coprime numbers in first example? All numbers even in first example.
If $ x_1^n\plus{}...\plus{}x_m^n\equal{}x_{m\plus{}1}^n$, then for any a
$ (x_1a)^n\plus{}...\plus{}(x_ma)^n\equal{}(x_{m\plus{}1}a)^n$. Therefore interested only case, when $ gcd(x_1,...,x_m)\equal{}1$. Then we can compare whith another known solutions .


geometry
ratio
symmetry
geometry unsolved

see  for my question http://www.badongo.com/pic.php?file=golden__2005-12-12_golden.GIF

Using a parallel projection, project the triangle $\triangle ABC$ into an equilateral triangle $\triangle A'BC$. (Just draw an equilateral triangle on the base BC. The line AA' is the direction of the parallel projection.) The points B, C, D stay in place and the points A, E, F, P, Q, R are carried into points A', E', F', P', Q', R'. (For example, E' is the intersection of CA' with a line through the point E parallel to AA'.) Parallel projection preserves area ratios and segment ratios on the same line. Solve the problem for the equilateral triangle $\triangle A'BC$ (skipping primes in the notation). By symmetry, the triangles $\triangle ABP \cong \triangle BCQ \cong \triangle CAR$ are congruent, the triangles $\triangle APE \cong \triangle BQF \cong \triangle CRD$ are also congruent and the triangle $\triangle PQR$ is equilateral. The triangles $\triangle BCQ, \triangle QCE$ have the same areas (equal bases BQ = QE and common C-altitude). Hence, the triangles $\triangle PQR, \triangle CRD$ have the same areas and

$QR \cdot PR = CR \cdot RD$

Since the triangle $\triangle PQR$ is equilateral, QR = PR, since the triangles $\triangle APE \cong \triangle CRD$ are congruent, AP = CR, and since P is the midpoint of AD, AP = PD. Therefore,

$PR^2 = AP \cdot (PD - PR) = AP \left(AP - PR\right)$

$\left(\frac{AP}{PR}\right)^2 - \frac{AP}{PR} - 1 = 0$

(c) [color=white].[/color] $\frac{AP}{PR} = \frac{1 + \sqrt 5}{2} = \phi$ (the other root is negative, not acceptable)

(b) [color=white].[/color] $\frac{PR}{RD} = \frac{PR}{PD - PR} = \frac{PR}{AP - PR} = \frac{1}{\phi - 1} = \phi$

$\frac{AD}{AR} = \frac{2 AP}{AP + PR} = \frac{2\phi}{\phi + 1} = \frac{2 \phi}{\phi^2} = \frac 2 \phi$

Denote $\xi = \frac{S(\triangle PQR)}{S(\triangle ABC},$ $\sigma = \frac{S(\triangle CAR)}{S(\triangle ABC)}$ and $\tau = \frac{S(\triangle CAD)}{S(\triangle ABC)}$. From congruence of the triangles $\triangle ABP \cong \triangle BCQ \cong \triangle CAR$, we have $\xi + 3 \sigma = 1$. Since the triangles $\triangle CRD, \triangle PQR$ have the same areas, we get $\tau = \sigma + \xi$ and substituting $\xi = 1 - 3 \sigma$ leads to $\tau = 1 - 2 \sigma$. The areas of the triangles $\triangle CAD, \triangle CAR$ are in the ratio of their bases AD, AR.

${\frac 2 \phi = \frac{AD}{AR} = \frac{S(\triangle CAD)}{S(\triangle CAR)}} = \frac \tau \sigma,\ \ 2\sigma = \phi \tau$

Solving for $\tau$,

$\tau = 1 - 2 \sigma\ = 1 - \phi \tau,\ \ \tau = \frac{1}{1 + \phi} = \frac{1}{\phi^2}$

The areas of the triangles $\triangle DAB, \triangle CAD$ are in the ratio of their bases BD, DC.

(a) [color=white].[/color] $\frac{BD}{DC} = \frac{S(\triangle DAB)}{S(\triangle CAD)} = \frac{1 - \tau}{\tau} = \phi^2 - 1 = \phi$


linear algebra
matrix
function
algebra
domain

The matrix $ A \equal{} \left[ \begin{matrix} 1 & 2 \\
3 & 0 \\
\minus{} 1 & 5 \\
\end{matrix} \right]$ is associated to a linear transformation $ T: \mathbb R^2\to\mathbb R^3$ according to the basis $ \alpha \equal{} \{v_1,v_2\}$ and $ \beta \equal{} \{w_1,w_2,w_3\}$. Find $ T.$

I must do this by not using the change of basis matrix. If I'd have the standard basis, then I'd just multiply the matrix by $ \left[ \begin{matrix} x \\
y \\
z \\
\end{matrix} \right]$ and I'm done, but how to make it when having different basis?

$ T$ is the linear transformation that takes $ av_1\plus{}bv_2$ to $ (a\plus{}2b)w_1\plus{}3aw_2\plus{}(\minus{}a\plus{}5b)w_3$.

I'm a bit lost yet.

I see you made a linear combination with the first basis but I don't get why taking the same scalars for the second basis.

Apply that matrix $ A$ to $ \begin{bmatrix}a\\b\end{bmatrix}$. Read the input as a linear combination of $ v_1$ and $ v_2$, and the output as a linear combination of $ w_1$, $ w_2$, and $ w_3$.

That line in my previous post was the answer. A linear transformation is a function, and that's a complete description of what the function does at any point in its domain. It's in terms of the $ v_i$ and $ w_i$ because those are the only terms we have with which to represent elements of the domain and codomain.


Express

$0.1234\bar{5}$

as a fraction.  :)

[hide="Hint"]
Seperate $0.1234$ and $0.0000\bar{5}$
[/hide]

[hide]12345-1234 = 11111
11111/90000
i'm not sure if you can simplify that... [/hide]

[quote="236factorial"][quote="LuCy4EvA"]i'm not sure if you can simplify that... [/quote]

11111=41*271, but none of those are divisible by 90000, so it's the simplest answer  :)[/quote]

thank you for telling me that, i'm really bad at finding factors and stuff.

Here's something you probably already know: to find if a number is prime, divide the number by the primes less than or equal to the square root of the number.

For example, for 119, test divisibility by only the primes 2, 3, 5, and 7.

[quote="buzzer11"]nine isn't a prime  :D[/quote]

Oh  :blush:  I was on a roll with odd numbers...  :D


A rectangular prism has dimensions h=2 ft. w=7 ft. and L= 4 ft. The prism is cut into two seperate tangular prisms by a plane parallel to one of the faces. what is the maximum increase in the surface area between the one prism and the two seperate prisms?

[hide] Make the plane parrelel to the face which has dimensions 7 ft by 4 ft.  This makes the surface area increase by $2*(7)(4)=56 ft^{2}$.  [/hide]


algebra
polynomial
Vieta
calculus
integration
Rational Root Theorem
absolute value

A polynomial P(x) is known to be of the form
$ {x^{19}} \minus{} {7x^{18}} \plus{} ... \minus{} 13$
where the ellipsis (...) represents unknown intermediate terms. It is also known that all roots of P(x) are integers. The largest root of P(x) is?

A. 7
B. 13
C. 6
D. not deducible from the given information
E. none of the others

Because of some weird theorem I read, all of the roots must be (a factor of the alone integer)/(a factor of the leading coefficient) if the roots are real. So the possible roots are ±1,±13. Obviously, there must be one of the $ 13$ roots and $ 18$ of the $ 1$ roots. So let's first try $ \minus{}13$. Because the coefficient of the 2nd term is the negative of the sum of all the roots, this doesn't work because even if all 18 ones are positive, it still won't be equal to $ \minus{}7$. So therefore it must be $ 13$, which is the answer.

[quote="Ihatepie"]Because of some weird theorem I read, all of the roots must be (a factor of the alone integer)/(a factor of the leading coefficient) if the roots are real. So the possible roots are ±1,±13. Obviously, there must be one of the $ 13$ roots and $ 18$ of the $ 1$ roots. So let's first try $ \minus{} 13$. Because the coefficient of the 2nd term is the negative of the sum of all the roots, this doesn't work because even if all 18 ones are positive, it still won't be equal to $ \minus{} 7$. So therefore it must be $ 13$, which is the answer.[/quote]

That's called the Rational Root Theorem :) .

Actually, the answer would be D.

The Rational Root Theorem lists all possible rational roots that you can then test, but it does not give irrational roots, or in any way imply that the possible roots it does give are solutions.

Without knowing the intermediate terms, you can only speculate as to what the roots could be.

Note: using the Remainder Theorem, if the root is $ z$, then $ P{(}z{)}=0$

Ihatepie is right though. In the problem, it stated that "all roots of $ P(x)$ are integers." Therefore, all the roots must have an absolute value of $ 1$ or $ 13$ by the Rational Root Theorem.

I'm not arguing that that isn't true, but can you also show that no matter what the intermediate terms are, 13 will be a root?

Well we know all the intermediate term coefficients and roots are integers, (it says in the problem) so the answer follows from my solution.

But again, as fishythefish stated, you don't know that 13 is actually always a root, and if 13 is not a root, it is not the biggest root because it isn't one to begin with.

I proved why it is a root. What was my flaw?

(I can clarify it if you want)

Please, clarify. I don't understand why it must be a root, seeing as the rational root theorem does not guarantee that the numbers that it comes up with are all roots.

But it says that if the coefficients are integers (which they are) then the roots must be among them. In this case, all of the roots must be $ 1$, $ \minus{}1$, $ 13$, $ \minus{}13$. So all the factors must be  $ (x\minus{}13): 13$, $ (x\plus{}13): \minus{}13$, $ (x\minus{}1): 1$, or $ (x\plus{}1): \minus{}1$.

Because the constant term is $ \minus{}13$, and (using vieta's) that is equal to the negative of the product of the roots, one of the roots must be either $ \minus{}13$ or $ 13$, while the rest are either $ 1$ or $ \minus{}1$. We are given another piece of information: the coefficient of the $ x^{18}$ term is $ \minus{}7$. Using Vieta's formulas, $ \minus{}7$ is equal to the negative of the sum of the roots, so the sum of the roots is $ 7$. I already proved that one of the roots is either $ 13$ or $ \minus{}13$. Let's assume that it is $ \minus{}13$. Because the sum of the roots is $ 7$, even if all the remaining roots are $ 1$, the sum is only $ 5$, which falls short. So therefore the root can't be $ \minus{}13$. So it has to be $ 13$. Since that is the largest possible root by the Rational Root Theorem, we know it is the largest root.

Your solution is incomplete, because you haven't shown that there are necessarily 4 roots.

There are 19 roots, I showed that due to the rational root theorem, they all have to be either $ \minus{}13$, $ 13$, $ 1$, or $ \minus{}1$.

The problem does not say that there are 19 roots. The degree of a polynomial only gives the number of roots, including complex roots and degenerate roots. The problem is only asking for real roots.

In other words, $ f(x)\equal{}x^3$ is a third-degree polynomial, but does not necessarily have 3 roots. (In fact, it only has one real root at $ x\equal{}0$.)

Yeah, Rational Root Theorem only works for rationals.  :D

1) The Fundamental Theorem of Algebra states that the given polynomial has $ 19$ roots, counting for multiplicities, irrespective of whether the roots are rational or not.

2) The problem explicitly states that all roots are integers.

Therefore, all $ 19$ roots are integers?

I believe the original post only referred to the roots on the x-axis (integers, which are, by definition, real). Generally, when solving polynomials, many people do not stop to consider non-real roots.

EDIT: I added this link, which I think might be helpful to everyone on this thread:
[url]http://www.artofproblemsolving.com/Wiki/index.php/Polynomials[/url]

Your second point may be true, but a direct implication of the fact that all roots are integers is that all solutions are purely real. Imaginary numbers aren't integers, and neither are complex numbers that aren't purely real.

Fine. But can you still prove that the multiplicities don't all happen to exist at the other possible values of $ x$? The point that I have been trying to get at is that nobody so far has shown that there has to be a root at $ x\equal{}13$.

Proof: By the Rational Root Theorem, the only solutions for $ x$ can be $ x \equal{} \pm 1$ and $ x \equal{} \pm 13$. By Vieta's, all the solutions multiply to $ 13$. Clearly, if $ x \equal{} \pm 1$ for all $ 19$ solutions, they do not multiply to $ 13$. Therefore, there must exist at least one instance where $ x \equal{} \pm 13$. It is obvious that there is exactly one instance where $ x \equal{} \pm 13$.

So? That only shows that at least one root has an absolute value of 13. What if there is a single root at $ x\equal{}\minus{}13$, a single root at $ x\equal{}\minus{}1$, and the rest at $ x\equal{}1$?

In that case, it doesn't sum to $ 7$ as given by Vieta's.

By Vieta's, the sum of all roots must be $ 7$.

From above, we cannot have $ x \equal{} 13$ as a root. $ \minus{}13 \plus{} 18 \times 1 \equal{} 5 \neq 7$. No other positive roots could exist, so $ x \equal{} \minus{}13$ is not a solution.

Finally, we're getting somewhere. The point that I have been trying to make over this entire thread is that no one has given an explicit proof that there is a root at $ x\equal{}13$, but all the information you need has now been posted.

So here's what we know:

-By the Fundamental Theorem of Algebra, there are 19 roots, if you count multiplicities.
-The problem states that all the roots are integers. Note the problem explicitly states that they all are integers, so there are no imaginary roots.
-Because the polynomial is monic, factoring it makes all of the factors some form of $ (x \minus{} a)$ where a is an integer.
-Because that last point is true, all of the coefficients of P(x) are rational and integers.
-Therefore, by the Rational Root Theorem, all of the roots are one of $ \minus{} 1$, $ 1$, $ 13$, and $ \minus{} 13$.
-By my logic in a previous post, 13 is a root and therefore has to be the largest.

[quote="fishythefish"]Finally, we're getting somewhere. The point that I have been trying to make over this entire thread is that no one has given an explicit proof that there is a root at $ x \equal{} 13$, but all the information you need has now been posted.[/quote] Although I might have done it unclearly, I proved it in my previous post.

Ihatepie had a complete solution, albeit not very formal (but that's okay since this question is a multiple-choice question). I think the confusion came from not reading the statement that all solutions are integers.

Or at least, the interpretation of said statement.

How can you interpret it differently?
It clearly states that all roots of P(x) are integers.

[quote="fishythefish"]There are two ways of interpreting that statement:

1) All [b]real[/b] roots of $ P(x)$ are integers. (Because most problems tend to ask for all real solutions; in fact, many textbooks would say that $ x^3$ has only 1 root, because they don't even consider complex or degenerate roots.)

2) All roots (including complex and degenerate roots) are integers. (Which effectively says that all 19 roots are real, there will be multiplicities, and there are no complex or degenerate roots.)

It depends what the reader thinks the original poster meant. From a purely mathematical point of view, I would agree with interpretation 2 here, because if interpretation 1 is meant to be used, the problem should have said, "all real roots of P(x) are integers."[/quote]

The problem says "It is also known that all roots of P(x) are integers. "  Also, what you said in 1), $ 0$ is [b]the one and only root [/b]of $ x^3$.

Sorry, that was the wrong function. $ x^3$ falls under case 2, because of the multiplicity.

But consider $ x^3\plus{}1$.

Ah, but in that case, not all roots are integers. If you were to tell me that all the roots are integers, I would say you are wrong, because the roots to $ x^2 \minus{} x \plus{} 1$ are not integral. In fact, they're complex, so they can't possibly be integral. However, if you said that all real roots are integral, you would be right. There's a difference between saying all roots are integers and all real roots are integers.

I believe the statement that all roots are integers directly implies that all roots are real, for complex roots with nonzero imaginary components are not integers, so no such complex roots could exist.

That's why I said the problem matters on the interpretation.

We are all interpreting it from a purely mathematical strong point. (Case 2)


Asymptote
geometry
geometric transformation
function

Hey im new to this site and since i dont understand the way my teacher teaches, i figured id enlist some more help.
Im working on a problem with asymptotes and it reads

Write and equation for the translation of y=2/x with the given asymptotes

1. x = 2; y= 3

and so on, i dont know what in the world this really means, but i get asymptotes just not this. Thanks.

please be more carefull where you post the next time :) This is the Oympiad section >> Algebra Open Question (ie you are supposed to post [b]very hard[/b] algebra questions here).

I am moving your posts to a more appropriate area of the forum.

[hide]
Since the asymptotes are $x=2$ and $y=3$
We can see that the graph of the function was transformed 2 units right and 3 units up.
Therefore the equation should be $y=\frac{2}{x-2}+3$.[/hide]


How do I describe something more complicated like $ \ce{SF6}$ in terms of Molecular Orbital Theory?

Now that I have a greater understanding of MO Theory I can actually draw the Partial MO Diagram for $ \ce{SF6}$ (the parts relevant to bonding). So I found that the bond order of this molecule is $ 4$. Is that in accordance with experimental data?

How can bond order be 4? There are six simple bonds S-F.


[quote="Brend"]Hi!

Show that if x,y,z are reals such that (x>=y>=z>0) then:

x^2(y/z)+y^2(z/x)+z^2(x/y)>=x^2+y^2+z^2

Bye[/quote]

I`m not sure do I understand what you wrote.

$\frac{yx^{2}}{z}+\frac{zy^{2}}{x}+\frac{xz^{2}}{y} \geq\ x^2 + y^2 + z^2$

Is this it?

As $x/y + y/x \geq 2$ for all x, y we have
\[ \frac{xy^2}{z} + \frac{zy^2}{x} + \frac{yz^2}{x} + \frac{xz^2}{y}  + \frac{zx^2}{y} + \frac{yx^2}{z} \geq 2(x^2 + y^2 + z^2)\]
so it suffices to show that \[ x^2\frac{y}{z} + y^2\frac{z}{x} + z^2\frac{x}{y} \geq x^2\frac{z}{y} + y^2\frac{x}{z} + z^2\frac{y}{x}\] which reduces to \[ x(y^2 - z^2) + yz(y - z) \geq 0\] which is true because $x \geq y \geq z$.

I really don't understand your last step !!!!!


geometry
vector
rotation
combinatorics unsolved
combinatorics

[quote="discredit"]Given a regular $ 2n$-gon, show that each of its sides and diagonals can be assigned in such a way that the sum of the obtained vectors equals zero.[/quote]
One of my favourite problems :)
Solution:
If it is possible to assign vectors to each side and diagonal of some regular $ k$-gon,so that their sum equals to zero vector,then we will call this $ k$-gon - [b]"good"[/b].
We will show that if we have some "good" regular $ n$-gon,then regular $ 2n$-gon is "good",too.
Let $ A_1A_2\dots A_{2n}$ be some regular $ 2n$-gon.Divide all its vertexes into two sets $ A_1A_2\dots A_{2n\minus{}1}$ and $ A_2A_4\dots A_{2n}$.Obiosuly vertexes from one set form regular $ n$-gon,denote them as $ R_1$ and $ R_2$,and as we know these $ n$-gons are "good".So we can assign vectors to each side and diagonals of $ R_1$ and $ R_2$,so that their sum is equal to $ 0$.
Now take each vertex of $ R_1$ and lead vector from it to each vertex from $ R_2$.It is clear that their sum is equal to $ 0$.
Now suppose that $ 2n\equal{}2^{k}r$,where $ r\in\mathbb{N}$ is odd and $ k\geq 1$.
It is enough to show that regular $ r$-gon is "good".Let $ A_1A_2\dots A_r$ be our regular $ r$-gon.
For each vertex we will lead a vector from it to next $ \frac{r\minus{}1}{2}$ vertexes,in a clockwise direction.As it showed on this $ 7$-gon:
[img]http://img187.imageshack.us/img187/8670/adic6.png[/img]
Obiously their sum is equal to $ 0$,because if we turn regular $ r$-gon with respect to its center in angle $ \frac{\pi}{r}$,our vectors will turn to itself.

[quote="Erken"]...Now take each vertex of $ R_1$ and lead vector from it to each vertex from $ R_2$.It is clear that their sum is equal to $ 0$...[/quote]
I can't see why this holds. Actually, I didn't look too careful but it seemed untrue for $ 2n \equal{} 10$. The rest of the problem is just recognizing that every graph which has all its vertices' degrees even, has a Eulerian path. Direct every vector to the same direction on this path and sum of them are $ 0$.

So you are claiming that, if we divide all vertices of a regular $ 10$-gon into two sets, $ 1,3,5,7,9$ and $ 2,4,6,8,10$ and lead a vector from each vertex of the first set to each vertex of the second set, the total sum of vectors will be non-zero, right?

But that has to be untrue, since if you rotate this vector system with respect to the centre of our 10-gon to a $ \frac {2\pi}{5}$ angle, the sum should turn into itself, but that means that the sum is $ 0$.


geometry
ratio
geometric transformation
reflection
inequalities
circumcircle
calculus

let $a>0$. For all the tangent lines on the curve $y=a-x^{2}$ in the first quadrant, determine which one whose intersection points with the x-axis and the y-axis forms a triangle with a minimum area.

[hide="Here is the answer."][b][u]Answer :[/u][/b] $\boxed{\ Y_{P_{\mathrm{min}}}=\frac{2a}{3}\ }$, i.e. $P_{\mathrm{min}}\left(\sqrt{\frac{a}{3}},\frac{2a}{3}\right)\in G_{f}$, where $f(x)=a-x^{2}\ ,\ x\in \left(0,\sqrt a\right)\ .$[/hide]

The tangent line at $(t,\ a-t^{2})$ on $y=a-x^{2}$ is $y=-2t(x-t)+t^{2}\Longleftrightarrow y=-2tx+t^{2}+a.$ Thus this tangent line passes through the points $A\left(\frac{t^{2}+a}{2t},\ 0\right),\ B(0,\ t^{2}+a).$
Let $S(t)$ be the area in question, we have $S(t)=\frac{(t^{2}+a)^{2}}{4t}.$
Since the tangent point lies in the first quadrant, the range of $t$ is $t>0$ and $a-t^{2}>0\ (a>0) \Longleftrightarrow 0<t<\sqrt{a}.$

$S'(t)=\frac{1}{4}\cdot \frac{2(t^{2}+a)\cdot 2t\cdot t-(t^{2}+a)^{2}}{t^{2}}$

$=\frac{(t^{2}+a)(\sqrt{3}t+\sqrt{a})}{4t^{2}}\cdot (\sqrt{3}t-\sqrt{a}).$

Thus $S(t)$ is local mimimum and  minimized at $t=\sqrt{\frac{a}{3}},$

yielding $S_{min}=S\left(\sqrt{\frac{a}{3}}\right)=\boxed{\frac{4\sqrt{3}}{9}a\sqrt{a}}.$

That's correct  :)

But $x \in (0, \sqrt{a})$ is not the same as $x \in [0, \sqrt{a}]$

How about this:

Find the ratio of altitude to base radius which will minimize the surface area of a closed right circular cylinder of prescribed volume $V$.

[b][u]Answer :[/u][/b] [b]altitude=[/b]$h$ and [b]base radius=[/b]$r\Longrightarrow h=2r\ .$[hide="Here is a nice and easy solution without calculus."]$V(r,h)=\pi r^{2}h$ - $\mathrm{constant}\ ; \ S(r,h)=2\pi r(r+h)$ -  $\mathrm{minim}\Longleftrightarrow$
$r^{2}h$ - $\mathrm{constant}\ ;\ r^{2}+rh$ - $\mathrm{minim}\Longleftrightarrow$
$r^{2}\cdot \frac{rh}{2}\cdot \frac{rh}{2}$ - $\mathrm{constant}\ ;\ r^{2}+\frac{rh}{2}+\frac{rh}{2}$ -  $\mathrm{minim}\Longleftrightarrow$
$r^{2}=\frac{rh}{2}\Longleftrightarrow \boxed{\ h=2r\ }$, i.e. [b][u]the axial section is a square ![/u][/b][/hide]

I obtained by using $A.M.-G.M.$ as well, but which is same as Virgil's solution.

[hide="Here is a very nice and easy new extremum problem."][color=darkblue][b][u]1. A new extremum problem (without calculus).[/u][/b] Ascertain $x>0\ ,\ y>0$ for which $x^{2}+y^{2}=1$ and the sum $x+xy$ is maximum.
[b][u]2. A geometrical interpretation.[/u][/b] Let $ABC$ be a triangle for which $AB\perp AC$. Denote the point $D\in BC$ for which $AD\perp BC$ and $a=BC,\ b=CA,\ c=AB,\ h=AD$. Prove that $\boxed{\ h+\max\{b,c\}\le \frac{3a\sqrt 3}{4}\ }$ (give and a geometrical proof).[/color][/hide][hide="Here is the proof."][color=darkblue]
$\blacktriangleright 1.\ x(1+y)$ - $\mathrm{max}\Longleftrightarrow$ $x^{2}(1+y)^{2}$ - $\mathrm{max}\Longleftrightarrow (1-y)(1+y)^{3}$ - $\mathrm{max}\ .$
But $(1-y)+\frac{1+y}{3}+\frac{1+y}{3}+\frac{1+y}{3}=2$ - $\mathrm{constant}$.
Therefore $\frac{(1-y)(1+y)^{3}}{27}$ - $\mathrm{max}$ $\Longleftrightarrow$ $1-y=\frac{1+y}{3}=\frac{2}{4}$ $\Longleftrightarrow$ $y=\frac{1}{2}\ ,\ x=\frac{\sqrt 3}{2}\ .$
[b]Remark.[/b] $x>0\ ,\ y>0\ ,\ x^{2}+y^{2}=1\Longrightarrow x(1+y)\le \frac{3\sqrt 3}{4}\ .$

$\blacktriangleright 2.$ [b]A geometrical proof.[/b] Denote the reflection $E$ of the point $A$ w.r.t. the point $D$.
It is well-known the remarkable inequality $2p\le 3R\sqrt 3$ in a triangle,  where $R$ is the its circumradius and $p$ is the its semiperimeter.
For the triangle $AEC$ this inequality becomes the inequality $2(h+b)\le \frac{3a\sqrt 3}{2}$, i.e. $h+b\le \frac{3a\sqrt3}{4}$ a.s.o..[/color][/hide]

It's correct. $\boxed{\frac{h}{r}=2}$ But how did you get that answer, did u use $AM-GM$? What do u mean by $constant$ and $minim$ ?


Let $ n$ be a string of digits $ n$ digits long.
What is the minimum $ n$, or length of the string, such that
[list]All possible permutations of $ 2$ digits are represented in the string
All permutations of $ 3$ digits
All permutations of $ k$ digits[/list]

Example $ 1234$ has the permutations of two digits $ 12 \ , \ 23 \ , \ 34$.

The example given is wrong.  The smallest string containing all permutations of $ 2$ digits is $ 121$.

:wink: Your misintepretted my example.  The example was just to show how the permutations of $ 2$ digts can be arranged and overlay.

...except those are $ 2$-digit subsets of $ 4$ digits, which isn't what you're asking about.

It is just an small example.  It [i]just[/i] illustrates the concept of how the permutations can be "in the string". :P

Back to the question itself, is this just a combinatorical problem? Are there more interpretations?

I think your question is a little unclear:  I see a two-parameter question with only one parameter.  For positive integers $ n \geq k$, define $ f(n, k)$ to be the length of the shortest sequence whose entries are from the set $ [n] \equal{} \{1, \ldots, n\}$ such that every $ k$-tuplet of distinct* members of $ n$ appears as a consecutive block in the sequence.

For example, $ f(n, 1) \equal{} n$ for all $ n$ (the sequence $ (1,\ldots, n)$ or any other permutation will do), while $ f(2, 2) \equal{} 3$ with t0r's example $ (1, 2, 1)$ as the shortest possible.  In terms of this function, are you asking for $ f(n, n)$ or $ f(n, 2)$?

This is closely related to de Bruijn sequences -- in that case, the sequences are circular, so $ (1, 2, 3)$ counts the pairs $ 12$, $ 23$ and $ 31$.

* I'm guessing that this is what you want -- we can also ask the question for $ k$-tuplets with repeated members allowed.

Sorry for the confusion.  :oops:
Thanks for telling me.

Re-phrase
If $ n$ represents a length of a string containing digits, 0 to 9, then find the smallest $ n$ such that every permutation of $ k$ digits from the set $ \{ 0 \ , \ 1 \  , \ 2 \ , \ ... \ , \ 9\}$ is represented $ k \in \mathbb{Z}^{\plus{}} \ , \ k \le 10$.
What if $ k\equal{}2$? $ k\equal{}3$? For any $ k$?

Please tell me if it is unclear still.

[quote="JBL"]In terms of this function, are you asking for $ f(n, n)$ [/quote]

That's how I originally read the question, hence my confusion.


parameterization
linear algebra
matrix
linear algebra unsolved

9x - 18y + 20z = -40
29x - 58y + 64= -128
10x - 20y + 21z = -42

There are infinitely many solutions with one arbitrary parameter... but why is this the case?

Also, how do you solve for the variables that are not arbitrary parameters?

Thanks!

Have you done Gaussian elimination?

$\left(\begin{matrix}9 &-18 & 20 &-40\\ 29 &-58 & 64 &-128\\ 10 &-20 & 21 &-42 \end{matrix}\right)$

Will reduce to $\left(\begin{matrix}1 &-2 & 0 & 0\\ 0 & 0 & 1 &-2\\ 0 & 0 & 0 & 0 \end{matrix}\right)$, so

We can tell from this that $x-2y=0\Rightarrow x=2y$ and $z=-2$, from here you should be able to do the rest.


geometry
incenter
angle bisector
geometry proposed

Let $ABC$ be a triangle and let $(O)$ be a circle passing through $A$ and $C$ . Sides $AB$ and $BC$ meet $(O)$ again at $D$ and $E$ , respectively . Let $(O')$ be the incircle of the circular triangle $EBD$ . Suppose $(O')$ touches the arc $DE$ at $M$ . Prove that : the angle bisector of $\angle AMC$ passes through the incenter of triangle $ABC$

See http://www.mathlinks.ro/Forum/viewtopic.php?t=33 , http://www.mathlinks.ro/Forum/viewtopic.php?t=6086 and http://www.mathlinks.ro/Forum/viewtopic.php?t=25674 .

  darij


Γνωριζει καποιος που ασχολειται με αναλυτικη γεωμετρια,αν η γραμμη που περναει απο τα 2 σημεια τομης 2 εξισωσεων υπερβολης δινεται απο την αφαιρεση των αντιστοιχων εξισωσεων υπερβολης(οπως συμβαινει στον κυκλο δλδ)?

Τhx !  :maybe:

Ναι αφου επαληθευει και τις δυο και γινεται ομοια με τον ριζικο αξονα στους κυκλους..
Μονο που στην περιπτωση που τα σημειατομης  ειναι περισσοτερα απο 2 εχεις περισσοτερες απο μια εξισωσεις


SMO 200, Open #7

In how many ways may 7 different prizes be awarded to 5 students in such a way that each student has at least 1 prize?

First each person needs a prize.
So first we give 5 prizes out of the 7 in 7P5 ways.
Then for the remaining two we chose two ppl in 7P2 ways.
So by fundamental principle of counting no of ways
= 7P5 X 7P2.

I'm pretty sure it's not that simple; you've counted some situations more than once. 7P5 includes giving 1 to person A, 4 to B, 5 to C, 6 to D, and 7 to E, and then the next 7P2 includes giving 2 and 3 to person A. This is the same as giving 3 to A, 4 to B, so on, and then giving 1 and 2 to person A. Both ways are considered separate under your counting, when they should not be.

[hide="My attempt"]Consider the possible ways of giving 3 prizes to one person and one to the other four. Then there are ${7 \choose 3}$ ways to give 3 prizes to the one person. Multiply this by $5!$ to include every possible rearrangement of people, including the distribution of the last four prizes. This gives $4200$ possibilities.

Now consider the possible ways of giving 2 prizes to two people and one to the other three. Now we have ${7 \choose 2}\cdot{5 \choose 2}$ ways of distributing the prizes to those two people getting two. Then we multiply by $5!/2$ to include all rearrangements while excluding the ambiguous rearrangement of switching the two people that got two presents. This gives a result of $12600$ possibilities.

$4200+12600 = \fbox{16800}$[/hide]

Use principle of inclusion-exclusion.

Let $A$ be the set of distributions where person $A$ gets nothing.

We want $U-A\cup B\cup C\cup D\cup D$ where $U$ is the universe.

Indeed there is overcounting in pencilkarthik's method: Suppose the presents are labelled 1 to 7, and that presents 1 to 5 are given to students A to E respectively. Then presents 6 and 7 are given to student A as well. This is the same as if presents 2 to 5 were given to students B to E respectively, present 6 was given to student A, and then presents 7 and 1 were given to student A subsequently. The method doesn't distinguish between these 2 when they are the same.

I think MellowMelon's method of counting doesn't leave loopholes, that should be correct. For inclusion-exclusion, I didn't think of it during the contest, it's a good way though :P

Consider the possible ways of giving 3 prizes to one person and one to the other four. Then there are ${7 \choose 3}$ ways to give 3 prizes to the one person.

Multiply this by $5!$ to include every possible rearrangement of people, including the distribution of the last four prizes. This gives $4200$ possibilities.

"Now first of all the students are distinct so there is no qstn of rearranging them , so only rearranging prizes makes sense.
Next we shouldnt mult by $5!$ we should actually mult by $4!$
which accounts for the remaining 4 prizes to be given to the 4 students.Each student always stays in his place.Only prizes rearrange"

Now consider the possible ways of giving 2 prizes to two people and one to the other three. Now we have ${7 \choose 2}\cdot{5 \choose 2}$ ways of distributing the prizes to those two people getting two.

"Here i think there is another flaw ${7 \choose 2}$ is fine but since the 2 students are distinct it should be 5P2 and not 5C2."

Any way my soln has another flaw that it doesnt consider the 2 prizes being given to one person.So throw it.

The logic of the ${7 \choose 2}\cdot{5 \choose 2}$ is this: The ${7 \choose 2}$ comes from picking 2 prizes to give to person 1. Then there are 5 prizes left, two of which we must give to person 2. Thus, ${5 \choose 2}$ possible prizes to give him. The fact that we are double counting which of these two people gets which pair of prizes is accounted for by the $5!/2$ as opposed to $5!$.

Dividing by 2 is a correct, or more accurately, dividing by $2!$. Somehow i forget that in most counting problems, it's always double counting that causes the error  :oops:


function
real analysis
real analysis unsolved

Show that if $f: [0,1]\rightarrow [0,1]$ is a continous function and it has topological transitivity then periodic points of $f$ are dense in $[0,1]$.
Topological transitivity means there for every open sets $U$ and $V$ there is $n>0$ such that $f^n(U)\cap V\neq \emptyset$.

Suppose we can find a non-degenerate compact subinterval $ I$ of $ [0,1]$ in which $ f$ has no periodic points. I'll denote the $ n$'th iterate of $ f$ by $ f^{n}$, and the identity map on some subset $ A$ of $ [0,1]$ by $ 1_{A}$. Notice that $ f^{n}(I),\ n\ge 0$ are all compact intervals (possibly degenerate). We want to reach a contradiction; we do this in a series of steps:

(1) [i]None of the intervals $ f^{n}(I)$ contains a fixed point of $ f$[/i]

Let $ y\in f^{n}(I)$ be a fixed point of $ f$, for some $ n\ge 0$. Our assumption that $ I$ contains no periodic points implies that for all $ n\ge 1,\ f^{n}-1_{I}$ has constant sign. If $ x\in I$ such that $ f^{n}(x)=y$ (which is, by assumption, different from $ x$), then $ f^{m}(x)-x$ has the same sign for all $ m\ge n$, and in conclusion $ f^{m}-1_{I}$ has the same sign for all $ m\ge n$. This is easily seen to contradict the topological transitivity of $ f$.

(2) [i]None of the intervals $ f^{n}(I)$ contains a periodic point of $ f$[/i]

Assume we can find a periodic point $ y\in f^{n}(I)$ for some $ n\ge 0$, and let $ T\ge 1$ be its period. Then, for all $ m\ge n$, the interval $ f^{m}(I)$ intersects one of the intervals $ f^{n}(I),\ \ldots,\ f^{n+T-1}(I)$, and hence the number of connected components of the sets $ S_{p}=\bigcup_{i=0}^{p}f^{i}(I),\ p\ge 0$ is bounded. Combined with the fact that, by transitivity, $ \bigcup_{p}S_{p}$ is dense in $ [0,1]$, this implies that $ [0,1]\setminus\bigcup_{p}S_{p}$ is a finite set $ \{x_{i}\ |\ 1\le i\le k\}$ (intuitively speaking, because the number of components of $ S_{p}$ is bounded, increasing $ p$ only enlarges these finitely many intervals, and the points left out are the finitely many "caught between" the intervals). Of course, by (1), the fixed points of $ f$ are among the $ x_{i}$. We actually prove that the $ x_{i}$ are precisely the fixed points of $ f$. Assume, for instance, that $ x_{1}<x_{3}$ are fixed points of $ f$, that $ f>1_{(x_{1},x_{3})}$, and that $ x_{2}\in(x_{1},x_{3})$ is the smallest $ x_{i}$ larger than $ x_{1}$ (the other cases can be treated similarly). Then, because $ f(x_{2})>x_{2},\ p$ can be chosen so large that $ x_{2}\in S_{p}$ (a picture should clear things up), contradicting the definition of the set $ \{x_{i}\}$. We have thus shown that $ \{x_{i}\}$ is the set of fixed points of $ f$.

If $ x_{1}<x_{2}$ are consecutive fixed points, then $ \left(\bigcup S_{p}\right)\cap(x_{1},x_{2})=(x_{1},x_{2})$, so $ f$ cannot take the values $ x_{1},x_{2}$ inside $ (x_{1},x_{2})$. This implies that $ f$ maps $ (x_{1},x_{2})$ into itself, and for all $ x\in(x_{1},x_{2})$ the sequence $ f^{n}(x),\ n\ge 0$ is strictly monotonic. Clearly, this contradicts the transitivity of $ f$. There is now only one case left, namely the case when $ f$ has exactly one fixed point $ x_{1}$. It follows from our previous discussion that $ f$ takes the value $ x_{1}$ precisely in $ x_{1}$, and that $ f-x_{1}$ has constant and opposite signs on the intervals $ (0,x_{1})$ and $ (x_{1},1)$. If $ f<x_{1}$ on $ (0,x_{1})$, then the resriction of $ f$ to $ [0,x_{1}]$ has topological trnsitivity, and also satisfies $ f>1_{[0,x_{1}]}$, two facts which are incompatible (I assume here that $ x_{1}\not\in\{0,1\}$). On the other hand, if $ f>x_{1}$ on $ (0,x_{1})$ and $ f^{2}$ has no fixed points in $ [0,x_{1}]$ other than $ x_{1}$, then the previous sentence applies to $ f^{2}$ (not that in this case $ f^{2}$ does indeed have topological transitivity on $ [0,x_{1}]$). Finally, if $ f>x_{1}$ on $ (0,x_{1})$ and $ f^{2}$ has a fixed point in $ [0,x_{1}]$ other than $ x_{1}$, then we can work with the restriction of $ f^{2}$ to $ [0,x_{1}]$ which now has at least two fixed points, a case which has already been treated. This finishes the proof of (2).

(3) [i]The end of the proof[/i]

(2) says, basically, that for all $ m\ne m,\ f^{m}-f^{n}$ is non-zero and hence has constant sign on $ I$. By transitivity, we can find $ n$ such that $ f^{n}(I)\cap I\ne\emptyset$ and $ f^{n}>1_{I}$ (call these two conditions $ (*)$), and we can find $ m$ such that $ f^{m}(I)\cap I\ne\emptyset$ and $ f^{m}<1_{I}$ (similarly, denote these two conditions by $ (**)$). Check now that $ (*)$, together with the previous observation, implies $ f^{mn}>1_{I}$, while $ (**)$ implies $ f^{mn}<1_{I}$. This provides the contradiction we were looking for.

[quote="grobber"] ... Our assumption that $ I$ contains no periodic points implies that for all $ n\ge 1,\ f^{n} \minus{} 1_{I}$ has constant sign... [/quote]
I1)  don't understand Why? :maybe: mayby there must be for [b]each[/b] $ n$  , $ f^{n}(x) \minus{} 1_{I}(x)$ has constant sign $ \forall x \in I$. Or I mean sign of this expression $ f^{n}(x) \minus{} 1_{I}(x)$ only depends on  $ n$
2) Can I say that $ f$ has topological transitivity if for all open $ A$ and $ B$  $ \in I$ and for all $ N > 0$ there exist $ n > N$ such that :
$ f^{n}(A) \cap B\neq \emptyset$


calculus
integration
function
inequalities
trigonometry
real analysis
real analysis solved

Let $f$ be a continiously differentable function, such that $f(-\frac{\pi}{2})=f(\frac{\pi}{2})=0$. Prove that $\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(f(x))^2dx\leq\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}(f'(x))^2dx$

Well, there is a Fourier series solution. With those boundary conditions, it's slightly more convenient to let $g(x)=f\left(x+\frac{\pi}2\right)$ and make the interval $[0,\pi].$

$g(x)=\sum_{n=1}^{\infty}b_n\sin(nx)$; $g'(x)=\sum_{n=1}^{\infty}nb_n\cos(nx)$

By Parseval's identity:

$\int_0^{\pi}(g(x))^2dx=\frac{\pi}2\sum_{n=1}^{\infty}b_n^2$ and $\int_0^{\pi}(g'(x))^2dx=\frac{\pi}2\sum_{n=1}^{\infty}n^2b_n^2$

From that, the inequality is clear, as is the condition for equality: that $b_n=0$ for all $n\ge 2$

In other words, we have equality when $f(x)=b\cos x.$

Here is another solution:

Take any $0<\alpha<1$. Then

\[
0\leq \int_{-\pi/2}^{\pi/2} \left( f'(x)+\alpha f(x)\tan{(\alpha
x)}\right )^2dx=
\]
\[
=\int_{-\pi/2}^{\pi/2} (f'(x))^2dx
+\alpha\cdot\int_{-\pi/2}^{\pi/2} \tan{(\alpha x)}df^2(x)
+\alpha^2\cdot\int_{-\pi/2}^{\pi/2} f^2(x)\tan^2{(\alpha x)}dx=
\]
( calculating the second integral by integration by parts)
\[
=\int_{-\pi/2}^{\pi/2} (f'(x))^2dx -
\alpha^2\cdot\int_{-\pi/2}^{\pi/2} f^2(x) \frac{1}{\cos^2{\alpha
x}}dx+ \alpha^2\cdot\int_{-\pi/2}^{\pi/2} f^2(x)\tan^2{(\alpha
x)}dx
\]
\[
=\int_{-\pi/2}^{\pi/2} (f'(x))^2dx -\alpha^2\cdot
\int_{-\pi/2}^{\pi/2} f^2(x)dx.
\]

So
\[
\alpha^2\cdot \int_{-\pi/2}^{\pi/2} f^2(x)dx\leq
\int_{-\pi/2}^{\pi/2} (f'(x))^2dx
\]

Finally, by passing to the limit $\alpha\to 1$, we get the
desired inequality.


MATHCOUNTS
AMC
AIME
AMC 8
email
Math Kangaroo

I didn't really know where I should have posted this. There didn't seem to be a place for general questions like these, and this forum in particular seemed to have the widest audience for this question, and also seems like the most active.

So, basically how did you get involved in math competitions? Because I know that for me, it was somewhat due to parents. That was the reason I got involved, but I ended up taking it on as my own interest when I started enjoying it. I know a lot of kids probably were just good at math and after being recognized, maybe introduced to it through school. Anyways, I'm just interested to see how some of the people most involved in these math competitions got their start.

I wonder about this also with regard to kids who do really well at a young age, like Mathcounts, since it seems like middle school would be kind of one of the earlier stages at which most kids are recognized as genuinely good math students who could be good at these competitions. So for those Mathcounts kids who do really well, I'm guessing they must have had interest and training before that middle school age. So I'm wondering how that all started.

But this is a question for everyone, even if you didn't do Mathcounts or math competitions at an early age. How did it start? :)

I got started with the math kangaroo in 4th and 5th grades- we all had to take it and i thought it was fun. Then I did mathcounts in middle school (doing ok, made it to states in CA), but i didn't actually start studying until after 8th grade  :rotfl:

In 8th grade at about october or so, a kid in my school told me of mathcounts. We practiced and got a team together. I had a sorta successful year with a 1st cd at states and 2nd written with a 76th nats. This year I learned about the amcs and i'll take the aime next week.

Went to some local competition in 6th grade and I found out by a teacher. Also, my teacher pressured me into doing AMC8 in 8th grade.

My school had me doing MOEMS in second grade. I was good at it (and loved doing it), so I then did MathCounts in sixth through eighth, and here I am now.

Ohio Math League in 4th and 5th grade. Then Mathcounts in Middle school. The desire to get into nationals after I realized there was a chance was what got me more involved.

Had been doing math using the Chinese curriculum at home since very young (I had a much better work ethic back then :D ), older siblings of friends had all done mathcounts (including one who placed 2nd at nationals), so, I started looking at probs in 4/5 grade, competed 6-8 grade.

My mom decided to force the AMC's on me last February (6th grade).  I did OK on them, and I started to pursue math competitions without forcing of parents anymore.

Looking at the thread, it seems like y'all started contest math before me... :|

Well, I suppose I took some random Math League test in 4th grade, which was my first "competition" although it's easy. Then I started going to this math center, but I didn't really do anything until sixth grade. I suppose I actually started in sixth grade, because of Mathcounts.

i came to a private school in 6th grade where mathcounts was big. I made the team. They over the summer, i found out about AoPS. :D

I was gifted, my mom yelled "HELP!!!" on an email list and my MC coach found her. That's how I got into MathCounts.

It turns out that she also was running a high-school math circle. That's how I got into the rest of them.

errr in elementary school i was considered "gifted" at math [ i was SOOOOOO not.] so, i worked on middle school "harder" math. >< but i was really really stupid. so when i got to middle school, i tested into my school's mathcounts program and realized how stupid i was [average of 10-15 on sprints, if not less] but i wasted entire 6th grade doing nothing, then in 7th grade, i was like 'crap if i want to do well i have to work' actually. at first my parents made me but then i realized i wanted to do it. so i started at the basics doing simple problems, then working my way through chapter , state, and finally nationals. i never made it to nationals, even in 8th grade, but i learned soo much. plus it helps a lot with amc [which i found out about in 8th grade]. don't have much time for math anymore. but i still enjoy it :)

In sixth grade, my math teacher told me that I should join the school math team which, despite the fact that they only did an easy local competition, gave me whatever start I had. Then in seventh grade, I found out about MathCounts, started my school's team, made nationals, and haven't stopped.

Start at 3rd grade in China because many people were more or less involved in this activity. Start to like it myself since middle school. Start to really like it since coming to U.S (10th grade).

I did some local math competitions in elementary / early middle school, but they were silly (computing large products?...)

In 7th grade, my mom heard from a friend about AMC8 and MathCounts, so I took them and did pretty well (making state MC). Then I continued doing stuff... I think I started becoming self-motivated around 8th/9th grade (perhaps after going to AMP after 8th?)

found out about the site from college confidential, and I looked into the amc 12 seriously around the january time frame. I wish I would have known about, oh, 5 years ago, but at least I still have my senior year ;]

Um randomly ended up at a MATHCOUNTS school round test in 8th grade, made the team, tied for 5th at states (CA), and here I am now...

You got 5th at ca states after 4 or so months?

I'm gonna say you are a truly gifted individual.

I tied for fifth, but my official rank ended up being like 9ish since there were six-eight people tied for fifth place.

My mom signed me up for Math Kangaroo in second grade. :P
I got a great math teacher (my avatar) in fourth grade who taught me competitive math (my mom initially thought he was a quack).
Since 6th grade, each successive year has been more intense than the previous - I'm in 11th now, and practice more than ever.

My math teacher at 2nd grade encouraged me to do some competitions (I was in China back then), and I thought they're fun and continued with the interest.
Kinda slowed down during 6th grade then started again during 8th.
Didn't realize this is 6 years old...

hm i don't think you should revive 6 year old topics...

Heck, how did you even find this thread?

By scrolling down a lot or using the search box.

On April Fools Day, we should all bump up a bunch of threads from very long ago and just put "bump, Happy April Fools Day!"

I'm so curious. What was the FIRST-EVER topic ever made on AoPS? We should bump that :)

In [url=https://artofproblemsolving.com/community/search]Search[/url], don't fill out anything [b]except[/b] for changing sorting to "Sort results by post time, oldest first", which should give you the oldest post. :P

Oldest post: https://artofproblemsolving.com/community/c6h2

Oh dang, I did NOT realize this was from 2009. It was under the "Math Kangaroo" tag (not "AIME poll" as previously mentioned).


function
advanced fields
advanced fields unsolved

Let $ X \equal{} \{f: \;\;A \rightarrow \mathbb R|\;A\subset \mathbb R$ finite $ \}$
Evaluate $ |X|$

I think the answer is [hide]$ 2^{\aleph_0}$. I can justify this assumption in this way:
the problematic disequation is $ |X|\ge 2^{\aleph_0}$. I consider the function $ \phi: \; \mathbb N^{(0,1)}\rightarrow X$.
Let $ \phi(f)\equal{}A$ where $ f: \; (0,1) \rightarrow \mathbb N$ and $ A\equal{}(0,1) \cup \{x\plus{}f(x)|x \in (0,1)\}$.
Do you think I'm right?[/hide]

Sure. $ |X| \le 2^{\aleph_0}$ because for every finite subset of $ \mathbb R$ we have $ 2^{\aleph_0}$ many such functions, and we have $ (2^{\aleph_0})^n \equal{} 2^{\aleph_0}$ subsets of size $ n$ for each $ n \in \mathbb N$. We take a union of $ \aleph_0$ subsets of size $ 2^{\aleph_0}$ which is still that size.
That $ X$ is at least that is in fact the easiest observation: for each $ x \in \mathbb R$ we have a function $ f$ that maps $ x$ to $ 0$ and all these functions are different.


rotation Alcumus counting distinguishability Support

Well, its only a little bit of karma so it doesn't really matter to you. Just rate some more problems.

The problem isn't that I am running out of karma (I have over 1600).

There are still two of the same problem (at least in my subject report).

[quote="PowerOfPi"]I notice that this problem:

"In how many ways can 5 different keys be placed on a keychain? (Two arrangements are considered the same if one can be rotated or flipped to be identical to the other.)"

was repeated twice. I submitted a bug report about it. How do I find out if it has been fixed or not? How do I find out if I lost karma?[/quote]

If you log on to the Alcumus landing and your bug report has been validated, there should be a notice which says so.  I've had a couple reports validated, and a message on the Alcumus landing notified me.

The landing page is the page you land on when you click Alcumus. It has three main options, Problems, Report, and Videos.

Can you tell me what subject the problem is appearing twice in?

It is in Counting with Symmetry. See the second and sixth problem in the attachment. They are the exact same question but it is worded differently (distinguishable vs. different). I noticed it because I got them with only a few problems in between.

I believe that was done purposefully to test your consistency.


Purple paint is made with a 16:3:1 ratio of white paint:blue paint:red paint. How much white paint, in gallons, is needed in order to make one gallon of purple paint? Express your answer as a common fraction.

1 gallon of purple paint (20x) is made up of 16x white, 3x blue, and x red.  So16x (white paint) is needed for 20x of purple, so the answer is 16/20=4/5.

sorry if this is somewhat the same

why can't you just NOT use variables

we know that there is the ratio of 16 for white and a total of 20 so we get the answer

$\frac{16}{20}$

[size=50]please rate thanks ![/size]

[quote="markoboy"]
why can't you just NOT use variables[/quote]

You don't have to. However, it does help some people better understand the problem if they are not familiar with ratios.

In this case, there are 20 parts of paint.
Just add $16+3+1=20$
16 of them are white.
Therefore, the answer should be $\frac{4}{5}$ of a gallon.
So $\frac{4}{5} * 1=\boxed{4/5}$
^Slightly trivial step for this problem, but what if it was to make 100 gallons of purple paint? 24? etc.


inequalities function calculus derivative limit logarithms

THis problem is from UM Problems Of the Week. It's a great problem. Prove that n^(n+k) > (n+k)^n for the natural numbers n > 2 and k > 0.
P.S.ZAbelman Can't Answer

spoiler:

[hide]Fill in more details by request.

Let f(x) = (ln x) /x, then it's a strictly decreasing function on (e, + :inf: ) since the derivative f'(x) = (1 - ln(x)) / x^2 < 0 for x in (e, + :inf: ).

So f(n) > f(n+k) since k>0 and n :ge: 3.

f(n) > f(n+k) ==> the desired result.

[/hide]

Pork_Chop8 wrote:By your formula, f(n) = (ln n)/n and f(n+k) = (ln (n+k))/(n+k). So, since f(n) > f(n+k), we get (ln n)(n+k) > (ln (n+k))n. How does that prove that n^(n+k) > (n+k)^n.

[hide]

(ln n)(n+k) > (ln (n+k))n ==> ln n^(n+k) > ln (n+k)^n since ln a^b = b(ln a)

ln n^(n+k) > ln (n+k)^n ==> n^(n+k) > (n+k)^n since ln x is a strictly increasing function.

[/hide]

[hide]

We know that

[tex]

\lim_{x \to \infty} \frac{1}{x} = 0

[/tex]

We can say that

[tex]

\lim_{x \to \infty} x^{1/x} = \lim_{x \to \infty} x^0 = 1

[/tex]

Thus as x increases, x^(1/x) decreases to one.  We can say that

n^(1/n) > (n + k)^(1/(n+k))

for positive k.  Raising both sides to the nth power,

n > (n + k)^(n/(n+k)

Taking the base (n+k) logarithm of both sides,

log n > n/(n+k)

(n+k) log n>n

log (n^(n+k)) > n.

n^(n + k) > (n+k)^n[/hide]

nr1337, your reasoning has two instructive errors.  First, 1/x approaching 0 does not by itself imply that x1/x approaches 1.  By that same logic, you could argue that x1/ln(x) approaches 1, which is not true.

Second, even if you did show that x1/x approaches 1, you haven't shown that it decreases monotonically toward 1.  In fact, it doesn't; compare x = 2 and x = 3.


- any ideas on this one? -
i am trying to manipulate SUM (2^i*[log(i+1)]) : i=1 to n .... am not getting any where..
 :(

They're probably already in the simplest possible form- I highly doubt that there is a closed form.


modular arithmetic
number theory
Frobenius
combinatorics
Additive Number Theory
Additive combinatorics
IMO Shortlist

Let $ p$ and $ q$ be relatively prime positive integers. A subset $ S$ of $ \{0, 1, 2, \ldots \}$ is called [b]ideal[/b] if $ 0 \in S$ and for each element $ n \in S,$ the integers $ n \plus{} p$ and $ n \plus{} q$ belong to $ S.$ Determine the number of ideal subsets of $ \{0, 1, 2, \ldots \}.$

This is Frobenius stamps problem, case $n=2$, also known as Sylvester's problem. All positive integers no less than $pq-p-q+1$ can be expressed as $mp + nq$, and exactly half of the other cannot ...

Define $[n]_q$ as the remainder when $n$ is divided by $q$, and for $0\le i\le q-1$, let $a_i$ denote the smallest integer such that $qa_i+[pi]_q\in S$.

Then it's clear that $S$ is ideal iff $a_0=0$ and for $1\le i\le q-1$, $0\le a_i\le a_{i-1}+\frac{p+[p(i-1)]_q-[pi]_q}{q}=a_{i-1}+\left\lfloor\frac{pi}{q}\right\rfloor-\left\lfloor\frac{p(i-1)}{q}\right\rfloor$ (consider "jumping" between the residue classes $p(i-1)\pmod{q}$ and $pi\pmod{q}$), i.e. if $b_i=a_i-\left\lfloor\frac{pi}{q}\right\rfloor$ for $0\le i\le q-1$ with $b_0=0$, then there is a clear bijection between the ideal subsets and the nonincreasing lattice paths (each step of length $1$) from $(0,0)$ to $(q,-p)$ that never drop below the line $px+qy=0$.

Now take $t_i=p$ if the $i^{th}$ step is rightward and $t_i=-q$ if the $i^{th}$ step is downward so that $t_1+\cdots+t_{p+q}=0$, and consider the partial sums $s_i=t_1+\cdots+t_i$ for $1\le i\le p+q$. Since $p,q$ are relatively prime, they are pairwise distinct. Notice that the index $1\le m\le p+q$ that minimizes $s_m$ is the only one that satisfies $s_{i+m}-s_m\ge0$ for all $1\le i\le p+q$ (indices taken $\pmod{p+q}$). But $S$ is ideal iff $s_i\ge0$ for all $i$, so exactly one cyclic shift of indices gives a working $S$, i.e. there are
\[\frac{1}{p+q}\binom{p+q}{p}\]ideal subsets.

The answer is $\frac{1}{p+q}\binom{p+q}{p}$.

Assume $p < q$. We create a Young tableaux (in English notation) as follows: the top row consists of the numbers $\{ (p-1)q, (p-2)q, \dots, q, 0 \}$ in that order and a column starting with $kq$ has has all the positive numbers of the form $\{kq-p, kq-2p, \dots\}$. An example with $(p,q) = (4,7)$ is shown below. \[ 	\begin{bmatrix} 		21 & 14 & 7 & 0 \\ 		17 & 10 & 3 \\ 		13 & 6 & \\ 		9 & 2 \\ 		5 \\ 		1 	\end{bmatrix} \] The main idea is that an ideal set of $S$ corresponds exactly to a subset of this Young tableau which is closed upwards and to the left, and contains the top row. In fact readers familiar with the Frobenius coin problem (or the chicken mc-nugget variation) will notice that the $\tfrac12(p-1)(q-1)$ entries not in the top row correspond to exactly the elements not obtained by coins of weights $p$ and $q$.

To count this, we give another bijection: it's equivalent to the number of up-right paths from $A = (0,0)$ to $B = (p,q)$ that stay above the diagonal line. Indeed, we can situate the Young tableu with the upper-right $0$ positioned at $B$; then given a path from $A$ to $B$ we take all the elements of the tableaux on or above this path.

[asy] 	draw( (0,0)--(4,7) ); 	dot("$0$", (4,7), dir(45), blue+4); 	dot("$7$", (3,7), dir(135), blue); 	dot("$3$", (3,6), dir(135), blue); 	dot("$14$", (2,7), dir(135), blue); 	dot("$10$", (2,6), dir(135), blue); 	dot("$6$", (2,5), dir(135), blue); 	dot("$2$", (2,4), dir(135), blue); 	dot("$21$", (1,7), dir(135), blue); 	dot("$17$", (1,6), dir(135), blue); 	dot("$13$", (1,5), dir(135), blue); 	dot("$9$", (1,4), dir(135), blue); 	dot("$5$", (1,3), dir(135), blue); 	dot("$1$", (1,2), dir(135), blue); 	dot("$A$", origin, dir(225), red+4); 	for (int i=1; i<=7; ++i) dot( (0,i), grey+1.5); 	for (int i=0; i<=1; ++i) dot( (1,i), grey+1.5); 	for (int i=0; i<=3; ++i) dot( (2,i), grey+1.5); 	for (int i=0; i<=5; ++i) dot( (3,i), grey+1.5); 	for (int i=0; i<=6; ++i) dot( (4,i), grey+1.5); [/asy]

Then it's a classical problem that the number of such paths is $\frac{1}{p+q} \binom{p+q}{p}$. (The proof is by the ``cyclic shift method'': show that given a sequence of $p$ right moves and $q$ left moves, exactly one cyclic shift of this sequence gives a valid path.)

We claim that the number of ideal sets is $\frac{1}{p+q}\binom{p+q}{p}$.

To see this, label the lattice points $(x,y)$ that satisfy $0\le x\le p$ and $y\ge 0$ with the number $py-qx$. The first claim is that every nonnegative integer label is achieved at some point. Since $p$ and $q$ are relatively prime, for every $n$, there are some integers $x'$ and $y'$ such that $py'-qx'=n$. Note that $(x'+kp,y'+kq)$, so we have some solution $(x,y) $ with $0\le x\le p$. Then, $y=\frac{n+qx}{p}\ge 0$, as desired.

For any ideal set $S$, let $A$ be the lattice points that have label in $S$. It is easy to see that if $(x,y)\in A$, then $(x-a,y+b)\in S$ for all nonnegative integers $a$ and $b$. Since $0\in S$, we have that $(0,0),(p,q)\in A$. Thus, any $(x,y)$ with $y\ge q$ is automatically in $A$. Therefore, we may restrict our attention to the region $0\le x\le p$ and $0\le y\le q$, such that $py-qx\ge 0$. In particular, it suffices to determine what subset of these lattice points may be in $A$.

As we noted, if $(x,y)\in A$, then $(x-1,y+1)\in A$ as well (as long as $(x-1,y+1)$ has a label). Thus, the points of $A$ in this region are exactly points above some path that only goes up and to the right from $(0,0)$ to $(p,q)$, staying above the line $py-qx=0$. Conversley, note that any $A$ that is of this forms leads to an ideal $S$. Thus, the number of ideal sets is simply the number of lattice paths from $(0,0)$ to $(p,q)$ that are always in the region $py-qx\ge 0$.

The path is made up of $p+q$ steps, which we denote as $w_1,\ldots,w_{p+q}\in\{p,-q\}$. Here, $w_i=p$ corresponds to going up one unit, and $w_i=-q$ corresponds to going right one unit. We wish to count the number of such sequences that satisfy $w_1+\cdots+w_{p+q}=0$ and
\[\sigma_{n}:=w_1+\cdots+w_n\ge 0\]
for all $n\in[0,p+q-1]$. For any sequence, not necessarily satisfying $\sigma_{n}\ge 0$, we claim that exactly one cyclic shift of it works.

Let $m$ be the index such that $\sigma_{m}$ is minimal. Clearly, if $\sigma_{m}<0$, then the sequence is invalid, so if the sequence is valid, then $\sigma_{m}=0$. But if $m\ne 0$, then we have $py-qx=0$ for $0\le x\le p$ and $0\le y\le q$ with $(x,y)\ne(0,0),(p,q)$, which can't happen since $p$ and $q$ are relatively prime. Thus, if the sequence is valid, then the we have the minimum at the start.

Conversely, consider the sequence $(w_{m+1},\ldots,w_{p+q},w_1,\ldots,w_m)$. Here, all the partial sums are nonnegative since they are of the form $\sigma_n-\sigma_m$ for some $n$. Thus, this is the one and only cyclic shift of any given sequence that is valid.

Thus, for all $\binom{p+q}{p}$ paths from $(0,0)$ to $(p,q)$, exactly one from the $p+q$ cyclically equivalent paths stays above $py-qx=0$, so there are a total of $\boxed{\frac{1}{p+q}\binom{p+q}{p}}$ such paths.

I claim that the answer is $\frac{1}{p+q}\binom{p+q}{q}$.

Note that, by the Frobenius Coin Problem, all numbers larger than $mn-m-n$ are in an ideal set $S$. Call a number $i$, a [b]generator[/b], if $i\in S$, $i-jp-kq\not\in S\forall (j,k)\in(\mathbb{Z}_{\ge_0}^2\setminus(0,0))$. Then, $0$ is always a generator, and we have that $S$ is uniquely determined by its set of generators.

We will now construct a bijection between the number of ideal sets and the number of gridwalks from $(0,0)$ to $(p,q)$ which do not pass $qx-py=0$. Suppose we number every lattice point such that $(x,y)$ is given the number $qx-py$. Obviously, the set of points enclosed by $\{qx-py>0, y>0,x<p\}$ all contain distinct labels, and I claim that these labels are precisely the numbers which cannot be expressed as $ip+jq$ for $i,j\in\mathbb{Z}_{\ge 0}$. If we assumed the contrary, then $ip+jq=xq-yp\implies (i+y)p=(x-j)q$, so $x-j$ is a positive multiple of $p$, which is absurd since $x<p$.

Thus, the set of possible generators is entirely enclosed within this triangle. To choose a suitable set of generators, no generator can be $ip+jq$ more than another one, for $i,j\in\mathbb{Z}_{\ge 0}$, and in the coordinate plane, this corresponds to two points such that the line connecting them has negative slope. So, to choose a valid set of generators, we pick $(x_1,y_1),\ldots,(x_k,y_k)$ such that $\{x_i\}$ and $\{y_i\}$ are both increasing. Now, if we interpret these points as "peaks" of a path from $(0,0)$ to $(p,q)$ (i.e. points $(x,y)$ such that $y$ is strictly larger than the height of all other points on the path with $x$ coordinate $\le x$), we can easily see that any choice of generators does indeed correspond with a path of the aforementioned form, and vice versa. So, we have a bijection.

To count such paths, consider a sequence of moves, consisting of $p$ "rights" and $q$ "ups," say $P=m_1m_2\ldots m_{p+q}$. If $P$ is a valid path, and we consider a cycle shift of it: $m_im_{i+1}\ldots m_{p+q}m_1\ldots m_{i-1}$, note that the ratio of ups to rights in $m_1\ldots m_{i-1}$ is strictly less than $\frac{q}{p}$, so this ratio is greater than $\frac{q}{p}$ in $m_i\ldots m_{p+q}$. Thus, this path crosses $y=\frac{q}{p}x$ at some point in the first $p+q+1-i$ positions. On the other hand, if we are given an arbitrary path $P$, we can construct a valid cyclic permutation of it by considering the following algorithm: Consider the first move, $m_i$ for which $P$ crosses the line. Then, take the cyclic permutation $m_{i+1}\ldots m_i$, and repeat. After each iteration, the number of contiguous moves starting from the end which do not cross the line is strictly increasing, so this process eventually terminates, yielding a good path. Combining these two results, we see that each permutation of $p$ "rights" and $q$ "ups" has exactly one good cyclic permutation. $\gcd(p,q)=1$, so no permutations yield cyclic symmetry. Thus, the number of paths, and hence ideal sets is just $\frac{1}{p+q}\binom{p+q}{q}$, as desired.

The answer is $\frac{1}{p+q}\binom{p+q}{p}$
Let $A=\{ap+bq|a,b\geq 0\}$. The condition is equvialent to that if $n\in S$ then $n+A\subset S$. By Frobenius Coin problem, for every $a\geq (p-1)(q-1)$ we have $a\in A$. Therefore we may only count the number of subset of $S=\{0,1,2,...,pq-p-q\}$ which satisfies the condition. Let $B=S\setminus A$, and let $C=A\cap S$
[color=#00f]CLAIM. [/color]$f(b)=pq-p-q-b$ is a bijection from $B$ to $C$
[color=#00f]Proof. [/color]
Firstly, we show that $|B|=|C|=\frac{(p-1)(q-1)}{2}$. Indeed, $C$ are the unions of the sets
$$C_i=\{jp+iq|\quad 0\leq j<\frac{pq-p-q-iq}{p}\}$$
where $0\leq i\leq p-2$. Now notice that
$$|C_i|=1+\left\lfloor\frac{pq-p-q-iq}{p} \right\rfloor=\left\lfloor \frac{(p-1-i)q}{p} \right\rfloor$$
hence
$$|C|=\left\lfloor \frac{q}{p}\right\rfloor+\left\lfloor \frac{2q}{p} \right\rfloor+...+\left\lfloor \frac{(p-1)q}{p} \right\rfloor$$
since $(p,q)=1$ we have that $q,2q,...,(p-1)q$ are congruent to $1,2,...,p-1$ mod $p$ in some order. Therefore,
$$|C|=\frac{1}{p}(q(1+2+...+(p-1))-(1+2+...+(p-1)))=\frac{(p-1)(q-1)}{2}$$
as desired. Now notice that if $a+b=pq-p-q$, then $a$ and $b$ can't both belong to $C$, otherwise we will have $pq-p-q\in C$ since $C$ is closed under addition. Therefore the claim follows from pigeonhole principle. $\blacksquare$
Now obviously each ideal subset must contain $C$, therefore we shall only count the number of possible subsets of $B$ which can be the union of an ideal subset and $B$, now under the bijection described in the CLAIM, the image of such subsets are subsets of $C$ such that if n belongs to it, then both $n-p$ and $n-q$ belong to it. Consider such a subset $Q$. Let $c_i$ be the largest number such that $(c_i-1)p+iq\in Q$(define $c_i=0$ if no such number exists, then the only constraints on these numbers are
$$c_0\leq c_1\leq c_2\leq ...\leq c_{p-2}$$
and $$c_i+1\leq \left\lfloor \frac{(i+1)q}{p} \right\rfloor$$
Now this numbers corresponds bijectively to a path from $(0,0)$ to $(q,p)$ which never passes through the line $px=qy$ and only uses up and right move. The following is a famous result but we are still gonna prove it.
[color=#00f]CLAIM.[/color] The number of such paths is exactly $\frac{1}{p+q}\binom{p+q}{p}$
[color=#00f]Proof.[/color] If we are allow to pass through the line then there will be $\binom{p+q}{q}$ paths, we divide these paths into equivalence classes, by defining two paths to be related if one of them can be shifted to another cyclically. Then each equivalence classes has $p+q$ elements, we claim that each equivalence classes have exactly one element which does not pass through the diagonal.
We can consider the one-dimensional problem by representing a up and down move by a move with displacement $\frac{q}{p+q}$ and $-\frac{p}{p+q}$ respectively. Let the equivalence class contains cyclic permutation of the numbers $a_1,a_2,...,a_{p+q}$. Notice that the path never cross the diagonal if and only if $a_1+a_2+...+a_k>0$ for each $1\leq k\leq p+q-1$. Now we have $a_1+a_2+...+a_{p+q}=0$. Using exactly same reasoning as I used [url=https://artofproblemsolving.com/community/c6h1671289p10632346]here[/url], we can show that there are at least one such path, now if there are two such paths, WLOG assume
$$a_1,a_2,...,a_{p+q}$$ and
$$a_{i+1},a_{i+2},...,i_{i+p+q}$$
are two such paths, then $a_1+a_2+...+a_i>0$ and $a_{i+1}+...+a_{p+q}>0$, so $a_1+a_2+...+a_{p+q}>0$, contradiction.

The answer is $\tfrac{1}{p+q}\tbinom{p+q}{p}$. Consider the up-right lattice paths from $(0, 0)$ to $(p, q)$ above the line $y=\tfrac{q}{p}x$ where all points on the path have nonnegative $x$ and $y$-coordinates less than $p$ and $q$, respectively; we claim that there is a bijection with these paths and the ideal subsets of $\mathbb{Z}_{\ge 0}$. We construct the bijection as follows: [list]
[*] Label each lattice point $(x, y)$ above $y=\tfrac{q}{p}x$ with nonnegative $x$ and $y$-coordinates bounded by $p$ and $q$, respectively with $qx-py$. Note that all of the labels that are not the origin are positive, and the origin has label $0$, and are precisely the set nonnegative integers that cannot be expressed as $ip+jq$ for nonnegative $i$ and $j$.
[*] Each path corresponds to a subset of $\mathbb{Z}_{\ge 0}$ by considering the labels on the path. This set corresponds to a unique ideal set by taking the complement with universal set $\mathbb{Z}_{\ge 0}$.
[*] Now given an ideal set $S$, take its complement $S'$, and assign each element of $S'$ to a unique ordered pair of nonnegative integers $(x, y)$ with $x < p$ and $y < q$ such that it is $qx-py$. One can easily see that the lattice points associated with each ordered pair can form a lattice path due to the restriction on $S$, completing the bijection.
[/list]

Now to enumerate these paths, we prove the following generalization due to Bizley and Grossman (independently). We follow Bizley's approach.

[color=#f00][b]Lemma:[/b][/color] [Bizley, 1954] Denote by $f(bn, an)$ the number of up-right paths from $(0, 0)$ to $(bn, an)$ weakly below $y=\frac{a}{b}x$. Then \[ f(bn, an) = \langle t^n \rangle \exp \sum_{j=1}^{\infty} \frac{1}{j(a+b)} \binom{(a+b)j}{aj} t^j. \]
[I]Proof.[/I] In our proof, we let $f_j(bn, an)$ be the number of up-right paths from $(0, 0)$ to $(bn, an)$ weakly below $y=\frac{a}{b}x$ with $j$ [i]contacts[/i] (not including the origin). We call such a path a [i]{$\tfrac{a}{b}$-path[/i]. A [i]highest point[/i] of a path is a point on the path that follows and precedes different steps. Additionally, we say that a [i]cyclic shift[/i] of a path can be obtained by removing the section of the path from $(0, 0)$ to some $(r, s)$ on the path, and moving that section to the other end so that $(0, 0)$ is moved to $(bn, an)$. The key idea is that the highest points on the path are not affected by cyclic shifts, and there are exactly $j$ cyclic shifts that transform a $\tfrac{a}{b}$-path with $j$ highest points to a $\tfrac{a}{b}$-path with $j$ contacts, vice versa. Thus the number of paths with $t$ highest points is \begin{align*} \frac{1}{j}n(a+b)f_j(bn, an). \end{align*} For notational purposes, define \[ F_n(a, b) := \frac{1}{n(a+b)} \binom{(a+b)n}{an}. \] We sum equation (1) over $1 \le j \le k$ to obtain \begin{align*} F_n(a, b) = \sum_{j=1}^n \frac{1}{j} f_j(bn, an). \end{align*} Let $g_j(bn, an)$ be the number of paths from $(0, 0)$ to $(bn, an)$ with $j$ highest points. Then, \begin{align*} f_j(bn, an) = \sum g_{a_1}(bn, an) \cdot \ldots \cdot g_{a_j}(bn, an), \end{align*} where the sum is taken over all $j$-tuples $(a_1, \ldots, a_j)$ of nonnegative integers with sum $n$. Equation (3) rewrites as \begin{align*} f_j(bn, an) = \langle t^n \rangle [P(t)]^j, \end{align*} where \[ P(t) := \sum_{i=1}^{\infty} g_i(bn, an) t^n. \] Hence, \begin{align*} F_n(a, b) = \langle t^n \rangle \sum_{i=1}^n \frac{1}{i} [P(t)]^i = \langle t^n \rangle \sum_{i=1}^{\infty} \frac{1}{i} [P(t)]^i = - \langle t^n \rangle \log(1-P(t)). \end{align*}
Isolating $P(t)$, we obtain \[ P(t) = 1- e^{-F_1t-F_2t^2-\ldots}. \] Now $f_j(bn, an)=\langle t^j \rangle (1- e^{-F_1t-F_2t^2-\ldots})^j$, so \[ f(bn, an) = \sum_{j=1}^n \langle t^n \rangle (1- e^{-F_1t-F_2t^2-\ldots})^j= \langle t^n \rangle e^{F_1t+F_2t^2+\ldots}, \] which proves the desired result.
:yoda:

Thus, taking $n=1$ in the lemma, we do some basic differentiation to find that the number of paths we want to count is indeed $\tfrac{1}{p+q}\tbinom{p+q}{p}$, and we conclude.

Fun ENUMERATIVE COMBINATORICS problem. The lattice point labeling is motivated by the fact that p and q can be thought of as weights for x and y coordinates, and by experience it's actually pretty common for these types of problems that have ``two degrees of freedom'' to have a bijection with a 2D graph (i can think of 2 bijection examples off the top of my head but don't quite know the contest names, one was a jmo problem the other an isl as well).
$\newline$

The answer is $\boxed{\frac{1}{p+q}\binom{p+q}{p}}$. $\textit{Label}$ the lattice points $(x,y)$ that satisfy $0\le x\le p$ and $y\ge 0$ with the number $py-qx$. Note that
[list]
    [*] Every nonnegative integer label is achieved at some point; this follows by $py-qx=n$ and $(x,y)\to(x+kp,y+kq)$, so there's $x\in[0,p],y\ge0$ by shifting.
    [*] Let $S_{p,q}$ be the lattice points that have label in $S$. It suffices to determine the number of subsets of the lattice points in $x\in[0,p],y\in[0,q]:py-qx\ge 0$ since \[0\in S\implies(0,0),(p,q)\in S_{p,q}\text{ and }(x,y)\in S_{p,q}\implies(x-a,y+b)\in S\forall a,b\in\mathbb N_0.\]
    [*] We'll (biject again!) take the obvious interpretation $w_1,\ldots,w_{p+q}\in\{p,-q\}$, where $w_i=p$ corresponds to y increases by 1 and $w_i=-q$ corresponds to x increases by 1. We'll count the number of such sequences that satisfy $w_1+...+w_{p+q}=0$ and $\sigma_{n}:=w_1+...+w_n\ge 0\forall n\in[0,p+q-1]$. (Assume henceforth though that we [b][i]don't take for granted that [/i][/b]$\sigma_n\ge0$.)
[/list]
Now take $m:\sigma_{m}=\min_{i\in[1,p+q-1]}\sigma_i$ (and take $m\ne0,p+q$ if there is another value). Note that since $\gcd(p,q)=1,\sigma_{m}\ne0$, m=0 is the only value in order to stay not below the line. Consider the sequence $(w_{m+1},...,w_{p+q},w_1,...,w_m)$. All the partial sums
\[ s_i=
\begin{cases}
\sum_{i=1}^{p+q-m}w_{m+i}+\sum_{i=1}^{m+i+1\mod{p+q}}w_{i}=\sigma_{p+q}-\sigma_m+\sigma_{m+i+1\mod{p+q}}\ge0 & \text{if } m+i+1>p+q \\ w_{m+1}+...+w_{m+i+1}=\sigma_{m+i+1}-\sigma_m\ge0 & \text{if } m+i+1\le p+q.
\end{cases} \]
This sequence is valid, and any cyclic shift by assumption that $\sigma_m$ is minimal means in \[(w_{m+i},...,w_{p+q},w_1,...,w_m,w_{m+1},...,w_{m+i-1}),\text{ we have }w_{m+1}+...+w_{m+i-1}>0\]\[\implies\sum_{j=i}^{p+q-m}w_{m+j}+\sum_{i=1}^{m}w_{i}=\sum_{i=1}^{p+q}w_i-(w_{m+1}+...+w_{m+i-1})<0,\] contradiction (this partial sum is negative). Hence exactly one in every p+q cyclic shifts of sequences are valid (i.e. stay above the y=qx/p line), so there are $\boxed{\frac{1}{p+q}\binom{p+q}{p}}$ ways, as claimed.


prove that:

$\displaystyle\sum_{j=k}^n \binom{j}{k} = \binom{n+1}{k+1}$ for $n\ge k$

[hide]Use induction: C(n+1, k+1) = C(n, k) + C(n, k-1)[/hide]

It's like Pascal's Triangle or block walking or whatever you call it.

I think it is block-walking... it comes up on the AoPS 2.

Oh come on, I didn't want an induction solution  :D .

Try to prove it by showing that the two sides count the same number of things.

Consider the set A={1, 2,..., n+1}. The number of k+1-subsets of A is just (n+1)C(k+1). Now classify the subsets by their maximal element. Clearly, there are (i-1)Ck subsets with maximal element i, i=k+1, 2,..., n+1. Summing over i yields the result.