counting
modular arithmetic
Marcin Kuczma
number theory
IMO
imo 1995
prime

Let $ p$ be an odd prime number. How many $ p$-element subsets $ A$ of $ \{1,2,\dots,2p\}$ are there, the sum of whose elements is divisible by $ p$?

This is problem 6 form IMO 1995.There are two different solutions to it:
The first is purely combinatorial: Tahe $ A \equal{} \{0..p \minus{} 1\}, B \equal{} \{p..2p \minus{} 1\}$.
For a set $ S$ different from $ A$ and $ B$ denote $ C \equal{} S \bigcap A$ ,$ D \equal{} S \bigcap B$.
Then the sets $ (C \plus{} x) \bigcap D$ form a group of $ p$ sets where all the residues appear. (The set $ A \plus{} x \equal{} \{(a \plus{} x) mod p| a \in A\}$)
So we can couunt easily.
The second uses multisection formula counting the coeff $ x^{pk} y^p$ at the polynomial
$ (1 \plus{} y)(1 \plus{} xy)\cdots (1 \plus{} x^{2p \minus{} 1}y)$

Define $X: =\{ 1,2,...,p\},Y: =\{p+1,p+2,...,2p\}$.
See $X$ and $Y$ as a representant system for $\mathbb{Z}/ p \mathbb{Z}$, since not more is necessary (so all identities concerning $X$ or $Y$ must be seen $\mod p$).
For a subset $A \subset X$ and $z \in \mathbb{Z}/ p \mathbb{Z}$ define $A+z: =\{ a+z \in X| a \in A \}$ and similar for a subset $B \subset Y$.
Call $A \subset X$ trivial iff $A=\emptyset$ or $A=X$, similar for $B \subset Y$ again.
Now there are only $4$ subsets $P \subset (X \cup Y)$ such that both $P \cap X$ and $P \cap Y$ are trivial, so call these subsets trival from now on too.
Then define for a nontrivial subset $P \subset (X \cup Y)$ a 'translation':
if $P \cap X$ is nontrivial define $P+z : = ((P\cap X) +z) \cup (P \cap Y)$ and $P+z : = (P \cap X) \cup ((P\cap Y) +z)$ otherwise.
Now it's easy to see that when $z$ goes through all possible residue classes, that also the sum of the elements of $P+z$ goes through all of them, so there is exactly one sum that is divisible by $p$.
So the 'translation' divides the nontrivial subsets into equivalence classes of $p$ sets each, all sets of the same class having same number of elements.

Since there are exactly $\binom{2p}{p}$ subsets of the desired order $p$ and $2$ of them are trivial, we get that there are $\frac{\binom{2p}{p}-2}{p}+2$ such subsets.

(note that this technique trivially generalises to other types of subsets and all sets of type $\{1,2,...,kp\}$)

Thanks for nice work ZetaX (is it true ? :D )!
It's a very famous problem ! It seems that there's another way to count this by using polynomial (or useing generator function) . Do you know who creat that nice solution? It's just my wondering about the exactly author of that nice solution which i saw on The Mathematics and Youth Magazine (Vietnam Magazine)  in 1996!

can you write the second solution in a slightly way iura

Consider the polynomial $f(x,y)=(1+xy)(1+x^2y)\ldots(1+x^{2p-1}y)$, the $k$-th factor refering to whether $k$ is present in the set or not.

Then the monomial $x^ky^l$ will refer to the set having $l$ elements and sum of elements $k$, so we need to compute the sum of coefficients of $x^{kp}y^p$ of $f$ to find the answer.

To do this, we need to compute the sum of coefficients $x^{pk}y^{pl}$ and substract 2, since there are two terms  for $l\neq 1$:$1, x^{p(2p-1)}y^{2p}$.

To compute the sum of coefficients of $x^{pk}y^{pl}$ we use Multisection formula that says us that it equals

$\frac{1}{p^2}\sum_{i,j}f(w^i,w^j)$($w$ is $p$th root of unity).

Now if $w^i$ is not $1$, $f(w^i,w^j)=\prod(1+w^{ik}w^j)=\prod (1+w^k)^2$ (every $w^m$ will be written twice as $w^{ki}w^j$). This equals $\prod (-1-w^k)^2=g(-1)^2=((-1)^p-1)^2=4$ ($g(x)=x^p-1$ is the polynomial with roots $w^i$). Since there are $p-1$ choices for $w^i$, $p$ choices for $w^j$ we get $4p(p-1)$.

Finally, if $w^i=1$, $f(1,w^j)=(1+w^j)^{2p}$. To evaluate $\sum_{j=0}^{p-1} (1+w^j)^{2p}$, note that it equals $p$ times the coefficients of $x^p$ in the polynomial $(1+x)^{2p}$ by the same multisection formula, so it equals $p\binom{2p}{p}$.

So our total sum is $\frac 1{p^2} (4p(p-1)+p\binom{2p}{p}) =\frac{\binom{2p}{p}-2}p+4$.
Substracting 2 we get the desired answer.

[quote="iura"].

To compute the sum of coefficients of $x^{pk}y^{pl}$ we use Multisection formula that says us that it equals

$\frac{1}{p^2}\sum_{i,j}f(w^i,w^j)$($w$ is $p$th root of unity).

.[/quote]
how can you prove that?What is miultisection formula?

If $w$ is a $n$th root of unity then $\sum_{i=0}^{n-1} w^k=0$ if $w\neq 1$ and $\sum_{i=0}^{n-1} w^k=n$ if $w=1$. By using this result, we can prove the Multisection Formula (which holds also for polynomials of more variables) :

$f(x)=\sum a_ix^i$, then $\sum_{i\equiv k\pmod m} a_ix^i=\frac 1n (\sum_{i=0}^{n-1} f(w^ix) w^{-ik})$. Particularly

$\sum_{i \equiv k\pmod m} a_i=\frac 1n(\sum_{i=0}^{n-1}f(w^i)w^{-ik})$

[quote="mathmanman"]Another (wonderful) solution
[/quote]
mathmanman is this the solution of Nikolai Nikolov from Bulgaria for which he get a special prize?

[quote="iura"]Consider the polynomial $f(x,y)=(1+xy)(1+x^2y)\ldots(1+x^{2p-1}y)$, the $k$-th factor refering to whether $k$ is present in the set or not.
[/quote]
I think that we have to consider the polynomial $f(x,y)=(1+xy)(1+x^2y)\ldots(1+x^{2p}y)$...am I right?

Sorry to bump this....

but when I solve it I keep getting $\left\lceil \frac{{2p \choose p}}{p}\right\rceil$, is this the same answer?

[quote="mathmanman"]Another (wonderful) solution :

We let $w$ be the p-th root of unity.
We thus have :
\[ \prod_{k=1}^{2p} (x - w^k) = (x^p - 1)^2 = x^{2p} - 2x^p + 1. \]
We now define the quantity :
\[ t(w) = \sum_{1 \leq j_1 < j_2 < \ldots < j_p \leq 2p} w^{j_1}w^{j_2} \ldots w^{j_p}. \]
So we have $t(w) = 2$. Besides, if we write $t(w) = \sum a_jw^j$, then $a_j$ represents the number of sub-sets ${j_1, j_2, \ldots, j_p}$ of ${1, 2, \ldots, 2p}$ such that $j_1 + j_2 + \ldots + j_p \equiv j \pmod p$, and we can write :
\[ (a_0 - 2) + a_1w + \ldots + a_{p-1}w^{p-1} = 0. \]
Since the minimal polynomial of $w$ on $\mathbb{Q}[X]$ is $1 + x + \ldots + x^{p-1}$, it follows that :
\[ a_0 - 2 = a_1 = a_2 = \ldots = a_{p-1}. \]
Besides, $a_0 + a_1 + \ldots + a_{p-1} = \binom {2p}{p}$, we conclude immediately that :
\[ a_0 = \frac 1p \left\{\binom {2p}{p} - 2 \right \} + 2. \][/quote]

I wonder that whether we can use this wonderful idea to solve the generation of this problem? I mean we replace $ 2p $ with $ n>p $?

[hide=different solution]
Lemma: Let $1\leq k\leq p-1$. The number of $k$-element subsets of $\{1,2,\ldots,p\}$ whose sum of elements is $a\pmod{p}$ is $\frac{1}{p}\binom{p}{k}$.

Proof: Note that $\gcd(k,p)=1$. Thus, the $\binom{p}{k}$ different $k$-element subsets can be grouped into $\frac{1}{p}\binom{p}{k}$ different groups of $p$ subsets each such that the subsets in each group are cyclic shifts of each other $\pmod{p}$. Thus, in each of these groups, the $p$ different sums of elements are $0,1,\ldots,p-1\pmod{p}$ in some order, so exactly one of them will be $a\pmod{p}$. Thus, there are $\frac{1}{p}\binom{p}{k}$ subsets whose elements sum to a number $a\pmod{p}$.

Now, consider a $p$-element subset of $\{1,2,\ldots,2p\}$ whose sum of elements is $0\pmod{p}$ (call such subsets [i]good[/i]). Suppose that it has $k$ elements in $\{1,2,\ldots,p\}$ and $p-k$ elements in $\{p+1,p+2,\ldots,2p\}$. We count the number of good subsets for each $k$. If $k=0$ or $k=p$, there is exactly one good subset ($\{1,2,\ldots,p\}$ and $\{p+1,p+2,\ldots,2p\}$ respectively), so it suffices to consider $1\leq k\leq p-1$.

Suppose that our good subset $A$ is such that the sum of the elements of $A\cap\{1,2,\ldots,p\}$ is $a\pmod{p}$; then, the sum of the elements of $A\cap\{p+1,p+2,\ldots,2p\}$ is $-a\pmod{p}$. By the lemma, there are $\frac{1}{p}\binom{p}{k}$ ways to choose the $k$ elements of $A\cap\{1,2,\ldots,p\}$ and $\frac{1}{p}\binom{p}{p-k}$ ways to choose $A\cap\{p+1,p+2,\ldots,2p\}$. Thus, the number of good subsets with this $k$ is
\[\sum_{a=0}^{p-1}\frac{1}{p}\binom{p}{k}\frac{1}{p}\binom{p}{p-k}=\frac{1}{p}\binom{p}{k}^2.\]

Thus, the number of good subsets with $1\leq k\leq p-1$ is
\[\sum_{k=1}^{p-1}\frac{1}{p}\binom{p}{k}^2=\frac{1}{p}\left[\sum_{k=0}^{p}\binom{p}{k}^2-\binom{p}{0}^2-\binom{p}{p}^2\right]=\frac{1}{p}\left[\binom{2p}{p}-2\right].\]
Adding back the two good subsets for $k=0$ and $k=p$, our final answer is $\boxed{\frac{\binom{2p}{p}-2}{p}+2}$.
[/hide]

[quote=mihaith]Yes, we can. If $\{ 1,2,...,2n \}$ is the initial set, then the number of subsets with $n$ elements such that each sum of these subsets' elements is divisible by $n$ is
$$\frac{(-1)^n}{n} \cdot \sum_{d|n} (-1)^d \varphi \bigg( \frac{n}{d} \bigg ) \binom {2d}{d} $$
where $"\varphi"$ is the Euler totient function.
$$\odot$$[/quote]

Solution for generalization: Consider the generating function $f(x)=\prod_{i=1}^{2n}(1-x^iy)$ where $y>1.$ Clearly, it suffices to find sum of coefficients in the terms of the form $x^{kn}y^{n}.$ So let $\omega$ be n-th primitive root of unity. By roots of unity filter it is sufficient to find the sum of coefficients in front of $y^{n}$ in $$P=\frac{\sum_{i=0}^{n-1}f(\omega^{i})}{n}$$
Now, $f(w^{i})=\prod_{j=1}^{2n}(1-\omega^{ij}y)=(\prod_{j=1}^{n}(1-\omega^{ij}y))^2.$ Now if we denote $\epsilon=\omega^{i},$ then $\epsilon$ is $\frac{n}{gcd(n,i)}$-th primitive root of unity. Hence $$f(w^{i})=(\prod_{j=0}^{\frac{n}{gcd(n,i)}-1}(1-\epsilon^{j}y))^2=(1-y^{\frac{n}{gcd(n,i)}})^{2gcd(n,i)}...(*)$$
Now it is clear that sequence $(\frac{n}{gcd(n,j)})_{1 \le j \le n}$ passes through all divisors of $n$ and only through them. In the spirit of this, we have:
[b]Lemma: [/b] For any divisor $d$ of $n$ the following has $\varphi(d)$ solutions in $j: d=\frac{n}{gcd(n,j)}$
[b]Proof: [/b] It is equivalent with $gcd(n,j)=\frac{n}{d}$ i.e $gcd(d,\frac{jd}{n})=1$ which, since $\frac{jd}{n} < d$ has $\varphi(d)$ solutions.
So let $d=gcd(n,j)$ in $(*)$ then: $f(w^{i})=(1-y^\frac{n}{d})^{2d}.$ Coefficient in front of $y^{n}$ is thus $(-1)^d\binom{2d}{d}.$ This holds for any divisor $d$ of $n$ and it appears for $\varphi(d)$ times, from Lemma. Hence, the answer is $$\frac{\sum_{d|n} (-1)^d \varphi \bigg( \frac{n}{d} \bigg ) \binom {2d}{d}}{n} \blacksquare$$

My solution is similar to CantonMathGuy's.

Let $A = \{ 1,2, \dots, p \}$ and $B = \{ p+1, p+2, \dots ,2p \}$. As usual $\sigma(S)$ denotes the sum of elements of set $S$.

Claim: The number of $k$-element sets $S_k \subset A$, $k<p$, such that $\sigma(S_k) \equiv \ell \mod p$, for a fixed $\ell$ is $\frac{1}{p} \binom{p}{k}$.
Fix $k<p$. We will establish the desired bijection. Suppose $\sigma(S_k) \equiv \ell \mod p$. Then to each element of $S_k$ add a fixed constant $i$ so that $\sigma(S_k +i) \equiv \ell +ik \mod p$. Here addition is defined in modulo $p$. Anyway,we can choose $i$ so that $\ell +ik$ is any desired residue mod $p$. There are $\binom{p}{k}$ subsets in total. By our bijection between all residues we get $\frac{1}{p} \binom{p}{k}$ subsets with $\sigma(S_k) \equiv \ell \mod p$.

Now we can directly count the number of $p$-element subsets with sum divisible by $p$.
If we choose no elements from $A$, then we choose all of $B$. If we choose all of $A$, then choose nothing from $B$.
Choose $1 \leq i \leq p-1$ elements from $A$. There are $\binom{p}{i}$ ways to do this. Then choose $p-i$ elements from $B$ with a fixed sum mod $p$. There are $\frac{1}{p} \binom{p}{p-i}$ ways to do so.

