modular arithmetic
Divisibility
number theory
IMO Shortlist

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]introduction for the IMO ShortList/LongList project[/url] and regarding[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=15623]solutions[/url]  :)

It's well-known that $P(x)=x^{p-1}-1$ has $p-1$ roots in $\mathbb Z_{p^2}$. Assume what we're trying to prove doesn't hold. In each pair $(1,2),(3,4),\ldots,(p-2,p-1)$ there's at least a root of $P$, so there are at least $\frac{p-1}2$ roots of $P$ among the first $p$ residues $\pmod{p^2}$. If $x$ is a root of $P$, then so is $-x$ (in $\mathbb Z_{p^2}$, of course), so there are at least $\frac{p-1}2$ other roots of $P$ among the last $p$ residues $\pmod{p^2}$.

This means that the roots of $P$ lie in the intervals $(1,p)$ and $(p^2-p,p^2)$. However, we can clearly find roots which are not in these intervals, for example the product of two roots chosen from the pairs $(\frac{p-3}2,\frac{p-1}2),(\frac{p+1}2,\frac{p+3}2)$. Their product is $\ge \frac{(p-3)(p+1)}4$ and $\le \frac{(p-1)(p+3)}4$. For $p\ge 7$ this product is outside the two intervals mentioned above, and for $p=5$ we can check it manually (take $a=1$).

My proof is a little bit different.

We will consider 3 cases:
1)$(\frac{p-1}{2})^{p-1} \not \equiv 1 \mod{p^2}$ and $(\frac{p+1}{2})^{p-1} \not \equiv 1\mod{p^2}$
2)$(\frac{p-1}{2})^{p-1} \equiv 1 \mod{p^2}$
3)$(\frac{p+1}{2})^{p-1} \equiv 1 \mod{p^2}$

In the first case, we obviously take $a=\frac{p-1}{2}$.
Let us consider the second case.
$(\frac{p-1}{2})^{p-1} \equiv 1 \mod{p^2}$ is equivalent to $(p-1)^{p-1} \equiv 2^{p-1} \mod{p^2}$ which is, after reducing $\mod{p^2}$,
$p(p-1) + 2^{p-1} - 1 \equiv 0 \mod{p^2}$
From FLT $2^{p-1} - 1$ is divisible by $p$ so, $2^{p-1} - 1 = pk$. So:
$p(p-1) + 2^{p-1} - 1 = p(p-1 + k) \equiv 0 \mod{p^2}$
So, $p-1+k \equiv 0 \mod{p}$ which means that $k \equiv 1 \mod{p}$ and $2^{p-1} - 1 \equiv p \mod{p^2}$

Now, we will show that $a=p-2$ satisfies required condition. Indeed:

$(p-2)^{p-1} - 1 \equiv 2^{p-2}p(p-1) + 2^{p-1} - 1 \equiv p(2^{p-2}(p-1) + 1) \mod {p^2}$
And since $2^{p-2}(p-1) + 1 \equiv -2^{p-2} + 1 \not \equiv 0 \mod{p}$ above congruence is not $0 \mod{p^2}$.

Now we check $p-1$:
$(p-1)^{p-1} - 1 \equiv -p(p-1) + 1 - 1 \equiv -p(p-1) \not \equiv 0 \mod{p^2}$

So, in this case we are done.
We are left with the case 3) but it's almost the same.

Let $ S \equal{} \{1,2,\ldots,p \minus{} 1\}$. Let $ A$ be the set of guys in $ S$ such that $ a^{p \minus{} 1}\equiv1\pmod{p^{2}}$, and $ B$ be the others. Go by contradiction.

1. $ p \minus{} 1\in B$.
Binomially expand $ (p \minus{} 1)^{p \minus{} 1}$. We get the sum of a bunch of terms that are divisible by $ p^{2}$, then the last two are $ \minus{} p(p \minus{} 1) \plus{} 1\equiv p \plus{} 1\pmod{p^{2}}$, which is not 1.

2. $ |B|\ge|A|$.
We'll construct an injection from $ A$ into $ B$. Say $ a\in A$. Then, $ a^{p \minus{} 1}\equiv1\pmod{p^{2}}$. Now, consider $ a\rightarrow (p \minus{} 1)a$, which is an injection since $ p$ is prime (this is really just $ a$ to $ \minus{} a$). Then, $ ((p \minus{} 1)a)^{p \minus{} 1} \equal{} a^{p \minus{} 1}(p \minus{} 1)^{p \minus{} 1}\equiv p \plus{} 1\pmod{p^{2}}$, so $ (p \minus{} 1)a\in B$. Thus, $ |B|\ge|A|$.

3. $ |A|\ge|B|$.
That is, at least half of our guys in $ S$ are in $ A$. $ p \minus{} 1$ is even, so we can break $ S$ up into the pairs $ \{1,2\},\{3,4\},\ldots,\{p \minus{} 2,p \minus{} 1\}$. By assumption, each of these pairs has a number that, when raised to the power $ p \minus{} 1$, is congruent to 1 modulo $ p^{2}$, so each pair has an element of $ |A|$. The conclusion follows.

1 and 3 give us $ |A| \equal{} |B|$. Now, note further that with our pairs from step 3, we in fact need exactly one member of each pair to be in $ A$. 1 is in $ A$, so 2 is not. This makes 3 in $ A$, so 4 is not. We see that we need the odd integers to be in $ A$, but the even integers to be in $ B$. We'll now proceed to get the contradiction.

Case 1: $ p\ge17$. Observe that one of $ p \plus{} 2,p \plus{} 4$ is not prime (one has to be divisible by 3, as $ p$ is not). Both integers are odd, and thus have odd factors that are furthermore at most $ p \minus{} 1$. If $ p \plus{} 2$ is composite, write it as the product of odd factors $ f_{1},f_{2}$, and note that $ (p \plus{} 2)^{p \minus{} 1} \equal{} f_{1}^{p \minus{} 1}f_{2}^{p \minus{} 1}\equiv1\pmod{p^{2}}$. The exact same thing is true of $ p \plus{} 4$ if it is composite. Now, we multiply by $ (p \minus{} 2)^{p \minus{} 1}$ or $ (p \minus{} 4)^{p \minus{} 1}$, to get that $ (p^{2} \minus{} 4)^{p \minus{} 1}$ or $ (p^{2} \minus{} 16)^{p \minus{} 1}$ is also 1 modulo $ p^{2}$. Observe that $ p \minus{} 1$ is even, so these are the same as $ 4^{p \minus{} 1},16^{p \minus{} 1}$, which have even bases, and when $ p\ge17$, this means that they are not 1 modulo $ p^{2}$, contradiction.

Case 2: $ p \equal{} 7,13$. $ p \plus{} 2$ is not prime here, and so we can do the same thing as before with $ p \plus{} 2$, to get $ 4^{p \minus{} 1}$ not 1 modulo $ p^{2}$.

Case 3: $ p \equal{} 5$. $ 3^{4}\equiv6\pmod{25}$. Oops.

Case 4: $ p \equal{} 11$. $ 5^{10}\equiv (125)^{3}\cdot5\equiv 64\cdot5\equiv320\equiv 78\pmod{121}$. Oops.

This exhausts all cases, so we're done.

Lemma: $(p-x)^{p-1} \not\equiv x^{p-1} \pmod {p^2}$ for $1\leq x\leq p-1$.
Proof: $(p-x)^{p-1} \equiv (-x)^{p-1} + (p-1)p(-x)^{p-2} \equiv x^{p-1} + px^{p-2} \not\equiv x^{p-1} \pmod {p^2}$.

Suppose for contradiction that for $1\leq a \leq p-2$, either $a^{p-1}-1$ or $(a+1)^{p-1}-1$ is $0$ mod $p^2$. By our lemma, since $1^{p-1} -1 \equiv 0 \pmod {p^2}$, $(p-1)^{p-1} -1 \not\equiv 0 \pmod {p^2}$, so $(p-2)^{p-1} -1 \equiv 0 \pmod {p^2}$; repeating this argument, we find $x^{p-1} - 1 \equiv 0 \pmod {p^2}$ for $x = 1, 3, ..., p-2$; since $p-1$ is even, their negatives also satisfy the equation. Since $x^{p-1}-1$ is of degree $p-1$, it can have at most $p-1$ roots mod $p^2$, so these are all the roots. Thus, $x^{p-1}-1 \equiv (x^2-1)(x^2-3^2)...(x^2-(p-2)^2) \pmod {p^2}$. Now the coefficient of the term $x^{p-3}$ is $-\sum_{k=1}^{\frac{p-1}{2}} (2k-1)^2 = - \left(\frac{p-1}{2}\right)^2 \not\equiv 0 \pmod {p^2}$. But $0<p-3<p-1$, the coefficient must be $0$ mod $p^2$. Contradiction.

we can also do this in this way :
considering the lemma posted by timwu we find as said : for $x=1,3,...,p-2$ we have $x^{p-1} \equiv 1 \pmod{p^2}$.
now if we find two distinct odd numbers between 1 and p like i and j such that   $ij \equiv 1 \pmod{p}$ we r done because then we have
$ i^{p-1} \equiv j^{p-1} \equiv 1 \pmod{p^2}$ and so $p^2 | (ij)^{p-1}-1$ which is impossible because $p | ij-1 , p \nmid p-1 \implies p^2 | ij-1 < p^2-1$ which means that we must have ij=1 which contradicts the fact that they are distinct odd natural numbers.
now suppose that $2^a || p-1$ then we have that $ (p-2^a)(\frac{p-1}{2^a}) \equiv 1 \pmod{p}$ so we must check the case in which $p = 2^a +1 $ or better say $p=2^{2^n}+1$ for some n . we can check the case p=5 easily.  so let's assume that n > 1. we have 5 | 2p+1 and so there exists an odd number distinct from 5 such that $5i = 2p+1 \equiv 1 \pmod{p}$ and it's easy to see that $1 <  5,i < p$
DoNe!

[quote="darkpseudo"]Can't we just use LTE ?? :
$ v_p(a^{p-1}-1) = v_p(a-1) $ ?[/quote]
So $p$ doesn't divide $a-1$ implies $p$ doesn't divide $a^{p-1}-1$ ?

[quote="darkpseudo"]Yes because obviously p doesn't divides a ( a< p ) .[/quote]
And what about Fermat's little theorem?

Sorry I did'nt quite understood you at first , one of the conditions of LTE is that $v_p({a-1})\geq 1 $ so there is no contradiction with Fermat theorem .
Here is what I was thinking :
We know that there are $\frac {p-1}{2}$ quadratic residue mod p if there exist two successif quadratic residue then take the first as ''a'' then we have $ a^{\frac{p-1}{2}} = 1 [p] $ then by LTE we have $ v_p{a^{p-1}-1}= v_p{a^{\frac{p-1}{2}}-1 = 1 }$ and the same think for a+1 since it is also a quadratic residue . But still the other case can't be proven the same way .

[quote="darkpseudo"] $v_p{a^{\frac{p-1}{2}}-1 = 1 }$  .[/quote] Why you are sure about this? For example: $a=3$, $p=11$ and $121|3^5-1$. I believe not a lot is known about $v_p m^{p-1}-1 $ when we don't know a lot about m.

I have a different approach!

Assume the statement is false. Let a number $a$ modulo $p^2$ be "good" if $a^p = a (\bmod p^2)$, otherwise let it be bad. Then there are no consecutive bad numbers in $1,2,...,p-1$, so at least half of them are good. If $a$ is good notice

$(p-a)^p = -a^p = -a \neq p-a (\bmod p^2)$

and so $p-a$ is bad. Therefore there are no consecutive good numbers in $1,2,...,p-1$ either, otherwise if we take $a,b$ consecutive good numbers, then $p-a,p-b$ are consecutive bad numbers. Since every number is good or bad and 1 is good, we reach the conclusion that:

1 is good, 2 is bad, 3 is good, 4 is bad, etcetera...

Notice that this implies $p^2-1,p^2-3,...$ are all good, and so we have proven $p-1$ different numbers are good. Also notice that

$(pk+a)^p = a^p (\bmod p^2)$

and so, for each subcongruence of $p$ modulo $p^2$, there is only 1 good number. This implies there are $p-1$ good numbers in total, which MUST be the ones I just described ($1,3,...,p-2$ and $p^2-1,p^2-2,...,p^2-(p-2)$).

Since $p \ge 5$, we get that $(p-2)^2$ is NOT one of these numbers. Therefore, it is bad. But notice that $p-2$ is good, and so

$((p-2)^2)^{p-1} = ((p-2)^{p-1})^2 = (1)^2 = 1 (\bmod p^2)$,

and so $p-2$ is good. Contradiction!

Q.E.D

Hmm how's this?

Let $S = {1, 2, \ldots, p-1}$ and $X = x \in S \mid x^{p-1} \equiv 1 \mod p$ and $Y = y \in S \mid y^{p-1} \not\equiv 1 \mod p$. The case $|Y| = 0$ is clearly impossible as $p-1 \in Y$, which can easily be verified through binomial expansion. Then, for some element $y \in Y$, the elements $X \cdot y \in Y$ and are all distinct, so $|Y| \ge |X|$. If $|Y| > |X|$, we are done as there must be two consecutive $y$ terms, so assume $|Y| = |X|$. If there are no two consecutive $y$ terms, since $1 \in X$ and $p-1 \in Y$, it must be that $1, 3, 5, \ldots \in X$. Furthermore, $Y \cdot y \in X$ since $|Y| = |X|$ and $S \cdot y$ are all distinct, so $2 \cdot 2 \equiv 4 \in X$ for $p \ge 5$, a contradiction.

