geometry
circumcircle
geometric transformation
reflection
incenter
rhombus
trapezoid

Let $\overline{AH_1}, \overline{BH_2}$, and $\overline{CH_3}$ be the altitudes of an acute scalene triangle $ABC$. The incircle of triangle $ABC$ is tangent to $\overline{BC}, \overline{CA},$ and $\overline{AB}$ at $T_1, T_2,$ and $T_3$, respectively. For $k = 1, 2, 3$, let $P_i$ be the point on line $H_iH_{i+1}$ (where $H_4 = H_1$) such that $H_iT_iP_i$ is an acute isosceles triangle with $H_iT_i = H_iP_i$. Prove that the circumcircles of triangles $T_1P_1T_2$, $T_2P_2T_3$, $T_3P_3T_1$ pass through a common point.

Your three circumcircles intersect at the orthocenter of triangle $ T_1 T_2 T_3$. Here is a proof using some triangle geometry facts.

At first, for reasons of laziness, I rename everything:

Suppose ABC is an acute, scalene triangle. Let $ H_a$, $ H_b$, $ H_c$ be the feet of the altitudes from A, B, and C, respectively. Also let X, Y, Z be the points where the incircle of triangle ABC touches BC, CA, and AB, respectively. Now, let X' be the point on the line $ H_a H_b$ such that $ H_a X' \equal{} H_a X$ and the angle $ \angle X' H_a X$ is acute. Define Y' and Z' by cyclic permutation. Prove that the circumcircles of triangles X'XY, Y'YZ and Z'ZX intersect at a common point.

[i]Proof.[/i] Let H' be the orthocenter of triangle XYZ. We will prove that the circumcircles of triangles X'XY, Y'YZ and Z'ZX pass through H'.

At first, we show a classical result:

[b]Lemma 1.[/b] For every triangle ABC with orthocenter H, the circumcenter of triangle BCH is the reflection of the circumcenter of triangle ABC in the line BC.

[i]Proof.[/i] It is well-known ([1], Lemma 1) that the reflection A' of the orthocenter H in the line BC lies on the circumcircle of triangle ABC. Hence, the circumcenter of triangle BCA' coincides with the circumcenter of triangle ABC. But since A' is the reflection of H in the line BC, the triangles BCH and BCA' are symmetric with respect to BC, and the circumcenter of triangle BCH must be the reflection of the circumcenter of triangle BCA' in the line BC, i. e. the reflection of the circumcenter of triangle ABC in the line BC. Lemma 1 is proven.

Now, let I be the incenter of triangle ABC. Then, I is the circumcenter of triangle XYZ. Applied to triangle XYZ, Lemma 1 yields that the circumcenter F of triangle XYH' is the reflection of I in the line XY. Thus, XF = XI and YF = YI. But obviously, XI = YI; so, XF = XI = YI = YF, and the quadrilateral XFYI is a rhombus, so that XF is parallel to YI, or, in other words, XF is perpendicular to CY. Similarly, YF is perpendicular to CX. Thus, F is the orthocenter of triangle CXY.

But according to [2] Theorem 3.6, the following result holds:

[b]Lemma 2.[/b] The orthocenter of triangle CXY coincides with the incenter of triangle $ H_a H_b C$.

In other words, F is the incenter of triangle $ H_a H_b C$. Hence, the line $ H_a F$ is the angle bisector of the angle $ \angle C H_a H_b \equal{} \angle X' H_a X$. Now, the isosceles triangle $ X' H_a X$ yields that the angle bisector of the angle $ X' H_a X$, i. e. in the line $ H_a F$, is the perpendicular bisector of the segment XX', i. e. the point X' is the reflection of the point X in the line $ H_a F$.

But since F is the circumcenter of triangle XYH', the circumcircle of triangle XYH' has center F. The line $ H_a F$ is a diameter of this circumcircle, and since the reflection of a point on a circle in a diameter of the circle lies on the same circle again, the reflection X' of X in the line $ H_a F$ lies on the circumcircle of triangle XYH' again. In other words, the circumcircle of triangle X'XY passes through H. Similarly, the circumcircles of triangles Y'YZ and Z'ZX pass through H, and we are done.

