function
induction
probability
expected value
combinatorics unsolved
combinatorics

Given is a permutation of $ 1,2,...,n$. At each step, we choose a number which isn't in the correct place (the supposed order is $ 1,2,...,n$) and put it in the correct place, leaving other numbers in the same order. (For example, if the sequence is $ 1,4,3,2$ and we choose $ 4$, it becomes $ 1,3,2,4$) Can this process go on indefinitely?

For a permutation $ p$, consider a function $ f(p) \equal{} \sum_{j \equal{} 1}^n |p_j \minus{} j|$, i.e., the sum of absolute differences of elements and their positions in $ p$.
In the sorting process this function never increases but occasionally can decrease. It is clear that $ f(p)\geq 0$ and $ f(p) \equal{} 0$ only if the permutation $ p$ is sorted.
In an infinite sorting this function must take a constant non-zero value after some step.

Suppose that there exists an infinite sorting process and let $ n$ be the smallest possible integer that admits such an infinite sorting.

Let $ x$ be the smallest elements that jumps infinite number of times. Then after some step in the sorting process no element smaller than $ x$ jumps at all and the function $ f(p)$ does not decrease. Without loss of generality assume that this happens straight from the beginning of the sorting process (simply by ignoring everything what happened before).

Since $ x$ jumps infinite number of times, it takes its correct place in the permutation an infinite number of times. However, it can leave its correct place only if there exists an element larger than $ x$ somewhere before $ x$ (whose jump would shift $ x$ from its correct place). Therefore, there exists an element $ y$ smaller than $ x$ somewhere after $ x$.

Since $ y < x$, it never jumps itself and can be shifted by jumps of other elements only towards the end of the permutation (as otherwise $ f(p)$ would decrease). But this way it cannot be shifted infinitely many times, so after some point $ y$ takes a fixed place in the permutation.
As soon as that happened, the sorting can be considered as two independent sortings -- at the left hand side of $ y$ and at the right hand side of $ y$ since no element jumps across $ y$ from one "half" to the other. Moreover, sorting of the left "half" must be infinite as it contains $ x$. Renaming the elements at the left hand side of $ y$ will give a permutation on smaller number of elements that admits an infinite sorting, a contradiction to the minimality of $ n$.
This contradiction proves that no infinite sorting is possible.

Another approach:

Alternatively, we can take $ y \equal{} 1$ right away (without considering any $ x$) and notice that if it ever takes its correct place then we have an infinite sortings of the remaining $ n \minus{} 1$ elements, a contradiction to the minimality of $ n$. Otherwise, $ y$ will be shifted towards the end of the permutation and sooner or later will take a fixed position, again splitting the permutation into two smaller ones, at least one of which will be subject to infinite sorting in contradiction to the minimality of $ n$.

Three follow-up questions (none of which are guaranteed to be nice):

1) Suppose a "deranged sorter" attempts to sort a permutation $ w \in S_n$ using the largest number of steps possible.  What is this number, and for what permutation is it maximized?

2) What is the minimal number of steps necessary to sort a given permutation $ w \in S_n$?  (I.e., can it be expressed in terms of any other "nice" statistics of $ w$?  What is the average value of this over all permutations in $ S_n$?

3) If you sort a permutation $ w$ randomly (choosing the number to which to apply a step uniformly at random), what is the expected number of necessary steps?

[quote="JBL"]1) Suppose a "deranged sorter" attempts to sort a permutation $ w \in S_n$ using the largest number of steps possible.  What is this number, and for what permutation is it maximized?[/quote]
Numerical experiments suggest that the maximum number of steps is $ 2^{n \minus{} 1} \minus{} 1$ and it is attained, in particular, for a permutation $ (n,1,2,\dots,n \minus{} 1)$ (as well as for its symmetric counterpart $ (2,3,\dots,n,1)$).

Cool -- I bet we could derive that this is an upper bound from your proof (perhaps show that a given subset of $ \{1, 2, \ldots, n\}$ can be the set of fixed points of at most one permutation we visit while performing a sequence of steps on $ w$, for example?).  Though what I just parenthetically proposed wouldn't show that those two permutations are actually the ones that maximize.

I'm not sure how to get this tight upper bound from my proof since it uses certain assertions that are true only for infinite sortings.
But here is a simple way to show that the number $ 2^{n \minus{} 1} \minus{} 1$ is attainable (not proving its maximality though) - I'll illustrate it for $ n \equal{} 5$:
51234
51243
51324
51342
52134
52314
52341
15234 - this is equivalent to the order 4 permutation 4123 which can be sorted in $ 2^3\minus{}1 \equal{} 7$ steps:
15243
15324
15342
12534
12534
12354
12345
Hence, the attainability of $ 2^{n\minus{}1}\minus{}1$ can be proved by induction on $ n$.

Let $ f(n)$ be the number in question and let $ g(n)$ be the longest we can possibly go before one of 1 or $ n$ ends up in its natural position.  Then it's immediate that $ f(n) \leq g(n) \plus{} f(n \minus{} 1) \plus{} 1$, so it is enough to argue that $ g(n) \leq f(n \minus{} 1)$.  This seems reasonably intuitive (somehow 1 and $ n$ just "hang along for the ride"), and I can easily show it for the permutations you've singled out.  It's not immediatly obvious to me how to say it for the general case, but I'll give it some more thought this afternoon.

If anybody is interested, the proof of the upper bound was given in Russian forum: [url]http://dxdy.ru/post190583.html#p190583[/url]

There was also conjectured a more general statement: if we select any $ k$ numbers out of $ n$ and move only the selected numbers, following the same rules, then we cannot make more than $ 2^k\minus{}1$ moves.


Putnam
algebra
polynomial
floor function
calculus
derivative
linear algebra

Let $ k$ be a positive integer. Prove that there exist polynomials $ P_0(n),P_1(n),\dots,P_{k\minus{}1}(n)$ (which may depend on $ k$) such that for any integer $ n,$
\[ \left\lfloor\frac{n}{k}\right\rfloor^k\equal{}P_0(n)\plus{}P_1(n)\left\lfloor\frac{n}{k}\right\rfloor\plus{} \cdots\plus{}P_{k\minus{}1}(n)\left\lfloor\frac{n}{k}\right\rfloor^{k\minus{}1}.\]
($ \lfloor a\rfloor$ means the largest integer $ \le a.$)

A solution by explicit construction of the polynomials $ P_i$:

$ P_i(x)\equal{}\frac{(\minus{}k)^i}{i!}\frac{d^i}{dx^i} \left(\frac{(\minus{}1)^{k\minus{}1}}{k^k}x(x\minus{}1)(x\minus{}2)\cdots (x\minus{}k\plus{}1)\right)$.
Extending the definition naturally gives $ P_k(x)\equal{}\minus{}1$.

For any integer $ n$, we can write $ n\equal{}k\left\lfloor\frac nk\right\rfloor\plus{}b\equal{}ka\plus{}b$ for some integer $ a$ and $ b\in \{0,1,\dots,k\minus{}1\}$. We therefore want to show $ P_0(ka\plus{}b)\plus{}aP_1(ka\plus{}b)\plus{}\dots\plus{}a^{k\minus{}1}P_{k\minus{}1}(ka\plus{}b)\minus{}a^k\equal{} \sum_{i\equal{}0}^{k}a^iP_i(ka\plus{}b)\equal{}0$ for all $ a$ and for any $ b\in \{0,1,\dots,k\minus{}1\}$.

We prove this by manipulating the sum:
$ \sum_{i\equal{}0}^{k}a^iP_i(ka\plus{}b)\equal{}\sum_{i\equal{}0}^k\sum_{j\equal{}0}^{k\minus{}i} a^i P_i^{(j)}(ka)\cdot\frac{b^j}{j!}$ (Taylor's theorem for polynomials; all higher derivatives are zero)
$ \equal{}\sum_{i\equal{}0}^k\sum_{j\equal{}0}^k P_0^{(i\plus{}j)}(ka)\cdot\frac{(\minus{}k)^i}{i!}\cdot \frac{b^j}{j!}\cdot a^i\equal{} \sum_{i\equal{}0}^k \sum_{j\equal{}0}^{k\minus{}i} \frac1{(i\plus{}j)!}\binom{i\plus{}j}{i}(\minus{}ka)^ib^jP_0^{(i\plus{}j)}(ka)$
Substituting $ m\equal{}i\plus{}j$ and rearranging,
$ \sum_{i\equal{}0}^{k}a^iP_i(ka\plus{}b)\equal{}\sum_{m\equal{}0}^k \frac1{m!}P_0^{(m)}(ka) \sum_{i\equal{}0}^m \binom{i\plus{}j}{i}(\minus{}ka)^ib^j$
$ \equal{} \sum_{m\equal{}0}^k \frac1{m!}P_0^{(m)}(ka)\cdot (b\minus{}ka)^m \equal{}P_0(ka\plus{}b\minus{}ka)\equal{}P_0(b)\equal{}0$ by the binomial theorem and Taylor again.

I did not solve this one but my friend got such an elegant proof that I must post it here.

Consider
\[ \left(\left\lfloor \frac{n}{k}\right\rfloor \minus{} \frac{n}{k}\right)\left(\left\lfloor \frac{n}{k} \right\rfloor \minus{} \frac{n\minus{}1}{k}\right)...\left(\left\lfloor \frac{n}{k} \right\rfloor \minus{} \frac{n\minus{}k\plus{}1}{k}\right)\]

Obviously this is equal to 0. (consider mod k) done!

Wow, that kind of makes the problem trivial... impressive  :o

I checked, Its the official solution as well!! haha why is a problem B5?? made me think its hard so i didn't attempt it.

http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/2007s.pdf

[quote="Xevarion"]I didn't solve this one, but you can also consider all of the cases $ n \equiv m \mod k$ and obtain a system of equations in which the variables are the polynomials. The corresponding matrix turns out to be a Vandermonde matrix, and you're basically done from there.[/quote]

Yeah I thought of that approach and wrote some random stuff in the last 5 minutes haha... good to know I at least was going in a profitable direction.

[quote="powerchess"]...the official solution...[/quote]There is nothing official about those solutions. The site is run by Kiran Kedlaya, who is not affiliated with the Putnam. It is of course a far better resource than the official site.

It's not too hard to go from that expression to mine- which version you got was mostly about how you approached the problem.
I took a fairly complicated route, solving $ k\equal{}2$ by linear algebra, guessing based on that answer, and tweaking the guess based on the data for $ k\equal{}3$ (a power of $ k$ became a factorial).

Assume that $x=\left\lfloor \frac{n}{k} \right\rfloor \text{ denote as }[\alpha]$.

It follows that $x$ must be equal to exactly one of the numbers $$n/k, (n-1)/k, (n-2)/k, \dots, (n-k+1)/k.$$ So we have $$(x-n/k)(x-(n-1)/k)\dots (x-(n-k+1)/k)=0.$$

Now just expand the product and bring $x^k$ to one side of the equation, to obtain the following equation:
$$x^k=P_1(n)+P_1(n)x+P_2(n)x^2+\dots +P_{k-1}(n)x^{k-1},$$

Now due to $[\alpha]$ the claim follows. $\blacksquare$

Can someone enlighten me how one would come up with the above magical approaches? My idea was to consider $\{ ka + i \}$ for $0 \le i \le k - 1$, and you claim that it holds for all $a \in \mathbb{R}$ instead of integers and you will get something like
\begin{align*}
x^k &= P_0(kx) + P_1(kx) x + \dots + P_{k - 1}(kx) x^{k - 1} \\
\left(  x - \frac{1}{k} \right)^k &= P_0(kx) + P_1(kx) \left( x - \frac{1}{k} \right) + \dots + P_{k - 1}(kx) \left( x - \frac{1}{k} \right)^{k - 1} \\
\left( x - \frac{2}{k} \right)^k &= P_0(kx) + P_1(kx) \left( x - \frac{2}{k} \right) + \dots + P_{k - 1} (kx) \left( x - \frac{2}{k} \right)^{k - 1} \\ \vdots \\
\left( x - \frac{k - 1}{k} \right)^{k - 1} &= P_0(kx) + P_1(kx) \left( x - \frac{k - 1}{k} \right) + \dots + P_{k - 1}(kx) \left( x - \frac{k - 1}{k} \right)^{k - 1}
\end{align*}
I have no idea how to continue this solution -- but I believe that the above system of solutions will give a solution of polynomials that satisfy the desired conclusion. Can anyone continue my approach, I think something like determinant should work, but I have no idea how it translates to polynomial.


Find all positive odd integers  $n$ for which there exist odd integers $x_{1},x_{2},...,x_{n}$ such that $x_{1}^{2}+x_{2}^{2}+...+x_{n}^{2}=n^{4}$

Some progress:
Letting $x=x_{1}= x_{2}= \ldots = x_{n}$ gives us
$n x^{2}= n^{4}$
$x^{2}= n^{3}$
So every $n = q^{2},x_{i}= q^{3}$ are solutions.
Another observation:
Since $x_{i}$ are odd:
$x_{1}^{2}+x_{2}^{2}+\ldots x_{n}^{2}\equiv n \equiv n^{4}\mod 8$
So the solutions must satisfy:
$n \cong 1 \mod 8$

If $a$ and $b$ are solutions, $ab$ is solution too.

Every odd integer in form $8n+1$ hold equality? Or only odd squares hold?

Every odd squares hold, and if $n$ holds, then $n$ is from the form $8k+1$. I'm not saying neither every odd in form $8k+1$ nor only the odd squares - there may be a non-square form the form $8k+1$ which holds. That's why my prevoius post was only observations, not a solution.


[quote="warut_suk"]A finite number of real numbers are written along a circle. If some four successive numbers a,b,c,d satisfy (a-d)(b-c)>0, we can exchange b and c. Prove that it is impossible to perform infinitely many such permutations.[/quote]
$(*)(a-d)(b-c)<0 \to ab+cd<ac+bd$
now name the numbers around the circle $a_1,...,a_n$ now assume the sum over the product of every consecutive numbers around the circle and name it $S$
so $S=a_1a_2+a_2a_3+...+a_na_1$
now if for numbers $a,b,c,d$ we had $(a-d)(b-c)<0$ then we would change the place of $b,c$ so the two elements $ab+cd$ in $S$ turn into $ac+bd$ but from $(*)$ we know that $ab+cd<ac+bd$ so in each step $S$ is being greater
in other words in each step $S$ is increasing
so because the value of $S$ is increasing in each step thus $S$ in each step earns a new value...
but we know that $n$ numbers can arrange around a circle in $(n-1)!$ different ways.
so these numbers can arrange around a circle in finite many ways...
but we proved that $S$ is increasing in each step so $S$ must earn a new value in each step such that $S$ didn't earn this value before but these permutations will end at a step because we've proved that the number of ways are finite...
got it??
 :D


ABCD yek morabba va P,Q noghaty delkhah be tartib ruye azlae CD va AB and.farz konid BP ,CQ ra dar R va AP ,DQ ra dar S ghat konad.paye amudhaye vared az  R va S bar CD ra be tartib X va Y minamim.sabet konid \[ 2XY \geq AB\]

stvs_f to kelas chandomi ?
kodoom madrese  dars mikhooni ?
lotfan javab bede ...

kelase Dovvome dabirestan az tizhooshane karaj baraye olampiad mikhunam .
(az bas soalam badihie be ta"ajob oftadin?)

Etefaghan aslan soal sade e nist . kheili sakhte ! .  (khodam ham halesh ro nemidoonam  :) )
in soale azmoon 1 hafte pish bood ke az ma gerefte boodan .
baram jaleb bood ke az koja in soal ro didi .
merc ke javab dadi .

PS : fekr konam ide hal in soal estefade az masahat bashe (motmaen nistam ) ....

  :)