[hide="Solution"]
Let $S=\{s\mid s^{p-1}\equiv 1\pmod {p^2}\}$. First, note the lemma: $x^p+(p-x)^p\equiv 0\pmod {p^2}$. This can be done by factoring or expanding the LHS. Then, rearranging gives $x(x^{p-1}-1)+(p-x)((p-x)^{p-1}-1)\equiv -p\pmod{p^2}$, which directly implies that at most one $x, p-x$ are in $S$. Since $1\in S$, to avoid contradiction we then need $1, 3, 5, \ldots p-2\in S$. Since $p-2\in S$, we have that $(p-2)^{p-1}\equiv 1\pmod{p^2}\implies (p^2-4p+4)^{\frac{p-1}{2}}\equiv 1\pmod{p^2}\implies (-4p+4)^{\frac{p-1}{2}}\equiv 1\pmod{p^2}$. Now, note that our lemma implies that $(p-1)^p\equiv -1\pmod{p^2}$, so then we get that $(-4p+4)^{p-1}\equiv 1\pmod{p^2}\implies 4^{p-1}(p-1)^p\equiv p-1\pmod{p^2}\implies 4^{p-1}\equiv -p+1\pmod{p^2}$. But since $4^p+(p-4)^p\equiv 0\pmod{p^2}$ by our lemma, and $(p-4)^{p-1}\equiv 1\pmod{p^2}$, we get that $0\equiv 4^p+(p-4)^p\equiv (-4p+4)+(p-4)\equiv 3p\pmod{p^2}$, or that $p=3$, a contradiction.
[/hide]

Can someone tell me if there's a mistake here, it seems too easy....

Call $a$ in $S=\{1,2,...,p-1\}$ "good" if $a^{p-1}=1 [p^2]$. If the problem statement is false, then for every $1 \le a \le p-2$, at least one of $a$ and $a+1$ is good. Then at least $(p-1)/2$ numbers in $S$ are good.

It is easy to prove by binomial theorem that  $(p-a)^{p-1}=(a^{p-1}+pa^{p-2}) [p^2]$. If $a$ in $S$ and $a^{p-1}=1 [p^2]$ then clearly $(p-a)^{p-1} \neq 1 [p^2]$. Thus at most one of $a,p-a$ are good for every $1 \le a \le (p-1)/2$. Thus there are at most  $(p-1)/2$ good numbers in $S$, and hence there are exactly $(p-1)/2$ good numbers in $S$. For the problem statement to remain false, it follows that $1,3,...,p-2$ are good and $2,4,...,p-1$ are not good.

Now note that if $a$ is good and $b$ is not good then $ab$ is not good. In particular, if $p \ge 7$ we get that since $3$ is good and $2$ is not good, $6$ is not good, a contradiction. If $p=5$ we can check that the problem statement is true manually.

It is well known that there exists a primitive root in $\mathbb Z/p^2\mathbb Z$. Hence for every $h\mid p(p-1)$ there exist exactly $\varphi(h)$ values $\alpha$ such that $\text{ord}_{p^2}(\alpha)=d$. Define $X={x\text{ s.t. }p^2\nmid x^{p-1}-1}$, and note that $x\in X\iff p\mid\text{ord}_{p^2}(x)$. Clearly there are $\sum_{d\mid p-1} \varphi(pd)=(p-1)\sum_{d\mid p-1} \varphi(d)=(p-1)^2$ such $x$. But for $p\geq 5$ we have $\tfrac{(p-1)^2}{p^2}>0.5$, and then it must be possible (by PHP) to find $a,a+1\in X$, as desired $\Box$