[b]References[/b] (both avaliable at [url=http://www.cip.ifi.lmu.de/~grinberg/]my geometry website[/url]; I was too lazy to browse other sites)

[1] Darij Grinberg, [i]Anti-Steiner points with respect to a triangle[/i].

[2] Darij Grinberg, [i]Generalization of the Feuerbach point[/i].

  Darij

Here I give my solution:

Call the three circumcircles $k_1$, $k_2$ and $k_3$
Firstly we can see that the circumcenter of $T_1P_1T_2$ is the incenter of $CH_1H_2$. This is true because $S_{T_1T_2}$ is $l_{\angle H_1CH_2}$ and $S_{T_1P_2}$ is $l_{\angle CH_1H_2}$. Call that center $I_C$.
So $\frac{CI_C}{CI} =\frac{CH_1}{CA} =cos{\gamma}$ because $\triangle{H_1H_2C}$ is similar to $\triangle{ABC}$ !

Consider $\triangle{CIT_1}$ and point $I_C$ on $CI$ so that $\frac{CI_C}{CI} =cos{2\angle{ICT_1}}$. Let $K$ be the reflection of $I_C$ over $CT_1$.  Then $\angle{IKC}= 90'$. ' means degree sign(sorry I didn't found it :) ). Let $IK$ intersects $CT_1$ in point $L$.

$\angle{CI_CK}= 90' - \frac{\gamma}{2} = \angle {CLK}$

So $C$, $I_C$, $L$ and $K$ lie on circle -> $\angle {CI_CL}=90$ ->  $I_C$, $I$, $T_1$ and $L$ lie on circle -> $\angle{II_CT_1}=\angle{ILT_1}= 90' - \frac{\gamma}{2}$

Then $\angle{T_1I_CT_2}= 180' - \gamma$.

We are almost ready!

Let circle $k_1(I_C) \cap k_2(I_B)=U$. By simple calculation of angles we can see that point $U$ lies also on $k_3$.  The problem is solved!

Also knowing the angles of $\triangle{T_1T_2T_3}$ we can easily see also that $U$ is its orthocenter!

Here's another approach:
As in the two previous solutions, we shall prove that the circumcircle of $ T_{1}P_{1}T_{2}$ passes through the orthocentre $ X$ of $ T_{1}T_{2}T_{3}$, which is clearly sufficient.

Assume $ AB$ is the shortest side of the triangle (we can't WLOG this, but in all other cases, the solution will be the same with slight modifications. The difference is, that when $ AB$ is shortest side. $ H_{1}$ is closer to $ B$ than $ T_{1}$ is, and $ H_{2}$ is closer to $ A$ than $ T_{2}$ is.)

Let $ Q_{2}$ be the point on $ H_{1}H_{2}$ such that $ H_{2}Q_{2} \equal{} H_{2}T_{2}$. Since $ \angle H_{1}H_{2}C \equal{} B$, $ \angle H_{2}Q_{2}T_{2} \equal{} 90 \minus{} \frac{B}{2}$. Since $ \angle H_{2}H_{1}C \equal{} A$, $ \angle P_{1}T_{1}H_{1} \equal{} 90 \minus{} \frac{A}{2}$, and $ \angle T_{2}T_{1}C \equal{} 90 \minus{} \frac{C}{2}$, $ \angle P_{1}T_{1}T_{2} \equal{} 180 \minus{} ( \angle H_{1}T_{1}P_{1} \plus{} \angle CT_{1}T_{2}) \equal{} 90 \minus{} \frac{B}{2} \equal{} \angle H_{2}Q_{2}T_{2}$. Thus quadrilateral $ T_{1}P_{1}Q_{2}T_{2}$ is concyclic.
A little more angle chasing gives $ \angle Q_{2}T_{2}T_{1} \equal{} 180 \minus{} \angle H_{2}T_{2}Q_{2} \minus{} \angle CT_{2}T_{1} \equal{} 90 \minus{} \frac {A}{2}$, and since $ \angle P_{1}T_{1}T_{2} \equal{} 90 \minus{} \frac{B}{2}$, if we let $ T_{1}P_{1}$ intersect $ T_{2}Q_{2}$ at a point $ T'_{3}$, we have $ T_{1}T_{2}T_{3}$ and $ T_{1}T_{2}T'_{3}$ are congruent triangles. Thus, the quadrilateral $ T_{1}T_{2}T_{3}T'_{3}$ is a concyclic, iscoceles trapezium, so $ T'_{3}$ lies on the incircle.
Computations give us $ H_{2}T_{2} \equal{} AT_{2} \minus{} AH_{2} \equal{} (s\minus{}a) \minus{} c*cos B \equal{} \frac{(s\minus{}b)(a\minus{}c)}{b}$. Also, $ Q_{2}H_{2}T_{2}$ is similar to $ BT_{3}T_{1}$, so $ \frac {Q_{2}T_{2}}{T_{2}T'_{3}} \equal{} \frac {Q_{2}T_{2}}{T_{3}T_{1}} \equal{} \frac {T_{2}H_{2}}{BT_{1}} \equal{} \frac { \frac {(s\minus{}b)(a\minus{}c)}{b} }{s\minus{}b} \equal{} \frac {a\minus{}c}{b}$.
Choose a point $ S$, distinct from $ T_{3}$ on segment $ T_{1}T_{3}$ so that $ T_{2}S \equal{}T_{2}T_{3}$, so $ \angle T_{2}ST_{1} \equal{} 90 \plus{} \frac {C}{2}$. Sin Rule gives:
$ \frac {ST_{1}}{T_{1}T_{3}} \equal{} \frac {ST_{1}}{T_{1}T_{2}} * \frac {T_{1}T_{2}}{T_{1}T_{3}} \equal{} \frac {sin ( \frac {A}{2} \minus{} \frac {C}{2} )}{cos ( \frac {B}{2} ) }$ $ \equal{} \frac {2 cos (\frac{A}{2} \plus{} \frac{C}{2}) * sin ( \frac {A}{2} \minus{} \frac {C}{2} )} {2 sin (\frac  {B}{2}) * cos (\frac {B}{2})} \equal{} \frac {sin A \minus{} sin C}{sin B} \equal{} \frac {a\minus{}c}{b}$.
Thus $ \frac {ST_{1}}{T_{1}T_{3}} \equal{} \frac {Q_{2}T_{2}}{T_{2}T'_{3}}$. Since $ T_{1}T_{2}T_{3}T'_{3}$ is an iscoceles trapezium, this shows us that $ T_{2}T_{1}Q_{2}S$ is also an iscoceles trapezium, and more importantly, is cyclic. But a quick angle chase shows us that $ \angle T_{2}ST_{1} \equal{} 90 \plus{} \frac{C}{2} \equal{} \angle T_{1}XT_{2}$, so $ T_{1}T_{2}XS$ is cyclic. This shows that $ T_{1}, T_{2}, X, S, Q_{2}, P_{1}$ all lie on a circle, as required.

[quote="cauchyguy"]Let $ \ol{AH_1}, \ol{BH_2}$, and $ \ol{CH_3}$ be the altitudes of an acute scalene triangle $ ABC$. The incircle of triangle $ ABC$ is tangent to $ \ol{BC}, \ol{CA},$ and $ \ol{AB}$ at $ T_1, T_2,$ and $ T_3$, respectively. For $ k = 1, 2, 3$, let $ P_i$ be the point on line $ H_iH_{i + 1}$ (where $ H_4 = H_1$) such that $ H_iT_iP_i$ is an acute isosceles triangle with $ H_iT_i = H_iP_i$. Prove that the circumcircles of triangles $ T_1P_1T_2$, $ T_2P_2T_3$, $ T_3P_3T_1$ pass through a common point.[/quote]
Notice that the problem is vitrually the same with this one: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=351094#351094

Reflect $ H_1$ and $ H_2$ into $ T_1T_2$ to form $ X$ and $ Y$ respectively.  One intersection, $ K$, of $ XY$ and the incircle will be such that $ T_1K\parallel T_2T_3$ by the link.  We will now prove that $ K$ is the reflection of $ P_1$ into $ T_1T_2$.  Since $ K$ lies on $ XY$ and $ P_1$ lies on $ H_1H_2$, it suffices to show that $ \angle P_1T_1T_2=\angle T_2T_1K$.  Yet, \[ \angle KT_1T_2=\angle T_3T_2T_1=180-\angle T_1T_3T_2-\angle T_3T_1T_2\] We see that $ \angle T_1T_3T_2=\angle T_2T_1C$ and $ \angle PT_1H_1=\angle AT_3T_2=\angle T_3T_1T_2$ the first because $ \triangle H_1P_1T_1\sim \triangle AT_3T_2$ since $ AT_3=AT_2$, $ P_1H_1=T_1H_1$, and $ \angle T_3AT_2=\angle H_2H_1T_1=\angle P_1H_1T_2$.  Thus, we have that \[ \angle T_2T_1K=180-\angle P_1T_1H_1-\angle T_2T_1C=\angle PT_1T_2\] implying that $ P_1$ and $ K$ are reflections of each other over $ T_1T_2$.  Thus, the circumcircle of $ \triangle P_1T_1T_2$ is the reflection of the circumcircle of $ \triangle T_1T_3T_2$ into $ T_1T_2$.  Since the reflection of the orthocenter of $ \triangle T_1T_2T_3$, $ H$, into $ T_1T_2$ lies on the circumcircle of $ \triangle T_1T_3T_2$, we see that $ H$ lies on the circumcircle of $ \triangle T_1T_2P_1$.  Doing the same with the other circles, we see that they all pass through $ H$, and are hence concurrent.

See at http://www.mathlinks.ro/viewtopic.php?t=315623 that the three circles are equal with the incircle of triangle $ ABC$, hence they all pass through the orthocenter of triangle $ T_1T_2T_3$ (4 circles theorem?)

Best regards,
sunken rock

Notice that

$\frac{sin T_1P_1T_2}{sin T_1T_2P_1} =  \frac{T_1T_2}{T_1P_1} = \frac{CI sin C}{2(sin A/2)T_1H_1} = \frac{CI sin C}{2IA(sin(A/2+B-90))sin(A/2)} = \frac{sin(90+C/2)}{sin(A/2+B-90)}$

and that $90+C/2+A/2+B-90 = 90-B/2 = \angle T_1P_1T_2 + \angle T_1T_2P_1$. Thus, $ \angle T_1P_1T_2 = 90+C/2 = 180 - \angle T_1T_3T_2$. So the circumcircle of $T_1P_1T_2$ is the reflection across $T_1T_2$ of the circumcircle of $T_1T_2T_3$, and we finish easily.


a,b,c  are  reals  with  a+b+c=0 . Show  that  a^3+b^3+c^3>0 <==>a^5+b^5+c^5>0

It is well-known that if x,y,z are reals satisfying x+y+z = 0 then
(x 5  + y 5  + z 5 )/5 = ( (x 3  + y 3  + z 3 )/3 )*( (x 2  + y 2  + z 2 )/2 )
from which the desired result follows easily....

Pierre.

The same result is true for four reals, can you prove it Nickolas? :)


let a,b,c   positive numbers and such that:
\[\begin{array}{l}a^{2}+b^{2}+c^{2}= 3 \\ then prove that: \\ \frac{a}{b}+\frac{b}{c}+\frac{c}{a}\ge \frac{9}{{a+b+c}}\\ \end{array}\]

[quote="Utkirstudios"]let a,b,c   positive numbers and such that:

$a^{2}+b^{2}+c^{2}= 3$
 then prove that:
 $\frac{a}{b}+\frac{b}{c}+\frac{c}{a}\ge \frac{9}{{a+b+c}}$

[/quote]
See  here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=33612


trigonometry
modular arithmetic
function

cos (a) cos(2a) cos(3a)-------------  and so on up to nth term
pl tell general formula

[quote="ayush_2008"]$ cos (a) cos(2a) cos(3a)$-------------  and so on up to $ N$th term
pl tell general formula[/quote]

i think its a product and i won't tell you the answer but what is $ cos ^n (n!)$  :?:

[quote="Poincare"]but what is $ cos ^n (n!)$  :?:[/quote]$ a_n\equal{}\cos^n(n!)$ is a convergent sequence because for $ n\ge6$, $ n!\equiv0\pmod{360}$.

[quote="t0rajir0u"]In degrees.  What about in radians?  And how is this relevant to the original problem?  And it still hasn't been clarified whether it's a sum or a product (or asking for the $ n$-angle formula).[/quote]

What makes you think it is a sum? obviously it is a product.  :huh:  :huh:

method: multiply and divide by sin a and use sin 2A =2 sin A.cos A successively  :)

That would work for $ \cos a \cos 2a \cos 4a ...$.  The finite version of this product is a little more complicated, I think.

[quote="ayush_2008"]pl send more answers i am not still satisfied.[/quote]Send what answers? Clarify what you are asking first: is it a SUM or a PRODUCT?  :ninja:

I believe that the question is

$ \text{Express in terms of}$ $ n$, $ \text{The product}$

$ \cos a \cdot \cos 2a \cdot \cos 3a \hdots \cdot \cos na$.

yes question is in product form and angles r in ap

Again, that's the product $ \cos a \cos 2a \cos 4a \cos 8a ... \cos 2^n a$.  This is the product $ \cos a \cos 2a \cos 3a ... \cos na$.

Not a typical problem... Tried half-angles, double angles, Euler's... basic techniques are not easily yielding... This feels like a problem harder than HSB level...  :ninja:

[quote="ayush_2008"]pl send more answers i am not still satisfied.[/quote]
LOL, SATISFIED?
You think we HAVE to help you with this? I think that statement was a bit too harsh... -_-

Cechk out the wiki for trig IDs
Theres similar stuff on it (with cosine products)

http://en.wikipedia.org/wiki/List_of_trigonometric_identities

The way I would do this if I had enough time on my hands would be to first take double angle formula, then triple angle, etc., then look for a pattern, then look for a way to express it in...(I forgot the name of the multiplicative equivalent of summation notation), then use any properties that I know. BUT, this would be [i]extremely[/i] tedious, and I'm not even sure that this would work.

The corresponding approach by Euler's (which is algebraically nicer) only allows you to express the sum in terms of the generating function for the [url=http://mathworld.wolfram.com/PartitionFunctionq.html]partition function q[/url] and I can't think of  a way to simplify it.  The answer is only nice when $ a \equal{} \frac{\pi}{n}, \frac{\pi}{n\plus{}1}, \frac{2\pi}{n}, \frac{2\pi}{n\plus{}1}$ or similar.


algorithm
number theory proposed
number theory

Find at least one set of 8 different positive integers a,b,c,d,e,f,g,h
which satisfies
$ a \plus{} b \plus{} c \plus{} d \equal{} e \plus{} f \plus{} g \plus{} h$
and
$ abcd \equal{} efgh$
and also at least one set of 10 different positive integers p,q,r,s,t,u,v,w,x,y,
which satisfies
$ p \plus{} q \plus{} r \plus{} s \plus{} t \equal{} u \plus{} v \plus{} w \plus{} x \plus{} y$
and
$ pqrst \equal{} uvwxy$

[quote="cycoo"]Find at least one set of 8 different positive integers a,b,c,d,e,f,g,h
which satisfies
$ a \plus{} b \plus{} c \plus{} d \equal{} e \plus{} f \plus{} g \plus{} h$
and
$ abcd \equal{} efgh$[/quote]

$ 570\plus{}23\plus{}5\plus{}1\equal{}575\plus{}19\plus{}3\plus{}2\equal{}599$

$ 570\cdot 23\cdot 5\cdot 1\equal{}575\cdot 19\cdot 3\cdot 2\equal{}65550$

[quote="cycoo"]and also at least one set of 10 different positive integers p,q,r,s,t,u,v,w,x,y,
which satisfies
$ p \plus{} q \plus{} r \plus{} s \plus{} t \equal{} u \plus{} v \plus{} w \plus{} x \plus{} y$
and
$ pqrst \equal{} uvwxy$[/quote]

$ 4400\plus{}21\plus{}7\plus{}3\plus{}1\equal{}4410\plus{}11\plus{}5\plus{}4\plus{}2\equal{}4432$

$ 4400 \cdot 21 \cdot 7 \cdot 3 \cdot 1\equal{}4410 \cdot 11 \cdot 5 \cdot 4 \cdot 2\equal{}1940400$

[quote="cycoo"]Well, I really admire your numbers:) I spent whole day trying to calculate such sets. I also tried to use a computer, but it was too many operations for my computer and I gave up. So I'm interested how did you find the numbers? Using a smart computer algorithm, or with another metod?[/quote]

Let us consider the first one :

$ a\plus{}b\plus{}c\plus{}d\equal{}e\plus{}f\plus{}g\plus{}h$ and so $ h\equal{}a\plus{}b\plus{}c\plus{}d\minus{}e\minus{}f\minus{}g$

Then $ abcd\equal{}efgh$ and so $ abcd\equal{}efg(a\plus{}b\plus{}c\plus{}d\minus{}e\minus{}f\minus{}g)$ and so $ a\equal{}\frac{efg(b\plus{}c\plus{}d\minus{}e\minus{}f\minus{}g)}{bcd\minus{}efg}$

So we can look for numbers such that $ bcd\minus{}efg\equal{}1$ so we are sure to have RHS be an integer (we also need $ b\plus{}c\plus{}d>e\plus{}f\plus{}g$)

In order to have $ bcd\minus{}efg\equal{}1$, a simple solution is to choose $ c,d,f,g$ such that $ \gcd(cd,fg)\equal{}1$ and then to find $ b$ and $ e$ using Bezout.

In my case : $ (c,d)\equal{}(5,1)$ and $ (f,g)\equal{}(3,2)$ and so $ (6k\plus{}5)5\minus{}(5k\plus{}4)6\equal{}1$

$ k\equal{}0$ would imply $ b\equal{}c$
$ k\equal{}1$ gives $ (b,c,d)\equal{}(11,5,1)$ and $ (e,f,g)\equal{}(9,3,2)$ and so $ a\equal{}162$ and $ h\equal{}165$ and numbers $ (162,11,5,1)$ and $ (165,9,3,2)$
...
I choosed $ k\equal{}3$


$ a, b, c$ positive real numbers. Determine the greater real number $ k$:

$ \frac{a}{b} \plus{} \frac{b}{c} \plus{} \frac{c}{a} \ge k\sqrt{\frac{a^2\plus{}b^2\plus{}c^2}{ab\plus{}bc\plus{}ca}\plus{}\frac{5}{4}}$

_______________
 Thanks  :blush:

[quote="Ligouras"]$ a, b, c$ positive real numbers. Determine the greater real number $ k$:

$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a} \ge k\sqrt {\frac {a^2 \plus{} b^2 \plus{} c^2}{ab \plus{} bc \plus{} ca} \plus{} \frac {5}{4}}$
[/quote]
If $ a \equal{} b \equal{} c$ then $ k\leq2.$ But for $ k \equal{} 2$ your inequality follows from
$ \frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a} \ge \sqrt {\frac {15(a^2 \plus{} b^2 \plus{} c^2)}{ab \plus{} bc \plus{} ca} \minus{} 6}.$ The proof idea see here:
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=219253


$ \frac{1}{a}\plus{} \frac{1}{b}\plus{} \frac{1}{c}\equal{} \frac{1}{abc}$
Proof that there are infinitly many $ (a,b,c)$ satisfying this equality.

[quote="inny"]$ \frac {1}{a} \plus{} \frac {1}{b} \plus{} \frac {1}{c} \equal{} \frac {1}{abc}$
Proof that there are infinitly many $ (a,b,c)$ satisfying this equality.[/quote]
The triplet $ (a,1\minus{}a,a^2\minus{}a\plus{}1)$ satisfies the equation for every integer $ a \neq 1,0$ .The conclusion follows immediately.


trigonometry
induction
summer program
Mathcamp
probability
calculus
derivative

Proving [tex]\sin(x)-\sin(y)=2\sin\left(\frac{x-y}{2}\right)\cos\left(\frac{x+y}{2}\right) [/tex] in my A2Trig class this year, I went a completely wrong way and then realized I could prove it in 2 steps.

"What is the average number of fixed points in a random permutation of n items?"

When I was a kid, I came up with a proof that was several pages long, involving a double induction and binomial coefficients galore.  I gave myself a pat on the back.  A few years later, I learned the two-line proof...

I've got a few. Last summer I wrote a 4 page solution to one of the Mathcamp qualifying quiz problems. The problem went something like this.

You start with a sequence of A's, B's and C's that is n letters long. Then you form a triangle according to the following rules. Under 2 letters that are the same, you write that same letter. Under 2 letters that are different, you write the third letter. An example is given below.

[code]
A B B C
 C B A
  A C
   B
[/code]

Notice that in this example, the three corners of the big triangle are different. Prove that for any sequence with 4 letters, the corners of the big triangle that is formed will either be all the same or all different.

Part b: For what other numbers n will this property always hold?

---------------

I did 4 pages worth of number theory / binomial coefficient stuff... A few months later I learned Lucas's theorem.

One of our homework problems said if we have a line segment and a point on the line segment what is the probability that one segment is more than twice the other. I had a 2-d solution with 7 lines and i still got 2/3. It can be done in 1-d.

[quote="zabelman"]What's the most overdone, unnecessary solution that you've come up with to a relatively easy problem before realizing the problem's simplicity?[/quote]

Proving that  :Sigma: C(n,r) = 2^(n-1)

Clearly, C(1,1) = 1 = 2^0

Then assume :Sigma: C(k,r) = 2^(k-1) holds

So 2 :Sigma: C(k,r) = 2^k

But C(k,0) = C(k+1,0) and then we use the nice summation C(k,r) + C(k,r+1) = C(k+1,r+1) and we sum in a 'staggered' fashion to get that:

2 :Sigma: C(k,r) = :Sigma: C(k+1,r) = 2^k, which proves it by mathematical induction.

A nice exercise, I thought, at the time.  But then I realized that:

(1+1)^n = :Sigma: C(n,r)1^n*1^n = :Sigma: C(n,r).

ding ding ding!

A while ago I was doing a problem that required finding the minimum of something.  I did this problem in two ways: once using AM-GM, which took about a minute, and once using partial derivatives which took a looooong time.

blahblahblah, I think your proof about the sum of binomial coefficients is fine.  It explains the identity about as well as the binomial theorem does.  (Although I admit the proof via binomial theorem is shorter.)  Once, when I gave a talk about Pascal's triangle to some 5th graders, I was going to show them the same proof, not using induction by name, but in spirit.  For example, I would have shown them that

1 + 4 + 6 + 4 + 1
= 1 + (1 + 3) + (3 + 3) + (3 + 1) + 1         [from previous row]
= (1 + 1) + (3 + 3) + (3 + 3) + (1 + 1)      [regrouping]
= 2 (1 + 3 + 3 + 1).                                   [factoring out 2]

I'll never know how well it would have gone over because I skipped that part in favor of other properties.

I do think that it is quite a nice proof by induction - the problem was, using the binomial theorem did not even occur to me at the time, and it should have been the first thing I thought of.

However, due to pride, or whatever, I persist in giving this exercise to students in the math club that I run, with the insistence that they treat it as an exercise in mathematical induction and not in the binomial theorem.

Here's another one of mine, which happened a few days ago. Prove that for any positive integer n,

[tex]\sqrt[n]{n} < 1+\sqrt{2/n}[/tex].

My first solution:

By weighted AM-GM, we have

[tex]\displaystyle \\ 1+\sqrt{2/n} =\left(\frac{n-2}{n}\right)\left(\frac{n}{n-2}\right)+\left(\frac{2}{n}\right)\left(\sqrt{\frac{n}{2}}\right)\\ \ge \left(\frac{n}{n-2}\right)^{\tfrac{n-2}{n}}\sqrt{\frac{n}{2}}^{\tfrac{2}{n}} = \sqrt[n]{\left(\frac{n}{n-2}\right)^{n-2}\cdot\frac{n}{2}}[/tex]

The function [tex]f(x) = \left(1+\frac{2}{x}\right)^x[/tex] has a derivative of

[tex]f'(x) = \left(1+\frac{2}{x}\right)^x\left(-\frac{2}{x+2}-\ln\left(\tfrac{x}{x+2}\right)\right)[/tex].

The second factor shown has the form [tex]a-\ln(a+1)[/tex], and since it is commonly known that [tex]e^a\ge a+1[/tex], we have [tex]a-\ln(a+1)\ge 0[/tex]. Thus, [tex]f'(x)[/tex] is positive and [tex]f(x)[/tex] is an increasing function. So, for n>=3,

[tex]\displaystyle \\  \sqrt[n]{\left(\frac{n}{n-2}\right)^{n-2}\cdot\frac{n}{2}} =  \sqrt[n]{f(n-2)\cdot\frac{n}{2}} \\ \ge  \sqrt[n]{f(3-2)\cdot\frac{n}{2}} = \sqrt[n]{3\cdot\frac{n}{2}} > \sqrt[n]{n}[/tex]

and so the inequality has been verified for n>=3. It can be checked directly for n=1 and n=2. [tex]\blacksquare[/tex]

The next day I sat down for 5 minutes and found the "intended" solution and felt pretty dumb.

Zabelman, that problem that you posted above with the A's, etc, was recently given to me by a friend at a summer youth program at FSU. She was asking for a proof of the 10-case, saying that her professor hasnt even found one yet. I got it in a way that I think is different to how you did it, and have almost finished pdfing it (First full problem im doing :))... When I finish it, ill post it here.

HMM.... Can someone please tell me why the following wont tex properly on aops? It works on my compiler.
O and, I had the tex labels at the front and end before, but it didnt work then (thats what teh edit is for)

\documentclass[11pt]{article}

\begin{document}
\section{Question}
\label{sec:Problem}
\small{a quick precursor: $P_k(i)$ means the (i+1)th element of the (k+1)th row}
\begin{enumerate}
\item In a sequence $P_k$, each element is one of either $A$, $B$, or $C$, picked randomly. A step in the sequence consists of having element $P(i)$ compare with element $P(i+1)$, i = 0 to (P.length-2). If these elements are different (say $A$ and $B$), then when the sequence is finished comparing and becomes a new sequence of length $n-2$, element $P(i)$ becomes the remote character (in this case $C$). If they are the same (say $C$) then $P(i)$ becomes $C$.

\indent Prove that the unique character that a $P_9$ sequence converges to at length 1 is determined by comparing the initial $P_9(0)$ and $P_9(9)$.
\end{enumerate}

\section{Lemma}
Consider $x$, $y$, $z$, $w$ to be $A$, $B$, or $C$ and to follow the rules of the sequence. Also consider $x$ + $y$ to be comparing $x$ and $y$.

Then

\begin {equation}
((x + y) + (y + z))
\end{equation}

\begin{center}
+
\end{center}

\begin{equation}
((y + z) + (z + w))
\end{equation}

\begin{center}
=
\end{center}

\begin{equation}
x + w
\end{equation}

To prove this, we can set (y + z) = A, and there are two cases.

\subsection{y = z}

In this case $(1)$ becomes

\begin{center}
((x + A) + A))
\end{center}

