induction
strong induction
number theory unsolved
number theory

A mathematical frog jumps along the number line. The frog starts at $1$, and jumps according to the following rule: if the frog is at integer $n$, then it can jump either to $n+1$ or to $n + 2^{m_n+1}$ where $2^{m_n}$ is the largest power of $2$ that is a factor of $n.$ Show that if $k \geq 2$ is a positive integer and $i$ is a nonnegative integer, then the minimum number of jumps needed to reach $2^ik$ is greater than the minimum number of jumps needed to reach $2^i.$

assume that $i_{0}$ is the minimum number such that $f(2^{i_{0}}k)\leqq(2^{i_{0}})$(*) for some k,where f(t) is the minimum jump that the frog need to reach t.Call $k_{0}$ the smallest such number.Consider the path that the frog jump from $1$ to $2^{i_{0}}k_{0}$.The length of each jump is a power of $2$.Because of (*) the path does not contain $2^{i_{0}}$;therefore assume that the frog jump from a  when it pass through $2^{i_{0}}$;assume $a=2^{t}(2m-1)$ then the frog will find himself at $2^{t}(2m+1)$->$2^{t}(2k-1)\leq\ 2^{i_{0}}\leq\ 2^{t}(2t+1)\to t=2^{i_{0}-m-1}$->$a=2^{i_{0)}}-2^{m}$
By the minimal of $i_{0}$ and $k_{0}$ we see that we can go from $1$ to $2^{m}$ by less jump than from $1$ to $2^{m}+2^{i_{0}}$;and we can find a bijection from the path from $2^{m}+2{i_{0}}$ to $2^{i_{0}}k_{0}$ to the path from $2^{m}$ to $2^{i_{0}}(k_{0}-1)$.Then we can go from $1$ to $2^{i_{0}}$ by less than $f(2^{i_{0}}k_{0})$ jump.Contradiction

OK. Base step is obvious for i=0 this thing is obvious. Now assume that the result holds for all i from 0 to k inclusive. Let's prove it'll hold for i = k + 1. look at the 2 paths of the frog to 2^(k+1) and p * 2^(k+1). In the 2nd path, let the largest number the frog jumps to be x, so x < 2 ^(k+1). then x + 2^(m index x + 1) > = 2 ^ (k+1). Then the number of steps needed to get to 2 ^ (k+1) from x is < (a idex (2 ^  m index x + 1) + 1), a index n is the min number of steps needed to get from 1 to n. The min number of steps needed to get from (x + 2^(m index x + 1)) to 2 ^ (k+1) * p is greater than or equal to (a idex (2 ^  m index x + 1) + 1), and the result follows.

[quote="Rust"] Then (it is easy to show)$N(n)=[log_2 n]+s(n)-1$.[/quote]  Please explain :)  :)

Turn round process from n to 1 is $n_0=n$ if $2|n_i, n_{i+1}=\frac n2$ else $n_{i+1}=n_i-1$. Number of steps is N(n).

[quote="shunka"][quote="Rust"]Let N(n) is minimal needed jumps to get n, s(n) -sum of 2-adic digits of n. Then (it is easy to show)
$N(n)=[log_2 n]+s(n)-1$.[/quote]

The formula is not correct. For example, for 2^n the formula claims that N(2^n) = n, which is not correct. For example, N(8)=4.[/quote]
N(8)=3 ($8=2^3$). However I solve for jump n+h, $h=1,2,...,2^{m_n}$. In my case N(3)=2. For this case ($h\le 2^{m_n+1}$) had not effictive formul for N(n).

[quote="shunka"][quote="Rust"]
N(8)=3 ($8=2^3$). However I solve for jump n+h, $h=1,2,...,2^{m_n}$. In my case N(3)=2. For this case ($h\le 2^{m_n+1}$) had not effictive formul for N(n).[/quote]

Now I understand even less.

By definition, N(n) is the minimal number of steps needed to reach n. For n=8, the minimal number of steps is 4. One can go 1 -> 2 -> 6 -> 7 -> 8 or 1 -> 3 ->5 ->7 -> 8. In both cases 4 steps are used, and there is no shorter sequence of steps reaching 8. Thus, I think, N(8)=4.

The proposed formula gives N(8) = [log_2(8)] + s(8) -1 = 3 + 1 -1 = 3. Thus the formula gives N(8)=3, which means that something is wrong.

The reply now claims that N(3)=2. I think that N(3)=1, since 1-> 3 produces 3 in one step.

What does the phrase "I solve for jump n+h" mean?[/quote]

I think he means he misread the problem. He may have read $2^{m_n}$ instead of $2^{m_n+1}$?

[quote="paladin8"]
I think he means he misread the problem. He may have read $2^{m_n}$ instead of $2^{m_n+1}$?[/quote]

Yes, this explanation makes sense. Thanks.

In fact, now I think that he understood that he could jump by any power of 2 smaller or equal to 2^{m_n}. That would explain the phrase "I solve for jump n+h, for h =1,2,...".

My solution was to prove that the maximum that the frog can move in $i-1$ moves was to $2^i-1$ by induction, and it looked really "elegant".  Something was obviously wrong though , due to the dismal score I got.  :oops:  :oops:

But when i = 3, i-1 = 2. In two steps one cannot reach 7 = 2^3-1.

Thus in general, one cannot even reach 2^i-1 in i-1 steps.

It seems that this does not help to find out if we can reach 2^i before we can reach k2^i. All we know that in i-1 steps we are far from both.

hey,
'rem' i dont quite understand your solution. could you perhaps clarify it using better notation? what do these 'indexes' mean?
its trivial to reduce it to proving 2^(n+1) takes more jumps than 2^n from which the result follows, since to reach (2k+1) * 2 ^ t you need to jump from (2k-1) * 2^t; so it reduces to the aforementioned problem. another interesting thing i noticed is when you try to work backwards, like from 2^(n+1) go to the next step to all possible values from which 2^(n+1) can be reached, and to continue the process, you get a string of numbers of the form {2^(n+1) - t}. Evidently the numbers {t} are the same numbers generated when you work forwards .. though using this observation doesn't help since it reduces the problem to the problem itself.  :?
so as far as im concerned the problem hasn't been solved yet on mathlinks.  :(

[quote="epitomy01"] ... since to reach (2k+1) * 2 ^ t you need to jump from (2k-1) * 2^t [/quote]

hmmm....?

If I did everything right, I think the sequence of steps

1 -> 3 -> 4 -> 12 -> 20 -> 28 -> 29 -> 30

is the unique sequence of 7 jumps that reaches 30 and there is no shorter sequence of steps that reaches 30. This tells me two things

1) You do not have to come to (2j+1)2^i from (2j-1)2^i (we come to 30 from 29)

2) You do not have to step on 2^i on your  path to (2j+1)2^i (we do not step on 2 on the way to 30)

My solution consists of proving first $S(2^n) < S(2^{n+1}) \le 2S(2^n)$...from there proceed by contradiction.  I believe I might have used induction too.

I just read the official solution

http://www.unl.edu/amc/e-exams/e8-usamo/e8-1-usamoarchive/2006-ua/2006usamoS.pdf

and I think it's really strange.

Why do they prove $M<i_{0}$ in the third paragraph, since it isn't used later anywhere... can anyone clarify?

It seems that in the 4th paragraph of the official solution one uses (at least implicitly) that m<i_0.

The fact that m<i_0 follows from the fact that m is at most M and that M<i_0 (the latter is proved in the third paragraph).

Here's a kind of long-winded solution. I'm not [i]entirely[/i] sure it works, but I believe it does. Lack of diagrams probably makes this extremely hard to follow...

Define an inverse frog as follows: an inverse frog can jump from $ a$ to $ b$ if and only if a frog can jump from $ b$ to $ a$ (with $ b<a$, of course). So this happens if and only if $ a\minus{}b\equal{}1$ or $ b\equal{}a\minus{}2^{m_{b}\plus{}1}$. Since $ 2^{m_{b}}\parallel{}b$,  let $ b\equal{}2^{m_{b}}B$ where $ B$ is odd. Then we get that  $ a\equal{}2^{m_{b}}(B\plus{}2)$, so $ m_{a}\equal{}m_{b}$. However, note that if $ a$ is a power of 2, we get $ B\equal{}\minus{}1$, and since only care about the positive number line (once we get to a negative number, we can never get back to 1), an inverse frog on a power of 2 can only jump to $ a\minus{}1$. Now, we see that an inverse frog on the integer $ a$ jumps according to one of:
(i) $ a\minus{}1$;
(ii) $ a\minus{}2^{m_{a}\plus{}1}$, given that $ a$ is not a power of 2.

Let $ f(n)$ be the minimum number of jumps required for a frog to jump from $ 1$ to $ n$, or equivalently the minimum number of jumps required for an inverse frog to jump from $ n$ to $ 1$. We need to show that $ f(2^{i})<f(k\cdot2^{i})$ for $ k\ge2$. First, we induct strongly on $ i$ to show that it is true for $ k\equal{}2$ and all odd $ k\ge3$. Then, we show that it is true for all even $ k\ge4$.

