algebra
Additive Number Theory
Inequality
reciprocal sum
IMO Shortlist

Let $A$ be a non-empty set of positive integers. Suppose that there are positive integers $b_1,\ldots b_n$ and $c_1,\ldots,c_n$ such that

- for each $i$ the set $b_iA+c_i=\left\{b_ia+c_i\colon a\in A\right\}$ is a subset of $A$, and

- the sets $b_iA+c_i$ and $b_jA+c_j$ are disjoint whenever $i\ne j$

Prove that \[{1\over b_1}+\,\ldots\,+{1\over b_n}\leq1.\]

Fisrt of all A must be infinite. Assume that the density of A in $\mathbb{N}$ is well defined. Denote by $p_{i}$ the probability that an element of A lie in the set $b_{i}A+c_{i}$. This probability is equal to \[p_{i}= \lim_{n\to \infty}\frac{\#\{b_{i}A+c_{i}\cap A \}\cap \{1,2,..n\}}{\#A \cap \{1,2,..n\}}=\]  \[\lim_{n\to \infty}\frac{\#\{x\in A, b_{i}x+c_{i}\le n \}}{\#A \cap \{1,2,..n\}}=\]  \[\lim_{n\to \infty}\frac{\#A \cap \{1,2,..\frac{n-c_{i}}{b_{i}}\}}{\#A \cap \{1,2,..n\}}\le \frac 1{b_{i}}\] Since one of this events may not occur and they exclude each other we have that $\sum \frac 1{b_{i}}\le 1$.
Now we only need to prove that the density of A in $\mathbb{N}$ is well defind i.e. $\lim_{n\to infty}d_{n}=\lim_{n\to \infty}\frac{\#A\cap \{1,..,n\}}{n}$ exists.

Can anybody fill in this argument?

I put the official solution below,but I can't understand the step  $ \frac{\phi(N\plus{}N_{0})}{\phi (N)}\ge\frac{1}{q^{N_{0}}}$ can somebody explain this to me? :)
And I am interested in the solution given in the comment,but the comment didn't give a full solution.I am surprised by the hint of the comment,but the last step which lead to the result didn't have a proof.I don't know if it is trivial or it is just a theorem about infinite set,could anyone continue the proof?

How stupid I am :blush: I knew the ineq now.
But if we define the density as ZetaX in http://www.mathlinks.ro/viewtopic.php?p=849974#849974
$ d_{A}(B) : \equal{}\lim_{k\to\infty}\frac{n_{B}(k)}{n_{A}(k)}$
Can we obtain $ d_{A}(A_{i})\equal{}\frac{1}{b_{i}}$?

[quote="ywl"]dear hxy09,

using the second approach (the comment in the official solution) leads to the following solution.
Lemma.
For a set $ A \subset \mathbf{N}$ and $ x \in \mathbf{N}$, let us define $ f(x) \equal{} \#\{y\mid y\in A,y\leq x\}$
if $ u_1,\ldots,u_n$ are real numbers such that $ \sum u_i > 1$ then there exists $ x$ such that $ f(u_i \cdot x)\geq u_i \cdot f(x)$ for all $ i \equal{} 1,\ldots,n$
This is not very intuitive, but you can prove it using contradiction. (I think it is a wonderful result)
the lemma is nontrivial, but as a brief outline, assume contradiction and work on from the large numbers and find a fast increasing sequence of $ \frac {f(x)}{x}$, which is smaller than 1 for all $ x$, and obtain a contradiction.

using the lemma one can finish the problem easily.[/quote]

Thank you very much,but can you give details? :)

I was trying to find another solution (but can't finish it).
Let $ f(x)\equal{}\sum_{a\in A}x^a$. Using the conditions in the problem we get $ 1\geq \sum_{i\equal{}1}^n x^{c_i}\frac{f(x^{b_i})}{f(x)}$. Can we prove (I don't even know if it's true) that $ \lim_{x\to 1}\frac{f(x^b)}{f(x)}\equal{}\frac{1}{b}$?

[quote="limes123"]I was trying to find another solution (but can't finish it).
Let $ f(x) \equal{} \sum_{a\in A}x^a$. Using the conditions in the problem we get $ 1\geq \sum_{i \equal{} 1}^n x^{c_i}\frac {f(x^{b_i})}{f(x)}$. Can we prove (I don't even know if it's true) that $ \lim_{x\to 1}\frac {f(x^b)}{f(x)} \equal{} \frac {1}{b}$?[/quote]

If $ \lim_{x\to 1}{f(x)(1\minus{}x)} \equal{}a>0$ then $ \lim_{x\to 1}\frac {f(x^b)}{f(x)} \equal{} \lim_{x\to 1}\frac {f(x^b)(1\minus{}x^b)}{f(x)(1\minus{}x)} \cdot  \lim_{x\to 1}\frac {1\minus{}x}{1\minus{}x^b} \equal{} \frac {1}{b}$
so it remains to prove that $ \lim_{x\to 1}{f(x)(1\minus{}x)} \equal{}a>0$ but I dont know how to prove this. And we can use the condition \[ {1\over b_{1}}\plus{}\,\ldots\,\plus{}{1\over b_{n}}>1.\].

Hello,
I believe I have a different solution that uses nothing on density (just some really bad bounds)

Let Y be the sum (1/a) for a in A and a <= (b_n)^j. Clearly Y < 1+1/2+...+1/(b_n)^n

Let f_i(x) be defined as b_i*x +c_i
Let Z be the sum (1/f(f(f(...x)) for some sequence of j f's, where each f is one of f_i. It is clear Z<Y since the elements in Z's sum are in Y's sum.

but f_d(x)f_e(x) > b_db_e(x+2*max(c_i) (this generalizes really easily but is a huge pain to write out)

so Z > (sum(1/b_i))^j * 1/(x+j*max(c_i)) where x is a generator of a.

if sum(1/b_i) > 1, then let it = x. then we have x^j/j*constant <<<< j*ln(b_n) for all j, since x^j/j<Z<Y<1+1/2+...+1/(b_n)^n ~ j ln (b_n)

But this is false for large j.

So sum (1/b_i) <=1

Solution by dysfunctionalequations and me.

[hide]We will suppose for the sake of contradiction that $\frac{1}{b_1} + \frac{1}{b_2} + \cdots + \frac{1}{b_n} > 1$.

Call a set [i]good[/i] if it satisfies the hypotheses of this problem. Call a set $X$ [i]primitive[/i] if there exist sets $X_0, X_1, \ldots$ such that:
[list][*] $X_0$ has exactly one element.
[*] $X_{n+1} = \bigcup_{i = 1}^n (b_i X_n + c_i).$
[*] $X = \bigcup_{i=1}^{\infty} X_i$. [/list]

It is easy to see that $A$ must be the superset of some primitive set. By definition, all primitive sets are good, so we may assume without loss of generality that $A$ is primitive.

For any positive real $r$, define $A_r = A \cap [0, r]$. We will first show that for all $r > K = \max(\min A, c_1, c_2, \ldots, c_n)$, $A_r = \{\min A\} \cup \bigcup_{i=1}^{n} (b_i A_{\frac{r-c_i}{b_i}} + c_i)$. It is obvious that the right-hand side is a subset of the left-hand side. To show that the left-hand side is a subset of the right-hand side, we note that since $A$ is primitive, any element $y$ of $A_r$ must equal either $\min A$ or $b_i x + a_i$ for some $x \in A$ and some $i$. $\{\min A\}$ accounts for the former case. In the latter case, we have that $x \leq \frac{y-b_i}{a_i}$, so $y \in b_i A_{\frac{r-c_i}{b_i}} + c_i$, which proves our claim.

Since all sets of the form $b_i A + c_i$ are disjoint, we may deduce from the above claim that $|A_r| = 1 + \sum_{i=1}^n |A_{\frac{r-c_i}{b_i}}|$ for all $r > K$.

Define $z_r = |A_r|$ for all integers $r$. Since $|A_r| = |A_{\lfloor r \rfloor}|$ for all $r > K$, we see that $z_r = 1 + \sum_{i=1}^n z_{\lfloor \frac{r-c_i}{b_i} \rfloor}$. We claim that there is some constant $m > 0$ such that $z_r > rm$ for all $r > 0$. Since $\frac{1}{b_1} + \frac{1}{b_2} + \cdots + \frac{1}{b_n} > 1$, we can find some positive integer $R$ such that whenever $r > R,$

\begin{align*}
\sum_{i=1}^n \lfloor \frac{r-c_i}{b_i} \rfloor
&\geq (\sum_{i=1}^n \frac{r-c_i}{b_i} ) - n \\
&= r ( \sum_{i=1}^n \frac{1}{b_i} ) -  (n + \sum_{i=1}^n \frac{c_i}{b_i} ) \\
&= r + r ( -1 + \sum_{i=1}^n \frac{1}{b_i} ) -  (n + \sum_{i=1}^n \frac{c_i}{b_i} ) \\
&\geq r.\end{align*}

Let $m = \min_{1 \leq i \leq R} \frac{z_i}{i}$. We will use strong induction to show that $z_r \geq rm$ for all $r$. It is easy to see that $z_r \geq rm$ when $1 \leq r \leq R$. Supposing now that the result is true for all positive integers less than some $r > R$, we have $z_r = 1 + \sum_{i=1}^n z_{\lfloor \frac{r-c_i}{b_i} \rfloor} > m \sum_{i=1}^n \lfloor \frac{r-c_i}{b_i} \rfloor  \geq rm$, so the inductive step is complete.

Since $\frac{z_r}{r}$ is bounded from below by a positive number, the limit inferior $c$ of $\{ \frac{z_r}{r} \}$ is positive. Hence, for any positive real number $\epsilon$ less than $c$, we can find arbitrarily large $t$ (lying in the subsequence of $\{ \frac{z_r}{r} \}$ that converges to $c$) that satisfy $z_t < t c + t \epsilon$ and $z_{\lfloor \frac{t - c_i}{b_i} \rfloor} > \lfloor \frac{t - c_i}{b_i} \rfloor (c - \epsilon)$ for all $i$ (in fact, $z_s > s(c - \epsilon)$ for all sufficiently large $s$, not necessarily in the subsequence that converges to $c$.) For any such $t$, we have

$\begin{align*}
t c + t \epsilon
&\geq z_t \\
&> \sum_{i=1}^n z_{\lfloor \frac{t-c_i}{b_i} \rfloor} \\
&> \sum_{i=1}^n ( (c - \epsilon)  \lfloor \frac{t-c_i}{b_i} \rfloor ) \\
&\geq (c - \epsilon) \sum_{i=1}^n (\frac{t-c_i}{b_i} - 1 ) \\
&= t (c - \epsilon) ( \sum_{i=1}^n \frac{1}{b_i} ) - (c - \epsilon)(n + \sum_{i=1}^n \frac{c_i}{b_i} )
\end{align*}.$

Dividing both sides by $t(c - \epsilon)$ and rearranging yields

$\frac{c + \epsilon + \frac{n + \sum_{i=1}^n \frac{c_i}{b_i}}{t}}{c - \epsilon} > \sum_{i=1}^n \frac{1}{b_i}.$

Since this holds for arbitrarily large $t$,
$\frac{c + \epsilon}{c - \epsilon} > \sum_{i=1}^n \frac{1}{b_i}$
for all positive $\epsilon$ less than $c$. But $\lim_{\epsilon \to 0} \frac{c + \epsilon}{c - \epsilon} = 1$, so $\sum_{i=1}^n \frac{1}{b_i} \leq 1$, which contradicts our assumption that $\sum_{i=1}^n \frac{1}{b_i} > 1$, so $\sum_{i=1}^n \frac{1}{b_i} \leq 1$, as desired. [/hide]

Maybe this is equivalent to the density argument but it's much easier for me to see...

By (1), $A$ is infinite. Note that for all $s>1$, $\sum_{a\in A}\frac{1}{a^s}\le\zeta(s)$ converges.

Also, for all $\epsilon>0$, there exists an integer $M$ such that for all $a\in A,a\ge M$ and $1\le i\le n$, $b_ia+c_i\le b_ia(1+\epsilon)$ (since the $b_i,c_i$ are fixed positive integers). By the problem hypothesis,
\[\sum_{i=1}^{n}\sum_{a\in A,a\ge M}\frac{1}{b_i^s a^s(1+\epsilon)^s}\le\sum_{i=1}^{n}\sum_{a\in A,a\ge M}\frac{1}{(b_ia+c_i)^s}\le \sum_{a\in A,a\ge M}\frac{1}{a^s},\]i.e.
\[\sum_{i=1}^{n}\frac{1}{b_i^s}\le(1+\epsilon)^s\]for all $s>1$ and $\epsilon>0$. The conclusion follows immediately by continuity.

dear @math154
desinty may be good for you, but mayn't for I.
   Please, who can solve the problem, by Generating function?

Dear [b]mathuz[/b],
I don't know why you are not satisfied with the density arguments, but it's the most natural approach.
Imagine a perfect situation when the density of $A$ is the same in every interval $[1,N]\,,\, N\in \mathbb{N}$ . Then the density of $b_i A+c_i$ in respect to $A$ (as being a subset of $A$) , framed in the interval $[1,N]$ , slightly differs $\frac{1}{b_i}$ , when $n\to \infty$. It is so, because $A$ has an infinitely many elements and the proportion of elements of $b_i \cdot\{a\in A \mid a\leq N/b_i\} $ , that leave the interval $[1,N]$ after translation by $c_i$ , will be as small as we want as $N\to \infty$.
This is the main idea, it only remains to carry out the general case :)

Denote (as above) the density of $A$ in $[0,N]$ as $d_N(A) = |\{a\in A \mid a\leq N\}|/N$. The above idea applies without changes if there are infinitely many $N$ with property $d_N(A) \leq \min_{k<N} d_k(A)$. In this case the density of $\{b_i a + c_i\ \mid a\in A, a\leq N/b_i \}$ in respect to $\{a\in A \mid a\leq N\}$ is bigger than $\frac{1}{b_i} - \varepsilon$ , where $\varepsilon$ can be taken arbitrary small.
If it is not the case, then $\liminf_{N\to\infty} d_N(A) = d > 0$. We can take $(N_k)_{k=1}^{\infty}$ with $\lim_{k\to\infty} d_{N_k} (A) = d$ and apply the above arguments to $N=N_k$. It gets a little bit more complicated since involves some routine "epsilon techniques". Here $d>0$ is an important thing.
So, the idea is more than clear, the only difficulties are pure technical, although it is not a problem if one has some calculus experience.
The Victor's solution above, essentially resembles density argument, but avoids all these annoying details one must care about.

Solution :

Consider linear functions $\psi_i :\mathbb{N}\to\mathbb{N}$, where $\psi_i(n) := b_in + c_i$ ($b_i\geq 2$).

Define sets $S(n): = \{\psi_{i_1}^{j_1}\psi_{i_1}^{j_1}\ldots \psi_{i_N}^{j_N}(n)|i_1, i_2, \ldots, i_N$, $j_1, j_2, \ldots, j_N\in\mathbb{N}\}$ for every $n\in \mathbb{N}$.

$\textbf{Lemma 1:}$

In these assumptions we have that $\sum_{i\in S(n)}\frac{1}{i}<\infty$ for any $n\in\mathbb{N}$.

$\textbf{Lemma 2:}$

We have that $\lim_{n\to\infty}\frac{\frac{1}{b_j}\sum_{i\in S(n)}\frac{1}{i}}{\sum_{i\in \psi_jS(n)}\frac{1}{i}} = 1$ for every $j$, $n\in\mathbb{N}$.

Return to main problem. Consider any $a\in A$ we have that $S(a)\subseteq A$ and for every $i\not= j$, $\psi_iS(a)\cap\psi_jS(a)=0$. From lemmas 1, 2 we see that $1=\lim_{a\in A, a\to\infty}\frac{\sum_{k=1}^n\sum_{i\in \psi_kS(a)}\frac{1}{i}}{\sum_{k=1}^n\frac{1}{b_k}\sum_{i\in S(a)}\frac{1}{i}} \leq \lim_{a\in A, a\to\infty}\frac{\sum_{i\in S(a)}\frac{1}{i}}{\sum_{k=1}^n\frac{1}{b_k}\sum_{i\in S(a)}\frac{1}{i}} = \frac{1}{\sum_{k=1}^n\frac{1}{b_k}}$, so $\sum_{k=1}^n\frac{1}{b_k}\leq 1$. $\Box$

Moreover from this proof we see that if $A=\cup b_iA + c_i$, then $\frac{1}{b_1}+\ldots +\frac{1}{b_n} = 1$.

[hide=Solution] Consider the formal series $$f(z) \, := \, \sum_{a \in A} z^a.$$ Note that $A$ must be infinite if the condition holds. From $$f(z)<(1+z+z^2+\dots)=\frac{1}{1-z},$$ we get that $f$ can be defined as a Functional Series for all $0<z<1$. Moreover, the limit $$\lim_{z \rightarrow 1^{-}} f(z)\cdot (1-z)=L$$ exists and $L>0$ (as we are taking limits on values where this is always positive). Thus, for all integers $b>0$, $$\lim_{z \rightarrow 1^{-}} \frac{f(z^b)}{f(z)}=\left(\lim_{z \rightarrow 1^{-}} \frac{f(z^b)\cdot (1-z^b)}{f(z)\cdot (1-z)}\right)\cdot \left( \lim_{z \rightarrow 1^{-}} \frac{1-z}{1-z^b}\right)=\frac{1}{b}.$$ The given condition of $b_iA+c_i$ being disjoint subsets of $A$ yields $$\sum^n_{j=1} z^{c_j}\cdot \frac{f(z^{b_j})}{f(z)} \le 1$$ for all $0<z<1$. Letting $z \rightarrow 1^{-}$ and taking the limits on both sides, we obtain $\sum^n_{j=1} \frac{1}{b_j} \le 1.$ $ \, \square$

 [/hide]

Is this correct? Limits always go haywire... :D

Solution with [b]stroller[/b]  :love:

Consider the directed graph with vertices the elements of $A$, and edge $u\to v$ iff $v=b_iu+c_i$ for some $i$. The condition implies that every vertex has outdegree $n$, and indegree $1$, so we get a forest, with each connected component generated by its root.* Note that we only need to prove the result on one connected component, so suppose $A$ corresponds to the minimal set generated by root $a$.

Now, suppose we have a vertex $v$ such that $a\to v$ has $e_i$ $i$-edges. Then, $a\le C\prod b_i^{e_i}$ for some constant $C$. So, if we consider all vertices with values $\le C*n^k$, this corresponds to at least the set of vertices such that $\sum e_i\log_n{b_i}\le k$. Call this set $A_k$. If we increment $k$, the $i$-edge of a given chain will increment by $\log_{b_i}n$ on average. So, each vertex will yield $\sum \log_{b_i}n$ children every increment, on average, and hence $|A_k|$ is of the order $\left(\sum\log_{b_i}n\right)^k$. However, by Jenson's on $\frac{1}{\ln(1/x)}$, $$\sum\frac{1}{b_i}>1\implies \sum\log_{b_i} n=\ln n\sum\frac{1}{\ln b_i}>\ln(n)\cdot\frac{n}{\ln n}=n$$
So, $|A_k|$ grows faster than $n^k$. However, we know that all elements in $|A_k|$ are less than $Cn^k$, so we eventually have repeated elements in $A_k$, which is a contradiction, as desired.

*See below for diagram

The following solution is a bit hastily written; which I apologize for. Also I am typing it late at night, so please do highlight if you find any errors in the solution.

[Hide=Solution]Consider the directed graph with vertices the elements of $A$, and edge $u\to v$ iff $v=b_iu+c_i$ for some $i$. The condition implies that every vertex has outdegree $n$, and indegree $1$. Color the edges with $n$ colors amongst $\{1,2 ,\dots n\}$ such that the edge $u \mapsto b_iu+c_i$ is colored with the color $i$.

Start from a vertex $a$ and start walking down the tree induced with root $a$ , hitting edges of color $i$ with frequency $p_i$. Then for some huge $N$ (such that all the $p_i$'s have a common denominator) , after walking down $N$ edges, we will have reached a number that is atmost $a\cdot \displaystyle \prod_{i=1}^{n} (b_i^{p_i})^N$.

Pick $N$ such that all the $N\cdot p_i$'s are integers. Then, considering all possible combinations of the choice of edges, we will we able to reach exactly $\frac {N!}{ \textstyle \prod_{i=1}^{n} (N\cdot p_i)!}$ many vertices. Note that this is of the order $\frac 1{\textstyle \prod p_i^{p_i}}$. Due to density reasons, we have the inequality  :

$$ \displaystyle \prod_{i=1}^{n} (b_i^{p_i})^N \geq \frac 1{\textstyle \prod p_i^{p_i}}$$
$$\iff \displaystyle \prod_{i=1}^{n} (p_i \cdot b_i)^{p_i} \geq 1$$

Now we pick the $p_i$'s to be proportional to the $\tfrac 1{b_i}$'s to get that $p_i \cdot b_i \geq 1$.

So we have $:=$

$$\sum_{i=1}^{n} \frac 1{b_i}\leq \sum_{i=1}^{n} {p_i} =1 $$

We are done. $\blacksquare$.


Instead of walking along two adjacent sides of a rectangular field, a boy took a shortcut along the diagonal of the field and saved a distance equal to $ \frac{1}{2}$ the longer side. The ratio of the shorter side of the rectangle to the longer side was:
$ \textbf{(A)}\ \frac{1}{2} \qquad\textbf{(B)}\ \frac{2}{3} \qquad\textbf{(C)}\ \frac{1}{4} \qquad\textbf{(D)}\ \frac{3}{4} \qquad\textbf{(E)}\ \frac{2}{5}$

[hide="Answer"]
We have $ D \equal{} L \plus{} W \minus{} \frac {1}{2}L$ from the statement and $ D^2 \equal{} L^2 \plus{} W^2$ from Pythagoras where $ L$ is the longer side and $ W$ is the shorter side
$ D \equal{} \frac {1}{2}L \plus{} W$
$ (\frac {1}{2}L \plus{} W)^2 \equal{} L^2 \plus{} W^2$
$ \frac {1}{4}L^2 \plus{} LW \plus{} W^2 \equal{} L^2 \plus{} W^2$
$ LW \equal{} \frac {3}{4}L^2$
$ W \equal{} \frac {3}{4}L$ We want to solve for $ \frac {W}{L}$.
$ \frac {W}{L} \equal{} \boxed{\frac {3}{4}}$
[/hide]

D      just think of a 3, 4, 5 triangle, 3+4=7 which is the distance he would have had to walked. He only walked 5. 7 - half of the long side(2) is equal to 5. Therefore, the ratio is the small side to the longer side, 3:4 or 3/4 equivalent.


Let $ \alpha \equal{} 3 \plus{} 2\sqrt{2}$ and $ \beta \equal{} 3 \minus{} 2\sqrt{2}$.

Prove that $ \alpha ^n \plus{} \beta ^n$ is not divisible by 5 for any integer $ n$.

[quote="Nora.91"]Let $ \alpha \equal{} 3 \plus{} 2\sqrt {2}$ and $ \beta \equal{} 3 \minus{} 2\sqrt {2}$.

Prove that $ \alpha ^n \plus{} \beta ^n$ is not divisible by 5 for any integer $ n$.[/quote]

$ \alpha \beta \equal{}1 \Rightarrow \alpha ^n \plus{} \beta ^n\equal{}\alpha ^{\minus{}n} \plus{} \beta ^{\minus{}n}$,

so we only need to prove the case that $ n$ is non-negative.

$ \alpha , \beta$ are roots of $ x^2\minus{}6x\plus{}1\equal{}0$. So define $ x_n\equal{}\alpha ^n\plus{} \beta ^n$ we have

$ x_{n\plus{}2}\minus{}6x_{n\plus{}1}\plus{}x_n\equal{}0$ for all $ n$ and $ x_0\equal{}2, x_1\equal{}6, x_2\equal{}34$.

Now $ 5|x_{n\plus{}2} \Rightarrow x_{n\plus{}1} \equiv x_n \pmod{5} \Rightarrow 5|x_{n\minus{}1}$,
similarly $ \Rightarrow 5|x_{n\minus{}4},x_{n\minus{}7},....,x_k$, where $ k \in \{ 0,1,2 \}$.

But $ 5 \nmid x_0,x_1,x_2$, contradiction, so $ 5 \nmid \alpha ^n \plus{} \beta ^n$ for all integers $ n$.


So when I go to the Advanced Mathcounts Tab I get this:

[edit: snip]
Announcements
The class message board is located in the "Online School" section of the Art of Problem Solving forum. The class message board will contain the weekly practice problems, and is also the place where you can ask questions about the class.
[edit: snip]

But then I click on Advanced Mathcounts/AMC8 Message Board and it says this:
The forum you selected does not exist.

Click Here to return to the Index

You can find the message board if you go to Online School. Click on Archive, then on Advanced Mathcounts/AMC8 Class. The message board remains up only a few weeks after class. It has now been archived. Hope this helped!!!

maybach -- I'm not sure what you're referring to when you mention what you click on.  When I click on the message board link, it works just fine.  Can you try it again?


Prove that there exists no comutative unitary ring with 5 invertible elements.

Anyone? Anything? Help! Please!  :blush:

[Moderator edit: Also http://www.mathlinks.ro/viewtopic.php?t=1354 ]

Pretty interesting, I have never dealt with this kind of problem before
(i only respond now because i did not know what unitary was)

One thing is for sure $Z_{m}$ will never give you a commutating unitary ring with exactly five invertible elements, because $phi(m)=5$ has no solutions

also, if you found a finite ring, it would have $1 mod 5$ elements

That's all I can say now

Is there any context that gives hints?

Let $I$ be the Identity, the units for a group of order 5, then we get $(-I)^5=I$ Which Implies that $I=-I$ So the ring has characteristic $2$. this means taht for every element here we have $a+a=0$, I dont know how to continue...

It’s going to seem a bit long, but the idea is very simple.

As Pascual noticed, the ring has characteristic $2$. It’s group of units is a multiplicative group with $5$ elements, so it must be cyclic, of the form $U=\{1,a,a^2,a^3,a^4\}$ for $a^5=1$.

Now let $A$ be the subring of our ring generated by $1$ and $a$. It’s a finite ring, having at most $2^5$ elements: the linear combinations of elements in $U$ with coefficients in $\mathbb Z_2$. Suppose we prove that there is a sum of elements in $U$ with at most $4$ terms which equals $0$. Then we’re pretty much done: the sum has either $1,2,3$ or $4$ elements. It can’t have $1$ term, since that would mean $a^i=0$ for some $0\le i\le 4$. It can’t have two terms, because then $a^i=a^j,\ 0\le i<j\le 4\Rightarrow a^{j-i}=1,\ 0<j-i<5$. If it has three terms, we can always rename the $a^i$’s to get it to the form $1+a+a^2=0\Rightarrow a+a^2+a^3=0\Rightarrow a^3=1$. Finally, if it has four terms, we can write it as $1+a+a^2+a^3=0$ (by eventually renaming the $a^i$’s), so $a+a^2+a^3+a^4=0\Rightarrow a^4=1$, which is a contradiction. Now let’s prove that indeed we must have such a null sum:

Consider $x=1+a+a^2+a^3+a^4$, and notice that $(x)=\{0,x\}$. In the ring $\tilde A=A/(x)$ we denote the projections of $a^i$ by the same symbols. If none of the sums of elements in $U$ is zero in $\tilde A$ except for $0$ itself and $1+a+a^2+a^3+a^4$, then $\tilde A$ has $31$ elements, which is impossible: it has characteristic $2$, so it must have an even number of elements. We thus find a sum $S$ with $1,2,3$ or $4$ terms in $U$ which projects onto zero in $\tilde A$, but then either $S$ or $S+x$ must be zero in $A$, and this will be the sum that we need, according to the previous paragraph.

"If it has three terms, we can always rename the $a^i$’s to get it to the form.. "
missed the case $1+a+a^3=0$


inequalities
induction
inequalities unsolved

Let $ \, a_{0}, a_{1}, a_{2},\ldots\,$ be a sequence of positive real numbers satisfying $ \, a_{i\minus{}1}a_{i\plus{}1}\leq a_{i}^{2}\,$ for $ i \equal{} 1,2,3,\ldots\; .$  (Such a sequence is said to be [i]log concave[/i].)  Show that for each $ \, n > 1,$
\[ \frac{a_{0}\plus{}\cdots\plus{}a_{n}}{n\plus{}1}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n\minus{}1}}{n\minus{}1}\geq\frac{a_{0}\plus{}\cdots\plus{}a_{n\minus{}1}}{n}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n}}{n}.\]

[quote="MithsApprentice"]Let $ \, a_{0}, a_{1}, a_{2},\ldots\,$ be a sequence of positive real numbers satisfying $ \, a_{i\minus{}1}a_{i\plus{}1}\leq a_{i}^{2}\,$ for $ i \equal{} 1,2,3,\ldots\; .$  (Such a sequence is said to be {\em log concave}.)  Show that for each $ \, n > 1,$
\[ \frac{a_{0}\plus{}\cdots\plus{}a_{n}}{n\plus{}1}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n\minus{}1}}{n\minus{}1}\geq\frac{a_{0}\plus{}\cdots\plus{}a_{n\minus{}1}}{n}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n}}{n}.\]
[/quote]
[hide="Solution"]
First we prove:

Lemma: $ a_{1}a_{n\minus{}1}\ge a_{0}a_{n}$.
Proof: Take the inequalities $ a_{i}\ge a_{i\minus{}1}a_{i\plus{}1}$ for $ i \equal{} 1,2,\cdots,n\minus{}1$ Multiplying these together and canceling factors gives $ a_{1}a_{n\minus{}1}\ge a_{0}a_{n}$.

Corollary: $ a_{k}a_{n\minus{}k}\ge a_{0}a_{n}$ for $ 1\le k\le\frac{n}{2}$
We induct on $ k$. For $ k \equal{} 1$ it is the same as the lemma. If it holds for $ k$, where $ 1\ge k\le\frac{n}{2}\minus{}1$, then $ a_{k},...,a_{n\minus{}k}$ is also a log concave sequence and thus $ a_{k\plus{}1}a_{n\minus{}k\minus{}1}\ge a_{k}a_{n\minus{}k}$. By the induction hypothesis, $ a_{k}a_{n\minus{}k}\ge a_{0}a_{n}$ and thus $ a_{k\plus{}1}a_{n\minus{}k\minus{}1}\ge a_{0}a_{n}$ and the induction is complete.

From this corollary, we now establish the inequality:
$ (a_{1}a_{2}\cdots a_{n\minus{}1})^{2}\ge (a_{0}a_{n})^{n\minus{}1}$
We take the inequalities $ a_{k}a_{n\minus{}k}\ge a_{0}a_{n}$ for $ k \equal{} 1,...,\frac{n}{2}$. If $ n$ is odd we square each of the $ \frac{n\minus{}1}{2}$ inequalities, multiply them together, and obtain the above inequality. If $ n$ is even, then we have $ n\minus{}k \equal{} k$ for $ k \equal{}\frac{n}{2}$, so we proceed as above without squaring this particular inequality, and produce the desired result.