So the number of ways is $$2 + \sum _{i=1} ^{p-1} \frac{1}{p} \binom{p}{i} \binom{p}{p-i} = \boxed{2 + \frac{\binom{2p}{p}-2}{p}}$$
The last equality follows from the identity $\binom{2p}{p} = \sum_{i=0}^{p} \binom{p}{i} \binom{p}{p-i}$ which can be proved by double counting the number of ways to choose $p$ elements from a $2p$-element set. So we are done.

[quote=iura]. To evaluate $\sum_{j=0}^{p-1} (1+w^j)^{2p}$, note that it equals $p$ times the coefficients of $x^p$ in the polynomial $(1+x)^{2p}$ by the same multisection formula, so it equals $p\binom{2p}{p}$.
[/quote]
No, it equals  $p\binom{2p}{p}+2p$ , as you forgot to consider the first and last terms.
But anyways you got the final answer correct ,so maybe it was a typo.

Of course, we can determine the number of such subsets for any fixed size of subset (not just those with $p$ elements).

As in other solutions, let
\[
f(x,y) = (1+xy)(1+x^2y)\cdots(1+x^{2p}y),
\]
and let $\zeta$ be a primitive $p^{\text{th}}$ root of unity.  We will consider this as a generating function in $x$ first, run the roots of unity computation, and read the result as a generating function in $y$.  Indeed, observe that $f(1,y) = (1+y)^{2p}$ while
\begin{align*}
f(\zeta^k,y) &= y^{2p}\Big((-y^{-1} - 1)(-y^{-1} - \zeta)\cdots (-y^{-1}-\zeta^{p-1})\Big)^2 \\&\hspace{2in}= y^{2p}(-(y^{-1})^p-1)^2 = (y^p + 1)^2.
\end{align*}
Therefore the sum of all coefficients of $x$ associated to powers of $p$ is
\[
\frac{1}{p}\sum_{k=0}^{p-1}f(\zeta^k,y) = \frac{(p-1)(y^p + 1)^2 + (y+1)^{2p}}p.
\]
From this, we can read off the answer as the coefficient of $y^p$ in the above expression, or $\boxed{2 + \tfrac{\binom{2p}p - 2}p}$.

In general, the number of subsets of size $k$ whose sum of elements is divisible by $p$ equals $\tfrac{1}{p}\textstyle\binom{2p}k$ when $k$ is not divisible by $p$ and equals $1$ when either $k=0$ or $k=2p$ (as we would expect).  Additionally, the total number of subsets over all sizes is $4 + \tfrac{4^p-4}{p}$, found by setting $y = 1$ above.

Let $f(x, y)$ be

\[(1+xy)(1+x^2y)\cdots (1+x^{2p}y).\]

Then we desire the sum of the coefficients of terms of the form $x^{pk}y^p$, where $k$ is a positive integer.

To get this value, we apply the roots of unity filter twice. Let $\omega = e^{\tfrac{2\pi i}{p}}$. Note that the sum of the coefficients of $y^0, y^p, y^{2p}$ is

\[\frac{\sum_{k=0}^{p-1} f(x, \omega^k)}{p}.\]

Then the coefficients of $y^0$ and $y^{2p}$ are clearly $1$ and $x^{p(2p+1)}$, so the coeffient of $y^p$ is

\[\frac{\sum_{k=0}^{p-1} f(x, \omega^k)}{p} - x^{p(2p+1)} - 1.\]

To find the sum of the coefficients of $x$ raised to a power of a multiple of $p$, we once again apply the roots of unity filter. We desire the value of

\begin{align*}
\frac{\sum_{m=0}^{p-1} \left(\frac{\sum_{k=0}^{p-1} f(\omega^m, \omega^k)}{p} - (\omega^m)^{p(2p+1)} - 1\right)}{p} & = \frac{ \frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} f(\omega^m, \omega^k)}{p} - p(\omega^m)^{p(2p+1)} - p}{p}\\
& = \frac{\frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} f(\omega^m, \omega^k)}{p} - p - p}{p}\\
& = \frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k) - 2p^2}{p^2}.
\end{align*}

It's easy to see that the two sets

\[\{m+k, 2m+k, \cdots, pm+k\}\]

and

\[\{(p+1)m+k, (p+2)m+k, \cdots, 2pm+k\}\]

are equal to the set $\{0, 1, \cdots, p-1\}$ of residues modulo $p$ when $m$ is not equal to $0$. When $m=0$, this set is just the number $k$ repeated $p$ times. Therefore,

\begin{align*}
&\text{ }\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k)\\ = &\text{ }\sum_{k=0}^{p-1} (1+\omega^k)^{2p} +  p(p-1) \cdot \left((1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1})\right)^2.
\end{align*}

Then we note that, by expanding using the binomial theorem and summing, we get that

\[\sum_{k=0}^{p-1} (1+\omega^k)^{2p} = p\cdot\binom{p}{0} + p\binom{2p}{p} + p\binom{p}{p} \omega^{kp} = p\left(\binom{2p}{p} + 2\right).\]

Moreover, since the polynomial

\[Q(x) = x^p-1\]

factors as

\[(x-1)(x-\omega)(x-\omega^2)\cdots (x-\omega^{p-1}),\]

we get that

\[(1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1}) = (-1)^pQ(-1) = 2\]

so that

\[p(p-1) \cdot \left((1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1})\right)^2 = 4p(p-1).\]

Therefore, we have

\[\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k) = p\left(\binom{2p}{p} + 2\right) + 4p(p-1)\]

so our answer is

\begin{align*}
\frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k) - 2p^2}{p^2} & = \frac{p\left(\binom{2p}{p} + 2\right) + 4p(p-1) - 2p^2}{p^2}\\
& = \boxed{\frac{1}{p}\left(\binom{2p}{p} - 2\right) + 2}
\end{align*}

The answer is $\frac{1}{p}\left(\binom{2p}{p}-2\right)+2$. We will instead find the number of subsets $A$ such that $p$ divides $|A|$ and the sum of the elements of $A$ is also divisible by $p$. Note that this is just the answer plus two (for the empty set and $A=\{1,\ldots,2p\}$).
Consider the generating function
$$F(x,y)=(1+x^1y)(1+x^2y)\ldots (1+x^{2p}y),$$
so the coefficient of $x^ay^b$ represents the number of subsets with sum $a$ and $b$ elements. Then by a roots of unity filter we wish to find
$$\frac{1}{p^2}\sum_{i=0}^{p-1}\sum_{j=0}^{p-1}F(z^i,z^j),$$
where $z$ is a primitive $p$th root of unity.
Note that if $p \nmid i$, then
$$F(z^i,z^j)=(1+z^{1i+j})\ldots(1+z^{2pi+j})=(1+z^0)^2(1+z^1)^2\ldots(1+z^{p-1})^2.$$
Since $(x-z^0)\ldots(x-z^{p-1})=x^p-1$ and $p$ is odd, the last product on the above line is equal to $(1^p+1)^2=4$. Thus we can write
$$\frac{1}{p^2}\sum_{i=0}^{p-1}\sum_{j=0}^{p-1}F(z^i,z^j)=\frac{1}{p^2}\left(4p(p-1)+\sum_{j=0}^{p-1}F(1,z^j)\right)=\frac{1}{p^2}\left(4p(p-1)+\sum_{j=0}^{p-1}(1+z^j)^{2p}\right).$$
To find the value of the inner summation, consider the sum of the $x^{kp}$ coefficients of $(1+x)^{2p}$, which by another roots of unity filter is simply $\frac{1}{p}\sum_{j=0}^{p-1}(1+z^j)^{2p}$.
On the other hand by direct computation this quantity is equal to $\binom{2p}{p}+2$, so it follows that
$$\frac{1}{p^2}\left(4p(p-1)+\sum_{j=0}^{p-1}(1+z^j)^{2p}\right)=\frac{1}{p^2}\left(4p(p-1)+p\left(\binom{2p}{p}+2\right)\right)=\frac{1}{p}\left(4p-4+\binom{2p}{p}+2\right)=\frac{1}{p}\left(\binom{2p}{p}-2\right)+4.$$
Subtracting $2$ yields the desired answer. $\blacksquare$

This problem took me so long.

The idea is to partition $\{1, 2, \dots, 2p\} = \{1, 2, \dots, p\} \cup \{p + 1, p + 2, \dots, 2p\} = A \cup B$.

$\bold{Lemma}:$ $\binom{2p}{p} = \sum_{k = 0}^{p} \binom{p}{k} \binom{p}{p - k} = 2 + \sum_{k = 1}^{p - 1} \binom{p}{k} \binom{p}{p - k}$.
[hide = Proof] The proof is straightforward. Denote by $A$ and $B$ the same sets as in the introduction. If we choose $k$ elements from $A$, then we must choose $p - k$ elements from set $B$ to ensure we have chosen a total of $p$ elements. Summing this for all values of $k$ precisely gives us $\binom{2p}{p}$. $\blacksquare$ [/hide]

Consider the set $A_{\ell} = \{a_1 + \ell, a_2 + \ell, \dots, a_k + \ell\}$ for $k \neq p$ integers $a_1, a_2, \dots, a_k \in A$. Then we make the trivial but important observation that we have that the sequence $A_0, A_1, \dots A_{p - 1}$ form a complete set of residues modulo $p$. Hence if we were to count say, the number of subsets of $k$ elements for which they are $0 \pmod p$, there would be $\frac{1}{p} \binom{p}{k}$ such subsets. (For every $p$ subsets, there is only but one with sum divisible by $p$).

Consider then the set $B_{\ell'} = \{b_1 + \ell', b_2 + \ell', \dots, b_k + \ell'\}$ for $k \neq p$ integers $b_1, b_2, \dots, b_k \in B$. Similarly, this sequence of sets forms a complete set of residues modulo $p$.

Now if the set $A_i \equiv x \pmod p$, then we may find a suitable $B_j$ so that $B_j \equiv p - x \pmod p$, as both of the sequences $A_i$ and $B_j$ form a complete residue class modulo $p$. Thus there are $p \left (\frac{1}{p} \binom{p}{k} \frac{1}{p} \binom{p}{p - k} \right) = \frac{1}{p} \binom{p}{k} \binom{p}{p - k}$ ways to choose these sets. Summing over all $k$ gives us $\frac{1}{p} \left(\binom{2p}{p} - 2 \right)$.

Now we also have the original sets $A$ and $B$. (Both of these sets have the property pertaining to them that the sum of their elements is divisible by $p$ and contain $p$ elements). Hence the total number of such $p$ element subsets becomes $\boxed{2 + \frac{1}{p} \left(\binom{2p}{p} - 2 \right)}$. $\blacksquare$

Here's a somewhat shorter solution.

Consider the generating function $$F(k) = \prod_{i=1}^{2p} (1+k^i X)$$ for which the coefficient of the $X^a k^b$ term denotes the number of $a$-element subsets with sum $B$. It suffices to find the coefficient of the $X^p$ term in this expansion for $a$ a multiple of $p$, which is given via roots of unity filter by $$\sum_{\omega^p = 1} f(\omega) = f(1) + \sum_{\omega^p =1, \omega \neq 1} f(\omega).$$ Notice that $f(1) ={2p \choose p}$, and $f(\omega)$ for any arbitrary $p$th root of unity (necessarily primitive) denotes the coefficient of $X^p$ in $$\prod_{i=1}^{2p}(1+\omega^i X) = (-1)^{2p} \prod_{i=1}^{2p} (-1-\omega^i X) = (-1-X^p)^2 = (1+X^p)^2,$$ which is just 2.

Thus, the answer is $$\frac{{2p \choose p} + 2(p-1)}p = \frac{{2p \choose p} - 2}p + 2$$ subsets.

Consider the generating function \[ F(x,y) = \prod_{i=0}^{2p}(1+x^iy).\] It suffices to find the sum of coefficients of all terms where the power of $x$ is a multiple of $p$ and the power of $y$ is equal to $p$. Let $\omega = e^{\frac{2\pi i}{p}}.$ Using roots of unity filter, the sum of coefficients of all terms where the power of $x$ is a multiple of $P$ is \[ \frac1p\sum_{i=0}^{p-1} F(\omega^i, y). \] The term when $y=0$ is equal to $(1+y)^{2p}$, for which the $y^p$ coefficient is $\binom{2p}p$. All other terms in this summation are equivalent to \[ \left(\prod_{i=0}^{p-1}(1+\omega^iy)\right)^2.\] The inside product is equivalent to evaluating the function with roots $\omega^iy$ (namely $x^p+y^p$) at $1$, hence the entire term is equal to $(1+y^p)^2$, with a $y^p$ coefficient of $2$. Since there are $p-1$ such terms, the total contribution is $2(p-1)$.

Our desired answer is the sum of the $y^p$ coefficients in the filter summation, which is equal to \[ \frac1p\left(\binom{2p}p+2(p-1)\right).\]

Consider
\[
\prod_{k=1}^{2p}(1+y^kx)=\cdots+f(y)x^p+\cdots.\tag{1}
\]
Let $a_i$ denote the number of $p$-element subsets of $\{1,2,\ldots,2p\}$ which has the sum of elements equal to $i$. It follows that
\[
\sum_{n=0}^\infty a_ny^n=f(y).
\]
We also have
\[
\sum_{p\mid n}a_n=\frac{f(1)+f(\omega)+f(\omega^2)+\cdots+f(\omega^{p-1})}{p}
\]
where $\omega=e^\frac{2\pi i}{k}$. Plugging $y=1$ into (1) gives $(1+x)^{2p}=\cdots+f(1)x^p+\cdots$. By the binomial theorem, the coefficient of the $x^p$ term of $(1+x)^{2p}$ is $\binom{2p}{p}$. Now, for $1\leq j\leq p-1$, we have
\begin{align*}
\cdots+f(\omega^j)x^p+\cdots&=\prod_{k=1}^{2p}(1+\omega^{jk}x)\\
&=\prod_{k=1}^{2p}(1+\omega^kx)\\
&=\left(\prod_{k=1}^{p}(1+\omega^kx)\right)^2\\
&=(x^p+1)^2\\
&=x^{2p}+2x^p+1
\end{align*}
so $f(\omega^j)=2$. Thus we have
\[
\sum_{p\mid n}a_n=\frac{2(p-1)+\binom{2p}{p}}{p}.\text{ }\square
\]

Ha! The answer confirmation's so simple I knew there had to be a combinatorial way! So I'm not going to post some rouf solution.