First, for the $ k\equal{}2$ case. We are showing that $ f(2^{i})<f(2^{i\plus{}1})$. Consider two inverse frogs, $ A$, and $ B$, with $ A$ starting on $ 2^{i\plus{}1}$ and $ B$ on $ 2^{i}$. Let $ a_{j}$ and $ b_{j}$ be their respective positions after $ j$ jumps. Note that $ a_{1}\equal{}2^{i\plus{}1}\minus{}1$ and $ b_{1}\equal{}2^{i}\minus{}1$. We construct a tree diagram for the possible values of $ a_{j}$, given the two choices the inverse frog has at each point. This gives us a binary tree, starting from $ j\equal{}1$, for each $ A$ and $ B$. Now, if we come to a point in either binary tree where the inverse frog only has one choice (basically, it gets to a power of 2 bigger than 1), on one branch write number-1, and on the other branch we have a blank. Then we can continue our tree off of our blanks, with more blanks. Note that any sequence of $ a_{j}$'s is strictly decreasing, and made up of integers, so in $ B$'s tree we eventually get to a 1 (and we know we won't end up with just a bunch of blanks because we can always just keep subtracting 1). Note that $ f(2^{i})$ is the minimal $ z$ such that there is a path with $ b_{z}\equal{}1$. We claim that if we match up the trees from $ j\equal{}0$ to $ j\equal{}z$, corresponding entries in the binary trees either contain a blank or differ by $ 2^{i}$. We do this by induction on $ j$. It's true for $ j\equal{}0$ and $ j\equal{}1$. Basically, if we have two non-blanks in corresponding positions on the two different trees, assume these differ by $ 2^{i}$. Thus, they are congruent modulo $ 2^{i}$, so unless $ 2^{i}$ divides both of them, the biggest power of 2 dividing them is the same. But obviously it's not possible for $ 2^{i}$ to divide anything in the $ 2^{i}$ tree because $ b_{1}\equal{}2^{i}\minus{}1$. Thus, the length of the inverse frog's two possible jumps is the same for both non-blank entries.

Now, we claim that there can't be we can't have $ a_{j}\equal{}1$ with $ j\le z\equal{}f(2^{i})$. Assume we do. Then, the corresponding position in $ B$'s tree must be blank, as it cannot be $ 1\minus{}2^{i}\le0$. We can trace this blank back to some power of 2, $ 2^{a}$, with $ a<i$, in $ B$'s tree. The analog on $ A$'s tree is not blank, since we can trace $ a_{j}\equal{}1$ back to it, so it is $ 2^{a}\plus{}2^{i}\equal{}2^{a}(1\plus{}2^{i\minus{}a})$, which is an odd multiple of $ 2^{a}$. But by the original inductive hypothesis, we take $ k\equal{}1\plus{}2^{i\minus{}a}$, which is again odd, because $ i>a$, and $ f(2^{a})<f^(2^{a}(1\plus{}2^{1\minus{}a}))$. Thus, we must have had a 1 in $ B$'s tree earlier than the 1 in $ A$'s tree, contradiction, since we took $ z$ to be the earliest 1 in $ B$'s tree. This proves the $ k\equal{}2$ case.

Now consider $ k\ge3$ odd. Let $ k\equal{}2k'\plus{}1$ where $ k'$ is a natural number; we induct on $ k'$. First, $ k'\equal{}1$, so we're proving that $ f(3\cdot2^{i})>f(2^{i})$. From $ 3\cdot2^{i}$, an inverse frog can jump to either $ 3\cdot2^{i}\minus{}1$ or $ 2^{i}$. However, if it jumps to $ 2^{i}$, it needs at least $ 1\plus{}f(2^{i})$ jumps to get to 1. So we only consider the former case. Also, note that the $ 2^{i}$ inverse frog has to jump to $ 2^{i}\minus{}1$. We now use exactly the same argument from the $ k\equal{}2$ case. For the inductive step, note that from $ (2k'\plus{}1)\cdot2^{i}$ we can go to $ (2k'\plus{}1)\cdot2^{i}\minus{}1$ or $ (2(k'\minus{}1)\plus{}1)\cdot2^{i}$. For the former, apply the same argument as the $ k\equal{}2$ case again, and for the latter, by induction hypothesis, we need $ 1\plus{}f((2(k'\minus{}1)\plus{}1)\cdot2^{i})>1\plus{}f(2^{i})$ steps to reach 1. This proves the $ k$ odd case.

It is left to prove the claim for all even $ k\ge4$. Let $ k\equal{}2^{m_{k}}\cdot K$, so $ K$ is odd. We wish to show that $ f(2^{i})<f(2^{m_{k}}
\cdot K\cdot2^{i})$. But note that $ f(2^{m_{k}}\cdot K\cdot2^{i})\equal{}f(K\cdot2^{m_{k}\plus{}i})>f(K\cdot 2^{m_{k}\plus{}i\minus{}1})>\cdots>f(K\cdot 2^{i})\ge f(2^{i})$, where we repeatedly use the $ k\equal{}2$ case, then finally the odd $ k$ case, since $ K$ is odd. This, finally, completes the proof.

My intuition is completely terrible, so here's an unfortunate solution that can probably be cleaned up significantly (it's probably basically equivalent to everyone else's solutions anyway).

Let $f(n)$ denote the least number of moves needed to get to $n$. Then the moving condition states that if $n=2^rs>1$ where $s$ is odd ($f(1)=0$), then
\[f(n)=f(2^rs)=1+\min(f(2^rs-1),f(2^rs-2^{r+1})),\]where if $s=1$ we simply ignore the second term and have $f(2^r)=1+f(2^r-1)$. (We will repeatedly use these two fundamental relations, of course.)

----------------------------------
We prove by strong induction on $i,j,k$ in that order that for all integers $i\ge0$, $j\ge1$, and $1\le k\le2^{i+1}-1$, $f(2^{i+1}j+k)>f(k)$. (1) For $i=0$, this is trivial for all $j,k$ since $f(1)=0$, establishing our base case. Now assume that $i\ge1$.

For $1\le k\le2^i-1$, the claim is clearly true for all $j$ since by (1), $f(2^{i+1}j+k)=f(2^i(2j)+k)>f(k)$. (2)

Now consider $k=2^i$ and $j\ge1$. For $j=1$, using (2) and the fact that $f(2^i)=1+f(2^i-1)$,
\begin{align*}
f(2^{i+1}+2^i)
&=1+\min(f(2^{i+1}+2^i-1),f(2^{i+1}+2^i-2^{i+1}))\\
&=1+\min(f(2^{i+1}+2^i-1),f(2^i))\\
&\ge1+\min(1+f(2^i-1),f(2^i))\\
&=1+f(2^i)>f(2^i).
\end{align*}For $j\ge2$, then,
\begin{align*}
f(2^{i+1}j+2^i)
&=1+\min(f(2^{i+1}j+2^i-1),f(2^{i+1}j+2^i-2^{i+1}))\\
&=1+\min(f(2^{i+1}j+2^i-1),f(2^{i+1}(j-1)+2^i))\\
&\ge2+\min(f(2^i-1),f(2^i))\\
&=2+f(2^i-1)>f(2^i).
\end{align*}So we've proven (1) for $k=2^i$ and $j\ge1$. (3)

Now we look at $2^i+1\le k\le 2^{i+1}-1$, inducting strongly on $k$. For the base case $k=2^i+1$, we have by (2) and (3) that (let $2^e$ be the largest power of two dividing $k$, so that $e\le i-1$ and thus $k>2^i\ge2^{e+1}$)
\begin{align*}
f(2^{i+1}j+k)
&=1+\min(f(2^{i+1}j+k-1),f(2^{i+1}j+k-2^{e+1}))\\
&\ge2+\min(f(k-1),f(k-2^{e+1}))\\
&=1+f(k)>f(k).
\end{align*}The exact same argument applies when $k\ge2^i+2$. This completes the induction.$\blacksquare$
----------------------------------

With (1), we now find
\begin{align*}
f(2^{r+1})=1+f(2^{r+1}-1)=1+f(2^r+2^r-1) & \ge2+f(2^r-1)\\
&=1+f(2^r)>f(2^r)
\end{align*}and for odd $2t+1\ge3$,
\[f(2^r(2t+1))=f(2^{r+1}t+2^r)>f(2^r).\]These two inequalities trivially imply the problem statement.

[b]Edit:[/b] copied from a PM to KingSmasher3, since it has some stuff that might help others.
[hide]since $v_2(2^i - r) = v_2(k 2^i - r)$ for $0<r<2^i$, it's more natural to try to prove the [i]reverse[/i]-sequence for $2^ik$ will also work for $2^i$ (if we stop/take out terms at the right places).

So take the minimal sequence $a_0,a_1,\ldots,a_x$ for $2^i k$ as you wrote, and let $b_u = 2^i k - a_{x-u}$. Then from $v_2(2^i - r) = v_2(k 2^i - r)$ for $0<r<2^i$, we see that as long as $2^i - b_l > 0$, the reverse-sequence $2^i - b_0, 2^i-b_1, \ldots, 2^i - b_l$ must be valid (more precisely, because $k2^i - b_u \to k2^i - b_{u-1}$ is a valid operation for $1\le u\le l$, so is $2^i - b_u \to 2^i - b_{u-1}$). If we take $l$ maximal, then similar to how you showed $a_j = 2^i - 2^{y-1}$, we can show that one of the following three cases must hold: (1) $2^i - b_l = 1$, in which case we're done; (2) $2^i - b_l>1$ but is not a power of $2$, which contradicts the maximality of $l$; or (3) $2^i - b_l>1$ is a power of $2$, in which case we can induct. (Since you also asked for some style feedback, it might be good to include a line about how by the minimality of $x$, the length of the minimal sequence from $1$ to $k2^i$ must equal the length of the minimal sequence from $1$ to $k2^i - b_l$ plus the length of the minimal sequence from $k2^i - b_l$ to $k2^i$---this is trivial but still worth mentioning.)
[/hide]

Let $a_0, a_1, a_2, ... , a_x$ be the minimal sequence of jumps for the frog to reach $2^ik$ with $a_0=1$ and $a_x=2^ik.$ Let $a_y$ be the smallest term greater than $2^ik-2^i.$ We define the sequence $b_0, b_1, b_2, ... , b_{x-y}$ such that $b_j=a_{j+y}-2^ik+2^i$ for $0 \le j \le x-y.$ Since $v_2(2^ik-r)=v_2(2^k-r)$ for all $r<2^k,$ $b$ is still a valid sequence. Now we have three cases:

(1) If $b_0=1,$ then we are done, since we have a sequence, namely $b,$ that gets to $2^k$ in a shorter number of steps.

(2) If $b_0>1$ is not a power of $2,$ this contradicts the fact that $a_y$ is minimal: Let $b_0=c2^d$ where $c\ge 3$ is odd and $d \ge 0.$ Then, $a_y=c2^d+2^ik-2^i$ has $2^d$ as its largest power-of-2 factor. This means that $a_{y-1}$ is either $a_y-1$ or $a_y-2^{d+1},$ both of which are greater than $2^ik-2^i.$

(3) If $b_0>1$ is a power of $2,$ it suffices to show that it takes less moves to get to $b_0$ than $a_y.$ Note that this is because $a_0, a_1, a_2, ... , a_y$ is also the shortest path to $a_y.$ We apply strong induction. Clearly, if $i=0,$ then it takes less steps to get to $2^i$ than $2^ik.$ Since $a_y=b_0k',$ we are done by the inductive hypothesis.

Edit: Revised solution. Thanks to math154 for help!

@ KingSmasher3:
No, because you cannot assume that the minimal paths for both $2^{i}*k$ and $2^{i}$ have the same beginning sequence from $a_{0}$ to $a_{j}$.

Edit: Sorry, I misinterpreted that as comparing the minimal paths, instead of building a path.

[quote="zero.destroyer"]@ KingSmasher3:
No, because you cannot assume that the minimal paths for both $2^{i}*k$ and $2^{i}$ have the same beginning sequence from $a_{0}$ to $a_{j}$.[/quote]

zero.destroyer- Thanks for reply. However, this concept shouldn't be a problem right? It does not matter if the minimal maths for both $2^ik$ and $2^i$ both start with $a_0, ... , a_j$ (since they probably don't). We just have to show that there exists a path to $2^i$ that is shorter than $a,$ the minimal path to $2^ik.$ It does not have to be the minimal path to $2^i.$

Here's a pretty short solution:

Define $m_{\ell}$ to be the minimum number of steps required to jump from $1$ to $2^\ell$.
We pretty much now induct on this statement: If $v_2(a) = p$, the it takes at least $1+m_{p}$ steps for $a$ to jump to a multiple of $2^{p+1}$. So now take the minimal sequence to $k \cdot 2^i$. If this sequence passes through $2^i$, we're of course done. Otherwise it skips over $2^i$. This can only happen if the jump was $2^i-2^j \rightarrow 2^i+2^j$ for some $j$.
But by the above statement, since jumping $2^i-2^j$ to $2^i$ takes $1+m_j$ moves (this is clearly achievable) while jumping $2^i+2^j$ to $k \cdot 2^i$ takes at least $1+m_j$ moves, we are done.

We will prove the result with strong induction on $i$. For the base case of $i=0$, it takes the frog 0 hops to jump to 1 and a positive number of hops to jump to any integer greater than 1, so the conclusion follows.

For the inductive step, suppose that the result holds for all $i<m$. We will consider what the frog does in reverse, as in its hops from $n$ to 1. Clearly, the hops backwards are $n\rightarrow n-1$ or $n\rightarrow n-2^{m_n+1}$, with the extra constraint that we have to stay positive. Suppose for the sake of contradiction that the frog needs more hops to get from $2^i$ to 1 than $2^ik$ to 1 and furthermore suppose that the frog does not do $2^ik\rightarrow 2^ik-2^{m_{2^ik}+1}$ as its first move. Then, it must go $2^ik\rightarrow 2^ik-1$. Now, from here, have the $2^i$ to 1 frog copy all the moves of the $2^ik$ to 1 frog unless it makes a move that makes it go nonpositive. At this point, the $2^ik$ frog must be at a point of the form $2^i(k-1)+2^a$ for some nonnegative integer $a$. But now, the $2^i$ to 1 frog can just repeat the moves from $2^a$ to 1 and by strong induction it takes less moves than going from $2^i(k-1)+2^a$, a contradiction. If the $2^ik$ to 1 frog makes the second kind of move on its first move, then it must move to some number of the form $2^ik'<2^ik$, and we can finish this case with an induction.

Sketch:
Consider the following restatement of the problem: Show that the minimum number of moves to transform the binary number $0...001$ into the number $2^i=1000000..0$ , is less than the amount of moves to transform the original sequence into the number $k2^i=blah0000000..0$, if we are allowed the following moves:
a) Add one to the digit one to the left of  the rightmost 1, and perform a carry if neccessary
b) Add a one to the ones place, and perform a carry if neccessary

