geometry
circumcircle
trapezoid
perpendicular bisector

[i]For the young friends of geometry I propose the following simple and nice problem . I hope you will enjoy it :[/i]

[color=red][b] Problem[/b][/color]

 A triangle $ ABC$ has circumcenter $ O$ . Let the altitude $ AD$  and  $ M,K,L$ the midpoints of segments $ OD,AB, AC$

respectively. Prove that $ MK\equal{}ML$.

[u] Babis[/u]

[hide="One way"]

Let $ A', B',$ and $ C'$ be the vertices of the anticomplementary triangle of $ \triangle{ABC}$, the triangle whose medial triangle is $ \triangle{ABC}$.

Notice $ O$ lies on the perpendicular bisector of $ BC$, and $ D$ lies on the perpendicular bisector of $ B'C'$.  Now notice that $ K$ is the midpoint of $ C'C$ and $ L$ is the midpoint of $ B'B$.  Thus, $ M$ lies on the perpendicular bisector of $ KL$.
[/hide]

[b][color=green][u]Proof. [/u] Let $ H$ - orthocenter. Let $ E$ be center of nine-point circle (midpoint of $ OH$). Because $ EM$ is midline, $ EM \parallel AD$. Because $ AD \perp BC, KL \parallel BC, EM \perp KL$. Denote $ S \in EM \cap KL$. But $ EK \equal{} EL$ (radii of nine-point circle), so $ KS \equal{} SL$. In triangle $ MKL$ $ MS \perp KL$, so it is isosceles and $ \boxed{MK \equal{} KL}$[/color][/b]
[img]http://i040.radikal.ru/0805/67/fddddbb90ef9.jpg[/img]
[color=darkblue][b][u]Observation:[/u][/b] It is true not only for $ D$, but for every point on $ AD$.[/color]

[quote="stergiu"][color=darkred]A triangle $ ABC$ has circumcenter $ O$ . Let the altitude $ AD$ , $ D\in BC$ and  $ M,K,L$

the midpoints of segments $ OD,AB, AC$ respectively. Prove that $ MK \equal{} ML$ .[/color] [/quote]

[color=darkblue][b][u]Proof.[/u][/b] Denote the midpoints $ P$ , $ R$ , $ S$ of the side $ [BC]$ and  the segments $ [DP]$ , $ [KL]$ respectively.

Now see the trapezoid $ KLPD$ . What see you ? Observe that $ S\in AP$ , $ SA \equal{} SP$  , $ MR\parallel OP$ $ \implies$

$ M\in SR$ . Thus, $ \overline {SMR}\parallel OP\parallel AD$ , i.e. $ \overline {SMR}\perp KL$ and $ SK \equal{} SL$ . In conclusion, $ MK \equal{} ML$ .[/color]

[b]First Proof[/b]
Make the diagram so BC=a is horizontal. Let N be the midpoint of BC, so $ ON \perp BC$. We can assume D is to the left of N.
Let $ Hor(X,Y)$ denote the horizontal distance from X to Y.
Note that $ Hor(M,B) \equal{} Hor(M,D) \plus{} DB \equal{} \frac {DN}{2} \plus{} DB$. Also, $ Hor(M,B) \equal{} Hor(M,K) \plus{} Hor(K,B) \equal{} Hor(M,K) \plus{} \frac {BD}{2}$. Setting these equal, we have $ Hor(M,K) \equal{} \frac {BD \plus{} DN}{2} \equal{} \frac {BN}{2} \equal{} \frac {a}{4} \equal{} \frac {LK}{2}$, so O is equidistant from K and L.

[b]Second Proof[/b]
K,L,D, and N, the midpoint of BC, lie on the nine-point circle. Since $ KL \parallel DN$ and KLDN is cyclic, KLDN is an isoceles trapezoid. So since M lies on the perp. bisector of DN, it is equidistant from L and K.

Everyone kind of had this last proof but with a little different wording.

Indeed, let $ \mathcal {E}$ be the center of the $ 9$- point center, let $ H$ be the orthocenter of $ \triangle ABC$. It is very well- known that $ \mathcal {E}$ is the midpoint of $ OH$. Now, for any point $ G$ running on $ AD$, if $ G_0$ is the midpoint of $ OG$, it is trivial that $ G_0\mathcal {E}\parallel{}AD$. But $ AD\bot KL\Longrightarrow G_0\mathcal {E}\bot KL$. But $ \mathcal {E}\in$ the perpendicualr bisector of $ KL$. Therefore, $ G_0\in$ the perpendicular bisector of $ KL$. Hence $ G_0K\equal{}G_0L$. Let $ G_0\equiv D$. The result is lead as follow.
Our proof is completed then.


I'm an 8th grader trying to learn upper-level high school biology and some of these questions are not working out for me.

1. You're studying a cellular enzyme involved in breaking down fatty acids for energy. Looking at the R groups of the amino acids, what amino acids would you predict to occur in the parts of the enzyme that interact with the fatty acids? Why might this region of the enzyme need to be isolated into a pocket, rather on the enzyme's surface?

Maybe this site will help:
http://www.chemie.fu-berlin.de/chemistry/bio/amino-acids_en.html

2. A researcher adds substrate to a dish of liver cells that contain enzymes. For a while, no products appeared. Then, the reaction rate was quite rapid, slowed down considerably after a while, and sped up again. Explain why these events happened.

3. Critique this argument: biochemical pathways are too complex to have evolved, because all intermediate steps in a given pathway must be present to product the final product.

Problems 1 and 2 are simple chemistry questions. Google the amino acids and check out R-group structure, polarity, and electrically charged amino acids. Also, remember that enzymatic reactions are dependent on contact between substrates and enzymes. Reaction speed can depend on concentrations of substrate and enzyme because there are only so many open active sites.

Problem 3 is a good biology question. The fact is that no biochemical pathway could have evolved with any "intention." Evolution is NOT an expedient; evolution is a RESPONSE. The intermediate steps in metabolic and other biochemical pathways seem to interact to achieve a goal in the cell that has a certain effect on an organism...and they do...but that's not their original purpose. Biochemical pathways evolved from extremely simple and rudimentary reactions that benefitted primitive cells in their environment. Those primitive cells that were able (by some mechanism or another, we won't be ultra-specific) to synthesize compounds advantageous to their environment survived longer and reproduced more. For a good example, take a look at photosystems I and II. Photosystem I (an already pretty developed biochemical pathyway) evolved prior to photosystem II and in some species of cyanobacteria, it is the only present photophosphorylation pathway for the creation of ATP. Think of this contextually- what is the purpose of photosystem I? To produce ATP. What is the purpose of photosystem II? To produce ATP and also to provide protons for the reduction of carbon chains to glyceraldehyde-3-phosphate. In primitive prokaryotes, the environment simply was not selective for a pathway that provided for an exceedingly complex food creation, energy storage mechanism. Of course, as selective factors changed, so did the pathways and, thus, organisms. We see that as multicellularity among algae and other organisms arose, a more efficient energy producing pathway such as photosystem II is seen. In those prokaryotes whos environment never selected for any more advancement of energy producing pathways, photosystem I remains the pathway for energy production.

I hope this has helped.


I'd like clarifications on the following problems:
13. Are spaces allowed? For example,
$ a\neq b, c \neq d$
vs.
$ a\neq b \neq c$
28. It says "complete" graph but we prove it has $ \leq \frac{2}{5}n^2$ vertices--do we ignore the "complete" part?
29. All round trips that a company can offer should have at least 6 cities. What does this mean, exactly? And can a company operate only 1 direction between cities, and the other company the other direction?
37. An counterexample is any prism with bases black. There are n/2 common sides of 2 white-colored faces, not n-2. Is the problem supposed to say n/2? (seems a tad easy)

28. Works very well if you ignore it being complete.
29. A restatement in graph theory terms: A graph with $ n\geq 5$ vertices has edges colored with 2 colors. All monochromatic cycles contain at least 6 vertices. Prove the graph has no more than $ \frac{n^2}{3}$ edges.

13. No spaces are not allowed. It should be just one line of text and imagine
each space as ``enter''. So you should have
$ a \neq b \neq c \neq d \neq a \neq c .....$

28.      Ignore ``complete'', you just have a graph on $ n$ vertices.

29. Restatement: Let $ G$ be a graph with $ n$ vertices, $ n \geq 5$. The edges of a graph are colored in
two colors such that there are no monochromatic cycles of length $ 3, 4$, and $ 5$.
Prove that there are no more than $ n^2/3$ edges in the graph.

37. Prove that the number of common sides of two
white-colored faces of the polyhedron is at least $ n\minus{}2$ or

Prove that the number of edges with
white-colored faces on both sides is at least $ n\minus{}2$

 An counterexample is any prism with bases black. There are n/2 common sides of 2 white-colored faces, not n-2. Is the problem supposed to say n/2? (seems a tad easy):

A prism has $ n$ faces, two of the are black, you are remained with $ n\minus{}2$ white faces
having in common $ n\minus{}2$ white edges. So everything seems ok.


Please make astab at this not so hard question.

Do you want to discuss this now already? 9 months or something like that before IMO? :huh:

Maybe (of course!  :lol: ) he's opening a forum to discuss what problems could be considered to be coming in IMO 2006! Well, maybe we should spend more time preparing for those problems rather than speculating about them!  :D

I know, I know. Well, let's lock this topic, I'll unlock it two months before IMO starts or something like that. :D This is really too early for this.


modular arithmetic
number theory unsolved
number theory

Prove that $\chi_{D}(k)=-\chi_{D}(k+D/2)$, for $D \equiv 0 \pmod 4$ and $\chi_{D}$ a Dirichlet character in $\mathbb{Z}_{D}$.

Also, which are the $D$'s such that this remains true?

This doesn't seem to true... I think you can only get $|\chi_{D}(k)| = |\chi_{D}(k+D/2)|$.

The definition of this character is:

$\chi_{D}(p)=(\frac{D}{p})$, (Legendre symbol) for $p$ prime, and $\chi_{D}(2)=0$, for $D \equiv 0 \pmod 4$. I've checked it for some $D$'s and it works.

Yeah, you're right, the source is totally wrong, then.

And with the hp. that $\mu(D/4)\ne 0$ and $D/4 \equiv 2,3 \pmod 4$ ?


geometry
circumcircle
parallelogram
geometry unsolved

$ P$ is a point in $ \triangle ABC$, $ PD\perp BC$ at $ D$, similarly define $ E,F$. $ Q$ is another point in $ \triangle ABC$ such that $ \angle BAQ\equal{}\angle CAP$, $ \angle ABQ\equal{}\angle CBP$, and $ Q$ is the orthocenter of $ \triangle BFD$

Prove that: $ \angle FED\equal{}90^{\circ}$

know lemma: the pedal triangle of a point P and the pedal triangle of its isogonal conjugate P' have the same circumcircle with center of the midpoint of PP'.

Q and P are isogonal conjugate. We have $ PD \parallel AQ$ and $ PF \parallel DQ$, so AQDP is a parallelogram and so for the lemma the circumcenter of DEF is the midpoint of PQ that stay on AD, so FE is a diameter and $ DEF \equal{} \frac{\pi}{2}$

in higher case of problem,the feet of prependicular from a point $ P$ to the sides of the triangle,and the feet of prependicular from its isogonal conjugate $ Q$,to the sides,make $ 6$ points which are concyclic by midpoint of $ PQ$,as circumcenter.
(in special case if we choose $ P$ and $ Q$ as orthocenter and circumcenter we will have 9_point circle)
with these properties it is clear that $ \angle FED\equal{}90^{\circ}$

Thanks [u][b]¬[ƒ(Gabriel)³²¹º]¼ [/b][/u]and [u][b]Ashegh[/b][/u]. Your solution are nice!  :P


Whoa..are we adding ARML problems to the Contest Directory, because that would be really cool...

Anyways, back to the problem...

Use long division, and the answer is $9-\frac{5 \cdot 2^{29}}{3^{29}+2^{29}}$

[quote="Iversonfan2005"]Whoa..are we adding ARML problems to the Contest Directory, because that would be really cool...[/quote] Unfortunately, no :( [quote="Iversonfan2005"]Use long division, and the answer is $9-\frac{5 \cdot 2^{29}}{3^{29}+2^{29}}$[/quote] But that's not the answer.

oh wow, completely missed the floor function (and yet it was the name of the topic ;) ), the answer is $\boxed{8}$ then.

[quote="maokid7"]could u explain how you would do long division w/o expanding stuff out.
i think i know but dont want to chance being wrong.  :?[/quote]

Treat them as polynomials.  ;)

I remember doing this at one of our ARML practices.  I got the correct expression, but for some reason I thought the floor was $9$.   :blush:


[quote="kalantzis"]Έστω οξυγώνιο τρίγωνο ΑΒΓ και Δ,Ε,Ζ οι προβολές των Α,Β,Γ στις ΒΓ,ΓΑ,ΑΒ αντίστοιχα. Φέρνουμε απ'τα Α,Β,Γ ευθείες κάθετες στις ΕΖ,ΖΔ,ΔΕ. Ν.δ.ο

 1)Οι ευθείες αυτές συντρέχουν
 2)Το σημείο τομής είναι το περίκεντρο του ΑΒΓ[/quote]

To περίκεντρο ειναι το ισογώνιο συζυγές του ορθοκέντρου οεδ!

1) Τριγoγωνομετρικός Ceva αφού $ \angle{AZE} \equal{} ACB$ κι αντίστοιχα για τα άλλα.
2) Το σημείο τομής θα είναι το ισογώνιο συζηγές του ορθοκέντρου κι άρα θα' ναι το περίκεντρο (γνωστόν).

