algebra
polynomial
superior algebra
superior algebra solved

let polynominal P(x) such that :
 $ P(k) = \frac{k!(n+1-k)!}{(n+1)!}   \forall l k \in 0;1;2... ;n$
 find value : $ P(n+1)$

$ P(n\plus{}1)\equal{}n\plus{}1$, just direct substitution

[quote="hjbrasch"]$ P(n \plus{} 1) \equal{} n \plus{} 1$, just direct substitution[/quote]

How did you get $ n\plus{}1$? If that was a polynomial formula and you only had to make $ k\equal{}n\plus{}1$ in it, it would still yield
$ \frac{(n\plus{}1)!0!}{(n\plus{}1)!}\equal{}1$. But it is not a polynomial formula.

I should say that the way I get the problem is:
$ P$ is a polynomial and $ P(k)\equal{}\frac{k!(n\plus{}1\minus{}k)!}{(n\plus{}1)!}$ for all $ k\equal{}\overline{0,n}$. Find $ P(n\plus{}1)$.

From now on, YOU is a generic name for hjbrasch.
Any two polynomials with the give property differ by a multiple of $ X(X\minus{}1)\ldots (X\minus{}n)$ and the value of this at $ n\plus{}1$ is $ (n\plus{}1)!$ so the value of $ P(n\plus{}1)$ can only be determined modulo a multiple of $ (n\plus{}1)!$. Since your polynomial seems to take values of the form $ 1/r$ for $ r\in\mathbb N$, the best we can hope for the coefficients of $ P$ is for them to be rational. Now if I put a rational coefficient to $ (n\plus{}1)!$ it is clear that I can reach any other rational number and this makes your problem a bit vague.

Are you sure you did not want $ P(k)\equal{}\frac{(n\plus{}1)!}{k!(n\plus{}1\minus{}k)!}$ and integer coefficients for $ P$?
Or did I not get the right problem?

It seems likely that the polynomial should have minimal degree, i.e., $ \leq n$. Then, it is unique, and it makes sense to ask for $ P(n\plus{}1)$. If I am not mistaken, the polynomials for $ n\equal{}0,1,2$ are $ 1,\minus{}X/2\plus{}1,X^2/3\minus{}X\plus{}1$. owk

Let $ P(X) \equal{} \sum_{i \equal{} 0}^n\frac {( \minus{} 1)^{n \minus{} i}(n \plus{} 1 \minus{} i)}{(n \plus{} 1)!}X(X \minus{} 1)\ldots \widehat{(X \minus{} i)}\ldots(X \minus{} n)$. The hat means that the corresponding term is missing from the product.
It is fairly easy to see that this is what we are looking for.

Then
\[ P(n \plus{} 1) \equal{} \sum_{i \equal{} 0}^n\frac 1{(n \plus{} 1)!}( \minus{} 1)^{n \minus{} i}(n \plus{} i \minus{} 1)\frac {(n \plus{} 1)!}{n \plus{} 1 \minus{} i} \equal{}
\]

\[ \sum_{i \equal{} 0}^n( \minus{} 1)^{(n \minus{} i)} \equal{}
\]

\[ \equal{} \left\{\begin{array}{cc} 1, &\mbox{if n is even}  \\
0,&\mbox{if n is odd}\end{array} \right.
\]
The description of $ P$ comes from Lagrange interpolation:
If $ x_1,\ldots, x_n$ are distinct numbers and we want a polynomial $ P$ such that $ P(x_i) \equal{} a_i$ for some $ a_i$ and all $ i \equal{} \overline{1,n}$, then we are going to look for a polynomial of the form
\[ P \equal{} \sum_{i \equal{} 1}^nc_i(X \minus{} x_1)\ldots\widehat{(X \minus{} x_i)}\ldots(X \minus{} x_n)
\]
The $ c_i$s can be uniquely determined from the conditions $ P(x_i) \equal{} a_i$. The point is that the $ x_i$s are all distinct and $ x_i$ cancels all the terms except the one where it does not appear in.

This $ P$ has degree $ \leq n \minus{} 1$. It is clear that if $ P,Q$ have the property that $ P(x_i) \equal{} Q(x_i) \equal{} a_i$, then $ (P \minus{} Q)(x_i) \equal{} 0$ for all $ x_i$, so by Bezout and again because the $ x_i$s are all distinct, $ (X \minus{} x_1)\ldots(X \minus{} x_n)| P \minus{} Q$. So any polynomial other than $ P$ with the required properties has degree at least $ n$, hence $ P$ is the polynomial of minimal degree with the required properties.

owk's computations match my formula.

[b]Hong Quy[/b], it seems that I counted the "k" to your P(k)-term in the problem description, since u didn't use a separator, sorry, then it is of course more involving


function
floor function
algebra proposed
algebra

[quote="flip2004"]Find all positive $x$ having the property  $\; \; \; \; \lfloor x\lfloor nx\rfloor\rfloor-\lfloor nx\rfloor = n-1 \; \; ,\; \; \; \forall n \in{\mathbb N}^{*}\; .$[/quote]
Let $m(n)=\lfloor x \lfloor nx\rfloor \rfloor-\lfloor nx\rfloor$. It is easy to show $-x-1+n(x^{2}-x)<m<(x^{2}-x)n+1$ if x>=0 and $-1+n(x^{2}-x)<m<(x^{2}-x)n-x+1$ if x<0. Therefore $x^{2}-x=1$ It give $x_{1}=\frac{1+\sqrt 5}{2},x_{2}=\frac{1-\sqrt 5 }{2}.$
Solution $x_{2}$ does not work, brcause $m(1)=1\not =0.$
Solution $x_{1}$ works.

[quote="Rust"]... $x_{1}=\frac{1+\sqrt 5}{2}$=... golden- mean[/quote] Nice solution ,... but ... [size=75][b] it must be shown that $x_{1}$  satisfies the desired equalities ! [/b][/size]

There is better equation:
$\lfloor x\lfloor nx\rfloor\rfloor+1=\lfloor nx^{2}\rfloor \; \; ,\; \; \; \forall n \in{\mathbb N}^{*}\;$.


1. Place a small number of weights or washers (be sure that all of the washers you use are the same size.) on the bottom clip of the apparatus. This part of the apparatus hangs straight down, and the weight of the washers supplies the centripetal force.

2. Practice whirling the stopper (or ball) until you can keep the top clip a short distance below the bottom of the glass tube while the stopper whirls. IMPORTANT! If the clip touches the bottom of the glass tube, the weights are no longer supplying the centripetal force! If the clip rises or falls appreciably as the stopper whirls, the radius of the circle is changing. Practice!
Use a stopwatch to measure the time taken for a reasonable number of revolutions (20 - 30 perhaps). Record your data.

3. Change the number of washers on the bottom clip (centripetal force) and repeat steps 3 and 4. Repeat for several different weights. Record the data.

4. Change the position of the top clip to change the radius of the circle. Repeat the experiment for this radius. Be sure to indicate where the radius changes in your data table.

During this experiment, i was wondering what are the MAJOR sources of errors that might occur during this procedures?  Also what really provides the centripetal force?

[quote="Rajiv"]A diagram could have been helpful for forum members to comprehend the experiment.

I'll do that on your behalf!

[quote="cdymdcool"]

Also what really provides the centripetal force?

[/quote]

Judging by the diagram, I feel it is the tension in the string providing necessary centripetal force. Since the string doesn't move, the tension, $ T \equal{} mg$, weight in hanger.[/quote]

beautiful!
but also what might be the major sources that cause this experiment to be inaccurate?


Εξεταστε αν καποιο από τα παρακατω αθροισματα ειναι αρρητος.

$ \sum_{n=1}^{\infty}{\frac{t}{n*(n+t)}}$ οπου [b]t[/b] ρητος στο (0,1)

Υπαρχουν απειροι τετοιοι αρρητοι?

Για t=1/2, το άθροισμα ισούται με 2[(1/2 - 1/3) + (1/4 - 1/5) + (1/6 - 1/7) + ...] = 2[1 - ln(2)] που είναι άρρητος.

Δεν έχω ελέγξει το δεύτερο ερώτημα ακόμη.

Ναι ετσι ειναι. Αν δεν υπαρχει καποιο "απροοπτο" στις πραξεις -δεν τις εκανα μεχρι τελους λογω χρονου- τοτε ισχυει και το δευτερο....


calculus
trigonometry
calculus computations

[quote="Xile"]If
y = x sin (rx)

For what values of r is it true that

d^2y
------ + y = 2r cos (rx)
dx^2[/quote]
We have:
$y = x \sin (rx)$ and what value of $r$ is it true that $\frac{d^{2}y}{dx^{2}}+y=2r \cos (rx)$?

[hide]$\frac{dy}{dx}=\sin (rx)+rx \cos (rx)$
$\frac{d^{2}y}{dx^{2}}=r \cos (rx)+r \cos (rx)-r^{2}x \sin (rx)$

$\frac{d^{2}y}{dx^{2}}+y=2r \cos (rx)$
$[ r \cos (rx)+r \cos (rx)-r^{2}x \sin (rx) ]+[ x \sin (rx) ]=2r \cos (rx)$
$2r \cos (rx)-r^{2}x \sin (rx)+x \sin (rx)=2r \cos (rx)$
$-r^{2}x \sin (rx)+x \sin (rx)=0$
$x\sin(rx) [-r^{2}+1 ] =0 \Rightarrow-r^{2}+1 =0 \text{ or }\Rightarrow \sin(rx)=0 \iff \boxed{r= 0, \pm 1}$

..or if you wanted all solutions I guess it would be $\iff \boxed{r= \frac{n \pi}{x}, \pm 1}$ where $n$ is an integer.[/hide]

You just have to derivate, knowing that: [sin(ax)]' = acos(ax), [cos(ax)]' = -asin(ax).

[hide="Answer"]y' = sin(rx) + rxcos(rx); y'' = 2rcos(rx) - r^2xsin(rx); y'' + y = 2rcos(rx) + (1 - r^2)xsin(rx). So your equation y'' + y = 2rcos(rx) becomes (1 - r^2)xsin(rx) = 0 => r = +/- 1, and r = kx/pi, k = 0, 1, 2, ...
[/hide]


function calculus derivative algebra polynomial induction inequalities

Hello everyone. First a definition:

A function $u$ belongs to the Schwartz class $\mathcal{S}$ if $u \in C^{\infty}$ (on $\mathbb{R}^{n}$) and for all multi-indicies $\alpha$ and $\beta$ ,

$\sup_{x \in \mathbb{R}^{n}}|x^{\alpha} \partial^{\beta}u(x)| < \infty$

I was trying to prove that the map $\mathcal{S} \to  \mathcal{S}$ defined by
$g \mapsto g - \Delta g$ is bijective. (Where $\Delta$ is the laplace operator)

No problem in proving that is injective.
When I was trying to prove that is surjection I got stucked in the following:
Given $\widehat{f}(\xi) \in \mathcal{S}$  prove that $\frac{\widehat{f}(\xi)}{1 + |\xi|^{2}} \in \mathcal{S}$

The hat is just an indication that to get to this sub problem I used the Fourier transform of f. (the fourier transform is a bijection in $\mathcal{S}$). I think that the problem can be solved just using the definition but I found very hard do majorize the things.

Thanks for any help.

I don't see what is the problem?

$\widehat{f}(\xi) \in S \Leftrightarrow f(x) \in S$

$\frac{1}{1+|\xi|^2} \le 1\ \forall \xi$.

$f \in S$ and $|g| \le |f|$ everywhere implies $g \in S$.

Right? The last statement comes direction from the definition -- just check if $g$ satisfies the conditions.

Hi Xevarion!.

[quote="Xevarion"]I don't see what is the problem?

$\widehat{f}(\xi) \in S \Leftrightarrow f(x) \in S$ [/quote]

Why you transformed to $f(x)$ again? Anyway...

[quote]
$\frac{1}{1+|\xi|^2} \le 1\ \forall \xi$.

$f \in S$ and $|g| \le |f|$ everywhere implies $g \in S$.

Right? The last statement comes direction from the definition -- just check if $g$ satisfies the conditions.[/quote]

I dont see that this came directly from the definition. I agree if that if were talking about $L^{\infty}$ spaces for example, then

$f \in L^{\infty}$ and $|g| \le |f|$ everywhere implies $g \in L^{\infty}$.

But I dont see why this is true under the Schwartz space since you have to majorize a multi-index derivative and it not clear for me that
if $|g| < |f|$ then $|\partial^{\beta}g| < |\partial^{\beta}f|$
or I'm completly wrong? :huh:

$D^{\beta}\left(\frac{\widehat{f}(\xi)}{1+|\xi|^2}\right) =\sum_{\alpha\le\beta}D^{\alpha}\widehat{f}(\xi)\cdot \frac{Q_{\alpha}(\xi)}{(1+|\xi|^2)^{|\beta|-|\alpha|+1}}$

$Q_{\alpha}$ is a polynomial. Its degree is under control - in fact, each rational function in that sum is bounded.

We can see that each term in this sum belongs to the Schwartz class, hence the whole sum belongs to the Schwartz class.

You are right: just comparing the absolute values of $f$ and $g$ is not enough. Say, $f(x)=e^{-x^2}\in S$ but $g(x)=e^{-x^2}\sin(e^{x^2})\notin S$. On the other hand, it is not hard to show that all partial derivatives of $\frac 1{1+|\xi|^2}$ grow at most polynomially at $\infty$ (actually, they have a power decay there, but it doesn't matter), which is a sufficient condition for a function to be a multiplier of $S$. So, you are doing everything right. Just the problem you faced is technically unpleasant. To do it, you first need to show that the $k$-th partial derivative of $\frac 1{1+|\xi|^2}$ is of the kind $\frac{P(\xi)}{(1+|\xi|^2)^{k+1}}$ for some polynomial $P$ (you do not even need to control its degree!), which is simple induction. Then you should recall that each partial derivative of the product can be represented as a sum of products of some partial derivatives of the factors with constant coefficients (again, you do not need to care of which derivatives or with what coefficients). This is another simple induction. At last, if you have a product of a function that decays faster than any power and a function that grows at most polynomially, it still decays faster than any power. Hope this helps :).

PS. Oops, Kent was faster (and more concise, as usual :))

Thanks folks!
By the way where I can found the proof of the formula used by Kent?

[quote="niski"]
By the way where I can found the proof of the formula used by Kent?[/quote]Most likely, nowhere. Just prove it yourself by induction on the order of the derivative. All you need is the product and chain rules (plus trivial observations like that a derivative of a polynomial is again a polynomial and so on).

fedja answered that question for me.

Side note on spelling: the name "Schwartz" has been correctly spelled throughout this topic. On the other hand, it's the Cauchy-Schwarz inequality and the Schwarz lemma in complex analysis. One should not confuse Laurent Schwartz (20th century, French) with H. A. Schwarz (19th century, German).

I think I can prove by myself. But  I was just wondering if there are any book that do that since I never saw anywhere (= multivariable calculus books)!
Thanks anyway!!


It's called Langley's problem and you can find a very nice animated solution [url=http://agutie.homestead.com/files/LangleyProblem.html]here[/url].

i tried to solve the first problem using this methode but i didn't find the solution  :blush:, i hate this kind of things

Here:
http://www.personal.us.es/rbarroso/trianguloscabri/
See Problem 90, you can find my collection of 17 solutions of
this problem. Some are mine.
I hope that the spanish no problem for you.

I remember this problem. That angle is 30, right?
I 'll post my solution later.


irrational number
real analysis
real analysis unsolved

Suppose $f: \Re\to\Re$ is continous and periodic such that the sequence
     $a_n=\frac{|f(1)|}{1}+\frac{|f(2)|}{2}+...+\frac{|f(n)|}{n},n\geq 1$
converges.Prove that:
a)$\forall k \in N^*,\exists c\in\Re$ such that : $f(c+1)=f(c+2)=...=f(c+k)=0$.
b)$a_n=0,\forall n \geq 1$