Now we have that in order to reach the $1000...00000$, the second to last move will be from the number $1111...111$. Similarly, in order to get $k2^i=blah0000..000$, we need to pass through some number of the form $something1111...111$. Now take the strategy that gives the minimum number of moves for $k2^i$, and apply it to get $2^i$, ignoring every move that affects a digit larger than $2^i$. Clearly, this will transform $1$ into $2^i$, and additionally it must take less moves, or else would have that the algorithm to generate $k2^i$ would only involve moves regarding digits less than $2^i$, and thus would force $k=1$, so we are done.

@above, but you forgot the case when the move affects both the digits larger than $2^i$ and the digits lower than $2^i$ that are made through carries.

Sketch:
Consider a path from $1$ to $k*2^i$, suppose this is the smallest path from $1$ to a number of the form $k*2^i$. Thus, when we take this path mod $2^i$ there must be no repeats. We want to prove that this path is from $1$ to $2^i$. If there are 2 adjacent terms in this path a and b s.t. there is a multiple of $2^i$ in between them, it is easy to see that $a==-2^x$ and $b==2^x$ for some x>1.(Modulo $2^i$ of course) Since x<i we can prove that the smallest path from b to 0 is greater that or equal to the smallest path from a to 0.

The write-up is tricky, so the following might be a nonsense.

We slightly alter the problem by letting the frog jumps from $n$ to $n-1$ or $n-2^{\nu_2(n)+1}$ instead, and the goal is to go from $n$ to $1$. This is equivalent to the problem by reversing the sequence of jumps. We also use induction on $i$; the base case $i=0$ and $i=1$ are easy to check.

Assume that $a_1, a_2, \hdots, a_m$ is a sequence of jumps from $2^i\cdot k$ to $1$, and let $b_j=a_j-2^i(k-1)$. We analyze the behavior of $b_j$.

[b]Case 1:[/b] $a_{j+1}=a_j-1$
[list]
[*]If $b_j=1$, then we do nothing.
[*]If $b_j>1$, then clearly $b_{j+1}=b_j-1$ so the jump from $b_j\to b_{j+1}$ is valid.
[/list]
[b]Case 2:[/b] $a_{j+1}=a_j - 2^{\nu_2(a_j)+1}$
[list]
[*]If $\nu_2(a_j)\geq i-1$, then $2^{i-1}\mid b_j$. Thus, either $b_j\leq 0$ or $b_j$ is a power of two.
[*]Otherwise, $\nu_2(a_j) < i-1$, thus $\nu_2(b_j) = \nu_2(a_j)$. Now we split into two more subcases.
[list]
[*]If $b_j > 2^{\nu_2(b_j)+1}$, then $b_{j+1} = b_j-2^{\nu_2(b_j)+1}$. The jump from $b_j\to b_{j+1}$ is valid.
[*]Otherwise, we must have that $b_j$ is a power of two. In this case, we use the induction hypothesis instead.
[/list]
[/list]
Summing up the above case split, we get that the sequence $b_1,b_2,\hdots$ is a valid jump until the sequence hit upon a power of two; we must hit since the last term is clearly negative. Let $b_s=2^t$ for some integers $s,t$ which $s$ is minimal.
[list]
[*]If $t=0$, then $b_1,b_2,\hdots,b_s$ is a valid sequence of jumps from $2^i$ to $1$. Moreover, $a_s>1$; thus, $m>s\geq f(2^i)$.
[*]If $t>0$, then we use the induction hypothesis as follows: the number of jumps to get from $a_s$ to $1$ is greater than the number of jumps to get from $b_s=2^t$ to $1$. Since $b_1,b_2,\hdots,b_s$ is a valid sequence of jumps, we get that
$$m > s+f(2^t) \geq f(2^i)$$
as desired.
[/list]

    Finally.. Finally finished!

    We'll proceed by induction on i, with i=0 trivial; henceforth assume the inductive hypotheses. We'll look at the frog in reverse moves, that is, the moves $n\to n-1$ or $n\to n-2^{m_n+1}$ (this holds since if this move were to occur, indeed the end move has same $\nu_2$ as the before end move), where we end at 1. Call the $2^ik\to1,2^i\to1$ frogs frog 1 and 2, respectively.

    Case 1: Frog 2 does $2^ik\to 2^ik-1$. Then, have frog 1 copy all the same length of jumps of frog 2, unless it goes past 1. Then, frog 1 is at a point of the form $2^i(k-1)+2^j:0\le j<i$. Now, frog 1 can make the same length as the moves of the frog going from $2^j$ until it gets to 1, which takes less moves than going from $2^i(k-1)+2^a$ by inductive hypothesis, as needed.

    Case 2: Frog 2 starts off as $2^ik\to 2^ik-2^{m_{2^ik}+1}$. Then, it goes to a point of the form $2^ij<2^ik$, so if frog 1 copies the move, it reduces directly into inductive hypothesis where frog 1 takes less moves, as needed.

We reverse all of the steps and interpret the frog starting from some number and jumping $n \to n-1$ or $n \to n-2^{\nu_2(n)+1}$ on each turn, with the goal of ending up at $1$. This is clearly equivalent and will make things clearer.

We now use strong induction on $i$. First, for $i=0$ the statement is clearly true for all $k$; henceforth suppose $i \geq 1$. Starting from $2^ik$, if the frog ends up at $2^i\ell$ for any $\ell<k$ at any point we are done by downwards induction $k$ (the base case is $k=1$; we don't need a strict inequality). Thus the frog must end up at $2^i(k-1)+2^m$ for some $m<i$ and jump to $2^i(k-1)-2^m$. By inductive hypothesis, reaching $1$ from $2^i(k-1)-2^m$ takes at least as many moves as reaching $1$ from $2^m$. Thus it takes less moves to go from $2^i(k-1)+2^m$ to $2^i(k-1)+1$ than to go from $2^i(k-1)+2^m$ to $1$, so it takes less moves to go from $2^ik$ to $2^i(k-1)+1$ than to go from $2^ik$ to $1$. There's an obvious bijection between a series of moves from $2^ik$ to $2^i(k-1)+1$ (since we never jump more than $2^{i-1}$ in this case) and a series of moves from $2^i$ to $1$, so it takes less moves to go from $2^i$ to $1$ than to go from $2^ik$ to $1$. $\blacksquare$


Yanıtın iyisi kötüsü olmaz dersen ben şöyle bi yanıt vereyim:
Şimdi acilen çıkmam lazım, akşam dönünce bi bakayım :)

[quote="ihsan_einstein"]Amaç sonuca gitmekten ziyade tartışmak ve fikir üretmek olmalı...

Bu soruya da hiçbir yanıt alamadım...
................................................
Diyelim bir bilgisayar programi yapacaksiniz. Program oyun oynayacak. Oyun soyle: 1'den 10'a dek bir tamsayi sececeksiniz, bilgisayar da tuttugunuz sayinin, ornegin 5'ten buyuk olup olmadigini soracak; buyukse, 6 yada 7'ye esit olup olmadigini soracak.. Yani evet-hayir oyunu. En sonunda bilgisayar bulacak elbet tuttugunuz sayiyi. Sonra sira sizde. Bilgisayar bir sayi tutacak, siz bilmeye calisacaksiniz. En cabuk kim bilirse kazanacak. Nasil bir program yapmali ki, bilgisayarin kazanma sansini arttirmali? Elbet her sayinin tutulma olasiligi ayniysa, sayilari ortadan bolmeye calisirsiniz. Ama her sayinin tutulma olasiligi ayni degilse, yani bazi sayilarin tutulma olasiligi daha fazlaysa, algoritma'yi degistirmeniz gerekir. Ornegin, 3 sayisinin tutulma olasiligi %99 ise, bilgisayarin ilk sorusu "tuttugun sayi 3'mu?" olmali ki %99 olasilikla bir soruda bilebilsin. Örneğin, 81 kisilik siniftan, kucuk bir kagida 1'den 10'a dek bir sayi yazmalarini isteyelim. Sonuc soyle olmuş olsun: 1 sayisini 3 kisi tuttu 2 sayisini 5 kisi tuttu 3 sayisini 8 kisi tuttu 4 sayisini 6 kisi tuttu 5 sayisini 10 kisi tuttu 6 sayisini 10 kisi tuttu 7 sayisini 19 kisi tuttu 8 sayisini 7 kisi tuttu 9 sayisini 8 kisi tuttu 10 sayisini 5 kisi tuttu. Son sorum: oyle bir bilgisayar programi yapin ki, bilgisayar, yukaridaki olasiliklara uygun olarak tutulan bir sayiyi olabildigince cabuk bulabilsin. Yani eger program, i sayisini s_i soru sorarak buluyorsa, (3s_1 + 5s_2 + 8s_3 + .... + 5s_10)/81 sayisi minimal olsun. Huffman adli bir adamin gelistirdigi guzel bir algoritma varmış(?) Bu tur sorulari cozuyor(mus). Asagi yukari her dort kisiden biri 7 sayisini secti.  Turkiye'de ayni deneyi yapsak ne olur du?

ihsan (...)[/quote]
İstersen yapalım bir anket, sonuçlarını değerlendiririz. Gerçi 81 sayısını bulmak çok zor ama... 3-5 seneye buluruz herhalde :D (Bkz. En zor aralık anketi)


Let $a,b,c,d$ be nonnegative real numbers such that $a+b+c+d=4$. Then,

(a) $\sum ab(b+2c)\le 12$;

(b) $\sum ab(b+pc) \le 4(1+p)$ for $p \ge \frac{37}{27}$.

This is very nice, but not so hard I think. All can be solved by my "few-line" solutions (about 5-lines).  :lol:

try it with something like AM-GM but does nothing... may you give some tips?


I was wondering whether I can do any kind of research in Economics if I am taking only a introductory macroeconomics course and I had microeconomics before? What kind of economics literature can I read if any except the economist and the wall street journal?

Can anybody please start posting responses to what I wrote? Thanks

I don't know if this would help at all, but, noticing that you reside in PA, I might suggest that you attempt to contact Carnegie Mellon's department of Economics if you own school's is not sufficient for research oppurtunities.  I think they recently had a nobel prize winner in the subject and probably would be able to help you more than anybody in this forum.

The Journal of Economic Perspectives is worth a look

But this journal is pretty advanced though?


topology
advanced fields
advanced fields unsolved

Let $ \mu$ be a positive Borel measure supported in a compact set $ E\subset\mathbb{R}$, with $ \mu$ not identically $ 0$. Assume there exists $ a>0,C>0$, such that for all intervals $ I,\mu(I)\leq C |I|^{a}$.
Give an explicit loewr bound for the Hausdorff dimension of $ E$.


