geometry
rhombus
trigonometry
geometric transformation
rotation
symmetry
floor function

Hexagon $ABCDEF$ is divided into four rhombuses, $\mathcal{P, Q, R, S,}$ and $\mathcal{T,}$ as shown.  Rhombuses $\mathcal{P, Q, R,}$ and $\mathcal{S}$ are congruent, and each has area $\sqrt{2006}$.  Let $K$ be the area of rhombus $\mathcal{T}$.  Given that $K$ is a positive integer, find the number of possible values for $K$.

[asy]
size(150);defaultpen(linewidth(0.7)+fontsize(10));
draw(rotate(45)*polygon(4));
pair F=(1+sqrt(2))*dir(180), C=(1+sqrt(2))*dir(0), A=F+sqrt(2)*dir(45), E=F+sqrt(2)*dir(-45), B=C+sqrt(2)*dir(180-45), D=C+sqrt(2)*dir(45-180);
draw(F--(-1,0)^^C--(1,0)^^A--B--C--D--E--F--cycle);
pair point=origin;
label("$A$", A, dir(point--A));
label("$B$", B, dir(point--B));
label("$C$", C, dir(point--C));
label("$D$", D, dir(point--D));
label("$E$", E, dir(point--E));
label("$F$", F, dir(point--F));
label("$\mathcal{P}$", intersectionpoint( A--(-1,0), F--(0,1) ));
label("$\mathcal{S}$", intersectionpoint( E--(-1,0), F--(0,-1) ));
label("$\mathcal{R}$", intersectionpoint( D--(1,0), C--(0,-1) ));
label("$\mathcal{Q}$", intersectionpoint( B--(1,0), C--(0,1) ));
label("$\mathcal{T}$", point);
dot(A^^B^^C^^D^^E^^F);[/asy]

[hide]
Let $\theta$ be the non-obtuse interior angle of P, and $x$ be the side length of each rhombus.  Then one interior angle of T equals $180-2\theta$.  Since opposite angles of a rhombus are equal, we know that the area of S equals
$\sqrt{2006}=x^2\sin{\theta}$
and the area of T equals
$K=x^2\sin{(180-2\theta )}$
$=2x^2\sin{(90-\theta )}\cos{(90-\theta )}$
$=2x^2\cos{\theta}\sin{\theta}$
$=2\sqrt{2006}\cos{\theta}$
Since $K$ is an integer we know that $\cos{\theta}$ must be some integer divided by $2\sqrt{2006}$.  Since $0<\theta<90$, $0<\cos{\theta}<1$.  Since
$89<2\sqrt{2006}$ and $90>2\sqrt{2006}$, the numerator of $\cos{\theta}$ can be any integer between 1 and 89 inclusive, and thus the answer is $\boxed{089}$[/hide][/hide]

[quote="seedifferently"]This was probably a lucky coincidence, but I got the answer by rotating degrees at a time.  It just so happened that after the first [hide]89[/hide] degrees of rotation, the next degree always placed the rhombus in its initial position, hence my answer of [hide]89[/hide].  Lucky?  I think so, but I figured I would post it anyway just to let everyone make of it what they will.  (And maybe just to gloat a bit at how very little work was involved in this complete assumption lol)[/quote]
Hmmm... yeah, basically I think your answer was complete coincidence  :P But good job anyway - for your rotational symmetry to even make sense, the central rhombus would have to be a square, which it isn't (though it does look like it on the diagram).  Beyond that, I'm not even sure where your assumption came from/what exactly you mean by rotating the rhombus, but your guess was certainly lucky!

The answer makes sense since the largest area occurs when the rhombus is actually a square and the internal angle is 90 (I could be wrong since I'm not thinking very clearly at 2 am).

[quote="randomdragoon"][hide="my method"]Let one of the congruent rhombuses have base $b$ and height $h$. Drawing the height from one of the vertexes gives a right triangle with side lengths $b$, $h$, and $\sqrt{b^2-h^2}$. The middle rhombus is made up of 4 of these triangles so its area is is $2h\sqrt{b^2-h^2} = \sqrt{4b^{2}h^{2}-4h^4}$

Since $bh=\sqrt{2006}$, the area of the middle rhombus is $\sqrt{8024 - 4h^4}$

Since the area is an integer, the thing under the square root is a square number. The largest square number less than 8024 is $89^2=7921$. Thus, there are $89$ possible areas of the middle rhombus.[/hide][/quote]

That is an excellent non-trig solution.
I wish I thought of that one.

I said [hide] Let one side be $x$, and an angle (doesn't matter which) of one of the rhombuses (rhombi?) with area $\sqrt{2006}$ be $\theta$.  Then $x^2\sin{\theta}=\sqrt{2006}$.  The area of the inside rhombus is $x^2\sin{180^{\circ}-2\theta}=x^2\sin{2\theta}=2\sqrt{2006}\cos{\theta}$.  Thus, the number of possibilities is the floor value of $2\sqrt{2006}$, or 89.[/hide]
Essentially the same as themonster's...

[quote="randomdragoon"][quote="pieterminate"][quote="probability1.01"]Ehh, isn't it easy to see that the center rhombus is at most twice the area of one of the four other rhombi? Just let X be the midpoint of AB, Y the midpoint of ED, and Z the point common to regions P, S, and T. Then it's pretty clear that the area of XYZ is at most half the area of AXYE.[/quote]

Umm, so where are you getting to with this?  :?[/quote]
Because we know the area of the other four rhombi, this puts an upper bound on the middle rhombus, and if we assume the lower bound is 1 we are basically done.[/quote]

That doesn't give you 89 though, does it?

[quote="mysmartmouth"][/quote][quote="randomdragoon"][quote="pieterminate"][quote="probability1.01"]Ehh, isn't it easy to see that the center rhombus is at most twice the area of one of the four other rhombi? Just let X be the midpoint of AB, Y the midpoint of ED, and Z the point common to regions P, S, and T. Then it's pretty clear that the area of XYZ is at most half the area of AXYE.[/quote]

Umm, so where are you getting to with this?  :?[/quote]
Because we know the area of the other four rhombi, this puts an upper bound on the middle rhombus, and if we assume the lower bound is 1 we are basically done.[/quote][quote="mysmartmouth"]

That doesn't give you 89 though, does it?[/quote]

Umm isn't $2\sqrt{2006}>89$ I thought $\sqrt{2006}$ equals a bit more than 44.5, so that times 2 is like 89 and some change. So then you get 89.

[quote="mysmartmouth"]

That doesn't give you 89 though, does it?[/quote]

$\lfloor 2 \sqrt{2006} \rfloor = \lfloor \sqrt{8024} \rfloor = \sqrt{8100} - 1 = 89$

[quote="Octahedr0n"][quote="randomdragoon"]The middle rhombus is made up of 4 of these triangles so its area is is $ 2h\sqrt {b^2 \minus{} h^2} \equal{} \sqrt {4b^{2}h^{2} \minus{} 4h^4}$[/quote]

Could someone please explain how the above sentence was gotten?  Thanks![/quote]

Pythagorean theorem.

[quote=RedFireTruck][hide=Solution]
We see that $$[\mathcal{P}]=AF^2\sin\angle AFC=\sqrt{2006}$$ and $$[\mathcal{T}]=K=AF^2\sin2\angle AFC=2AF^2\sin\angle AFC\cos\angle AFC=2\sqrt{2006} \cos\angle AFC.$$

We see that all integer values between $0$ and $2\sqrt{2006}$ exclusive are possible values of $K$. Since $89<2\sqrt{2006}<90$, there are $\boxed{089}$ possible values of $K$.
[/hide][/quote]

hes back lets goo

[quote=RedFireTruck][hide=Solution]
We see that $$[\mathcal{P}]=AF^2\sin\angle AFC=\sqrt{2006}$$ and $$[\mathcal{T}]=K=AF^2\sin2\angle AFC=2AF^2\sin\angle AFC\cos\angle AFC=2\sqrt{2006} \cos\angle AFC.$$

We see that all integer values between $0$ and $2\sqrt{2006}$ exclusive are possible values of $K$. Since $89<2\sqrt{2006}<90$, there are $\boxed{089}$ possible values of $K$.
[/hide][/quote]

YAY HES BACK ORZ

[b]Solution:[/b] Notice that all the rhombi have side length $a$. Let one of the angles of the four congruent rhombi be $\theta$. This implies one of the angles of rhombus $\mathcal{T}$ is $2\theta$. Notice that the area of one of the four congruent rhombi is $a^2 \cdot \sin\theta$ whereas the area of rhombus $\mathcal{T}$ is $a^2 \cdot \sin2\theta$. We have that the ratio of $\sin2\theta$ to $\sin\theta$ is between $0$ and $2$ (exclusive in this particular setup). Hence, the possible positive areas are between $0 \cdot \sqrt{2006}$ and $2 \sqrt{2006}$ (exclusive). When we apply the integer restriction, we get our final answer of $\boxed{089}$.

[i]Comments:[/i] The motivation comes from the fact that the area of rhombus $\mathcal{T}$ is always fixed as determined by the angles of the other rhombi. This motivates a trig solution which leads us to a bound of the area.

Solved with [b]amuthup[/b], [b]js104[/b], [b]crazyeyemoody907[/b], [b]ETS1331[/b], [b]dottedcaculator[/b], [b]v4913[/b], [b]CT17[/b], [b]CyclicISLsclesTrapezoid[/b], [b]squareman[/b], and [b]bluelinfish[/b].

Let the side length of each rhombus be $X$, and let the angles of each rhombus be $\theta$ and $180-\theta$. We note that $x^2 \sin \theta = \sqrt{2006}$, and the area of the rhombus $\mathcal{T}$ is $x^2 \sin 2\theta = x^2 \sin \theta \cdot 2 \cos \theta = 2\sqrt{2006} \cos \theta$. Since $0 < \theta < 90$ is the only restriction, the answer is clearly $\lfloor 2\sqrt{2006} \rfloor = \fbox{089}$.


[quote="vietnam2007"]$x,y$ and $z$ are positive real numbers such that $x\sqrt{yz}+y\sqrt{xz}+z\sqrt{xy}\geq \frac{2}{3}$

prove that :

$x^{2}+y^{2}+z^{2}\geq 1$[/quote]

wrong problem!, $see x = y = z = \sqrt{\frac{2}{9}}$

Possibly reverse inequality sign in second one?


can anyone do this problem and tell me how they arrived at the answer

log 10 to the third square root of M squared

You problem description could mean a few things... Do you mean:

$\log_{10}{\sqrt[3]{M^2}}$?

If so:

$\log_{10}{\sqrt[3]{M^2}}=\log_{10}{{M^\frac{2}{3}}}$, because of exponent rules.

$=\frac{2}{3}\log_{10}{M}$ because of the power rule of logarithms.

-BLt

[quote]Looks like he might mean$\log_{ 10^3 } \sqrt{M^2} = \log_{10^3} M = \frac{ \log M}{\log(10^3)} = \frac{1}{3} \frac{ \log M}{\log 10} = \frac{1}{3} \log_{10} M.$[/quote]

Very uncommon to get a question with $\sqrt{M^2}$

wouldnt it just be $M$ ?

lol  :rotfl:


Let $ P(x)$ be a polynomial such that when $ P(x)$ is divided by $ x \minus{} 19$, the remainder is $ 99$, and when $ P(x)$ is divided by $ x \minus{} 99$, the remainder is $ 19$. What is the remainder when $ P(x)$ is divided by $ (x \minus{} 19)(x \minus{} 99)$?

$ \textbf{(A)}\ \minus{}x \plus{} 80 \qquad
\textbf{(B)}\ x \plus{} 80 \qquad
\textbf{(C)}\ \minus{}x \plus{} 118 \qquad
\textbf{(D)}\ x \plus{} 118 \qquad
\textbf{(E)}\ 0$

[hide="Click for solution"]
$ P(19)\equal{}99$ and $ P(99)\equal{}19$, so $ P(x)\equal{}(x\minus{}19)(x\minus{}99)Q(x)\plus{}ax\plus{}b$, where $ a$ and $ B$ are constants, and $ Q(x)$ is a polynomial.  Then $ 99\equal{}P(19)\equal{}19a\plus{}b$ and $ 19\equal{}P(99)\equal{}99a\plus{}b$.  Thus, by solving the system of equations, we find that $ a\equal{}\minus{}1$ and $ b\equal{}118$.  The remainder is $ \minus{}x\plus{}118$, or answer $ \boxed{\textbf{C}}$.
[/hide]

[quote=Amkan2022][quote=NamelyOrange][quote=Amkan2022]Sorry but why is the remainder in form $ax+b$ instead of just some constant $a$, since shouldn't it be $\deg(x-99) - 1 = \deg(x-19) -1 = 0$?[/quote]

Dividing by a degree $n$ polynomial gives a degree $n-1$ (or less) remainder.[/quote]

Exactly, so since $x-19$ and $x-99$ have degree $1$, the remainder should be degree $0$, which is some value $r$

....But then why is the remainder of form $ax+b$?[/quote]

But we're asking for the remainder when it's divided by $(x-19)(x-99)$, which has degree $2$.


[quote="digger"][quote="kiet"]Evaluate expression using remainder theorem

x= 2+ square root (2)               f(x)= 10x-3x^3-8+8x^2[/quote]
Evaluate $f(x)= 10x-3x^{3}-8+8x^{2}$ in the point $x= 2+\sqrt2$?[/quote]

$x-2=\sqrt{2}\Longrightarrow (x-2)^{2}=2\Longleftrightarrow x^{2}-4x+2=0,$ thus you can write as $f(x)=(x^{2}-4x+2)Q(x)+ax+b.$
So,....

[quote="kiet"]Evaluate expression using remainder theorem

x= 2+ square root (2)               f(x)= 10x-3x^3-8+8x^2[/quote]
[hide]$f(x)=10x-3x^{3}-8+8x^{2}$ or easily written as $f(x)=-3x^{3}+8x^{2}+10x-8$
Plugging in $x=2+\sqrt{2}$, you get $-3\cdot(2+\sqrt{2})^{3}+8\cdot(2+\sqrt{2})^{2}+10\cdot(2+\sqrt{2})-8$
Hiding some ugly expansion, you get$-60-42\sqrt{2}+48+32\sqrt{2}+20+10\sqrt{2}-8=0$ so that function is equal to $\boxed{0}$[/hide]

You are right but it is useful to apply Horner's algorithm to make the calculations less ugly.

I've thought that [b]t0rajir0u[/b] possibly called it "synthetic division".


Case 1: 0 horizontal pieces

Obviously only 1.

Case 2: 2 horizontal pieces

Then there are 3 vertical pieces, and there are 4 ways to arrange.

Case 3: 4 horizontal pieces

There are 3 ways to arrange.

1+3+4=8

Fibonacci numbers have something to do with this.

Yes.  Note that the number of ways to make a 2 by 5 is the same as the ways to make a 2x4 +ways to make 2x3, because you can add either two horizontal or a vertical.


function
real analysis
real analysis unsolved

Find values of [i]a[/i] and [i]b[/i] so that the function [i]y=axe^(-bx)[/i] has a local maximum at the point (2,10).

Let $f(x)=axe^{-bx}\ (a\neq 0)$, we have $f'(x)=a(1-bx)e^{-bx}$
The condition gives $f'(2)=0\ and\ f(2)=10\Longleftrightarrow a(1-2b)e^{-2b}=0\ and\ 2ae^{-2b}=10$,yielding $\boxed{a=5e,b=\frac{1}{2}}$, then you should confirm $f(x)$ has a local maximum at the point $(2,10)$


So, I was given this nice little problem saying:

[i]"One man tells another, 'Let's make a deal. Every day, during a whole month, I'll give you 10,000 dollars. In addition, every day I'll add 5,000 more - so the second day you'll be paid 15,000 dollars, the third 20,000, and so on. In exchange, you must give me 0.01 the first day, and that quantity will be doubled every day'.

The second man quickly accepts. Did he make a good deal?"[/i]

Well, the original thing was much longer and more beautiful, with some sort of story about a millionaire, but you get the idea.

With some calculations it's easy to see that the second man made a disastrous mistake, and that he'll be losing 8,262,418.23 dollars by the end of the month. BTW, they're in the attached Excel file.

The problem is that then I'm asked to find some formulas that will tell you how much money each person had to pay, based only on the day.

I've been able to make some so far:

- Payment of the second man each day (0.01 - 0.02 - 0.04...)
=[2^(d-1)] / 100

- Cumulative payment of the second man (0.01 - 0.03 - 0.07...)
=[(2^d)-1)] / 100

- Payment of the first man (10,000 - 15,000 - 20,000...)
=10000 + 5000·(d-1)

The one I can't solve is the last one, the cumulative payment of the first man (the list that goes 10,000 - 25,000 - 45,000...). I only managed to do something like this:
=[10000 + 5000 (d-1)] + [10000 + 5000 (d-2)] + ...

Is there any possibility to make a formula to do the above in a more elegant way, without nasty infinite additions?

Help will be greatly appreciated.

Edit: Sorry for writing "dollars" so many times, but this program does nasty things when I try to type the symbol $\$$...

Click the smiley to reveal hidden content
[hide=" :) "]So this is what happens:

2nd man has a total of:
$\$10000$
$\$25000$
$\$45000$
$\$70000$
$\$100000$

At the nth day, he has a total of $\$ n(7500+2500n)$

1st man has a total of:
$\$0.01$
$\$0.03$
$\$0.07$
$\$0.15$
$\$0.31$

At the nth day, he has a total of $\$ \frac{2^{n+1}-1}{100}$[/hide]

Could a mod move this to a higher forum? This is way too hard for classroom math!

Thank you very much!

[hide="One quick comment though,"] I think you've made a mistake here:
[i][2^(n+1)-1] / 100[/i]
This formula gives as results 0.03 - 0.07, etc., not 0.01 - 0.03 - etc. as we want.

I think the correct formula is the one I posted before:
[2^n-1] / 100

[/hide]

[quote]Could a mod move this to a higher forum? This is way too hard for classroom math![/quote]

I'll keep this in mind if I have to post another problem.


integration
quadratics
probability and stats

I'm wondering if for two browniens motions, uncorrelation is meaning independancy ?

No, here is the counterexample. Let $ W$ be the Brownian motion and $ M_t\equal{}\int_0^t\mathrm{sign}\,(W_s)dW_s, t\geq 0$. Then $ M_t$ is a square integrable martingale with its variation equal $ \langle M\rangle_t\equal{}\int_0^t(\mathrm{sign}\,(W_s))^2ds\equal{}t$, and hence by the Levy theorem  is a Brownian motion. Moreover, $ M$ and $ W$ are non-correlated:
$ \mathrm{cov}\,(W_t,M_s)\equal{}E\langle w,M\rangle_{t\wedge s}\equal{}E\int_0^{t\wedge s}\mathrm{sign}\,(W_r)\, dr\equal{}0.$ On the other hand, $ M$ is a functional of $ W$ and thus can not be independent on $ W$.

Thanks for that nice counterexemple, I deduce from that : given two brownien motion $ B_1$ et $ B_2$  so that $ < B_1,B_2 > _t \equal{} \rho t$ we can not say that $ B_2 \equal{} \rho B_1 \plus{} \sqrt {1 \minus{} \rho^2}W$ where $ W$ is a brownien motien independ form $ B_1$ , we can juste say that $ W$ is uncorrelated with  $ B_1$ !

[quote]Thanks for that nice counterexemple, I deduce from that : given two brownien motion  et  so that  we can not say that  where  is a brownien motien independ form  , we can juste say that  is uncorrelated with [/quote]

No you don't !

In your example $ B_2$ is indeed a brownian motion by Levy's theorem  (you have

$ <B_2>_t\equal{}t$ which is enough to say that $ B_2$ is a brownian motion).