By intuition we feel like our answer would be close to 1/p(2pCp) since it's around that expected value 1 in p subsets to be divisible by p; but since there are TWO elements same mod p, it kind of messes things up, while one distinct of each would help greatly. So we partition the sets into $\{1, 2, \dots, 2p\} = \{1, 2, \dots, p\} \cup \{p + 1, p + 2, \dots, 2p\} = M\cup N$; now, consider $M_k=\{m_1+k,m_2+k,...,m_m+k\}\forall k\ne p,m_1,m_2,...,m_m\in M$; do the similar thing for N. There are $p \left (\frac{1}{p} \binom{p}{k} \frac{1}{p} \binom{p}{p - k} \right) = \frac{1}{p} \binom{p}{k} \binom{p}{p - k}$ ways to choose some $N_i\equiv p-M_j\pmod p$; in particular, summing over all possible k simplifies to  $\frac{1}{p} \left(\binom{2p}{p} - 2 \right)$; but since we also need to add set M and N, there are $2 + \frac{1}{p} \left(\binom{2p}{p} - 2 \right)$ many ways as our final answer. $\blacksquare$

Goofy gen func rouf

Consider a generating function $$F(x,y) = (1+xy)(1+x^2y)(1+x^3y)\dots (1+x^{2p}y)$$ This generating function describes the subsets, where the exponent of $x$ is the sum of the elements and the exponent of $y$ is the size. Therefore, we want the sum of the coefficients of $x^{kp}y^p$ for positive integers $k$.
\\
\\
We now apply a Roots of Unity Filter. The generating function containing only the terms $x^{kp}$ can be obtained by taking
\[
\frac{1}{p}\sum_{k=0}^{p-1}F(e^{\frac{ik\pi}{p}}x,y)
\]
and we want the sum of the terms with exponent $y^p$ when evaluated at $x=1$. We write
\[
    (1+xy)(1+x^2y)\dots (1+x^{2p}y) =
    y^{2p}\left(-\frac1y-x\right)\left(-\frac1y-x^2\right)\left(-\frac1y-x^3\right)\dots \left(-\frac1y-x^{2p}\right)
\]
Let $P_x(t)$ be a monic polynomial in $t$ with roots $x^i$ for $i=1,2,\dots 2p$. When $x\neq 1$ is a $p^\text{th}$ root of unity, $P_x(t) = (t^p-1)^2$ Then, we find that $$F(x,y) = y^{2p}P_x\left(-\frac1y\right)$$ Plugging in $x=1$, we calculate that
\begin{align*}
[y^p]\frac{1}{p}\sum_{k=0}^{p-1}F(e^{\frac{ik\pi}{p}},y) &= [y^p]\frac{y^{2p}}{p}P_{e^\frac{ik\pi}{p}}\left(-\frac1y\right)\\
&= [y^p]\frac{y^{2p}}{p}\left((p-1)\left(\frac{-1}{y^p}-1\right)^2+\left(1+\frac{1}{y}\right)^{2p}\right)\\
&= [y^p]\frac{1}{p}\left((p-1)(y^p+1)^2 + (y+1)^{2p}\right)\\
&= \boxed{\frac{1}{p}\left(2(p-1)+\binom{2p}{p}\right)}
\end{align*}

Let $A(x,y)$ be the generating function
\[A(x,y) = (1+yx)(1+yx^2)\cdots(1+yx^{2p})\]
We apply the roots of unity filter on $x$ to get
\[\frac{A(1,y)+A(w,y)+\cdots+A(w^{p-1},y)}{p} = \frac{(1+y)^{2p}+(p-1)(1+yw)\cdots(1+yw^{2p})}{p}\]
We call this function on $y$, $B(y)$. Note that
\[(1+w)(1+w^2)\cdots(1+w^{p}) = 2\]
Then, we apply the roots of unity filter on $y$ to get
\begin{align*}
    \frac{B(1)+B(w)+B(w^2)+\cdots B(w^{p-1})}{p} &= \frac{p+p\binom{2p}{p}+p+2^{2}(p-1)(p)}{p^2}
\end{align*}
But, we need to subtract $2$ because it counts the empty set and the set with size $2p$. This gives us
\[\boxed{\frac{\binom{2p}{p}+2p-2}{p}}\]

Let $F(x,y)=\prod_{i=1}^{2p}(1+yx^i)$ be the gen func representing sums of subsets and their number of elements. Note that the answer is equal to \[\frac{1}{p^2}\left(\sum_{k=1}^p \sum_{k=1}^p F\left(e^{2\pi ij/p},e^{2\pi i k/p}\right)\right)-2\] by roots of unity filter, with the $-2$ coming from the empty set and $\{1,2,\dots,2p\}$ being included in this count. We thus compute this!!!
[list] [*]First, if $j=1,2,\dots,p-1$, then the sequence $j,2j,\dots, 2pj$ contains each residue modulo $p$ twice. Thus $j+k,2j+k,\dots, 2pj+k$ contains each residue twice. herefore, \[\sum_{k=1}^{p}F\left(e^{2\pi ij/p},e^{2\pi i k/p}\right)=p\prod_{k=1}^p \left(1+e^{2\pi i k/p}\right)^2=4p\] As \[\prod_{k=1}^p \left(1+e^{2\pi i k/p}\right)^2=\prod_{k=1}^p \left(-1-e^{2\pi i k/p}\right)^2=P(-1)^2=4\] in $P(x)=x^p-1$. [*]If $j=p$, then \[\sum_{k=1}^{p}F\left(1,e^{2\pi i k/p}\right)=p\sum_{k=1}^{p}F\left(1+e^{2\pi i k/p}\right)^{2p}\] By roots of unity filter on $(1+x)^{2p}$, we get that the above sum is $p\left(2+\binom{2p}{p}\right).$ [/list] Thus the total sum ignoring the division by $p^2$ and subtraction is \[p\left(2+\binom{2p}{p}\right)+4p(p-1)=p\binom{2p}{p}+4p^2-2p\] implying a final answer of \[\frac{p\binom{2p}{p}+4p^2-2p}{p^2}-2=\frac{\binom{2p}{p}-2}{p}+2.\]

[b][color=red]Remark:[/color][/b] N6 is crazy lol


Prove following allegations.
a) There is an odd number n, that for any even k none of the numbers $ k^k \plus{}1, k^{k^k} \plus{}1, k^{k^{k^k}} \plus{}1, k^{k^{k^{k^k}}} \plus{}1,. . .$ is not divisible by n.

b) For any natural n there is a natural k, that all members of consistency $ k^k \plus{}1, k^{k^k} \plus{}1, k^{k^{k^k}} \plus{}1, k^{k^{k^{k^k}}} \plus{}1,. . .$ are divided into n.

Contradiction for part a?  $ 2^2\plus{}1$ is 5 and $ 2^{2^2}\plus{}1$ is 17.


Let $ p$ is a prime. Prove $ p^2\equiv 1$ (mod 30) or $ p^2\equiv 19$ (mod 30)

It's only true for $ p>5$.
[hide]We have to show that either $ p^2\minus{}1$ is divisible by $ 30$ or $ p^2\minus{}19$ is. Both are even for $ p>5$. Since $ p$ is either $ 1$ or $ 2$ mod $ 3$ for $ p>$5, both are divisible by $ 3$. So we have to show $ 5$ divides one of the two. If $ p>5$ then it is either $ 1$,$ 2$,$ 3$, or $ 4$ mod $ 5$. If it is $ 1$ or $ 4$ mod $ 5$, then $ 5$ divides $ p^2\minus{}1$. If it is $ 2$ or $ 3$ mod $ 5$, then $ 5$ divides $ p^2\minus{}19$. So since $ 2$,$ 3$, and $ 5$ all divide one of $ p^2\minus{}1$ or $ p^2\minus{}19$, one of them must be divisible by $ 30$.[/hide]


There is a huge trend towards Asymptote in this community even though there are good alternatives, but I doubt this is the case in print. It would be very interesting to know what kinds of languages (or software) are used to produce geometry diagrams for books and also for olympiad problems (especially official IMO solutions).

I'm not sure about olympiad solution booklets but usually when submitting a paper with pictures for publication, you are just required to send an .eps file that you can produce in any way you want. Most of my colleagues prefer something like Xfig as far as I know.


In right $\bigtriangleup ABC$, $\overline{CF}$ is the median to hypotenuse $\overline{AB}$, $\overline{CE}$ is the bisector of $\angle ACB$, and $\overline{CD}$ is the altitude to $\overline{AB}$. Prove that $\angle DCE \cong \angle ECF$.

[hide]
Notice that $\triangle CBD$ is similar to $\triangle ABC$, therefore $\angle BCD = \angle A$.  Also, note that $\triangle CFA$ is isoceles, so $\angle FCA = \angle A$.  Since $CE$ bisects $\angle C$, it follows that $\angle DCE = \angle ECF$.
[/hide]
I got a question tho... what if $CE$ is not between $CD$ and $CF$??? will that ever happen???

Hmm... I don't think so because, as you pointed out, $\angle BCD \cong \angle A$. The angle bisector must lie between $\overline{CD}$ and $\overline{CF}$, because if it didn't, then it's quite clear that it can't be an angle bisector since one angle will be larger than the other.


Was this year easier or harder than usual?

I thought it was quite a bit easier...considering i normally cant do 2 completely in any USAMO

Well I've heard from an IMO participant that it's the hardest USAMO in the past few years.