projective geometry
trigonometry
geometry solved
geometry

We are given an angle $\angle xOy$. Let $A,B$ be two points in its plane. $P$ is a variable point on $Ox$. Let $\{ M \} = AP \cap$ the bisector of the angle and $\{ N \} = BM \cap Oy$.

Does $PN$ pass through a fixed point all the time?

Yes, and the fixed point lies on the line AB. More generally:

[color=blue][b]Theorem.[/b] If x, y, z are three lines through a point O, and A and B are two points, and for every point P on the line x we construct the points $M=AP\cap y$ and $N=BM\cap z$, then, for varying point P on the line x, the line PN intersects the line AB at a fixed point.[/color]

[i]Proof.[/i] We have to prove that if $P_1$ and $P_2$ are two points on the line x, and we construct the points $M_1=AP_1\cap y$ and $N_1=BM_1\cap z$ for the point $P_1$ and the points $M_2=AP_2\cap y$ and $N_2=BM_2\cap z$ for the point $P_2$, then the lines $P_1N_1$ and $P_2N_2$ intersect the line AB at the same point. But this is obvious: Since the lines $P_1P_2$, $M_1M_2$, $N_1N_2$ are concurrent (at the point O), the triangles $P_1M_1N_1$ and $P_2M_2N_2$ are perspective, so that by the Desargues theorem, the points $P_1M_1\cap P_2M_2$, $M_1N_1\cap M_2N_2$ and $P_1N_1\cap P_2N_2$ are collinear. Since $P_1M_1\cap P_2M_2=A$ and $M_1N_1\cap M_2N_2=B$, this actually means that the points A, B and $P_1N_1\cap P_2N_2$ are collinear; in other words, the point $P_1N_1\cap P_2N_2$ lies on the line AB, i. e. the lines $P_1N_1$ and $P_2N_2$ intersect the line AB at the same point. This proves the Theorem.

  Darij

[hide="Here is (I hope) an agreeable surprise for you, Perfect_radio (without projective geometry)."]
[color=green][b]Lemma.[/b] Let $ABC$ be a triangle and let $P$ be a point which belongs to the side-line $BC$. Denote $m(\widehat {PAB})=x$ and $m(\widehat {PAC})=y$. Then there is the following relation: $\frac{PB}{PC}=\frac{OB}{OC}\cdot \frac{\sin x}{\sin y}\ .$[/color]

[color=darkred][b]Theorem.[/b] Given are  three fixed lines $x\ ,\ y\ ,\ z$ which pass through a fixed point $O$ and two fixed points $A\ ,\ B\ .$ For a mobile point $P\in x$ define the points $M=AP\cap y$ and $N=BM\cap z\ .$ Prove that the intersection $F\in PN\cap AB$ is a fixed point .[/color]

[color=darkblue][b]Proof.[/b] Denote $m(\widehat {AOx})=a\ ,$ $m(\widehat {BOz})=b\ ,$ $m(\widehat {xOy})=c\ ,$ $m(\widehat {yOz})=d$ (the values $a\ ,$ $b\ ,$ $c\ ,$ $d$ are constant). From the well-known above lemma we obtain the relations  $\frac{NM}{NB}=\frac{OM}{OB}\cdot \frac{\sin d}{\sin b}\ ,$ $\frac{PA}{PM}=\frac{OA}{OM}\cdot \frac{\sin a}{\sin c}$ and from the Menelaus' theorem applied to the transversal $\overline {NPF}$ for the triangle $AMB$, i.e. $\frac{NM}{NB}\cdot\frac{FB}{FA}\cdot \frac{PA}{PM}=1$ we find the following chain of relations:
$\frac{FA}{FB}=$ $\frac{NM}{NB}\cdot\frac{PA}{PM}=$ $\left(\frac{OM}{OB}\cdot \frac{\sin d}{\sin b}\right)\cdot\left(\frac{OA}{OM}\cdot \frac{\sin a}{\sin c}\right)=$ $\frac{OA}{OB}\cdot \frac{\sin a}{\sin b}\cdot \frac{\sin d}{\sin c}$ (constant), what means the point $F$ is fixed.[/color][/hide]
\[ \boxed {\mathrm {\ Come\ on\ \ STEAUA\ -\ Bucuresti\ !\ }}  \]\[ \mathrm {\ U.\ E.\ F.\ A.\ \ C\ U\ P\ (\ quarters\ )\ }  \]\[ \mathrm {\ RAPID\ Bucuresti\ -\ STEAUA\ Bucuresti\ }  \]\[ \blacksquare.\blacksquare.\blacksquare\ \ \ \ \bigstar.\bigstar.\bigstar  \]\[ \mathrm {\ The\ first\ round\ score\ : \ 1\ -\ 1\ }  \]

[quote="perfect_radio"]Meanwhile I had the idea of sending $O$ to infinity through a projection, then proving that theorem for $3$ parallel lines. It's valid, right?[/quote]

Of course, it's valid. It's also very easy if you send A and B to infinity.

  darij


ok, so I've wanted to learn LaTex (the right way on document and all) for quite some time. i can do it on AoPS but when i try to make a document it never works.
i downloaded the files and packages and everthing. when i read the instructions i think the step that I am unable to complete is to make it so that its a PDF file. like the directiosn say make sure it says "LaTex-PDF at the tab next to LateXcenter" this might seem stupid but i don't know how to change it to a PDF. i try to go save and then choose save as file type PDF, but it only offeres TTX or BBX or something like that.

any help would be appreciated!

Save the file as tex but you then tell latex you want that converted to PDF. To do that in texniccenter look for the dropdown box(see red ellipse in picture below) and choose LaTeX=>PDF then compile your document by pressing the Build current file button (green ellipse in picture).

i was just trying to do that but the thing is that dropdown box doesn't have any options to choose from. it's completely blank for me, and i try to scroll down but there are no options.

sorry if these questions are stupid. technology hates me. i would be better off sending you a letter. :D

You need to have a pdf reader (like Adobe's) installed on your computer. If you have, go to Build, Define Output Profiles, then press the Wizard button in the bottom left. This should set it up for you. You will need to tell it where to find latex.exe - somewhere like C:\Program Files\MiKTeX 2.6\miktex\bin but it maybe different on your computer.

is latex.exe supposed to be installed on my computer?
if so, im not really sure where to find it. i pressed on this tab that showed like  BOX.. but i wasn't sure where in my documents to find it.

[quote="mihail911"]is latex.exe supposed to be installed on my computer? [/quote]Yes, if you have installed MIKTeX. In My Computer look in C:\Program Files\MiKTeX 2.6\miktex\bin and it should be there. If it is that is where you must navigate to when you press the button in TexnicCenter.

thanks a lot stevem!!!
i got it to show >PDF!!
thanks so much!

You are putting it in the form of
$\dbinom{}{}$
and
$\dfrac{}{}$
right :?:

[quote="mihail911"]ok. i had one more question. i was trying out some of the basic LaTex things on the page:
i wrote the following thing:
Now you can do more than just $ x$. You can now write things like $ \displaystyle\binom{5}{3}!$

When I went to build it, it said 1 error and the document turned out with everything except it was like:
[b]Now you can do more than just $ x$. You can now write things like 53!.[/b]

the same thing happens when i do it with \dfrac ___
what is wrong?[/quote]
Did you have the amsmath and amssymb packages included?  They are practically necessary.  Many of the best and most commonly used commands and environments, including \dfrac, \binom, and \genfrac, and the enviornment align, are only included in these packages.  amsthm is another standard package to include, for theorem environments.

So put the following line in your preamble, if it isn't there :
[code]\usepackage{amsmath,amssymb}[/code]

Edit :  Fixed command name (thanks, stevem)

Thos commands require the amsmath package. Just add the line
\usepackage{amsmath}
in the preamble of your document (after \documentclass and before \begin{document}).

[quote="Boy Soprano II"]So put the following line in your preamble, if it isn't there :
[code]\includepackage{amsmath,amssymb}[/code][/quote]That should be
[code]\usepackage{amsmath,amssymb}[/code]

one more question: im working on my midterm right now for my class and i want to box my answers. like "so the answer is \box{5}.
how would i do that?


calculus
integration
calculus computations

$ \int \frac {1}{1\minus{}2008x\minus{}x^2}dx$

$ \alpha_{\pm}\equal{}\frac{2008 \pm \sqrt{2008^2\plus{}4}}{\minus{}2}\equal{}\minus{}1004 \pm \sqrt{1004^2\plus{}1}$

$ \frac {1}{1\minus{}2008x\minus{}x^2} \equal{} \frac {A}{x\minus{}\alpha_\plus{}}\plus{}\frac {B}{x\minus{}\alpha_\minus{}}$

then solve for A, B and integrate? messy maybe, but nothing too hard.


You have two block of clay in cube form and the edges are 10 cm. How many spheres with a radius of 5 cm can you make with that amount of clay?

[hide]You have $2000\text{ cm}^{3}$ of clay. Each sphere is $\frac{500\pi}{3}\text{ cm}^{3}.$

$\left\lfloor2000\div\frac{500\pi}{3}\right\rfloor=\boxed{3}$[/hide]


What chapters in Intro to Geometry should I go through for success in AMC 10?  I don't have time to go through the whole book.  (I don't think.)

You probably don't need some 3-D, and not Ch. 17. But I think you have enough time in 2 months if you work at it... that would be best

I just finished intro to geo and found almost all of the chapters useful. As long as you're pretty good with geometry already, you should be ok with skipping the first few chapters.

Also, to see how you should go, try review problems on some chapters

If you don't read the chapter, you can just read the Summary and it will probably give you the main ideas, without the practice.

Look through the summaries and challenge problems of different chapters and brush up on anything you think you need to work on. It really depends on what you need to learn.

Will do, thanks.  If I can solve the review problems but not all of the challenge problems, should I move on or not?

[quote="AdithyaGanesh"]I have 2 months left till AMC 10.  Should I work through Intro to Counting and Prob or Intro to Geo?[/quote]

There's not much C/P on AMC 10, so do some Intro to Geo and the harder parts of C/P


Real numbers $x,y,a$ satisfy
$x+y=x^{3}+y^{3}=x^{5}+y^{5}=a$.

Find all possible $a$

[hide]We have $x+y=(x+y)(x^{2}-xy+y^{2})=(x+y)(x^{4}-x^{3}y+x^{2}y^{2}-xy^{3}+y^{4})$.  One possibility is $a=x+y=0$.  If $x+y\ne 0$, then we have $1=x^{2}-xy+y^{2}=x^{4}-x^{3}y+x^{2}y^{2}-xy^{3}+y^{4}$.

Then $(x^{2}-xy+y^{2})^{2}=x^{4}-x^{3}y+x^{2}y^{2}-xy^{3}+y^{4}$.  Expanding and simplifying gives $x^{3}y-2x^{2}y^{2}+xy^{3}=0$.  Factoring out $xy$, we obtain $xy(x^{2}-2xy+y^{2})=0$.

If $x=0$, then $y=y^{3}=y^{5}$.  From the first equality we get $y(y-1)(y+1)=0$, so $y=-1,0,1$.  All of these satisfy the original equations, so $a=-1,0,1$ are all possibilities.  The case where $y=0$ is the same.

If $x,y\ne 0$, then $x^{2}-2xy+y^{2}=(x-y)^{2}=0$.  Therefore $x=y$.  We have $2y=2y^{3}=2y^{5}$.  Dividing by two gives the same equation we considered in the last paragraph, which has solutions $y=-1,0,1$.  Therefore, $a=2y=-2,0,2$ are all possibilities.

