I'm trying to come up with ideas for an Intel Science Talent Search project, but I'm not doing too well. I'm interested in many fields of science, especially cosmology, but I don't know what my topic should be. I've read the guidelines on the site as to how the paper should be set up, but I would appreciate advice from anyone who has participated in this competition regarding actually getting started with research.

I think most participants get in contact with a scientist in their field of interest, who acts as a mentor and gets the student started with the whole research process.

Is there any online mentoring program that allows me to contact a mentor? I live overseas and I'm finding it with difficult to find a mentor.


geometry inradius trapezoid parallelogram invariant rhombus incenter

A circle of radius $ r$ is inscribed in a quadrilateral $ ABCD$. It touches $ AB$ at $ P$ and $ CD$ at $ Q$. $ AP \equal{} 19$, $ PB \equal{} 26$, $ CQ \equal{} 37$, $ QD \equal{} 23$. Find $ r$.

Since $AP \doteq CQ$ and $BP \doteq DQ$, the quadrilateral $ABCD$ is not a rhombus. Hence, it is either a tangential trapezium or a general tangential quadrilateral. In the first case, let $X$ be the intersection of the non-parallel pair of its opposite sides and $x$ the line parallel to its base. In the second case, let $X, Y$ be the intersections of the opposite sides $X \equiv AB \cap CD$, $Y \equiv BC \cap DA$ and $x \equiv XY$ the line passing through the points $X, Y$. There exist a central projection, which carries the incircle $(I)$ to itself and the line $x$ to infinity. Any lines intersecting on the line $x$ are carried into parallel lines. Thus the quadrilateral $ABCD$ is projected into a parallelogram $A'B'C'D'$ with the incircle $(I)$, i.e., into a rhombus. Denote $a = AP, b = BP, c = CQ, d = DQ$. From the analysis of the problem [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=28485]Not Hard[/url] in the Olympiad Section, Geometry, Unsolved Problems, it follows that the products $ac = AP \cdot CQ$ and $bd = BP \cdot DQ$ are invariant under this central projection. Hence, it is sufficient to find the radius $r$ of the incircle $(I)$ for the rhombus $A'B'C'D'$, given the products $a'c' = A'P' \cdot C'Q' = AP \cdot CQ = ac$, $b'd' = B'P' \cdot D'Q' = BP \cdot DQ = bd$.

Since the quadrilateral $A'B'C'D'$ is a rhombus, $a' = A'P' = C'Q' = c'$ and $b' = B'P' = D'Q' = d'$. Thus we are actually given $a' = \sqrt{a'c'} = \sqrt{ac} = \sqrt{19 \cdot 37}$ and $b' = \sqrt{b'd'} = \sqrt{bd} = \sqrt{26 \cdot 23}$. The rhombus diagonals $A'C' \perp B'D'$ are perpendicular to each other. Since they bisect its internal angles, they meet at its incenter $I' \equiv I$. Hence, the angle $\measuredangle A'IB' = 90^o$ is right. The inradius $r = IP'$ is the altitude of the right angle triangle $\triangle A'IB'$ from the vertex $I$ to the hypotenuse $A'B'$. From similarity of the right angle triangles $\triangle A'P'I \sim \triangle IP'B' \sim \triangle A'IB'$, it follows that

$\frac{A'P'}{IP'} = \frac{A'I}{B'I} = \frac{IP'}{B'P'}$

$r^2 = IP'^2 = A'P' \cdot B'P' = a'b'$

$r = \sqrt{a'b'} =\ ^4\sqrt{abcd} =\ ^4\sqrt{19 \cdot 26 \cdot 37 \cdot 23} \doteq 25.46$

[quote="Myth"]Excuse, I see your formula should correct for all qudrilaterals. But that is untrue.[/quote]

Indeed it is not true for all tangential quadrilaterals.

To Pengshi:
Please disregard the result until the error is found.

Let $ABCD$ be an arbitrary tangential quadrilateral with the sides $a = AB$ , $b = BC$, $c = CD$, $d = DA$, the diagonals $e = AC$, $f = BD$ and the angles $\alpha = \measuredangle DAB$, $\beta = \measuredangle ABC$, $\gamma = \measuredangle BCD$, $\delta = \measuredangle CDA$. Using the cosine theorem for the triangle $\triangle ABC, \triangle DBC$, we have

$e^2 = a^2 + b^2 - 2ab \cos \beta = c^2 + d^2 - 2cd \cos \delta$

Since the quadrilateral $ABCD$ is tangential, the sums of the opposite sides are equal, $a + c = b + d$. Hence,

$a - b = c - d$

$a^2 - 2ab + b^2 = c^2 - 2cd + d^2$

Subtracting this from the equation obtained with the help of the cosine theorem, we get

$2ab(1 - \cos \beta) = 2cd(1 - \cos \delta)$

$4ab \sin^2{\frac \beta 2} = 4cd \sin^2{\frac \delta 2}$

$\left(\frac{\sin{\frac \beta 2}}{\sin{\frac \delta 2}}\right)^2 = \frac{cd}{ab}$

Let $R, S$ be the tangency points of the incircle $(I)$ with the sides $BC, DA$, Since the segment lengths of the tangents from the vertices $A, B, C, D$ to the corresponding tangency points are equal, the sides $a, b, c, d$ of the quardilateral $ABCD$ are

$a = AB = AP + BP = 45$
$b = BC = BR + CR = BP + CQ = 63$
$c = CD = CQ + DQ = 60$
$d = DA = DS + AS = DQ + AP = 42$

Hence, the problem is to find the inradius $r$ of a tangential quadrilateral $ABCD$, given the 4 sides $a, b, c, d$ and the tangency points $P \in a, Q \in c$ with the incircle $(I)$. Since the lines $BI, DI$ are the angle bisectors of the quadrilateral angles $\beta = \measuredangle ABC$, $\delta = \measuredangle CDA$,

$\measuredangle ABI = \frac \beta 2$, $\measuredangle CDI = \frac \delta 2$

From the right angle triangles $\triangle BPI, \triangle DQI$,

$\sin{\frac \beta 2} =  \frac{IP}{BI}\frac{r}{\sqrt{BP^2 + r^2}}$

$\sin{\frac \delta 2} =  \frac{IQ}{DI} = \frac{r}{\sqrt{DQ^2 + r^2}}$

Combining this with the previously obtained equation for a tangential quadrilateral,

$\left(\frac{\sin{\frac \beta 2}}{\sin{\frac \delta 2}}\right)^2 = \frac{DQ^2 + r^2}{BP^2 + r^2} = \frac{cd}{ab}$

and calculating $r^2$ from this equation, we get

$r^2 = \frac{cd \cdot BP^2 - ab \cdot DQ^2}{ab - cd} = \frac{60 \cdot 42 \cdot 26^2 - 45 \cdot 63 \cdot 23^2}{45 \cdot 63 - 60 \cdot 42} = \frac{67935}{105} = 647$

$r = \sqrt{647} \doteq 25.44$

Hey, I was not that far off (just kidding, I played enough with tangential quadrilaterals to know that differences in various distances are usually very tiny). My previous post is totally bogus, I got fooled by my previous reply to the post [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=28485]Not Hard[/url].

[quote="pengshi"]I brute forced with trig and found the answer to be $\sqrt{{abc+acd+abd+bcd\over a+b+c+d}}$.[/quote]

This yields the same result, if the notation is $a = AP, b = BP, c = CQ, d = DQ$ (and not the sides of the quadrilateral): $r = \sqrt{647}$. Would you mind to post what you did? Thanks.

yetti

Here's what I did to obtain pengshi's result:
Let $a+b = AB$, $b+c = BC$, $c+d = CD$, $a+d = AD$, the center of the incircle be I.
$ abc+acd+abd+bcd = (a+b) * cd + (c+d) * ab = AB * cd + CD * ab$
Let $\alpha = \measuredangle AIP$, $\beta = \measuredangle BIP$,  $\gamma = \measuredangle CIQ$, $\theta = \measuredangle DIQ$
Therefore $ AB * r^2 + CD * r^2 - (abc+acd+abd+bcd) = AB * (r^2-cd) + CD * (r^2-ab) $
Which equals
$\displaystyle AB(r^2-r^2\tan\gamma \tan\theta) + CD(r^2-r^2\tan\alpha\tan\beta) = AB*r^2(\frac{\tan\gamma + \tan\theta}{\tan(\gamma+\theta)}) + CD*r^2(\frac{\tan\alpha + \tan\beta}{\tan(\alpha+\beta)})$
Finally we get $AB*r*\frac{c+d}{\tan(\gamma+\theta)} + CD*r*\frac{a+b}{\tan(\alpha+\beta)} = r(\frac{AB*CD}{\tan(\gamma+\theta)} + \frac{AB*CD}{\tan(\alpha+\beta)}) = 0$
Thus $AB * r^2 + CD * r^2 = abc+acd+abd+bcd => r^2(a+b+c+d) =  abc+acd+abd+bcd$

And we are left with the formula.  Sorry about my terrible latex layout...

[quote="yetti"]
This yields the same result, if the notation is $a = AP, b = BP, c = CQ, d = DQ$ (and not the sides of the quadrilateral): $r = \sqrt{647}$. Would you mind to post what you did? Thanks.

yetti[/quote]
Let the centre of the incircle be $I$. Let $\alpha=\angle AOP$, $\beta=\angle BOP$, $\gamma=\angle COP$,$\theta=\angle DOP$, then $\alpha+\beta+\gamma+\theta=\pi$. Also $\tan \alpha = AP / r$, $\tan \beta= BP / r$ , $\tan \gamma = CP / r$, $\tan \theta = DP / r$. Use the addition formula for $tan$ repeatedly to get some huge formula for $\tan(\alpha +\beta +\gamma +\theta)$. Finally, plug in the above and we get the result.

[quote="anipoh"]Here's what I did to obtain pengshi's result: ...[/quote]
Thanks. My formula must lead to the same thing:

$r^2 = \frac{CD \cdot DA \cdot BP^2 - AB \cdot BC \cdot DQ^2}{AB \cdot BC - CD \cdot DA}$

Using Pengshi's notation $a = AP, b = BP, c = CQ, d = DQ$,

$r^2 = \frac{(c + d)(d + a) b^2 - (a + b)(b + c) d^2}{(a + b)(b + c) - (c + d)(d + a)}$

The denominator is

$q = (a + b)(b + c) - (c + d)(d + a) = ab + ac + b^2 + bc - cd - ac - d^2 - ad =$

$= (a + c)b + b^2 - (a + c)d - d^2 = (a + c)(b - d) + (b + d)(b - d) = (a + b + c + d) (b - d)$

The numerator is

$p = (c + d)(d + a) b^2 - (a + b)(b + c) d^2 = (cd + ac + d^2 + ad)b^2 - (ab + ac + b^2 + bc)d^2 =$

$= ac(b^2 - d^2) + cbd(b - d) + abd(b - d) = (abc + acd + cbd + abd) (b - d)$

Square of the inradius is

$r^2 = \frac p q = \frac{abc + acd + cbd + abd}{a + b + c + d}$

This is another solution.

Let $ABCD$ be an arbitrary circumscribed quadrilateral with the sides $a = AB$ , $b = BC$, $c = CD$, $d = DA$ and the angles $\alpha = \measuredangle DAB$, $\beta = \measuredangle ABC$, $\gamma = \measuredangle BCD$, $\delta = \measuredangle CDA$. Since $a + c = b + d$, from the well know formula on the area

$[ABCD] = \sqrt {\left( {p - a} \right)\left( {p - b} \right)\left( {p - c} \right)\left( {p - d} \right) - abcd\cos ^2 \left( {\frac{{\alpha  + \gamma }}{2}} \right)} $

follows easily  $\left[ {ABCD} \right] = \sqrt {abcd} \sin \frac{{\alpha  + \gamma }}{2}$.  Thus

$ r\frac{{a + b + c + d}}{2} = \sqrt {abcd} \sin \frac{{\alpha  + \gamma }}{2} \ \   \Rightarrow  $

$ r^2  = \frac{{4abcd}}{{\left( {a + b + c + d} \right)^2 }}\sin ^2 \frac{{\alpha  + \gamma }}{2} \ \ $  [color=blue](*)[/color]

On the other hand since $\cot \frac{\alpha }{2} = \frac{{19}}{r}{\rm{  }}$ and ${\rm{  }}\cot \frac{\gamma }{2} = \frac{{37}}{r}$ we have

$ \cot \frac{{\alpha  + \gamma }}{2} = \frac{{\cot \frac{\alpha }{2}\cot \frac{\gamma }{2} - 1}}{{\cot \frac{\alpha }{2} + \cot \frac{\gamma }{2}}} = \frac{{703 - r^2 }}{{56r}} $

$ {\mathop{\rm sen}\nolimits} ^2 \frac{{\alpha  + \gamma }}{2} = \frac{1}{{1 + \cot ^2 \frac{{\alpha  + \gamma }}{2}}} = \frac{{3136r^2 }}{{3136r^2  + \left( {703 - r^2 } \right)^2 }} $

and, from [color=blue](*)[/color], we obtain

$r^2  = 648\frac{{3136r^2 }}{{3136r^2  + \left( {703 - r^2 } \right)^2 }}{\rm{  }} \Rightarrow {\rm{  }}r = \sqrt {647} \ \   \blacksquare$

[quote="Myth"]Excuse, I see your formula should correct for all qudrilaterals. But that is untrue.[/quote]
Since the underlying formulas for $a = AP, b = BP, c = CQ, d = DQ$ were deduced for a tangential trapezium $ABCD$, the incircle formula $r =\ ^4\sqrt{abcd}$ is true for tangential trapeziums (the sums of 2 pairs of the adjacent angles are equal to $180^o$). The second type of tangential quadrilaterals, for which the formula is true, are bicentric quadrilaterals (the sums of 2 pairs of the opposite angles are equal to $180^o$). Indeed, for a tangential quadrilateral $ABCD$