I dont understand ! What I'm saying is : given two browniens motions $ B_1$ and $ B_2$ correlated by $ \rho$ , Obviously by levy's theorem $ W$ is a brownien motions wich is uncorrelated to $ B_1$ , but the counterexemple show that $ W$ is not necessary independent from $ B_1$ ! Actually, I was wondering if we can always decompose two correlated browniens motions with independent browniens motions as they do for simulations ? are we clear now  :huh: ?

[b]yassine[/b], your conclusion in post #3 is not correct. $ W$ and $ B_1$ are independent indeed, and the reason is that you have assumed much more than just non-correlatedness. The Levy theorem has a multidimensional version: if $ X\equal{}(X_1,\dots, X_d)$ is a continuous square integrable martingale, and $ \langle X_j,X_k\rangle_t\equal{}\delta_{jk}t$ then $ X$ is an $ n$-dimensional Brownian motion. Hence you just have to verify that $ (W,B_1)$ is a 2-dim martingale with $ \langle W\rangle_t\equal{}\langle B_1\rangle_t\equal{}t, \langle W,B_1\rangle_t\equal{}0$ and then apply Levy theorem.
To conclude: for processes, correlation is not a proper tool to get independence
(unless you already know the processes are jointly Gaussian), but for martingales the mutual  quadratic characteristic $ \langle\cdot,\cdot\rangle$ is indeed. This is the reason why the example in my previos letter was designed in such a way that $ \langle W,M\rangle_t\not\equal{}0$  a.s. but $ E\langle W,M\rangle_t\equal{}0$  :)

:blush: for martingales a quadratique covariation equal to $ 0$ is meaning independency !! what a strong result ! thank you for the general version of Levy's theorm, I didn't know that  :roll:


calculus
integration
function
trigonometry
special factorizations
calculus computations

Let $ f(x)\equal{}\int_{0}^{\infty}e^{\minus{}t^2}\cos{xt}dt$

Show that $ f'(x)\equal{}\minus{}\frac{1}{2}xf(x)$

moreover show $ f(x)\equal{}\frac{1}{2}\sqrt{\pi}e^{\minus{}x^2/4}$.

[quote="wizard"]Let $ f(x) \equal{} \int_{0}^{\infty}e^{ \minus{} t^2}\cos{xt}dt$

Show that $ f'(x) \equal{} \minus{} \frac {1}{2}xf(x)$

moreover show $ f(x) \equal{} \frac {1}{2}\sqrt {\pi}e^{ \minus{} x^2/4}$.[/quote]
Is that not strange or I am missing something?
We have $ f^{(2)}(x) \equal{} \minus{} x^2f(x)$ and $ f(x) \equal{} \frac {1}{2}\sqrt {\pi}e^{ \minus{} x^2/4}$ is not solution for this equation!!

$ g(x,t)\equal{} e^{ \minus{} t^2}\cos{xt}$,
$ |g_x(x,t)|\equal{}|\minus{}te^{ \minus{} t^2}\sin{xt}| \le te^{ \minus{} t^2}$.
$ \int_0^{\plus{}\infty}te^{ \minus{} t^2}dt < \infty$, so you can use the theorem of derivation under the integral sign:
$ f'(x)\equal{}\int_0^{\plus{}\infty}\minus{}te^{ \minus{} t^2}\sin{xt}*dt\equal{}\minus{}xf(x)/2$ integrating by parts.
This is an easy differential equation with the initial condition $ f(0)\equal{}\int_0^{\plus{}\infty}e^{ \minus{} t^2}dt\equal{}\sqrt{\pi}/2$.

This is a computation of the Fourier transform of the Gaussian. I know essentially three ways to make that computation:

1. By completing the square and making a "change of variables" which is actually a use of Cauchy's Theorem in complex analysis.

2. By setting up and solving a first order linear differential equation. In other words, exactly this topic.

3. By working in $ \mathbb{R}^n$ and invoking the following characterization of Gaussians: they are the only globally integrable functions that are both radial and also can be factored as $ f(x)f(y).$


Bobby found 204 cents today.
He has pennies, nickels, and quarters.
What is the smallest amount of pennies that he can have?

[hide=" :D "]Nickels and quarters could only form numbers that are the power of five.

200 is the closest multiple of five lower than 204.

204-200 is 4.

4 pennies.[/hide]

[hide="Simple Answer"]It is impossible to create 4 cents with anything other than pennies.  That means the fewest pennies he could have found is 4.[/hide]


linear algebra
matrix
linear algebra unsolved

Let $A$ a matrix $n \times n$. Show that there exists a natural $p \geq 1$ such that $A^{p}\in sev <I_{n}, A, A^{2}, ..., A^{p-1}>$.

try to see what would happen if it were not the case ..


limit
function
calculus
calculus computations

Well, it's hard to do it without zeta function, since it IS the zeta function. :lol:

You can see various ways to prove the result [url=http://mathworld.wolfram.com/RiemannZetaFunctionZeta2.html]here[/url] or [url=http://www.mathlinks.ro/viewtopic.php?t=50418]here[/url], or in your Calculus textbook...  And there is always my favourite [url=http://www.secamlocal.ex.ac.uk/people/staff/rjchapma/etc/zeta2.pdf]paper[/url].


inequalities
symmetry
combinatorics proposed
combinatorics

A permutation $\sigma: \{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ is called [i]straight[/i] if and only if for each integer $k$, $1\leq k\leq n-1$ the following inequality is fulfilled
\[ |\sigma(k)-\sigma(k+1)|\leq 2. \]
Find the smallest positive integer $n$ for which there exist at least 2003 straight permutations.

[i]Valentin Vornicu[/i]

[quote]We say that f is a straight permutation or order n if and only if for each k=1,2,...,n-1 we have that |f(k)-f(k+1)|  2.

Find all values of n such that there are less than 2003 straight permutations of order n.

(A permutation's order is the number of elements that permutation has).[/quote]
this is not a very difficult one :)  :)
 Tn is the number of straight permutation or order n
 we can prove that Tn+1=Tn+Tn-2.

I think that you misunderstood the problem. The answer you are giving is not correct, and the problem is not that simple. Only the 6 guys who went to the IMO solved it in the contest, so it actually separated the team from the other competitiors. I wouldn't call this problems easy :D

You are right I misunderstood the problem  :(
Tn is only the number permutation that begin with 1.
However, I still don't think that this one is very difficult,I'll find out the solution soon. :?  :?  :?  :?

[quote="Valentin Vornicu"]We say that f is a [i]straight[/i] permutation or order n if and only if for each k=1,2,...,n-1 we have that |f(k)-f(k+1)| \leq 2.

Find all values of n such that there are less than 2003 straight permutations of order n.

(A permutation's order is the number of elements that permutation has).[/quote]
As I promised,here is my result
Sn= the number straight[/i] permutation or order n
S1=1 S2=2 S3=6 Sn=Sn-1+Pn-2
P1=4 P2=6  P3=8 Pn=Pn-1+Pn-3+2
with n<=17 Sn<2003

again I must tell you that you are wrong. Keep trying though - remember in the TST you had this problem and other two in only 4 hours. I still don't think it's easy :D

Sorry because I'm not very good at English so I can't post the full solution.
Anyway, Iwant to see your solution!! :D

well for one you have not got the right result. for second the recurrence relationships are not correct. please check your solution. it is easy to make mistakes :D

I will post later my solution (in a couple of hours).

hi!
silversunboy, u can see sol at :
http://ajorza.tripod.com/math.htm

[quote="silversunboy"][quote]We say that f is a straight permutation or order n if and only if for each k=1,2,...,n-1 we have that |f(k)-f(k+1)|  2.

Find all values of n such that there are less than 2003 straight permutations of order n.

(A permutation's order is the number of elements that permutation has).[/quote][/quote]

 My solution is based on my first result:
 Tn is the number of straight permutations of order n that start by 1
   we can prove that Tn+1=Tn+Tn-2.
  T1=1 T2=1 T3=2
 Sn is the number of straight permutations of order n
  we have
 Sn=2Tn+ 2(Tn-2+..+T1)
 S1=1 S2=2 S3=6 S4=12 S5=20
<=>[color=green] Sn=Sn-1+2Tn-2+2Tn-3+2[/color]
It was just a mistake of calculating,when I try to shorten the result I made a mistake. Now I know for sure that my solution is right. :(  :(
 Thanks.

[quote]My solution is based on my first result:
Tn is the number of straight permutations of order n that start by 1
we can prove that Tn+1=Tn+Tn-2.
[/quote]
you solution is based on a false fact :D. Please compute with your recurrence T5 and also compute it manually. See that the results differ :D.

I think that Andrei Jorza's solution, although finds correct n, is also flawed :D, but I need to check it some more. It's easy to miss some cases here.

Sorry it was a mistake in typing
Tn+1=Tn+Tn-2+1 not Tn+1=Tn+Tn-2

well you now (after so many trials) have got the recurrence right. Still no justification however. Think how many things could have got wrong with this problem in contest :D So you see that it is not an easy problem :D.

H..m I'm afraid to say that I must agree with you. :D  :D  :D
How about your solution? do you have a short solution??

:) i think i solve it too... but in a different way...[an ugly way i think cause i worked almost 3 hours at it]
i found smth like this:
T2n+1=n.(4n 2 +3n+5)/3+2
T2n+2=n.(4n 2 +9n+11)/3+4

:) i think i solve it too... but in a different way...[an ugly way i think cause i worked almost 3 hours at it]
i found smth like this:
T2k+1=k.(4k 2 +3k+5)/3+2
T2k+2=k.(4k 2 +9k+11)/3+4

n=22??

The main ideea is to look where $n$ is positioned. In that idea let us denote by $x_n$ the number of all the straight permutations and by $a_n$ the number of straight permutations having $n$ on the first or on the last position, i.e. $\sigma(1)=n$ or $\sigma(n)=n$. Also let us denote by $b_n$ the difference $x_n-a_n$ and by $a_n'$ the number of permutations having $n$ on the first position, and by $a_n''$ the number of permutations having $n$ on the last position. From symmetry we have that $2a_n'=2a_n''=a_n'+a_n''=a_n$, for all $n$-s.
Therefore finding a recurrence relationship for $\{a_n\}_n$ is equivalent with finding one for $\{a_n'\}_n$.

One can simply compute: $a_2'=1$, $a_3'=2$, $a_4'=4$. Suppose that $n\geq 5$. We have two possibilities for the second position: if $\sigma(2)=n-1$ then we must complete the remaining positions with $3,4,\ldots,n$ thus the number of ways in which we can do that is $a_{n-1}'$ (because the permutation $\sigma': \{1,2,\ldots, n-1\}\to\{1,2,\ldots,n-1\}$, $\sigma'(k)=\sigma(k+1)$, for all $k$, $1\leq k\leq n-1$, is also a straight permutation).

If on the second position we have $n-2$, $\sigma(2)=n-2$, then $n-1$ can only be in the last position of the permutation or on the third position, i.e. $\sigma(3)=n-1$ or $\sigma(n)=n-1$. If $\sigma(n)=n-1$, then we can only have $\sigma(n-1)=n-3$ thus $\sigma(3)=n-4$ and so on, thus there is only one permutation of this kind. On the other hand, if $\sigma(3)=n-1$ then it follows that $\sigma(4)=n-3$ and now we can complete the permutation in $a_{n-3}'$ ways (because the permutation $\sigma': \{1,2,\ldots, n-3\}\to\{1,2,\ldots,n-3\}$, $\sigma'(k)=\sigma(k+3)$, for all $k$, $1\leq k\leq n-3$, is also a straight permutation). Summing all up we get the recurrence:
\[ a_n'=a_{n-1}'+1+a_{n-3}' \Rightarrow a_n=a_{n-1}+a_{n-3}+2,\ \forall \ n\geq 5. \eqno(1) \]
The recurrence relationship for $\{b_n\}$ can be obtained by observing that for each straight permutation \break $\tau: \{1,2,\ldots,n+1\}\to\{1,2,\ldots,n+1\}$ for which $2\leq \tau^{-1}(n+1)\leq n$ we can obtain a straight permutation $\sigma: \{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ by removing $n+1$. Indeed $n+1$ is "surrounded" by $n$ and $n-1$, so by removing it, $n$ and $n-1$ become neighbors, and thus the newly formed permutation is indeed straight. Now, if $\tau^{-1}n\in\{1,n+1\}$ then the newly formed permutation $\sigma$ was counted as one of the $a_{n}$-s, minus the two special cases in which $n$ and $n-1$ are on the first and last positions, and also minus the permutations which begin or end with a sequence of the form $n..n-2..n-1..n-3...$ thus $n$ and $n-1$ not being neighbors. If $\tau^{-1}(n)\nin\{1,n+1\}$ then certainly $\sigma$ was counted with the $b_n$-s. Also, from any straight permutation of $n$ elements, not having $n$ and $n-1$ in the first and last position, thus $n$ certainly being neighbor with $n-1$, we can make a straight $n+1$-element permutation by inserting $n+1$ between $n$ and $n-1$. Therefore we have obtained the following relationship:
\[ b_{n+1} = a_n - 2-a_{n-3} +b_n = a_{n-1}+b_n ,\ \forall \ n\geq 4 \ \Rightarrow \]
\[ b_n= a_{n-2}+a_{n-3}+\cdots +  a_2 + b_3 \Rightarrow x_n = a_n + a_{n-2}+a_{n-3}+\ldots + a_2 + b_3, \ \forall \ n\geq4. \]
It is obvious that $\{x_n\}_n$ is a "fast" increasing sequence, so it is easy to compute the first terms using the relationships  obtained above, which will prove that the number that we are looking for is $n=16$.


function
induction
algebra unsolved
algebra

Let $x=0$,$f(y)=f(f(y))(*)$,for all $y\in R$.
Let $x=1$,$f(y+1)=f(1)+f(f(y))=f(1)+f(y)$ for all $y\in R$.
Let $y=0$,$f(0)=0,f(x^4)=x^3f(x),f(x^4+y)=f(x^4)+f(y)$
Let $a=x^4\geq 0,f(a+y)=f(a)+f(y)$ for all $a>0,y\in R$
Let $y=a$,$f(2a)=2f(a)$,by induction,for all $n\in N,f(na)=nf(a)$
If there exist $x\neq y$,$f(x)=f(y)$,Suppose $x>y,a=x-y>0$.
$f(x)=f(a)+f(y),f(a)=0$
So $f(na)=0$ for all $n\in N$, a contradiction with condition (i)
So for all $x\neq y$,$f(x)\neq f(y)$.
By (*),$f(y)=y$.for all $y\in R$.
So $f(x)=x$.

We don't need a to be >0.
Because $ ( \minus{} x)^3.f( \minus{} x) \equal{} f(x^4) \equal{} x^3.f(x) \rightarrow f(x) \equal{} \minus{} f( \minus{} x)$
So for a<0:
$ f( \minus{} a) \plus{} f( \minus{} x) \equal{} f( \minus{} a \minus{} x) \rightarrow \minus{} f(a) \minus{} f(x) \equal{} \minus{} f(a \plus{} x) \rightarrow f(a) \plus{} f(x) \equal{} f(a \plus{} x)$

Setting $x=0$ shows that $f(f(y)) = f(y)$, so $f(x^4 + y) = x^3 f(x) + f(y)$ for all real $x,y$. If $f(y) > y$ for any $y$, setting $x = (f(y) - y)^{\frac{1}{4}}$ gives $f(f(y)) = f(x^4 + y) = x^3 f(x) + f(f(y))$, whence $x^3 f(x) = 0$, or $f(x) = 0$. Note that $f(x^4 + y) = x^3 f(x) + f(y) = f(y)$ for all $y$, whence $f(kx^4 + x) = f(x) = 0$ for all $k$. Since $f(y) > y$, $x > 0$, so there are infinitely many $z$ ($z = kx^4 + x$, $k \in \mathbb{Z}^+$) for which $f(z) = 0$, which is a contradiction. Hence, $f(y) \leq y$ for all real $y$.

Setting $x=1$ gives $f(y+1) = f(y) + f(1)$. Setting $y=0$ in this equation gives $f(0) = 0$.  Setting $y=0$ in the original equation gives $f(x^4) = x^3 f(x)$, and setting $y = -x^4$ gives $0 = f(0) = x^3 f(x) + f(-x^4)$. Hence, $f(-x^4) = -f(x^4)$ for all $x$, whence $f(x) = -f(-x)$ for all real $x$. Since $f(x) \leq x$ and $-f(x) = f(-x) \leq -x$ for all real $x$, we find that $f(x) = x$ for all real $x$.

Let $P(x,y)$ denote the given relation from $(ii)$.
Setting $P(0,x)$ gives $f(x) = f(f(x))$ for every $x$ in $R$.
Setting $P(-1,-1)$ gives us $f(0) = -f(-1) + f(f(-1)) = -f(-1) + f(-1) = 0$.
Setting $P(x,0)$ gives $f(x^{4}) = x^{3}f(x)$.
Now $P(-x,0) = -x^{3}f(-x)$, so $f$ is odd.
The next part is to use $(i)$ to prove that $f(s) = 0$ then $s = 0$.
Notice that if there is a number $s$ such that $f(s) = 0$ different from $0$,
there is also a positive such number because $f$ is odd.
So assume that there is a positive number $s$ such that $f(s) = 0$.
Setting $P(s^{\frac{1}{4}}, s)$ gives $f(2s) = f(s) + f(f(s)) = 0$ so $f(2s) = 0$.
Now by induction we show that $f(ns) = 0$ for every natural number $n$.
But this is easy, just by setting $P((ns)^{\frac{1}{4}}, s)$ gives $f((n+1)s) = f(ns + s) = f(ns) + f(s) = 0$.
This violates $(i)$ so if $f(s) = 0$, then $s = 0$.
Setting $P(x, f(x^{4}) - x^{4})$ and using $f(f(x)) = f(x)$ we get
$f(f(x^{4}) - x^{4}) = 0$ and so $f(x^{4}) = x^{4}$, but $f$ is odd so $f(x) = x$ is the only solution.

[quote=steppewolf]Let $P(x,y)$ denote the given relation from $(ii)$.
Setting $P(0,x)$ gives $f(x) = f(f(x))$ for every $x$ in $R$.
Setting $P(-1,-1)$ gives us $f(0) = -f(-1) + f(f(-1)) = -f(-1) + f(-1) = 0$.
Setting $P(x,0)$ gives $f(x^{4}) = x^{3}f(x)$.
Now $P(-x,0) = -x^{3}f(-x)$, so $f$ is odd.
The next part is to use $(i)$ to prove that $f(s) = 0$ then $s = 0$.
Notice that if there is a number $s$ such that $f(s) = 0$ different from $0$,
there is also a positive such number because $f$ is odd.
So assume that there is a positive number $s$ such that $f(s) = 0$.
Setting $P(s^{\frac{1}{4}}, s)$ gives $f(2s) = f(s) + f(f(s)) = 0$ so $f(2s) = 0$.
Now by induction we show that $f(ns) = 0$ for every natural number $n$.
But this is easy, just by setting $P((ns)^{\frac{1}{4}}, s)$ gives $f((n+1)s) = f(ns + s) = f(ns) + f(s) = 0$.
This violates $(i)$ so if $f(s) = 0$, then $s = 0$.
Setting $P(x, f(x^{4}) - x^{4})$ and using $f(f(x)) = x$ we get
$f(f(x^{4}) - x^{4}) = 0$ and so $f(x^{4}) = x^{4}$, but $f$ is odd so $f(x) = x$ is the only solution.[/quote]

f(x) = -x is odd too, but you can easily rule that case out by plugging in some values.

[quote=WizardMath]My solution:

$P(0,y)$ gives $f(y) = f^2(y)$.
$P(x,1)$ and $P(1,x^4)$ give $f(x^4) = x^3f(x)$. In particular, we also have $f(0)=0$.
So we have for all $x \ge 0$, $f(x+y) = f(x) + f(y)$. Plugging in $y=-x$ gives $f$ is odd. So $f$ satisfies Cauchy's equation.
Suppose for the sake of contradiction that $f$ is not injective. Let $f(a) = f(b)$ for unequal $a,b$. We have $f(a-b)=0$ from Cauchy's equation. Then by induction using Cauchy's equation, we have $f(n(a-b)) = 0$ for every $n \in \mathbb{N}$. This contradicts the assumption, hence $f$ is injective. So we must have, using the first relation we found, that $f(y) = y$ $\forall \ y \in \mathbb{R}$.[/quote]

I did the exact same thing :)!

[b]Solution.[/b]Let $P(x,y)$ be the assertion for $f(x^4+y)=x^3f(x)+f(f(y))$.
$$P(0, x)\implies f(x)=f(f(x))\qquad (1)$$ $$P(1, x)\implies f(x+1)=f(x)+f(1)\qquad (2)$$
[b]Lemma 1.[/b] $f$ satisfies Cauchy's equation.
[b]Proof.[/b] In $(2)$ letting $x=0\implies f(0)=0$. $P(x,0)\implies f(x^4)=x^3f(x)$. Rewriting the original equation gives that $f(x+y)=f(x)+f(y)\forall x\geq 0$.
Since $f(0)=0$, plugging $y=-x$ $\implies  -f(x)=f(-x)\implies f$ is odd$\implies f$ satisfies Cauchy's equation.$\square$

[b]Lemma 2.[/b] If we prove that $f$ is injective we are done.
[b]Proof.[/b] By $(1)$ if $f$ is injective $\implies f(x)=x\forall x\in \mathbb{R}$. Thus if $f$ is injective we're done.$\square$

[b]Lemma 3.[/b] $f$ is injective.
[b]Proof.[/b]FTSOC suppose $f$ is not injective, so we have that $f(a)=f(b)$, and $a\neq b$. We have that $f(x+y)=f(x)+f(y)$, plugging $x=a$, $y=-b \implies 0=f(a)-f(b)=f(a)+f(-b)=f(a-b)$. Now we have $f(a-b)=0$, by induction $\implies f(k(a-b))=0\forall k\in \mathbb{N}\implies a=b$.$\square\blacksquare$

Let $P(x,y)$ be the given assertion.
$P(0,x)\Rightarrow f(f(x))=f(x)$
$P(-1,-1)\Rightarrow f(0)=0$
$P(-x,y)-P(x,y)\Rightarrow x^3f(x)=-x^3f(-x)\Rightarrow f(x)=-f(-x)$ for all $x\ne0$, but it's true for $x=0$ also.

Assume $f(k)=0$ for some $k\ne0$. WLOG $k>0$ (by oddness).
$P(k,k)\Rightarrow f(k^4+k)=0$
Consider the sequence $k_n$ defined by $k_1=k$ and $k_{n+1}=k_n^4+k_n$. By $P(k_n,k_n)$ we have by induction that all $k_n$ are zeroes of $f$. Also, $k_n>0$ implies $k_{n+1}=k_n^4+k_n>k_n>0$ and so all $k_n$ are distinct. This means that $f$ has infinitely many zeroes which is a contradiction.
So $f(k)=0\Leftrightarrow k=0$.

$P(x,0)\Rightarrow f(x^4)=x^3f(x)$
$P\left(\sqrt[4]x,y\right)\Rightarrow f(x+y)=f(x)+f(y)\forall x\ge0$. Set $x\mapsto x+y$ and $y=-y$ for the assertion $f(x)+f(y)=f(x+y)$ if $x+y\ge0$. But $f(-x)+f(-y)=f(-x-y)$, so $f$ is additive in general.
If $f(a)=f(b)$ for some $a,b$. Setting $x=a-b$ and $y=b$ in this gives $f(a-b)=0$, and so $a-b=0$, implying injectivity. Then $f(f(x))=f(x)\Rightarrow\boxed{f(x)=x}$ which fits.

$P(0,y) : f(y) = f(f(y))$.
$P(1,0) : f(1) = f(1) + f(f(0)) \implies f(f(0)) = f(0) = 0$.
$P(x,0) , P(-x,0) \implies x^3f(x) = -x^3f(-x) \implies f$ is odd.
$f(x^4+y) = x^3f(x) + f(f(y)) \implies f(x^4+y) = f(x^4) + f(y) \implies f$ is a Cauchy function.
Assume $n \neq 0$ such that $f(n) = 0$ Now note that we have $f(2n) = 2f(0) = 0$ and with induction we have $f(an) = 0$ for infinite $a$ which gives contradiction so $n$ doesn't exist.
Assume $a,b$ such that $f(a) = f(b)$ Now we have $f(x^4+a) = f(x^4) + f(a) = f(x^4) + f(b) = f(x^4+b)$. Now assume that $a \neq b$ then we have $f(0) = f(b-a)$ so $b-a = 0 \implies a = b$ so contradiction so $f$ is injective.
Note that we had $f(ax) = af(x) \implies f(f(ax)) = f(af(x)) \implies f(ax) = f(af(x)) \implies ax = af(x) \implies f(x) = x$.
Answers $: f(x) = x$.

Let $P(x,y)$ be the assertion in (ii).
$P(0,y)\implies f(y)=f(f(y)).$
$P(1,0)\implies f(f(0))=f(0)\implies f(0)=0.$
Comparing $P(x,0)$ and $P(-x,0)$ we get $f$ is odd.

If $f(1)=0,$ then by induction $f(n)=0~\forall n\in \mathbb{N},$ a contradiction with (i). Thus $f(1)\neq 0.$
Suppose $\exists f(z)=0: z>0$ and $z \neq 1.$
$P(z,0)\implies f(z^4)=z^3f(z)=0,$ which contradicts (i). Thus $f(x)=0\iff x=0.$

$P(\sqrt[4]{x},y)\implies f$ is additive.
Suppose $\exists u,v: f(u)=f(b)$ for some real $u,v.$
$P(u-v,v)\implies f(u-v)=0\implies u=v,$ thus $f$ is injective.

$P(0,x)\implies \boxed{f(x)=x}~~\forall x,$ which obviously works.

[quote=shobber]Let ${\bf R}$ denote the set of all real numbers. Find all functions $f$ from ${\bf R}$ to ${\bf R}$ satisfying:

(i) there are  only finitely many $s$ in ${\bf R}$ such that $f(s)=0$,
and

(ii) $f(x^4+y)=x^3f(x)+f(f(y))$ for all $x,y$ in ${\bf R}$.[/quote]
$\color{blue}\boxed{\textbf{Answer: }f\equiv x}$
$\color{blue}\boxed{\textbf{Proof:}}$
$\color{blue}\rule{24cm}{0.3pt}$
In $(ii) x\to 0:$
$$\Rightarrow f(y)=f(f(y))...(iii)$$
Replacing $(iii)$ in $(ii):$
$$\Rightarrow f(x^4+y)=x^3f(x)+f(y)...(\alpha)$$
In $(\alpha) x\to 1, y\to 0:$
$$\Rightarrow f(1)=f(0)+f(1)$$
$$\Rightarrow f(0)=0$$
$\color{red}\boxed{\text{If }\exists a\neq 0 / f(a)=0:}$
$\color{red}\rule{24cm}{0.3pt}$
In $(\alpha) x\to a:$
$$\Rightarrow f(y+a^4)=f(y)$$
$$\Rightarrow f\text{ is periodic}$$
By $(i) (\Rightarrow \Leftarrow)$
$\color{red}\rule{24cm}{0.3pt}$
$$\Rightarrow f(x)=0 \Leftrightarrow x=0...(\omega)$$
In $(\alpha) y\to 0:$
$$\Rightarrow f(x^4)=x^3f(x)...(iv)$$
Replacing $(iv)$ in $(\alpha):$
$$\Rightarrow f(x^4+y)=f(x^4)+f(y)...(\beta)$$
In $(\beta) y\to f(y):$
$$\Rightarrow f(x^4+f(y))=f(x^4)+f(y)$$
$$\Rightarrow f(x^4+f(y))=f(x^4+y)...(\theta)$$
In $(\theta) y\to -x^4:$
$$\Rightarrow f(x^4+f(-x^4))=0$$
By $(\omega):$
$$\Rightarrow f(-x^4)=-x^4$$
$$\Rightarrow f(x)=x, \forall x\in\mathbb{R}^-_0...(1)$$
In $(\beta) y\to -x^4-1:$
$$\Rightarrow -1=f(x^4)-x^4-1$$
$$\Rightarrow f(x^4)=x^4$$
$$\Rightarrow f(x)=x,\forall x\in\mathbb{R}^+...(2)$$
By $(1)$ and $(2):$
$$\Rightarrow \boxed{f\equiv x}_\blacksquare$$
$\color{blue}\rule{24cm}{0.3pt}$


The dimensions of a triangle are 13, 13, and 24. What is the area in square units of this triangle?

A) 30 B) 60 C) 90 D) 156 E) 312

hello, with the theorem of Pythagorean we get $ 12^2\plus{}h^2\equal{}13^2$ from here we get $ h\equal{}5$ therefore we can compute the area of the triangle as $ A\equal{}\frac{1}{2}ah\equal{}\frac{1}{2}24\cdot5\equal{}60$
so the answer is $ B$.
Sonnhard.


induction
inequalities
pigeonhole principle
calculus
integration
least common multiple
combinatorics proposed

If $a_1 < a_2 < ... < a_k$ is a set of k distinct positive integer whose $2^k$ subsets all have different sums, then the sum of the reciprocals of the integers must be less than 2:

       $\frac 1{a_1} + \frac 1{a_2} + ...+ \frac 1{a_k} < 2 $

It's easy to prove by induction that $a_i \geq 2^{i-1}$.
Now, given that $\displaystyle \sum_{i=0}^{+\infty} \frac {1}{2^i} = 2$, the inequality follows.

This reminds me a similar problem, by Erds as well, but with a completely different solution.

Given $n$ positive integers $a_1, a_2, \ldots, a_n$, so that the least common multiple of any two of them is greater than $a_n+1$, show that
$\frac {1}{a_1}+\frac {1}{a_2}+\ldots+\frac {1}{a_n} < 2$.

With a little more effort, the $2$ can be replaced by $\frac {3}{2}$.

A with a more serious effort, you may replace it by $ \frac {31} {30}$, which is the best possible (and with a non strict inequality).

Reference :
A. Schinzel, G. Szekeres, 'Sur un problme de M. Paul Erds', Acta Sci. Math. (Szeged), 20 (1959), p.221-229.

Pierre.

The first problem, the one posted by namdung, was used in an old Romanian TST and they had a nasty and long solution, so I got scared :).