The answer is $a=-2,-1,0,1,2$.[/hide]

[hide]very nice, pretty standard but the main trick you use is this: \[1=x^{2}-xy+y^{2}=x^{4}-x^{3}y+x^{2}y^{2}-xy^{3}+y^{4}. \implies (x^{2}-xy+y^{2})^{2}=x^{4}-x^{3}y+x^{2}y^{2}-xy^{3}+y^{4}\] good job I'll look for alternate solutions[/hide][/hide]


This always baffles me when something like this appears in the Round Table (and it has many times I assure you).

You are human. Your body and brain behave differently at different points of your life. Sometimes you're happy. Sometimes you're sad. Sometimes you have lots of insights. Sometimes you don't. It is nothing to worry about. What actually is surprising is that people have such a long period of insight into problems, that it concerns them when they don't for a little bit.

I have a few suggestions. First, don't force yourself to do things you don't feel like doing. It could be a result of "burn-out" (especially considering the mental laziness comment). That is usually the case when it happens to me. Then I just don't do problems for a few days or week or so. I come back refreshed, and actually your brain formulates memory and connections when resting, so this often brings lots of insight I didn't have before.

The other more active thing to try is running (I've said this before), or any good cardio exercise. Studies show that your brain makes three times as many neurons when you exercise for twenty minutes a day. It also increases circulation and blood flow to the brain. Endorphines are released. I went running today, and it was the first time this week. I am without a doubt more motivated to do math than any other day. I feel wide awake and it shook the mental laziness I was in.

Hopefully this helps somewhat.

[b] @HilbertThm90 [/b]: Thank you!

[quote="HilbertThm90"]First, don't force yourself to do things you don't feel like doing.[/quote]
Actually, sometimes, certain situations arise where you ought to solve difficult math(or any other field) problems (even when you don't like) in order to constantly challenge your mental faculties. I am actually seeking a remedy in the situation where, even when I don't feel like solving problems, I need to solve them (That is even when I'm feeling mentally lazy).

@HilbertThm90, I can assure you that my 'problem' is not a result of 'burn-out' (at least in my case) but a result of some mental laziness which I seemed to develop rather recently.

Are there any other suggestions apart from doing exercise (like running as suggested by HilberThm90, which is a really good suggestion) that could relieve me from this sheer mental laziness?

Burnout might just mean you've been doing a lot of it and your brain wants to take a break. Happens to the best. That's why it's helpful to keep your mental activity balanced through hobbies or exercise or friends or whatever.

[quote="Gen8"]Hi all, I'm facing a problem, and I personally feel "The Round Table" is the most appropriate place to discuss about my problem in order to evoke some fruitful suggestions/advice.

On some occasions (these days it's becoming regular), Whenever I encounter a difficult math/computer science problem (not necessarily confined to Math/C.S. but, in general, while solving difficult problems, for example -- Intricate Brainteasers, Crypt arithmetic puzzles etc), instead of persevering I give up in the middle;I feel lazy to persevere (to actually find a solution to the problem) and also I can't conjure up of any way on how to solve/approach the problem. (I feel, this is mainly due to mental laziness rather than lack of requisite knowledge)

I feel if I could put more "mental effort" I could solve the problem, but these days, due to some reason I'm unable to put the required mental effort; This results in a lot of personal disappointment, because of my mental lethargy/laziness.

Also, I personally feel I'm having less "Eureka moments of joy" these days. (While solving intricate problems, it's highly discouraging not to have "eureka moments")

I want to ask-- Did any of you ever encounter a situation akin to mine, where you felt mentally "lazy/lethargic" when striving to solve a "difficult" problem?

Can anyone of you offer some suggestion/advice on how to get out of this "lazy mental state"? Is my "situation" common or uncommon?

[b]@all [/b]: Please don't misconstrue that I loathe problem solving; I really enjoy solving difficult problems, but not so much these days because of the above-mentioned problem of mine.

Thank you!

[b] P.S.: [/b] Sorry JBL, I couldn't concoct a much better title for my thread. :D If you manage to conjure up a much better title, please do re-edit the "title of the thread".[/quote]

I think a problem is that you have a low opinion about yourself, perhaps understandable since some teenagers behave like that
Some quotes: "my problem", "mental lethargy/laziness", "lazy mental state", "my "situation"", "problem of mine"
I suggest you not to individualize these difficulties to yourself and not use such negative attitude. Leave that to your detractors.

I feel the same way sometimes too. I normally just take a break from what I'm doing, relax for a little while, and then come back to it when I actually feel like doing it.

If you force yourself to do it, you're more likely to feel lazy.

 :lol:

[b]@bogdanno, @TZF, @digs[/b]: Thank you!

[quote="bogdanno"]I think a problem is that you have a low opinion about yourself, perhaps understandable since some teenagers behave like that [/quote]
Actually, I don't have such a low opinion on myself. I think you might have slightly misconstrued. Another fact: I'm not a teenager. :P (I'm only 20!)

[quote="bogdanno"] Some quotes: "my problem", "mental lethargy/laziness", "lazy mental state", "my "situation"", "problem of mine"
I suggest you not to individualize these difficulties to yourself and not use such negative attitude. Leave that to your detractors.
[/quote]
Sorry if I had greatly individualized it, but I personally felt that I'm the only one who is facing this particular problem (I know it's silly, and maybe incorrect too). I mean, all the "superstars" here on AoPS are almost always posting solutions/hints to problems that are difficult (Say -- problems in Topology, Combinatorics, Abstract Algebra,etc), who appear to be not devoid of enthusiasm at any time while I sometimes feel so unenthusiastic when striving to solve a tough CS problem/Math problem/Brain-Teaser.I want to be as enthusiastic in problem solving as some of those "superstars". I personally feel "mental laziness" is the primary contributor in my lack of enthusiasm in problem solving (or rather solving intricate problems).I'm really amazed on seeing some of the "superstars" here who never exhibit any sort of mental lethargy at any time.


how do i make it so latex stops numbering the pages?
thanks

the pg number is always at the bottom of the page, id like to get rid of it and also decrease the bottom margin. I am able to decrease the top margin, but it doesn't seem to decrease the bottom one symmetrically. How do i do that in addition to how do i get rid of the page numbering?

:) how do you get page numbering in the first place? Just a normal document (article/report) should not have page numbering by default :?

put this command in your file's header

\pagestyle{empty}

[i]Posted from a Sony Ericsson K700i [/i]


[VERSION 2.2]List of Underplayed Math Games Download Address
Updated July 2nd. 100% legal.

First of all, what games are overplayed?
Sudoku, Bejewelled, Minesweeper, Backgammon, you name it, and you got bored of it.
The following games provide great alternative math experience. They not only look good, but also require you to THINK A LOT. If you want to give your brain a thorough rest, don't play any of these.
Some of these download websites will redirect you so I can't provide a specific link to that game. You can easily find them using their search function.

Dragon Booster: Race...Battle...Win
note: it can only be played online. It takes a long time to learn this game, but I PROMISE at last it's gonna amaze you.
http://www.cbc.ca/dragonbooster/game/

Legend of Aladdin
note: It's NOT a Bejewelled clone. It's much better, requiring more brain power.
http://get.games.yahoo.com/proddesc?gamekey=legendofaladdin

SquareOff
http://www.shockwave.com/gamelanding/squareoff.jsp

Passage 3
http://www.download.com/Passage-3/3000-2111_4-9618010.html?tag=lst-0-1

Quadrow
http://www.shockwave.com/gamelanding/quadrow.jsp

Quarto
Gearz
Mozaki Block
Cubis Gold/Cubis 2
http://www.zone.com/
or play them via MSN Messenger

Puzzle Oldies Games
http://freeoldies.com/fo_search.php?type=guide&rub=reflexion&lang=us

"Puzzle", "Traditional" DOS games
http://www.dosgamesarchive.com/list/cat/8
http://www.dosgamesarchive.com/list/cat/13

Chinese Checkers
http://www.dosgamesarchive.com/download/game/228

Cubis is not underplayed :o
You can play Cubis and Mozaki block in MSN.

[quote="math92"]some of them don't work on my computer. :([/quote]

DOS games don't. Unless they do. I mean certain DOS games work on certain non-Dos systems and you just need to try them out.

I updated it to v2.2. lol.


Let G be a tree, and the average of the degrees of its vertices is 1:5. How
many vertices are in G?

Use the identities $ \sum_{v\in V(G)}d(v)\equal{}2e(G)$ and $ e(G)\equal{}|V|\minus{}1$.

Thank you!  Appreciate it.  I knew there were identities, but I couldn't find them in my notes.


Find all positive integer triples $ (x,y,z)$ that satisfies $ x^4\plus{}y^4\equal{}z^4$.

There is no solutions for z^n=x^n+y^n, where n>2

Yes this is Fermat's Last theorem.Is there any shorter proof than A.Wiles proof ? I mean,I know what Fermat wrote in his book's margin ,but does anyone found the elementary proof ?

[quote="t0rajir0u"]The following two facts were known to Fermat, both of which are usually proved by infinite descent, and both of which imply the $ n \equal{} 4$ case of the last theorem.

[b]Theorem:[/b]  There are no solutions to $ x^2 \plus{} y^4 \equal{} z^4$ in positive integers.

[b]Theorem:[/b]  There are no solutions to $ x^4 \plus{} y^4 \equal{} z^2$ in positive integers.[/quote]

I believe the intended purpose of this topic is to perform this proof *without* invoking FLT. This proof of a specific case is much, much shorter than Dr. Wiles' proof. Please don't invoke FLT for this problem any more :).

This is very well-known. You can see it in a lot of equation books. If you can not, may be this is helpful:
[url]http://math.uga.edu/~pete/4400flt4.pdf[/url]
[hide="PS"] You must have adobe reader of foxit reader[/hide]

[quote="solafidefarms"]Please don't invoke FLT for this problem any more :).[/quote]
I didn't invoke FLT.  Fermat had a [b]correct[/b] proof of this case, and it is quite elementary.

[quote="SUPERMAN2"]May be one day one of you find a elementary proof for Fermat's Last Theorem which is only have one line!:blush:  :blush:[/quote]

And then, God came down to Fermat in a dream and preached the wisdom that is Fermat's Last Theorem.

BigGsus:"Look, if you have this for n>2, then there are no integer solutions. Say something like you had a proof of it but it didn't fit in a margin."
Fermagnetism:"Wait, wait, wait... are you [i]sure[/i] there aren't any solution?"
BigGsus:"Trust me. This will bother mathematicians for centuries."
Fermagnetism:"Wait... why did you choose me though? Why not Pascal or Diophantus?"
BigGsus:"I threw dice."

[quote="v235711"]I don´t know why you guys are talking about Fermat´s last theorem.Although it is clear that it instantly solves the problem, it´s proof is incredibly harder than this ridiculous problem.It´s no use applying something extremely hard in such an easy problem!I mean, can you prove FLT in less then 5 minutes?This problem that i posted shouldn´t require much more time than this.[/quote]There's no need to get so defensive. Yes, many replies mention about FLT. Have you overlooked t0r's post? A proof of Fermat's infinite descent method can be easily found anywhere on the internet or some typical old elementary number theory textbook...


just a suggestion because currently accounts can be created with entirely bogus email addresses...

possible preemptive measure against spam :)

Trouble with this is that so many spam blockers block too many emails, then people can't join at all.  Also, probably 10% of people enter their emails wrong.  If we start having trouble with board spam, we'll re-implement this, but until that happens, we won't.


quadratics
number theory
relatively prime
algebra
quadratic formula