$r = a \tan{\frac \alpha 2} = b \tan{\frac \beta 2} =  c \tan{\frac \gamma 2} = d \tan{\frac \delta 2}$

$r^4 = abcd \tan{\frac \alpha 2} \tan{\frac \beta 2} \tan{\frac \gamma 2} \tan{\frac \delta 2}$

For a tangential trapezium $ABCD$ with the bases $AB$, $CD$,

$\tan{\frac \alpha 2} = \frac{1}{\tan{\frac \delta 2}},\ \tan{\frac \beta 2} = \frac{1}{\tan{\frac \gamma 2}}$

$\tan{\frac \alpha 2} \tan{\frac \beta 2} \tan{\frac \gamma 2} \tan{\frac \delta 2} = 1$

$r^4 = abdc$

For a bicentric quadrilateral $ABCD$,

$\tan{\frac \alpha 2} = \frac{1}{\tan{\frac \gamma 2}},\ \tan{\frac \beta 2} = \frac{1}{\tan{\frac \delta 2}}$

$\tan{\frac \alpha 2} \tan{\frac \beta 2} \tan{\frac \gamma 2} \tan{\frac \delta 2} = 1$

$r^4 = abdc$

However, nothing in the problem conditions implies that the defined tangential $ABCD$ should be a tangential trapezium or a bicentric quadrilateral and in fact, it is neither, although it is close to a bicentric quadrilateral. Using the result of the subsequent posts, $r = \sqrt{647}$ and the angles of the given quadrilateral $ABCD$ are:

$\alpha = \measuredangle DAB = 2 \arctan{\frac{r}{AP}} = 2 \arctan{\frac{\sqrt{647}}{19}} \doteq 106.483^o$

$\beta = \measuredangle ABC = 2 \arctan{\frac{r}{BP}} = 2 \arctan{\frac{\sqrt{647}}{26}} \doteq  88.744^o$

$\gamma = \measuredangle BCD = 2 \arctan{\frac{r}{CQ}} = 2 \arctan{\frac{\sqrt{647}}{37}} \doteq  69.014^o$

$\delta = \measuredangle CDA = 2 \arctan{\frac{r}{DQ}} = 2 \arctan{\frac{\sqrt{647}}{23}} \doteq  95.759^o$

$\alpha + \beta + \gamma + \delta \doteq 360.000^o$

$\alpha + \gamma \doteq 175.497^o < 180^o$ (but close)

$\beta + \delta \doteq 184.503^o > 180^o$ (but close)

which explains, why the incorrect formula gives the value of $r$ so close to the value of $r$ obtained from the correct formula.


Show that in any triangle $ABC$ the following inequality holds:
$\frac{1}{sinA}+\frac{1}{sinB}+\frac{1}{sinC} \geq \frac{2\pi}{\sqrt{3}} (ABC)^{-{\frac{1}{3}}}$,
where $A$,$B$,$C$ are in radians.

I don't know how did you obtain that,but Jeane it is easy to see that $\frac{1}{sinA} +\frac{1}{sinB} +\frac{1}{sinC}\geq2\sqrt3$ ;)

this is stronger than 1/sina+1/sinb+1/sin >=2sqrt(3)


find and algebraic formular to find the C...
the formular to find D was D=12*(0.8)n-1 but has nothing to do with C....

i think thats about it... A+ question good luck

[u]N	                       D	                                 C[/u]
1	                       12                                      12
2	                       1.6	                                13.6
3	                       0.8	                                14.4
4	                       0.4	                                14.8
5	                       0.2	                                15
6	                       0.1	                                15.1
7	                       0.05	                                15.15

firsty thanks for the welcome

yes but whats the algabraic equation though...

i have found pattern but can't write it as an equation...

thank you

If the pattern of the differences is a geometric progression with common ratio $r$, then your succession must be in this form:
$C_{n}=a+b\cdot r^{n}$.
Substituting the first values, you'll know $a$ and $b$:
$12=a+b\cdot 0.5$
$13.6=a+b\cdot 0.25$

Or you could do it the hard way:
[hide]If $n>2$, $\frac{D_{n}}{D_{n-1}}=0.5$, so $\frac{D_{n}}{D_{2}}=\frac{D_{n}}{D_{n-1}}\frac{D_{n-1}}{D_{n-2}}\cdots\frac{D_{3}}{D_{2}}=0.5^{n-2}$, and then $D_{n}=1.6\cdot 0.5^{n-2}=6.4\cdot 0.5^{n}$

$C_{n}=D_{1}+\sum_{i=2}^{n}{D_{n}}=12+6.4\sum_{i=2}^{n}{0.5^{n}}=12+6.4\frac{0.5^{2}-0.5^{n+1}}{1-0.5}=\cdots$[/hide]


rational
decimal representation
number theory
IMO Shortlist

Let $f(n)$, $n=1,2,\ldots$ be the decimal representation of x. Then the decimal representation of y is $g(n) = f(2^{n})$.
x is rational, therefore the sequence is eventually periodic, that is, there are $t,x_{0}\in \mathbb{N}^{+}$ such that for all $x > x_{0}$ we have $f(x) = f(x+t)$.
By induction, we get that for all $x,y>x_{0}$ such that $t \mid x-y$ we have $f(x) = f(y)$.

Let's write $t = 2^{k}d$, with k nonnegative and d odd.
For all $x>k$, we have $t \mid 2^{x+\phi(d)}-2^{x}= 2^{x}(2^{\phi(d)}-1)$ because $2^{k}\mid 2^{x}$ and ${d \mid 2^{\phi(d)}-1}$.
Therefore, for all $x>\mbox{max}(k,x_{0})$ we have $f(2^{x+\phi(d)}) = f(2^{x})$, and finally $g(x+\phi(d)) = g(x)$.
So, also $g(x)$ is eventually periodic.
And y is rational  :)

$x$ is rational .Suppose , the decimal representation of $x$ contains infinitely many non-zero digits after decimal.
So , the digits in its decimal representation eventually will appear periodically.
let , the minimal period be $k$  (after the digits start appearing periodically)
hence , there exists some $M\in N$ such that , for $n_1 , n_2 \ge M$ ,
$2^{n_1}$th and $2^{n_2}$th digits after decimal are equal in the decimal representation of $x$ if
$2^{n_1}=2^{n_2}(mod k)$  .
Say , $k=2^p.q$ where $p\ge 0$ and $q$ is odd .
Now , note that , $2^{n_1}=2^{n_2} (mod k) $ if and only if  $n_1=n_2(mod r)$
where $r$= order of 2 moduldo $q$.
So , there exists $M$ such that , for $n_1,n_2 \ge M$ , $n_1$ and $n_2$th digit in the decimal representation of $y$ are equal if and only if $n_1=n_2(mod r)$ . hence , y is rational .

On the other hand , if $x$ contains only finitely many non-zero digits after the decimal place , then y also contains only finitely many non-zero digits after decimal , hence y is rational in this case too . :)

if $x$ is rationnal, then either its decimal representation contains a finite number of digits, or it's digits sequence is eventually periodic, after a certain number of first digits.

Dealing with the first case is not difficult at all: since $x$ has an $m$ finite number of digits after the decimal point, then $y$ has at most $\log{m}$ digits after the dot point, hence $y$ is rationnal as well.

Let's move to the second case. Since $x$ has infinitly many digits after the decimal point, $y$ has also infinitly many digits. So it remains to prove that, if the digits of $x$ are eventually periodic, so are the digits of $y$.

Note $K$ the period of the digits of $x$. It's enough to prove that $(2^n)$ is eventually periodic modulo $K$. If $K$ is a power of $2$,  say $K=2^a$, then eventually the sequence will be congruent to $0$ mod $K$. If $K$ is not a power of 2. Set $K = 2^a.m$ where m is an odd integer.

Suppose the assumption is true. That is $(2^n)$ is eventually periodic modulo $K$. This is equivalent to the following: there exists an integer $j$ such that starting from an $n$ sufficiently large we get for all $N > n$, $2^{N+j} = 2^N [K]$, or $2^{N+j-a} = 2^{N-a} [q]$, or $j = 0[ord_2(q)]$. Thus, taking $j = ord_2(q)$, the assumption remains true, and thus the sequence $(2^n)$ is eventually periodic modulo $K$.

[quote=Sketshup]

Note $K$ the period of the digits of $x$. It's enough to prove that $(2^n)$ is eventually periodic modulo $K$. If $K$ is a power of $2$,  say $K=2^a$, then eventually the sequence will be congruent to $0$ mod $K$. If $K$ is not a power of 2. Set $K = 2^a.m$ where m is an odd integer.

[/quote]

It seems like everyone let $K = 2^a \cdot m$, but the following solution will not (so is it right?):

Consider $2^1, 2^2, ..., 2^{K+1} \pmod K$. There are $K+1$ numbers in this sequence, so by Pigeonhole Principle, there exists $a$ and $b$ ($a<b$) such that $2^a \equiv 2^b \pmod K$. Thus, $2^{a+i} \equiv 2^{b+i} \pmod K$ for all nonnegative integers $i$ i.e. $2^{n} \equiv 2^{n+b-a} \pmod K$ for all sufficiently large $n$ i.e. $(2^n)$ is eventually periodic modulo $K$.

We begin with a lemma.

[b]LEMMA.[/b]  If $t\in (0,1)$ is rational, then the decimal representation of $t$ repeats after some time, and vice versa.

[i]Proof.[/i]  The backwards direction is well known.  For the forwards direction, assume there are $j$ non-repeating digits before the “block” of repeating digits.  We can simply take $\frac{l}{10^j}+\frac{m}{10^j}$ for appropriate the appropriate $l$, which is clearly rational, and for $m\in (0,1)$, a repeating decimal that begins repeating immediately.  Thus, we only need to prove for repeating decimals that begin to repeat immediately.

We denote the number of digits after which the decimal representation of $m$ repeats to be $r$.  However, note that we have $r=p\cdot w$, where $p$ is a positive integer in $[1, 10^{r}-1]$ and $w=\overline{0.00\ldots 0100\ldots 0100\ldots 0100\ldots}$ where there are $r-1$ zeroes between each pair of ones.  We can show that $w$ is rational by summing  the geometric sequence $\frac{1}{10^r}+\frac{1}{10^{2r}}+\frac{1}{10^{3r}}\ldots=\dfrac{\frac{1}{10^r}}{1-\frac{1}{10^r}}$ with a well-known formula, which is rational. $\square$

Now, for the problem, note that by the lemma we only need to prove that $y$ repeats; but this is equivalent to proving that $2^n \pmod{r}$ cycles as $n$ increases over positive integers for positive integer $r$.  However, by Euler’s totient theorem, we have $2^{\phi(r)}\equiv 1\pmod{r}$, so we are done. $\blacksquare$

[quote=LMat]Is this question basically asking if $2^n$ is eventually periodic modulo any number? I thought that would just go without saying since there is a finite number of remainders and multiplying a number with a particular remainder by $2$ always produces the same new remainder?[/quote]
Yep, that's why this problem is nearly trivial.

My solution:
Let $x=0.x_1x_2x_3 \cdots$ Since $x$ is rational, hence we can write $x=0.\overline{x_1x_2 \cdots x_m}$. Then $y=0.x_2x_4x_8x_{16} \cdots$
Now, it is easy to see that if $i \equiv j \pmod{m}$, then $x_{i}=x_j$. Thus it suffices to show that the sequence $\langle 2^{n} \rangle_{n=1}^{\infty}$ is periodic modulo any number $m$. This is clear by the pigeonhole principle, since we must have $2^k \equiv 2^l \pmod{m}$ for some $k \ne l$, and this clearly implies that the sequence is periodic. $\blacksquare$

[u]Lemma:[/u] The sequence of digits of the decimal expansion of a number is periodic iff the number is rational.

[u]Proof of Lemma:[/u] The only if direction is very easy, since if the decimal expansion is periodic, we can write the number as an infinite geometric series, which we know sums to a rational number. Now let us prove the if direction. Consider long dividing $m/n$. We will get a sequence of remainders:
\begin{align*}
10m&=q_1n+r_1 \\
10r_1&=q_2n+r_2 \\
10r_2&=q_3n+r_3 \\
&\vdots
\end{align*}
The sequence $q_1,q_2,\ldots$ are the digits of $m/n$. Since $0 \le r_i \le n-1$, by pigeonhole, there must exist $r_i=r_j$, and hence $q_i=q_j$, for some $0\le i,j\le n$, $i\not = j$. Then $q_{i+k}=q_{j+k}$ for all $k\ge 1$. Hence, the sequence of digits is periodic. $\square$

Let $k$ be the period of the decimal expansion of $x$. In order to show that $y$ is rational, we must show that its decimal expansion is periodic. This is equivalent to showing that $2^n$ is periodic $\pmod{k}$. Since $2^{\phi(k)} \equiv 1 \pmod{k}$, the sequence $2^n \pmod{k}$ must be periodic.

[hide=Solution][quote=ISL 2006 N2]For $ x \in (0, 1)$ let $ y \in (0, 1)$ be the number whose $ n$-th digit after the decimal point is the $ 2^{n}$-th digit after the decimal point of $ x$. Show that if $ x$ is rational then so is $ y$.