Remark that the problem could've been:
[quote=ISL'01NT4]Given a positive integer $k$, show that for every sufficiently large prime $p$ there must exist $k$ consecutive integers $x_1,x_2,\cdots, x_k$ such that none of $x_i^{p-1}-1$ is divisible by $p^2$[/quote]

My solution
Lemma :
If $a$ is an integer not divisible by $p$, then $p^2\mid (p-a)^{p-1}-1$ iff $p^2\mid a^p-a+p$
Proof :
$p^2\mid (p-a)^{p-1}-1$ $\Leftrightarrow$ (by binomial expansion) $p^2\mid p(-a)^{p-2}(p-1)+(-a)^{p-1}-1$ $\Leftrightarrow$ (because $p$ is odd) $p^2\mid pa^{p-2}+a^{p-1}-1$
Put $M:=\frac{a^{p-1}-1}p$, then $M\in\mathbb{N}$ by FLT
So $p^2\mid pa^{p-2}+a^{p-1}-1$ $\Leftrightarrow$ $p^2\mid pM+ pa^{p-2}$ $\Leftrightarrow$ $p\mid M+a^{p-2}$ $\Leftrightarrow$ (because $p$ doesn't divide $a$) $p\mid aM+a^{p-1}=aM+pM+1$ $\Leftrightarrow$ $p\mid aM+1$ $\Leftrightarrow$ $p^2\mid paM+p=a^p-a+p$ $\Box$

Suppose that $p^2\mid a^{p-1}-1$ and $p^2\mid (a+1)^{p-1}-1$ for $a\in [\![1,p-2]\!]$ : by our lemma, one can find that neither $(p-a-1)^{p-1}-1$ nor $(p-a)^{p-1}-1$ is divisible by $p^2$, which would finish the proof

So suppose that $p^2\mid a^{p-1}-1$ $\Rightarrow$ $p^2$ divides neither $(a-1)^{p-1}-1$ nor $(a+1)^{p-1}-1$
Suppose the problem is false, and w'll derive a contradiction
$p^2\mid 1^{p-1}-1$ so $p^2$ divides not $2^{p-1}-1$ so $p\mid 3^{p-1}-1$... and so each integer $a$ odd in $[\![1,p-1]\!]$ is such as $p^2\mid a^{p-1}-1$ and contrary for even $a$. By our lemma, for an even a, because $a$ is even $p-a$ is odd, we get that $a^p-a\equiv -p\mod{p^2}$
Because $p\geq5$, we have for $a=2,4$, $2^p-2\equiv_{p^2} -p$ and $4^p-4\equiv_{p^2}-p$, so that $2^p\equiv_{p^2}2-p$ and then $-p\equiv_{p^2}4^p-4=2^{2p}-4\equiv_{p^2}(2-p)^2-4\equiv_{p^2} -4p$ so $3p\equiv 0\pmod{p^2}$, a contradiction $\Box$

[hide=Solution][quote=ISL 2001 N4]Let $p \geq 5$ be a prime number. Prove that there exists an integer $a$ with $1 \leq a \leq p-2$ such that neither $a^{p-1}-1$ nor $(a+1)^{p-1}-1$ is divisible by $p^2$.[/quote]
Note that
$$ 1, 2^p,3^p, \ldots , (p-1)^p $$
are distinct $\pmod{p^2}$ and satisfy the congruence
\begin{align*} x^{p-1} \equiv 1 \pmod{p^2} \end{align*}
If $h$ which is distinct than above $p-1$ numbers satisfies the congruence too, let $h \equiv r \pmod{p}$
\begin{align*} h^{p-1} \equiv 1 \pmod{p^2} \implies r^p \equiv h \pmod{p^2} \end{align*}
Since, $ r \neq 0$ $\implies$ $r$ lies among those $p-1$ values, contradiction to our assumption! Thus, there are exactly $p-1$ solutions to
\begin{align*} x^{p-1} \equiv 1 \pmod{p^2} \end{align*}
Assume that there donot exist consecutive values that donot satisfy the above congruence. Note that if $r$ is a solution, then so is $p^2-r$ and if $q,r$ both are solutions then so is $qr$. Thus $\tfrac{p-1}{2}$ solutions must lie in the interval $(1,p-1)$ and others in $\left( p^2-p-1, p^2 -1 \right)$. Note that $1$ is a solution and $p-1$ is not. Thus, $3$ and $p-2$ compulsarily must be a solution to the congruence but $3(p-2)$ which should be a solution lies outside the range of intervals, a contradiction $\qquad \blacksquare$[/hide]

[quote=Cindy.tw][quote=eraydin]can somebody prove " $ P(x)=x^{p-1}-1 $  has $ p-1 $  roots in $ \mathbb{Z}_{p^{2}} $ "[/quote]

Hensel Lemma can![/quote]

A simpler way is to notice that
$$x^{p(p-1)}-1=(x^{p-1}-1)(x^{(p-1)^2}+\dots +1)$$ But since in $\mathbb{Z} _{p^2}$ $x^{p(p-1)}-1 $ has exactly $p(p-1)$ roots, $P(x)$ has at most $p-1$ roots and $x^{(p-1)^2}+\dots +1$ has at most $(p-1)^2$ roots, $P(x)$ has exactly $p-1$ roots.

From here, we work only in $\mathbb{Z} / p^2\mathbb{Z}$.

It is well known that $x^{p-1} - 1$ has at most $p-1$ roots. Moreover, if $x$ is a root, then $-x$ is also a root. Therefore there at most $\frac{p-1}{2}$ integers between $1$ and $p-1$ that are roots. Thus the only way there are no two consecutive roots is if all the odds or all the evens are roots. Since $1$ is obviously a root, it must be the odds. Thus
\[ x^{p-1}-1 = (x-1)(x+1)(x-3)(x+3) \cdots(x-p+2)(x+p-2) = (x^2 - 1)(x^2 - 9) \cdots (x - (p-2)^2 .\]
However, the coefficient of $x^{p-3}$ on the right hand side is
\[ - (1^2 + 3^2 + \cdots + (p-2)^2) = 2^2(1^2 + 2^2 + \cdots (p-1/2)^2) - (1^2 + 2^2 + \cdots (p-1)^2) = \frac{p (p-1)(p+1) - p(p-1)(2p-1)}{6} = \frac{p(p-1)(2-p)}{6} \]
which is not divisible by $p^2$, contradiction.

[hide=Fakesolve]I ended up watching a hint when I was almost finished.  :maybe:   :wallbash_red:

[b]Solution. [/b] Assume the contrary and let for every $k\in\{2,3,\ldots, p-2\}$ we have one of $k^{p-1}-1$ or $(k+1)^{p-1}-1$ divisible by $p^2$. We'll use $a \equiv b$ to denote $a\equiv b \pmod{p^2}$ wherever required. Now we proceed with the following claim.

[color=#f00][b]Claim. [/b][/color] We have $$(p-k)^{p-1}-1 \equiv -pk^{p-2}+k^{p-1}-1 \pmod{p^2}$$
[i]Proof. [/i]Using [url=https://brilliant.org/wiki/binomial-theorem-n-choose-k/]Binomial Theorem[/url] we have
\begin{align*}
(p-k)^{p-1}-1 &=\left[\overbrace{\binom{p-1}{0}p^{p-1}-\binom{p-1}{1}p^{p-2}k + \ldots}^{\text{Rest are}~0 \pmod{p^2}} - \binom{p-1}{p-2}pk^{p-2} +\binom{p-1}{p-1}k^{p-1}\right] -1 \\
&\equiv -(p-1)pk^{p-2}+k^{p-1} - 1 \pmod{p^2} \\
&\equiv -pk^{p-2}+k^{p-1} - 1 \pmod {p^2}\\
\end{align*} as desired. $\square$
Consequently, by $k=1$ in previous claim, we get $$(p-1)^{p-1}-1 \equiv -p \pmod{p^2}$$ but $p^2 \nmid p$. Therefore, $(p-1)^{p-1} \not\equiv 1 \pmod{p^2}$ whence $(p-2)^{p-1} \equiv 1$ due to assumption but this implies $-p2^{p-2}+2^{p-1} \equiv 1,$ whence we get $2^{p-1}\not\equiv 1$ since otherwise $-p2^{p-2} \equiv 0,$ a contradiction. Previous result immediately implies, via assumption, that $3^{p-1} \equiv 1$ which gives $$(p-3)^{p-1}-1 \equiv -p3^{p-1}+3^{p-1}-1 \equiv -p \not\equiv 0 \implies (p-3)^{p-1} \not\equiv 1$$Continuing in the stated manner, we get the alternative sequence as $$3^{p-1} \equiv 1, 4^{p-1} \not\equiv 1, 5^{p-1}\equiv 1, 6^{p-1} \not\equiv 1,\ldots$$Therefore, we get
\begin{align*}
&\iff(p-2)^{p-1}-1 \equiv (p-4)^{p-1}-1 \\
&\iff -p2^{p-2}+2^{p-1} \equiv -p4^{p-2}+4^{p-1} \\
&\iff p2^{p-2}[2^{p-2}-1] \equiv 2^{p-1}[2^{p-1}-1] \\
&\iff p[2^{p-2}-1] \equiv 2[2^{p-1}-1] \\
&\iff 2^{p-2}[p-4] \equiv p-2 \\
&\implies 2^{(p-2)(p-1)}[p-4]^{p-1} \equiv [p-2]^{p-1} \implies 2^{(p-2)(p-1)} \equiv 1 \pmod{p^2} \\
\end{align*}
but now notice that $\operatorname{ord}_{p^2}(2) \mid \phi(p^2)=p(p-1)$. If $\gcd(\operatorname{ord}_{p^2}(2),p)=1$ then $\operatorname{ord}_{p^2}(2) \mid p-1$ but here it's a contradiction (here, not in problem now) since $2^{p-1} \not\equiv 1$. Hence $\operatorname{ord}_{p^2}(2)=pd$ where $d \mid p-1$. Consequently, we have $pd=\operatorname{ord}_{p^2}(2) \mid (p-2)(p-1)$ which gives $p \mid 3$ which is a contradiction. Therefore, our result holds, i.e. the problem statement. $\blacksquare$[/hide]

I now know the proof given in MONT (the same one given [hide=here] [url]https://olympiads.win.tue.nl/imo/imo2001/imo2001-shortlist.pdf[/url] [/hide], but originally when I tried this problem, I had the following approach:
Assume for the contrary that among every $2$ consecutive numbers, at least one is divisible by $p^2$. Also, note that $p|a^p-a$ always due to Fermat.
So, $p^3 | (i^{p-1}-1)((i+1)^{p-1} -1) \ \forall \ i \in [{1,2,...p-2}]$.
Now I attempt to prove that this is not possible by proving a much stronger result, that in fact

$p^3$ can not divide  $\sum_{i=1}^{p-2} (i^{p-1}-1)((i+1)^{p-1} -1)$. If this is true, then clearly the problem will be finished. Now first I tried this for $p=5,7$, it works! Then I spent a (very) long time trying to play with that expression modulo $p^3$ but I could not do much at all.

I could reduce it to showing that $p^3 \nmid \sum_{i=1}^{p-2} (i^2+i)^{p-1} + p + p^2 \cdot \binom{p-1}{2} - p(p-1) - 2 \sum_{i=1}^{p-1} i^{p-1}$
but then I could do nothing more.

NOTE: I tried this problem with above mentioned approach for at least about $4-5$ hours spread out over two days. I tried to check this for $p=11$ but my calculator won't work upto that point (it just approximates the product then, which is not good for divisibility). So after working very long on this method, I gave up on this and worked through the official solution,
But still it seems like this approach should work, in fact it does for $5,7$! But as I am not very experienced, I am not able to work through this, but these expressions seem calculatable mod $p^3$ but I just am not able to do it.
So I am posting it here in the hope that someone else may be able to try it using this method (as imo, it seems pretty cool) or even check upto some larger values. If you are able to do it, please please post it here (and also PM me pls).

By the way, the official solution is sooooo coool  :D !

I knew this was Hensel's as soon as I saw it  :-D

[color=#3D85C6][b]Claim:[/b][/color] $f=X^{p-1}-1$ has precisely $p-1$ roots in $\mathbb{F}_{p^2}$

[b][color=#3D85C6]Proof:[/color][/b] Observe that $f'=(p-1)X^{p-2}$ and thus, $f'$ doesn't have roots in $\mathbb{F}_p^\times.$ Therefore, by Hensel's Lemma, for each $i\in\mathbb{F}_p^\times$ there exists a unique $j\in \mathbb{F}_p$ such that $i+jp$ is a root of $f$ in $\mathbb{F}_{p^2}.$ Consequently, $f$ has precisely $p-1$ roots not divisible by $p$ in $\mathbb{F}_{p^2}.$ It is obvious that $pk$ is never a root of $f,$ and thus, out claim is proven. $\square$

Coming back to the problem, let's assume it is false. It then follows that each of $\{1,2\},\{2,3\},...,\{p-2,p-1\}$ has (at least) a root of $f$ in $\mathbb{F}_{p^2}.$ Hence, $f$ has at least $p-1/2$ roots in $\{1,2,...,p-1\}.$ However, if $x$ is a root then so is $-x.$

Therefore, by our claim, there are precisely $(p-1)/2$ roots in each of the intervals $[1,p-1]$ and $[p^2-p+1, p^2-1],$ and since $1$ is a root, then $3$ and $p-2$ must also be roots.

This is a clear contradiction, since $3(p-2)$ will also be a root, and $p-1<3(p-2)<p^2-p+1.$

Probably some of the arguments can be simplified.

By veryfing $p=5$ and $p=7$ directly (both work with $a=2$), we may assume $p\geq 11$. Observe that $a=1$ is impossible so let us consider only $\{2,3,\ldots,p-2\}$.

If $g$ is a primitive root modulo $p^2$ and $x = g^k$, $1\leq k \leq \varphi(p^2) = p(p-1)$, then $x^{p-1} \equiv 1 \pmod {p^2}$ if and only if $g^{k(p-1)} \equiv 1 \pmod {p^2}$, which is if and only if $p(p-1) \mid k(p-1)$, i.e. $p$ divides $k$. So the number of solutions to $x^{p-1} \equiv 1 \pmod {p^2}$ is $\frac{p(p-1)}{p} = p-1$ which implies that the number of solutions in $\left[1,\frac{p^2-1}{2}\right]$ is $\frac{p-1}{2}$ (as if $x$ is a solution, then so is $p^2-x$ since $p-1$ is even). In particular, as $1$ is a solution and $\frac{p^2-1}{2} > p - 1$, the number of solutions in $[2,p-1]$ is at most $\frac{p-3}{2}$.

Now if we suppose, for contradiction, that the desired statement does not hold, then in $\{2,\ldots,p-1\}$, $p\geq 11$, among two consecutive elements at least one has to be a solution to $x^{p-1} \equiv 1 \pmod {p^2}$. So the number of solutions in this set is at least $\frac{p-3}{2}$, which equals the abovementioned upper bound. Equality is possible if and only if the solutions in $\left[2,\frac{p^2-1}{2}\right]$ are precisely $3$, $5$, $\ldots$, $p-2$. Moreover, it is clear if $x_1$ and $x_2$ are solutions to $x^{p-1} \equiv 1 \pmod {p^2}$, then so is $x_1x_2$ - hence $(p-2)(p-4) \equiv 8-6p$ and $6p-8$ is also a solution. However, $6p-8 > p - 2$ and $6p - 8 \leq \frac{p^2-1}{2}$ (equivalent to $p(p-12) + 15 \geq 0$ which is true for $p\geq 11$) and this is a contradiction!

[hide=Solution][quote=ISL 2001 N4]Let $p \geq 5$ be a prime number. Prove that there exists an integer $a$ with $1 \leq a \leq p-2$ such that neither $a^{p-1}-1$ nor $(a+1)^{p-1}-1$ is divisible by $p^2$.[/quote]
Call the set of integers $A$,where $a \in A \implies p^2 \not | a^{p-1}-1)$,where $p$ is a prime.Note that $(P-a)^{p-1}-a^{p-1} \equiv pa^{p-2} \not\equiv 0 \pmod p^2$,so we get that atleast,one of $(p-a,a) \in A$.Now FTSOC we assume the opposite (i.e. no integer $a$ exists such that neither $a^{p-1}-1$ nor $(a+1)^{p-1}-1$ is divisible by $p^2$.)So clearly $1$ doesnt belong in the set $A$.But this gives $p-1 \in A$ and we get,
 $$p-2 \not\in A \implies 2 \in A \implies 3 \not\in A \implies 4 \in A\implies p-4 \not\in A$$
So, \begin{align*} p^2|(p-2)^{p-1}-1, \implies (p-2)^{p-1} \equiv p.2^{p-2}+2^{p-1} \equiv 1 &\pmod {p^2} \\
 p^2|(p-4)^{p-1}-1\implies (p-4)^{p-1} \equiv p.4^{p-2}+4^{p-1} \equiv 1 &\pmod {p^2} \end{align*}
Finally we slve a system of equations,(Consider them in modulo $p^2$)
\begin{align*}p.4^{p-2}+4^{p-1} &\equiv1 \\
&\equiv (p.2^{p-2}+2^{p-1})^2 \\
&\equiv p.4^{p-1}+4^{p-1}\end{align*}
Thus we have $p.4^{p-2} \equiv p.4^{p-1} \pmod p^2 \implies p^2|4p\implies \text{Contradiction!}$,The End $\blacksquare$[/hide]

Let us define set $A$ to be the set of $a$ such that $a^{p-1}\not\equiv 1 \pmod{p^2}$. We would like to show that there are two elements of $A$ that are consecutive. Note that if $a\not\in A$ (i.e. if $a^{p-1}\equiv 1 \pmod{p^2}$), then $$(p-a)^{p-1}\equiv -\tbinom{p-1}{1}pa^{p-1}+a^{p-1}\equiv pa^{p-2}+1 \pmod{p^2}.$$ It follows that in order for $(p-a)^{p-1}$ to be congruent to $1 \pmod{p^2}$, we need $pa^{p-2}\equiv 0\pmod{p^2}$, meaning that $p$ has to divide $a^{p-2}$. But $a$ is coprime to $p$, so $(p-a)\in A$ if $a\not\in A$.

We know that $1\not\in A$, so $(p-1)\in A$. Assume for the sake of contradiction that the problem statement is false. Then we must have $(p-2)\not\in A$, $(p-3)\in A$, and $(p-4)\not\in A$. If $(p-2)\not\in A$, then $(p-2)^{p-1}\equiv 1 \pmod{p^2}$. Then, expanding and simplifying using the binomial theorem, we get $2^{p-2}p+2^{p-1}\equiv 1 \pmod{p^2}$.

If $(p-4)\not\in A$, then $(p-4)^{p-1}\equiv 1\pmod{p^2}$. Expanding and simplifying using the binomial theorem, we get $2^{p-2}+2^{2p-3}\equiv 1 \pmod{p^2}$, which we can factor as $$(2^{p-1}-1)(2^{p-2}+1)\equiv 0\pmod{p^2}.$$ Since $(p-2)\not\in A$, we must have $2\in A$, and so $2^{p-1}-1\not\equiv 0\pmod{p^2}$. So the only way that the above congruence could be true is if $p^2\mid 2^{p-2}+1$.

However, by Fermat's Little Theorem, we have $2^{p-1}\equiv 1\pmod{p}$, so $2^{p-2}+1\equiv 2^{-1}+1 \pmod{p}$. Since the inverse of $2$ is $\tfrac{p+1}{2}$, we now have $2^{p-2}+1\equiv \tfrac{p+1}{2}+1 \pmod{p}$. We see that in order for $\tfrac{p+1}{2}+1\equiv 0 \pmod{p}$, we must have $3\equiv 0 \pmod{p}$. Since we are given $p\geq 5$, we have now reached a contradiction, so it is not possible for both $(p-2)\not\in A$ and $(p-4)\not\in A$, and we are done.

[quote=sergei93]I think this problem can be tackled using group theory, just that I haven't quite found the way to do so. Has anyone tried?[/quote]

Let $P(x)=x^{p-1}-1$, and let $g$ be a generator of $(\mathbb{Z}/{p^2}\mathbb{Z})^{\times}$. The set of roots of $P(x)$ are precisely the $p-1$ elements of the multiplicative subgroup $G=\langle g^p \rangle$.

Given that $a$ is a root iff $-a$ is a root, the roots of the polynomial must also be $G'=\pm \{1, 3, \dots, p-2\}$ for the problem to not be true.

However, it can be verified that for $p\geq 5$, $G'$ doesn't form a group under multiplication mod $p^2$. This yields the desired contradiction. $\blacksquare$

Let $A=\{x\mid 1\le x\le p-2\land x^{p-1}\not\equiv 1\pmod{p^2}\}.$ We claim $a\not\in A$ implies $p-a\in A.$ Indeed, $$(p-a)^{p-1}\equiv a^{p-1}-\binom{p-1}{1}pa^{p-2}\equiv a^{p-1}+pa^{p-2}\pmod{p^2}.\quad(*)$$ Suppose FTSOC that at most one of $a,a+1$ is an element of $A$ for all $a\in[1,p-2].$ Notice $$1\not\in A\implies p-1\in A\implies p-2\not\in A\implies 2\in A\implies 3\not\in A\implies p-3\in A\implies p-4\not\in A.$$ Hence by $(*),$ $$1^2\equiv\left((p-2)^{p-1}\right)^2\equiv\left(2^{p-1}+p2^{p-2}\right)^2\equiv 2^{2(p-1)}+2\cdot 2^{p-1}\cdot p2^{p-2}\equiv 4^{p-1}+p4^{p-1}\pmod{p^2}$$ and $1\equiv (p-4)^{p-1}\equiv 4^{p-1}+p4^{p-2}\pmod{p^2}.$ Therefore, $4^{p-1}+p4^{p-1}\equiv 4^{p-1}+p4^{p-2}\pmod{p^2}$ or $4^{p-1}\equiv 4^{p-2}\pmod{p}$ or $4\equiv 1\pmod{p}$ since $p>2.$ This is absurd, as it implies $p\mid 3$ and we have $p>3.$ $\square$

We consider $a=p-2$ and $a=\tfrac{p-1}{2}$. I claim that at least one of these works.
First suppose that $a=p-2$ doesn't work, i.e. one of $(p-2)^{p-1}-1$ and $(p-1)^{p-1}-1$ is divisible by $p^2$. By the Binomial Theorem,
$$(p-1)^{p-1}-1 \equiv -(p-1)p+1-1 \equiv p \pmod{p^2},$$
so we would require $p^2 \mid (p-2)^{p-1}-1$. Again by the Binomial Theorem, we have
$$(p-2)^{p-1}-1 \equiv -(p-1)2^{p-2}p+2^{p-1}-1 \pmod{p^2} \implies 2^{p-1}-1 \equiv -2^{p-2}p \pmod{p^2}.$$
Now we look at $a=\tfrac{p-1}{2}$. We have
$$p^2 \mid (\tfrac{p-1}{2})^{p-1}-1 \iff (p-1)^{p-1}-2^{p-1} \equiv 0 \pmod{p^2} \iff -(p-1)p+1-2^{p-1} \equiv 0 \pmod{p^2} \iff 2^{p-1}-1 \equiv p \pmod{p^2},$$
but since $-2^{p-2} \not \equiv 1 \pmod{p}$, this is impossible. Likewise, $p^2 \mid (\tfrac{p+1}{2})^{p-1}-1$ is equivalent to $2^{p-1}-1 \equiv -p \pmod{p^2}$, which is also impossible, hence $a=\tfrac{p-1}{2}$ works if $a=p-2$ doesn't, so we're done. $\blacksquare$

Solved with two hints from [b]MONT[/b].

Let $S$ be the set of positive integers $k$ such that $1\le k\le p-1$ and $p^2\nmid\left(k^{p-1}-1\right).$ We will first prove that at least one of $a$ and $p-a$ is in $S$.
Assume FTSOC that neither of them are in $S$. We have that $$0\equiv (p-a)^{p-1}-1\equiv -(p-1)(p)\left(a^{p-2}\right)+a^{p-1}-1\equiv p\cdot a^{p-2}\pmod{p^2},$$ which is impossible because $p\nmid a$, contradiction.

Now, assume FTSOC that the wanted statement is false. Then, for every two consecutive positive integers between $1$ and $p-1$, inclusive, at most one of them is in $S$. Specifically, $\left\{\frac{p-1}{2},\frac{p+1}{2}\right\}$ must have exactly one element in $S$. Assume for now that $\frac{p+1}{2}$ is the one not in $S$(the other case is symmetric). Then, $\frac{p+3}{2}$ must be in $S$, so $\frac{p-3}{2}$ must not be in $S$. Then $\frac{p-5}{2}$ must be in $S$, etc. This makes all odd positive integers within bounds in $S$ and all even positive integers within bounds not in $S$, or vice versa. However, since $1$ is clearly in $S$, we indeed have that all odd positive integers within bounds are in $S$ and all even positive integers within bounds are not in $S$.

Now, this means that $p-2$ and $p-4$ are both in $S$. Plugging in,
$$1\equiv (p-2)^{p-1}\equiv -(p-1)(p)\left(2^{p-2}\right)+2^{p-1}\equiv p\cdot 2^{p-2}+2^{p-1}\pmod{p^2}.$$
Multiplying both sides by $2$, we get that $$p+2^p\equiv2\pmod{p^2}.$$ Similarly, we also have $$p+4^p\equiv4\pmod{p^2}.$$ These combine to $$p+(2-p)^2\equiv p^2-3p+4\equiv4\pmod{p^2},$$ which means that $p|3$, contradiction. QED.

Call a positive integer $0\le a\le p^2-1$ $p$-powerful if $p^2\equiv a^{p-1}-1$. If $a$ is $p$-powerful and $b$ is $p$-powerful then $ab$ is $p$-powerful. There are also at most $p-1$ $p$-powerful numbers.

Assume the opposite of what we want to prove, then $\{2k-1,2k\}$ has a $p$-powerful number for $1\le k\le \tfrac{p-1}{2}$, and since $-1$ is $p$-powerful, the additive inverse of each of those $p$-powerful is also $p$-powerful. That gives $p-1$ numbers.

However, one of the following numbers is $p$-powerful:
\[\frac{(p-2)(p-1)}{2}\]
\[\frac{(p-1)(p-1)}{2}\]
\[\frac{(p-2)(p+1)}{2}\]
\[\frac{(p-1)(p+1)}{2}\]
but none of them are between $1$ and $p-1$ or $p^2-p+1$ and $p^2-1$ inclusive. Contradiction.

Call a nonzero residue mod $p$, $a$, fortunate if $$a^{p-1}\equiv 1\pmod{p^2},$$ and unfortunate otherwise. We wish to show that there exist two consecutive unfortunate residues mod $p$.\\

Claim: At least one of $a$ and $p-a$ is unfortunate. Suppose note. Then, $$a^{p-1}\equiv 1\pmod{p^2}$$ and $$(p-a)^{p-1}\equiv 1\pmod{p^2}.$$ However, by binomial theorem the latter is $$p(-a)^{p-2}(p-1)+a^{p-1}\pmod {p^2}.$$ However, since we know that $a^{p-1}$ is 1 mod $p^2$, this means that $p(-a)^{p-2}(p-1)$ is divisible by $p^2$, which is clearly false.\\

Now, note that clearly 1 is fortunate. Thus, due to the claim the only possible way for there to be no two consecutive unfortunate numbers is if $a$ is unfortunate if and only if $a$ is even.\\

Now, this means that $p-2$ and $p-4$ are both fortunate.\\

Expanding out $$(p-2)^{p-1}\equiv 1\pmod{p^2}$$ using binomial theorem would give us $$p(-2)^{p-2}(p-1)+2^{p-1}\equiv 1\pmod{p^2}$$ which rearranges to $$2^{p-2}(p+2)\equiv 1\pmod{p^2}.$$ Doing the same with $p-4$, we have $$4^{p-2}(p+4)\equiv 1\pmod{p^2}.$$ If we square the first congruence, we get $$4^{p-2}(p^2+4p+4)\equiv 1\pmod{p^2}$$ $$4^{p-2}(4p+4)\equiv 1\pmod{p^2}$$ However, since $4^{p-2}$ is relatively prime to $p^2$, $p+4$ and $4p+4$ are both the inverse of $4^{p-2}$ mod $p^2$. Hence, they are congruent mod $p^2$, which means that $$3p\equiv 0\pmod{p^2},$$ clearly a contradiction as $p\geq5.$


$ \lim_{(x,y) \to (0,0)} \frac {x^2 \plus{} y^2}{\sqrt {x^2 \plus{} y^2 \plus{} 1} \minus{} 1} \equal{} 2$ for $ (x,y) \in \mathbb{R}^{2}$. I know that. But can it equal $ 0$ in $ \mathbb{Z}^{2}$?

$ 0 \leq \frac {x^2 \plus{} y^2}{\sqrt {x^2 \plus{} y^2 \plus{} 1} \minus{} 1} \leq x^2 \plus{} y^2$ for $ (x,y) \in \mathbb{Z}^{2}$. So the limit is $ 0$ in $ \mathbb{Z}^{2}$?

$ \minus{}1$ and $ 1$ are the closest integers to $ 0$.

[quote="ragingbullrocky"]$ \lim_{(x,y) \to (0,0)} \frac {x^2 \plus{} y^2}{\sqrt {x^2 \plus{} y^2 \plus{} 1} \minus{} 1} \equal{} 2$ for $ (x,y) \in \mathbb{R}^{2}$. I know that. But can it equal $ 0$ in $ \mathbb{Z}^{2}$?

$ 0 \leq \frac {x^2 \plus{} y^2}{\sqrt {x^2 \plus{} y^2 \plus{} 1} \minus{} 1} \leq x^2 \plus{} y^2$ for $ (x,y) \in \mathbb{Z}^{2}$. So the limit is $ 0$ in $ \mathbb{Z}^{2}$?

$ \minus{} 1$ and $ 1$ are the closest integers to $ 0$.[/quote]
use taylor formula here
$ \sqrt {x^2 \plus{} y^2 \plus{} 1} \minus{} 1$~$ 1\plus{}\frac{ x^2 \plus{} y^2 }{2}\minus{}1$ after is simple.

That was not my question. I [b]already [/b] know that the limit is 2. But can it equal 0 in $ \mathbb{Z}^{2}$?


A series of novels consists of 40 volumes. Each volume is the
same price. If the first 10 volumes cost a total of $ \$160$, what is
the cost of the entire series, in dollars?

Another way to solve this problem would be to set up a proportion.

$ \frac{10}{160} \equal{} \frac{40}{x}$

where $ x$ is how much the 40 volumes costs.

To solve proportions, we cross-multiply.

$ 10x \equal{} 6400$

$ x \equal{} 640$

So our answer is $ \boxed{640}$

$v=\text{price of a volume}$

$10v=160$
$10v\times4=160\times4$
$40v = \boxed{640}$


function
search
combinatorics unsolved
combinatorics

Denote by $ P(S)$ the family of all subsets of a finite set $ S$ (including the empty set and $ S$ itself). The function $ f: P(S)\rightarrow R$ satisfies

$ f(X\cap Y)\equal{}\min\{f(X),f(Y)\}$ for any $ X,Y\in P(S)$.

Find the largest numbers of distinct values which $ f$ can take.

There can be at max $ n\plus{}1$ distinct values the function can take for $ |S|\equal{}n$.
I shall soon post the proof.

Let  $ |S| = n$,$ S = {e_1,e_2,...e_n}$

      $ f(S) = x$ for some $ x\in \mathbf{R}$

Let each of $ f(S - e_k) = min(f(S - e_k), f(S) )\quad \forall \quad f 1\leq k\leq n$ be a distinct value (also distinct from $ x$).As of now we have $ n + 1$ values. I shall now prove that any other value of the function takes one among the $ n + 1$ values.

Let $ L_m$ denote a subset of $ S$ with $ m$ elements. For $ m\leq {n - 2}$ you can always find two distinct elements of $ S$ that are not in $ L_m$. Let those two elements be $ e_i$ and $ e_j$.(obviously $ i\neq j$)

$ f(L_m) = min( f(L_m\cup {e_i}), f(L_m\cup {e_j}) )$

This means to say $ f(L_m) = f(L_{m + 1}) \quad \forall m\leq {n - 2}$.Hence the proof.

Is there any significance with function mapping to $ \mathbf{R}$ ? Function could have mapped to any other set right ?

Was already posted and solved: http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1636421822&t=150150

[quote="srikanth"]Is there any significance with function mapping to $ \mathbf{R}$ ? Function could have mapped to any other set right ?[/quote]
Well, the obvious properties you want are that it be totally ordered and to have at least $ n \plus{} 1$ elements.  But those are the only properties of $ \bf R$ we need for the proof.


Let $ M, N, P$ be the points of the sides $ AB, BC, CA$ of the triangle $ ABC$, such that $ MNP$ be an equilateral triangle.$ AE, BF, CK$ be the medians of the triangles $ AMP, BMN, CNP$. Suppose that $ AE \equal{} BF \equal{} CK$. Prove that $ ABC$ be an equilateral triangle.
----
Prove that $ ABC$ be still an equilateral triangle if $ AE, BF, CK$ be  the bisector or  $ S_{(AMP)} \equal{} S_{(CPN)} \equal{} S_{(BNM)}$
 :blush:  :D  :lol:

3/If $ S_{(AMP)} \equal{} S_{(CPN)} \equal{} S_{(BNM)}$
It's easy to prove that $ PM//BC, MN//AC, NP//AB$
Thus ABC is an equilateral triangle.


quadratics
algebra
polynomial
geometry
Rational Root Theorem

[hide="hint"]$2(68x^2+75)=x(15x^2+373)=15x^3-136x^2+373x-150$
If we use synthetic division with (1) we'll see our result to be (102), if i'm not mistaken.
Also when x=0, our result is -150.
We have a sign change which by theorem indicates a root so $0<x<1$
[/hide]

To solve a general cubic, first divide by the coefficient of the $x^3$ term, then use Tartaglia's/Cardano's method.  (ask around on the forums if you don't know what this is - it's ugly but useful)

There exists a quartic formula as well, but it's uglier than the cubic one (which is pretty ugly by itself), but Abel proved that there is no general formula for quintics or higher using abstract algebra.

If we graph it (after dividing by the leading coefficient), we can see that it will have no rational roots.

[url=http://www.sosmath.com/algebra/factor/fac11/fac11.html]about the title[/url]
[url=http://mathworld.wolfram.com/CubicEquation.html]here too[/url]
[url=http://mathworld.wolfram.com/CubicFormula.html]here more[/url]

[quote="Ignite168"]This takes quadratics a bit further, can someone solve for all values of x?

$2(68x^2+75)=x(15x^2+373)$

Thanks. ;)[/quote]

[hide]Rearrange the equation to be $15x^3-136x^2+373x-150=0$

Then substitute values of $x$ to make the whole thing true using rational root theorem.

Then once you've found out an $x$ that works, divide $x-a$ (where $a$ is the $x$ that works) into the polynomial and then you get a quadratic.  Solve the quadratic and the answer would be $a$ and the two quadratic roots. :) [/hide]

I'm not sure if I said that right... :!:

There are many thing you can do to make your "guess and check" time simpler:

Descartes Rule of Sign (with upper and lower bound method)
Rational Root Theorem
Syntheic Division (Remainder Theorem+Factoring)

OR

The Cubic Formula (kind of a hassle)

This problem is really ugly and it comes out in a mess  :mad:.........and according to my TI-89 the roots are apparently $4.29207+1.51749i$, $4.29207-1.51749i$, and $.482517$.

Thanks guys! I'm in Geometry at the moment (Algebra 2 next year) so I have no idea what all those were but now I have a couple of things to research I guess :)

[quote="srulikbd"]ns subject!
in this link http://www.sosmath.com/algebra/factor/fac11/fac11.html ,(Solving the depressed cubic) I didn't understand why we can say that if we have $y^3+Ay=B$ we can say that $A=3st \text{ and } B=s^3-t^3$
is it WLOG?[/quote]It is making use of the cubic identity $(s-t)^3+3st(s-t)=s^3-t^3$. Compare that with this $y^3+Ay=B$. If you let $y=s-t$, $A=3st$, $B=s^3-t^3$, you obtain their equivalence.

ok tnx. I assume we can't just  make(I don't know how to say it...like making to square?) $(x+something)^3=something$ and then just find x...there is a proof that we can't make it?
and what about non integer powers?

you mean completeing the square?

The problem is that while you can make any given coefficent =0 (except the first one) you can't make two of them at the same time. You are left with something like
$(x+m)^3=nx+q$

Suppose you wanted to make
$x^3+ax^2+bx+c=0$ into the form
$(x+u)^3=v$
then
$3u=a$
$3u^2=b$
in general you can't satisfy both at the same time. If you set u=a/3 then you are left with
$(x+\frac{a}{3})^3=(\frac{a^2}{3}-b)x+(\frac{a^3}{27}-c)$

As for noninteger powers, if they are rational you can rewrite it as a polynominal with integer powers. If they are irrational, you are likely to end up with transcendental answers.

so in order to solve quartic equation we in the beginning throw out the third power, and then 1 power, and stay with 4 and 2 power, what easily solve, right?
http://planetmath.org/encyclopedia/QuarticFormula.html lol  :D
more information http://mathforum.org/dr.math/faq/faq.cubic.equations.html


[hide="Hint (Recursions)"]$ f(i,n,a*_{n})\equal{}$ the number of sequences of $ n$ elements with exactly $ i$ combinations $ 01$ and the last digit $ a_{n}\equal{} a*_{n}$

Here are some recursions:
$ f(0,n\plus{}1,0)\equal{}f(0,n,0)\plus{}f(0,n,1)$
$ f(0,n\plus{}1,1)\equal{}f(0,n,1)$
with $ f(0,1,0)\equal{}f(0,1,1)\equal{}1$
then $ f(0,n,1)\equal{}1$ and $ f(0,n,0)\equal{}n$

$ f(1,n\plus{}1,0)\equal{}f(1,n,0)\plus{}f(1,n,1)$
$ f(1,n\plus{}1,1)\equal{}f(1,n,1)\plus{}f(0,n,0)\equal{}f(1,n,1)\plus{}n$
with $ f(1,2,0)\equal{}0$ and $ f(1,2,1)\equal{}1$

$ f(2,n\plus{}1,0)\equal{}f(2,n,0)\plus{}f(2,n,1)$
$ f(2,n\plus{}1,1)\equal{}f(2,n,1)\plus{}f(1,n,0)$

[/hide]

I understood!
This problem can be do if we use the consequence of the following problem
http://www.mathlinks.ro/Forum/viewtopic.php?p=934555#934555
Prove it, please!
Do you have a more simple solution?

For all:
Do you have a more simple solution for this problem? The solution of[b] mszew[/b] is very long and very difficult to understand!

Notice that the sequence must be of the form 1...1[b]0[/b]...0[b]1[/b]...1[b]0[/b]...0[b]1[/b]...1 with at least one digit per block except the first optional block of '1's. Thus the answer is the number of ways to choose the starting position of the next 4 blocks giving the answer $ \binom{n}{4}$.

You're false. The solution is $ C^5_{n\plus{}1}$

[quote="nmtvn"]You're false. The solution is $ C^5_{n \plus{} 1}$[/quote]

Sorry I was careless.. but the method is identical...

The sequence must be of the form 1...1[b]0[/b]...0[b]1[/b]...1[b]0[/b]...0[b]1[/b]...1[b]0[/b]...0 with at least one digit per block except the first and last optional blocks. Thus the answer is the number of ways to choose the starting position of the next 5 blocks with the last block possibly starting at the $ (n\plus{}1)$th position giving the answer $ \binom{n\plus{}1}{5}$

[quote="nmtvn"]Given some $n>3$. Find the number of all sequences $ a_{1}a_{2}...a_{n}$ with $ a_{i}\in \left\{0;1\right\}$ for all $i$ such that the substring $01$ occurs exactly $2$ times.[/quote]

We have exactly four different structures for such sequences :

1) Structure 0_01_10_01_1
Such sequences are identified by triples $ (m>1,n,p)$ giving the positions of the beginning of first 1_sequence, second 0_sequence and second 1_sequence.
So we have $ \left(\begin{array}{ll}n\minus{}1\\3\\  \end{array} \right)$ such structures.

2) Structure 0_01_10_01_10_0 (only if $ n>4$)
Such sequences are identified by 4_tuples $ (m>1,n,p,q)$ giving the positions of the beginning of first 1_sequence, second 0_sequence,  second 1_sequence and third 0_sequence.
So we have $ \left(\begin{array}{ll}n\minus{}1\\4\\  \end{array} \right)$ such structures.

3) Structure 1_10_01_10_01_1 (only if $ n>4$)
Such sequences are identified by 4_tuples $ (m>1,n,p,q)$ giving the positions of the beginning of first 0_sequence, second 1_sequence,  second 0_sequence and third 1_sequence.
So we have $ \left(\begin{array}{ll}n\minus{}1\\4\\  \end{array} \right)$ such structures.

4) Structure 1_10_01_10_01_10_0 (only if $ n>5$)
Such sequences are identified by 5_tuples $ (m>1,n,p,q,r)$ giving the positions of the beginning of first 0_sequence, second 1_sequence,  second 0_sequence,  third 1_sequence and third 0_sequence
So we have $ \left(\begin{array}{ll}n\minus{}1\\5\\  \end{array} \right)$ such structures.

So, the total requested number is :

If $ n\equal{}4$ : $ N\equal{}\left(\begin{array}{ll}n\minus{}1\\3\\  \end{array} \right)\equal{}1$
If $ n\equal{}5$ : $ N\equal{}\left(\begin{array}{ll}n\minus{}1\\3\\  \end{array} \right)$ $ \plus{}2\left(\begin{array}{ll}n\minus{}1\\4\\  \end{array} \right)\equal{}6$
If $ n>5$ : $ N\equal{}\left(\begin{array}{ll}n\minus{}1\\3\\  \end{array} \right)$ $ \plus{}2\left(\begin{array}{ll}n\minus{}1\\4\\  \end{array} \right)$ $ \plus{}\left(\begin{array}{ll}n\minus{}1\\5\\  \end{array} \right)$

So $ N\equal{}\frac{(n\plus{}1)n(n\minus{}1)(n\minus{}2)(n\minus{}3)}{120}$ $ \forall n>3$

[quote="pco"]We have exactly four different structures for such sequences[/quote]

Actually you essentially have only one because you can count in the way I showed such that it includes all possibilities

pco, use "\binom{}{}" or "{  \choose  }" for pretty binomial coefficients (& less typing that all those arrays).

@weiquan:
Your solution is very good, it's short and original! Thank you very much!


conics
algebra
polynomial
geometry
3D geometry
prism
system of equations

I have heard many times that a system of equations of $n$ variables can only have a unique solution set if the system has n equations.

How is this true? Just today I used only 3 equations of 4 variables to find the unique solution set.

Am I missing something here?

$x^2+y^2=0$ has one solution (over $\Re$).
There are probably some implicit restraints in the equations. Perhaps you can show us the problem you were working on?

Well if they're linear equations, then yeah... or if they happen to be "special", if you know what I mean.

i am pretty sure that it means linear equations...it gets more complicated with conics, etc

Yes I am talking about linear equations.

However, I ask this question because I solved a system of linear equations of 4 variables with only 3 equations. This seems to contridict the above dogma.

$(1)$ $c_1a_1 + c_2a_2 + c_3a_3 + c_4a_4$
$(2)$ $c_5a_1 + c_6a_2 + c_7a_3 + c_8a_4$
$(3)$ $c_9a_1 + c_{10}a_2 + c_{11}a_3 + c_{12}a_4$

where $c_n$ is a constant and $a_n$ represents a variable

You could just do $S_1(1)+(2)$, $S_2(1)+(3)$, $S_3(2)+(3)$, (where $S_n$ represents a non zero scalar) to get linear equations of three variables, which is solvable. Then just continue the gaussian elimination method to solve the system.

So why does an n variable linear system of equations require n equations to determine the system? Obviously, a system of linear equations of 4 variables can be solved with only 3 equations.

EDIT: I was thinking and does this mean that I only found one possible solution to the above system? If so, how can one prove that if there is n systems and n variables, then there is only one unique solution set?

[quote="breez"]$(1)$ $c_1a_1 + c_2a_2 + c_3a_3 + c_4a_4$
$(2)$ $c_5a_1 + c_6a_2 + c_7a_3 + c_8a_4$
$(3)$ $c_9a_1 + c_{10}a_2 + c_{11}a_3 + c_{12}a_4$

where $c_n$ is a constant and $a_n$ represents a variable

You could just do $S_1(1)+(2)$, $S_2(1)+(3)$, $S_3(2)+(3)$, (where $S_n$ represents a non zero scalar) to get linear equations of three variables, which is solvable. Then just continue the gaussian elimination method to solve the system.

So why does an n variable linear system of equations require n equations to determine the system? Obviously, a system of linear equations of 4 variables can be solved with only 3 equations.[/quote]

I think that using your method with explicit numbers, you would find either that the fourth variable takes arbitrary values or that two of the equations in the system of three are linearly dependent.

Try it out with actual numbers.  Your solution can't possibly be right, because a $4$-variable linear equation describes a $3$-space in $4$-space.  The intersection of two spaces forms a plane.  The intersection of a plane and a space forms a line.  A point is impossible to form!

For an easier three-dimensional analogue, can you see why it is impossible for two planes to intersect to form a point?

You can find everything in terms of a single variable, but you can't determine that variable unless you're given a fourth equation.

It's related with the fact that a polynomial of degree $k$ is determined by at least $k+1$ points.

Try to position two pieces of paper so that their intersection point is a single point. It could take a while though... :D (keep in mind that the pieces of paper are only parts of infinite planes though).

[quote="breez"]Yes, so basically I found one solution of infinite others?

btw, where can I learn more about intersections of spaces/planes/etc? I don't understand nor can I picture the "intersection of two spaces."[/quote]

Neither can I.  That's why I use planes as my analogues.  :D

Well you can imagine rectangular prisms which are pieces of space. :D


geometry
geometric transformation
rotation

Sam's answer of this problem:
If in $00: 00$ is dark, will after $72$ hours be sunny ?
was:
Yes. It will be sunny.

His teacher saw that he had a mistake. What was his mistake, and what is the
real answer ?

It will not be sunny, because 72 hours is 3 days, so it will be dark.

[quote="#H34N1"]I don't get it. It would not be sunny since $0\equiv 72\mod 24$ or something, so it'd be not sunny[/quote]

You're thinking WAY too complicated.

[quote="xpmath"]What's wrong with using modulo?[/quote]

Why use it when you can use good ol' 2nd grade division?  :blush:

[quote="xpmath"]Both ways are all right.

Off topic: I can't believe you were actually smarter than me in 4th (or was it 5th) grade! :oops:  Not now though...[/quote]

I was not! And that IS spam!

On topic: It COULD be sunny, if Daylight Savings Time occured and it was dawn...

[quote="xpmath"]I was on topic for the first sentence.
I'm pretty sure that it is not DST.[/quote]

Not DST? How about a global catastrophe involving the Earth being knocked to an angle where it's always sunny where they live?

Or maybe they live at the N. Pole or S. Pole  :roll:

[quote="frostmourne"]1. as long as the earth is still intact and rotating, one section will never be all sunny

2. this has strayed from math, so try to get back to the math problem

if 00:00 is dark, then 72 hours later, it is still dark because it will be 00:00 again[/quote]

1. Incorrect. Suppose that it was tilted so that it's rotation was perpendicular to the rays of the sun. That's only one counter example to your conjecture.

2. Whatever.   :wink:

[quote="vamathletes"]Doesn't this say sam made a mistake, so it would be dark.[/quote]

Yeah, the original question was a yes-no question, sam said yes, and apparently he was wrong...so obviously its not sunny.

Ah, well, this is AoPS, so modulo is perfectly fine.
Also, yes, the question asked what his mistake was, and 72 is
0 (mod24), so it will be some some full days, and it will still be dark. Not taking into consideration seasonal differences...   :roll:


Given W be a vector space and  two $ U,V$are two sub vectors space of W ( $ U,V \in W$ )such that $ U  \cap V \equal{}\{0\}$ and $ U\plus{}V\equal{}W$
Prove that : $ dim(U)\plus{}dim(V)\equal{}dim(W)$
Sorry for my bad English

Let $ \{u_i\}$ be a basis for $ U.$ Let $ \{v_j\}$ be a basis for $ V.$

First, we claim that $ \{u_i\}\cup\{v_j\}$ is an independent set.

Suppose $ \sum_i\alpha_iu_i\plus{}\sum_j\beta_jv_j\equal{}0.$ Note that $ \sum_i\alpha_iu_i\in U.$ Hence, $ \sum_j\beta_jv_j\equal{}\minus{}\sum\alpha_iu_i\in U$ also. Thus, $ \sum_j\beta_jv_j\in U\cap V.$ Since $ U\cap V\equal{}\{0\},$ then $ \sum_j\beta_jv_j\equal{}0.$ And since $ \{v_j\}$ is an independent set, we have that $ \beta_j\equal{}0$ for each $ j.$

The same argument with the letters reversed shows that $ \alpha_i\equal{}0$ for each $ i.$ Hence, $ \sum_i\alpha_iu_i\plus{}\sum_j\beta_jv_j\equal{}0$ implies that each $ \alpha_i\equal{}0$ and each $ \beta_j\equal{}0.$ Thus $ \{u_i\}\cup\{v_j\}$ is an independent set.

The statement that $ U\plus{}V\equal{}W$ is that statement that for all $ w\in W,$ we can write $ w\equal{}u\plus{}v$ for $ u\in U,v\in V.$ But then $ u\equal{}\sum_i\alpha_iu_i$ and $ v\equal{}\sum_j\beta_jv_j,$ so it follows that $ w\equal{}\sum_i\alpha_iu_i\plus{}\sum_j\beta_jv_j.$

Thus $ \{u_i\}\cup\{v_j\}$ is an independent set that spans $ W,$ hence a basis of $ W.$ The cardinality of this basis is the sum of the cardinalities of each component basis. That is, $ \dim W\equal{}\dim U\plus{}\dim V.$


Princeton college LaTeX integration search calculus \/closed

For some unknown reason, there has been a really serious issue with triple posting/spamming. I've heard of numerous people when they don't get their threads answered, they post it multiple times in other forums, and it's just very annoying.

So, do you think we should have anti-multiple posting filters to avoid this issue from arising ever again? (It's like filtering multiple-posting)

It's almost impossible to create such a filter that you are proposing.

http://www.phpbb.com/community/viewtopic.php?t=367172

Something like that...

I don't know how it works, but the Princeton Listserv lists don't allow people to post the same message twice. Maybe you could check each new post against the most recent $ n$ posts, where $ n$ is small enough to not cause too much work but large enough to actually do something, and reject the post if it is too close to an existing one (or even just if it's identical). How bad could that be? At least then people would be forced to wait for a while before making the same post in a different forum, or they'll have to modify the post somewhat.

[quote]they'll have to modify the post somewhat[/quote]
Which they will certainly do. (Some of them do it already.)

For mathematical topics, they could check LaTeX formulas of significant length against each other, which would solve mlok's problem some what (most don't edit the LaTex formulas).

It's not likely two posts with $ \sum^{1523n}_{i\equal{}1}\int^{2\pi}_{ni}f^{(4)}(i)$ or something like that would happen in the same day without it being a double post.

#H34N1, that is already implemented. But that's for double posting in the same thread. We're talking about different threads in different forums. It's hard to implement any of these ideas. There are very few (compared to the total number of posters) that do this thing (post the same problem in 5 different forums) and the solution is by far not simple and easy to avoid (once they realize they can't do that, they will change a little thing everywhere - thus making it impossible for the computer to distinguish between posts).

It's not that serious of an issue, and we don't need a filter because thats what moderators are for.

It's not about that. It's a technical impossibility at this time anyway (and I doubt it will change in the next years).

Like egosearch, it has the posts that a person made stored in an SQl database. It could search with 80% relevance against their own post and reject it.

I write many similar-looking posts.  Any threshhold low enough to catch simple wording changes/addition of nonsense at the end of posts is too low to avoid lots of false positives.  This is something that moderators should (and can, and do) take care of.  One thing you can do to help moderators is to comment on doubles with text to the effect of, "This has been posted in three other forums.  That kind of behavior is extremely rude -- please stop."

Just asking: if the same question is posted in two different threads, is it really much of a problem? the only thing i can think of is people abusing this and trying to get their post count up... which very much could be "the problem".  :huh:

Or...sometimes people get impatient and they want their homework answered quickly.

Darij, it will be a few more years before that is implemented.

[quote="darij grinberg"]http://stupidfilter.org/   :P

  dg[/quote]

God, after reading just a page of that site......

If just we could apply that to politicians and the news.  I could use some peace and quiet.

What should someone do if they posted a question that's integral to understanding a concept on a test, but it hasn't been answered?

I guess to restate, what's a good way to get their question answered without being "annoying" and causing problems with multiple postings?

Go find your teacher and ask him or her.


advanced fields
advanced fields unsolved

A standard ,fair 6 sided dice is rolled two times susessively.
Let $\alpha,\beta$ be the numbers appearing in the first, second respectively and the following equality.

\[(x-\alpha)^2(x-\beta)^2=x^4+ax^3+bx^2+cx+d\]

Find the expectation values of $a,b,c$ and $d$.

Would you please move this problem to an appropriate forum,moderator Myth.

kunny

It could potentially go many places; I don't see the harm in just leaving it here.

Each of $\alpha$ and $\beta$ is a random variable with mean $\frac72$ and variance $\frac{35}{12}.$ Furthermore $\alpha$ and $\beta$ are independent. This gives us the following without digging any further. (Note that $E(\alpha^2)=\frac{91}6.$)

$E(a) = -2E(\alpha+\beta) = -2\cdot2\cdot\frac72 = -14.$

$\text{Var}(a)=4\text{Var}(\alpha+\beta) = 4\text{Var}(\alpha)+4\text{Var} (\beta) = \frac{70}3.$

$E(b)=E(\alpha^2+4\alpha\beta+\beta^2) = E(\alpha^2)+4E(\alpha)E(\beta) + E(\beta^2)$

$=\frac{91}6+4\cdot\frac72\cdot\frac72 + \frac{91}6 = \frac{238}3.$

$E(c)=-2E(\alpha^2\beta+\alpha\beta^2) = -2[E(\alpha^2)E(\beta) + \E(\alpha)E(\beta^2)]$

$=-2(\frac{91}6\cdot\frac72+\frac72\cdot\frac{91}6)=-\frac{637}3.$

${E(d)=E(\alpha^2\beta^2)=E(\alpha^2)E(\beta^2)=(\frac{91}6})^2 = \frac{8281}{36}.$

Thank you for your reply, Kent Merryfield.

Here is my solution.

From $E(1)=1,E(\alpha)=\frac{7}{2},E(\alpha )^2=\frac{91}{6}$,

$E((x-\alpha)^2)=E(x^2-2\alpha x+\alpha ^2)$

$=E(1)x^2-2E(\alpha)x+E(\alpha ^2 )=x^2-7x+\frac{91}{6}$.

Similarly $E((x-\beta)^2)=x^2-7x+\frac{91}{6}$.

Since $\alpha$ and $\beta$  are indepedent,

$E(f(x)^2)=E((x-\alpha)^2(x-\beta)^2)=E((x-\alpha)^2)E((x-\beta)^2)$

$=\left(x^2-7x+\frac{91}{6}\right)^2$

$=x^4-14x^3+\frac{238}{3}x^2-\frac{637}{3}x+\frac{8281}{36}$

On the other hand,
$E(f(x)^2)=E(x^4+ax^3+bx^2+cx+d)$

$=E(1)x^4+E(a)x^3+E(b)x^2+E(c)x+E(d)$

Comparing the coefficients of $x^3,x^2,x$ and costant term,yielding Kent Merryfield's answer.


[quote="sinankaral53"]$ 1 \minus{} \sqrt3.\cos{40} \equal{} ?$[/quote]
[color=blue][b] its realy what i could understan[/b][/color]

[url=http://www.servimg.com/image_preview.php?i=305&u=12899977][img]http://i89.servimg.com/u/f89/12/89/99/77/almonk18.jpg[/img][/url]
 :)

[quote="sinankaral53"]$ 1 \minus{} \sqrt3.\cos{40} \equal{} ?$[/quote]

Do you expect a simplified answer? Because there is no simpler exact answer; you have to use a calculator for the approximate answer.

i worked on this problem so much but probably there is a mistake
otherwise as you said no simpler answer

hello, do you mean $ 1\minus{}\sqrt{3}\cos(40^{\circ})$?
Sonnhard.


MATHCOUNTS
geometry
3D geometry
sphere
ratio

A right circular cone whose base has a radius of 4 cm and whose  height is greater than 2 cm is inscribed in a sphere with a radius of  5 cm, as shown. What is the ratio of the volume of the cone to the volume of the sphere? Express your answer as a common fraction.

Since the bone is right, the altitude in perpendicular to the base. There is a 3,4,5 triangle with the right angle on the center of the base of the cone, another vertex at the center of the sphere, and another vertex somewhere on the circumference of the base of the cone. Since the radius of the sphere is 5, the height of the cone is 8, and the volume of the cone is $ \frac{128\pi}{3}$ cubic centimeters. The volume of the sphere is $ \frac{500\pi}{3}$. Thus our desired ratio is $ \frac{128}{500}\equal{}\boxed{\frac{32}{125}}$.


MATHCOUNTS
ratio
geometry
3D geometry
prism
rectangle
modular arithmetic

A couple more problems from my Mock MathCounts test - PM me if you want the whole thing.

1. Find the 9920th digit after the decimal place in the decimal equivalent of 5/7.
2. Find the only integer below 3000 that has exactly 11 distinct, positive factors.
3. The average words per sentence in a certain essay is 20. On the
other hand, the average words per sentence in a certain instant
messaging conversation is 5. If the average words per sentence
of the combination of the two is 15, find the ratio of words in the
essay to the number of words in the instant messaging conversation.
(Note for question 3: I dunno if I worded it right. I gave the problem to someone else and they got a different answer than I did.)
4. A certain cube made out of pie has side length 50 cm, and costs $ \$$150. Another rectangular prism made out of the same kind of pie has dimensions 25 cm x 75 cm x 100 cm. How much does the rectangular prism cost, given that the cost of prisms made out of pie are based solely on volume?
5. Find the area of a triangle with vertices at points (2,3), (2,6) and
(5,3). Give your answer as a decimal.

CHALLENGE PROBLEMS. May not be able to be solved by the average middle school student? I dunno.

300 Spartans are preparing for battle, but unfortunately they
haven’t come up with a battle formation yet. If they must be
positioned so that they create a rectangle (with every Spartan
in the formation), then how many formations are possible?

What integer n has the property that 4100 is greater than n50, and
4100 is less than (n + 2)50?

Okay. Have fun! Remember - PM me if you want more problems.

1. [hide]5/7= 0.714285....  9920(mod 6) is 2. so the second digit in the repeating sequence is 1.[/hide]

2. [hide]1024 = 2^10 which has (10+1)=11 factors, so 1024.[/hide]

3. [hide]Let the number of sentences in the essay be x and the number of sentences in the instant messaging conversation be y. There are 20x words in the essay, and 5y words in the instant messaging conversation. (20x+5y)/(x+y)=15, so 20x+5y=15x+15y. That means 5x=10y, so x=2y. 40y/5y=8/1.[/hide]

4. [hide]The volume of the cube is 50^3=125000 and the volume of the prism is 187500. Let the price of the prism of pie be x. Then, 187500/12500=x/150, so x=225.[/hide]

5. [hide]The area of the triangle is bh/2, the base of this triangle is 3 and the height is 3, so the area of the triangle is 4.5.[/hide]

6. [hide]The prime factorization of 300 is 2^2 * 3 * 5^2, so it has (2+1)(1+1)(2+1)=18 factors. The length of the rectangle is one of the factors and the width is 300/factor, so there are 18 formations.[/hide]

7. [hide]4100/50=82, so n=81[/hide]

[hide="1"]

$ \frac {5}{7} \equal{} .714285....$(repeats) so $ 9920 \equiv 2 \pmod{6}$, thus the dgit is $ \boxed{1}$[/hide]
[hide="2"]To have an odd number of factors, a number must be a square and it's prime factorization must be $ p^{10}$.  If we use $ 2$, then $ 2^{10} \equal{} 1024$ and $ 3^{10} > 3000$, thus the answer is $ \boxed{1024}$[/hide]
[hide="3"]We make an equation where $ x \equal{} \text{ number of sentences in essay}$ and $ y \equal{} \text{ number of sentences in IM}$.  So:

$ \frac {20x \plus{} 5y}{x \plus{} y} \equal{} 15 \implies 5x \equal{} 10y \implies x \equal{} 2y \implies \frac {x}{y} \equal{} \boxed{2}$[/hide]
[hide="4"]Volume of cube is $ 50^3 \equal{} 125000$ with price 150.  Volume of prism is $ 25 \times 75 \times 100 \equal{} 187500$.  Setting up proportions, we find the answer is:

$ \frac {125000}{150} \equal{} \frac {187500}{x} \implies \boxed{x \equal{} 225}$[/hide]
[hide="5"] Shoestring:

(2,3)
(2,6)
(5,3)
(2,3)

$ (6 \plus{} 30 \plus{} 6) \minus{} 12 \minus{} 6 \minus{} 15 \equal{} 9 \div 2 \equal{} \boxed{4.5}$

[/hide]
[hide="6"]  We simply need to find the number of factors of 300 and divide by 2.  The prime factorization is $ 2^2 \ times 3 \times 5^2$ so the answer is $ (2 \plus{} 1)(1 \plus{} 1)(2 \plus{} 1) \equal{} 18 \div 2 \equal{} \boxed{9}$[/hide]
[hide="7"]  We have $ 4100 > 50n$ and $ 4100 < 100 \plus{} 50n$.  Dividing 4100 by 50, we get 82, but since that would make it equal, we subtract 1 and our answer is thus $ \boxed{81}$

[/hide]

[quote="007math"][quote="Waffle"] Mock MathCounts test [/quote]

Shouldn't this go in the MC forum then?[/quote]

Naw. I chose a bunch of problems I thought that a normal middle school student should probably know how to do.

EDIT: Maybe you guys should check your answers. Because for some reason, 007math and cheeseater get different answers on a bunch.

I got...
[hide="Question 1"]1, yeah, just see their answers.[/hide]
[hide="Question 2"]2, 1024, again, just see their answers.[/hide]
[hide="Question 3"]3, I just got the same as 007math, but I asked my friends about it, and some agreed with cheeseeater.[/hide]
[hide="Question 4,5"]Again, just see their answers[/hide]
[hide="Question 6"]This one, I'd have to agree with cheeseater. Since I didn't say "distinct", i think 18 is right.[/hide]

GAAH QUESTION 7 got MESSED UP!

Sorry guys, but the right question was...

What integer n has the property that $ 4^{100}$ (not 4100) is greater than $ n^{50}$, and $ 4^{100}$ is less than $ (n\plus{}2)^{50}$?

Sorry for that.

An average middle schooler probably couldn't do any of these.  5% of them are super smart, 20% okayish B-C grades and th rest D and F and don't pay attention...

But this is AoPS where second graders get 25 on USAMTS

[hide="Problem 1"]
$ \frac {5}{7} \equal{} 0.\overline{714285}$, and we want the $ 9920$th digit after the decimal point.  Because the digits repeat every $ 6$ times, we search for $ 9920$'s modulo $ 6$ residue (or for those of you who don't know modulus yet, the remainder when $ 9920$ is divided by $ 6$) and find that it is $ 2$.  Thus, the desired digit is the second in $ 714285$, which is $ \boxed{1}$.
[/hide]

[hide="Problem 2"]
To have $ 11$ distinct, positive factors, a number must be of the form $ p^{10}$, where $ p$ is a prime.  This is because the number of distinct, positive factors of a number $ n \equal{} p_1^{a_1}\times p_2^{a_2} \times \ldots \times p_k^{a_k}$ is $ (a_1 \plus{} 1)(a_2 \plus{} 1)\dots (a_k \plus{} 1)$, and because $ 11$ is prime, it can only be $ (10 \plus{} 1)$, so it must be of the form $ p^{10}$.  The smallest prime $ p$ that satisfies this is $ p \equal{} 2 \implies p^{10} \equal{} \boxed{1024}$, and we quickly check $ p \equal{} 3$ to ensure that it is the only one that is less than $ 3000$.
[/hide]

In that case, question 7 would be [hide]15 because you can simplify the exponents 100 and 50 to 2 and 1, so 16 and n are the remaining numbers. Therefore, n has to be 15 so that n+2 is 17.[/hide]


function
integration
algebra unsolved
algebra

[quote="hien"]Let $f(x)$ is continuos on $R$. Assume that $\int\limits_{x}^{x+1}f(t)dt=0$ for all $x\in R$. Prove that $f$ is period function[/quote]
Let \[F(x)=\int_{a}^{x}f(t)dt\] . We have $F(x+1)=F(x)$ periodic function, therefore $f(x)=F'(x)$ periodic too.


recently started playing magic again and i cant seem to find any of my old cards.... i dont really like some of the newer sets and i prefered the old cards. hoping some1 out there has some older cards that they no longer might need? we could jus do some transaction through ebay or something?

you can contact me on aim (LordOfTheLings1) or email (Lingfengzhou@yahoo.com)

I had some... but I'm not really that good. I win with lame cards still do to strategy :)

i got about 1000 cards, man, and I no longer play

you like old cards? I got mostly of the godly old ones (Zuran Orbs, Icy Manipulators, Shiva Dragons, all of the Avatars and a bunch more)

if you leave your msn contact here, we can talk more

unfoturnately i do not have msn... but we could communicate through email or if u have aim

in my blog i was selling cards and paper

for more information

http://www.senhorcarteiro.blogspot.com


[url]http://www.artofproblemsolving.com/Wiki/index.php/1976_USAMO_Problems/Problem_5[/url]

I am having a little trouble understanding the progression of thoughts in the first solution given for this problem. I understand (and came up with the second solution) when I was working on the problem, but the first solution slightly confuses me. I get lost particularly at the long line of equal summations.
Any help would be appreciated!
Thanks!

The generality of the first solution isn't really necessary; all that's being done is substituting four primitive roots of unity instead of three and summing all the resulting equations.


number theory
least common multiple
MATHCOUNTS

hi everyone again a silly doubt . :D

  this question is from aops which i found n din see answer n tried to solve but couldnt  :(

here it is:-

John runs a mile in 6 minutes. Bob runs a mile in 9 minutes.
Suppose they were on a circulur track and ran at the same time.
In how many minutes will John meet up with Bob again after he passes Bob?

I know this question is very easy for you guys.

bur please post the answer.

explanation please!

When John runs 1 mile, Bob would have run 2/3 of a mile.
or in other words he would have 1/3 of a mile remaining
when John finishes 2 miles he would have 2/3 of his [u]second[/u] mile remaining

When John completes his third lap Bob would have completed his second lap.

So the answer would be 18 min, which can be found through the above method or by just taking the LCM of 6 and 9.

I think...

Yes batteredbutnotdefeated:

The second way, finding the LCM, is much faster and would be more useful in MATHCOUNTS like situations.


inequalities
geometry
rectangle
AMC 10
AMC 8
AMC 10 A
AMC

whoa. simon's favorite factoring trick anyone?

uh... i'm not that bright of a person so i just substituted in the set 3,3,4 because that's what made the most sense to me.(is the Amc 10 a multiple choice test like the amc 8?)

Yes, AMC-10 is multiple choice.
How I did it was:
A + B + C = 10
AMC + AM + MC+ MA + A + B + C + 1 = (A + 1)(B + 1)(C + 1)
AMC + AM + MC + MA + 11 = (A + 1)(B + 1)(C + 1)
AMC + AM + MC + MA = (A + 1)(B + 1)(C + 1) - 11
The largest possible value of (A + 1)(B + 1)(C + 1) will be 80 since 3, 3, and 4 are the three numbers closest to equality.
AMC + AM + MC + MA = 80 - 11 = 69.

[quote="WarpedKlown1335"]Let A, M, and C be nonnegative integers such that A+M+C=10. What is the maximum value of A*M*C + A*M + M*C + C*A?[/quote]

Maximums almost always occur when the numbers are as close to each other as possible.  In this case, they must be 3,3, and 4.  So AMC = 36, AM = 9, MC=12, and AC=12.  Sum = 69.

This isn't the most sound way to do it, but oh well.

[Edit] Oh wait, everyone else's solution depended on numbers being close together producing the greatest product anyway...

I agree with mathfanatic, but i'll just show my thought process when i did it the first time (some years ago).

i think on an AMC-12, they had the same question, but with A+M+C=12.  Anyways, that's how i did it, just assuming they were equal.  At the time i didnt know what the am-gm inequality was, so  the way i thought of it was like this: i knew from geometry that a rectangle is maximized when it is a square, so i thought that the volume of a rectangular box would be maximized when it is a cube.  So i thought of the AMC, AM, MC, etc. as the volumes/areas of cubes/squares, which would be maximized when a=m=c.

But i thought that the process was pretty interesting, thinking of it like a geometry maximization problem.  I thought that this was groundbreaking, cause i never saw something like this before... until later when i learned the am-gm inequality.


parameterization
calculus
calculus computations

Suppose that the surface of a football is given by the graph of the equation $4x^{2}+y^{2}+4z^{2}=9$, and that a drop of water lands on the point $(1,1,1)$.

Find a parametrization for the curve that the drop of water follows, assuming that it moves in the direction tangent to the football most nearly downward.


Let $\mu(X) < +\infty$ and let $f_n\to f$ by $\mu$ and $g_n\to g$ by $\mu$. Proof that:
a)$f=0 \mu- a.e. \Rightarrow  f_n^2\to f$ by $\mu$
b)$f_n*g\to f*g$ by $\mu$
c) $f_n^2\to f^2$ by $\mu$
d)$f_n*g_n\to f*g$ by $\mu$
Thanks for any help :)