if the period $T$ of $f$ is rational, it is straightforward. Suppose that $T>0$ is an irrational number and $f$ is not the null function. WLOG, one can choose $0<a<b<T$ such that $f(x)>1$ on $[a;b]$. (because $f$ is continuous and the problem remains unchanged if one multiplies $f$ by an arbitrary non null constant). Moreover it is classical (Weyl criterion for example) that the proportion of integers $k$ between $1$ and $n$ such that there exists $p>0$ satisfying $pT+a<k<pT+b$ tends to $Z=\frac{b-a}{T}>0$. So one can find $N_0>0$ such that this proportion is at least $\frac{Z}{2}$ for any $n > N_0$. From here, for $n>N_0$, $\frac{|f(1)|}{1}+\frac{|f(2)|}{2}+..\frac{|f(n)|}{n}> \sum_{i=1}^{\frac{nZ}{2}} \frac{1}{i} > ln(\frac{nZ}{2})$. Hence this sequence diverges. So the period $T$ of $f$ must be rational.

Take $g: [0,\infty]\to [0,M],g(x)=|f(x)|+|f(x+1)|+\dots+|f(x+k)|$,  . We have that $g$ is periodic with same period as $f$ . Assume that $g(x)\neq 0$, hence $g(x)\ge \epsilon,\forall x\in[0,T]$ for some $\epsilon$. Thus,

\[ a_{nk}= \frac{g(1)} k+\frac{g(k+1)} {2k}+...+\frac{g((n-1)k)}{nk}\ge \frac{\epsilon}{k}(1+\frac 1 2+...+\frac 1 n)\to \infty \]
Contradiction.

For the second point:
Assume that period of f is not rational. For any $k$ we can choose $c_k\in [0,T]$ s.t $f(c_k+i)=0,i=1,..,k$. Since $c_k$ is bounded, it has an convergent subsequence. Denote by $\ell$ it's limit. Now one can prove that for any $[a,b]\subset [0,T]$ one can find a 0 value of $f$.

A way to prove is that finding $n$ such that $f([\ell-\epsilon+n,\ell+\epsilon+n])\subset [a,b]$ for some $\epsilon$. Hence, the period must be rational. And this case is simpler.

[quote="xirti"]
A way to prove is that finding $n$ such that $[\ell-\epsilon,\ell+\epsilon]\subset [a,b]$ for some $\epsilon$. Hence, the period must be rational. And this case is simpler.[/quote]

I don`t quite understand how this implies that $T$ must be rational. :blush:

It was a little typo in my previous post.

Here's the argument: Since $f$ have a "0" in each interval and is continuous, it is 0 everywhere. Hence $a_n=0$, and our claim holds in this case. The only case reamined to be considered is when the period is rational.


[quote="ifai"]Let $z=-3i\left[\left(\frac{1+i}{1-i}\right)^{1998}+\frac{\left(\cos\frac{\pi}{12}+i\sin\frac{\pi}{12}\right)^2}{\cos\frac{\pi}3-i\sin\frac{\pi}3}\right]$.
Find $\arg z$.[/quote]
[hide]First we know that $\left(\cos\frac{\pi}{12}+i\sin\frac{\pi}{12}\right)^2 = \left(\cos\frac{\pi}{6}+i\sin\frac{\pi}{6}\right)$. The numerator has $r=1$ and $arg=\frac{\pi}{6}$. The denominator has $r=1$ and $arg=\frac{-\pi}{3}$, resulting in ${\frac{\left(\cos\frac{\pi}{12}+i\sin\frac{\pi}{12}\right)^2}{\cos\frac{\pi}3-i\sin\frac{\pi}3}\right]}$ having $r=1$ and $arg=\frac{-\pi}{6}$, making it ${\cos\frac{\pi}6-i\sin\frac{\pi}6} = \frac{\sqrt{3}}{2} + \frac{i}{2}.$
$\frac{1+i}{1-i} = i$. And $i^{1998} = -1$. So we get \[ -3i (\frac{\sqrt{3}}{2} - 1 + \frac{i}{2}) = \frac{3}{2} + (3 - \frac{3\sqrt{3}}{2})i \][/hide]

$\arg z$ is just the angle that $z$ makes with the real axis. As you've stated, $z = 3 + 3i = ae^{(\pi/4)i}$ (with $a = 3\sqrt{2}$) , so $\arg z = \pi/4$

[quote="deej21"]$\frac{1 + i}{1 - i} = \frac{(1+i)^2}{1-i^2} = i$
Powers of i repeated every fourth power, so $i^{1998} = i^2 = -1$
The second part can be written $\frac{\cos \frac \pi 6 + i \sin \frac \pi 6}{\cos \frac \pi 3 - i \sin \frac \pi 3}$ by deMoivre. Multiply by the conjugate to get $\frac{\sqrt{ \text{cis } \frac \pi 3} \text{cis }\frac \pi 3}{\cos^2 \frac \pi 3 + \sin^2 \frac \pi 3} = \sqrt{\text{cis }\pi} = i$
So $z = -3i(-1 + i) = 3 + 3i$
Not sure what arg means though...

note: $\text{cis }\theta = \cos \theta + i \sin \theta$.  There is no \cis apparently, and I'm too lazy to write it all out.[/quote]
$\cos\theta+i\sin\theta=e^{i\theta}=\exp{i\theta}$


function
calculus
derivative
algebra
system of equations

Give x,y>0 satisfy $ x^2\plus{}y^2\equal{}1$Find
Min :$ \frac{1}{x}\plus{}\frac{1}{y}$
Max :$ xy^2$

Rawr Lagrange Multipliers.

1. We have $ \frac { \minus{} 1}{x^2} \equal{} 2x\lambda$ and $ \frac { \minus{} 1}{y^2} \equal{} 2y\lambda$

Isolating $ \lambda$ and setting it equal, we have $ x^3 \equal{} y^3$ so $ x \equal{} y \equal{} \frac {1}{\sqrt2}$ for our relative extreme giving the minimum as $ 2\sqrt2$

2. We have $ y^2 \equal{} 2x\lambda$ and $ 2xy \equal{} 2y\lambda \implies \lambda \equal{} x$

Thus, $ 2x^2 \equal{} y^2$ so $ x \equal{} \frac {1}{\sqrt3} , y \equal{} \frac {\sqrt2}{\sqrt3}$ and our maximum is then $ \frac {2}{3\sqrt3}$

By AM-GM,

$ \frac {\frac {1}{x} \plus{} \frac {1}{y}}{2} \geq \frac {1}{\sqrt {xy}} \implies \frac {1}{x} \plus{} \frac {1}{y} \geq \frac {2}{\sqrt {xy}}$

Also by AM-GM,

$ \frac {x^2 \plus{} y^2}{2} \equal{} \frac {1}{2} \geq xy \implies \frac {2}{\sqrt {xy}} \geq 2\sqrt {2}$

$ \frac {1}{x} \plus{} \frac {1}{y} \geq \frac {2}{\sqrt {xy}} \geq 2\sqrt {2}$

$ \therefore \min(\frac {1}{x} \plus{} \frac {1}{y}) \equal{} \boxed{2\sqrt {2}}$

@Mewto55555: What are Lagrange Multipliers? They seem cool  :D

Uh basically if you have a function f(x,y) subject to a constraint g(x,y)=k, then what you do is you take the following system of equations:

$ f_x\equal{}\lambda g_x$
$ f_y\equal{}\lambda g_y$

where $ f_x$ is the partial derivative of f with repect to x. Then you just solve the thingy and there are your relative extrema (but you still have to watch for critical points on the boundaries, here they would be at x=0, y=0, x=1,y=0).

It extends similarly to functions with more variables.

For the first one, by QM-HM, $ \frac {\sqrt {2}}{2} \equal{} \sqrt {\frac {x^2 \plus{} y^2}{2}} \geq \frac {2}{\frac {1}{x} \plus{} \frac {1}{y}}$. Therefore, $ \frac {1}{x} \plus{} \frac {1}{y} \geq \frac {2}{\frac {\sqrt {2}}{2}} \equal{} 2 \sqrt {2}$.

For the max, by QM-GM, we have $ \frac {\sqrt {3}}{3} \equal{} \sqrt {\frac {x^2 \plus{} \left(\frac {y}{\sqrt {2}}\right)^2 \plus{} \left(\frac {y}{\sqrt {2}}\right)^2}{3}} \geq \sqrt [3]{\frac {xy^2}{2}}$, so $ xy^2 \leq \frac {2\sqrt {3}}{9}$. Equality holds when $ x \equal{} \frac {\sqrt {3}}{3}$ and $ y \equal{} \frac {\sqrt {6}}{3}$.

Also Mewto you forgot to check the boundary cases, and demonstrate that your extrema are actually minima/maxima. :P


what is the number of permutations of set $1,...,2n$ such that for every $i$ its position is $i$ or $i+1$ or ... or $i+n-1$ (mod $2n$)
for example when $n=3$ we have $4,1,3,2,5,6$

If $n = 3$, then for every $i$, its position is $i, i+1$, or $i+2 (mod 6)$.
In your example, $4$ is permutated to $1$ which isn't $4,4+1$, or $4+2 (mod 6)$ ??  :maybe:


modular arithmetic
geometry
3D geometry
number theory proposed
number theory

$ (a)$ Prove that every multiple of $ 6$ can be written as a sum of four cubes.
$ (b)$ Prove that every integer can be written as a sum of five cubes.

a) We have $ 6x\equal{}(x\plus{}1)^2\plus{}(\minus{}x)^3\plus{}(\minus{}x)^3\plus{}(x\minus{}1)^2$
b) We have that $ x^3\equiv x\pmod6$. Suppose we want to write $ n$ as a sum of 5 cubes. Let $ n\equal{}6m\plus{}k$, $ 0\leq k<6$. Then $ n\minus{}k^3$ is a multiple of 6, so it can be written as a sum of 4 cubes, and by adding $ k^3$, we can write $ n$ as 5 cubes.

[hide="Solution"](a). Note the identity $ (n\plus{}1)^3\plus{}(n\minus{}1)^3\plus{}(\minus{}n)^3\plus{}(\minus{}n)^3\equal{}6n$.

(b). Note $ 0^3\equiv 0 \pmod{6}$, $ 1^3\equiv 1 \pmod{6}$, $ 2^3\equiv 2 \pmod{6}$, ..., $ 5^3\equiv 5 \pmod{6}$. This means that we can take the first cube to be $ 1^3$ if the integer $ k$ is congruent to $ 1$ modulo $ 6$, $ 2^3$ if it is congruent to $ 2$ modulo $ 6$, etc.  Subtracting will leave a multiple of $ 6$ to be written as $ 4$ cubes via part (a). For example $ 10\equal{}4^3\plus{}(\minus{}8)^3\plus{}(\minus{}10)^3\plus{}9^3\plus{}9^3$.[/hide]


geometry
3D geometry
sphere
analytic geometry
function
rotation
vector

hello people, I'm sorry I might be OT but I have no idea how to solve this:

there are two spheres $ S_{i}$ of radius R and mass $ m_{i}$.

we have something like

[code]
S1          S2
O___________O===============

------------|--------------> x
           x=0
[/code]

the plane denoted as "____" has no friction, the "===" one has a dynamic coefficient $ \mu\neq 0$.

Let the x-axis oriented towards the right and suppose that the coordinate of S2 is 0.

S2 is not moving and S1 is moving with constant speed $ v_{0}$ (positive) and hits S2.

1)What is the time $ t_{f}$ and the distance $ d_{f}$ (from the zero and initial position of S2) in which the sphere S2 starts moving with costant-speed?

2)What is the kinetic energy of the whole system $ S_{1}\cup S_{2}$ at time $ t_{f}$ ??

I found the intial speed of the sphere S2, let it be $ v_{2f}(0)$, right after the hit and I can find the function $ v_{2f}(t) \equal{} v_{2f}(0)\minus{}\mu g t$ but I have no idea how to find d the stuff asked in questions #1 and #2... can you help?

bye :)

I don't think the first question is possible if I understand the picture. $ S_{2}$ will never move at a constant speed if ==== has a coefficient of friction. There will always be a force opposing motion and never a force in the direction of motion. Thus, it will continually slow down until it stops.

I agree if we consider S2 like a point but we should consider it like a rigid object (the radius is given) :)

If a sphere is rollin without slicing, doesnt have friction force, because if its velocity is $ v$ and the angular velocity is $ \omega$ then $ v \equal{} R\omega$ (this equivalent to say that the contac point has velocity 0) then if the friction force is in the direction to the moving, $ v$ will increase and $ \omega$ will decrease, contradiction, now if the friction force is in opposite direction to the moving then $ v$ will decrease and $ \omega$ will increase contradiction, so the friction force is null (this is an ideal model, think in the skittles, in the reality are become deformed).

Let $ I \equal{}\frac{2m_{2}R^{2}}{5}$  the moment of inertia of $ S_{2}$. After the hit (by conservation of the momentum and conservation of the energy) $ S_{2}$ has velocity $ v_{0,2}\equal{}\frac{2m_{1}v_{0}}{m_{1}\plus{}m_{2}}$ and $ S_{1}$ has velocity $ v_{0,1}\equal{}\frac{(m_{1}\minus{}m_{2})v_{0}}{m_{1}\plus{}m_{2}}$. Note that the normal annul the weight and the friction force goes on x-axis so the angular momentum is conserved with respect to the origin i.e $ \vec{r}\times\vec{p}\plus{}I\vec{\omega}\equal{} cte$, therefore
$ Rm_{2}v_{0,2}\equal{} Rm_{2}v_{f}\plus{}I\omega_{f}\equal{} Rm_{2}v_{f}\plus{}\frac{Iv_{f}}{R}$ (expres $ \vec{r}$ and $ \vec{p}$ in its components if it's necessary)
$ v_{f}\equal{}\frac{5v_{0,2}}{7}\equal{}\frac{10m_{1}v_{0}}{7(m_{1}\plus{}m_{2})}$
now you can use $ v_{0,2}\minus{}g\mu t_{f}\equal{} v_{f}$ and $ \frac{m_{2}v_{0,2}^{2}}{2}\equal{}\frac{m_{2}v_{f}^{2}}{2}\minus{}m_{2}g\mu d_{f}$ to finish.
Please review the calculations.

Astronum: how did you find that? :)

and I actually don't know whether the sphere starts rolling right after the hit or it slices a while, but I think this can be found out...

and where did astrojas exactely used the conservation of angular momentum and for which system?

After the hit $ S_{2}$ starts to move without rotating, but the firction makes that the the sphere became to rotate with certain angular aceleration until $ v \equal{}\omega R$. Now consider the symstem consisting in $ m_{2}$ and the frame of reference with the x-axe of the statement and the y-axe vertical, then the friction doesn`t make torque and the normal annul the weigth. Let $ \vec{r}$ the position vector of the center of mass then $ \vec{r}\times\vec{p}\equal{} (r_{x}\mathbf{\hat{\i}}\plus{}R\mathbf{\hat{\j}})\times(v\mathbf{\hat{\i}}) \equal{}\minus{}Rv\mathbf{\hat{k}}$
I'm not very rigorous couse i'm a student of electronics enginering, but I was in IPHO.