Πείτε αν θέλετε περαιτέρω εξήγηση για τα παραπάνω.

[i]Edit: Μολις είδα ότι ο Νίκος με πρόλαβε.... :P[/i]

[quote="bilot4"]1) Τριγoγωνομετρικός Ceva αφού $ \angle{AZE} \equal{} ACB$ κι αντίστοιχα για τα άλλα.

[/quote]

epieikos aparadektos! eutuxos omos to deutero se sozei!

[quote="bilot4"]Lol :P  Δεν έχεις κι άδικο... Κατά μια ευρύτερη έννοια πάντως αυτό είναι η απόδειξη του ότι αν 3 ευθείες συντρέχουν, θα συντρέχουν και οι ισογώνιές τους :)  (προσπαθώ να δικιολογήσω τον εαυτό μου :P )[/quote]

w8....den ksereis allh apodeiksi tou theorimatos autou???poses fores sou exo pei re tin pio omorfi sunthetiki apodeiksi?

Ρε παιδιά έλεος ! Τι ισογώγια και trigonometrika Ceva του λέτε του παιδιού ... Έστω ότι η κάθετη από το Α τέμνει την ΖΕ στο S .
Tότε $ \angle{BAS}\equal{}90\minus{}\angle{AEZ}\equal{}90\minus{}B\equal{}\angle{BAO}$  επομένως τα $ A,S,O$ συνευθειακά . Όμοια και για τα άλλα και τέλος  :P

[quote="silouan"]Ρε παιδιά έλεος ! Τι ισογώγια και trigonometrika Ceva του λέτε του παιδιού ... Έστω ότι η κάθετη από το Α τέμνει την ΖΕ στο S .
Tότε $ \angle{BAS} \equal{} 90 \minus{} \angle{AEZ} \equal{} 90 \minus{} B \equal{} \angle{BAO}$  επομένως τα $ A,S,O$ συνευθειακά . Όμοια και για τα άλλα και τέλος  :P[/quote]

dld $ \angle{BAS}\equal{} \angle{BAO}$ ara isogonies??????re sil tin apodeiksi grafeis?tespa kala kaneis ..gt o kalantzis me to pou akouei isogonies isos na borei na kanei tin apodeiksi monos tou alla kapoios allos pou den kserei ti shmainei auto leei ti pipes lene toutoi do. exeis dikio!

[quote="r_boris"]Επίσης καλό είναι να φέρουμε τις εφαπτόμενες του περιγεγραμμένου κύκλου στα Α,Β,Γ[/quote]
Το κλασσικό θεώρημα στις [b]αντιπαράλληλες ευθείες[/b].

[b]Κάθε κύκλος χορδής $ BC,$ τέμνει πάντοτε τις πλευρές $ AC,\ AB$ στα σημεία $ E,\ Z$ αντιστοίχως, έτσι ώστε $ EZ\parallel AA',$ όπου $ AA'$ είναι η εφαπτομένη του περίκυκλου $ (O)$ του $ \bigtriangleup ABC$ στο $ A$[/b].

$ ($ $ \angle CAA' \equal{} \angle B \equal{} \angle ZEA$ $ \Longrightarrow$ $ EZ\parallel AA'$ $ \Longrightarrow$ $ AO\perp EZ$ $ ).$

Κώστας Βήττας.

[quote="Nick Rapanos"]
w8....den ksereis allh apodeiksi tou theorimatos autou???poses fores sou exo pei re tin pio omorfi sunthetiki apodeiksi?[/quote]

Ρε Nick ξενχνιέμαι :blush:  Ποια ακριβώς συνθετική απόδειξη εννοείς?...Εγώ θυμάμαι την άλλη για τη συμμετροδιάμεσο :)  Αυτή χρησιμοποιείς κι εδώ?

[quote="r_boris"][quote="r_boris"]Επίσης καλό είναι να φέρουμε τις εφαπτόμενες του περιγεγραμμένου κύκλου στα Α,Β,Γ[/quote]
Ν θυμάμαι καλά(?) θεώρημα NAGEL δεν λέγεται Κώστα?[/quote]
Ροδόλφε έχεις δίκιο, η εκφώνηση όπως έχει δοθεί και αφορά στα ίχνη $ E,\ Z$ των αντίστοιχων υψών επί των πλευρών $ AC,\ AB$ αντιστοίχως, σχετίζεται ως άμεση εφαρμογή του, με το [b]θεώρημα του Nagel[/b], όπως αναφέρεται στη βιβλιογραφία (ΑΣΚΗΣΕΙΣ ΓΕΩΜΕΤΡΙΑΣ F.G.M. (Ιησουϊτών), θεώρημα 127, σελίδα 299, εκδόσεις Α. ΚΑΡΑΒΙΑ, Αθήνα 1952).

$ \bullet$  Η ακτίνα του περιγεγραμμένου κύκλου του $ \bigtriangleup ABC$ δια της κορυφής $ A,$ είναι κάθετη επί την ευθεία $ EZ.$

Στη σελίδα 297 του ίδιου βιβλίου υπάρχει το θεώρημα 124, που αναφέρεται στη γενική περίπτωση όπου τα σημεία $ E,\ Z,$ επί των $ AC,\ AB,$ είναι τα σημεία τομής τους από τυχαίο κύκλο με χορδή $ BC$ και γι' αυτό αναφέρθηκα σ' αυτό, αφού το [b]θεώρημα του Nagel[/b], είναι ειδική περίπτωση αυτού του θεωρήματος.

$ \bullet$  Η ευθεία $ EZ$ είναι πάντοτε παράλληλη προς την εφαπτομένη του περιγεγραμμένου κύκλου του $ \bigtriangleup ABC$ δια της κορυφής $ A$ και άρα είναι κάθετη επί την ακτίνα $ OA.$

Η απόδειξη και στις δύο περιπτώσεις είναι ίδια και η ευθεία $ EZ$ ονομάζεται [b]αντιπαράλληλη ευθεία[/b] της ευθείας $ BC,$ ως προς τη γωνία $ \angle A$ (ως προς τις ευθείες $ AB,\ AC,$ της γωνίας $ \angle A$ ).

Κώστας Βήττας.


How do you think when taking the AMC10/12, AIME, or USAMO?  Do you try to be calm and relaxed and do the problems like you normally would or do you try to use the pressure to make you concentrate harder?

It really depends on the person. I have a hard time calming myself down, but I find that I have to - I can't work if I'm nervous.

i try to be calm and try to make it as close as practice
i really reallly fail when im under pressure

also, i need to convince  myself that i can solve the problems else i stress over it and dont try on the ones that seem too hard + plus i think a lot slower.

I do bad under pressure too. I try not to think too much about after the test, which makes me nervous. I try to convince myself that it isn't important and any outcome is good.

Truffles, I think your pondering of what a good mindset isn't very helpful to you. You shouldn't think of the real test as anything different than your practices if you want to do as well as you do then.

It varies with me. Sometimes I do much better under pressure, but sometimes it's completely the opposite. I guess I just go with whatever my attitude is at the time.

I'm usually extremely nervous before a math competition, but I calm down pretty much immediately when I actually start. Unfortunately, I often get extremely rushed and pressured at the end, if I don't think I have enough time.

I only work well when I'm either really calm, or extremely hyped up on adrenaline. So if I'm already nervous, I try to increase the pressure, and if I'm feeling okay, I try to calm down. That's just me, though.

I try to run at least a mile before any of my tests, so that my body uses up it's adrenaline.  It helps me stay relaxed during my tests.

:rotfl: cool  :)

Yeah, basically what everyone else said. It depends on the person, so you will need to judge yourself. In general, keeping it close to practice is good.

I dislike pressure, but it tends not to do much to my scores. I  :love:  the MathCounts countdowning atmosphere though.


[quote="Nora.91"]Let $ p(x)$ be a polynomial such that when divided by $ (x \minus{} 1)$ it leaves the remainder [b]2[/b] and when divided by $ (x \minus{} 2)$ it leaves the remainder [b]1[/b]. What is the remainder when it is divided by $ (x \minus{} 1)(x \minus{} 2)$ ?

[hide="Click"]
I got the answer as $ 3 \minus{} x$ , is that correct ?
[/hide][/quote]
That's correct.

$ \begin{cases}a(1)\plus{}b\equal{}2 \\ a(2)\plus{}b\equal{}1 \end{cases}$ gives $ (\minus{}x\plus{}3)$ as the remainder.

Thanks, stephencheng.

I did it as   $ p(x) \equal{} q(x)(x\minus{}1)(x\minus{}2) \plus{} 3\minus{}x$.

The classic very easy way for such questions is(just a few words for those who didnt understand it):
$ P(x) \equal{} (x \minus{} 1)(x \minus{} 2) \cdot q(x) \plus{} ax \plus{} b \Leftrightarrow P(1) \equal{} a \plus{} b \Leftrightarrow a \plus{} b \equal{} 2$ $ \boxed{1}$
$ P(x) \equal{} (x \minus{} 1)(x \minus{} 2) \cdot q(x) \plus{} ax \plus{} b \Leftrightarrow P(2) \equal{} 2a \plus{} b \Leftrightarrow 2a \plus{} b \equal{} 1$ $ \boxed{2}$
So solving the system of $ \boxed{1},\boxed{2}$ we taking the solutions...

y i calculated -1 as my answer?

by using elimination method, i calculated that p(x)=-2 and x=0..
so, p(x)/(x-2)(x-1)=-1

hello, we have $ p(x)\equal{}p_3(x)(x\minus{}1)(x\minus{}2)\minus{}x\plus{}3$.
Sonnhard.


4. Rose fills each of the rectangular regions of her rectangular flower bed with a
different type of flower. The lengths, in feet, of the rectangular regions in her
flower bed are as shown in the figure. She plants one flower per square foot in
each region. Asters cost $ \$1$ each, begonias $ \$1.50$ each, cannas $ \$2$ each, dahlias $ \$2.50$ each, and Easter lilies $ \$3$ each. What is the least possible cost, in dollars, for her garden?

$ (A) 108 \qquad (B) 115 \qquad (C) 132 \qquad (D) 144 \qquad (E) 156$

The areas of the different regions in her garden are 20, 6, 21, 15, and 4.
[hide]To minimize the cost, we must put the most expensive plants in the smallest region. You would put easter lilies in the 4 sq. ft. area, the dahlias in the 6 sq. ft. area, the cannas in the 15, the begonias in the 20, and asters in the 21. The total cost is:
Easter lilies:12
Dahlias:15
Cannas:30
Begonias:30
Asters:21
for a total of [b]108 dollars, [size=150]A[/size][/b][/hide]


inequalities
combinatorial geometry
analytic geometry
geometry

Assume there are $ n\ge3$ points in the plane, Prove that there exist three points $ A,B,C$ satisfying $ 1\le\frac{AB}{AC}\le\frac{n\plus{}1}{n\minus{}1}.$

Could you help me please?Although I have tried for many days,I still cannot solve this problem.

Bump. Such a nice problem, yet remain unsolved for 2 years.

I've got some raw idea. Take a point $O$ on the convex hull, and place them on the cartesian plane such that $O$ is the origin and each point has a nonnegative abscissa. Label the other $n-1$ points $A_1,A_2,\ldots,A_{n-1}$ such that the distances from $O$ is increasing. In my imagination, $A_{n-1}$ is so far away from the other points, so something like $\frac{A_{n-1}A_0}{A_{n-1}A_1}$ could work. Unfortunately, $\left(\frac{n+1}{n-1}\right)^n$ isn't that large, in fact it converges to $e^2$. Fortunately, we now know that the points shouldn't be so far away apart.

[quote="jgnr"]Label the other $n-1$ points $A_1,A_2,\ldots,A_{n-1}$ such that the distances from $O$ is increasing. In my imagination, $A_{n-1}$ is so far away from the other points, so something like $\frac{A_{n-1}A_0}{A_{n-1}A_1}$ could work.[/quote]
I think this is a good approach, but it might be cleaner to take $A_0A_{n-1}$ as the overall maximal distance (i.e. without restricting $A_0$ to be a point on the convex hull). Let $k=\frac{n+1}{n-1}$ and $M=A_0A_{n-1}$.

To gain intuition, it helps a lot to find a clean solution when all the points are collinear. In particular, for odd $n$, simply considering $A_iA_{i+1}$ minimal works, but this is messy for even $n$ and rather ineffective/nonrestrictive for the original problem. Another natural approach is to go by contradiction; then $\frac{A_0A_{i+1}}{A_0A_i}\ge k\implies \frac{A_iA_{i+1}}{A_0A_i}\ge k-1 = \frac{2}{n-1}$. If we WLOG assume $A_0A_m\ge A_0A_{n-1}/2$ where $m=\lceil{(n-1)/2}\rceil$, then $\frac{A_0A_m}{A_{n-1}A_m} \ge k\implies A_0A_m\ge M\frac{k}{k+1} = M\frac{n+1}{2n}$. Summing up $A_iA_{i+1} \ge (k-1)A_0A_i\ge (k-1)A_0A_m$ for $i\ge m$ in addition to $A_0A_m\ge A_0A_m$ yields
\[ M \ge [1+(n-1-m)(k-1)]A_0A_m \ge [1+\lfloor{\frac{n-1}{2}}\rfloor \frac{2}{n-1}] M\frac{n+1}{2n} > M, \]which is absurd.