jeddan? akhe soale  azmooone 1 hafte pishe ma ham bude.
(ye private message barat mizaram bekhun)

Salam . man ye rahehal daram barash vali fek konam rahe halle kootah taram dare :
mishe farz kard ke toole zel'e morabba $ 1$ hastesh hal :
$ AQ \equal{} x$ va $ DP \equal{} y$ pas $ BQ \equal{} 1 \minus{} x$ va $ CP \equal{} 1 \minus{} y$ . age do khate $ SY$ va $ SX$ ra edame bedim ta zel'e $ AB$ ro dar $ Y'$ va $ X'$ (be tartib) ghat konan oon moghe $ SY'$ va $ SX'$ ham amood mishan chon $ AB\parallel{}CD$ . pas az oonjayi ke do mosallase $ AQS$ va $ DPS$ ba ham moteshabehan pas :
$ \frac {SY}{SY'} \equal{} \frac {y}{x}$ dar natije $ \frac {SY}{SY' \plus{} SY} \equal{} \frac {y}{x \plus{} y}$ amma $ SY' \plus{} SY \equal{} 1$ pas :
$ SY \equal{} \frac {y}{x \plus{} y}$ . ama age tavvajoh konin $ \frac {SY}{AD} \equal{} \frac {PY}{y}$ ke az oonjayi ke $ AD \equal{} 1$ natije mishe :
$ PY \equal{} \frac {y^{2}}{x \plus{} y}$ .
be hamin tartib $ PX \equal{} \frac {(1 \minus{} y)^{2}}{2 \minus{} x \minus{} y}$ . hala bayad neshoon bedin jame in dota az $ \frac{1}{2}$ ke nesfe toole zele morabae bishtare ke inam kare sakhti nist mitoonin ba ye mohasebat be dast biarin . :)


inequalities
trigonometry
integration
function
limit
calculus
real analysis

Is the inequality true?
For all positive integer $ n$ and $ x \in [0,\pi]$,we have:
$ \sin x\plus{}\frac{\sin 2x}{2}\plus{}\cdots\plus{}\frac{\sin nx}{n} \le \int_0^{\pi}\frac{\sin t}{t}dt$

Define:

$ S(n,x) \equal{} \sum^{n}_{i \equal{} 1}\frac {\sin{i x}}{i}$

then:

$ \frac {\partial}{\partial x}S(n,x) \equal{} \sum^{n}_{i \equal{} 1}\cos{i x} \equal{} \frac {1}{2}\left(\cot{\frac {x}{2}}\sin{n x} \plus{} \cos{n x \minus{} 1}\right)$

then, from

$ \frac {\partial}{\partial x}S(n,x) \equal{} 0$ and some trigonometric manipulation we get that the maximum of the function is in:

$ x \equal{} \frac {2 \pi}{n}$

Therefore we have:

$ S\left(n,\frac {2 \pi}{n}\right) \equal{} s(n) \equal{} \sum^{n}_{i \equal{} 1}\frac {\sin{2 \pi\frac {n}{i}}}{i}$

It can be shown that $ s(n)$ is strictly increasing, so the maximum it can obtain is when $ n \rightarrow \infty$:

$ \lim_{n \rightarrow \infty} s(n) \equal{} \lim_{n \rightarrow \infty} \sum^{n}_{i \equal{} 1}\frac {\sin{2 \pi\frac {n}{i}}}{i}$

and this can be represented as a Riemann integral as:

$ \lim_{n \rightarrow \infty} \sum^{n}_{i \equal{} 1}\frac {1}{i}\sin{2 \pi\frac {n}{i}} \equal{} \int^{2 \pi}_{0}\frac {\sin x}{x}\,dx  \approx 1.41815$

We also have:

$ \int^{\pi}_{0}\frac {\sin x}{x}\,dx\approx 1.85194$

and so:

$ 1.41815 < 1.85194$

It's not... Try plugging $ n \equal{} 1$ in your equation and you get:

$ \sum^{1}_{i \equal{} 1}\cos{x i} \equal{} \frac {\cos x}{2}$

It's false!

[Edit:]

I was wrong. The point $ x\equal{}\frac{2 \pi}{n}$ is the closes minimum to $ x\equal{}0$. The closest maximum is $ x\equal{}\frac{\pi}{n\plus{}1}$ and then the sum approaches $ \int^{\pi}_{0}\frac{\sin x}{x}\,dx$ as $ n \rightarrow \infty$.

I am sorry
I just make something wrong by mutiply $ 2$
But I give the reason that the left can tend to the right.
The case when n tend to infinite can't cover all cases.

[quote="zhaobin"]
The case when n tend to infinite can't cover all cases.[/quote]

But if the function $ f(x)$ is strictly increasing, then the maximum it can obtain is the value $ L$ when $ x \rightarrow \infty$. Then $ \forall x \in I \rightarrow f(x) < L$ and if you need to show that $ f(x) < H$ then it's true if $ L < H$.

what is the strictly increasing function here :o?

$ s(n) \equal{} \sum^{n}_{i \equal{} 1}\frac {\sin{2 \pi\frac {n}{i}}}{i}$

I don't how to show your $ s(n)$ is strictly increasing about $ n$,But if it is true see the following
[quote="zhaobin"][quote="milin"]

$ \frac {\partial}{\partial x}S(n,x) \equal{} \sum^{n}_{i \equal{} 1}\cos{i x} \equal{} \frac {1}{2}\left(\cot{\frac {x}{2}}\sin{n x} \plus{} \cos{n x \minus{} 1}\right)$

then, from

$ \frac {\partial}{\partial x}S(n,x) \equal{} 0$ [/quote]
Thank you for answer,but I don't think you are right here.
because
$ \sum^{n}_{i \equal{} 1}\cos{i x} \equal{} \frac {\sin (n \plus{} \frac 1 2)x \minus{} \sin \frac 1 2x}{2 \sin \frac 1 2x} \equal{} \frac {\sin \frac {nx} 2 \cos \frac {(n \plus{} 1)x} 2}{\sin \frac 1 2x}$
So $ \frac {\partial}{\partial x}S(n,x) \equal{} 0$
when $ x \equal{} \frac {2k \pi}{n}$ or $ x \equal{} \frac {(2k \plus{} 1) \pi}{n \plus{} 1}$

In fact if you let $ x \equal{} \frac {\pi}{n}$,the left will tend to the right when n tend to infinite.[/quote]

But from here,I have point out your maximum point is wrong.(Not only one such maximum point)
Please think it over...

I know! And I sad I was wrong in the following post and I wrote what was wrong. And hopefully corrected my self!

Here is some thought(Not solution).
We have show that:$ S(n,x)$ get maximum about $ x$ when $ x\equal{}\frac{2k\pi}{n}$ or  $ x\equal{}\frac{(2k\plus{}1)\pi}{n}$
The first case is easy to deal with because we can follow by induction.
For the second,when $ k\equal{}0$ the inequality obvious.
But how to do when $ k \ge 1$,We just have the function $ \frac{\sin x}{x}$ just decreasing in $ [0,\pi]$
I have it is not easy to do,Also I have doubt if the inequality is true?
Can somebody offer some help?Thank you.

Hello,everyone,another problem:If we let
$ f(x)\equal{}\sin x\plus{}\frac{\sin 2x}{2}\plus{}\cdots\plus{}\frac{\sin nx}{n},x \in [0,\pi]$

Can we prove that $ f(x)$ attains its maximum at $ x\equal{}\frac{\pi}{n\plus{}1}$
I think it is still nice.

Hello,I wonder if someone has noticed  this problem :?:
Is it easy or hard?


algebra
difference of squares
special factorizations

You misread the problem.  It's $ 32^2 \minus{} 18^2$

Here's how to do it fast:
We know the difference of squares is $ x^2 \minus{} y^2 \equal{} (x \plus{} y)(x \minus{} y)$, so plug in these values.
$ (32 \plus{} 18)(32 \minus{} 18) \equal{} 50*14 \equal{} 700$


[quote="Hustla25"]ABCD is a rectangular sheet of paper. E and F are points on AB and CD
respectively such that BE < CF. If BCFE is folded over EF, C maps to
point C’ on AD and B maps to B’ such that (angle)AB’C’ congruent to (angle)B’EA. If AB’ = 5 and
BE = 23, then the area of ABCD can be expressed as a+b(c^1/2) square units,
where a, b, and c are integers and c is not divisible by the square of any
prime. Compute a + b + c.[/quote]

[hide="hint"]
AB'C' is similar to AEB', C'B'EF is congruent to CBEF.  Don't forget either.

[/hide]


White has a king on e1 and 8 pawns on a2, b2, ..., h2.
black has only the king, on e8.

the white wants to make 8 queens, black king wants to avoid this plan.

black king takes a pawn or queen - black win.
checkmate or stalemate when there are less than 8 queens - black win too.

who has the winning strategy ?

Black should be able to a) capture 1 pawn or b) get checkmated/stalemated or c)get the 50 move rule

[quote="sup3rcrash3r"]there's no 50 move rule. It states that a piece is not capture or a pawn is not moved. So, every time you move a pawn, the count is reset.[/quote]
I thought it was either one. So if a pawn moves but no captures are made for 50 moves, then it is the 50 move rule and a draw.

Nope, the rule says that if 50 moves pass without a capture or a pawn push, then it is a draw.

Also, i'm pretty sure this scenario is a win for the player with the queens. Here's an outline of a strategy:

1)It's clearly easy to promote a pawn without risk of stalemate or losing a pawn. One possible way to achieve this is with a 'v' formation. WLOG, we promote either the a or h pawn. Let's say we promote the H.

2)Once a pawn is promoted to a queen, use that queen and the king to force the opponents king to the h-file, as if you were going to mate him, but don't mate. Then, promote the other pawns, being careful of stalemate.


How many [b]distinguishable[/b] rearrangements of the letters in CONTEST have both the vowels first? (For instance, OETCNST is a one such arrangements but OTETSNC is not.)

$ \textbf{(A)}\ 60\qquad
\textbf{(B)}\ 120\qquad
\textbf{(C)}\ 240\qquad
\textbf{(D)}\ 720\qquad
\textbf{(E)}\ 2520$

[hide="My Solution"]There are two vowels so there are two arrangements of them. There are five consonants, so there are 120 arrangements, except there are two T's so we divide by 2!=2 to get 60. 2*60=120.[/hide]

why isn't OTETSNC not a possible arrangement???
anyway:
[hide]we only have two vowels, so there are 2 possibility's for the first letter... then we have 5!/2! arrangements of the next five letters (there are 2 T's)... so 5!/2! *2 = 5! = 120 -> B[/hide]

[quote="shake9991"]why isn't OTETSNC not a possible arrangement??? [/quote]

The first two letters need to be vowels, not just the first.

shouldnt the answer be 240 because the vowels can be rearranged as well? So like 2*120=240?

That was accounted for in the solutions of the others. There are $ \frac{5!}{2!}\equal{}60$ ways to arrange the consonants. There are $ 2!\equal{}2$ ways to arrange the vowels. Hence, $ 60(2)\equal{}\boxed{120}$.


if a(p+q)^2 +2bpq+c=0 and a(p+r)^2+2bpr+c=0, then express q+r an qr in terms of p,a,b adn c.

$\text{If } a(p+q)^2+2bpq+c=0 \text{ and } a(p+r)^2+2bpr+c=0, \text{then express q+r an qr in terms of p,a,b and c.}$
That's in latex and it's easier to read

[hide="answer"]
the $2$nd one,
Substitute your result from the $1$st one into this,
$2ap^2+a(q+r)^2-2aqr+2p(q+r)(a+b)+2c=0$
$2ap^2+\frac{[-2p(a+b)]^2}{a}-2aqr+2p*\frac{2p(a+b)}{a}*{(a+b)}+2c=0$
and then you can solve for $qr$
[/hide]
Correct?

Thats right,how'd ya approach it cause my frind says the way i got it wont be applicable for all questions,i made some stupid assumptions and i got the nswer. :(

this was basically easy even though it took me 20min :cursing:  :cursing:  :cursing:  :cursing:  :cursing:  :cursing:  :cursing:  :cursing:  :cursing:
there is no need for an assumption
subtract the 2 equations and see what you get, factorise a bit and then you will get $q+r$ then add the 2 equations and you will get some thing, write $q^2+r^2$ as $(q+r)^2-2qr$ and substitute $q+r$ value in the equation and then you will get the value of $qr$.


MATHCOUNTS
geometry
Support
number theory
\/closed

In the next week we will be setting the schedule for our late fall classes.  One of these classes will be a 'MATHCOUNTS Problem Series'.  Our Problem Series courses will be structured more like a series of Math Jams than our current subject-oriented courses.  There will be 18 hours of instruction over 12 classes, like our regular courses, but there will not be regular homeworks (i.e. all enrollments will be 'audited').  Each class will focus on a particular subject area, with problems of varying difficulty, from chapter for warm-ups through nationals (and maybe a bit beyond for message board discussion).  The class is designed to help students prepare for MATHCOUNTS.

I post here to ask those of you *who might take the course* to let us know what times are best for you.  Tuesday and Sunday evenings are already taken by other courses.  Please do not respond if you are not considering taking the course.

The course will begin in early November and run through February, with some days off for winter holidays.  We know we won't be able to hit a time that works for everyone (though you might consider taking the class as a correspondence course - the transcripts for each class will be available to enrolled students throughout the course), but we'd like to reach as many of you as possible.

Thanks much for your input.

I will probably take the course... the best time for me would be on Saturday.

Cool.  Please also let me know which days you absolutely can't do it/which ones you can make it.

hmm...any day other than monday. ill be doing lots of extra-currics this year, so possibly anytime after 6pm would do. but on monday, 830 pm would do. oh yeah, and this is central time. ill prbly do the class, even though the warmups and chapter, and state are a bit easy, i can always pick up new concepts. but i would like the national part more. mufasa!