What is the smallest integer $n$, greater than one, for which the root-mean-square of the first $n$ positive integers is an integer?  Note: The root-mean square of $n$ numbers $a_{1}, a_{2}, \ldots, a_{n}$ is defined to be \[\sqrt{\frac{a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}}{n}}.\] [hide="Stuck here"]We know that $1^{2}+2^{2}+\cdots+n^{2}=\frac{n(n+1)(2n+1)}{6},$ so we're looking for the smallest $n$ s.t. $\frac{(n+1)(2n+1)}{6}$ is an integer.

For the square root of a number to be integer, the number itself must be integer. (A logical assumption :D) Therefore, $n$ is odd. (If $n$ was even, $2n+1$ and $n+1$ are both odd and can't be divided by $6$.)

I can't find a good way to find $n$ after this. I hope this problem isn't trivial...  :blush: [/hide]

4everwise, why can't $n$ be even? Let $n=6k+2$. Then, 6 divides $n(n+1)$. So you should not rule out all even numbers but only some.

10000th, you missed the fact that he has to divide by n.

You might see if using the fact that n+1 and 2n+1 are relatively prime can help and considering the possible factorizations.  I don't know if this works, but it might.

Oh ok   :oops:

Hmm... I'll try to consider those when either $n+1$ or $2n+1$ are multiples of 6.

I have bounced this off a few people, one gave me the answer $\boxed{337}$ he claimed it was right, but didn't have the time to tell me how or why.

A few other people have told me that this is just a very hard question. I got as far as 4everwise, but I dunno ither what to do next

337 is indeed the right answer. I remember doing this problem a while ago...It's not terribly bad, just a bunch of NT. I might post a solution later.

I don't understand the fifth line. Why does $n=\frac{-3+d}{4}$?

[quote="236factorial"]I don't understand the fifth line. Why does $n=\frac{-3+m}{4}$?[/quote]

Apply the quadratic formula for finding $n$,that's what he's done.

I believe this problem (or a variation but really the same thing) is in the AMC forum under the thread AMC daily problem started by Silverfalcon.  I did a lot of analysis and eliminate the case greatly, and there's another solution with pell's equation and stuff like that...

edit: oh, the pell's equation one is up there...
anyways, here the link to the brute force soln.:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=97509[/url]


From each vertex of triangle $ABC$ we draw 3 arbitary parrallell lines, and from each vertex we draw a perpendicular to these lines. There are 3 rectangles that one of their diagnals is triangle's side. We draw their other diagnals and call them $\ell_1$, $\ell_2$ and $\ell_3$.

a) Prove that $\ell_1$, $\ell_2$ and $\ell_3$ are concurrent at a point $P$.

b) Find the locus of $P$ as we move the 3 arbitary lines.

As for the source of the problem:

[quote="[url=http://groups.yahoo.com/group/Hyacinthos/message/70?expand=1]Hyacinthos message #70[/url]"][b]From:[/b] Antreas P. Hatzipolakis
[b]Date:[/b] Tue Jan 4, 2000 7:39pm
[b]Subject:[/b] 9PC as locus (was: Griffiths Locus)

[code]Bernard Gibert wrote:

>2). this particular one is described and noted (Ko) in "Le cercle d'Euler"
>by Collet & Griso.

Dear Bernard

I have a question about a locus which probably is included in the book
above, a book which I heve not seen:

Who is the author of this problem ?

Through the vertices of a triangle ABC we draw three parallels, and three
other paerpendicular to previous ones. So there are formed three rectangles
ADBE, BSCZ, and CKAH, which have as their diagonals the sides AB, BC,
CA, of the triangle. Find the locus of the intersection point of the three
other diagonals ED, SZ, KH.
(word-by-word translation from Panakis (*))

                      E            A         K

                      B            D         S

                      Z            H         C

The locus is the Euler Circle (as we [=Greeks, following you French (**)],
call the nine-point-circle or Feuerbach circle).

The triangle ABC is inscribed in the rectangle EKCZ.
It would be interesting the particular case that the rectangle is a square.

Asterisks:
(*) Panakis = I. Panakis: 2500 Problems of Geometric Loci With Their
Solutions [in Greek]. Athens, ca 1965, p. 654, #582.
The book has a general bibliography but not references for each one problem.

(**): Cf Victor Thebault:
A triangle ABC is inscribed in a circle (O) with a fixed diameter D,
and a transversal D', which turns about a fixed point, cuts BC, CA, AB
in A1, B1, C1. Let A2 and A3, B2 and B3, C2 and C3 be the orthogonal
projections of A and A1, B and B1, C and C1 on D.
(a) Show that the circles with centers at the the midpoints of AA1, BB1,
CC1 and passing through A2 and A3, and B2 and and B3, C2 and C3 meet
in a fixed point on the Euler circle, that is, the nine-point circle of
                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
the triangle.
(b) Find the locus of the second point of interesection of the three
circles.
(The American Mathematical Monthly 45(1938) 554 by V. Thebault)

Antreas[/code][/quote]

easy problem but nice
I just give a hint:
Use ceva  sinus theorem in median triangle of $ABC$.   let the intersection point of diagonals be $P$ with angle chasing show vertix of median triangle and $P$ are on a circle

Is there a solution that will handle so many different configurations?


ratio
geometric series
geometric sequence
arithmetic sequence

$ 13)$ Find the sum of 3/2 + 5/4 + 7/8 + 9/16 ......

Okay, so I know the formula for the sum of an infinite series is the first term over 1 - the common ratio.

I guess this is an infinite sequence 3+5+7... over another one ( 2 + 4+ 8 +16? I'm not sure what my thought process should be.

$ 29)$Find the sum 13/2 + 7/2 + 49/26+ ....

I'm not sure what the sequence in 29 is.
[hide="13"]
Denote $ S$ as the sum of the sequence. Then:
$ \begin{eqnarray*}
S&=& \dfrac 32+\dfrac 54 + \dfrac 78 + \dfrac 9{16} ...\\
\dfrac S2 &=&\qquad \dfrac 34 + \dfrac 58 + \dfrac 7{16} ...\\
\dfrac S2 &=&\qquad \dfrac 24 + \dfrac 28 + \dfrac 2{16} ...\\
\dfrac S2 &=& \dfrac {\dfrac 24}{1-\dfrac 12}...\\
\dfrac S2 &=& 1\\
S &=& 2$
[/hide]

How does the equation suddenly have a 2/4 + 2/8 etc.. when it was just 3/4 and 5/8 the equation above it??

For 13, that is.

Brut3Forc3's thought process is hard to follow without words.  Look at both sides of his equations carefully.

The first line is the given summation.  The second line is the given summation divided by two, with the terms moved to the right so that denominators are lined up.  The third line is the [i]first line minus the second line[/i] (this is the most important step).

[quote="Casa De Mathematica"]Okay, so I know the formula for the sum of an infinite series is the first term over 1 - the common ratio.[/quote]

But do you know [i]why[/i] that formula works?  The proof is by a similar argument.  Suppose we wanted to find the sum of an infinite geometric series

$ S \equal{} a \plus{} ar \plus{} ar^2 \plus{} ar^3 \plus{} ... \plus{} ar^n \plus{} ...$

where $ a$ is the first term and $ r$ is the common ratio.  We are calling our sum $ S$.  Multiplying by $ r$,

$ rS \equal{} ar \plus{} ar^2 \plus{} ar^3 \plus{} ar^4 \plus{} ... \plus{} ar^n \plus{} ...$

which is just $ S$ with the first term deleted!  Hence we conclude that

$ S \minus{} rS \equal{} a \Leftrightarrow$
$ S \equal{} \boxed{ \frac{a}{1 \minus{} r} }$

as desired.

[quote="Casa De Mathematica"]

$ 29)$Find the sum 13/2 + 7/2 + 49/26+ ....[/quote]

Are you sure there's no more information to go on? It looks like the series could continue onto anything.

Big hint for 29:

[hide]The common ratio= 7/13.[/hide]

[quote="madness"]This is also called an Arithmetico Geometric Progression where the numerators are in Arithmetic Progression and the denominators are in geometric progression.

Let Sn be the sum of the first n terms of the series.
Let d be the common difference and r be the common ratio .
Sn = $ a \plus{} (a \plus{} d).r \plus{} (a \plus{} d).(r^2) \plus{} ............... \plus{} (a \plus{} (n \minus{} 1).d).(r^(n \minus{} 1))$
$ r.Sn \equal{} 0 \plus{} a.r \plus{} (a \plus{} d).(r^2) \plus{} ............ \plus{} (a \plus{} (n \minus{} 1).d).(r^n)$
$ Sn.(1 \minus{} r) \equal{} a \plus{} d.(r \plus{} r^2 \plus{} ............ \plus{} r^(n \minus{} 1)) \minus{} (a \plus{} (n \minus{} 1).d).(r^n)$
Therefore Sn = $ a/(1 \minus{} r) \plus{} d.r.(1 \minus{} r^(n \minus{} 1))/(1 \minus{} r) \minus{} (a \plus{} (n \minus{} 1).d).r^n/(1 \minus{} r) .$
Sum to infinity can be shortened as
Sn = $ a/(1 \minus{} r) \plus{} d.r/((1 \minus{} r)^2)$ (Why?)
 :)

Edit : I'm not able to give r power n-1 using dollar signs . How do I do it ???[/quote]
Try r^{n-1}.  :lol:
Oh, and you can use \cdot for multiplication...


Determine a function $ f$ satisfying the functional relation $ f(x) \plus{} f\left(\frac{1}{1 \minus{} x}\right) \equal{} \frac{2(1 \minus{} 2x)}{x(1 \minus{} x)}$

Replace x with $ \frac{1}{1\minus{}x}$
$ f\left(\frac{1}{1\minus{}x}\right)\plus{}f\left(\frac{x\minus{}1}{x}\right)\equal{}\frac{2(1\minus{}x^2)}{x}$

Now replace again x with $ \frac{1}{1\minus{}x}\Rightarrow f\left(\frac{x\minus{}1}{x}\right)\plus{}f(x)\equal{}\frac{2x(x\minus{}2)}{1\minus{}x}$

Now solve the system.


Hi, today I was reviewing some college algebra, and I came to this problem with a statement I'm not sure about.

Okay, all the problem says to do is graph the equation (not function) x = y^2 which is easy.  But, then the book says this, "If we restrict y so that y >= 0, the equation x = y^2, y>= 0, may be written equivalently as y = sqrt x."

I understand that if we want y = sqrt x to be a function then we have to restrict y >= 0. But this is talking just about equations, so if all we want is an equivalent equation, why do we [i]have[/i] to restrict y?? Can someone help me? Is the book's statement wrong????

Remember that by definition, square root signs assume the POSITIVE resultant value, thus, the negative values for $ y$ don't apply, and we have to restrict $ y$ to be either $ 0$ or positive.


calculus
derivative
integration
calculus computations

[size=150][b]let the derivative of f(x)= [f(x)]^2
        f(0)= -0.5
find f(x) using mean value theorem[/b][/size]

[hide="Solution"]$ \int\frac{dy}{y^2}\equal{}\int dx$

$ \minus{}\frac{1}{y}\equal{}x\plus{}C$

Put $ x\equal{}0$ to get:

$ C\equal{}\frac{1}{0.5}\equal{}2$

So $ \boxed{y\equal{}\minus{}\frac{1}{x\plus{}2}}$[/hide]

thankyou.we want the solution by mean value theorem


Find all primary numbers p and q , for which

                           [(5^p - 2^p)(5^q - 2^q)]: pq