the first statement of MindFlyer is wrong...consider for example {3,5,6,7}: the sums are all distinct (0,3,5,6,7,8,9,10,11,12,13,14,15,16,18,21) but all elements are smaller than 8.
I didn't find another proof yet but I'll think of it.

Here is a hint. Prove that
\[
a_1 + \cdots + a_j \geq 2^j-1
\]
for $j = 1,2,\ldots,k$ (here, $a_1<\cdots <a_k$.) Then, show that each sequence with this property satisfies the required inequality
\[
\sum \frac{1}{a_i} < 2.
\]

i didn't think of the word hint to mean solution :)

[quote="vess"]
\[
a_1 + \cdots + a_j \geq 2^j-1
\]
[/quote]
Oh yeah, looking more carefully at my proof, that's what I was actually proving, not what I wrote above!!   :?
Thanks, Peter Scholze and vess!

Hi!
MindFlyer, could you please post your solution for the problem with divisors in this topic.
Thanks!

Ok, what we want to prove is not that difficult if we know the Abel Sumation formula :D.
First notice that, if we have a subset $S$ of ${A=[a_1, a_2,\cdots, a_k]}$, we now that \[\sum_ {x\in{S}}x\leq\sum_{x\in{A}}x\] And since there are $2^k$ posible subets of A, each with a diferent sum, then by the pigeonhole principle we get that \[\sum_{i=1}^k{a_i}\geq{2^k}\]
In the same way we show that \[\sum_{i=1}^j{a_i}\geq{2^j}\] for $j=1,2,...,k$
Then it follows that \[\sum_{i=1}^j{a_i}\geq{2^{j-1}}\]  for $j=1,..., k$
WLOG we can assume that $0<a_1<a_2<\cdots<a_n$. Also we know that
$2^0<2^1<...<2^k-1$. Combining this two we obtain $2^0a_1<2^1a_2<\cdots<2^{k-1}a_k$.
Now we have \[\frac{1}{a_1}+\cdots+\frac{1}{a_k}=\frac{2^0}{2^0a_1}+\cdots+\frac{2^{k-1}}{2^{k-1}a_k}\]
By the Abel Sumation formula (discrete analogus of integration by parts) we get:
\[\left(\frac{1}{2^0a_1}-\frac{1}{2^1a_2}\right)2^0+\left(\frac{1}{2^1a_2}-\frac{1}{2^2a_3}\right)(2^0+2^1)+\cdots+\left(\frac{1}{2^{k-2}a_{k-1}}-\frac{1}{2^{k-1}a_k}\right)(2^0+\cdots+2^{k-2})+\frac{1}{2^{k-1}a_k}(2^0+\cdots+2^{k-1})\]
Since every term of the form
$\displaystyle{\frac{1}{2^{i-1}a_i}-\frac{1}{2^{i}a_{i+1}}}$ are positive, we get that the last expression is less than or equal to \[\left(\frac{1}{2^0a_1}-\frac{1}{2^1a_2}\right)a_1+\left(\frac{1}{2^1a_2}-\frac{1}{2^2a_3}\right)(a_1+a_2)+\cdots+\left(\frac{1}{2^{k-2}a_{k-1}}-\frac{1}{2^{k-1}a_k}\right)(a_1+\cdots+a_{k-1})+\frac{1}{2^{k-1}a_k}(a_1+\cdots+a_k)\]By the Abel sumation formula, we know that the last expression is equal to: \[\frac{a_1}{2^0a_1}+\cdots+\frac{a_k}{2^{k-1}a_k}=\sum_{i=1}^{k-1}\frac{1}{2^i}=2-\frac{1}{2^{k-1}}<2\]
And we're done (Notice that we didn't use that the $a_i$'s were integers so it works for every positive numbers :))

[quote="Leonardo"]Notice that we didn't use that the $a_i$'s were integers so it works for every positive numbers
[/quote]
You actually used it to prove that $\sum_{i=1}^k a_i \geq 2^k$.

DusT: I'll post a solution for that problem as soon as I have some time, maybe tomorrow. However, you can find a proof for the weak form in Problem Solving Strategies by Engel, too.


Let be given a triangle $ABC.$ Prove that: $\sqrt{3}\sum a\le 7R+4r$

this may or may not help...divide everything by R and substitute:

sin A= a/2R

r/R=(cos A+cos B+cos C)-1

I don't understand :blush:  Could you show me your complete solution?


What is isometry in high school geometry?

Do you have one or two sample questions?

[quote="jli"][quote="bpms"]Yo man, learn to use google or something.
http://www.google.com/search?hl=en&q=isometry&btnG=Google+Search[/quote]

YES!!! PLEASE.

another website is mathworld.com.  they have everything you need to know about math.

also, make sure you check your pm's.  pm's are private messages and you can check them at the top.  im pretty sure its yellow right now because i pmed you already.[/quote]
And Wikipedia :lol:


$P ( n )$ jest najwiekszym pierwszym dzielnikem $n$, i $\varepsilon_n = \left\{\begin{array}{l} 1, \mbox{dla } P ( n ) < P ( n + 1 )\\ 0, \mbox{dla } P ( n ) > P ( n + 1 ) \end{array}\right.$.

Udowodnij ze
\[ \sum_{n = 1}^{\infty} \frac{\varepsilon_n}{2^n}  \]
jest niewymierne.

P.S: Jezeli pojawia sie jakies odpowiedzi, to mam jeszcze kilka zadan na zapleczu ;)

Jako, że problem leży sobie już jakiś czas bez odpowiedzi, może byś tak $\{x\}$ pokazał rozwiązanie (lub przynajmniej drobny szkic tegoż) ?  :)

P.S. ... i przy okazji pozostałe problemy z zaplecza zapostował - jakiś większy ruch by się zrobił od razu  :D

Musza ten problem ponownie rozwiazac, tak dawno lezy :)
Main idea byl (chyba) taki: If the thing is irrational then
For sufficently large $n$, $\varepsilon_n$ gets periodic.
This is impossible (perhaps make use of Dirichlets Theorem)...

Za uzycie angielszczyzny przepraszam: chodzi o to ze mi sie slowa placza w polskim.
(O czym swiadczy powyzsza karkolomna konstrukcja jezykowa ;))


function
algorithm
algebra proposed
algebra

For positive integers $n,$ the integer $f(n)$ is defined by the following conditions $(a),(b).$

$(a)\ f(1)=1.$
$(b)$ For any positive integers $n,$

$\begin{cases} f(2n)=f(n) \\ f(2n+1)=f(n)+1 \end{cases}$

For $1\leq n\leq 2006,$ let $M$ be the maximum value of $f(n),$ find all positive integers $n\leq 2006$ such that $f(n)=M.$

It was already posted some time ago...anyway, it's easy to show that finding every $f(n)$ in function of $f(1)=1$ we get an algorithm for changing base from $10$ to $2$


geometry
perimeter
AMC
AIME
AMC 10
AMC 10 A

Points $ A$, $ B$, $ C$, and $ D$ lie on a line, in that order, with $ AB \equal{} CD$ and $ BC \equal{} 12$.  Point $ E$ is not on the line, and $ BE \equal{} CE \equal{} 10$.  The perimeter of $ \triangle AED$ is twice the perimeter of $ \triangle BEC$.  Find $ AB$.
(A) 15/2
(B) 8
(C) 17/2
(D) 9
(E) 19/2
[img]http://www.artofproblemsolving.com/Classes/AMC/Images/2002amc10A23isos.gif[/img]

How do you prove that AE=ED and AB=CD? (I am just not seeing why they have to be equal)