School hasn't started for me yet, so I don't know my after school activity schedule, but I think I can make it on any day except friday, as long as it's at or after 4:00 pm PST. I prefer Saturday, though.

Yes - there are no formal homeworks in the problem series classes, though we will be giving many extra problems on the message board that supports the class.

So is it like a problem collection that gives you one question at a time? (and give you the answer after some time?)

Not sure what you're asking here, but I'll try to answer.  The classes themselves will be just like the regular courses: a series of lessons centered around problems of varying types.  Each day we'll be tackling problems in a specific subject area (numbers, counting, algebra, word problems, geometry, etc).  The class will be a series of problems in which we explore various problem solving techniques.  Outside the class, we'll post lots of similar types of problems on the message board for students to practice on (there is a message board just for the students in that class).  Since this particular course goes through the holidays, you'll have even more message board time than usual, as we'll still stick up some practice problems through the holidays.

The students together will come up with the solutions on the message board, and the instructors will also participate to answer questions, acknowledge correct answers, and so on.

:?: So what's the difference between this and "Evaluated"?
I've never taken a course, so I'm confused about the system :?

In the subject courses, there are formal problem sets.  2 of them (at the middle and the end) are Challenge sets - they're longer and a little harder than the problem sets.  'Evaluated' students can write up all their work on the Challenge sets and send it to instructors to get feedback on.  'Audited' students can't.  We did this dual-fee structure to give cost-conscious students a chance to still participate in the classes for a reduced fee.  Full solutions are given to all the problems, and there's a message board for each class if you have questions.

You may want to take a look at the number theory class, as well.  It has some MATHCOUNTS-level material.  MCrawford can tell you more about it.

I can't :( My school starts in September and I might be too busy with all my courses, and by the time I determine if I have time to take the course or not, the course would already be started.

As for this class, do you evaluate all the non-Challenge questions or are there no interaction between the Instructer and the student via the virtual classroom.

Um, again not sure I understand your question.  In the problem series classes like this one, there are no problem sets.  All the problems are posted on the course message boards for the students to dissect.  The instructor will comment on some of the solutions.

As for interaction via the Virtual Classroom, there's plenty of that - have you been to a Math Jam?  It's a lot like that.

Mmmm...I'll get back to you in September. :)


Trivial by Minkowski's Lattice Point Theorem :D

[quote=cyborg_w][quote=individ]http://math.stackexchange.com/questions/1127654/parametrization-of-solutions-of-diophantine-equation[/quote]

I dont see how this help since RHS is constant, not variable

[quote=nhat]Let $a,b,c$ be integers different from zero.Prove that the equation $ax^{2}+by^{2}+cz^{2}=1$ has a solution in rational numbers[/quote]

maybe there is information missing in the question because I found this.
http://math.stackexchange.com/questions/1914139/the-equations-ax2by2cz2-0-and-ax2by2cz2-1[/quote]

Your link is another problem.
It says if this form has a solution, then the other. It is possible to describe any square.
Generally square shape has the property that if the solutions it is possible to describe any form.
In the other task conditions. To find a solution. That is, the parameterization of this equation. I wrote it.


modular arithmetic
superior algebra
superior algebra unsolved

Let $\ell\equiv5\pmod6$ with $l\ge5$. Is it true that $\mathbb{Z}\left[\xi\right]$ with $\xi=\text{RootOf}(x^{2}=x-\ell)$ is not euclidian?

I think I've proven it, but it's quite a bit stronger than what I needed to prove so I wonder if it's correct (reasoning is a bit long to post here).
Note that I'm sure its true for $\ell\in\{5,11,17,41\}$, but I think it's just true for all $\ell\equiv5\pmod 6$. A simple yes or no will do as I think my proof is ok. :)

you read http://www.mathlinks.ro/Forum/viewtopic.php?t=123497 , right? ;) indeed, the proof in the linked ps generalizes to your result! all these rings are not euclidian.


[quote="amirhtlusa"][hide="hint"]
take ln, and then you're done!
[hide] by chebyshev[/hide]
[/hide][/quote]
Or just wieghted $\mathrm{AM-GM}$ which follows instantly from weighted Jensen for $f(x)=\mathrm{e}^{x}$.

Or muirhead, but that's cheap...I think the chebyshev solution is the nicest.

My previous solution was obviously wrong. Here are two nother ways to prove this inequality (generalisation of [url]http://www.mathlinks.ro/Forum/viewtopic.php?t=113277[/url]):
[b]1.[/b] The function $f(t)=t\ln t$ is convex and $g(t)=\ln t$ is concave, so applying Jensen twice we get
\[\sum x_{i}\ln x_{i}\geqslant n\cdot \frac{\sum x_{i}}{n}\cdot \ln\left(\frac{\sum x_{i}}{n}\right)\geqslant \frac{\sum x_{i}}{n}\cdot \sum \ln x_{i}.\]
Raising $\mathrm{e}$ to the power of both sides gives the desired inequality.
[b]2.[/b] Let us reneumerate $x_{i}$ modulo $n$, i.e. now we consider $x_{0},\ldots,x_{n-1}$ and identify $x_{i}$ with $x_{i+n}$. By rearrangement, for any $0\leqslant j\leqslant n-1$:
\[\sum_{i}x_{i}\ln x_{i}\geqslant \sum_{i}x_{i+j}\ln x_{i}.\]
Summing this inequality over $0\leqslant j\leqslant n-1$ we obtain
\[n\sum_{i}x_{i}\ln x_{i}\geqslant \sum_{i}\left(\ln x_{i}\cdot \sum_{j}x_{j}\right)\]
which gives the desired inequality after dividing both sides by $n$ and raising $\mathrm{e}$ to thier power.

you takae it too complex. easily prove for $n=2$ then you make everything into two variables like for $n=2$ for example $x_{1}^{x_{1}-x_{2}}x_{2}^{-(x_{1}-x_{2})}\ge1$...

For any $\{i,j\}\subset \overline{1,n}\ ,\ i\ne j$ we have $x_{1}\le x_{j}\Longleftrightarrow \ln x_{i}\le \ln x_{j}\ .$

Suppose w.l.o.g. $x_{1}\le x_{2}\le \ldots \le x_{n}\ .$ From the Chebyshev's inequality obtain

$\sum_{i=1}^{n}x_{i}\cdot\sum_{i=1}^{n}\ln x_{i}\le n\cdot \sum_{i=1}^{n}\left(x_{i}\ln x_{i}\right)$ a.s.o.


Vieta
algebra
polynomial
quadratics
quadratic formula

$ 1)$ Let $ A\equal{}$ the sum of the roots of $ x^3\plus{}5x^2\minus{}6x\minus{}16\equal{}0$, $ B\equal{}$ the largest root, and $ C\equal{}$ the product of all three roots. Find $ B^A\times C$.

$ 4)$ How many negative roots does the equation $ 8x^8\plus{}6x^6\plus{}4x^4\plus{}2x^2\equal{}7x^7\plus{}5x^5\plus{}3x^3\plus{}x\plus{}1$ have?

I have no idea how to do this.

i don't really know what the name for this is. is it vieta's formula or something, but i did it this way:
[hide="a big hint"](1). we know that the factored form of the polynomial is of the form $ (x\minus{}a) \cdot (x\minus{}b) \cdot (x\minus{}c)$ where a, b, and c are the roots.
multiply it out and see what terms and coefficients compare with what we are looking for. [/hide]

[hide="one part"]i believe that -1 times the $ x^2$ coefficient is the sum of the roots. in other words, when you multiply the factored form out you get $ ...\minus{}(a\plus{}b\plus{}c) \cdot x^2...$[/hide]

hope that helps

[quote="Bicameral"]
$ 4)$ How many negative roots does the equation $ 8x^8 \plus{} 6x^6 \plus{} 4x^4 \plus{} 2x^2 \equal{} 7x^7 \plus{} 5x^5 \plus{} 3x^3 \plus{} x \plus{} 1$ have?

I have no idea how to do this.[/quote]

Hmm... Hope I do this right.
[hide]4)
$ f(x) \equal{} 8x^8 \plus{} 6x^6 \plus{} 4x^4 \plus{} 2x^2 \minus{} 7x^7 \minus{} 5x^5 \minus{} 3x^3 \minus{} x \minus{} 1$
$ f(\minus{}x) \equal{} 8x^8 \plus{} 6x^6 \plus{} 4x^4 \plus{} 2x^2 \plus{} 7x^7 \plus{} 5x^5 \plus{} 3x^3 \plus{} x \minus{}1$
Since there is only 1 change of signs- look at $ (3x^3[\plus{}] x [\minus{}]1)$, there is only 1 negative root.[/hide]

[hide="(1)"]
It's not difficult to apply the Rational Roots Theorem and a bit of trial and error to find that $ x \equal{} 2$ is a root. The remaining two roots can be found with the quadratic formula to be $ \frac{\minus{}7 \pm \sqrt{17}}{2}$, so $ B \equal{} 2$.

By Vieta's formulas, the sum of the roots is $ A \equal{} \minus{}5$, and the product of the roots is $ C \equal{} 16$. Explanation: let the roots be $ x_1, x_2, x_3$. Then $ (x \minus{} x_1)(x \minus{} x_2)(x \minus{} x_3) \equal{} x^3 \minus{} (x_1 \plus{} x_2 \plus{} x_3)x^2 \plus{} (x_1x_2 \plus{} x_1x_3 \plus{} x_2x_3)x \minus{} x_1x_2x_3$; if we compare coefficients, we see that the sum of the roots is the opposite of the coefficient of the $ x^2$ term, and the product of the roots is the opposite of the constant term. So the expression evaluates to $ 2^{\minus{}5} \cdot 16 \equal{} \frac{1}{2}$
[/hide]

