counting
derangement
permutations
double counting
combinatorics
IMO 1987
IMO

Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.

One Nice Solution:

Count all pairs $(x, s)$ where s is a permutation with $x$ a fixed point of $x$.
Clearly, if we fix $x$, then there are $(n-1)!$ possible permutations $s$.
So the total count is $n!$.
But if we count the number of permutations $s$ with exactly $k$ fixed points,
then we get the sum in the question.

Hi e.lopes,

it is nice that you copy & paste solutions quickly but could you please be so creative and develop your [b]OWN IDEAS[/b] and write [b]DETAILED SOLUTIONS[/b]!  :)

A nice generalisation of this problem is http://www.mathlinks.ro/Forum/viewtopic.php?t=60832

Isn't it just an algebraic identity if you use the formula (which is easily proved with inclusion\exclusion) for derangements?
$ p_n(0)\equal{}n! \sum_{i\equal{}0}^{n} \frac{(\minus{}1)^i}{i!}$
Hence:
$ p_n(k)\equal{}\binom{n}{k}(n\minus{}k)! \sum_{i\equal{}0}^{n\minus{}k} \frac{(\minus{}1)^i}{i!}$

$ \sum_{k\equal{}0}^{n}k p_n(k)\equal{} \sum_{k\equal{}0}^{n} k\binom{n}{k}(n\minus{}k)! \sum_{i\equal{}0}^{n\minus{}k} \frac{(\minus{}1)^i}{i!}\equal{}\sum_{k\equal{}0}^{n} k\frac{n!}{k!} \sum_{i\equal{}0}^{n\minus{}k} \frac{(\minus{}1)^i}{i!}\equal{}n!\sum_{k\equal{}0}^{n}\frac{k}{k!} \sum_{i\equal{}0}^{n\minus{}k} \frac{(\minus{}1)^i}{i!}$

So all we need to show is that $ \sum_{k\equal{}0}^{n}\frac{k}{k!} \sum_{i\equal{}0}^{n\minus{}k} \frac{(\minus{}1)^i}{i!}\equal{}1$, which follows from straight-forward induction -
if $ \sum_{k\equal{}0}^{n}\frac{k}{k!} \sum_{i\equal{}0}^{n\minus{}k} \frac{(\minus{}1)^i}{i!}\equal{}1$, then:
$ \sum_{k\equal{}0}^{n\plus{}1}\frac{k}{k!} \sum_{i\equal{}0}^{n\plus{}1\minus{}k} \frac{(\minus{}1)^i}{i!}\minus{}\sum_{k\equal{}0}^{n}\frac{k}{k!} \sum_{i\equal{}0}^{n\minus{}k} \frac{(\minus{}1)^i}{i!}\equal{}\sum_{k\equal{}0}^{n}\frac{k}{k!} \frac{(\minus{}1)^{n\plus{}1\minus{}k}}{(n\plus{}1\minus{}k)!}\plus{}\frac{1}{n!}\equal{}\sum_{k\equal{}0}^{n} \frac{(\minus{}1)^{n\plus{}1\minus{}k}}{(n\plus{}1\minus{}k)!(k\minus{}1)!}\plus{}\frac{1}{n!}\equal{}\frac{\sum_{k\equal{}0}^{n} \binom{n}{n\plus{}1\minus{}k} (\minus{}1)^{n\plus{}1\minus{}k}  \plus{} 1}{n!} \equal{} (1\minus{}1)^n/n!\equal{}0$

I don't think it was a suitable problem for an IMO. If you happen to know derangements it becomes an exercise.

Clearly, $ p_n(k)\equal{}\binom{n}{k}\cdot d_{n\minus{}k}$, where $ d_n$ is the number of derangements of $ \{1;2;\dots;n\}$. Evaluate $ \frac{p_n(k)}{p_{n\minus{}1}(k\minus{}1)}$ to note that $ p_n(k)\equal{}\dfrac{n}{k}\cdot p_{n\minus{}1}(k\minus{}1)$. Hence,
$ \sum_{k\equal{}0}^{n}{kp_n(k)}\equal{}n\cdot\sum_{k\equal{}1}^{n}{p_{n\minus{}1}(k\minus{}1)}\equal{}n\cdot(n\minus{}1)!$
as the latter sum is the number of permutations of $ \{1;2;\dots;n-1\}$, which proves our claim and avoids the rather messy algebra.

In the interest of completeness, I'll include a rather general technique:  the relevant generating function is

$ \sum_{n, k \ge 0} \frac {p_n(k)}{n!} x^n y^k \equal{} \frac {1}{1 \minus{} x} e^{yx \minus{} x}$

(see the proof [url=http://www.artofproblemsolving.com/Forum/weblog.php?w=634]here[/url]).  This gives the obvious identity $ \sum_{k \equal{} 0}^{n} k p_n(k) \equal{} n!$ when $ y \equal{} 1$.  Differentiating with repsect to $ y$, we obtain

$ \sum_{n, k \ge 0} \frac {kp_n(k)}{n!} x^n y^{k \minus{} 1} \equal{} \frac {x}{1 \minus{} x} e^{yx \minus{} x}$

which, upon the substitution $ y \equal{} 1$, gives $ \sum_{k \equal{} 0}^{n} p_n(k) \equal{} 0$ when $ n \equal{} 0$ and $ n!$ otherwise.  We have the following obvious generalization:

$ \sum_{k \equal{} r}^{n} (k)_r p_n(k) \equal{} n!, n \ge r$

where $ (k)_r \equal{} k(k \minus{} 1)...(k \minus{} (r \minus{} 1)) \equal{} r! {k \choose r}$.  Combined with a well-known identity involving the [url=http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind]Stirling numbers of the second kind[/url], this gives one proof of the result in [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=63678]this related thread[/url] about the sum

$ \sum_{k \equal{} 0}^{n} k^r p_n(k) \equal{} \sum_{\pi \in S_n} \text{Fix}(\pi)^r$.

ZetaX:  was this the problem that inspired your thread?  :)

Another solution:

The following identities are quite obvious:
(1) [code]p_n(k)=\binom{n}{k}\cdot p_{n-k}(0)[/code] with [code]p_0(0):=1[/code]
(2) [code]\sum_{k = 0}^{n} p_n(k) = n![/code]

The rest is a simple index shift j = k-1:
[code]
\sum_{k = 0}^{n} k \cdot p_n(k) = \sum_{k = 1}^{n} k \cdot \binom{n}{k}\cdot p_{n-k}(0) =
n \cdot \sum_{j = 0}^{n-1} \binom{n-1}{j}\cdot p_{n-1-j}(0) = n \cdot \sum_{j = 0}^{n-1} p_{n-1}(j) = n \cdot (n-1)! = n![/code]

Sorry, here the solution one can read:

The following identities are quite obvious:
(1) $ p_n(k)\equal{}\binom{n}{k}\cdot p_{n\minus{}k}(0)$ with $ p_0(0): \equal{}1$
(2) $ \sum_{k \equal{} 0}^{n} p_n(k) \equal{} n!$

The rest is a simple index shift j = k-1:
$ \sum_{k \equal{} 0}^{n} k \cdot p_n(k) \equal{} \sum_{k \equal{} 1}^{n} k \cdot \binom{n}{k}\cdot p_{n\minus{}k}(0) \equal{}
n \cdot \sum_{j \equal{} 0}^{n\minus{}1} \binom{n\minus{}1}{j}\cdot p_{n\minus{}1\minus{}j}(0)$
$ \equal{}n \cdot \sum_{j \equal{} 0}^{n\minus{}1} p_{n\minus{}1}(j) \equal{} n \cdot (n\minus{}1)! \equal{} n!$

My own preferred way to think about e.lopes original solution is as follows:

Dividing both sides by $ n!$, we are being asked to show that the expected number of fixed points in a random permutation $ \sigma$ is $ 1$.  But this is the sum of $ n$ indicator variables $ X_i$ corresponding to each $ i$ being fixed.  By symmetry, the probability that $ \sigma(i)\equal{}i$ (the expectation of $ X_i$) is $ \frac{1}{n}$.  The result follows from linearity of expectation.

Somewhat similar to above...

This is basically a derangement problem! Thus, we use a probabilistic interpretation. We know the probability of a permutation having $k$ fixed points is \[\frac{p_{n}(k)}{n!}\], and so the expected value of fixed points is \[\sum_{k=0}^nk \frac{p_n(k)}{n!}\]. In derangement, we know that the expected value is 1 fixed, and thus \[\sum_{k=0}^nk \frac{p_n(k)}{n!} = 1\] or \[\sum_{k=0}^nk p_n(k) = n!\] as desired $\blacksquare$

Similar to above, let us calculate the expected number of fixed points there are in any permutation.  The element $a$ is a fixed point with probability $\frac{1}{n}$ and there are $n$ elements, making the expected number of fixed points in any permutation to be $n\left(\frac1n\right)=1$.  The total number of permutations is $n!$ therefore the total number of fixed points in all the subsets is $n!$.

We can calculate this another way as well.  $p_n(k)$ is the number of permutations with $k$ fixed points so $kp_n(k)$ is the total number of fixed points in the set of permutations with $k$ fixed points.  Thus the total number of fixed points in all the permutations is $\sum_{k=0}^n kp_n(k)$, but this is also $n!$, as calculated above.  So
\[
\sum_{k=0}^n kp_n(k)=n!,
\]
as desired.

Surely not a new idea, but willl post my soltion as well :)

We count the number of pairs (fixed point, permutation) in two ways. Let there be $X$ such pairs.

Note that each point is fixed point in $(n-1)!$ permutations, just fix one and randomly permute all other elements. Because there are $n$ points, we have that $X=n \cdot (n-1)!=n!$.

On the other hand, from the perspective of permutations: each permutation with $k$ fixed points is counted $k$ times in $X$, once for each fixed point. Since there are $p_n(k)$ permutations with $k$ fixed points, they are together counted $kp_n(k)$ times in $X$. Summing up over all values of $k$ we get $X=\sum_{k=0}^n kp_n(k)$. The desired equality follows.

[b]Probabilistic Method:[/b]
Let $X$ be the number of fixed points in a random permutation. It is well known that $\mathbf{E}[X]=1$. Hence,
$$1=\mathbf{E}[X]=\sum_{k} k\mathbf{P}[X=k]=\sum_{k} k \cdot \frac{p_{n}(k)}{n!} \Leftrightarrow \sum_{k} k p_n(k)=n!$$

[b]Double Counting:[/b]
Consider a $n! \times n$ matrix. Label the rows $P_1, P_2, \cdots P_{n!},$ and the columns $1, 2 \cdots n$. Here, each row corresponds to a permutation of $\{1, 2, \cdots n\}$.
Let $N$ be the total number of fixed points over all these permutations. We count $N$ in two ways.

[b]Rows[/b]: The number of fixed points $k$ appears $P_{n}(k)$ times.
[b]Columns[/b]: Each element is a fixed point in exactly $(n-1)!$ permutations.

Hence,
$$\sum_{k} k p_n(k)=N=n \cdot (n-1)!=n!$$

Consider a permutation $a_1,a_2,...,a_n$ of $1,2,...,n$. We shall put exactly one star over some number in the new permutation such that, the number with the star over it is a fixed point. Over all permutations of $1,2,...,n$, there are $\sum_{k=0}^n kp_n(k)$ ways to put a star over some fixed point of the permutation. On the other hand, if we pick the position of the star first, then there are $n\cdot (n-1)! = n!$ ways to do so, since there are $n$ possible elements to put the star over and $(n-1)!$ ways to permute the rest. Therefore, $$\sum_{k=0}^nk p_n(k)=n!.$$

Let the set of permutations of this set be $\Gamma$. We define $F(\pi)$ for a permutation $\pi$ as the number of fixed points and $F_{\pi}$ as the set of fixed points under $\pi$. We compute that
\[\sum_{k=0}^n kp_n(k) = \sum_{\pi \in \Gamma}F(\pi) = \sum_{\pi \in \Gamma, k \in F_{\pi}} 1.\]
Thus, for each $k$ in the set $\{1,2,3,\cdots , n\}$, this sum counts the number of times it is a fixed point of a permutation. But clearly, each $k$ is the fixed point of a permutation exactly $(n-1)!$ ways, so the sum is
\[\sum_{k=0}^n kp_n(k) = \sum_{k=1}^n (n-1)! = n!,\]
as desired.

A given position has a $\tfrac{1}{n}$ chance of being a fixed point. Hence, the expected number of fixed points of a permutation is $\frac{1}{n} \cdot n=1$. However, the expected number of fixed points can also be calculated as
\[\sum_{k=0}^{n} k \cdot \frac{p_n(k)}{n!}=0\cdot \frac{p_n(0)}{n!}+1\cdot \frac{p_n(1)}{n!}+2\cdot \frac{p_n(2)}{n!}+\dots +n \cdot \frac{p_n(n)}{n},\] since the probability of $k$ fixed points is equal to $\frac{p_n(k)}{n!}.$ We can set the two expected values equal, getting
\[\sum_{k=0}^{n} k \cdot \frac{p_n(k)}{n!}=1\]
\[\sum_{k=0}^nk p_n(k)=n!.\]

divide it by n! and now what we are having on the left hand side is probability that we can find a fixed point in any permutation and now we know that this is true because we can find atleast 0 fixed points in any permutation reason for the left hand side is that the weight of k means that we have k point in the permutations so we get overall fixed points inn the particular permutation and then the other thing is caluclating the probability that the permutaion has k fixed points

[hide=Solution]We will find another way to express the expected number of fixed points for a certain $n,$ which is $$\frac{\sum_{k=0}^n{kp_n(k)}}{n!}.\quad (*)$$

Consider a permutation of the set $\{1,2,...,n\}.$ For each of the $n$ elements, there is a $\tfrac{1}{n}$ probability that it will be in its original position, so the expected number of fixed points is $n\cdot\tfrac{1}{n}=1.$ Setting this equal to $(*)$ yields the desired result.[/hide]

Isn't this well-known? If I recall correctly, a similar problem appeared in the Global Section of the OTIS Excerpts. Anyways, my solution is below.

Notice $\sum_{k = 0}^{n} k \cdot p_n(k)$ counts the total number of fixed points over all $n!$ permutations, as the multiplicity of fixed points per each permutation is accounted for in the sum.

Now, we count the total number of fixed points in another fashion. If $i$ is fixed where $1 \le i \le n$, then there's $(n-1)!$ possible permutations of the other $n-1$ letters, i.e. $(n-1)!$ permutations where $i$ is fixed. Hence, the total number of fixed points is just $$\underbrace{(n-1)! + (n-1)! + \ldots + (n-1)!}_{\text{n times}} = n \cdot (n-1)! = n!$$ as desired. $\blacksquare$

Sample a random permutation of $\{1, 2, \cdots, n\}$ and compute the number of fixed points. The expected value of this quantity is $1$ which is quite easy to show through the linearity of expectation. However this quantity is also just \[\frac{1}{n!} \sum_{k=0}^nk p_n(k).\] This finishes.

The expected number of fixed points of a permutation of $\{1,2,3,\ldots,n\}$ is $\frac{\sum_{k=0}^n kp_n(k)}{n!}$.