From this we rearrange to get:
$ (a_{0}a_{1}\cdots a_{n\minus{}1}a_{n})^{\frac{1}{n\plus{}1}}(a_{1}\cdots a_{n\minus{}1})^{\frac{1}{n\minus{}1}}\ge a_{0}a_{n}$

By AM-GM, we have that:
\[ \frac{a_{0}\plus{}a_{1}\plus{}...\plus{}a_{n\minus{}1}\plus{}a_{n}}{n\plus{}1}\ge (a_{0}a_{1}\cdots a_{n\minus{}1}a_{n})^{\frac{1}{n\plus{}1}}\]

\[ \frac{a_{1}\plus{}...\plus{}a_{n\minus{}1}}{n\minus{}1}\ge (a_{1}\cdots a_{n\minus{}1})^{\frac{1}{n\minus{}1}}\]
Multiplying these together produces:
\[ \frac{(a_{0}\plus{}a_{1}\plus{}...\plus{}a_{n\minus{}1}\plus{}a_{n})(a_{1}\plus{}...\plus{}a_{n\minus{}1})}{(n\plus{}1)(n\minus{}1)}\ge (a_{0}a_{1}\cdots a_{n\minus{}1}a_{n})^{\frac{1}{n\plus{}1}}(a_{1}\cdots a_{n\minus{}1})^{\frac{1}{n\minus{}1}}\ge a_{0}a_{n}\]
Adding $ (a_{0}\plus{}a_{1}\plus{}...\plus{}a_{n\minus{}1}\plus{}a_{n})(a_{1}\plus{}...\plus{}a_{n\minus{}1})$ to each side, we get:
\[ \frac{n^{2}(a_{0}\plus{}a_{1}\plus{}...\plus{}a_{n\minus{}1}\plus{}a_{n})(a_{1}\plus{}...\plus{}a_{n\minus{}1})}{(n\plus{}1)(n\minus{}1)}\ge a_{0}a_{n}\plus{}(a_{0}\plus{}a_{1}\plus{}...\plus{}a_{n\minus{}1}\plus{}a_{n})(a_{1}\plus{}...\plus{}a_{n\minus{}1}) \equal{} (a_{0}\plus{}\cdots\plus{}a_{n\minus{}1})(a_{1}\plus{}\cdots\plus{}a_{n})\]
or
\[ \frac{a_{0}\plus{}\cdots\plus{}a_{n}}{n\plus{}1}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n\minus{}1}}{n\minus{}1}\geq\frac{a_{0}\plus{}\cdots\plus{}a_{n\minus{}1}}{n}\cdot\frac{a_{1}\plus{}\cdots\plus{}a_{n}}{n}.\]
as desired.[/hide]