[hide="(4)"]
See [url=http://www.artofproblemsolving.com/Wiki/index.php/Polynomial#Descartes.27_Law_of_Signs]Descartes Law of Signs[/url]
[/hide]


How many positive integers $ x$ are there satisfying $ x < 10^{2006}$ and $ 10^{2006}|(x^2 \minus{} x)$?

what's about $ x\equal{}\frac{1\plus{}\sqrt{1\plus{}4.10^{2006}}}{2}$ and some others similar to them? It is a positive number $ <10^{2006}$ and $ x^2\minus{}x\equal{}10^{2006}$

A change: x be positive integer  :D
Dear Rust, please give the answer (how many?)


I know this is a ridiculously simple question, but for it may concern my tests, I have to ask: Does a postive number under a square root sign mean the postive square root of this number? or both of the positive/negative square roots? As I've learnt before, it's the first; but in my maths class today, my teacher said it's the latter. I tried to explain, but she insisted her opinion. I'm not sure if I'm true, because I've learnt most of my maths in China; is this an American rule?

As I learned it [in America], if you start with the equation

$ x \equal{}\sqrt{4}$

Then $ x \equal{} 2$ (just the positive root), but if you instead have the equation

$ x^{2}\equal{} 4$

Then $ x \equal{}\pm 2$. There should be a $ \pm$ sign specified in front of the square root symbol in a problem if the problem is looking for both positive and negative roots; otherwise the principle value is assumed.

[quote="AstroPhys"]Usually taking the any even root denotes giving both the positive and negative part, unless otherwise noted.  The postive root is called the [i]principal[/i] root and it is used for things like distance where the negative answer is not applicaiton.  There are other uses of the different roots, including the imaginary roots.[/quote]

what are imarginary roots?

I think giving the original question will clarify the question:

f(x) = sqrt(x), find f(36)

My answer: f(36) = 6.  Teacher's answer: f(36)=6, -6

* sqrt(x) is x under sqrt sign

Taking square root of a number means both of its positive/negative roots; but a number (or a variable, in this case) under a square root sign just means the postive root, a.k.a. the principal root.

I can't really give any suggestions, except always writing them both...failsafe that way I guess. You can ignore negatives on certain real life problems though..

[quote="t0rajir0u"][quote="timwu"]f(x) = sqrt(x), find f(36)

My answer: f(36) = 6.  Teacher's answer: f(36)=6, -6[/quote]

Your teacher is wrong.  A function can only return one value.  See, for example, [url=http://en.wikipedia.org/wiki/Function_%28mathematics%29#Terminology.2C_notation.2C_and_examples]the Wiki article[/url].[/quote]

ur right...that wouldn't even be a function then right?

[quote="7h3.D3m0n.117"]Imaginary roots: $ \sqrt{\minus{}1}\equal{} i$. Imaginary roots are present in some quadratics. They can be graphed on an imaginary plane.[/quote]
They're present in more than quadratics  :wink:

@ timwu:
If the [i][b]original[/i][/b] problem had a $ \sqrt[even]{}$ then it is only the positive value. If the original problem had a $ variable^{even power}$ and you are solving for $ variable$ then use both. From a less strict point of view, find all the values and then try them in the original equation, remembering that $ \sqrt[even]{}$ gives only positive values.

[quote="7h3.D3m0n.117"]Imaginary roots: $ \sqrt{\minus{}1}\equal{} i$. Imaginary roots are present in some quadratics. They can be graphed on an imaginary plane.[/quote]

i knew them as imarginary numbers. i ddidnt know they had other names. and arent there also things like s-roots or something like $ ^{^{\infty}}\sqrt{5}$ or something

[quote="timwu"][quote="Kyron]@ timwu:
If the [i][b]original[/i][/b] problem had a $ \sqrt [even]{}$ then it is only the positive value. If the original problem had a $ variable^{even power}$ and you are solving for $ variable$ then use both. From a less strict point of view, find all the values and then try them in the original equation, remembering that $ \sqrt [even]{}$ gives only positive values.[/quote]

Thank you, though I can't explain it to my teacher, who holds the opinion of its opposite...[/quote][/quote]
You're very welcome. Perhaps you could show your teacher my post  :D .


algebra
polynomial
algebra unsolved
inequalities

The $ n$ roots of a complex coefficient polynomial $ f(z) \equal{} z^n \plus{} a_1z^{n \minus{} 1} \plus{} \cdots \plus{} a_{n \minus{} 1}z \plus{} a_n$ are $ z_1, z_2, \cdots, z_n$. If $ \sum_{k \equal{} 1}^n |a_k|^2 \leq 1$, then prove that $ \sum_{k \equal{} 1}^n |z_k|^2 \leq n$.

Lemma 1:Let $ x_1,x_2,..,x_n$ are positive real numbers such that $ x_i\leq 1$ for all $ i \equal{} 1,2..,n$(or $ x_i\geq 1$ for all $ i \equal{} 1,2..,n$ .We have:
$ x_1 \plus{} x_2 \plus{} .. \plus{} x_n\leq n \minus{} 1 \plus{} x_1x_2...x_n$

Lemma 2:Let polynomial $ f(x) \equal{} g(x)h(x)$($ f,g,h\in C[x]$) that:
$ f(x) \equal{} a_0x^n \plus{} a_1x^{n \minus{} 1} \plus{} ... \plus{} a_{n \minus{} 1}x \plus{} a_n$
$ g(x) \equal{} b_0x^k \plus{} b_1x^{k \minus{} 1} \plus{} ... \plus{} b_{n \minus{} 1}x \plus{} b_n$
$ h(x) \equal{} c_0x^l \plus{} c_1x^{l \minus{} 1} \plus{} ... \plus{} c_{n \minus{} 1}x \plus{} c_n$
We have:$ |b_0c_l|^2 \plus{} |c_0b_k|^2\leq |a_0|^2 \plus{} |a_1|^2 \plus{} ... \plus{} |a_n|^2$

Let $ z_1,z_2,..,z_n$ are root of polynomial $ f(x)$;$ z_1,z_2,..,z_k$ are root of polynomial $ f(x)$ such that :$ |z_i|\leq 1$ for all $ i \equal{} 1,2,..,k$;$ z_{k \plus{} 1},..,z_n$ are root of polynomial $ f(x)$ such that:$ |z_i| > 1$ for all $ i \equal{} k \plus{} 1,..,n$
Using lemma 1:we have:$ \sum_{i \equal{} 1}^{n}|z_i|^2\leq k \minus{} 1 \plus{} n \minus{} k \minus{} 1 \plus{} |z_1..z_k|^2 \plus{} |z_{k \plus{} 1}..z_n|^2$.
Using lemma 2 for $ g(x) \equal{} (x \minus{} z_1)..(x \minus{} z_k)$ and $ h(x) \equal{} (x \minus{} z_{k \plus{} 1})..(x \minus{} z_n)$
we have:$ |z_1z_2...z_k|^2 \plus{} |z_{k \plus{} 1}..z_n|^2\leq 1 \plus{} |a_1|^2 \plus{} ... \plus{} |a_n|^2\leq 2$.
This problem is proven

Very Nice Solution~ :)

this seems dumb but could you provide a proof of lemma 2?

The key is to notice $f(x)\overline{f}(1/x)$ gives the sum of squares of coefficient magnitudes, so we can "swap" roots with small magnitude to get the desired bound. This also gives an upper bound on the Mahler measure.

I am sorry, but could someone clarify what math154 means by swapping roots with small magnitude? Thank you very much!

Let's begin with the first part: "t[i]he key is to notice $f(x)\overline{f}(1/x)$ gives the sum of squares of coefficient magnitudes[/i]". It should mean:
$$ (*)\,\,\,\,\,\,\,\,\,\frac{1}{2\pi i}\oint_C \frac{1}{z}f(z)\overline{f}(\frac{1}{z})\,dz=\sum_{k = 1}^n |a_k|^2.  $$
where $C$ is the unit circle. Indeed, it follows from:
\[\frac{1}{2\pi i}\oint_C z^n\,dz =\begin{cases}1 \,,\,n=-1\\
0\,,\, n\neq -1, n\in \mathbb{Z}\end{cases}\]
See  that the LHS of (*) equals $\frac{1}{2\pi}\oint_C |f(z)|^2\,|dz|=\frac{1}{2\pi}\int_0^{2\pi}|f(e^{i\varphi})|^2 \,d\varphi$.
Now, using AM-GM, we get:

\[\frac{1}{2\pi}\int_0^{2\pi}|f(e^{i\varphi})|^2 \,d\varphi\geq \exp \left(2\left(\frac{1}{2\pi}\int_0^{2\pi}\ln\left(|f(e^{i\pi}|)\right)\,d\varphi \right)\right) =\left(M(f)\right)^2 \]
where $M(f)$ is the [url=https://en.wikipedia.org/wiki/Mahler_measure]Mahler measure[/url] of the polynomial $f$.
Let $z_1,z_2,\dots,z_m$ be the zeroes of $f$ with magnitude greater or equal to $1$. We have (using Bernouli inequality):
\[\left(M(f)\right)^2=\prod_{i=1}^m |z_i|^2\geq 1+\sum_{i=1}^m (|z_i|^2-1)=\sum_{i=1}^m |z_i|^2-m+1\]
All that together yields:
\[\sum_{i=1}^m |z_i|^2\leq m.\]
Summing up the rest $n-m$ of $z_i$'s with small magnitude, the result follows.

Cool, thank you so much for all your help, dgrozev! I don't mean to be picky, since your solution is truly amazing, but I was wondering if there is a solution without calculus?

[quote=MathPanda1]...but I was wondering if there is a solution without calculus?[/quote]
yes, there is, the one in the post #2. But what you asked was about the meaning behind this:
[quote=math154]The key is to notice $f(x)\overline{f}(1/x)$ gives the sum of squares of coefficient magnitudes,...[/quote]
and I cannot think of something that doesn't it involve some complex analysis.

Thank you very much for all your help! I was just wondering, since I wasn't able to prove the second lemma in math10's solution. I was wondering if you have a proof of that lemma? Thank you!

[quote=dgrozev]Let's begin with the first part: "t[i]he key is to notice $f(x)\overline{f}(1/x)$ gives the sum of squares of coefficient magnitudes[/i]". It should mean:
$$ (*)\,\,\,\,\,\,\,\,\,\frac{1}{2\pi i}\oint_C \frac{1}{z}f(z)\overline{f}(\frac{1}{z})\,dz=\sum_{k = 1}^n |a_k|^2.  $$
where $C$ is the unit circle. [/quote]

This is cool.  However, the right hand side is the sum of ALL normed squares of coefficients of $f$,  including the leading coefficient $1$.
So we can only get from (*) that $|z_1|^2 + \dots + |z_m|^2 \leq m+1$.


Hey,

My high school Math League club lost its after school transportation funding due to the budget cut.  Only athletic teams will be allowed to have after school trips, but I feel that is really unfair.

To keep Math League alive in my school, I've started a fundraiser to raise $1,500.  This money will be used to pay for the private cabs (large vans) that we plan on using for transportation to and from the competing schools.  With the total cost per student being $60 and 25 students in the club, we'll need $1,500.

I know members of AoPS are just as passionate about math, so I'm hoping that we will be able to receive some donations.  Please think about donating, and if you financially can not, please help me in spreading the word to others (your parents, friends, relatives).

To donate, visit:

http://www.fundable.com/groupactions/groupaction.2008-08-02.3475835549

Thanks so much in advance!


Show that for every positive integer $ n$, $ 2^{\frac{1}{2}} \cdot 4^{\frac{1}{4}} \cdot 8^{\frac{1}{8}} \cdot ... \cdot (2^n)^{\frac{1}{2^n}}<4$.

[quote="moldovan"]Show that for every positive integer $ n$, $ 2^{\frac {1}{2}} \cdot 4^{\frac {1}{4}} \cdot 8^{\frac {1}{8}} \cdot ... \cdot (2^n)^{\frac {1}{2^n}} < 4$.[/quote]

I think this is very easy ...
$ \prod_{k\equal{}1}^{n}2^\frac{k}{2^k}\equal{}2^{\sum_{k\equal{}1}^{n}\frac{k}{2^k}}\equal{}2^{2\minus{}\sum_{k\equal{}n\plus{}1}^{\infty}\frac{k}{2^k}}<2^2\equal{}4.$

hello, let $ P\equal{}2^{\frac{1}{2}}\cdot4^{\frac{1}{4}}\cdot8^{\frac{1}{8}}\cdot(2^n)^{\frac{1}{2^n}}$
from here we get
$ \ln(P)\equal{}\frac{\ln(2)}{2}\plus{}\frac{\ln(2)}{2}\plus{}\frac{3}{8}\ln(2)\plus{}\cdots\plus{}\frac{3}{8}\ln(2)\plus{}\cdots\plus{}\frac{n\ln(2)}{2^n}$
$ \ln(P)\equal{}\ln(2)\left(\frac{1}{2}\plus{}\frac{2}{4}\plus{}\frac{3}{8}\plus{}\cdots\plus{}\frac{n}{2^n}\right)$
$ \ln(P)\equal{}\ln(2)\left(\minus{}2\left(\frac{1}{2}\right)^{n\plus{}1}(n\plus{}1)\minus{}2\left(\frac{1}{2}\right)^{n\plus{}1}\plus{}2\right)<2\ln(2)$
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, let $ P \equal{} 2^{\frac {1}{2}}\cdot4^{\frac {1}{4}}\cdot8^{\frac {1}{8}}\cdot(2^n)^{\frac {1}{2^n}}$
from here we get
$ \ln(P) \equal{} \frac {\ln(2)}{2} \plus{} \frac {\ln(2)}{2} \plus{} \frac {3}{8}\ln(2) \plus{} \cdots \plus{} \frac {3}{8}\ln(2) \plus{} \cdots \plus{} \frac {n\ln(2)}{2^n}$
$ \ln(P) \equal{} \ln(2)\left(\frac {1}{2} \plus{} \frac {2}{4} \plus{} \frac {3}{8} \plus{} \cdots \plus{} \frac {n}{2^n}\right)$
$ \ln(P) \equal{} \ln(2)\left( \minus{} 2\left(\frac {1}{2}\right)^{n \plus{} 1}(n \plus{} 1) \minus{} 2\left(\frac {1}{2}\right)^{n \plus{} 1} \plus{} 2\right) < 2\ln(2)$
Sonnhard.[/quote]

This is in fact the same as by me (just write it without log-function).


Find all solutions of the following functional equation: \[f(x^{2}+y+f(y))=2y+f(x)^{2}. \]

Here's my Ugly Proof... Let given functional eq as T-eq

We know $ f$ is surjective cuz for given $ x$, $ 2y$ moves all in Real number.

Let $ f(a) \equal{} 0$ for some $ a$, take $ y \equal{} 0$ in T-eq then $ f(x^2 \plus{} f(0)) \equal{} f(x)^2$,

Thus $ f(x)^2 \equal{} f(x^2 )$, so $ f( \minus{} a) \equal{} 0$

Take $ x \equal{} 0, y \equal{} a, \minus{} a$, we get $ f(a) \equal{} 2a \plus{} f(0)^2$, $ f( \minus{} a) \equal{} \minus{} 2a \plus{} f(0)^2$ so $ a \equal{} 0$

Here, We get $ f(x) \equal{} 0 \Longleftrightarrow x \equal{} 0$

Now put $ y \equal{} \minus{} \frac { f(x)^2}{2}$, we get $ f(x^2 \minus{} \frac { f(x)^2}{2} \plus{} f( \minus{} \frac { f(x)^2}{2})) \equal{} 0$

which means $ x^2 \minus{} \frac { f(x)^2}{2} \plus{} f( \minus{} \frac { f(x)^2}{2}) \equal{} 0$ Thus $ f(p) \equal{} f(q) \Longrightarrow p^2 \equal{} q^2$

If $ f(p) \equal{} f( \minus{} p) \equal{} r$, where $ p > 0$

put $ y \equal{} 0$ in T-eq, $ f(x^2 ) \equal{} f(x)^2$ Thus $ f(x) \ge 0$ when $ x \ge 0$, Thus $ r \ge 0$

put $ y \equal{} p, \minus{} p$ in T-eq, we get $ f(x^2 \plus{} p \plus{} r ) \equal{} 2p \plus{} f(x^2)$, $ f(x^2 \minus{} p \plus{} r) \equal{} \minus{} 2p \plus{} f(x^2 )$

Put $ x \equal{} 0$ in first one, $ f(p \plus{} r) \equal{} 2p$, put $ x \equal{} \sqrt {p \plus{} r}$ in Second one, we get $ f(2r) \equal{} \minus{} 2p \plus{} f(p \plus{} r) \equal{} 0$ so $ r \equal{} 0$ means $ p \equal{} 0$

Therefore, $ f(p) \equal{} \minus{} f( \minus{} p)$

Thus $ f(p) \equal{} f(q)$ means $ p^2 \equal{} q^2$ so $ p \equal{} q$ which means $ f$ is injective

Now, take $ x \equal{} 0$ in T-eq, we get $ f(y \plus{} f(y)) \equal{} 2y$. We know $ f$ is bijective.

Thus $ y \plus{} f(y)$ moves all of real numbers. So we can set $ y \plus{} f(y) \equal{} t$ with $ \forall t \in R$

Let's reconsider about T-eq, we get $ f(x \plus{} t) \equal{} f(x) \plus{} f(t)$ with $ x\ge 0$

Then $ f(x \plus{} y) \equal{} f(|x| \plus{} x \plus{} y \minus{} |x|) \equal{} f(|x| \minus{} x) \plus{} f(y \minus{} |x|) \equal{} f(|x|) \plus{} f(x) \minus{} f(|x| \minus{} y)$

$ \equal{} f(x) \plus{} f(y)$ Thus $ f(x \plus{} y) \equal{} f(x) \plus{} f(y)$ Thus $ f(q) \equal{} kq$ for $ q \in Q$

Then $ \forall \alpha \ge 0$, $ f(x \plus{} \alpha) \equal{} f(x) \plus{} f(\sqrt {\alpha})^2 \ge f(x)$ which means $ f$ in increasing function.

$ \forall x \in R$, let two rational sequence $ (a_n), (b_n)$ which are converge to $ x$ with $ a_n < x$, $ b_n > x$ for all $ n in N$

Then $ f(a_n ) \equal{} k a_n \le f(x) \le f(b_n ) \equal{} k b_n$, so $ f(x) \equal{} kx$ for all $ x \in R$

cuz $ f(x^2 ) \equal{} f(x)^2$, $ f(1) \equal{} 1$. so we get $ f(x) \equal{} x$ for all $ x \in R$

we have $f$ is surjective and $f(0)=0$, $f(y+f(y))=2y$ and $f(x^2)=f(x)^2 $. We can $f(a)=0$ $ \Rightarrow $ $a=0$. So $g(x)=f(x)+x$ is surjective in $ g:(-\infty ,0]\rightarrow (-\infty, 0] $. For all $z\le 0$, $x\in R$, we have $f(x+z)=f(x)+f(z)$ and $f(x)=-f(-x)$ - odd function. So $g $ is surjective in all $R$. For all $x,y\ge 0$ we get that $f(x+y)=f(x)+f(y)$ and $f$ is monotone increasing.

Answer: $f(x)=x$.

$P(x,y)$ and $P(-x,y)$ give us $f(x)^{2}=f(-x)^{2}$
So $f(x)=f(-x)$ or $f(x)=-f(-x)$

Suppose that $f(0)\neq 0$,
If there exist a $t$ satisfy $f(t)=-f(-t)$
then $P(0,t)$ and $P(0,-t)$ give us $f(0)=0$, a condradiction.
Since $f(x)^{2}=f(-x)^{2}$, $f$ is even.
If there exist $p$ s.t. $f(p)\leq 0$ and $p\neq 0$
We can get that $p=0$ from $P(\sqrt{-f(p)},p)$ and $P(\sqrt{-f(p)},-p)$
So $f(x)>0$ for all non-zero real number $x$
a contracdition with $P(x,-y)$ for a sufficient large $y$

So $f(0)=0$, and it's easy to get $f(x^{2})=f(x)^{2}$ and  $f(x+y)=f(x)+f(y)$
Hence $f(x)=x$

Here is a solution by my friend and teammate [b]RAMİL JABİYEV [/b] (İ like his fe solutions that is why I post here)

Claim 1:$f (a)=0$ $\Longrightarrow$ $a=0$
Proof:Just see $P (0,a) $ and $P (0,-a) $ (Note:Here we used that $f (x)^2=f (-x)^2$) Then done...

Claim 2:$f (f (x))+f (x)=2x $
Proof:Firstly lets look at $P (x,-\frac {f (x)^2}{2}) $
which gives us $x^2-\frac {f (x)^2}{2}-f (-\frac {f (x)^2}{2})=0$.Then $P (0,-\frac {f (x)^2}{2}) $ yields that $f $ is odd.Now $P (x,-x^2) $ gives the desired relation .

Claim 3:$f(2x)=2f (x) $
Proof:Using the above claim it is nothing

Claim 3:$f (x)=x $ is a solution
Proof: $P(x,f (y)) $ and using the fact that $f $ is odd we conclude that $f $ is additive and since $f $ is bounded in some interval we get $f (x)=x $ for any $x\in R $.

[quote=tenplusten]... and since $f $ is bounded we get $f (x)=x $ for any $x\in R $.[/quote]
Quite funny  :D
"since $f(x)$ is bounded ...", we get ... an unbounded function ....
Do you think this sentence is quite consistant ?

[quote=tenplusten]$f (x^2)=f (x)^2\ge 0$ .So f is bounded in some interval :D[/quote]

According to me, each word is important in maths statements.
And "f is bounded" is not equivalent to "f is lowerbounded over $\mathbb R^+$"

With this last sentence, I do agree.

Alternative ending:
After we establish that $ 2x = f(x) + f(f(x)) $ we set $a_n = n_{th}$ iteration of $f$. Then, we get that
$a_n + a_{n-1} = a_{n-2}$ and solving the recurrence we find that $a_n = l + m(-2)^n$.
But $f$ is lowerbounded in positive reals and therefore we must have $m=0$ and $a_n = l$ which is constant.
Thus, $f(f(x))=f(x)$ and due to surjectivity we have $f(x)=x$ in positive reals.
Now choose $x$ large enough s.t. $x^2 + y + f(y) > 0$ and from the initial relation we get that $f(y)=y,  \forall y \in \mathbb{R}$


linear algebra
matrix
linear algebra theorems

It is easy to see that if $ \lambda$ is an eigenvalue of a matrix $ A$ with a corresponding eigenvector $ \vec{v}$, then $ e^{\lambda}$ is an eigenvalue of $ e^A$ with eigenvector $ \vec{v}$. What about the other direction? It is true if $ A$ is diagonalizable, but what about the case when it's not? In other words, is it true that $ e^A$ and $ A$ have the same eigenvalues, eigenvectors, and multiplicities?

It suffices to analyze the case that $ A$ is a Jordan block, which we'll write as $ \lambda I \plus{} N$ where $ N$ is the nilpotent part of the Jordan block.  $ I$ and $ N$ commute, so

$ e^{\lambda I \plus{} N} \equal{} e^{\lambda I} e^{N}$

and you know what $ e^{\lambda I}$ looks like, so it's down to figuring out what $ e^N$ is.  But of course, if $ N^n \equal{} 0$, then

$ e^N \equal{} \sum_{i\equal{}0}^{n\minus{}1} \frac{N^i}{i!}$

is a funny-looking upper triangular matrix with all $ 1$s on the diagonal.  So $ e^{\lambda}$ has the same multiplicity as $ \lambda$ and in fact I believe this implies that $ e^A$ has the same Jordan decomposition as $ A$, but with the eigenvalues modified appropriately.


In the addition shown, different letters stand for different digits. If $ O$ stands for 7, what digit does $ W$ represent? \\
 \\
$ TWO \plus{} TWO \equal{} FOUR$

O=7
R=4
U is carry-over digit
F=1
T=8 (2T+c=17, c={0,1})

8W7+8W7=17U4

2W+1=U
2W carries over.
So, W={5,6,9}
If W=5, U=1 (not good)
[b]If W=6, U=3 (good)[/b]
If W=9, U=9 (not good)

W=6.


vector
algebra
polynomial
linear algebra
linear algebra unsolved

Let $A$ and $B$ be two $n\times n$ positive definite matrices with complex coefficients, i.e. $A^*=A$, $B^*=B$, and for every non null vector $\vec x\in \mathbb{C}^n$,  $xAx^*>0$ and $xBx^*>0$ [$x^*$ is the transpose conjugate of $x=(x_1,\dots,x_n)$], prove that the coefficient of $\lambda^{n-1}$ in
\[
\det(\lambda I_n+(A+tB)^m)
\]
is a polynomial on $t$ with positive coefficients for every $m\in \mathbb{N}$, $m>2$ and $n\ge 3$.


Let $ a,$ $ b$ and $ c$ are positive numbers. Prove that:
\[ \frac{a}{b}\plus{}\frac{b}{c}\plus{}\frac{c}{a}\geq3\sqrt{\frac{a^2\plus{}b^2\plus{}c^2}{ab\plus{}ac\plus{}bc}}\]

Very nice inequality  :)

Squaring both sides , the inequality is equivalent to
$ (ab\plus{}bc\plus{}ca)(\frac{a}{b}\plus{}\frac{b}{c}\plus{}\frac{c}{a})^2\geq 9(a^2\plus{}b^2\plus{}c^2)$ or equivalently

(all the following sums are cyclic)

$ \sum\frac{a^3}{b}\plus{}\sum ab\plus{}\sum\frac{a^3c}{b^2}\plus{}\sum ab\plus{}2\sum\frac{a^2b}{c}\plus{}\sum\frac{a^2c}{b}\geq 7(a^2\plus{}b^2\plus{}c^2)$

Now by AM-GM we have that $ \sum\frac{a^3}{b}\plus{}\sum ab\geq 2(a^2\plus{}b^2\plus{}c^2)$

and $ \sum\frac{a^3c}{b^2}\plus{}\sum ab\geq 2\sum\frac{a^2c}{b}$

So we have to prove that  $ 3\sum\frac{a^2c}{b}\plus{}2\sum\frac{a^2b}{c}\geq 5(a^2\plus{}b^2\plus{}c^2)$

Also by AM-GM  $ 2\sum\frac{a^2c}{b}\plus{}2\sum\frac{a^2b}{c}\geq 4(a^2\plus{}b^2\plus{}c^2)$

we have to prove that $ \sum\frac{a^2c}{b}\geq a^2\plus{}b^2\plus{}c^2$

which is true since from VMO ineq 1991 we have $ \sum\frac{x^2y}{z}\geq x^2\plus{}y^2\plus{}z^2$   so QED  :D

[quote="silouan"]which is true since from VMO ineq 1991 we have $ \sum\frac {x^2y}{z}\geq x^2 \plus{} y^2 \plus{} z^2$   so QED  :D[/quote]
But it's wrong for positive $ x,$ $ y$ and $ z.$ ( $ x\rightarrow\plus{}\infty$ and $ y<z.$ ):wink:

[quote="arqady"][quote="NguyenDungTN"][quote="arqady"]Let $ a,$ $ b$ and $ c$ are positive numbers. Prove that:
\[ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\geq3\sqrt {\frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} ac \plus{} bc}}
\]
[/quote]

I think it can be solved by Schur-SOS method.[/quote]
Try! I don't sure. :P
I have proved it by AM-GM. :wink:[/quote]

OK :D

This is Hungkhtn's proof.

Notice that if $ a \ge b \ge c$ then
$ \left(\frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\right)\minus{}\left(\frac {b}{a} \plus{} \frac {c}{b} \plus{} \frac {a}{c}\right)\equal{}\frac{(a\minus{}b)(a\minus{}c)(c\minus{}b)}{abc} \le 0$
so it enough to consider the case $ a \ge b \ge c$
We will prove:

$ \left(\frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\right)^2 \ge 9\left(\frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} ac \plus{} bc}\right)$