[quote="dphexen"][quote="asdrojas"]then $ \vec{r}\times\vec{p}\equal{} (r_{x}\mathbf{\hat{\i}}\plus{}R\mathbf{\hat{\j}})\times(v\mathbf{\hat{\i}}) \equal{}\minus{}Rv\mathbf{\hat{k}}$[/quote]

why is that?[/quote]

$ (\vec{a}\plus{}\vec{b})\times\vec{c}\equal{}\vec{a}\times\vec{c}\plus{}\vec{b}\times\vec{c}$
and $ \mathbf{\hat{\i}}\times\mathbf{\hat{\i}}\equal{}0$ and $ \mathbf{\hat{\j}}\times\mathbf{\hat{\i}}\equal{}\minus{}\mathbf{\hat{k}}$

It is the angular momentum... and??

when the problem asks when S2 starts to move wth constant speed... I guess when it stops slicing and starts rotating but how do I find that out? Can we find a function v(t) to find the speed of the center of mass of S2 at time t supposing the hit is at t=0?

After the hit $ S_{2}$ starts to slicing with velocity $ v_{0,2}$ and with aceleration $ \minus{}g\mu$, then the friction force makes the sphere rotate with angular aceleration $ \alpha\equal{}\frac{f_{r}}{R}\equal{}\frac{g\mu}{R}$, that is, the velocity will decrease an the angular velocity will increase until $ v\equal{}R\omega$, after that the velocity will be constan and the friction force will desapear. So $ v(t)$ is a linear function whith pendient $ \minus{}g\mu$ for $ 0<t<t_{f}$ and constant after that.

With the ecuation for the angular momentum, you can find $ v_{f}$ using $ v_{f}\equal{}\omega_{f}R$ and $ \omega_{0}\equal{}0$.

[quote]$ \vec{r}\times\vec{p}\plus{}I\vec{\omega}\equal{} cte$, therefore
$ Rm_{2}v_{0,2}\equal{} Rm_{2}v_{f}\plus{}I\omega_{f}\equal{} Rm_{2}v_{f}\plus{}\frac{Iv_{f}}{R}$ (expres $ \vec{r}$ and $ \vec{p}$ in its components if it's necessary)
$ v_{f}\equal{}\frac{5v_{0,2}}{7}\equal{}\frac{10m_{1}v_{0}}{7(m_{1}\plus{}m_{2})}$
[/quote]

[quote="asdrojas"]With the ecuation for the angular momentum, you can find $ v_{f}$ using $ v_{f}=\omega_{f}R$ and $ \omega_{0}= 0$.[/quote]

and how do I find $ \omega_{f}$ and $ \omega_{0}$??

and the angular momentum respect to what is cte?

If O i sthe origin and $ \vec P = m_{2}v\hat\i$ and C is the center of mass then the momentum which is cte is $ \vec L =\vec_{OC}\wedge\vec P$ right??

my exact questions are:

let the hit be at time t=0... find the motion of S2

it is $ v(0) \equal{} v_{0,2}$. Let the time $ t_{1}$ at which it stops slicing. For $ t\in [0,t_{1}]$ it is $ v(t)\equal{}v(0)\minus{}\mu g t$ and $ v(t)\equiv v$ for $ t\geq t_{1}$.

At time $ t_{1}$ it starts rolling with a certain angular speed $ \vec\omega$ such that $ v \equal{}\|\vec\omega\| R$ (using the just-rolling condition).

The problem asks for t1 right?

and now what do I do?

[quote="dphexen"]
and how do I find $ \omega_{f}$ and $ \omega_{0}$??

and the angular momentum respect to what is cte?

If O i sthe origin and $ \vec P = m_{2}v\hat\i$ and C is the center of mass then the momentum which is cte is $ \vec L =\vec_{OC}\wedge\vec P$ right??[/quote]

The the complete equation is for the angolar moment is $ \vec{r}\times\vec{p}+I\vec{\omega}= cte$ with respect to x=0, y=0, z=0, and I coose y vertical. In this equation I don't know how much is $ \omega_{f}$ and $ v_{f}$ but with the relation $ v_{f}=\omega_{f}R$ and the equation for the conservation of the angular momentum. I asume $ \omega_{0}= 0$ becouse i assumed the hit so brief that the friction force doesn't make any work, and there aren't another thing that can makes to $ S_{2}$ rotate.

[quote="dphexen"]but the friction force is $ \vec F \equal{}\minus{}f\hat\i$, why is its momentum null? It is $ OC\wedge\minus{}f\hat\i$ and $ \langle OC,\hat\j\rangle\neq 0$ !![/quote]

No, $ f_{r}$ is aplied on the contact point P betwen the sphere and the ground, P is on x-axe so $ OP\times f_{r}\equal{}0$

so since the friction is applied to the contact point we have that its momentum is zero and equal to the angular momentum of S2 since f_r is the only external force.

We use the second cardinal equation to say that the angular momentum of S2 is constant but how do we actually find it? It is the angular momentum of the center of mass? I don't understand why you compute $ \vec r\wedge\vec p\plus{}I\vec\omega$.

it is $ \vec r \equal{} C\minus{}O$ where C is the center of mass.
For one of the center mass theorem we can say that $ \vec p \equal{} m_{2}v\hat\i$ where v is the speed at which the ball only rolls.
In out frame reference it's also $ \vec r \equal{} x_{C}\hat\i\plus{}R\hat\j$ for some x_C so the external product is $ \minus{}m_{2}v R\hat k$

and now?

[quote="dphexen"]

it is $ \vec r \equal{} C\minus{}O$ where C is the center of mass.
For one of the center mass theorem we can say that $ \vec p \equal{} m_{2}v\hat\i$ where v is the speed at which the ball only rolls.
In out frame reference it's also $ \vec r \equal{} x_{C}\hat\i\plus{}R\hat\j$ for some x_C so the external product is $ \minus{}m_{2}v R\hat k$

and now?[/quote]

The angular mome

Yes, when S2 is over x=0 and $ \omega\equal{}0$, $ L\equal{}\minus{}m_{2}v R\hat k$, for solve this problem you have to know that  the total angular momentum is the angular momentum of the center of mass plus the rotational angular momentum. The equation $ \vec{L}\equal{}\vec{r}\times\vec{p}\plus{}I\vec{\omega}$ is used mainly with problems of astronomy, and apears in any good book of mechanics.

[quote="dphexen"]ok and how do I use that L is costant?[/quote]

The equation for L is $ Rm_{2}v_{0,2}\equal{} Rm_{2}v_{f}\plus{}I\omega_{f}\equal{} Rm_{2}v_{f}\plus{}\frac{Iv_{f}}{R}$.

now
$ Rm_{2}v_{f}=\vec r\wedge\vec p$

$ I\omega_{f}=\frac{I v_{f}}{R}$

 :arrow: I actually don't understant why it is equal to $ Rm_{2}v_{0,2}$

Suppose I understand that... I can find $ v_{f}=\frac{Rm_{2}v_{0,2}}{\left (\frac{I}{R}+Rm_{2}\right)}$ from the above but how do we find the time at which the velocity starts being constant? from the relation $ v_{0,2}-\mu g t_{f}= v_{f}$ ??

And what is $ -m_{2}g\mud_{f}$ term in $ \frac{m_{2}v_{0,2}^{2}}{2}=\frac{m_{2}v_{f}^{2}}{2}-m_{2}g\mu d_{f}$ ??

 :arrow: And how about the kinetic energy question?

For the kinetic energy question I would say that at the beginning it is

$ K_{i}\equal{} K_{1,i}$ found with Konig theorem.(nothing moves but S1) until the hit

then $ K_{f}\equal{} K_{1,f}\plus{}\frac{1}{2}\left ( m_{1}v_{0,1}^{2}\plus{}m_{2}v_{f}^{2}\plus{}I\omega_{f}^{2}\right )$ where $ \omega_{f}\equal{}\frac{v_{f}}{R}$ right?

[quote]$ Rm_{2}v_{f}\equal{}\vec r\wedge\vec p$

$ I\omega_{f}\equal{}\frac{I v_{f}}{R}$

 :arrow: I actually don't understant why it is equal to $ Rm_{2}v_{0,2}$
[/quote]

In $ x \equal{} 0$, $ L \equal{} Rm_{2}v_{0,2}$ ($ \omega \equal{} 0$), and for $ x\geq d_{f}$ $ L \equal{} Rm_{2}v_{f}\plus{}\frac{Iv_{f}}{R}$, so $ Rm_{2}v_{0,2}\equal{} Rm_{2}v_{f}\plus{}\frac{Iv_{f}}{R}$

[quote]And what is $ \minus{}m_{2}g\mu d_{f}$ term in $ \frac{m_{2}v_{0,2}^{2}}{2}\equal{}\frac{m_{2}v_{f}^{2}}{2}\minus{}m_{2}g\mu d_{f}$ ??[/quote]

 $ m_{2}g\mu d_{f}$ Is the work made by the friction.


Find the number $ N\equal{}\overline{abcde}$ in base 10 such that $ a^5\plus{}b^5\plus{}c^5\plus{}d^5\plus{}e^5\equal{}N$ .

[hide="Answers but no method..."]$ 54,748 \equal{} 5^5 \plus{} 4^5 \plus{}7^5 \plus{}4^5 \plus{} 8^5$
$ 92,727 \equal{} 9^5 \plus{} 2^5 \plus{} 7^5 \plus{} 2^5 \plus{} 7^5$
$ 93,084 \equal{} 9^5 \plus{} 3^5 \plus{} 0^5 \plus{} 8^5 \plus{} 4^5$

I know that these are solutions, but have no idea how one would go about finding them[/hide]


I'm about to take my first AoPS class, and I just learned about awesomemath. Are the AoPS classes and awesomemath similar? Personally I think AoPS is better, but would like to hear what previous attendees of the awesomemath summer program have to say.

I haven't been to awesome math but I bet it's more expensive.

it definately is more expensive

but it also depends on what you feel is best for you.

its going to be my first time at camp so i dont know enough to really say

but with aops classes, the only problem is that if the class turnes out to be too hard or too easy,  you cant really change ur pick.

other than that, its pretty good but u need to be really motivated and finish all the hw or eles you wont get anything out of the classes.

AoPS homework is assigned from the book, correct?

The instructors encourage you to work the problems in the book, but there are many other homework problems in the Challenge Sets and Message Board Problems.

AMSP costs around 3300 for Dallas and 3700 for Santa Cruz, which doesn't include spending money and air tickets.  To contrast, AoPS classes cost from 150 to around 350 dollars...

[quote="Temperal"]Seeing as one is an online class and the other a summer camp, are they really comparable?[/quote]

agreed.

i've taken aops classes as well as attend amsp, and personally i prefer amsp just because it's not online. it is certainly costly, but i think it's worth the money if you're willing to try and learn. Plus, you can get one on one help at the camp[from professors and ta's] , and you'll also make tons of new friends and have good time during summer.

if you can afford to go, then go. i recommend doing so.

I can afford to go, but I have plans for the summer.

[i]sigh...[/i] I guess I will stick with AoPS classes!


advanced fields
advanced fields theorems

Hellooooooooooooooo! Can somebody help me with documentation in [b]Mathematical Methods in Risk Theory[/b]? Can i find a virtual book with this subject? Thank uuuuuuuuuu
Have a nice day  :)

Hi,

well, first reflex when looking for something like this : google! :)