Now note that there is $\frac{1}{n}$ probability for any specific element to be in its original position. By the Linearity of Expectation, the expected number of fixed points is $n\cdot \frac{1}{n}=1$.

This proves the desired result.

Let $S$ be the set of all permutations of $1,2,\ldots,n$. We will count the number of ways to choose a pair $(s,i)$ such that $s\in S$ with $k$ fixed points has a fixed point $i$. First, there are $p_n(k)$ ways to choose the permutation $s$ with $k$ fixed points, and then $k$ choices for the fixed point $i$. There are thus
$$\sum_{k=0}^{n}{kp_n(k)}$$
such pairs. We can choose a fix $i$ first, for which we have $n$ choices, and then permute the remaining $n-1$ elements, so $n!$ ways in total. Note that we to not count the permutations with $0$ fixed points here, but in the above sum $kp_n(k)=0$ for $k=0$ anyways. Thus
$$\sum_{k=0}^{n}{kp_n(k)}=n!$$

[hide = Proof] Denote by $X_k =$ the event of $k$ fixed points. Then $\mathbb{E}[X_k] = \mathbb{P}[X_k] \cdot k = \frac{\binom{n}{k} \cdot (n - k)!}{n!} \cdot k$. Summing all of the events yields \[\mathbb{E}[X_0 + X_1 + \cdots + X_n] = \left (\binom{n}{1} \cdot (n - 1)! \cdot 1 + \binom{n}{2} \cdot (n - 2)! \cdot 2 + \cdots + \binom{n}{n} \cdot (n - n)! \cdot n \right). \].
Now the expected number of moves required to pick a permutation with $k$ fixed points is $1$. (We can omit derangements). Thus we have that

\begin{align*}
\mathbb{E}[X_0 + X_1 + \cdots + X_n] &= \left (\binom{n}{1} \cdot (n - 1)! \cdot 1 + \binom{n}{2} \cdot (n - 2)! \cdot 2 + \cdots + \binom{n}{n} \cdot (n - n)! \cdot n \right) = 1 \\
& \implies \frac{1}{n!} \sum_{k = 0}^{n} p_n(k) \cdot k = 1.
\end{align*}
,as desired. $\blacksquare$ [/hide]

The quantity $k.p_n(k)$ represents the number of all fixed point in those permutations which has $k$ fixed point. So their sum is the total number of fixed points. And the number of all fixed point is $n!$ counting by the columns.

[b]Remark: [/b] The case $k=0$ is not that redundant. Though it is obvious, it can give a realization what $k.p_n(k)$ actually mean, in other words there is not fixed point in all the permutations with $0$ fixed point.

The expected number of fixed points of a particular permutation is $n \cdot \frac 1n = 1$, so we have $n! \cdot 1 = n!$ total fixed points across all permutations, which is essentially what the question is asking for. $\blacksquare$


trigonometry
function
calculus
derivative
real analysis
real analysis unsolved

How do i show that $ g(x) \equal{} \sin(x)$ is uniformly continuous on $ \mathbb{R}$?

Either use a trig identity, or write $ \frac{\sin a\minus{}\sin b}{a\minus{}b}\equal{}\cos c$ (by the Mean Value theorem), hence $ |\sin a\minus{}\sin b|\le |a\minus{}b|$. This can be generalized to any function $ f$ with bounded derivative $ f'$.

If I were to write $ \frac{\sin a\minus{}\sin b}{a\minus{}b}\equal{}\cos c$, how would i justify that exactly? would i still start from showing $ |g(x)\minus{}g(a)|$?


floor function
function
algebra proposed
algebra

Prove that for any positive integer  $m$, the equation
\[ \frac{n}{m}\equal{}\lfloor\sqrt[3]{n^2}\rfloor\plus{}\lfloor\sqrt{n}\rfloor\plus{}1\]
has (at least) a positive integer solution $n_{m}$.

[i]Cezar Lupu & Dan Schwarz[/i]

Since $ \frac {n}{m}$ is an integer, the first thing we think of is to let $ n \equal{} mk$.

Then the problem reduces to showing that $ k \equal{} \lfloor\sqrt [3]{m^2k^2}\rfloor \plus{} \lfloor\sqrt {mk}\rfloor \plus{} 1$ has a solution for some integer k.

Now, we consider the function $ f(k) \equal{} k \minus{} \lfloor\sqrt [3]{m^2k^2}\rfloor \minus{} \lfloor\sqrt {mk}\rfloor \minus{} 1$ taking the natural numbers to the integers.

When $ k \equal{} 1$, $ f(k) < 0$. Note that every time we increase k by 1, $ f(k)$ can increase by at most 1. Also note that $ k$ grows faster than $ \lfloor\sqrt [3]{m^2k^2}\rfloor \plus{} \lfloor\sqrt {mk}\rfloor \plus{} 1$, since it is an exponential of greater power than either of the terms in $ \lfloor\sqrt [3]{m^2k^2}\rfloor \plus{} \lfloor\sqrt {mk}\rfloor \plus{} 1$, so there must be an integer m s.t. $ f(m) > 0$.

Lastly, consider the function $ g(k) \equal{} max(f(1),f(2),f(3),...,f(k))$. Then $ g(1) < 0$, $ g(m) \ge f(m) > 0$, and since $ g(x \plus{} 1)$ is always either 0 or 1 greater than $ g(x)$, $ g(x)$ must hit every integer between $ f(1)$ and $ f(m)$ at some integer k between 1 and m.

This implies there exists an $ f(k)$ s.t. $ f(k)\equal{}0$, so we're done.


absolute value
wilkinson catalyst
P2 catalyst
birch reduction

Set $A$ consists of $m$ consecutive integers whose sum is $2m$, and set $B$ consists of $2m$ consecutive integers whose sum is $m$. The absolute value of the difference between the greatest element of $A$ and the greatest element of $B$ is $99$. Find $m$.

[quote="jimhu"]I got different answer... I checked it and seems correct..
[hide]
Telling from the numbers, some of them might be negative. So let $1-k$ be the first number that the consecutive integers start on.
We have sums to be:
$\frac{m^2+m}{2}-mk=2m$ and $\frac{4m^2+2m}{2}-m(k+99)$
Solving gives $\boxed{m=65}$.[/hide][/quote]

By the way, each set starts with a different number :!:

[quote="Ezbakhe Yassin"]I got the same results as [b]amirhtlusa[/b].

$S_A=S_m=\frac{a_1+a_m}{2}\cdot m = \frac{a_1+a_1+m-1}{2}\cdot m = 2m \Rightarrow \boxed{2a_1+m=5}$ [1]

$S_B=S_{2m}=\frac{b_1+b_{2m}}{2}\cdot 2m = \frac{b_1+b_1+2m-1}{2}\cdot 2m = m \Rightarrow \boxed{b_1+m=1}$ [2]

$|a_m-b_{2m}|=99 \Rightarrow |a_1+m-1-(b_1+2m-1)|=99 \Rightarrow \boxed{m+b_1-a_1=99}$ [3]

From [b][1][/b], [b][2][/b] and [b][3][/b], we have that:

$\boxed{a_1=-98; b_1=-200; m=201}$[/quote]]

Hmm.. Strange. If we test my answer, we have 65 consecutive integers starting at -30.
And then 130 consecutive integers starting at -129 .The sums should be:
$\frac{65^2+65}{2}-(65)(31)=130=2m$
$\frac{130^2+130}{2}-(65)(31+99)=130=65=m$[/hide]

Could anyone try to solve it using another method?

i just checked the answer with Kalva, 201 is correct

[quote="JesusFreak197"]It's the difference between the greatest elements that we're looking for, not the least elements. ;)[/quote]

Yes, but difference between least terms is still 99, therefore I used to my advantage...

No, because each sequence has a different number of terms. ;)

[quote=donot]Sorry for the revive, but I wanted to post a cleaner solution.
[hide="Work with the means."]
The mean of Set $A$ is $\frac{2m}{m}=2$, so this is also the median. There are $\frac{m-1}{2}$ elements greater than the median, so the greatest element in this set is $\frac{m+3}{2}$.
The mean of Set $B$ is $\frac{1}{2}$, so the middle two elements are $0$ and $1$. There are $m$ elements after $0$, so $m$ is the greatest element in set $B$. Since $m$ is positive, $m >\frac{m+3}{2}$, and $m-\frac{m+3}{2}=99$. Solving, we get $m=201$.
[/hide][/quote]

pls dont laugh if my doubt is trivial

why m>(m+3)/2 ,it is thou not alwys true??