Rewrite this inequality to $ M(b\minus{}c)^2\plus{}N(a\minus{}b)(a\minus{}c) \ge 0$

with
$ M\equal{}\frac{2}{bc}\plus{}\frac{(b\plus{}c)^2}{b^2c^2}\minus{}\frac{9}{ab\plus{}bc\plus{}ca}$

$ N\equal{}\frac{2}{ac}\plus{}\frac{(a\plus{}b)(a\plus{}c)}{a^2b^2}\minus{}\frac{9}{ab\plus{}bc\plus{}ca}$

If $ b\minus{}c \ge a\minus{}b$ then $ 2(b\minus{}c)^2 \ge (a\minus{}b)(a\minus{}c)$. We have

$ M\equal{}\frac{6}{bc}\minus{}\frac{9}{ab\plus{}bc\plus{}ca}>0$
$ M\plus{}2N \ge \frac{6}{bc}\minus{}\frac{18}{ab\plus{}bc\plus{}ca} \ge 0$

We conclude that

$ M(b\minus{}c)^2\plus{}N(a\minus{}b)(a\minus{}c) \ge  \frac{1}{2}(a\minus{}b)(a\minus{}c)(M\plus{}2N) \ge 0$

Now suppose that $ b\minus{}c \le a\minus{}b$ then $ 2b \le a\plus{}c$. Certainly $ M \ge 0$ and

$ N \ge \frac{2}{ac}\plus{}\frac{a\plus{}b\plus{}c}{ab^2}\minus{}\frac{9}{ab\plus{}bc\plus{}ca} \ge \frac{2}{ac}\plus{}\frac{3}{ab}\minus{}\frac{9}{ab\plus{}bc\plus{}ca} \ge \frac{(\sqrt{2}\minus{}\sqrt{3})^2}{ac\plus{}ab}\minus{}\frac{9}{ab\plus{}bc\plus{}ca}>0$

Here is my proof:
$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\geq3\sqrt {\frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} ac \plus{} bc}}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}\left(\frac {a^3}{b} \plus{}\frac {a^3c}{b^2} \plus{}2ab \plus{} \frac {2a^2b}{c} \plus{}\frac {a^2c}{b}\minus{}7a^2 \right)\geq0,$ which true by AM-GM. :lol:

[quote="arqady"]Here is my proof:
$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\geq3\sqrt {\frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} ac \plus{} bc}}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}\left(\frac {a^3}{b} \plus{} \frac {a^3c}{b^2} \plus{} 2ab \plus{} \frac {2a^2b}{c} \plus{} \frac {a^2c}{b} \minus{} 7a^2 \right)\geq0,$ which true by AM-GM. :lol:[/quote]

Very nice solution, argady. :)

Thank you very much, NguyenDungTN! I'll try it.

[quote="Anaxerzia"][quote="silouan"] $ \sum\frac {a^2c}{b}\geq a^2 \plus{} b^2 \plus{} c^2$[/quote]

Eh.. are you sure? (1,2,16) break it, I think.[/quote]
It's a cyclic sum:
$ \sum_{cyc} \frac{a^2c}{b} \equal{} \frac{a^2c}{b} \plus{} \frac{b^2a}{c} \plus{} \frac{c^2b}{a}$

$ \sum \frac{x^2y}{z} \geq \sum x^2$ is only true when $ x \geq y \geq z >0$  :)

[quote="arqady"][quote="NguyenDungTN"]

This is Hungkhtn's proof.

Notice that if $ a \ge b \ge c$ then
$ \left(\frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\right) \minus{} \left(\frac {b}{a} \plus{} \frac {c}{b} \plus{} \frac {a}{c}\right) \equal{} \frac {(a \minus{} b)(a \minus{} c)(c \minus{} b)}{abc} \le 0$
so it enough to consider the case $ a \ge b \ge c$
We will prove:

$ \left(\frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\right)^2 \ge 9\left(\frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} ac \plus{} bc}\right)$

Rewrite this inequality to $ M(b \minus{} c)^2 \plus{} N(a \minus{} b)(a \minus{} c) \ge 0$

with
$ M \equal{} \frac {2}{bc} \plus{} \frac {(b \plus{} c)^2}{b^2c^2} \minus{} \frac {9}{ab \plus{} bc \plus{} ca}$

$ N \equal{} \frac {2}{ac} \plus{} \frac {(a \plus{} b)(a \plus{} c)}{a^2b^2} \minus{} \frac {9}{ab \plus{} bc \plus{} ca}$

[/quote]
Here for all $ a \equal{} \max\{a,b,c\}$ we obtain: $ M\geq0$ and
 $ N(ab \plus{} ac \plus{} bc) \equal{} \frac {2b}{c} \plus{} \frac {2b}{a} \plus{} \frac {a}{b} \plus{} \frac {ac}{b^2} \plus{} \frac {3c}{b} \plus{} \frac {c^2}{b^2} \plus{} \frac {c^2}{a^2} \plus{} \frac {2c}{a} \plus{} \frac {2c^2}{ab} \minus{} 6 >$
$ > \frac {a}{b} \plus{} \frac {b}{a} \plus{} \frac {ac}{b^2} \plus{} \frac {c}{a} \plus{} \frac {2b}{c} \minus{} 6\geq2\left(\frac {b}{c} \plus{} \frac {c}{b}\right) \minus{} 4\geq0.$ :wink:
By the way, I have proved only that
$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\ge \sqrt {\frac {12(a^{2} \plus{} b^{2} \plus{} c^{2})}{ab \plus{} bc \plus{} ca} \minus{} 3}$ is true.
I still don't see how the Hungkhtn's way works for the following inequality:
$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\ge \sqrt {\frac {13(a^{2} \plus{} b^{2} \plus{} c^{2})}{ab \plus{} bc \plus{} ca} \minus{} 4}.$  :maybe:[/quote]

Sorry, argady. I'll try again but I think the above inequality too strong.

And agardy, What do you think about the following inequality? Can we use SS method?

$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a} \ge 3\sqrt [8]{\frac {3(a^6 \plus{} b^6 \plus{} c^6)}{(a^2 \plus{} b^2 \plus{} c^2)(a^4 \plus{} b^4 \plus{} c^4)}}$

I was posted it in box Inequality proposed and own. But it was unsolved.