[i]Proposed by J.P. Grossman, Canada[/i][/quote]
[b][color=#000]Solution:[/color][/b] Suppose, Let $r$ be the period of $x$. So, Since, $x$ is ratiional $\implies$ $x=0.\overline{x_1x_2x_3 \ldots x_r}$ $\implies$ $y=0.x_2x_4x_8 \ldots$. So, we Basically need to show that, $2^n$ is periodic $\pmod{r}$. Note, if $r$ is odd, then $2^n \equiv$ $ 2^{\phi(r)+n} $ $ \equiv 2^{2\phi(r)+n} $ $\equiv \ldots \pmod{r}$ $\implies$ $y$ is rational. If $r$ is a power of $2$, then, clearly, $2^n$ becomes periodic, so $y$ is again rational. Now, Suppose if $r$ is even, then the residues $2^n \pmod{r}$ are even numbers smaller than $r$. Hence, by PHP, we'll eventually hit an even number which we had already been a residue and then the series will continue & we're again done! $\qquad \blacksquare$
[/hide]

Let $x_k$ and $y_k$ denote the $k$-th digits of $x$ and $y$ respectively. Obviously $y_k = x_{2^k}$. It is well known that a number rational if and only if its decimal representation is eventually periodic.

We shall invoke this fact repeatedly. Let $T_1$ be the period of the decimal representation of $x$ and write $T_1 = 2^n m$ for an odd integer $m$. Let $T = \varphi(m)$. I claim that the decimal representation of $y$ repeats with period $\varphi(m)$. Observe that
\[ a \equiv b \mod{T} \implies 2^a \equiv 2^b \pmod{m} . \]
If $a$ and $b$ are larger than $n$ we can conclude the stronger $2^a \equiv 2^b \pmod{T_1}$ since they are both divisible by $2^n.$. Thus if $a \equiv b \pmod{m}$ for big enough $a,b$, then $x_{2^a} = y_{2^b}$. Immediately $y_a = y_b$. Hence the decimal representation is periodic. Hence $y \in \mathbb{Q}$.

[hide=Storage]
[b]Claim:[/b] If a real number $z\in(0,1)$ is rational, then the decimal representation of $z$ is (eventually) repeating.
[i]Proof:[/i] Let $z=p/q$, where $\gcd(p,q)=1$, and let $q=2^a5^bM$, where $\gcd(M,10)=1$. Then, since $10^{\phi(M)}\equiv 1\pmod{M}$, $\frac{10^{\phi(M)}-1}{q}$ is equal to $\frac{k}{2^a5^b}$ for some integer $k$ and therefore terminates. Thus, if we let $z=0.z_1z_2z_3\ldots$, then for all sufficiently large $N$ $z_N=z_{N+\phi(M)}$ as desired.

[b]Claim:[/b] If a real number $z$ is eventually periodic in its decimal representation, then it is rational.
[i]Proof:[/i] The first however many terms which do not follow the repeating pattern don't matter, since they are finite and their sum is rational. For all of the repeating terms, by the geometric series formula they must converge to a rational value. Summing this proves the claim.

Now, since the case where $x$ terminates is trivial, we consider the case where $x$ repeats forever.

[b]Claim:[/b] Since $x$ is eventually periodic, so is $y$.
[i]Proof:[/i] Let $x=0.p_1p_2\ldots p_j\ldots p_k a_1a_2\ldots a_ka_1a_2\ldots a_ka_1\ldots$, so that the first $j$ decimal digits are somewhat arbitrary and after these, $x$ is periodic with period $k$. It is sufficient to show that the powers of $2$ are eventually periodic modulo $k$, because if this is true then after some point the digits of $y$ will be periodic since they must all come from $a_1,a_2,\ldots, a_k$. However, this is simple; let $k=2^mQ$, where $Q$ is odd. If $Q=1$, then clearly all powers of two will eventually be zero modulo $k$. Otherwise, note that $2^{\phi(Q)}\equiv 1\pmod{Q}$, so the powers of two will eventually be periodic modulo $Q$. Since they will also be equal to $0$ modulo $2^m$, by the Chinese Remainder Theorem the powers of two will be periodic modulo $k$ as desired. Thus, the decimal representation of $y$ is eventually periodic, which solves the problem.

[/hide]

It is trivial that $x\in\mathbb{Q}\iff x\text{ has terminating or eventually periodic digits}$. When $x$ has terminating digits, the problem is trivial, otherwise write $x=0.a_1\cdots a_kb_1\cdots b_lb_1\cdots b_lb_1\cdots b_l\cdots$, where $b_1\cdots b_l$ is the repeating part. Notice an obvious fact, that the sequence $(f_n)_{n=1}^{\infty}$ defined by: $f_1$ arbitrary, and $\forall n\ge 1$, $f_{n+1}$ is the residue then $2f_n$ is divided by $m$, must be periodic. Then \[y=0. a_2 a_4 \cdots a_{2^{[log_2 k]}}b_{2^{[log_2k]+1}-k} \cdots.\] By the above claim, set $f_1=2^{[log_2k]+1}-k$ we can see that $y$ must be eventually periodic.

Notice that as $x$ is rational its decimal is eventually periodic with say period $p \in \mathbb{N}$ and notice that $2^k$ is also periodic $\pmod{p}$ meaning that the decimal representation of $y$ is also eventually periodic and $y \in \mathbb{Q}$. $\blacksquare$ \\

It is well known that a number is rational iff its decimal representation is periodic.
So since $x$ is rational, let $m$ be the length of the period of $x$.
But, since $2^k \pmod{m}$ is periodic, the decimal representation of $y$ is periodic, implying that $y$ is rational.

Let $x$ have period length $n=2^a.b$ where $b$ is odd.Then $y $ will be periodic from the $a^{th}$ digit after the decimal point with a period $\phi (b)$ because
$$2^{a+\phi(b)} \equiv 2^a \pmod{2^a.b}$$

Assume $x$ has some random digits after the decimal point and then periodic of period $k.$

Then, $y$ will also have some random digits and then, it will be periodic of period $\varphi(k)$ because \[i\equiv j\bmod{\varphi(k)}\iff 2^i\equiv 2^j\bmod{k}\] for big enough $i$ and $j,$ that is, $i$ and $j$ greater than $\nu_2(k).$

Let $x$ have period $\ell$. Note that $2^y$ eventually cycles modulo $\ell$, since if $\ell$ is even, then we are trivially done. If $\ell$ is odd, we have $2^{\phi(\ell)} \equiv{1} \pmod{\ell}$ and therefore $2^{a+\phi(\ell)} \equiv{2^a} \pmod{\ell}$

ISL marabot solve

This is obvious if $x$ has finitely many digits after the decimal point, because it also implies that $y$ has finitely many digits after the decimal point.

If $x$ has infinitely many digits after the decimal point, then let its period be $k$. For odd $k$, this is obvious as $2^n$ cycles $\pmod k$ since $2^{\phi(k)}\equiv 1\pmod k$. Now consider what happens if $k$ is even. Then let $k=2^l m$ where $m$ is odd. After a certain point, when $n$ exceeds $l$, $2^n$ will cycle $\pmod k$. So $y$ is also rational.

Just a [i]little[/i] easy for an N2.

Note that if $x$ is rational, after a certain amount $C$ of decimal places the decimal representation of $x$ is periodic (including possibly all zeroes). Let this period be $P$. Consider the decimal places of $y$ past $\log_2 C$. Now observe that for $n$ greater than this quantity the $n$th decimal place of $y$ is completely determined by $2^n$ modulo $P$. It is easy to see that $2^n$ modulo $P$ is periodic, thus after $\log_2 C$ decimal places the decimal representation of $y$ is periodic, proving it is rational.

Because $x$ is rational, at one point, it must start repeating. Let the period of the repeating be $k$. Let $m$ be the least positive integer $n$ such that the $2^n$-th digit after the decimal point of $x$ is part of the repeating. We know that at least two of $2^m,2^{m+1},\dots,2^{m+k}$ are equivalent mod $k$, so let the exponents of those two numbers be $a$ and $b$. We can see that the $2^{a+1}$-th and the $2^{b+1}$-th digits in $x$ are equal and so on, meaning that $y$ now repeats with a period of $b-a$, meaning that it is rational. QED.

Suppose $x$ is rational. Notice after some amount of digits which do not repeat, $x$ repeats with period $t.$ It suffices to show this is also the case for $y.$ We claim there exists a constant $k$ such that $2^i\equiv 2^{i+k}\pmod{t}$ for sufficiently large $i.$ Indeed, let $t=2^ab$ where $2\nmid b,$ and suppose $i\ge a.$ Then, there exists $k$ such that $$2^k\equiv 1\pmod{b}\implies 2^{k+i-a}\equiv 2^{i-a}\pmod{b}\implies 2^{k+i}\equiv 2^i\pmod{2^ab}.$$ Hence, $y$ is also eventually periodic and we are done. $\square$

HUh

If $x$ eventually terminates we are done because $y$ eventually terminates. Otherwise let $x=0.\bar{d_1d_2d_3\dots d_k}.$ Since $2^i$ is periodic mod $k$ we're done because then the digits of $y$ are periodic.

Let $x=\Sigma_{i=1}^{\infty} 10^{-i} a_i$, where for all $i$, we have $a_i\in \{0,1,\dots,9\}$. Then $y=\Sigma_{i=1}^{\infty} 10^{-i} a_{2^i}$. Note that if $x$ is a terminating decimal, then so is $y$, and then $y$ is automatically rational. Else $x$ is a repeating decimal, so suppose that the digits of $x$ have a period of $r$, i.e. suppose that if $i\equiv j\pmod{r}$ then $a_i=a_j$.

    Note that $2^i\equiv 2^{i+\phi(r)}\pmod{r}$ for every $i\in \mathbb{Z}_{\geq 0}$, since $2^\phi(r)\equiv 1\pmod{r}$ by Euler's theorem. So for every $i\equiv j\pmod{\phi(r)}$, we have $2^i\equiv 2^j\pmod{r}$, which means that $a_{2^i}=a_{2^j}$. Therefore the sequence $(a_{2^i})_{i=0}^{\infty}$ is periodic with period $\phi(r)$, so $y\in \mathbb{Q}$.

Since $x\in \mathbb{Q}$ sequence of it's digits after the decimal point has period $m$, starting from some position. Thus for some big $k$ the $k-\text{th}$ digit of $y$ depends on remainder $a_i$ of $2^k$ mod $m$. But $\left \{ a_i\right \}$ is clearly periodic from some member, implying $y\in \mathbb{Q}.$

[i]Solution:[/i] The solution is a casework on whether the decimal expansion of $x$ terminates or not.

[b]Case 1:[/b] $x$ terminates in its decimal expansion.

Say $x = 0.a_1a_2\ldots a_k$ where $a_i$ is a digit for $i \in [1,k]$. Let $\alpha$ be a number such that $2^{\alpha} \le k < 2^{\alpha+1}$. Observe that that the first $\alpha$ digits of $y$ will be $a_2, a_4, \ldots, a_{2^{\alpha}}$. Every digit beyond that will be 0. This means $y$ must have a terminating decimal expansion therefore $y$ must be rational as desired.
---------
[b]Case 2:[/b] $x$ has a non-terminating decimal expansion.

This is the more interesting part of the problem. It is well-known that digits of a non-terminating decimal expansion are eventually periodic iff it is a rational number. This means digits of $x$ also must be eventually periodic. Therefore $x$ can be written as
    \[x = 0.a_1a_2\ldots a_k \, \overline{b_1b_2\ldots b_m}\]
where again $a_i$ and $b_j$ are digits. Here $a_i$ is non-periodic part and $b_j$ is periodic part. It is easy to see that $m$ is the period of the repeating part. Once more, let $\alpha \in \mathbb{Z}^+$ such that $2^\alpha \le k < 2^{\alpha + 1}$. One can again determine the first $\alpha$ digits of $y$ as stated in the above case. Say the $(\alpha + 1)$th digit is some $b_l$. By basic modular arithmetic, the $(\alpha +2)$th digit will be $b_h$ where $h = l\cdot 2 + k \pmod{m}$. The next digit can be generated similarly(a small induction which is skipped). Since we want to show that $y$ is rational, it suffices to show its decimal expansion is also eventually periodic. This boils down to showing there exists distinct $a,b$ such that
    \[2^al + (2^a-1)k \equiv 2^bl + (2^b-1)k \pmod{m} \iff (l-k) (2^a-2^b) \equiv 0 \pmod{m}\]
Now since $2^a$ is periodic modulo $m$, we are done. $\blacksquare$

[b]Remark.[/b] The last congruence is the $a$th digit after the non-periodic part, therefore the congruence above makes sense.

:o my first NT from some contest, it's actually time to stop doing just geo, i'm way too numbax T__T

[hide=Page 1][img]https://i.imgur.com/xoCoYC4.jpg[/img][/hide] [hide=Page 2][img]https://i.imgur.com/csgIpBm.jpg[/img][/hide]

handwritten solution images attached

[hide=Solution]Firstly, if $x$ terminates, then $y$ also terminates, implying that both are rational. Now, if $x$ has a length of infinity, then it must be of the form $0.X\overline{a_1a_2\dots a_n},$ where $X$ and $Y$ are both strings and $Y$ repeats infinitely. Suppose $X$ has $x_1$ digits. To prove that $y$ is rational, it suffices to show that $y$ starts with a string and then repeats another string. Now, suppose $2^k>x_1>2^{k-1}.$ We claim that for $i\geq k$, the $i$th digit after the decimal point of $y$ is $a_{(2^i-x_1)\pmod{n}}.$ It suffices to show that for some $m$ and $x_2,$ $2^{i+m}-x_1\equiv 2^i-x_1\pmod{n}$ holds for all $i\geq x_2.$ This is clear, since for sufficiently large $x_2,$ we $2^i$ has more powers of $2$ than $n,$ and taking away those powers of two, $n$ would be odd, allowing us to use Fermat's Little Theorem to finish. [/hide]

Someone please proofread because [s]i think[/s] this doesn't make sense at all.

[hide=Solution Sketch]
Since $x$ is rational there can be $2$ cases----
[color=#f00]Case-(i)[/color] Decimal expansion of $x$ is terminating
In this case note that the decimal expansion of $y$ will also terminate (since after precisely $\lceil \frac{\log d}{\log 2} \rceil$ we have that $2^n>d$ where $d$ is the length of the finite decimal part and hence $y$ has a decimal expansion of length precisely $ \lfloor \frac{\log d}{\log 2} \rfloor $ and is thus rational.

[color=#f00]Case-(ii)[/color] Decimal expansion of $x$ is recurring.
Let the length of the recurring part be $k$.
 [color=#00f]Claim:[/color] The sequence $\{2^n\}$ is periodic modulo $k$.
Proof: Note that by Euler we have that $2^{\phi(k)} \equiv 1 \pmod{k}$. Also by Euclid's Division Algorithm, any number $j=m.\phi(k)+r$ where $r \in [0,\phi(k)-1]$. Thus $2^j \equiv 2^{m\phi(k)}.2^r \equiv 2^r \pmod{k}$. Running $r$ through $[0,\phi(k)-1]$ gives the required periodicity.

Now since $2^n$ is periodic modulo $k$, we must have that the decimal expansion of $y$ will also be recurring and thus $y \in \mathbb{Q}$

Let the decimal expansion of $x$ repeat with period $k$. Notice that $\{2^n\}_{n \geq 1}$ is periodic modulo $k$, so the decimal representation of $y$ repeats too. Thus $y$ is rational.

if $x$ terminates then so does $y$

otherwise, $x$ will eventually repeat with some period $t$, in which case $y$ will repeat with some period $p | \phi(t)$.

storage from a while ago

I'm confused if this is a fakesolve or not...
    If x terminates y will terminate. If x is periodic after some number of digits with period $p=2^ij\forall i=v_2p$, it's well known that $2^n$ is periodic mod j and $2^n\equiv 0\pmod {2^i}$, hence it is periodic mod p as well. $\blacksquare$

Obviously if $x$ terminates then $y$ must also terminate, making it rational.

Otherwise, $x$ must eventually becomes periodic, suppose with period $k$. Clearly we can build a period wih Euler's Totient function and CRT on the sequence $\{2^n\} \pmod{k}$, making $y$ periodic and thus rational.

The bulk of the problem is in the following lemma:
[b]Lemma.[/b] If $\alpha$ is rational if and only if its decimal representation terminates, or is eventually periodic.
[b]Proof.[/b] The $\Longleftarrow$ is standard. We thus show $\implies$. Let $\alpha = p/q < 1$ (if $p/q > 1$, just simplify it). Then do long division of $p/q$. We note that doing this process, we always add $0$s to the back of our remainder. If it terminates (this happens if the remainder is 0), we are done. Otherwise, to show periodicity, it suffices to show the same remainder will appear twice. This is true by pigeonhole principle, since there are only $q$ possible remainders.

If $x$ terminates, then $y$ also terminates, hence $y$ must be rational. Otherwise, $x$ is eventually periodic. Take this period to be $P$. Note that $2^{k + \phi(P)} \equiv 2^k \pmod P$, i.e. $y$ will also be eventually periodic; it must hence be rational.

If the decimal expansion of $x$ terminates, then it is clear that the decimal expansion of $y$ must terminate too, making it rational. If the decimal expansion of $x$ repeats, let the period be $p$. The sequence $\{2^n\}$ is periodic modulo $p$, so the decimal expansion of $y$ also repeats, implying $y$ is rational. $\square$


Given $ a,b,c \ge 0$.Prove that:
$ \sum\frac{a^2}{(b\plus{}c)^2}\plus{}k^2\plus{}2 \ge 2k \sum\frac{a}{b\plus{}c}$

What is $ k$  ??

the inequality will be very easy if $ k\in]\minus{}\infty;1]$


ARML
geometry
logarithms
ratio
conics
parabola
3D geometry

Some of you may recall the first [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=30264]ARML Practice Series[/url].  ARML's going to be here in exactly one month (June 2nd/3rd).

Here's how the practice series will go

\[ \text{Rules}  \]

[i][u]Time Limit:[/u][/i] You have until I post the solution to a problem to PM me with a solution.  I will post solutions approximately 24 hours after I post the problem.  You will always have [i]at least[/i] 24 hours but possibly more (this all depends on my schedule).  Check the [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=86171]solution thread[/url] to see which problems have solutions posted to already.

[i][u]Calculator Usage:[/u][/i] I will specify for each question whether or not calculator usage is permitted.

[i][u]Scoring:[/u][/i] Correctness of an answer will be worth anywhere from 1 to 10, inclusive.  This value will be stated along with the problem itself.  The more difficult a problem is, the more points it will be worth.

I will also post exemplary solutions in the solution thread.  You will receive two bonus points for each solution that you have posted here.

[edit: changed one thing about the scoring]

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

No calculators, 3 points

A box 4 by 6 by 8 is resting on a floor.  A box 2 by 3 by 5 is placed on top of the first box forming a two-box tower.  If $A$ is the exposed surface of the tower, compute the least possible value of the area of $A$.

As I said before, you have until I post the answer to a problem to send in solutions.  So even though I'm posting problem 2, problem 1 can still be answered up until I post the solution (which will be in a couple hours).

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

Calculators allowed, 6 points

Let $f(x)=(x-1)(x-2)^2(x-3)^3\cdots(x-1999)^{1999}(x-2000)^{2000}$.  Compute the number of values of $x$ for which $|f(x)|=1$.

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

4 points, no calculator

Compute the largest real value for $b$ such that the solutions to the following equation are integers:

\[ \left(\log_{2^{10}}x^{2b}\right)^2 = \log_{2^{10}}x^4.  \]

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

No calculators, 8 pts total

Assuming that $a^3+b^3 = c!$ has solutions, and $c$ is at least 12:

A. (3 pts) Prove that the largest prime less than $c$ does not divide $a$.
B. (5 pts) Prove that $a+b$ is a multiple of 330.

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

calculators allowed, 4 points

In triangle $ABC$, angle bisectors $\overline{AD}$ and $\overline{BE}$ intersect at $P$.  If $a=3, b=5, c=7, BP=x,$ and $PE=y,$ compute the ratio $x: y$ where $x$ and $y$ are relatively prime integers.

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

calculator allowed, 10 pts total

Throughout this problem, the points $A(a,a^2), B(b,b^2), C(c,c^2),$ and $D(d,d^2)$ represent distinct lattice points on the parabola $y=x^2.$

Let the area of triangle $ABC$ be $K.$  It can be shown that \[ K=\frac 12|(a-b)(b-c)(c-a)|.  \]

1. (2 pts) Show that $K$ must be an integer.
2. (2 pts) Show that $K=3$ is the only possible prime value for $K$.
3. (3 pts) Show that $K$ cannot be the square of a prime.
4. (3 pts) Show that the area of quadrilateral $ABCD$ cannot be 8.

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

calculator, 4 points

Compute all integer values of $n, 90\le n\le 100$,  that can [i]not[/i] be written in the form $n=a+b+ab$, where $a$ and $b$ are positive integers.

Sorry about falling behind on the grading.  I'm not going to be able to update grading until after the AP Chem exam (which is tomorrow).  But this just gives you all the more time to work them! (be careful though...I'm probably going to catch up on all of them at once)

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

8 pts, no calculator

In concave hexagon $ABCDEF, m\angle A = m\angle B = m\angle C = 90^\circ, m\angle D = 100^\circ,$ and $m\angle F=80^\circ.$  Also $CD=FA, AB=7, BC=10,$ and $EF+DE=12.$  Compute the area of the hexagon.

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

calculator, 5 pts

When expanded as a decimal, the fraction $1/97$ has a repetend (the repeating part of the decimal) that begins right after the decimal point and is 96 digits long.  If the last three digits of the repetend are $A67$, compute the digit $A$.

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

no calculator, 7 pts

Let $[{x}]$ represent the greatest integer less than or equal to $x$.  Compute the number of first quadrant ordered pair $(x,y)$ solutions to the following system:

\begin{eqnarray*} x + [y] &=& 5.3\\ y + [x] &=& 5.7 \end{eqnarray*}

When sending me an answer, I please request that you put the number of the day in your title.  So something like ARML Practice Series Day 11 is perfect :)  It helps me with the grading.  Thanks :)

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