No matter what x is, the above = x. By the same reasoning, $(2)$ = w, and $(3)$ upholds.

\subsection{$y\neq z$}
WLOG, we can set y = C and z = B. Then, (1) becomes
\begin{center}
((x + C) + A)
\end{center}
and (2) becomes
\begin{center}
((z + B) + A)
\end{center}
If we think of A corresponding to $0$, B to $1$, and C to $2$, then $(1) = x - 1$ (mod 3) and $(2) = w + 1$ (mod 3). Thus
\begin{center}
$(2) + (1) \equiv w + 1 + x - 1 \equiv w + x = (3)$
\end{center}

\section{Proof}
\small{(the diagram was too difficult to construct in pdf...)}

On the 3rd step, by the above lemma, each element on $P_6$,
\begin{center}
$((P_9(i) + P_9(i+1)) + (P_9(i+1) + P_9(i+2))) + ((P_9(i+1) + P_9(i+2)) + (P_9(i+2) + P_9(i+3)))$
\end{center}
\begin{center}
$=$
\end{center}
\begin{center}
$P_9(i) + P_9(i+3)$
\end{center}
And then if we continue,
\begin{center}
$P_3(0) = (P_9(0) + P_9(3)) + (P_9(3) + P_9(6))$
\end{center}
\begin{center}
$P_3(1) = (P_9(1) + P_9(4)) + (P_9(4) + P_9(7))$
\end{center}
\begin{center}
$P_3(2) = (P_9(2) + P_9(5)) + (P_9(5) + P_9(8))$
\end{center}
\begin{center}
$P_3(3) = (P_9(3) + P_9(6)) + (P_9(6) + P_9(9))$
\end{center}
And thus,
\begin{center}
$P_0(0) = ((P_9(0) + P_9(3)) + (P_9(3) + P_9(6))) + ((P_9(3) + P_9(6)) + (P_9(6) + P_9(9))$
\end{center}
Which, by our lemma, is equal to
\begin{center}
$P_9(0) + P_9(9)$
\end{center}

This last comparison is comparing our original row's first and last characters, and thus the proof is complete.
\end{document}

The tex implementation for the message board doesn't TeX up whole documents - just math bits.  Another thing you could do with a nicely TeXed solution is to just make a PDF file and attach that using the attachments addition you'll see in the posting window.

[quote="jelyman"]Is it supposed to be a download and not a full posted solution?[/quote]

Yes. PDF is designed to be viewed in its own page layout, so it would not intermix with the display environment in this forum.

jelyman, I looked at your file, "sequence.pdf", and feel the need to give you points on writing clear proofs. This is, after all, a thread on "Overdone Solutions", and your poor write-up makes your solution look overdone.

A mathematical paper should begin with an introduction that explains the result in nonmathematical language. Of course, since it is difficult to explain mathematical results without mathematical notation, most introductions simply summarize the result enough that the reader can recognize the topic. In a write-up of a solution to a puzzle, simply repeat the original wording of the puzzle for an introduction. Unfortunately, you start by introducing some difficult notation about the sequence [tex]P_k(i)[/tex]. The reader has to decipher your notation before he or she can learn what you intend to talk about. Furthermore, since your definition of the [tex]P_k(i)[/tex] sequence has some errors in it, the reader has an especially difficult time grasping your topic.

In your lemma, you introduce the notation [tex]x+y[/tex] without explanation. That is a major faux pas. How is the reader to know that [tex]x+y[/tex] is the entry [tex]P_{k+1}(i)[/tex] created when [tex]x=P_k(i)[/tex] and [tex]y=P_k(i+1)[/tex]? Also, the plus sign + is not suitable for that binary operation. We mathematicians do reuse the plus sign for other binary operations, but only operations that resemble addition. They have to be commutative, be associative, have an additive identity (zero), and have an inverse operation (subtraction). For noncommutative operations we use a multiplication sign * instead. For nonassociative operations, such as this one, we use function notation.

A good clear notation can make a mathematical problem a lot simpler and make the result more powerful. When I was working on my doctoral dissertation in mathematics, my advisor gave me a current problem in combinatorical analysis and a suggestion on a way to solve it. Months later I returned with a clear notation that demonstrated that his suggestion could not work. One month after that, someone else solved the problem (and sent my advisor a preprint). I applied my notation to the other person's solution and the notation made additional results obvious. I had a new dissertation topic.

Don't use equation fragments in your sentences. Equation fragments are worse than sentence fragments. For example, at the bottom of page one you said, "No matter what [i]x[/i] is, the above = [i]x[/i]. By the same reasoning, (2) = [i]w[/i], and (3) upholds." That should be, "No matter the value of [i]x[/i], the value of the above expression equals [i]x[/i]. By the same reasoning, the value of expression (2) equals [i]w[/i], and the sum of expressions (1) and (2) is expression (3)." Though, since you are not supposed to use addition for your binary operation, you shouldn't be talking about the sum.

Let me give you a clear notation for writing up your proof and you can take it from there. By the way, the propery holds not just for [i]n[/i] equal to 4 or 10. It holds for all [i]n[/i] that are one more than a power of 3.

Question:
You start with a sequence of A's, B's and C's that is n letters long. Then you form a triangle according to the following rules. Under 2 letters that are the same, you write that same letter. Under 2 letters that are different, you write the third letter. An example is given below.

[tex]\tabcolsep=0pt\begin{tabular}{ccccccc}
A&&B&&B&&C\\
&C&&B&&A\\
&&A&&C\\
&&&B
\end{tabular}[/tex]

Notice that in this example, the three corners of the big triangle are different. Prove that for any sequence with 4 letters, the corners of the big triangle that is formed will either be all the same or all different.

For what other numbers n will this property always hold?

Solution:
Define the function [tex]f(x,y)[/tex] where [i]x[/i] and [i]y[/i] are in the set {A,B,C} as follows: if [i]x[/i] and [i]y[/i] are the same, then [tex]f(x,y)[/tex] equals that value, and if [i]x[/i] and [i]y[/i] are two distinct members of the set {A,B,C}, then [tex]f(x,y)[/tex] equals the third member of {A,B,C}.

Lemma 1. [tex]f(f(x,y),y)=x[/tex].

Proof of Lemma.
If [tex]x=y[/tex], then [tex]f(f(x,y),y)=f(f(x,x),x)=f(x,x)=x[/tex].
If [tex]x\ne y[/tex], then let [tex]z=f(x,y)[/tex] be the third element of the set {A,B,C}. [tex]f(f(x,y),y)=f(z,y)[/tex]. Since [tex]z \ne y[/tex], [tex]f(z,y)[/tex] must be the element of the set that is neither [i]z[/i] nor [i]y[/i]. So [tex]f(z,y)=x[/tex].
End of Proof.

For a [i]n[/i]-element sequence [tex]\mathbf{s} = s_1,s_2,\ldots,s_n[/tex] with elements in {A,B,C} define the ([i]n[/i]-1)-element sequence [tex]f(\mathbf{s})[/tex] as [tex]f(s_1,s_2),f(s_2,s_3),\ldots,
f(s_{n-1},s_n)[/tex]. Note that if the subsequence [tex]\mathbf{t}[/tex] consists of [i]k[/i] consecutive elements of [tex]\mathbf{s}[/tex] then [tex]f(\mathbf{t})[/tex] is the matching [i]k[/i]-1 consecutive elements of [tex]f(\mathbf{s})[/tex].

Lemma 2. Given a four-element sequence [tex]\mathbf{s} = w,x,y,z[/tex], the one-element sequence [tex]f^3(\mathbf{s})[/tex] consists of the element [tex]f(w,z)[/tex].

Proof of Lemma.
...

Erin J. Schram

Thanks. I was hoping someone would critique me like that. Btw, this was also quite choppy because it was my first document in latex.
Also, when I first got the problem, my conjecture was that for all 3^k + 1, it works, but I was put off on doing that because I really wanted to actually test to see if this works. So, I made a program in java, but then found that I had accidentally deleted a key file (for my compiler) and couldnt find it anywhere, so I got put off, and then I didnt even try to do it for all 3^k + 1. Heh. I really did want to see if that program would work too....

Or I think you can do it this way:
Let A=0(mod 3), B=1(mod 3), C=2(mod 3).
Let x,y be two letters. The letter under x, y on the next row is (3-(x+y))(mod 3)
Let a, b, c, d each represent a number
numbers on the next row are
(3-(a+b)(mod 3), (3-(b+c))(mod 3), (3-(c+d))(mod 3)
next row:
((a+2b+c)-3)(mod 3), ((b+2c+d)-3)(mod 3)
last row:
 (9-(a+d+3(b+c))(mod 3)=(3-(a+d)(mod 3)
as desired, we showed that 4 works.
Once we showed 4 works, we can easily show 10 works by looking at first, 4th, 7th , 10th letter of the first row.

Beta, can you generalize and prove that it works for any n that is 1 more than a power of 3? Can you prove that these are the only numbers that actually work?

I thought of a combinatorial method using paths of proving both that the [tex]3^n + 1[/tex] cases work and that no other cases work. We use beta's isomorphism where A is assigned 0, B is assigned 1, C is assigned 2, and the number written under x and y is 3-x-y (mod 3). Let's say our starting sequences is [tex]a_1, a_2, ... a_n[/tex]. Under this sequence, we write out the next sequence with the members expressed in terms of members of our starting sequence. If we continue this process into subsequent rows, the point at the bottom of the triangle formed is [tex]c_1a_1 + c_2a_2 + ... + c_na_n[/tex] (mod 3), where [tex]c_i[/tex] is a coefficient. The sequence of lenght n will always work iff [tex]c_2,c_3,...,c_{n-1}[/tex] :equiv: 0 (mod 3). It is clear that [tex]c_n[/tex] is the number of paths from [tex]a_1[/tex] to the end tip of the triangle. If we call the k-1st member of the n-1st row from the bottom C(n,k), (This means that the leftmost member is called the 0th member and the bottom row is the 0th row) we have the identity C(n,k)=C(n-1,k)+C(n-1,k-1) where C(n,k) = 0 if it would be undefined. Since C(0,0) = 1, we get an upside-down Pascal's triangle as the number of paths from each point to the bottom tip of the triangle.
Now it needs to be shown that nCk :equiv: 0 (mod 3) for all k iff k is a power of 3. We define g(x), the largest power of 3 that divides x. If n is not a power of 3, there is a greatest number [tex]3^p \le n[/tex]. We can prove that [tex]g(n(n-1)...(n-3^p+1))/g(3^p(3^p-1)...1)=1[/tex]. However, we can also prove that if n is a power of 3, g(nCk) > 1. We can prove both of these things by considering the sequence g(n/1), g(n-1)/2)...g(1/n) (we must extend the definition of g to work on negative powers of 3) and we see that if n is not a power of 3, the first [tex]3^p[/tex] are a permutation of the last [tex]3^p[/tex].

edit-oops,i am way too late

Let the sequence be[tex] a_1, a_2, ...a_n[/tex]
By induction using property of Pascal's Triangle, we can show that the last row is
[tex](-1)^i(3-\displaystyle\sum_{i=0}^{n} \binom{n-1}{i-1}a_i(\mod 3)[/tex]
So we want 3 to divide [tex]\displaystyle \binom{n-1}{i-1}[/tex] for [tex]n>i>1[/tex].
Suppose n-1 is not a power of 3.
[tex]\binom{n-1}{i-1}=\frac{(n-1)!}{(i-1)!(n-i)!}[/tex]
Let [tex]\lfloor \frac{n-1}{3^k} \rfloor =1[/tex]. and let[tex] i-1=3^k[/tex]
[tex](n-1)![/tex] has
[tex]\displaystyle\sum_{i=1}^{k} \lfloor \frac{n-1}{3^i} \rfloor [/tex] powers of 3
(3^k)! has
[tex]\displaystyle\sum_{i=1}^{k} \lfloor \frac{3^k}{3^i} \rfloor[/tex]
(n-1-3^k)! has
[tex]\displaystyle\sum_{i=1}^{k} \lfloor \frac{n-3^k}{3^i} \rfloor[/tex]
Since[tex]\displaystyle\sum_{i=1}^{k} \lfloor \frac{n-1-3^k}{3^i} \rfloor[/tex]+[tex]\displaystyle\sum_{i=1}^{k} \lfloor \frac{3^k}{3^i} \rfloor[/tex]=[tex]\displaystyle\sum_{i=1}^{k} \lfloor \frac{n-1}{3^i} \rfloor [/tex]
Then  [tex]\binom{n-1}{3^k}[/tex] can't be a multiple of 3.
so n-1 must be a power of 3 as desired.

Back to the beginning question (sorry I'm late)- when my calculus class first began to learn how to take the derivative, we had to derive a fairly simple equation by the limit definition (the whole delta-x plus x thing).  It took the whole board and the entire 65 minute period just because there were a few square roots in it.  Then, the next day we learned the exponent rules and chain rules.  It took five minutes and a couple steps to do.  We were [i]so[/i] mad at the teacher

Just want to note that Mathcamp didn't really want us to discuss quiz problems on the forum because they sometimes reuse problems. Oh well. But I think they won't mind too much.

When I solved this problem a year ago I did a pretty nice proof of why numbers like 3^k+1 work, which was what Beta posted at 1:54 EST. I didn't prove that those were the only numbers that worked, since I did not know anything about binomial coefficients except what they were at the time.


Given $ a \star b \equal{} \frac{a^2 \minus{} b^2}{ab}$ express $ 6 \star 2$ as a common fraction.

[quote="hellomynameis"]Hi, I put 8/3 as the answer but I got it wrong, apparently the answer was $ %Error. "FRAC" is a bad command.
{8}{3}$, but that is equivalent and I thought that the formatting was not necessary for fractions.[/quote]

You could report an error. Also, when you type here, you need to type \frac{8}{3}


induction
function
algebra unsolved
algebra

Suppose that the function $f: \mathbb N \to \mathbb N$ satisfies the following conditions:
a) $ f(1)=1$,
b) $ 3f(n) \cdot f(2n+1) = f(2n) \cdot [1 + 3f(n)]$ for all $n \in \mathbb N$, and
c) $ f(2n)<6f(n)$ for all $n \in \mathbb N$.

Find positive integers $k$ and $m$ satisfying $f(k)+f(m)=293$.

b) yields $ f(2n)$ is divisible by $ 3f(n)$ and then together with c) we get the recursions:

$ f(2n)=3f(n),f(2n+1)=1+3f(n)$

Claim: $ f(\sum_{i=0}^m\alpha_i2^i)=\sum_{i=0}^m\alpha_i3^i$ with $ \alpha_i\in\{0,1\}$

Proof: Apply $ f(\sum_{i=0}^m\alpha_i2^i)=\alpha_0+3\sum_{i=0}^{m-1}\alpha_{i+1}2^i$ plus induction on $ m$.

as for the solution, e.g., set $ k=47,m=5$

[quote="hien"]Let $ f: \mathbb{Z}^ \plus{} \rightarrow\mathbb{Z}^ \plus{}$ satify:
a) $ f(1) \equal{} 1$
b) $ 3f(n).f(2n \plus{} 1) \equal{} f(2n).[1 \plus{} 3f(n)]$
c) $ f(2n) < 6f(n)$
Find numbers $ k,m$ satifying $ f(k) \plus{} f(m) \equal{} 293$[/quote]
Because $ (3f(n),1\plus{}3f(n))\equal{}1$ we get $ f(2n\plus{}1)\equal{}k(1\plus{}3f(n)),f(2n)\equal{}3kf(n)$, from c) we get, that k=1.
It give $ f(2n)\equal{}3f(n),f(2n\plus{}1)\equal{}3f(n)\plus{}1$. Because f(1)=1, for $ n\equal{}a_0\plus{}a_1*2\plus{}...\plus{}a_k*2^k, a_i\equal{}0,1$ 2-adic digits we get
$ f(n)\equal{}a_0\plus{}3*a_1\plus{}...\plus{}a_k*3^k$.
I think it posted before.

[quote="hjbrasch"]b) yields $ f(2n)$ is divisible by $ 3f(n)$ and then together with c) we get the recursions:

$ f(2n) = 3f(n),f(2n + 1) = 1 + 3f(n)$

Claim: $ f(\sum_{i = 0}^m\alpha_i2^i) = \sum_{i = 0}^m\alpha_i3^i$ with $ \alpha_i\in\{0,1\}$

Proof: Apply $ f(\sum_{i = 0}^m\alpha_i2^i) = \alpha_0 + 3\sum_{i = 0}^{m - 1}\alpha_{i + 1}2^i$ plus induction on $ m$.

as for the solution, e.g., set $ k = 47,m = 5$[/quote]

Quite OK.

And all couples $ (k,m)$ are $ (5,47),(7,45),(13,39),(15,37),(37,15),(39,13),(45,7),(47,5)$

actually, one can easily show that all possible solutions are given by

$ k\equal{}32 \alpha \plus{}8\beta\plus{}2\gamma \plus{}5$
$ m\equal{}32(1\minus{}\alpha)\plus{}8(1\minus{}\beta)\plus{}2(1\minus{}\gamma)\plus{}5\equal{}52\minus{}k$

with $ \alpha,\beta,\gamma\in\{0,1\}$ (i.e. 8 different ordered solutions)

[quote="hjbrasch"]actually, one can easily show that all possible solutions are given by

$ k \equal{} 32 \alpha \plus{} 8\beta \plus{} 2\gamma \plus{} 5$
$ m \equal{} 32(1 \minus{} \alpha) \plus{} 8(1 \minus{} \beta) \plus{} 2(1 \minus{} \gamma) \plus{} 5 \equal{} 52 \minus{} k$

with $ \alpha,\beta,\gamma\in\{0,1\}$ (i.e. 8 different ordered solutions)[/quote]

How can you find exactly it?

$ 293\equal{}1\cdot 3^5\plus{}1\cdot 3^3\plus{}2\cdot 3^2\plus{}1\cdot 3^1\plus{}2\cdot 3^0$ and now you look for decompositions

$ 293\equal{}f(k)\plus{}f(m)\equal{}\sum_{i\equal{}0}^5(a_i\plus{}b_i)3^i$ with $ 0\leq a_i,b_i\leq 1$ from which it follows that $ 0\leq a_i\plus{}b_i\leq 2$ and all sums $ a_i\plus{}b_i$ are uniquely determined.

[quote="hien"]Okay, i see, thanks so much for reply[/quote]

Hi teacher Hien  :D . I saw it is a problem from book " Bài toán hàm số qua các kì thi Omlympic " of Nguyễn Trọng Tuấn , it is so nice  :wink:

Yes, the idea of solving is that a number is presented based on base 2 and the function values in base 3


Here is a cute problem that I like very much:
   Given is a number $a\geq 2$. Prove that for infinitely many numbers $n$, the largest prime factor of $ a^n-1$ is at least $ n\cdot log_a{n}$.

And I was hoping that at least this problem is not so ugly, but nobody is interested... :(  :blush:


geometry
circumcircle
parallelogram
incenter
angle bisector
geometry solved

Russia 1996..
good problem  :)

[Moderator edit: Note that the version of this problem on Kalva's site is wrong, because it has AB = AC instead of the correct AB = BC.]

We'll analize the case when $\triangle{ABC}$ is acute(the case when it's obtuse can be solved in a similar way).
Let $OE$ meet $CD$ at $K$ and the altitude from $B$ meet $CD$ at $L$ and $AC$ at $H$.
Then, since $KOCH$ is cyclic:
$\angle{BOE}=\angle{KOL}=\angle{DCA}=\angle{DCB}$, hence $LOEC$ is cyclic. From here we get that:
$\angle{OLE}=\angle{OCE}=\angle{OBC}$, hence $BE=EL$. Since $\angle{ABO}=\angle{BLE}$ we see that $AB$ is parallel to $LE$, so $DFEL$ is a paralelogram $\rightarrow$ $DF=LE=BE$.

[quote="Amir.S"]Let $ABC$ be an isosceles triangle with $AB=BC$. Let $O$ be the center of the circumcircle of triangle $ABC$. The angle bisector of the angle $BCA$ meets the side $AB$ at $D$. The perpendicular to the line $CD$ through the point $O$ intersects the line $BC$ at $E$. The parallel to the line $CD$ through the point $E$ meets the line $AB$ at $F$. Show that $DF=BE$.[/quote]

Here is another solution of the problem.

We will use directed angles modulo 180°.

Since $OE\perp CD$, we have < (OE; CD) = 90°, and thus

< (OE; BC) = < (OE; CD) + < (CD; BC) = 90° + < (CD; BC) = 90° + < DCB.

On the other hand, since the triangle ABC is isosceles (with AB = BC) and O is its circumcenter, we have $BO\perp CA$. Thus, < (BO; CA) = 90°, and it follows that

< (BO; CD) = < (BO; CA) + < (CA; CD) = 90° + < (CA; CD) = 90° + < ACD.

But since the line CD is the angle bisector of the angle BCA, we have < DCB = < ACD, so that < (OE; BC) = 90° + < DCB = 90° + < ACD = < (BO; CD). In other words, if L is the point of intersection of the lines BO and CD, we have < OEC = < OLC. Hence, the points O, C, E and L lie on one circle. Consequently, < LEC = < LOC. But < LOC = < BOC, and since the point O is the circumcenter of triangle ABC (i. e., the center of the circle through the points A, B, C), the central angle theorem for directed angles modulo 180° yields < BOC = 2 < BAC. Thus,

  < LEC = < LOC = < BOC = 2 < BAC = < BAC + < BAC
            = < BAC + < ACB         (since < BAC = < ACB, as the triangle ABC is isosceles)
            = < (AB; CA) + < (CA; BC) = < (AB; BC).

In other words, < (LE; BC) = < (AB; BC). Thus, LE || AB. In other words, LE || DF. Since we also know that EF || DL (this is just a rephrase of EF || CD), it follows that the quadrilateral EFDL is a parallelogram. Thus, DF = LE.

Now, since the point O is the circumcenter of triangle ABC, we have BO = CO, so that the triangle BOC is isosceles, and thus < OBC = < BCO. In other words, < LBE = < ECO. But since the points O, C, E and L lie on one circle, we have < ECO = < ELO. Thus, < LBE = < ELO. In other words, < LBE = < ELB. Hence, the triangle BEL is isosceles, and BE = LE. Comparing this with DF = LE, we get DF = BE. Problem solved.

[b]EDIT:[/b] A bit more can be said about the configuration of this problem:

Since the triangle ABC is isosceles (with AB = BC), and O is its circumcenter, the line BO is the angle bisector of the angle ABC. Also, we know that the line CD is the angle bisector of the angle BCA. Hence, the point L, defined as the point of intersection of the lines BO and CD, must be a common point of two angle bisectors of triangle ABC; thus, the point L is the incenter of triangle ABC. The point E can be considered as the point of intersection of the circumcircle of triangle COL with the line BC different from C (in fact, we have showed that the points O, C, E and L lie on one circle). Now, we know that LE || AB and $OE\perp CD$. Thus, we have solved the following problem:

[color=blue][b]Additional problem.[/b] Let ABC be an isosceles triangle with AB = BC. Let O be the circumcenter and L the incenter of triangle ABC. Denote by E the point of intersection of the circumcircle of triangle COL with the line BC different from C. Then, prove that LE || AB and $OE\perp CD$.[/color]

  darij

Let the circumcentre be O and the incentre be I. Connect CO and EI.

Let $\angle{BCD}=x$, then $\angle{CBI}=90^{o}-\angle{BCA}=90^{o}-2x$ and $\angle{CEO}=90^{o}-x$. Since we have $\angle{BOE}=\angle{CEO}-\angle{CBI}=x$. Thus $\angle{BOE}=\angle{BCI}$. Therefore C,E,O,I are concyclic. Thus $\angle{EIO}=\angle{ECO}=\angle{EBO}$ which gives that $BE=IE$.

Since $\angle{CEI}=\angle{COI}=\angle{CBD}$, so $IE \parallel FD$. Since $EF \parallel ID$, so EFDI is a parallelogram. Therefore $FD=EI=EB$.


geometry
IMO Shortlist
quadrilateral
incircle
Triangle

This is really a perfect corollary for the Monge-D'Alembert circle theorem and its 1-2 variant.