is an integer .

Γειά σου Ράλλη !

Γεια σου ρε Νικο!!!!!Προσπαθουσα να καταλαβω ποιος εισαι γιατι ηξερα οτι εισαι στο φορουμ αλλα με τοσα ψευδωνυμα εχω μπερδευτει.....Πολυ καλη ασκηση, την εχω λυσει...Λυση θα βαλω αυριο γιατι τωρα κολλαει ο Η/Υ,εχει πολυ κοσμο......Α,ξερεις καθολου σλοβενικα??Η εστω μερικες φρασεις για τα βασικα...Αν θες στην κεντρικη σελιδα του φορουμ,κανε κλικ στο ΙΜΟ και αν ψαξεις θα βρεις πολλες χρησιμες φρασεις συγκεντρωμενες.Αντε τα λεμε.....

ΡΑΛΛΗΣ :D

Το αυριο εγινε μεθαυριο, αυτο παραμεθαυριο,κ.ο.κ....Λοιπον,δεν την ειχα λυσει(ειχα λυσει μια που τις εμοιαζε πολυ,αλλα τελικα ο τροπος λυσης διεφερε αρκετα+αυτο ηταν που με μπερδευε...)Εχουμε:
Επειδη p,q ρειναι πρωτιοι αριθμοι διακρινουμε τις περιπτωσεις
1)p διαιρει το$5^{p}-2^{p}$οποτε για p διαφορετικο των 2,5 απο το θ.Fermat περνουμε p/3 (για p=2,5 προκυπτει ατοπο)<=>p=3
2)p/$5^{q}-2^{q}$και τωρα το δυσκολο σημειο...Αφου p.q διαφορετικοι του 2 θα ειναι και οι δυο περιττοι οποτε (q,p-1)=1.Αρα υπαρχουν κ,λ εZ ωστε κq-λ(p-1)=1<=>[b]kq=λ(p-1)+1 (1) [/b]Eπισης [b]$5^{q}$ισουπολοιπο$2^{q}$ modp(2)[/b]Απο τις 1+2+θ.Fermat παιρνουμε p/3
Σε καθε περιπτωση εχουμε δηλαδη p=3.Tωρα 5^3-2^3=117=9*13.
Τωρα ευκολα προκυπτουν οι λυσεις (p,q)=(3,3),(3,13),(13,3)

ΡΑΛΛΗΣ :D

Τέλεια Ράλλη !!!!


Hey guys, not sure if this is the right place for this question, but anyway, I want to know if the following sum can be expressed in closed form: \[ \sum_{n \equal{} \minus{}\infty}^\infty \text{sech}\left(nx\right)\text{sech}\left((m\minus{}n)x\right).\]  Here $ m$ is an integer and $ x$ is a real.

It appears to me that the following equality is true for all integers $ m \ne 0$ and all reals $ x \ne 0$:

$ \sum\limits_{n \equal{}  \minus{} \infty }^\infty  {\text{sech} \left( {nx} \right)} \text{sech} \left( {\left( {m \minus{} n} \right)x} \right) \equal{} 2\left| {m\text{csch} \left( {mx} \right)} \right|$

At the moment I have no idea how to prove it.


induction
combinatorics proposed
combinatorics

A pile of cards, numbered with $1$, $2$, ..., $n$, is being shuffled. Afterwards, the following operation is repeatedly performed: If the uppermost card of the pile has the number $k$, then we reverse the order of the $k$ uppermost cards.

Prove that, after finitely many executions of this operation, the card with the number $1$ will become the uppermost card of the pile.

Let $n_1>1$ be the largest card which ever appears on top (if $n_1=1$ we're done). After we perform the required operation, we will work only with the topmost $n_1-1$ cards, and all of them will be less than $n_1$, so they must be precisely $1,2,\ldots,n_1-1$. We can thus use induction.

I read the solution but I don't understand in that solution .According to that solution after we perform the required the opration we work only with

n1-1 topmost cards.But why n1-1 topmost cards must be 1,2,3,.....,n1-1 .

Could you help me?

Yes, the solution contains a small error: after flipping card $ n_1$, we only ever deal with the top $ n_1 \minus{} 1$ card of the deck; of these, some will appear at the top of the deck and other may not.  Those that appear all belong to the set $ \{1, 2, \ldots, n_1 \minus{} 1\}$ -- the others may not belong to this set, but if they don't, it doesn't matter (since they never appear on the top of the deck, and so might as well be blank for the purposes of this problem).  So, either we may ignore them or we may simply trade them out for the remaining cards from $ \{1, 2, \ldots, n_1 \minus{} 1\}$.  In either case, we do get to induct, and that's all we need.

i'm sorry but i didn't understand your solutions so i'm posting here my own solution. first of all we must fix a notation : the cards and their values will be represented as a set of integers and the card on the top will be represented by the first number of the set (so the bottom will be the last number of the set). Now we can deduce two considerations.
-Consideration 1 : the value of a number is important only if it is the first number of the set.
-Consideration 2 : only the biggest number of the set can move the last number of the set, so if the last number of the set is also the biggest one it won't move. We can also see that if the biggest number of the set is in the first position the operation defined in the exercise will invert the order of all the set (being the range of the biggest number maximal) and the biggest number comes to the last position and will no longer move. The main idea of my demonstration is that operating many times as required by the exercise if a number never comes to the top then at the top must be the 1 (this is not obvious because if for example we have a configuration 'C' and after 'k' operations we have the same configuration 'C' the '1' will never be on the top and on the top will be always only the same 'k' numbers repeating themselves).
I have at the same time demonstraded by induction this fact and the fact that the '1' will sooner or later appear on the top.
Let see the case in which n=2.This is very simple: there are only two configurations : '1-2' that is already ok, and '2-1' that with one operation becames '1-2'. we see that we have demonstrated that if the '2' doesn't come to the top then there is alredy the '1' and that the '1' finally comes on the top. Now let's suppose that this is demonstrated for all sets of 'n' numbers : we will demonstrate
that it is ok also for all the sets with 'n+1' numbers. We can see that we can build all the sets of 'n+1' numbers putting the number 'n+1' in a set of 'n' numbers: if the 'n+1' number is put in the last or in the first position
then from consideration 2 we see that the presence of the 'n+1' isn't important at all and the only numbers to move will be the numbers of the set of 'n' numbers: for that set we supposed that the '1' comes
on the top so we are ok. Now let's suppose that the 'n+1' is put in a generic place in the set of 'n' numbers. If the 'n+1' ever cames on the top from what i said right now we are ok (both the 'n+1' and the '1' get on the top which is what we wanted to show). So let us also suppose that the 'n+1' never comes on the top. Then from consideration 2 the last number (let's call it 'L') of the set
will not move and so we can ignore it.From consideration 1 we know that the value of the biggest number is not important because we supposed it will never come on the top: so we can imagine that the biggest number has the value 'L' and that the number in first position does not exist. Now what we have done is building a set of 'n' numbers composed by different numbers from 1 to n. This is a case in which we supposed that if a number (in this case the biggest number of the set that we re-called with the value 'L') does not appear on the top then the '1' has already appeared on the top. We supposed that the biggest number won't appear in first position so we must deduce that there is alredy a '1' (this is ok because we showed that if the biggest number does not come to the top then there is already a '1').

The solution below might be similar to (or possibly same as) what has already been commented, which admittedly I have not read quite carefully.

Assume $n > 1$. Let $S = \{1, 2, \cdots, n\}$ and let $F \subset S$ denote the set of numbers that appear on the top finitely many times. We shall prove by induction that $k \in F$ if $1 < k \le n$ (*). Observe that if $k$ comes up on the top, then in the next step it is placed in the $k$th position, and its position does not change after that unless a larger number makes it to the top. First, this implies that $n \in F$, which is the base case. Second, it constitutes the inductive step ( because if all numbers larger than $k$ belong to $F$, then $k \in F$). Hence, (*) follows. Therefore, $1 \not \in F$ because the process continues indefinitely. Hence, $1$ will appear on the top after finitely many steps.


mtms5467 is bored at home, and decides that blasting into outer space is a good idea. After landing atop a high cliff on some random planet, mtms5467 steps out, and hurls a rock into the air. The rock goes a lot faster and higher than expected--after 5 seconds, it reaches a maximum height of 567 feet, and after a total of 14 seconds, it smashes on the ground and disappears into dust.

a) What is the acceleration due to gravity on this planet?

b) What was the initial upward velocity of the rock?

c) How high above ground level was the cliff?

This can be solved using the projectile motion formula/setting up a quadratic equation. I learned this in Algebra 1 so I thought it'd be appropiate for the Mathcounts forum...a mod can move it if necessary

I think I learned this in Alg II or at least the teacher talked about it.

I think this is a similar question:
mtms5467, can you help me?

A projectile is launched upward from ground level with an initial speed of 98 m/s. How high will it go? When will it return to the ground?

[quote="lotrgreengrapes7926"][quote="SplashD"][quote="lotrgreengrapes7926"]Isn't this more a physics question? And I don't think we can tell, as we don't know the gravitational force.[/quote]

Isn't there a formula?[/quote]
I thought that only worked on Earth.[/quote]

Why are you asking me? I didn't take Physics yet or know anything about it.

I don't know physics.  mtms5467, could you give us a set-up?  Thanks.

My approach--I would first try to plot the information as points on a parabola. Have the parabola both in vertex form and in $y=ax^{2}+bc+c$ form. Then look at this website
http://www.purplemath.com/modules/quadprob.htm
and try to put the $y=ax^{2}+bc+c$ parabola into the form they give in the middle of the page.

[quote="SplashD"]A projectile is launched upward from ground level with an initial speed of 98 m/s. How high will it go? When will it return to the ground?[/quote]

Can you answer my question, mtms5467?

[quote="lotrgreengrapes7926"][quote="bpms"]I have an idea. You can try to find a quadratic that fits for this.
If it's $ax^{2}+bx+c$ then you can plug in x's. $\frac{-b}{2a}=5$
$-10a=b$
The equation can be rewritten as $ax^{2}-10ax+c$.Plugging in five for x gives $25a-50a+c=567$
$c-25a=567$
Plugging in fourteen gives
$196a-140a+c=0$
So we have the system
$56a+c=0$ and
$c-25a=567$
Therefore $25a+567=-56a$
$a=-7$
plugging into $c-25a=567$ gives $c=388$.
So the equation is $-7x^{2}+70x+388$ I don't know what godd this does though :([/quote]

$f(14) \ne 0$ because it's falling off a cliff, which we don't know the height of.
EDIT: Never mind.

mtms, is it 567 feet above the cliff or above the ground?[/quote] So I wasted all that time deriving an equation for nothing!

[quote="bpms"][quote="lotrgreengrapes7926"]
$f(14) \ne 0$ because it's falling off a cliff, which we don't know the height of.
EDIT: Never mind.

mtms, is it 567 feet above the cliff or above the ground?[/quote] So I wasted all that time deriving an equation for nothing![/quote] No, if it's 567 feet above where the rock breaks, then your equation is correct.

I've moved this thread to the Introductory Physics forum (with a shadow thread still in the MathCounts forum), which should be the right place for it. If not, a mod can move it to the appropriate forum.

So for the original question all you have to do is apply newton's laws of motion and keep solving.(is the height of cliff coming 567 too?).

@splashD--you need to give the angle at which the projectile is projected as well.

SplashD--

When working with meters, the gravitational force is 9.8, and -1/2 of that is -4.9. The given initial velocity is 98. The height is 0 (launched from ground level). Using all the information we have we can set up the equation $h=-4.9t^{2}+98t$