[quote="arqady"]
$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\ge \sqrt {\frac {12(a^{2} \plus{} b^{2} \plus{} c^{2})}{ab \plus{} bc \plus{} ca} \minus{} 3}$ is true.
[/quote]
I don't know SS method. But for this inequality, we can use the following trivial lemma
\[ \sum \frac{a^2}{b} \ge \frac{(3\sum a^2\plus{} 2\sum ab)(\sum a) \minus{}18abc}{3\sum ab}\]
:)

[quote="arqady"]Here is my proof:
$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\geq3\sqrt {\frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} ac \plus{} bc}}\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}\left(\frac {a^3}{b} \plus{} \frac {a^3c}{b^2} \plus{} 2ab \plus{} \frac {2a^2b}{c} \plus{} \frac {a^2c}{b} \minus{} 7a^2 \right)\geq0,$ which true by AM-GM. :lol:[/quote]

I also did like this.

the inequality is from Mongolian Olympiad 2007.

[quote="NguyenDungTN"][quote="arqady"]What about the following 10_math's inequality?
For positive $ a,$ $ b$ and $ c$ prove that:
\[ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\ge \sqrt {\frac {13(a^{2} \plus{} b^{2} \plus{} c^{2})}{ab \plus{} bc \plus{} ca} \minus{} 4}
\]
[/quote]

I think we can square and use method as Hungkhtn's proof.[/quote]
Dear arqady and NguyenDungTN, we can prove this inequality after assuming that $ a\plus{}b\plus{}c\equal{}1$ and setting $ q\equal{}ab\plus{}bc\plus{}ca$, after all, we used the following lemma :)
\[ \frac{a}{b}\plus{}\frac{b}{c}\plus{}\frac{c}{a} \ge \frac{7\minus{}36q^2}{q(7\minus{}12q)}\]
:)

Thank you very much, can_hang2007! I'll check it.

[quote="can_hang2007"][quote="NguyenDungTN"][quote="arqady"]What about the following 10_math's inequality?
For positive $ a,$ $ b$ and $ c$ prove that:
\[ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}\ge \sqrt {\frac {13(a^{2} \plus{} b^{2} \plus{} c^{2})}{ab \plus{} bc \plus{} ca} \minus{} 4}
\]
[/quote]

I think we can square and use method as Hungkhtn's proof.[/quote]
Dear arqady and NguyenDungTN, we can prove this inequality after assuming that $ a \plus{} b \plus{} c \equal{} 1$ and setting $ q \equal{} ab \plus{} bc \plus{} ca$, after all, we used the following lemma :)
\[ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a} \ge \frac {7 \minus{} 36q^2}{q(7 \minus{} 12q)}
\]
:)[/quote]
very nice , can_hang2007 , the last time i did this , i tried using another lemma however it turned out to be true if and only if $ \sum a^2 \leq 207$ when q=1 , seems like that lemma was not as strong as yours  :)


The graphs of $ y\equal{}\frac{x^2\minus{}4}{x\minus{}2}$ and $ y\equal{}2x$ intersect in:

$ \textbf{(A)}\ \text{1 point whose abscissa is 2} \qquad
\textbf{(B)}\ \text{1 point whose abscissa is 0}\\
\textbf{(C)}\ \text{no points} \qquad
\textbf{(D)}\ \text{two distinct points} \qquad
\textbf{(E)}\ \text{two identical points}$

[hide]Substituting in $ 2x$ for $ y$ in the first equation gives $ 2x \equal{} \frac {x^2 \minus{} 4}{x \minus{} 2}$. Multiplying both sides by $ x \minus{} 2$ you get $ 2x^2 \minus{} 4x \equal{} x^2 \minus{} 4$, which simplifies to the quadratic $ x^2 \minus{} 4x \plus{} 4 \equal{} 0$, which is $ (x \minus{} 2)^2$ which implies that $ x \equal{} 2$, but when plugging that into the initial equation we find that there is a hole in the graph at $ x\equal{}2$, and thus the graphs intersect at no points, or $ C$.[/hide]


geometry
geometric transformation
reflection
geometry unsolved

$ \angle BOC \equal{} 100^\circ.$ See [url]http://www.mathlinks.ro/viewtopic.php?t=2[/url].

Let $ X$ be isogonal conjugate point of $ O$ wrt triangle $ ABC$. Then $ \angle XAB\equal{}10,\angle XCA\equal{}20$. Let $ D$ be reflection of $ C$ on $ AX$. Then triangle $ XCD$ is equilateral because $ \angle CXD\equal{}60,XC\equal{}XD$.Since $ \angle XCB\equal{}30$, $ D$ is reflection of $ X$ on $ BC$. From $ \angle ADC\equal{}20\plus{}60\equal{}\angle ABC$, $ A,B,C,D$ are cyclic. Hence $ \angle CBD\equal{}\angle CAD\equal{}20$. But $ D,X$ are symetric wrt $ BC$. Hence $ \angle XBC\equal{}20$ and $ \angle OBC\equal{}60$ yielding $ \angle BOC\equal{}100$.


How many three digit numbers are left if we exclude all three digit numbers in which there are exactly two digits the same, but these two digits are not adjacent? :?:

Since the two equal digits cannot be next to each other, the desired number must be of the form $ aba$, where $ a,b \in \mathbb{Z^ \plus{} }, 0 \leq b \leq 9, 1 \leq a\leq 9,$ and $ a \ne b$.  We have $ 9$ possibilities for $ a ([1,9]$) and $ 9$ possibilities for $ b ([0,9], b\ne a$). There are $ 81$ possibilities.

Our answer is then the number of three digit numbers minus $ 81$.  From $ 100 \minus{} 999$, there are $ 900$ numbers.  Our answer is $ 900 \minus{} 81 \equal{} \boxed{819}$.

[hide="solution"]
Let $ abc$ be a number such that two of it's digits are the same and they are not adjacent, so $ a$ must equal $ c$. Now that $ a \equal{} c$ we need to look for numbers in the form $ aba$, which is easy to find:

For each $ a$ there are $ 9$ solutions for $ b\in \{0,1,\cdots,9\}, b\notin \{a\}$, and since there are $ 9$ possible values for $ a\in \{1,2,\cdots,9\}$, there are in total $ 9\cdot 9 \equal{} 81$ 3-digit numbers that have two digits the same and they are not adjacent.

The total amount of 3-digit numbers is $ 900$, so the answer is $ 900 \minus{} 81 \equal{} \boxed{819}$.

Edit: Forget this, J.Mayers beat me by a minute, basicly the same exact solution.

Edit2: Thanks mathking123 it's fixed now.
[/hide]

[quote="tonypr"]
there are in total $ 9\cdot 10 \equal{} 81$ 3-digit numbers

[/quote]

You might want to fix this.


A circle with center $ O$ is tangent to the coordinate axes and to the hypotenuse of the $ 30^\circ$-$ 60^\circ$-$ 90^\circ$ triangle $ ABC$ as shown, where $ AB \equal{} 1$. To the nearest hundredth, what is the radius of the circle?
[asy]defaultpen(linewidth(.8pt));
dotfactor=3;

pair A = origin;
pair B = (1,0);
pair C = (0,sqrt(3));
pair O = (2.33,2.33);

dot(A);dot(B);dot(C);dot(O);

label("$A$",A,SW);label("$B$",B,SE);label("$C$",C,W);label("$O$",O,NW);
label("$1$",midpoint(A--B),S);label("$60^\circ$",B,2W + N);

draw((3,0)--A--(0,3));
draw(B--C);
draw(Arc(O,2.33,163,288.5));[/asy]$ \textbf{(A)}\ 2.18\qquad \textbf{(B)}\ 2.24\qquad \textbf{(C)}\ 2.31\qquad \textbf{(D)}\ 2.37\qquad \textbf{(E)}\ 2.41$

[hide]Drop a perpendicular from $ O$ to $ AC$ and call the foot $ X$. Likewise, drop a perpendicular to $ AB$ and call the foot $ Y$. Now, if we draw the radius of circle $ O$ to the tangency point $ T$ with $ BC$, $ OC$, and $ OB$, we have, by HL Congruency, $ \triangle{OBY}\cong\triangle{OBT}$ and $ \triangle{OCX}\cong\triangle{OCT}$. Hence, $ XC\equal{}CT\equal{}r\minus{}\sqrt{3}$ and $ BT\equal{}BY\equal{}r\minus{}1$. Since $ BC\equal{}2$, $ r\minus{}1\plus{}r\minus{}\sqrt3\equal{}2$, so $ r\equal{}\frac{3\plus{}\sqrt3}{2}\approx2.37\Longrightarrow\mathrm{ (D) \ }$[/hide]

Let D be the point of tangency from O to AB. Then the external angle to B is 120, so $ \angle OBD\equal{}60$. Let $ BD\equal{}x$, then $ OD\equal{}1\plus{}x$. So $ tan OBD\equal{}tan 60\equal{}\frac{x\plus{}1}{x}$. Solving, $ x\equal{}1\plus{}\frac{\sqrt{3}\plus{}1}{2}$ which is D.

[quote="Fibonacci11235"]Another way of doing this is using the excircle formula.

Calling the radius of the excircle tangent to side $ a$, $ r$.

$ r\equal{}\frac{K}{s\minus{}a}$

where $ K$ is the area of the triangle and the semiperimeter, $ s\equal{}\frac{a\plus{}b\plus{}c}{2}$

$ r\equal{}\frac{K}{\frac{a\plus{}b\plus{}c}{2}\minus{}a}$

$ r\equal{}\frac{K}{\frac{\minus{}a\plus{}b\plus{}c}{2}}$

$ r\equal{}\frac{2K}{\minus{}a\plus{}b\plus{}c}$

$ K\equal{}\frac{1}{2}\cdot 1\cdot \sqrt3\equal{}\frac{\sqrt3}{2}$

$ r\equal{}\frac{2\cdot \frac{\sqrt3}{2}}{\minus{}2\plus{}\sqrt3\plus{}1}$

$ r\equal{}\frac{\sqrt3}{\sqrt3\minus{}1}\approx2.37\Longrightarrow\mathrm{ (D) \ }$[/quote]

For the formula $ r\equal{}\frac{K}{s\minus{}a}$
Can you replace side $a$ with $b$ or $c$?

Also I have a question about Solution 2 written by AHSME:
http://grab.by/ofBk

How do they get $rx+ry+{ \sqrt3 \over 2 } =r^2$?

[quote="ssilwa"]Yes, but then the radius will have to correspond to the right excircles.[/quote]
Oh, so we use $a$ because the excircle touches hypotenuse $a$?

Yup. The proof is a very simple. (Find the area twice basically using the fact that the circle is tangent to the external angle bisectors.) Also, for your other question, just draw some right triangles. Remember, connecting tangent points to center is fruitful.


function
algebra
functional equation
Functional Equations

Find all functions $f: \mathbb{N}_{0}\to \mathbb{N}_{0}$ such that for all $m,n\in \mathbb{N}_{0}$: \[mf(n)+nf(m)=(m+n)f(m^{2}+n^{2}).\]

Solution: $ f(x)\equal{}c$ where $ c\in\mathbb{N}_{0}$ for any $ x\in\mathbb{N}_{0}$

First if we plug in $ m\equal{}0$ and $ n\equal{}1$ we get $ f(0)\equal{}f(1)$