[quote="tom123"]Let $\mu(X) < +\infty$ and let $f_n\to f$ by $\mu$ and $g_n\to g$ by $\mu$. Proof that:
a)$f=0 \mu- a.e. \Rightarrow f_n^2\to f$ by $\mu$
[/quote]
$f=0 \mu- a.e.$ - mean $\mu\{x| \; f(x)\ne 0\}=0$? If it's right than
[hide]Let $A=\{x| \; f(x)\ne 0\}$. Then $\mu A =0$ and $X_1 = X \setminus A$. It is obvious that if $f_n^2\to f$ by $\mu$ on $X_1$ then $f_n^2\to f$ by $\mu$ on $X$. (Because $\mu (X\setminus X_1) =0$).
Now let $\varepsilon,\delta >0$.  We want to prove that
\[ \exists N, \forall n>N \mu\{|f^2_n|>\delta\} < \varepsilon.  \] But we have  $f_n\to f$ by $\mu$. It follows that $\exists M, \forall m>M \mu\{|f_n|>\sqrt{\delta}\} < \sqrt{\varepsilon}.$ It follows that  $\exists M, \forall m>M \mu\{|f_n|^2>\delta\} < \varepsilon.$[/hide]

[quote="tom123"]Let $\mu(X) < +\infty$ and let $f_n\to f$ by $\mu$ and $g_n\to g$ by $\mu$. Proof that:
b)$f_n*g\to f*g$ by $\mu$
[/quote]
We want to prove that $\forall \delta , \varepsilon >0 \; \exists N, \forall n>N \mu\{|f_ng-fg|>\delta\} < \varepsilon.$
Or
$\forall \delta >0 \; \mu\{|g||f_n-f|>\delta\} \to 0$ when $n\to \infty.$
If $\mu\{g(x)=\infty\}>0$ than i don't understand what is that mean $f_ng-fg$ on this set...
So i assume that $\mu (\{g(x)=\infty\})=0$.So $\bigcap\limits_{k=1}^{\infty} \{|g|>k\} = \emptyset$, and $\{|g|>k+1\}\subset \{|g|>k\}$ thus
$\mu \{|g|>k\} \to 0$. So there exist $N$ such that $\mu\{|g|>N\}< \varepsilon.$
Then $\{|g||f_n-f|>\delta\} \subset \{|g|>N\} \bigcup \{|f_n-f|>\frac{\delta}{N}\}$
So  $\mu \{|g||f_n-f|>\delta\} \le \mu( \{|g|>N\} \bigcup \{|f_n-f|>\frac{\delta}{N}\}) \le$
$\le \mu( \{|g|>N\})+ \mu(\{|f_n-f|>\frac{\delta}{N}\}) \le$
(since $f_n\to f$ bu $\mu$ we get $\exists N, \forall n>N \mu\{|f_n-f|>\delta\} < \varepsilon.$ )
$\le \varepsilon + \varepsilon =2\varepsilon \; \forall n>N$.
So we prove that
\[ \forall \delta , 2\varepsilon >0 \; \exists N, \forall n>N \mu\{|f_ng-fg|>\delta\} < 2\varepsilon. \]