[quote="Teki-Teki"]i thought that it was medium, given that 1,2,4 were fairly easy to approach (although 2 might not have been if you didn't think about a disk of radius $\frac{\sqrt{2}}{2}$) and 3,5,6 were fairly difficult, although 5 wasn't bad if you could show one little thing...6 was a beast.[/quote]

agreed.  although 5 was beast too.. how the hell were you supposed to prove that thing was composite.

was it sufficient for #2 to prove that 3 circles of radius five are tangent to a circle with radius greater than root(2)/2?

[quote="noneoftheabove"]You prove it by chinese remainder theorem using mod 113 and 911 apparently...=( and i think the easy ones were easy and hte hard ones were hard.[/quote]

Except it doesn't work for larger n, because a divisor of 7^{6*7^n}-...+1 has to be 1 mod 7^{n+1}...

Hehe..  Me, too.  Except that I voted medium-easy.

[quote="diophantient"]The first time I've ever fully solved a USAMO problem was during the test.
I think that qualifies it as easy.[/quote]

Are you sure? because that happend to me last year. Do you normally take full length 4.5 hour tests because if you don't thats probably why because you can do a lot in 4.5 hours. Like i looked at the problem i solved last year and i had no idea how to do it.

i voted hard..couldn't make any progress on any of em.

#1 was abnormally easy, so that's probably why so many people got a question.

So far 3 of my 4 proofs that actually completed the problem still remain standing, and one of them has been reinforced. I am almost certain that my proof for #4 is rigorous, and my proof for #2 uses a little bit of handwaving but is rigorous once you get to the fact that the hexagonal packing leaves gaps that are a part of any type of gap that might exist.

It had like two problems (1 and 4) easier than normal, and like three (3, 5, 6) much harder than normal.

[quote="mrosett"]I got 1,2 (kind of), 3, and 4. 5 was a beast, and I didn't get around to 6[/quote]

Finally, someone who solved the same problems as I did, and with the same levels of confidence...

This seems to me to be certainly one of the hardest, and probably the hardest, USAMO to date.

Getting 14 was much easier than on most exams, but after 1 and 4 the problems got rapidly difficult. 2 had a lot of very icky steps to make which were hard to rigorize (I expect many, many fewer people got 6-7 than the initial response suggests), 3 and 5 were just hard, and I didn't even want to look at 6 because it did not yield to any obvious approaches and I thought I might find a factorization on 5.

I probably failed in large part because taking a test under pressure (especially the USAMO) is harder than from the comfort of your own home, but I did significantly worse than I normally do on IMOs under testing conditions...

[quote="Phelpedo"][quote="sapphyre571"]seeing as I didn't even qualify but was able to solve 2 and 4 completely in an hour each and make decent progress on 1 and a little on 5 and 6 (I know I didn't take it officially, but 2 and 4 were the first USAMO problems I've ever solved. no wait. the 2nd and third problems I've ever solved.)[/quote]

You solved #2 but not #1?  :| I don't think we've seen one complete solution for #2 on this forum yet.[/quote]

I believe I saw a rigorous one by Steinhardt...very clever trick

[quote="noneoftheabove"]is there anywhere on this forum with #3? im interested to see the steps that i trivialized =P[/quote]

here's a short version of what I said...

Choose a subset of n+1 elements of S not all of whose n-element subsets are in one class.  Take those elements out and set them aside in one set.  Now from what remains, do the same thing.  And again.  And again.  Keep doing so until no n+1-element subset exists not all of whose n-element subsets are in one class.  Once this is the case, every n+1-element subset of the remaining set has all of its n-element subsets in the same class.  It's pretty easy to show then that the entire remaining set has all of its n-element subsets in the same class.  So, we can then choose that class which all of those subsets are in.  Clearly, we have, from each of the n+1-element subsets we set aside, a n-element subset in the class, and in the remaining set, we have a sufficient number of disjoint n-element subsets in that class, as desired.

My actual solution was a lot more clear and rigorous, with the "pretty easy" statement above in a two-page lemma, and the full solution at 5 pages.


Okay, here's the problem.  I am working with an exercise physiologist to develop a calculation for race times.  We have the data but cannot figure out how to get a value distance for a specific time (7 minutes).  7 minutes is the base for the log we are shooting after and we have the percentages of velocity based off empirical data. However, every time you recalculate using a different time for, say, 100m, the percentage changes.

Knowing that I can plot the data in Excel, how would I go about finding the equation (or equations) to use for my percentages?  Another way to explain is this: for example, if someone runs 5,000m in 15:00, the distance they can run in 7:00 is about 2,382.50m.  The velocity of the 5,000m pace is 96.2% of the velocity for the 7:00 (or 2,382.5m) pace.  Everytime you enter new numbers, the distances change.  However, the percentages do not. For example, 7:00 is 100%.   7:30 is 99.82%; 8:45 is 98.64%; 10:00 is 98.15%; 11:15 is 97.66%; 12:30 is 97.17%; 15:00 is 96.2%.

What I need to know is how to put these percentages into a scatter plot, calculate the formula and apply it to figure out the distance.  Sorry this is so poorly explained.  It's been many years since I did poorly in math.

Thanks,

Will

Since this is empirical data, you're not looking for "the formula"; there isn't one. You're really looking for a good model that fits your data. The nature of the problem says that this should be a smooth model, and the derivatives beyond the first will be quite small for large distance and time.

Do you care about sprints? Obviously, the data would have a different shape there.

I really don't know what kind of model would be best for your purposes; you should probably find an applied mathematician to ask about this.

The simplest thing you could do is linear interpolation between your data points- that's easy to calculate, but doesn't really incorporate the large-scale changes in speed well.


A triangular corner with side lengths $DB=EB=1$ is cut from equilateral triangle $ABC$ of side length $3$. The perimeter of the remaining quadrilateral is

[asy]
draw((0,0)--(2,0)--(2.5,.87)--(1.5,2.6)--cycle, linewidth(1));
draw((2,0)--(3,0)--(2.5,.87));
label("3", (0.75,1.3), NW);
label("1", (2.5, 0), S);
label("1", (2.75,.44), NE);
label("A", (1.5,2.6), N);
label("B", (3,0), S);
label("C", (0,0), W);
label("D", (2.5,.87), NE);
label("E", (2,0), S);[/asy]

$\text{(A)} \ 6 \qquad \text{(B)} \ 6\frac12 \qquad \text{(C)} \ 7 \qquad \text{(D)} \ 7\frac12 \qquad \text{(E)} \ 8$

[hide] Say that D is on AB and E is on CB.  The quadrilateral has sides AC=3, AD=2, CE=2, and DE, which is 1 because triangle BDE is obviously equilateral.  So the perimeter is 3+2+2+1=8. E.[/hide]

[hide]$1 + 2 + 2 + 3 = 8 \implies \boxed E$[/hide]

[hide]Obviously, the answer is simple $3(3) - 1=8$ because we are adding 1 and subtracting 2 from the triangle's perimeter.[/hide]


A      triangle       ABC    is   turned    about   the  vertex  A  in  the plane  of  the

triangle   into        the      position      of       AB'C'.If       the       line    AC

bisects   the   line   segment     BB'.Prove   that the  line  AB' bisects   the line segment

CC'

AB=AB',AC bisect BB'
Therefore,angleB'AC'= angleBAC=angleB'AC
AC=AC',angleB'AC'= angleB'AC
Therefore, AB' bisect CC'


[hide="da answer"]
i guess you could just do guess and check so...
numbers that have two or more of the same digit between 100 and 325 are...
between 100 and 110 there are[b]2[/b]
100-110 are [b]2[/b]
111-120 are [b]9[/b]
121-130 are [b]2[/b]
131-140 are [b]2[/b]
141-150 are [b]2[/b]
151-199 are [b]10[/b]
200-210 are [b]3[/b]
211-220 are [b]3[/b]
221-230 are [b]9[/b]
231-300 are [b]15[/b]
301-310 are [b]1[/b]
311-325 are [b]3[/b]

total them up and u get $61 keychains$[/hide]

there are alot of ways you could mess up.  i probably made a mistake.  Well, we'll see.

[quote="FoRgE_BlaDe2"]Lift tickets are numbered 100-325. You can win a key chain if your tifket number has a two or more digits that are the same. If all the tickets are sold, how many key chains could be won? Show all your work plz...[/quote]

I would do it this way:

[hide]
Suppose the first two digits are the same. The first two digits could then be 1 and 1 or 2 and 2 (not 3 and 3 because numbers only go up to 325).

11_ <- 10 combinations (last digit can be any number from 0-9)
22_ <- 10 combinations

Now, suppose the first digit and the third digit are the same.

1_1 <- 9 combinations (we have already counted 111)
2_2 <- 9 combinations (we have already counted 222)
3_3 <- 3 combinations (0, 1, or 2 for the middle number)

Now, suppose the second and third digits are the same.

_11 <- 2 combinations (0 cannot be the first digit, we have already counted 111, so only 2 and 3 work)
_22 <- 2 combinations (0 cannot be the first digit, we have already counted 222, so only 1 and 3 work)
_33 <- 2 combinations (0 cannot be the first digit, 333 is too large, so only 1 and 2 work)
_44 <- 2 combinations (same as above)
_55 <- 2 combinations (same as above)
_66 <- 2 combinations (same as above)
_77 <- 2 combinations (same as above)
_88 <- 2 combinations (same as above)
_99 <- 2 combinations (same as above)

Adding them all up, I got 60 combinations.

Again, there is room for error...but math92 and my answers are off by 1! :P
[/hide]

[quote="FoRgE_BlaDe2"][hide]You guys suck :D the answer is 62. Focus more![/hide][/quote]
we do not suck, there was a lot of ways you could make a careless error.

[hide="SpOiLeR!!!"]1st and 2nd digit same

11_, 10 tickets
22_, 10 tickets

1st and 3rd digit same

1_1, 10 tickets
2_2, 10 tickets
303, 313, 323, 3 tickets

2nd and 3rd digit same

_00, 3 tickets
_11, 3 tickets
_22, 3 tickets
_33, 2 tickets
_44, 2 tickets
_55, 2 tickets
_66, 2 tickets
_77, 2 tickets
_88, 2 tickets
_99, 2 tickets

add all up =66, but over counted when all three are equal- case 111, 222. subtract two for each, and have 62.

P.S. I didnt check my work.[/hide]

[quote="FoRgE_BlaDe2"]Sorry if I hurt ur feelings I was just joking :D about u guys sucking![/quote]it's okay, i didn't mean to make it sound so serious :D  :D


[quote]x(y^2)(z^3) <= ((x + y + y + z + z + z) / 6)^6[/quote]

That is correct by AM-GM. The problem is that the RHS of this inequality is not constant. We know that x+y+z=1, but we know very little about x+2y+3z. Try to cleverly modify your use of AM-GM so that the RHS that you get IS constant.

[quote="Fierytycoon"]Here is the problem:

Given that x, y, z > 0 and that x + y + z = 1, find the maximum value of
x(y^2)(z^3).

Now, what I did was use AM-GM, such that x(y^2)(z^3) <= ((x + y + y + z + z + z) / 6)^6. Since x + y + z = 1, we must have x = y = z = 1/3. However, this answer is obviously wrong, so I think I am doing something fundamentally incorrect. Can someone inform me of why my reasoning is wrong? Thanks.[/quote]

Doesn't x+y+y+z+z+z change though?  It would be greater if z increased, thus creating more room for x(y^2)(z^3) to be large.  So in this case equality is not necessarily optimal.

[quote]That is correct by AM-GM. The problem is that the RHS of this inequality is not constant. We know that x+y+z=1, but we know very little about x+2y+3z. Try to cleverly modify your use of AM-GM so that the RHS that you get IS constant.[/quote]

I have the proper solution, I'm just wondering why mine does not work.

Ok, the RHS of the inequality is not constant, but the inequality ALWAYS holds no matter what x, y, and z are. And for the inequality, the equality case is ALWAYS when x = y = z. Since we know that x + y + z = 1, we should be able to find that x = y = z = 1/3, right?

Yes, that is the case when the two will be equal.  However, if we can make the RHS larger, we could still make the left hand side larger as well (albeit not as large as we make the right).  So, if we pick z = 1/2, y=1/3, x=1/6, the RHS will be big.  The LHS may not be quite as large as the RHS, but it could still be larger than the RHS when x = y = z = 1/3.

Lets try Lagrangian Multipliers.

y^2*z^3 = K
2yxz^3 = K
3z^2xy^2 = K

Immediately, we have that

x = 1/2*y
x = 1/3*z

This gives us that 6x = 1, and x=1/6, y=1/3, z=1/2.

AM-GM solution: [hide]Try using AM-GM on (x)(y/2)(y/2)(z/3)(z/3)(z/3).[/hide]

Joel:

Ah, I see what you are saying. However, there is one problem: according to what you are saying, although we can use inequalities to place bounds on expressions, we can never really prove that the maximum value of an expression is some constant using inequalities. So even with zabelman's AM-GM solution, we can't prove that the expression to be maximized can't exceed the constant found.

[quote]Ah, I see what you are saying. However, there is one problem: according to what you are saying, although we can use inequalities to place bounds on expressions, we can never really prove that the maximum value of an expression is some constant using inequalities. So even with zabelman's AM-GM solution, we can't prove that the expression to be maximized can't exceed the constant found.[/quote]

Of course we can! If it did go above the constant we found with AM-GM, then we would be proving AM-GM wrong!

[quote]Of course we can! If it did go above the constant we found with AM-GM, then we would be proving AM-GM wrong![/quote]

Hmm...good point! :)

Ah, so if we have a constant on the RHS, we're good, but if we have some expression, we don't know how much that expression can be increased.

Thanks for the help everyone.

Just so you know, what your proof did conclusively show is that the given expression is less than 1/64.  This is because we can take the supremum (maximum, although in this case it can't be achieved in the given region) of the RHS, which occurs when z = 1, x = y = 0.  Because the RHS is always smaller than 1/64 and the LHS is always smaller than some version of the RHS, the LHS must be smaller than 1/64 for all x, y, z.


Find all natural number n such that n^2|(2^n)+1.

IMO 1990 pb n°3.

Posted before...

Pierre.


geometry
rectangle
parallelogram
MATHCOUNTS
rhombus
set theory

[quote="happyme"]Sets A, B, C and D are all subsets of quadrilaterals. A is the set of rhombi, B is the set of rectangles, C is the set of parallelograms, and D is the set of kites. What is the set $(A\cap B)\cup(C\cap D)$?

a) squares
b) rectangles
c) parallelograms
d) rhombi
e) none of these

EDIT: Could you please put the logic behind your solution?
I'm new to set theory...[/quote]

[hide="there is not too much logic behind this problem, I think"]$A \cap B$ is a set of quadrilaterals that are both rhombi and rectangles - which are squares.

$C \cap D$ is a set of quadrilaterals that are both parallelograms and kites - which are rhombi.

Finally, the union of squares and rhombi are... rhombi. which gives $\boxed{d)}$.

Set theory in MATHCOUNTS is oten not difficult; you only need to know principle of inclusion-exclusion (aka PIE) and using Venn diagram... $\cap$ means "and" and $\cup$ means "or."[/hide]

[quote="happyme"]Sets A, B, C and D are all subsets of quadrilaterals. A is the set of rhombi, B is the set of rectangles, C is the set of parallelograms, and D is the set of kites. What is the set $(A\cap B)\cup(C\cap D)$?

a) squares
b) rectangles
c) parallelograms
d) rhombi
e) none of these

EDIT: Could you please put the logic behind your solution?
I'm new to set theory...[/quote]
[hide="answer"] It is d, because:
the intersection, as in the "members" of the sets common to one another, of A (rhombus) and B (rectangles) is square. The intersection of C (parallelograms) and D (kites) are rhombuses.
Therefore, the union, or both resulting sets combined, is d, or rhombuses, as squares are rhombuses.
[/hide]

[quote="happyme"]Did you see my edited problem, or my original one?[/quote]

i saw the original.


There are $ N$ stones in a pile. Two players alternately take stones from the pile. A player in turn takes a number of stones that divides the number of stones taken by his opponent in his last move. The first player in his first move can take an arbitrary number of stones, but at least one and not all $ N$. The player who picks up the last stone wins the game. What is the smallest $ N\geq 2008$ for which the second player has a winning strategy.

Clearly, the player who's presented with an odd number can win.  Then we can assume $ N$ is even, and that neither player will ever pick up an odd number of stones.

Now the problem is reduced to a $ \frac{N}{2}$-stone game.  By the argument above, the problem is equivalent to a $ \frac{N}{4}$-stone game, and so on...

It then is reduced to a $ 2$-stone game in which player 2 wins. (because the game cannot be equivalent to a game with an odd number of stones)

Hence, $ N$ is a power of $ 2$, so our answer is $ 2048$.

Indeed, nice solution to rather nice problem  :lol:

Maybe you can try some other problems I posted in this forum. But I warn you: they're quite challenging  :)


geometry
3D geometry
group theory
abstract algebra
modular arithmetic
superior algebra
superior algebra unsolved

[quote="mtphaovibul"]Prove that every group of order 1575 is solvable.  Equivalently, there aren't no simple group of order 1575.[/quote]

Of which level must the proof be ? There is a well known theorem of Feit and Thompson which asserts that every finite group of odd order is solvable, but only specialists of group theory have a chance to read the proof one day, I think...
Well, the following statement, much more elementary, is proved in the Introduction of Rotman (4th edition, cor. 7.55, p. 197) : Let $ G$ be a nonabelian simple group, and let $ p$ be the smallest prime divisor of $ \vert G \vert$ (i.e. of the order of $ G$). Then either $ p^{3}$ divides $ \vert G \vert$ or $ 12$ divides $ G$.
Thus : a nonabelian simple group of odd order is divisible by the cube of a prime.
Now, it is a classical fact that if a group $ G$ has a normal subgroup $ H$ such that $ H$ and the factor  group $ G/H$ are both solvable, then $ G$ is solvable.
If I'm not wrong, one can thus prove by recurrence  on the order that every finite group with odd order not divisible by the cube of a prime is solvable.
There is perhaps a more elementary proof, but why bother ?

Friendly,
P.

[quote="mtphaovibul"]I am aware of that, in this case I try to find a proof that use only sylow-theorem and counting argument.[/quote]

Let us try this.

Let $ G$ be a group of order $ 1575 \equal{} 9 \times 7 \times 25$.

First fact : if $ G$ has no normal subgroup of order $ 25$, it has exactly $ 21$ subgroups of order $ 25$. (Sylow theorem : the number of the Sylow $ 5$-subgroups is $ \equiv 1 \pmod{5}$ and divises $ 63$. The only divisors of $ 63$ which are  $ \equiv 1 \pmod{5}$ are $ 1$ and $ 21$, and $ 1$ is excluded by hypothesis.)

Second fact : if $ G$ has no normal subgroup of order 5 and no normal subgroup of index 3, then any two subgroups of order $ 25$ of $ G$ have trivial intersection.
Let $ A, B$ be two subgroups of order $ 25$ of $ G$ with nontrivial intersection and let us deduce a contradiction.
Let $ I$ denote the intersection of $ A$ and $ B$. (Thus $ I$ is of order $ 5$.) A group of order $ p^{2}$, with $ p$ prime, is abelian, thus $ A$ and $ B$ are abelian, thus each element of $ A$ and each element of $ B$ commute with each element of $ I$, thus $ A$ and $ B$ are both contained in the normalizer $ N_G(I)$ of $ I$. Thus $ A$ and $ B$ are two distinct Sylow $ 5$-subgroups of $ N_G(I)$. By Sylow theorem, the order of $ N_G(I)$ is of the form $ 25 \times d$, where $ d$ is a divisor of $ 63$ which has a divisor $ d'$ such that $ d' \equiv 1 \pmod{5}$ and $ d' > 1$.
We must have $ d' \equal{} 21$, thus $ d$ is $ 21$ or $ 63$.
If $ d \equal{} 63$, then the order of $ N_G(I)$ is $ 25 \times 63$, thus $ N_G(I)$ is $ G$, thus $ I$ is a normal subgroup of $ G$ with order $ 5$, which contradicts the hypothesis of the second fact. If $ d \equal{} 21$, then the order of $ N_G(I)$ is $ 25 \times 21$, thus the number of conjugates of $ I$ is $ 3$.
Now, $ G$ acts on the conjugates of $ I$ by conjugation and this action is nontrivial because it is transitive. Thus the kernel of this action is a proper normal subgroup $ K$ of $ G$ such that $ G/K$ is isomorphic to a subgroup of $ S_{3}$ (symmetric group), thus the index of $ K$ divides 6; since the order of $ G$ is odd, the index of $ K$ is odd, thus it is $ 3$, which contradicts the hypothesis of the second fact.
Thus the second fact is proved.