[b]Theorem 1[/b] (Monge-D'Alembert). The exsimilicenters of three given circles in general position are collinear.

[i]Proof of Theorem 1[/i]. This is a simple consequence of Menelaus' theorem, since the exsimilicenter $ E$ of two circles $ \mathcal{C}_{1}(O_{1},r_{1})$ and $ \mathcal{C}_{2}(O_{2},r_{2})$ satisfies $ EO_{1}/EO_{2} \equal{} r_{1}/r_{2}$ (the segments are not oriented).

[b]The 1-2 variant of Theorem 1[/b]. Let there be three circles in general position. The exsimilicenter of two of them lies on the line determined by the insimilicenters of the other two pairs.

Consider $ \Gamma(O)$ the circle tangent to the lines $ AB$, $ BC$, $ AD$ of the quadrilateral $ ABCD$ (this circle obviously exist, according to Apollonius) and denote by $ \rho_{1}$, $ \rho_{2}$, $ \rho_{p}$ the incircles of triangles $ APD$, $ BPC$ and $ CPD$ respectively.
Since $ A$ is the exsimilicenter of $ \rho_{1}$ and $ \Gamma$ and $ K$ is the insimilicenter of $ \rho_{1}$ and $ \rho_{p}$, according to the 1-2 variant of the Monge-D'Alembert theorem, the line $ AK$ intersects the line $ OI$ at the insimilicenter of $ \Gamma$ and $ \rho_{p}$. Similarly, we obtain that the line $ BK$ intersects $ OI$ at the same insimilicenter $ F$ of $ \Gamma$ and $ \rho_{p}$. Thus, it remains to prove that $ E$ lies on the line $ OI$.
It is easy to see now that the quadrilaterals $ APCD$ and $ PBCD$ are circumscribed. Denote by $ \omega_{a}$ and $ \omega_{b}$ their incircles. We proceed similarly: $ A$ is the exsimilicenter of $ \omega_{a}$ and $ \Gamma$, $ C$ is the exsimilicenter of $ \omega_{a}$ and $ \rho_{p}$, and thus, according this time to the original Monge-D'Alembert theorem, the line $ AC$ intersects the line $ OI$ at the exsimilicenter of the circles $ \rho_{p}$ and $ \Gamma$. Analogously, $ B$ is the exsimilcenter of $ \omega_{b}$ and $ \Gamma$, $ D$ is the exsimilcenter of $ \rho_{p}$ and $ \omega_{b}$, and thus $ BD$ intersects $ OI$ at the exsimilicenter of $ \Gamma$ and $ \rho_{p}$. In this case, we conclude that $ E$, $ F$ are the insimilicenter and exsimilicenter of the circles $ \Gamma$ and $ \rho_{p}$, respectively. This proves the problem and moreover it shows that the cross-ratio $ (O, E, I, F)$ is harmonic.

[quote="April"]Point $ P$ lies on side $ AB$ of a convex quadrilateral $ ABCD$. Let $ \omega$ be the incircle of triangle $ CPD$, and let $ I$ be its incenter. Suppose that $ \omega$ is tangent to the incircles of triangles $ APD$ and $ BPC$ at points $ K$ and $ L$, respectively. Let lines $ AC$ and $ BD$ meet at $ E$, and let lines $ AK$ and $ BL$ meet at $ F$. Prove that points $ E$, $ I$, and $ F$ are collinear.

[i]Author: Waldemar Pompe, Poland[/i][/quote]

Double Desargue!

[b]Lemma 1:[/b] If the incircles of $WXY$ and $WZY$ in convex quadrilateral $WXYZ$ are tangent, then $WXYZ$ is circumscriptible.

Suppose the incircles are tangent to each other at $T$. Then we have
\[WX+WY-XY=2WT=WZ+WY-YZ\]
which implies that $WX+YZ=WZ+XY$, so the result follows.

[b]Lemma 2:[/b] If a circle $\Gamma$ is externally tangent to two circles $\Gamma_1$ and $\Gamma_2$ at $M$ and $N$, respectively, then $MN$ passes through the exsimilicenter of $\Gamma_1$ and $\Gamma_2$.

This is a variant of the Monge circle theorem, but can be proven using simple homothety.

[b]Proof of Problem:[/b]
Let
$I_1$ be the incenter of $APD$
$I_2$ be the incenter of $BPC$
$I_1'$ be the incenter of $APCD$ (this exists by Lemma 1)
$I_2'$ be the incenter of $BPDC$ (------)
$G$ be the intersection of $AI_1$ and $AI_2$.

I claim that $E,F,G,I$ lie on a line.

By Desargue on $AI_1K$ and $BI_2L$ and Lemma 2, $FIG$ is a line. (as $AK\cap BL=F$, $I_1K\cap I_2L=I$, and $AI_1\cap BI_2=G$.

Note that $AB,CD,I_1'I_2'$ concur on the exsimilicenter of the incircles of $APCD$ and $BPDC$. Thus by Desargue on $AI_1'C$ and $BI_2'D$, $EIG$ is a line, as $AI_1'\cap BI_2'=G$, $CI_1'\cap DI_2'=I$, and $AC\cap BD=E$.

This completes the proof.

Only a single Desargue is needed. :)

[hide="Solution by math154 and me"]Let $\omega_A$ and $I_A$ be the incircle and incenter of $\triangle APD$, respectively, and let $\omega_B$ and $I_B$ be the incircle and incenter of $\triangle BPC$, respectively.   We have $AP + PD - AD = 2PK = PD + PC - DC = 2PL = PB+PC-BC$, whence $AP+CD = AD+PC$ and $BP+CD = BC+PD$, so $APCD$ and $PBCD$ are tangential quadrilaterals. Let their incircles be $\omega_1$ and $\omega_2$, respectively. By Monge's theorem on $\omega_A$, $\omega_1$, and $\omega$, we find that the exsimilicenter $X_A$ of $\omega$ and $\omega_A$, $A$, and $C$ are collinear. By Monge's theorem on $\omega_B$, $\omega_2$, and $\omega$, we find that the exsimilicenter $X_B$ of $\omega$ and $\omega_B$, $B$, and $D$ are collinear.

Let $X_P$ be the exsimilicenter of $\omega_A$ and $\omega_B$. By d'Alembert's theorem on $\omega_1$, $\omega_2$, and $\omega$, $X_P$, $X_A$, and $X_B$ are collinear. Hence, we may apply Desargue's theorem on $AKX_A$ and $BLX_B$ to find that $F$, $I$, and $E$ are collinear. [/hide]

Truly a beautiful problem :)

[hide="Solution"]So \[PK=\frac{PD+PC-DC}{2}=\frac{PD+PA-DA}{2}\implies AP+CD=PC+DA\] implies that quadrilateral $APCD$ has an incircle; call it $\omega_a$. Let $I_a$ be the insimilicenter of $\omega$, $\omega_a$ and define $\omega_b$, $I_b$ similarly. By Monge D'Alembert on $\omega$, $\omega_a$, and the incircle of triangle $APD$, $I_a\in AK$; similarly $I_b\in BL$. By Desargue on triangles $AI_aC$ and $BI_bD$, it suffices to show that $AB$, $CD$, $I_aI_b$ concur. But this follows from Monge D'Alembert on $\omega$, $\omega_a$, $\omega_b$. $\blacksquare$[/hide]

This is very very beautiful!

It can be done using Monge d'Alembert theorem multiple times. In my solution I also used three constructed circles.

Let $BC$ and $AD$ meet at $G$.

Let $\omega$ be the incircle of $PCD$. Let $\omega_1$ and $\omega_2$ be the incircles of $PAD$ and $PBC$. Let $\Gamma$ be the incircle of $GAB$.

Note that
\[
\frac{PD+PC-CD}{2}=\frac{PA+PK-AD}{2}
\]
so $PA+CD=PC+AD$ and $PCDA$ is circumscribed. Similarly, so is $PDCB$. Let $\Gamma_1$ and $\Gamma_2$ be the incircles of these quadrilaterals, respectively. Let $Se(X,Y)$ denote the exsimilicenter of two circles $X,Y$, and let $Si(X,Y)$ denote their insimilicenter.

By Monge on $\Gamma,\omega_1,\omega,$ $Si(\Gamma,\omega)$ lies on $AK$ and similarly $BL$.

By Monge on $\Gamma_1,\omega_1,\omega$, $Se(\omega_1,\omega)$ lies on $AC$. By Monge on $\Gamma, \omega_1,\omega$, $Se(\gamma,\omega)$ is collinear with $A$ and $Se(\omega_1,\omega)$. So it also lies on $AC$, and similarly $BD$.

Thus the three points are collinear on the line through the centers of $\omega$ and $\Gamma$.

Very beautiful!

We begin by noticing that the quadrilaterals $PADC$ and $PBCD$ are circumscribed. Indeed, we have $$PA-AD=PK-KD= PC-CD$$ and by the converse of Pithot's Theorem, the claim holds. A similar argument works for $PBCD$. Let us denote by $\omega$ the incircle if triangle $PDC$ with center $I$ and by $\Omega$ the circle tangent to the lines $AB,BC,AD$ with center $O$ and let circles $\omega_1$ and $\omega_2$ denote the incircles of triangles $PAD$ and $PBC$, respectively. Denote by $\Omega_1$ and $\Omega_2$ the inscribed circles in the quadrilaterals $PADC$ and $PBCD$, respectively. Let $E',F'$ be the exsimilicenter and insimilicenter, respectively, of the circles $\omega$ and $\Omega$. The points $O,I,E',F'$ are collinear and $(O,I,E',F')=-1$.

Next, we show that $A,C,E'$ are collinear and $A,K,F'$ are collinear. Similar statements shall hold for $B$ and we will get $E=E'$ and $F=F'$ proving the result.

Notice that $A$ is the exsimilicenter for circles $\omega_1$ and $\Omega$ and $K$ is the insimilicenter for circles $\omega_1$ and $\omega$. Applying Monge D'Alembert's Theorem, we see that points $A,K,F'$ are collinear.

Notice that $A$ is the exsimilicenter for circles $\omega_1$ and $\Omega_1$ and $C$ is the exsimilicenter for circles $\Omega_1$ and $\omega$ thus, by Monge D'Alembert's Theorem, line $AC$ passes through the exsimilicenter of circles $\omega_1$ and $\omega$. Also, note that $A$ is the exsimilicenter of circles $\omega_1$ and $\Omega$ and so, by Monge D'Alembert's Theorem, line $AE'$ passes through the exsimilicenter of circles $\omega_1$ and $\omega$. This proves that $A,E',C$ are collinear and the conclusion holds.

Let $\omega_A$ and $\omega_B$ be the incircles of $\triangle APD$ and $\triangle BPC$, and let $I_A$ and $I_B$ be their centers. Let lines $AI_A$ and $BI_B$ meet at $J$. Then let $\omega_J$ be the circle centered at $J$ tangent to lines $AB$, $AD$, and $BC$.

Now, note
\[AP - AD = KP - KD = CP - CD,\]
so $APCD$ has an incircle $\gamma_D$. Similarly define $\gamma_C$.

We are now ready to solve the problem.
[list]
[*] By Monge on $\gamma_C, \omega, \omega_J$, the exsimilicenter for $\omega$ and $\omega_J$ belongs to $AC$; similarly it belongs to $BD$ and it is $E$.
[*] By Monge on $\omega_A, \omega, \omega_J$, the insimilicenter for $\omega$ and $\omega_J$ belongs to $AK$; similarly it belongs to $BL$ and it is $F$.
[/list]
Thus $E$, $F$, $I$, $J$ are collinear.

Solution from [i]Twitch Solves ISL[/i]: We begin with the following claim.

[b][color=red]Claim:[/color][/b]  	The quadrilaterals $APCD$ and $PBCD$ 	both have an incircle.

[i]Proof.[/i]  	Follows by Pitot theorem since $AP+CD = PC+DA$ 	(see SL 2017 G7 for another example of this lemma). $\blacksquare$

Let $I$ be the center of $\omega$ (the incenter of $\triangle CPD$). Moreover, if we let $G = \overline{AD} \cap \overline{BC}$, we will denote by $J$ the incenter of $\triangle GBA$, and by $(J)$ the circumcircle.

[asy] size(12cm);

pair D = (11.14,-6.04); pair C = (2.,-6.); pair P = (4.444652508480686,1.8445570362182018); pair I = (5.51778691510771,-3.4234688887952602); pair K = (7.493465232949166,-1.745777572891788); pair L = (3.0432615410670767,-2.652315765041075); pair T = (5.5064439102990566,-6.015345487572424); pair A = (15.364272954643416,5.744248447444408); pair B = (-3.880008641661257,-1.1284043179454462); pair F = (5.883808240537381,-3.2775609912250143); pair J = (6.629240970901842,-2.980407478817377); pair G = (9.058135630380526,-11.847675599776444);

filldraw(B--A--G--cycle, invisible, deepcyan); filldraw(incircle(B, A, G), invisible, deepcyan); filldraw(P--C--D--cycle, invisible, red); filldraw(incircle(P, C, D), invisible, red);

draw(B--F--A, dotted); draw(A--C, dotted); draw(B--D, dotted); pair E = extension(B, D, A, C);

draw(incircle(B, P, C), deepgreen); draw(incircle(A, P, D), deepgreen); pair I_1 = extension(D, I, B, incenter(B, P, C)); filldraw(CP(I_1, foot(I_1, C, D)), invisible, orange+dashed); pair I_2 = extension(C, I, A, incenter(D, P, A)); filldraw(CP(I_2, foot(I_2, C, D)), invisible, orange+dashed);

dot("$D$", D, dir(D)); dot("$C$", C, dir(225)); dot("$P$", P, dir(120)); dot("$I$", I, dir(I)); dot("$K$", K, dir(K)); dot("$L$", L, dir(L)); dot("$T$", T, dir(T)); dot("$A$", A, dir(A)); dot("$B$", B, dir(B)); dot("$F$", F, dir(F)); dot("$J$", J, dir(J)); dot("$G$", G, dir(G)); dot("$E$", E, dir(E));

/* TSQ Source:

!size(12cm);

D = (11.14,-6.04) .C = (2.,-6.) R225 .P = (4.444652508480686,1.8445570362182018) R120 I = (5.51778691510771,-3.4234688887952602) K = (7.493465232949166,-1.745777572891788) L = (3.0432615410670767,-2.652315765041075) T = (5.5064439102990566,-6.015345487572424) A = (15.364272954643416,5.744248447444408) B = (-3.880008641661257,-1.1284043179454462) F = (5.883808240537381,-3.2775609912250143) J = (6.629240970901842,-2.980407478817377) G = (9.058135630380526,-11.847675599776444)

B--A--G--cycle 0.1 lightcyan / deepcyan incircle B A G 0.1 lightcyan / deepcyan P--C--D--cycle 0.1 lightred / red incircle P C D 0.1 lightred / red

B--F--A dotted A--C dotted B--D dotted E = extension B D A C

incircle B P C deepgreen incircle A P D deepgreen I_1 := extension D I B incenter B P C CP I_1 foot I_1 C D 0.1 yellow / orange dashed I_2 := extension C I A incenter D P A CP I_2 foot I_2 C D 0.1 yellow / orange dashed

*/ [/asy]