calculators, 7 pts

There was a chess tournament involving two eighth graders and [u]at least ten[/u] ninth graders.  Each contestant played once against each other contestant.  Each contestant received two points for a win, one point for a tie, and zero points for a loss.  The two eighth graders amassed a total of 20 points and each ninth grader earned $N$ points.  Compute $N$.

[quote="chess64"][quote="joml88"]Let $[x]$ represent the greatest integer less than or equal to $x$.[/quote]

For some reason that doesn't work... try $\left[x\right]$ maybe...

edit: oh and how many points is this worth, and is calculator allowed?[/quote]
Not needed ;)

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

calculator, 7 pts

Assume that as a cubical bar of soap is used, all edges shrink at a constant rate of $n$ units per day.  Starting with a full bar, the soap was used for 6 days and its surface area was cut in half.  Starting with a full bar of soap, compute exactly the time it would take for the volume to become one-eighth of the original volume.

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

calculator, 9 pts

Compute the smallest positive integer that can [i]not[/i] be the difference between a square and a prime, if the square is larger than the prime.

[size=150][color=darkred]Day 14[/color][/size]

calculator, 7 pts

Two right circular cones have parallel bases (that is, their bases lie in parallel planes), and the apex of each is (at) the center of the base of the other.  The cones intesect in circle $C$.  If the areas of the bases are 400 and 900, compute the area of circle $C$.

The problem is correct as stated.

If you believe there is an error with a problem, please PM me with a title that will get my attention so we don't clutter up this page.  I don't read PM's with solutions until I go through and grade all of them for that day, so make sure that your title will catch my attention.

[quote="jackb1115"]Should the bases have area $400$ and $900$, or $400\pi$ and $900\pi$?

JB[/quote]

no, it works out fine.

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

calculator, 6 pts

Define a sequence of integers as follows: $a_1=1, a_2=2, a_3=4, a_4=5, a_5=7, a_6=9,$ the next four terms are the next four even integers after 9, the next five terms are the next five odd integers after 16, and so on.  Compute $a_{1999}.$

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

no calculator, 6 pts

The diagonals of a convex polygon connect non-adjacent vertices.  The diagonals of a regular 10-sided polygon are drawn.  Compute the number of parallel pairs of diagonals.

[size=150][color=darkred]Day 17[/color][/size]

calculator, 10 pts

Let $ABCD$ be a regular pyramid whose edges have length 5.  Consider the set of pyramids of the form $AMNP$ where $M$ lies on $\over{AB}$, $N$ lies on $\over{AC}$, and $P$ lies on $\over{AD}$ such that $AM, AN,$ and $AP\in\{1,2,3,4\}.$  Compute the sum of the volumes of all such pyramids.

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

10 pts, no calculator

If $\sqrt[3]{\sqrt[3]{2}-1}$ is written as $\sqrt[3]{a}+\sqrt[3]{b}+\sqrt[3]{c}$ where $a,b,$ and $c$ are rational number, compute teh sum $a+b+c$.

ATTENTION: The ARML Practice Series will end at Day 21.  However, I might post some extra sets of problems or something, if there is a great enough demand.  And actually, I'm just going to go ahead and post the rest of the problems for the ARML Practice Series.

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

calculator, 8 pts

On the sides of right triangle $ABC$, squares are erected ($AB$ is the hypotenuse).  If $BC=68$ and $AC=204,$ compute the absolute value of the difference between the areas of $\triangle BDE$ and $CEF$.

[img]http://www.artofproblemsolving.com/Forum/album_pic.php?pic_id=872[/img]

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

calculator, 7 pts

Compute the number of distinct ways one can arrange the numbers 21, 31, 41, 51, 61, 71, and 81 from left to right so that the sum of every four consecutive numbers is divisible by 3.

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

10 pts, calculator

The unit hypercube in 8 dimensions can be defined as the set of points $(x_1,x_2,\ldots,x_8)$ such that $0\le x_i\le 1$ for $i\in \{1,2,\ldots,8\}.$  Suppose the hypercube is cut into smaller hyper-rectangular boxes with side lengths of $\frac 13$ or $\frac 23$ by hyperplanes whose equations are $x_i=\frac 13$ for $i\in\{1,2,\ldots,8\}$ Color the hyper-rectangular box with vertex on the origin red, color those adjacent to red hyper-rectangular boxes blue, and those adjacent to blue hyper-rectangular boxes red were "adjacent" means bordering along one of the hyperplanes $x_i=\frac 13$.  If $R$ equals the total volume of the red hyper-rectangular boxes and $B$ equals the total volume of the blue hyper-rectangular boxes, compute $R-B$.

This problem is REALLY cool!  Do not be discouraged by how highly specialized it seems.  I'll give some small hints in a couple of days probably.

This was from my first year on the New York City A team at ARML, team round 10.  I didn't understand it at all at the time, but it's really easy now :-)

i can't see the image for day19.  where are E and F supposed to be?

edit: nvm, fine now

I am grading up to problem 18 tonight.  You will have until at least the beginning of Sunday to do problem 19, 20, and 21.  I will have everything graded by the end of next Monday.

Are we required to submit solutions, or just answers?

Just answers.  But if you submit a solution and I use it for the solution thread you get 2 bonus points.

Assign the distance between the bases a length. Now we have radii of 20 and 30, respectively. Looking at the intersecting cones from the side, we have a line starting at (0,20) with slope -20, and a line starting at (1,30) with slope 30. Thus the two equations are: y=-20x+20 and y=30x, so we solve simultaineously for 50x=20, so x= 2/5. Now y=12, so the area of the circle is $\boxed{144\pi}$ actually, no pi involved if the base areas don't involve pi, so depending on the question it could be 144


A ball of twine has radius 3 inches. The cross section of a strand of this twine is a circle with radius 1/16 inch. Based on this, what is the length of the twine when it is unraveled? Ignore any stretching of the twine or imperfections in the shape of the ball of twine.