Third fact : let $ H$ be a finite group and $ p$ a prime such that $ p^{2}$ divides the order of $ H$. If any two Sylow $ p$-subgroups of $ H$ have trivial intersection, the number of Sylow $ p$-subgroups of $ H$ is $ \equiv 1 \pmod{p^{2}}$.
Proof. Choose a Sylow $ p$-subgroup $ P$ of $ H$ and let it act on the set of all Sylow $ p$-subgroups of $ H$ by conjugation. Use the fact that an element $ x$ of $ P$ fixes a Sylow $ p$-subgroup $ Q$, i.e. normalizes it, if and only if $ x \in P \cap Q$. (See for example Rotman, 4th ed., lemma 4.11, p. 78; it's easy.)
There is one orbit with one element (the element $ P$) and all other orbits have $ \vert P \vert$ elements (because the stabilizer of an element of such an orbit is reduced to unity), which proves our thesis.

Now, put $ H \equal{} G$ and $ p \equal{} 5$ in the third fact. In view of the first fact, you find that if $ G$ has no normal subgroup of order $ 25$, there are two Sylow $ 5$-subgroups whose intersection is not trivial. In view of the second fact, $ G$ has either a normal subgroup of order $ 5$ or a normal subgroup of index $ 3$.

Thus, in any case : $ G$ has either a normal subgroup of order $ 5$, a normal subgroup of order $ 25$ or a normal subgroup of index $ 3$.

This proves that $ G$ is not simple.
In order to prove that $ G$ is solvable, it would suffice to prove that each group of order 3, 5, 25, 1575/3, 1575/5 and 1575/25 is solvable. The first three are trivial, of course.

Perhaps there is a simpler proof, I don't know.

Friendly,
P.


My favorite is probably public shaming game. What about you guys?

You never specified it to be in Fun Factory. Therefore, my favorite game is Call of Duty 4.

mine is For The Win, u never said in the forums

Everything on this forum makes me lose now.

Well I'm [b]sorry[/b], but it is my favorite game.

Question and Answer, so easily. I'm the silliest kid there.

I lost.  :noo:

Ha ha, you lost.  :harhar:

I already lost  :P
Do I lose again?
That would be pointless,

D[size=84]ARN YOU[/size], [size=100]I[/size] [size=75]LOST[/size].

Just felt like talking like Death there.

Super Smash Brothers Melee.

WHERE IS STARCRAFT. I AM REQUESTING KOREAN BACKUP!

Why'd we quit hurt and heals? People like them.

[quote="Wickedestjr"]Why'd we quit hurt and heals? [/quote]

Because I said so.

[quote="Wickedestjr"]People like them.[/quote]

No they don't.

Then why did 22% of the users that answered this poll say that hurt and heals were their favorites?
I think that is unfair that you can quit them, just because you don't like them.  :(

*opens book*
Once upon a time, there was a hurt and heal. When it died, another hurt and heal was created. When that died, two hurt and heals were created. When one of those died, three hurt and heals were created. When two of those died, five hurt and heals were created. 78% of the people called it spam, and 7h3.D3m0n.117 the Great deleted them all. Now the spammers are mad at him because of it.
The End.
*closes book*

Hmm???

 :clap2:  That was a pretty entertaining story.

But is it really spamming if we are following the rules of the game? It doesn't count as a post anyway, because it is in FF.

I was never against the Hurt n Heals. But it [i]is[/i] annoying when you wake up one morning to find half of the first page of FF flooded with them. Currently, there are three Hurt and Heals present. I believe that is a reasonable amount. However, when one game ends, I will allow only [b]one[/b] new game of HnH to replace it. If you want to create a new Hurt and Heal, please send me a PM right after a pre-existing Hurt and Heal ends. The PM should include the name of the title, the subjects in question. The first person to send me the PM has the right to create the thread. Any others will be locked. Fair enough?

[quote="1=2"]...and [b]7h3.D3m0n.117 the Great[/b] deleted them all.[/quote]

Brownie points to you, 1=2  :lol:

[quote="7h3.D3m0n.117"]I was never against the Hurt n Heals. But it [i]is[/i] annoying when you wake up one morning to find half of the first page of FF flooded with them. Currently, there are three Hurt and Heals present.
[/quote]
QFT.
If you don't understand what does this mean: ask chenhsi or Brut3Forc3 or anyone who plays mafia in MafiaScum.

[quote="Wickedestjr"]Oh!!! Yeah, that is fair. I didn't think that you were going to let us make anymore at all. I was confused. That is fair. Sorry for complaining earlier.[/quote]

Glad we could come to an agreement  :) .

And I'm going to lock this because this is getting horribly off topic (although I doubt anyone would raise objections  :P ).


[quote="Redriver"]And this problems is much harder !
Give $a,b,c\ge 0$ such that $abc=1$
Prove that :
 $\frac{a^{2}}{(2a+b)(1+ab)}+\frac{b^{2}}{(2b+c)(1+cb)}+\frac{c^{2}}{(2c+a)(1+ca)}\ge \frac{1}{2}$[/quote]
Let $a=\frac{y}{x}$, $b=\frac{z}{y}$ and $c=\frac{x}{z}$, where $x$, $y$ and $z$ are positives.
Hence, $\sum_{cyc}\frac{a^{2}}{(2a+b)(1+ab)}=\sum_{cyc}\frac{y^3}{(2y^2+xz)(x+z)}=\sum_{cyc}\frac{y^4}{(2y^2+xz)(x+z)y}\geq$
$\geq\frac{(x^2+y^2+z^2)^2}{\sum\limits_{cyc}(2y^2+xz)(x+z)y}=\frac{(x^2+y^2+z^2)^2}{\sum\limits_{cyc}(2x^3y+2x^3z+2x^2yz)}=\frac{x^2+y^2+z^2}{2(xy+xz+yz)}\geq\frac{1}{2}$.


Let $ ABC$ be a triangle and let $ D,E,F$ be the tangency points of its in circle $ (I)$ with $ BC,CA,AB$, respectively.Denote by $ B_1,C_1$ the second points where $ BI,CI$ intersect the circumcircle $ (O)$ of $ \triangle ABC$.Let $ O_1$ be the midpoint of the segment $ B_1C_1$.The circle centered at $ O_1$ with radius $ O_1D$ intersects $ (O)$ at $ X$ and $ Y$.Prove that $ X,Y,E,F$ are collinear.

I need a short solution without calculating so much.Thanks.

This problem is one step of problem at here:
http://www.mathlinks.ro/viewtopic.php?t=253661

See the nice proof of [b]April[/b].


Let $ n\geq 3$ be integer. Arranging $ n$ integers $ 1,\ 2,\ \cdots ,\ n$ in circle, we can get $ n$ adjacent product of 2 numbers.
Consider the way such that the sum of the product of $ n$ numbers is maximal and denote the sum by $ a_n$. Find $ a_n$.

I have found that the maximum sum is formed by placing the numbers in one of the following order, depending on the case:

Case $ n$ is even: $ 1,3,5,7,\dots,n \minus{} 1,n,n \minus{} 2,\dots,4,2$.
Case $ n$ is odd: $ 1,3,5,7,\dots,n,n \minus{} 1,n \minus{} 3,\dots,4,2$.

(Basically, place the odds in ascending order and then the evens in descending order.)

I have not yet found a way to express this sum in closed form, nor a way to prove it.