For the original problem, the same thing works, except we WLOG $A_0A_m\ge A_mA_{n-1}$ (i.e. $A_m$ to the right of the perpendicular bisector of $A_0A_{n-1}$), use $\frac{A_0A_m}{M-A_0A_m} \ge \frac{A_0A_m}{A_{n-1}A_m} \ge k$ (from the triangle inequality) to get a lower bound on $A_0A_m$, and multiply the $\frac{A_0A_{i+1}}{A_0A_i} \ge k$ to get $\frac{M}{A_0A_m} \ge k^{n-1-m} \ge 1+(k-1)(n-1-m)$ to get the final inequality. Of course, we can replace $\frac{n+1}{n-1}$ with the unique positive solution to $k^{\lfloor{(n+1)/2}\rfloor} = k+1$.

Suppose not. Consider two points $X$ and $Y$ such that $XY=\max$ and WLOG $XY=1$. Label the remaining points in two ways: $A_1,A_2,\dots,A_{n-2}$ and $B_1,B_2,\dots,B_{n-2}$ such that $XA_1 \geq XA_2 \geq \dots \geq XA_{n-2}$ and $YB_1 \geq YB_2 \geq \dots \geq YB_{n-2}$. Obviously, $XA_k,YB_k<\left(\dfrac{n-1}{n+1}\right)^k$
Claim: there is point $Z=A_i=B_j$ such that $i \geq \left\lfloor \dfrac{n}{2} \right\rfloor$ and $j \geq \left\lfloor \dfrac{n-1}{2} \right\rfloor$.
Proof: since $\left\lfloor \dfrac{n}{2} \right\rfloor+\left\lfloor \dfrac{n-1}{2} \right\rfloor=n-1$, points $A_i$, where $i \in \left[\left\lfloor \dfrac{n}{2} \right\rfloor,n-2\right]$ cannot be covered by points $B_j$, where $j \in \left[1,\left\lfloor \dfrac{n-1}{2} \right\rfloor-1\right]$. $\square$
Then by triangle inequality $1=XY \leq ZX+ZY<\left(\dfrac{n-1}{n+1}\right)^{\left\lfloor \frac{n}{2} \right\rfloor}+\left(\dfrac{n-1}{n+1}\right)^{\left\lfloor \frac{n-1}{2} \right\rfloor}$, which doesn’t hold for $n\geq 3$ (for small $n$, check by hands; for larger $n$, replace $\left\lfloor\dfrac{k}{2}\right\rfloor$ with $\dfrac{k-1}{2}$ and check by derivative that RHS is decreasing). $\blacksquare$

Beautiful result.

Suppose we have a set of $n$ points not satisfying the condition. Take the longest segment, $P_1P_2,$ assume WLOG it is $1.$ Let the distances from the other $n-2$ points to $P_1$ be $a_1 > a_2 >  \dots  >a_{n-2}.$ Let the distances from the other $n-2$ points to $P_2$ be $b_1 > b_2 >  \dots  > b_{n-2}.$ We have the property $a_k, b_k < \left( \frac{n-1}{n+1} \right)^{k}.$

Case 1, $n = 2m$ for an integer $m > 1.$ We must have a point $P$ whose distances to $P_1$ and $P_2$ are strictly less than $\left( \frac{n-1}{n+1} \right)^{m}$ and $\left( \frac{n-1}{n+1} \right)^{m-1}$ respectively. Otherwise, the points with distances $a_m, a_{m-1}, \dots a_{2m-2}$ from $P_1$ must also be points with distances $b_1, b_2, \dots b_{m-2}$ to $P_2,$ but this is impossible since $m-1 > m-2.$ It's not hard to see $\left( \frac{n-1}{n+1} \right)^{m} + \left( \frac{n-1}{n+1} \right)^{m-1} \le 1$ for $m \ge 2$ through calculus techniques violating the Triangle Inequality.

Case 2, $n = 2m+1$ for an integer $m \ge 1.$ We must have a point $P$ whose distances to $P_1$ and $P_2$ are both strictly less than $\left( \frac{n-1}{n+1} \right)^{m}.$ Otherwise, the points with distances $a_m, a_{m-1}, \dots a_{2m-1}$ from $P_1$ must also be points with distances $b_1, b_2, \dots b_{m-1}$ to $P_2,$ but this is impossible since $m > m-1.$ It's not hard to see $2 \left( \frac{n-1}{n+1} \right)^{m} \le 1$ for $m \ge 1$ through calculus techniques violating the Triangle Inequality.


LotR
The Best movie ever
Lord of the Rings

How many people here are Tolkien fans? I've read the trilogy, the Hobbit and the Silmarillion and have some friends who are busily studying Elvish. =)

Me too, I've read LotR and The Hobbit, but not the Silmarillion.
How about a poll?

Well either it could be
"Are you a Tolkien fan?" Yes or no
or
"Which books written by Tolkien have you read?" LotR, The Hobbit, Silmarillion, or the combination of the three.
It could even be about the movie. (Which LoTR movie did you see and where?)

Speaking of the movie...I didn't see the second one...
Books tend to be better than the movies that try to adapt them. Tis my opinion.

ah. well youll love the two towers movie.

It's not bad. Ir's not like the HP movie, that s*****. (I'm not sure if s*** is a bad word or not, but just to make sure.)

well, TTT did have a somewhat.. excessive... scene at Helm's Deep... my opinion anyhow. Yes, it is still infinitely better than HP.
By the way, I am obsessed with LoTR. I tried to learn Elvish AND swordfighting. Heh.

Well fencing might come in handy, but Elvish...perhaps when inter-galactic travel becomes something we can afford :)

Swordfighting...I want to learn swordfighting...not because of LoTR, though =P...

Whaaaat?  "Sucks" is not a bad word.  If you asterisk it out, it seems like one though...

Harry Potter [i]was[/i] a terrible movie nonetheless.

It wasn't exactly 'fencing' so much as 'swordfighting,' as in 'watch the movie over a couple hundred times in slow motion until you can copy all the moves exactly with this samurai sword you bought from eBay and make your parents really really mad'...

This was immediately after the first movie came out. I was eleven or twelve then, and a true loser. I'm not allowed to touch that eBay sword anymore; it lies buried and forgotten under a heap of water bottles.

Hehe I love the LOTR books.  I stayed home a day from school so I can read Return of the King.  I am crazy I guess.

I tend to bring books to school - I've pretty much mastered the art of navigating the school without looking up from my book...

I like Tolkien - mainly because of the descriptiveness. I like stories that involve an entirely different world from ours today, plenty of plot twists and some action. Which is why I like swordfighting novels. =)

[quote=gnidlaps]you def should they are amazing[/quote]

I just don't have any time recently. I have so much school work, that I probably shouldn't even spend as much time on AoPS as I do.

I only like the hobbit.
The other books start getting confusing to me with my smol brain.

[quote=AlienGirl05][quote=larkwhisker]Lord of the Rings is really good but the Rings of Power is just liberal media propaganda.[/quote]

I'm sorry, please elaborate how that would work.[/quote]

Yeah lotr is one of the best books out there.

The Silmarillion and the Unfinished Tales are really good.

The Silmarrilion is the history of the first age (and some of the second) and basically the story of Middle Earth before Lotr. By the way, I am writing a new sequel to Tolkien's world based on the unfinished tales.

Honestly they’re all pretty good but the return of the king movie was just hours of people getting their necks stabbed out so that pushes that to number one :/

i am reading hobbit rn it pretty good haven't finished it tho

The LoTR movies were my favourite movies of all time, I also had really liked (not much anymore) the hobbit ones, I know a lot about LoTR because I’m pretty passionate about it but I had never actually read the books. Recently though I read the hobbit and I thought it was good, then ~4 days ago I got the LoTR books, currently I’m 250 pages into them and I think they are fantastic (way better than the movies (which are my favourite movies ever)) the only criticism I have of the books and it’s not really much of a criticism is Tom Bobadill. I felt like Toms section dragged on a bit (and this is coming from someone who thoroughly enjoyed the first 100 pages of just shire stuff) but overall the books and movies are great and I would highly recommend them. I think my favourite though (based on the movies) is either the fellowship of the ring, or return of the king. I can’t comment on the Sillmerilian yet because I haven’t read it yet (though I intend to after I finish RoTK) but it also seems pretty good.

(Also the original thread was started in 2003, that’s old)