[hide="Solution"]

[b]Lemma 1:[/b] First we will prove, by induction, that $ \frac {a_{k}^{k \plus{} 1}}{a_{k \plus{} 1}^k} \ge a_0 \forall k \in \mathbb{N}$.

For our base case we use $ k \equal{} 1$. Since $ a_{i \minus{} 1}a_{i \plus{} 1} \le a_i^2$ for all $ i \in \mathbb{N}$, we have $ a_0a_2 \le a_1^2 \Rightarrow \frac {a_1^2}{a_2^1} \ge a_0$.

Now, suppose that $ \frac {a_k^{k \plus{} 1}}{a_{k \plus{} 1}^k} \ge a_0$ for some $ k \equal{} j$. We wish to prove it is true for $ k \equal{} j \plus{} 1$ as well.

  $ \dfrac{a_j^{j \plus{} 1}}{a_{j \plus{} 1}^j} \ge a_0$

  $ a_{j \plus{} 1}^{j \plus{} 2} \ge \dfrac{a_{j \plus{} 1}^{2(j \plus{} 1)}}{a_j^{j \plus{} 1}} a_0$

  $ a_{j \plus{} 1}^{j \plus{} 2} \ge a_{j \plus{} 2}^{j \plus{} 1}a_0$ (since $ a_ja_{j \plus{} 2} \le a_{j \plus{} 1}^2$)

  $ \dfrac{a_{j \plus{} 1}^{j \plus{} 2}}{a_{j \plus{} 2}^{j \plus{} 1}} \ge a_0$