http://www.google.com/search?q=mathematical+methods+in+risk+theory


Get an [url=http://www.irchelp.org/irchelp/irctutorial.html]IRC client[/url] and /join #aops on the IRCnet network. Im waiting :D

Anyone having problems or questions?  I can fix/answer them ;)

Why is no one joining? Do you need help using IRC?

i do, what do i do once i click the link?

Hm what's the problem? maybe your firewall's preventing you from connecting

The Washington, USA server's open to firewalls

OK i guess I ll download that thing again since you're still using it.....I hope I still remember how it works..


geometry
quadratics
conics
parabola
algebra
quadratic formula

y = x^2 - mx + m -2

1. Prove that for all real m, there are two real solutions to

x^2 - mx + m - 2 = 0

2. If the graph contains the point (3,6), find the two roots.

3. We have the graph of #2, form a triangle by using the vertex and the two zeroes. Find the area of this triangle.

(1)[hide]Well b/c of the Fundamental Theorem of Algebra you know it has 2 solutions.  However, to prove that they are real, you can plug it into the quadratic formula:

[tex]\displaystyle\frac{m\pm\sqrt{m^2-4(m-2)}}{2}[/tex].  So this means if you want two real solutions always, the discriminant [tex]b^2-4ac[/tex] must be greater than or equal to 0.

m^2 -4m + 8  :ge: 0

Now if you think of this graph, it is a parabola that opens upward and never touches the x-axis.  So, the values for f(x) will always be positive.[/hide]

JS1527 wrote:(1)[hide]
m^2 -4m + 8  :ge: 0
Now if you think of this graph, it is a parabola that opens upward and never touches the x-axis.  So, the values for f(x) will always be positive.[/hide]

This can be rigorized a bit.  If it did touch the x axis, then there would be real solutions.  But the solutions would have [tex]\sqrt{16 - 32} = 4i[/tex], so they don't have real solutions.  It opens upward, since +m^2.

[quote="probability1.01"][quote="Chinaboy"]y = x^2 - mx + m -2

1. Prove that for all real m, there are two real solutions to this equation.[/quote]

I assume you mean two solutions to 0 = x^2 - mx + m - 2.[/quote]

ya, thanks.

and ya, you're all right.

I first did it like JS, and that drove my mom crazy, and Beta's proof was what was in the book.

Quote:2. If the graph contains the point (3,6), find the two roots.
[hide]
y = x^2 - mx + m -2
6 = 3^2 -3m+m-2
m = 1/2

y=x^2-(1/2)x + 1/2 -2
x={3/2, -1}

[/hide]
Quote:3. We have the graph of #2, form a triangle by using the vertex and the two zeroes. Find the area of this triangle.

[hide] find vertex: [tex](\frac{-b}{2a},f(\frac{-b}{2a}))[/tex].  Find distance from vertex to x-axis.  A=1/2*(3/2+1)*h[/hide]


inequalities
logarithms
search
inequalities unsolved

Let  $ a,b,c \in (1;+\infty )$ Prove that
${ \log_{ab}c+\log_{bc}a+\log_{ca}b\ge \log_{a^{2}bc}bc+\log_{ab^{2}c}ac+\log_{ abc^{2}}ab }$

_____________________________
Azerbaijan Land of Fire  :ninja:

We can see the same title  [url=http://www.mathlinks.ro/viewtopic.php?t=326478]here[/url].
That are very confusing us. :wink:

See [url]http://www.mathlinks.ro/search.php?search_author=Pirkuliyev+Rovsen[/url]

''Functional Equation'', ''Equation'' are appeared several times, you do realize it?

You shouldn't put such vague titles of post. :mad:

You are to be regard as a spammer.

Japanese Communities Moderator.

kunny

With the substutions $ x \equal{} \log a$ etc., we have equivalently for $ x,y,z>0$

$ \sum \frac {x}{y\plus{}z} \ge \sum \frac{x\plus{}y}{x\plus{}y\plus{}2z}$

But $ \sum \frac{x\plus{}y}{x\plus{}y\plus{}2z} \le \sum  \frac{x\plus{}y}{4} \left[\frac{1}{x\plus{}y} \plus{} \frac{1}{x\plus{}z} \right] \le \frac{3}{4} \plus{} \frac{1}{4} \sum \frac {x}{x\plus{}z} \plus{}  \frac{1}{4} \sum \frac {y}{x\plus{}z}$

From Rearrangement $ \sum \frac{x}{x\plus{}z} \le \sum \frac{y}{x\plus{}z}$

From Nesbitt $ \frac{3}{4} \le \frac{y}{x\plus{}z}$ and so we are done

[quote="hsbhatt"]With the substutions $ x \equal{} \log a$ etc., we have equivalently for $ x,y,z > 0$

$ \sum \frac {x}{y \plus{} z} \ge \sum \frac {x \plus{} y}{x \plus{} y \plus{} 2z}$

But $ \sum \frac {x \plus{} y}{x \plus{} y \plus{} 2z} \le \sum \frac {x \plus{} y}{4} \left[\frac {1}{x \plus{} y} \plus{} \frac {1}{x \plus{} z} \right] \le \frac {3}{4} \plus{} \frac {1}{4} \sum \frac {x}{x \plus{} z} \plus{} \frac {1}{4} \sum \frac {y}{x \plus{} z}$

From Rearrangement $ \sum \frac {x}{x \plus{} z} \le \sum \frac {y}{x \plus{} z}$

From Nesbitt $ \frac {3}{4} \le \frac {y}{x \plus{} z}$ and so we are done[/quote]some typos. It should be

$ \sum \frac {x \plus{} y}{x \plus{} y \plus{} 2z} \stackrel{C\minus{}S}{\le} \sum \frac {x \plus{} y}{4} \left[\frac {1}{x \plus{} z} \plus{} \frac {1}{y \plus{} z} \right]$

$ \equal{} \frac 14 \sum \frac {x}{x \plus{} z} \plus{} \frac 14 \sum \frac {y}{y \plus{} z} \plus{} \frac 24\sum \frac {y}{x \plus{} z}\le \sum \frac {y}{x \plus{} z}$ by rearrangement  :)


logarithms
geometry
geometric transformation

Let $ x\equal{}2\plus{}\sqrt{2}, y\equal{}(\log_{2}3)^2\plus{}\log_{3}4,z\equal{}(\log_{3}4)^2\plus{}\log_{2}3$,

determine the maximum and minimum of the three.

How is there a maximum and a minimum? Where are the variables?

He gave you three real numbers and he wants you to arrange them in decreasing order without using a calculator.

Oh. Well $ (\log_{2}3)$ is just 1.5 right? And $ (\log_{3}4)$ is 4/3? Estimate root 2 as 1.4ish. Can you get it from there?

lol...

$ \log_x y$ doesnt equal to $ \frac{y}{x}$...

[quote="Bovy11"]Let $ x \equal{} 2 \plus{} \sqrt {2}, y \equal{} (\log_{2}3)^2 \plus{} \log_{3}4,z \equal{} (\log_{3}4)^2 \plus{} \log_{2}3$,

determine the maximum and minimum of the three.[/quote]

i have $ \sqrt2$ memorized to alot of digits and you should too
$ x \equal{} 3.414213562 \ldots$

we will find $ \log_23$ and $ \log_34$ by estimation:
note that $ 3^5 \approx 2^8 \implies log_23 \approx 1.6$
and $ 3^5 \approx 4^4 \implies log_34 \approx 1.25$
now we evaluate y and z
$ y \approx 1.6^2 \plus{} 1.25 \equal{} 3.81$
$ z \approx 1.25^2 \plus{} 1.6 \equal{} 3.1625$
so $ y > x > z$

EDIT: 501 POSTS WOOT :wow:

[quote="FantasyLover"]lol...

$ \log_x y$ doesnt equal to $ \frac {y}{x}$...[/quote]

Haha ouch. I'd like to say I was on drugs when I made that post but I wasn't. I just took a year hiatus from Maths and now I'm rusty as f**k. I don't know WHAT I was thinking when I wrote that!

 :blush:

Hi,I think stevenmeow's way is the best XD
and sorry for my poor translation of problem,,,I have to study English lol.


inequalities
blogs
inequalities unsolved

Let $ a$, $ b$, $ c$ denote the three sidelengths of a triangle $ ABC$. Its altitudes are denoted by $ h_a$, $ h_b$, $ h_c$, and the radii of its excircles are called $ r_a$, $ r_b$, $ r_c$. Prove the inequality

$ \frac {a}{h_a \plus{} r_a} \plus{} \frac {b}{h_b \plus{} r_b} \plus{} \frac {c}{h_c \plus{} r_c}\geq\sqrt3$.

[quote="chien than"][quote="nmtvn"]New trigonometrical inequality[/quote]
To Mods: Please lock this topic, this is a problem from M&Y, issue 9, and we can't discuss it now[/quote]
See here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=167965

But there isn't any true and full solution in that topic! All of solutions are false or not full!

But you can't post a problem from M&Y if it wasn't issue less than 2 months . I think you know it and please don't do it again .

If you want to send solutions to M&Y magazine , you can visit N.T.TUAN'weblog . All problem can be solved on this blog  :mad:

Please respect yourself !  :(

[hide="to nmtvn"] Giữ lấy tự trọng của mình nếu còn có nó  :mad: [/hide]


[hide="solution"]
Note that if the lamps are all on at some point, they will next be all off, so we will prove only that they are at some point all on.

We claim that for any power of $ 2$, $ 2^{k}$, all lamps will be on in exactly $ 2^{k}$ moves. We prove this by induction. In the case that $ k=0$ the result is obviously true. Suppose it is true for $ k$. Then, for the first $ 2^{k}-1$ moves, only the first $ 2^{k}-1$ lamps could be on, and on the $ 2^{k}$th move we are given that the $ 2^{k}$th lamp turns on along with all lamps before it. Embedding this situation into the case where we have $ 2^{k+1}$ lamps, we see that after this the left and right sides of the arrangement will be mirror images of each other, and are initially $ 0000\ldots 00011000 \ldots 0000$, so that the inductive hypothesis says that it will be exactly $ 2^{k}$ moves before all the lamps are on, for a total of $ 2^{k+1}$ moves before all the lamps are on, thus completing the induction.
[/hide]

I don't really understand how you proved part (b)

my solution for part (b) is basically taking 2^n + 1

and then being like haha it reflects

since essentially you start out with the left two on

and then you get to the left 2^n on

and then you have the right two on

and then (the reflection of the above) you get to the right 2^n on

and then you get left two on

blah blah blah

at no point are all of them the same state

Yeah I sort of assumed that they gave us the same statement as they did at MOP, which had part (b) prove that at some point they were all on.

You can furthermore prove that if $ n$ is odd, then the lamps will never be all off.

It is easy to see that $ 000\ldots 0$ can only result from $ 111\ldots 1$ or $ 000\ldots 0$ (since if you had both, ones and zeros, then there is at least a $ 01$ or a $ 10$ in the chain which will result in a $ 11$).

On the other hand, there will always be an even number of ones in the chain and the ones will furthermore only appear in blocks of even size. Also, the number of zeros between two such blocks is always even. This is also easy to verify; it is true after the first step and afterwards, ones will only result from $ 01$ and $ 10$. Also two such "transitions" (ie $ 10$ or $ 01$) cannot coincide since this would require either a $ 101$ or a $ 010$, both impossible by the induction hypothetis. Hence, the number of ones will be 2 times the number of such "transitions", and they will only appear in $ 11$-blocks. Also, the number of separating zeros between two blocks of ones remains even since the the size of an already existing separating zero-block shrinks by 2 and new separating zero-blocks of the length $ k$ can only result from a block of ones of length $ k+2$ and this is an even number by our assumption.

Hence, if there is an even number of ones, there will always be an even number of ones, making it impossible to switch off all lamps for odd $ n$ since switching all lamps off would require all lamps to be switched on, thus an odd number of ones. $ \Box$

Lemma: If we have an infinite sequence of lamps $L_{1},L_{2},....$ we prove by induction that after 2^k-1 seconds the lamps $2,4,6,...,2^k$ will be on and all others off where no lamp bigger than $2^k$ was turned on.
Proof:
For $k=1$ it is obvious.
Suppose it is true for $k=n$ now we prove for $k=n+1$.
Firs after $2^n-1$ seconds $2,4,6,....,2^n$ are on and others off. In the next move we have $2^n+1$ is on and others off. We have that by symmetry wrt $L_{2^n+1}$ that lamp is always off(and it starts as turned on) so it behaves as $L_{1}$ did on the start. So we have that lamps $2^n+1,2^n,2^n-1,...,2$ and $2^n+1,2^n+2,....,2^n+2^n$ behave the same way as $1,2,3,...,2^n$ did in the first $2^n-1$ moves. Because of this we have that after using $2^n-1+2^n=2^{n+1}-1$ moves in total lamps $2,4,6,8,....,2^{n+1}$ are all on and others are all off.

Back to the problem.
If $n=2^s+1$ we have that after $2^s-1$ moves lamps $2,4,6,...,2^s$ are on and in the next move they are all off.
If $n=2^s+2$ we have that after $2^s-1$ moves lamps $2,4,6,...,2^s$ are on and in the next move only $2^s+1$ is on and others off(which is symmetric to the situation after  second where only $2$ is on) so we will never turn the all off(because the game is periodic because of symmetry and if they were all off at one point they would never turn back on)

A cute problem, I liked it a lot.
[hide="solution"]
First define the starting setup of only $L_1$ being on as the 1st state, and after $k-1$ moves we reach the $k$th state.

a) I claim for all $n=2^x$ for $x\in\mathbb{N}$, the lamps will be all turned on at exactly the $n$th state (which means that they will all turn off at the $n+1$th state)