<EBC=<ECB since the middle triangle is isosceles, so you can use SAS to prove it pretty easily.

I know that <EBC=<ECB and that <EBA=<ECD, but I am still unsure of which two sides you are referring to... (sorry, but I just don't see it...)

[quote="jhangil"]Points $ A$, $ B$, $ C$, and $ D$ lie on a line, in that order, with $ \boxed{AB \equal{} CD}$ and $ BC \equal{} 12$.  Point $ E$ is not on the line, and $ BE \equal{} CE \equal{} 10$.  The perimeter of $ \triangle AED$ is twice the perimeter of $ \triangle BEC$.  Find $ AB$.
[/quote]
Now is it more clear? :)

:rotfl:
Yes that does make it more clear! (I think I should start by reading the problem correctly)
By the way Brut3For3 what grade are you in?

I'm in 11th. How 'bout you?
By the way, is this an SAT problem?

I am in tenth grade, I am not really ready for the AIME yet... This is not a SAT problem and actually it's AMC 10 A #23 and that's why I was thinking that it is hard.

[hide="outline"]its easy after you drop and altitude on the small isoceles $ \triangle$ and use pythagoras[/hide]
@jhangil: buddy that means its easy!

When I was doing the problem I just "assumed" that AB=CD, but it was already given -_-; Yeah the problem was really easy, but I didn't bother to look at the problem again and freaked out because it was #23. By the way I got 8 on the Mandelbrot again ^^; because I forgot a important(easy) formula for #6... and didn't work out # 7 because I had to catch the bus.

if its important why couldnt you derive it?  :P

:blush:  Well, probably because I didn't really understand how AoPS derived it, but I'll definetly need to know the concept before the AMC. I am pretty sure you will know when you see it because I actually got pretty close, but failed.


I don't think this really matters much, but it's a tad annoying. Whenever I open a blog, either the main blog or just one entry with the comments below it, I always start from the middle of the page (gah, this is harder to explain than I thought...I hope you know what I mean), so I always have to scroll up to the top before I can read from the top down.

I'm using IE6? on a Windows XP, with the AoPS Skin. This thing didn't happen until the blogs were updated.

Does it happen with other browsers? Have you tried Firefox 2?
I'm looking at this from a Firefox 2, Opera 9 and IE7 computer and I have no such problem.

All right, I haven't had a chance to check on Firefox (I have the Mac version), but I am confirming that the same thing happens on both my XP's, using IE.

What is the url you are using? I really am not able to recreate this bug ...

Ok, I've finally been able to recreate the bug. It was an IE7 javascript problem. It is fixed now.


What is the value of the following expression:
$ 1 \minus{} 3 \plus{} 5 \minus{} 7 \plus{} 9 \minus{} \cdots \minus{} 43 \plus{} 45 \minus{} 47 \plus{} 49$ ?


algebra
polynomial
calculus
floor function
calculus computations

$ L_k(x) $ a sequence of polynomials defined by $L_0(x) = 1 $,  $L_1(x) = 1+x, L_k (x) = L_{k-1}(x) + xL_{k-2}(x) $for  $ k>=2 $.  Give an expression of  $ L_k(x)$
THanx A lOT..
I'm WaiTin' for an Answer..!!

[quote="Kent Merryfield"]Not exactly a calculus problem ...

Just running the recursion for a while (a spreadsheet helps) and looking for patterns, we see that

$L_k(x)=\sum_{j=0}^{\lfloor\frac{k+1}2\rfloor}{{k+1-j}\choose j}x^j$

Note: $L_k(1)=F_{k+1},$ where $F_n$ is the $n$th Fibonacci number.[/quote]
thanx a alot H :roll: OW CAN I thank u!!!

[quote="various"]thanx a alot H :roll: OW CAN I thank u!!![/quote]

By contributing nontrivial solutions/ideas/information in these bulletin boards.

"From each according to his abilities, to each according to his needs."


inequalities
function
rearrangement inequality

Question
[hide]$ x_{1}^{n \plus{} 1} \plus{} x_{2}^{n \plus{} 1} \plus{} \cdots \plus{} x_{n}^{n \plus{} 1} \geq \prod_{j \equal{} 1}^n x_{j} \left( \sum_{i \equal{} 1}^n x_{i} \right)$
[/hide]
By Tchebychef

$ \sum_{i \equal{} 1}^n x_{i}.x_i^{n} \geq \sum_{j \equal{} 1}^n x_{j} \frac {\sum_{i \equal{} 1}^n x_{i}^n}{n} \geq \prod_{j \equal{} 1}^n x_{j} \left( \sum_{i \equal{} 1}^n x_{i} \right)$

The 2nd part is got by applying $ AM \minus{} GM$ to the first one

[hide]
Rohit I'm disappointed at you. You have forced me to use my least favorite inequality. I was trying to prove it using weighted AM-GM but decided it wasn't worth it. If anybody has a good proof using weighted AM-GM or someother simple inequality, please post it.[/hide]

Why so much pain :D  The answer is shorter :D

Still nice :)

PM me your method da. And well 2 step solution is almost as good as a one step soln.

But the one step soln is the best n its very powerful too :D

Well actually, its very simple but nice :) Ill call you instead :D

Well doesnt it obviosly follow off by majorisation  :?: <less than 1 step, first sight solution>

Rags, what did you say  :huh:  i didnt get you there :) The soln is an elegant one step soln i told shreyas already so shre dont answer da :D

Majorisation inequality.
You can read about it on thomas mildorf packet on the inequality forum macha. :D
Its pretty powerful.
Wats ur method  :?:

thats one step dear boy :D :D Well ill wait for some more time for pardesi to finish this off :D

i don't know the 'degree' of how short or an elegant solution rohit wants if this is not it then tell me i will further simplify if possible
consider the convex,increasing function $ f(x) \equal{} x^{n}$
so we have if weights as $ \omega_{i}\equal{}\frac {x_{i}}{\sum x_{i}}$
then $ \sum w_{i}f(x_{i}) \geq f(\sum \omega_{i}x_{i}) \geq f((\prod x_{i})^{\frac {1}{n}}))$
thus done

last step follows from the increasin nature and the  RMS and AM-GM inequality

no da, that wasnt the soln i was looking for. Maybe there are more ' elegant ' methods but my method is only 1 step da :)

I think you should post your solution. Many of us have posted elegant solutions and none of them is what you had in mind. So get the cat out of the bag.

Well the answer is by the rearrangement inequality (How? :D)

That is an exercise for you to find out like given in the ncert text book :D :P

Here are some good links, for those interested folks:

http://en.wikipedia.org/wiki/Rearrangement_inequality
http://www.pims.math.ca/pi/issue2/page21-23.pdf


:ninja: Find the length of median BM in triangle ABC, where AB=5, BC=6, and AC=7 :ninja:

I say this problem is difficult. To others it may not be, but illustrates a wonderful concept.

Oh, and I will be posting more triangle problems soon...

Because I like triangles...

 :rotfl:  :starwars:  :spam: <these are awesome smileys...

Extend $ BM$ to $ B'$ so that $ BM \equal{} MB'$. Let the median $ BM \equal{} MB' \equal{} x$.
Then you have a parallelogram $ ABCB'$ with area $ 2\sqrt{9(9\minus{}5)(9\minus{}7)(9\minus{}6)}\equal{}12\sqrt{6}$ (using Heron's).
Also, $ \frac{1}{2}(7)(2x)\equal{}12\sqrt{6}\Rightarrow x\equal{}\frac{12\sqrt{6}}{7}$.

Is that right?