Thus, the statement is true for all natural numbers $ k$.

  $ \Box$

[b]Lemma 2:[/b] Now we will prove, by induction, that $ a_1a_2a_3 \ldots a_{n \minus{} 1} \ge (a_0a_n)^\frac {n \minus{} 1}{2}$ for all natural numbers $ n \ge 2$.

For our base case we use $ n \equal{} 2$. We know that $ a_1^2 \ge a_0a_2$ from the problem condition, so $ a_1 \ge (a_0a_2)^\frac {1}{2}$.

Now, suppose that $ a_1a_2a_3 \ldots a_{n \minus{} 1} \ge (a_0a_n)^\frac {n \minus{} 1}{2}$ for some $ n \equal{} m$. We wish to prove it is true for $ n \equal{} m \plus{} 1$ as well.

  $ a_1a_2a_3 \ldots a_{m \minus{} 1} \ge (a_0a_m)^\frac {m \minus{} 1}{2}$

  $ a_1a_2a_3 \ldots a_m \ge (a_0a_m)^\frac {m \minus{} 1}{2} a_m$

  $ a_1a_2a_3 \ldots a_m \ge a_0^\frac {m \minus{} 1}{2} a_m^\frac {m \plus{} 1}{2}$

By our first lemma,

  $ \dfrac{a_m^{m \plus{} 1}}{a_{m \plus{} 1}^m} \ge a_0$

  $ \dfrac{a_m^\frac {m \plus{} 1}{2}}{a_{m \plus{} 1}^\frac {m}{2}} \ge a_0^\frac {1}{2}$

  $ 1 \ge \dfrac{a_0^\frac {1}{2} a_{m \plus{} 1}^\frac {m}{2}}{a_m^\frac {m \plus{} 1}{2}}$