[quote="tom123"]Let $\mu(X) < +\infty$ and let $f_n\to f$ by $\mu$ and $g_n\to g$ by $\mu$. Proof that:
c) $f_n^2\to f^2$ by $\mu$
[/quote]

we want to prove that \[ \forall \varepsilon ,\delta >0\; \exists N \forall n>N \mu\{|f_n^2-f^2|>\delta\}<\varepsilon. \]
Note that
2) $\exists N_1 \; \forall n>N_1 \mu\{|f_n-f|>\frac{\delta}{M+\delta}\} < \frac{\varepsilon}{3}.$
1) as in b) $\exists M \mu \{|2f| > M\}<\frac{\varepsilon}{3}$
3) $\{|(f_n-f)(f_n-f+2f)|>\delta\}\subset \{|f_n-f|>\frac{\delta}{M+\delta}\}\bigcup\{|2f|>M\}$
So we can write
$\mu\{|f_n^2-f^2|>\delta\} = \mu \{|(f_n-f)(f_n-f+2f)|>\delta\} \le \mu \left( \{|f_n-f|>\frac{\delta}{M+\delta}\}\bigcup\{|2f|>M\}\right) \le$
$\le \mu \{|f_n-f|>\frac{\delta}{M+\delta}\} + \mu \{|2f|>M\} \le \varepsilon/3 + \varepsilon/3 < \epsilon$
$\forall n>N_1.$