A. 256 ft.      B. 768 ft.        C. 1536 ft.       D. 3072 ft.

I have the answer, so I can tell you if it's correct or not, I just am not sure how to go about solving the problem.

P.S. This is from a MuAlphaTheta Geometry Regional March 2005 Test, question #9

How does one become a member of Mu Alpha Theta?

I'm not sure.. you can check out their website and then talk to your school about it. If you have a math club you might want to talk to your coach, they may know about it.

Well, I figured out the answer while in History class, heh.

You have to look at the wire like it's a cylinder.
Therefore we know that this cylinder has a radius of 1/16 in and has a height of x.
We know how to find the volume of a sphere 4/3(pi)r^3 which equals 36(pi)
We also know how to find the volume of a cylinder h(pi)r^2  which is x(pi)1/256
Since we know that the volume of the cylinder should equal the volume we can set these equations equal to each other:  36(pi) = x(pi)1/256
Cancel out the pi's and we get 36 = x/256
Multiply 256 to both sides and x (the height of the cylinder) = 768

Therefore choice (B) 768 ft is correct

Hmm.. as I was typing this up I noticed a dilemma.. the answer is in feet but the way I found the answer would leave me with 768 inches, as far as I can see it does at least.

Can anyone help revise or tell me why my logic fails in this instance? Thanks!

Your answer is correct. From 36=x/256:

36 in = x in/256

36*256 in = x in

3*256 ft = (The answer)

3*256=768

Oh ok, I see, during the class I must have been using my calculator and I didn't write down the step where I converted from inches to feet. Okie doke, thanks for the confirmation! :)


The sum of ten consecutive odd numbers is 640. What is the
greatest of these ten numbers?

The greatest number: 73

In an arithmetic sequence (addition/subtraction in a sequence), the sum is denoted by:

S_n = n*(a_1 + a_n)/2, where n is the number of terms in the sequence

Because the sequence is based on consecutive odd numbers, each number is +2 greater than the number before. Therefore, the tenth and last number (a_n) must be the first number + 18.

a_n = a_1 + 18

In addition, we know the sum (s_n) is 640. Thus after substituting,

640 = 10 (a_1 + (a_1 + 18))/2
1280 = 180 + 20*a_1
1100 = 20a_1
55 = a_1

a_10 = 73


find all functions $f: \mathbb{R}\to \mathbb{R}$ such that
 $f(x^{2}-y^{2})=xf(x)-yf(y)$ holds for every $x,y \in \mathbb{R}$

Choose $x=y=0$ then $f(0)=0$.
Choose $y=0$ then $f(x^{2})=xf(x)\forall x\in\mathbb{R}$(1).
Therefore $f(x^{2}-y^{2})=f(x^{2})-f(y^{2})\forall x,y\in\mathbb{R}$(2). Denote $g(x)=f(x)-f(1)x$ , then $g$ satisfying (1) and (2), but $g(1)=g(0)=0$. Now, easily see that $g(x)=0\forall x\in\mathbb{R}$.

Final, $f(x)=ax\forall x\in\mathbb{R}$.

how do you show $g(x)=0 \forall x\in \mathbb{R}$

This problem is posted before here http://www.mathlinks.ro/Forum/viewtopic.php?p=337857#p337857


Is $ \text{\LaTeX}$'s algorithm for end-of-line word splitting with hyphenation and the justified alignment of text any more superior, typographically speaking, than Microsoft Word's, aesthetically? If I understand correctly, $ \text{\LaTeX}$ tries several cases and measures 'badness'... while Word just makes a new line ad hoc and formats each line independently. Does this result in any big differences?