Edit: See [url=http://www.research.att.com/~njas/sequences/A110610]here[/url]. This appears to have been from the Putnam.

This is Putnam 1996 B3 and [url=http://www.research.att.com/~njas/sequences/A110610]A110610[/url] in the [url=http://www.research.att.com/~njas/sequences]OEIS[/url].

Thank you for the information, JBL, Yongyi781.

The problem was posed in practice[trial] examination of Tokyo University entrance exam on 15 August.

I have just found the source. :lol: That was 1996 Putnam B3.[url=http://www.unl.edu/amc/a-activities/a7-problems/putnam/-pdf/1996s.pdf]Solution[/url]


let abc=1 prove that

a 3  + b 3  + c 3  + (ab) 3  + (bc) 3  + (ca) 3  >= 2(a 2 b + b 2 c + c 2 a)

Two times Schur+ AM-GM. Apply Schur for $ a,b,c$ then Schur for $ ab, bc, ca$ then AM-GM.

I have heard about it but I don't know it.
Help me out!! :?

I tried to solve this problem for 3 days and I cannot.
Could at least try?
If it turns out to be very easy don't even post the solution  :blush:

No, you should not think like that. Ok, Schur inequality is $ a^3+b^3+c^3+3abc$ greater than $ a^2(b+c)+b^2(c+a)+c^2(a+b)$. Replace here first a,b,c by a,b,c (smart substitution :D) and then $ a,b,c$ by $ab,bc,ca$ and add the two inequalities. All it remains to prove then is just an application of AM-GM. Is it clear now?


linear algebra
matrix
vector
algebra
polynomial

Let $ T: V\rightarrow V$ be defined by $ T(f(x))\equal{}f(x)\plus{}f(2)x$ where $ V\equal{}P_{3}(F)$.  My goal is to find an ordered basis $ \beta$ such that $ [T]_{\beta}$ is a diagonal matrix.  Now I plugged in the standard matrix and got a matrix.  I then found the eigenvalues (1,3).  However, when I went to find the eigenvectors, I got a vector of all 0's.  I know the answer is supposed to be $ \beta\equal{}\{\minus{}2\plus{}x,\minus{}4\plus{}x^{2},\minus{}8\plus{}x^{3},x\}$.  Any thoughts?

If we write the basis in the order $ \{1,x,x^2,x^3\},$ the matrix of the transformation should be
\[ \begin{bmatrix}1&0&0&0\\1&3&4&8\\0&0&1&0\\0&0&0&1\end{bmatrix}\]
Is that what you have? The eigenvalues are indeed $ 1$ and $ 3,$ and the eigenvalue $ 1$ has geometric multiplicity $ 3.$

I would add that there is no such thing as "the" answer - a basis is never unique. That is particularly to be noted in a case like this in which there's a 3-dimensional eigenspace. There are many choices.

That is indeed what I have.  When I go about finding the eigenvectors though, I get that all four terms are 0.  How would I go from what I have to the basis that I provided?  Thanks.

Have you checked your calculations? Getting all four terms zero basically violates the definition of eigenvalue.

Subtract $ 3$ times the identity:
\[ \begin{bmatrix}\minus{}2&0&0&0\\1&0&4&8\\0&0&\minus{}2&0\\0&0&0&\minus{}2\end{bmatrix}\]
Row reduce that:
\[ \begin{bmatrix}1&0&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\end{bmatrix}\]
There's one free variable, the second one. You can let that be arbitrary, while the first, third, and fourth variables must be zero. That means that $ \begin{bmatrix}0&1&0&0\end{bmatrix}^T$ is an eigenvector; this corresponds to the polynomial $ x.$

Now subtract $ 1$ times the identity from the original matrix:
\[ \begin{bmatrix}0&0&0&0\\1&2&4&8\\0&0&0&0\\0&0&0&0\end{bmatrix}\]
This has rank $ 1.$ It's almost in row echelon form already; all you have to do is interchange the top two rows. That's a pivot in the first column, while the second, third, and fourth columns represent free variables. Hence we have a three-dimensional eigenspace, which you can get by making arbitrary assignments of the last three variables. For instance, if we let the second variable be $ 1$ and the third and fourth zero, we get that the first variable must be $ \minus{}2,$ giving us the vector $ \begin{bmatrix}\minus{}2&1&0&0\end{bmatrix}^T,$ or $ \minus{}2\plus{}x.$ Similar arbitrary assignments will get us $ \minus{}4\plus{}x^2$ and $ \minus{}8\plus{}x^3.$

Okay, thanks.  I just got that earlier today.


[quote="yaa"]Prove that :$ (a^3 \plus{} b^3 \plus{} c^3)(a^2 \plus{} b^2 \plus{} c^2)\geq3(a^4b \plus{} b^4c \plus{} c^4a)$ with a,b,c>0[/quote]

your inequality dose not hold...

try $ a\equal{}3,b\equal{}2,c\equal{}1$


function
integration
calculus
derivative
trigonometry
modular arithmetic
limit

Find the Fourier series of the fuction on the interval:
\[ f(x)\equal{}cosh(\pi x)\]     \[ \minus{}1 \leq x \leq 1\]

Write $ \cosh(\pi t)$ as
$ \frac {e^{\pi t} \plus{} e^{ \minus{} \pi t}}{2}$

Also you can compute it with integrals.You see that your function is pare and you can develop it into a cosinus fourier series.
From now on your function developed in Fourier series will look like :

f ~ $ \frac{a_0}{2}\plus{} \sum_{n\equal{}1}^{\infty} a_n\cos(n \pi x)$

where $ a_n\equal{}\int^{1}_{\minus{}1} f(x) \cos(n \pi x)\,dx \equal{}2\int^{1}_{0} f(x) \cos(n \pi x)\,dx.$
From there it is simple to compute $ a_n$ and $ a_0$ considering $ \cosh\equal{}\cos(j x)$
.

I can't understand what you are suggesting.

We're working with functions periodic of period 2. Our Fourier coefficients are defined by
\[ \widehat{f}(k) \equal{} \frac12\int_{ \minus{} 1}^1f(x)e^{ \minus{} i\pi kx}\,dx
\]
from which we reconstruct the function by
\[ f(x) \equal{} \sum_{k \equal{} \minus{} \infty}^{\infty}\widehat{f}(x)e^{i\pi kx}.
\]
One identity I'll use has to do with derivatives: $ \widehat{f'}(k) \equal{} i\pi k\widehat{f}(k).$

This particular function $ f$ is real and even, so its Fourier transform will be real and even (and we will be able to rewrite it as a cosine series). $ f$ is continuous, but not $ C^1.$ In particular, $ f'$ is bounded but has a jump discontinuity at $ 1.$ From that I predict that $ \widehat{f}(k)$ will be $ O(k^{ \minus{} 2})$ as $ k\to\pm\infty$ (which will mean that the Fourier series will converge absolutely and uniformly.)

We have $ f'(x) \equal{} \pi\sinh(\pi x)$ on $ ( \minus{} 1,1),$ which has a jump discontinuity with a downward jump of size $ \minus{} 2\pi\sinh(\pi)$ at $ x \equal{} 1.$ That gives us that $ f''(x) \equal{} \pi^2\cosh(\pi x) \minus{} 2\pi\sinh(\pi)\delta(x \minus{} 1).$

That gives us the following differential equation: $ f''(x) \minus{} \pi^2f(x) \equal{} \minus{} 2\pi\sinh(\pi)\delta(x \minus{} 1).$

The Fourier transform of $ \delta(x \minus{} 1)$ is $ \frac12\int_{ \minus{} 1}^1\delta(x \minus{} 1)e^{ \minus{} i\pi kx}\,dx \equal{} \frac12e^{ \minus{} i\pi k} \equal{} \frac {( \minus{} 1)^k}{2}.$

We take the Fourier transform of the differential equation to get

$ \minus{} \pi^2k^2\widehat{f}(k) \minus{} \pi^2\widehat{f}(k) \equal{} \minus{} \pi\sinh(\pi)( \minus{} 1)^k$

$ \widehat{f}(k) \equal{} \frac {\sinh(\pi)( \minus{} 1)^k}{\pi(k^2 \plus{} 1)}.$

This satisfies our expectation that $ \widehat{f}$ is real, even and $ O(k^{ \minus{} 2})$ for large $ k.$ Our series is

$ f(x) \equal{} \frac {\sinh(\pi)}{\pi}\sum_{k \equal{} \minus{} \infty}^{\infty}\frac {( \minus{} 1)^ke^{i\pi kx}}{k^2 \plus{} 1} \equal{}$ $ \frac {\sinh(\pi)}{\pi}\left(1 \plus{} \sum_{k \equal{} 1}^{\infty}\frac {2( \minus{} 1)^k\cos(\pi kx)}{k^2 \plus{} 1}\right).$

Putting $ x \equal{} 0$ in this expression gets us that $ \sum_{k \equal{} \minus{} \infty}^{\infty}\frac {( \minus{} 1)^k}{k^2 \plus{} 1} \equal{} \frac {\pi}{\sinh(\pi)}.$ Try $ x \equal{} 1$ to see what you get there.

Prof. Kent I would be grateful if you clarify few things;
[quote="Kent Merryfield"]
One identity I'll use has to do with derivatives: $ \widehat{f'}(k) \equal{} i\pi k\widehat{f}(k).$ [/quote]
Did you miss a minus there? That is, should it be $ \widehat{f'}(k) \equal{} \minus{} i\pi k\widehat{f}(k)$ ?
[quote="Kent Merryfield"]
$ f$ is continuous, but not $ C^1.$ In particular, $ f'$ is bounded but has a jump discontinuity at $ 1.$ [/quote]
I read few times your post, but I can't understand how come $ x\rightarrow \cosh{x}$ isn't $ C^1$ ( for that matter I thought it was analitic   :huh:  )
[quote="Kent Merryfield"]
From that I predict that $ \widehat{f}(k)$ will be $ O(k^{ \minus{} 2})$ as $ k\to\pm\infty$ (which will mean that the Fourier series will converge absolutely and uniformly.)[/quote]
This is the most interesting to me. How did you come up with that estimate? Maybe it has to do something with function being $ C^l$, $ l$ some integer ( but since your comment about $ f$ isn't $ C^1$ didn't make much sense, I wasn't not sure about it...) ?

[quote="Mr.Doe"][quote="Kent Merryfield"]
$ f$ is continuous, but not $ C^1.$ In particular, $ f'$ is bounded but has a jump discontinuity at $ 1.$ [/quote]
I read few times your post, but I can't understand how come $ x\rightarrow \cosh{x}$ isn't $ C^1$ ( for that matter I thought it was analitic   :huh:  )[/quote]

The function in question is [i]not[/i] defined by $ f(x) \equal{} \cosh \pi x$ on all of $ {\bf R}$.  Rather, it's the function $ f: {\bf R} \to {\bf R}$ with period 2 given by $ f(x) \equal{} \cosh \pi x$ when $ x \in [ \minus{} 1, 1]$.  Equivalently, if we consider the function $ g(x) \equal{} x \pmod 2$ to be $ g: {\bf R} \to [\minus{}1, 1)$ then the function $ f$ is given by $ f(x) \equal{} \cosh \pi g(x)$.

$ \widehat{f'}(k) \equal{} i\pi k\widehat{f}(k)$ is the correct sign. One way to see it formally: take
\[ f(x) \equal{} \sum_{k \equal{} \minus{} \infty}^{\infty}\widehat{f}(k)e^{i\pi kx}.
\]
and differentiate both sides with respect to $ x.$

------

I was reaching a bit with the presumptions when I claimed $ \widehat{f}(k) \equal{} O(k^{ \minus{} 2}),$ because I was really using something stronger than merely that $ f'$ is bounded. I was actually using that $ f$ is very smooth except at a finite number of points (one point, actually) and at that one point it is continuous and $ f'$ has a jump discontinuity. It really comes down to saying that $ f''(x)$ is a nice function plus a Dirac delta - in other words, looking ahead to the computational technique I would use.

But this sort of function is common: continuous and smooth except for some "corners" in the graph. See enough of them and the $ O(k^{ \minus{} 2})$ estimate becomes routine.

In order to understand my derivation, you have to see where the Dirac delta in $ f''$ comes from. Understanding that starts with what JBL just said. I do suggest drawing graphs, and drawing them over more than one period.

A further exercise:

Let $ g(x)\equal{}\cos\left(\frac{\pi x}2\right)$ on $ [\minus{}1,1],$ extended to be periodic of period $ 2.$

Show that $ g(x)$ is continuous but not $ C^1$ and that $ g'(x)$ has a jump discontinuity at $ 1.$

Copy the methods in my long post to the extent possible and use them to compute the Fourier series of $ g.$

What sum identity can you find by setting $ x\equal{}1$ in this series?

Fourier coefifcients are given by;
$ \widehat{g}(k)\equal{}\frac{1}{2}\int_{\minus{}1}^1g(x)e^{\minus{}ik\pi x}dx$, so our function will be given with the following expresion; $ g(x)\equal{}\sum_{k\equal{}\minus{}\infty}^{\infty}\widehat{g}(k)e^{ik\pi x}$.
We derive the identity that profesor Kent mentioned.  $ g'(x)\equal{}\sum_{k\equal{}\minus{}\infty}^{\infty}\widehat{g}(k)i\pi k e^{i\pi k x}$, multiplying by $ \frac{1}{2}e^{\minus{}il\pi x}$, where $ l\in\mathbb{Z}$, and integrating from $ \minus{}1$ to $ 1$ with respect to $ x$, we have;

$ \widehat{g'}(l)\equal{}\sum_{k\equal{}\minus{}\infty}^{\infty}\widehat{g}(k)ki\pi \frac{1}{2}\int_{\minus{}1}^{1}e^{ix\pi(k\minus{}l)}dx$, using orthogonality of functions $ e^{ik\pi x},k\in\mathbb{Z}$, only the term $ k\equal{}l$ "survives", so we have; $ \widehat{g'}(l)\equal{}i\pi l\widehat{g}(l)$.

$ g'$ is given by $ g'(x)\equal{}\minus{}\frac{\pi}{2}\sin(\frac{\pi x}{2}),  x\in(\minus{}1,1)$, I'm going to argue that $ g'$ has a jump discontinuity at point $ \minus{}1$ ( to make things different from the last post ).
One can easily find that  $ \lim_{x\rightarrow \minus{}1\plus{}}g'(x)\equal{}\frac{\pi}{2}\sin(\frac{\pi}{2})$, and $ \lim_{x\rightarrow \minus{}1\minus{}}g'(x)\equal{}\lim_ {x\rightarrow 1\minus{}}g'(x)\equal{}\minus{}\frac{\pi}{2}\sin(\frac{\pi}{2})$.
 So $ g'$ has a downward jump of size $ \minus{}\pi\sin(\frac{\pi}{2})$ at $ \minus{}1$.
We now have the following ODE;
$ g''(x)\equal{}\minus{}\big(\frac{\pi}{2}\big)^2\cos(\frac{\pi x}{2})\minus{}\pi\sin(\frac{\pi}{2})\delta(x\plus{}1)$, again the Fourier transform of $ \delta(x\plus{}1)$ equals $ e^{i\pi k}$,
taking the Fourier transform of the ode, we get;
$ \minus{}\pi^2k^2\widehat{g}(k)\plus{}\big(\frac{\pi}{2}\big)^2\widehat{g}(k)\equal{}\minus{}\frac{\pi}{2}\sin(\frac{\pi}{2})(\minus{}1)^k$.

From the equation we get the coefficients are given by;
$ \widehat{g}(k)\equal{}\frac{\sin(\frac{\pi}{2})}{2\pi}\frac{(\minus{}1)^k}{4k^2\minus{}1}$.

Profesor Kent, I would be glad if you could check this, and point out any mistakes  :) .

A couple of items:

1. $ \sin\left(\frac{\pi}2\right)\equal{}1.$ You should make that simplification.

2. The jump discontinuity at $ \minus{}1$ in $ g'(x)$ is an [i]upward[/i] jump. We should actually have

$ g''(x)\equal{}\minus{}\left(\frac{\pi}2\right)^2\cos\left(\frac{\pi x}2\right)\plus{}\pi\delta(x\plus{}1)$

(which is the same as $ \minus{}\left(\frac{\pi}2\right)^2\cos\left(\frac{\pi x}2\right)\plus{}\pi\delta(x\minus{}1)$. Working at $ \minus{}1$ compared to working at $ \plus{}1$ made no difference; $ 1$ and $ \minus{}1$ are equal $ \pmod{2}$ and are hence the "same" point.)

One thing to check, which has a bearing on item (2): the function $ g$ is positive (it's nonnegative everyhwere). $ \widehat{g}(0)$ is simply the average value of the function and must be positive. Check your formula: does it show $ \widehat{g}(0)>0?$

The overall structure looks sound. You just need to attend to those details.

Thank you for the quick reply.
I have question concerning 2. You claim that it's an upward jump, but somehow that is not clear to me, if we look the limit for left, at point $ \minus{} 1$ ( of $ g'$ ) we arive at value $ \frac {\pi}{2}$, and then we have a drop of $ \pi$. Does it mean that I should be always looking the function from left to right, and not the other way around ( like I was doing )?

Indeed $ \widehat{g}(0)$ is less then zero, I probably messed up something along the way (*) .

I must admit this is a great way to compute Fourier coefficients, usually I would use the formula for them ( and kill myself integrating the expression  :lol: ).

Edit: (*) That is, if instead of the drop, we have a jump of $ \pi$, then $ \widehat{g}(0)>0$.

For $ \minus{}3<x<\minus{}1,$ the function $ g(x)$ is not $ \cos\left(\frac{\pi x}2\right).$ Instead, we must remember that this is periodic of period $ 2$ and thus for $ \minus{}3<x<\minus{}1,$ we have $ g(x)\equal{}\cos\left(\frac{\pi(x\plus{}2)}2\right)\equal{}\minus{}\cos\left(\frac{\pi x}2\right).$ Hence in that same interval, $ g'(x)\equal{}\frac{\pi}2\sin\left(\frac{\pi x}2\right)$ and $ \lim_{x\to\minus{}1^\minus{}}g'(x)\equal{}\minus{}\frac{\pi}2.$

I do recommend drawing pictures of the graphs of $ g(x),g'(x),$ [i]etc.[/i] Even though I didn't physically do that, I am mentally imaging those graphs as I type this.


integration
calculus
derivative
algebra
polynomial
calculus computations

find $ a,b,c,d$ such that :    $ \int_{0}^{1}(e^t\minus{}at^3\minus{}bt^2\minus{}ct\minus{}d)^2.dt$
is minimal
:)

$ \gamma (t) \equal{} at^3 \plus{} bt^2 \plus{} ct \plus{} d$

$ I(a,b,c,d) \equal{} \int_0^1 (e^t \minus{} \gamma (t))dt \equal{} \int_0^1 (e^{2t} \minus{} 2e^t \gamma (t) \plus{} \gamma^2(t))dt$

$ I \equal{} \frac {e^2 \minus{} 1}{2} \minus{} 2\int_0^1 \gamma (t)e^tdt \plus{} \int_0^1 \gamma^2(t)dt \equal{}$

$ \left[\frac {e^2 \minus{} 1}{2} \minus{} 2\left(e(d \plus{} b \minus{} 2a) \minus{} (d \minus{} c \plus{} 2b \minus{} 6a)\right) \plus{} (\frac {a^2}{7} \plus{} \frac {ab}{3} \plus{} \frac {2ac \plus{} b^2}{5} \plus{} \frac {ad \plus{} bc}{2} \plus{} \frac {2bd \plus{} c^2}{3} \plus{} cd \plus{} d^2) \right]$

solving partial derivatives we get

$ I_a \equal{} \minus{} 12 \plus{} 4e \plus{} \frac {2}{7}a \plus{} \frac {1}{3}b \plus{} \frac {2}{5}c \plus{} \frac {1}{4}d$
$ I_b \equal{} 4 \minus{} 2e \plus{} \frac {1}{3}a \plus{} \frac {2}{5}b \plus{} \frac {1}{4}c \plus{} \frac {2}{3}d$
$ I_c \equal{} \minus{} 2 \plus{} \frac {2}{5}a \plus{} \frac {1}{4}b \plus{} \frac {2}{3}c \plus{} d$
$ I_d \equal{} 2 \minus{} 2e \plus{} \frac {1}{4}a \plus{} \frac {2}{3}b \plus{} c \plus{} 2d$

our min will occur when $ I_a \equal{} I_b \equal{} I_c \equal{} I_d \equal{} 0$

then we just have to solve an ugly system

This is the problem of Least Squared Method Problem.
Maybe an expert of satistics can solve easily. :lol:

Define the inner product $ f \cdot g \equal{} \int_{0}^{1} f(t) g(t) \, dt$, which induces a norm $ f \cdot f \equal{} \int_{0}^{1} f(t)^2 \, dt$.  We are minimizing the norm (distance) between $ e^t$ and the space of cubic polynomials, which we do by orthogonally projecting $ e^t$ on that space.  If I'm not mistaken, this projection is given by

$ \frac {e^t \cdot 1}{1 \cdot 1} 1 \plus{} \frac {e^t \cdot t}{t \cdot t} t \plus{} \frac {e^t \cdot t^2}{t^2 \cdot t^2} t^2 \plus{} \frac {e^t \cdot t^3}{t^3 \cdot t^3} t^3$.

the linear system has determinant expanding by shifting diagonals

$ det \equal{} \frac {2^4}{105} \plus{} \frac {1^4}{48} \plus{} \frac {2^4}{225} \plus{} \frac {1^4}{48} \minus{} \frac {1^4}{4^4} \minus{} \frac {2^4}{125} \minus{} \frac {1^4}{9} \minus{} \frac {2^4}{189} \equal{}$
$ 2^4\left(\frac {1}{105} \plus{} \frac {1}{225} \minus{} \frac {1}{125} \minus{} \frac {1}{189}\right) \minus{} \left(\frac {1}{16^2} \plus{} \frac {5}{72}\right) \equal{}$
$ \frac {256}{23625} \minus{} \frac {169}{2304} \ne 0$ since  $ \frac {odd}{even} \ne \frac {even}{odd}$

so the system is solvable. i think this is the simplest approach -.-

What do you mean?  Projection is essentially linear algebra, too.


limit
logarithms
integration
calculus
calculus computations

$ \lim_{t\to \plus{}\infty}\log t \int_{\log t}^{\plus{}\infty} e^{\minus{}\frac{x^2}{2}} dx > 0$

Thanks in advance!

The limit is 0. We have that

${ \lim\limits_{a\rightarrow \infty}a\int\limits_{a}^{\infty}e^{-x^{2}/2}}dx=\lim a\left(K-\int\limits_{0}^{a}e^{-x^{2}/2}dx\right)$

$ =\lim\frac{K-\int\limits_{0}^{a}e^{-x^{2}/2}dx}{1/a}=\lim\frac{a^{2}}{e^{a^{2}/2}}=0$,

where  $ K=\int\limits_{0}^{\infty}e^{-x^{2}/2}dx$.


rotation
calculus
integration
function
geometry
geometric transformation

Well I guess my last problem was a bit difficult so I'll give an easier problem.  I don't have a diagram so try to bear with the description.

Imagine a sherical shell of mass $ M$ on a tabletop (moment of inertia $ \frac{2}{3}MR^{2}$), free to rotate along its vertical axis.  A massless string is wrapped around the shell, which also runs along a pulley of radius $ R$, and moment of inertia $ I$.  The string wraps around the pulley and then drops off the table, attached to a block of mass $ m$, at a height $ h$ above the floor (so the block is suspended by the string, which passes over a pulley and then continues above the table where it wraps around the shell).  As the block falls, it pulls the string, causing the pulley and shell to spin.  Find the velocity of the block when it hits the floor.

I have found at least 2 ways to solve this problem.

So here is the solution if I understand the problem correctly.
I will just solve it with plain equations of motion.
But it can be solved using energy considerations, Lagrangiana etc. etc.

I assume that the shell is fixed, the rope doesnt slip on the shell etc.
Let the $ z$ axis points downwards, with the origin on the table.
So the equations of motion:
\[ m\ddot z \equal{} mg\minus{}F\]
\[ \dfrac23 MR^2\cdot \dfrac{\ddot z}{R}\equal{}F\cdot R\]

Plugging $ F$ from the second equation into the first one:
\[ mg\equal{}\left(m\plus{}\dfrac23 M\right)\ddot z\]
That is:
\[ \ddot z \equal{} \dfrac{3m}{3m\plus{}2M}g\]
Lets write the acceleration as this:
\[ \ddot z \equal{} \dfrac{d\dot z}{dz}\dfrac{dz}{dt}\equal{}\dfrac{\dot z\cdot d\dot z}{dz}\]

Plugging this into the previous equation:
\[ \dot z\cdot d\dot z \equal{} \dfrac{3m}{3m\plus{}2M}g\cdot dz\]
integrating:
\[ \dfrac{\dot z ^2}{2}\equal{}\dfrac{3m}{3m\plus{}2M}g\cdot z \plus{}C_1\]
So the velocity:
\[ \dot z \equal{}v\equal{} \sqrt{\dfrac{6m}{3m\plus{}2M}g\cdot z \plus{}C}\]
The initial condition is: $ v(z\equal{}0)\equal{}0$. So the integration constant: $ C\equal{}0$.
So the velocity as a function of height is:
\[ v(z)\equal{}\sqrt{\dfrac{6m}{3m\plus{}2M}g\cdot z}\]
We are looking for the velocity at the floor. So:
\[ v(h)\equal{}\sqrt{\dfrac{6m}{3m\plus{}2M}gh}\]

I hope I didnt mess up anything, because I was straight latexing, without writing anything down...

If I understand the problem correctly, we can just use conservation of energy and get

$ v \equal{} \sqrt{\frac{6mghR^2}{(3m \plus{} M)R^2 \plus{} 3I}}$.

You can use principles of rotation and the equations of motion, or you can use conservation of energy.  I don't have the answer in front of me but I'll re-work it and confirm.

[i]Thaakisfox[/i] forgot the pulley's moment of inertia,  [i][b]I[/b][/i], of course, if the rope doesn't slides over that. (If there isn't any friction, he would be right).

[i]durt[/i] lost somewhere a factor of 2 from the shell's moment of inertia...
So, if the rope doesn't slides on the pulley,

\[ v \equal{} \sqrt{\frac{6mghR^2}{(3m \plus{} 2M)R^2 \plus{} 3I}}.\]

The acceleration could be obtained from movements equations (shell, pulley and block) and then Torricelli gives the velocity.

We can also obtain it from mechanical energy conservation:

\[ {v^2 \over 2}({2\over3}M \plus{} m \plus{} {I \over R^2}) \equal{} mgh\]

and leave Lagrange and etc. etc. rest in peace...

The form I have it in is a bit different but I'm almost positive they are equivalent so Immanuel Bonfils is correct.  Here is what I have, just to make sure

$ \sqrt{\frac{2mgh}{m+\frac{I}{R^{2}}+\frac{2M}{3}}}$

Just remember: Immanuel Bonfils is ALWAYS right... lol

BTW Immanuel, are you French?

Hmm. Yes, I automaticaly assumed the pulley to be ideal....
 :blush:

No, Immanuel Bonfils is not ALWAYS correct. :blush: See some of my old problems.  This just happens to be an easier one.

I'm far to pretend perfection, but if you are spiking about your (actually Berkeley's) problem 2007, look it better to see that, without any image (before Conjurer's post with im.JPG) my solution was quite consistent. By the way read HilbertThm90 last post on the subject.

Bu it's OK. Let's go ahead, and I want to thank you for your excellent contribution in the forum. Good job. Keep it like that, please


From a pile of 100 pennies, 100 nickels, and 100 dimes, select 21 coins which have a total value of exactly 1 dollar. In your selection you must also use at least one coin of each type. How many coins of each of the three types should be selected?

Pennies  =          Nickels  =     Dimes  =

$ p\plus{}n\plus{}d\equal{}21$

$ p\plus{}5n\plus{}10d\equal{}100$

$ p\equal{}21\minus{}n\minus{}d$

$ 21\plus{}4n\plus{}9d\equal{}100$

$ d\equal{}3, n\equal{}13, p\equal{}5$.


geometry
geometric transformation
algebra solved
algebra

Hello Friends.
                    The following problem is from Elimination round of 11 klass. It was solved only by one contestant during contest. Guess who ? I Think its Andrey Badzyan ( andrew ) .

 Given positive integers a,b,c,d all greater than 1. They satisfy the relation :
  a^b^c^d = d^c^b^a .  Prove that a=d and b=c .

   Have a nice time solving this one :D

You have posted it long time ago (Power Tower equation). Maybe andrew wants to post his solution. I'm really interested.

hmm...if i'm not wrong i just solved in half an hour using some standard methods...first, we see that we must $a=x^{\alpha}, d=x^{\delta}$, where we may assume that $\alpha, \delta$ have no common divisor. now, write $b=(\alpha)^n(\delta)^m\beta$, where $\beta$ is not divisible by $\alpha$ nor $\delta$, analogous for c. now comparing the powers of $\alpha$ on both sides(this is possible: if their difference is not 0, then we have an $\alpha$ on one side, which has to divide $\beta$ or $\gamma$ respectively, which is not possible), we obtain in the case $\alpha, \delta \neq 1$, that $b,c$ have no common divisor, and this would force $\alpha=c^{b^{x^{\alpha}}}$, contradiction by simple inequality. so we have $\alpha=\delta=1$, so we have $a=d$. now doing something similar one more time, we obtain $b=c$. i don't know if i'm wrong somewhere.

Peter

Hi.
     I think my translation is incorrect.
      If we write it like this a^{b^(c^d)} = d^{c^(b^a)} . Does this makes any difference?
 As far as difficulty is concerned andrew himself said to me in a PM about this problem that this was solved only by one contestant .

 Those who know Russian can check out the problem at St. PBMO site.

sorry, my proof is wrong. the thing with power of $\alpha$ does indeed not work, sorry. i will try to find a new proof.

Peter

I think I solved this terrible problem. As hxtung says, " I'll post my soln! " :D

When one of $a,b,c,d$ is 1 it;s easy. So let $a,b,c,d>1$
As Peter mentioned $a=x^{\alpha}, d=x^{\beta}$, $(\alpha, \beta)=1$.
Then $\frac{\alpha}{\beta}=\frac{c{}^b{}^a}{b{}^c{}^d}$.
Now if $e=(b,c)$ and $d<a$ then both $c{}^b{}^a, b{}^c{}^d$ are perfect $e^d$ powers.
Hence so is $\beta$ which means either $e=1$ or $\beta=1$.
The first case is obvious.
Now the second means like above that $e{}^{b{}^a-c^d}|\alpha$.
Now we use the following fact : if $a,b$ are integers $a>b$ then
 $a^n-b^n>a^{n-1}$
Now we get $\alpha=\frac{c{}^b{}^a}{b{}^c{}^d}$.
If $e=(b,c)>1$ and if we let $p|\alpha$ then applying fact
(we see that the powers of $p$ i the denominator and numerator are of form $k{}^e{}^d$ )we get that the power of $p$ in $\alpha$ is at least e^{\alpha}^{e^d-1} which is contradiction.

Is my proof true?

First, I claim that  b,c have the same prime factors. ....So, we can write b=y^m, c=y^n  with   natural numbers.
Harazi, If $b,c$ have same prime factors, it doesn't mean they are $y^m, y^n$
Maybe I didn't get something in your proof

Yes, iura, you are right, I'm completely idiot. The proof is totally wrong. Sorry!

[quote="iura"]
Now if $e=(b,c)$ and $d<a$ then both $c^{b^a}, b^{c^d}$ are perfect $e^d$ powers.[/quote]

I don't understand this point. Can you prove it in detail?

I say 4a$ is a $k$ power iff $a=b^k$ for some $b$.
Now $b^a$ and $c^d$ are both divisible by $e^d$, so result

iura, I don't understand your solution at all. How do you prove the following two statements?

1) either  $e=1$ or $\beta=1$.

2) The first case is obvious.  ($e=1$ is obvious)

iura...i don't understand how you conclude that $\beta$ is a perfect $e^d$ power...i only see that $\frac{\alpha}{\beta}$ is one...but maybe i'm just not seeing something.

Peter

Peter: If $\frac{\alpha}{\beta}$ is a $k $ power and $\alpha, \beta$ are coprime the
$\alpha, \beta$ are also $k$ powers!
Mozilla: Suppose $\beta>1$ and $e>1$.
Then as I said $\beta$ is a $e^d$ power so \beta=u^{e^d}
Now one can obviously prove that $\beta>d$ contradicting $x^{\beta}=d$.
If $e=1$ then $b^{c^d}, c^{b^d}$ are coprime and so
$\beta=b^{c^d}, \alpha=c^{b^d}$. Now one can prove again that $\beta>d$ and again the same contradiction!

iura, than you very much for answering my questions. :) But I still have problem. :blush: Please explain the following to me because I can't proof it.