[hide=@#13][url=aops.com/community/user/174289][b]daniellionyang[/b][/url] · Jul 27, 2016, 7:47 PM [url=aops.com/community/p6725701](view)[/url][color=transparent]helo[/color]
Wait, what is the source of this problem? I think I saw it before on AIME.

-----------
[color=#5b7083][aops]x[/aops] 13[color=transparent]hellloolo[/color] [aops]Y[/aops] 0 [color=transparent]hellloolo[/color] [/hide]
Posting this for contest collections.

Let the first sequence be ${a+1, a+2, \ldots a+m}$ and let the second sequence be ${b+1, b+2 \ldots b+2m}$. Then $2a+m+1=4, 2b+2m+1=1$, so $2a+m=3, 2b+2m=0$. We also have $(b+2m)-(a+m)=99$, so $b+m-a=99$. Solving gives $m=\boxed{201}$.

What I did was set the smallest numbers of set A and B to
$a-m+1$ and $b-2m+1$, respectively.

Then I got the equations

$b-2m=0$
$2a-m=3$
$b-a=99$
Which gives me an answer of $m=67$, but somehow im a third off? Where did I go wrong?


LaTeX
quadratics
algebra unsolved
algebra

Find all real x,y,z that \left\{\begin{array}{c}x+y+zx=\frac12\\ \\ y+z+xy=\frac12\\ \\ z+x+yz=\frac12\end{array}\right.

You mean $ \{\begin{array}{c}x+y+zx=\frac12\\ \\ y+z+xy=\frac12\\ \\ z+x+yz=\frac12\end{array}$.

place your latex codes between dollar signs

We can easily show that all are positive. Subtract the eq in pairs to get: x-z=x(y-z) & y-x=y(z-x). Divide the two eq. & simplify to get: (y/z)+(x/y)+(z/x)=3. Apply A.M. G.M. to get x=y=z. Solve any eq. by the quadratic formula. Sorry for the inconvenience but my latex is not working.

[quote="amitsaha"]We can easily show that all are positive[/quote]
Maybe easily, but wrong : $ (x,y,z)=(-1,2,\frac 12)$ is a solution, for example.

$ \{\begin{array}{c}x + y + zx = \frac12 \\
 \\
y + z + xy = \frac12 \\
 \\
z + x + yz = \frac12\end{array}$

First equation gives $ y=\frac 12-x-xz$

Plugging this in the third equation, we get $ x(1-z-z^2)=\frac{1-3z}2$ and so $ 1-z-z^2\ne 0$ and $ x=\frac{1-3z}{2(1-z-z^2)}$

Plugging these values in the second equation, we get $ 4z^5+2z^4-20z^3-5z^2+11z-2=0$ which may be written $ (z-2)(z+1)(2z-1)(2z^2+4z-1)=0$

And so $ 5$ solutions :
$ (x,y,z)=(-1,2,\frac 12)$

$ (x,y,z)=(\frac 12,-1,2)$

$ (x,y,z)=(2,\frac 12,-1)$

$ (x,y,z)=(-1-\sqrt{\frac 32},-1-\sqrt{\frac 32},$ $ -1-\sqrt{\frac 32})$

$ (x,y,z)=(-1+\sqrt{\frac 32},-1+\sqrt{\frac 32},$ $ -1+\sqrt{\frac 32})$

tnx pco
خیلی توپ بود
It's in persian which is mean very very nice


$ c\in \mathbb{R}$ and $ c \equal{} \frac {\sqrt {a \minus{} 2b} \minus{} 3b}{4a \minus{} \sqrt {2b \minus{} a}}$
$ c \plus{} \frac {a}{b} \equal{} ?$

[hide]use that a square root in this equation must be real[/hide]

[hide]$ a\minus{}2b\geq 0$ and $ 2b\minus{}a \geq 0$, thus $ a\minus{}2b\equal{}2b\minus{}a\equal{}0 \implies a/b\equal{}2$

Then $ c \equal{} \minus{} \frac{3b}{4a} \equal{} \minus{} \frac{3}{8}$

Then $ c\plus{}a/b\equal{}13/8$[/hide]

What if $ a,b$ are not neccessarily reals?  Then how do you know that both $ \sqrt{2b\minus{}a}$ and $ \sqrt{a\minus{}2b}$ must be reals?

If a-2b and b-2a are real numbers, then a,b are real

I don't see why $ a\minus{}2b$ and $ b\minus{}2a$ must be reals.

[quote="cosinator"]I don't see why $ a \minus{} 2b$ and $ b \minus{} 2a$ must be reals.[/quote]
The OP said "use that a square root in this equation must be real ", but it was hidden.  (not sure why...)

[b]Altheman [/b]read it wrong, it was a-2b and 2b-a. And yes, there's no good reason why they should have to be real, except that it's given (check [b]queen's [/b]hidden content).  :wink:

But what [b]Altheman[/b] said, you can say that let x = Im(a) and y=Im(b). And in that case, you know that x-2y = 0 and y-2x=0. Solving the system gives (x,y)=(0,0), so a and b must be real.

Zuton force, I'm not convinced.  You are assuming that the result of the square roots must be real, but in reality just the expression must be real.

Thinking... $ c \in \mathbb{R} \implies arg(\sqrt{a\minus{}2b}\minus{}3b) \equal{} arg(4a\minus{}\sqrt{2b\minus{}a}) \implies \sqrt{a\minus{}2b}\minus{}3b \equal{} k(4a\minus{}\sqrt{2b\minus{}a})$ for some $ k \in \mathbb(R)$.  Hence we have $ 4ak\plus{}3b \equal{} \sqrt{a\minus{}2b}\plus{}k\sqrt{2b\minus{}a}$.

I don't know where to go from there, but thinking about it now, $ k\equal{}c$...

Wait... did the problem specify that the square roots must give reals????

we dont want a complex value here so that is why we say $ c\in R$

I know $ c$ is real, what I'm asking is does that imply that $ \sqrt{2b\minus{}a}$ and $ \sqrt{a\minus{}2b}$ are necessarily also reals, or could imaginary parts end up canceling later?

[hide]Since $ c \in \mathbb{R}$, $ a\minus{}2b \ge 0$ and $ 2b\minus{}a \ge 0 \implies a\minus{}2b \le 0$, which implies that $ \displaystyle a\minus{}2b\equal{}2b\minus{}a\equal{}0 \implies \frac{a}{b}\equal{}2$. Then:
\[ c\plus{}\frac{a}{b}\equal{}\frac{\minus{}3b}{4a}\plus{}\frac{a}{b}\equal{}\minus{}\frac{3}{4} \cdot \frac{b}{a} \plus{}\frac{a}{b}\equal{}\minus{}\frac{3}{8}\plus{}2\equal{}\boxed{\frac{13}{8}}\][/hide]

123456789, I would completely agree if we were given $ a$ and $ b$ are real.  However, isn't it possible for $ c$ to be real if $ a$ and $ b$ are complex?  Couldn't the imaginary parts cancel in the expression?

It says that $ c$ is a real number, so if the denominator has an imaginary term, the numerator won't, and it won't cancel out.

are you assuming that $ a$ and $ b$ are real?  Because your explanation makes it sound like you are.

[quote="facis"]$ 4ak \plus{} 3b \equal{} \sqrt {a \minus{} 2b} \plus{} k\sqrt {2b \minus{} a}$[/quote]

$ 4ak \plus{} 3b \equal{} (1 \plus{} ki)\sqrt {a \minus{} 2b}$
$ (4ak\plus{}3b)^2\equal{}(a\minus{}2b)(1\plus{}ki)^2$

hmmm......

[quote="queen"]how can you cancel complex numbers when only one of the root becomes complex?[/quote]

How do you know only one of the roots is complex?

For real $ a$ and $ b$, it's obvious because $ \sqrt{a\minus{}2b}\equal{}\sqrt{\minus{}(2b\minus{}a)}\equal{}i\sqrt{2b\minus{}a}$. But the problem doesn't say $ a$ and $ b$ have to be real, only that $ c$ is real. For example, if $ \sqrt{a\minus{}2b}\equal{}1\plus{}i$, $ \sqrt{2b\minus{}a}\equal{}i\minus{}1$, and they're both complex.

The question is whether you can find a pair of complex values of $ a$ and $ b$ that will make both the numerator and denominator complex, in such a way that they cancel out and produce a real quotient.


how many of the 26 capital letters are symmetrical with respect to a point?

I might be misunderstanding the question but...

[hide="my "not sure" answer"] 26(26-3) = 598

umm.. try not to trust me.. the wording was hard for me to understand...[/hide]

Hint: The answer is less than 26

I don't believe there is a formula to evaluate this.. you either have to know if off hand, or consider each letter one by one.

[hide]
Uhh,  I get 7, I'm not sure though.[/hide]

[hide]Let's just type the alphabet and see.... ABCDEFGHIJKLMNOPQRSTUVWXYZ

OK. We have A, B, C, D, E, H, I, K, M, O, T, U, V, W, X, and Y.

(That is if there's any place that you can fold the figure with a line of symmetry. otherwise, I don't know.)

If so, then I get 16. [/hide]

I think he means what does symmetric with respect to a point actually mean.  Does it mean its the same if rotated 180 degrees about a point?  If so, then I see I, O, and X.  ah, and H, N, S, and Z?  I'll say 7.

if point djshowdown2's result is right
if line elementsofmathkid's result is right


algebra
binomial theorem
number theory proposed
number theory

I'm assuming $ \mathbb{N}= \{1, 2, \ldots\}$ and $ \mathbb{N}_{0}= \mathbb{N}\cup \{0\}$. In the first place, recall that $ \gcd(2^{a}+1, 2^{b}+1) = 1$, whenever $ a, b \in \mathbb{N}_{0}$ and $ \gcd(a,b) = 1$. Then let $ (n,k) \in \mathbb{N}^{\,2}$ such that
\[ (k^{n}+2^{n}+1) \mid (k^{n+1}+2^{n+1}+1)\quad\qquad (1) \]
So actually, taking $ k = 1$ would entail $ (2^{n-1}+1) \mid (2^{n}+1)$, whereas settling $ k = 2$ would imply $ (2^{n+1}+1) \mid (2^{n+2}+1)$ (absurd in both cases). On the other hand, when fixing $ n = 1$, it's clear that (1) leads to have $ (k+3) \mid (6k+4)$, i.e. $ (k+3) \mid 14$, which is possible iff $ k \in \mathbb{N}$ and $ (k+3) \in \{1, 2, 7, 14\}$, viz iff $ k = 4$ or $ k = 11$. Hence from here on going we can admit $ k \ge 3$ and $ n \ge 2$. Now $ k^{n+1}+2^{n+1}+1 = k\cdot (k^{n}+2^{n}+1)-2^{n}(k-2)-k+1$. Thus from (1)
\[ \frac{2^{n}(k-2)+k-1}{k^{n}+2^{n}+1}\in\mathbb{N}\quad\Longrightarrow\quad k^{n}\le 2^{n}(k-3)+k-2\quad\qquad (2) \]
that is impossible whether $ k \ge 3$ and $ n \ge 2$, since then (through Newton's binomial theorem)
\[ k^{n}\ge (k-1)^{n}+2n (k-1)^{n-1}+2n(n+1) (k-1)^{n-2}> 2^{n}\cdot (k-3)+k-2. \]
Thus there are no other solutions, apart from those we have already detected. :wink:

Great!
So there are only two solutions: $ (k,n)=((4,1),(11,1))$.

:) Indeed, I did a few typos, that I'm just going to fix.


I have found an interesting one by running test on computer program and get:
If $a,b,c$ is nonnegative and $a+b+c=3$ then
$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \geq ab+bc+ca$
  But I don't know how to prove it. Can anyone do it?

If I am right that it is a weak one :lol:
in fact we can prove
$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \geq 3$
Wlog $a \ge b \ge c$
we have
$3-bc \ge 3-ac \ge 3-ba$
$\frac 1{a+1} \ge \frac 1{b+1} \ge \frac 1{c+1}$
so we get:$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \ge \frac 1 3(9-ab-bc-ca)(\frac 1{a+1}+\frac 1{b+1} +\frac 1{c+1})$
it is easy to prove $9-ab-bc-ca \ge 6$
and $\frac 1{a+1}+\frac 1{b+1} +\frac 1{c+1} \ge \frac 3 2$(caughy)
 :)

[quote="zhaobin"]If I am right that it is a weak one :lol:
in fact we can prove
$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \geq 3$
Wlog $a \ge b \ge c$
we have
$\frac 1{a+1} \ge \frac 1{b+1} \ge \frac 1{c+1}$

 :)[/quote]

Yes, you use Trebusep but if $a>b>c$ then $\frac 1{a+1} \ge \frac 1{b+1} \ge \frac 1{c+1}$ is wrong ! Right? :D Then you prove the weaker inequality :D

ok,Here goes my solution again(for your orginal one),hope it is right.
but unfortunatly it is ugly.
let $x=a^2+b^2+c^2,y=ab+bc+ca$
and notice $f(t)=\frac 1 {1+t}$ is convex $t>0$
so we have
$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \geq (9-y) \frac 1 {1+\frac{9-3abc}{9-y}}$
so we need to prove:
$(9-y)^2 \ge y(9-y+9-3abc)$
because $-3abc \le a^2+b^2+c^2-2ab-2bc-2ca=x-2y$(schur and a+b+c=3)
and $9-y=x+y$
we need to prove
$(x+y)^2 \ge y(x+y+x+2y+x-2y)$
equal to
$(x+y)^2 \ge y(3x+y)$
$(x+2y)x \ge 3xy$
$3 \ge y$
and it is proved :)

Strange. I couldn't  belived that it can be prove by AM-GM. Indeed, I have to use Schur one times and expand... for very long time.
   I will check your sols again. But I hope you edit your sols first because it is difficult to read. Anyway, thank you for your effort! :lol:

[quote="Gibbenergy"][quote="zhaobin"]ok,Here goes my solution again(for your orginal one),hope it is right.
but unfortunatly it is ugly.
let $x=a^2+b^2+c^2,y=ab+bc+ca$
and notice $f(t)=\frac 1 {1+t}$ is convex $t>0$
so we have
$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \geq (9-y) \frac 1 {1+\frac{9-3abc}{9-y}}$
[/quote]
Ok! I have checked your sols. already. I can prove the rest of yours but I don't understand how can you use Jense here. Can u solve me where is your "t" in your sols and how can u obtain that form. Thank u![/quote]
ok,because $f(t)=\frac 1 {1+t}$ is convex $t>0$
we have
$\frac{3-bc}{9-y} f(a)+ \frac{3-ca}{9-y} f(b)+ \frac{3-ab}{9-y} f(c) \ge f(\frac{a(3-bc)}{9-y}+\frac{b(3-ca)}{9-y}+\frac{c(3-ab)}{9-y})$
this is because $\frac{3-bc}{9-y}+ \frac{3-ca}{9-y}+\frac{3-ab}{9-y}=1$
thus we get:
$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \geq (9-y) \frac 1 {1+\frac{9-3abc}{9-y}}$
Hope it is clear now.
thanks if you like my solution :P

[quote="zhaobin"]
ok,because $f(t)=\frac 1 {1+t}$ is convex $t>0$
we have
$\frac{3-bc}{9-y} f(a)+ \frac{3-ca}{9-y} f(b)+ \frac{3-ab}{9-y} f(c) \ge f(\frac{a(3-bc)}{9-y}+\frac{b(3-ca)}{9-y}+\frac{c(3-ab)}{9-y})$
this is because $\frac{3-bc}{9-y}+ \frac{3-ca}{9-y}+\frac{3-ab}{9-y}=1$
thus we get:
$\frac{3-bc}{a+1}+\frac{3-ac}{b+1}+\frac{3-ba}{c+1} \geq (9-y) \frac 1 {1+\frac{9-3abc}{9-y}}$
Hope it is clear now.
thanks if you like my solution :P[/quote]
Ok. It is look very neat and logic. I think you are successful now. And you are amazing. Your sols is better than mine a lots. Anyway, congragulation!

I have just found a different solution to this beautiful inequality.

[color=blue][b]Problem.[/b] Let a, b, c be three positive reals satisfying a + b + c = 3. Prove that

$\frac{3-bc}{a+1}+\frac{3-ca}{b+1}+\frac{3-ab}{c+1}\geq bc+ca+ab$.[/color]

[i]Solution.[/i] Using the notation $\sum$ for cyclic sums, this inequality rewrites as $\sum\frac{3-bc}{a+1}\geq bc+ca+ab$. Now, we will homogenize this inequality by noting that

$\frac{3-bc}{a+1}=\frac{3^2-3bc}{3a+3}=\frac{\left(a+b+c\right)^2-3bc}{3a+\left(a+b+c\right)}=\frac{a^2+b^2+c^2+2ca+2ab-bc}{4a+b+c}$

and $bc+ca+ab=3\frac{bc+ca+ab}{3}=3\frac{bc+ca+ab}{a+b+c}$, so the inequality in question takes the homogeneous form

$\sum\frac{a^2+b^2+c^2+2ca+2ab-bc}{4a+b+c}\geq 3\frac{bc+ca+ab}{a+b+c}$.

Now, since $b^2+c^2\geq 2bc$, we have

$a^2+b^2+c^2+2ca+2ab-bc\geq a^2+2bc+2ca+2ab-bc=a^2+2ca+2ab+bc$
$=a\left(a+b+c\right)+\left(bc+ca+ab\right)$,

so that it remains to prove the (stronger) inequality

$\sum\frac{a\left(a+b+c\right)+\left(bc+ca+ab\right)}{4a+b+c}\geq 3\frac{bc+ca+ab}{a+b+c}$.

This rewrites as

$\sum\frac{a\left(a+b+c\right)}{4a+b+c}+\sum\frac{bc+ca+ab}{4a+b+c}\geq 3\frac{bc+ca+ab}{a+b+c}$
$\Longleftrightarrow\ \ \ \ \ \left(a+b+c\right)\sum\frac{a}{4a+b+c}+\left(bc+ca+ab\right)\sum\frac{1}{4a+b+c}$
$\geq \left(bc+ca+ab\right)\cdot\frac{3}{a+b+c}$
$\Longleftrightarrow\ \ \ \ \ \left(a+b+c\right)\sum\frac{a}{4a+b+c}\geq\left(bc+ca+ab\right)\left(\frac{3}{a+b+c}-\sum\frac{1}{4a+b+c}\right)$
$\Longleftrightarrow\ \ \ \ \ \left(a+b+c\right)\sum\frac{a}{4a+b+c}\geq\left(bc+ca+ab\right)\sum\left(\frac{1}{a+b+c}-\frac{1}{4a+b+c}\right)$
$\Longleftrightarrow\ \ \ \ \ \left(a+b+c\right)\sum\frac{a}{4a+b+c}\geq\left(bc+ca+ab\right)\sum\frac{3a}{\left(a+b+c\right)\left(4a+b+c\right)}$
$\Longleftrightarrow\ \ \ \ \ \left(a+b+c\right)\sum\frac{a}{4a+b+c}\geq\frac{3\left(bc+ca+ab\right)}{a+b+c}\sum\frac{a}{4a+b+c}$
$\Longleftrightarrow\ \ \ \ \ a+b+c\geq\frac{3\left(bc+ca+ab\right)}{a+b+c}\ \ \ \ \ \Longleftrightarrow\ \ \ \ \ \left(a+b+c\right)^2\geq 3\left(bc+ca+ab\right)$.

But this inequality is obvious from

$\left(a+b+c\right)^2-3\left(bc+ca+ab\right)=\frac12\left(\left(b-c\right)^2+\left(c-a\right)^2+\left(a-b\right)^2\right)\geq 0$.

Thus, the problem is solved.

  Darij


P(X) is a monic polynomial of degree 4 with integer co-efficients and constant term 4. One zero is $ \sqrt2$, another zero is rational and the sum of the zeroes is positive. Factorise P(x) fully over $ R$.

Two of the roots of $ 2x^{4}\minus{}5x^{3}\plus{}cx^{2}\plus{}dx\minus{}18\equal{}0$ are reciprocals, while the remaining roots are opposites of each other. Find the four roots of the equation and evaluate c and d

[hide="my soln. for qn 2 but don't understand a certain step"]
Let the roots be $ \alpha.\frac{1}{\alpha},\beta,\minus{}\beta$
product of the roots , simplifying etc,
$ a\equal{}\frac{1}{2},2$ and $ \b\equal{}\pm3.$ I can write this in factored form i.e. $ (2x\minus{}1)(x\minus{}2)...$ expand and equate similar degree but the book has another way

using sum and product 2 at a time, $ 1\minus{}\beta^{2}\equal{}\minus{}8\equal{}\Rightarrow c\equal{}\minus{}16$
and sum of product 3 at a time,=$ \frac{\minus{}45}{2}\equal{}\equal{}\Rightarrow  d\equal{}\minus{}45$

Why are the multiplying by 2[/hide]

[hide="hint for #1"]if the polynomial has integer coefficients and one of its roots is rational we can conclude that $ \minus{}\sqrt{2}$ is a root. Giving us the factorized form of $ (x\minus{}\sqrt{2})(x\plus{}\sqrt{2})(x^{2}\plus{}cx\minus{}2)$ [/hide]

but $ \minus{}\sqrt2$ is not rational :S

did you take $ \minus{}\sqrt2$ as a zero because the qn says integer coeffecients are rational?

thanks for the hint appreciate it

any takers on number 2?

I'm not sure I understand where you have trouble with on #2... is it just this last part?

[quote="bos1234"]
and sum of product 3 at a time,=$ \frac{\minus{}45}{2}\equal{} \equal{}\Rightarrow d \equal{}\minus{}45$

Why are the multiplying by 2[/quote]

Well they multiplied it by 2 because the polynomial isnt monic -- the first coefficient is a $ 2$. So by vieta's, $ \frac{\minus{}d}{2}\equal{}\frac{\minus{}45}{2}$, so $ d\equal{}45$, supposedly. Im not sure why the book has it negative, though (unless I did something wrong?)

[quote="t0rajir0u"][quote="bos1234"]but $ \minus{}\sqrt2$ is not rational :S

did you take $ \minus{}\sqrt2$ as a zero because the qn says integer coeffecients are rational? [/quote]

Yes.  This is the [b]conjugate root theorem[/b] (for algebraic roots over rational coefficients).  Specifically, given rationals $ a, b, c$ such that $ a\plus{}b\sqrt{c}$ is a root, $ a\minus{}b\sqrt{c}$ is also a root.  I give a proof of this in my blog.[/quote]

@bos1234

The 2001 HSC Extension 2 paper has a question based on the Conjugate-Root Theorem (for algebraic roots over rational coefficients).


calculus
integration
combinatorics unsolved
combinatorics

[quote="keira_khtn"]Given a positive integer $ n$, calculate: $ \sum_{k \equal{} 1}^n\left( \minus{} 1\right)^k\left(n \plus{} k\right)!\left(n \minus{} k\right)!$.[/quote]
Denote $ S_n: \equal{} \sum\limits_{k \equal{} 1}^n( \minus{} 1)^k(n \plus{} k)!(n \minus{} k)!\;$ and
\[ \begin{array}{|c|} \hline L_n: \equal{} (n!)^2 \plus{} S_n \equal{} \sum\limits_{k \equal{} 0}^n( \minus{} 1)^k(n \plus{} k)!(n \minus{} k)! \; \; \; ,\; \; \; \; R_n: \equal{} \frac {1}{2}\left((n!)^2 \plus{} ( \minus{} 1)^n\frac {(2n \plus{} 1)!}{n \plus{} 1}\right) \\
\hline\end{array}\; .
\]
[color=red][b] Prove [/b][/color]  $ \begin{array}{|c|}\hline L_n \equal{} R_n \\
\hline \end{array}\; .$
However   $ L_0 \equal{} R_0 \equal{} 1\; ,\; L_1 \equal{} R_1 \equal{} \minus{} 1 \; ,\; L_2 \equal{} R_2 \equal{} 22\; ,... .$ Find a recurrence  satisfied  by  both sequences $ (L_n) \; , \; (R_n)\; .$
Or, use WZ-method (Wilf-Zeilberger $ \approx$ (1990)  , in fact  [b]Markoff -method  $ \approx$ (1890) [/b] .
Using Integral Calculus it's possible to find [b]a proof[/b] in following way:  Denote by $ \Gamma$ the Gamma , and by $ B(\cdot ,\cdot )$ the Beta  functions. We give
\[ \begin{array}{c} (n \minus{} k)!(n \plus{} k)! \equal{} \Gamma(n \minus{} k \plus{} 1)\Gamma(n \plus{} k \plus{} 1) \equal{} B(n \minus{} k \plus{} 1,n \plus{} k \plus{} 1)(2n \plus{} 1)! \equal{} \\
\equal{} (2n \plus{} 1)! \int\limits_{0}^{1}t^{n \minus{} k}(1 \minus{} t)^{n \plus{} k}\; dt \equal{} ( \minus{} 1)^k (2n \plus{} 1)! \int\limits_{0}^{1}t^n(1 \minus{} t)^n\left(\frac {t \minus{} 1}{t}\right)^k \; dt\; . \end{array}
\]
Therefore , using  equality $ B(p,q) \equal{} \int\limits_{0}^{1}t^{p \minus{} 1}(1 \minus{} t)^{q \minus{} 1}\; dt\; ,\; ( p > 0,q > 0),$ one finds
\[ \begin{array}{c} S_n: \equal{} \sum\limits_{k \equal{} 1}^{n}( \minus{} 1)^k(n \minus{} k)!(n \plus{} k)! \equal{} \sum\limits_{k \equal{} 0}^{n}( \minus{} 1)^k(n \minus{} k)!(n \plus{} k)! \minus{} (n!)^2 \equal{} \\
\equal{} (2n \plus{} 1)!\int\limits_{0}^{1}t^n(1 \minus{} t)^n \sum\limits_{k \equal{} 0}^{n}\left(\frac {t \minus{} 1}{t}\right)^k \; dt \minus{} (n!)^2 \equal{} \\
\equal{} (2n \plus{} 1)! \int\limits_{0}^{1}(1 \minus{} t)^n \left( t^{n \plus{} 1} \plus{} ( \minus{} 1)^n (1 \minus{} t)^{n \plus{} 1}\right)\; dt \minus{} (n!)^2 \equal{} \\
\equal{} \displaystyle \frac { n!(n \plus{} 1)! \plus{} ( \minus{} 1)^n(2n \plus{} 1)! }{2n \plus{} 2} \minus{} (n!)^2 \equal{} \displaystyle \frac { ( \minus{} 1)^n(2n \plus{} 1)! \minus{} n!(n \plus{} 1)!}{2n \plus{} 2}\; , \end{array}
\]
which completes  the solution.


A bucket is put under two faucets. If one faucet is turned on alone, the bucket will be filled in 3 minutes; if the other is turned on, the bucket will be filled in 2 minutes. If both are turned on, how many seconds will it take to fill the bucket?

[quote="steve123456"][hide="Click here to reveal hidden content"]

One faucet can fill the 1/3 of the bucket, and the other fills 1/2 of the bucket in a minute. Both on can fill 5/6 of the bucket in a minute, so 6/5 minutes can fill the bucket. That is [b]1 minute, 12 seconds.[/b][/hide][/quote]

Just a clarification - the question asked for how many seconds, so the answer is actually 72 seconds. Again, though a minor point, it can cost a full question on competitions like Mathcounts, where they're looking for answers in a specific form. :)


function
linear algebra
matrix
vector
linear algebra unsolved

Let $x_{i}$ and $x'_{i}$ in $\mathbb{R}^{n}$ for $i=1,...,k\leq n$ have $\parallel x_{i}-x_{j}\parallel \geq \parallel x'_{i}-x'_{j}\parallel$ then exists a continous family of k-tuples $x_{i}^{t}$,such that $x_{i}^{0}=x_{i}$ and $x_{i}^{1}=x'_{i}$ and $\parallel x_{i}^{t}-x_{j}^{t}\parallel$ is decreasing in $t$.

I don't understand your problem. Does $x_{n}^{t}$ mean $(x_{n})^{t}$ ?

I'd write those as $x_{i}(t)$ myself: we want a continuous function $x(t)=\begin{bmatrix}x_{1}(t)\\ x_{2}(t)\\ \vdots\\ x_{n}(t)\end{bmatrix}$ such that $x(0)=x$ and $x(1)=x'$, with the additional property that $\|x_{i}(t)-x_{j}(t)\|$ is a decreasing function for each $i,j$.

At least, that's what I think the problem is- the notation is very confusing. $x,x',x(t)$ are vectors of vectors.


1. Which is larger: [tex]\sqrt{n+1}^\sqrt{n}
[/tex] or [tex]\sqrt{n}^\sqrt{n+1}[/tex] for n>8

I think you ought to try to prove it with calculus. Showing that it works for n=9 doesn't prove it works for n=10 or indeed any other value.

Calc stands for calculus, not calculator....  That did seems suspiciously easy.  I'm going to leave now.  My apologies.

[quote="zabelman"][tex]\displaystyle \sqrt{n+1}^{\sqrt{n}}\quad ?\quad\sqrt{n}^{\sqrt{n+1}}[/tex]

[tex]\displaystyle \sqrt{n} \ln \sqrt{n+1}\quad? \quad\sqrt{n+1} \ln \sqrt{n}[/tex]

[tex]\displaystyle \frac{\ln \sqrt{n+1}}{\sqrt{n+1}} \quad?\quad \frac{\ln \sqrt{n}}{\sqrt{n}}[/tex]

[tex]\displaystyle f(a)=\frac{\ln a}{a}[/tex]

[tex]\displaystyle f'(a)=\frac{1-\ln a}{a^2}[/tex]

[tex]f'(a)[/tex] is negative, i.e. [tex]f(a)[/tex] is decreasing, when [tex]a>e[/tex]. Since [tex]n \ge 8[/tex], [tex]\sqrt{n} > e[/tex], so [tex]f(a)[/tex] is decreasing, so ? is [tex]\le[/tex].[/quote]

I think you left more to be desired with this... You have shown that they are BOTH decreasing, but that doesn't mean that one is greater or equal to the other... and at what rate are both of them decreasing, does one decrease faster/more slowly than the other?

An also, you made the substitution [tex]\displaystyle{a = \sqrt{n}}[/tex] and [tex]\displaystyle{a = \sqrt{n+1}}[/tex], which is fine, but you must also remember to apply [tex]\displaystyle{\; da}[/tex] at each differentiation, because it will change your result...

I was saying that since f(a) is decreasing, [tex]\sqrt{n}<\sqrt{n+1}[/tex] implies [tex]f(\sqrt{n})>f(\sqrt{n+1})[/tex], which is the basic meaning of "decreasing."

And, correct me if I'm wrong, f'(a) means the derivative of f(a) with respect to a.  You would be multiplying by da/da which is 1.

zableman, you are correct, i'm sorry. I misunderstood what you wrote.

juggle, no....

he made a substitution g(n) = n + 1

so the derivative of f(g(x)) must use the chain rule. It is the same for f(a) where a represents an equation.

Yeah, I guess f'(a) does not necessarily mean the derivative of f(a) with respect to a.  Still, let's assume we are differentiating with respect to a nonetheless.

I think we agree up to the last sentence.  You are saying because we are using n, we need to differentiate with respect to n.  But, I think zabelman used f(a) for an explanatory cause so we can look at the original piece with more insight.  He said if a>e, then f(a) is decreasing.  If a = sqrt(n),   then a is in fact always greater than e.

In other words, zabelman showed that the function ln(a)/a is strictly decreasing for a>e.  Which means that when we start plugging in sufficiently large values for a, the function begins to decrease.  In our case, we start plugging numbers at sqrt(8) and then escalate to no bound.  Since it is always greater than e, it is always decreasing.

Sorry about the sqrt(x) thing - I get confused easily and avoid complications.


On a dice we have the following numbers written: 0,1,2,3,4,5. We throw this dice until the sum of the points that appered is bigger than 12.  Which sum has the highest probability that we can obtain  from all the other's?
a)13
b)14
c)15 or
d)16.