Now, assume there exist numbers $ a,b\in\mathbb{N}_{0}$ not equal and neither equal to $ 0$ such that $ f(a)$ is not equal to $ f(b)$ wolog $ f(a)>f(b)$.
If we plug in $ a\equal{}m$ and $ b\equal{}n$ in the original equation we get: $ af(b)\plus{}bf(a)\equal{}(a\plus{}b)f(a^{2}\plus{}b^{2})$.
However, as $ f(a)>f(b)$ we have $ (a\plus{}b)f(b)<af(b)\plus{}bf(a)<(a\plus{}b)f(a)$.
Then, $ (a\plus{}b)f(b)<(a\plus{}b)f(a^{2}\plus{}b^{2})<(a\plus{}b)f(a)$, and diving through by $ a\plus{}b$ we get:
$ f(b)<f(a^{2}\plus{}b^{2})<f(a)$ but then we can just repeat this procedure with $ a$ and $ a^{2}\plus{}b^{2}$ to get another number $ c\equal{}(a^{2}\plus{}b^{2})^{2}\plus{}a^{2}$ so that $ f(b)<f(x)<f(a^{2}\plus{}b^{2})$ and we can repeat this forever and because the function is $ \mathbb{N}_{0}\to\mathbb{N}_{0}$ then we get infinitely many natural numbers in the range $ (f(b),f(a)$ which is impossible. Therefore we can never have two numbers $ a,b\in\mathbb{N}_{0}$ not equal and neither equal to $ 0$ so that $ f(a)$ is not equal to $ f(b)$. So, $ f(x)$ is constant, QED.

Let's set n=0 --> $mf(0)=mf(m^2)$ --> for all m $f(m^2)=f(0)=K$
$m+n|mf(n)+nf(m)$
also $m+n|(m+n)f(m)$
--> $m+n|m(f(m)-f(n))$
now let's take n such that $n=t^2$ & $(m,n)=1$
--> $m+n|f(m)-f(n)$
we had $f(m^2)=f(0)=K$
--> $m+n|f(m)-K$
The left hand side can get as large as we need it to be but the right hand side will remain the same therefore the righthand side should be 0.
--> The solution is $f(m)=K$ :lol:

[quote=rem]but then we can just repeat this procedure with $ a$ and $ a^{2}\plus{}b^{2}$ to get another number $ c\equal{}(a^{2}\plus{}b^{2})^{2}\plus{}a^{2}$ so that $ f(b)<f(x)<f(a^{2}\plus{}b^{2})$[/quote]

Hello,rem!I think

$c=(a^2+b^2)^2+b^2$ and $f(b)<f(c)<f(a^2+b^2)$.

Thanks.


linear algebra
matrix
vector
analytic geometry
function
superior algebra
superior algebra unsolved

Hi,

This exercise is to show that matrix rings are simple. It is set up as follow:

Let $ K$ be a field. Let $ V$ be an n-dimensional vector space over $ K$ and let $ A=\text{End}_{K}(V)$, the ring of $ n\times n$ matrices over $ K$. We need to show that the 2-sided ideals are either $ (0)$ or $ A$.

Let $ W$ be a subspace of $ V$. Then $ L_W=\{ f \in A|f(W)=0\}$ is clearly a left ideal of A. Prove that every left ideal has this form.

(Outline of 1 method) Let $ I$ be a left ideal, $ W=\{x\in V|f(x)=0\quad\forall f\in I\}$, so $ I\subset e L_W$. Let $ e_1,\dots,e_n$ be a basis of $ V$ with $ e_1,\dots,e_r$ a basis of $ W$.

a. Show that if $ f(x)$ has zero $ e_1-$coordinate for all $ f\in I$, then $ x\in W$. [Note that if $ \pi$ permutes $ e_i$ then $ \pi(f) \in I$.]

b. Note that $ H=\{e_1-$coordinate function of $ f|f\in I\}$ is a subspace of $ V^*=\text{Hom}(V,K)$. Use duality and (a) to conclude that $ H$ is the annihilator of $ W$, and so any linear function $ V\rightarrow K$ vanishing on $ W$ is in $ H$.

c. Let $ E_{ij}$ be the function taking $ e_j$ to $ e_i$ and vanishing on $ e_k$ for $ k\ne j$. Using (b) and a projection onto $ e_1$, prove that $ E_{1j}\in I$ for $ j>r$.

(there's more)

For (a), it seems that if $ f(x)$ has zero $ e_1-$coordinate for all $ f\in I$, then $ x=0$. Because
$ \pi_{1j}(f(x))=\pi_{1j}(0,\dots,x_j,\dots)=(x_j,\dots,0,\dots)=0$ (since $ \pi_{1j}(f)\in I$). So $ x_j=0$.

Am I doing something wrong here?

(b) is confusing to me since $ f(x)=0\quad\forall x\in W, f\in I$, then $ H(W)=0$...? I'm not sure how to use duality and (a) here.

For (c), how do I show that something belongs to $ I$? $ f\in I$ if $ f(W)=0$?

Thanks in advance,

The whole thing would probably be clearer if you stuck with matrices, and looked explicitly at entries.

Here's what I'd do:
Define matrices $ E_{i,j}$ with $ 1$ in the $ ij$-position and zeros otherwise.

Let $ I$ be a two-sided ideal in $ M_n(K)$ containing a nonzero matrix $ A$. Find $ i,j$ so that the $ ij$ entry $ a(i,j)$ of $ A$ is nonzero. We have that $ \frac1{a(i,j)}E_{1,i}AE_{j,1}\equal{}E_{1,1}$, so $ E_{1,1}$ is in $ I$. We have that $ E_{k,1}E_{1,1}E_{1,l}\equal{}E_{k,l}$, so $ E_{k,l}\in A$ for each $ k$ and $ l$. These are a basis for $ M_n(K)$, so $ I\equal{}M_n(K)$.

To characterize one-sided ideals, note that the row space of $ AB$ is contained in the row space of $ B$- in fact, we can make $ A$ a row, to extract any element of that row space, and stack $ n$ of those to make any matrix with all of its rows in that space. If you started with multiple generating matrices, you get the sum of those row spaces, and the ideal is generated by some matrix with its row space that sum. For the other side, exchange rows with columns.

Thanks for the reply.

However, could you follow the method used in the exercise please? I am trying to work according to the method proposed instead of just proving problem.

Again, thanks in advance.


geometry
trigonometry
projective geometry
geometry proposed

Hi, gdeskos!

It's better for us to post the problem here and attach an image instead of attaching a winword document.

Also, there is a [url=http://www.mathlinks.ro/Forum/index.php?f=4]Geometry Forum[/url] to post such problems

Χωρίς παρεξήγηση...

[quote]Let  $c ( O,r )$ be  a  circle  and  $AB$ diameter of $c$.
Let  also  any  two  points  $M,N$  on $AB$ such that  $OM=ON$ .

Let  $P$  random   point  on  the  circumference and  $R ,D$ and  $Q$  the  extension  of  $PM , PO$  and  $PN$  on  the  circumference . Joining  the  extensions  of  $AB$  and $RQ$  at  $S$ ,  prove  that   $SD$  is  a  tangent  to  the  circle  $c$  at  $D$ .[/quote]

;)  ;) :lol: Ok  .( Μου  φαίνεται  οτι  ετσι  είναι  καλύτερα . Αλήθεια  τι  απέγινε  το  Ελληνικό    Forum ;  Για  προσπάΘησε  την  λιγο την  άσκηση  αυτή . ΄Εχω  βρεί  μια  αρκετα  καλή  λυση  )

See http://www.mathlinks.ro/Forum/viewtopic.php?t=42878 (with the Pascal's theorem).

Here is a solution without the Pascal's theorem.
Denote the tangent $XX$ in the point $X\in w$ to the circle $w$.
Define the intersection $S'\in RQ \cap DD$ and  $x=m(\widehat {RPD})$, $y=m(\widehat {QRD})$.
$\frac{DR}{DQ}=\frac{\sin x}{\sin y},\ \frac{S'R}{S'Q}=\frac{DR}{DQ}\cdot \frac{\sin x}{\sin y}\Longrightarrow \boxed {\frac{S'R}{S'Q}=\left(\frac{\sin x}{\sin y}\right)^2}\ \ (1).$
$OM=ON\Longrightarrow PM\sin x=PN\sin y\Longrightarrow \frac{NP}{MP}=\frac{\sin x}{\sin y}\ .$
$DM\parallel PN$, $DN\parallel PM$ $\Longrightarrow$ $\triangle DRM\sim \triangle DQN$ $\Longrightarrow \frac{MR}{NQ}=\frac{PN}{PM}\ .$
Apply the Menelaus' theorem to the transversal $\overline {MNS}$ and the triangle $PRQ$:
$\frac{SR}{SQ}\cdot \frac{NQ}{NP}\cdot \frac{MP}{MR}=1\Longrightarrow \frac{SR}{SQ}=\left(\frac{NP}{MP}\right)^2\Longrightarrow \boxed {\frac{SR}{SQ}=\left(\frac{\sin x}{\sin y}\right)^2}\ \ (2).$
From the relations $(1)$ and $(2)$ results $S'\equiv S$, i.e. the line $DS$ is tangent to the circle.

The problem is quote]Let  $c ( O,r )$ be  a  circle  and  $AB$ diameter of $c$.
Let  also  any  two  points  $M,N$  on $AB$ such that  $OM=ON$ .

Let  $P$  random   point  on  the  circumference and  $R ,D$ and  $Q$  the  extension  of  $PM , PO$  and  $PN$  on  the  circumference . Joining  the  extensions  of  $AB$  and $RQ$  at  $S$ ,  prove  that   $SD$  is  a  tangent  to  the  circle  $c$  at  $D$ .[/quote]

and you Virgil wrote

[quote="Virgil Nicula"]
Define the intersection $S'\in BC \cap AA$ and  .[/quote]

Which is the point $C$    :huh: ?

I corrected above my solution (without the Pascal's theorem).

:lol:  :lol: Well ... your  solution is  very  good ! .
But  I was  hoping  and  expecting  that  you  would  apply  a clear , straight ,  pure  geometric  approach !

[quote="gdeskos"]:lol:  :lol: Well ...
... I was  hoping  and  expecting  that  you  would  apply  a clear , straight ,  pure  geometric  approach ![/quote]

   Me too.

   T.Y.

   M.T

Neither ... (a solution with the Pascal's theorem; see
http://www.mathlinks.ro/Forum/viewtopic.php?t=42878 )... nor ... (a metrical solution) !
What I do is gratuitously. what is your opinion w.r.t it, my dear future friend Armpist ?

Well ........... I   found a  pure  geometric  solution .

  Draw  line  CD . Also  from  Q $\parallel$  to  AB  meeting  PR  at  K  and  OD  at  L . So  we  have KL = LQ (since OM=ON ) . Now  draw  from  L $\parallel$ to  PR  cutting  RQ  at S . Then since  LS $\parallel$ to  KR  then  RS = SQ and  OS $\perp$ RQ  Therefore  $\angle OSC = 90$ . THe  quadrateral  SLQD  is  inscriped  in  a circle  since  $\angle SLD =\angle RPD$  and  $\angle RPD = \angle RQD$ .SO  $\angle CSD = \angle DOC$ .
Then  the  quadrateral  OCDS is  inscribed  so  $\angle ODC = \angle OSC =90$  so $OD \perp DC$  . Finaly  we  find  that  DC  is  the  tangent  of  the  circle  at  D

Thanks, [i]Gdeskos[/i] and (my old friend) [i]Armpist[/i] ! [color=blue]By the way, [b]Armpist[/b]: see you my reply from the Darij's solution of the proposed problem posted to http://www.mathlinks.ro/Forum/viewtopic.php?t=28329 ? I am anxious to hear the your opinion about it (eventually by a private message).[/color]


algebra
function
domain
abstract algebra
superior algebra
superior algebra unsolved

If every submodule of a free A-module is free, then A is PID. Here is my solution: A is free A-module with basis $ \{e\}$, then any proper ideal $ I$ of $ A$ is a submodule of A, then it has a basis, but if there are at least 2 elements $ a_1, a_2$ then the linear combination $ a_1 a_2\minus{}a_2 a_1$ is zero so basis must consist of 1 element.
I feel that i might miss something here, please point out my mistakes..

[quote="Ronx"]If every submodule of a free A-module is free, then A is PID. Here is my solution: A is free A-module with basis $ \{e\}$, then any proper ideal $ I$ of $ A$ is a submodule of A, then it has a basis, but if there are at least 2 elements $ a_1, a_2$ then the linear combination $ a_1 a_2 \minus{} a_2 a_1$ is zero so basis must consist of 1 element.
I feel that i might miss something here, please point out my mistakes..[/quote]

Hello.
I think this proof is accurate, but "proper ideal " is perhaps not the best expression. I would say "non-null ideal". You prove that every non-null ideal has a basis with one element. The null ideal has empty basis.

P.S. If your teacher indicates a better proof than the mine for the factoriality of $ \mathbb{R}[X,Y,Z]/(X^{2} \plus{} Y^{2} \plus{} Z^{2})$, please let me know it.

Friendly,
P.


Παραθέτω ένα πρόβλημα πολύ καλό.Είναι κατασκευή του φίλου μου Νίκου Ράπανου .
Αρχικά νόμιζα ότι το είχα λύσει αλλά το δικό μου αποτέλεσμα δεν ήταν το ίδιο με το δικό του .Βάζω λοιπόν το πρόβλημα

Σε ένα reality πρόκειται να επιλεχθούν 5  παίκτες  από  15 αρχικούς υποψήφιους.
Μεταξύ αυτών των 15 υποψηφίων υπάρχουν 3 ανδρόγυνα, για τα οποία ισχύει ότι οι δύο  σύζυγοι  θα  είναι μαζί από την  αρχή  μέχρι και  το  τέλος  της  διαδικασίας  της επιλογής. Δηλαδή ή θα επιλεχθούν και οι δύο σύζυγοι ή κανένας  από τους δύο.
Η επιλογή των <<5>> θα εξελιχθεί σε δύο φάσεις :
Στην πρώτη φάση θα επιλεχθούν 10 από τους  15 αρχικούς υποψήφιους  και στη δεύτερη φάση θα επιλεχθούν 5 από τους 10 επιτυχόντες της πρώτης φάσης.
Με πόσους διαφορετικούς τρόπους μπορεί να πραγματοποιηθεί η επιλογή των <<5>> ;

[quote="stedes"]Όλοι οι δυνατοί συνδυασμοί για τους <<5>> είναι $279$.
Όλοι οι δυνατοί τρόποι για να επιλεγούν οι <<5>> είναι $4788$ .
(Αν δεν έχω κάνει λάθος στις πράξεις)!
Σωστά;
Στέλιος… :)[/quote]

Στέλιο νομίζω ότι ο Νίκος (Ράπανος )  μου είχε πει ένα άλλο αποτέλεσμα κοντά στις 19000 και κάτι αν θυμάμαι καλά ???(Έχω την εντύπωση 19152 ). Μπορείς να δώσεις τη λύση σου και τα βήματα που έκανες για να δούμε αν κάτι πάει στραβά.......
Παρεπιπτόντως και εγώ κάπου εκεί είχα βρει........ :huh:

Τελικά είχα κάνει λάθος στις πράξεις  :| .

Τελικό αποτέλεσμα:
$\binom{3}{3}\binom{9}{4}\left[\binom{3}{2}\binom{4}{1}+\binom{3}{1}\binom{4}{3}\right]+ \ \binom{3}{2}\binom{9}{6}\left[\binom{2}{2}\binom{6}{1}+\binom{2}{1}\binom{6}{3}+\binom{6}{5}\right]+$

$+\binom{3}{1}\binom{9}{8}\left[\binom{1}{1}\binom{8}{3}+\binom{8}{5}\right]=\boxed{19152}$

Στέλιος... :!:

Σωστά .....Συγχαρητήρια Στέλιο.

Στλελιο (ή κάποιος άλλος) μπορείς να μου εξηγήσεις τι εκφράζει ο κάθε συνδιασμός στο άθροισαμ που έγραψες παραπάνω ?Ευχαριστώ

[quote="stedes"]
Τελικό αποτέλεσμα:
$\binom{3}{3}\binom{9}{4}\left[\binom{3}{2}\binom{4}{1}+\binom{3}{1}\binom{4}{3}\right]+ \ \binom{3}{2}\binom{9}{6}\left[\binom{2}{2}\binom{6}{1}+\binom{2}{1}\binom{6}{3}+\binom{6}{5}\right]+$

$+\binom{3}{1}\binom{9}{8}\left[\binom{1}{1}\binom{8}{3}+\binom{8}{5}\right]=\boxed{19152}$
[/quote]
[quote="silouan"]
Στέλιο (ή κάποιος άλλος) μπορείς να μου εξηγήσεις τι εκφράζει ο κάθε συνδιασμός στο άθροισμα που έγραψες παραπάνω ?Ευχαριστώ
[/quote]
$-\binom{3}{3}\binom{9}{4}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην πρώτη δεκάδα μπορούν να μπουν τρία ζευγάρια,

  $\binom{3}{2}\binom{4}{1}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην τελική πεντάδα μπορούν να μπουν δύο ζευγάρια,εφόσον στην πρώτη δεκάδα έχουν μπει τρία ζευγάρια,

  $\binom{3}{1}\binom{4}{3}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην τελική πεντάδα μπορεί να μπει ένα μόνο ζευγάρι,εφόσον στην πρώτη δεκάδα έχουν μπει τρία ζευγάρια.

$-\binom{3}{2}\binom{9}{6}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην πρώτη δεκάδα μπορούν να μπουν δύο μόνο ζευγάρια,

  $\binom{2}{2}\binom{6}{1}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην τελική πεντάδα μπορούν να μπουν δύο ζευγάρια,εφόσον στην πρώτη δεκάδα έχουν μπει δύο μόνο ζευγάρια,

  $\binom{2}{1}\binom{6}{3}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην τελική πεντάδα μπορεί να μπει ένα μόνο ζευγάρι,εφόσον στην πρώτη δεκάδα έχουν μπει δύο μόνο ζευγάρια,

  $\binom{6}{5}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην τελική πεντάδα δεν θα υπάρχει κανένα ζευγάρι,εφόσον στην πρώτη δεκάδα έχουν μπει δύο μόνο ζευγάρια.

$-\binom{3}{1}\binom{9}{8}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην πρώτη δεκάδα μπορεί να μπει ένα μόνο ζευγάρι,

  $\binom{1}{1}\binom{8}{3}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην τελική πεντάδα μπορεί να μπει ένα ζευγάρι,εφόσον στην πρώτη δεκάδα έχει μπει ένα μόνο ζευγάρι,

  $\binom{8}{5}=$ όλοι οι δυνατοί συνδυασμοί με τους οποίους στην τελική πεντάδα δεν θα υπάρχει κανένα ζευγάρι,εφόσον στην πρώτη δεκάδα έχει μπει ένα μόνο ζευγάρι.

$\boxed{19152}=$ πλήθος δυνατών τρόπων με τους οποίους μπορεί να επιλεγεί η τελική πεντάδα.

Ελπίζω τώρα να έγινε κατανοητή η λύση  ;) .