[b][color=red]Claim:[/color][/b]  	The point $F$ is the insimilicenter of $(I)$ and $(J)$.

[i]Proof.[/i]  	By Monge d'Alembert theorem on $(I)$, $(J)$, and 	the incircle of $\triangle APB$, we 	get that $\overline{BL}$ passes through said insimilicenter. 	By symmetry, so does $\overline{CK}$, as needed. $\blacksquare$

[b][color=red]Claim:[/color][/b]  	The point $E$ is the exsimilicenter of $(I)$ and $(J)$.

[i]Proof.[/i]  	By Monge d'Alembert theorem on $(I)$, $(J)$, and 	the incircle of $BPDC$, we 	get that $\overline{BD}$ passes through said exsimilicenter. 	By symmetry, so does $\overline{CA}$, as needed. $\blacksquare$

The previous two claims imply all four points $E$, $F$, $I$, $J$ are collinear.

First we claim that the Quadrilaterals $APCD$ and $BPDC$ are circumscribed .

Note that $$PK= \frac {PD+PC-DC}{2} = \frac {PA+PD-AD}{2} \implies AD + PC=PA+CD$$

Hence by converse of Pitot's theorem, $APCD$ has a incircle . Similarly $BPDC$ has a incircle.

Denote by $\omega_1 ,\omega_2$ ,the incircles of $\Delta APD$ and $\Delta BPD$ . Denote by $\Omega_1 ,\Omega_2$ ,the incircles of Quadrilaterals $APCD$ and $BPDC$ . Define $U \equiv DA \cap BC$ . Denote by $\Omega$ the $U$-excircle of $\Delta UAB$. Let $J$ denote the center of $\Omega$ . We show that $F,E,I,J$ lie on the same line .

Denote by $f(\alpha, \beta)$ and $g(\alpha, \beta)$ the exsimilicenter and insimilicenter of circles $\alpha$ and $\beta$ respectively .

Now we begin the Monge assault . :D

First Monge's on the triples $\{\Omega,\Omega_1,\omega \}$ implies that $\underbrace {f(\Omega_1,\Omega)}_{A} - \underbrace {f(\Omega_1,\omega)}_{C} -{f(\Omega,\omega)}$ .
 Similarly $B-D-f(\Omega,\omega)$ .

Hence $f(\Omega,\omega)= AC \cap BD \equiv E$ $\blacksquare$ .

Next Monge on $\{\Omega,\omega_1,\omega \}$ implies $\underbrace {f(\Omega,\omega_1)}_{A} - \underbrace {g(\omega_1,\omega)}_{K} -{g(\Omega,\omega)}$ .
Similarly $B-L-g(\Omega,\omega)$.

Hence $g(\Omega,\omega)= AK \cap BL \equiv F$ $\blacksquare$ .

Hence $I,J,F,E$ are collinear as desired

Solved with [b]nukelauncher[/b].

Let \(\omega_A\), \(\omega_B\) denote the incircles of \(\triangle APD\), \(\triangle BPC\). Observe from \(\triangle CPD\) and \(\triangle APD\) that \[\frac{PC+PD-CD}2=PK=\frac{PA+PD-CD}2\implies PC+AD=PA+CD,\] so by Pitot's theorem, quadrilateral \(PADC\) has an incircle \(\Gamma_A\). Analogously, quadrilateral \(PBCD\) has an incircle \(\Gamma_B\).

[asy]         size(9cm); defaultpen(fontsize(10pt));         pen pri=lightblue;         pen sec=red;         pen tri=purple;         pen qua=fuchsia;         pen fil=invisible;         pen sfil=invisible;         pen tfil=invisible;         pen qfil=invisible;

pair P,C,D,I,K,L,IA,IB,A,B,EE,F,Q,O,I1,I2;         P=dir(120);         C=dir(205);         D=dir(335);         I=incenter(P,C,D);         K=foot(I,P,D);         L=foot(I,P,C);         IA=K+0.8*(K-I);         IB=extension(L,I,P,P+(C-P)*dir(90)*(IA-P)/(I-P));         A=extension(P,reflect(P,IA)*K,D,reflect(D,IA)*K);         B=extension(P,reflect(P,IB)*L,C,reflect(C,IB)*L);         EE=extension(A,C,B,D);         F=extension(A,K,B,L);         Q=extension(A,D,B,C);         O=incenter(Q,A,B);         I1=extension(A,IA,C,I);         I2=extension(B,IB,D,I);

draw(B--F--A,tri);         draw(B--D,sec); draw(A--C,sec);         draw(C--foot(O,B,C),pri);         filldraw(incircle(Q,A,B),qfil,qua+Dotted);         filldraw(circle(I1,abs(I1-foot(I1,C,D))),sfil,sec+dashed);         filldraw(circle(I2,abs(I2-foot(I2,C,D))),sfil,sec+dashed);         filldraw(incircle(P,A,D),tfil,tri);         filldraw(incircle(P,C,B),tfil,tri);         filldraw(incircle(P,C,D),qfil,qua);         filldraw(A--B--C--D--cycle,fil,pri);         draw(C--P--D,pri);         draw( (EE+4*(EE-O))--(O+3*(O-EE)),blue+dashed);

dot("\(P\)",P,N);         dot("\(C\)",C,SW);         dot("\(D\)",D,SE);         dot("\(A\)",A,NE);         dot("\(B\)",B,W);         dot("\(K\)",K,dir(15));         dot("\(L\)",L,dir(120));         dot("\(E\)",EE,S);         dot("\(F\)",F,dir(280));         dot("\(I\)",I,dir(260));         dot("\(O\)",O,SE);         label("\(\omega\)",I+inradius(P,C,D)*SE,E,qua);         label("\(\Gamma\)",O+inradius(Q,A,B)*SE,SE,qua);         label("\(\omega_A\)",IA+inradius(A,D,P)*dir(300),dir(330),tri);         label("\(\omega_B\)",IB+inradius(B,C,P)*dir(150),dir(150),tri);         label("\(\Gamma_A\)",I1+abs(I1-foot(I1,C,D))*dir(-30),dir(120),sec);         label("\(\Gamma_B\)",I2+abs(I2-foot(I2,C,D))*dir(150),W,sec);     [/asy]

If \(I_A\), \(I_B\) denote the centers of \(\omega_A\), \(\omega_B\), then let \(O=\overline{AI_A}\cap\overline{BI_B}\). Then there is a circle \(\Gamma\) centered at \(O\) tangent to \(\overline{AB}\), \(\overline{BC}\), \(\overline{AD}\). [list]     [*]By Monge's theorem (with three exsimilicenters) on \(\omega\), \(\Gamma\), \(\Gamma_A\), the exsimilicenter of \(\omega\) and \(\Gamma\) lies on \(\overline{AC}\); analogously, it lies on \(\overline{BD}\), so it is \(E\).     [*]By Monge's theorem (with one exsimilicenter and two insimilicenters) on \(\omega\), \(\Gamma\), \(\omega_A\), the insimilicenter of \(\omega\) and \(\Gamma\) lies on \(\overline{AK}\); analogously, it lies on \(\overline{BL}\), so it is \(F\). [/list] Then the points \(E\) and \(F\) lie on line \(OI\), as required.

Probably same as above$,$ but I$'$m extremely glad I managed to solve yet another $\text{G8}.$

[b]Lemma 1:[/b] Quadrilaterals $APCD$ and $BPDC$ have incircles$.$
[i]Proof:[/i] We only prove this for $APCD,$ as the argument will be similar for $BPDC.$ Let $w_1$ touch $AB, AD$ at $U_1, U_2$ respectively and $w$ touch $CD$ at $V.$ It is evident that $$AU_1=AU_2, PU=PK=PL, CL=CV, DV=DU_2.$$ Now $AP+CD=AD+CP$ and we are done$.$ $\hspace{1cm}\square$

Let the incircles of $APCD, BPDC$ be $k_1, k_2$ respectively$.$

Now for the main problem$:$
Let $X$ be the exsimilicenter of $w, w_1,$  $Y$ be the exsimilicenter of $w, w_2$ and $Z$ be the exsimilicenter of $w_1, w_2.$ By definition$,$ $X\in IK$ (since $IK$ is the line through the centers of $w, w_1$) and similarly $Y\in IL.$