[quote="tom123"]Let $\mu(X) < +\infty$ and let $f_n\to f$ by $\mu$ and $g_n\to g$ by $\mu$. Proof that:
d)$f_n*g_n\to f*g$ by $\mu$
[/quote]

Note that $\forall \varepsilon$
1) $f_ng_n-fg =f_ng_n - f_ng +f_ng-fg = f_n(g_n - g) + g(f_n-f) = (f_n-f)(g_n-g)+f(g_n-g) + g(f_n-f)$
2) $\exists M \; \mu\{f>M\}<\varepsilon,\mu\{g>M\}<\varepsilon$
3) $\{|f_ng_n-fg|>\delta\} \subset \{|f_n-f||g_n-g|>\delta/3\}\bigcup\{|f||g_n-g|>\delta/3\}\bigcup$
$\bigcup\{|g||f_n-f|>\delta/3\} \subset \{|f|>M\}\bigcup\{|g_n-g|>\frac{\delta}{3M}\}\bigcup\{|f_n-f|>\frac{\delta}{3M}\}\bigcup\{|g|>M\}\bigcup$
$\bigcup\{|f_n-f|>\sqrt{\frac{\delta}{3}}\}\bigcup\{|g_n-g|>\sqrt{\frac{\delta}{3}}\}$
4) $\exists N \forall n>N \mu\{|f_n-f|>\frac{\delta}{3M}\}<\varepsilon$
$\mu\{|g_n-g|>\frac{\delta}{3M}\}<\varepsilon,\mu\{|f_n-f|>\sqrt{\frac{\delta}{3}}\}<\varepsilon$
$\mu\{|g_n-g|>\sqrt{\frac{\delta}{3}}\}<\varepsilon$
Thus
$\mu\{|f_ng_n-fg|>\delta\}\le \mu\{|f|>M\}+\mu\{|g_n-g|>\frac{\delta}{3M}\}+\mu\{|f_n-f|>\frac{\delta}{3M}\}+\mu\{|g|>M\}+$
$+\mu\{|f_n-f|>\sqrt{\frac{\delta}{3}}\}+\mu\{|g_n-g|>\sqrt{\frac{\delta}{3}}\} \le 6\varepsilon \forall n>N$