[quote="iura"]
the power of $p$ in $\alpha$ is at least $e^{{\alpha}^{e^d-1}}$
[/quote]


inequalities
function
calculus
derivative
inequalities proposed

[quote="zhaobin"][quote="siuhochung"][quote="zhaobin"]assume $a \leq b \leq c$,
so we have to prove $3a \leq 1+abc$
the same as $3a \leq 1+ab \sqrt{9-a^2-b^2}$
leq $b \sqrt{1-a^2-b^2} \geq a  \sqrt{9-2a^2}$
so we have to prove $3a \leq 1+a^2  \sqrt{9-2a^2} $
I think it will not be hard. :)  :)
hope I 'm right. :)  :)[/quote]

i think the last inequality is false.[/quote]
why?when $a  \leq  \sqrt{3}$[/quote]
sorry i meant this.
$b \sqrt{9-a^2-b^2} \geq a  \sqrt{9-2a^2}$
can u prove it?

zhaobin could you please edit your last post to present a nice and complete proof of the problem? thanks :)

[quote="Valentin Vornicu"] 1,000,000 ROL (~40$ \$)[/quote]

do u know the show "who wants to be a millionaire?"  :P

since we know $\min\{a,b,c\}\le\frac 3{\frac1a+\frac1b+\frac1c}$
we only have to prove $1+abc\ge \frac 9{\frac1a+\frac1b+\frac1c}$

$1+abc\ge \frac 9{\frac1a+\frac1b+\frac1c}=\frac{9abc}{ab+bc+ca}$
$\Leftrightarrow (1+abc)(ab+bc+ca)\ge 9abc$

since $ab+bc+ca\le a^2+b^2+c^2=9$ we conclude
$9(1+abc)\ge(1+abc)(ab+bc+ca)\ge 9abc$
$\Leftrightarrow 1 \ge 0$
which is definitly true

peeta

ps: it feels like i did a mistake somewhere but i looked over it a few times now, its just too easy and also its not ony $\le$ but $<$

[quote="peeta"]
since $ab+bc+ca\le a^2+b^2+c^2=9$ we conclude
$9(1+abc)\ge(1+abc)(ab+bc+ca)\ge 9abc$
$\Leftrightarrow 1 \ge 0$
which is definitly true
[/quote]
This is definitely wrong.
I don't think this inequality is easy by the way.

Let $a \ge b \ge c$, fix $c$.

Now $abc + 1 \ge 3c \Leftrightarrow (ab-3)c + 1 \ge 0$

 To minimize $ab$, we set $a^2 = 9 - b^2 - c^2$ and $b = c$.

So we just need $(c\sqrt{9 - 2c^2} - 3)c + 1\ge 0$

or $c^2 \sqrt{9 - 2c^2} \ge 3c-1$.

So let f(c), g(c) be the functions $c^2 \sqrt{9 - 2c^2}$ and $3c-1$, both defined on the interval $c \in [0, \sqrt{3}]$.

Obviously, $f(\sqrt{3}) \ge g(\sqrt{3})$.  A derivatives argument shows that $g'(c) \ge f'(c)$.