Proof: We use induction. First, the base case of $n=2$ is clearly true.
Now assume that the claim is true for $n=2^k$. Then for $n=2^{k+1}$, at the $2^k$th state $L_1, L_2, \ldots , L_{2^k}$ are all turned on. Then for the $2^k+1$th state only $L_{2^k}$ and $L_{2^k+1}$ are on.
However, note that at this point, because the setup is symmetric, $L_{2^k}$ and $L_{2^k+1}$ always will have the same state. Thus, they act just like if we had two sets of $2^k$ lights paired up side by side. By the induction step, we know that all the lights will turn on at the $2^k+2^k=2^{k+1}$ state, completing the induction.

------
b) I claim for all $n=2^x+1$ for $x\in\mathbb{N}$, the lamps will never all turn off.

Proof: by the proof of part (a) at the $2^k$th state lamps $L_1, L_2, \ldots , L_{2^k}$ are all turned on, while $L_{2^k+1}$ stays off the entire time. Thus at the $2^k+1$th state only $L_{2^k}$ and $L_{2^k+1}$ are on. However, this is exactly the same as the 2nd state where $L_1$ and $L_2$ are turned on, except mirror imaged; thus, this cycles back and forth, and the lights never all turn off at the same time. $\Box$
[/hide]

Maybe it will sound stupid :blush: , but I don't understand the problem, can anybody explain what happens to leftmost or rightmost lamp(with several examples)? For example, what happens to 1,0,0 after one second?(1 is on position, and 0 is off position) it becomes 1,1,0, or 0,1,0 or 0,1,1? Thank you.

Does anyone know if all lamps turn off iff $n=2^k$? I think it's true but I'm unsure.

a) For $n=2$ we can turn it all off. Now note that if for some $n$ we can turn them all off we will turn them off for $2n$. We use induction. Let lamp be $1$ if it is turned on and $0$ otherwise. After some time we will have $n$ ones followed by $n$ zeroes. In next move we have $n-1$ zeroes then $2$ ones and then $n-1$ zeroes again. Now second $n$ lamps act the same as the first $n$ lamps until that moment, and first $n$ lamps act the same by simmetry (from right to left). So $n$-th and $n+1$-th lamps will always be in the same state so they can basically ignore each other. After some number of moves we wil get $2n$ ones and in the next move $2n$ zeroes so all lamps are turned off. Now we have proven that for $n=2^k$ all lamps will be turned off.
b) Take $n=3*2^k=2^{k+1}+2^k$. We will have $2^{k+1}$ ones at some moment followed by $2^k$ zeroes. Let this be state $l$. In the next move we will get $2^{k+1}-1$ zeroes then $2$ ones and then again $2^k-1$ zeroes. Now for some time, like in the part a) they will act simmetricaly until the moment when we get $2^k$ ones at the end which means by simmetry that they are followed by $2^k$ more ones which are followed by $2^k$ zeroes(all this from right to left). Note that this state of all the lamps is simmetrical to the state $l$ so it will repeat and the lamps will never be off.

I like it, nice one. And surprisingly I solved this one rather quickly - like 10 min - especially for a combinatorics problem.

As for the notation: $L_i \equiv T$ or $L_i \equiv F$ means $L_i$ is on or $L_i$ is off. Furthermore $(\dots) \rightarrow (\dots)$ denotes the change of the states in a second.
(a) Choose $n=2^k$. We want to proceed by induction.
[b]Base step:[/b] Note $(L_1,L_2) \equiv (T,F) \rightarrow (T,T) \rightarrow (F,F)$.
[b]Inductive hypotesis:[/b] For $(L_1,L_2,\dots,L_{2^k})$ satisfy the following conditions:
(i) There is some time, when $L_{2^k} \equiv T$.
(ii) The first time, when $L_{2^k} \equiv T$ happens, we also have $(L_1,L_2,\dots,L_{2^k}) \equiv (T,T,\dots,T)$.
(iii) The next step is $(L_1,L_2,\dots,L_{2^k}) \equiv (F,F,\dots,F)$. That's also the first time, when that state is achieved.
[b]Induction step:[/b] Look at $(L_1,L_2,\dots,L_{2^k+2^k})$. Before $L_{2^k} \equiv T$, it'll be an $F$, and so will be $L_{2^k+1},L_{2^k+2},\dots,L_{2^{k+1}}$, as $(L_{2^k},\dots,L_{2^{k+1}})$ stays constant for that period of time. The first time, when $L_{2^k} \equiv T$ happens, we have \[ (L_1,\dots,L_{2^{k+1}})  \equiv (T,T,\dots,T,F,F,\dots,F) \rightarrow (F,F,\dots,F,T,T,F,F,\dots,F) \] with $2 \cdot (2^k-1)$ times state $F$. The tuple above is symmetric about the symmetry axis and thus it'll stay symmetric about that axis. The right side of the symmetry axis contains a $2^k$-tuple $(T,F,F,\dots,F)$. By inductive hypotesis, this will hit $(...,T)$ sometime. And and that time, it'll hit $(T,T,\dots,T)$. So $(L_1,L_2,\dots,L_{2^{k+1}})$ will hit $(T,T,\dots,T)$ for the first time, when $L_{2^{k+1}}$ hits $T$ the first time. The next step is $(F,F,\dots,F)$ and obviously before that, this state has never been achieved due to the inductive hypotesis. Done. $\hfill \square$
(b) Choose $n=2^k+1$. Note \[ (L_1,L_2,\dots,L_{2^k+1}) \equiv (T,F,F,\dots,F) \rightarrow (T,T,F,F,\dots,F) \rightarrow \dots \rightarrow (T,T,\dots,T,F) \rightarrow (F,F,\dots,F,T,T) \] due to the things proven in (a). But that's symmetric to $(T,T,F,F,\dots,F)$. So basically, this one is periodic and due to (a), it'll has never reached $(F,F,\dots,F)$ in between. $\hfill \square$

İt is also true that the number of lamps that are on will always be the power of 2.So taking $n $ not power of 2 $\implies $ b is done.

And also in k th step there will be at most k lamps that this operation has influence on it.
So by induction this problem is destroyed.

İt seems right but İ cannot prove that at every step the number of lamps that are on will be the power of 2.Can anyone help me to prove this?

This is basically a problem similar to CANADA 1994.

Notice that this construction is basically the right side of Pascal's triangle where odd means the light is on (We know everything down the center line is even by symmetry) until the lights "reach" the right side. It's clear that after the nth second, the rightmost light that is turned on is the n+1th light, assuming that n+1 is less than the number of lights.

a) Consider $2^k+1$ lights to reach a position where every other light is turned on after $2^k-1$ seconds, since we know that $2^k-1$ is all ones in binary, so by Lucas's theorem, all numbers in this row of Pascal's triangle are odd. Then, on the next second, all lights are clearly turned off.

b) Consider $2^k+2$ lights to reach a position where only the second to last light is turned on after $2^k$ seconds. Once again, by Lucas's theorem, we can confirm only one light will be on, which is the $2^k+1$ th one. Then, we can see by symmetry this is identical to the position after 1 second, and at no point in between were all the lights off (since there is no row of Pascal's triangle with all zeroes), so this process will repeat indefinitely with always at least one lamp on.

[hide=Solution][quote=ISL 2006 C1]We have $ n \geq 2$ lamps $ L_{1}, . . . ,L_{n}$ in a row, each of them being either on or off. Every second we simultaneously modify the state of each lamp as follows: if the lamp $ L_{i}$ and its neighbours (only one neighbour for $ i \equal{} 1$ or $ i \equal{} n$, two neighbours for other $ i$) are in the same state, then $ L_{i}$ is switched off; – otherwise, $ L_{i}$ is switched on.
Initially all the lamps are off except the leftmost one which is on.