It is not the best way, but you can also use [url=http://www.artofproblemsolving.com/Wiki/index.php/Stewart's_Theorem]Stewart's Theorem[/url].

You get $ 5^2(3.5)\plus{}6^2(3.5)\equal{}(3.5)^2(7)\plus{}BM^2(7)$.
So $ BM \equal{} \frac{\sqrt{73}}{2}$.

RisingFlame, your solution is incorrect because the area formula you used for the parallelogram is only for quadrilaterals whose diagonals are perpendicular.

Use the fact that the sum of the squares of the sides of a parallelogram is equal to the sum of the squares of the diagonals after extending the triangle to form a parallelogram as RisingFlame suggested.

brightzhu's answer is correct!

 :rotfl:  :P  :ninja:

[url=http://www.artofproblemsolving.com/Wiki/index.php/Stewart's_Theorem]Stewart's Theorem[/url] will destroy this problem -- as it will with nearly all problems involving the length of a cevian (i.e. a line from a vertex of a triangle to the opposite side). But pay attention to math154's way to solve the problem. It is a very nice method!

There is a formula (which follows from Stewart's):

$ m_a\equal{}\frac12\sqrt{2b^2\plus{}2c^2\minus{}a^2}$

Yes, obviously. Stewart's theorem was the first thing that came to mind.

-rts2007


inequalities
linear algebra
linear algebra unsolved

Hello

In the following problem I don't understand why linear model is required

I see only one variable here

Could you have a look at it and help me

What other variables should be?

If I understand it correctly, the trick with this problem is that you cannot start handling cases before they arrive (but you can work on the leftovers from previous months). So, say, 500 cases in the first month and 100 cases in the second will require just $ 2$ lawyers (if you want to finish everything by the end of the second month) but if you exchange the numbers, you'll need $ 4$ lawyers. So, there is only one variable, but the whole point is about writing the correct set of restrictions for it.

But  still the model seems to be strange  :(

this is the answer and I don't get it what Y values represent here

The $ y$'s should be related to those leftovers I was talking about and either the authors meant something different from what I read in the problem, or the solution is incorrect. If you take this (rather uninventive) approach, the inequalities should be
$ 150x\plus{}y_1\ge 650$
$ 150x\plus{}y_2\ge 450\plus{}y_1$
and so on up to
$ 150x\ge 500\plus{}y_{11}$
plus the requirement that all $ y's$ are non-negative. The first equation here means that you complete $ 150x$ hours of casework and you have $ y_1$ hours of leftovers after the first month.

Also, I wish the book authors to recruit $ 4.45$ collaborators for their next project...  :rotfl:

Thank you very very much  :)

The solution is from answer guide so it is correct.

I 've understood that solution

I would use integer model there :roll:

[quote="Reality"]
The solution is from answer guide so it is correct.
I 've understood that solution
[/quote]
Wow, I still don't understand it the way it was written :(. I mean, take the same $ 100$ plus $ 500$ example (where we clearly need $ 10/3$ lawyers assuming that fractional lawyers are allowed). Write the book system $ 150x\equal{}100\plus{}y$, $ 150x\plus{}y\ge 500$ and try to minimize $ x$ under these (and no other) conditions. You'll get $ x\equal{}2,y\equal{}200$. Can you explain me what the book authors really meant to do for this case? (It may be useful for you too: if you can do it, then you, indeed, have a perfect understanding of what is going on but if you have trouble with it, then it may make sense to continue the discussion in this thread :)).

I couldn't find time to log on till today

As far as I understand y means here unused time. For example in January we need lawyers due to 650 hours. But employees hired at the beginning of the year can't be dismissed. so we should hire X lawyers for the whole year.  Then this X lawyers mean 150X hours. 150x shouldn't be less then 650

150x>=650  that means if we want to have an equation here we should add a variable on the right side

150X=650+y1   that y1 is surplus . hours that will not be used.

[b]
 Write the book system ,  and try to minimize  under these (and no other) conditions. You'll get . Can you explain me what the book authors really meant to do for this case?[/b]

I don't think you can take just numbers like 100 and 500.  The objective system is to minimize 150X

I think this is some kind of a disbalanced task. where you need to balance it before you solve.

still i find this task a stupid thing  :(

Thank you for your attention  :)

[quote="Reality"]
150X=650+y1   that y1 is surplus . hours that will not be used.
[/quote]
Why do they transfer to the next month then? :?

[quote]
I don't think you can take just numbers like 100 and 500.  The objective system is to minimize 150X
[/quote]
You can certainly change the numbers to whatever you want and the approach should make sense in each case. Yes, you should minimize $ X$ (or $ 150X$, that is the same).

[quote]
I think this is some kind of a disbalanced task. where you need to balance it before you solve.
[/quote]
Erm... What do you mean? :?

[quote]
still i find this task a stupid thing  :(
[/quote]
The approach taken by the book is certainly "uninventive", I agree to that.

[quote]
Thank you for your attention  :)
[/quote]
You are always welcome :).


conics
ellipse
Euler
geometry
circumcircle
projective geometry
geometric transformation

Let $ ABCD$ be convex quadrilateral inscribed a Ellipse with center $ O$. $ M,N$ are midpoint of $ AC,BD$. Through $ A,C$ draw two line $ \ell_a,\ell_c$ parallel to $ ON$, Through $ B,D$ draw two line $ \ell_b,\ell_d$ parallel to $ OM$. Let $ \ell_a$ intersect $ \ell_b,\ell_d$ at $ Q,R$, resp, $ \ell_c$ intersect $ \ell_b,\ell_d$ at $ P,S$, resp. $ AC\cap BD \equal{} I$. Let $ X,Y,Z,T$ be centroids of triangle $ IAB,IBC,ICD,IDA$. Prove that four lines $ XQ,ZS,YP,TR$ are concurrent.

[b]Lemma.[/b] $ABCD$ is a cyclic quadrilateral and $P$ is the intersection of its diagonals $AC,BD.$  Then Euler lines of $\triangle PAB,$ $\triangle PBC,$ $\triangle PCD$ and $\triangle PDA$ concur.

Let $O_a,O_b,O_c,O_d$ and $H_a,H_b,H_c,H_d$ be the circumcenters and orthocenters of $\triangle PDA,$ $\triangle PAB,$ $\triangle PBC,$ $\triangle PCD,$ respectively. We will show that $H_aO_a,H_bO_b$ and $H_cO_c$ concur, then the conclusion follows by analogous reasoning. $M,N$ are the midpoints of $PA,PB$ and $S,T$ are the orthogonal projections of $A,B$ onto $BD,AC.$ Then we have

$\frac{H_bH_c}{TH_c}=\frac{AH_b+CH_c}{CH_c}=\frac{2(NO_b+NO_c)}{CH_c}=\frac{2O_bO_C}{CH_c}$

From $\triangle PBC \sim \triangle PAD$ we get then $\frac{H_bH_c}{O_bO_c}=\frac{H_aH_b}{O_aO_b}=2 \cdot  \frac{TH_c}{CH_c}=2 \cdot \frac{SH_a}{DH_a}$

Since $H_aH_b \parallel O_cO_b$ and $H_cH_b \parallel O_aO_b,$ then  $\triangle O_aO_bO_c \sim \triangle H_aH_bH_c \ (\star)$

Define $Q \equiv H_aH_c \cap O_aO_c,$ $U \equiv AH_a \cap MO_a,$ $V \equiv BH_c \cap NO_c.$ $NO_c,$ $BH_c$ cut $H_aH_c,$ $O_aO_c$ at $E,F,$ respectively. From $(\star)$ we have $\angle EH_cF=\angle EO_cF$ $\Longrightarrow$ $E,F,O_c,H_c$ are concyclic $\Longrightarrow$ $\angle VFE=\angle VO_cH_c=\angle UO_aH_a$ $\Longrightarrow$ $EF$ is parallel to $H_aO_a.$ As a result, $\triangle UH_aO_a$ and $\triangle VEF$ are homothetic $\Longrightarrow$ $Q,U,V$ are collinear, thus $\triangle H_aH_bH_c$ and $\triangle O_aO_bO_c$ are perspective through the line $\overline{QUV}.$ By Desargues theorem, it follows that $H_aO_a,H_bO_b$ and $H_cO_c$ concur.
_____________________________________________

Back to the problem, project the circum-ellipse of $ABCD$ into a cirle $(O')$ through parallel projection. Label projected points with primes. $A,B,C,D$ go to $A',B',C',D'$ on $(O').$ Since midpoints go to midpoints under parallel projection, then centroids $X,Y,Z,T$ go to centroids $X',Y',Z',T'$ of $\triangle I'A'B',$ $\triangle I'B'C',$ $\triangle I'C'D',$ $\triangle I'D'A'.$ Parallels $\ell_a,\ell_c$ to $ON$ go to the perpendiculars from $A',C'$ to $D'B'$ and parallels $\ell_b,\ell_c$ to $OM$ go to the perpendiculars fom $B',D'$ to $A'C'$ $\Longrightarrow$ $Q',P',S',R'$ are orthocenters of $\triangle I'A'B',$ $\triangle I'B'C',$ $\triangle I'C'D',$ $\triangle I'D'A'$ $\Longrightarrow$ $X'Q',$ $Y'P',$ $Z'S',$ $T'R'$ are Euler lines of $\triangle I'A'B',$ $\triangle I'B'C',$ $\triangle I'C'D',$ $\triangle I'D'A'.$ Now, according to our previous lemma, $X'Q',$ $Y'P',$ $Z'S',$ $T'R'$ concur, thus the primitive lines $XQ,$ $YP,$ $ZS,$ $TR$ concur  as well.

Thank you dear luisgeometra, that's the way which I creat this problem :)!

About the lemma, I thing we can let  $M, N, P, Q$ be the reflections of  $P$ about the midpoints the sides $AB, BC, CD, DA$. And then the Euler  line of $\triangle PAB,$ $\triangle PBC,$ $\triangle PCD$ and $\triangle PDA$ concur. Can you prove it ?


A point object of mass m is connected to a cylinder of radius R via a massless rope. At time $ t \equal{} 0$ the object is moving with an initial velocity $ v_0$ perpendicular to the rope, the rope has a length $ L_0$, and the rope has a non-zero tension. All motion occurs on a horizontal frictionless surface. The cylinder remains stationary on the surface and does not rotate. The object moves in such a way that the rope slowly winds up around the cylinder. The rope will break when the tension exceeds $ T_m$.
I wonder if the momentum and kinetic energy of the object are conserved in this case.


group theory
abstract algebra
superior algebra
superior algebra solved

Prove that the group  $\mathbb{Q}/\mathbb{Z}$ has no proper subgroup of finite index.

Suppose that $(q_i\mathbb{Z})$ generate then take $k$ the denominator of $\prod_i q_i$ then $\frac{1}{k+1}\mathbb{Z}$ can't be generated.

More generally, a divisible abelian group $G$ (such as $\mathbb Q/\mathbb Z$) has no normal subgroups $H\lhd G$ of finite index larger than $1$. This is because such subgroups $H$ would induce an epimorphism $f: G\to G/H$, which would make $G/H$ divisible, but this is impossible, since $G/H$ is finite and non-trivial.

Thank you both
2grobber:Could you please explain what is divisible group ?

$G$ is divisible iff: For every $n\in\mathbb{N}^*$ and $x\in G$ there exists $y\in G$ such that $y^n=x$.


On their summer vacation, the Charen family flew from New York City to Raleigh and then to Atlanta on their way to New Orleans. Returning from New Orleans, they flew to St. Louis and then to Detroit on their way to New York City. According to the mileage chart below, what was the total length of the familys round-trip?

Distance Between Cities (Miles)

please see the following pdf link warm up -1 problem no 2

http://sch.ci.lexington.ma.us/~jfrost/MC/2004%20-%202005%20Warmups.pdf?FCItemID=S0133B27B

answer 3184

I can't open the link for some reason, so just add the values from NYC $ \rightarrow$ Raleigh, Raleigh $ \rightarrow$ Atlanta, Atlanta $ \rightarrow$ New Orleans, New Orleans $ \rightarrow$ St. Louis, St. Louis $ \rightarrow$ Detroit, and finally, Detroit $ \rightarrow$ NYC.

Yeah just use the chart to add all the different trips and yo will end up with 3184 if everything is done righjt


Let $ ABC$ be a fixed acute triangle. Denote $ M, N$ be the moving points on the side $ AB,AC$, such that if $ H,K$, respectively, are the projection of $ D,E$ onto $ BC$, then $ HK\equal{} \frac {1}{2} BC$. Prove that: $ (ADE)$ always goes through a fixed point, of course, it is different from $ A$. :D


limit
floor function
real analysis
real analysis unsolved

Find the limit, if there exist one:

$ \lim_{x \to 0}{x^4 \left(1 \plus{} 2 \plus{} 3 \plus{} \dots \plus{} \left\lfloor \frac {1}{x^2} \right\rfloor \right)}$,

where $ \lfloor x \rfloor$  is the floor function.

$ \frac {1}{2} \left(1 \minus{} \frac {1}{x^2}\right) < x^4\left(1 \plus{} 2 \plus{} 3 \plus{} \cdots \plus{}\left\lfloor \frac {1}{x^2} \right\rfloor  \right)\leq \frac {1}{2}\left(1 \plus{} \frac {1}{x^2}\right)$.

$ \therefore \lim_{x\to\infty} x^4\left(1 \plus{} 2 \plus{} 3 \plus{} \cdots \plus{} \left\lfloor \frac {1}{x^2} \right\rfloor  \right) \equal{} \frac {1}{2}$


algebra
polynomial
superior algebra
superior algebra unsolved

Does anybody know if the Sendov conjecture has been proven (the general case, I know the particular case of degree at most 8)? And if yes, where to find a proof?

[b]Sendov Conjecture:[/b] If $P(z) =\prod_{k=1}^{n}(z-z_{k})$ is a polynomial with all its zeros inside the closed unit disk, then each of the disks $|z-z_{k}|\leqslant 1$, $k=1, 2, \ldots, n$ must contain a zero of $P'$.

http://arxiv.org/PS_cache/math/pdf/0206/0206173.pdf

I am not sure this proof is true. If you see some wrong, please post here  :wink:


If $ X$ is path locally connected then the connected components are the same as the path connected components.

Clearly, any path-connected component lies in a connected component. We will show that if $ X$ is locally path connected, then the path-connected component is equal to the connected component containg it.
Consider a connected component $ S$ containing the path connected component $ T$, which contains a point $ x$. The set $ \{y \in S: \textrm{there exists a path from x to y} \}$ can be shown to be open and closed, and it contains $ x$, so it is the whole $ S$. In particular, $ S$ is path-connected, so $ S \equal{} T$.


probability
arithmetic sequence
geometric sequence

There is a lock with all the numbers between 0 and 39.

1. What is the probability that the three number lock combination forms an arithmetic sequence in order?

2. What is the probability that the four number lock combination forms an arithmetic sequence in order?

3. What is the probability that the three number lock combination forms a geometric sequence in order?

4. What is the probability that the four number lock combination forms a geometric sequence in order?

The numbers don't have to be distinct

Are the numbers distinct?  And do you mean in order?


[quote="moogra"]A tank contains 250 gallons of water. A specific amount of water is drained from the tank and replaced with the same amount of alcohol. The tank is thoroughly mixed. From the new mixture, the same amount of liquid is drained as before and again replaced with alcohol and thoroughly mixed. If the ratio of water and alcohol in the final mixture is 16:9 respectively, how much water now remains in the tank?[/quote]
[hide]Who cares what was added and removed, there are $\boxed{160\text{ gallons}}$ of water in the final mixture.[/hide]


Find a polynomial $ p\left(x\right)$ with real coefficients such that

$ \left(x\plus{}10\right)p\left(2x\right)\equal{}\left(8x\minus{}32\right)p\left(x\plus{}6\right)$

for all real $ x$ and $ p\left(1\right)\equal{}210$.

Let $ p(x)\equal{}a_nx^n\plus{}a_{n\minus{}1}x^{n\minus{}1}\plus{}...\plus{}a_0, a_n\not \equal{}0$, then $ a_n2^nx^{n\plus{}1}\plus{}...\equal{}8a_nx^{n\plus{}1}\to n\equal{}3$.
$ (2x\minus{}8)|p(2x)\to (x\minus{}8)|p(x)$, $ (x\plus{}10)|p(x\plus{}6)\to (x\plus{}4)|p(x)$. Therefore $ p(x)\equal{}(x\plus{}4)(x\minus{}8)(ax\plus{}b)$ and
$ (x\plus{}10)(2x\plus{}4)(2x\minus{}8)(2ax\plus{}b)\equal{}(8x\minus{}32)(x\plus{}10)(x\minus{}2)(ax\plus{}6a\plus{}b)$. It give $ a(x\plus{}2)(x\plus{}b/2a)\equal{}a(x\minus{}2)(x\plus{}6\plus{}b/a)$
or $ b\equal{}\minus{}4a$ or $ p(x)\equal{}a(x\minus{}4)(x\minus{}8)(x\plus{}4)\equal{}a(x\minus{}8)(x^2\minus{}16)$. From $ p(1)\equal{}a(\minus{}15)(\minus{}7)\equal{}210\to a\equal{}2$ or $ p(x)\equal{}2(x\minus{}8)(x^2\minus{}16).$

I have reached the same result   ..but I don't understand how did you prove that the polynomial was of degree 3...I used the fact that if I had another root I would have infinit roots reaching a contradiction...your solutions seems to be simpler and I would like you to explain me that  .Thank you!!
 :)

PD: First post!

Look at the leading coefficient. On the left it is 2^n, and on the right it is 8, so n=3

Sorry for bringing up an old post but, I have made an easy to read pdf file of the solution(In spanish) and I just want to post it, it doesn't contain any accents.

[hide="Another solution"]Let $n=\text{deg} p$ and $m$ be leading coefficient of $p(x)$. Thus the leading coefficient of $(x+10)p(2x)$ is $m\cdot2^n$ and the leading coefficient of $(8x-32)p(x+6)$ is $8m$. Thus, $n=3$.

Substituting $x=-10$ gives $p(-4)=0$. Substituting $x=-2$ gives $-48p(4)=8p(-4)=0$ so $p(4)=0$. Substituting $x=4$ gives $14p(8)=0\cdot p(10)=0$ so $p(8)=0$.

Therefore, $p(x)=a(x-4)(x+4)(x-8)$ for some $a$. Substituting $p(1)=210$ gives $a=2$. So $p(x)=2(x-4)(x+4)(x-8)$.[/hide]


Show that if $ f$ is a continuous real-valued function on the real line and if there is a constant $ c>0$ such that $ |f(x)\minus{}f(y)|>c|x\minus{}y|$ for all $ x, y\in\mathbb{R}$ then $ f(\mathbb{R})\equal{}\mathbb{R}$.

I'm pretty sure it suffices to prove that $ \mathbb{R}\subset f(\mathbb{R})$. And also for any $ x$ and positive $ k$, $ |f(x\plus{}k)\minus{}f(x)| > ck$. But how do I continue?

from $ |f(x)\minus{}f(y)|>c|x\minus{}y|$ we get that if $ f(x)\equal{}f(y)$ then $ x\equal{}y$. So $ f$ is injective.
Now $ f$ is injective and continuous, so $ f$ is strictly monotonic. Suppose that $ f$ is increases.
Then $ f(x)>cx\plus{}f(0)$ and $ f(y)<f(0)\plus{}cy$. And we get that
$ \forall A,B\ \exists x,y: \ f(x)<A, f(y)>B$. And now the statement of the problem is follows from Cauchy theorem.


Gauss
MATHCOUNTS
AMC
AIME
USA(J)MO
USAMO
absolute value

Predict the top 57 places at nats. There are the following groups:

Winner (1 choice):

Runner-up (1 choice):

Semifinalists (2):

Other cd (8):

13-20 (8):

21-30 (10):

31-40 (10):

41-57 (17):

Scoring:

41-57=1 pt each

31-40= 2pt each

21-30= 3 pt each

13-20=4pt

CD=7 pt

Semi=10 pt

Runner=15

Winner=25

Basically, you get the number of points for each prediction based on where you put them.

That is, say I have Bobby Shen as QF, me as 13-20, and siddhant as 41-57. If siddhant makes 13-20 (:rotfl:), i win, and bobby gets 13-20, i only get points for people who did as well as or better than the place I guessed. However, i get points equivalent to where i placed them, so i get one point for siddhant and 4 pts for me.

Post your predictions when ready. No picking a person more than once.

Oh by the way, you can keep editing your choices, up until the day before I leave for nats, at which point I save your final choices.

i think chestnut could make the top 57. idk any1 else

srry. Tony Zeng

