group theory
abstract algebra
linear algebra
matrix
modular arithmetic
Galois Theory
superior algebra

We say that the rank of a group $ G$ is at most $ r$ if every subgroup of $ G$ can be generated by at most $ r$ elements. Prove
that here exists an integer $ s$ such that for every finite group $ G$ of rank $ 2$ the commutator series of $ G$ has length less than $ s$.

[i]J. Erdos[/i]

Do i understand correctly this problem? Can this problem be reformulated as: if given finite group $G$, such that for every subgroup $H\subseteq G, \exists a, b\in H: H= <a, b>$, then we need to prove that exists integer $s$ not depending on $G$, such that $G^{(s)}=\{e\}$.

So is next (simpler) problem true: if given finite group $G$, such that for every subgroup $H\subseteq G, \exists a, b\in H: H= <a, b>$, then we need to prove that $G'\not= G$.

To prove this problem we need to prove problems $A$ and $B$.

Problem $A$

Prove that $\exists s\in\mathbb{N}$, such that for every finite solvable group $G:rk G\leq 2$, then $G^{(s)} = \{e\}$.

Problem $B$

Prove that every finite group $G:rk G\leq 2$ is solvable.

Let $s\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every finite solvable group $G:rk G\leq 2$, we have that $G^{(s)}=\{e\}$.

Let $s_1\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every finite Abelian group $A: rk A\leq 2$ and finite solvable group $G\subseteq Aut(A):rk G\leq 2$, we have that $G^{(s_1)}=\{e\}$.

Let $s_2\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every prime number $p$, finite Abelian $p$ group $A: rk A\leq 2$ and finite solvable group $G\subseteq Aut(A):rk G\leq 2$, we have that  $G^{(s_2)}=\{e\}$.

Let $s_3\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every number $n\in \mathbb{N}$, prime number $p$ and finite solvable group $G\subseteq GL(2,\mathbb{Z}_{p^n}) :rk G\leq 2$, we have that $G^{(s_3)}=\{e\}$.

Let $s_4\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every number $n\in \mathbb{N}$, prime number $p$ and finite solvable group $G\subseteq SL(2,\mathbb{Z}_{p^n}):rk G\leq 2$, we have that $G^{(s_4)}=\{e\}$.

Denote for every $n$ and prime number $p$ subgroups $X_i(p,n)=X_i:=\left\{\begin{pmatrix}a+1 & d\\ b &c+1\end{pmatrix}\in SL(2,\mathbb{Z}_{p^n})|a,b,c,d\in p^i\mathbb{Z}_{p^n}\right\}\subset SL(2,\mathbb{Z}_{p^n})$. Easy to see that $\{e\}=X_n<X_{n-1}<...<X_1<X_0=SL(2,\mathbb{Z}_{p^n})$ and $X_i$ is $p$ group.

Lemma $A$:

Prove that $\forall n-2\geq i\geq 2, X_i\lhd X_2$, $X_i/X_{i+2}\cong \mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}, \forall n-1\geq i\geq 2, X_{i+1}/X_{i+2}\cong \mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}$.

Proof:

First we need to prove that $\forall i>0, |X_i| = p^{3(n-i)}$. It is true, because $\forall (a,b,d)\in p^i\mathbb{Z}_{p^n}\times p^i\mathbb{Z}_{p^n}\times p^i\mathbb{Z}_{p^n},\exists c\equiv\frac{1-bd}{a+1}-1\pmod {p^n}$ easy to see that $c\in p^i\mathbb{Z}_{p^n}$, $\begin{pmatrix}a+1 & d\\ b &c+1\end{pmatrix}\in SL(2,\mathbb{Z}_{p^n})$, so $\begin{pmatrix}a+1 & d\\ b &c+1\end{pmatrix}\in X_i$, so $|X_i| = | p^i\mathbb{Z}_{p^n}\times p^i\mathbb{Z}_{p^n}\times p^i\mathbb{Z}_{p^n}| = p^{3(n-i)}$. Easy to check that $\forall i\geq 2, \forall A, A'\in X_i, [A,A']\in X_{i+2}$, so $X_i'\subseteq X_{i+2}$. So we can prove that $\forall n-2\geq i\geq 2, X_i\lhd X_2$, $X_i/X_{i+2}$ is Abelian and $\forall i\geq 2$, $X_i/X_{i+1}$ is Abelian. Easy to see that $\forall n-2\geq i\geq 2, \forall g\in X_i\setminus X_{i+1}, g^p\in X_{i+1}/X_{i+2}$, so $X_i/X_{i+2}\cong \mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}$ and $\forall n-1\geq i\geq 2, X_{i+1}/X_{i+2}\cong \mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}$. $\Box$

Sequence $A$:

Prove that $\forall i<n,g\in X_i\setminus X_{i+1}$, then we have that $g^p\in X_{i+1}\setminus X_{i+2}$.

Let $s_5\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every number $n\in \mathbb{N}$, prime number $p$ and finite solvable $p$ group $G\subseteq X_2=X_2(p,n) :rk G\leq 2$, we have that  $G^{(s_5)}=\{e\}$.

Let $s_6\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every prime number $p$ and finite solvable $p$ group $G$, such that $\exists \{e\}<N_k<...<N_0=G: N_i\lhd G, \forall 0\leq i\leq k-2, N_i/N_{i+2}\cong \mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}, N_i/N_{i+1}\cong\mathbb{Z}_p\oplus\mathbb{Z}_p$, then we have that $G^{(s_6)}=\{e\}$.

Let $s_7\in \mathbb{Z}\cup\{\infty\}$ is minimal number such that for every numer $n\in \mathbb{N}$, prime number $p$ and finite solvable $p$ group $G$, such that $\exists \lambda, \tau\in \mathbb{Z}_{p^n} : G=\left\langle\begin{pmatrix}1 & 0\\ \lambda &1\end{pmatrix}\right\rangle\left\langle\begin{pmatrix}1 & \tau\\ 0 &1\end{pmatrix}\right\rangle\subset SL(2,\mathbb{Z}_{p^n})$, we have that $G^{(s_7)}=\{e\}$.

Lemma 1

Prove that $s\leq s_1+2$.

Proof to lemma 1:

Lemma:

Let given group $G$ and $N\triangleleft G$. Prove that $G/Z(N)\subseteq Aut(N)$. (Where $Z(N) = \{g\in G: \forall x\in N, gx=xg\}$).

Proof:

Denote homomorfism $\pi: G\to Aut(N)$ where $\forall g\in G, x\in N, \pi(g)(x) = gxg^{-1}$. Easy to see that $\ker\pi = Z(N)$, so $G/Z(N)\cong \pi(G)\subseteq Aut(N)$. $\Box$

Let given finite solvable group $G:rkG\leq 2$. Let $\nu\in\mathbb(Z) : G^{(\nu)}\not= \{e\}$, $G^{(\nu+1)} = \{e\}$. If $\nu<1$, then $G^{(s_1+2)} =\{e\}$, so we can think that $\nu\geq 1$. Let homomorfism $\pi: G\to G/G^{(\nu)}$. From lemma we can get that $G_1=G/Z(G^{(\nu)})\subseteq Aut(G^{(\nu)}), G_2=\pi(G)/Z(\pi(G^{(\nu-1)}))\subseteq Aut(\pi(G^{(\nu-1)})$, $rk G_1, rkG_2\leq 2$. From defenition of $s_1$ we can get that $G_1^{(s_1)}=G_2^{(s_1)}=\{e\}$, so $G^{(s_1)}\subseteq Z(G^{(\nu)})$, $\pi(G^{(s_1)})=(\pi(G))^{(s_1)}\subseteq Z(\pi(G^{(\nu-1)}))$. So $\forall g\in G^{(s_1)}, x_1\in G^{(\nu)}, x_2\in G^{(\nu-1)}, [g,x_1]=\{e\}, [g,x_2]\in G^{(\nu)}$, so $\forall g_1, g_2\in G^{(s_1)}, x\in G^{(\nu-1)}, [[g_1,g_2],x]=\{e\}$, so $[G^{(s_1)},G^{(s_1)}]\subseteq Z(G^{(\nu-1)})$ and $G^{(s_1+1)}\subseteq Z(G^{(\nu-1)})$. Easy to see that $G^{(\nu-1)}\nleq Z(G^{(\nu-1)})$, so $s_1+1\geq \nu$, $\nu+1\leq s_1+2$ and it finish proof of lemma 1. $\Box$

Lemma 2

Prove that $s_1\leq s_2$.

Proof of lemma 2:

Let given finite Abelian group $A: rk A\leq 2$ and finite solvable group $G\subseteq Aut(A):rk G\leq 2$. Denote for every prime $p||A|$ group $A_p$ - Sylow $p$ subgroup of $A$. Easy to see that $\forall g\in G, g(A_p) = A_p$. Denote for every prime $p||A|$ homomorfisms $\pi_p: G\to Aut(A_p)$, where $\forall a_p\in A_p, \pi_p(g)(a_p) = g(a_p)$, let $K_p = \ker\pi_p$. $\prod_p A_p = A$, so $\cap_p K_p = \{e\}$. Easy to see that $\forall p||A|, rk G/K_p, rk A_p\leq 2, G/K_p\cong \pi_p(G)\subseteq Aut(A_p)$, so from defenition of $s_2$, $(G/K_p)^{(s_2)} = \{e\}$, so $G^{(s_2)}\subseteq \cap_p K_p = \{e\}$. $\Box$

Lemma 3

Prove that $s_2\leq s_3+2$.

Proof of lemma 3:

Let given prime number $p$, finite Abelian $p$ group $A: rk A\leq 2$ and finite solvable group $G\subseteq Aut(A):rk G\leq 2$. Let $n\geq k\in\mathbb{N} : A\cong \mathbb{Z}_{p^n}\oplus\mathbb{Z}_{p^k}$. Denote $A_0 = A^k = \{a^k|a\in A\}$, easy to see that $A_0\cong\mathbb{Z}_{p^{n-k}}$, $\forall g\in G, g(A_0) = A_0$. Denote homomorfism $\pi: G\to Aut(A_0)$, where $\forall g\in G, a_0\in A_0, \pi(g)(a_0) = g(a_0)$, let $K = \ker\pi$. $G/K\cong \pi(G)\subseteq \mathbb{Z}_{p^{n-k}} = Aut(\mathbb{Z}_{p^{n-k}}) = (\mathbb{Z}_{p^{n-k}})^{\times}$, so $G'\subseteq K$. Easy to see that $A/A_0\cong\mathbb{Z}_{p^k}\oplus\mathbb{Z}_{p^k}$, denote homomorfism $\psi: G\to Aut(A/A_0)$, where $\forall g\in G, xA_0\in A/A_0, \psi(g)(xA_0) = g(x)A_0$, let $L=\ker\psi$, $G/L\cong\psi(G)\subseteq A/A_0\cong\mathbb{Z}_{p^k}\oplus\mathbb{Z}_{p^k}$, $rk G/L\leq 2$, so from defenition of $s_3, (G/L)^{(s_3)} = \{e\}$, so $G^{(s_3)}\subseteq L$. In addition $G^{(s_3+1)}\subseteq K\cap L$. Easy to check that $K\cap L$ is Abelian, so $G^{(s_3+2)} = \{e\}$. $\Box$

Lemma 4

Prove that $s_3\leq s_4+1$.

Proof of lemma 4:

Let given number $n\in \mathbb{N}$, prime number $p$ and finite solvable group $G\subseteq GL(2,\mathbb{Z}_{p^n}) :rk G\leq 2$. Easy to see that $G'\subseteq (GL(2,\mathbb{Z}_{p^n}))'\subseteq SL(2,\mathbb{Z}_{p^n})$, $rk G'\leq 2$, so from defenition of $s_4, G^{(s_4+1)} = \{e\}$. $\Box$

Lemma 5

Prove that $s_4\leq s_5+6$.

Proof of lemma 5:

Let given number $n\in \mathbb{N}$, prime number $p$ and finite solvable group $G\subseteq SL(2,\mathbb{Z}_{p^n}):rk G\leq 2$.

Lemma $(a)$ :

Prove that $X_1\lhd X_0$, $X_0/X_1\subseteq SL(2,\mathbb Z_p) = SL(2,p)$.

Proof:

Denote homomorfism $\pi: X_0\to SL(2,p)$, where $\forall x = \begin{pmatrix}a & d\\ b &c\end{pmatrix}\in SL(2,\mathbb{Z}_{p^n})$, $\pi(x) = \begin{pmatrix}a_p & d_p\\ b_p &c_p\end{pmatrix}\in SL(2,p)$, $a_p,b_p,c_p,d_p\in \mathbb{Z}_p : a\equiv a_p\pmod p, b\equiv b_p\pmod p, c\equiv c_p\pmod p, d\equiv d_p\pmod p$. Easy to see that $X_1 = \ker\pi$, so $X_1\lhd X_0$, $X_0/X_1\cong \pi(X_0) \subseteq SL(2,p)$. $\Box$

Lemma $(b)$:

Let given solvable group $G: G\subseteq SL(2,p)/Z(SL(2,p)) = PSL(2,p)$. Prove that $G^{(4)} = \{e\}$.

Proof:

It is easy sequense of Theorem $1.1$ from http://www.academia.edu/1816978. $\Box$

Sequence:

Let given solvable group $G: G\subseteq SL(2,p)$. Prove that $G^{(5)} = \{e\}$.

Denote homomolrfism $\xi: X_0\to X_0/X_1$, from lemma $(a)$, $X_0/X_1\subseteq SL(2,p)$, so $\xi(G)\subseteq SL(2,p)$, $\xi(G)$ is solvable, so from lemma $(b)$, $(\xi(G))^{(4)}\subseteq Z(SL(2,p))$ and $(\xi(G))^{(5)} = \{e\}$, so $G^{(5)}\subseteq X_1$. Let's prove that $X_1'\subseteq X_2$. $\forall x=\begin{pmatrix}a & d\\ b &c\end{pmatrix}, x'=\begin{pmatrix}a' & d'\\ b' &c'\end{pmatrix}\in X_1$, easy to check that $[x,x'] = \begin{pmatrix}a & d\\ b &c\end{pmatrix}\begin{pmatrix}a' & d'\\ b' &c'\end{pmatrix}\begin{pmatrix}c & -d\\ -b &a\end{pmatrix}\begin{pmatrix}c' & -d'\\ -b' &a'\end{pmatrix}\in X_2$, so $[X_1,X_1]\subseteq X_2$, $X_1'\subseteq X_2$. So $G^{(6)}\subseteq X_2$, $rk G^{(6)}\leq 2$, so from defenition of $s_5$, $G^{(6+s_5)}=\{e\}$. $\Box$