[hide=Post #60 by tigeryong][url=artofproblemsolving.com/community/user/482382][b]tigeryong[/b][/url] · March 20, 2024 at 8:55 AM [url=artofproblemsolving.com/community/p30217532](view)[/url][color=transparent]helo[/color]
[quote name="EarthyW" url="/community/p30213009"]
bro this thread is so old
[/quote]

*Sauron, the Elves, and the Wizards have left the chat*

-----------
[color=#5b7083][aops]x[/aops] 60[color=transparent]hellloolo[/color] [aops]Y[/aops] 0 [color=transparent]hellloolo[/color] [/hide]
Still though, like, thats before I was born. Crazy. Also why does the two towers only have one vote thats not mine *tears*

I personally love Tolkien. I've read the hobbit twice and the Lord of the Rings and the Silmarillion once along with watching the LoTR movies and a gazillion lore videos. My favorite of the books would either be the SiImarillion or the Fellowship of the Ring.


If anybody gets the admit card, please inform....

Since I did not recieve the acknowledgement card although it seems my application form is received, I guess the same could happen abt my admit card.... :(  :(

Same here. My application form has been recieved. We handed it in person. Don't worry I haven't got it either and I live pretty close to IIT-M. :D

Same here.
Nor have i got my jee admit card.

I thought this thread was for ppl to announce their getting of the admit card, not announce their not gettin..
:P:P

I suppose if I apply a NOT operator throughout the thread, it will amount to us getting. Because NOT(NOT) = TRUE>

this is to keep the thread ahead of others....

attention seeking..... :(

you've got it?  :huh:  No one has got it here so far  :maybe:
N Soumya why r u anxious abt the iit jee admit card?  :D

[quote="VARUNARASU"][quote="Euclidean Geometer"]Yeah we ve all got it in Bangalore i guess...
or atleast i ve got it :D
Good luck[/quote]
i dunno how u got it but i havent got it as yet. perhaps they thought they should start off by giving it to the iit toppers. :D[/quote]

:D
when did u get it? recently only or long back?  :maybe:

LOL! I think you are referring to the acknowledgement card and not the admit card?

Sir, I know i am not AS SMART as u but i know da diff b/w an admit card and an acknowledgement card. Got it TODAY afternoon :D

ofc 2 genii are debating so others flee out  :rotfl: Yes toppers are getting it first n Cyber Shre got it today?  :P   :rotfl:

[quote="VARUNARASU"][quote="Euclidean Geometer"]Yeah we ve all got it in Bangalore i guess...
or atleast i ve got it :D
Good luck[/quote]
i dunno how u got it but i havent got it as yet. perhaps they thought they should start off by giving it to the iit toppers. :D[/quote]
first i thot u were jokin varun but now dat even u've got (also suhas keshav etc..) does make me think u r right
infact i must be  d only banglorean not to've go  :rotfl:  :rotfl:
those iit ppl dont even want me to write exam leave alone givin admission :rotfl:

rock n chappli the kattans in the same place?  :rotfl:   :D

How ironical. Chappli and Rock are writing in Adyar. I'm writing in MVM.  :wallbash:  :bomb:  :censored:

I wish I could actually say something to that. I am writing in ANNA NAGAR>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Highly sensitive of the chaps at IIT, to give centres by the farthest distance from home, AND YOU DONT EVEN SAY ANYTHING HERE BABY!!

jus got it  :)
my centre is mgr janaki college, which is like walking distance from my house!  :rotfl:
so sucks to you, shreyas n shruti :D

where is gokul's centre?  :D
Sabarimalai?  :D  :D

he hasnt got it yet.. but it'll be either sabarimala or japan :D

shre i am sorry to say this but to add agony to pain a saddening news has alarmed us !!!! :(
karthik ram the man who shouts out the answers even before the exams are over and karthik sriram the RMO specialist have placed us in their hit list on IIT JEE day they are writing in our centre da Alas GOD SAVE THE QUEEN! AMEN! :maybe:

:cursing:   Yeah, yeah. Sucks to us indeed

At least you guys have someone in your centre whom you know. I am stuck at SBOA, and lunch time is going to SUCK BIG TIME :(  :wallbash_red:

[quote="shruthibaskaran"]:cursing:   Yeah, yeah. Sucks to us indeed

At least you guys have someone in your centre whom you know. I am stuck at SBOA, and lunch time is going to SUCK BIG TIME [/quote]

you might meet up with someone you know considering the no. of people you knw n all  :D  So dont lose hope! I reckon you might meet with one of the n chappli's where $ lim_{n \rightarrow \infty}$  :rotfl:   :P

Ahem. If only that was meant to be a compliment, I might say thanks, but to your good health, I suggest you remove that post mistah!

Oh noooo i didnt mean it as u think but you have thrown a new dimension into the matter  :P   :rotfl:   :D

otw there would have been a hint of subu sarcasm there  :P   :rotfl:   :D

[quote="smokinjoe"]me DAV..quite close[/quote]

dei you gokul ah??? :o  :D


trigonometry algebra function domain calculus derivative AMC

is this true? it is probably well know if it is known, but could somebody prove it anyway?

\[\frac{3\sqrt3}{4}\le\sin^3A+\sin^3B+\sin^3C\le2\]

with $A,B,C$ being the angles of a triangle

Actually, we have

\[
0 < \sin^3(A) + \sin^3(B) + \sin^3(C) < 2
\]

The lower bound is obvious - take two small angles and a large obtuse angle. We seek the upper bound.

First, observe that $f(x) = \sin^3(x)$ has $f'(x) = 3\sin^2(x)\cos(x)$ and $f''(x) = 6\sin(x)\cos^2(x) - 3\sin^3(x) = 3\sin(x)\left(2\cos^2(x)-\sin^2(x)\right) = 3\sin(x)\left(2-3\sin^2(x)\right)$. Hence, $f$ has inflexion points at $x_0 = \sin^{-1}\left(\sqrt{\frac{2}{3}}\right)$ and $\pi - x_0$, where $f$ is convex over $(0,x_0]$ and $[\pi-x_0,\pi)$, and concave between the points of inflexion. (We restrict the domain to possible angles of a triangle.) We remark that a triangle with an obtuse angle, since that obtuse angle could be decreased while the any acute angle could be increased, [is not optimal.] Therefore, we may assume $A,B,C \in \left(0,\frac{\pi}{2}\right)$. Since there is a single inflexion point in the interval, WLOG $A=B$; hence, we consider only sums of the form

\[
S(A) = f(A) + f(A) + f(2A)
\]

where $0 < A < \frac{\pi}{2}$ since $\sin(x) = \sin(\pi-x)$. We have $S'(A) = 6\sin(2A)\sin(A)\left(1 + 2\cos(A)\cos(2A)\right)$. The bondary limits are $S(0) = 0$ and $S(\pi/2)=2$. The $A$ derivative is 0 at $0, \pi/2$. ($1 + 2\cos(A)\cos(2A)$ is never zero; use $\cos(2A) = 2\cos^2(A)-1$ and check the derivative of $g(x) = 4x^3-2x+1$ over $0 < x < 1$.)

Edit - Added a few missing words.

For the upper bound, see also http://www.mathlinks.ro/Forum/viewtopic.php?t=33518 .

  darij

o yea, that makes sense ... i was doing a usamo problem from 1981 and misscalculated somewhere and had this weird result and just wanted to ask if it is not maybe true after all, but i was stuck thinking of acute angles so one extreme would be (90,90,0) but i just got messed up  :blush:
thanks for help

peeta

ps: couldnt quite follow ur prove the end and could quite understand the proofs of the site darij gave either :(
does anybody has a more simple prove?


In california, the gas prices are like $3 per gallon

how much does your gas cost

post your state and price

Er...it's like 2.70ish in Houston. Texas is huge. I wouldn't dare speak for the whole state. And I know for a fact that it's more expensive than 3 in some parts of Cali.

[quote="jhollenbeck"]in CA where i live gas is like 2.85 in lots of places and on the drive out of yosimite, there is a gas station that is the only one for like 50 miles and it is up to almost 4.50 a gallon! :o[/quote]

holy cow!!!

what gastattion is it?

Here in Longview texas it's sround 2.70 I think... It was up to 2.91 one time. But it went back down to 2.25 then kept on raising back up.

This site is pretty cool: http://www.gasbuddy.com

I think you are a little off on your estimate there, math92.

2.6 ish in sugar land dpends how lucky u get

i've been paying 2.60 and 2.70 for premium gas (regular is 20 cents cheaper). my sports car can only run the good stuff.

howard county, MD
$2.86 three days ago...
but w/ these crazy price fluctuations it could be like $3.50 or $2.00 by now...

[quote="noneoftheabove"]people say that if that regular and premium are the same because u can get rid of the bad stuff that regular has for much cheaper then buying premium every time considering we are already paying enough for gas. is that your car in your avatar[/quote]
yep that's my car but the picture is greatly disproportional to its real image. and my car runs [b]much[/b] better with premium. it has to do with the temperature that the gas detonates in the engine, not the "bad stuff" in regular.

In good ole' Michigan, (in the city where I live) the prices usually range between 2.6 and 2.7

Cheapest is about 2.65 ish up to 2.75 ish

In Port St. Lucie, Florida

Forgot about dollar signs =  latex :/

wow...4 to 5.5

by the way, your average post per day is 3.14!!! :D

now its 3.18 i ruined it u should have told me earlier :D

Hmm gas in Austin is now like 2.70-2.80...I saw one place at 2.99 though.

[quote="mwahahahaha"]jeeebus! $5 a gallon!?
one of these days...a nation-wide riot's gonna break-out[/quote]

I heard it went up to 6 dollars in Atlanta.

[quote="noneoftheabove"]most places are 4 to 5.5 because of hurricane katrina and most of the drills being damagedbut i feel sorry for the people in louisiana although some evacuated to my school in tx.[/quote]

The way I understand it, it's not so much that we aren't drilling enough oil, but we aren't refining it fast enough.  Katrina closed down one of the major North American oil refineries so the surplus of crude oil is only piling up even more.

this disaster just shows how out of date our refining processes are and how dependant we are on oil. alternate energy sources need to be focused on even more.

It's not so much that we have out-of-date refining processes but rather the US in particular has recently (in the last 30 yrs) placed restrictions on refineries for environmental reasons.

Alternate energy sources definitely do need to be looked into and developed more.  There is no question about that.

Okay, I really don't want to drive anymore... jumped 40 cents in a few hours.  :o
Maybe we should alter the poll.

michigan is about 3 bucks
the gas price is supposedly jumping up because the hurricane damaged the power and now the pipeline in new orleans cant run.
my science teacher was in the army, and he says that the army could just haul up a generator the size of a truck, and can power a small city and power the pipeline

what i would like to do is be able to convert hurricanes into electricity by absorbing the power which would let us power california for 6 months which would eliminate disaster and save energy then we wouldnt be dependent on gas and we should get resources such as hydro or solar for cars

well, MD just jumped about a dollar in a day... it was 3.50ish yesterday, blah

the east coast is messed up because of katrina

Now the gas is anywhere from 3.15  to 3.50 :strecher: I don't know when all this will recover. Maybe 2 weeks or so.

It will take longer than two weeks i am guessing about 7 months because when Ivan The Terrible hit the gas prices went up for about 5 months, and because Katrina was so bad and it hit more oil drills because it hit the Gulf which has more oil, than where Ivan hit. The gas prices will be up for a while


Find the least positive integer a such that 2001 divides 55^n+a32^n for some odd integer n

$ 2001\equal{}3 \times 23 \times 29$

Then the question $ \Leftrightarrow \begin{cases} 55^n\plus{}a 32^n\equal{}1^n\plus{}a(\minus{}1)^n\equal{}0(mod \;\; 3) \\
55^n\plus{}a 32^n\equal{}9^n\plus{}a (9)^n\equal{}(a\plus{}1) 9^n\equal{}0(mod \;\; 23) \\
55^n\plus{}a 32^n\equal{}(\minus{}3)^n\plus{}a(3)^n\equal{}(a\minus{}1) 3^n(mod \;\; 29) \end{cases}$
$ \Leftrightarrow \begin{cases} a\equal{}1(mod \;\; 3) \\
a\equal{}\minus{}1(mod \;\; 23) \\
a\equal{}1(mod \;\; 29) \end{cases}$
$ \Leftrightarrow a\equal{}1770(mod \;\; 3 \times 23 \times 29)$

So the answer is $ 1770$.


analytic geometry
graphing lines
slope
algebra
linear equation

I know the formula for finding slope is
$ \frac{y2\minus{} y1}{x2 \minus{}x1}$  but how do you decide what number is $ y2$ and which number is $ y1$?

Let's say the two points are (1, 3) and (4, 9). It doesn't matter which you choose, but one coordinate is (x1, y1) and the second coordinate is (x2, y2). Let's say we choose (4, 9) to represent (x1, y1), then (1, 3) would represent
(x2, y2).

So;

1 = x2
3 = y2
4 = x1
9 = y1

When we plug these values in, we get;

$ \frac{y2 \minus{} y1}{x2 \minus{} x1}$
$ \frac{3 \minus{} 9}{1 \minus{} 4}$
$ \frac{\minus{}6}{\minus{}3}$
$ 2$

Hope that helps.

And just in case you didn't know, you can also find the slope with the formula;

$ \frac{y1 \minus{} y2}{x1 \minus{} x2}$

It doesn't order which you choose.

[quote="game.guy"]
So;

1 = x2
3 = y2
4 = x1
9 = y1
[/quote]
But if we use the formula $ \frac{y1 \minus{}y2}{x1\minus{}x2}$
We find that the slope is $ \frac{6}{1}$ instead of $ \frac{\minus{}6}{\minus{}3}$ which is the slope using the formula  $ \frac{y2\minus{}y1}{x2\minus{}x1}$. Obviously $ \frac{\minus{}6}{\minus{}3}$ and  $ \frac{6}{1}$ are 2 different numbers. Isn't there only supposed to be one slope per linear equation?

No, you get (9-3)/(4-1) = 6/3 = 2. So it works either way. Hope this helps.

This works because $ \frac{y_1\minus{}y_2}{x_1\minus{}x_2} \implies \frac{\minus{}1}{\minus{}1} \times \frac{y_1\minus{}y_2}{x_1\minus{}x_2} \implies \frac{y_2\minus{}y_1}{x_2\minus{}x_1}$.  So it's okay to switch the numbers, as long as $ (x_1,y_1)$ and $ (x_2,y_2)$ stay together.

Well it really doesn't matter for example if i call a point (x,y) and another point (a,b) then i just have to do the y's minus the x's but sure u always start with the same one from the same coordinate for example

(y-b)/(a-x) would be wrong while (y-b)/(x-a) would be right because positive x and y coordinates are from the same point while the coordinates of the negative x and y are from the second point


function
algebra
polynomial
algebra unsolved

Find all functions $f : \mathbb{R}\to\mathbb{R}$ such that $f(1) = 1$ and
\[f\left(f(x)y+\frac{x}{y}\right)=xyf(x^{2}+y^{2}), \]
for all real numbers $x$ and $y$ with $y\not = 0$.

I only get f(x)= 1/x if x not = 0 and f (x)=0 if x = 0 as my answer.

i put x = 0, and yields f(f(0)y)= 0 for all y, which means f(0)=o

then i suppose x not =0 and put f(x)y+x/y=0, which yields f(x)=1/x for x not 0 from the RHS...

I am doing it in a rush so i am not sure of the answer.... but i think my logic is somehow correct....

[quote="singapore1728"] (1/y) f (1+1/y^2)= y f (1+y^2)

[u]so f (x) is monotonically decresing for y < 0 and increasing for y >0[/u]....[/quote]

I don't see why.

--
Patrick

sorry pco, my mind must not be working since I do it hurriedly, so just ignore the quoted line, as they shouldnt in the soltion... they are just my doodling.

so dear N T Tuan, is the answer correct?

[quote="singapore1728"] then i suppose x not =0 and put f(x)y+x/y=0, which yields f(x)=1/x for x not 0 from the RHS...[/quote]

That's wrong again.
$f(x)y+\frac{x}{y}=0$, so $y^{2}=-\frac{x}{f(x)}$ (if $\frac{x}{f(x)}<0$) leads,in RHS, to $f(x^{2}-\frac{x}{f(x)})=0$. But, since you did not show that f is injective, you can't  conclude $x^{2}-\frac{x}{f(x)}=0$.

To demonstrate f is injective would be a strong step.

--
Patrick

$x=a, y=b$ for $a,b\in\mathbb{R}$ gives $f(f(a)b+a/b)=abf(a^{2}+b^{2})$ and $x=a, y=-b$ gives $f(-f(a)b-a/b)=-abf(a^{2}+b^{2})$ i.e. $f(-x)=-f(x)$ for all $x\in\mathbb{R}$

Taking $x=0$ yields to $f(yf(0))=0$. So, there are two cases:
a) $f(x)=0$ for all $x$: $f(x/y)=xy*0 \Leftrightarrow 0=0 \Rightarrow$ possible
b) $0$ is the only root of $f$. (otherwise there would exist $\infty$ roots, what is case a). )
with $x=1$ and $f(1)=1$ you geht $f(y+1/y)=yf(y+1)$

that's how far i got atm^^

Hello Kathi;)

[quote="kathi;)"]$x=a, y=b$ for $a,b\in\mathbb{R}$ gives $f(f(a)b+a/b)=abf(a^{2}+b^{2})$ and $x=a, y=-b$ gives $f(-f(a)b-a/b)=-abf(a^{2}+b^{2})$ i.e. $f(-x)=-f(x)$ for all $x\in\mathbb{R}$[/quote]

No, $f(-x)=-f(x)$ for all $x$ which may be written as f(a)b+a/b for some a and b.

[quote="kathi;)"]
b) $0$ is the only root of $f$. (otherwise there would exist $\infty$ roots, what is case a). )
[/quote]

No, it exist functions having an infinity of "roots" (it's impossible for polynomials, but a lot of functions have this property)

[quote="kathi;)"]...the only function that fulfills $f(f(x)y+x/y)=xyf(x^{2}+y^{2})$ is $f(x)=0$

the problem is the condition $f(1)=1$^^[/quote]

Singapore1728 gave at least one solution : f(x)=1/x for any x different from 0 and f(0)=0.

--
Patrick

yes, i already know one of my mistakes (it was that i couldn't see the difference between $y$ and $y^{2}$...)

but if $f(0)$ would not be $0$, then there would exisit $\infty$ roots, i.e. exactly every $x\in\mathbb{R}$ - contradiction to $f(1)=1$

[quote="pco"]Hello Kathi;)

[quote="kathi;)"]$x=a, y=b$ for $a,b\in\mathbb{R}$ gives $f(f(a)b+a/b)=abf(a^{2}+b^{2})$ and $x=a, y=-b$ gives $f(-f(a)b-a/b)=-abf(a^{2}+b^{2})$ i.e. $f(-x)=-f(x)$ for all $x\in\mathbb{R}$[/quote]

No, $f(-x)=-f(x)$ for all $x$ which may be written as f(a)b+a/b for some a and b.

[/quote]

what's the problem with that?

[quote="kathi;)"]yes, i already know one of my mistakes (it was that i couldn't see the difference between $y$ and $y^{2}$...)
but if $f(0)$ would not be $0$, then [u]there would exisit $\infty$ roots, i.e. exactly every $x\in\mathbb{R}[/u: e1fbf4d891]$ - contradiction to $f(1)=1$[/quote]

No again. It exist a lot of nonzero functions with infinity of roots. For example sin(x). You can not say" f have an infinity of roots" => f=0

[quote="kathi;)"][quote="pco"]
[quote="kathi;)"]$x=a, y=b$ for $a,b\in\mathbb{R}$ gives $f(f(a)b+a/b)=abf(a^{2}+b^{2})$ and $x=a, y=-b$ gives $f(-f(a)b-a/b)=-abf(a^{2}+b^{2})$ i.e. $f(-x)=-f(x)$ for all $x\in\mathbb{R}$[/quote]
No, $f(-x)=-f(x)$ for all $x$ which may be written as f(a)b+a/b for some a and b.
[/quote]
what's the problem with that?[/quote]

I mean that you demonstrate that "if it exist real a and b  such that x=f(a)b+a/b, then f(-x)=-f(x)". It does not mean that f(-x)=-f(x) for any x in R. May be some x can not be written as x=f(a)b+a/b. Imagine, for exemple, that  f is such that af(a)>=1 for any a, then equation (in b) x=f(a)b+a/b have no real solutions for x in (-2,2) and you can't say anything about relations between f(-x) and f(x) in this interval.

--
Patrick

i have the following:

let $f(0)=c$. $x=0$ gives $f(cy)=0,\forall y\neq 0$. $x=c$ gives $f(\frac{c}{y})=cyf(c^{2}+y^{2})=0, \forall y\neq 0$.
so $c=0$ or $f(c^{2}+y^{2})=0, \forall y\neq 0$.

assume that $c\neq 0$. then $f(cy)=0$ for $y\neq 0$ gives $f(c^{2})=0$. combining this with $f(c^{2}+y^{2})=0$ for $y\neq 0$ we get $f$ is constant and $f\equiv 0$. so this is a solution. now we turn our attention to $c=f(0)=0$.

$x=1$ implies $f(y+\frac{1}{y})=yf(y^{2}+1)$. on the other hand, $y=1$ gives $f(x+f(x))=xf(x^{2}+1)$. from these two equations we get $f(x+\frac{1}{x})=f(x+f(x))$ for $x\neq 0$. from this i inspect $f(x)=0$ for $x=0$, otherwise $f(x)=\frac{1}{x}$. just need to show that $f$ is injective...

probably that didn't help.. :blush:

[hide="hmm..."]
We can get $f(0)=0$ because if $f(0)\neq 0$, then we can plug in $x=0,\ y=\frac{1}{f(0)}$ to get $f(1)=0$: a contradiction.

For any nonzero $x$, there exists a nonzero $y$ such that
\[f(x)y+\frac{x}{y}=x^{2}+y^{2}\]
as a cubic equation has at least one real root. Let $c$ be this common value; then we have
\[f(c)=xyf(c)\Rightarrow f(c)(xy-1)=0\]
Now to show that if $f(c)=0$, then $c=0$... :maybe: If we can show this, then we'll be done, since $xy=1$ and $f(x)y+\frac{x}{y}=x^{2}+y^{2}$ implies $f(x)=\frac{1}{x}$.
[/hide]


I didn't even write a single problem down yet but I was wondering if anyone will be interested to take another Mock AMC by me (If I write one). It won't be anytime soon but I was just wondering if anyone will be interested.

It will be like the last one ------- Pretty close to the real AMC-12 level.

Anyone?  :)

it just keeps getting better. i wonder if we can get to mock amc alpha  :P

Sure.

Post is too short, so I'm lengthening it.

Same response as to AMC D...

I'll do it!  :D if no conflict during that time (which was what happened for the last one...)  :(

Sure! It sounds fun and I didn't learn about this til after the Mock AMC D.... :(

If I remember, I'll do it... *watches self forget*. :P

[quote="pkothari13"]Yeah I'm interested as well.  Do you have a rough idea as to when you will administer it?[/quote]

Eh. Hard to say. The "date" for the test really depends on how much time I get. And obviously, I don't know how much I'll get. Not anytime *soon* though.

[quote="agolsme"]will it be before the amc 12 on january 31st( or something like that) ?[/quote]

I'm shooting for before Christmas if possible (but I'm not sure).. Now.. Back to the class..  :D

[quote="Silverfalcon"]Now.. Back to the class..  :D[/quote]

:D Count me in.

i would like to do it, just try and do it on a weekend or on winter break

[quote="zanttrang"]If it's over winter break, I'm in - otherwise, it's a toss-up as to whether my weekend is busy.  Also, if you're interested in somebody to help you proof-read solutions and clean up and typeset your problem set as well as a solution set, let me know - I enjoy doing that sort of stuff.[/quote]

I would be *greatly* appreciated if you can write up the solution. As for problems, you can do the same thing you did on last AMC B I did but that's really upto you (it doesn't really matter much to me).