Multiplying, we get:

  $ a_1a_2a_3 \ldots a_m \ge a_0^\frac {m}{2} a_{m \plus{} 1}^\frac {m}{2} \equal{} (a_0a_m)^\frac {(m \plus{} 1) \minus{} 1}{2}$

This was the form we wanted; so for all natural numbers $ n \ge 2$, we have $ a_1a_2a_3 \ldots a_{n \minus{} 1} \ge (a_0a_n)^\frac {n \minus{} 1}{2}$.

  $ \Box$

We can write the result of our second lemma as:

  $ (a_1a_2 \ldots a_{n \minus{} 1})^\frac {2}{n \minus{} 1} \ge a_0a_n$

  $ (a_1a_2 \ldots a_{n \minus{} 1})^\frac {2n}{n^2 \minus{} 1} \ge (a_0a_n)^\frac {n}{n \plus{} 1}$

  $ (a_0a_n)^\frac {1}{n \plus{} 1} (a_1a_2 \ldots a_{n \minus{} 1})^\frac {2n}{n^2 \minus{} 1} \ge a_0a_n$

  $ \sqrt [n^2 \minus{} 1]{a_0^{n \minus{} 1}a_1^{2n}a_2^{2n}a_3^{2n} \ldots a_{n \minus{} 1}^{2n} a_n^{n \minus{} 1}} \ge a_0a_n$