Lemma 6

Prove that $s_5\leq s_6+1$.

Proof of lemma 6:

Let given number $n\in \mathbb{N}$, prime number $p$ and finite solvable $p$ group $G\subseteq X_2=X_2(p,n) :rk G\leq 2$. Denote groups $N_i=X_i\cap G$, from lemma $A$, $N_i\lhd G$. Let $j: G\subseteq X_j, G\nleq X_{j+1}$, so $N_j = G$. From $rk G\leq 2$, lemma $A$ and sequence $A$ we get that $\forall n-2\geq i\geq j$, $N_i/N_{i+2}\cong\mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}\vee\mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p}\vee\mathbb{Z}_{p^2}\vee\mathbb{Z}_{p}\oplus\mathbb{Z}_{p},\forall n-1\geq i\geq j, N_{i}/N_{i+1}\cong \mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\vee\mathbb{Z}_{p}$. From sequence $A$ easy to see that if for some $n-1\geq i\geq j+1, N_{i}/N_{i+1}\cong\mathbb{Z}_{p}$, then $N_{i-1}/N_{i+1}\cong\mathbb{Z}_{p^2}$ and so $N_{i-1}/N_{i}\cong\mathbb{Z}_{p}$. So $\exists k:\forall n>i\geq k, N_{i}/N_{i+1}\cong\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}$ and $\forall j\leq i< k, N_{i}/N_{i+1}\cong\mathbb{Z}_{p}$. $rk N_k\leq 2$, from sequence $A$ we can get that $\forall n-2\geq i\geq k, N_{i}/N_{i+2}\cong\mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}$, so from defenition of $s_6$, $(N_k)^{(s_6)} = \{e\}$. From sequence $A$ we can get that $\forall l\in\mathbb{Z}, g\in G\setminus N_{j+1}, g^{p^l}\in N_{j+l}\setminus N_{j+l+1}$, so $G/N_k\cong \mathbb{Z}_{p^k}$, so $G'\subseteq N_k$ and $G^{(s_6+1)} = \{e\}$. $\Box$

Lemma 7

Prove that $s_6\leq s_7+6$.

Proof of lemma 7:

Let given prime number $p$ and finite solvable $p$ group $G$, such that $\exists \{e\}<N_k<...<N_0=G: N_i\lhd G, \forall 0\leq i\leq k-2, N_i/N_{i+2}\cong \mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}, \forall 0\leq i\leq k-1, N_i/N_{i+1}\cong\mathbb{Z}_p\oplus\mathbb{Z}_p$.

Lemma $7.1$:

Prove that for every subgroup $F\subseteq G$, $\exists i: N_i\subseteq F$, $F/N_i$ is cyclic.

Proof:

Let $i: N_i\subseteq F, N_{i-1}\nleq F$. Define groups $F_i = N_i\cap F$ let $r: F\subseteq N_r, F\nleq N_{r-1}$ . Let's prove that $\forall r\leq j<i, F_j/F_{j+1}\cong\mathbb{Z}_p$. Easy to see that enough to prove that if for some $u, F_u/F_{u+1}\cong\mathbb{Z}_p\oplus\mathbb{Z}_p$, then $F_{u+1}/F_{u+2}\cong\mathbb{Z}_p\oplus\mathbb{Z}_p$ and this is true because $F_u/F_{u+2}\subseteq N_u/N_{u+2}\cong\mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}, F_{u+1}/F_{u+2}\subseteq N_{u+1}/N_{u+2}\cong \mathbb{Z}_p\oplus\mathbb{Z}_p$. So $\forall r\leq j<i, F_j/F_{j+1}\cong\mathbb{Z}_p$. $\forall 0\leq i\leq k-2, N_i/N_{i+2}\cong \mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}, \forall 0\leq i\leq k-1, N_i/N_{i+1}\cong\mathbb{Z}_p\oplus\mathbb{Z}_p$, so $\forall g\in F_r\setminus F_{r+1}, q\in\mathbb{N}, g^q\in F_{r+q}\setminus F_{r+q+1}$, so $F/N_i = F/F_i$ is cyclic. $\Box$

Lemma $7.2$:

Prove that $\exists a, b\in G\setminus N_1: G = <a><b>$ and $\forall i, <a^{p^i}><b^{p^i}>=N_i=G^i:=<\{g^i|g\in G\}>$.

Proof:

Take any $a, b\in G: <a, b>N_1 = G$. Easy to see that $\forall i\leq k-2, x, y\in N_i\setminus N_{i+1} : <x, y>N_{i+1} = N_i$, then $<x^p, y^p>N_{i+2} = N_{i+1}$, so $N_k = <a^{p^k}, b^{p^k}>$. So $<a>\cap <b> = \{e\}$ and $\#\{a^ib^j| i, j\in p^i\mathbb{Z}\} = p^{2(k-i+1)} = |N_i|$.
$\forall 0\leq i\leq k-2, N_i/N_{i+2}\cong \mathbb{Z}_{p^2}\oplus\mathbb{Z}_{p^2}, \forall 0\leq i\leq k-1, N_i/N_{i+1}\cong\mathbb{Z}_p\oplus\mathbb{Z}_p$, so $\forall i,j\in\mathbb{N}, g\in N_i\setminus N_{i+1}, g^j\in N_{i+j}\setminus N_{i+j+1}$ and so $<a^{p^i}><b^{p^i}>\subseteq G^i\subseteq N_i$, so $<a^{p^i}><b^{p^i}> = G^i = N_i$. $\Box$