Have a look at [url=http://nitens.org/taraborelli/latex]The Beauty of LaTeX[/url] particularly [url=http://nitens.org/taraborelli/latex#justification]Line breaks, justification and hyphenation[/url] and [url=http://oestrem.com/thingstwice/2007/05/latex-vs-word-vs-writer/]LaTeX vs. Word vs. Writer[/url]


trigonometry
complex numbers
calculus
calculus computations

define  the  sum  of  the  series
$ \sum_{n \equal{} 1}^{\infty}\frac {\sin nx}{n!}$

thanks

Hint: $ \sin nx\equal{}\text{Im}\,(e^{inx})\equal{}\text{Im}\,\left((e^{ix})^n\right).$

That, and the imaginary part of a sum is the sum of the imaginary parts.

Note also that the natural place to start this sum would be at $ n\equal{}0,$ and you can do just that by noting that the $ n\equal{}0$ term would be zero.


trigonometry
calculus
integration
calculus computations

Solve the differential eqn:

\[ \frac{d^2 \theta}{d t^2} + k \cos {\theta} = 0 \]

Warning: the complete solution involves elliptic integrals which cannot be evaluated in terms of elementary functions.

Damn! I hoped the solution would be simple to solve my Physics problem. but it seems my hope was in vain. Anyways, it will be good to know the solution for future. please post if you have the time!  :lol:

We can do quite a few things with this without writing an explicit solution for $\theta(t).$

There are stationary points (constant solutions) at $\theta=\left(k+\frac12\right)\pi.$ (And $\theta'=0.$) For even values of $k,$ this is an unstable saddle point. (All solutions beginning near there eventually depart the neighborhood.) For odd values of $k,$ this point is stable but not asymptotically stable - all solutions beginning near there trace a periodic path staying in the neighborhood.

Note that $u(t)=\frac12\left(\frac{d\theta}{dt}\right)^2+k\sin\theta$ must remain constant for a solution. (Note the connection to energy.)

If $u(t)<k,$ the solutions are bounded and periodic. If $u(t)>k,$ the solutions are unbounded.


i was working on a chinese tst problem that i found on this forum and i ended up with
the following

$ 8a^{4}\equal{}(2k)(2k\plus{}1)$

i need to show that $ a$ or $ k$ is 0 and i think using infinite descent might work, however, i dont really know how i can use it...

does anyone know?

Don't have much time now but I will try to help. You can eliminate some stuff by plugging in that $ k\equal{}4b$ as otherwise $ 8$ will not divide the left hand side. Now you have:

$ a^{4}\equal{}b(8b\plus{}1)$

Now $ b$ must be congruent to $ 0$ or $ 1$ modulo $ 8$.


linear algebra
matrix
function
vector
linear algebra unsolved

Let $A, B \in \mathcal{M}_{n}(\mathbb{R})$ be two symmetric matrices.
We define $f: t \mapsto \max \text{ Sp}(A+Bt)$.
Show that $f$ is convex.

(Sp denotes the spectrum.)

Problem is easy with glance to this:
If $A$is a symmetric matrix,then max value of function $g(x)=x^{T}Ax$defined on real vectors $x$with norm $1$ is $max sp(A)$ and the maximum is gained for eigenvector corresponded to $maxsp(A)$.
To show the convexity of $f$:
$f(s.t_{1}+(1-s).t_{2})=z^{t}.(A+B(s.t_{1}+(1-s)t_{2})).z =s.z^{t}.(A+B.t_{1})z+(1-s).z^{t}.(A+B.t_{2})z$
 which $z$is a vector with unit norm.
According to above discussion:
$z^{t}.(A+B.t_{1})z\leq maxsp(A+B.t_{1})$
$z^{t}.(A+B.t_{2})z\leq maxsp(A+B.t_{2})$
So:
$maxsp(s.t_{1}+(1-s).t_{2})\leq s.maxsp(A+B.t_{1})+(1-s).maxsp(A+B.t_{2})$


The sum of 5 real numbers is 8 and the sum of their squares is 16. What is the largest possible value for one of the numbers?

I have a solution, but I do not understand how one would come up with it.

spoiler:

[hide]let us denote the numbers as a, b , c , d, e with a <= b <= c <= d <= e.

then

a + b + c + d + e  = 8 or a + b + c + d = 8 - e

and

a2 + b2 + c2 + d2 + e2=16 or

a2 + b2 + c2 + d2 = 16-e2.

(

the latter halves of these equations are very important, since it will give us something to work with later (specifically, now).

using the cauchy-schwarz inequality,

4*(a2 + b2 + c2 + d2) >= (a+b+c+d)2

note that equality exists when and only when a = b = c = d.

the reason we broke this up is so that now we can get an inequality for e, which is what we want anyway, right? so:

(16 - e2)*4 >= (8-e)2

or, simplifying, 5e2 - 16e <= 0

=> e(e-16/5) <= 0.

=> the maximum value for e is 16/5, and this occurs in the equality case when a=b=c=d = 6/5[/hide]

Now where is your question about motivation?

Yeah, Nukular's approach is the one I came up with.  Perhaps Fiery was asking about the solution on the kalva site, which does seem to come out of the blue.  The kalva solution comes from looking at the equality case.  Namely, suppose that four of the numbers are equal (to say x) and the other number is y.  Then you can solve to find x = 6/5 and y = 16/5 (or x = 2 and y = 0, but that case is not so interesting here).  Thus the equality case seems to occur when four of the numbers are 6/5.  That's why the kalva solution looked at (a - 6/5)2 + (b - 6/5)2 + etc.  Does that make sense?

By the way, I took this USAMO when I was a kid!  I have no idea whether I got this question right back then.

Ah, I see, Nukular's solution seems logical. And yes, Ravi, I was asking about the solution on kalva. Anyways, thanks for the help.

Out of curiosity ravi, what score did you get on that usamo?

To tell the truth, I don't remember my score, because it was more than 20 years ago.  But I'm sure it was bad.  (I remember getting Question 2, the one about maps, and not much else.)  I was 14 that year, and had essentially never seen olympiad-level problems then.

You guys are so lucky to have quality books and web sites (like this one!) to study from.  The original reason I hung around this site was to learn about future math contests for my 9-year-old daughter.  But now I guess I hang around for the fun problems...

P.S. Tetrahedr0n, this problem reminds me of another USAMO question that you asked about here:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?p=63954#63954[/url]
Actually, I think that problem was a little tougher.

ravi the reason i asked you was that my mother took the final (national) round of the romanian olympiad in 1977 and 1978, the year of the usamo in question. it was an interesting coincidence. i like your solution for the other usamo problem a lot...  i just wonder how you could come up with that?

Tetrahedr0n, you're fortunate to have such a talented mom.  Does she help you with math now?

For the other (tougher) USAMO problem, it took me a lot of pages of messing around!  In both my proofs for that problem, I was guided by the equality case (all 2's except one 2 - n).  I was looking for a sum that had two properties:

(1) Each term is 0 in the equality case (and hopefully nonnegative/nonpositive in any case).
(2) The sum can be evaluated in terms of the sum of the numbers and the sum of their squares.

I agree that the kalva solution to that problem is not elegant.  I think I prefer my second proof to my first, but I'm still not sure that I have found the "best" proof.


minh la thanh vien moi, minh thay dien dan nay that bo ich
mong se duoc trao doi voi cac ban nhieu van de

Chán thật, từ nay anh Hungkhtn không còn lên nữa rồi. Bây giờ đến lượt mình cũng không thể tiếp tục lên đây được nữa. Tạm biệt tất cả.
Tự hào là người Việt Nam!


This is a game and frankly I dont know the name of the game, so I just call it "moving object".
We have 4 red objects and 4 blue objects in a line and there are 2 blank spaces between them:
r r r r _ _ b b b b
We have to move red and blue alternatively.
There is only 2 legal moves:
+ slide 1 space: before: ... x _ ... after: ... _ x ...
+ jump over other object: before: ... x y _ ... after: ... _ y x ...
and red can only go to the right and blue can only go to the left.
The question is : Is that possible to move all red in to other side and all blue into other side too, which will make the line look like b b b b _ _ r r r r ?

Try [url=http://www.cut-the-knot.org/SimpleGames/FrogsAndToads.shtml]this[/url]. It also suggests a name for the game :).


I got my scores yesterday :lol: . A stupid mistake cost me a point in #2  :blush: . Anyway, I got a 24 and 2 commended solutions. Yay! How did you guys do?

man, how come half the people got perfect in first round.  these problem are not easy at all, especially the second one, it took me half hour to figure out.

[quote="thoobik"][quote="Anh!"]A stupid mistake cost me a point in #2 :blush: . Anyway, I got a 24 and 2 commended solutions. Yay![/quote]

The same on all counts.[/quote]

The same on most counts, change #2 to #3. The mistake is still stupid, though.

The real surprise is that I got a commended on #5... and I consider myself weak at geometry...  :cool:

25, first three commended. A 25 on this round will be a lot harder though.

[quote="mathfanatic"]25, last three commended.  I got the impression that commendations were given out based on solution length, i.e. how many steps you could not show without getting marked off.[/quote]

Varies by grader (I note this because solutions which are 6 pages per problem make graders sad!).  Some of the graders reward concise proofs, some reward rigorous ones.  Most reward concise, rigorous ones.  In other words, prove your assertions, but don't take 6 pages to do it.

[quote="white_horse_king88"]Wow.. only a 23, I'm sad now. Cuz ur all so good, and I just screwed up on number 2. Forgot x^2 + y^2 - 11 = 0. Meh.[/quote]

same here. 23, -2 on #2.

24 with a stupid mistake on the r,s,t,u one.
I thought they were all integers. Oh well. I'm happy with a 24.
I didn't submit with LaTeX, so none were commended.

[quote="PepeCamello"]
I didn't submit with LaTeX, so none were commended.[/quote]

LaTeX is only required to be published - it isn't required to be commended.

25, commended on #1.  I'm not listed on the website as having a 25, though.  I thought I submitted my permission form...

Hmm, if u thought they were all integers and got a 4 on it, how is it that a mistake of forgetting about the r>=s>=t>=u (or some permutation thereof) condiotion gets me only 1 point? :(

My friend made the same mistake PepeCamello did but he got a 25. So i think it depends on the graders.

And are there any criteria based on which commendation is given out?

I didn't do nearly as well as yall did but I am really happy with my score of 6.  This being my first year I was only able to solve 2 problems, 1 and 3 and I got a 4 on nuber one and a 2 on number 3.  Being in the 8th grade and doing that makes me really pleased though.

[quote="anhnguyen"]And are there any criteria based on which commendation is given out?[/quote]

[quote="rrusczyk"]Varies by grader (I note this because solutions which are 6 pages per problem make graders sad!).  Some of the graders reward concise proofs, some reward rigorous ones.  Most reward concise, rigorous ones.  In other words, prove your assertions, but don't take 6 pages to do it.[/quote]

I got a 25 and 1 commended solution (the last one)
im proud to be the only sevie on the perfect scores list (unless i missed someone when i looked)


How would I [url=http://mathworld.wolfram.com/LegendreSymbol.html]do the curly brace shown here in LaTeX?[/url][/url]

Use left( and \right) which sizes the brackets to the right size $ \left(\frac{a}{p}\right)$

But how would you have the multiple lines of text?

Ah! You want the cases enviroment, which gives stuff like:
\[ \pi\equal{}\begin{cases}22/7\text{ if you're lazy}\\
3.141594...\text{ otherwise}\\
\end{cases}\]

Basically, do dollar signs left-side-of-brace \begin{cases} line1\\line2\\....\\\end{cases} dollar signs


true or false
repeating decimal+repeating decimal=repeating decimal
repeating decimal×repeating decimal=repeating decimal
please ????????????????

Two propositions are all true because a finite decimal can also be denoted by a repeating decimal. If not,(if a finite decimal is not a repeating decimal), your assertions are all false, you can easily find the reason.


I have 5 red marbles, 4 green marbles, 3 blue marbles, 2 orange marbles, and 1 white marble.  I line up the marbles in a straight line.  What is the probablility that no two red marbles are next to eachother?

Does it matter what colour the other marbles are? Can you not just consider it as 5 reds and 10 not-reds?

Can someone explain how to do this? I suck at probability.

[hide]For some reason I get 2/13 using the balls and urns method-so (11C5)/(15C5).., werid thing is, I was studying for the AIME yesterday, and I encountered a similar type of problem..so I think I did it right
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=66513[/hide]

Here is a possible solution: just for simplicity, assume all the not-red balls are blue.
Place all the 10 blue balls on the table, so clearly the order does not matter. Then, there are eleven "gaps" where you can put the first red, including on either end. You can place this wherever. Then there are twelve gaps in which you can place the second red, but two of these gaps are next to the existing red, so the prob that it is legal is 10/12. If it is legal, you can place the third red in 13 gaps, but 4 are next to existing reds, so the prob that it is valid is 9/13. By a similar argument, the probabiltiy that the fourth is legal is 8/14, and the fifth: 7/15.
When you take the product of these fractions, it cancels to give 2/13.
I am not familiar with the US Olympiad system. Is this solution at an appropriate level?


Orice grup de ordin 2007 este comutativ :)

Poate se da la concurs :D
Da chiar..[hide]subiecte, ceva, stie careva?  Tot asa.. inainte de ONM :wink:  :D [/hide]
Oricum, bafta tuturor!

[quote="andyciup"]

Oricum, bafta tuturor![/quote]

Sa fie !! :showoff:

postez aici 3 subiecte de la cls a X-a, ca ceilalalti mai intarzie :P

problema 1:
dem ca ecuatia z^n + z +1=0 are o solutie complexa de modul 1 d.n.d. n restul impartirii lui n la 3 este 2.

problema 2:

rezolvati ecuatia: 2^(x patrat +x)  + log in baza 2 din x  = 2^(x+1)

problema 3: pt ce numere naturale n mai mari sau egale cu 2 numarul
a indice n = (n-1)^n^(n+1)  +  (n+1)^n^(n-1) este divizibil cu n^n?


[b][u]Problem[/u][/b]
Let P(x) is polynomial have degree $n>1$ with n positive roots differentiate. Prove that:
$\frac{1-nx}{x^{_{}}{2}}.P(x)+(1-\frac{1-nx}{x^{2}}).P'(x)-P''(x)=0$  have n positive roots differentiate.
:D

anyone give me idea  :) And I think this problem isn't difficult  :D


Let $ a,b,c >0$. Prove that

[list]$ (a\plus{}b) \left(\frac{a}{b}\plus{}\frac{b}{c} \right) \plus{} \frac{1}{b} \geq  2\left(\frac{ a}{b} \plus{} \sqrt{\frac{b}{c}} \right).$[/list]

Divide by b to get
$ (\frac {a}{b} \plus{} 1)(\frac {a}{b} \plus{} \frac {b}{c}) \plus{} \frac {1}{b^2} \ge \frac {2}{b}(\frac {a}{b} \plus{} \sqrt {\frac {b}{c}})$
Let $ \frac {a}{b} \equal{} x$, $ \frac {b}{c} \equal{} y$, and $ \frac {1}{b} \equal{} z$. Then we have to show
$ (x \plus{} 1)(x \plus{} y) \plus{} z^2 \ge 2z(x \plus{} \sqrt {y})$
$ x^2 \plus{} x \plus{} y \plus{} xy \plus{} (z \minus{} x \minus{} \sqrt {y})^2 \ge(x \plus{} \sqrt {y})^2$
$ x \plus{} xy \plus{} (z \minus{} x \minus{} \sqrt {y})^2 \ge 2x \sqrt {y}$.
$ x(1 \minus{} \sqrt {y})^2 \plus{} (z \minus{} x \minus{} \sqrt {y})^2 \ge 0$
Which is obviously true.
Equality holds when $ b \equal{} c$ and $ a \plus{} b \equal{} 1$.


greatest common divisor
number theory unsolved
number theory

let $ a_1\equal{}a$, $ a_{n\plus{}1}\equal{}pa_n\plus{}q$ where $ a,p,q\in Z$.
assume that $ (a,p)\equal{}(a,q)\equal{}(p,q)\equal{}(a,k)\equal{}(p,k)\equal{}(q,k)\equal{}1$ for some integer $ k>1$.
is it true that $ \{a_n\bmod{k}\}\equal{}Z_k$ ?

ps.
(.,.) means greatest common divisor

No, e.g. $ a\equal{}1, p\equal{}3, q\equal{}5, k\equal{}7 \implies a_n \equiv 1 \bmod 7$


Could people give me questions involving geometry?
I'm a bit shaky on those and it could help. Thanks in advance.

1. (Countdown) Each interior angle of a regular polygon measures 165 degrees. How many sides does the polygon have?
[hide]24[/hide]
--------------------------------------------------------------------------------
2. (Countdown) A cube is increased to form a new cube so that the surface area of the new cube is 16 times that of the original cube. By what factor is the volume of the cube increased?
[hide]64 [/hide]
-------------------------------------------------------------------------------
3. (Target) A cube has edge length 6 cm. What is the furthest distance between any two vertices? Express your answer as a decimal to the nearest hundredth.
[hide]10.39 [/hide]
--------------------------------------------------------------------------------
4. (Sprint) Triangle ABC is such that BC=12 cm , the point D is on the side AC and AB = AD = CD = BD . How many square centimeters are in the area of the triangle ABD ? Express your answer to the nearest whole number.
[hide]21[/hide]
--------------------------------------------------------------------------------
5. (Sprint) The surface area of a cube is 294 square centimeters. What is the ratio of the number of square centimeters in the surface area to the number of cubic centimeters in the volume of the cube? Express your answer as a common fraction in lowest terms.
[hide]6/7 [/hide]
--------------------------------------------------------------------------------
6. (Sprint) A triangle has sides measuring 4 , 5 and n . What value of n would make the area of the triangle as big as possible. Express your answer to the nearest hunderdeth?
[hide] 6.40 [/hide]
--------------------------------------------------------------------------------
7. (Sprint) Let ABC be a triangle. Let X be a point on AB and Y be a point on AC such that AX=XY=YB=BC . If the angle ABC measures 132 degrees, find the number of degress in the measure of the angle BAC .
[hide]12 [/hide]
--------------------------------------------------------------------------------
8. (Target) Points X=(0,0), Y=(4,6) and Z=(10,0 ) are given. How many units are in the length of the radius of the circle which passes through the points X,Y and Z ? Express your answer to the nearest tenth.
[hide]5.1 [/hide]

i think all of these are from ellis saabs page  :wink:
http://mathcounts.saab.org/mc.cgi

yashar.biz/mathcounts has a decent collection of tests.

[quote="Hustla25"]yeah man, how did u kno

do you have other mathcounts sites i can get probs from[/quote]

i did them for a week, every day, before our state competition


calculus
integration
function
limit
topology
absolute value
real analysis

I'm preparing for my final exam and I've been doing some old problems, including the following three.  I've written out what I hope are solutions so I'm just asking for them to be checked.

1) Does there exist a closed set $ E\subseteq [0,1]$ with $ m(E)\equal{}1$, aside from the obvious example $ E\equal{}[0,1]$?
[hide="Solution"]Let $ E$ be the set in question and $ E^{c}\equal{}C$ be its complement relative to $ [0,1]$, so $ E\cup C\equal{}[0,1]$.  Since $ E$ and $ [0,1]$ are closed, $ C$ is open and since $ m(E)\equal{}1$, $ m(C)\equal{}0$.  So we need an open null set.  But every open set must contain an interval (in $ \mathbb{R}$) and an interval is not a null set.  Hence no such set can exist.[/hide]

2) Let $ f$ be any function in $ L^{p}(\mathbb{R})$, $ 1\leq p\leq\infty$.  Show that $ \lim_{n\rightarrow\infty}\left\|f\chi_{\{\left|f\right|<\frac{1}{n}\}}\right\|_{p}\equal{}0$.
[hide="Solution"]
Let $ f_{n}\equal{}f\chi_{\{\left|f\right|<\frac{1}{n}\}}$.  Since $ \left|f_{n}\right|<\frac{1}{n\plus{}1}$ for all $ x$, we have that $ f_{n}$ converges uniformly to $ f\equal{}0$.  Also, $ \left|f_{n}\right|\leq f$, and $ f\in L^{1}(\mathbb{R})$ by assumption.  By the dominated convergence theorem,
$ \left\|f\chi_{\{\left|f\right|<\frac{1}{n}\}}\right\|_{p}\equal{}\left(\int\left|f_{n}\right|^{p}\right)^{1/p}\equal{}\left(\int\left|f\chi_{\{\left|f\right|<\frac{1}{n}\}}\right|^{p}\right)^{1/p}\rightarrow\left(\int 0\right)^{1/p}\equal{}0$.[/hide]

3a) Suppose $ f\in L^{1}(E)\cap L^{\infty}(E)$.  Show that $ f\in L^{p}(E)$ for every $ 1\leq p\leq\infty$.  Suggest an upper bound for $ \left\|f\right\|_{p}$ in terms of $ \left\|f\right\|_{1}$ and $ \left\|f\right\|_{\infty}$.
[hide="Solution"]We have that $ \left\|f\right\|_{p}^{p}\equal{}\int\left|f\right|^{p}\equal{}\int\left|f\right|\cdot\left|f\right|^{p\minus{}1}\leq\int\left|f\right|\cdot\left\|f\right\|_{\infty}^{p\minus{}1}\equal{}\left\|f\right\|_{\infty}^{p\minus{}1}\int\left|f\right|\equal{}\left\|f\right\|_{1}\left\|f\right\|_{\infty}^{p\minus{}1}$.  Both terms are finite by assumption and so $ f\in L^{p}$.  Taking $ p$th roots yields an upper bound: $ \left\|f\right\|_{p}\leq\left\|f\right\|_{1}^{1/p}\left\|f\right\|_{\infty}^{1\minus{}1/p}$.[/hide]
3b) Given $ f\in L^{p}(E)\cap L^{q}(E)$, consider the function $ F(r)\equal{}\int_{E}\left|f(x)\right|^{r}\,dx$.  Prove that $ F(r)$ is a continuous function at every point in the interval $ p\leq r\leq q$.
[hide="Solution"]Let $ (r_{n})$ be a sequence in $ [p,q]$ with $ r_{n}\rightarrow r$.  Let $ f_{n}\equal{}\left|f(x)\right|^{r_{n}}$.  If $ \left|f(x)\right|<1$, then $ \left|f_{n}\right|\leq\left|f(x)\right|^{p}$ and if $ \left|f(x)\right|\geq 1$, then $ \left|f_{n}\right|\leq\left|f(x)\right|^{q}$.  Both of these bounds are integrable so $ \left|f(x)\right|^{r}$ is integrable and $ F(r_{n})\equal{}\int\left|f(x)\right|^{r_{n}}\rightarrow\int\left|f(x)\right|^{r}\equal{}F(r)$, which defines continuity.[/hide]

When I grade such things, I tend to count at least something off for any incorrect statement even when the primary argument is present.

Hence there's a problem with #2. Yes, the primary argument involves the DCT and you have that. But you said that $ f_n\to 0$ uniformly, which is false. This is not uniform convergence - and you don't need uniform convergence. Looking back to the previous sentence: no, it's false that $ |f_n|<\frac1{n\plus{}1}.$ Why should that be true? There's no reason for it. Just say that $ f_n\to 0$ pointwise almost everywhere, then cite $ |f|$ as the dominating function (another problem - you should have said $ |f|,$ not $ f$) and quote the DCT.

I think there may be a valid argument in 3b), but you owe it to your reader to make that argument clearer. This is a DCT argument, so say that. And make crystal clear what the dominating function is. And mention that $ |f(x)|^{r_n}\to |f(x)|^r$ pointwise, since you need that.

Okay thank you.  I'm aware that pointwise convergence is the necessary criterion, so I'm not really sure why I went for uniform convergence.  And yes, I probably just neglected those absolute value terms on the dominating function.  In 3b, I thought it was clear what my dominating functions were, and that it was clear I was using DCT, but I just realized now that I never actually cited DCT.

So if each question was out of 10 points (5 points for 3a and 3b), would somewhere around 25-26 points be appropriate for you if you were grading?


1) Find $ f(x,y)$ such that $ 2009 f'_{x}\plus{}2010 f'_{y}\equal{}0$.