I'll do my best to write one but right now, I can't guarantee anything. I want to go over as many AMC and AHSME as possible so Mock AMC just have to wait. Sorry guys!  :(


conics
ellipse
calculus
linear algebra
geometry unsolved
geometry

How to translate the equation $ 5x^2\plus{}4xy\plus{}8y^2\equal{}1$ to an ellipse?

Is this from your linear algebra class? Or calculus?

I ask because there are two different methods on normalizing ellipses and hyperbolas.. Or at least I have learned two different ways, in those two classes.


How many of the first 50 numbers have an odd number of factors or exactly 2 factors?

I don't know how to solve it. Please explain it to me. Thanks.

If a number has an odd number of factors, it's a perfect square, and if it has only two then it's prime.

There are 7 perfect squares under 50 and 15 primes under 50, so the answer is 7+15=22.


Prove that for any nonnegative integers $n$ and $m$ that

$\frac{(2n)!(2m)!}{n!m!(n+m)!}$ is always an integer.

Hmm, again?
It's #3 from the IMO 1972. (so certainly posted before)
Just use Legendre's formula.


algebra
polynomial
trigonometry
function
complex numbers

Does $(-32)^{1/5}=2^{5/2}i^{2/5}$?

Is there a simpler way of writing $(-1)^{1/5}$ with imaginary numbers? (trying to get the negative from under the radical)... thanks.

I see my mistake now, thanks.

Doesn't $(2i^{2/5})^5=-32$ not $(-32)^{1/5}$?

So the answer would be $-2$?

Well, yes but...

$-2$ is not the "only" solution to$\sqrt[5]{-32}$ because as we can see, we are taking the 5th root of a number so it should have  a total number of 5 solutions. Of course in this case, $-2$ is a solution of$\sqrt[5]{-32}$... one of a total of five.
Am I Clear....?

This is also true for all the nth roots of m.

It isn't directly, but somehow indirectly supported by the fundamental theorem of algebra
"..................I think........................."

Doesn't the Fund. Theorem of Algebra only involve integer exponents?

[quote="Jhonny Ruiz"]well the way I lerned it was that it stated that any polynomial equation with degree $n$ and complex coeficient has a total of $n$ roots.

I remember not about it talking about integer exponents.

Can someone please correct me if I'm wrong...[/quote]

a polynomial is defined to have integer exponents

So... is $-2$ the only solution of $(-32)^{1/5}=x$? (including compleX)

no it is not the only solution because there has to be a total of 5 solutions so based on that there is also 4 more answers for x.

Think about it
$\sqrt[5]{-32}=x$
$x-\sqrt[5]{-32}=0$

Which i think is a "polynomial" and if you take that to the 5th power you would get another "polynomial" with degree 5 that means that that "polynomial" equation has to have "5" solutions based on the Fundamental theorem of algebra.
We know a real one, because by theorem we have to have a real solution for odd polynomial eqautions but there is still 4 complex ones

Well, couldn't we just raise both sides of the equation by 25 and say there are 25 real and complex solutions of the equation? (infinitely)?

edit: nvm, i forgot about multiplicity. there may be only one distinct solution, but 25 solutions.

[quote="Jhonny Ruiz"]So are you telling me that let's say

$x-27^{1/3}x^{1/2} +2=0$ is not a polynomial?[/quote]

Look here  ;)

[url]http://id.mind.net/~zona/mmts/functionInstitute/polynomialFunctions/definition/definition.html[/url]

Here is another thing to think about. We know that a polynomial with degree n has n solutions, but say we allow $P(x)=x^{\frac{1}{2}}-1$. That cannot have half a solution.

[quote="Jhonny Ruiz"]

Also, for the second problem

$\sqrt[5]{-1}=i^6$[/quote]

 :huh:

$\sqrt[5]{-1} = \cos \frac{k \pi}{5} + i \sin \frac{k \pi}{5}, k = 0, 1, 2, 3, 4$

[quote="Jhonny Ruiz"]Altheman you are right, but take a look at this.
Let's say the folowing equation is not a polynomial.
$\sqrt{x} -1$
Well, let's make it one.

$(\sqrt[4]{x})^2-1=(\sqrt[4]{x}+1)(\sqrt[4]{x}-1)$
Work this out and the answers would be $x=1,x=i^8$[/quote]

It's still not a polynomial.  It has the same solutions as a polynomial, and $i^{8} = 1$ anyway.

Jhonny Ruiz, I think you need to review your material a little...

[quote="ccy"][quote="LordoftheMorons"]${(-32)^{1/5}} = -2$
We cannot get imaginary solutions with an odd root.[/quote]

uh..
$\left(\sqrt[5]{32}\left(\cos\left(\frac{\pi}{5}\right)+\sin\left(\frac{\pi}{5}\right)i\right)\right)^5=-32$[/quote]

Very well, I stand corrected. However, I will state that any imaginary root of a polynomial of an odd degree will be inherently ugly.

here is a distinction that we need to make here

1)

Solve for x $x^5=1$

2)

Find x: $\sqrt[5]{1}=x$

---

These are 2 different problems. The first one has 5 solutions since it is a 5th degree polynomial.

The second one has 1 solution since $f(x)=\sqrt[5]{x}$ is a function. Therefore, there is only one output for 1 input.

[quote="LordoftheMorons"]
Very well, I stand corrected. However, I will state that any imaginary root of a polynomial of an odd degree will be inherently ugly.[/quote]

Only if you insist on representing complex numbers in $\mathbb{Z} [i]$.  :)

Altheman, I agree entirely:  However, in this case I think that $\sqrt[5]{-32}$ was intended to mean "find all five fifth roots of $-32$."

[quote="fireemblem13"][quote="Altheman"] a polynomial is defined to have integer exponents[/quote]
a polynomial has to have whole number exponents, not integer exponents.
$x^{-1}=\frac{1}{x}$
is not a polynomial.[/quote]

A polynomial is a function of the form

$P(x) = \sum_{k=0}^{n} a_k x^k$, where $a_k \in$ some field (so, non-negative integer exponents).  You can have polynomials $\in \mathbb{Z}, \mathbb{R}, \mathbb{C}$, etc.  They're generally taken to be $\in \mathbb{Z}$.

he's right, it is usually defined to be $\in \mathbb{Z}$


Suppose that the points $(-h, y_{0})$, $(0, y_{1})$ and $(h, y_{2})$ are on the graph of $y = ax^{2}+bx+c$.  It can be shown that the area enclosed by the parabola, the x-axis and the
lines $x =-h$ and $x = h$ is: Area = $(\frac{h}{3})(2ah^{2}+6c)$.

[size=150]Show that this area may also be given by the
Area = $(\frac{h}{3})(y_{0}+4y_{1}+y_{2})$.[/size]

[i]Mod edit: Texed up...[/i]

Wow... a calculus-seeming problem without really requiring calculus  :lol:

[hide]Let $f(x) = ax^{2}+bx+c.$

Focusing our efforts on $2ah^{2}+6c$, we have:

$y_{0}= ah^{2}-bh+c$,
$y_{1}= c$,
$y_{2}= ah^{2}+bh+c$,

$\Rightarrow y_{0}+4y_{1}+y_{2}= ah^{2}-bh+c+4c+ah^{2}+bh+c = 2ah^{2}+6 \Rightarrow (h/3)(2ah^{2}+6c) = (h/3)(y_{0}+4y_{1}+y_{2})$

The fact that the given expression is the area isn't even used.[/hide]

You are very smart.  What a great reply.

Thanks!


[quote="GameBot"]Michi's grades for four quarters of school were 83, 87, 93 and 89. Her final exam is counted as $ \frac13$ of her yearly grade, while the other $ \frac23$ of her grade is the average of her grades in each of the four quarters. What grade must Michi obtain on her final exam to get exactly for her yearly grade?[/quote]

The sum of her grades now is $ 352$, for an average of $ 88$.

To get 90 on her yearly grade, she must get $ 91$ on the final test $ \frac{2}{3}x\plus{}\frac{88}{3}\equal{}90 \implies 2x\equal{}182 \implies x\equal{}91$.

The average of 88 is correct. However, the final test score is not 91. Because the other grades count for 2 times as much as the final test, we can say that 88 is 2 below from 90, thus the final test should be $2\cdot2 = 4$ above 90, or $\boxed{94}.$