$ (a)$ Prove that there are infinitely many integers $ n$ for which all the lamps will eventually be off.
$ (b)$ Prove that there are infinitely many integers $ n$ for which the lamps will never be all off.[/quote]
[b][color=#000]Solution:[/color][/b] For part [b](a)[/b], we show that $n=2^k$ works, $k \geq 1$ by induction on $k$. Establishing the base case $k=1$ is easy. We assume that for some $k=r$, it holds that $n=2^r$ lamps work  and when the lamp $L_{2^r}$ is turned on the first time, all the other lamps are switched on too (easy to prove for $k=1$). Suppose, it takes $x$ modifications to reach the 'all lamps switched off' state for $2^r$ lamps, then after the ($x-1$)th modification, all $2^r$ lamps are switched on. For $2^{r+1}$ lamps, after $x-1$ modifications, $L_1,L_2$ $\ldots$ $L_{2^r}$ are turned on. Note, Lamps $L_{2^r+1}$, $L_{2^r+2}$ $\ldots$ $L_{2^{(r+1)}}$ haven't yet been turned on, because that requires $L_{2^r}$ to be turned on (but the lamp $L_{2^r}$ gets turned on for the first time after $x-1$ modifications). So after $x$ modifications, $L_{2^r}$, $L_{2^r+1}$ are switched on and all others are switched off. Now, divide the lamps into two groups, namely: from $L_1$ to $L_{2^r}$ and lamps from $L_{2^r+1}$ to $L_{2^{(r+1)}}$. Notice after more $x-1$ modifications, both the groups will have all lamps turned on (Induction hypothesis). Hence in the next step all $2^{(r+1)}$ lamps are switched off.

For part [b](b)[/b], we show that $n=2^k+1$ works, for $k \geq 1$. From part (a) construction, at some point of time, all lamps, except the lamp$L_{2^k+1}$, will be turned on and in the next step, only $L_{2^k}, L_{2^k+1}$ are switched on. Notice that this is equivalent to the configuration right after the first modification and hence the process keeps cycling, never hitting on the the configuration where all lamps are turned off. $\qquad \blacksquare$[/hide]

[hide=Solution]For part a, I claim that if $n=2^k$, then all the lamps will eventually be off. We check the $n=2$ case separately, and we induct on $k$ for $k \geq 2$. In what follows, let $1$ represent an “on” lamp and $0$ represent an “off” lamp. If $k=2$, then the lamps go from 1000 to 1100 to 0110 to 1111 to 0000.

For the inductive step, assume $2^k$ lamps will eventually be all off for $k \geq 2$. Note that $2^{k+1}$ lamps is just two copies of $2^k$ lamps back to back, so the initial moves will be the exact same as $2^k$ lamps on the left half and leave all the right lamps off. Eventually, all $2^k$ lamps on the left side will be on, and the others will be off.

The next move will leave the middle two lamps on and the rest off. The middle $2^k$ lamps give a configuration found in the sequence of moves turning $2^k$ lamps all off, so eventually all these lamps will be on. Apply another move and we get two copies of that configuration, leading to all lamps off.

For part b, take $n=2^k+1$. The first move puts the left two lamps on, and the rest off. All $2^k$ lamps on the left will eventually be on, with the last lamp off. Another move gives the first move reflected, so we will eventually get all $2^k$ lamps on the right on, and the rest off. Another move repeats the first move, leading to an infinite cycle. [/hide]

This one was simple!
First of all, let $0$ and $1$ denote the switched off and switched on states of a lamp respectively. From now on, we will denote the lamps with only $0$s and $1$s.

[b](a)[/b] We will show that if $n=2^k$ for $k\geq1$, then eventually all lamps will be switched off, that is, all the bits will become $0$. We proceed by induction. For $n=2^1=2$, the process is just $(10)\rightarrow (11)\rightarrow (00)$. Now suppose for some $k\geq 1$, an arrangement of $n=2^k$ bits will eventually become all $0$s in the process. We further assume that the in the second last step of the process, the bits will be all $1$s and that this will be the only time that the last bit became $1$. Now for $n=2^{k+1}$, imagine a partition between the first $2^k$ and the last $2^k$ bits. We can see that till the $2^k$th bit does not become $1$, the bits to the right of the $2^k$th bit will remain $0$. Now for the first $2^k$ bits, we use the induction hypothesis, and consider the step where all of the first $2^k$ bits become $1$. The next step results in $(111\dots111|000\dots000)\rightarrow (000\dots 001|100\dots000)$ where $|$ represents the partition. Now note that the arrangement has become symmetric and for the rest of the process, it will remain so, since the process when started from the leftmost bit, is a reflection of the process when started from the rightmost bit. Also since the $2^k$th and the $2^{k+1}$th bits will always be identical, so their modification will only depend on the neighboring bit to their other side of the partition. So we can separately consider the process on the two sides of the partition, since the "one-neighbor condition" for the $2^{k}$th and $2^{k+1}$th bits will be fulfilled. Then each side of the partition will look exactly as if we started with two sets of $2^k$ bits with the given problem condition. By our hypothesis, we know that the process would eventually lead to all $0$s, and the hypothesis also ensures that only in the step before all the bits become $0$, will the last bit be $1$. Hence we are done. $\blacksquare$

[b](b)[/b] We shall show that for $n=2^k+1$ where $k\geq 1$, the lamps will never be all switched off, that is, the bits will never be all $0$s. Consider an arrangement of the $2^k+1$ bits. We note that the last bit will remain $0$ until the $2^k$th bit becomes $1$. By part [b](a)[/b], we know that this occurs for the first time when the first $2^k$ bits are all $1$s. Then in the next step we get $(111\dots1110)\rightarrow (000\dots0011)$. This arrangement is exactly the reflection of the arrangement after the first step, that is $(100\dots000)\rightarrow(110\dots000)$. Since the process works exactly similarly on reflections, so we know that the arrangement of bits will keep repeating and so we will never reach all $0$s. $\blacksquare$

Why does everyone say this was simple :(

[b](a)[/b] We claim that $2^n$ works for all $n\ge 1$. We start with a lemma before we actually prove this. Of course, let $0$ denote off and $1$ denote on.

[b][color=#f00]Lemma:[/color][/b] Start with $2^{k+1}$ lamps such that all lamps are off except for $2^k$ lamps right in the center. For example, when $k=2$, this would look like
\[ 00111100\]
I claim that after a while, all lamps will be on (of course after this, all lamps will be off). And between the start and when all lamps are on, the end lamps will only turn on on the final move. Using the example above,
\[ 00111100\longrightarrow 01100110\longrightarrow 11111111\]
Indeed, note that the end lamps only turn on on the final move.

[i]Proof.[/i]  Strong induct on $k$. The base case $k=1$ is trivial ($0110\longrightarrow 1111$).

Now, suppose that the claim is true for $k=1,\ldots,\ell-1$. Consider $2^{\ell}$ lamps in the aforementioned setup. Define the $p$-block to be the block of $p$ lamps that is symmetric about the string of lamps, e.g. we start with the $2^{\ell-1}$-block all on. Performing one move, we basically end up with two pairs of adjacent lamps spaced one-quarter and three-quarters the way along the string. For example, when $k=2$, we have
\[00111100\longrightarrow 01100110\]
Thus, by cutting the string right in the middle, we have two identical strings of length $2^{\ell-1}$.

So, suppose we have a string of length $2^{\ell-1}$ with a $2$-block all on and everything else off. Apply the $k=1$ hypothesis on the $4$-block, so we have a $4$-block all on. Also, the condition that the end lamps are only turned on at the end means that all other lamps are off. Then, apply the $k=2$ hypothesis on the $8$-block, so we have an $8$-block all on and all other lamps are off. Keep going until all lamps are on.

So, our $2^{\ell}$ lamps are now all on, completing the induction (note that the two strings don't interfere with each other from the last condition in our claim). Also, this last condition is fulfilled in the $k=\ell$ case because the end lamps are last to turn on from the inductive hypothesis, and they turn on at the same time since the two strings are identical. $\blacksquare$

Now, we show that $2^n$ lamps always works. Again, we'll only show that we can turn all of them on. Similar to before, we claim the extra condition that the right-most lamp will only turn on at the end.

Induct on $n$. The base case $n=1$ is trivial. Suppose that the statement is true for $n=m-1$. Consider $2^m$ lamps with only the left-most one on. Note that we can ignore the second half of the string and only look at the first $2^{m-1}$ lamps. Applying the inductive hypothesis, these are eventually all on. The condition that the right-most one only turns on at the end ensures that the moves here don't interfere with the next $2^{m-1}$ lamps. So now, we have the first $2^{m-1}$ lamps all on and the next $2^{m-1}$ lamps all off. Applying another move, we end up with a $2$-block on and everything else off.

Now, similar to how we proved the lemma above, just apply the lemma to the $4$-block, then the $8$-block, and so on until everything is on. This completes the induction. $\square$

[b]b)[/b] I claim that $2^{n}+1$ works for all $n\ge 1$. Indeed, from part a), we can ignore the last lamp, and eventually the other $2^n$ lamps are all on (the condition that the right-most lamp only turns on at the end means it doesn't interfere with our last lamp). So, if $n=3$, our string would currently look like
\[111111110\]
Applying one move, we get
\[ 111111110 \longrightarrow 000000011\]
Now, we're basically performing moves but with the string reversed (since after the first move we will always have two $1$s followed by all $0$s). So, by part a), we'll eventually get
\[ 000000011\longrightarrow\cdots\longrightarrow 011111111\longrightarrow 110000000\]
And now it just cycles, so we'll never get all the lamps to be on, and thus they will never be all off! $\square$

[b] [color = red] Claim: [/color] [/b] If $n = 2^k$ for some $k \in \mathbb{Z}_{> 0}$, all the lamps will eventually be on.

[i]Proof:[/i] In what follows, the \textit{middle $2\ell$ lamps} are the lamps $2^k - \ell + 1, 2^k - \ell + 2, \ldots, 2^k + \ell$. We go by induction on $k$, with base case $k = 1$ trivial. Suppose the result is true for $n = 2^k$. We now check that it holds for $2^{k + 1}$ as well. By induction, after some number of moves, the first $2^k$ lamps will all be on. After this, the following move will turn all lamps off except the middle $2$. The move after this will turn all lamps off except the middle $4$. After two moves from here, the middle $8$ lamps will be on, while the remaining lamps will be on. Continuing similarly, eventually the middle $2^{k + 1}$ lamps will all be on, implying that all the lamps will be on.

Now, for part (a), take $n = 2^k$. By the claim, at some stage all lamps will be on. The move following this will turn all lamps off.

For part (b), take $n = 2^k + 1$. After a single move, the first two lamps will be on, while all other lamps will be off. By the claim, at some stage, the first $2^k$ lamps will all be on, while the $2^k + 1$'st lamp will be off. After a single move from this stage, all but the last two lamps will be off. This is symmetric to the position that was there after the first move; as such, by repeating the argument, it follows that eventually all but the first two lamps will be off. As a result, the state of the lamps cycles, meaning that there will never be a time when all lamps are off. $\Box$

Instead I'll just give examples which easily generalize. Denote $1$ as on and $0$ as off.

a) Take $n=2^k$.
[hide=n=2]
$1$ $0$
$1$ $1$
$0$ $0$[/hide]

[hide=n=4]
$1\text{ }0\text{ }0\text{ }0$
$1\text{ }1\text{ }0\text{ }0$
$0\text{ }1\text{ }1\text{ }0$
$1\text{ }1\text{ }1\text{ }1$
$0\text{ }0\text{ }0\text{ }0$ [/hide]

[hide=n=8]
$1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$
$1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$
$0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$
$1\text{ }1\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0$
$0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0$
$0\text{ }0\text{ }1\text{ }1\text{ }1\text{ }1\text{ }0\text{ }0$
$0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0$
$1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1$
$0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$

Notice how [by induction] that in the 4th line we have $4$ $1$'s and $4$ $0$'s. Also, after that we get two middle $1$'s, and then $4$ middle $1$'s, and then we get the pattern $0\text{ }1\text{ }1\text{ }0$ -which finishes the problem. Well, we still have to see more; let's go on to $16$.
[/hide]

[hide=n=16]
We know that at the $8$th move that it will get to [that], we'll just start there.
$1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$
$0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$
$0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$
$0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$
$0\text{ }0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0$
Notice how, [again by induction] that we have $8$ middle $1$'s now. In the next row, we have
$0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0$
but wait! This is the 5th row of $n=8$ -just twice! And it's clear how it plays out from here:
$0\text{ }0\text{ }1\text{ }1\text{ }1\text{ }1\text{ }0\text{ }0\text{ }0\text{ }0\text{ }1\text{ }1\text{ }1\text{ }1\text{ }0\text{ }0$
$0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0\text{ }0\text{ }1\text{ }1\text{ }0$
$1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1\text{ }1$
$0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0\text{ }0$.
This is just $n=8$ playing out again, but twice in the same string, and [by induction] we are done.
[/hide]

b) Not really that instructive but let's do it anyway; take $n=2^k+1$.

[hide=n=3]
$1\text{ }0\text{ }0$
$1\text{ }1\text{ }0$
$0\text{ }0\text{ }1$
$1\text{ }1\text{ }0$
$0\text{ }0\text{ }1$
$1\text{ }1\text{ }0$
and it just repeats like that forever, never achieving $0\text{ }0\text{ }0$.[/hide]

[hide=n=5]
$1\text{ }0\text{ }0\text{ }0\text{ }0$
$1\text{ }1\text{ }0\text{ }0\text{ }0$
$0\text{ }1\text{ }1\text{ }0\text{ }0$
$1\text{ }1\text{ }1\text{ }1\text{ }0$
$0\text{ }0\text{ }0\text{ }0\text{ }1$
$1\text{ }1\text{ }1\text{ }1\text{ }0$
$\dots$. Actually, since we already know for powers of two that it gets to "$1\text{ }1\text{ }1\text{ } \dots 1$", it gets to "$1\text{ }1\text{ }\dots1\text{ }0$" for $n=2^k+1$ and there gives the contradiction because it will keep repeating forever.[/hide]

[hide=Note]Well, for $n=2^k+1$ we still technically had to prove that it never [i]achieved[/i] $0\text{ }0\text{ } \dots 0$ but we know this is true as in $n=2^k$ we only get $0\text{ }0\text{ } \dots 0$ after $1\text{ }1\text{ } \dots 1$.[/hide]

[hide=btw]this is a good beginners problem because it really only requires logic and trying things. This is also an excerpt from my (unfinished) book :|[/hide]

Solved with [b]Th3Numb3rThr33[/b].

The constructions for (a) and (b) are \(n=2^k\) and \(n=2^k+1\) respectively.

[color=blue][b]Solution (a)[/b][/color] We will verify by induction on \(k\) the following hypothesis:
"For \(n=2^k\), \(L_n\) will eventually turn on, and the first time it turns on, all the lamps will be on."

The base case, \(n=2\), is easily verified: \(10\to11\to00\). Then, if the hypothesis holds for \(k-1\), in the case of \(n=2^k\) lamps, the state will eventually be \[\underbrace{11\cdots1}_{2^{k-1}}\underbrace{00\cdots0}_{2^{k-1}}\to\underbrace{0\cdots0}_{2^{k-1}-1}11\underbrace{0\cdots0}_{2^{k-1}-1}.\] Then the lamps are symmetric around the center, so applying the inductive hypothesis again, the first time \(L_n\) is on, all the lamps are on.

To finish, note that \[\underbrace{11\cdots1}_{2^k}\to\underbrace{00\cdots0}_{2^k},\] as needed.

[color=blue][b]Solution (b)[/b][/color] By the hypothesis in (a), the state of the lamps for \(n=2^k+1\) will eventually be \[\underbrace{11\cdots1}_{2^k}0\to\underbrace{0\cdots0}_{2^k-1}11.\] However, the state \(0\cdots011\) is merely a reflection of a state we've seen earlier: \(110\cdots0\), so the states of the lamps are periodic and never all off.

[hide = a more elaborate and detailed solution]
For (a), we claim that for all powers of 2, all the lamps will eventually be turned off. We proceed by induction to show this.\\
Let $O$ denote a lamp that is on, and let $X$ denote a lamp that is off. For the case $n = 2$, we have
$$OX\to OO\to XX$$ \\
Now assume that for some positive integer $k$, $n = 2^k$ works, and it takes exactly $2^{k}$ seconds to turn off all the lamps. Then for $n = 2^{k+1}$, evidently after the first $2^{k}-1$ seconds (in the $2^k$ case, the last move is turn all off), we would have $$\underbrace{O\cdots O}_{2^k}\underbrace{X\cdots X}_{2^k}$$ since the latter $2^k$ off lamsp doesn't change during those seconds. Then for the $2^{k}+1$ second, it changes to $$\underbrace{X\cdots X}_{2^{k}-1}OO\underbrace{X\cdots X}_{2^k-1}$$\\
Now we claim that for the rest of the time, the state of the first $2^k$ lamps would be symmetric to the state of the last $2^k$ lamps. Notice the following four cases of the middle $4$ lamps $$XOOX\to ?OO?\;,\;OOOO\to ?XX?\;,\;XXXX\to ?XX?\;,\;OXXO\to ?OO?$$ which are the same changes that would happen to $L_1$ for the $2^k$ lamps case. Thus after another $2^k$ moves, we would be done with all off, where in total, it takes $2^k-1+1+2^k = 2^{k+1}$ seconds to turn all the $2^{k+1}$ lamps off. Therefore we complete our induction and we are done since there are infinitely many powers of 2 in the set of integers.\\
For $(b)$ we claim that for all positive integers of the form $2^k+1$ for some positive integer $k$, the lamps can never be all off. Firstly notice that by a direct result from the proof for part $(a)$, we get that for a fixed integer $k$, after $2^k-1$ seconds, we would arrive with the stage of $$\underbrace{O\cdots O}_{2^k}X$$ and evidently, the next move would be, $$\underbrace{O\cdots O}_{2^k}X\to \underbrace{X\cdots X}_{2^k-1}OO$$ Now notice that this is actually the exact reverse of the stage at the first second, namely $$OO\underbrace{X\cdots X}_{2^k-1}$$
Thus, it follows that after some more seconds, we would arrive with $$X\underbrace{O\cdots O}_{2^k}\to OO\underbrace{X\cdots X}_{2^k-1}$$ Now we have a loop of stages. Also since there won't be a stage during the first $2^k$ seconds where the lamps are all on or off, there won't be any afterwards. Therefore since there are infinitely many positive integers of the form $2^k+1$ for some positive integer $k$, we are done.[/hide]

Define the first state to be the state where only the leftmost one is on, and let the $n$th state be the state of the lamps one second later when the given operation has been done. Denote $0$ for an off lamp and $1$ for an on lamp. The main claim is the following:

[b][color=#f00]Claim:[/color][/b] Let $a$ be a nonnegative integer. If $n\ge 2^a$, then the $2^a$th state will be $$\underbrace{11\ldots1}_{2^a}\underbrace{00\ldots0}_{n-2^a}.$$
[i]Proof.[/i] We proceed by induction. The base cases $a=0,1$ are trivial.

Suppose that the statement is true for $a=k$. We will attempt to prove the statement for $a=k+1$. By the induction hypothesis, the $2^k$th state will look like $$\underbrace{11\ldots1}_{2^k}\underbrace{00\ldots0}_{n-2^k}.$$ Then the $2^k+1$th state will look like $$\underbrace{00\ldots0}_{2^k-1}11\underbrace{00\ldots0}_{n-2^k-1}.$$ Imagine placing a divider between the two ones. Notice that the ones are symmetric about this divider, so the numbers on the left and right of this divider are equal.

This means that for the transition between the $2^k+1$ to $2^k+2$th state, it will be the same as if there were two separate sets of the lamps, as the outcome of a lamp next to the divider only depends on the state of that lamp and the neighboring lamp on the same side of the divider. However, this implies that the $2^k+2$th state is symmetric as well. Continuing this, we get that every state up to the $2^{k+1}$th state is symmetric (after that, it may not be symmetric anymore because the size of the portion to the left of the divider is $2^k$).

Therefore, until the $2^{k+1}+1$th state, the lamps will behave like there were two independent sets of lamps divided by the divider. By the induction hypothesis, in $2^k-1$ transitions, we will get from a single $1$ on the side to the first $2^k$ elements being $1$s in $2^k-1$ moves, so that during the $(2^k+1)+(2^k-1)=2^{k+1}$th state, both sides of the divider will have $2^k$ ones closest to the divider and zeros elsewhere, implying that the first $2^{k+1}$ terms will all be ones. This finishes the induction. $\blacksquare$

We are in a position to do both parts now.
[b][color=#f00]Part A:[/color][/b] We claim that $n=2^i$ works for any nonnegative integer $i$. By the claim, the $2^i$th state will be all ones, then the next state will be all zeros.

[b][color=#f00]Part B:[/color][/b] We claim that $n=2^i+1$ works for any positive integer $i$. By the claim the $2^i$th state will be $$\underbrace{11\ldots1}_{2^a}0.$$ It is clear that no state before this had all zeros, because then every state after that would have been all zeroes. The next state will then be $$\underbrace{00\ldots0}_{2^a-1}11.$$ However, this is just a mirror image of the $2$nd state, putting us essentially in the same position as in the second state. Therefore we will never reach all zeroes.

I still wonder if we can prove that the game ends [b]iff[/b] n is a power of 2... I've used my computer to check all numbers between $[1, 58]$ and the claim seems to be correct.

Not so good writeup ahead.
Denote the on lamps by $1$ and off lamps by $0$, also denote the next step of modification by $``\to "$.
[b][color=#f00]Lemma: [/color][/b] We will eventually reach the arrangement $$\underbrace{111\cdots \cdots111}_{2^a} \underbrace{000\cdots \cdots 000}_{n-2^a}$$
[hide=Proof]
Begin by strong inducting on $a$. Base case $a=1$ is easy to verify, assume it's true for $a \le k$.
$$100\cdots \cdots 000 \to 110\cdots \cdots 000 \to \cdots $$
$$\to \underbrace{111\cdots \cdots111}_{2^k} \underbrace{000\cdots \cdots 000}_{n-2^k} \quad \text{(by assumption)}$$
$$\to \underbrace{000 \cdots \cdots 001}_{2^k} \underbrace{100\cdots \cdots 000}_{n-2^k}$$
$$= \underbrace{\boxed{000 \cdots \cdots 00 \color{red}1}}_{2^k} \underbrace{\boxed{{\color{red}{1}}00\cdots \cdots 000}}_{2^k} \underbrace{00\cdots \cdots 00}_{n- 2\cdot 2^{k}}$$
Notice that the lamps in the two blocks are symmetric about the "centrally placed" $({\color{red}11})$ lamps. Now consider only the block $\displaystyle{ \underbrace{\boxed{000 \cdots \cdots 00 \color{red}1}}_{2^k}}$ By our inductive hypothesis we can reach $ \underbrace{\boxed{111 \cdots \cdots 11 \color{red}1}}_{2^k}$ (because the ordering of placing the first on lamp on leftmost / rightmost place doesn't matter), and because of the symmetry $\displaystyle{\underbrace{\boxed{{\color{red}{1}}00\cdots \cdots 000}}_{2^k} \to \underbrace{\boxed{{\color{red}{1}}11\cdots \cdots 111}}_{2^k}}$. (In each step as the left block "changes", the right "changes" symmetrically thus when finally the left block contains all on lamps, the right also contains all on lamps as well.)
Thus we arrive at the arrangement
$$\underbrace{111\cdots \cdots111}_{2^{k+1}} \underbrace{000\cdots \cdots 000}_{n-2^{k+1}}$$
[/hide]
Now for part $(a)$ choose $n=2^x$. By the lemma we will arrive at
$$\underbrace{111\cdots \cdots111}_{2^{x-1}} \underbrace{000\cdots \cdots 000}_{2^x-2^{x-1}} \to \cdots$$
$$\to \underbrace{111\cdots \cdots111}_{2^x} \underbrace{000\cdots \cdots 000}_{2^x -2^x} = 111\cdots \cdots 111$$
$$\to 000\cdots \cdots 000$$
Thus all the lamps can be turned off.
For part $(b)$ choose $n=2^x + 1$. By the lemma we will arrive at
$$\underbrace{111\cdots \cdots111}_{2^{x}} \underbrace{000\cdots \cdots 000}_{2^x + 1 -2^{x}}$$
$$= \underbrace{111\cdots \cdots111}_{2^{x}} 0$$
$$\to 000\cdots \cdots 0011$$
Which is basically the arrangement in the second step but with a different ordering, this will keep looping and all the lamps will never get turned off.

My explanation sucks.

(a) Let $n=2^i$ for positive integer $i$. We claim that all lamps eventually turns off. We prove this using a very simple induction argument on $i:$

$n=2$ obviously works: let $1$ be on and $0$ be off. $10\to 11\to 00.$

Suppose we have $10000000\dots00$ (with $2^i$ lamps) turning into $111\dots1000\dots0$ (with $2^{i-1}$ on and $2^{i-1}$ off.) Now, this becomes $00\dots0110\dots00$ and from now on, the lamps will be symmetric, so we can split this into two sections of lamps with the same starting position as the beginning. The two lamps in the center do not matter since when determining their status, only the lamps closer to the edges of the line of lamps matter. By induction, this will eventually turn into all $1$ and then it becomes all $0.$

(b) Now, $n=2^i+1$ won't work because $11\dots110$ (with $2^{i}+1$ lamps) will become $00\dots0011$ and then this will become $011\dots111$ and the problem just cycles infinitely, which shows that they can ever all by off, since if it does all become off then it stays that way.

Denote a lamp switched on by $1$, and a lamp switched off by $0$. Also, the arrow $\mapsto$ simply denotes the passage of a second, when a configuration of lamps changes.
$(\text a)$ Here, $n=2^k$ for $k\in\mathbb N$ works, which we will show.

[b]Claim:[/b] for $n=2^k$, the first instance of the last lamp being switched on will happen, and at that time, all of the lamps will be switched on.
Induct on $k$. The base case is the configuration of lamps $10\mapsto11$.
If the claim holds for $2^k$, let $n=2^{k+1}$, then we eventually reach:
$$\underbrace{11\ldots11}_{2^k\text{ times}}\underbrace{00\ldots00}_{2^k\text{ times}}\mapsto\underbrace{00\ldots00}_{2^k-1\text{ times}}11\underbrace{00\ldots00}_{2^k-1\text{ times}}.$$
After this point, the center two lamps will always have the same state, by symmetry. Now we use the induction hypothesis on the right half of the lamps to finish. Note that this process always takes at least two steps.

Then we will have:
$$\underbrace{11\ldots11}_{n\text{ times}}\mapsto\underbrace{00\ldots00}_{n\text{ times}}.$$

$(\text b)$ Here, $n=2^k+1$ for $k\in\mathbb N$ works, which we will show. Due to the claim from part $(\text a)$, we will eventually end up with:
$$\underbrace{11\ldots11}_{2^k\text{ times}}0\mapsto\underbrace{00\ldots00}_{2^k-1\text{ times}}11.$$
During this, we pass through the state $11\underbrace{00\ldots00}_{2^k-2\text{ times}}$ since $1\underbrace{00\ldots00}_{2^k-1\text{ times}}\mapsto11\underbrace{00\ldots00}_{2^k-2\text{ times}}$. Now notice that the claim is equivalent to:
[quote][b]Claim:[/b] starting from the lamp configuration $11\underbrace{00\ldots00}_{2^k-2\text{ times}}$, the first instance of the last lamp being switched on will happen, and at that time, all of the lamps will be switched on.[/quote]
since $1\underbrace{00\ldots00}_{2^k-1\text{ times}}\mapsto11\underbrace{00\ldots00}_{2^k-2\text{ times}}$. Then, reversing this lamp configuration, we eventually obtain:
$$0\underbrace{11\ldots11}_{2^k-2\text{ times}}\mapsto11\underbrace{00\ldots00}_{2^k-1\text{ times}},$$
which ends up in a loop. Since no all-zero configuration occurs in this loop, we’re done.

Call the time at the start when all lamps are off $T_1$. Then, call the second after that $T_2$ and so on.

Lemma: For $n=2^k$, at $T_{2^k}$, all lamps will be on. Furthermore, $L_{2^k}$ will not be on until $T_{2^k}$.

Proof: We will prove this by induction. The base case of $k=0$ is obvious. Also, since lamps $L_m$ can't be on until $T_m$, $L_{2^k}$ can't be on until $T_{2^k}$.

At $T_{2^{k-1}}$, the lamps $L_1, L_2,\ldots, L_{2^{k-1}}$ are on. At $T_{2^{k-1}+1}$, only lamps $L_{2^{k-1}}$ and $L_{2^{k-1}+1}$ are on. By symmetry, after this, $L_{2^{k-1}}$ and $L_{2^{k-1}+1}$ will be in the same state. So, they can't turn off because of each other. So, the lamps $L_1, L_2,\ldots L_{2^{k-1}}$ are equivalent to the $n=2^{k-1}$ case flipped, and the lamps $L_{2^{k-1}+1}, L_{2^{k-1}+2},\ldots, L_{2^k}$ are equivalent to the $n=2^{k-1}$ case. So, at $T_{2^k}$, all the lamps will be on.

[size=200][color=#f00]a[/color][/size]
Let $n=2^k$ for some positive integer $k$. Then, at $T_{2^k}$, all lamps will be on. So, at $T_{2^k+1}$, all lamps will be off.

[size=200][color=#00f]b[/color][/size]
Let $n=2^k+1$ for some positive integer $k$. Then, at $T_{2^k}$, all lamps except for $L_{2^k+1}$ will be on. So, at $T_{2^k+1}$, only $L_{2^k}$ and $L_{2^k+2}$ will be on. This is the mirror image of $T_2$, when only $L_1$ and $L_2$ are on. So, the process will continue infinitely.

I claim that for all positive integers $k$, taking $n=2^k$ works, and on the $n-1$th move, all the lamps will be on. Clearly this holds for $n=2$, so now we induct on $k$. Consider the case $n=2^{k+1}$. On the $2^k-1$th move, the first $2^k$ lamps will be on, by the inductive hypothesis (we don't need to worry about the tail having only one neighbour, since it's easy to show that the $i$th lamp first turns on during the $i-1$th move). Then on the $2^k$th move only the middle two lamps will be on. Then we can split the lamps in half and again by the inductive hypothesis it takes another $2^k-1$ moves for all lamps to be on.

Then take $n=2^k+1$. Clearly after $2^k$ moves, the last two lamps will be on. Then by symmetry the lamps will never be all off (this is equivalent to the problem after just one move). We are done. $\blacksquare$

I claim that for all $n=2^k$ where $k\in \mathbb{Z}^+$, until all lamps turn on, the last lamp will never be on, and that after all lamps turn on, then all lamps will turn off, proving that there are infinitely many integers $n$ satisfying part $(a)$. We will use induction. For simplicity, let $0$ represent an off lamp and $1$ represent an on lamp. Then, for $n=2^1$, the lamps go $10$ then $11$ then $00$, which satisfies our claim. Assume that for some $2^k$, our claim is satisfied. We will now prove that our claim is satisfied for $2^{k+1}$. We claim that there will eventually be a point when the first $2^k$ lamps are on and the last $2^k$ lamps are off. This is because the $2^k$th lamp is never on until the first $2^k$ lamps are on, so the $2^k+1$ lamp will always be next to $2$ off lamps, so it will stay off until after first $2^k$ lamps are on. $1$ second after this point, there will be $2^k-1$ off lamps followed by $2$ on lamps followed by $2^k-1$ off lamps. Because of symmetry, this is the same as having $2$ groups of the $2^k$ case. The last lamp will never be on until all lamps turn on because it is true for the $2^k$ case. This completes our induction. This proves part $(a)$. I claim that for all $n=2^k+1$ where $k\in \mathbb{Z}^+$ and $k\ge 69420$, the lamps will never be all off, proving part $(b)$. After the first second, we will have $2$ on lamps followed by $2^k-1$ off lamps. At some later point, we will have $2^k$ on lamps followed by $1$ off lamp. This is because, by the claim in part $(a)$, the $2^k$th lamp will never be on until the first $2^k$ lamps are on, so $2^k+1$ will also be off until after the first $2^k$ lamps turn on. $1$ second after this point, we will have $2^k-1$ off lamps followed by $2$ on lamps. This is simply what we got after the first second, but in reverse order. Therefore, by symmetry, at some later point, we will have $2$ on lamps followed by $2^k-1$ off lamps, finishing our loop so we can never have all $2^k+1$ lamps be off. This proves part $(b)$.

The first thing that happens will be $L_1$ and $L_2$ being switched on and all others being switched off. We will call this the [i]starting state[/i] for convenience. We first prove a lemma that will be used for both parts.

[b]Lemma.[/b] For all positive integers $k$, there will eventually be a state such that the first $2^k$ lamps are on and all the rest are off, given that we are starting from the starting state and there are at least $2^k$ lamps. Also, if $k>1$, this happens after the event for $k-1$ happens, and from the second after the $k-1$ event, $L_1$ and $L_{2^k}$ are first on when this event for $k$ occurs.
[b]Proof.[/b] We proceed by strong induction. Base case $k=1$ is trivial. Therefore, for the inductive step, assume that this is true for $1,2,\dots,k$. Then, we use the statement for $k$ and start from that state. The next thing that happens is that $L_{2^k}$ and $L_{2^k+1}$ are on, and all other lamps are off. Now, consider lamps $L_{2^{k-1}+1}$ to $L_{3\cdot2^{k-1}}$. This is precisely the position that happens one second after the $k-1$ case, and therefore the $k$ case happens again, meaning that there will eventually be a move such that all lamps in that range are on and all other ones are off. The next second, only lamps $L_{2^{k-1}}$, $L_{2^{k-1}+1}$, $L_{3\cdot2^{k-1}}$, and $L_{3\cdot2^{k-1}+1}$ are on. This is again precisely the second after the $k-1$ case, but repeated twice for lamps $L_1$ to $L_{2^k}$ and lamps $L_{2^k+1}$ to $L_{2^{k+1}}$. Therefore, eventually, all of those lamps are on. These two groups don't interact with each other because of our first on condition, and the first on condition clearly holds true here.

(a) Let $n=2^k$ for positive integers $k$. The second after the event for $k$ occurs, everything is off and clearly will stay off forever.
(b) Let $n=2^k+1$ for positive integers $k$. After the event for $k$ occurs, the next second, $L_{2^k}$ and $L_{2^k+1}$ are the only two lamps that are on. This is now the starting position but flipped, so by symmetry this clearly lasts forever.

a) $n=2^k$ works. We induct, with the base case being obvious. By the inductive hypothesis, the first $2^k$ turn on. Then only the middle 2 are on. We can think of this as two groups of $2^k$ going together, so the lamps will all turn on.
b) $n=2^k+1$ doesn't work. By part a), the first $2^k$ turn on, and then after, only the last two will be on. This repeats infinitely, and we are done.

Great, interesting problem! This problem suggests stuff like induction, and powers of 2 since it's easy to split them. Indeed, for part a) 2^k suffices and b) has 2^k+1. The key is to see that by induction (base case k=1 trivial) time=2^k seconds (from henceforth call it $T_i$) at $T_{2^{k-1}}$ all 2^{k-1} left lamps are on and the right ones are off.

First note that since lamps only can light up consecutively (as in if there are some consecutive lamps L_i,L_{i+1},...,L_{i+j} are off with L_{i-1} on, L_{i+1} cannot be lit until L_i is, and this spirals to the start meaning that no lamp can turn on until their partner to the left turns on, which each move taking one second) means that L_{2^k} cannot light up until at least T_{2^k}. Inductive step: at T_{2^{k-1}} the left half is lit up and the right half is off. Then T_{2^{k-1}+1} --> middle two are on. Now it's the same as inductive hypothesis occuring twice at the same time in both halves, meaning L_{2^{k-1}} and L_{2^{k-1}+1} will turn off and on at the same time (due to turning off will still turn off since they're the same state, and turning on will still turn on (since to turn on in the T_{2^{k-1}} subsection there would need to be a lamp of opposite state anyway). This means that all lamps are on at T_{2^k} (since T_{2^{k-1}+1} is considered as T_1 in either state). $\square$

Now, for part a, since T_{2^k} all lamps are on, the next second they're all off.
As for part b, since T_{2^k} all are on, T_{2^k+1} means only the right two most lamps are on. This is just the mirror image of T_2 when only the leftmost two lamps are on, meaning it will repeat into all left 2^k lamps with (by reflection) being on with 2^k+1th lamp being off, and infinitely repeat into that same situation again. $\blacksquare$

[b][color=#00f]Claim: [/color][/b]When $n$ is a power of $2$, the lamps will eventually all turn on (which also implies that they will all turn off).

Proof: Base case $n = 2$ is obvious. For the inductive step when $n = 2^{k+1}$, note that the the first $2^k$ lamps will be on. Then the lamps in the $2^k$ and $2^k+1$ position will be the only ones on after the next step. At this point the future arrangements will always be symmetric and thus the lamps at positions $2^k$ and $2^k+1$ are solely determined by one neighbor. Thus, the two halves $1\dots 2^k$ and $2^k+1\dots 2^{k+1}$ behave just like when $n = 2^k$, and so all lamps will be on at some point. $\square$

[b][color=#00f]Claim: [/color][/b] When $n = 2^k+1$ for $k \geq 1$, the process will continue forever.

Proof: From our first claim then we know the first $n-1$ lamps will be on. But then we must end up with the last two lamps being on in the next step. This state is equivalent to the second state of any process, where the first two lamps are on. Thus, the process cycles, and will never end. $\square$

This proves the problem. $\blacksquare$

a.
Claim: If $n=2^k, k>=1$, then the lamps will eventually all turn off.
Proof: We will prove this in 2 parts. The first part is that the the lamps will reach the state $1...2^k-1$ will be off, lamps $2^k, 2^k+1$ will be on, and lamps $2^k+2, 2^{k+1}$ will be off, and the second part is that the lamps will eventually all turn on (which means that they will all turn off) from the state mentioned above.
We will prove both parts by induction.
Base case: $n=2$, which goes $10, 11, 00$.
Inductive step for the first part: We see that when we get to the state $111...10...000$ where there are $2^k$ $1$s and $2^k$ $0$s, we will get to this state. Also, as we get that the first $2^k$ (as our base case) are on (and will be on for the first time, as a result of the induction), this is achievable, and therefore the first part is proven.
Inductive step for the second part: Once we reach the state $0...11...0$, then we can split the string up into 2 $10...0$s of size $2^k$ each, proving it for $2^{k+1}$
Therefore $a$ is true.
b.
Claim: If $n=2^k+1$, then it repeats forever.
Proof: By $a$, we know that $2^k$ will eventually be all on. Therefore, it will be in the state $1111.....110$ ($2^k$ $1$s), and then go to $00000...01$, which is just a reflection of the starting state, and therefore it cycles.
Therefore $b$ is true

Nice problem but I cannot prove this two statements :
1. The number of on lights at any second after 2 seconds is  even .
2. All the lights are eventually off iff $n$ is some power of $2$.
actually if $1$ is true we can easily discard the odds and i guess without using $1$ we can prove the $2$ nd one by inducting on $\lfloor log_2 n \rfloor$.I mean , let $2^k\leq n< 2^{k+1}$ then after some stage we will get the scenario $\underbrace {00..01}_{2^{k-1}}||\underbrace{10...0}_{n-2^{k-1}}$ . But then we have to prove that those two middle positions have always same state (then  the left part will not be affected by the right part sort of )
Could anybody help ?

For (a), I claim that $n=2^m$ works.

We proceed by using induction. Clearly the base case with $m=1$ works. We show that $n=2^{m+1}$ also works.

We also show in our induction that is takes exactly $2^m$ steps for the case $n=2^m$ for all entries to be $=0$.

Now for $n=2^{m+1}$, we get that after $2^m - 1$ moves, the first $2^m$ entries are all $1$. And after another move, we get that all entries except the $2^m$ and $2^{m} + 1$th ones are $0$. Now note that due to symmetry, the action of the next $2^m$ moves on the first $2^m$ entries and the action on the latter $2^m$ entries work like they are independent from each other which finish by using our induction hypothesis. :yoda:
-----
For (b), I claim that $n = 2^m + 1$ works. After hte first move, we have $100\ldots0$. From part (a), after $2^m-1$ moves, we have all the first $2^m$ entries are $=1$. Then after another move, we have the following configuration, $00\ldots 0011$ which is just the reverse of what we had after move $1$, and so, due to symmetry, we never reach a position where all the entries are $0$ and keep on alternating between the configurations we showed above and this goes on forever. :yoda:
-----

For brevity, we describe a current state of $n$ lamps as a $n$-element binary tuple with $0$ indicating an off lamp and $1$ otherwise.

[b](a)[/b] Instead of showing that all lamps will eventually be off, it is sufficient to show that eventually, all lamps will be on. We claim that $n = 2^k$ works for positive integers $k$. Clearly $k = 1$ works as we get $(1, 0) \to (1, 1)$, observe that the rightmost lamp never turns on until the last state.

Now assume that $n = 2^k$ for some positive integer $k$ works, and that the rightmost lamp will only turn on until the last state. For $n = 2^{k + 1}$, by our previous assumption, the first $2^k$ lamps will eventually turn all on, as before the state the lamp in the $2^k$ spot will never turn on, and thus will not interact with any lamps past $2^k$.

The next second, we achieve the state $(0, 0, \dots, 1, 1, \dots, 0, 0)$ where lamps $2^k$ and $2^{k + 1}$ are on. Each side (Lamps from $1$ to $2^k$, and lamps from $2^k + 1$ to $2^{k + 1}$) "mirrors" each other, and eventually each side will turn all on respectively, making all the lamps on. An important detail to notice is that the rightmost lamp only turns on in the final state, so that the induction can work. Our proof is complete.

[b](b)[/b] We claim that $n = 2^k + 1$ works for positive integers $k$, and all lamps will never turn off. By our last claim in (a), the first $2^k$ spots will eventually turn all on, at $(1, 1, 1, \dots, 1, 0)$. The next second, only the last two lamps are on, giving the state $(0, 0, 0, \dots, 1, 1)$. However, this is simply the reverse of the state achieved on the second state, hence we reached a loop where we never reach a state of all lamps being off. Our proof is complete.


integration
limit
real analysis
real analysis unsolved

Here are some problems from the GM 3/2000 and GM 1/2000:

1) Let (xn) be a real sequence such that lim(n-->oo) xn/n^2=1. Compute lim(n-->oo) (sum(k=1,n) k/(k^2+xn)).

2)Compute in two ways: lim(x-->oo) x(2x-(x^n+ax^(n-1)+1)^(1/n)-(x^n-ax^(n-1)+1)^(1/n)) for a real and n>=3.

And how did you manage to get that result?

cheers! :D

it's easy Lagrangia: take xn = n2.
Then \sum k=1n k / (k2+n2 ) = 1/n \sum k=1n ( k/n) / ( k2/n2 +1 ) which is the riemann sum on [0,1] for the standard division, for f(x)= x/(x2+1) and it's limit is exactly  \int 01 x/(x2+1) dx = 1/2 ln 2 :)

since xn is arbitrary, this must be the result. however it is not that trivial to prove this statement. :)

the first problem:
we all know that  \sum k/(k 2 +n 2 ) = 1/2 ln 2.

we expect that
\sum k/(k 2 +n 2 ) - \sum k/(k 2 +xn2 ) = 0

\sum k/(k 2 +n 2)-k/(k 2 +xn2 ) = \sum k (xn2-n 2)/(k 2 +n 2)(k 2 +xn2 ) = (xn2-n 2)\sum k/(k 2 +n 2)(k 2 +xn2 ).

since (xn2-n 2) \lim 0,
we need to prove that
\sum k/(k 2 +n 2)(k 2 +xn2 )
is bounded. This is easy.

\sum k/(k 2 +n 2)(k 2 +xn2 ) \leq \sum k/(k 2 +n 2)(k2) \leq \sum k/(k2)(k2) = \sum 1/k3
which obviously converges.

sorry, the proof above is not correct. the error occurs at:
x_n^2/n^2 \lim 1 doesn't mean xn^2-n^2 \lim 0....