[quote="tom123"][quote="anik_andrew"]
So i assume that $\mu (\{g(x)=\infty\})=0$.So $\bigcap\limits_{k=1}^{\infty} \{|g|>k\} = \emptyset$, and $\{|g|>k+1\}\subset \{|g|>k\}$ thus
$\mu \{|g|>k\} \to 0$. So there exist $N$ such that $\mu\{|g|>N\}< \varepsilon.$
[/quote]
$\bigcap\limits_{k=1}^{\infty} \{|g|>k\} = \emptyset$ or
$\bigcap\limits_{k=1}^{\infty} \{|g|>k\}\not = \emptyset$?[/quote]
Sorry, i mean
$\mu(\{g(x)=\infty\}) = \mu \bigcap\limits_{k=1}^{\infty} \{|g|>k\} = 0$ instead of  $\bigcap\limits_{k=1}^{\infty} \{|g|>k\} = \emptyset$. Then
$\mu \{|g|>k\} \to 0$
(I use that $\mu X<\infty$ for the contionuosly therem)


How does beauty in mathematics appear to you ? When ?
What makes you feel Mathematics is beautiful ?
(Please do not cite Erdos, "If numbers are not beautiful then nothing is", or the citation with Beethoven 9th Symphony ;), I would like to hear some interesting opinions of yours concerning generally aesthetics in mathematics)

well, i have discussed this many times before.. mathematics is essencially beautiful because of the human creativity that is present in a idea, proof or claim...

Yes, but did you really experienced it as such ? Is it the same feeling as for an work of art ?
Do you feel "often" mathematics is beautiful ? When reading , solving problems ?
(Sorry, if the amount of questions gets silly ;), but I want you to get the point of my question)

for me it is the same feeling of art... and i can tell, i am an artist ;) I am a musician, and i also do experimental installations ( i can explain you what this is later if you want)
but i think that the problem is with the traditional conception of mathematics, i think that conception of the postmodern aesthic of art applies more to aesthic vision of mathematics...

I think an incredible thing about mathematics is that it doesn't depend on anything. We have English, history, biology, and some other subjects that have little value outside the Earth. (Don't get me wrong, I'm not trashing other subjects.) But in math, no matter what happens for this planet with plagues, wars, hunger, or anything else, a circle will never intersect a line in three points. We can stretch the truth in politics and make ourselves believe things consistent with our greed, but the circle has no desires - if someone takes over the Universe the circle will mock him as he tries to make it intersect a line thrice. He can own a set of $n$ stars - but the number of subsets will always be $2^n$.

I also find parts math to be beautiful such as very elegant solutions.  Also things that simplify nicely make me happy as well.  (I define things that make me happy when i see them to be beautiful, its a good definition trust me) for example answers of 1, 0, pi, or products of nice binomials such as (x-1)(x+3)(x-6). answers like .87347 are ugly.


number theory
greatest common divisor
superior algebra
superior algebra unsolved

let X^P=X for all elements of ring R,P given prime no.find characteristic of R.

we have $2x=(2x)^{p}= 2^{p}x^{p}= 2^{p}x$, i.e. $(2^{p}-2)x = 0$, for all $x \in R$. hence the characteristic divides $(2^{p}-2)$ - perhaps it's equal to it?  :maybe:

The idea of -oo- can be extended to $(n^{p}-n)x=0$ for all integers n, hence the characteristic of R is a divisor of $gcd(2^{p}-2,3^{p}-3,4^{p}-4,...)$

I think this gcd is p and hence the charateristic of R is p...

just a divisor of $p$, right? but I can't see that the gcd is $p$ ...

$gcd(2^{p}-2,3^{p}-3,4^{p}-4,...)$ is a multiple of p which is usually bigger than p.
[code] p  gcd
 2    2
 3    6
 5   30
 7   42
11   66
13 2730
[/code]

LiMa

Sorry, the $\gcd$ is $\prod_{(q-1)|(p-1)}q$ (where $q$ is prime only).
For example, it is $42$ if $p=7$.