vector
inequalities
trigonometry
inequalities unsolved

Let  a,b,c  be  positive  real  numbers  such  that $a+b+c = abc$
Find  the  minimum  value  of  the :

   $A = \sqrt{1+\frac{1}{a^{2}}}+\sqrt{1+\frac{1}{b^{2}}}+\sqrt{1+\frac{1}{c^{2}}}$

It smells trigonometric and the solution is very machanical.

mateivld, how your first inequality came?

[quote="gdeskos"]Please post full solutions. I don't think Minkowski works[/quote]
Minkowski is good , offcouse
$A \geq \sqrt{3^{2}+(\frac{1}{a}+\frac{1}{b}+\frac{1}{c})^{2}}\geq \sqrt{3^{2}+3(\frac{1}{ab}+\frac{1}{bc}+\frac{1}{ca})}$
and since a+b+c=abc , we're done

Your solution has been posted by Minh Can.
You should look up other's solution. :wink:


Let $ p(x) \equal{} a_0 \plus{} a_1x \plus{} \cdots \plus{} a_nx^n,a_0a_n \neq 0$ and suppose that $p$ has $n$ real roots. Prove that the number of sign changes in the sequence $ (a_0,\ldots,a_n)$ is precisely the number of positive root of $p$.

[quote="No Reason"]Let $ p(x) \equal{} a_0 \plus{} a_1x \plus{} ... \plus{} a_nx^n,a_0a_n \neq 0$ and suppose that p has n real root.Prove that the number of sign changes in the sequence $ (a_0,..,a_n)$ is precisely the number of positive root of p.[/quote]

Very nice proposition :)

I suppose that "$ a_0a_n\neq 0$" means $ a_0...a_n\neq 0$ or, better, $ a_i\neq 0$ $ \forall i$ (in order to give sense to the expression "sign changes").

1) this is obviously true for $ n\equal{}1$

2) suppose this is true up to $ n\minus{}1$
Let $ f(P)$ be the number of sign changes in the sequence of coefficients of $ P(x)$
Let $ g(P)$ be the number of positive roots of $ P(x)$

Let $ P(x)\equal{}a_0 \plus{} a_1x \plus{} ... \plus{} a_nx^n$ with $ n$ real roots. Wlog say $ a_0>0$ (else replace $ P(x)$ with $ \minus{}P(x)$)
Let $ P'(x)\equal{}a_1 \plus{} 2a_2x \plus{} ... \plus{} na_nx^{n\minus{}1}$

Since $ P(x)$ has $ n$ roots, we know that $ P'(x)$ has $ n\minus{}1$ roots and $ P(x)$ roots and $ P'(x)$ roots are interlaced.
We also have $ f(P')\equal{}g(P')$ (induction rule).

So, since $ P(0)>0$ :
Either $ P'(0)>0$ and $ g(P')\equal{}g(P)$, but then $ a_0>0$ and $ a_1>0$ and so $ f(P)\equal{}f(P')$ and so $ f(P)\equal{}g(P)$
Either $ P'(0)<0$ and $ g(P')\equal{}g(P)\minus{}1$, but then $ a_0>0$ and $ a_1<0$ and so $ f(P)\equal{}f(P')\plus{}1$ and so $ f(P)\equal{}g(P)$
Q.E.D


search
inequalities
induction
graph theory
combinatorics proposed
combinatorics

An [i]animal[/i] with $n$ [i]cells[/i] is a connected figure consisting of $n$ equal-sized cells[1].

A [i]dinosaur[/i] is an animal with at least $2007$ cells. It is said to be [i]primitive[/i] it its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.

(1) Animals are also called [i]polyominoes[/i]. They can be defined inductively. Two cells are [i]adjacent[/i] if they share a complete edge. A single cell is an animal, and given an animal with $n$ cells, one with $n+1$ cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.

A primitive $n$-saur can have at most $4n-3$ cells.

Consider a cross formation consisting of a center cell and four extensions of length $n-1$.  Of any partitioning of this animal, one partition contains the center cell.  The other partitions can have length at most $n-1$, so this animal is $n$-primitive.

Pick an $n$-subanimal out of a primitive $n$-saur that minimizes the number of animals into which the other cells are divided, and consider the remaining cells.  If there are more than $3(n-1)$ of them, and they divide themselves into $3$ or less animals, one of them must have at least $n$ cells, contradiction.  If they divide themselves into $4$ or more animals, these animals must be attached to the $n$-subanimal at at least two distinct cells (since a cell can only have three free edges for $n > 1$), so it is possible to create another $n$-subanimal by combining one of the other animals with it and removing some cells around the location where the others are attached.  This produces an $n$-subanimal such that the other cells are divided into less animals; contradiction.

Another solution (I hope it is correct):
The construction is same.
Now say we have a primitive animal with $ 4n\minus{}2$ cells, that cannot be divided into two animals, each with at least $ n$ cells.
Going downwards from the top of animal, we can divide the animal into rows. Suppose the animal has $ k$ rows, and the $ i$-th row has $ a_{i}$ cells.
If $ n \leq a_{1} \plus{} ... \plus{} a_{i} \leq 3n\minus{}2$ for some value of $ i$, cutting horizontally between the $ i$-th and $ i\plus{}1$-th rows would give two animals, each with at least $ n$ cells. Contradiction.
Thus $ a_{1} \plus{} ... \plus{} a_{i} \leq n\minus{}1$, or $ a_{1} \plus{} ... \plus{} a_{i} \geq 3n\minus{}1$. From this, clearly we have for some value of $ i$ that: $ a_{1} \plus{} ... \plus{} a_{i\minus{}1} \leq n\minus{}1$ and $ a_{1} \plus{} ... \plus{} a_{i} \geq 3n\minus{}1$, so $ a_{i} \geq 2n$ for some $ i$.
Now consider the $ i$-th row. Since it has at least $ 2n$ cells, divide the animal vertically in the middle of this string of horizontal cells. Now we have two animals, each with at least $ n$ cells. Contradiction.

epitomy, do I misunderstand your solution, or is this shape a counterexample to your argument?

[code]X _ X X X
X _ X _ _
X X X X X
_ _ X _ X
X X X _ X[/code]

One of your claims was that splitting between the $ i$th and $ i\plus{}1$th row splits the animal into to two new ones, right? Here, splitting the animal between the 1st and 2nd rows creates three new animals, not two.

Your argument was basically my solution, except that you have to do more than just use rows. I couldn't get it to work without turning the animal into a graph, and then into a tree.

Graph theory was apparently the most natural way to approach this.  In particular, I believe a nice solution I read considered a minimal spanning tree (which appears to be essentially what I did in my solution).

[quote] One of your claims was that splitting between the ith and i+1th row splits the animal into to two new ones, right? Here, splitting the animal between the 1st and 2nd rows creates three new animals, not two. [/quote]
Yes, sorry that is a flaw in my proof.
Could you post your proof using graph theory? I don't understand how to fix my proof.
Also, what is a spanning tree?

Here's a sketch of my proof. We don't get our individual problem scores back, but I estimate based on my total score and my solution quality for each problem that this was scored as a $ 6/7$.

Turn the animal into a graph, then into a tree. Prove or state as well-known that there is a vertex with degree 1, and start there. Mark that vertex 1. Now go along vertices, increasing the number by 1 each time (so 1,2,3...), until you reach a vertex with more than degree 2. Go towards the vertex that is joined to more vertices; i.e. the subgraph created by splitting it off from the vertex you're at now is of the greatest size. For this vertex, count up all of the vertices on the other paths you did not take, and in addition to adding 1, also add the total you just computed.

You can prove that if you ever write down a number in between $ 2008$ and $ n \minus{} 2007$ (where $ n$ is the size of the animal), there is a way to partition the animal into two dinosaurs. (I believe I lost my point from not stating this proof) Then by using the fact that the maximum degree of any vertex is 4, you can prove that a number in this interval must be assumed if $ n > 8025$, and you're done.

[quote="epitomy01"]Also, what is a spanning tree?[/quote]

Search engines are your friend.  Any connected graph $ G$ contains a [i]spanning tree[/i] $ T$, a tree such that $ V(T) \equal{} V(G)$ and $ E(T) \subset E(G)$.  ($ V$ = the set of vertices of, $ E$ = the set of edges of.)

[hide="Solution"].
Consider animals as a graph, with cells as vertices and 2 cells(or vertices) joined by an edge if they share a border. Notice that the maximal degree of any vertex in this graph is $4$. Now we make the graph into a tree (just consider its spanning tree). We will now introduce some notation. Let $v$ be a vertex in a tree, and $v_1, v_2, .. v_k$ be its neighbors,  let $T_i$ be the subtree contation $v_i$ after the deletion of edge connecting $v$ and $v_i$. Then $f(v) = max(|V(T_1)|, \ldots, |V(T_k)|)$.

Lemma: Let $d > 1$ be the maximal degree in a graph. Then there exists $v$ such that $f(v) \le \frac{d}{d-1}(n-1)$.

Proof: Suppose otherwise, that the minimal $f(v)$ is $> \frac{d-1}{d}(n-1)$. Consider the neighbor $v_i$ where this occurs. Since the subtree containing $v$ has at most $\frac{1}{d}(n-1)$ vertices, which means it cannot be the subtree with maximal edge set. so $f(v_i) \le n-(n-f(v)+1) = f(v)-1$, contradicting minimality and showing that there is one with the desired value. The last inequality comes from the fact that the maximal subtree neighboring $v_i$ does not contain the subtree containing $v$ or $v_i$.

Back to the problem, if there is a vertex $v$ in a dinosaur with size $n$ such that $n-f(v) \ge 2007$, then we are done, so we need $n-f(v) \le 2007$ but there exists $v$ such that $f(v) \le \frac{d-1}{d}(n-1)$. So we need $n-\frac{d-1}{d}(n-1) \le 2007 \Rightarrow n-1 \le 2006d \le 2006*4 = 8024$, so $n <= 8025$. To show that this is acheivable, just consider a central cell with 4 arms of length size 2006.
[/hide]

The answer is 4*n-3.Now,for example,pick an animal with center cell and n-1 cells from each direction.Now,lets prove we can partitate 4*n-2.We do this by simple induction on n.For n=1,2 is obvious.Now,we pick a subanimal with 4*n-6 cells(it is obvious we can do this) and from the inductive hypothesis we have that this can be partioned in two subanimals with n-1 cells or more.Now,if both of them have more than n-1,we are done,so we suppose they don't.Now,we add 4 cells.Now,if some of them touches an animal with n-1,we are finished,so suppose not.Now,the subanimal must be adjacent to the bigger subanimal at least at one cell,so if we pick  that cell,it can partitate the bigger subanimal into at most 3 parts an the bigger subanimal now has 3*n-2 cells(cause the 4 we added must form a subanimal with it by assumption),so there exist one with n cells and the rest is a one subanimal,so we are done

Optimal construction is shown above

To show that $4n-2$ doesn't work, put the n-saur onto the coordinate plane and place all the cells as integer coordinates and draw edges between adjacent cells. In this case, a connected graph is a partition and if 2 disjoint subgraphs would represent 2 different partitions.

We say 2 cells are connected if there is a path between them that doesn't go through the origin. Consider the set of cells which are connected to $\{(-1,0), (1,0), (0,1), (0,-1)\}$ (It is possible that a cell is connected to more than one of these, and it is also possible that one of the cells in this set is not actually on the n-saur and thus its connected set has size 0).

By the pigeonhole principle, one of these sets has $n-1$ points. WLOG let that set be the connected points of $(1,0)$. The connected set of $(1,0)$ and the point $(1,0)$ create an n-saur with at least $n$ points. This is because there exists some path from (1,0) to every point in this set and thus every point in this set can get to any other point in this set by going through (1,0), thus creating a connected graph/partition

The rest of the points not in the connected set of $(1,0)$ form a partition because they could not have been adjacent to a point in the connected set of $(1,0)$ or else they would be in that set.

If there are less than $n$ points remaining, then we employ the greedy algorithm on the connected set of $(1,0)$. First, we choose $(1,0)$. And then we choose all points adjacent to $(1,0)$ and then all points adjacent to those adjacent points et cetera until we get another $n$-saur.

Is this solution correct?
We show that $4n-2$ does not work.
Mark one random square with at most three neighbors.  Consider the following process:
1. Consider the last marked square. There are at most three "new" neighbours (other than the one already considered previously), so the unmarked squares can be categorized into three different connected "routes." Since there are at most $n$ marked squares currently ($(n-1)+1$), there are $3n-2$ squares yet to be marked, so one of the routes will have at least $n$ squares. Mark all of the squares that are not in that route. Thus, after this, there are always exactly two connected pieces and the unmarked one is a dinosaur.
2. If there are at least $n$ marked squares now, we are done since the marked square figure is connected and the unmarked figure is connected and a dinosaur
3. Mark the square in the unmarked route adjacent to the square we just processed

Does anyone know if my solution is correct? At first, I had another solution, but found an error, so I am wondering if there is still an error that I overlooked. Thank you so much for all your help! All advice is much appreciated :)

[hide=Solution]
The answer is $\boxed{8025}$. For this, consider a long cross made up of four arms of length $2006$ and one center piece (looks like a plus sign). Attempt to partition this dinosaur. The center piece must be in one of the other partitions. The other partitions have size at most $2006$, so they are not dinosaurs. Thus, this works.

Now, assume that there is a primitive dinosaur $\mathcal{D}$ with size $n\geq8026$. Consider the graph $\mathcal{G}$ with vertices at each of the cells and edges between two vertices if and only if the corresponding cells are connected in $\mathcal{D}$. Let $\mathcal{T}$ be a spanning tree of $\mathcal{G}$.