By the Arithmetic Mean - Geometric Mean Inequality, we get:

$ \dfrac{(a_0 \plus{} a_1 \plus{} \ldots \plus{} a_n)(a_1 \plus{} a_2 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2 \minus{} 1} \ge a_0a_n$

$ \dfrac{(a_0 \plus{} a_1 \plus{} \ldots \plus{} a_{n \minus{} 1})(a_1 \plus{} a_2 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2(n^2 \minus{} 1)} \ge \dfrac{a_0a_n}{n^2} \minus{} \dfrac{a_n(a_1 \plus{} a_2 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2(n^2 \minus{} 1)}$

  $ \dfrac{(a_0 \plus{} a_1 \plus{} \ldots \plus{} a_{n \minus{} 1})(a_1 \plus{} a_2 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2(n^2 \minus{} 1)} \ge \dfrac{a_0a_n}{n^2} \plus{} \dfrac{a_n(a_1 \plus{} a_2 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2} \minus{} \dfrac{a_n(a_1 \plus{} a_2 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2 \minus{} 1}$

  $ \dfrac{(a_0 \plus{} \ldots \plus{} a_{n \minus{} 1})(a_1 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2 \minus{} 1} \plus{} \dfrac{a_n(a_1 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2 \minus{} 1} \ge \dfrac{(a_0 \plus{} \ldots \plus{} a_{n \minus{} 1})(a_1 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2} \plus{} \dfrac{a_n(a_0 \plus{} \ldots \plus{} a_{n \minus{} 1})}{n^2}$

  $ \left( \dfrac{a_0 \plus{} \ldots \plus{} a_{n \minus{} 1}}{n \plus{} 1} \plus{} \dfrac{a_n}{n \plus{} 1} \right) \left( \dfrac{a_1 \plus{} \ldots \plus{} a_{n \minus{} 1}}{n \minus{} 1} \right) \ge \left( \dfrac{a_0 \plus{} \ldots \plus{} a_{n \minus{} 1}}{n} \right) \left( \dfrac{a_1 \plus{} \ldots \plus{} a_{n \minus{} 1}}{n} \plus{} \dfrac{a_n}{n} \right)$

  $ \dfrac{a_0 \plus{} a_1 \plus{} \ldots \plus{} a_n}{n \plus{} 1} \times \dfrac{a_1 \plus{} a_2 \plus{} \ldots \plus{} a_{n \minus{} 1}}{n \minus{} 1} \ge \dfrac{a_0 \plus{} a_1 \plus{} \ldots \plus{} a_{n \minus{} 1}}{n} \times \dfrac{a_1 \plus{} a_2 \plus{} \ldots \plus{} a_n}{n}$[/hide]

[hide="Solution"] This inequality, after algebraic manipulation, makes us prove that $\frac{(a_{0}+...a_{n-1})(a_{1}+...a_{n})}{n^{2}} \ge a_{0}a_{n}$.
Lemma 1. We show that $a_{0}a_{n} \le a_{i}a_{n-i}$.
We have the inequalities:
$a_{i}a_{i+2} \le a_{i+1}^{2}$,
$a_{i+1}a_{i+3} \le a_{i+2}^{2}$,
...
$a_{n-2}a_{n} \le a_{n-1}^{2}$.
Multiplying all the inequalities and dividing, we get the desired result.

Now, from our original LHS, we see that $\frac{(a_{0}+...a_{n-1})(a_{1}+...a_{n})}{n^{2}} \ge ((a_{0}...a_{n-1})(a_{1}...a_{n}))^{1/n}$, which is $((a_{0}a_{n})(a_{1}a_{n-1})...(a_{n-1}a_{1}))^{1/n} \ge a_{0}a_{n}$. [/hide]


Let $ f(x) \equal{} \prod^n_{k\equal{}1} (x \minus{} a_k) \minus{} 2,$ where $ n \geq 3$ and $ a_1, a_2, \ldots,$ an are distinct integers. Suppose that $ f(x) \equal{} g(x)h(x),$ where $ g(x), h(x)$ are both nonconstant polynomials with integer coefficients. Prove that $ n \equal{} 3.$

[quote=subham1729]I don't know if there is any direct argument or not but for me it's coming $12$ straight forward cases, showing just one case others are similar.Suppose $g(a_1)=-2,g(a_2)=2,g(a_3)=1,g(a_4)=1$ so now $a_2=x,a_4=x+1\implies a_3=x-1\implies 2|3$ absurd.Similarly we can show this contradiction with all cases.[/quote]

Could you explain more, i don't understand your solution :(

This is due to $f(k) = -2$ for at least $n$ values of $k$, but because $2$ is prime, we can only have $\pm 1$ and $\pm 2$ as factors.


calculus
integration
logarithms
calculus computations

first note that
$ \ln (1 \minus{} x^{2}) \equal{} \minus{} \sum_{n \equal{} 1}^{\infty} \frac {x^{2n}}{n}$
since $ |x| < 1$
thus it's enough to calculate integral like this:
$ \int_{0}^{1} x^{\alpha} \ln x dx$ note that it's equal to $ \equal{} \minus{}\frac{1}{(\alpha \plus{} 1)^{2}}$
thus we need to calculate sum
$ \minus{} \sum _{n \equal{} 1}^{\infty} \int_{0}^{1}\ln x \frac {x^{2n}}{n} \equal{} \sum _{n \equal{} 1}^{\infty} \frac {1}{n(2n \plus{} 1)^{2}}$
last sum can be calculated by simple algebraic manipulation.


analytic geometry
geometry
incenter
ratio
vector

I found on mathworld and wikipedia that the coordinates of the [b]incenter[/b] of a triangle is
$ (\frac{ax_A \plus{} bx_B \plus{} cx_C}{a \plus{} b \plus{} c}, \frac{ay_A \plus{} by_B \plus{} cy_C}{a \plus{} b \plus{} c})$
(where $ x_A$ is the x coordinate of point A, and $ a$ is the length of side opposite of A).
Is there an elegant (yet rigorous) proof for this?

Also while I'm at it, is there also an elegant proof that the coordinates of the [b]centroid[/b] is
$ (\frac{x_A \plus{} x_B \plus{} x_C}{3}, \frac{y_A \plus{} y_B \plus{} y_C}{3})$?

both of these [i]seem[/i] intuitive, but I don't have enough skills to come up with a rigorous proof.

In fact, in general, what are other centers of triangles with a nice formulas for coordinates or proofs for the coordinates?

For the [i]centroid[/i]:
Take a triangle $ ABC$. Name its vertices as $ A%Error. "ARROW" is a bad command.
(x_1,y_1)$ , for $ B%Error. "arrow" is a bad command.
(x_2,y_2)$ and similarly for $ C$.
let $ D$ be midpoint of $ AB$.its coordinates are $ [(\frac {x_1 + x_1}{2}),(\frac {y_2 + y_2}{2})]$
now, section formula says, if a line is divided internally in the ratio $ m_1: m_2$ then the coordinates for the point $ P$ where it is divided are $ [(\frac {m_1x_2 + m_2x_1}{m_1 + m_2}),(\frac {m_1y_2 + m_2y_1}{m_1 + m_2})]$
And we know that median is divided in ratio $ 2: 1$. Take segment $ CD$ and apply section formula as you have coordinates of $ D$ and $ C$ and the ratio. And you will get the required result.

[i]for practice try to prove the section formula[/i] stated above.doesnt require much mathematics, just application of known thngs.

Actually the formula for that centroid is the median already.

[quote="Nguyen Ngoc Linh"]We can easily prove those two formulas by using vector.[/quote]

Yes, vectors are nice for stuff like this.

Stepping stone equation for the incenter:
$ \vec{I}_{ABC} \equal{} \frac {[BCI]}{K}\vec{A} \plus{} \frac {[ACI]}{K}\vec{B} \plus{} \frac {[ABI]}{K}\vec{C}$, where $ [XYZ]$ denotes the area of $ \triangle XYZ$ and $ K \equal{} [ABC]$.


Hey, why the heck not? I'll post a new problem everytime one is solved.

Arithmatic - Open

1. Let x be the result when the digits of w are reversed and let $y=x-w$. Let z be the result when the digits of y are reversed and let $n=y+z$. Find $\frac{n}{10}$ for $w=1089$.

2. Express $(0.202202202202202...)_{3}$ in base 2 with repeating digits, [b]not[/b] as a fraction.

#1 is correct.

Algebra I - Focus on Rational Expressions

1. Simplify: $\frac{\frac{m^{3}-m^{2}n}{6m}}{\frac{5n-5m}{18}}$.

[hide]$\frac{\frac{(m-1)^{2}n}{6}}{\frac{5n-5m}{18}}$[/hide]
is that it?
-jorian

Umm.. [b]complex[/b] fractions aren't simplified and I have no idea what you did to your numerator. Before you post your answers, please check them by plugging in numbers for m and n and see if it is equal to the original term.

i crossed out the m squared and the 6m
-jorian

Somehow I don't think $m^{3}n-2m^{2}n+mn$ is equal to $m^{3}-m^{2}n$ though.

[quote="jhredsox"][hide]$\frac{\frac{m^{2}(m-1)n}{6m}}{\frac{5n-5m}{18}}$[/hide]
where do u go from there?

-jorian[/quote]

This answer was close...shouldn't $(m-1)n$ though.

I mean the answer is close, but the (m-1)n term is wrong.

Need I remind you of http://www.artofproblemsolving.com/Forum/viewtopic.php?t=115949


Did anyone solve it? It seemed inpenetratable to me.

Let's continue discussing the problem where it comes from, namely at http://www.mathlinks.ro/Forum/viewtopic.php?t=5549 ...

  darij