I need real names, not AOPS names, and if you are stuck for people, you can go [url=http://mathcounts.org/Document.Doc?id=341]here[/url]

I propose that the person with the most gets a free pin from each other person.

Then again, the only people who will probably be able to find each other are *people's names should be placed here but I do not wish to say names*.

[hide="my predictions"]
Winner: Bobby Shen

Runner-Up: Alan *hou

SF: Darryl Wu, Jason Hyun

QF: Sam Zbarsky, Calvin Deng, Kevin Lei, Max Schindler

CD: Runpeng Liu, Eric Schneider, Lewis Chen, David Yang, Siddhant Dogra, Mark Sellke, Victor Wang, Joshua Brakensiek

13-20: Peter Xu, Jonathan Tidor, Aaron Clein, Donghyun Choi, Alexander Clifton, Yury Aglyamov, Victoria Xia, Edward Park

21-30: Steven Chen, Lilly Shen, Alexander DiLauro, Ray Li, Matthew Tan, Kevin Zhou, Hirsh Jain, Scott Wu, Patrick Liscio, Brian Cai

31-46: Cindy Zhao, *other people*[/hide]

I think xpmath forgot to include Shyam :!:

I do not know anything about Shyam other than he got first place in Kansas. Which doesn't necessarily mean I should put him on my list.

[hide="My predictions"]Winner: Who cares?

Runner-Up: Arnav Tripathy

SF: Richard Rusczyk, David Patrick

QF: Barack Obama, George W. Bush, John McCain, Sarah Palin

CD: who cares?

13-20: ...

21-30: lalalalala

31-46: hahahahaha[/hide]

Dang, tinytim pretty much [i]nailed[/i] all the beastly people.

yo this is completely accurate, okay?

[hide]Winner: Alan Zhou

Runner-Up: Alan Zhou

SF:Alan Zhou, Alan Zhou

QF: Alan Zhou, Alan Zhou, Alan Zhou, Alan Zhou

CD: Alan Zhou, Alan Zhou, Alan Zhou, Alan Zhou, Alan Zhou, Alan Zhou, Alan Zhou, Alan Zhou

13-20: Alan Zhou x 8

21-30: Alan Zhou x 10

31-46: Alan Zhou x 16

46-228: Alan Zhou x I'm too lazy to calculate.[/hide]

also why do you have your sister beating me, mewto?

EDIT: OH DANG WE GET PINS IF WE HAVE A LOT ACCURATE okay I'll do this seriously.

[hide]Winner: Alan Zhou

Runner-Up: Bobby Shen

SF: Calvin Deng, Jason Hyun

QF: Sam Zbarsky, Siddhant Dogra, Darryl Wu, Runpeng Liu

CD: David Yang, Lewis Chen, Vincent (Victor) Zhou (Wang), Peter Xu, who by the way sucks, is extremely fat, fails at math, shouldn't have made nationals, and likes to cut his fingers just to watch the blood drip into small salt shakers.

13-20: Mark Selke, Eric Schneider, Alexander Clifton, Joshua Brakensiek, Yur(i/y) whatever, Jonathan Tidor, Kevin Lei, Aaron Clein.

21-30: Donghuyun Choi, Steven Chen, Lilly Shen, Alexander DiLauro, Edward Park, Kevin Zhou, Victoria Xia, Scott Wu, Patrick Liscio, Max Schindler.

31-46: Brian Cai, Cindy Zhao, Matthew Tan (note that the last two are in THAT ORDER), Hirsh Jain, Ray Li, Nolan Cooney, possibly Stella Schindler if MO's lucky.

46-227: Dunno.

228: Some kid.[/hide]

I wouldn't normally put that weird Peter Xu kid in CD, but Siddhant forced me to.

I just realized CD has 12 people  :wink: .

[hide="new predictions"]
Winner: Bobby Shen

Runner-Up: Alan Zhou

SF: Calvin Deng, Jason Hyun

QF: Sam Zbarsky, Lewis Chen, Kevin Lei, Max Schindler

CD: Runpeng Liu, Darryl Wu, David Yang, Victor Wang,

13-20: Peter Xu, Eric Schneider, Jonathan Tidor, Aaron Clein, Alexander Clifton, Siddhant Dogra, Victoria Xia, Mark Sellke

21-30: Steven Chen, Lilly Shen, Alexander DiLauro, Tony Zeng, Yury Aglyamov Hirsh Jain, Scott Wu, Joshua Brakensiek, Edward Park, Donghyun Choi

31-46: Matthew Tan, Cindy Zhao, *other people*[/hide]

[quote="xpmath"]I just realized CD has 12 people  :wink: .

[hide="new predictions"]
Winner: Bobby Shen

Runner-Up: Alan *hou

SF: Calvin Deng, Jason Hyun

QF: Sam Zbarsky, Darryl Wu, Kevin Lei, Max Schindler

CD: Runpeng Liu, Lewis Chen, David Yang, Victor Wang,

13-20: Peter Xu, Eric Schneider, Jonathan Tidor, Aaron Clein, Alexander Clifton, Yury Aglyamov, Victoria Xia, Mark Sellke

21-30: Steven Chen, Lilly Shen, Alexander DiLauro, Matthew Tan, Siddhant Dogra, Hirsh Jain, Scott Wu, Joshua Brakensiek, Edward Park, Donghyun Choi

31-46: Cindy Zhao, *other people*[/hide][/quote]

I'm flattered

[quote="HiDN428"]vicotria xia gonna own all, lol, watch...she got perfect states, 1rst cd, 3-0 every game game cept 1-2, and 1rst team, lol[/quote]

Perfect state is ridiculously easy to get...

[quote="gauss1181"][quote="Mewto55555"][hide="My predictions"]

Winner: Bobby Shen

Runner-up: Max Schindler

SF: Hairy Darry (Darryl Wu), Jason Hyun

CD: Samuel Zbarsky, Alan *hou, Joshua Brakensiek, Runpeng Liu, Mark Sellke, Eric Schneider, Calvin Deng, David Yang

13-20: Lewis Chen, Victor Wang, Siddhant Dogra, Steven Chen, Lilly Shen, Yury ----, Albert Chu, Stella Schindler

21-30: Scott Wu, Bryan Cai, Kevin Zhou, Peter Xu, Maximillian Wang (gasp funny first name), Charlie Pasternak, Shyam Narayanan, Kevin Lei, Alfred Xue, Tony Zeng

31-40: Later

[/hide]

If I didn't include you, don't get annoyed, these are semi-random from the MC page, and if you think you are a beast and PM me, i might put you on my list. Plus order is somewhat random.[/quote]

WTF? Why is Shyam there and I'm not? Shyam and I both got a 40 at states...[/quote]

LOL Shyam beat you by a place.

[quote="xpmath"][quote="shentang"]more people who didn't make nationals should make predictions, like me :P I predict based on written, not cd cause that can vary by a lot
[hide]
1st Alan Zhou 43
1st Bobby Shen 43
4th Darryl Wu 40
cd qualifier Runpeng Liu 37
cd qualifier Victor Wang 37
cd qualifier Ray Li 36
cd qualifier Peter Xu 36
Jonathan Tidor 34
Aaron Klein 33
David Fink 32

I think the nationals test will not be that hard. Just like I when I thought states would be hard because chapter was easy, it wasn't. So many would expect nationals to be hard but I think it will still be easy.

[/hide]

[/quote]

Ok I am fine with all of that but why do you have Ray above me? He can destroy me in anything except Mathcounts, but still.[/quote]

Hah reviving this thread is funny.

[quote="Maybach"][quote="pythag011"]Dude mathcounts is pointless, ok?

MOP = 2093158092p5y23p78o6qu3pew79rtea78790rwwqy08ty3oyt4qy34u34u3t1434uio345pu52345098152345234-23452345-845328234590345724395732409674302986708934 * |Mathcounts| (absolute value since mathcounts is negative value.)[/quote]

Mathcounts is awesome for people like me who can't do proofs and isn't very smart.   :oops:[/quote]

Way to mix up your singular/plural forms of verbs. It should be "and aren't very smart."

I was about to say, even saying "ain't" would be more acceptable.

I did that on purpose!  That was to show I am not very smart.

whoa. quite amusing, looking back at predictions.

hello

why would one participate in MathCounts?

buzzer11

Hello

I participate because:

I stink at AIME
I stink at USAMO even more because I can't do proofs
I like showing off my math "skills" to my really sucky school

Maybach

hi

I should really get off the MO forum

Maybach


vector
linear algebra
matrix
linear algebra unsolved

Hi

Let Mn(C) be the space vector of matrix nxn on the complex field.
Let E be a subspace vector of Mn(C) such that every A in E is diagonalizable.

I wonder if we can say something on E.

I hope that there's an invertible matrix P such that PEP^{-1} is included in the (n-dimension) space vector of diagonal matrix, but i do not have a clue if it's true.

Rafik

[quote="Rafik"]I hope that there's an invertible matrix P such that PEP^{-1} is included in the (n-dimension) space vector of diagonal matrix, but i do not have a clue if it's true.[/quote]No. As counterexample take the subspace of hermitian $ n\times n$-matrices.

Note that $ E$ is necessarily a commutative sub-algebra of $ M_n(\mathbb C)$ such that the matrices in $ E$ are [b]simultaneously[/b] diagonalizable.

Thank you,

but the set of hemitian nxn matrix is a subspace vector on the field R and not on the field C.
In fact, if lambda is complex (and not real) and A is a non trivial hermitian matrix then lambda A is not hermitian.

You noticed an important point : if E is a subspace vector of diagonalizable matrix of Mn(C) then we study the equivalent views :

1) every A,B in E hold AB=BA

or

2) the elements of A are simultaneous diagonalizable

[quote="Rafik"]but the set of hemitian nxn matrix is a subspace vector on the field R and not on the field C.[/quote]That's right. I was a bit hasty this morning.  :o

Hermitian matrices aren't a subspace- complex multiplication breaks them.
Now, if the field is $ \mathbb{R}$, the symmetric matrices are an obvious maximal choice.

Over $ \mathbb{C}$, I don't even see how to construct two matrices that don't commute with every linear combination diagonalizable. It's definitely impossible for $ 2\times 2$ matrices.

[quote="jmerry"]Over $ \mathbb{C}$, I don't even see how to construct two matrices that don't commute with every linear combination diagonalizable. It's definitely impossible for $ 2\times 2$ matrices.[/quote]A rigorous argument would be interesting for this.  :roll:

Let the matrices be $ A$ and $ B$. WLOG, $ A$ is diagonal; we can add a multiple of the identity to make it $ \begin{bmatrix}a&0\\0&\minus{}a\end{bmatrix}$. Clearly, $ a$ is not zero, since $ A$ and $ B$ don't commute. Adding multiples of the identity and $ A$, we can zero the diagonal elements of $ B$, making it $ \begin{bmatrix}0&b\\c&0\end{bmatrix}$.
If either $ b$ or $ c$ is zero, $ B$ is nilpotent and not diagonalizable. If both are nonzero, $ A\plus{}\sqrt{\minus{}\frac{a^2}{bc}}B$ is nilpotent and not diagonalizable.

[quote="Third Edition"]Note that $ E$ is necessarily a commutative sub-algebra of $ M_n(\mathbb C)$ such that the matrices in $ E$ are [b]simultaneously[/b] diagonalizable.[/quote]
Then we can give an upper bound for the dimension, see http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1248585#1248585

"Over , I don't even see how to construct two matrices that don't commute with every linear combination diagonalizable."
see: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=231017
This problem has not been solved.
Perhaps JCMath knows a proof ????

loup blanc,
I do.
This is a remarkable result proved by Motzkin and Taussky in the 1950s.
You might want to look at this http://www.pnas.org/content/39/9/961.full.pdf+html?ck=nck


find all n such that:
(x+y+z)^2=nxyz have positive integer solutions

Standart problem - standart solution.

Suppose equation (x+y+z)2=nxyz has solution in positive integers x,y,z.

Let x,y,z be solution with x+y+z=minimum. Suppose WLOG x \qeq y \qeq z.
(1) x2-x(nyz-2(y+z))+(y+z)2=0 ==> x'=(y+z)2/x,y,z is another solution ==> x' \geq x \geq y.
So xx'=(y+z)2 and x,x' \geq y ==> x+x' \leq y+(y+z)2/y. From (1) we obtain x+x'=nyz-2(y+z) ==>
(2) nyz-2(y+z) \leq y+(y+z)2/y \leq 5(y+z)/2 ==>
(3) 2nyz \leq 9(y+z).

If z=1 then from (2) ny \leq 4y+4+1/y. a) y>1 then ny \leq 4y+4 ==> n \leq 6; b) y=1 then (x+2)2=nx ==> x=1,2,4 ==> n=9 or n=8.

If z>1 then from (3) we obtain 2n(y+z) \leq 9(y+z) ==> n \leq 4.

So we proved n=8,9 or n \leq 6.
Your task is to find solutions for these n (it is not too hard).


[quote="i_like_pie"]A sphere of radius 1 is concentric with a cube of side length 4. A point is randomly chosen on a face of the cube, and a second point is randomly chosen on the opposite face. What is the probability that the line connecting the two points does not intersect the sphere?[/quote]
[hide="an attempt"]
If the distance between the first point chosen and the center of that face is $ t$, then the distance between the second point chosen and the center of that face must be $ 2 \minus{} t$ or greater. (because if the first point has $ 0$ as $ t$, then the 2nd point must be $ 2$ away from the center)
The area of the possible second points is $ 16 \minus{} (2 \minus{} t)^2\pi$, so the chance is $ \frac {16 \minus{} 4\pi \plus{} 4\pi t \minus{} \pi t^2}{16}$
The chances of the first point being $ t$ away from the center increases linearly until $ t$ reaches $ 2$, then decreases linearly until it reaches $ 2\sqrt {2}$
I'm lost fromhere :(

Edit- Since the rate of increase and decrease are both linear, and the probabilities are being multiplied, then i can safely average the values for $ t \equal{} 0$ and $ t \equal{} 2\sqrt {2}$.
that is $ \frac {4 \plus{} \pi \sqrt {2} \minus{} 2\pi }{4}$
In other words, $ 53.992440774469494252264855587542 \%$

Edit2- Actually $ (2 \minus{} t)$  is negative wen $ t \equal{} 2\sqrt {2}$
I should average the values for $ t \equal{} 0$ and $ t \equal{} 2$ and add the probability that the first point lies outside the circle with radius $ 2$
$ \frac{16\minus{}4\pi \plus{} 16 \minus{} 4\pi \plus{} 4 \pi (2) \minus{} \pi (2)^2}{(16)(2)} \plus{} \frac {16 \minus{} 4\pi}{16}$
$ \frac {8 \minus{} \pi}{8} \plus{} \frac {8 \minus{} 2\pi}{8}$
$ \frac {8 \plus{} 8 \minus{} 3\pi } { 8}$
$ \frac { 16 \minus{} 3\pi }{8}$
$ \boxed{82.1903 \% }$
[/hide]


induction
function
algorithm
irrational number
number theory proposed
number theory