Some notation:

- For a graph $\mathcal{K}$, let $\left|\mathcal{K}\right|$ denote the number of vertices in $\mathcal{K}$ (for example $\left|\mathcal{G}\right|=\left|\mathcal{T}\right|=n$). Also let $D\left(\mathcal{K}\right)$ denote the maximal degree of any vertex in $\mathcal{K}$. Note that $D\left(\mathcal{T}\right)\leq D\left(\mathcal{G}\right)\leq4$ by definition and the problem constraints (each cell can only be connected in four places).

- For a vertex $V$ in graph $\mathcal{K}$, let $\deg_{\mathcal{K}}\left(V\right)$ denote the degree of $V$ with respect to $\mathcal{K}$.

- For a vertex $V$ in $\mathcal{T}$ and neighbor $N$, let $S_{V,N}$ denote the subtree formed by removing edge $V-N$ and taking the resulting tree containing $N$. It follows by definition that \[\left|S_{V,N}+S_{N,V}\right|=n.\]

- For a vertex $V$, let $M\left(V\right)$ denote the neighbor of $V$ with the largest subtree (if there are multiple, choose arbitrarily). That is, $\left|S_{V,M\left(V\right)}\right|\geq\left|S_{V,N}\right|$ for any neighbor $N$ of $V$. Note that \[\left|S_{V,M\left(V\right)}\right|\geq\frac{n-1}{\deg_{\mathcal{T}}\left(V\right)}\geq\frac{n-1}{D\left(\mathcal{T}\right)}\geq\frac{n-1}{4}>2006\] by the Pigeonhole Principle. Since $\left|S_{V,M\left(V\right)}\right|$ is an integer, we get that $\left|S_{V,M\left(V\right)}\right|\geq2007$.

Let $A$ be the vertex in $\mathcal{T}$ which minimizes $\left|S_{V,M\left(V\right)}\right|$ (if there are multiple, choose arbitrarily). Assume that $M\left(M\left(A\right)\right)\neq A$. Then $S_{M\left(A\right),M\left(M\left(A\right)\right)}$ is a proper subtree of $S_{A,M\left(A\right)}$, so \[\left|S_{M\left(A\right),M\left(M\left(A\right)\right)}\right|<\left|S_{A,M\left(A\right)}\right|,\] contradiction ($M\left(A\right)$ has smaller $\left|S_{V,M\left(V\right)}\right|$ than $A$). Thus, $M\left(M\left(A\right)\right)=A$.

Now, remove edge $A-M\left(A\right)$ to form a forest with trees $\mathcal{T}_A$ and $\mathcal{T}_{M\left(A\right)}$ (with $A$ and $M\left(A\right)$ in it, respectively). We know that \[\left|\mathcal{T}_A\right|=\left|S_{M\left(A\right),A}\right|=\left|S_{M\left(A\right),M\left(M\left(A\right)\right)}\right|\geq2007\] and \[\left|\mathcal{T}_{M\left(A\right)}\right|=\left|S_{A,M\left(A\right)}\right|\geq2007.\] Thus, if we revert back to our cell version of this graph, we have found a partition of $\mathcal{D}$ into two dinosaurs, contradiction. Thus, there is no primitive dinosaur with size $n\geq8026$ and thus our answer is correct.
[/hide]

Let $k=2007$. The answer is $4k-3$. The construction is to take a central cell and append four rods, each consisting of $k-1$ cells, to the four sides of the central cell.

Now we show that all dinosaurs with $V \ge 4k-2$ cells are not primitive. Transfer the problem to graph theory terms: form a spanning tree $T$ to represent the dinosaur, where cells are vertices and shared sides are edges. We wish to bipartition $T$ by removing an edge such that both resulting subtrees have at least $k$ vertices.

Let $v \in T$ be any vertex. Consider any neighbor $w$ of $v$, and define $S_{v, w}$ as the largest subtree containing $w$ but not $v$; we say $S_{v, w}$ is a [i]branch[/i] emanating from $v$. We say $S_{v, w}$ is [i]small[/i] if it has fewer than $k$ vertices, [i]large[/i] if it has greater than $V-k$ vertices, and [i]medium[/i] otherwise. Our goal is to find a $v$ with a neighbor $w$ such that $S_{v, w}$ is medium, since we can then take the bipartition $\{S_{v, w}, T \setminus S_{v, w}\}$.

Let us start by picking any $v \in T$. If $v$ has a medium branch, we are done, so assume otherwise. As $1 \le \deg v \le 4$, not all of $v$'s branches can be small, since that would imply that $|T| \le 4(k-1) + 1 < V$. Also note that $v$ cannot have two or more large branches; hence, $v$ has exactly one large branch. This observation is the basis for our algorithm:
[list]
[*]Let $w$ be the neighbor of $v$ such that $S_{v,w}$ is large. Then, $w$ has a branch $S_{w,v}$ consisting of $v$ appended to all of $v$'s small branches, meaning $S_{w,v}$ has at least $1$ more vertex than the largest small branch of $v$. Also note that $S_{w,v}$ has at most $3(k-1) + 1 = 3k-2 \le V-k$ vertices. Thus, $S_{w,v}$ is either medium or small.
[*]If $S_{w,v}$ is medium, we're done. If $S_{w,v}$ is small, forget $v$ and consider $w$ instead. Repeat these two steps with $w$ playing the role of $v$.
[/list]
In this manner, we move from vertex to vertex until we find a medium branch for the first time. At every step of the way, the size of the largest small branch of our vertex in consideration increases by at least $1$, and that branch never overshoots $V-k$ vertices, so this algorithm must terminate when we find a medium branch.

[quote=stroller]Hmm, how do we know each "cell" has exactly 4 edges with the current wording?  :read:[/quote]

A cell is a unit square if I understood it correctly, so the maximum degree of the vertices is 4.

Define a thing as an animal that is not a dinosaur.
Define an animal with size n if it consists of n equal-sized cells.

We will prove the broader case of when n is the size of a dinosaur, the answer is $4n-3.$

Construction: cross of tiles. very ez to prove

Proving the maximum: We will prove by contradiction. Let’s say for some $n>\ge 2$ ($n = 1$ is obvious) there is an arrangement of at least $4n-2$ cells such that it cannot be partitioned into $2$ primitive dinosaurs. Let the maximum number of cells be $m$. It is obvious that we can have at least $1$ dinosaur in these $4n-2$ cells.

Consider a dinosaur such that when removed, it creates the biggest thing. We can assume the dinosaur has size $n$ to maximize the size of the animal. If this biggest thing has size $x$ where $x < n-1$, we, then we can add cells to this thing to increase its size to $n-1$, and we would have created an animal with more than m cells. To prove this won’t make an animal that can be partitioned into two dinosaurs, if we can, then we see that this added cell must have been added to one of these dinosaurs, which means before we added it, it had a size of $n-1$, which is greater than $x$, a contradiction (we assumed $x$ to be the biggest thing that could be created). Therefore, this thing must have size $n-1.$

We now see that we are left with at least $2n-1$ cells that aren’t included in the dinosaur or this thing. We can just assume it is $2n-1$ for now since we are proving with contradiction. If we remove the dinosaur again temporarily, we see that these $2n-1$ cells are all distributed among things. If one of these things were a dinosaur, then we would have a contradiction. Therefore, if these $2n-1$ cells are distributed among $2$ things, then by the Pigeonhole Principle, we would have an animal with at least $n$ cells, making it a dinosaur.

Define a used cell as a cell that is part of the dinosaur, call it dinosaur $1$, that is adjacent to this $n-1$ sized thing.

This means we must have these $2n-1$ cells distributed among $3$ things. Now consider a used cell. If we remove this cell from the dinosaur and add it to the $n-1$ sized thing. The $n-1$ sized thing is now a dinosaur, and the dinosaur is now a thing. However, dinosaur $1$ was connected to at least $3$ things, each with size at least $1.$ This means when we remove this cell, we can also remove a cell that is part of one of these things that is adjacent to one of the dinosaur’s cells, which means this will for $2$ dinosaurs, a contradiction.

However, to prevent this, if we remove this cell from dinosaur $1,$ it could also be connected to other things too, not only the $n-1$ sized thing. This means for dinosaur $1$ to not be able to “steal” one of the things cells, the things must be connected to the dinosaur at this cell and only this cell. However, each cell only has $4$ sides. One of the sides is already connected to one of the sides of the dinosaur. Another side is also connected to the $n-1$ sized thing. Therefore, there are only $2$ sides left with at least $3$ things to be adjacent to. By the Pigeonhole Principle, one of the things will not be connected to dinosaur $1$ at this cell, a contradiction.

Therefore, we cannot have a $4n-2$ celled animal, as all of them will be able to be partitioned into $2$ dinosaurs. This means $4n-3$ is the answer.

Very messy drawing:

Devilish for amo 1/4 but pretty cool

Replace $2007$ with $n$; the answer is $4n-3$. As a construction, consider a cross with a center cell and four "arms" each $n-1$ long. If this animal is partitioned, the partition containing the center cell has at least $3n-2$ cells, so the other partitions have length at most $n-1$. As such this animal is primitive.
Now it suffices to show that no $4n-2$-cell dinosaur is primitive. Suppose otherwise, and consider a "semi-maximal path" $P=c_1,\ldots,c_k$ along the cells of the dinosaur $D$—that is, a path that cannot be made longer by "naively" adding cells to its start or end. Upon removing this path from $D$ there should remain some number (possibly zero) of connected components. For each of these components, let its "anchor" be one of its cells that is adjacent to $P$ (pick arbitrarily).
Define a sequence of animals $a_0,\ldots,a_k \subseteq D$, starting with $a_0=\emptyset$. To construct the rest, "walk" from $c_1$ to $c_k$, and upon entering a cell $c_i$ set $a_i$ equal to the union of $a_{i-1},c_i$, and whatever connected components are anchored to $c_i$. Note that $a_k=D$ and
$$0=|a_0|<|a_1|<\cdots<|a_{k-1}|<|a_k|=|D|=4n-2.$$
Further, as $P$ is "semi-maximal" we actually have $|a_1|=1$ and $|a_{k-1}|=4n-3$.
Now, it is clear that for all $i$, we can partition $D$ into the two possibly empty animals $a_i$ and $D \setminus a_i$—that is, both of these are connected figures. Because we can't have both of these be dinosaurs by assumption, there must exist some $2 \leq i \leq n-1$ with
$$|a_{i-1}|\leq n-1 \text{ and } |a_i|\geq (4n-2)-(n-1)=3n-1.$$
Note that $i=1$ and $i=n$ fail because of their known values.
By definition, this means that the connected components anchored to $c_i$ must have total size at least $(3n-1)-(n-1)-1=2n-1$. On the other hand, there are only two possible edges to which a connected component could possibly be anchored to $c_i$, as the other two are "occupied" by $c_{i-1}$ and $c_{i+1}$. It then follows that there are at most two connected components anchored to $c_i$, and therefore one of them must contain at least $n$ cells. Let this connected component be $C$; then $D \setminus C$ is an animal, being connected "through" $P$, which also contains $3n-2\geq n$ cells, so we can partition $D$ into the dinosaurs $C$ and $D \setminus C$, contradiction. As such, $D$ cannot exist, so every $4n-2$-cell dinosaur is non-primitive. $\blacksquare$

Please could someone check this as it feels too short.
[hide = solution]
We will prove that the maximum is $4n-3$ for all $n$, giving a value of $8025$ as the maximum number of cells. Let an [i]n-dinosaur[/i] be an animal with at least $n$ cells (for brevity, from now on we will refer to this as a dinosaur), and let a [i]sub-dinosaur[/i] be a dinosaur which is one of the two dinosaurs a larger dinosaur is partitioned into. Note that $4n-3$ can be achieved by having a line of $n-1$ cells protruding from each edge of a certain cell; this can't be partitioned into two animals of size $n$ as then the center square would have to be removed, leaving three disconnected animals, implying that two have to be part of the sub-dinosaur and hence leaving at most $n-1$ cells for the other sub-dinosaur, a contradiction, as required.

We will proceed by induction. Note that the base case where $n = 1$ is clear, as by the inductive definition of an animal we can remove the cell from an animal we added to it from an animal with one less cell than it to get two sub-dinosaurs, the cell we removed and the remaining cells, so for an animal of at least two cells there exists a partition into two $1$-dinosaurs. For the step, note that for a dinosaur with $4n - 2$ cells there exists a partition of it into two animals, both of which contain at least $n-1$ cells. If both contain at least $n$ cells, then we are done, so assume that one contains $n-1$ cells. Then there exists a cell in the larger animal which touches a cell in the smaller animal. Let a [i]branch[/i] be a series of connected cells protruding from a side of this cell (not including the side connected to the smaller partition), for which if any cell in the larger partition is connected to the branch, then that cell is in the branch. Note that a branch is an animal. There are at most three branches here, implying that at least one of them must have $n$ cells (as the total number of cells in branches is $3n-2$, so the pigeonhole principle applies). Since each branch has less than $3n-1$ cells, we are done, as we can do a partition, one sub-dinosaur being the branch with the largest number of cells and the other being the remaining cells (note that an animal connected to another animal is an animal and since the non-branch partition is formed by connecting the original smaller partition with the cell from which the branches protrude - which is an animal - and between 0 and 2 branches, both of which are animals, the non-branch partition is an animal). [/hide]

The following lemma kills the problem. Construct the tree with a base vertex of degree $4$ and with four length $2007$ paths.