10x

Not sure to understand exactly the terms of the problem. A try nevertheless :

Let's denote E(n,p) the event : we have 'n' so far and we dice a 'p'
Let's denote E(n) the event : we have n

Then :

 E(13) = E(12,1) U E(11,2) U E(10,3) U E(9,4) U E(8,5)
 E(14) = E(12,2) U E(11,3) U E(10,4) U E(9,5)
 E(15) = E(12,3) U E(11,4) U E(10,5)
 E(16) = E(12,4) U E(11,5)
 E(17) = E(12,5)

Now all the E(p,i) i=0..5 are equiprobable so 13 is the more probable


modular arithmetic
number theory solved
number theory

a) Choose any positive integer $x$ and $y=(n+x)!+x.$

b) For each positive integer $j$, the number $\dfrac{y+j} {x+j}$ is a positive integer. Since the limit is $1$ when $j$ goes to $+ \infty$, it follows that there exists $n$ such that $1 \leq \dfrac{y+n} {x+n} < 2.$ Therefore $\dfrac{y+n} {x+n} =1$ and $x=y.$

Pierre.

Could you explain a bit more on your b solution?

[quote="ZetaX"]Hmm, what's not clear¿

He shows that the quotient $q_{n}= \frac{y+n}{x+n}$ gets smaller than $2$ at some point, and $q_{n}$ clearly is always a positive integer (by assumption), thus for big $n$, $q_{n}$ will be $1$.[/quote]
Thank you, I couldn't make all of those connections at once...

a)
$x+j|y+j$ <=> $x+j|y-x$ for $j=1,2,3,..,n$
we can take $y-x=\prod_{j=1}^{n}(x+j)$
$y=\prod_{j=1}^{n}(x+j)+x=(x+n)!+x$

b)
for all positive integers $j$, $x+j|y+j$
<=> for all positive integers $j$, $x+j|y-x$
$j=-x+xa$ => $xa|y-x$ => $a|y-x$ for all positive integers $a$
=> $y-x=0$
=> $x=y$

[quote=mynamearzo]I have a different solution for the $2^{nd}$ part.
 We know that there are infinitely many primes.
 We have here that , \[\ x+j\equiv0\pmod{y+j}
  \  \forall \ j\in \mathbb{N} ............ [1] \]

 Now we can say , \[ \exists m \in \mathbb{N} \] such that x+m is a prime.
 so,   y+m=1   or   y+m=x+m       ..... from [1]
  But  \[ \ y+m \neq 1   \] as y and m are +ve integers.
  So, y+m  =  x+m.
 \[ \Longrightarrow x=y.... \]
\[ QED. \][/quote]

Man, I didn't get your solution at all! On what basis you made a case that $y+m=1$?

[quote=Rushil]a) Given any positive integer $n$, show that there exist distint positive integers $x$ and $y$ such that $x + j$ divides $y + j$ for $j = 1 , 2, 3, \ldots, n$;

b) If for some positive integers $x$ and $y$, $x+j$ divides $y+j$ for all positive integers $j$, prove that $x = y$.[/quote]

It has been some time since I bumped this thread.
[hide=Solution for Part b]
For the divisibility, obviously $x \le y$
$x+j \mid y-x+x+j \implies x+j \mid x-y$.
Now pick some $j$ such that $|x-y| \le x+j$. This forces $x-y=0$ and we are done! $\blacksquare$
[/hide]


geometry
circumcircle
trigonometry
perpendicular bisector
geometry unsolved

D is a point on the minor arc AC of the circumcircle of triangle ABC with center O. Take point P on [AB] such that angleADP=angleOBC and take a point Q on [BC] such that angleCDQ=angleOBA . Prove that angleDPQ=angleDOC.

Sorry, i forgot to say that ABC is an acute angled triangle

A sketch:

Show first that if $A',C'$ are the intersections between the altitudes from $A,C$ of $ABC$ respectively and the circle $(O)$, then $DP,DQ$ pass through $C',A'$ respectively. Then show that $PQ$ always passes through $H$, the orthocenter of $ABC$.

What we have to show is that $\angle DPH=\angle DOC$. Since $AB$ is the perpendicular bisector of $HC'$, we have $\angle PDH=2\angle DC'C=\angle DOC$, Q.E.D.

Nice problem.
Let $E=PD\cap{AO}, F=QD\cap{CO}$. Simple angle chasing shows that  $OEDF$ is cyclic, thus $\angle{DOC}=\angle{DEF}$, so we have to prove that $\angle{DEF}=\angle{DPQ}$ or that $PQ$ and $EF$ are parallel or that $\frac{QF}{QD}=\frac{PE}{PD}$. From triangles $APE$ and $APD$ we obtain: $\frac{PE}{PD}=\frac{AE\sin{OAB}}{AD\sin{BAD}}=\frac{\sin{OCB}\cdot{\sin{OAB}}}{\sin{DEO}\cdot{\sin{BAD}}}$ . Similarly we obtain : $\frac{QF}{QD}=\frac{\sin{OCB}\cdot{\sin{OAB}}}{\sin{DFO}\cdot{\sin{BCD}}}$. But $DEOF$ and $ABCD$ are cyclic, so $\sin{BAD}=\sin{BCD}$ and $\sin{DEO}=\sin{DFO}\Rightarrow{\frac{QF}{QD}=\frac{PE}{PD}}$. QED