PS: note that the mentioned number is the denominator of the $(p-1)$-the Bernoulli number (see http://www.mathlinks.ro/Forum/viewtopic.php?t=91510 ).

If we refer to the gcd as $n$, then the caracteristic can be any divisor $d > 1$ of $n$, since all the rings $\mathbb Z/d$ satisfy $x^{p}= x$.

LiMa

By Jacobson's theorem, we also know that any such ring is commutative.

I wonder if we can describe all such rings (e.g. as product of these $\mathbb{Z}/(d)$).


This topic should go in the questions forum, cuz it has nothing to do with MC.  Anyways, just put dollar signs around your code and you can write in $ \text{\LaTeX}$.  You don't have to download it to use it in forums.

[code]$ (Command) $
or
\[ (Command) \][/code]

sorry about positioning.
\[ \sqrt{9}\]
wow, it works!


function
integration
real analysis
real analysis solved

1) For n \in N*, x \geq 0 prove that (1+x/n)^n \geq 1+x
2)Using 1) show that lny \leq y-1 for any y>0
3) For 0<a<b using 1) study the convergence of
x(n)= ((a+1)(a+2)...(a+n))/((b+n)(b+2)...(b+n))
BUCHAREST-2001
----------------------------------------------------------------
I will not follow the indications of the problem.
Gamma function is useful for an equivalent of x(n).

Gamm(a)=G(a)=\int_[0;+oo[exp(-t).t^(a-1)dt is defined for a>0
lim_{n->+oo}n^a.n!/(a(a+1)(a+2)...(a+n)) = Gamma(a)
This gives a(a+1)(a+2)...(a+n)~n^a.n!/Gamma(a)

x(n)~(b/a)n^(a-b).Gamma(b)/Gamma(a) when n->+oo

lim x(n)=0   since 0<a<b

Now another question: Study the convergence of \sum_{n>0}x(n)

For (1) we just use the expansion of (1+x/n)^n=1+nC1*(x/n)+S where S is >=0, and since nC1=n we get (1+x/n)^n>=1+x.

What does (3) ask? You just defined a sequence. Is the question you asked about the convergence of \sum x_n  the only question for (3)?

[quote="Moubinool"]
3) For 0<a<b study the convergence of
x(n)= ((a+1)(a+2)...(a+n))/((b+n)(b+2)...(b+n))
[/quote]
Question 3) was study the convergence of x(n)
I add a new question study the convergence of the serie  \sum x(n) with
the same hypothesis.

I don't know why the full question 3) does not appear, but i did quote
it appears.


Find all $ x,y,z \in \mathbb{Z}^{\plus{}}$ such that $ xyz\equal{}4 \left(x\plus{}y\plus{}z \right)$ and $ x<y<z$.

[quote="AstroPhys"]Find all $ x,y,z \in \mathbb{Z}^{ \plus{} }$ such that $ xyz \equal{} 4 \left(x \plus{} y \plus{} z \right)$ and $ x < y < z$.[/quote]
[hide] Okay, so we simply plug in numbers for this problem.  However, note that if x=3, then y is at least 4 and z is at least 5.  So, xyz is at least 60 and x+y+z is at least 12.  So, xyz is 5 times x+y+z.  It is quite obvious that $ \frac {x \plus{} y \plus{} z}{xyz}$ will therefore be at least 5 if x is 3 or more.  Now, we only need to plug in for x=1 and x=2.

x=1:
We obtain that
\[ xy \equal{} 4 \plus{} 4y \plus{} 4z
\]

\[ yz \minus{} 4y \minus{} 4z \equal{} 4
\]

\[ yz \minus{} 4y \minus{} 4z \plus{} 16 \equal{} 20
\]

\[ (y \minus{} 4)(z \minus{} 4) \equal{} 20
\]
Now, y-4 and z-4 must be factors of 20, but z-4 must be larger than y-4.  We find that the factor pairs of 20 are (1, 20), (2, 10), and (4, 5).  We can thus find that $ (x, y, z) \equal{} (1, 5, 24), (1, 6, 14), (1, 8, 9)$.

x=2:
We have that
\[ 2zy \equal{} 8 \plus{} 4y \plus{} 4z
\]

\[ yz \minus{} 2y \minus{} 2z \equal{} 4
\]

\[ yz \minus{} 2z \minus{} 2y \plus{} 4 \equal{} 8
\]

\[ (y \minus{} 2)(z \minus{} 2) \equal{} 8
\]
So, y-2 and z-2 are factors of 8 so that z-2 is more than y-2.  We have that the factor pairs of 8 are (1, 8) and (2, 4).  We use this to find that $ (x, y, z) \equal{} (2, 3, 10), (2, 4, 6)$.

So, $ \boxed{(x, y, z) \equal{} (1, 5, 24), (1, 6, 14), (1, 8, 9), (2, 3, 10), (2, 4, 6)}$. [/hide]


Whoosh!!! Looking out the window, the passengers see the wheels touch down on to the ground. *click* “Hello everyone!!! Welcome to Bantam. The weather outside is 51 degrees, with cloudy skies and heavy rainfall.” “Lovely weather…” people swing their heads around to see who muttered those words. “Please keep your seatbelts fastened until we reach the terminal” *click* *snap* “God some idiot already took his off” someone mutters.

As the passengers step out into the plaza, they notice the unusually smooth arches. Something about them actually seemed angular… As the small group stepped out into the city, they were instantly greeted by a mass chaos of nothing but metal upon metal upon metal. These passengers came from all around the world, but were never expecting this drab. Suddenly a member yells out: “Let’s make our own city!!!” And they did. They moved out into a peaceful grove 132.6 miles away. The city flourished economically and was bustling with productivity. On the way in, there would always be a sign greeting newcomers.

Welcome to New Bantam!!!

The city got bigger and bigger and bigger. People packed the beautifully natural city streets and talked pleasantly to each other. Not overly, but just right. All was good.

Politics. As the city expanded, the politics grew meaner and meaner. It got meaner and meaner until two opposing new wannabe mayors planned their own evil plots to kick Dojo off the mayor’s chair and plant their butts on it.

Dojo was aware of these men and believed they would remain dormant. Nothing happened until that one morning. As he woke up, he found only 16 people left in the city, among them the two evil mayor campaigners.

“This is horrible!!!” yells a citizen. “Outrageous” “Crazy” “Absurd” was just some words from the small crowd. Dojo raised his hand. “Stop please stop” he firmly said. “We will set up a jailing system.” The majority of people who vote on one person will be sent to jail, and his identity discovered.” So it was to be, on that faithful October 13th, which just happened to be a Friday.

[color=red][size=200][b]The Rules(read them, even if you already know them)[/b][/size][/color]
[list][*]Votes must be in [b]bold[/b].  If you do not bold your vote, it will not be counted.
[*]Once a player has reached lynching state, his pleas are useless and any attempts to unvote will be unheeded. You may [b]vote: no lynch[/b] – majority votes of this kind are necessary to end the day without a death.
[*]The game is not to be discussed outside of the thread unless your role specifically states that you may do so.
[*]Once your death scene has been posted, you’re dead.  Stop typing. The only thing you can type is a "bah" post.
[*]Don’t edit/delete previously submitted posts
[*]Don’t quote any PMs from me. Neither true, nor false. Seriously.
[*]If you have a night choice to make, it is due by the posted deadline.  I will not wait for you – if you do not submit a choice to me, tough!  No choice will be made.
[*]Treat this game as a commitment.  Be considerate – don’t leave us hanging.
[*]Remember, it’s a game.  It’s supposed to played.  It’s supposed to be [i]fun[/i].  Do your part.
[*] To prove you've read this, write "Dojo is awesome" in your confirm post.
[*] Check the first post of the following thread: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=177754[/list]

THE LIVING
1. dragon96
2. james4l
3. monkeygirl12
4. cf249
5. Chompy
6. Bugi
7. SuperNerd123
8. dysfunctionalequations
9. PowerOfPi
10. ernie
11. isabella2296
12. KING1
13. Mewto55555
14. lotsofmath
15. mathfreak123
16. zapi2007

[b]Sorry about a misunderstanding in the mafia role send outs. Majority for mafia is a mafia win.[/b]

Confirm in thread.

ok!!!

did you know that dojo is awesome? i mean look at that highly developed story!

I'll say so!!! How 'bout a six cuber for all that hard work? :wink:

I confirm.

The following statement is (semi)false: Dojo is awesome.</making post longer>

Confirm.

Apparently, Dojo is awesome, though I have no evidence to support this statement.

Dojo is awe.
Dojo is aweary.
Dojo is aweather.
Dojo is aweigh.
Dojo is awesome.
Dojo is awestru[b]c[/b]k.
D[b]o[/b]jo is[b]n[/b]'t aw[b]f[/b]ul.
Dojo is awhile.
Dojo is awh[b]ir[/b]l.
Dojo is awkward. (jk)

[b]m[/b]eep.

I concur that Dojo is awesome.

\confirm

[b]10[/b] confirms, [b]6[/b] to go.

Man, I love this rule.

Rofl, wouldn't it be hilarious if I said dojo was awesome? Like the day would ever come when I meant that. :P  :D

Confirm.

[quote="meewhee009"]
I KNOW.
No female?
That's just wrong.
[/quote]
Majority of people on AoPS are guys. Sorry. :)

I think that town went bad the moment they lynched Chompy. Chompy was one of the most powerful roles townies had and you guys lynched him. I can't understand why eggy protected james on the last night. It was obvious that the game was going on because someone was scum.

[quote="dragon96"]eggy likes to screw up games.[/quote]

Town's fault in general, not just eggy. Only reason it was even close was due to bad modding rules which resulted in killing ernie.

I was soo dumb this game I spent half of it thinking I was mafia then I got killed.

[quote="Dojo"][quote="pythag011"]Only reason it was even close was due to bad modding rules which resulted in killing ernie.[/quote]
No comment[/quote]

Seriously, explain to me how the game would have been worse if you didn't have random lynch rules at deadling, considering that one viable mafia strategy is just stalling until deadline.

[quote="Dojo"]Rules are rules. If you didn't like the rule, you should have just asked for a replacment.[/quote]

You never even wrote that it was random lynch at deadline. I've never seen any game ever do that so how am I supposed to know that was a rule?

At the very least, write rules that differ from the mafia standard in opening post. I'm pretty sure standard is either no lynch or person with most votes, tiebroken by who got that amount of votes first.

[quote="Dojo"]I announced rule on post #120. I clarified on #232. ernie was rand-lynched on #608 or so. He should have known the rules by then.[/quote]

Edit it into first post then. A lot less confusing since it's pretty easy to forget a rule that was announced like 400 posts ago.

Also, that rule wasn't a particularly good rule. I don't see any advantages of that rule over standard rules.

The rules about lynch were soooooo bad... It was like 2 helps for james's team ( ok this was my team so thanks :D ), first the ernie thing, then the supernerd thing...

[quote="Dojo"]I don't think many people reread the first page every day.[/quote]

I don't read it every day, but I do check it once in a while just to make sure I'm not breaking any rules.

Speak for yourself. I never check it...except maybe when scumhunting.

lastpost (this is used to preserve order of locked topic)


Prove that if $x,y \in (0,1]$ and $z>0$, then $zx+zy+2 \leq \frac{y+z}{x} + \frac{x+y}{z} $.

[quote="georg"]Sorry it is:

Prove that if $ x,y\in (0,1)$ and $ z > 0$, then $ zx\plus{}zy\plus{}2\leq\frac{y\plus{}z}{x}\plus{}\frac{x\plus{}y}{z}$.

Thank you very much! :)[/quote]

Sorry, the original inequality appears to be right, I thought it was z+x+z+y+2 on the LHS for some reason.  The $ x \equal{} y \equal{} z \equal{} 1$ case is just an equality case.  However, as it stands, the equality is unbalanced.  For example, if you let $ x$ and $ y$ get arbitrarily close to $ 1$, then the inequailty gets very close to
$ 2x\plus{}2\le z\plus{}1\plus{}\frac{2}{z}$
which clearly isn't true for $ z > 1$.  Did you mean
$ z(x\plus{}y)\plus{}2\le\frac{y\plus{}z}{x}\plus{}\frac{x\plus{}z}{y}$?

If so, then it follows from
[hide]
$ \frac{x}{y}\plus{}\frac{y}{x}\ge 2$, by AM-GM
$ \frac{z}{x}\ge zx$, $ \frac{z}{y}\ge zy$[/hide]

Sorry, I got sniped while typing my response  :rotfl:


[quote="aidan"]How many permutations are there in a $ 2\times 2\times 2$ Rubik's cube?[/quote]

You can find out [url=http://en.wikipedia.org/wiki/Pocket_Cube]here[/url].


[hide]

The nice way is to make Q(x) somehow into P(X).

P(x) = x^2*(x^4-x^3-x^2-1) + x^4 - x^3 -x.  So when we sum this for the roots of Q(x), x^2*(x^4-x^3-x^2-1) is 0, so we're concerned with x^4-x^3-x (i).  We're working with x such that Q(x)=0, or 0=x^4-x^3-x^2-1.  This means that x^4-x^3=x^2+1.  So we can substitute this into (i) to get (i)=x^2+1-x.  We know that the sum of the roots of Q(x) is 1, and we can find that the sum of the squares of the roots of Q(x) is 3.  And we're adding 1 four times, so our sum is 3+1*4-1=6.[/hide]

timhlu wrote:Consider the polynomials P(x) = x^6 - x^5 - x^3 - x^2 - x and Q(x) = x^4 - x^3 - x^2 - 1. Given that Z1, Z2, Z3, and Z4 are roots of Q(x) = 0, find P(Z1) + P(Z2) + P(Z3 + P(Z4).

[hide]Well, we reduce. Notice if x is a root of Q, P(x) = x(x^5 - x^4 - x^3 - x + x^3 - x^2 - 1) = x(x^3 - x^2 - 1) = x^4 - x^3 - x^2 - 1 + x^2 - x + 1 = x^2 - x + 1. Thus P(A) + P(B) + P(C) + P(D) = sum of the squares of roots - sum of the roots + 4 = sum of the squares of roots + 3.

If a,b,c,d are roots, (a+b+c+d)^2 = a^2 + b^2 + c^2 + d^2 + 2*pair sum. so 1 = a^2 + b^2 + c^2 + d^2 - 2, so a^2 + b^2 + c^2 + d^2 = 3.

So P(A) + P(B) + P(C) + P(D) = 3 + 3 = 6.

Tada.

[/hide]

[quote]We know that the sum of the roots of Q(x) is 1, and we can find that the sum of the squares of the roots of Q(x) is 3.[/quote]

How do you know that the sum of the squares of the roots is 3?

yeah our solutions have the same ideas.  Massamume explained that part clearly in his though.