First apply $\text{Monge's Theorem}$ to $w_1, w$ and $k_1.$ We easily see that $A$ is the exsimilicenter of $w_1$ and $k_1,$ $C$ is the exsimilicenter of $w$ and $k_1$ and $X$ is by definition the exsimilicenter of $w_1$ and $w.$ Thus due to the mentioned theorem$,$ the point $X$ must lie on $AC.$
By the exact same reasoning this time for $w, w_2$ and $k_2,$ we see that $Y$ lies on $BD.$

Now notice that $K$ is the insimilicenter of $w_1, w,$ $L$ is the insimilicenter of $w_2, w$ and $Z$ is the exsimilicenter of $w_1, w_2,$ therefore by $\text{Monge's Theorem},$ it follows that $K, L$ and $Z$ are collinear$.$

Another application of $\text{Monge's Theorem}$ to circles $w, w_1$ and $w_2$ yields that $X, Y$ and $Z$ are collinear$.$

Finally consider triangles $AKX$ and $BLY.$ We have that $$AB\cap KL\cap XY=Z.$$ Therefore $\text{Desargues's Theorem}$ tells us that $$F=AK\cap BL, I=KX\cap LY, E=AX\cap BY$$ are collinear$,$ as desired$.$ $\hspace{1cm}\blacksquare$

This problem is insane!  :10:

Let $I_1$ be the incenter of $APD$, $I_2$ be the incenter of $BPC$ and $I$ be the incenter of $CPD$.

Now, observe that since the incircles of $APD,PDC$ are tangent at point $K$, we have that $\frac{PC+PD-CD}{2}=PK= \frac{AP+PD-AD}{2} \implies AD+PC=AP+CD$, so by Pitot's Theorem, $APCD$ has an incircle $\omega_B$. Similarly, $BPDC$ has an incircle $\omega_A$.

Let $K_B,K_A$ be the excimilienters of $\omega,\omega_1$ and $\omega,\omega_2$, respectively, where $\omega_1$ is the incircle of $APD$, $\omega_2$ is the incircle of $BPC$ and $\omega$ is the incenter of $CPD$. By Monge's Theorem on $\omega_B, \omega_1,\omega$, we have that $A,C,K_B$ are collinear. Similarly $B,D,K_A$ are collinear.

Notice that since $K$ is the inscimilicenter of $\omega_1,\omega$, we have that $I,I_1,K,K_B$ are collinear, and moreover, $(I,I_1;K,K_B)=-1$. Similarly, $(I,I_2,L,K_A)=-1 \implies (I,I_2,L,K_A)=(I,I_1;K,K_B)$. Thus, by the so forgotten [b]Prism Lemma[/b], we have that $K_BK_A,I_1I_2,KL$ are concurrent. However, since $I_1I_2 \cap K_AK_B$ lies on $AB$ (due to Monge's Theorem on $\omega_1,\omega_2,\omega$, the concurrency point is actually the excimilicenter of $\omega_1,\omega_2$), so triangles $AK_BK,BK_AL$ are in perspective, so by Desargues' Theorem, we have that $AK_B \cap BK_A=E, AK \cap BL= F, K_BK \cap K_AL=I$ are collinear, so we are done!
$\blacksquare$

Denote by $\Gamma$ circle, inscribed in both angles $ABC,BAD,$ by $\omega_1,\omega_2$ incircles of $APD,BPC.$

Note that $PBCD$ is tangential since $$|CD|+|CP|-|PD|=2|CL|=|BC|+|CP|-|PB|.$$ Then by the three homothety centers theorem center of external homothety $\omega\mapsto \omega_2$ lies on $BD,$ and analogously for center of external homothety $\omega\mapsto \omega_1.$ Applying three homothety centers theorem again, we can conclude that points $E,F$ are respectively centers of external and internal homothety $\omega\mapsto \Gamma,$ finally implying $I\in EF$.

It's not that hard to notice that $ADCP$ and $DPBC$ are circumscriptible. Call their incircles $\omega_1$ and $\omega_2$, respectively. Denote $O$ the centre of $\omega$. Also, let the incircles of $(ADP)$ and $(BPC)$ be $\omega_a$ and $\omega_b$.
Finally, consider $T_1$ and $T_2$ the exsimilicenters of $\omega_a$ and $\omega$, and $\omega_b$ and $\omega$, respectively.
\\
\\ Apply Monge for $\omega, \omega_a, \omega_1$ and get that $T_1$ lies on both $AC$ and $OK$.
\\
\\ Apply Monge for $\omega, \omega_b, \omega_2$ and get that $T_2$ lies on both $BD$ and $OL$.
\\
\\ Apply Monge one last time for $\omega, \omega_a, \omega_b$ and get that $T_1T_2, AB$ and $KL$ are concurent.
\\ Last but not least, use Desargue's theorem for triangles $AT_1K$ and $BT_2L$, and, together with our previous observations, the conclusion follows immediately.

It is clear that $APCD$ and $BPDC$ are both tangential. Indeed, $AP-AD=PK-DK=CP-CD$ and similarly for $BPDC$. Let the incircle of $APCD$ be $\Omega_A$ and incircle of $BPDC$ be $\Omega_B$. Let $\omega_A$ be the incenter and incircle of $\triangle APD$ and $\omega_B$ be the incenter and incircle of $\triangle BPC$. Let $\Omega$ be the circle tangent to segment $AB$, ray $BC$, and ray $AD$.

Let $F'$ and $E'$ be the insimilicenters and exsimilicenters of $\omega$ and $\Omega$, respectively. Using Monge on
[list=a]
[*] $\omega$, $\Omega$, $\omega_A$ gives $B,L,F'$ collinear
[*] $\omega$, $\Omega$, $\omega_B$ gives $C,K,F'$ collinear
[*] $\omega$, $\Omega$, $\Omega_A$ gives $A,C,E'$ collinear
[*] $\omega$, $\Omega$, $\Omega_B$ gives $B,D,E'$ collinear
[/list]
So $E=E'$, $F=F'$. We are done.

im not very smart (it was only around 30 minutes though)---Monge + Menelaus (intuitively though, this feels like it should work, which is nice. incircles and collinearity and no other weird conditions basically means you cant mess up)

Let's use Monge to obtain some collinearities. Define $CI\cap AK=U$ and $DI\cap BL=V$. By Monge it's not hard to prove $RUV$ collinear.

This is all we need. Consider applying Menelaus on:
\[\triangle AUC, \overline{EIF}\]
\[\triangle RAU, \overline{BVF}\]
\[\triangle RAC, \overline{EBD}\]
\[\triangle RUC, \overline{DIV}\]
where the first one is what we want to prove, and the rest are known collinearities. These give equations
\[\frac{EA}{EC}\cdot \frac{IC}{IU}\cdot \frac{FU}{FA}=1\]
\[\frac{BR}{BA}\cdot \frac{VU}{VR}\cdot \frac{FA}{FU}=1\]
\[\frac{EC}{EA}\cdot \frac{BA}{BR}\cdot \frac{DR}{DC}=1\]
\[\frac{DC}{DR}\cdot \frac{IU}{IC}\cdot \frac{VR}{VU}=1\]
Since these multiply to $1$ and three of them hold, so the fourth must also hold and $EIF$ is collinear.

Or just $\triangle AUC$ and $\triangle BVD$ perspective, oops.

Monge spam!!! This is a truly remarkable problem. I enjoyed this problem a lot!

Let $\omega_A, \omega_B$ be the incircles of $ADP$ and $BCP$, respectively, and let $I_A, I_B$ be the centers of $\omega_A$ and $\omega_B$, respectively and denote $I$ by the center of $\omega$. By Monge-D-Alembert's theorem, we see that $AB, I_AI_B, KL$ are concurrent, so applying Desargues's theorem on triangles $BI_BL$ and $AI_AL$, we get that $I, F, BI_B \cap AI_A$ are collinear. Let $J = BI_B \cap AI_A$. Then $I, F, J$ are collinear. Thus it suffices to prove that the points $E, I, J$ are collinear. Let $\Omega$ be the circle tangents $BC, AB, AD$. Then it's clear that $J$ is the center of $\Omega$. Now consider the following claim:

[b][color=red]Claim:[/color][/b] $AC \cap II_A$ is the exsimilicenter of $\omega$ and $\omega_A$.

[i]Proof.[/i] Note that $PC + PD - CD = 2PK = PD + AP - AD$, or equivalently, $AD + PC = CD + AP$. Thus quadrilateral $APCD$ is circumscribed about a circle $\gamma$. Applying Monge's theorem on circles $\omega, \omega_A, \gamma$ yields exsimilicenter of $\omega, \omega_A$ lies on line $AC$. Therefore $AC \cap II_A$ is the exsimilicenter of $\omega$ and $\omega_A$. $\blacksquare$

Now applying Monge theorem on circles $\Omega, \omega_A, \omega$, we see that the points $AC$ passes through the exsimilicenter of $\omega$ and $\Omega$. Similarly $BD$ passes through the exsimilicenter of $\omega$ and $\Omega$. Hence $E$ is the exsimilicenter of $\omega$ and $\Omega$, which means that $I, J, E$ are collinear. Thus we're done. $\blacksquare$

Straightforward.
[color=#f00][b]Claim 1:[/b][/color] $APCD,BCPD$ are inscribed quadrilateral.
[hide=Proof] $CB-CP = LC-LP = CD-DP$ $\blacksquare$[/hide]
Let $\omega$ be the incircle of $GAB$ where $G = AB \cap CD$
Let $\Omega$ be the incircle of $PCD$
Let $\omega_1$ denote the incircle of $BPCD$
Let $\omega_2$ denote the incircle of $APCD$
Let $\Gamma_1$ denote the incircle of $BPC$
Let $\Gamma_2$ denote the incircle of $APD$
[color=#00f][b]Claim 2:[/b][/color] $F$ is the insimilicenter of $\omega$ and $\Omega$
[hide=Proof]By Monge on $\Gamma_1,\Omega,\omega$ we have it on $BL$ similarly it lies on $AK$ so it is $AK \cap BL = F$ [/hide]
[color=#f00][b]Claim 3:[/b][/color] $E$ is the exsimilscenter of $\omega$ and $\Omega$
[hide=Proof]By Monge on $\omega_1,\omega,\Omega$ we get insimiliscenter lies on $BD$ and similarly on $AC$ so $AC \cap BD = F$ is the exsimiliscenter[/hide]
So we're done.
[hide=Remark]Earlier SL geos seem to like Monge spam, (like 2014 G7)[/hide]


calculus
derivative
limit
function
real analysis
real analysis unsolved

Let $ f(x)\equal{}e^{\sqrt{x}}\plus{}e^{\minus{}\sqrt{x}}$
Compute
$ \lim_{n\minus{}>\infty}\lim_{x\minus{}>0}f^{(n)}(x)$ (derivative of order n)

[hide="Hint"]Find the Taylor expansion of the even function $ g(x)\equal{}e^x\plus{}e^{\minus{}x}$ and consider the Taylor expansion of $ g(\sqrt{x})$.[/hide]

So we have $ e^x \equal{} \sum\limits_{k \equal{} 0}^\infty \frac {x^k}{k!}$ which means $ e^x \plus{} e^{ \minus{} x} \equal{} \sum\limits_{k \equal{} 0}^\infty (1 \plus{} ( \minus{} 1)^k)\frac {x^k}{k!} \equal{} \sum\limits_{k \equal{} 0}^\infty \frac {x^{2k}}{(2k)!}$.

Thus, $ e^{\sqrt x} \plus{} e^{ \minus{} \sqrt x} \equal{} \sum\limits_{k \equal{} 0}^\infty \frac {x^k}{(2k)!}$.

This then implies that the desired limit is equal to $ 0$.

Just one question, shouldn't it be $ \lim_{x\rightarrow 0^{\plus{}}}$ ?


Equilateral triangle ABC has AB=1 and has K as its circumcircle. A square, one of whose sides is parallel to BC, has two of its vertices on AB and AC, and the remaining two at K. What is the side length of the square?

what i meantwas $ \frac{\sqrt{3}}{3}$..not great with latex..but is that right/


analytic geometry
graphing lines
slope
calculus
derivative
calculus computations

$ y \equal{} \minus{} x^4 \plus{} 10x^3 \minus{} 36x^2 \plus{} 21341234220445723893240575x \plus{} 13936048234505238907$
At what x coordinate is the slope of the tangent line at a relative maximum?

What do you notice about the last two coefficients (other than their size)? There is something interesting about them that affects the problem. Just think carefully, and you will notice a pattern.

It seems that the only interesting thing about those coefficients is that they do not appear in the second derivative $ y''$.

[quote="t0rajir0u"]I don't know why you felt the need to post this problem twice.  The Calculus forum is not a game - you do not win anything if you successfully trick someone into giving an incorrect answer, and that is not likely to happen here anyway.[/quote]
Notice that the numbers have changed.

It doesn't matter; it's the same problem.  You posted this set of numbers in the previous thread and there was no good reason not to continue the discussion there.

Okay, fine. You can answer it on either topic. There is an answer this time, though.


[quote="inom"]Solve the system  of equation
$5x+3y=72$
$2x+3y=36$[/quote]

[hide]
sorry about no solution, but this question is a mental one

$x, y \longrightarrow \{12, 4\}$[/hide]

[quote="inom"]Solve the system  of equation
$5x+3y=72$
$2x+3y=36$[/quote]
[hide="Elimination Method"] Subtract equations to get $3x=36\Longrightarrow x=12$
$2(12)+3y=36\Longrightarrow3y=12\Longrightarrow y=4$ [/hide]

[quote="inom"]Solve the system  of equation
$5x+3y=72$
$2x+3y=36$[/quote]
[hide]
3x=36
x=12
60+3y=72
y=4[/hide]

I decide I like elimination by addition so:
 [hide] i wrote it out to help anyone who doen't understand

        5x + 3y = 72
         2x + 3y= 36 and i multiply this by -1

          5x + 3y = 72
         -2x - 3y= -36
            3x = 36 divide it by 3
             x=12
           60 + 3y = 72 subtract 60 on both sides!
               3y= 12 divide by 3
                y= 4
            S={(12,4)}
I won't however show elimination by temporary substitution though :maybe:
[/hide]


linear algebra
matrix
linear algebra unsolved

a) Prove that there are 5x5 complex matrices which are not unitarily tridiagonalisable.
  b) (very difficult) What about 4x4? But 3x3?  :D

There exists a bases in which the associated matrix is tridiagonal, that is all entries $a_{ij}$ with $|i-j|>1$ are 0.


On cashing a check Mr. Moneybags finds that the cashier reversed the dollars and cents. After leaving the bank he spends 5 cents for a newspaper and discovers then that he has twice the amount that the check originally called for. What was the original amount of the check?

[hide]The original check was for 31.63.
Let a = original dollars and b = original cents then the original check is for:
100a + b (in cents)
Since these are transposed:
100b + a - 5 = 2(100a + b)
98b = 199a + 5
From here, I don't know an easy way to find integer-solutions only for a and b so I drew up a table of values for 98b and another for 199a + 5, i.e.
[u]98b:[/u]
98
196
304
...
6174

[u]199a + 5[/u]
204
403
602
...
6174

since they're equal (6174) when b = 63 and a = 31, this must be a solution.[/hide]


Given positive reals $a,b,c,d$ such that $(a^{2}+b^{2})^{3}=c^{2}+d^{2}$, prove that

$\frac{a^{3}}{c}+\frac{b^{3}}{d}\geq 1$


The problem is as follows:

Each of eight boxes contains six balls. Each ball has been colored with one of $ n$ colors, such that no two balls in the same box are the same color, and no two colors occur together in more than one box. Find the smallest integer $ n$ for which this is possible.

I have the official solution:

The smallest such $ n$ is 23.

We first show that $ n \equal{} 22$ cannot be achieved. We present two arguments.

First argument:
Let $ m_{i,j}$ be the number of balls which are the same color as the $ j^{\mathrm{th}}$ ball in box $ i$ (including that ball). For a fixed box $ i$, $ i\leq i\leq 8$, consider the sums \[ S_{i}\equal{}\sum^{6}_{j \equal{} 1}m_{i,j}\mathrm{and}s_{i}\equal{}\sum^{6}_{j \equal{} 1}\frac{1}{m_{i,j}}\] For each fixed $ i$, since no pair of colors is repeated, each of the remaining seven boxes can contribute at most one ball to $ S_{i}$. This $ S_{i}\leq 13$. It follows by the convexity of $ f(x) \equal{}\frac{1}{x}$ that $ s_{i}$ is minimized when one of the $ m_{i,j}$ is equal to 3 and the other five equal to 2. Hence $ s_{i}\geq\frac{17}{6}$. Note that \[ n \equal{}\sum^{8}_{i\equal{}1}\sum^{6}_{j\equal{}1}\frac{1}{m_{i,j}}\geq 8\cdot\frac{17}{6}\equal{}\frac{68}{3}\]

Hence there must be 23 colors.

I'll give the second argument later. Could anybody enlighten me on two things:

(a) What do they mean by "it follows from the convexity of $ f(x) \equal{}\frac{1}{x}$"?
(b) Why is it that $ n \equal{}\sum^{8}_{i\equal{}1}\sum^{6}_{j\equal{}1}\frac{1}{m_{i,j}}$?

1. $ f(x)\equal{}/frac 1 x$ is talking about Jenson's inequality.
2. Consider a particular color, like the color of the $ i$th ball in the $ j$th box, then there are $ M_{i,j}$ balls of this color, and by summing over the reciprocals, you get exactly 1 for each color. Therefore, adding all the reciprocals for each $ M_{i,j}$will get the number of colors

Ok i get Part 1 now, but what do you mean by "and by summing over the reciprocals, you get exactly 1 for each color"? Thanks..

Well say we're looking at the color blue. Say there are $ b$ blue balls in total. Then for each blue ball, we have $ \frac{1}{m_{i,j}}\equal{}\frac{1}{b}$ and in the summation $ \sum_{i \equal{} 1}^{8}\sum_{j \equal{} 1}^{6}\frac{1}{m_{i,j}}$, that fraction will appear $ b$ times, so it will total up to 1.


group theory
abstract algebra
superior algebra
superior algebra unsolved

Let H be a subgroup with index 2. Prove that H is normal.

thanks

Look up the archives, this question has been treated before (also the more general case where $p$ is the smallest prime dividing the order of the group).


Isabella's house has $ 3$ bedrooms. Each bedroom is $ 12$ feet long, $ 10$ feet wide, and $ 8$ feet high. Isabella must paint the walls of all the bedrooms. Doorways and windows, which will not be painted, occupy $ 60$ square feet in each bedroom. How many square feet of walls must be painted?

$ \textbf{(A)}\ 678 \qquad \textbf{(B)}\ 768 \qquad \textbf{(C)}\ 786 \qquad \textbf{(D)}\ 867 \qquad \textbf{(E)}\ 876$

[quote="worthawholebean"]Isabella's house has $3$ bedrooms. Each bedroom is $12$ feet long, $10$ feet wide, and $8$ feet high. Isabella must paint the walls of all the bedrooms. Doorways and windows, which will not be painted, occupy $60$ square feet in each bedroom. How many square feet of walls must be painted?

$\text{(A)}\ 678 \qquad \text{(B)}\ 768 \qquad \text{(C)}\ 786 \qquad \text{(D)}\ 867 \qquad \text{(E)}\ 876$[/quote]
[hide]So the total amount of square feet of painting is going to be 1056. But we forgot to subtract the areas of the doorways and windows. They each only occupy a total 60 square feet in each bedroom so subtract 180 to get 876 oe E.[/hide]

"OMG! The ceiling is a wall too!"  :P
Freaked some people out quite a bit, this one.

the ceiling isn't a wall, we don't use such an assumption to solve the problem

No, you have it right, but blue1421 messed up.

She only calculated the areas for half of the opposing walls.

[quote="mathwizarddude"][quote="blue1421"][hide]E
3*((10*8)+(12*8)-60)=876[/hide][/quote]

This should be an easy problem, but I'm not sure why the area for each bedroom should be $ 10*8 \plus{} 12*8 \minus{} 60.$  There are four walls in each bedroom, with each pair of opposite walls having the same area.  So we should have $ 3*[2(10*8 \plus{} 12*8) \minus{} 60]$ instead.  If not, did I misunderstood the problem or something (as English is not my native language)?[/quote]

My sincerest apologies. I messed up when typing. I forgot to multiply the (10*8) and (12*8) by 2. So, I agree with your solution.


Hi guys,

I am a beginner programmer. Recently, I joined in C++ course and I got part of an assignment that I could not solve......The question is: The input file is

CA 12
CA   9
IB    3
CF  11
CF  11

The out put file should looks like

              employee name       =>  CA  21 <== total hours worked
                                                    IB     3
                                                    CF  17
This program gives the total hours worked for each employee.

briefly what I did is

fin>> initial1 >> initial2>> hours;
fin>> next_i1>> next_i2 >> hours;
while (!fin.eof())
{
      if ((next_i1 == initial1) && (next_i2 == initial2))

          total_hours = total_hours + hours;
      else
          total = hours;

       fin>> ...etc
       fin>> ..etc
}
  ....etc

I just wrote that roughly ....I hope what I mentioned was clear.

I guess most of you are expert programmer....aren't you?  :huh:

You have to keep a # of hours worked in an array. That would take 26*26 space (for all letters in alphabet). Then just read input and add up to appropriate point. Then just print all answers greater than 0. Code follows(but try to write it by yourself first)

[code]
,...some stuff

int worked[26][26] = {0}, curh;

char name[3];

while(scanf("%s %d", &curh, name)==2){

      worked[int(name[0]-'A')][int(name[1]-'A')] += curh;
}

for(i = 0; i < 26; i++)
   for(j = 0; j < 26; j++)
         if(worked[i][j])
              printf("%c%c %d\n", i+'A', j+'A', worked[i][j]);

...some other stuff :-)
[/code]


A stack of $2000$ cards is labelled with the integers from $1$ to $2000,$ with different integers on different cards. The cards in the stack are not in numerical order. The top card is removed from the stack and placed on the table, and the next card is moved to the bottom of the stack. The new top card is removed from the stack and placed on the table, to the right of the card already there, and the next card in the stack is moved to the bottom of the stack. The process - placing the top card to the right of the cards already on the table and moving the next card in the stack to the bottom of the stack - is repeated until all cards are on the table. It is found that, reading from left to right, the labels on the cards are now in ascending order: $1,2,3,\ldots,1999,2000.$ In the original stack of cards, how many cards were above the card labelled 1999?

not sure if this is correct..but i got..

[hide="???"]
927
[/hide]

Can you post your solution? An answer helps no one. As far as we know you could have guessed.

k so if i'm not mistaken clearly on the first go all cards in the places ${1,3,5...1999}$ that is $1\mod2$ are placed on the desk...so what remains is:

After Turn 1:$2,4,6..2000$, $1\mod2$ have been placed
1000 cards remain
After Turn 2:$4,8,12...2000$, $2\mod4$ have been placed
500 cards remain
After Turn 3:$8,16,24...2000$, $4\mod8$ have been placed
250 cards remain
After Turn 4:$16,32,48...2000$, $8\mod16$ have been placed
125 cards remain

Now we have an odd number of cards remaining which means that the first and the [b]last[/b] card will be placed on the desk so the second card will go on the bottom..(hope thats clear)..so we have..

After Turn 5:$64,96...1984,32$, $16\mod32$ have been placed
62 cards remain
After Turn 6:$96,160,224....1952,32$, $0\mod64$ have been placed
31 cards remain

Again note that the second card must go on the bottom..since its odd

After Turn 7:$288,416...1952,160$
15 cards remain

After Turn 8 you have the cards in this order...

${672,928,1184,1440,1696,1952,416}$

After Turn 9

${1440,1952,928}$

Clearly the $1440^{th}$ card is $1998$ and then the 1952 card goes down and so the $928^{th}$ card would be the card with the number $1999$, thus there are $\boxed{927}$ cards above..

Ya after 31 cards i just had them listed..i'm sure there's abetter way of doing this...thats why i asked first...hmm i'd like to see the more mathematical way..however..

@above yes

[hide=Recursive solution]Consider the general problem: with a stack of $n$ cards such that they will be laid out $1, 2, 3, ..., n$ from left to right, how many cards are above the card labeled $n-1$?

Let $a_n$ be the answer to the above problem.

As a base case, consider $n=2$. Clearly, the stack, from top to bottom, must be $(1, 2)$, so $a_2=0$.

Next, let's think about how we can construct a stack of $n+1$ cards from a stack of $n$ cards. First, let us renumber the current stack of $n$ by adding $1$ to the label of each of the cards. Then we must add a card labeled "$1$" somewhere in the new deck.

Working backwards, we find that we must move the bottom card to the top, then add "$1$" to the top of the deck. This is because after one move, the number "$1$" will be laid out and the top card will be moved to the bottom, so the deck becomes the same as what we had before, but with everything renumbered correctly such that $2, 3, 4, ...$ will then be laid out in order.

Therefore, if $a_n \ne n-1$ (meaning the card $n-1$ is not at the bottom of the deck and so it won't be moved to the top), then $a_{n+1} = a_n + 2$, since a card from the bottom is moved to be above the $n-1$ card, and the new card "$1$" is added to the top. If $a_n = n-1$ (meaning the card $n-1$ is the bottom card), then $a_{n+1}=1$ because the $n-1$ card will move to the top and the card "$1$" will be added on top of it.

With these recursions and the base case we found earlier, we calculate $a_{2000} = \boxed{927}$. To calculate this by hand, a helpful trick is finding that if $a_n=1$, then $a_{2n-1}=1$ as well. Once we find $a_{1537}=1$, the answer is just $1+(2000-1537)\cdot2$.[/hide]


Wow, you guys have a very nice site here!  This is amazing.  Congrats to all the people who have put work into this.

I am trying to start a similar board for our dept.  Is there someone I can get advice from?  I really like how latex can be used.

Shawn

http://www.phpbb.com/phpBB/viewtopic.php?t=94454

Hope it helps. :)

To save you looking through all 27 pages of that link :) , you could go straght to the software that you need which is [url=http://www.mayer.dial.pipex.com/tex.htm]LatexRender[/url].

You will need LaTeX, ImageMagick and GhostScript installed on the server, but if that's not possible then you can use [url=http://www.forkosh.com/mimetex.html]mimeTeX[/url] which is a CGI program; instructions are also included in the LatexRender download.

This is Awsome!  Thanks!  Is there someone on here I can pm if I have any questions?  Or just post up in a thread?

As I'm the one who maintains LatexRender you can email me - the address is at the bottom of readme.txt in the download.

Most of the time things go very easily and you are typing LaTeX in your board in minutes but, like everything to do with computers, things do occasionally go wrong. However, once sorted you can forget about it and get on with typing mathematics.
From experience the problems that are likely to arise are:
1. Latex, Imagemagick, Ghostscript (or mimeTeX) not working on the server or the host doesn't allow these programs to run or be called from PHP; these are issues to be discussed with the host
2. paths in the various files not correct; they are easy to get wrong but easy to fix

My advice is to ensure example.php (a bit like [url=http://www.artofproblemsolving.com/LaTeX/AoPS_L_TeXer.php]AoPS's TeXer[/url]) is working first, then all that's needed is to add the code to the board.

Do you have a recommandation as to where I host our board?  Our university will not host a phpBB board for "security reasons".

What kind of costs can I expect per year?

Cheers,

Shawn

The main problem is finding a host that understands what LaTeX is and provides it on the server. You may also prefer a host based in your own country.

One company I came across via [url=http://www.jwbales.us/math/]Dr. Bales’ Math Blog[/url] is [url=http://www.floatinghost.com/]FloatingHost.com[/url] which advertises a LatexRender Plugin [url=http://www.floatinghost.com/web-hosting/web-features.htm]here[/url] (under Server Technologies) so they presumably understand LaTeX. However, I have absolutely no experience of them so this is only an observation not a recommendation.

Otherwise you need to look at hosts that friends recommend and ask those hosts if they are willing to provide LaTeX.

If you are using phpBB don't forget that the LatexRender page  points to Aaron Erickson's mod which conforms to phpBB standards, which should help when you upgrade phpBB in the future.


Prove or disprove that:

$ (ab \plus{} bc \plus{} ac)(\frac {a}{b} \plus{} \frac {b}{c} \plus{} \frac {c}{a}) \leq (a^2 \plus{} b^2 \plus{} c^2)^2$

for positive reals $ a,b,c$ satisfying $ a \plus{} b \plus{} c \ge abc$

Try $ a \equal{} b \equal{} 1,c \equal{} 0.1$.


Each face of a cube is given a single narrow stripe painted from the center of one edge to the center of its opposite edge.  The choice of the edge pairing is made at random and independently for each face.  What is the probability that there is a continuous stripe encircling the cube?

$ \textbf{(A)}\ \frac {1}{8}\qquad \textbf{(B)}\ \frac {3}{16}\qquad \textbf{(C)}\ \frac {1}{4} \qquad \textbf{(D)}\ \frac {3}{8}\qquad \textbf{(E)}\ \frac {1}{2}$

[hide] There are three distinct possible stripes that could encircle the cube.  For every one of the these three stripes, there are two faces that can have their stripe oriented in any direction.  Since each face has two possibilities for its stripe, there are 2x2x3=12 cubes with a stripe going around it.  The total number of cubes is 2^6, since theres two possible stripe orientations for every face.

2x2x3/2^6= 3/2^4=3/16.[/hide]

[hide="Almost the same as the above."]
=====
There are three possible loops with any given orientation and each occurs with probability $ \frac{1}{16}$ since four of the stripes need to be lined up in a certain way. So $ \frac{3}{16}$.
=====
[/hide]

I got this because I had to make a ton of Rubik's Cubes diagrams last week. Basically, I thought how no matter what you do for the first stripe, you can put it so that it's horizontal on the side facing you. You can get a stripe that doesn't intersect the top or bottom $ (1/2)^3\equal{}1/8$ of the time. You can get a stripe from the bottom that goes through the top $ (1/2)^4\equal{}1/16$ of the time. $ 1/8\plus{}1/16\equal{}3/16$

That was pretty much the easiest last AMC 10 problem ever.

[hide="solution"]
Start with any face of the cube.

Case 1: That face is part of the continuous stripe.
There are two ways to position the stripe on this face. The opposite face must have the same position, as well as the two other faces that border both of the faces we've already fixed. For the remaining two faces, there are two ways for each, so 2*2*2=8 ways here.

Case 2: This face is not part of the continuous stripe
There are still two ways for this, and two as well for the opposite face. There is only one way for the other four faces, since they can't be positioned in a way which violates the restrictions of this case.

Thus, there are 12 possible arrangements out of 64 possible, so B.[/hide]

What did they mean by opposite edge? Was this to the opposite edge of the cube that would have a length of $ 2s$ where $ s$ is a side of the cube? Or does opposite edge mean the opposite edge on the face of the cube? I was so confused by this........

[hide]There are 3 ways for the stripe to go (front over the top to back) (front across left to back) (left across top to right) In each of the loops, there are 4 sides, the other two don't matter. Since there is only 1 right way and 2 choices for 4 sides, you do 1^4/2^4=1/16. 1/16*3=3/16 or B[/hide]

You put up an argument, but then wouldn't there be a face not with a stripe. Maybe that is why it is not allowed?

[quote="kaiz99"]I got 1/8 for this, and i got that because i assumed that the stripe could go from edge A to edge B, then go back from B to A, and do that, and thus i got the probability as 1/8+1/16+1/32+....., why can't the stripe keep going back and forth between two edges? Did I misread?[/quote]

You misread. Each face gets one stripe. You don't start at an edge and then move to another edge.

I read this as "from the center of one face to the center of an adjacent face".

I thought this was kinda misplaced. Oh well.

[hide="Solution"]
===============================

The probability for 4 stripes to go in the same direction is:

$$ \left(\frac{1}{2}\right)^4=\frac{1}{16} $$

There are three ways for this to happen each with two faces parallel to each other with stripes that we don't care about.

So:

$$ \frac{1}{16}\cdot3=\boxed{\frac{3}{16}} \ or \ \boxed{B}$$

===============================
[\hide]


MATHCOUNTS
articles
ARML
mathleague.org
Purple Comet

In high school, are there any math competitions like Mathcounts (but in high school)?
Well, I'm not looking for a math club where anyone can join, but more like a team (yes, with tryouts) that has some challenge in it? :surf:

Should this really be in this forum?
If you want a team one, maybe Mandelbrot, Itest, Purple Comet, and maybe others. For mostly individual ones, the AMC/AIME/USAMO is the major one.

There is also ARML.

In high school, it is easy to find challenge :)

[quote="hunter34"]Can't forget about MOP/IMO[/quote]

MOP is a "program".  :wink:
http://en.wikipedia.org/wiki/Mathematics_competitions#National_high_school_competitions

With articles about them too!

$ \mu\,\alpha\,\theta$!

[quote="Temperal"][quote="hunter34"]Can't forget about MOP/IMO[/quote]

MOP is a "program".  :wink:
http://en.wikipedia.org/wiki/Mathematics_competitions#National_high_school_competitions

With articles about them too!

$ \text{Mu Alpha }\theta$![/quote]
that's a good one. ARML, Mu alpha theta, Mandelbrot. also Rocket City ML

Can't forget about the pair mathleague.org and mathleague.com (totally unrelated)

I used to do a lot of math competitions but then I moved :(

http://theitest.com

http://purplecomet.org

I almost forgot these.


A bag contains 'm' white and 'n' black balls.A ball is drawn from the bag and is put back into the bag with 'k' additional balls of the same color as that of the ball drawn.Now,another ball is drawn from the bag.Find the probability that this ball is white.

The answer comes out to be m/(m+n).

If again a ball is drawn and then it is put back into the bag with 'k' additional balls of the same color as that of the ball drawn.Again,is the probability that a white ball is drawn is m/(m+n).

What will be the probability  of a white ball being drawn  if this process is continued 10 times?

probability doesn't appear to be the favoured topic or have i posted the question in the wrong section