2) Find the minimum and the maximum value of $ f(x,y)\equal{}x^2\plus{}y^2\minus{}3xy\plus{}x\plus{}y$, where $ (x,y)\in \{(x,y): x^2+y^2\leq 16\}$.

[quote="sondhtn"]1)Find $ f(x,y)$ such that $ 2009 f'_{x} \plus{} 2010 f'_{y} \equal{} 0$[/quote]

We at least have $ f(x)\equal{}h(2010ax\minus{}2009ay\plus{}b)$ where $ h(x)$ is any differentiable function.

But I'm not sure for now that these are the only solutions

[quote="sondhtn"]1)Find $ f(x,y)$ such that $ 2009 f'_{x} \plus{} 2010 f'_{y} \equal{} 0$[/quote]

here is a general solution :

Let $ g(x,y)\equal{}f(y,\frac{2010y\minus{}x}{2009})$

We get $ f(x,y)\equal{}g(2010x\minus{}2009y,x)$ and :

$ f'_x(x,y)\equal{}2010g'_x(2010x\minus{}2009y,x)\plus{}g'_y(2010x\minus{}2009y,x)$
$ f'_y(x,y)\equal{}\minus{}2009g'_x(2010x\minus{}2009y,x)$

And the equation $ 2009f'_x(x,y)\plus{}2010f'_y(x,y)\equal{}0$ becomes $ g'_y(2010x\minus{}2009y,x)\equal{}0$ and so $ g'_y(x,y)\equal{}0$ and so $ g(x,y)\equal{}h(x)$

Hence the answer $ \boxed{f(x,y)\equal{}h(2010x\minus{}2009y)}$ where $ h(x)$ is any differentiable function


1. Find the last 3 digits of $ 7^{1166}$

2. What is the remainder when $ 7^{348} \plus{} 25^{605}$ is divide by 8?

1. I can find last 2 digits only:

[hide]
$ 7^{1166} \equiv 7^{58\cdot\lambda (100)}\cdot 7^{6} \equiv 343^2 \equiv 43^2 \equiv 49 \pmod {100}$[/hide]

[quote="modularmarc101"]1. You wanna look at $ \mod{1000}$ since it's the last 3 digits.

$ 7^{1166} \equiv 7^2*7^{1164} \equiv 49*401^{291} \equiv 49*201^{97} \equiv 49*201*201^{96} \equiv 849*401^{48}$....continue doing this until you get $ 849*201 \equiv 649 \mod{1000}$. So the last 3 digits are $ \boxed{649}$.

2. As xpmath said, the answer is $ \boxed{2}$.[/quote]

Could you please explain how you're moving through the steps in #1? How can you say that all of the expressions are congruent to each other in mod8?

I was using mod 1000 not mod 8. I'll show you why:

We have a number $ a_0a_1a_2a_3....a_n$, where $ a_n$ is a digit. If we where to expand the number, we would have $ a_0 \plus{} 10a_1 \plus{} 100a_2 \plus{} 1,000a_3...10^{n}a_n$. If we where to put this in $ \mod 1,000$, we would be left with $ a_0 \plus{} 10a_1 \plus{} 100a_2 \mod 1,000$ or the last the last three digits.

#1 is really ugly... I used a few tricks to simplify the computation, but I still ended up finding $ 3^{64}\bmod 1000$...

[hide="1"]
$ \lambda(1000)\equal{}100$, so we want $ 7^{66}\bmod 1000$.

$ (10\minus{}3)^{66}\equal{}\sum_{k\equal{}0}^{66}\binom{66}{k}10^{k}(\minus{}3)^{66\minus{}k}$ from the binomial theorem. All we really care about is $ k\equal{}0,1,2$, because after that the terms don't matter $ \bmod 1000$.

$ k\equal{}0$ gives $ 3^{66}$.

$ k\equal{}1$ gives $ \minus{}66\cdot 10\cdot 3^{65}$.

$ k\equal{}2$ gives $ 2145\cdot 100\cdot 3^{64}$.

Then our answer is congruent to $ 3^{64}(9\minus{}1980\plus{}214500)\equiv 3^{64}\cdot 529\bmod 1000$.

$ 3^{64}\equiv 49^6\cdot 3^4\equiv 401^3\cdot 81\equiv 801\cdot 401\cdot 81\equiv 281\bmod 1000$.

$ 281\cdot 529\equiv\boxed{649} \bmod 1000$.
[/hide]


If $p,q,r$ are the roots of the cubic equation $x^3 - 3px^2 + 3q^2 x - r^3 = 0$, then show that $p = q =r$.

[hide="solution"]
Let's say $f : x \to  x^3-3px^2+3q^2x-r^3$.
We know $f(q)=f(p)=f(r)=0$.
Factoring $0=f(p)-f(q)=-2(p+2q)(p-q)^2$.
either $p=q$ but from $0=f(p)=-(r-q)(r^2+rq+q^2)$, $r=p=q$.
either $p=-2q$ and from $0=f(r)=3rq(q+2r)$ we get (keeping in mind that $0=f(p)=10p^3-r^3$)
      if $r=0$ then $p=q=0$
      if $q=0$ then $p=0$ and $r=0$
      if $q=-2r$ then $p=-2q=4r$ and $f(p)=-81r^3=0$ so $r=0=p=q$
So either $r=q=p$ or $r=p=q=0$ and certainly $q=p=r$.

[/hide]

We have $p + q + r = 3p$, $pq + qr + pr = 3q^2$, $pqr = r^3$.
Solving this system we get $p = q = r$.

[quote=Maharjun]Try solving it yourself first, if you find it troublesome, look into the solution

[hide]
From given equation we have-

$ p + q + r = 3p - - - - - - - - - - - - - - - - - - - (i) \\
\& pq + qr + pr = 3{q^2} - - - - - - - - - - - - - (ii) \\
\& pqr = {r^3} - - - - - - - - - - - - - - - - - - - - (iii)$

[u][i][b]CASE I $ a,b,c \neq 0$[/u][/i][/b]

from (iii), we have $ pq = {r^2}$.
and from (i) we have $ p + q = 3p - r$

substituting in (ii) we get

${ \implies pq + qr + pr = 3{q^2} \\
\& \implies pq + r\left( {p + q} \right) = 3{q^2} \\
\& \implies {r^2} + \left( {3p - r} \right)r = 3{q^2} \\
\& \implies pr = {q^2} \Rightarrow pqr = {q^3} = {r^3} \Rightarrow q = r \\
}$

now in between the last step we got $ pr = q^2$

now $ pr = q^2\implies pr = q\cdot q \implies p = r$ ------------------------------[$ \because q = r\neq0$

$ \because p = q ,q = r \implies \boxed{p = q = r}$

[u][i][b]CASE II one of $ a,b,c$ is zero.[/b][/i][/u]

1.)[b]p or q = 0[/b]
$ \implies pqr = r^3 = 0 \implies r = 0$

$ \implies pq + qr + pr = 3q^2 = 0$[because either of $ p,q = 0$ and $ r = 0$]
$ \implies \boxed{p = q = r = 0}$

2.)[b]r = 0[/b]
$ \implies pq + qr + pr = pq = 3q^2$ from (ii)
also $ q = 2p$ from (i). putting in (ii) we get $ p^2 = 6p^2 \implies p^2 = 0\implies p = 0$

because $ p = r = 0$, from the previous case, we get above we get $ \boxed{p = q = r = 0}$

[i]IF two quantities are zero then the third can be proven to be zero using the above logics[/i]
[b]Q.E.D[/b]
[/hide][/quote]

I think you meant $p,q, r \ne 0$ , for [b][i]CASE I[/i][/b] .

I think the problem is for $p,q,r\in\mathbb{R}.$ Otherwise $q^3=r^3$ doesn't imply $q=r.$


limit
real analysis
real analysis unsolved

Let $ x_n,y_n\to 0$ and $ y_n\neq 0$. Show that if $ \exists \lim_{n\to\infty} \frac{x_{n\plus{}1}\minus{}x_n}{y_{n\plus{}1}\minus{}y_n}\equal{}A$ than $ \exists \lim_{n\to \infty} \frac{x_n}{y_n}$

[url=http://planetmath.org/encyclopedia/StolzCesaroTheorem.html]Cesaro-Stolz[/url] if $ y_n$ is monotone, [url=http://dictionary.reference.com/browse/false]false[/url] without extra assumptions.

I click fedja's "false" link but find nothing :P
So I want to post an counterexample:
$ x_n\equal{}\frac{1}{n}$,$ y_n\equal{}(\minus{}1)^n\frac{1}{n}$


Find all functions $f: N\to N$ that $f(m)^2+f(n)^2=f(m^2+n^2)$,for all$m;n\in{N}$.


matrix
Extremal combinatorics
combinatorics
IMO Shortlist
IMO
IMO 1999

Let $n$ be an even positive integer. We say that two different cells of a $n \times n$ board are [b]neighboring[/b] if they have a common side. Find the minimal number of cells on the $n \times n$ board that must be marked so that any cell (marked or not marked) has a marked neighboring cell.

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

Very nice problem.

The answer is $ \frac {n(n\plus{}2)}{4}$. For the optimal marking: Consider chessboard colouring. We must mark $ \frac {n(n\plus{}2)}{8}$ black squares, and the same number of white squares. To do this: consider the $ n$ white diagonals of the square. Leave the $ 1$-st, $ 3$-rd, $ 5$-th ... $ n\minus{}1$-th diagonals all unmarked. For the $ 2$-nd, $ 4$-th ... $ n$-th diagonal, starting from the topmost square in each of the diagonal, mark the alternating squares. Do the exact same for the black diagonals. It's easy to see this marking satisfies the conditions, and that there are $ \frac {n(n\plus{}2)}{4}$ squares marked.

To prove we can do no better: For each marked square, give it a value of $ 1$, and for each unmarked square, give it a value of $ 0$.  Let the value of square, with coordinates $ (i,j)$ be $ a_{i,j}$. Colour the squares as shown in the following figure: consider the $ n$ by $ n$ square as collection of nested squares. Colour the outmost square, don't colour the square after that, colour the next square, and so on. See the attached pdf, for an example, when $ n\equal{}8$.

For any square, if the adjacent squares are assigned values, say $ A, B, C, D$, then we know $ A\plus{}B\plus{}C\plus{}D \geq 1$ (since at least one of those squares has been marked). Now consider all the colored square. For each coloured square, write out the corresponding inequality (eg, for the square with coordinates $ (1,1)$, the inequality is $ a_{2,1} \plus{} a_{1,2} \geq 1$). Since there are $ \frac {n(n\plus{}2)}{2}$ colored squares, we have $ \frac {n(n\plus{}2)}{2}$ such inequalities. When we add up these inequalities, on the $ RHS$ we have $ \frac {n(n\plus{}2)}{2}$. But since each square (colored or not) is adjacent to exactly $ 2$ colored squares (we can easily verify this), on the $ LHS$, for each $ (i,j)$, $ a_{i,j}$ occurs exactly twice.  That means, the inequality is simply: $ 2 \sum a_{i,j} \geq \frac{n(n\plus{}2)}{2}$, so $ \sum a_{i,j} \geq \frac{n(n\plus{}2)}{4}$. But clearly, $ \sum a_{i,j}$ is just the number of marked squares, so that means we have at least $ \frac {n(n\plus{}2)}{4}$ marked squares.

[quote="epitomy01"]To prove we can do no better: For each marked square, give it a value of $ 1$, and for each unmarked square, give it a value of $ 0$.  Let the value of square, with coordinates $ (i,j)$ be $ a_{i,j}$. Colour the squares as shown in the following figure: consider the $ n$ by $ n$ square as collection of nested squares. Colour the outmost square, don't colour the square after that, colour the next square, and so on. See the attached pdf, for an example, when $ n\equal{}8$.

For any square, if the adjacent squares are assigned values, say $ A, B, C, D$, then we know $ A\plus{}B\plus{}C\plus{}D \geq 1$ (since at least one of those squares has been marked). Now consider all the colored square. For each coloured square, write out the corresponding inequality (eg, for the square with coordinates $ (1,1)$, the inequality is $ a_{2,1} \plus{} a_{1,2} \geq 1$).[/quote]
Nice solution! I would just like to note that this is not the only way of summing the inequalities $a_{i-1,j}+a_{i+1,j}+a_{i,j-1}+a_{i,j+1}\ge1$ over a set $S$ of squares $(i,j)$ (assuming we use each at most once): since the corners only have two neighbors each, we need $S$ to border each square on the board exactly $k$ times, where $k\in\{1,2\}$ is fixed. For $k=2$, we find the previous post's set of "colored" squares.

For $k=1$, on the other hand, this is clearly [b]equivalent[/b] to marking $n(n+2)/4$ squares satisfying the original problem conditions, with the additional caveat that every cell has [i]exactly[/i] one marked neighbor. But this strengthening is valid, as the previous post's marking of every other square in every other diagonal (for a fixed color) illustrates. Of course, these restricted markings can also be viewed as partitions of the board into contiguous regions $R$ consisting of two adjacent marked squares $p,q$ such that the only neighbors of $p,q$ lie in $R$.

This is very beautiful problem. It is related to the fact that we can tile the plane with pieces like these:

oXXo
XXXX
oXXo

(the X represents the piece), but the solution doesn't use it.

The answer is $\frac{n}{2}(\frac{n}{2}+1)$.

First, note that this is in fact possible. Color the board like a chessboard. For each two consecutive squares on the main black diagonal, place a marker like this:

X
MX (M=marker)

Repeat the process for the third-main black diagonal. And for the fifth, and so on. Do this again on the other side of the main black diagonal. It is easy to see we can cover all black squares with just $k(k+1)/2$ markers, where $k=n/2$. We do this again for the white squares, and end up using  $k(k+1)$ markers.

Now to prove that this is the maximum, we construct a set of $2k(k+1)$ squares, so that every marker can cover at most two of these squares. This is easy:

take the squares on the edge
take the squares at distance 2 from the edge
take the squares at distance 4 from the edge

and so on. In fact, my set of squares will look like a minisquare inside a square inside a bigger square inside etc. This set satisfies my condition. So done.

[quote=MathPanda1]These are some really great solutions! I was just wondering, what is the motivation for making such colorings? Thank you so much for all your help![/quote]

Greeting,

Coloring came to me naturally in 5-10 minutes. Proving was harder for me.

Your friend,
Luo Zhang

Hmm, very nice job polya36! But in particular, like the nested square coloring in epitomy01's solution, is there any motivation behind wanting to color in that manner, e.g. thought process/insights toward that coloring? Thank you so much for all your help!

See attachment for solution.  The marked cells go out in a spiral from the center.

So $\dfrac {n^2} 4 + \dfrac n 2$ markings are enough for an $n \times n$ board.

$\dfrac {n^2} 4 + \dfrac n 2$ is also minimal, as you can see by building up the board with concentric square shells of thickness 2.

Suppose $n \equiv 2\pmod 4$. In the thickness-2 shell around the $n-4 \times n-4$ board, there are $4(n-4)+12= 4n-4$ edge cells, which aren't neighbors to any cell in the $n-4 \times n-4$ board.  Since at most two edge cells can be neighbors to a cell inside the square,
at least $2n-2$ more markings are needed for the $n \times n$ board.

2 markings are needed for a $2 \times 2$ board.  So for $n = 2 \mod 4$, at least $2 + (2\times 6 - 2) + ... + (2n-2) = \dfrac {n^2} 4 + \dfrac n 2$ markings are needed.

Similarly, if $n \equiv 0\pmod 4, (2\times 4 - 2) + ... + (2n-2)= \dfrac {n^2} 4 + \dfrac n 2$ markings are needed.

Color the board in a checkerboard fashion. Clearly, it suffices to answer how many white squares need to be marked so that all black squares are next to marker, and then multiply the answer by $2$. This is because white squares are only adjacent to black squares and vice versa. We claim the final answer is $\boxed{\frac{n(n+2)}{4}}$, which means that if $k=n/2$, then the answer for the white squares is $k(k+1)/2$. We'll show this restated problem. Actually, we'll show that we need at least $k(k+1)/2$ white squares marked to cover all the black squares, and that we actually can cover all the white squares by marking $k(k+1)/2$ black squares (this is equivalent because of color symmetry). I know this is a bit confusing, but you'll see why I chose it this way soon.

First, we'll show that we need at least $k(k+1)/2$ white squares to be marked to cover all the black squares. To do this, color all black diagonals (marked in orange) alternately, and color the odd numbered black diagonals blue, and the even numbered black diagonals red. See the diagram below for more details.

[asy]
int m=13,n=13;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(i<n-1 && j>0 &&(i+j)%4==1 && max(n-1-i,j)%2==0)dot((i+1/2,j-1/2),red);
if(i<n-1 && j>0 &&(i+j)%4==3 && max(n-1-i,j)%2==0)dot((i+1/2,j-1/2),blue);
if(i < m-1) draw((i, j)--(i + 1, j));
if(j < n-1)draw((i, j)--(i, j + 1));
//if(i<m-1 && j>0) draw((i,j)--(i+1,j-1));
}
}
for(int k=0 ; k<n ; ++k) {
if(k%2==0) continue;
draw((k,0)--(0,k),orange+0.5);
draw((n-1,k)--(k,n-1),orange+0.5);
}
[/asy]