[color=#00f][b] Lemma:[/b][/color] There is some vertex $v$ so that $G - v$ does not leave behind any dinosaurs.

[color=#f00][b] Proof:[/b][/color] Assume that for every vertex $v \in V(G)$, $G - v$ leaves behind dinosaurs. Then we have that if we consider the base of this tree, then we have at most four components for which aren't dinosaurs. A contradiction. $\square$

Hence we have the four components give us $4(n - 1)$ vertices and adding back the base of the tree gives us $4(n - 1) + 1$ total vertices. $\blacksquare$

Let $n=2007$. The answer is $4n-3$, achieved by a "+" shape where there are $n-1$ cells sticking out of the middle in all four directions. We will now prove that $4n-2$ doesn't work, so assume FTSOC that there is a primitive dinosaur of size $4n-2$.

View an animal as a graph where the cells are the nodes and the edges are whether the two cells are orthogonally connected. Note that each node has degree at most $4$. Now arbitrarily remove edges until the graph is a tree. Clearly, any solution on the tree must work on the original graph.

Now consider any leaf node in the tree, say $A$. Consider the longest path starting from $A$ in the tree(if there are multiple, choose any), and say it ends at $B$, which must be a leaf node. Let this path have length $k$, and let the path be $AP_1P_2\dots P_{k-1}B$. Define $P_0=A$ and $P_k=B$. Now let $f(x)$ be the number of nodes dangling off the path not including $P_x$(the ones that would be not connected to something in the path if $P_x$ were removed from the tree and all of its edges were removed), plus one(for $P_x$), at $P_x$. Also, define
\[g(x)=f(0)+f(1)+\dots+f(x).\]

Now consider the least $m$ such that $g(m)\ge n$. If $g(m)\le 3n-2$ we already have a contradiction by deleting the edge between $P_m$ and $P_{m+1}$, so we must have $g(m)\ge 3n-1$. But $g(m-1)\le n-1$ by definition, so
\[2n=(3n-1)-(n-1)\le g(m)-g(m-1)=f(m).\]
Therefore, by pigeonhole, there must be some tree dangling off of $P_m$ that has size at least $n$, contradiction.

Let $n = 2007$.

The answer is $4n - 3$. The construction is same as above.

Now we'll prove that the primitive dinosaur has at most $4n - 3$ edges. Let $G$ be a our primitive dinosaur and let $v$ be a cell in $G$. Let $v_{1}, \dots, v_{k}$ be neighbors of $v$. Define a vertex $u$ is $i$-good if there exist path $v$ to $u$ passing through vertex $v_{i}$. Let $A_{i}$ be a set of $i$-good vertices. For some $i$, if $|A_{i}| \geq n$, then $A_{i}$ is dinosaur and the rest of cells form a dinosaur, a contradiction. So the number of cell in $G$ not exceeds $1 + \sum_{i=1}^{k}|A_{k}| \leq 1 + 4(n - 1) = 4n - 3$. This completes proof. $\blacksquare$

We solve the more general case. An animal with at least $k$ cells is known as a [i]k-nimal[/i]. Now, we claim that the maximum number of cells in a primitive $k-$nimal is $4k-3$.\\

Consider a $k-$nimal with its cells in the shape of its cross with $k-1$ cells in each of the arms. This gives a total of $4k-3$ cells, and any set of $k$ cells in this configuration must pass through the center square implying that only one such set of cells exists (For any animal with less than $4k-3$ cells simply remove an adequate number of cells of the arms).\\

Now, look at this animal with $n$ cells as a simple connected graph $G$, where each vertex represents a cell and each edge between two vertices represents two cells being adjacent.  Then, we know there exists a spanning tree $T$ of this graph. Then, we have the following (kinda) well known result.

[color=#f00][b]Claim[/b] : Let $T$ be a tree and $v$ be any vertex of $T$. Let $v_1,v_2,\dots,v_m$ be the vertices adjacent to $v$. Let $T_i$ be the tree which contains $v_i$ which is obtain upon deleting the edge $vv_i$.Then, let $f(v)=\max_{i=1}^m|V(T_i)|$. Let $\Delta>1$ be the maximum degree among all vertices of $T$. Then, there exists a vertex $v$ such that[/color]
    \[\frac{n-1}{\Delta} \leq f(v) \leq \frac{(\Delta -1)(n-1)}{\Delta} \]

[i]Proof : [/i] Let $d$ be the degree of some vertex. The left inequality clearly follows from Pigeonhole Principle as,
\[f(v) \geq \frac{n-1}{d} \geq \frac{n-1}{\Delta}\]
Now, to see why the right inequality must be true, consider the vertex $v$ such that $f(v)$ is minimum. Suppose $f(v) \geq \frac{(\Delta-1)(n-1)}{\Delta}+1$. Let $v_i$ be the neighbour of $v$ with $|T_i| \geq \frac{(\Delta-1)(n-1)}{\Delta}+1$. Then, clearly the tree containing $v$ after removing $v_iv$ contains at most $n - \frac{(\Delta -1)(n-1)}{\Delta}-1 = \frac{n-1}{\Delta}$. Now, if the tree $T_j$ which attains the maximum of $f(v_i)$ contains $v$, then $f(v_i) \leq \frac{n-1}{\Delta} \leq \frac{(\Delta -1)(n-1)}{\Delta}$ (with equality holding if and only if $\Delta=2$ in which case the result is obvious anyways). Thus, this violates the minimality of $f(v)$. If $T_j$ does not contain $v$ on the other, hand $f(v_i)=f(v)-1<f(v)$ again violating the minimality. Thus, our assumption must have been false and indeed, the required inequality holds.

Now, note that if the given inequality is true, the spanning tree $T$ of our graph contains two vertices $v,v_i$ such that when we delete edge $vv_i$ we have two trees such that the larger of them, has length at least $\frac{n-1}{\Delta}$ and the smaller has length at least $n-\frac{(\Delta -1)(n-1)}{\Delta} = \frac{n-1}{\Delta}$. Thus, $T$ and indeed $G$ contain two vertex-disjoint connected subgraphs containing at least $\lceil{\frac{n-1}{\Delta}}\rceil$. Thus, for all $n\geq 4k-2$, we have two vertex-disjoin connected subgraphs such that each has at least
\[\lceil{\frac{n-1}{\Delta}}\rceil \geq \lceil{\frac{4k-2-1}{4}}\rceil \geq k\] thus implying that it includes two $k-$nimals. Thus, such an animal cannot be primitive and we are done.


summer program
PROMYS
induction
search
number theory

I know there is a formula for the nth k-gonal number. Can someone tell me what it is and show how to get it?

By any chance, are you applying to PROMYS? If so, I am not sure if we can answer this question because of the similarity of this question and a PROMYS application question. Either way, I don't think we can answer this question because other people who visit AoPS might be applying, and giving the solution would skew the results. The other questions can be found [url=http://www.promys.org/promys/Application05.pdf]here[/url].

Question 9a asks:

[quote]What are the first five hexagonal numbers? What are the first five septagonal numbers? What are the first five r-gonal numbers? Give a formula for the nth triangular number. Give a formula for the nth square number. Give a formula for the nth pentagonal number. [b]In general, give a formula for the nth r-gonal number.[/b][/quote]

Edit: deleted until that what fanaticsm said is cleared up !

I wasn't going to apply... I didn't even know about that camp. I guess I'll have to try and derive it myself. :D

Ahh I see...well, good luck then (and sorry if I sounded accusatory, I didn't intend it to be that way)  :D

I find that question on the PROMYS app kind of amusing... because it was on our Open Door Problem Set last year (the one we get after we've done all the stuff at PROMYS =P). Maybe people are getting smarter...

That problem from PROMYS isn't original....I think a lot of number theory texts would cover polygonal numbers.  I'm not saying it's easy but it doesn't seem to hard for people to get that answer from somewhere else.  Anyway, there was a [url=http://www.artofproblemsolving.com/Community/AoPS_Y_MJ_Transcripts.php?mj_id=40]math jam on polygonal numbers[/url].

If the nth 4-gonal numbers is the sum of the first n triangular then the formula for the nth k-gonal number is
nCr(n+k-2,k-1)

The nth k-gonal number is

$\displaystyle\left(\frac{k}{2}\right)(n^2-n)-n^2+2n$

As fanaticsm noted, this is a problem from the PROMYS application, so I don't think that it's proper that the solution should be discussed here.

Mods, please lock/delete this thread until the application period is over?

Just use induction and you can find it really easily anyway, I don't see what the big fuss is about.  Specifically, because you can write the polygonal numbers as sums of certain consecutive members of integer sequences, you can find ALL of them from the formula for triangular numbers, and you can prove that formula easily with induction.

[quote="goodyfresh741"]Just use induction and you can find it really easily anyway, I don't see what the big fuss is about. [/quote]

It's not about being fussy or self-righteous. It's simply a matter of academic and intellectual integrity.

I'm sure a quick google search would turn up very quick results for many of the PROMYS problems.

What sets AoPS apart is that while we have many very capable and talented members, most of them would not jump to prove that they can solve the problem if it compromises or raises doubt about their honor. Problems like these have been discussed after the application period, but for now, just so that there is no chance of questionable conduct, I think it's best we leave this thread be.  ;)


In the coordinate plane, let denote $ C_1$ the circle with centrer the origin, radius $ 2$ and $ C_2$ the circle with center the point $ (1,\ 0)$ radius $ 1$. Suppose that the circle $ C_3$ with center the point $ (a,\ b)$, radius $ t$ touches internally to $ C_1$ and externally to $ C_2$, where $ b$ is a positive real number.

(1) Express $ t$ in terms of $ a,\ b$, then find the range of $ t$ for which $ t$ can be valued.

(2) When $ t$ moves in the range found in (1) , find the maximum value of $ b$.

[hide]
1a)Let $ O$ be the center of $ C_3$. Then we have that the radius of $ C_1$ passing through $ O$ hits $ C_1$ at the point of tangency with $ C_3$. So then the distance from the origin to $ O$ is $ 2-t$; since the distance from the origin is $ \sqrt{a^2+b^2}$, we have $ t=2-\sqrt{a^2+b^2}$. (Note that this does not guarantee tangency to $ C_2$.)

1b)Since $ C_3$ is externally tangent to $ C_2$, the distance from the center of $ C_2$ to $ O$ is the sum of their radii, or $ 1+t$. But this distance is merely $ \sqrt{(1-a)^2+b^2}$; thus combining we have $ t=\sqrt{(1-a)^2+b^2}-1$. (We don't actually have to compute this number.) Now $ O$ may lie on any radius of $ C_1$, and the radius uniquely determines a circle $ O_3$. Thus the radius may range from 1 (consider $ O=(-1,0)$) to 0 at (2,0).

2: Setting the two previous equations for t equal, we have
\[ 3-\sqrt{a^2+b^2}=\sqrt{(1-a)^2+b^2}\]
\[ 9-6\sqrt{a^2+b^2}+a^2+b^2=1-2a+a^2+b^2\]
\[ 4-3\sqrt{a^2+b^2}=-a\]
\[ 4+a=3\sqrt{a^2+b^2}\]
\[ 16+8a+a^2=9a^2+9b^2\]
\[ 16+8a-8a^2=9b^2\]
\[ b=\frac{2\sqrt{4+2a-2a^2}}{3}\]
\[ b=\frac{2\sqrt{-2(a-\frac 12)^2+\frac 92}}3\]
As the maximal value occurs when $ (a-\frac 12)^2$ is minimal, namely at $ a=\frac 12$, the maximal value of $ b$ is $ \sqrt{2}$.
[/hide]

After all, How $ a,\ b$ are expressed $ a,\ b$ in terms of $ t$?


group theory
abstract algebra
superior algebra
superior algebra unsolved

Let $ G$ be a finite group which operates on an $ n\geq 2$ elements set $ A$, such that $ \forall (a_1,a_2),(b_1,b_2) \in A^2$ where $ a_1 \not\equal{}a_2$ and $ b_1\not\equal{}b_2$, there exists an element $ g \in G$ ,such that  $ ga_i\equal{}b_i$ for $ i\equal{}1,2$ .Prove that $ n(n\minus{}1) \mid |G|$.

[hide="Lagrange’s theorem."]The problem is more complicated than I at first thought. See solution below.[/hide]

thanks very much, :D  very easy problem.  :lol:

Let $ X \equal{} \{(a_1,a_2)\in A^2: a_1\ne a_2\}$ and fix an element $ (a_1,a_2)\in X$. Then $ X \equal{} \{(ga_1,ga_2): g\in G\}$.

Let $ K \equal{} \{g\in G: ga_1 \equal{} a_1,ga_2 \equal{} a_2\}$. Then $ K$ is a subgroup of $ G$; let $ G/K$ be the set of all cosets of $ K$ in $ G$.

(Reason for doing this: Given $ g,h\in G,\ a\in A$, it is possible that $ ga \equal{} ha$ but $ g\ne h$. This is a slight annoyance here. Fortunately, group action is an operation that is sort of a homomorphism (not a real homomorphism, just sort of a one); our $ K$ here is simply the kernel of this sort-of homomorphism. This takes care our slight annoyance: now, $ ga \equal{} ha\ \Leftrightarrow\ gK \equal{} hK$.)

Define $ \mathrm{f}: X\to G/K$ by $ \mathrm{f}\,(ga_1,ga_2) \equal{} gK$. Then f is a bijection. Since $ |X| \equal{} n(n \minus{} 1)$, it follows that $ K$ has index $ n(n \minus{} 1)$ in $ G$, and the result follows by Lagrange.