it looks wrong to me too but i couldnt find the mistake. u probably know how difficult it can be to find ones own mistakes  :)
i'll be glad to see what i did wrong, although i'd be even more glad to see that its right  :D
dont know  :?

[quote="peeta"]since $ab+bc+ca\le a^2+b^2+c^2=9$ we conclude
$9(1+abc)\ge(1+abc)(ab+bc+ca)\ge 9abc$[/quote]
Wrong direction.

Dear Singular, without calculus (derivatives) and completely !
[b]The affair with 35$ for one who will solve nicely this problem remains of tropical [/b] [b]interest ![/b]

[quote="zhaobin"]sorry.
and here is a full solution.
$WLOG,a \leq b \leq c$
with $a^2+b^2+c^2=9$,we get $a \leq b \leq \sqrt{9-a^2-b^2}$
we prove $3a \leq 1+ab \sqrt{9-a^2-b^2} $
first I prove $b \sqrt{1-a^2-b^2} \geq a \sqrt{9-2a^2} $
this is because $b^2(9-a^2-b^2)-a^2(9-2a^2)=9(b^2-a^2)-(b^2-a^2)(2a^2+b^2)=(b^2-a^2)(9-2a^2-b^2) \geq 0$
and then we should only to prove $3a \leq 1+a^2 \sqrt{9-2a^2} $ when $a \leq \sqrt{3}$
and it is not hard :)  :)[/quote]
is there anything wrong with my solution?

Dear Singular, without calculus (derivatives) !!

[quote="toanhocmuonmau"]My solution:
Problem 1. [ Virgli Nicula ]

If $a,b,c$ are arbitrary real numbers satisfying $a^{2}+b^{2}+c^{2}=9,$ then
\[3\min \left\{ a,b,c\right\}\leq abc+1 \]
Proof.

WLOG, we may assume $c\geq b\geq a,$ with this assumption, the given inequality becomes
\[abc+1\geq 3a \]
We have 2 cases

$a)$ If $a\leq 0,$ then by AM - GM Inequality, we have
\[abc+1-3a\geq \frac{a(b^{2}+c^{2})}{2}+1-3a=\frac{a(9-a^{2})}{2}+1-3a= \frac{(a+1)^{2}(2-a)}{2}\geq 0 \]
$b)$ If $a\geq 0,$ since $c\geq b\geq a,$ we obtain $\sqrt{3}\geq a\geq 0.$

$+,$ If $a\leq \frac{1}{3},$ the inequality is trivial.

$+,$ If $\sqrt{3}\geq a\geq \frac{1}{3},$ we can easily check that
\[bc\geq a\sqrt{b^{2}+c^{2}-a^{2}}=a\sqrt{9-2a^{2}}\]
So we have to prove
\[a^{2}\sqrt{9-2a^{2}}+1\geq 3a \]

\[\Leftrightarrow f(a)=2a^{6}-9a^{4}+9a^{2}-6a+1\leq 0 \]
$++,$ If $1\geq a\geq \frac{1}{3},$ we have
\[2f(a)=a^{2}(a-1)\left[ 4a(a-1)^{2}+12a^{2}-18a+7\right]+(1-3a)(7a^{2}-6a+3) \leq 0 \]
$++,$ If $\sqrt{3}\geq a\geq 1,$ then
\[f(a)\leq 2a^{6}-9a^{4}+9a^{2}-5=(a^{2}-1)(2a^{4}-7a^{2}+2)-3\leq-3<0 \]
The inequality is proven.

Equality occurs if and only if $(a,b,c)=(2,2,-1).$

The method i use here is mixing variables.

Can i recieve the reward? :P :P[/quote]
In the problem, a,b,c are POSITIVE reals. If they were arbitrary reals, then a=b=0, c=-3 (and permutations).

[quote="Valentin Vornicu"]Prof. Virgil Nicula just gave me this inequality to post it on the forum. He said he will reward the (Romanian :?) student that comes up with the "nicest" solution with 1,000,000 ROL (~40 $\$$). I am not sure what he ment by that, but here goes the inequality :)

Prove that if $a$, $b$, $c$ are positive reals such that $a^{2}+b^{2}+c^{2}= 9$ then
\[3 \min\{ a,b,c\}\leq 1+abc . \][/quote]
inf{a,b,c}=0, but min{a,b,c} doesn't exist. (WLOG a<=b<=c. Take: b=(3^1/2)-h, c=(3^1/2)-h, h->0).

[quote="Soarer"][quote="ctumeo"][quote="Virgil Nicula"][u]See[/u] [b]PP1[/b] from [url=http://www.artofproblemsolving.com/blog/43632][color=darkred][b]here[/b][/color][/url].[/quote]
a) I think that if a,b,c are real numbers with a^2+b^2+c^2=9, then min{a,b,c}=-3. It's wrong?
b) I think that if a,b,c are positive real numbers with a^2+b^2+c^2=9, then inf{a,b,c}=0, but min{a,b,c} doesn't exist. It's wrong?[/quote]

min{a,b,c} means the minimum of a,b,c, where $(a,b,c)$ is a tuple that satisfies $a^2+b^2+c^2 = 9$ (i.e. it depends on a,b,c), rather than minimum of a,b,c subjected to the condition $a^2+b^2+c^2 = 9$, i.e. what you may be worrying about in your point b. I don't understand your complaint in a.[/quote]

Thanks for the explanation (you're rigth, I've misunderstand the text).
a is the same thing of b (we add positive squares, then the minimum is negative, and the minimum negative is -3).


Hi everybody
I have designed this problem:
Suppose that we have N points on a page.N is natural and odd number.R,S are natural numbers such that N=R+S.
Prove that there exist 4 lines L1,L2,L3,L4 such that:
1)there exist R points in right of L1 and S points in left of that.
2)there exist S points in right of L2 and R points in left of that.
3)there exist R points over the L3 and S points below that.
4)there exist S points over the L4 and R points below that.
5)besides the lines L1,L2,L3,L4 make arectangle.
thank you if you solve this problem.
This problem is about Combinatorial Geometry.

this doesn't belong here.  This is for questions regarding the site i think.


If there are $ 3$ linearly independent vectors in $ \mathbb{R}^3$, then will there always exist an inner product such that the vectors are pairwise orthogonal?

Is this true for any set of linearly independent vectors in $ \mathbb{R}^n$?

Thanks.

Would this be an easier question if instead of $ \mathbb{R}^n$, it was an arbitrary $ n$-dimensional vector space over $ \mathbb{R}$? Forget the standard basis.

Think about how to define an inner product abstractly and without reference to a basis.  What do you have to specify?

By define abstractly do you mean..

$ \langle u,v \rangle \equal{} \langle v,u \rangle$
$ \langle ku,v \rangle \equal{} k\langle u,v \rangle$
$ \langle u,v \plus{} w \rangle \equal{} \langle u,v \rangle \plus{} \langle u,w \rangle$
$ \langle u,u \rangle\ge 0$ equality iff $ u \equal{} \hat{0}$

No, because that doesn't tell you which inner product you're working with or how to compute anything.

So, pick a basis.* There isn't a standard basis, so let's use that set of independent vectors $ v_1,v_2,\cdots$ we started with. Can you define an inner product on linear combinations $ \sum a_iv_i$ of these? Are the $ v_i$ orthogonal?

*I don't really think t0rajir0u's recommendation is worthwhile- we need a basis of some sort, unless there's some outside structure. It's just that we can pick [i]any[/i] basis.

[quote="jmerry"]It's just that we can pick [i]any[/i] basis.[/quote]
I guess I worded that poorly.  What I wanted to say was "try to define an inner product without reference to the standard basis."

Sorry If I have interpreted this wrong, but do you mean linear combinations of the components of the vectors (like a weighted Euclidian Inner Product) or literally a linear combinations of the vectors.

I had thought about a weighted Euclid product before, except it didn't work
Consider the linearly independent set $ v \equal{} (1, \minus{} 1,1), u \equal{} (3,1, \minus{} 1), w \equal{} (1, \minus{} 7,4)$

If we define some inner product by; $ \langle u,v \rangle \equal{} au_1v_1 \plus{} bu_2v_2 \plus{} cu_3v_3$ with $ a,b,c \in \mathbb{R}$ and $ a,b,c > 0$ Then we are given a sytem of equations that we need to solve, namely
$ \langle u,v \rangle \equal{} 0, \langle v,w \rangle \equal{} 0, \langle w,u \rangle \equal{} 0$
\[ \left( \begin{array}{cccc} 3 & \minus{} 1 & \minus{} 1 & 0 \\
3 & \minus{} 7 & \minus{} 4 & 0 \\
1 & 7 & 4 & 0 \end{array} \right)
\]

\[ \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \end{array} \right)
\]
Which implies $ a \equal{} b \equal{} c \equal{} 0$ but this isn't an inner product. Perhaps I did something very wrong?

[quote="ocha"]... the components of the vectors[/quote]What do you mean, "the components"? My $ v_i$ are $ v_1\equal{}e^x,v_2\equal{}e^{\minus{}x},v_3\equal{}\cos(x),v_4\equal{}\sin(x)$ in the space of solutions to $ f^{(4)}(x)\equal{}f(x)$... or maybe that was $ \cosh(x),\sinh(x),e^{ix},e^{\minus{}ix}$.

There is no standard basis. Vectors have components with respect to a basis, but it depends which one you pick. The coefficients of that linear combination [b]are[/b] the components, relative to the one basis we're looking at.

$ e^{ix}, e^{ \minus{} ix}, cos(x), sin(x)$ or $ e^{x},e^{ \minus{} x},cosh(x), sinh(x)$...so we are also considering functions to be vectors in this case?

I think we have established that: we have some basis $ B \equal{} \{v_1,v_2,...v_n\}$ and $ [x]_B \equal{} (a_1,a_2...a_n)$ given $ x \equal{} \sum a_iv_i$. And we have forgoten about the standard basis.

[quote="jmerry"] Can you define an inner product on linear combinations $ \sum a_iv_i$ of these? Are the $ v_i$ orthogonal?[/quote]
Could you please elaborate? (btw, if you couldn't tell, I am new to vector spaces and inner products)

[quote="ocha"]$ e^{ix}, e^{ \minus{} ix}, cos(x), sin(x)$ or $ e^{x},e^{ \minus{} x},cosh(x), sinh(x)$...so we are also considering functions to be vectors in this case?[/quote]
You can define [b]arbitrary symbols[/b] to be vectors; it's absolutely irrelevant what they are as long as you define everything in a consistent way.

[hide="This is the definition we have been trying to get you to find."] Given a basis $ v_1, v_2, v_3$, an inner product is uniquely determined by the values of $ (v_i, v_j)$.  Why?  What can you set these to be to get them to be orthonormal? [/hide]

I chose that example as something where there was never a standard basis in the first place. The solutions to an $ n$th order linear homogeneous differential equation (in one variable) are an $ n$-dimensional vector space, and it's a standard example. In fact, the introductory linear algebra class I took added a bit of differential equations to exploit this. The two sets I gave are both bases (at least if we do things over $ \mathbb{C}$), and neither is more "standard" than the other.
This is something that should be normal- vector spaces come from many places, and we don't always start with a basis. We need to be able to pick a basis, center our view on it, and turn the space into a copy of $ F^n$. This includes turning $ F^n$ into a different version of $ F^n$, which is the point of my initial "Forget the standard basis" comment.

Okay, Thanks a lot guys  :)
I will meditate on this and post a solution if a get a  :idea: moment.

I think I understand what you mean by "forget the standard basis"
[hide]
Let $ B \equal{} \{v_1,v_2,v_3\}$ be a basis

$ [v_1]_B \equal{} (1,0,0), [v_2]_B \equal{} (0,1,0), [v_3]_B \equal{} (0,0,1)$ and these vectors are orthogonal.

So if we can find a change of basis matrix, $ P_{B\to C}$, then we can also define an inner product on the change of basis matrix. So if we let $ S$ be the standard basis then

$ (1,0,0) \equal{} [v_1]_{B} \equal{} P_{S\to B}[v_1]_{S} \equal{} [v_1 | v_2 | v_3]\cdot v_1$

We have $ \left(P_{S\to B}v_i\right)^T\left(P_{S\to B}v_j\right) \equal{} 0$

$ \therefore (v_i)^T P_{S\to B}^T P_{S\to B} v_j \equal{} 0$

Since $ P_{S\to B}^T P_{S\to B}$ is symmetric, it must define an inner product!!

EDIT:...actually that used the standard basis, quite a bit?
[/hide]

That's technically correct, but you certainly haven't "forgotten the standard basis."  Did you read my comment?

[hide="Here is the inner product"] $ (v_i, v_j) \equal{} \delta_{ij}$.

In other words, [b]define[/b] the inner product to be the unique inner product such that $ v_1, v_2, v_3$ form an orthonormal basis, and show that it's well-defined. [/hide]


geometry
trapezoid
inequalities
inequalities unsolved

Let $p,q$ be the length of diagonals of a trapezium that is circumscribed about a circle of radius $r$. Prove

$ p^2+q^2 \geq 16r^2 $

This inequality is weak:

$p^{2}+q^{2} \geq 2pq \geq 2 \cdot 8r^{2} =16r^{2}$


geometry
3D geometry
prism
geometry unsolved

Here are a few questions about the same subject. I hope that not all of them are stupid...

1. If projections of some conv. body on 2 planes are squares (equilateral triangles), are there
necessarily congruent?
2.Is it true that for any $k$ planes there is conv. body the projections of which on $k$ planes are
all triangles(quadrangles, equilateral triangles, squares)?
3.Does there exist a body projection of which on any plane is triangle (quadrangle...)?
4.Given planes $a,b,c,d$, no parallel. Can you find a body whose projections on these planes are
triangle, quadrangle, pentagon and hexagon, respectively?
5.Is it true that for any $k$ planes (in general position) there is a body which projection on $i$-th plane
is $(i+2)-$gon?

And this is the most interesting:

6.If projections of some convex body on any plane is polygon, prove that body is polyhedron.

The answer to your first question is clearly no (for squares, at least; it also seems to be true for equilateral triangles, but it's harder for me to explain the construction).

Consider a cube $ABCDA'B'C'D'$, and let $M,N,P,Q,M',N',P',Q'$ be the midpoints of the sides $AB,BC,CD,DA,A'B',B'C',C'D',D'A'$ respectively. Our body will be the prism $MNPQM'N'P'Q'$. It's projection on the plane $(ABCD)$ is the square $MNPQ$, while its projection on $(ABB'A')$ is the square $ABB'A'$.

I have a question: is the sixth one also a question of yours, or is it something you know for sure is true?

Its only a conjecture, I don't have a proof, but it really looks intuitively very acceptable, doesn't it?
Of course even if its true it can be very hard.