Can someone please help me! I've accidentally deleted the wrong passage and then asked it to view on pdf form. I then thought that everything was ok, since the number of pages seemed correct and closed Texnic center, but that isn't so! Is there any way which I can get what I deleted back? Please tell me this is so? I can't believe what I've done! (I've deleted quite a bit you see and need it for tomorrow!)

Help! :(  :(

If Undo (Ctrl-Z) doesn't work, then there's no way you can get that back unless you had a backup of the file ...

I can't do ctrl-z since I closed the program and then have now started it again to realise what I've done! Doens't it save a log of everything we do? :(

(sorry, I'm pretty freaked out!)  :(

No, if you don't have a backup you're pretty much screwed.  :|

Crap! Thanks anyway. I guess I better get started again. :o

Serves me right anyway, I should have been more careful. :(

[quote="beans"]For anyone interested, I have managed to rescue myself. (I had saved the document as a pdf file earlier, and so am just going to print the deleted pages from there!) Phew. lesson of the day- before editing save a txt file of the tex![/quote]TeXnic center automatically makes backups of your file once every 10 minutes (by default, you can lower that down from the options page to 1 minute I think).

Where does it save these backup files to?

They just overwrite previous saves (this is a good reason to save as soon as you open the document, and to save under a new name [b][i]before[/b][/i] making any changes that you don't want saved in the old file.


induction
logarithms
number theory unsolved
number theory

let n is a natural number
Prove that
2>1/n+1  +...+ 1/3n+1

[hide="Solution"]$ \frac {1}{n\plus{}2} < \frac {1}{n\plus{}1}$
$ \frac {1}{n\plus{}3} < \frac {1}{n\plus{}1}$
...
$ \frac {1}{3n\plus{}1} < \frac {1}{n\plus{}1}$=>

$ \frac {1}{n\plus{}1} \plus{}\frac {1}{n\plus{}2} \plus{} ... \plus{}\frac {1}{3n\plus{}1}$ < $ (2n\plus{}1)(\frac {1}{n\plus{}1})$ < $ 2$

The end!

This can be proven by mathematical induction also.[/hide]

We can make the rather stronger claim that the upper bound is $ \ln 3 \approx 1.0986$, which is quite a bit tighter.


Let :
\[ a \geq b \geq c \geq 1 \]
\[ x \geq y \geq z \geq 1 \]
Prove that :
\[ a^x + b^y + c^z \geq 3(\frac{a+b+c}{3})^\frac{x+y+z}{3} \]

By applying Power-Mean on the RHS, we see that it's sufficient to prove
\[
a^x + b^y + c^z \geq a^{\frac{x+y+z}{3}} + b^{\frac{x+y+z}{3}} + c^{\frac{x+y+z}{3}}
\]
That should be obvious. Or you can just apply a simple smoothing argument on the exponents.

\[ a^x + b^y + c^z \geq a^\frac{x+y+z}{3} + b^\frac{x+y+z}{3} + c^\frac{x+y+z}{3} \]
  You mean this equality is obvious . Please show me this .

Okay

[b]Lemma:[/b] Suppose that $a\geq b \geq 1$ and $p \geq q \geq x \geq 0$, then $a^{p+x} + b^{q-x} \geq a^p + b^q$.

[b]Proof:[/b] We have \[  a^{p+x} + b^{q-x} \geq a^p \cdot b^x + b^{q-x} \cdot 1 \geq a^p + b^q \] (we used the Rearrangement Inequality). $\square$

So we can just apply a smoothing argument on the LHS to make the exponents equal while not increasing its value. (I'm trying to think of a better way to this)

More generally, I think that if $a_1 \geq a_2 \geq \cdots \geq a_n \geq 1$ and the sequence $x_1 \geq x_2 \geq \cdots \geq x_n \geq 0$ majorizes the sequence $y_1 \geq y_2 \geq \cdots \geq y_n \geq 0$, then
\[
a_1^{x_1} + \cdots + a_n^{x_n} \geq a_1^{y_1} + \cdots + a_n^{y_n}
\]

Here is a different route to prove this which resembles the proof of Chebycheff.

[b]Claim:[/b]: $\displaystyle a^x+b^y+c^z \geq \frac{a^x+a^y+a^z}{3} + \frac{b^x+b^y+b^z}{3} + \frac{c^x+c^y+c^z}{3}$ (which makes a nice problem itself  :)  :) )

[b]Lemma[/b]: If $x\geq y > 0$ and $u\geq v \geq 1$, then $u^x-u^y \geq v^x-v^y$.

[b]Proof:[/b] $u^x-u^y  = u^y(u^{x-y} - 1) \geq v^y(v^{x-y} - 1)  = v^x-v^y$.

By the Lemma, we have:

(1) $a^x+b^y+c^z\geq a^y+b^z+c^x$ since $(a^x-a^y) + (b^y-b^z) \geq (c^x-c^y) + (c^y-c^z) = c^x-c^z$.

(2) $a^x+b^y+c^z\geq a^z+b^x+c^y$ since $a^x-a^z  = (a^x-a^y)+ (a^y-a^z) \geq (b^x-b^y) + (c^y-c^z) $.

(3) $a^x+b^y+c^z\geq a^x+b^y+c^z$ is obviously true.

So the claim is true by adding (1), (2) and (3).

From the claim, we could go either AM-GM first then Power Mean or the reverse.

AM-GM first leads to billzhao's claim above.

By AM-GM, $\displaystyle \frac{a^x+a^y+a^z}{3} + \frac{b^x+b^y+b^z}{3} + \frac{c^x+c^y+c^z}{3} \geq a^{\frac{x+y+z}{3}} + b^{\frac{x+y+z}{3}} + c^{\frac{x+y+z}{3}}$.

Power Mean first,

$\displaystyle  \frac{a^x+b^x+c^x}{3} + \frac{a^y+b^y+c^y}{3} + \frac{a^z+b^z+c^z}{3} $
$\displaystyle \geq \left(\frac{a+b+c}{3}\right)^x + \left(\frac{a+b+c}{3}\right)^y + \left(\frac{a+b+c}{3}\right)^z$ then apply AM-GM to get the desired result.

$Claim$:Let $a_{n}$ and $b_{n}$ are two decreasing sequences such that:$a_{i} >=1$ and $b_{i}>=1$ for all 1<=i<=n.
Then we have:$\sum a_{i}^{b_{i}}$>=$\sum a_{i}^{\sum b_{i}/n}$.
$Proof:$
Well,I have another solution based on this lemma (Prove by Abel's identity)
$Lemma$:If $x_1,...,x_{n}$ and $y_1,...,y_{n}$ are two positive sequences satisfied:
For all 1<=j<=n:
$\prod x_{i}$>=$\prod y_{i}$ with i=1 to j.
$y_1>=y_2>=...>=y_{n}$.Then:
$x_1+...+x_{n}$>=$y_1+...+y_{n}$

Then we apply this lemma :$x_{i}=a_{i}^{b_{i}}$ and $y_{i}=a_{i}^{(\sum b_{i})/n}$ (the condition of x_{i} and y_{i} to the lemma can be easily to prove).Then we have this claim. :)


Dear everyone.

For four points A,B,C,D
Nine-point-circles of triangles ABC,BCD,CDA,DAB are concurrent.

May I ask you a favor? thanks.


calculus
integration
algebra
function
domain
Ring Theory
superior algebra

Hello together,

Im searching for an integral domain $ R$ with this property:

There are $ a,p \in R\setminus \{0\}$ with $ p$ prim and $ a$ arbitrarily, so that $ \max\{n\in \mathbb{N}| p^n \text{ devides } a\}$ does not exist, in other words, such that $ p$ is an infinity divisor of $ a$.

Or, if there is none, how to proof? The only condition to $ R$ is to be an integral domain, if $ R$ is not integral dom, you can clearly find examples.

Thank you.
Natroc

Consider the ring $ R \equal{} K[x, \frac {z}{x}, \frac {z}{x^2}, ... , \frac {z}{x^n}, ...] \subset K(x,z)$. It surely is an integral domain as it is a subset of a field. Also, $ x$ is prime ($ x$ divides some element iff it divides the $ z$-free part, so primality of $ x$ is reduced to primalityof $ x$ in $ K[x]$).
But now $ x^n|z$ for all $ n$ (by definition of $ R$).

What is meant by $ K(x,z)$? The quotient field of $ K[x,z]$? And do you mean $ R: \equal{} K[x,\frac {z}{x},\frac {z}{x^2},...,\frac {z}{x^n},...]$ ?

[quote="Natroc"]What is meant by $ K(x,z)$? The quotient field of $ K[x,z]$?[/quote]
Yes.

[quote="Natroc"]And do you mean $ R: \equal{} K[x,\frac {z}{x},\frac {z}{x^2},...,\frac {z}{x^n},...]$ ?[/quote]
Umm, what's the difference¿

I would read what you (ZetaX) first wrote as stopping at $ n$- which means that it doesn't make sense without $ n$ defined in advance. A terminal ... makes it unambiguous.


All the point in 3-space are coloured with 5 different colours (there is at least one point of each colour) prove that there exists at least one plane such that the points that make up that plane are made up of at least four of those colours.

[quote="nr1337"][quote="dts"][quote="nr1337"]Isn't that trivial?  Just take any four points of different colors (they exist by the problem definition) and connect them.   We've got our plane.[/quote]

A plane is defined by three points, not four.[/quote]

Why can't we have a rectangular plane?  Planes aren't necissarily triangular.[/quote]

If you have four points, you cannot guarantee that they are all on the same plane.  They could form a tetrahedron, in which case they do not define a plane.

This is one of those things I can see is true by just thinking about it for a little bit, but for which I can't come up with a nice proof.
Maybe this works.  Let P be a plane that contains three points of different colors.  Now let l be a line that contains points of the other two colors.  Consider the set of all planes that contain l.  If one of them contains 4 different color points we are done.  Otherwise, none do.  But that means that the colors of the plane P must be divided into lines.  Simply take a plane that contains one of the other two colors, but which is tilted at a different angle.  This plane will contain that color and the three original colors.  As I warned, I can't really explain my logic.


group theory
abstract algebra
superior algebra
superior algebra unsolved

$G$ a finite group of order $n$. Suppose that if $G$ has a subgroup of order $k$, then there is only one subgroup of order $k$.
Is $G$ necessary cyclic?

In particular, each $p$-Sylow of $G$ is unique and whence normal in $G$. Also their intersection is pairwise disjoint, and $G$ can be written as the internal direct product of its $p$-Sylows. Now if each $p$-Sylow is cyclic, we are done. Otherwise, for each $p$-Sylow $S_{p}$ with cardinal say $p^{n}$ ($n >1$) we must have $\sum_{k=0, \dots,n-1} p^{k} \geq  p^{n}$ (since each unique subgroup of $S_{p}$ has a cardinal dividing $p^{n}$ strictly). This is obviously absurd.

P.S : in the case $G$ is not abelian, the $p$-Sylow subgroups of $G$ are still determining an internal direct product but I didn't verify carefully that this sum must equal $G$ (and is not strictly included in $G$). It seems kind of clear by induction.

I hope I did not commit any big mistake this time  :D

[quote="julien_santini"] Also their intersection is pairwise disjoint, and $G$ can be written as the internal direct product of its $p$-Sylows. [/quote]

just a question :  why can $G$ be written as the internal direct product of its $p$-Sylows. The  $p$-Sylows are just pairwise distinct and normal. Does it suffice ?

Yes:
Let $S: = S_{p_1} \times \S_{p_2} \times ... \times S_{p_n}$ be the direct product of the sylow subgroups.
Then the claim is that $f: (x_1,x_2,...,x_n) \mapsto x_1x_2...x_n$ is a group isomorphism.

Lemma:
if $U,V \subset G$ are normal subgroups with $U \cap V = \{ e \}$, then the map $F: U \times V \mapsto G, (u,v) \mapsto uv$ is injective and $UV=f(U \times V)$ is a normal subgroup in $G$.
Prove: try yourself, it's easy.

But multiple use of this lemma implies the result.

Yes, it does. What you want to prove is this: given two normal subgroups $H,K$ of a group $G$ satisfying $H\cap K=\{1\}$, the subgroup $HK$ of $G$ is the internal direct product $H\times K$.

It suffices to prove that every element $h$ of $H$ commutes with every element $k$ of $K$. Look at the commutator $[h,k]=hkh^{-1}k^{-1}$. On the one hand, it must belong to $H$, since both $h$ and $kh^{-1}k^{-1}$ do. On the other hand, it must belong to $K$, since both $hkh^{-1}$ and $k^{-1}$ do. Since $H$ and $K$ have trivial intersection, we must have $[h,k]=1$, meaning that $h$ and $k$ commute, as desired.

Edit:

I see ZetaX answered before I did.

oops  :blush:  I thought a necessary condition was $S_i \cap <S_j>_{j \neq i}=\{1\}$ and not just $S_i \cap S_j=\{1\}$... sorry again ...

For every proper divisor $k$ of $n$, there are, under the given assumption, at most $\phi(k)$ elements of order $k$.
Since
\[ \sum_{k|n}\phi(k)=n\,,  \]
there still are at least $\phi(n)$ elements of order not a proper divisor of $n$. These have necessarily order $n$, so they generate $G$, which is then cyclic.

why at most $\phi(k)$ elements of order $k$ ? (It makes me think to the proof that any finite subgroup of the multiplicative group of a field is cyclic. But here I can't understand your statement ?)

Yes, it works very similar:
If $x$ has order $k$, then of the powers $x^i$, only the ones with $gcd(i,k)=1$ have order $k$ too.
Now assume there is some $y \not \in <x>$ with order $k$. But then $<x>$ and $<y>$ are different subgroups with $k$ elements.


superior algebra
superior algebra unsolved

What notation could be used to denote the following field?:

\[ \left\{\frac{a\plus{}bx}{c\plus{}dx}\ : \ a,b,c,d\in\mathbb{Z}_{2}\right\}.\]
Could we use $ \mathbb{Z}_{2}\left(x\right)/x^{2}\mathbb{Z}_{2}\left(x\right)$?

In what sense is this a field?  It does not look closed under multiplication to me.  Also, I am not sure what you mean by $ x \over 0$.

By the way, $ \mathbb{Z}_{2}\left(x\right)/x^{2}\mathbb{Z}_{2}\left(x\right)$ is not a field, as it has zero divisors: $ x^2\equal{}0$.

I'm looking for a field with $ 16$ elements but I guess that example doesn't make sense.  Would the field $ \mathbb{Z}_{2}\left[x\right]/\left<x^4\plus{}x^{3}\plus{}1\right>$ work?

Yes, it's always the case that $ \mathbb{F}_p [x] / \left<p(x)\right> \cong \mathbb{F}_{p^k}$ when $ p$ is degree $ k$ and irreducible over $ \mathbb{F}_p$.


ARML
algebra
polynomial
pigeonhole principle
probability
geometry
perimeter

Here are solutions to the first two days.  Most of the times we will use solutions that are PMed to us by competitors.

[size=150][b]Day 1[/b][/size]
Let $Q(x)$ be the quotient when $37x^{73}-73x^{37}+36$ is divided by $x-1$. Compute the sum of the coefficients of $Q(x)$.

[i]Solution-Complements of Rep123Max[/i]

[quote="Rep123Max"]
$37x^{73}-73x^{37}+36=37x^{73}-73x^{37}+73-37=37(x^{73}-1)-73(x^{37}-1)$

$(x-1)|(x^{73}-1)$ and $(x-1)|(x^{37}-1)$ leaving a quotient of

$37(x^{72}+x^{71}+\ldots+x+1)-73(x^{36}+x^{35}+\ldots+x+1)$

Subbing in $x=1$ since the question wants the sum of the coefficients of the quotient, it is $37(73)-73(37)=\boxed{0.}$[/quote]

[size=150][b]Day 2[/b][/size]

Let $P(x)$ be a polynomial whose degree is $1996$. If $P(n)=\frac 1n$ for $n=1,2,3,\ldots,1997$, compute the value of $P(1998).$

[i]Solution[/i]

[quote]First, multiply both sides of $P(n)=\frac 1n$ by $n$ and subtract both sides by one:

\[nP(n)-1=0.\]

Now, we know that this is satisfied for $1,2,\ldots,1997$.  In other words, $nP(n)-1$ has zeros at $1,2,\ldots,1997$.  So we can write it as:

\[nP(n)-1=k(n-1)(n-2)\cdots(n-1997)\]

where $k$ is some constant.  So pluggin in $n=0$ we can find $k$ as follows:

\[-1=k(-1)(-2)\cdots(-1997)\Rightarrow k=\frac{1}{1997!}.\]

Therefore \[1998P(1998)-1=\frac{1}{1997!}(1997)(1996)\cdots(1)\Rightarrow P(1998)=\boxed{\frac{1}{999}.}\][/quote]

[size=150][color=black]Day 3[/color][/size]

If $P(x)$ is a polynomial in $x$, and $x^{23}+23x^{17}-18x^{16}-24x^{15}+108x^{14}=(x^4-3x^2-2x+9)\cdot P(x)$ for all values of $x$, compute the sum of the coefficients of $P(x)$.

The most common solution given was straightforward polynomial division:
[quote="Solution 1"]Directly divide $x^{23}+23x^{17}-18x^{16}-24x^{15}+108x^{14}$ by $(x^4-3x^2-2x+9)$ to obtain $P(x)=x^{19}+ 3x^{17}+2x^{16}+12x^{14}$, so the sum of the coefficients is $1+3+2+12=\fbox{18}$.[/quote]

However, this problem originally appeared in an individual round, suggesting a faster way (although in most cases, people said the division process took them less than 5 minutes to do anyways):

[i]Solution-Thanks to Elemennop[/i]

[quote="Elemennop"]Given, $\displaystyle x^{23}+23x^{17}-18x^{16}-24x^{15}+108x^{14}=(x^4-3x^2-2x+9)\cdot P(x)$,

we isolate $P(x)$ to one side.

$P(x)=\displaystyle\frac{x^{23}+23x^{17}-18x^{16}-24x^{15}+108x^{14}}{x^4-3x^2-2x+9}$

Now that we have $P(x)$, the sum of the coefficients of it is merely $P(1)$. Therefore,

$P(1)=\frac{1+23-18-24+108}{1-3-2+9}=\frac{90}{5}=\fbox{18}$.[/quote]

Wow, that really is a much better solution.

[size=150][color=black]Day 4[/color][/size]
Point value: 6

No calculators!  :P

The number $85^9-21^9+6^9$ is divisible by an integer between $2,000$ and $3,000$. Compute that integer.

This probably was originally #8 on an ARML individual round. Most people used guess and check to quickly find that 5 and 7 divided this expression (thanks to Rep123Max):

[quote="Rep123max"]
Answer: $\fbox{2240}$

Solution: After realizing that the numbers are too big to go through all the factoring (in the normal, alloted time), I began to search for values that were divisible by it.

For some reason, I started with seeing if 7 divides the equation (probably because 21 was sticking out at me): $85^9-21^9+6^9\equiv (1)^9-(0)^9+(-1)^9\equiv 0\pmod 7$. So we now have one divisor. Noticing that seeing if 49 divides it does not look promising, I moved downwards to 5.

$85^9-21^9+6^9\equiv (0)^9-(1)^9+(1)^9\equiv 0\pmod 5$. Again, noticing that 25 does not look to promising (although, I did try it for about a minute), we move down to 2.

$85^9-21^9+6^9\equiv (1)^9-(1)^9+(0)^9\equiv 0\pmod 2$. I continued with powers of 2 because it seemed easy to work with:

$85^9-21^9+6^9\equiv (1)^9-(1)^9+(0)^9\equiv 0\pmod 4$.
$85^9-21^9+6^9\equiv (-3)^9-(-3)^+(0)^9\equiv 0\pmod 8$.
$85^9-21^9+6^9\equiv (5)^9-(5)^9+(0)^9\equiv 0\pmod {16}$.
$85^9-21^9+6^9\equiv (21)^9-(21)^9+(0)^9\equiv 0\pmod {32}$.
$85^9-21^9+6^9\equiv (21)^9-(21)^9+(0)^9\equiv 0\pmod {64}$.

We can stop there, we have that $2^6\cdot5\cdot7=2240|(85^9-21^9+6^9)$, so we are done.[/quote]

Although his solution took less than 5 minutes anyways, the "most elegant" solution was algebraic manipulation:

[quote="Solution 2"]
Consider the general case $a^k-b^k+c^k$.
Since $a^k-b^k$ is divisible by $a-b$, then $a^k-b^k+c^k$ is divisible by the greatest common factor of $a-b$ and $c^k$. Hence, our expression is divisible by $GCD(85-21,6^9)=GCD(64,6^9)=2^6$.
By the same token $GCD(21-6,85^9)=GCD(15,85^9)=5$ is a factor.
Also, for odd $k$, the expression $a^k+c^k$ is divisible by $a+c$, so $GCD(85+6,21^9)=7$ must also be a factor. Since all these divisors are relatively prime, $85^9-21^9+6^9$ is divisible by $2^6\cdot 5\cdot 7=\fbox{2240}$.
[/quote]

Props to those who jumped on that immediately.

[size=150][color=darkblue]Day 5[/color][/size]

3 points this time, and still no calculator...but at least we get a break from too much more algebra. :)

You have 121 marbles, some of which are red, some white, and the rest blue. You also have 10 jars. If all the marbles are distributed into the jars, there [i]must[/i] be a jar with at least $n$ marbles of the same color. Compute the maximum possible value for $n$.

This problem was originally a Team question #1 on ARML. Apparently, what the question was asking for was confusing, since only 11 out of 17 people got it overall and only around 5 on their first try. It was basically two applications of Pigeonhole, but several people misread the number of marbles or jars.  Anyways, here's a solution (Thanks to mathfanatic):

[quote="mathfanatic"]
Answer: $\fbox{5}$

Solution:

Since 121/3 = 40.333, at least 41 marbles must have the same color.

Since 41/10 = 4.1, at least 5 marbles of the same color must be in some jar.

Check that this is minimum: take {5R,4W,4B} and 9 sets of {4R,4W,4B}.

Alternatively, we can think of the problem as having thirty jars containing 121 marbles of the same color.  Again, the answer is 5.[/quote]

Or we could pigeonhole jars first:

[quote="Solution 2"]
Since there are 121 marbles to put into 10 jars, there must be at least one jar with at least 13 marbles. In that jar, since there are 3 total different colors for marbles, there must be at least one color with at least 5 marbles.
Thus, the answer is $\fbox{5}$
[/quote]

Good job to everyone who got it!

[size=150][color=green]Day 6[/color][/size]

No calculators, though not sure how they could help anyways.

Worth 7 points.

In order to list the integers from 0 through 7 in binary notation [0, 1, 10, 11, 100, 101, 110, 111], we must write twelve 1's. Compute the number of 1's needed to list, in binary notation, the integers from 0 through 1023.

So, as expected, there were many different approaches to this problem:

[quote="Elemennop"]We can see that if we order all the numbers in base $2$ into a certain order, there is symmetry between one subset and the subset of the next group. Specifically, between the subset of all the numbers between $2^n$ and $2^{n+1}-1$, inclusive, has the same number of $1's$ written as between $0$ and $2^n-1$, plus an additional $n$  $1's$ at the beginning of the number (This is obvious for smaller cases of $n$, such as $n=1,2,3$).

We can define this recursively: Define $f(n)$ as the number of $1's$ written to list out all integers between $2^n$ and $2^{n+1}-1$. By our previous definition, $f(n)$ is defined as:

$f(n)=f(1)+f(2)+...+f(n-1)+2^n$

Now we can quickly list out all the ordered pairs, getting the next $f(n)$ by adding up all the terms in the f(n) part of the ordered pair, then adding $2^n$. We are looking for everything up to $f(9)$ (The $1's$ between $512$ and $1023$ in base $2$).

$(0,1)$
$(1,3)$
$(2,8)$
$(3,20)$
$(4,48)$
$(5,112)$
$(6,256)$
$(7,576)$
$(8,1280)$
$(9,2816)$

Now to find our answer, we merely add up $f(1)+f(2)+...+f(9)=2f(9)-2^9$ (because $f(9)-2^9=f(1)+f(2)+...+f(8)$ by our formula) $=2(2816)-512=5632-512=\fbox{5120}$.

Note: I tried to find some general formula for $f(n)$ in terms of $f(0)$, but ran into some problems. If anyone else wants to follow up on this, feel free to.[/quote]

[quote="alan"]im fairly certain this method works.  try smaller cases to notice a pattern in the amount of "1"s used.  indeed, it begins to resemble binomial expansion very quickly.

$0-0 \rightarrow 0$
$0-1 \rightarrow 0 + 1$
$0-3 \rightarrow 0 + 2(1) + 2$
$0-7 \rightarrow 0 + 3(1) + 3(2) + 3$
$\vdots$
$0-(2^n-1) \rightarrow \binom{n}{0}(0) + \binom{n}{1} (1) + \binom{n}{2} (2) \dots + \binom{n}{n-1}(n-1) + \binom{n}{n}(n)$

$1023=2^{10}-1$

$=\binom{10}{0}(0) + \binom{10}{1} (1) + \binom{10}{2} (2) \dots + \binom{10}{9}(9) + \binom{10}{10}(10)$
$=(0+10) + \binom{10}{1}(1+9) + \binom{10}{2}(2+8) + \binom{10}{3}(3+7) + \binom{10}{4}(4+6)+\binom{10}{5}(5)$
$=5*2^{10}=\boxed{5120}$
[/quote]

[quote="djshowdown2"]When dealing with binary, powers of two are always useful, so we see that $1023 = 2^{10} - 1$ and is therefore nine 1's in binary.  So I listed out the first couple numbers in reverse order and recognized the pattern within the digits (first digit cycles through $2^0$ 1's then $2^0$ 0's, second digit is $2^1$ 1's and $2^1$ 0's, third is $2^2$ and so on).
111111111
111111110
111111101
111111100
111111011
111111010

if this pattern is continued through 000000000, there are 1024 rows and 10 columns.  Clearly half of the digits in the each column are 1's, so the total is $\frac{1}{2}1024 \times 10=\fbox{5120}$[/quote]

[quote="fanaticsm"]Day 6:

The answer is $\boxed{5120}$

For each binary number $a$ there is a complimentary number $b$, such that $a+b=1023$. The reason for calling them complimentary number is because their binary representations completes each to other to 10 units Thus, the answer to the question is $512\cdot 10=5120$

[b]Note:[/b] If you have no idea as to what I mean when I say 'complimentary', here is an example:

Consider $a=618$ and $b=405$, and then compare the binary representation for $a$ and $b$:

$1001101010=a=618$
$+$
$0110010101=b=405$
$=$
$1111111111=1023=a+b$[/quote]

[quote="paladin8"]ANSWER: $\fbox{5120}$

We notice that if we write all the numbers in binary from $0$ to $2^n-1$, exactly half of the numbers have a $1$ as the last digit, half have $1$ as the second to last digit, and so on. $2^n-1$ has $n$ digits and there are $2^n$ total numbers. So $2^{n-1}$ of them have a $1$ in a certain spot. Thus there are $n(2^{n-1})$ total $1$'s. Since $1024=2^n$, $n=10$ and we have $10(2^9)=5120$ appearances of $1$.[/quote]

paladin8 has the general formula, $n(2^{n-1})$.

[size=150][color=indigo]Day 7[/color][/size]

No calculators, 4 points.

Compute $x$ if $\text{Arctan }x+\text{Arctan }1=2\left(\text{Arctan }x-\text{Arctan }\frac{1}{3}\right)$.

This problem came from a team round, so don't worry about it if you spent a lot more time getting your hands dirty with the algebra. Some people immediately took the tangent of both sides, but the undistributed 2 on the right hand side makes for an ugly cubic. Instead, if the terms were collected first, the work is a lot easier.

[quote="paladin8"]ANSWER: $\boxed{7}$

Rearrange to get $\arctan{x}=\arctan{1}+2\arctan{\frac{1}{3}}$.
So $x=\tan{(\arctan{1}+2\arctan{\frac{1}{3}})}$.
Using the tangent sum formula,
$x=\frac{\tan{(\arctan{1})}+\tan{(2\arctan{\frac{1}{3}})}}{1-\tan{(\arctan{1})}\tan{(2\arctan{\frac{1}{3}})}}$.
We use the tangent sum formula again to evaluate $\tan{(2\arctan{\frac{1}{3}})}$.
$\tan{(2\arctan{\frac{1}{3}})}=\frac{2\tan{(\arctan{\frac{1}{3}})}}{1-\tan^2{(\arctan{\frac{1}{3}})}}=\frac{\frac{2}{3}}{1-\frac{1}{9}}=\frac{3}{4}$
Plugging that back in we get $x=\frac{1+\frac{3}{4}}{1-\frac{3}{4}}=7.$
[/quote]

Also, here's another approach that considers an actual triangle:

[quote="alan"]let $y=\arctan{x}, z=\arctan{\frac{1}{3}}$
$y+45=2(y-z)$
$45+2z=y$
draw triangle for $z$
$\sin{z}=\frac{1}{\sqrt{10}}, \cos{z}=\frac{3}{\sqrt{10}}$
$\sin{2z}=2\sin{z}\cos{z}=\frac{3}{5}$
so it forms a 3-4-5
$x=\tan{y}=\tan{(45+2z)}=\frac{\tan{45}+\tan{2z}}{1-\tan{45}\tan{2z}}=\frac{1+\frac{3}{4}}{1-(1)(\frac{3}{4})}=\boxed{7}$[/quote]

Again, thanks to all those who provided solutions.  :)

[size=150][color=red]Day 8[/color][/size]

5 points and no calculator

Compute the length of the tangent segment from the origin to the circle that passes through the points (3, 4), (6, 8), and (5, 13).

[quote="djshowdown2"]If you draw a coordinate plane and plot the three points, you can see the general curve of circle, so put a center at point $(h,k)$.  Draw 3 segments: a radius to the point of tangency, the tangent from the origin, and a segment connecting the origin and the center of the circle, forming a right triangle.  The length of the hypotenuse is $h^2+k^2$ and the radius is $r$ so calling the length of the tangent segment $x$ you can write the equation $h^2 + k^2 = r^2 + x^2$ by Pythagorean Theorem.

Describe the circle based on two different points.  $(3,4)$ gives you $k^2+h^2=r^2+8h+6k-25$ and $(6,8)$ gives $k^2+h^2=r^2+16h+12k-100$ so you have $x^2 = 8h+6k-25 = 16h +12k - 100$ so $8h+6k = 75$ and thus $x^2 = 75 - 25 = 50$ so $x=\boxed{5\sqrt{2}}$[/quote]

[quote="paladin8"]ANSWER: $\boxed{5\sqrt{2}}$

Consider the line from the origin through $(3,4)$ and $(6,8)$ and the tangent line of length $x$. The distance from the origin to $(3,4)$ is $5$ and the distance to $(6,8)$ is $10$. By Power of a Point, $(5)(10)=x^2 \Rightarrow x=5\sqrt{2}$.[/quote]

[size=150][color=violet]Day 9[/color][/size]

No calculators and 6 points.

Let $x_n+iy_n=(1+i\sqrt{3})^n$, where $x_n$ and $y_n$ are real and $n$ is a positive integer. If $x_{19}y_{91}+x_{91}y_{19}=2^k\sqrt{3}$, compute $k$

This problem was from a team round, so no worries if it took a little longer to think of. The core of the problem seemed to be DeMoivre's Theorem for everybody, and it was pretty much straightforward from then on.

Here's one solution in the complex plane (Thanks to djshowdown2):

[quote="djshowdown2"]Write $1+i\sqrt{3}$ as the polar coordinate $(2,\frac{\pi}{3})$.  Using that $(r,\theta)^n = (r^n,n\theta)$,

$(2,\frac{\pi}{3})^{19} = (2^{19},\frac{19\pi}{3}) \Rightarrow (2^{19},\frac{\pi}{3}) \Rightarrow 2^{18} + 2^{18}\sqrt{3}i$

$(2,\frac{\pi}{3})^{91} = (2^{91},\frac{91\pi}{3}) \Rightarrow (2^{91},\frac{\pi}{3}) \Rightarrow 2^{90} + 2^{90}\sqrt{3}i$

so the value in question is

${2^{18}2^{90}\sqrt{3} + 2^{90}2^{18}}\sqrt{3}$
$(2^{108} + 2^{108})\sqrt{3}$
$2(2^{108})\sqrt{3}$
$2^{109}\sqrt{3} = 2^k\sqrt{3}$
$\framebox[.5 in]{k=109}$[/quote]

And another approach involving cis (Thanks to Elemennop):

[quote="Elemennop"]$(1+i\sqrt{3})$ can be rewritten as $2\displaystyle\left(\frac{1}{2}+\frac{\sqrt{3}}{2}i\right)$. Conveniently, the second expression is $\cos60+i\sin60$, or just $\text{cis}60$. Thus, $x_n+iy_n=(2)^n(\text{cis}60)^n$.

Now that we've simplified the first expression, we can rewrite what we're looking for as:

$\text{Re}[(2^{19})(\text{cis}60)^{19}]\cdot\text{Im}[(2^{91})(\text{cis}60)^{91}] + \text{Re}[(2^{91})(\text{cis}60)^{91}]\cdot\text{Im}[(2^{19})(\text{cis}60)^{19}]$

$2^{110}\text{Re}(\text{cis}1140)\cdot\text{Im}(\text{cis}5460)+2^{110}\text{Re}(\text{cis}5460)\cdot\text{Im}(\text{cis}1140)$

Since we can subtract any measure of $360k$ from the value of $\text{cis}$, we do this to the two expressions to see that are both $60$! How nice.

$2^{110}\cdot\frac{1}{2}\cdot\frac{\sqrt{3}}{2} + 2^{110}\cdot\frac{1}{2}\cdot\frac{\sqrt{3}}{2}$

$2^{108}\sqrt{3} + 2^{108}\sqrt{3} = 2^{109}\sqrt{3}$

Therefore, the value of $k$ is $\fbox{109}$.[/quote]

[size=150][color=olive]Day 10[/color][/size]

Let $x$ be a randomly selected integer from the set $\{100,101,\ldots,999\}.$ What is the probability that $x^2$ and $(x+100)^2$ have the same number of digits?

All the solutions were basically variations of this one (thanks to fanaticism):

[quote="fanaticism"]
The probability is $\boxed{\frac{7}{9}}$

The squares of three-digit numbers have either 5 or 6 digits. If $10,000 \leq x^2 < 100,000,$ then $100 \leq x \leq 316$ and $x$ and $x+100$ both lie in this range if $x \in \{100, 101, ..., 216\}.$ If $100,000 \leq x^2 < 1,000,000,$ then $317 \leq x \leq 999$ and $x$ and $x+100$ both lie in this range if $x \in \{317, 318, ..., 899\}$. Out of 900 three-digit numbers, there are $(216-100+1) + (899-317+1) = 117 + 583 = 700$ values of $x$ satisfying the condition stated in the problem.

Therefore, the required probability is $\frac{700}{900} = \frac{7}{9}$.[/quote]

[size=150][color=orange]Day 11[/color][/size]

Part 1 (6 pts):

Prove that if $n=\sqrt{a}+\sqrt{b}+\sqrt{c}$ for integers n, a, b, and c, then a, b, and c must be perfect squares.

Part 2 (4 pts):

Using Part 1 or otherwise, prove that if $T=T(a,b,c)$ is a right triangle with integer sides, then the perimeter of $\sqrt{T}=(\sqrt{a},\sqrt{b},\sqrt{c})$ cannot be an integer.

[quote="qwertyq"]
\[\displaystyle n=\sqrt{a}+\sqrt{b}+\sqrt{c}\]
\[n-\sqrt{c}=\sqrt{a}+\sqrt{b}\]
square both sides and rearrange to get
\[n^2+c-a-b=2\sqrt{a}\sqrt{b}+2n\sqrt{c}\]
\[n^2+c-a-b=2(\sqrt{a}\sqrt{b}+n\sqrt{c})\]
The left side is obviously an integer since $n$,$a$,$b$, and $c$ are integers
therefore the right side has to be an integer
for that to happen $\sqrt{a}\sqrt{b}$ has to be an integer and $n\sqrt{c}$ has to be an integer
Ignore the first expression for now
For the second expression to be an integer $c$ has to be a perfect square since $n$ is an integer that multiplys it. If $c$ were anything other than a perfect square then that expression would not be an integer.
Similarly for $a$ and $b$ we can rearrange the original to make
\[n^2+a-b-c=2\sqrt{b}\sqrt{c}+2n\sqrt{a}\] and
\[n^2+b-c-a=2\sqrt{c}\sqrt{a}+2n\sqrt{b}\]
Thus, $a$, $b$, and $c$ are all perfect squares. [/quote]

[quote="Rep123Max"]
This is easily proved by contradiction. Supposing that the perimeter of \sqrt{T}=T(\sqrt{a}, \sqrt{b}, \sqrt{c}) is an integer, then a=d^2, b=e^2 and c=f^2 for integers d, e, and f. Since the trianlge is right, a^2+b^2=c^2\Longrightarrow d^4+e^4=f^4 which is not true for integral d, e, and f. Thus, the perimeter is not integral.[/quote]

Solution to problem I posted:

[quote="Elemennop"]The obvious way to see how many solutions there are is to see how many intersections there between the graphs of the two equations (this allows us to not actually have to find the solutions $(x,y)$).

So, the first equation is $\sin(x+y)=\cos(x+y)\Longrightarrow\tan(x+y)=1$. A tan function has a value of 1 at values of $\frac{\pi}{4}+k\pi$ for all integer values of k.

Looking at the second equation, we see it's a circle with center at $(0,0)$ and a radius of $\frac{1995\pi}{4}$.

We essentially have the graph of a circle with a large radius, and an infinite amount of lines with equation of $x+y=\frac{(4k+1)\pi}{4}\Rightarrow y=-x+\frac{(4k+1)\pi}{4}$ for all integers k.

Each line (excluding tangents) will make two intersections with the circle. Thus, we only need to find how many lines will go inside the circle, then multiply that by two and account for any tangents that might occur.

To see how many lines appear, we must find what two lines are the tangent lines of the circle. These two lines will have equation y=-x+m for some real number m. All equations of that form make an $45^{\circ}-45^{\circ}-90^{\circ}$ triangle with the coordinate axes.

Thus, imagine quadrant I of the graph. There will be a quarter circle, and some line l that is tangent to the circle and has the form mentioned above. Because it's an isosceles triangle, it's tangent from the center of the circle will be both the altitude of the triangle from the origin as well as the median.

Knowing that the median of a right triangle will split the hypotenuse into two equal parts, each with length equal to the median, and seeing that the median is the radius of the circle, $m=\frac{1995\pi}{4}=\frac{1}{2}h$, and the hypotenus has length $\frac{1995\pi}{2}$. Since it's base angles are $45^{\circ}$, it's legs have length $\frac{1995\sqrt{2}\pi}{4}$. Thus, any of our lines such that $|m|>\frac{1995\sqrt{2}\pi}{4}$ will be outside the circle (and since the $\sqrt{2}$ is there, it's clear we won't have any tangent lines formed from our first equation).

Now we need to see what's the highest k we can get. $1995\cdot\sqrt{2}$ is approximately equal to 2821 and some fractional part. Thus, all $(4k+1)\le2821$ or $(4k+1)\ge2821$ will be within the circle and have two intersection points. Our answer is twice however many integer solutions there are to $|4k+1|\le2821$. Solving this, we see $-705.5\le k\le705$.

Therefore, the answer is $2(705+705+1)=2(1411)=\fbox{2822}$.[/quote]

[quote="fanaticism"]
\begin{eqnarray*}
\sin{(x+y)} - \cos{(x-y)} = 0 &\rightarrow& \left(\sin{x} \cdot \cos{y} + \cos{x} \cdot \sin{y}\right) - \left(\cos{x} \cdot \cos{y} + \sin{x} \cdot \sin{y}\right) = 0\\  &\rightarrow& (\sin{x})(\cos{y} - \sin{y}) - (\cos{x})(\cos{y} - \sin{y}) = 0\\ &\rightarrow& (\sin{x} - \cos{x})(\cos{y} - \sin{y}) = 0\\
\end{eqnarray*}

Therefore, $\sin{x} = \cos{x}$ or $ \sin{y} = \cos{y}$

Therefore, $x = \frac{\pi}{4} + n\pi$ or $y = \frac{\pi}{4} +n\pi$, where n is an integer. The radius of the circle is $\frac{1995\pi}{4}$. For $  x \geq 0$, there are vertical lines at $\left\{x = \frac{\pi}{4}, \frac{5\pi}{4}, ... , \frac{1993\pi}{4}\right\}$, for a total of 499 lines intersecting the circle at two points, making 998 points of intersections. Similarly, for $y \geq 0$, there are 499 vertical lines intersecting the circle at 998 points. For $x < 0$, there are vertical lines at $\left\{x = -\frac{3\pi}{4}, -\frac{7\pi}{4}, ... , -\frac{1995\pi}{4}\right\}$. There are $\frac{1995-3}{4} + 1$, or 499 vertical lines, 498 of which intersect the circle at two points, the other is a tangent.

Thus, there are 997 points of intersection. Similarly for y < 0, there are 997 points of intersections. The total number of points of intersections, or rather, solutions equals $2(998) + 2(997) = 3990$.[/quote]

so you get the same answer both ways...?

In the ARML book, it actually reads:
$\sin (x+y) = \cos (x+y)$
$x^2+y^2 = \left(\frac{1995\pi}{4}\right)^2$

And in the provided solutions:
$\sin(x+y)-\cos(x-y) = 0$
$(\sin{x}\cdot\cos{y}+\cos{x}\cdot\sin{x})-(\cos{x}\cdot\cos{y}+\sin{x}\cdot\sin{y}) = 0$

So the intended problem was probably:
$\sin (x+y) = \cos (x-y)$
$x^2+y^2 = \left(\frac{1995\pi}{4}\right)^2$

The actual problem is a lot harder, unless I'm missing something really obvious or I messed up somewhere down the line:
$\sin (x+y) = \cos (x+y) \rightarrow \tan(x+y)=1$
$\displaystyle x+y=\frac{\pi}{4}+n\pi$
This equation describes lines that are separated by a perpendicular distance of $\frac{\pi}{\sqrt{2}}$.
$x^2+y^2 = \left(\frac{1995\pi}{4}\right)^2$ is a circle with diameter $\frac{1995\pi}{2}$, enough distance for at least $\displaystyle\frac{\left(\frac{1995\pi}{2}\right)}{\left(\frac{\pi}{\sqrt{2}}\right)}\approx1410.67\rightarrow1410$ of these lines. If any of these lines are tangent to the circle, it must be either at $(\frac{1995\sqrt{2}}{8},\frac{1995\sqrt{2}}{8})$ or at $(-\frac{1995\sqrt{2}}{8},-\frac{1995\sqrt{2}}{8})$.
However, neither of these points satisfies $\displaystyle x+y=\frac{\pi}{4}+n\pi$ for integral $n$, so there are no tangent lines to the circle.
Thus, there should be $1410*2=\fbox{2820}$ solutions to the system since each intersecting line produces two solutions.

I found this problem pretty hard to do without calculator, so you're probably right Max. The original problem should read:

For $x$ and $y$ in radians, compute the number of solutions in ordered pairs $(x,y)$ to the following system:

\begin{eqnarray*}
\sin (x+y) &=& \cos (x-y) \\
x^2+y^2 &=& \left(\frac{1995\pi}{4}\right)^2
\end{eqnarray*}

[quote="towersfreak2006"]Yes, you can always work on a problem until the solutions are posted. And the day 44 problem was really tough, as only three people got the right answer. I also stole it from joml88's book :) and the recent years seem to be more tricky.

[size=150][color=indigo]Day 46[/color][/size]

No calculators, 6 points

Point $P$ is inside a rectangular box. The distances from point $P$ to four of the vertices of the box are $1, 2, 3,$ and $4$. If the distance from $P$ to another vertex is greater than $5$, find that distance.[/quote]

[quote="ARML Solution"]
This solution is based on the easily proved theorem that given rectangle $ABCD$ and point $P$, then $PA^2+PC^2=PB^2+PD^2$; this holds even when $P$ is not in the plane of the rectangle! Let the vertices of one face of the box be $A$, $B$, $C$, and $D$, and the diagonally opposite vertices (with respect to the center of the box) be $A'$, $B'$, $C'$, and $D'$ respectively. To simplify notation, let the distance $PA$ be represented simply by $A$, $PB$ by $B$, etc. Thus we know that $A^2+C^2=B^2+D^2$, and (from rectangle $ABA'B'$) $A^2+A'^2=B^2+B'^2$, etc.

1. Let $A[=PA]=1$. Then either $2=B$ or $2=C$ $[2%Error. "neqA" is a bad command.
'$ since $A^2+A'^2=1^2+2^2<3^2$+anything, so no distance from $P$ to another vertex can equal to $3]$. Suppose $2=C$. Then $3\neq A$, $C$, $B$, $D$, $A'$, or $C'$. Therefore $3=B'$ or $D'$ (symmetrical situation). Let $3=B'$. Then $4\neq A$, $C$, $B$, $D$, $A'$, $C'$, or $B'$, so $4=D'$. But we cannot accommodate a distance greater than $5$. Therefore $2=B$.

2. Now $3\neq A$, $B$, $A'$, or $B'$, so either $3=C$ $[$or $D']$ or $3=D$ $[$or $C']$. Suppose $3=C$. Then we have $D=\sqrt{6}$. Now $4\neq A'$, $B'$, $C'$, OR $D'$, since we could not accommodate a distance greater than $5$. Therefore $3=D$.

3. Finally, we have $C=\sqrt{12}$ and $4=C'$ $[$this is the only way to get a pair of "opposite points" whose squares total more than $25]$. Then $'D=\sqrt{19}$, $B'=\sqrt{24}$, and $A'=\sqrt{27}$ or $3\sqrt{3}$. Note: It can be shown that such a box [i]does[/i] exist.
[/quote]

Also, the following is an interesting solution that assumes the box to be a cube. I don't think it works, but then again, what do I know about geometry? Perhaps someone else can comment on it:

[quote="tarquin"]To make it convenient, put the point inside a cube. On a cartesian plane, the coordinates of the cube are then

$(0,0,0)$
$(0,a,0)$
$(0,0,a)$
$(a,0,0)$
$(a,a,0)$
$(a,a,a)$
$(0,a,a)$
$(a,0,a)$

If the coordinates of $P$ are $(m,p,q)$ using the distance formula we have

$m^2 + p^2 + u^2 = 1$

$m^2 + (p-a)^2 + u^2 =4$

$m^2 + p^2 + (u-a)^2 = 9$

$(m-a)^2 + p^2 + u^2 = 16$

Adding them all up and subtracting $3m^2 + 3p^2 + 3u^2 = 3$ yields $(m-a)^2 + (p-a)^2 + (u-a)^2 = 27$

$\sqrt {27} = 3 \sqrt 3$[/quote]

Well if I wanted to type a little bit more than I could have put it in any arbitrary rectangular prism I'd just add on some value $x$ and I would have ended up with $(m - a - x)^2 + (p - a- x)^2 + (q - a -x)^2 = 27$

Er I think.

[quote="towersfreak2006"][size=150][color=violet]Day 47[/color][/size]

No calculators, 6 points

There are several values for a prime, $p$, with the property that any 5-digit multiple of $p$ remains a multiple of $p$ under "cyclic permutation". One such value is $41$ (for example, since $50635$ is a multiple of $41$, so are $55063$, $35506$, $63550$, and $[0]6355$); another such value of $p$ is $3$. Compute the value of $p$ that is greater than $41$.[/quote]

[quote="paladin8"]ANSWER: $271$

So we know $p$ divides some number $abcde = 10^4a+10^3b+10^2c+10d+e$ and its permutations $bcdea$, $cdeab$, $deabc$, and $eabcd$. Thus it must divide the sum of these five numbers, $11111(a+b+c+d+e)$. Since we have $11111 = (41)(271)$, $p = 271$ is the only possible number.[/quote]

Since these are from before 1995, no use of calculator was permitted for any of these (for some obvious reasons...)

Compute $\sqrt{(111,111,111,111)(1,000,000,000,005)+1}$.

[quote]
$\sqrt{(111,111,111,111)(1,000,000,000,005)+1}=\sqrt{(\frac{999,999,999,999}{9})(1,000,000,000,005)+1}$
$\sqrt{(111,111,111,111)(1,000,000,000,005)+1}=\sqrt{\left[\frac{10^{12}-1}{9}\right]\left[10^{12}+5\right]+1}$
$\sqrt{(111,111,111,111)(1,000,000,000,005)+1}=\sqrt{\frac{10^{24}+4\cdot10^{12}+4}{9}}$
$\sqrt{(111,111,111,111)(1,000,000,000,005)+1}=\sqrt{\frac{(10^{12}+2)^2}{9}}$
$\sqrt{(111,111,111,111)(1,000,000,000,005)+1}=\frac{10^{12}-1+3}{3}$
$\sqrt{(111,111,111,111)(1,000,000,000,005)+1}=\frac{999,999,999,999+3}{3}=\boxed{333,333,333,334}$
[/quote]

Let $z$ and $z+1$ be complex $n$th roots of $1$. If $n$ is a positive integer multiple of $5$, compute the smallest possible value for $n+z^3$.

[quote]
Drawing a unit circle around the origin $O$ in the complex plane, we know that points representing the $n$th roots of unity lie on this circle and are the vertices of a regular $n$-gon. The points $P$ and $Q$, representing the complex numbers $z$ and $z+1$ respectively, lie on this circle; $PQ$ is parallel to the x-axis and $PQ=1=OP=OQ$, so angle $POQ=60^\circ$. Thus, additional vertices must lie at $A(1,0), B(-1,0)$ and at points $P'$ and $Q'$ representing $-z$ and $-(z+1)$ respectively, producing the six vertices of a regular hexagon. Since $P, A, Q'$ represent the cube roots of $1$, then $z^3=1$. If there are additional vertices along arc $PQ$, there must be corresponding vertices along each of the other five arcs of the circle. Thus $n$ must be a multiple of $6$. Since it is given to be a multiple of $5$, the smallest possible value for $n$ is $30$, and $n+z^3=\boxed{31}$.
[/quote]

Compute all positive integer values of $n$, $1<n<100$, such that $\binom{n}{2}$ is a perfect square.

[quote]
Since $\binom{n}{2}=\frac{n(n-1)}{2}=k^2$, the odd factor is a positive square, while the even factor is twice a positive square. Testing the five possible odd squares, we see that $\boxed{n=2,9,50}$ work.
[/quote]

Points $P,Q,$ and $R$ are the midpoints of the medians of triangle $ABC$. If the area of triangle $ABC$ is $1,024$, compute the area of triangle $PQR$.

[quote]
Let $P$ and $Q$ be midpoints of medians $AD$ and $BE$ respectively, and let the medians intersect at $G$. Letting $GD=2x$, we have $AG=4x$, $AP=3x$, so $PG=x$. Since $PQ$ is parallel to $AB$, triangles $PQG$ and $ABG$ are similar, with ratio of similitude $1:4$. Thus the area of $PQG=\frac{1}{16}$ times the area of $ABG$. Similarly, we see that the area of $PQR$ is $\frac{1}{16}$ the area of $ABC$ = $\frac{1}{16}(1024)=\boxed{64}$.
[/quote]

If
\[\tan(120^\circ-x)=\frac{\sin120^\circ-\sin x}{\cos120^\circ-\cos x}\]
where $0^\circ<x<180^\circ$, compute $x$.

[quote]
Expressing $\tan(120^\circ-x)$ as $\frac{\sin(120^\circ-x)}{\cos(120^\circ-x)}$, expanding numerator and denominator and cross-multiplying with the right side of the original equation, we get
\[\begin{equation*}
(\sin{120^\circ}\cos{x}-\sin{x}\cos{120^\circ})(\cos{120^\circ}-\cos{x})=(\cos{120^\circ}\cos{x}+\sin{120^\circ}\sin{x})(\sin{120^\circ}-\sin{x})
\end{equation*}\]
Putting in values for $\sin{120^\circ}$ and $\cos{120^\circ}$, multiplying out and simplifying the result, we eventually get $-4\sin{x}=2\sin{2x}+2\sqrt{3}\cos{2x}$. Dividing through by $4$ now leads to $\sin{-x}=\sin{60^\circ+2x}$. Considering the possible cases, only $\boxed{x=100}$ satisfies the given conditions.
[/quote]

As $t$ takes on all real values, the set of points $(x,y)$ defined by
\[x=t^2-2,\qquad y=t^3-9t+5\]
forms a curve that crosses itself. Compute the ordered pair $(x,y)$ where this crossing occurs.

[quote]
Two different values of $t$ must produce the same $(x,y)$; call them $t_1$ and $t_2$. Then $(t_2)^2-2=(t_1)-2$, so $t_2=\pm t_1$ which implies that $t_2=t_1$. Now $(t_1)^3-9(t_1)+5=(-t_1)^3-9(-t_1)+5$, so $t_1=3$ and $t_2=-3$ (or vice versa), from which we can conclude that $\boxed{(x,y)=(7,5)}$.
[/quote]

A convex pentagon is inscribed in a circle. If its sides are $16, 16, 16, 16,$ and $6$, its area will be $k\sqrt{7}$. Compute the number $k$.

[quote]
Let the pentagon be $ABCDE$ with $AE=6$. Let $AD=a$ and $AC=BD=CE=b$. Applying Ptolemy's Theorem to $ABCD$, we have $16a+16^2=b^2$; applying it to $ACDE$, we have $16a+96=ab$. Solving for $a$ in the first expression, and substituting into the second, we have $b^3-2^9b-2^9\cdot3=0$, which only has $b=24$ as a rational root. Triangles $ABC$ and $CDE$ are isoceles, each with area $48\sqrt{7}$; triangle $ACE$ is isoceles with area $27\sqrt{7}$. The sum of these gives the pentagon's area, $123\sqrt{7}$, so $\boxed{k=123}$.
[/quote]

[quote="JesusFreak197"]Why has the answer been posted already? I got home from school, saw the question, had to go straight out, got the answer while I was out (and it's the correct answer, by the way), and I come back and the answer is posted? I don't think so. :dry: You didn't give nearly enough time for this, especially considering that this was a 6-point question.[/quote]

towersfreak2006 had to leave today and wanted to the get the solutions posted before he left.  On the other hand, he did give almost one full day for it...

I'm looking at the fact that the one whole day doesn't help much when I went to bed right before he posted it, and couldn't see it until after I got home from school. I think I overreacted a little there, but it just seems a little unfair to me to post the answers to two problems within 16 minutes of each other... I'm used to the answers being posted the day after I first see it, rather than just six hours after.

Ok, there is still time to send me answers for Day 48 or Day 49.  As always, they can be sent in anytime before the solutions are posted for them to be valid.  If I remember, I will post them tomorrow before I leave for ARML...but since I have to leave at like 4 AM I will probably not be coherent enough to post them :P

Anyways, the top 3 places can't possibly change so I will go ahead and congratulate them.

[size=167][color=olive]1st Place - d343seven  :winner_first: [/color][/size]

[size=150][color=silver]2nd Place - paladin8  :winner_second: [/color][/size]

[size=134][color=brown]3rd Place - alan :winner_third: [/color][/size]

[size=117][color=green][u]Honorable Mentions[/u][/color]

[color=blue]djshowdown2
xxreddevilzxx
Elemennop
Rep123Max
JesusFreak197
isaacchao
qweretyq[/color][/size]

The top 3 were the only to break 100.  d343seven put on a stellar performance by almost breaking 200! (and probably would have had he attempted some of the last few problems...but he probably out of town or something).  Great job everyone!

I would like to thank you all for participating in the ARML Practice Series.  It has been a great pleasure hosting.  The best of luck at ARML tomorrow and I hope to see some of you there.
 :bye:

$\blacksquare$

[quote="JesusFreak197"]Wow... if I had been here for every day since I started doing this, I could have come in fourth! :o Congratulations to the top three![/quote]

ditto on that. I miss the first 20 days or so.

Sorry for not posting the final two solutions earlier.  Btw, d343seven sent in correct solutions to the last two so he did get 200 points :)

[size=150][color=green]Day 48[/color][/size]

[i]Calculator Allowed[/i]
[i]5 points[/i]

Let $2^x3^y=\left(24^{\frac 12+\frac 13 +\cdots+ \frac{1}{60}}\right)^1\cdot\left(24^{\frac 13+\frac14+\cdots+\frac{1}{60}}\right)^2\cdot\left(24^{\frac 14+\frac 15+\cdots+\frac{1}{60}}\right)^3\cdot \ldots \cdot\left(24^{\frac{1}{60}}\right)^{59}.$  Compute the value of $x+y$.

[quote="JesusFreak197"]Focus on the exponents. Each one loses the first term of the previous exponent, and is put to one power higher. When the exponents are added due to the multiplication of the $24^n$ terms, we are left with a series of $\frac{1}{2}+\frac{3}{3}+\frac{6}{4}+\frac{10}{5}+...+\frac{1770}{60}=\frac{1}{2}+\frac{2}{2}+\frac{3}{2}+\frac{4}{2}+\frac{5}{2}+...+\frac{59}{2}$. We can quickly solve this by using $\frac{n(n+1)}{2}$ for the numerators of the fractions, and we get $\frac{\frac{59(60)}{2}}{2}=\frac{1770}{2}=885$. So, $2^x3^y=24^{885}=2^{2655}3^{885}$, and $x+y=3540$.[/quote]

[size=150][color=blue]Day 49[/color][/size]

[i]No Calculuator[/i]
[i]4 points[/i]

Compute the largest factor of $1001001001$ that is less than $10,000.$

[quote="xxreddevilzxx"]well.... we can see that since the number can be divided by any factors of $1001$, we have then $1001001001 = 1001 \cdot 1000001$. From there, we know that by pattern of adding 0's in the middle of 2 1's, it is divisible by 1001 once again. so $1001001001 = 1001^2 \cdot 9901$, which means $\boxed{9901}$ is the answer.[/quote]

OR

[quote="isaacchao"]1001001001 = 10^9 + 10^6 + 10^3 + 1
= 10^6(10^3+1)+ (10^3 +1)
=(10^6 + 1)(11*91)
=101*(10^4-10^2+1)*11*91
=101*9901*11*91

among testings, 9901 is the largest factor of 1001001001 that is less than 10000

9901[/quote]

Althought it doesnt matter at all, i didnt get points for day 49 =)

[quote="Solution 2"]
Since there are 121 marbles to put into 10 jars, there must be at least one jar with at least 13 marbles. In that jar, since there are 3 total different colors for marbles, there must be at least one color with at least 5 marbles.

can you elaboraete a bit?
I still didn't get your answer.

Ah, is this one mine? I think this was the original problem:

You have 121 marbles, some of which are red, some white, and the rest blue. You also have 10 jars. If all the marbles are distributed into the jars, there must be a jar with at least n marbles of the same color. Compute the maximum possible value for n.

With your 10 jars, let's put 12 marbles into each one to minimize the number of marbles in the most "populated" jar. Then we have placed 120 marbles into jars, and there's one left over, so then one jar will have at least 13 marbles. So let's look at that jar then. If you put 4 red marbles, 4 white marbles, and 4 blue marbles to diversify the colors in the jar, you have 12 marbles, and you'll need to add another marble. Whichever color you choose, there will be 5 marbles of that color in that jar, so there will be at least 5 marbles of the same color in a jar.

I hope that helps. :)