Hello everyone!
I saw this problem somewhere ( may be in some olympiad ):
Is it possible to divide the set of natural numbers { 1,2,3,... } into a
disjoint union of Fibbonachi sequences?
( Sequence {f(n)} is called Fibbonachi if it satisfies relation
 f(n+2)=f(n+1)+f(n) , and we do not demand that f(1)=f(2)=1 ).

[quote="pbornsztein"]It depends....
If you are asking for a finite number of Fibonacci sequences then the answer is no.
If you allow an infinite number of such sequences, the answer is yes.

Pierre.[/quote]

How can you prove it for infinite number of Fibbonachi sequences ?

Ok, I prove my claim for the infinite case (and the finite one will follow). An infinite case allows a long post :D

First define $f(n)$ to be the nearest integer to $n \phi$, where $\phi = \frac { 1 +\sqrt 5} 2$ is the golden mean. Since it is an irrational number, there is no integer $n$ such that $n \phi = m + \frac 1 2$ where $m$ is an integer, so that $f$ is well-defined.

From $(n+1) \phi - n \phi > 1$ we deduce that $f(n+1) > f(n)$, which means that $f$ is increasing.
Note that $f(1) =2$, and from $\phi ^2 = \phi + 1$ it follows that :
$|f(f(n)) - f(n) - n | \leq |f(f(n)) - \phi f(n) | + (\phi - 1) |f(n) - \phi n| \leq \frac 1 2 + (\phi - 1) \frac 1 2 < 1$
Since the leftmost term is an integer, we deduce that $f(f(n)) = f(n) + n.$ (1)

Now, let $f^{k+1} = fof^k$ where $f^0 = id$.
From (1), we deduce that for all $a$, the sequence $a,f(a),f(f(a)), \cdots, f^k(a), \cdots, $ is a Fibonacci sequence.

From above we easily see that $f(n) > n$ for all $n$, so that $f^k(n) \geq n$ for all $k,n$.

Let $S_1$ be the above sequence for $a= a_1 = 1$.
Let $a_2$ be the least integer which is not a term of $S_1$. Then $a_2 = 4$, and we define $S_2$ to be the sequence for $a=a_2$.
Let $p > 0$ be an integer. Assume that $S_1, \cdots, S_p$ has been defined. If each positive integer belongs to one of these sequence, we stop. Otherwise, let $a_{p1}$ be the least integer which is not a term of the preceeding sequences, and define $S_{p+1}$ to be the sequence with $a=a_{p+1}$.

First, note that each sequence is a Fibonacci one, that each positive integer belongs to at least one of the sequences, and that no integer appear twice in the same sequence.

Now, we prove that no integer belongs to two distinct sequences :
Assume that there is a common term to $S_i$ and $S_j$ with $i>j$ (and then $a_i > a_j$ from our construction). Then, there are integers $m,n$ such that $f^n(a_i) = f^m(a_j)$. Wlog, we may assume that $n$ is minimal for which such a $m$ does exist.
- If $n,m > 0$ then since $f$ is injective we deduce that $f^{n-1}(a_i) = f^{m-1}(a_j)$, which contradicts the minimality of $n$.
- If $n=0$ then $a_i = f^m(a_j)$ so that $a_i$ is a term of $S_j$. From our construction, it leads to $i < j$ (otherwise, $S_i$ would never start at $a_i$). A contradiction.
- If $m = 0$ then $a_j = f^n(a_i) \geq a_i$, a contradiction.

Therefore, the sequences are pairwise disjoints.

It remains to prove that the above construction gives an infinite number of sequences $S_i$.
Direct checking shows that we construct at least $S_i$ for $i = 1, \cdots 13$.
An easy straightforward induction gives that for all $p \geq 13$ we have $p^2 < (\frac 3 2)^p - 1$. (1)

Now, we have :
a) For all $n>0$ : $f(n) \geq \frac {3n} 2$
b) For all $i > 0$ and $ k \geq 0$ : $f^k(a_i) \geq (\frac 3 2)^k a_i.$

Since b) follows by induction from a), we only prove a).
If $n$ is even, $\frac {3n} 2$ is an integer, thus the nearest integer to $n \phi$ is at least $\frac {3n} 2.$
If $n$ is odd then $n \phi - \frac {3n-1} 2 > \frac {3n} 2 - \frac {3n-1} 2 = \frac 1 2$. Thus $f(n) \neq \frac {3n-1} 2$ so that $f(n) \geq \frac {3n+1} 2$, and we are done.

Now, let $p \geq 13$ and assume that $S_p$ does exist.
Let $x = [(\frac 3 2)^p ]$. Thus $(\frac 3 2)^p - 1 < x < (\frac 3 2)^p.$ Moreover there are exactly $x$ positive integers less than $(\frac 3 2)^p$. Among these integers, from b), at most $p$ belong to $S_i$ for each $i=1, \cdots, p$. Therefore, the sequences $S_1, \cdots, S_p$ do not use more than $p^2$ integers in $E = \{1, \cdots , x \}$. From (1), we deduce that at least one element of $E$ is not a term of the sequences, so that the procedure above will construct $S_{p+1}$. Thus, by induction, we deduce that the number of Fibonacci sequences is not finite.

Thus, we are done in the infinite case. And the same reasoning prove that claim in the finite case.

Pierre.

Very good!
Thank you!

Did you knew this problem before or you solved it on the place?

It appeared in one of my books  :D

Pierre.

Hello there!

A long ago I have posted a problem about Fibbonachi sequences.
My solution was pretty hard, and Pierre wrote an elementary solution.
Again, my solution is hard and uses hard analysis, but I think that it is
interesting, so I attach it to this message.
If somebody is interested, please read it.

:D  :D  :D  :D  :D  :D  :D  :D

this pro is [b]IMO-SL-04[/b],too---------->leva can solve this prooooooooooooo

 :D  :D  :D  :D  :D  :D  :D  :D

Are you talking about the initial problem?

Wow! Two ISL-04 problems for me  :D

Pierre.

Wait a minute, how could this be on the ISL 2004? It is well known. One of my friends had it in an oral examination (I know, he wasn't lucky). Of course, I don't want to reduce Pierre's contribution. He has two till now.  ;)  :D  PS: isn't the ISL 2004 supposed to be known after IMO 2005?  ;)

[quote="harazi"]Wait a minute, how could this be on the ISL 2004? It is well known. [/quote]

I agree.
This is perhaps why it has not been selected by the jury.

Pierre.

No this problem cannot be IMO Shotlisted problem from 2004! I saw this problem somewhere in a national olympiad:

Estonia 2000 problem 6!!!!!

BTW Pierre, which other problem did you solved?

This one :
http://www.mathlinks.ro/Forum/viewtopic.php?t=27188

Pierre.

Anyway, does somebody want to read my proof?

[quote="pbornsztein"]It depends....
If you are asking for a finite number of Fibonacci sequences then the answer is no.
If you allow an infinite number of such sequences, the answer is yes.

Pierre.[/quote]

Pierre,  here is a simpler restatement of your construction for the infinite case.
(The finite case is clearly impossible, because a Fibonacci set has density 0).

Let $f(n)$ be the function which writes $n$ as a sum of Fibonacci numbers $F_i$ (using the greedy algorithm, i.e. use the largest possible Fibonacci number at each step), then replaces each $F_i$ with $F_{i+1}$.  Then the natural numbers can be partitioned into orbits of $f$ as in your solution.

Problem: if $S(a)$ denotes the set (orbit of $f$ starting at a) {$a,f(a), f(f(a), ... $}, and one inductively writes {$1,2,3,... $} $= S(1) \cup S(a_1) \cup S(a_2) ... $,  what is a formula for $a_n$?

[hide="Hint"] Consider $f(f(n))$.[/hide]


[quote="cdymdcool"]f(x-3)=f(x+5)  if 0 is a root, what are the other roots?[/quote]
$ f((z \plus{} 3) \minus{} 3) \equal{} f((z \plus{} 3) \plus{} 5)$
$ f(z) \equal{} f(z \plus{} 8)$

Let $ z \equal{} 0$ and you'll find that $ f(0) \equal{} f(8) \equal{} 0$. Then let $ z \equal{} 8$ to find $ f(8) \equal{} f(16) \equal{} 0$. You could also let $ z \equal{} \minus{} 8$ to get $ f(0) \equal{} f( \minus{} 8) \equal{} 0$. This process can be repeated infinitely many times, so roots occur at $ 8k$, where $ k$ is an integer. Of course, there could be more roots, but we have no way of knowing.


function
algebra
polynomial
calculus
calculus computations

Find the minimum value of the function $ 8^x\plus{}8^{\minus{}x}\minus{}4(4^x\plus{}4^{\minus{}x})$.

Here I assume $ x\in\mathbb{R}$.

We have $ f(x) \equal{} 8^{x} \plus{} 8^{ \minus{} x} \minus{} 4(4^{x} \plus{} 4^{ \minus{} x})$.

Let $ u \equal{} 2^{x} \plus{} 2^{ \minus{} x}$.

Hence, $ f(x) \equal{} 8^{x} \plus{} 8^{ \minus{} x} \minus{} 4(4^{x} \plus{} 4^{ \minus{} x}) \equal{} u^{3} \minus{} 4u^{2} \minus{} 3u \plus{} 8 \equal{} g(u)$

The global minimum of $ g$ is $ \minus{} \infty$ but it occurs when $ u\rightarrow \minus{} \infty$.

However, $ u \equal{} 2^{x} \plus{} 2^{ \minus{} x}\geq 2,\forall x\in\mathbb{R}$ and $ g'(u) \equal{} 3u^{2} \minus{} 8u \minus{} 3 \equal{} (3u \plus{} 1)(u \minus{} 3)$.

So $ g$ is an decreasing function on $ (2,3)$, increasing function on $ (3,\infty)$.

We also know that all polynomials are continuous.

$ \therefore f_{\min} \equal{} g(3) \equal{} \minus{} 10$

Thank you very much kunny :lol:


A random number selector can only select one of the ten integers $0,1,2,\ldots 9$, and it makes these selections with equal probability. Determine the probability that after $n$ selections $(n > 1)$, the product of the $n$ numbers selected will be divisible by $10$.

edit: whew, changed 9 to 10 now. my mistake.

Since a number needs to be either 0 or have both factors 2 and 5 in order to be divisible by 10:
1-(8/10)^n should be the answer, picking from (1,2,3,4,6,7,8,and 9)

huh? where'd you get $(8/10)^n$? (I understand that you're trying to count the complement but what are you taking as the complement?)

Anyways, I seem to be getting $1 - (9/10)^n - (5/9)^n - (8/9)^n + (4/9)^n$. But I don't know if that's correct or not either...since I don't have the solutions.

[quote="agolsme"]A random number selector can only select one of the [b]nine [/b]integers $0,1,2,\ldots 9$, and it makes these selections with equal probability. Determine the probability that after $n$ selections $(n > 1)$, the product of the $n$ numbers selected will be divisible by $10$.[/quote]

Nine or Ten ? ( 0 to 9 makes 10? )

[hide]Anyway assuming its 10, just find that it will be divisible by 2 (= $(1-(1/2)^n$   and probality that it will be divisible by 5 would be (=$(1-(4/5)^n$  rest is easy.. [/hide]

What if 0 is chosen? Maybe you have the chance of a multiple of 2 is $\frac{2}{5}$ and the chance of 0 is $\frac{1}{10}$ and then do the same thing you were doing, since if any of the terms is 0 then it automatically works.

[hide]Let $P$ be this probability. Then $1-P$ is the probability that the product is not divisible by 10, which means that the number is either not divisible by 2 or by 5.

To not be divisible by 2, none of the numbers are even, which has $(1/2)^n$ probability. Similarly, to not be divisible by 5, none of the numbers are either 0 or 5, which has $(4/5)^n$ probability.

To subtract off what was overcounted, the probability of getting neither an even product nor a one divisible by 5 must be accounted for. Since all numbers generated must be 1,3,7,9, there is $(2/5)^n$ probability.

So $1-P=(1/2)^n+(4/5)^n-(2/5)^n\Rightarrow P=\boxed{1+(2/5)^n-(1/2)^n-(4/5)^n}$.[/hide]

Yeah...

[hide]

So, $P(D) = 1 - P(NOT)$.

$P(NOT) = (3/5)^n + (9/10)^n - (1/2)^n$

Reason: If the number isn't divisible by $n$, it either has no factor of $2$, or no factor of $5$. Because we don't want to overlap, we subtract the products with no factors of $2$ or $5$ from that total, using PIE.

So $P(D) = 1 + (1/2)^n - (3/5)^n - (9/10)^n$.

However, it seems, the actual answer may be $P(D) * (9/10)^{n-2}$ to account for the fact that if there can't be a $0$ in the final product.

I tried it for a few low values and it seems to work.

[/hide]

[quote="JBL"]In the original problem, 0 was not an option.  (This was question 3 of 5 from the 1972 USAMO.)  Presumably, agolsme wants the 0 to be included but forgot to change "nine" to "ten."  Everyone who has posted an answer so far is wrong :-)[/quote]

Actually, if it's according to the real problem, which came from USAMO 1972, the solution would be 1-(4/5)^n-(5/9)^n+(2/5)^n


calculus
function
integration
search
algebra
domain
real analysis

Find the function $y=y(x)$ which can makes
\[T=\int_{(x_{1},y_{1})}^{(x_{2},y_{2})}\frac{ds}{\sqrt{2g(y_{1}-y)}}=\int_{x_{1}}^{x_{2}}\frac{\sqrt{1+y'^{2}}}{\sqrt{2g(y_{1}-y)}}\, dx \]
minimum and, find the minimum value also, where $y_{i}=y(x_{i})$.

Moreover, what is calculus of variations?

In English the phrase us usually "calculus of variations." Try searching in various places for the words in that order. In general, the calculus of variations is the search for functions which provide maxima or minima for [i]functionals[/i], where by "functional," we mean a function whose domain is some set of functions satisfying certain properties on a certain interval and whose codomain is the real numbers.

If I'm not mistaken, your problem is the brachistichrone problem - Johann Bernoulli's famous public challenge. Here's the physical model: Find the shape of a frictionless wire along which a bead can slide from one point to another in minimum time. $T,$ the value of the functional, is the elapsed time. And that for it to be Bernoulli's original problem, that $g$ in the denominator is not a function, it is merely a constant (the acceleration of gravity.)

Historically, this problem came first; the more general field of calculus of variations was developed as generalizations of this first problem.

Thank you for your answer, Prof. Kent Merryfield. :)
I fixed the phrase, and I also learned something. :lol:
Besides, what should we know before learning calculus of variations? And when do students study it usually?