Take $\lambda\in\mathbb{N} : N_{\lambda}$ is Abelian, but $N_{\lambda - 1}$ is not Abelian. Denote homomorfism $\pi: G\to Aut(N_{\lambda})$, where $\forall g\in G, x\in N_{\lambda}, \pi(g)(x) = gxg^{-1}$. Take $a, b$ from lemma $7.2$, $N_{\lambda} = <a^{p^{\lambda}}><b^{p^{\lambda}}>$. $N_{\lambda}$ is Abelian, so $N_{\lambda}\cong\mathbb{Z}_{p^n}\oplus\mathbb{Z}_{p^n}$, where $n=k+1- \lambda$. $\pi(G)\subseteq Aut(N_{\lambda})\cong GL(2,\mathbb{Z}_{p^n})$, so $\pi(G') = (\pi (G))'\subseteq SL(2,\mathbb{Z}_{p^n})$. From lemma $7.1$, $\exists i: N_i\subseteq G'$, $G'/N_i$ is cyclic. From defenition of $a, b$, $N_i = <a^{p^i}><b^{p^i}>$, $a^{p^i}\in Z(a), b^{p^i}\in Z(b)$, so in basis $a, b$ of $N_{\lambda}$ we get that $\pi(N_i) = \left\langle\begin{pmatrix}k & 0\\u  &1\end{pmatrix}\right\rangle\left\langle\begin{pmatrix}1 & f\\ 0 &v\end{pmatrix}\right\rangle\subseteq SL(2,\mathbb{Z}_{p^n})$, $\det\begin{pmatrix}1 & f\\ 0 &v\end{pmatrix}\equiv\det\begin{pmatrix}k & 0\\u  &1\end{pmatrix}\equiv 1\pmod {p^n}$, so $v\equiv k\equiv 1\pmod {p^n}$. So $\pi(N_i) = \left\langle\begin{pmatrix}1 & 0\\u  &1\end{pmatrix}\right\rangle\left\langle\begin{pmatrix}1 & f\\ 0 &1\end{pmatrix}\right\rangle\subseteq SL(2,\mathbb{Z}_{p^n})$ and from defenition of $s_7$, $\pi(N_i^{(s_5)}) = (\pi(N_i))^{(s_7)} =\{e\}$, so $N_i^{(s_7)}\subseteq\ker\pi = Z(N_{\lambda})$. $G^{(2)}\subseteq N_i$, so $G^{(s_7+2)}\subseteq Z(N_{\lambda})$. Let $\tau = \lambda - 1$. Denote homomorfism $\xi:G\to Aut(N_{\tau}/N_{\lambda})$, where $\forall g\in G, xN_{\lambda}\in N_{\tau}/N_{\lambda}, \xi(g)(xN_{\lambda}) = g(x)N_{\lambda}$. Easy to see that $\xi(G^{(s_7+2)})\subseteq GL(2,p)$, $\xi(G^{(s_7+2)})$ is $p$ group, $|GL(2,p)|=(p^2-1)(p^2-p)$, so $|\xi(G^{(s_7+2)})|\leq p$ and $\xi(G^{(s_7+3)})=\{e\}$, so $G^{(s_7+3)}\subseteq \ker\xi$ and so $\forall g\in G^{(s_7+3)}, xN_{\lambda}\in N_{\tau}/N_{\lambda}$ we have $gxN_{\lambda} = xgN_{\lambda}$. We know that $G^{(s_7+3)}\subseteq G^{(s_7+2)}\subseteq Z(N_{\lambda})$, so easy to check that $G^{(s_5+4)}\subseteq Z(N_{\tau})$. From defenition of $\lambda$, $N_{\tau}\nleq Z(N_{\tau})$, so $N_{\tau}\nleq G^{(s_7+4)}$. From lemma $7.1$, $\exists d: N_d\subseteq G^{(s_7+4)}, G^{(s_7+4)}/N_d$ is cyclic. $N_{\tau}\nleq G^{(s_7+4)}\Rightarrow\tau <d$. $N_d\subseteq N_{\tau}$, so $G^{(s_7+4)}/(N_{\tau}\cap G^{(s_7+4)})$ is cyclic and so $G^{(s_7+5)}\subseteq Z(N_{\tau})\cap N_{\tau}$, so $G^{(s_7+6)} =\{e\}$. $\Box$

Lemma 7

Prove that $s_7\leq 1$.

Proof of lemma 7:

Let given numer $n\in \mathbb{N}$, prime number $p$ and finite solvable $p$ group $G$, such that $\exists \lambda, \tau\in \mathbb{Z}_{p^n} : G=\left\langle\begin{pmatrix}1 & 0\\ \lambda &1\end{pmatrix}\right\rangle\left\langle\begin{pmatrix}1 & \tau\\ 0 &1\end{pmatrix}\right\rangle\subset SL(2,\mathbb{Z}_{p^n})$. Easy to see that $\forall\begin{pmatrix}a & d\\ b &c\end{pmatrix}\in G, a\equiv 1\pmod {p^n}$ and $\begin{pmatrix}1 & \tau\\ 0 &1\end{pmatrix}\begin{pmatrix}1 & 0\\ \lambda &1\end{pmatrix}\in G$, so $\lambda\tau + 1\equiv 1\pmod {p^n}$, $p^n|\lambda\tau$. So $\begin{pmatrix}1 & \tau\\ 0 &1\end{pmatrix}\begin{pmatrix}1 & 0\\ \lambda &1\end{pmatrix} = \begin{pmatrix}1 & \tau\\ \lambda &1\end{pmatrix} = \begin{pmatrix}1 & 0\\ \lambda &1\end{pmatrix}\begin{pmatrix}1 & \tau\\ 0 &1\end{pmatrix}$ and $G$ is Abelian, $G' = \{e\}$. $\Box$

Solution to Problem $A$:

From lemmas 1,..., 7 we get that $s\leq s_1+2\leq s_2+2\leq s_3+4\leq s_4+5\leq s_5 + 11\leq s_6+12\leq s_7+18\leq 19$. done

Solution of problem $B$:

Easy to see that if $G$ is finite simple group with $rk G\leq 2$ then $G$ is group of $2$-rank $\leq 2$. So from classification of simple groups of $2$-rank $\leq 2$ (see it in PDF here : http://projecteuclid.org/euclid.bams/1183533159), $G$ is one of next groups $L_2(q), L_3(q), U_3(q), U_3(4), A_7$ and $M_{11}$. And we only need to prove problem $B$ in this cases. $\Box$


function factorial calculus integration limit trigonometry logarithms

[quote="justmath11"] $\infty! = \sqrt{2\pi}$[/quote]

Those Ramanujan's formulas.............

[quote="justmath11"]This expression is somewhat interesting... is this expression "discovered" by Srinivasa Ramanujan?

$\infty! = \sqrt{2\pi}$

I am interesting to know how was this formula derived....  and if I were to understand this, what math subjects should I know in the first place?

The Thread "Most Beautiful Formulas" by Rodolphe2005 is very interesting... I realized that there are indeed many beautiful formulas yet they're challenging... :D[/quote]

This expression derives from a "Ramanujan summation" of the complex extension of the Gamma function, which is itself a real extension of the factorial function.  It is not actually literally "true," in the sense that $1 + 2 + 4 + 8 + ... = - \frac{1}{2}$ is not literally true, but as a renormalized product it has some meaning.

I suppose you would need to know a lot of complex analysis to really understand it.  I certainly don't.  :(

[quote="GoBraves"][quote="t0rajir0u"]
$1 + 2 + 4 + 8 + ... = - \frac{1}{2}$
[/quote]

??

Can you please explain that in more detail?[/quote]

Sorry, I wrote it wrong, it should be $-1$.  Anyway, it's a summation as a geometric series.  It's not technically a legal maneuver, but it's a "renormalized sum."

[quote="perfectnumber628"]is it sort of like the formula for the sum of a geometric series that converges, but this one doesn't converge?  so you can't really use the formula to sum it  :?[/quote]

Something like that.  Only more complicated.  Again, I don't pretend to really understand it at all :(

But I can say that this technique, as odd as it may seem, has practical applications in quantum mechanics where certain sums and products need to be "renormalized" to get rid of infinities that crop up - and when those renormalizations are made, the resulting theory actually produces verifiable results.   :D

Um im not sure but its this one[url]http://mathworld.wolfram.com/TauFunction.html[/url].

[quote="blahblahblah"][quote="RiemannZetaFunction"]Speaking of Ramanujan dose anybody want to explain the Tau Function?[/quote]

Are you sure you don't mean the $\Gamma$ (Gamma) function?[/quote]

hang on people, are we sure factorial infinity is the square root of 2 pi? Where is this result quoted, much less the proof..

And both the Tau function and the Gamma function are important here. If you didn't get the complex analysis explanations like most of us lay folk you'll be hard pressed to get aroung understanding the Tau function.
However the gamma function is defined for a complex number z as an integral
check it on
http://en.wikipedia.org/wiki/Gamma_function[/code][/list]

[quote="yasiru89"]

hang on people, are we sure factorial infinity is the square root of 2 pi? Where is this result quoted, much less the proof..[/quote]

The result is given at

http://mathworld.wolfram.com/InfiniteProduct.html

As a "regularized product," but I haven't been able to find a readable explanation of exactly what this is.

I got it! (OK I don't get most of it yet but atleast I know how it can be derived)
Chk out [b]Stirling's Formula[/b] in Wikipedia:-

[url]http://en.wikipedia.org/wiki/Stirling%27s_formula[/url]

It gives the approximation
n! ~ sqrt (2pi.n). (n/e)^n

which simplifies to the constant sqrt (2pi) when n= infinity is considered!
It's pretty weird but the formula does approximate factorials to an amazing degree of accuracy(from those I've evaluated) when n is large enough.

Also 1+2+3+4+....= -1/12

[quote="yasiru89"]It gives the approximation
n! ~ sqrt (2pi.n). (n/e)^n
which simplifies to the constant sqrt (2pi) when n= infinity is considered![/quote]

I don't think so.  $\lim_{n\to\infty}\sqrt{2\pi n}$ is infinite, not $\sqrt{2\pi}$.  Also, $\left(\frac ne\right)^n$ goes to infinity.

[quote="yasiru89"]consider the whole sum, regard square root of 2pi and square root n seperately, as n goes to infinity, square root n-> n
Then consider n^n as n-> infinity, n^n-> infinity. But multiples of infinity (speaking frankly) yield infinity.

However note that the denominator holds infinity too. Now instead of getting the multiple to give 0 or infinity (both of which are impossible when infinity/infinity is considered)-just cancel them out- then the sum approaches 1*square root 2pi

I've explained this very abstractly, working with zeros and infinities is very confusing as neither seem to take precedence.[/quote]

Nice try, but this doesn't work: the rate at which $n^n$ goes to infinity is vastly larger than that of $e^n$, and there is no way to conveniently make them disappear.  Infinities, like zeroes, don't just cancel.

True, but then I realised that were taking a limit as n approaches infinity. If we consider the exponential function it's the limiting value of (n+1/n)^n as n reaches infinity. So I figured why not plug it instead of e as the limit is considered anyway, I don't know how formally correct my method is but it gives something like
lim n->inf.   n^(n^2 + n + 0.5) . sq.root 2pi / (n+1)^(n^2)

(sorry I never got the hang of this script)

But if infinities don't cancel off as you say it's not much use I suppose....

[quote="quantum leap"][quote="justmath11"]
$\infty! = \sqrt{2\pi}$
[/quote]

When I saw that on t0rajir0u's signature, I considered it, then [i]really just thought he made it up[/i].  Complex analysis is looking more fun now though.  My favorite one-liner is still $\int_{-\infty}^{\infty} e^{-x^2}\,dx=\sqrt{\pi}$. :D[/quote]

Mathworld never lies!   :P

[quote="JBL"]The limit really does go to infinity, so nothing tricky that you do is going to make it not go to infinity.  Also, $e$ is the limit of $(1 + \frac 1 n)^n$ as $n$ grows very large, not $(n + \frac 1n)^n$.[/quote]

You misunderstand, I meant (n+1)/n...

Anyway I've been thinking about this and if you chk wikipedia

[url]http://en.wikipedia.org/wiki/Gamma_function[/url]

They give an identity
$\Gamma(z+1)=z \, \Gamma(z)\,.$

I tried integration by parts and somewhere along the evaluation you get something like infinity/infinity. If this is undefined the identity cannot be proved. Am I missing something?

Also you know any good books on complex analysis (this kind of stuff) on a introductory to intermediate level?

But $e^x>x^n$ for $x>1$ and constant $n$, which is why $\lim_{x\to\infty}{\frac{x^n}{e^x}=0}$
edit:ah, i misread, i thought you said the limit was undefined

Regarding the identity: $\Gamma (z+1)=z\Gamma (z)$
$\Gamma (z+1)= \int_0^\infty{t^{z}e^{-t}}\,dt$
Let $u=t^z$ and $dv=e^{-t}dt$, then
$\\\Gamma (z+1)= \int_0^\infty{t^{z}e^{-t}}\,dt\\ =-t^ze^{-t}|_{0}^{\infty}+z\int_0^\infty{t^{z-1}e^{-t}}\,dt\\ =z\Gamma (z)$

Masoud Zargar

[quote="Danbert"]\[ \int_0^\infty{t^{z-1}e^{-t}}\,dt  \]
\[ \begin{array}{ccc} u=e^{-t}& &dv=t^{z-1}dt\\ du=-e^{-t}dt& &v=\frac{t^z}z \end{array}  \]
\[ \left[e^{-t}\cdot\frac{t^z}z\right]_0^\infty+\frac1z\int_0^\infty{t^z\cdot e^{-t}}\,dt=\int_0^\infty{t^{z-1}e^{-t}}\,dt  \]
Deal with the stuff on the left first:
\[ \begin{array}{ccl} \left[e^{-t}\cdot\frac{t^z}z\right]_0^\infty&=&\left(\displaystyle\lim_{a\to\infty}{e^{-a}\cdot\frac{a^z}z}\right)-(0)\\ &=&\displaystyle\lim_{a\to\infty}{\frac{a^z}{ze^a} }\end{array}  \]
This is of the form $\frac\infty\infty$, but is equal to 0.  Just use L'Hopital's $z$ times.

That should clear up your problem.  It's true that $\frac\infty\infty$ is undefined, but the [i]limit[/i] exists (and is equal to zero).  Integrals to infinity are evaluated with limits, typically.  (I haven't seen any other way, but I'm only in Calc II).[/quote]

Sure that's what I got and that is what I did inorder to get that identity, but this fractional business isn't very satisfactory...

I mean consider

$lim_{x \to 0}{\frac{e^x - 1}{x}}$

as Δx gets smaller and smaller this tends to 1, not zero...Given that infinity over infinity is equivalent to zero over zero then wouldn't the limit be 1 and not zero?

Can someone explain this to me and then kindly get back to the questions in hand and present a proof that factorial infinity = square root 2pi

much appreciated. :?:

Look up L'Hopital's rule.

If $\frac{f(x)}{g(x)}$ has the form $\frac\infty\infty$, $\frac00$, etc. at $x=c$ then $\displaystyle\lim_{x\to c}\frac{f(x)}{g(x)}=\displaystyle\lim_{x\to c}\frac{f^\prime (x)}{g^\prime (x)}$  (I think that's stated correctly)

The limit you give goes to $\displaystyle\lim_{x\to0}\frac{e^x}{1}=1$ as expected.

[quote="yasiru89"]I mean consider

$lim_{x \to 0}{\frac{e^x - 1}{x}}$

as Δx gets smaller and smaller this tends to 1, not zero...Given that infinity over infinity is equivalent to zero over zero then wouldn't the limit be 1 and not zero?

Can someone explain this to me and then kindly get back to the questions in hand and present a proof that factorial infinity = square root 2pi

much appreciated. :?:[/quote]

Saying that "infinity over infinity is equivalent to zero over zero" is a very dangerous and basically untrue statement.  They're "equivalent" in the sense that they're both undefined without reference to an explicit limit.  Example:

$\lim_{x \to \infty} \frac{x}{x} = 1$.  This is an infinity over an infinity.

$\lim_{x \to 0} \frac{x}{x} = 1$.  This is a zero over a zero.  [b]However[/b]:

$\lim_{x \to \infty} \frac{x^2}{x} = \infty$.  This is an infinity over an infinity.

$\lim_{x \to 0} \frac{ \cos x - 1}{\sin x} = 0$.  This is a zero over a zero.

Basically, what I'm trying to say is that with the right limit, you can make either of those expressions equal to whatever you want.

As for the question at hand, I'm sorry if it sounds like I'm saying $\lim_{z \to \infty} z! = \sqrt{2 \pi}$, because that's not true.  This statement is absurd.  The limit is $\infty$ and you're not crazy.  :)

The expression isn't meant to be "true" as a normal statement - it's what's called a [b]Zeta-regularized product[/b].  I'm sorry I can't explain anymore, but I don't know more myself  :blush:

It's really quite mind-boggling.  Just don't worry about it anymore because I haven't found many answers about it myself  :(

That's why I said equivalent, couldn't find a better word...

You're right about the limit idea, it's always a swing between one, zero and infinity..
 But then again have you considered that when x goes to infinity x^2 --> x, and it becomes x/x = 1 as you say.

And also though L'Hopital's rule gives you a different version of the problem with calculus, it's basis is, just as t0rajir0u mentioned,
$\lim_{x \to 0} \frac{x}{x} = 1$

So to me what's most interesting is that calculus is based on these abstract ideas of limits.

But that isn't to say that this limit of factorial infinity being square root 2pi notion isn't letting up on me even if it leads back to the Riemann Zeta function based stuff.  :(

There are possibilities other that 0, 1 and infinity:  consider $\lim_{x\to \infty} \frac{x^2}{2x^2 +1}$.

Also, it is not true that as $x$ grows larger, $x^2 \to x$.  They both approach infinity, but neither one approaches the other (and in fact they get further and further apart).

Mathworld has a small, not very enlightening entry on Zeta-Regularized Product [url=http://mathworld.wolfram.com/Zeta-RegularizedProduct.html]here[/url].  The way it works is this:

You have to ignore issues of convergence.  Say we have an infinite product, $\prod_{n=1}^\infty \lambda_n$.  Define a function $\zeta_\lambda(s) = \sum_{n = 1}^\infty \lambda_n^{-s}$.  Then we have $\zeta_\lambda'(s) = \sum_{n = 1}^\infty -\ln(\lambda_n)\lambda_n^{-s}$ and so $\zeta_\lambda'(0) = \sum_{n = 1}^\infty -\ln(\lambda_n)$ and thus $e^{-\zeta_\lambda'(0)} = \prod_{n=1}^\infty \lambda_n$.  If you set $\lambda_n = n$, then the function $\zeta_\lambda$ is just the standard zeta function, and $\zeta'(0) = -\frac 12 \ln (2\pi)$, and the result follows.  The reason this doesn't "really work" is that we've messed around with convergences -- those equalities are equalities of formal power series, but there are places where I've defined functions that don't really make sense.  In particular, I've implicitly used an analytic extension of the function $\zeta_\lambda$ to the point 0, where our original definition (as an infinite sum) isn't valid.

By definition infinity^n, where n is a positive integer is infinity,
It's one of the few numbers (should the word apply) whose square is equal to the number along with 0 and 1.

I saw the entry on Mathworld earlier, didn't catch the exp part, thanks a million for clearing it up for me.
It's pretty cool...

[quote="quantum leap"][quote="justmath11"]
$\infty! = \sqrt{2\pi}$
[/quote]

When I saw that on t0rajir0u's signature, I considered it, then [i]really just thought he made it up[/i].  Complex analysis is looking more fun now though.  My favorite one-liner is still $\int_{-\infty}^{\infty} e^{-x^2}\,dx=\sqrt{\pi}$. :D[/quote]

Now this is a pretty interesting integral, how it's evaluated takes you totally by surprise.
It involves conversion to polar coordinates by taking the square of the integral. Then we would be dealing with the limits, this is basically the real number system squared which translates to evaluating the integral from zero to infinity as a the square of a real number is always greater than or equal to zero.
Now the change of variable would require a 2r coefficient to the integral, but since we're evaluating an area in polar coordinates this becomes r. And the integral becomes,

$\int_{0}^{\infty} e^{-r^2} r\,dr$

Now should we use a simple substitution, say u=r^2
du/dr = 2u and the integral simplifies to,

${1/2} \int_{0}^{\infty} e^{-u}\,du$

This gives half and plugging back to the polar integral gives
s^2= pi and hence s = square root pi

Lol... I thought it said "infinity is not equal to sqrt(2pi)" Shows what too much computer science does to you.

Anyways, aren't you supposed to "prove" it by saying something like

1*2*3*... = 2*3*4*... = 1*2*3*... *(2/1)*(3/2)*(4/3)*...

Or something? (actually, here this would give you infinity. shut up) I know that that's the method you use to "prove" 1+2+4+... = -1.

Maybe we could invent some form of multiplication-y p-adic numbers!

As near as I can tell, the proof is a lot more complicated than that.  For example, the other strange identity in my signature is proven using a "renormalization" of $\zeta(-1)$.

First of all, you will never, ever, ever, ever see it written that way in a reasonably advanced textbook, second of all, your post is almost completely devoid of content.  Please try and contribute something of value when you post.

Oh by the way,

[quote="GoBraves"][quote="t0rajir0u"]
$1 + 2 + 4 + 8 + ... = - \frac{1}{2}$
[/quote]

??

Can you please explain that in more detail?[/quote]

Let $S=1+2+4+8+...$
Then $2S=2+4+8+16+...$
So $S-2S=1$
$-S=1$
$S=-1$
$QED$

Of course, this proof doesn't "really work" either.

For $s\in \mathbb{R}_{\geq 1}$, the function
\[ f(s) = \sum_{n\geq 1} \frac{1}{n^s}  \]
defines an analytic function.  We can analytically continue this function to $\mathbb{C}\setminus\{0\}$ (obviously there is a pole at $s=0$!) by using the Gamma function.  (there are also simple 'intermediate' analytic continuations to, for example $\text{Re}(s)>0$).  Call the function which is analytic in $\mathbb{C}\setminus\{0\}$ and which agrees with $f$ on $\mathbb{R}_{\geq 1}$ $\zeta$ (e.g, the Riemann zeta function)

Now, there is a reflection formula for the Riemann zeta function relating $\zeta(s)$ to $\zeta(1-s)$.  If we use some easily calculated values of the Gamma function, we can find $\zeta(-1)$ from knowledge of $\zeta(0)$, which is what we want.  Of course none of this is really that easy, but this is the cliffs notes version.

[quote="t0rajir0u"][quote="ZetaX"][quote="t0rajir0u"]As near as I can tell, the proof is a lot more complicated than that.  For example, the other strange identity in my signature is proven using a "renormalization" of $\zeta(1)$.[/quote]
Sure that you don't mean $\zeta(-1)$¿ Seems to make more sense... (especially because $1+2+3+... \"=\" \zeta(-1) = -\frac{1}{12}$)[/quote]

Yes, that's what I mean :blush:

By the way, can you give us a sketch of the proof?[/quote]

How about this? I think I saw this on a post somewhere in this forum too. Although I'm not sure how you get it on a zeta summation.

consider a sum S where---
S= r - 2r^2 + 3r^3 - 4r^4 + ....
Sr= r^2 - 2r^3 + 3r^4- ....
S + Sr = r - r^2 + r^3 - r^4 +.....
It can be shown(just use the Sr+S sum)
S (1+r) = r (1+ (-r) + (-r)^2 + (-r)^3+...) = r / (1+r)

then S= r / (1+r)^2

Now take the limit as r goes to 1.
S= 1 - 2 + 3 - 4 + ..... = 1/(1+1)^2 = 1/4

Now let 1+2+3+4+.....= T

2( 2+4+6+8+.....) = 4T

& 1/4 + 4T = T , then 1/4= -3T
T= 1+2+3+4+5+.... = -1/12

Also I saw somewhere(on a forum in here actually) that for the geometric series
f(a)= 1 + a + a^2 +....
when a=2 can give the sum as 1/(1-2)=-1
But this can't be the case because for the geometric sum to n terms
S= a(1- r^n) / 1- r
as n goes to infinity r^n only goes to zero if and only if r is less than 1
 :!:

Also can anyone show me how to differentiate the Hadamard Product for the zeta function? I've always gotten it via Wallis product but this seems easier, just that I get an extra Euler constant somehow and answers don't match up!

@blahblahblah: the pole is at $s=1$ ;)

The formula that gives $\zeta(-1)$ and others is:
Set $\eta(x) : = \zeta(x) \cdot \pi^{-\frac{x}{2}} \cdot \Gamma \left(\frac{x}{2}\right)$
Then we have: $\eta (x ) = \eta (1-x)$ (poles will occure but in a "good" way).

A proof of this requires some knowledge (e.g. contour integration) about holomorphic/analytic functions and is somewhat long, so I will not post it.

[quote="ZetaX"]@blahblahblah: the pole is at $s=1$ ;)[/quote]

 :blush:


geometry
MATHCOUNTS
area of a triangle
Heron\u0027s formula

I dont really understand what "area enclosed by 3 lines" means....but usually counting techniques prove very useful in these types of problems.

If you know the lengths of the sides, you could use Heron's formula; else... Pick's works sometimes. But what about when the lines don't intersect on lattice points?! Then you HAVE to use Heron's or bh/2.

There was another triangle area formula but I've forgotten it. Anyone know?

Maybe it was Shoelace. Is Shoelace something to do with matrices?

Shoelace:
http://staff.imsa.edu/math/journal/volume2/articles/Shoelace.pdf

I guess it sort of has to do with matricies.

[quote="ccy"]Is there an efficient way to find the area of an area enclosed by 3 lines efficiently?

Or is the most efficient way finding the intersections and then using shoelace?

(based on Mathcounts 2005 Sprint #25)[/quote]

Isn't that a triangle. For that you can use either $\displaystyle \dfrac{1}{2}\ \text{Base}\cdot\text{Height}$ or $\sqrt{s(s-a)(s-b)(s-c)}$ where s is the semiperimeter and a, b, and c are the sides.

Of course it's a triangle, but what would be an efficient way to find the area given the equations of 3 lines?


group theory
abstract algebra
superior algebra
superior algebra unsolved

Hello,

Supposed that G is a simple connected algebraic group such that G/Z(G) is a abstract finite simple group, then whether can all automorphism of G/Z(G)  be  induced by automorphism of G?

Thanks!

If the quotient $G/Z(G)$ is finite, it's discrete- and that means that $Z(G)$ is an open and closed subgroup of $G$. $G$ is either abelian or not connected.

If we drop any connectedness hypothesis from $G$, there's something there.

hi,Jmerry, I only know a little about algebraic group, can you give a proof in detail? Thanks very much!

A proof of what? A clear question would help.

I have another question:

Let G be a simple connected algebraic group and t be a Frobenius morphism of G(i.e G_t is finite). Supposed that x and y are elements of T with order p, where T is a maximal tori. whether is the following true?
If x conjugate to y in Aut(G_t), then x conjugate to y in G_t .

[quote="rulin"]I only know a little about algebraic group[/quote]
You know more terminology than I do, based on your last post. I don't know the definitions or the standard techniques to answer that sort of question.

I am studying the Lie type simple groups in this term, and these can be describe as algebraic groups version, but I know a little about the toplogy, so......If you are interested in it, please refer to http://darkwing.uoregon.edu/~seitz/Lausanne.pdf


Solve the inequality $\frac{x(x+3)}{2x-5}\leq 0$`.

My first post on this cool new site... :D
I think that it becomes-
x(x+3)<=0
x+3<=0
x<=3
I hope that's right...

Close, you need to take the sign of all the terms. from -3 and under, they're all negative. between -3 and 0, 2 are negative. Between 0 and 2.5, 1 is negative. From 2.5 onwards, all are positive. Therefore, we have (-infinity,-3]U[0,2.5)

[quote="#H34N1"]Is there any way to do it besides sign analysis?[/quote]

Graph it.

[Not the preferred method]

Note that $2x-5 < 0$.
Hence $x < \frac{5}{2}$ and $x(x+3) \geq 0$.
So that $x \geq-3$ or $x \geq 0$.
Therefore, $x \in (-\infty,-3] U [0, \frac{5}{2}]$

You forgot to put a round bracket around the 5/2 instead of square, since function is undefined at that value.

Thanks,
I hope they notice that and it is clear from how it was shown that $x < \frac{5}{2}$.


function
analytic geometry
graphing lines
slope

:ninja:  Does anyone know any good tricks or tips about slope intercept form and advanced stuff about it?????????????????????????????????

This is the wrong forum to be asking such a question. (Correct me if I'm wrong).


advanced fields
advanced fields unsolved

Prove that $ [0,1]$ cannot be written as the union of a sequence of disjoint closed sets.

I'll do it for open sets.

Let $ [0,1]=A\cup B$ where $ A$ and $ B$ are disjoint, nonempty open sets.  Let $ 1\in B$ and so $ (1-\varepsilon,1]\subseteq B$ for some $ \varepsilon>0$ since $ B$ is open.  Now let $ c=\sup A$.  Clearly $ 0\leq c\leq 1$ and it follows by definition of $ c$ that $ (c-\varepsilon,c)\cap A\neq\emptyset$ and $ (c,c+\varepsilon)\cap B\neq\emptyset$ for any $ \varepsilon>0$.  Actually, $ (c,1]\in B$.  So $ c\in\bar{A}$ and $ c\in\bar{B}$.  Then $ c\in\bar{A}\cap\bar{B}=A\cap B=\emptyset$, a contradiction.

Just make a small modification to make it hold for closed sets.

[quote="JRav"]I'll do it for open sets.

Let $ [0,1] = A\cup B$ where $ A$ and $ B$ are disjoint, nonempty open sets.  Let $ 1\in B$ and so $ (1 - \varepsilon,1]\subseteq B$ for some $ \varepsilon > 0$ since $ B$ is open.  Now let $ c = \sup A$.  Clearly $ 0\leq c\leq 1$ and it follows by definition of $ c$ that $ (c - \varepsilon,c)\cap A\neq\emptyset$ and $ (c,c + \varepsilon)\cap B\neq\emptyset$ for any $ \varepsilon > 0$.  Actually, $ (c,1]\in B$.  So $ c\in\bar{A}$ and $ c\in\bar{B}$.  Then $ c\in\bar{A}\cap\bar{B} = A\cap B = \emptyset$, a contradiction.

Just make a small modification to make it hold for closed sets.[/quote]

I think you or me might've misunderstood it, maybe the title is misleading for me  :maybe: . Anyway I think that the problem should be rephrased to this: Show that the interval $ [0,1]$ cannot be written as a countably infinite disjoint of closed subintervals of $ [0,1]$.
[hide="idea"] if it would be possible, show that the set of endpoints of intervals is the perfect set, so it cannot be countable. [/hide]

[quote="JRav"]I'll do it for open sets.[/quote]

are you saying that the union of open sets cannot be closed?  i, for one, am shocked by this!

Perhaps I'm misunderstanding you, but if $ M\equal{}\mathbb{R}$, then $ (\minus{}\infty,1)\cup (0,\infty)\equal{}\mathbb{R}$, which is closed relative to itself.

No, I'm saying that what you proved is obvious.  The union of open sets cannot equal $ [0,1]$, because then $ [0,1]$ would be open as well.  There is no 'small' modification that will make that argument hold for closed sets.  So what you posted is useless, in addition to being overly convoluted.

Moreover, since $ [0,1] \equal{} \bigcup_{x\in [0,1]} \{x\}$, any 'proof' (e.g., yours) that doesn't use some sort of countability/uncountability argument will probably not get very far.

JRav, it's true that you have a habit of not reading questions very well and answering an easier variant instead of the question at hand.  Perhaps you should read more carefully.

The Baire category theorem or equivalent reasoning is the key here. See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=378533#378533]here[/url] for a proof.


Hello
Is this the correct way of thinking about this problem.

Since the current flows from + to -, i.e. clockwise in bottom loop, this current induces a magnetic field which flows OUT OF THE PAGE, OUTSIDE THE GIVEN LOOP. (i.e. outside the circuit). In order to combat this (faraday law), current must flow clockwise when switch is closed hence producing a magnetic field which opposes the bottom loop.

[img]http://i33.tinypic.com/1z6t6he.jpg[/img]

[quote="sanchit"]hey from which book is this ques from!!!!!!!!![/quote]

http://test.scripts.psu.edu/students/c/a/cao5021/ee/.../45791-UlabyISMCh06.pdf

You can also use Lenz's Law in this problem. The reasoning should turn out the same.


Putnam
group theory
abstract algebra
induction
geometry
geometric transformation
rotation

Suppose that a finite group has exactly $ n$ elements of order $ p,$ where $ p$ is a prime. Prove that either $ n\equal{}0$ or $ p$ divides $ n\plus{}1.$

Consider $ S \equal{} \{(g_1,...,g_p) | g_1...g_p \equal{} e\}$
By allowing first $ p\minus{}1$ variables to vary, we can see that $ |S| \equal{} |G|^{p\minus{}1}$.
We can count it by another way, either $ e$, elements of order $ p$, or there are some $ g_i \neq g_j$.
The first two cases add up to be $ n\plus{}1$, and the last case has to be divisible by $ p$, for any cyclic permutation of $ (g_1,..,g_p)$ still stays in S.
If $ p$ does not divide $ |G|$, $ n \equal{} 0$ by Lagrange's theorem.
Otherwise, by above inspection, $ p|n\plus{}1$

This was trivial to me- that's the standard argument used to prove existence of elements of order $ p$. A very disappointing A5.

For a generalization, see [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=562838#562838]here[/url].

I was a first time contestant this year and this is the only question I left feeling good about :blush:

They key insight was thinking about the order of identity.

On some generalisation (like Jmerry's post)
http://www.pitt.edu/~gmc/ch1/node7.html

[quote="Soarer"]Consider $ S \equal{} \{(g_1,...,g_p) | g_1...g_p \equal{} e\}$
By allowing first $ p \minus{} 1$ variables to vary, we can see that $ |S| \equal{} |G|^{p \minus{} 1}$.
We can count it by another way, either $ e$, elements of order $ p$, or there are some $ g_i \neq g_j$.
The first two cases add up to be $ n \plus{} 1$, and the last case has to be divisible by $ p$, for any cyclic permutation of $ (g_1,..,g_p)$ still stays in S.
If $ p$ does not divide $ |G|$, $ n \equal{} 0$ by Lagrange's theorem.
Otherwise, by above inspection, $ p|n \plus{} 1$[/quote]

You are awesome.

I looked at this problem and was like, "This is probably not hard for someone who knows group theory." Unfortunately, I do not.

Yeah, I felt a bit angry at the problem since it really didn't test ingenuity but rather the amount of math you've taken.

And the funny thing is I started studying group theory on my own just a week before the contest, and in the early morning (4am) of the contest day I was looking at problems and theorems that involved groups with elements having order $ p$. And, I just couldn't believe my eyes when I saw the question.  :huh:

[quote="Xevarion"]I'm angry because I've had a course in group theory and I still didn't get this problem. :o[/quote]

lol.  Same here.   :P

By the way, just to put a name to this result -- it's an immediate consequence of Sylow's theorems. If there are order $ p$ elements in $ G$, the number of $ p$-Sylows is equivalent to 1 mod $ p$; each $ p$-Sylow contains 1, so there are $ (kp\plus{}1)(p\minus{}1)  \equal{} kp^2 \plus{} (k\minus{}1)p \minus{} 1$ elements of order $ p$. The result follows. (But the graders might expect more than a citation of Sylow's theorems...)

That's a trap. That count doesn't apply if $ p^2$ divides the order of $ G$.

The result you want is still true, but it's not on the standard list of Sylow theorems.

[quote="Xevarion"]By the way, just to put a name to this result -- it's an immediate consequence of Sylow's theorems. If there are order $ p$ elements in $ G$, the number of $ p$-Sylows is equivalent to 1 mod $ p$; each $ p$-Sylow contains 1, so there are $ (kp \plus{} 1)(p \minus{} 1) \equal{} kp^2 \plus{} (k \minus{} 1)p \minus{} 1$ elements of order $ p$. The result follows. (But the graders might expect more than a citation of Sylow's theorems...)[/quote]

I don't understand. p-Sylow subgroups are not groups of order p, or can you provide a proof of number of subgroups of order p has to be 1 mod p?

[quote="Soarer"]I don't understand. p-Sylow subgroups are not groups of order p, or can you provide a proof of number of subgroups of order p has to be 1 mod p?[/quote]
Sorry, I was too hasty. $ p$-Sylows are of order $ p^k$ where $ p^k$ is the largest power of $ p$ which divides $ |G|$. Putting that in instead of $ p$ still works. And $ p$-Sylows contain only elements of order $ p$, and the set of all $ p$-Sylows contains all elements of order $ p$. And they intersect only at the identity.

jmerry: it's not 'standard' Sylow theorem that the order of a $ p$-Sylow is a power of $ p$? It only contains order $ p$ elements... Or am I missing something?

edit: Oh, wait, I see what's wrong. Ok ignore everything I just said. sorry.

One way I can prove Xevarion's claim is to use this A5 problem and the p-1 to 1 correspondence of order p elements and subgroup of order p ($ x \to <x>$). However, the claim really looks like Sylow III, is there any way to do it by group actions?

Xevarion, we didn't prove Cauchy's Theorem this tricky way in our algebra class.

Instead, we derived it as a consequence of Sylow's Theorem.

I feel that without knowing this argument beforehand, it is rather non-trivial to think of it.  Sure, the argument is easy (I think it is an exercise in Dummit and Foote that I had actually done!), but it is not easy to see it in half an hour if you haven't seen it before.

Hm...an alternate solution that doesn't seem to be given in the official solutions:

First note that the desired is equivalent to showing that the number of subgroups of order $ p$ is $ 1$ mod $ p$. Consider the set $ S$ of all subsets of $ G$ of size $ p$. Let $ G$ act on $ S$ by right-multiplication.

Lemma 1: The size of any orbit of $ S$ under $ G$ is either $ |G|$ of $ |G|/p$. In the latter case, the orbit contains a unique group of order $ p$.

Proof: Let $ N$ be the normalizer of an element $ X$ of $ S$. Then $ X$ is the union of orbits of $ N$ under its action on $ G$. These orbits correspond to cosets of $ N$, so $ X$ is the union of cosets of $ N$. Since $ X$ has size $ p$, the first part of the lemma follows by the orbit-stabilizer theorem. Now, for any orbit of size $ |G|/p$, the stabilizer of any given set in the orbit has size $ p$. Some set in the orbit contains the identity, and the stabilizer of this set must be contained in this set, since any element in the stabilizer must map the identity to another element of the set. Since the set and stabilizer have the same size, the set equals the stabilizer. Uniqueness then follows since every other element in the orbit is a coset of the stabilizer.

=====

Now let $ |G| \equal{} ap$. Now, suppose there are $ x$ orbits of size $ |G|\equal{}ap$ and $ y$ orbits of size $ |G|/p \equal{} a$. Then $ xap \plus{} ya \equal{} \binom{ap}{p}$ since there are $ \binom{ap}{p}$ total sets of size $ p$. We now have another lemma:

Lemma 2: $ \frac{\binom{ap}{p}}{a}$ is an integer and is congruent to $ 1$ mod $ p$.

Proof: It is equal to $ \frac{(ap\minus{}1)(ap\minus{}2)\ldots (ap\minus{}p\plus{}1)}{(p\minus{}1)(p\minus{}2)\ldots 1}$.

Thus we have $ xp\plus{}y\equal{}\frac{\binom{ap}{p}}{a}$. Taking mod $ p$ gives $ y \equiv 1$ by the previous lemma, which is what we wanted, so we are done.

=====

This is a modification of one of the proofs of Sylow's theorem that I have seen (consequently, also my favorite proof). I have also seen Frobenius' proof of Cauchy's theorem (the one given earlier in the thread) although I didn't think of how to use it to solve this problem. Someone told me the proof was by the proof of Cauchy's theorem before I had a chance to work on it, so I'm not sure how easy it is to consider proofs of Cauchy's theorem. However, we've now seen two different ways to modify proofs of Cauchy's theorem to the desired result of A5. I am skeptical of whether the inductive proof of Cauchy's theorem could be modified to give this, however, since some of the cases in the induction don't employ counting arguments and thus can't give information about the number of elements of order $ p$.

Though I'm not saying this was my favorite problem, it isn't an unfair problem, as some people are making it out to be. The result does appear to be somewhat known (it is cited in Herstein, at the very least) which is the main downside. If all you've seen is proofs of Cauchy's theorem, then you have to understand the proofs well to make the modifications similar to what jmerry made.

Again, I'm not saying it was a perfect problem, but no need to bash it.

[quote="Soarer"]Consider $ S \equal{} \{(g_1,...,g_p) | g_1...g_p \equal{} e\}$
By allowing first $ p \minus{} 1$ variables to vary, we can see that $ |S| \equal{} |G|^{p \minus{} 1}$.
We can count it by another way, either $ e$, elements of order $ p$, or there are some $ g_i \neq g_j$.
The first two cases add up to be $ n \plus{} 1$, and the last case has to be divisible by $ p$, for any cyclic permutation of $ (g_1,..,g_p)$ still stays in S.
If $ p$ does not divide $ |G|$, $ n \equal{} 0$ by Lagrange's theorem.
Otherwise, by above inspection, $ p|n \plus{} 1$[/quote]

I don't see why all of the cyclic permutations of a given p-tuple need to be unique.

Because $ p$ is prime.  There are lots of ways to make the argument from that -- e.g., consider $ k$ such that a cyclic rotation by $ k$ positions returns you the same tuple.  Suppose $ k$ is not divisible by $ p$.  Then there are integers $ m, n$ such that $ mk \equal{} np \plus{} 1$, so $ m$ rotations by $ k$ gives you the same thing you started with, but also a rotation by one position.  Equivalently, a subgroup of a group of prime size is either the whole group or the trivial group.

[quote="JBL"]Because $ p$ is prime.  There are lots of ways to make the argument from that -- e.g., consider $ k$ such that a cyclic rotation by $ k$ positions returns you the same tuple.  Suppose $ k$ is not divisible by $ p$.  Then there are integers $ m, n$ such that $ mk \equal{} np \plus{} 1$, so $ m$ rotations by $ k$ gives you the same thing you started with, but also a rotation by one position.  [/quote]

OK. I wish that was obvious to me like it is to everyone else apparently.

[quote="JBL"]Equivalently, a subgroup of a group of prime size is either the whole group or the trivial group.[/quote]
I agree, but how is that equivalent?

The group is $ C_p$ acting on $ p$-vectors by cyclic rotation.  The subgroup is generated by the element "rotate by $ k$ places."

I see--you're using the fact that if $ G$ is a finite group acting on a set $ X$ and we fix $ x \in X$, then the size of the orbit of x $ |Gx|$ divides $ |G|$. In our case G is the subgroup of the symmetric group $ S_p$ generated by the permutation $ \sigma \equal{} (1,2,...,p)$ and X is the set of all p-tuples of elements of G.

So then why is the order of S guaranteed to be |G|^p-1?

because any of the first $ p\minus{}1$ elements can get any of the $ |G|$ values and the last element is uniquely determined by the equation.

[quote=va2010]Here's another argument that doesn't seem to be given in this thread -- no binomial coefficients appear!

Assume there is at least one element $q$ of order $p$ -- if no such $q$ exists, we're done. Let
\[ A = \{ g \in G: gq \neq qg \text{ and } g \text{ has order dividing } p  \} \] and
\[ B = \{ g \in G: gq = qg \text{ and } g \text{ has order dividing } p  \}. \]

I claim that $p \mid |A|$, and $p \mid |B|$, which will imply the result, since \[ p \mid |A| + |B| = |\{g \text{ has order dividing } p\}| = |\{g \text{ has order } p\}| + 1 = n + 1. \]
Consider the function $f: A \mapsto A$ which takes $x \mapsto qxq^{-1}$. Observe that if $qx \neq xq$, then $q(qxq^{-1}) \neq (qxq^{-1})q$, so the function takes $A$ to $A$. Observe also that it's clearly injective, hence, $f$ induces a permutation of $A$, $\pi_A$. Note that for any $x$, $f^{p}(x) = q^{p} x q^{-p} = x$, and since $f(x) \neq x$, every cycle in the permutation in $\pi_A$ has size $p$, so $p \mid |A|$.

We use a similar argument for $B$. Consider the function $g: B \mapsto B$ which takes $x \mapsto xq$. Then, $g^{p}(x) = x$ again and $g(x) \neq x$, so all cycles in the permutation of $B$ induced by $g$ have size $p$, and $p \mid |B|$ so we may conclude.[/quote]

Beautiful and fresh solution.


What is the sum of all integers less than 100 with exactly 12 divisors?

[hide]
Just do some casework to find that the only numbers are 60, 72, 84, 90, 96.

The sum of these is $\boxed{402}$. [/hide]


Hey, Guys...the following problem from IMO 1959, the very first: Prove that the fraction (21n+4)/(14n+3) is irreducible for every natural number n.
...just can't get what is meant by the given solution: 3(14n+3)-2(21n+4)=1...I mean, what is their "sample" method?!...can't see through...tried to get the same...no chance. I searched for discussion of it in the forum, but without result.
Please, help my curiosity!

[quote="symplectic_manifold"]Prove that the fraction (21n+4)/(14n+3) is irreducible for every natural number n.
...just can't get what is meant by the given solution: 3(14n+3)-2(21n+4)=1...I mean, what is their "sample" method?![/quote]

It just means that these wo numbers are coprime from Bezout's theorem.

Pierre.

OK! Thank you very much, Pierre!
I couldn't imagine that an IMO problem can be that easy...but I broke my head over it, intuitively feeling it must be solved in few steps. I thought I had no creativity for it...or were just thick...but one cannot start creative process if he doesn't know certain facts! :D
I looked up the condition for two numbers to be coprime...now is everything clear! :blush:

[quote="symplectic_manifold"]
I couldn't imagine that an IMO problem can be that easy...[/quote]

This problem is quite 50 years old...
I think things have a bit changed since then :D

Pierre.

Pierre, can you explain, how do you apply Bezout's theorem to show that the numbers are coprime. I've tried to, but failed. Thank you very much.

gcd(21n+4, 14n+3) divides gcd(2(21n+4), 3(14n+3)), but the latter equals one because the two numbers are consecutive.

I know this solution (I found it myself some time ago). I'm interested in solution using Bezout's theorem.

Here with Bezout's theorem the following is meant, I think:
You can exactly that numbers represent as linear combination $ax+by$ for given $a,b$ that are multiples of $gcd(a,b)$. (and since here $1$ can be represented, you have that they are coprime)

Edit: I found a link: http://mathworld.wolfram.com/BezoutsTheorem.html


Find all triplets $ a,b,c \in Z$ such as for any natural number n we have
$ (a.2^n \plus{} b)\left| {(c^n \plus{} 1)} \right.$
I spend 2 hours to solve it but  :blush: . Please help me . :lol:

[quote="Pul de Algodoncito"]do you want to find some triplets, a triplet that does the job or all triplets of numbers?[/quote]
Find some triplets
$ (a,b,c) \in Z^3$

These work: $ (0,1,c); (0,2,2r\plus{}1);(0,\minus{}1,c); (0,\minus{}2,2r\plus{}1)$. But maybe you were looking for something not that trivial. Also, if $ a\equal{}0$, these are the only triplets that work. You may notice that, if $ a\equal{}0$, $ c^2\equiv \minus{}1\ mod\ b$. Now let $ r$ be the residue mod $ b$ such that $ r^2\equiv \minus{}1\ mod\ m$. Then $ r^4\equiv 1\ mod\ m$. Since $ c\equiv r\ mod\ m$ (so $ b|c^2\plus{}1$), then $ b|r^4\plus{}1\equal{}2$ and $ m\equal{}1,2,\minus{}1,\minus{}2$ yielding the solutions I gave.

I don't understand.Can you explain clearly?  My mistake : find all triplets  :blush:


trigonometry
calculus
calculus computations

hi,

i will be glad if somebody helps me to solve this problem ,please ,

[u]problem[/u]
x and y are real numbers .
z is a complex number such that $z = x+iy$
$z = x-iy$
(E) is an equation in C such that : $(E)^{:}z^{5}= z+(z)$

$a = \sqrt[4]{2 \times sin(\Pi\div 3)}$
$b = \sqrt[4]{2}$

express  the solutions of (E) using  a and b .
thanks in advance

[quote="Jimmy"]I think he wants you to solve the equation $z^{5}=z+\bar{z}$ in terms of $a$ and $b$.[/quote][hide="Hint."]$z^{5}=z+\overline z\Longrightarrow$ $z^{5}=\overline z^{5}$ $\Longleftrightarrow$ $z=0$ or $z=\omega \overline z\ ,$ where $\omega\in \{1,\alpha ,\alpha^{2}, \alpha^{3},\alpha^{4}\}\ ,\ \alpha =\cos\frac{2\pi}{5}+i\cdot\sin\frac{2\pi}{5}\ .$[/hide]


quadratics
calculus
derivative
analytic geometry
graphing lines
slope
conics

The smallest value of $x^2+8x$ for real values of $x$ is
\[ \text{(A)}\ -16.25\ \ \ \ \text{(B)}\ -16\ \ \ \ \text{(C)}\ -15\ \ \ \ \text{(D)}\ -8\ \ \ \ \text{(E)}\ \text{None of these} \]

Is it an equation where it equals 0?

Hou aboud [hide]d[/hide]

hiitsme, could you post a solution next time not just an answer?
[hide]I got [b]b[/b], using -b/2a to get that x is -4.  Plugging that into the equation we get 16-32=-16.[/hide]

Well, the quadratic formula is in the form:

$x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} \\ x = \frac{-b}{2a} \pm \frac{\sqrt{b^2-4ac}}{2a}$

Notice that the second half of the expression will determine the actual x intercepts. The left expression is the optimum x therefore, and the intercepts are always $\frac{\sqrt{b^2-4ac}}{2a}$ away from the optimum x.

The expression under the square root is the discriminant and it determines whether the number is real or not.

Or you can use calculator.

If you know how, that's what I mean.

:-D

[b]
How about using Geometer's Sketchpad?[/b]

[hide]
B
I guess calculus can be used here (we just started this), this is prolly too advanced for this forum but...

The derivative is
$2x + 8$
We want where the graph reaches a minimum (ie slope is 0).
$2x + 8 = 0$
$x = -4$
Since this is a parabola opening upward we know this must be a minimum and not a maximum.
Plugging -4 in:
$16 + 8(-4) = -16$
So B
[/hide]

well,the solutions are all the same i think

Can you get there with plain old simple algebra?

How do you prove the quadratic formula?  How can you use that here?

Also remember your Bible Stories ...

... Sorry poor joke .. but it is just another parabola!  $y=x^2+8x$ and see it is always greater than ....

Yea finding the vertex of the parabola will give the same answer.

[quote="cosinerburc"]you can also use the fact that x^2+8x=(x+4)^2-16>=-16[/quote]I like this solution the most. It is the simplest and uses no independent theorems (such as $ax^2+bx+c=0\Rightarrow{x}=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$).

$(x+4)^2\ge0\Rightarrow(x+4)^2-16\ge-16\Rightarrow{x}^2+8x\ge-16$, and equality is attained when $x=-4$, so the proof is complete.

[quote="hiitsme"]Oh I'm sorry, I thought is was to find x in x^2 + 8x = 0 ...  :blush:

And can you go into detail on what -b/2a is?[/quote]

[hide="solution"]$-\frac{b}{2a}$ is to find the maximum or minimum x value in a quadratic equation

$\frac{8}{2}=-4$

$16-32=16$

(B)[/hide]

[quote="jli"][quote="hiitsme"]Oh I'm sorry, I thought is was to find x in x^2 + 8x = 0 ...  :blush:

And can you go into detail on what -b/2a is?[/quote]

[hide="solution"]$-\frac{b}{2a}$ is to find the maximum or minimum x value in a quadratic equation

$\frac{8}{2}=-4$

$16-32=16$

[hide="B"](B)[/hide][/hide][/quote]A little more in depth:

Suppose you have the equation $y=ax^2+bx+c$ and you want to find $\min{y}$ (if $a>0$) or $\max{y}$ (if $a<0$). (Note that if $a<0$ then the equation represents a parabola that opens down, so there is no minimum value, and if $a>0$, then the parabola opens up and there is no maximum (i.e. it extends upwards to infinity).)

Then you can use calculus to find the point where $y'=0$: \[\frac{dy}{dx}=\frac{d}{dx}(ax^2+bx+c)=2ax+b=0\Rightarrow{x}=\frac{-b}{2a}.\]

Since $y'$ is a linear function its sign will change at its zero $x=\frac{-b}{2a}$, so this is where the max or min is. Substituting for $x$ gives (with a little algebra) $y=\frac{4ac-b^2}{4a}$, so the vertex of the parabola (whose $y\text{-coordinate}$ is the max or min of $y$) is the point $\left(\frac{-b}{2a},\frac{4ac-b^2}{4a}\right)$.

If you don't know how to use calculus or what it means, you can also do this algebraically. $y=ax^2+bx+c$ can be manipulated to $a\left(x+\frac{b}{2a}\right)^2+\frac{4ac-b^2}{4a}$, so $\left(x+\frac{b}{2a}\right)^2\ge0\Rightarrow{a}\left(x+\frac{b}{2a}\right)^2+\frac{4ac-b^2}{4a}\ge\frac{4ac-b^2}{4a}$, and equality is attained for $x=\frac{-b}{2a}$, so $\frac{4ac-b^2}{4a}$ is the extreme (min or max) value in all cases. I hope that made sense.

As a sidenote, I don't know much about algebra. I'm guessing it's not a coincidence that the numerator of the $y\text{-coordinate}$ at the min or max of $y$ is the opposite of the discriminant of $ax^2+bx+c$. I'm pretty sure the discriminant is defined by $b^2-4ac$ because of its significance in quadratic formula and determining the number of real zeros.

the max or min (ie vertex) of any quadratic function will always be between the two zeros (the x-coordinate, i mean). It's on the line of symmetry. If the function is easy to factor, as in this case it is, just find the roots: 0 and -8. Therefore the x-coord of the vertex is (0-8)/2=-4. Plugging it back into the equation, you should get 16. I.e. answer B.

Cheers!

P.S: you could always use -b/2a if you know it...it's faster.


trigonometry
geometry
geometric transformation
reflection
function
circumcircle
angle bisector

Let a convex quadrilateral $ ABCD$ fixed such that $ AB \equal{} BC$, $ \angle ABC \equal{} 80, \angle CDA \equal{} 50$. Define $ E$ the midpoint of $ AC$; show that $ \angle CDE \equal{} \angle BDA$
[i](Paolo Leonetti)[/i]

[hide]Lemma: In any triangle $ \triangle ABC$, if $ D$ lies on side side $ BC$, $ \alpha = m \angle BAD$ and $ \beta m \angle DAC$, then $ \frac {AC}{AB} = \frac {DC \sin \beta}{BD \sin \alpha}$.
Proof: Let $ \theta = m \angle ADC$. By the law of sines, we have
$ \frac {AC}{\sin \theta} = \frac {DC}{\sin \beta} \,\,\,\,\,\,\,\,\,\, (1)$
and
$ \frac {AB}{\sin(\pi - \theta)} \& = \nonumber \\
\frac {AB}{\sin \theta} = \frac {BD}{\sin \alpha} \,\,\,\,\,\,\,\,\,\, (2)$
Dividing (1) by (2) yields
$ \frac {AC}{AB} = \frac {DC \sin \beta}{BD \sin \alpha}$
as desired.

Since $ m \angle ABC = 80^{\circ}$ and $ \triangle ABC$ is isosceles, we have $ m \angle BAC = m \angle BCA = 50^{\circ}$. Let $ \omega$ be the circle tangent to lines $ AB$ and $ BC$, at $ A$ and $ C$. For any point $ X$, we have that $ \angle AXC = 50^{\circ}$ if and only if $ X$ is on the circumference of $ \omega$. Since $ m \angle ADC = 50^{\circ}$, we have that $ D$ lies on $ \omega$.

Let $ A_1$ be $ \overline{AC} \cap \overline{BD}$. We want to show that $ m \angle CDE = m \angle ADB$, that is, $ m \angle ADE = m \angle CDA_1$. In other words, we want to show that $ D$ is the point where the reflection of the median through $ D$ to $ AC$ across the angle bisector of $ \angle ADC$, that is, symmedian of $ \triangle ADC$ from $ A$, intersects $ AC$.

Let $ Z = BD \cap \omega$. Note that $ \triangle ABZ \sim \triangle DBA$ and $ \triangle CBZ \sim DBC$ by AA (since $ \angle BDA \cong \angle AZB$ and $ \angle CDB \equiv \angle BCZ$.) Thus, $ \frac {BA}{ZA} = \frac {DB}{AD}$ and $ \frac {CB}{CZ} = \frac {DB}{DC}$. Since $ BC = BA$ by equal tangents, we have

$ \frac {DB \cdot AZ}{AD} = BA = BC = \frac {DB \cdot CZ}{DC}$

Dividing both sides by $ DB$, we conclude that $ \frac {AZ}{AD} = \frac {CZ}{DC}$, or $ \frac {AZ}{ZC} = \frac {AD}{DC}$. Let $ m \angle ZDA = \alpha$ and $ m \angle CDZ = \beta$. Since $ ABCD$ is cyclic, $ m \angle ZCA = \alpha$ and $ m \angle CAZ = \beta$. By the law of sines, $ \frac {AZ}{\sin \alpha} = \frac {CZ}{\sin \beta}$, so $ \frac {AD}{DC} = \frac {AZ}{ZC} = \frac {\sin \beta}{\sin \alpha}$. However, our lemma tells us that $ \frac {AD}{DC} = \frac {AA_1 \sin \alpha}{CA_1 \sin \beta} = \frac {AA_1}{CA_1} \frac {DC}{AD}$. Hence,
$ \frac {AA_1}{CA_1} = \frac {AD^2}{DC^2} \,\,\,\,\,\,\,\,\,\, (3)$
Now, let $ A_1'$ be the point where the symmedian of $ \triangle ACD$ through $ D$ hits $ AC$. Since the function $ f(x) = \frac {x}{a - x} = \frac {a}{a - x} - 1$ is injective for $ x \in (0, s)$, if we can show that $ \frac {AA_1'}{AC - AA_1'} = \frac {AA_1'}{A_1 C} = \frac {AD^2}{DC^2}$, it will follow by (3) that $ A_1 = A_1'$.

Let $ \alpha' = m \angle CDE$ and $ \beta' = m \angle EDA$. Our lemma tells us that
$ \frac {\sin \beta'}{\sin \alpha'} \& = \frac {AD \cdot CE}{DC \cdot EA} \\
\& = \frac {AD}{DC} \,\,\,\,\,\,\,\,\,\, (4)$
since $ E$ is the midpoint of $ AC$. However, by definition, $ \alpha' = m \angle A_1' DA$ and $ \beta' = m \angle A_1' DC$, so by our lemma and (4),
\begin{align*} \frac {AA_1'}{A_1' C} & = \frac {DA \sin \alpha'}{DC \sin \beta'} \\
& = \frac {DA}{DC} \frac {1}{\frac {DC}{AD}} \\
& = \frac {DA^2}{DC^2} \end{align*}
which was what we wanted. [/hide]

So simple!
$ \angle BCA \equal{} \angle BAC \equal{} 50^o \equal{} \angle ADC$ therefore $ B$ is the intersection of two tangents through $ A$ and $ C$ of $ (ACD)$.
So $ DB$ is the D-symmedian of triangle $ ADC$ and we are done.

Maybe the most beautifull problem of the contest

It is easy to see that the circumcenter O of CDA lies on the circumcircle of ABC, and because BO is perpendicular to AC, using the power of E with respect to the two circumcircles it is easy to see that AC is the polar of B with respect to (O), hence BD is the polar of the intersection K of AC with the tanget of (O) at D with respect to (O) and if M is the intersection of BD with (O) then KM is the polar of M with respect to (O) which means that KM is tangent to (O) at M, hence AMCD is a harmonic quadrilateral and hence DM (i.e DB) is the D-symmedian of the triangle ACD.

[quote="NickNafplio"]Maybe the most beautifull problem of the contest[/quote]

LOL It is my first "own" problem, and before yesterday I didn't know what a symmedian is  :D

X in BE such that CXE=CDE so DECX cyclic so DXE=DCE=180-CDA-CAD=180-CAB-CAD=180-BAD, so ABXD cyclic so BDA=AXB=CXE=CDE.

I've also solved it with trig, but I think simpler, sine theorem does the trick.
[hide="Solution"]

Put $ \angle CDE\equal{}x,\angle ADB\equal{}y,\angle ABD\equal{}z$.

Use the sine theorem in triangles $ ADE$ and $ DEC$ to obtain:

$ \frac{AD}{AE}\equal{}\frac{\sin \angle AED}{\sin(50\minus{}x)}$

$ \frac{CE}{DC}\equal{}\frac{\sin x}{\sin\angle DEC}$

Multiply these two to get ($ AE\equal{}CE$ as $ ABC$ is isosceles): $ \frac{AD}{DC}\equal{}\frac{\sin x}{\sin 50\minus{}x}$

In $ ADC$, sine theorem gives us $ \frac{AD}{DC}\equal{}\frac{\sin(y\plus{}z)}{\sin(130\minus{}y\minus{}z)}$

Also, $ 1\equal{}\frac{AB}{BD}\cdot\frac{BD}{BC}\equal{}$

$ \frac{\sin y}{\sin(180\minus{}y\minus{}z)}\cdot \frac{\sin(50\plus{}y\plus{}z)}{\sin(50\minus{}y)}\equal{}$

$ \frac{\sin y}{\sin(50\minus{}y)}\cdot\frac{DC}{AD}$ (because $ \sin(180\minus{}t)\equal{}\sin t$)

Now we get $ \frac{\sin y}{\sin(50\minus{}y)}\equal{}\frac{\sin x}{\sin(50\minus{}x)}$

Cross-mutliply and use product-to-sum formulas to get:

$ \cos(50\minus{}x\minus{}y)\minus{}\cos(50\minus{}x\plus{}y)\equal{}\cos(50\minus{}y\minus{}x)\minus{}\cos(50\minus{}y\plus{}x)$

$ \cos(50\minus{}x\plus{}y)\equal{}\cos(50\minus{}y\plus{}x)$

The values in brackets vary from $ 0$ to $ 100$, and as $ \cos$ function is strictly decreasing in that interval, the 2 brackets must be equal, so $ x\equal{}y$

[/hide]

Symmedian means the line symmetric of the median with respect to the bisector of the angle from which the median is drawn.
If the bisector is the internal bisector, is the (internal symmedian); if is the external bisector, then is the external symmedian.
An internal symmedian cuts the opposed side of the triangle in two segments which are proportional to the squares of the adjacent sides.


Find $ a,b \in Z_ \plus{}$ such as$ \frac{{a^b  \plus{} b}}{{ab^2  \plus{} 9}}$ is a integer.  :)

The correct problem is: find all natural numbers $ a,b$ such that $ \frac{ba^2\plus{}b}{ab^2\plus{}9}$ is an integer.

Daniel


Given are 10 cards with the numbers 1, 2, 3, ..., 10.
Now the following operation is performed 9 times :
Take two cards (at random) with numbers a and b.
Replace them by a new card with the number a + b + ab.
What are all possibilities for the remaining number on the last card ?

[hide]ab+a+b=(a+1)(b+1)-1. If we let this equal c, then we see that c+1=(a+1)(b+1). Thus, the end number will be the product of (1+1)(2+1)(3+1)...(10+1)-1=11!-1. Correct?[/hide]


(P-1)! +1 = P^k

find prime number [color=red]P[/color] and integer [color=red]k[/color]

Some possible solution triplets: (2,1), (3,1), (5,2).

That's all there are for $ p < 167$, at which point Microsoft Excel stopped doing the factorial calculations.  In general this is probably quite hard.  Even Wilson's Theorem is hard to prove.

Well, if you say it's so hard maybe we should try to do it step by step. What I came to (nothing much really) is that if we cross out k=1 and p=2 or 3 we have for the rest:
$ (p\equiv ( \minus{} 1) \ (mod3))\wedge (p^{2}\equiv 1 \ (mod5))$ (of course mod5 not for p=5) and
$ k\equiv 0 \ (mod2)$
I'll admit, quite interesting problem. :wink:

If you want Excel to keep being able to do it, use logarithms.


number theory
greatest common divisor
Stanford
college
HMMT

A sequence of positive integer is defined by $a_0=1$ and $a_{n+1}=(a_n)^2+1$. Find gcd($a_{999}$,$a_{2004}$).

what is SMT? All of these questions are on HMMT.

What??  :?

SMT stands for Stanford Math Tournament.

I didn't know that it was on the HMMT, sorry.

I think that, since HMMT and SMT coincide on the same day, a lot of problems are on both

anyway, the key thing to note here is that the xnth term is divisible by the nth term and the kth term. Since can be easily demonstrated by doing modulo n.
if a(n) is the smallest number divisible by a prime p, then the only terms that can be divisible by p is p(xn) where x is some number.
Proof: take the sequence in mod p. After reaching a(n), it will reapeat itself (in mod p) until it reaches a(2n)

Thus the only primes a(999) and a(2004) can share is a(GCD 999, 2004) which is a(3) or 5

oops; edit: i accidentally read as a1=1 and not a0=1. That means the a(xn+1)th term is divisible by the a(n+1th)term . So now we find the GCD of 1000 and 2005 which is 5, and so that means that the GCD is a(5-1)=a(4)=677

I saw the solution on the HMMT website, and actually the answer

was $a_4=26^2+1$, not $a_3=26$.

And I didn't understand the solution. :(


The locus of the midpoint of a line segment that is drawn from a given external point $ P$ to a given circle with center $ O$ and radius $ r$, is:

$ \textbf{(A)}\ \text{a straight line perpendicular to }\overline{PO} \\
\textbf{(B)}\ \text{a straight line parallel to } \overline{PO} \\
\textbf{(C)}\ \text{a circle with center }P\text{ and radius }r \\
\textbf{(D)}\ \text{a circle with center at the midpoint of }\overline{PO}\text{ and radius }2r \\
\textbf{(E)}\ \text{a circle with center at the midpoint }\overline{PO}\text{ and radius }\frac{1}{2}r$

[hide="Click for solution"]
Let that $ PA$ be any line segment through $ P$ such that $ A$ lies on the given circle with center $ O$ and radius $ r$.  Let $ A$ be the midpoint of $ PA$ and let $ O'$ be the midpoint of $ PO$.  To see that the required locus is a circle with center $ O'$ and radius $ \frac{1}{2}r$, consider the similar triangles $ \triangle POA$ and $ \triangle PO'A'$.  For any point $ A$ on the given circle, $ O'A'\equal{}\frac{1}{2}OA\equal{}\frac{1}{2}r$, so the answer is $ \boxed{\textbf{(E)}}$.
[/hide]


integration
trigonometry
real analysis
real analysis unsolved

Find an equivalent for $\int_{0}^{\infty}{ sin(x^n)dx}$.

$=\frac{1}{n} \int_{0}^{+ \infty} sin(u)u^{\frac{1}{n}-1} du$.
But $\int_{0}^{+ \infty} sin(u)u^{\frac{1}{n}-1} du = \int_{0}^{\pi / 2} sin(u)u^{\frac{1}{n}-1} du + \int_{\pi /2}^{+ \infty} sin(u)u^{\frac{1}{n}-1} du$ and:

$\int_{0}^{\pi /2} sin(u)u^{1/n-1} du \to  A \in \mathbb{R}$ by dominated cinvergence.
$\int_{\pi /2}^{+ \infty} sin(u)u^{\frac{1}{n}-1} du = \frac{1-n}{n} \int_{\pi / 2}^{+ \infty} cos(u) u^{\frac{1}{n} - 2} du$.
And with dominated convergence you got that $\frac{1-n}{n} \int_{\pi / 2}^{+ \infty} cos(u) u^{\frac{1}{n} - 2}$ tends to $- \int_{\pi / 2}^{+ \infty} cos(u) u^{ - 2} du$
Hence it is equivalent to $\frac{C}{n}$. ($C$ is easily computable).


How many numbers can be expressed as the sum of two or more distinct elements of the set $ \{ 0, 1, 2, 4, 8, 16 \}$?

Because they are powers of two, we can reach any numbers less than or equal to $ 16\plus{}8\plus{}4\plus{}2\plus{}1\equal{}31$, just think about it in binary.  The answer is thus $ \boxed{31}$.

I feel that the solution to this should be given in more understandable terms. Surely there is a simpler, but more understandable, way to the solution, right?

I got the answer, but can anyone explain to me why
6C2 + 6C3 +6C4 + 6C5 + 6C6 doesn't work?

I feel like it should, because you are trying to find the amount of numbers that can be expressed by two or more elements, and no combination of elements overlap with each other.

[hide=Solution with more explanation]
First of all, we can throw out the $0$, as it doesn't affect sums with two or more numbers.
Then, our list is ${1_2,10_2,100_2,1000_2,10000_2}$. Remember that we are in binary, so all positive integers less than or equal to $11111_2=31$ can be formed using two or more set elements. Thus, we have $\boxed{31}$ distinct possible sums.[/hide]

[quote=Bestestsocks]I bashed to get the answer. This problem was way easier than level 23[/quote]

The difficulty level of a bash solution feels ~level 23.  That said, the binary solution trivializes the problem; it does feel easier than level 23.

[quote=V_V]is this rly even CP?? Binary is not CP(it's NT) and also there was no real "constructive counting"[/quote]

Well, I would say it's both.

it was in counting probability
¯\_(ツ)_/¯

[quote=V_V]is this rly even CP?? Binary is not CP(it's NT) and also there was no real "constructive counting"[/quote]

exactly lol

[hide=Solution]
Using all the values from $2^0\text-2^n$ (and $0$ to sum up to themselves), you can get any number up to $2^{(n+1)}-1$ because binary works that way. Since the highest power of $2$ is $16=2^4$, we can get any number up to $2^5-1=32-1=31$. So you can get the numbers $1\text-31$, which is $\boxed{31}$ numbers.
[/hide]

[quote=harryhero]Think about the base 2 (binary) counting system. It uses the values of the powers of 2, with each digit having a maximum of 1.

Isn't the base 2 system exactly this problem?[/quote]

Yes! That's what I originally thought!


Let $A$ be the sum of all fractions whose numerators and denominators add up to $456$.Compare $A$ to number 2007


probability
geometry
geometric transformation
rotation

A class contains n boys and n girls. If they all randomly select seats around a circular table that seats 2n, what is the probability that some two boys will sit next to one another?

I have a solution that treats each person as distinct, but now I am trying to find a solution that treats each person as indistinct. Here is my current, wrong solution:

[hide]The number of ways to seat them in a line is C(2n,n), so the number of ways to do so in a circle is C(2n,n)/2n. Since there is only one way to seat them such that no two boys will sit next to one another (if we alternate boy, girl, boy, girl, etc...), our desired probability is 1-1/(C(2n,n)/2n).[/hide]

There are 2n! ways to arrange 2n people in a line, but you have to divide by 2n, so there are (2n-1)! combinations. Since the only way for there not to be boys sitting next to each other is for it to go alternate all around the table, and there are n! seats for girls and n! seats for boys, and we have to divide by 2n, we get

[(2n-1)!-(n!n!)/2n]/(2n-1)!

Maybe this could be simplified. Of course it's probably wrong anyway....

Yeah, but you're treating each person as distinct. I am looking for a method that treats each person as indistinct. :D

Topper, I'm pretty sure you don't want to divide by the 2n there.

Number of combos for seats in all: (Assuming that I can tell boys and girls apart, If I couldn't, how would I be able to tell if they had boys sitting together?)

Well, there are n places where boys can sit. To pick them, do          C(2n,n). The remaining seats belong to the indistingishable girls. There is only 1 combination that has boys never next to othere boys: BGBGBGBGB......

We must divide by 2n (because it's a circle) and then we have our answer:  1/C(2n,n)/2n. Or something...

Again, likely this can be simplified/ is wrong/both.

I think you're close there.  There's a slight problem, though -- I think what's messing you up is rotation.  Not every arrangement has 2n rotations any more -- the "good" arrangements, BGBGBG... have only 2 rotations.  So lets not rotate and see what happens:
C(2n, n) total ways.  2 bad ways.  Thus ((C(2n, n) - 2)/C(2n, n) is our probability.  This is equal to ((2n)! - 2n!*n!)/(2n)! = ((2n - 1)! - n!n!/n)/(2n - 1)!, which almost looks like Topper's answer of
[(2n-1)!-(n!n!)/2n]/(2n-1)! .  So, what's the problem?  Topper divided by 2n, but he only should have divided by n -- by taking the value n!n! for the number of arrangements of BGBGBG..., he had already tacitly assumed that we always had a boy in the first place.  He only needed to divide by n, not 2n, to sift out which boy started.  With that change, we have the same answer through two different methods.  So we must be correct :).


Find all $x, y \in \mathbb{R}$ such that:

${\sqrt{2x(y+1)}} + \sqrt{(x+1)y} + \sqrt{(x-1)(y-2)} = \sqrt{4x(3y-1)}$


Let set F equal the fibonacci sequence, and set G equal a "double fibonacci" sequence:

a1 = 1
a2 = 1
a3 = 1
a4 = 1
an = an-1 + an-2 + an-3 + an-4

...or every term is the sum of the previous four terms.

If you list out the first few terms of each...
1 1 2 3 5 8 13 21 34
1 1 1 1 4 7 13 25 49

The sequences have 1, 1, and 13 in common. If there are any other terms they have in common, find the next one. If not, prove it.

(Don't know how hard this is)

At first sight, it can be really hard.
But who knows what thoughts will come on my head at second sight... :?


let $ \theta\in(1,\infty)\setminus Q$. then the set $ \{x\theta \minus{} y: x,y\in N\}$ is :

a) dense in every $ (a,b)\subset(1,\infty)$ ?

b) uniformly distributed in every $ (a,b)\subset(1,\infty)$ ?

a) yes.  fix $ t\in (1,\infty)$.  we know by density/uniform distribution of $ (\{n\theta\})_{n\in\mathbb{N}}$, that we can find $ N\theta$ such that the fractional parts of $ t$ and $ N\theta$ are close.  by subtracting an appropriate integer $ M$ from $ N\theta$ we can make $ (N\theta\minus{}M)\minus{}t$ equal to $ \{N\theta\}\minus{}\{t\}$.

b) i don't even know what a notion of uniform distribution on $ (1,\infty)$ looks like, since the measure of $ (1,\infty)$ is infinite.

[quote="spectral"]thanks for a)

b) the question is about U D in $ (a,b)$ which has finite measure $ b \minus{} a$ :wink:[/quote]

perhaps you had better define exactly what it would mean to be uniformly distributed in the second question, since i don't see how the usual notion of uniform distribution would generalize.

let $ (a,b)$ be a bounded subinterval of real line.

the set $ \{z_n: n\in N\}$ is U D in $ (a,b)$ iff
for every subinterval $ [c,d]$ of $ (a,b)$ holds $ \frac {Z_n}{n}\to\frac {d \minus{} c}{b \minus{} a}$,
where $ Z_n$ denotes the number of elements of the intersection $ \{z_k: 1\le k\le n\}\cap[c,d]$.

[usually it's assumed that $ z_n\in(a,b)$ for all $ n$,
if not all elements of the set are in $ (a,b)$, we certainly skip others]

so in the problem:
first we fix $ \theta > 1$ irrational and reals $ 1 < a < b$ (reals, so $ b\neq \infty$) and next,
we want to show (actually ask, but I think the answer will be "yes" :wink:) that $ \{x\theta \minus{} y: x,y\in N\}\cap(a,b)$ is U D in $ (a,b)$
it means, that for every subinterval [c,d] ...........

$ \{x\theta\minus{}y: x,y\in\mathbb{N}\}$ is indexed by two variables, not just one though -- in what order are you going to go through them?


Hello. I found this problem in a book. I'd like some help to solve it. Here it goes.

"Let S(N) be the sum of the digits of N. Consider the sequence $a_1=1999!$, $a_2=S(a_1)$, $a_3=S(a_2)$, etc.
Find $a_{1999}$ "

For example, N=1234, S(N)=1+2+3+4=10, S(10)=1+0=1, etc.

Thank you.

[hide="Solution"]
It's a little complicated to explain, but the answer is $\boxed{9}$.

Consider $a_1 = 18$.  Then we have $a_2 = 9, a_3 = 9, ... a_{1999} = 9$.  Next consider a larger number, such as $a_1 = 729$.  We have $a_2 = 18, a_3 = 9, a_4 = 9, ... a_{1999} = 9$.

For all input values, you're going to reach some point where $a_k$ is a one-digit number, and then every new value in the sequence is just that same number.  You should be able to see from the above example that any number that's divisible by 9 will give $9$ as the eventual answer.  But why?

The answer lies in the fact that $10^k - 1$ is always divisible by 9.  (Try it for yourself.)  So, a number $N = d_1d_2d_3...$, where $d_k$ is the $k^{th}$ digit of the number, can be rewritten $N = d_1 10^k + d_2 10^{k-1} + ...$.  For example, $N = 1234 = 1000 + 200 + 30 + 4$.  Since we know that $1000 - 1 = 999, 100 - 1 = 99, 10 - 1 = 9$, we know that if we divide $1000 + 200 + 30 + 4$ by 9, we will get the same [b]remainder[/b] as we will if we divide $1 + 2 + 3 + 4$ by 9.  (And we do; the remainder is $1$, which is also the answer you get if $a_1 = 1234$.)

So, basically, the answer for any $a_1 = N$ is that, for sufficiently large n, $a_n = N \bmod 9$, or phrased otherwise, the answer is the remainder when $N$ is divided by 9 - except, as we have seen, if $N$ is a multiple of 9.

Now, $1999!$ is definitely a multiple of 9, so the answer is definitely $\boxed{9}$.  (This is also a consequence of the observation that, if a number is divisible by 9, the sum of its digits will also be divisible by 9.  Read up on modular arithmetic if you're more interested.) [/hide]

Please pay attention to the levels of forums before you post.  This not appropriate for the Middle School Classroom Math forum.

Hi, so it was very easy!

so, $a_1=1999!$ is obvious is a multiple of 9, M(9)
then the sum of its digits it is too, that is, $S(a_1)=M(9)$, etc.

$a_1=1999!=M(9)$, so $a_2=S(a_1)=M(9)$
 $a_2=M(9)$, so $a_3=S(a_2)=M(9)$,
and keep going...
We stop when $S(a_k)$ is one digit, that is, $9$!

Thank you!


John and a group of friends took a bus trip. Each person paid the bus driver with the same 9 coins. If the bus driver recieved $8.41 from the group, how many dimes did he recieve?

[hide]
$ 841 \equal{} 29^2$

So there are 29 people and each paid 29 cents. If we have a quarter, it's impossible to have 9 coins, since there are only 4 cents left, so assume there are only pennies, nickels and dimes:
$ p \plus{} n \plus{} d \equal{} 9$
$ p \plus{} 5n \plus{} 10d \equal{} 29$
Subtract the first from the second,
$ 4n \plus{} 9d \equal{} 20$
It's easy to find a solution $ (4,5,0)$, and we can verify there's no other positive integer solutions.

Therefore, there are no dimes.[/hide]
[/hide]


How would I solve the following problem. I know you use the Intermediate Value Theorem:

Prove that x = cos x for some x in (0,1).

let $f(x)=\cos x-x$, $f(0)=1$, and $f(1)=-1$, it must hit the x-axis by the intermediate value theorem

Well, $f(1)$ isn't $-1$. It is at least negative, since $\cos 1<1$.


After the new year's party at the movies, Bobert and Eustine get into an argument over who is better at math.  To decide this, they decide to flip a coin three timnes, with Bobert getting a point if the coin lands heads, and Eustine getting a point if the coin lands tails.  The person who gets at least 2 points isthe winner.  What is the probability that Bobert will win?

Yup you got it KBabe

you don't have to be shy ( I mean like putting the question mark at the end )

Yeah, you're right.  Just put it spoiler next time so that other people won't be able to see the answer.

Obviously, 1/2   :D

[size=200]Patsies are going down!!!! :P [/size]

http://www.steelers.com
[i]
Moderater D-MATH says: Try to stay on topic, it woudn't be as bad if you actually posted a solution with steps and all before this[/i]

[quote="h_s_potter2002"]After the new year's party at the movies, Bobert and Eusine get into an argument over who is better at math.  To decide this, they decide to flip a coin three timnes, with Bobert getting a point if the coin lands heads, and Eustine getting a point if the coin lands tails.  The person who gets at least 2 points isthe winner.  What is the probability that Bobert will win?[/quote]

Hm, I asked Bobert and he said 2/3...

Sorry, I didn't mean to confuse you.

[b]HHH
HHT
HTH[/b]
HTT
[b]THH[/b]
THT
TTH
TTT

So yes, it is 4/8, or 1/2.

He is one of the Albatross Problem characters. I want to have one for every letter of the alphabet. Also I would like every single person here to start posting with those names and start a tradition. I will be accepting suggestions for names, private meesage me.

My dream is to make a tradition that is so big that the AMCs will put problems with those names  :D

So everyone post using those names!

Albatross, Bobert, Caddlebot, Deberg, Eustine, Frankinfueter....Zeta.

*imagines the AMCs being filled with mutated animals, cat poison, and six-legged KFC chickens*

Maybe that's not such a good idea :P .

Doesn't have to be those topics... :lol:

[quote="A+MATH"]Albatross, Bobert, Caddlebot, Deberg, Eustine, Frankinfueter....Zeta.[/quote]

Actually, the AMC used Zeta as a name in one of their tests, but I forgot which one.  It was also in one of the Mock AMC's too.

1 down, 25 to go :P .

Generalize the probability of getting all heads when flipping a coin [i]n[/i] times.

[quote]HHH
HHT
HTH
HTT
THH
THT
TTH
TTT
[/quote]

you don't have to try it like that...

[quote]why would it be 2/3?

it would just be 1/2 because you don't know anything about it other than the fact that it's a two sided dice.... so it's 1/2...

wait, who's Bobert? is this a joke?[/quote]

I believe it's a coin not a die

[hide="this is my whole answer"][hide="this is one third of my answer"]1[/hide][hide="this is another third of my answer"]/[/hide][hide="this is the last third of my answer"]2[/hide][/hide]

Jli -

[hide]When you say[quote]This is one third of my answer[/quote]
You do realize that the answer you gave was not  one third but twice of your answer. :)
Answer is $1/2$  one third of $1/2$ is  $1/6$ and not $1$ as you said.. :)
math is fun..[/hide]

Obviously, 1/2. But how can i prove? it :blush:

[quote="shinwoo"]

[quote]why would it be 2/3?

it would just be 1/2 because you don't know anything about it other than the fact that it's a two sided dice.... so it's 1/2...

wait, who's Bobert? is this a joke?[/quote]

I believe it's a coin not a die[/quote]

oops, sorry, I meant coin...

[quote="A+MATH"]
Albatross, Bobert, Caddlebot, Deberg, Eustine, Frankinfueter....[b]Zeta[/b].[/quote]

No intention to disappoint you but Zeta has already been used in AHSME.  :)

Check out the proof on Mock AMC J.


So I googled the qualifying quiz from '06 (the year I attended) a few days ago to look at it. The first two hits were the quiz and A119750 in the Online Encyclopedia of Integer Sequences, which appeared to generalize #8. But the sequence was wrong! It relied on a misconception that probably more than half of us that attempted the problem fell into, including myself. And for bragging's sake, I pointed out the error and my name's in the entry now. :D

Cheers.


solve the system:
$ x \equal{} (3y \minus{} y^3)/(1 \minus{} 3y^2)$
$ y \equal{} (3z \minus{} z^3)/(1 \minus{} 3z^2)$
$ z \equal{} (3x \minus{} x^3)/(1 \minus{} 3x^2)$

hello, setting the first equation in the third one and simplifying we get
$ z=\frac{y(y^2-3)(-3+27y^2-33y^4+y^6)}{(-1+33y^2-27y^4+3y^6)(-1+3y^2)}$
setting this in the second equation and simplifying we get
$ {y(y^2+1)(13y^{12}-286y^{10}+1287y^8-1716y^6+715y^4-78y^2+1)(y^{12}-78y^{10}+715y^8-1716y^6+1287y^4-286y^2+13)=0}$.
With Maple 13 i have found $ 25$ real solutions.
Sonnhard.

aadil, remember trig formulaes?
[hide="solution"]
since $ tan a$ ranges from - infinity to + infinity,
we make the substituion that $ y \equal{} tan(3a)$
since we have $ tan(3a) \equal{} \frac {3tan(a) \minus{} tan(a)^3}{1 \minus{} 3tan(a)^2}$
we get $ x \equal{} tan(3a) , y \equal{} tan(a) , z \equal{} tan(\frac {a}{3})$ and  also $ x \equal{} tan(\frac {a}{9}$
thus we have $ tan(3a) \equal{} tan(\frac {a}{9})$
or $ a \equal{} n \pi \frac {8}{9}$ and we are done! [/hide]
what is your solution?

Make sure to mention that  the denominators are not  equal to $ 0$ when the solutions are substituted(check it).

very valid point i should have checked it and either ways i dont see how there can be 25 solutions?????

i also  used tan 3a.
how is it that there are exactly 25 real solutions?

Suppose we didn't have Maple or Mathematica to solve the problem. How in the world would you find 25 real solutions to that monster of an equation?

it would be nice if someone explained the occurence of 25 solutions after 3 people have raised the same doubt

We have that $ \tan(3a)\equal{}\tan(a/9)$.  Tangent has a period of $ 2\pi$ so

$ \tan(3a)\equal{}\tan(a/9)\Leftrightarrow 3a\equal{}a/9\plus{}2k\pi\Leftrightarrow 26a/9\equal{}2k\pi$

$ a\equal{}\frac{9k\pi}{13}$.  This is a multiple of $ 2\pi$ iff $ 26|k$.  So that gives $ k\equal{}0, 1, 2, 3, 4, 5\ldots 25$ are the unique solutions.  But notice that if $ k\equal{}13$, then the tangent is undefined.  So all $ k$ from 0 to 25, not including 13, are solutions giving 25.


Since scores are out now and no one has created the usual poll, I'll take the liberty of doing so.

[b]5[/b]5[b]5[/b]5[b]5[/b] :o

Having read Matt's solutions, I have absolutely no idea how I'm tied with him on the commended leaderboard. :huh:

Well, congrats!   :lol:

I got 5545[b]5[/b]

So I'm pretty happy... My first commend!

[b]5[/b]555[b]5[/b]

i feel like the next round is a bit more difficult...maybe eliminate some perfect scores...

55[b]5[/b]54

I just cited the Dirichlet series in 5b.  I didn't actually prove that $ \sum_{n\equal{}1}^{\infty} \frac{\varphi(n)}{n^s} \equal{} \frac{\zeta(s\minus{}1)}{\zeta(s)}$.

4 5 5 5 4

I got points off on #5 for citing that
\[ \left( \sum_{n \equal{} 1}^\infty \frac {f(n)}{n^s} \right) \left( \sum_{n \equal{} 1}^\infty \frac {g(n)}{n^s} \right) \equal{} \sum_{n \equal{} 1}^\infty \frac {(f*g)(n)}{n^s}
\]
But this is a really basic, well-known fact and easy to prove, so how could it trivialize the problem? The only other fact I cited without proof is $ \phi(n) * 1 \equal{} n$, although isn't that extremely well-known?

[b]5[/b]5555

yay my first perfect round! :)

5555[b]5[/b]

w00t, first perfect and first commend (for some reason, I always get the highest score on round 3...)

I got 5 4 5 5 4, which I'm satisfied with since this is my first round trying USAMTS and I'm in 8th grade.

I problem #2, I used the fact that (n+k-1) C (k) is the number of ways to choose k objects from n items if repetitions are allowed, and the grader took off a point for that since I had to prove it.

And in problem #5, I also cited the Dirichlet series that lingomaniac88 used.

55545

My mistake was actually really stupid.  In #4, I divided all elements in the set by 2007, but got the wrong set.  I should have had {1, 10001, ...} while instead, I had {1, 1001, 1001001, ...}.  This is my first stupid mistake on the USAMTS thus far.

What was the cutoff for AIME? I got in with a 70.

I got in with a 68, so I'm pretty sure that is the cutoff.

hm

[b]5[/b]5555

yay

my total is now 74

Still no commendeds?

well ok, I don't actually care, I have a 75.

[b]55[/b]553.

Didnt prove the Dirichlet series for #5; brought my score to 3 :oops:

[quote="calc rulz"]I got points off on #5 for citing that
\[ \left( \sum_{n \equal{} 1}^\infty \frac {f(n)}{n^s} \right) \left( \sum_{n \equal{} 1}^\infty \frac {g(n)}{n^s} \right) \equal{} \sum_{n \equal{} 1}^\infty \frac {(f*g)(n)}{n^s}
\]
But this is a really basic, well-known fact and easy to prove, so how could it trivialize the problem?[/quote]
Sorry, calc rulz, but most mathematicians have either never seen a Dirichlet convolution or have forgotten everything they learned about convolutions in graduate school. It does not count as a well-known fact. At the very least, you should have mentioned that $ (f*g)(n) \equal{} \sum_{d\mid n}f(d)g(n/d)$, so that a grader who remembered convolutions in general, but had forgotten which one was the Dirichlet convolution, could understand which convolution you used. I happen to fall in that category myself.

Further confusing the confused grader, you wrote $ \phi(q)*1$ rather than the correct form $ (\phi*1)(q)$.

No, I did not grade Problem 5.

Erin Schram
USAMTS grader

[quote="not_trig"][quote="lingomaniac88"][quote="calc rulz"]The only other fact I cited without proof is $ \phi(n) * 1 \equal{} n$, although isn't that extremely well-known?[/quote]

Is that even true?

$ \phi(24) \equal{} 8 \neq 24$[/quote]

heh I don't think this is multiplication... maybe convolution?

[b]5 5[/b] 5 5 5

yay?[/quote]
Definitely looks like a convolution product.
That's equivalent to $ \sum^{n}_{d|n}\phi(d) \equal{} n$, by the way.
I think that it's well enough to be stated without citation.

[b]5[/b]5555.  My first perfect, and first commended!

[quote="McDutchy"][b]55[/b]5[b]5[/b]5

When you take time to do your solutions correctly, it's amazing.[/quote]

I agree :D

[b]5[/b] 5 5 [b]5[/b] 4

I forgot to check if any circles were inside one another. :P

555[b]5[/b]5
But round 4 seems quite a bit harder. Surely they are trying to compensate round 3...[/b]

yeah they're probably trying to break some ties for 75 pts. :)

[b]5[/b]555[b]5[/b]

O.o my lowest amount of commends yet on a single round. I don't have any clue why I have so many.

Round 4 looks really hard...

I got [b]5 5[/b] 5 5 5.  The last round looks a lot tougher, though.

[quote="azjps"]Having read Matt's solutions, I have absolutely no idea how I'm tied with him on the commended leaderboard. :huh:[/quote]

Thanks  :lol: .  Don't be so modest, your solutions must have been pretty elegant to get that many commended solutions!

55553

Gah, why don't I ever get any commendeds?

5 5 5 3 2

Dont know what was wrong with my solution for number 4
Number 5 - had no idea how to do part b.

Still have a 62