Note that there are $1+2+\cdots+k$ red dots and $1+2+\cdots+k$ blue dots, so a total of $k(k+1)$ dots. Furthermore, any white square is adjacent two at most two dots, so we need at least $k(k+1)/2$ white squares to be marked. Now, mark all the red squares (note that these are black), and then we see that all the white squares are covered.

So we've shown that we need to mark at least $k(k+1)/2$ white squares to cover all the black squares, so we need at least $k(k+1)$ squares marked to cover all squares. We've also shown that we can mark $k(k+1)/2$ black squares to cover all the white squares, so we can mark $k(k+1)$ squares to cover all squares. $\blacksquare$

[quote=Eyed]Proof without words:[/quote]

nice

Color the board in rings using the following method: color every cell neighboring the edge of the board white, then every uncolored cell neighboring any existing white cell black, then every uncolored cell neighboring any existing black cell white, and so on, making a grid that looks like this:
\begin{align*}
1~~1~~1~~1~~1~~1~~1~~1\\
1~~0~~0~~0~~0~~0~~0~~1\\
1~~0~~1~~1~~1~~1~~0~~1\\
1~~0~~1~~0~~0~~1~~0~~1\\
1~~0~~1~~0~~0~~1~~0~~1\\
1~~0~~1~~1~~1~~1~~0~~1\\
1~~0~~0~~0~~0~~0~~0~~1\\
1~~1~~1~~1~~1~~1~~1~~1
\end{align*}
Then every single cell borders four other cells, and it is easy to see that it borders exactly two white cells. There are $4(x-1)$ cells in a ring of size $x$, so the number of white cells in an $n\times n$ grid with $n=4k$ is \[4(4k-1+4k-5+\dots + 3)=8k^2+4k\] Thus, the number of marked cells is at least $4k^2+2k$ Similarly, if $n=4k+2$ then \[4(4k+1+4k-3+\dots + 1)=8k^2+12k+4\] so the number of marked cells is at least $4k^2+6k+2.$ As a construction, in each white ring, alternately color two and skip two, starting at the top left corner each time and going clockwise.
\begin{align*}
\textbf{1}~~\textbf{1}~~1~~1~~\textbf{1}~~\textbf{1}~~1~~1 & \\
1~~0~~0~~0~~0~~0~~0~~\textbf{1} & ~~| ~~\textbf{1}~~\textbf{1}~~1~~1~~\textbf{1}~~\textbf{1}\\
1~~0~~\textbf{1}~~\textbf{1}~~1~~1~~0~~\textbf{1} & ~~| ~~1~~0~~0~~0~~0~~1\\
\textbf{1}~~0~~1~~0~~0~~\textbf{1}~~0~~1 & ~~| ~~1~~0~~\textbf{1}~~\textbf{1}~~0~~1\\
\textbf{1}~~0~~1~~0~~0~~\textbf{1}~~0~~1 & ~~| ~~\textbf{1}~~0~~1~~1~~0~~\textbf{1}\\
1~~0~~\textbf{1}~~\textbf{1}~~1~~1~~0~~\textbf{1} &~~ | ~~\textbf{1}~~0~~0~~0~~0~~\textbf{1}\\
1~~0~~0~~0~~0~~0~~0~~\textbf{1} & ~~| ~~1~~1~~\textbf{1}~~\textbf{1}~~1~~1\\
\textbf{1}~~\textbf{1}~~1~~1~~\textbf{1}~~\textbf{1}~~1~~1 &
\end{align*}

[quote name="MathPanda1" url="/community/p7618700"]
These are some really great solutions! I was just wondering, what is the motivation for making such colorings? Thank you so much for all your help!
[/quote]

Experimentation. A lot of it. In fact, the first coloring I experimented with is actually not the best I could do: it was rings centered at a vertex of the grid. However, it did show that both straight lines and $90^\circ$ turns were good.

Let $S$ be a set of squares such that any square has a neighbour in $S$. We have to mark all squares of $S$.Consider the chessboard coloring in $n \cdot n$ board as shown below.
[center][img=5x5]https://cdn.discordapp.com/attachments/961202142809563140/1091582355896012800/image.png[/img][/center]
Consider the following diagonals(starting with bottomleft then skipping next and so on) as shown below. Squares in following different diagonals don't share a common neighbour.
[center][img=5x5]https://cdn.discordapp.com/attachments/961202142809563140/1091583217573822515/image.png[/img][/center]
Now we write $V$ in the black squares($r$ be the no. of $V$ black squares) as shown below and note that any $2$ black square in which $V$ is written doesn't have a common neighbour.So the set $S$ must have atleast $r$ neighbours of $V$ black squares. Note that $r=1+2+...+\frac{n}{2}=\frac{n \cdot (n+2)}{8}$.
[center][img=5x5]https://cdn.discordapp.com/attachments/961202142809563140/1091585668142076027/image.png[/img][/center]
Now note that since a white square and a black square doesn't share a common neighbour. We can reflect the considered diagonals across vertical line of symmetry of board.Now note that any $2$ $V$ squares doen't have a common neighbour. They are $2r=\frac{n \cdot (n+2)}{4}$ in number so set $S$ has atleast $\frac{n \cdot (n+2)}{4}$ neighbours of $V$ squares.
[center][img=5x5]https://cdn.discordapp.com/attachments/961202142809563140/1091589251432448110/image.png[/img][/center]

The construction is also clear from above diagram.All the squares in which $V$ is written ,we take it as part of set $S$ and this satisfies the problem condition. So we are done  :D.

[hide=Motivation][center][img=5x5]https://cdn.discordapp.com/attachments/961202142809563140/1091592258760998912/image.png[/img][/center][/hide]

The answer is $\frac{n(n+2)}{4}$. For a construction, consider the outermost "ring" of squares (which has dimensions $n \times n$), then the third-outermost "ring" (which has dimensions $(n-2) \times (n-2)$), fifth-outermost "ring", and so on. Mark squares in groups of two, keeping two cells "between" each group (walking along each ring).

To prove that this is maximal, note that any marked square is adjacent to exactly two squares in the above rings. Since there are $\frac{n(n+2)}{2}$ squares in these rings, it follows that we need at least $\frac{n(n+2)}{4}$ marked squares. $\blacksquare$

[b]Remark:[/b] Constricting the equality case motivates the proof of the bound. By the time we get to $n=8$, it more or less becomes apparent that there is some "ring" structure to these equality cases, which gives the general equality case. Furthermore, if we consider these "rings" carefully enough, the proof of the bound is not too hard to come up with. There's another solution (in #11) which uses a checkerboard coloring: I think this is somewhat natural as well, but by the time I got the equality case the idea of rings was too appealing for me to give it more consideration. Also worth noting that you can take the blue cells only in post #11 and the argument works (with each white cell being adjacent to at most $1$ blue cell).

EDIT: actually these are really the same solution. If you take the blue/red cells and repeat the coloring for the white cells you get the rings in this solution lol. I still think if you're focusing on the checkerboard coloring looking at only blue cells is perhaps more motivated if you start from small cases.


algebra
binomial theorem
number theory
divisibility tests

The question is:

Find 5 prime factors of $2^{90}-1$

I've so far found only three. I'm having problems finding the last two. See the hidden section for my work so far.

[hide]
By the binomial theorem, we know that in general \[a^{n}-b^{n}=(a-b)\left(\sum_{k=0}^{n-1}{a^{k}b^{n-1-k}\right)}\] So we can extend that to say that \[2^{ab}-1=\&\left(2^{a}\right)^{b}-1^{b}\]  \[\boxed{2^{ab}-1=(2^{a}-1)\left(\sum_{k=0}^{b-1}{2^{ak}}\right)}\] So we learn two important things from this. First, $2^{x}-1$ can only be prime if $x$ is prime. Second, we can begin to find some factors of $2^{90}$ right away. We can write $90$ as a product $ab$ where either $a$ or $b$ is prime in three different ways (since $90=2\times3^{2}\times5$). This will give us a factor of $2^{2}-1=3$, $2^{3}-1=7$ and $2^{5}-1=31$. So there's three prime factors of $2^{90}-1$, but I don't know how to find the last two. Any help please? :)
[/hide]

[quote="Farenhajt"][hide="Hint"]Calculate and factor $2^{9}-1$ and $2^{10}-1$, which are, as you proved, divisors of $2^{90}-1$[/hide][/quote]

[hide]
Oh! I didn't think of that! I was so busy looking for extra nuances of the binomial theorem, I forgot to look at the obvious fact that some of these factors are bashable.

$(2^{9}-1)=511=73\times7$ -- we already had $7$ but now we have $73$ too.

$(2^{10}-1)=1023=3\times11\times31$, which gives us the last prime factor -- $11$.

So our final answer is $\boxed{3,31,7,73,11}$

Of course, in a contest setting, factoring 1023 is not a fun thing to do with all the stress. I almost gave up and assumed 341 to be prime before trying the divisibility-by-11 rule. Is there any approach to finding the last two factors that doesn't require so much arithmetic footwork?
[/hide]

Interesting. I had never thought of that! Just to prove it:
[hide]
RTP: If $a|b$ then $2^{a}-1|2^{b}-1$.

Since $a|b$, we can write $b=ac$ so now we have $2^{a}-1|2^{ac}-1$. And as we showed before,
$2^{ac}-1=(2^{a}-1)\left(\sum_{k=0}^{c-1}{2^{ak}}\right)$. So clearly, $2^{a}-1|2^{ac}-1$. $QED$
[/hide]
Thanks, Farenhajt, I learned a new idea :)


:starwars:  :starwars:  :starwars:  :starwars:  :starwars:

haha

[size=200][color=blue]GO INDIANA!!!!!!!!!!!!!!!!!!![/color][/size]

huh? how did guest post?

btw, indianamath go gore yourself, jk jk

hooray for kansas being a large contributer of grain!

I'm not from Kansas, but who cares???? I'm posting anyway

We all lost. But now I won because I have a spork!

I take that back. I lost.
Oh yeah yay for Kansas Math people.

same, pay no attention to my personal information though.