Στέλιος... :!:

Σε ευχαριστώ πάρα πολύ .  :lol: Πολύ ωραία η επεξήγησή σου.


In this link

 http://www.emepne.gr/my%20files/2008-anisotites-teliko.pdf

 I have in Greek some theory and enough solved problems in elementary inequalities.It will be usefull to beginners , but not only.The language will be not a problem , since  the sympols and the letters are known. I have traslated some problems into english, but I can not send the file , becouse a quota  limit  10MB does not allow me to send it.I'm waiting V.Vornicu to solve this problem.

          [i]Babis Stergiou , Mathematics teacher, Greece [/i]

I'm sorry, but the web site isn't showing up...


prove that for every positive integer n there exists a n-digit number divisible by 5^n all of whose digits are odd

meh, im bored, so i post random problems

blah. this is the only one i managed to solve. why don't you get online. you can find this solution like anywhere. yeah

yeah, but some people might have diff ways of going at it

Yeah, I don't really think there was more than one reasonable way of approaching that one.

Some of my friends found constructive proofs. I did it with induction nonconstructively.

lol. its sorta like show them what you got. basically i was happy that you said there was another way to do the problem


After I asked Mr. Rusczyk about whether or not I should read the new probability book that's coming out, I got this interesting response.

[quote="rrusczyk"]I would recommend teaching from it if you've finished DPatrick's intermediate course by then. What I mean is, find a few people in your school (or at the Math Circle), and use the book as a guide to teach them. You'll be amazed at how much math you learn teaching. I didn't learn much in any one class I took. I've learned an enormous amount teaching. [/quote]
I've been thinking about this for some time now and was wondering if I should help to arouse more interest and build a stronger math team at Torrey Pines. The majority of the students at my school do not seem to be engaged in math and our math team is not all that great. What I had in mind was to teach students who are interested for about an hour after school each day. I can't teach during lunch due to Science Olympiad.

Pros:
1) Our school would definately do better in competitions against other schools
2) It would get more students involved in mathematics. Our math club only has about 10 members. Sad, eh?
3) As Mr. Rusczyk mentioned, my problem solving abilities would improve as well.

Cons:
1) Takes up lots of time
2) Might not have many participants

If you have somthing to add, please comment. Thanks.

What Mr.rusczyk is 100% correct. I remember I learned more about problem solving "skills" when I started to monitor Math Chats. Although I'm too busy to host one now, I still remember it was fun and taught me a lot. Right now, I'm just solving problems since I mastered most of basic skills.

As for setting up a program, you might want to contact one of teachers if they can help you out. I made my school to take AMC-10 and AMC-12 last year only because I talked with teachers, main guy who do all high academic stuffs, and even the principal. It worked out pretty well but we got only like two practices.

It is really hard to find people who are interested in competitions as much as you do. In my school, no people other than me and few teachers know what "AMC" stands for. So, you might want to try to practice in here rather than on school. I mean, it's good for you to try to work with people in your school but if you set a school record, that might make more attention than trying to set up a program.

At least that's what I did in junior high. I was the first one to make in state in Mathcounts in my rural school and the junior high principal came to me to handshake me for my accomplishment.  :)

Hope this helps!


You have a 1.5 meter long sword. You are trying to take it into the airport...(ahh the idea of bringing weapon). however the airplane does not allow any thing whose greatest dimension exceed 1 meter. How do you take it in???

[hide]
a 1m x 1m x 1m box, diagonally[/hide]

[hide="Possible Answer"]If you want to be economical, you could use a 87cm x 87cm x 87cm box, or 1m x 80cm x 80cm box :D :P [/hide]

[quote="polymorphic"][hide]You travel really fast! Lorentz contraction  :D [/hide][/quote]

Nice! Though you would have to be traveling at $\frac{\sqrt{5}}{3}$ the speed of light if I calculated that correctly :D

Yeah, that fourth dimension really comes in handy  :lol:


Find all triples $ (n,x,y)$ of positive integers satisfying $ n^x\plus{}1\equal{}(n\plus{}1)^y.$

if we don't consider the cases $ x \ or \  y \equal{} 1$ then  the non-trivial answer is $ (n,x,y) \equal{} (2,3,2)$ and it the only answer which is non-trivial.
the proof is given for the generalization :$ x^p \minus{} y^q \equal{} 1$ [url=http://www.mathlinks.ro/viewtopic.php?search_id=2089714107&t=311106]here[/url].


LaTeX algebra polynomial limit integration function calculus

Let $ \alpha \in R $
  $ A= $ {{$ k.\alpha $} $ / k\in Z $} . $ A \in B $
 Prove that :
 $ \forall b\in [0,1) , \forall k >0 $, there exists $ a \in A : a \in (b-k , b+k)  \iff  \alpha $ is an irrational number .

[Moderator edit: the trouble here was caused by typing "< = >" inside $\LaTeX$. Replacing that by "\iff" produced a double-headed implication arrow. "< = >", if typed without spaces, is a forum code that causes unpredictable trouble.]

Retype:
$ \Longleftrightarrow$

[quote="romano"]Let $ \alpha \in R $
  $ A= $ {{$ k.\alpha $} $ / k\in Z $} . $ A \in B $
 Prove that :
 $ \forall b\in [0,1) , \forall k >0 $, there exists $ a \in A : a \in (b-k , b+k)$ if and only if($ \Longleftrightarrow$)  $ \alpha $ is an irrational number .[/quote]

Romano - what is that period doing in $\{k.\alpha\}$? Is it a decimal point or do you mean $k\cdot\alpha$? Please clarify.

(By the way, the $\LaTeX$ coded needed to produce $k\cdot\alpha$ is "\cdot".

Aw well guys can anybody please tell me the problem properly. Theres been a lot of confusion.

In my opinion, it's just a stetement of the following well-known property of irrationals:

$\alpha$ is irrational iff the sequence of fractional parts $\{n\alpha\}$ is dense in $(0,1)$.

I mean : {k.a}= k.a - [k.a]
 Grobber explained clearly this problem .

The problem will be easier if you can prove : " If $ \alpha $ is an rational , then A has finite elements "

I think nobody is saying anything not because it's tough, but because stuff like this has been discussed on the forum lots of times. I even believe Kent showed Weyl's Theorem, namely that that sequence is equidistributed in $(0,1)$, not merely dense. Try searching the forum for stuff like "dense" and "uniformly distributed".

[quote="grobber"] namely that that sequence is equidistributed in $(0,1)$, not merely dense. T[/quote]
Are you sure that is true for $\alpha = \pi$? Hardy and Littlewood just proved that $\{\{k\alpha\}\}$ is equidistributed for almost all real numbers $\alpha > 1$, see [1]

Refs:

[1] http://mathworld.wolfram.com/EquidistributedSequence.html ( Hardy and Littlewood(1914)
[2] http://mathworld.wolfram.com/WeylsCriterion.html (Finch 2003)

[2] is newer but ...

Prof Kent, can you comment please?

Hardy and Littlewood proved that $(\{x^n\})_n$ is equidistributed for almost all $x$, which is completely different from what we're looking at here. Weyl's Theorem states that if $P$ is a polynomial with at least one irrational coefficient, then $(\{P(n)\})_n$ is equidistributed in $(0,1)$. All the $\{\}$ I used are meant to be fractional parts.

The "almost every $\alpha$" was for $\alpha^k$, not $k\cdot\alpha$. The product is much, much easier than that power.

$\{k\cdot\alpha\}$ is "equidistributed" on $[0,1]$ if and only if $\alpha$ is irrational.

The key is the limit $\lim_{N\to\infty}\frac1N\sum_{k=1}^Ne^{2\pi ikm\alpha}$ which is zero unless $m\alpha$ is an integer.

Hence if $f$ is a trigonometric polynomial $f(x)=\sum_{m=-n}^n\hat{f}(m) e^{2\pi imx}$, then, as long as $\alpha$ is irrational,

(*) $\lim_{N\to\infty}\frac1N\sum_{k=1}^Nf(k\alpha) =\hat{f}(0)=\int_0^1f(x)\,dx.$

Since trigonometric polynomials are dense in the $C(\mathbb{T})$ in the uniform norm, (*) holds for any continuous $f.$ (Note: by $\mathbb{T}$ I mean the quotient topological group $\mathbb{R}/\mathbb{Z}$, which can be thought of as a circle. We could just as easily have said "periodic continuous function" as "continuous function on $\mathbb{T}.$)

If $\{k\cdot\alpha\}$ were not dense in $[0,1]$, we could find a continuous $f$ with nonzero integral that was zero except on an interval missed by the sequence. (*) ensures that this cannot happen.

This problem will pretty hard if you don't use Weyl's theorem !!
 I am thinking about an easier solution . We can prove this problem by definition :
 " The set A is dense in B iff A \in B , $ \forall b \in B , \forall k >0 $ , there exists $ a \in A $ such that : $ a\ in (b-k,b+k) $

  Or we can use the lemma :
 " The set A is dense in B iff A \in B , $ \forall u,v \in B , u<v $ , there exists $ a\in A $ such that : u< a < v "

  Try it to solve this problem !

I think denseness can be proved by the pigeonhole principle.

just use the fact that subgroups of $R$ are dense or discret.

I was not suggesting using Weyl's Theorem to prove denseness :). I was just saying that it had been discussed before, and I'm sure the denseness has received solutions on the forum without involving that powerful theorem.

Anyway, here's a proof.

Let's work on the circle of length $1$, and let's denote $\{n\alpha\}$ by the point $A_n$. As we add another $\alpha$ (i.e. we add another point on the circle), we go around the circle in a counter-clockwise direction. First of all, since $\alpha$ is irrational, no two points $A_i,A_j,\ i\ne j$ are the same, meaning that there are infinitely many points on our circle. It means that we can find some $m<n$ s.t. the length of the arc (in a counter-clockwise direction) $A_mA_n$ is $<\varepsilon$. All arcs of the form $A_{m+k(n-m)}A_{m+(k+1)(n-m)}$ have the same length $<\varepsilon$, so, by looking only at these points, we see that for each arc $I$ with length $>\varepsilon$, at least one of these points must "fall" in $I$.

This proves what we wanted, which was the denseness of $(A_n)_n$ on the circle.


function
analytic geometry
geometry
3D geometry
sphere
calculus
integration

This is the last problem on my first homework set for PDE. I have no idea where to begin (i.e. I don't understand what a radial function is). Any help is appreciated. I'm not looking for a solution (that's cheating), but any nudge in the right direction is appreciated.

For a function u(x,y) of 2 variables, its Laplacian Du is defined to be uxx + uyy, and likewise for more variables. Which radial functions (i.e., functions of the polar coordinate r but independent of theta or whatever angular variables there are) are harmonic (i.e., satisfy the PDE Du=0) ? The answer depends on the number of independent variables ... try to do this for all dimensions n > (or equal to) 2.

Thanks.

[quote="jpps1"]I don't understand what a radial function is
...
radial functions (i.e., functions of the polar coordinate r but independent of theta or whatever angular variables there are)[/quote]

"Radial function" means radially symmetric: it's constant on every sphere (circle, in 2 dimensions) centered at the origin, and so is a function only of the distance $ r$ from the origin.  For example, $ f(x, y) \equal{} (x^2 \plus{} y^2)^{\frac{3}{2}}$ is a radial function.

[hide="A suggestion"] apply the divergence theorem to the integral of $ \nabla u$ over a sphere.[/hide]

More explicitly, a function $ f: \mathbb{R}^n\to \mathbb{C}$ is radial if there is a function $ g: \mathbb{R}_{\geq 0}\to \mathbb{C}$ such that $ f(x) \equal{} g(|x|)$ for all $ x\in\mathbb{R}^n$.

(that is, the value of $ f(x)$ only depends on the (euclidean) distance of $ x$ from the origin)


The 450 juniors at East HS drink a total of 1500 cartons of milk per  5-day week. If the average senior drinks milk at the same rate as the average junior, what is the average number of total cartons of milk the 600 seniors drink each school day?

Divide to get the number of cartons drunk by junoirs each day.\[ \frac{1500}{5}\equal{}300\]Use proportions to find the amount the senoirs drink a day.\[ \frac{300}{450}\equal{}\frac{x}{600}\]\[ x\equal{}400\]

We divide 1500/450=3.3333333.... so 1 junior drinks 3.33333 cartons of milk per 5 day week since there are 600 senios they drink 600 x 3.33333=2000 per 5 days so we divide by 5 to get a total 400 per day.


function
inequalities
number theory
prime numbers
number theory unsolved

For the first ones:
a) Correct, now also write $\phi(2n)$ as such a product and compare.
b) Similar, but here a "new" prime factor $2$ is added.

For the other:
a) Yes there are more, for example $x=36$.
Write $\phi(n) = \prod p_{i}^{n_{i}}(p_{i}-1)$ (this is equivalent to what you gave above) and show that no prime $p>13$ can occure because otherwise the product is to big.
Now show that no prime $p>3$ can occure two times or more in $n$ by unique prime factorisation. Similar, $2$ can't occure more than $3$ times and $3$ more than two times.
Now only a finite amount of number is to check: those of type $2^{a}3^{b}5^{c}7^{d}$ with $a \in \{ 0,1,2,3 \}$, $b \in \{0,1,2\}$, $c,d \in \{1,2\}$.
You can avoid checking most of this cases by unique factorisation and inequalities again, e.g. all for that $c=d=1$ have to big $\phi \geq (5-1)(7-1)=24$.
You can also use the two previous problems to handle some cases after you did another one.

b) show that $x$ is a solution iff $ax$ is a solution for all $a$ coprime to $2$ and $3$. Then it suffices to handle the case $x=2^{a}3^{b}$.

c) very similar to b)

d) take a look at the biggest prime dividing $x$.

e) similar to d)