When the height is 0, the projectile lands. So we plug 0 in for h and find that the solutions are 0 and 20. So the projectile will return to the ground at [b]20 seconds[/b].

Using $\frac{-b}{2a}$ or just common sense (the two x-ints are 0 and 20) we find the x-coord. of the vertex is 10. The vertex is the maximum of the parabola, so we plug 10 in for t and solve for h. Solving we get [b]490[/b].

[quote="shadysaysurspammed"]@splashD--you need to give the angle at which the projectile is projected as well.[/quote]
Actually I don't think you need the angle...

[quote="bpms"]Is my equation right :maybe: .[/quote]
The equation I got was $-7x^{2}+70x+392$

So is the cliff 388 feet above the ground.

[quote="bpms"]plugging into $c-25a=567$ gives $c=388$.[/quote]
Slight calculatory error. It's $392$.

[quote="mtms5467"]mtms5467 is bored at home in CT, and decides that blasting into outer space is a good idea. After landing atop a high cliff on some random planet, mtms5467 steps out, and hurls a rock into the air. The rock goes a lot faster and higher than expected--after 5 seconds, it reaches a maximum height of 567 feet, and after a total of 14 seconds, it smashes on the ground and disappears into dust.

a) What is the acceleration due to gravity on this planet?

b) What was the initial upward velocity of the rock?

c) How high above ground level was the cliff?[/quote]
I think I'll try it.
[hide="A"]Let $x$ feet/second be the acceleration due to gravity on the planet. Then it takes $9$ seconds for the rock to go from $567$ feet in the air to the ground, and it also takes $9$ seconds for the rock to go from a speed of $0$ feet/second (when the rock is $567$ feet above the ground) to a speed of $9x$ feet/second (when the rock is on the ground). The average speed for the whole time is $\frac{0+9x}{2}=\frac{9x}{2}$ feet/second, which means that $9\times\frac{9x}{2}=567$, or $x=\boxed{14}$ feet/second^2.[/hide]
[hide="B"]The rock ends up at $0$ feet/second after $5$ seconds, so it started as $5x=\boxed{70}$ feet per second since the rock would decelerate at $x$ feet/second^2.[/hide]
[hide="C"]From B the rock traveled at an average speed of $\frac{5x}{2}=35$ feet/second for $5$ seconds, so it traveled a total of $35\times5=175$ feet to get to a height of $567$ feet, which means that the cliff is $567-175=\boxed{392}$ feet high.[/hide]
I hope that's right.  :lol:

[hide]
We know that the rock reaches its maximum height at 567 feet, and then takes 14-5 = 9 seconds to reach ground level. Therefore the following equation can be used to find acceleration due to gravity:
s = ut+1/2at^2
As we know u = 0 when the maximum height is reached,
-567 = 1/2*a*(9)^2
Solving for a, we get
a = [b]-14 feet/s^2[/b]

Now, we know that the rock takes 5 seconds to reach the maximum height from the time when it is thrown. This information can be put into the following equation:
v = u+at
As velocity is 0 at maximum height,
0 = u+(-14)(5)
u = [b]70 feet/s[/b]

Finally, it takes 5 seconds for a rock thrown from a certain height h with an initial vertical velocity of 70 feet/second to reach ground level. The following equation can be used:
-h = 70(14)+1/2*(-14)*(14)^2
h = [b]392 feet[/b][/hide]


hey guys!!!!!!!whatshould i do at level 7?it says me ''i 'd like the backwards tho''.......I don't understand.there's nothing else to do.......... :(

At level 7 you should buy some armor before you take the next quest, and maybe get some experience to get a decent mana base, so you should kill some monsters to advance to level 8.

Unless we're talking about a different game of course. ;)

[quote="Peter VDD"]Unless we're talking about a different game of course. ;)[/quote]

I fear you are... since the question seems to refer to [url=http://deathball.net/notpron]Notpron[/url] level 7.

HINTS see below

By the way, I have been stuck in lvl 18 for a long time now (not that I would like the spam in this lvl that much), but please don't give hints...

As for Peter's game, you are talking about EQ, right? I actually never played it, I play RS (F2P) instead, and I must say the description seems similar... anyway, I think when I was lvl 7 I spent most of my time questing and slaughtering goblins, and it was pretty clear what to do all the time, so I would wonder if anybody would ask for help at this level...

  darij

HINTS for NP lvl 7:
[hide="Hint (or spoiler if you see it this way)"]Look at the title: "he went to the old school"
[hide="Hint II"]There is a google bar...
[hide="Hint III"]Maybe you don't like chocolate bars, but be open minded and don't defy learning some highly interesting facts about the history of Twix ;)
[/hide][/hide][/hide]

[quote="darij grinberg"]As for Peter's game, you are talking about EQ, right?[/quote]Actally I was talking about Diablo. I guessed it wouldn't be that game but there are just 1000 games with a level 7 ;)

There is an entire topic devoted to notpron by the way.


Find first
(1) decimal digit of 2^987654321
(2) two decimal digits of  2^987654321
(3) three decimal digits of 2^987654321
(4) n decimal digits of 2^98765321 (represent as function of n)

This is already posted in Intermediate Forum and the Puzzles/Brainteaser. Please delete this, mods.


There is a $ n*n$ form.We define "running through" which means a line has common point with the interior(without edge) of the grid.Find the least number of lines that can "running through" all of the grids.

An $ n \times n$ square is divided into $ n^2$ unit squares.  The question asks for the smallest number of lines necessary such that for each unit square, at least one line passes through its interior.

Isn't it obviously $ n$ ?  :wink:

Pierre.

how is it obvious? a line can pass through the interiors of more than $ n$ unit squares...

In fact,it's not hard to find when n=4,we need at least 3 lines.
I wonder if for each n is bigger than 3,we need at least n-1 lines.


geometry
trigonometry
function
geometry unsolved

Let (O) be a circle with AB is a diameter. C is a mobile point on circle. Contruct equilateral triagle BCD such that D is out of circle (O). Define the projection E of C on the silelines AB. Assume M, N, P, Q is the midpoints of  AD, OA, OE, DE, respectively. Find the position of C on circle (O) such that the area of quadrangle MNPQ is minimum

[quote="phuong"] [color=darkred]Let $ w \equal{} C(O,R)$ be a circle with a diameter $ AB$ . For a mobile point $ C\in w$ construct the equilateral triangle $ BCD$

such that $ D$ is out of $ w$ . Define the projection $ E$ of $ C$ on the line $ AB$ . Denote the midpoints  $ M$ , $ N$ , $ P$ , $ Q$

 of  $ AD$ , $ OA$ , $ OE$ , $ DE$ respectively. Find the position of $ C\in w$ such that the area of $ MNPQ$ is [b]maximum[/b].[/color] [/quote]

[color=darkblue][b][u]Proof.[/u][/b] Denote the projection $ F$ of $ D$ on $ AB$ . Prove easily that $ [MNPQ] \equal{} \frac 12\cdot [AED]$

(watch to two cases : $ E\in (OB)$ and $ E\in (AO]$ ). Observe that

 $ [AED] \equal{} \frac 12\cdot AE\cdot DF$ . Thus, $ [MNPQ]\ \minus{} \ \max\ \Longleftrightarrow\ AE\cdot DF\ \minus{} \ \max$ . Suppose w.l.o.g. $ R \equal{} \frac 12$ .

If denote $ m(\widehat {ABC}) \equal{} x\in\left(0,\frac {\pi}{2}\right)$ , then $ AE \equal{} \sin^2x$ and $ DF \equal{} \cos x\cos (x \minus{} 30)$ . Therefore,

$ [MNPQ]\ \minus{} \ \max\ \Longleftrightarrow$ the function $ f(x) \equal{} \sin^2x\cos x\cos (x \minus{} 30)$ is [b]maximum[/b] on $ \left(0,\frac {\pi}{2}\right)$ .

Denote $ \tan x\equal{}t>0$ . Thus,  $ [MNPQ]\ \minus{} \ \max\ \Longleftrightarrow$ $ h(t)\equal{}\frac {t^2(t\plus{}\sqrt 3)}{(t^2\plus{}1)^2}\ \minus{}\ \max$ .

Show easily that $ h'(t)\ .s.s.\ \minus{}\left(t^3\plus{}2t^2\sqrt 3\minus{}3t\minus{}2\sqrt 3\right)$ a.s.o.

[b][u]New problem.[/u][/b] [u]Ascertain the geometrical locus of the point[/u] $ D$ . $ \blacktriangleleft\boxed{\boxed {\ \mathrm {S\ U\ C\ C\ C\ E\ S\ S\ !}\ }}\blacktriangleright$[/color]

In my country, that problem has used for the test to select the pupil in 9 grade. How can the pupil do?


[quote="tridecalogism_lover"][quote="binbunbo"]If a, b, c > 0
Prove that:
$a^{2}+b^{2}+c^{2}+2abc+1 \geq 2 (ab+bc+ca)$[/quote]

just plug in numbers for a b or c, like 1 or something. I don't know if there's any other way of solving this besides that.[/quote]
That wouldn't be a proof though.

[hide="Possible hint"]It suffices to prove that $2abc+1 \ge ab+bc+ca$.  I don't know how to prove this, but it seems plausible (by plugging in some numbers)
From that point on, note that we have by 3 applications of AM-GM (or 1 application of Cauchy) that:
$a^{2}+b^{2}+c^{2}\ge ab+bc+ca$
Adding this to the other inequality gets the desired result.[/hide]

[quote="vishalarul"]It suffices to prove that $2abc+1 \ge ab+bc+ca$[/quote]

But of course it's not true.  Let $c \to 0$ and let $a, b$ be large.

I managed to solve it when $a,b,c>6$:
[hide]If $a,b,c>6$,
$2-\frac{a}{3}< 0$

$2-\frac{b}{3}< 0$

$2-\frac{c}{3}< 0$

Since $a,b,c$ are positive,
$bc(2-\frac{a}{3}) < 0$

$ac(2-\frac{b}{3}) < 0$

$ab(2-\frac{c}{3}) < 0$

Now we have by the trivial inequalities that:
$a^{2}+\frac{1}{3}> bc(2-\frac{a}{3})$

$b^{2}+\frac{1}{3}> ac(2-\frac{b}{3})$

$c^{2}+\frac{1}{3}> ab(2-\frac{c}{3})$

Adding these three inequalities gets the desired result.[/hide]

To a mod: Move this to
Forum index » Olympiad Section » Inequalities » Inequalities Unsolved Problems.


Let $A_1$, $B_1$ and $C_1$ be the midpoints of the arcs $BC$, $CA$ and $AB$ of the circumcircle of a triangle $ABC$ respectively. Let $A_2$, $B_2$ and $C_2$ be the points where the incircle of the triangle touches the sides $BC$, $CA$ and $AB$ respectively.

Prove that $A_1A_2$, $B_1B_2$ and $C_1C_2$ are concurrent.

A simple angle chase will show that $AB_1C_1$ and $IB_1C_1$ are both similar to $ICB$, so they must be congruent, and it follows from here that $B_1C_1\perp AI\Rightarrow B_1C_1\|B_2C_2$. We do the same for the other pairs of sides of $A_1B_1C_1,A_2B_2C_2$ to conclude that they are homothetic.

I assumed that by arcs $BC,CA,AB$ you meant the arcs which do not contain $A,B,C$ respectively.

It's the concurrence of the lines DD", EE", FF" in http://www.mathlinks.ro/Forum/viewtopic.php?t=17224 post #2. Very easy and classical.

  Darij