Source: UNCC HS Math Contest 1995 #16

F(N) = n/3 if n is a multiple of 3
F(N) = 2n+1 otherwise.

For how many positive integers k is it true that F(F(k)) = k?

(A) 0
(B) 1
(C) 2
(D) 3
(E) 4

[hide] (C) 2. The integers are 1 and 3.

I'm not good at explanations...but there are 4 possible ways in which F(F(k)) = k. Either

a) (k/3)/3 = k, which gives k = 0. We can discount this since the question asks for positive integers.

b) 2(k/3) + 1 = k, which gives k = 3

c) (2k+1)/3 = k, which gives us k = 1 or

d) 2(2k+1) + 1 = k, which gives us k = -1. We can discount this since the question asks for positive integers.[/hide]

[quote="rippledance"]I'm not good at explanations...[/quote]

Nonsense...er, rubbish.  That was a brilliant explanation.  :wink:

Remember that zero is not a positive integer.

[quote="Tare"]Is "crap" a bad word? I say that because everyone seems to use it without the asterisks...[/quote]

It's really up to you.  But this is getting off subject.

Heh, heh.  Look at me shamelessly editing rippledance's post to make it right...

Thanks. I was going to edit it, but oh well...

It's better if you don't edit them. Other people should be able to read this post and see that people do make mistakes. It would be rather disturbing if someone came along and saw that everything on the forum was perfect, and that person thought that no one else makes mistakes. Mistakes are a very important part of mathematics, so don't remove them please.


Euler
geometry
circumcircle
ratio
analytic geometry
vector
algebra

Euler line of a triangle is the line that connects the triangle's orthocenter, centroid, and circumcenter, with centroid in between and dividing the distance from orthocenter to circumcenter into ratio of two to one (for example, if the length of the euler line is 15, then the distance from orthocenter to centroid will be 10, and the distance from centroid to circumcenter will be 5). Prove that the distance of the Euler line equals $9R^2 - a^2 - b^2 - c^2$, $R$ being the circumradius, and $a, b, c$ the length of the sides

[hide]if you remember a discussion in AoPS vol. 2 where if the origin is the circumcenter of $\triangle ABC$ and the verticies of the triangle are $\vec{A}$, $\vec{B}$ and $\vec{C}$, then the orthocenter is given by $\vec{H}=\vec{A}+\vec{B}+\vec{C}$, (Note that all the vectors have the same length as the circumradius since we chose the circumcenter as the origin in this vector system)

so all that remains to use a mess of algebra to show that $||\vec{A}+\vec{B}+\vec{C}||^2=9R^2-(a^2+b^2+c^2)$

Let $\vec{A} =<x_0 \, y_0>$, $\vec{B}=<x_1 \, y_1>$, and $\vec{C}=<x_2 \, y_2>$
since our center is the circumcenter, $R^2=x_n^2+y_n^2$

the LHS is $(x_0+x_1+x_2)^2+(y_0+y_1+y_2)^2$

for the RHS, we get
$= 9R^2-\left(\, (x_0-x_1)^2+(y_0-y_1)^2+(x_1-x_2)^2+(y_1-y_2)^2+(x_0-x_2)^2+(y_0-y_2)^2 \, \right)$
$=3R^2+2( x_0x_1+y_0y_1+x_2x_1+y_2y_1+x_0x_2+y_0y_2)$
$= \left( \, x_0^2+x_1^2+x_2^2+ 2(x_0x_1+x_2x_1+x_0x_2) \,\right)+ \left( \, y_0^2+y_1^2+y_2^2+ 2(y_0y_1+y_2y_1+y_0y_2)\, \right)$
$=(x_0+x_1+x_2)^2+(y_0+y_1+y_2)^2$ as desired[/hide]

wow...nice coordinate geometry (seems like all crazy smart people turns geometry into coordinate...), a more geometric one is below:
[hide]
draw a perpendicular bisector of side $BC$, it'll pass thru $O$, and then draw $OB$. using pythagorean theorem, the length from the midpoint of $BC$(denoted $D$) to $O$ will be $R^2 - \frac{a^2}{4}$. Draw $OA$ and the median from $A$ to $BC$, since the centroid divides the median in a ratio of 2:1, we can find $AG$ and $GD$ easily knowing that $AD^2 = \frac{b^2}{2} + \frac{c^2}{2} - \frac{a^2}{4}$ by Stewarts Theorem. Because $OA$ equals $R$, we have all the lengths we need to find $GO$ using Stewarts Theorem (apply to $\triangle ADO$). Since the Euler line is 3 times this length, upon simplifying we'll get $9R^2 - a^2 - b^2 - c^2$.  (sorry, all the algebra omitted, try it out as a practice   :lol:  :lol:)
[/hide]
I think the good thing about this method is that if we let $n = \frac{M^2}{9}$, where $M$ is the length of the Median, the whole thing becomes easy and the algebra simple. Because all the nasty variables eventually cancels out, and the rest is like early algebra II homework
(I still remember: add polynomials, $(9x^5 + 7x^4 - 67x^3 + 2x^2 - 1) + (7x^4 + x^3 - 2x^2 + 5x)$, basically bunch of brainless work)

[quote="Altheman"]if you remember a discussion in AoPS vol. 2 [/quote]
I don't have AoPS books. Can you please explain your first part?

if the center is the circumcenter, and we have vectors $\vec{A}$, $\vec{B}$, and $\vec{C}$ are the verticies, we want a vector $\vec{H}$, so it is perpendicular to the sides, we know that line $AH$ will be perpendicular to line $BC$ since $H$ is the orthocenter, so their dot product will be 0, and the vector connecting 2 points is just subtracting those vectors

$(\vec{H}-\vec{A})\cdot(\vec{B}-\vec{C})=0$

repeating this process for the other sides, we have

$(\vec{H}-\vec{B})\cdot(\vec{A}-\vec{C})=0$ and
$(\vec{H}-\vec{C})\cdot(\vec{B}-\vec{A})=0$

we find that $\vec{H}=\vec{A}+\vec{B}+\vec{C}$ satisfies this

i don't have time to type out the how that vector satisfies that, maybe tomorrow i will finish it up

I also remember proving it at [url=http://www.mathlinks.ro/Forum/viewtopic.php?p=120219#p120219]http://www.mathlinks.ro/Forum/viewtopic.php?t=17684 post #2[/url].

  darij

I note the circumcircle $w=C(O,R)$, the middlepoint $M$ of the side $[BC]$ and $\{A,A'\}\subset AM\cap w$. The power $p$ of the point $G$ w.r.t. the circle $w$ is $p=\overline {GA}\cdot \overline {GA'}=OG^2-R^2$. But $\overline {GA}\cdot \overline {GA'}=-GA\cdot GA'$. Thus, $GO^2=R^2-GA\cdot GA'$. Therefore,
$GA\cdot GA'=GA(GM+MA')=\frac 23 MA\cdot (\frac 13 MA+MA')=$
$\frac 29 m^2_a+\frac 23 MA\cdot MA'=\frac{1}{18} (2b^2+2c^2-a^2)+\frac 16 a^2=\frac 19(a^2+b^2+c^2)\Longrightarrow$
$GO^2=R^2-\frac 19(a^2+b^2+c^2)\Longrightarrow HO^2=9\cdot GO^2=9R^2-(a^2+b^2+c^2).$

Proceeding similarly, we will obtain easily the following generalization:

[u]Generalization.[/u] Let a point $P$ in the interior of the triangle $ABC$, the circumcircle $w=C(O,R)$, the intersections $M\in AP\cap BC$, $\{A,A'\}\subset AP\cap w$ and I know $\frac{PA}{PM}=x$, $\frac{MB}{MC}=y$.
Then, $PO^2=R^2-PA\cdot PA'$, where
$PA\cdot PA'=\frac{x}{(x+1)^2(y+1)^2}[ xya^2+y(y+1)b^2+(y+1)c^2].$

From this relation results the following inequality:

$x>0,\ y>0\Longrightarrow (x+1)^2(y+1)^2R^2\ge x[ xya^2+y(y+1)b^2+(y+1)c^2].$

[u]Particular cases.[/u] $P: =I(x=\frac{b+c}{a},\ y=\frac cb)\Longrightarrow IA\cdot IA'=2Rr\ a.s.o.$

[u]Remark.[/u] Generally, the power $p$ of the point $P(u,v,w)$ w.r.t. the circumcircle $w$, where $(u,v,w)$ are the barycentrical coordinates of the point $P$, is given by the following relation:

$p(P)=\overline {PA}\cdot \overline {PA'}=-(vwa^2+wub^2+uvc^2).$


A wrench 30cm long lies along the positive y-axis and grips a bolt at the origin. A force  is applied in the direction $<0,3,-4>$ at the end of the wrench. Find the magnitude of the force needed to supply 100J of torque o the bolt.

$\vec{F}= F \hat e_{F}$ where $\hat e_{F}$ is a unit vector in direction of $\vec{F}$. Normalizing your vector, it's $\frac{(0,3,-4)}{5}$
$\vec \tau = \vec r \times \vec F$
Your $\vec r$ is given to be $0.3 \vec j$.
$100 \hat e_{\tau}= (0,0.3,0) \times F \frac{(0,3,-4)}{5}= F\frac{-1.2 \vec i}{5}$

So, $\hat e_{\tau}=-\vec i$ and $F \approx 416.67 N$

[quote="maokid7"]100J of torque[/quote]
Torque is measured in Newton-meters (or foot-pounds, etc), but not in Joules.


AMC
AIME
MATHCOUNTS
AMC 10
geometry
3D geometry
pyramid

AIME MARATHON

This is something that we did in the MATHCOUNTS forum, and it worked well.  Here is how it works:
1) A math problem from the AIME is posted.
2) If you solve the problem, you get to post your own problem.
3) Then you allow others to solve your problem.  After they solve your problem, they post their own.
4) Someone answers that problem, posts their own...........

If you disagree with an answer or have a question, feel free to post it.

I'll start out with a more difficult AMC10:

You have four marbles.
Three have a radius 1, the other has radius 2.
You form a pyramid by placing the three marbles of radius 1 tangent to each other and setting the radius 2 marble on top.  How tall is the figure?

A picture is attached.

There is no picture attached, but
[hide="My guess"]
$4+\sqrt{3}$
[/hide]

There is already an AIME Marathon.. [url=http://artofproblemsolving.com/Forum/viewtopic.php?t=42590&start=100]artofproblemsolving.com/Forum/viewtopic.php?t=42590&start=100[/url]

Mods, please delete this! Thx  :P

I just pmed rrusczyk about this.

Somebody must split the thread or is it a bug in the forum? It's weird because even I did post on AIME marathon thread WindSlicer posted, I didn't start the thread (You can easily figure out this by my comment on the first thread of the first page).

So, I don't know what's up.

For the problem I get:
[hide] $3+\sqrt{\frac{23}{3}}$

The centers of the 4 marbles form a tetrahedron with the base triangle equilateral of edge length 2, and the three other edges with length 3.  The line through the center of the bigger marble perpindicular to the base equilateral triangle goes through the centroid of the equilateral triangle.  Thus the height of the tetrahedron is ${\sqrt{3^2-\left( \frac{2\sqrt{3}}{3}\right) ^2}}=\sqrt{\frac{23}{3}}$.  But the whole tetrahedron is 1 unit above the floor.  Additionally, the top of the big marble is 2 units above the top of the tetrahedron.  Hence, the answer is $\boxed{3+\sqrt{\frac{23}{3}}}$.
[/hide]

Well something weird has happened obviously but I am going to revive this thread since the other one contains many posted problems and I didn't want to have repeats posted. So here is problem:

For {1,2,3,..., n} and each of its nonemptry subsets a unique alternating sum is defined as follows: Arrange the number in the subset in decrasing order and then beggining with the largest, alternately add and subtract successive numbers. Ex: {1,2,3,6,9} is 9-6+4-2+1=6. Find the sum of all such alternating sums for n=7.

[hide]For any sum without n in the set, each element will have the opposite sign in the sum that does contain n. Therefore, everything will cancel out except the number of n's, which is . There are that many n's, so the sum of all of these is . For n=7, the solution is .[/hide]

Use a simple 5 point star to understand what it's asking, and then work for smaller cases to see how you can work up to the 1000 point star.

What I don't understand is the statement that "the angles at $P_i$ are equal." I don't see how that can be possible for every angle in the star, because some must be acute and some must be obtuse, unless it simply means the acute angles at the points of the stars.

[quote="Elemennop"]Those are referring to the acute angles.[/quote]

Give the next Problem

[quote="Elemennop"]Alright, here's a problem I really liked on the AIME:

A regular n-star is the union of n equal line segments $P_1P_2, P_2P_3, \ldots , P_nP_1$ in the plane such that the angles at $P_i$ are all equal and the path $P_1P_2 \ldots P_nP_1$ turns counterclockwise through an angle less than $180^{\circ}$ at each vertex. There are no regular 3-stars, 4-stars or 6-stars, but there are two non-similar regular 7-stars. How many non-similar regular 1000-stars are there?[/quote]
This is his problem.


I wasn't sure where to post this, but anyway.

What's your favorite paradox? Or several of your favorites? This is one of mine, maybe by Godel? (I'm really not sure though...)

Call a set proper if it does not contain itself as a member.
Then, call the set A is the set of all proper sets.
Does A contain itself, or is it proper?

:-)

.dzhonatan

Berry's Paradox

- the english alphabet is finite, so there are a finite number of english expressions with less than 100 letters

- then there must exist a finite number of natural numbers which are denoted by english expressions of fewer than 100 letters

- Let n be the smallest positive integer that cannot be denoted by fewer than 100 letters

- the above expression contains fewer than 100 letters, and thus denotes an un-denotable number.

the paradox that swiftstream named is by bertrand russell[/quote]

S: T is false.
T: S is true.

I bet this is the second :D  shortest one!

I think the shortest one is

P: P is false :D

It really easy to achieve paradoxes with self-referential sentences.

Yeah, self-recurring loops are a faszinating topic. I really think that reading books by Douglas R. Hofstadter is a "must". Especially I enjoyed the well-known "Gdel, Escher, Bach: an Eternal Golden Braid" which is full of basic and nice computer science, math and psychology stuff. Particularly amazing pictures by M. Escher can be found there too. But I also like his book "Metamagicum".

some references:

http://www.amazon.com/exec/obidos/tg/detail/-/0465026567/qid=1077284784/sr=1-1/ref=sr_1_1/103-1065354-4176625?v=glance&s=books
http://www.forum2.org/tal/books/geb.html
http://www-personal.umich.edu/~jlawler/geb.html

Weird,i had exactly this post,yesterday,on another forum...wicked!

in math, l think the paradoxes with Cantor's theory are the most beautiful

[quote="nonIMO"]My favourite one is from probability theory. That is if you randomly (it means that probabilities to born in every day of the year are equal) choose about 23 (as I remember  :maybe: ) people the probability that there are two of them that have the same birthday is 1/2 !!! It's unbelieveable! But it's true, check it yourselves!
I've found this in the William Feller's book "Introduction to Probability Theory and Its Applications".[/quote]

I don't think that is a paradox.  It is just counterintuitive and fascinating.

how much wood could a woodchuck chuck if a woodchuck could chuck wood?

[quote="MindFlyer"][quote="Peter VDD"]I always lie.[/quote]
I don't think this is a paradox. It just means that you sometimes lie, and sometimes tell the truth. So, this time you lied, and everithing works.  :)[/quote]

???

If I ALWAYS lie, i can not SOMETIMES lie and SOMETIMES tell the truth eh? ;)

[quote="joml88"]If you always lie then saying that you always lie would be a lie.  So what (s) he was saying is that suppose you lie sometimes.  We could consider this one of the times you lie.[/quote]To be more specific, the negation of the proposition "I always lie" is not "I always tell the truth" as people would be proned to think on the first sight, but "I do not always lie", which is equivalent that "Some of my propositions are lies (which is the case with that one), and others are truths)".

yes, indeed

you got me on that one :D

I should have said 'I am lying'.

[quote="Valentin Vornicu"]To be more specific, the negation of the proposition "I always lie" is not "I always tell the truth" as people would be proned to think on the first sight, but "I do not always lie"...[/quote] Well, the negation of quantifier is basic logic. It is not black but white.  :D

i like hilbert's hotel paradox, the banach-tarski paradox, and teh st. peterburg's problem.

patty: caro ALWAYS lies
me: patty ALWAYS tells the truth

okay, its like a previous one, but i like it and i know patty likes it too.
sorry for the nickname, patty, i know you hate it, and that's why i use it...
coming back in [b]5 days[/b] ^^!!

I really don't like all those paradoxes which are just contradictory / self contradictory statements. All it is, is that not every statement has to be true or false. I really can't see how turning the most simple one into much more complicated but the same idea ones is that interesting.. maybe thats just me. I do like other paradoxes mentioned above. Also those ones about mindreading aliens. They're interesting.

oh that makes me feel so warm and fuzzy, NOT

Heres one of the ones I mentioned about aliens:

A being put one thousand dollars in box A and either zero or one million dollars in box B and presents you with two choices:

   1. Open box B only.
   2. Open both box A and B.

The being put money in box B only if it predicted you will choose option (1). The being put nothing in box B if it predicted you will do anything other than choose option (1) (including choosing option (2), flipping a coin, etc.).

Assuming that you have never known the being to be wrong in predicting your actions, which option should you choose to maximize the amount of money you get?

edit - heres another one.

I pick two numbers > 1 at random (actually the > 1 condition doesn't have to be there, but makes it easier to explain). I tell you one of these numbers (chosen from the two at random).  You have to guess whether the number I tell you is the higher or lower of my two numbers.
Here is a strategy that gives you a probability of > 1/2 of being correct:
If I tell you the number x, choose "low" with probability 1/x.

Now if I chose x<y, half the time I tell you x and you win 1/x of the time, and half the time I tell you y and you win 1 - 1/y of the time. Total = 1/2 (1/x + 1 - 1/y) = 1/2 + 1/2 (1/x - 1/y) > 1/2.

Does this seem strange to you?

Define the quotation of a phrase to be that phrase in quotes, so the quotation of orange is "orange" .

To append a phrase to another is simply to concatenate them, so apple appended to orange is orange apple.

Then the paradox is

"yields falsehood when appended to its own quotation" yields falsehood when appended to its own quotation

kinda like this sentence is false, except without explicit self-reference.

quining is good fun.

Here is a fun one.

An eccentric, wealthy man (you have no idea how wealthy), has taken an interest in you.  He provides you with two envelopes, telling you that one contains exactly twice the amount of money as the other.  You are allowed to choose one envelope, open it and look inside, and then, based on what you see, decide whether to keep that money or take the other envelope instead.  What should you do?

The initial thought is this.  Suppose that you choose one envelope at random.  You of course have a 1/2 probability of choosing the envelope with more money in it, and 1/2 probability of choosing the one with less.  Suppose, then, that you find that the envelope has X dollars in it.  Now since you had equal probability of choosing the envelope with more money in it or the one with less, the other envelope has X/2 dollars with probability 1/2 and 2X dollars with probability 1/2.  This gives an expected value for the amount of money in the other envelope of 1.25X > X.  Hence you should switch.

But note that this works [i]no matter the value of X[/i]!  Thus the conclusion is, that after picking an envelope at random, you should [i]always[/i] switch to obtain a higher expected return.  This of course makes no sense at all.  What went wrong?

Wooooah, what an old thread!
14 year bumps, lol.


[quote="Silverfalcon"]How many natural numbers (ie. 1,2,3,...) equal three times the sum of the digits?

A. None
B. 1
C. 2
D. 3
E. 4 or more[/quote]
[hide="Solution"]
Clearly, no $ 1$ digit number works.  Now, assume that an $ n$ digit number works, where $ n>2$.  Thus, the largest sum is $ 9n$.  So, $ 3(9n)\ge10^n$.  Clearly, this doesn't work when $ n\ge 3$.  So, the number must have two digits.  Let the number be $ 10a\plus{}b$.  By the given condition, $ 10a\plus{}b\equal{}3a\plus{}3b\implies 7a\equal{}2b$.  Therefore, $ 7|b$.  Let $ b\equal{}7x$, so $ x\equal{}1$ since $ b<10$.  Hence, $ 14\equal{}14x\equal{}7a\implies a\equal{}2$.  Thus, the only such number that works is $ 27$, so the answer is $ \boxed{B}$, or only one number. [/hide]

[hide="Another way"]

Most problems like this that have sum of digits can be considered by looking on numbers that are 0 on base 9. So, we look from 9,18,etc.. and immediately, 27 comes to the answer. Then, using logic, it can be seen that 27 is the only answer. But to be full, casework as previous solution is needed. [/hide]


Given that half as many people lived in Toronto as lived in the rest of Ontario, what percent of Ontario's residents lived in Toronto? Express your answer as a mixed number.

Let $ t\equal{}\text{the number of people living in Toronto}$ and $ p\equal{}\text{total number of people in Ontario}.$ We are given $ t\equal{}\frac{p\minus{}t}{2}$ and we get $ 2t\equal{}p\minus{}t\implies 3t\equal{}p.$ That means $ \frac{1}{3}$ of the Ontario's population lives in Toronto. Quickly checking gives $ \frac{2t}{3}\equal{}2\left(\frac{t}{2}\right).$ Finally, $ \frac{1}{3}\equal{}\boxed{33\frac{1}{3}}.$


How many ways can you tile a $3 \times n$ rectangle with $2 \times 1$ dominoes?

Assuming that n is even right?

I bet anything this has to do with recursion.

k lol this is just a guess

ya i think $n$ is even

but if u look at a $3\times 2$ there are only $3$(i'm sure thats correct) ways to put $2\times1$ tiles..so looking at a $3\times4$ you have two $3\times 2$..so that would be $3^{2}=9$..so looking at this we see that for any $n$ we have
$\frac{n}{2}$,$3\times 2$ squares..so the total number of ways is $\boxed{3^{\frac{n}{2}}}$...hmm i have a slight doubt about thsi..but could someone let me know..thx

Um, you can't do that  :roll: You don't have to have two $3 \times 2$ for a $3 \times 4$...

ya i was thinking about that as well..i knew that would factor in somehow..k thx

I could be wrong, but is the number of ways to tile a $3\times (2k)$ board the solution of

$f(k)=4f(k-1)-f(k-2)$ for $k\ge 3$ with $f(1)=3$ and $f(2)=11$?

I could write its explicit form, but its rather ugly.  If this is right, I'll post a solution, so is it?

I don't know the answer, but I think it has to do with Catalan numbers.

Sorry for reviving an old thread.

Yes, zgorkster is correct.  Let $ a_{n}$ be the number of ways to tile a $ 3 \times 2n$ rectangle with $ 1 \times 2$ dominoes and let $ b_{n}$ be the number of ways to tile a $ 3 \times (2n-1)$ rectangle with a corner missing with $ 1 \times 2$ dominoes.

Consider how to tile a $ 3 \times 2n$ rectangle with dominoes, beginning with the left edge.  If we use three dominoes to cover the left edge (which we can do in one way), we're left with a $ 3 \times (2n-2)$ rectangle, which we can cover in $ a_{n-1}$ ways.  If we use two dominoes to cover the left edge (there are two ways to do this), we're left with a $ 3 \times (2n-1)$ rectangle missing a corner, and there are $ b_{n}$ ways to cover this.  Thus $ a_{n}= a_{n-1}+2b_{n}$.

Now, consider how to tile a $ 3 \times (2n-1)$ rectangle missing a corner.  Such a rectangle has one column with only two boxes.  If we cover these two boxes with a single domino (one way), we're left with a $ 3 \times (2n-2)$ rectangle ($ a_{n-1}$ ways).  If we cover them with two dominoes, then in the next column we are left with only one box which we need another rectangle to cover (so, one way) and then we're left with a $ 3 \times (2n-3)$ rectangle missing a corner ($ b_{n-1}$ ways).  Thus $ b_{n}= a_{n-1}+b_{n-1}$, or $ a_{n}= 4a_{n-1}-a_{n-2}$, as zgorkster claimed.

Now we have to eliminate one of the sequences from one of the equations.  Since the thing we really want is $ a_{n}$, I'll re-write the first equation as $ b_{n}= \frac{a_{n}-a_{n-1}}{2}$.  Substituting this into the second equation, we have $ \frac{a_{n}-a_{n-1}}{2}= a_{n-1}+\frac{a_{n-1}-a_{n-2}}{2}$.

[quote=graviton2]I don't understand the above solution to this problem. Could someone explain why the above solution works[/quote]

What part of the solution do you not understand? It would be easier to help you if you told us that at least

I don't understand this part of the solution. Why did JBL consider this to solve the problem?
[quote=JBL]
Now, consider how to tile a $ 3 \times (2n-1)$ rectangle missing a corner.  Such a rectangle has one column with only two boxes.  If we cover these two boxes with a single domino (one way), we're left with a $ 3 \times (2n-2)$ rectangle ($ a_{n-1}$ ways).  If we cover them with two dominoes, then in the next column we are left with only one box which we need another rectangle to cover (so, one way) and then we're left with a $ 3 \times (2n-3)$ rectangle missing a corner ($ b_{n-1}$ ways).  Thus $ b_{n}= a_{n-1}+b_{n-1}$, or $ a_{n}= 4a_{n-1}-a_{n-2}$, as zgorkster claimed.
[/quote]

Call a solution for a $3\times n$ primitive if it is not formed by stacking up solutions for $3\times k$ rectangles for $k<n$.

There are $3$ primitive solutions for $3\times 2$. It is not hard to show by construction, that there are only $2$ primitive solutions for a $3\times 2k$ rectangle when $k>1$.

Now any other solution to the $3\times 2k$ rectangle will consist of a primitive solution to $3\times 2j$ solution stacked on top of an arbitrary solution of the $3\times 2(k-j)$ rectangle.

So if there are $f_k$ solutions in total for $3\times 2k$, then we have:

$f_1=3$ and $f_k=3f_{k-1}+2(f_{k-2}+\cdots+f_1+1)$

We take a difference $f_n-f_{n-1}$ and get

$f_n-f_{n-1}=3(f_{n-1}-f_{n-2})+2f_{n-2}\implies f_n=4f_{n-1}-f_{n-2}$ with base $f_1=3,f_2=11$.

This recurrence can be solved for an explicit formula:

$f_n=\frac{3+\sqrt{3}}{6}(2-\sqrt{3})^{n+1}+\frac{3-\sqrt{3}}{6}(2+\sqrt{3})^{n+1}$

It is amazing to see that there is a closed form solution. Here is my solution in detail.


geometry
inradius
inequalities
geometry solved

show for a point P inside a triangle ABC
PA+PB+PC>=6r
r is inradius of ABC

It's obviously enough to show this for that point P in which PA+PB+PC reaches its minimum.

Case 1: All the angles of ABC <120

Then PA+PB+PC reaches its minimum in Torricelli's pt, for which <APB=<BPC=<CPA=120 deg. This means that \sum PB*PC*31/2/4=S (the area of ABC). PA+PB+PC>=(31/2*4*\sum PB*PC*31/2/4)1/2=(4*31/2pr)1/2>=6r iff p>=3*31/2r, which is well-known (it can be shown by using Jensen and the convexity of cotan, for example).

Case 2: =120. In this case the minimum is reached in A (I think), so we need to show that AB+AC>=6r. I heven't thought about this. Besides, I'm not even sure that the minimum IS indeed reached for P=A.

P.S. p is the semiperimeter.

What a luck to me when I have a tighter inequality !
     PA+PB+PC>=2*( \sum a*m_a)/(a+b+c) (m_a,m_b,m_c is the median of ABC)  (it is proved in [url=http://mathlinks.ro/viewtopic.php?t=3866]Geometry / Proposed and Own Problem / a heavy inequality[/url]).
      Since m_a>=h_a we have our result. :D


geometry
3D geometry
conics
hyperbola
symmetry
LaTeX
number theory unsolved

If $a, b, q = \frac{a^2+b^2}{1+ab}$ are integers, then $q$ is a perfect square.

Well I have seen many solutions of this problem. Most assume to the contrary that q is not a perfect square. Then I see nothing which follows uses this assumption. (In fact I think the 'contradiction' holds even if we assume q to be a perfect square.) Then they choose a and b such that a+b is minimal. Then they proceed further to prove that $b=0$ and $q = a^2$ . In my opinion the proof goes exactly the same way had we assumed that $q$ is a perfect cube, fifth power, etc.

Will we not get the same 'contradiction' if we assumed $q$ to be a perfect square?

Can anyone explain this to me?

This is part of the solution I found in one of Titu's books.

Let q be the number as stated in the problem. We want to show that among all pairs of nonnegative integers $\(a,b\)$ with the property $\frac {a^2+b^2}{ab+1}$ and $ a \le b$, the one with $a+b$ minimal has $b=0$.

But why? Can it be that some other $a$ and $b$ with $a+b$ not minimal have the property that $q$ is not a perfect square?

If you know the solution (or rather, understand the solution), can you please explain everything in detail?

[quote="Lek Huo Tang"]If a, b, q = (a 2 +b 2 )/(ab+1) are integers, then q is a perfect square.

Well I have seen many solutions of this problem. Most assume to the contrary that q is not a perfect square. Then I see nothing which follows uses this assumption. (In fact I think the 'contradiction' holds even if we assume q to be a perfect square.) Then they choose a and b such that a+b is minimal. Then they proceed further to prove that b=0 and q = a 2 . In my opinion the proof goes exactly the same way had we assumed that q is a perfect cube, fifth power, etc.

Will we not get the same 'contradiction' if we assumed q to be a perfect square?

Can anyone explain this to me?[/quote]
Your problem is WRONG, because if $ab+1<0$ then $q$ can not be a square, because is a negative number !!!!

The problem is not wrong. It can be proved that if ab+1 were negative, the resulting fraction can NEVER be an integer.

By the way how did you type those mathematical equations?

There is a solution to this problem in Arthur Engel's book, involving hyperbolas. As has been said, the task is to show that if a solution exists for $q$, then one exists for the same $q$ with $b=0$, in which case $q$ must equal $a^2$. One shows that if a lattice point exists on the upper branch of the hyperbola $x^2+y^2=qxy+q$, then a corresponding point exists directly below it. Then we flip it across the axis of symmetry and repeat until $b=0$.

Arthur Engel also rates it in his book (Problem Solving Strategies) as the hardest IMO problem until 1995. But I think this should probably be in the problem-solving section.

Hmm... Are you kidding? This is a very standart problem for a descent method. And, of course, it can't be the hardest IMO problem (maybe easiest ;) ).
The same thing I can say about IMO95, pr6 (did Engle mean this problem?).

I still don't understand your solution. Can you please explain in detail?

If $ \frac{a^2+b^2}{1+ab} = q$ is an integer, then $q$ is a perfect square.

Can anyone teach me how to use Latex?

Engel meant IMO 1996/5, a geometry problem.

Thank you.

But I saw in some other sites that teach us to use some sort of \begin document  blablabla. What's the difference.

And why is it that your line remains unchanged even when you use $?

[quote="Lek Huo Tang"]I still don't understand your solution. Can you please explain in detail?

If $\frac{a^2+b^2}{1+ab} = q$is an integer, then $q$ is a perfect square.

Can anyone teach me how to use Latex?

Engel meant IMO 1996/5, a geometry problem.[/quote]
You just need to use $ $ when you write formulas.

Then do I need to install anything if I wish to type mathematics equations using Microsoft word? Can I use Latex with Microsoft Word?

And does anyone know how to create PDF files? Is it enough to have only Acrobat Reader?

I believe you should ask such questions in another section.

You need Equation Editor to type equations Word. It comes with standart installation package and you should select it while installing MS Office.

To create PDF you need
1) Adobe Acrobat (not Adobe Reader!). It is a commercial product
OR
2) pdflatex (to make pdf from tex). it comes with Latex distributive.
OR
3) PDFwriter to convert word to pdf.
Probably, thre are other options.


geometry
incenter
analytic geometry
geometry unsolved

Figure, $ I$ is the incenter of △$ ABC$, $ Ge$ is the Gergonne point, $ Na$ is the Nagel point, $ Mi$ is the Mittonpunkt point . $ I', M'$ respectively are the isotomic conjugate of $ I,Mi$ .

Prove that：$ I', M', Ge, Na$ are on a line

We use barycentric coordinates with respect to $ \triangle ABC.$ Then we have

$ I \ (a: b: c) \ , \ M_i \ (a(s \minus{} a): b(s \minus{} b): c(s \minus{} c))$

$ N_a \ (s \minus{} a: s \minus{} b: s \minus{} c) \ , \ G_e  \left ( \frac {1}{s \minus{} a}: \frac {1}{s \minus{} b}: \frac {1}{s \minus{} c}\right)$

$ I'\left ( \frac {1}{a}: \frac {1}{b}: \frac {1}{c}\right) \ , \ M'\left ( \frac {1}{a(s \minus{} a)}: \frac {1}{b(s \minus{} b)}: \frac {1}{c(s \minus{} c)}\right)$

Equation of the straight line $ N_aG_e$ is then

$ N_aG_e \equiv a(s \minus{} a)(c \minus{} b)x \plus{} b(s \minus{} b)(a \minus{} c)y \plus{} c(s \minus{} c)(b \minus{} a)z \equal{} 0$

Now, it's easy to check that coordinates of $ I'$ and $ M'$ satisfy its equation $\Longrightarrow$ $ N_a,G_e,I',M'$ are collinear. Furthermore $ IM_i \parallel N_aG_e,$ since $ IM_i$ and $ N_aG_e$ share the same infinite point $ T_{\infty}$ with barycentric coordinates

$ T_{\infty}(a(b^2 \plus{} c^2 \minus{} ac \minus{} ab): b(a^2 \plus{} c^2 \minus{} ab \minus{} bc): c(a^2 \plus{} b^2 \minus{} ac \minus{} bc)).$


Hi everyone!

The qualification rounds are about to start.  Here is the list of who is playing who:

undefined117 vs. kookamunga

verizonwires vs. fingolfin999

abacadaea vs. desperado

alkjash vs. AIMEman

mathcountsfreak vs. Lawrence Wu

mz94 vs. bball43

michaelwong256 vs. rd5493

RollandWu vs. BOGTRO

The qualification round will consist of two seven-problem normal games.  Setup should look like it is below:
[img]http://aopsftw.googlepages.com/ftwsetup1.png/ftwsetup1-medium;init:.jpg[/img]
 If there is a tie in the number of games one (1-1), then a countdown will decide the winner.  In the normal game, Password can be substituted with the password you and your opponent decide upon.  You must start the game with only your opponent.  Under no circumstances may you allow others to play with you during this tournament.

[b]Scoring[/b]

The scores are based on who won each game, nothing else.

Please record your scores at the end of each game, at least write down who won each game.  When you are done, please enter your results [url=http://aopsftw.x10hosting.com/Forum/viewforum.php?f=7]here[/url].
You must register there first, you must provide a real email address as you need to activate it with it.

Please post Qualification Round scores like this:
Game 1 (Normal) : [Person who won]
Game 2 (Normal) : [Person who won]
Game 3 (Countdown) : [Person who won] ***
***- Game 3 is only if there is a tie in number of wins after the first two games.

If you have any questions, please email me at aopsftw [-at-] gmail dot com OR post at the forum, there is a link in the left sidebar to it.

Please Private Message your opponent via Art of Problem Solving / Mathlinks to decide when to play and the password for your games.

I would like all Qualification Round games to be completed by April 1st.
I have also created my new site, this one will be more reliable than the previous one.  Here is the address to it:
http://aopsftw.x10hosting.com
Emails and PMs about this are being sent right now.
Thank you for your cooperation!
:)

MZ94 VS BBALL43

Game 1 (Normal) : [Person who won] (mz94)
Game 2 (Normal) : [Person who won] (mz94--by cd tiebreaker)
Game 3 (Countdown) : [Person who won] ***
***- Game 3 is only if there is a tie in number of wins after the first two games.

 :lol:

Thanks mz94.
I am adding this to the rules.
If there is a tie anywhere, a countdown will decide.
Examples:
At the end of both normal games, each player won 1 game.  Use a countdown.
At the end of a game, scores are the same.  Use a countdown.
Edit
Forgot to mention this.  I have a news section of the site at
http://aopsftw.x10hosting.com/
Sorry about changing hosts, but this change was worthwhile.  :)

Do you post your results where deperado put them or where mz94 put them? :|

Either is fine, but I prefer you use the forum desperado posted at.
 :)

Well, since I can't seem to find that forum...

_____________________________

RollandWu vs. BOGTRO

Game 1 (Normal): RollandWu
Game 2 (Normal): Tie, RollandWu by CD tiebreaker
Game 3 (CD): N/A

____________________________

WHY'D YOU GIVE ME ROLLAND???

I'm pretty sure that there is a link in my first post to it.
I didn't try to give you Rolland as an opponent, it was just the way I decided to match people.  It was basically random.  I will add this to my site.  Thanks!
:)

Actually, minicon did 1vs. 16, 2vs.15, 3vs. 14, 4vs. 13, 5vs. 12, 6vs. 11, 7vs. 10, 8vs. 9 by order of sign up.

That's correct.
Weren't you supposed to play rd5493 2 hours ago?

hmm. Let the 2 players be A and B.

A won the first game, and they tied in second game.

At last, B won the last cd.

What if this happens?

Should they play another game? (And what if they tied again, and again? hmm that would be fun.)

Then they would have to play a countdown for the third part as it would be tied for the first 2 parts.
A countdown always settles any tie.  This tie could be from a countdown.
:)

Ummmm...
AIMEman still hasn't responded after 4 days...
What should I do?

Sorry H3, D3m0n Shad0w said she would substitute if people couldn't come.  You can be on that list though.  (meaning if another person can't make it, you fill in).
 :|

minicon, if you pm me, don't expect me to respond, because I'm going to be in Taiwan from today at 8:30 pm P.T. to April 7 at 11:00 pm P.T.  I might because my grandfathers place has a computer but I might not stay there.

[quote="michaelwong256"]Please don't make me play #H34N1 if mz94 doesn't come, minicon.[/quote]
lol, once i played him so much he started lagging and i won. he was so mad lol
Hmm...that avatar seems  familiar. Sitan Chen?

RollandWu got the bye? aww, i deserve a bye.

@undefined117 actually it's 1050 vs 1300 :P

Game 1: Lawrence Wu (by cd tiebreaker)
Game 2: Lawrence Wu
Game 3: Lawrence Wu (by cd tiebreaker)
Game 4: not played
Game 5: not played
Final Winner: Lawrence Wu

I think you're supposed to put it on the scores forum.

I've posted it again in the scores forum.

minicon, you said if mz94 doesn't respond in 5 days, I'll get an automatic bye.  Tommorow is the last day, but he responded today to play today or tommorow, but something is telling me that he's not going to play tommorow either.  Will I still get the automatic bye?  Because he did respond.

Today is the fifth day.  mz94 responded but did not play on the scheduled day and time.

Did you include time zones in your message?

Well I said that I would be on the computer until 5:00 P.M. E.T. and to come on whenever.

Take what place?
RollandWu already has a bye and that is settled...

is it too late to sign up? aww.. well i want to play in the next tournament =D

When is the final?
I just want to get it over with...
Because I have no chance against rolland.


Let $M$ be the midpoint of the hypotenuse $AB$ of a right
triangle $ABC$. Prove that the line joining the incenters
of triangles  $ACM$  and  $BCM$  bisects the area of triangle
$ABC$.

[u] Babis[/u]

Let $a = [BC], b=[AC], c = [AB]$ be sides and $p = \tfrac{1}{2}(a+b+c)$ semiperimeter of the C-right $\triangle ABC$.
Let $K, L, M$ be midpoints of $[BC], [CA], [AB].$ Let $I_a, I_b$ be incenters of $\triangle AMC, \triangle BMC$ and let $I_aI_b$ cut $BC, AC$ at $P, Q$.
$\triangle AMC, \triangle BMC$ are both M-isosceles with areas $[AMC] = [BMC] = \tfrac{1}{2} [ABC] = \tfrac{1}{4}ab$, semiperimeters $p_a = \tfrac{1}{2}(c+b)$, $p_b = \tfrac{1}{2}(c+a)$ and inradii

$r_a = [I_aL] = \frac{[AMC]}{p_a}= \frac{ab}{2(c+b)},\ r_b = [I_bK] = \frac{[BMC]}{p_b}= \frac{ab}{2(c+a)}.$

$[MI_a] = [ML] - [I_aL] = \tfrac{1}{2}a - r_a = \frac{ac}{2(c+b)}$ and similarly, $[MI_b] = \frac{bc}{2(c+a)}$.

$[CP] = [CK] + [KP] = [CK] + \frac{[MI_a]}{[MI_b]} \cdot [KI_b] = \tfrac{1}{2}a + \frac{a}{b} \cdot \frac{c+a}{c+b} \cdot r_b =$ $\tfrac{1}{2}a + \frac{a^2}{2(c+b)} = \frac{ap}{c+b}$ and similarly, $[CQ] = \frac{bp}{c+a}$.

$2 [PQC] = [CP] \cdot [CQ] = \frac{abp^2}{(c+a)(c+b)} = \frac{abp^2}{c^2 + bc + ca + ab} =$ $\frac{2abp^2}{a^2 + b^2 + c^2 + 2bc + 2ca + 2ab} = \frac{2abp^2}{4p^2} = \tfrac{1}{2}ab = [ABC]$.


Pentru inegalitatea $\ (2)$ mai puteam folosi si spargerile cu medii si stabileam relativ usor inegalitatea $\frac{a^{3}}{a^{2}+ab+b^{2}}\geq\frac{2a-b}{3}$ si bineinteles analoagele, care adunate dau inegalitatea noastra.

Si ultima inegalitate iese cu "metoda Stormraven" :D

Cauchy: \[\sum_\textrm{cyc}\frac{a^{4}}{\left( a^{2}+b^{2}\right) (a+b)}\cdot \sum_\textrm{cyc}\left( a^{2}+b^{2}\right) (a+b) \geq \left( \sum_\textrm{cyc}a^{2}\right)^{2},\] deci este suficient sa demonstram \[\left( \sum_\textrm{cyc}a^{2}\right)^{2}\geq \frac{a+b+c}4 \cdot \sum_\textrm{cyc}\left( a^{2}+b^{2}\right) (a+b)\]  \[\, \Longleftrightarrow \, \, \sum_\textrm{sym}a^{4}+3 \sum_\textrm{sym}a^{2}b^{2}\geq 3 \sum_\textrm{sym}a^{3}b+\sum_\textrm{sym}a^{2}bc .\] $\left( \star \right) \, \, \, \sum_\textrm{cyc}(a-b)^{4}\geq 0 \, \, \Longleftrightarrow \, \, \sum_\textrm{sym}a^{4}+3 \sum_\textrm{sym}a^{2}b^{2}\geq 4 \sum_\textrm{sym}a^{3}b$.

$\left( \star \star \right) \, \, \, \sum_\textrm{sym}a^{3}b \geq \sum_\textrm{sym}a^{2}bc$ (iese cu Muirhead / AM-GM)

$\left( \star \right)+\left( \star \star \right) =$ soluţie.

Ma simt magulit :D
Felicitarile mele pentru rezolvare.
Probabil ca nu am gasit-o pentru ca nu stiu Muerhead (inca... :D ). Felicitari inca o data  :clap:

[quote="Mircea Lascu"]Fie $a,b,c>0$. Aratati ca:
\[\frac{a^{4}}{ab(a+b)}+\frac{b^{4}}{bc(b+c)}+\frac{c^{4}}{ac(c+a)}\geq\frac{a+b+c}{2}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{(1)}\]

[/quote]

ca s-au tot dat mai multe solutii pt 2 si 3 mai dau si eu una pt 1, cam asemanatoare dar nu prea aveam ce face :)

deci avem :

$\frac{a^{4}}{ab(a+b)}+\frac{b^{4}}{bc(b+c)}+\frac{c^{4}}{ac(c+a)}\geq  \frac{(a^{2}+b^{2}+c^{2})^{2}}{ab(a+b)+bc(b+c)+ca(c+a)}$

si ne ramane se dem:

$\frac{(a^{2}+b^{2}+c^{2})^{2}}{ab(a+b)+bc(b+c)+ca(c+a)}\geq  \frac{a+b+c}{2}$

$\Rightarrow 2\cdot (\sum{a^{2}})^{2}\geq  2\cdot \sum{a^{2}b^{2}}+\sum{a^{3}b}+\sum{ab^{3}}+2\cdot \sum{a^{2}bc}$

$\Rightarrow 2\cdot \sum{a^{4}}+4\cdot \sum{a^{2}b^{2}}\geq  2\cdot \sum{a^{2}b^{2}}+\sum{a^{3}b}+\sum{ab^{3}}+2\cdot \sum{a^{2}bc}$

$\Rightarrow 2\cdot \sum{a^{4}}+2\cdot \sum{a^{2}b^{2}}\geq  \sum{a^{3}b}+\sum{ab^{3}}+2\cdot \sum{a^{2}bc}$

dar $2 \cdot \sum{a^{4}}\geq  \sum{a^{3}b}+\sum{ab^{3}}$ conform muirhead $(4,0,0) \succ (3,1,0)$

deci ne ramane sa dem:

$\sum{a^{2}b^{2}}\geq  \sum{a^{2}bc}$, evident adevarata. (e echivalenta cu $\sum{x^{2}}\geq  \sum{xy}$ pt $x=ab, y=bc, z=ca$)


[quote="miyomiyo"]How long is the shortest string of digits that contains ever number from 1 to 999?
For example: 28199 contains 2, 8, 1, 9, 28, 81, 19, 99, 281, 819, and 199.[/quote]
If we have every 3 digit number, we automatically have every 2 digit and 1 digit numbers
then the minimum is 902 :?:

[quote="CircleSquared"]If we have every 3 digit number, we automatically have every 2 digit and 1 digit numbers
then the minimum is 902 :?:[/quote]
You are right but..

You want anywise the number 100, right?

So necessarily, will appear a number $ 00x$ (x is the digit that you put after 100). There are totally 9 such numbers
Such or else you have to put some digit after $ 00$, so put the numbers $ 1,2,..,9$ each of them once (for the sake of symmetry)

When you count '902' digits, you don't count all these cases that necessarily exist

Similarly, you put the number 560, so there is some number $ 0xy$. There are totally 81 such numbers (excluding the previous 9)

Thanks [b]pontios[/b], that was an interesting process.


A professor is assigning grades to a class of 10 students. As a very kind professor, he only gives out A's, B's, and C's. How many ways can the professor assign grades to all his students?

what a great reason to revive a post over a year old...

[quote=gauss1181]3 grades are possible for each of the 10 students, so there are a total of $ \boxed{3^{10}}$ ways the grades can be assigned.[/quote]
[hide=Which equals...]
$\boxed{59049}$

@MathArt4,

Hide your answers. Even though someone else wrote it, you need to hide answers.

[quote=elevate]This really shouldn't be a level 19 problem and give out 100+ points...[/quote]

it is a level 10 problem now.

Also, i didn;t know u could enter 3^10 as an asnwer

[quote=Natsuki]What does "j00 r t3h 1337" mean? I got it from this problem![/quote]

Correctly answer a problem at 13:37 server time.


Well, as the Poincaré Conjecture is not a Conjecture anymore, you'll have to change that name in the stars....

It is a conjecture until it's proved that the demostration has no mistakes

And even then... some proven conjectures are still so called sometimes.

But I see some other problem: who will get the Millenium Prize for it...

Speaking of which, isn't Kepler's Conjecture now proven?

To Leopoldo: It's proved

To ZetaX: Well, it's wrong to do that

The demostration has to be revised so you can't consider that's it's proved.
The first time Wiles sayd that he proved Fermat he didn't, when they revised it they found that there was a mistake, here can happen the same, it's very common with this kind of problem so it's still a conjeture and not a theorem

I don't know actually, I only know because of [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=90195]what I've seen here[/url]


function
calculus
derivative
trigonometry
complex analysis
complex analysis unsolved

The problem is this:

Find all entire functions [i]f[/i] that satisfy

                [i]f''[/i](1/n)+[i]f[/i](1/n)=0

for all n such that n is a positive integer.

_______________
I started by assuming [i]f[/i] has a power series expansion, such that

                 [i]f[/i](z)=SUM{(A_n)*z^(n)}.

I then took the double derivative of this expansion, added the power series expansions of [i]f''[/i](z) and [i]f[/i](z), then plugged in 1/n. i tried to look for a power series expansion i recognized, but i couldn't...so i'm guessing there's something wrong with my approach? shouldn't i be able to recognize e^(z)? and for that matter, cos(z) and sin(z) as well?

any help is appreciated! thanks a bunch.

No need to restrict the analysi to $ \frac{1}{n}$.

Since $ f$ is an entire function, $ \minus{}f$ and $ f''$ must be entire functions as well. Since they coincide for the convergent series $ \frac{1}{n}$ they coincide everywhere, i.e. we have $ \forall z\in\mathbb{C}\,: \,f''(z)\plus{}f(z)\equal{}0$ and the solution space is generated by $ \sin z$ and $ \cos z$


function
number theory solved
number theory

Let $f: N \rightarrow N$ be function satisfying:
$f(1)=f(2)=1$; $\displaystyle f(n)=f([\frac {n}{2}])+f([\frac {n+1}{2}])$; $\forall n \geq 3$.
Find the value of $\displaystyle S=\sum_{k=1}^{2004}f(k)$.

It's easy to see the pattern in the values of $f$, but I'm too lazy to actually compute the value asked.

We have blocks of numbers of the form $\frac {2^n+2^{n+1}}2,\ldots,2^{n+1}$ for which $f$ takes the value $2^n$, and in between those blocks it takes consecutive values. This means that it's enough to count those blocks containing numbers which are smaller than $2004$ and then it's easy.


As I noted in [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=534505]this thread[/url], these questions have traditionally gone in the Puzzles subforum.  They are also poorly conceived, since I can construct a "pattern" (such as a polynomial) which produces those values in order, no matter what "those values" happen to be.

If the sequence is $\{a_n\}_{n=1}^{\infty}$, then it satisfies the recurrence formula

$(1) \; a_n = 7(a_{n-1} - 1) + n$

for $3 \leq n \leq 7$ where $a_1 = 0$ and $a_2 = 2$. The formula (1) is not valid for n=2 since that requires that $a_1=1$.

i think it will have an equation of the form (exponential) or factorial will be included because the sequence diverges fast,
or does it even have an nth term?
  f(n)   0     2    10     67     467       3268         22876
  1dif     +2    +8   +57  +400    +2801       +19608
  2dif        +6   +49   +343  +2401    +16807
  3dif         x(49/6) x7       x7       x7

[quote="unknown_pattern18"]
  2dif        +6   +49   +343  +2401    +16807[/quote]

Well, isn't this annoying.  Every term except the first is a power of $7$.  What a horrid little problem  :|

this equation works up to the 4th term

U=((43/6)n^3)-(40(n)^2)+((431/6)n)-9

Obviously my first comment didn't stick ....  A polynomial of 3rd degree can be used to match any 4 data points.  You have 7 data points, so there exists a unique polynomial of 6th degree which will give those 7 values.

but... that shouldn't prevent the people participating in the thread to construct sequences that fit the problem

also, the polynomial that would match the data points hasn't been given either yet

1dif +2 +8 +57 +400 +2801 +19608
2dif +6 +49 +343 +2401 +16807
3dif x(49/6) x7 x7 x7

if we ignore the x(49/6) in the 3dif and imagine it was times 7
then the equation for the 1difference is ((7^n)-1)/6=U

but how do we get from the 1diff to the sequence,what do we do with this ((7^n)-1)/6=U to give us the nth for the sequence.

If the first differences are given by $\Delta(n)$, then the function itself is given by $f(n) = f(0) + \sum_{i=0}^{n-1}\Delta(i)$ (where the indexing may be different from your own).

what would happen if we remove 0 from the sequence and put 1 instead,
what would be the nth term for this sequence ?
1, 2, 10, 67, 467, 3268, 22876

if we remove 0 from the sequence,and put 1 instead then the 3diff will all be the same, times 7

lets forget 0, and suppose 1 is the first term
what will be the nth term.

[quote="unknown_pattern18"]what would happen if we remove 0 from the sequence and put 1 instead[/quote]

[quote="Solar Plexsus"]If the sequence is $\{a_n\}_{n=1}^{\infty}$, then it satisfies the recurrence formula

$(1) \; a_n = 7(a_{n-1} - 1) + n$[/quote]

The $n^{th}$ term is fairly basic to find from here.  I'll leave it as an exercise to anyone who wants to try.

no one there to find the nth term ?
t0rajir0u can u solve it for us plz

how come, no one can find the nth term for a simple sequence?

the nth term for the sequence below
1, 2, 10, 67, 467, 3268, 22876
is it that hard or ?

[quote="unknown_pattern18"]find the nth term for the sequence

0,   2,   10,   67,   467,   3268,   22876

let me know if i posted it in the right place[/quote]

Is there a source for this question or did you create this question.


geometry
circumcircle
congruent triangles

Let $ AD$ be a median of triangle $ ABC$. Let the point $ E$ lie on $ AD$ (extended if necessary) such that $ CE$ is perpendicular to $ AD$. Suppose that angle $ ACE \equal{}$ angle $ ABC$. Prove that either $ AB \equal{} AC$ or angle $ BAC$ is a right angle.

Did you get this problem from the same place as your digits and divisibilty one?

If I'm right then, these problems are from a recent exam at a British training camp, where is the third?

The third one is quite long: I'll post it in this forum soon. (Perhaps it should go into the Advanced Section?)

[hide="Solution"]Draw the circumcircle of $ ABC$. By alternate segment theorem, the angle between $ CA$ and the tangent at $ A$ is equal to angle $ ABC$, which the question told us was equal to angle $ ACE$. By the converse of alternate angles, the line $ CE$ and the tangent at $ A$ are parallel. Since $ CE$ is perpendicular to $ AD$, the tangent is perpendicular to $ AD$. The line from the point of tangency which is perpendicular to the tangent passes through the centre $ O$, so $ O$ lies on the line $ AD$. Now we have two cases to consider:

Case 1: $ O$ is distinct from $ D$.

In this case, since $ AD$ (which we now know passes through $ O$) bisects $ BC$, they are perpendicular (the line through the centre which bisects a chord is perpendicular to said chord). We have two congruent triangles $ ADC$ and $ ADB$ (SAS) so $ AC \equal{} AB$. Interestingly in this case, $ D$ and $ E$ are the same point.

Case 2: $ O$ lies on $ BC$ (and so is point $ D$).

In this case, $ BC$ is a diameter of the circle, so by Thale's theorem, angle $ BAC$ is a right angle.[/hide]

Thanks KrazyFK; I've put the third one in the Advanced Section: Algebra Unsolved Problems, under the title Regions.


invariant
number theory
least common multiple

Consider $n$ positive integers $a_{1}, \ldots, a_{n}.$ Any two numbers $a_{i}$ and $a_{k}$ with $i < k$ can be changed as follows: $a_{i}$ is replaced by $gcd(a_{i},a_{k})$ and $a_{k}$ is subsituted by $lcm(a_{i},a_{k}).$ Prove that the sequence is changed only a finite number of times.

Consider $P(a_{1},\ldots,a_{n})=\prod_{i=1}^{n}a_{i}^{i}.$. Since $\gcd(a,b)<\text{lcm}(a,b)$ for $a\not=b$, $P(a_{1},\ldots,a_{n})$ can only increase. To have $P$ not increase in a step, we need $a_{i}^{i}a_{k}^{k}=f(a_{i})^{i}f(a_{k})^{k}$, since $i<k$, $f(a_{i})\le a_{i}$ and $f(a_{k})\ge a_{k}$, this is only possible when $f(a_{i})=a_{i}$ and $f(a_{k})=a_{k}$. So to have the sequence change, $P$ must increase. But $P$ can only increase a finite number of times (since $P\le\prod a_{i}^{n}$). So the process ends in a finite number of steps.


Hint: The diagonals of a rhombus are orthogonal and bisect each other. Use this fact to split the rhombus into four 3-4-5 right triangles.

I know the correct answer and I knwo what I think it is. What do you think it is?? :roll:

[quote="j2009d"]Tell me what you think the answer is. I am confused. I got one answer, but the answer key said something else.

There is a rhombus with side lengths of 10 and 1 diagonal of length of 12 inches. What is the length of the other diagonal?

Plz help me understand this! :idea:  :lol:[/quote]

Draw a rhombus and draw the diagonals. Remember that the diagonals of a rhombus bisect each other, and let the unknown diagonal be $ 2x$.  When they bisect, they form $ 4$ right triangles with side length $ 6$ and $ x$.  The side length is $ 10$, so using Pythag. Triples, $ x \equal{} 8 \implies 2x \equal{} \boxed{16}$

:rotfl:
I got 16 too and with the same reasoning. I am 99% sure thats the right answer
BUT the answer key says 8 :o
I don't understand. Can you try to figure it out?

[quote="j2009d"]BUT the answer key says 8 :o [/quote]

No it doesn't; it says $ \boxed{16}$

I guess my coach had a wrong answer key.
I got no school tomorow, but I'll recheck it on Monday.
Thanks for helping me out.

You can see the answers on MATHCOUNTS' website you know...

I didn't bother to check... :blush:
I guess I should have done that to make sure. I just figured the answer key I ahd was right. :rotfl:  :rotfl:


calculus
integration
trigonometry
calculus computations

Hey all!! first post here. I'm a college Junior at the University of Texas. I'm an economics major and a business minor and have to take 2 more semesters of calculus. I'm currently taking M408L here. Got a few questions on definate integrals. Hope to stay here a while and learn and hopefully help out when I can ;)

[img]http://show.imagehosting.us/show/687020/0/nouser_687/T0_-1_687020.jpg[/img]
for 16 i got #5

and for 18 i got #2

thx!

You got them both:

1) Let $u=2x$, then we have $4\int_0^3 f(2x) \ dx = 2\int_0^6 f(u) \ du = 2(8) = 16$

2) Let $u = 5-t^3 \Rightarrow du = -3t^2 \ dt$, and then we have $-\frac{1}{3}\int \sin u \ du = \frac{\cos(5-t^3)}{3} + C$


calculus
geometry
similar triangles
Pythagorean Theorem

A 12m ladder leans across a 5m fence and touches a high wall located 3m behind. Find the distance X from the ladder base to the fence bottom.

If a moderator would kindly move this...
Does this question need calculus? I'm sure it could be solved with some geometry but I can't think of anything right now. :wallbash:

It's not a calculus problem, but it's definitely too hard for where it was.

Call z the distance from the bottom of the ladder to the fence, then by similar triangles and pythagorean theorem, $\frac{\sqrt{z^2+25}}{12}=\frac{5}{\sqrt{144-(z+3)^2}}$. Solve for z, and then $x=z+3$.

[hide="hint"]this is just a similar triangles problem[/hide]
[hide="some steps"]say the height touching the wall is h, and the distance from the ladder touching the ground to the fence is d, then

$\frac{h}{5}=\frac{3+d}{d}$ and $12^2=h^2+(d+3)^2$ solve for $d$[/hide]

Why do I never see similar triangles in questions?And we just did a chapter on this at school. :roll:

[quote="uran"]It seems to me that both hints lead to proper equation of 4th degree or something similar :?[/quote]

You're right, and as far as I can tell, it can't be factorized in $\mathbb{Z}[x]$

Thanks [b]Farenhajt[/b]!  :lol:
Your comment makes me think that we don't have all required information.
If $5+y$ is height of the wall, and $3+x$ is distance from ladder base to the wall, then we have $(5+y)^2+(3+x)^2=12^2$ and it is obvious that this equation has infinite number of positive real solutions.

My guess is that [b]babycafe521[/b] forgot to type height of the wall  :?

Most probably - and that WOULD make it a Getting Started problem.

Maybe it's a question that the teacher expects them to use a graphing calculator on?


function
algorithm
search
LaTeX
linear algebra
matrix
geometry

Hello all,  Has any1 taken part in the INOI 2009? If yes, how was your paper? And when would the results be out?? :lol:

its no use to sit on a computer for you wont be able to view it
 :rotfl:

:)

as a matter of fact... sitting in front of the computer would not have been any more useful than sitting on the computer!!

[quote="keshav_57"]I appeared for INOI 2009
No idea about when the results will be out..

My paper went just moderate...
Would have been much much better had I been sitting on a computer instead of a box![/quote]

Did your programs run properly??

[quote="keshav_57"]thr is this thing they do for 'security'
that once u close a program... u cant reopen it...

now they didnt tell this to us at the start...
so once i finished with a problem for once.. i closed it..
wasted abt 15 mins trying to open it later...!!
then i tried to do both problems without closing any..
which gave a compilation error... as obviously their was multiple declaration of 'main' function

then i declared an integer array (int arr[100000]) which again gave an error which i didnt understand... bcoz array size of 100000 is allowed if im not mistaken..

and then there was the keyboard.. which rested only halfway on the desk...
so it kept 'tilting' if i typed numbers on the right side..[/quote]

What could be the cutoff this time?

Hi guys I wrote INOI at chennai. Which centers are you guys from? Here they didnt impose any such restrictions regarding not being able to open ur file once u closed it etc. I attempted both the questions but i am doubtful regarding both. I am at a complete blank for the second question ( game with two bowls and score decided by $ f(x)\equal{}A x^{2} \plus{} B y^{2} \plus{} C xy$ , etc..) Any one got the solid algorithms for either of the problems.

[quote="phinfinity"]Hi guys I wrote INOI at chennai. Which centers are you guys from? Here they didnt impose any such restrictions regarding not being able to open ur file once u closed it etc. I attempted both the questions but i am doubtful regarding both. I am at a complete blank for the second question ( game with two bowls and score decided by $ f(x) \equal{} A x^{2} \plus{} B y^{2} \plus{} C xy$ , etc..) Any one got the solid algorithms for either of the problems.[/quote]

Yeah!

I did the 1st one...

Acc to me the algo can be sumthing like:

1.enter 2 arrays 1 given[] and other needed[]
2. search 4 1st element of needed[] in given[]
3. make that element reach the zeroth memory pos. by decrement by 1 successively
4. now split the array given[] into two arrays with current elment being the boundary.
5. make that array=given[]
6. ++count
7.repeat steps 1 to 6.
8. cout<<count;

@Sybarite
your code for 1st problem will suffice for array size <= 10,000
but not for n = 100,000, it will exceed time limit
bcoz the algorithm takes time proportional to $ n^2$, and just keep this in mind...
keep the calculations to $ \le 10^8$

however... even i gave the same solution
:)

@phinfinity
for the 2nd problem... use recurrence...
let m be number of beads in first bowl, and n be number of beads in second bowl
val[m][n] = score for m, n beads

if (m, n > 0)
  if (m+n) even // ur move
     val[m][n] = a*m^2 + b*n^2 + c*m*n + max(val[m-1][n+1], val[m][n-1])
  if (m+n) odd // opponents move
     val[m][n] = a*m^2 + b*n^2 + c*m*n + min(val[m-1][n+1], val[m][n-1])
else
  only one possible move..

i didnt use latex.. coz i think latex here would actually make it tougher to read..

@Keshav

Have you made both the probs?? :o

That cud be enough to clear the cutoff, i guess. :lol:

Keshav, u rock man.
U will egt selected to both the TCs.{IMOTC as well as IOITC}.

i guess my solution for the 1st prob will solve 90% test cases ar n <= 6000 for them
and again im guessing my second solution to be correct..

but u never know...
its only when u actually check ur problems on a large number of input that u can figure out whether or not ur solution has unforeseeable errors..

btw... acc. to me... my chances for IOITC are much better than my chances for IMOTC..
id be really disappointed with myself it i dont make it to atleast one camp..
n id be sky high if i make it to both!!

again.. hoping for the best..
:)

Srivatsan1991, are u the B Srivatsan of Chennai who went to IOI  the past 2 years? Its great to have the past medallists here.

For schools where ZCO is not organised, and where there are not too many participants, how do we participate? And where did you guys prepare from? :huh:

There shouldn't be much difficulty in registering for ZCO even if it is not conducted officially in your school. The details will be given in the site [url]http://www.iarcs.org.in[/url] at the appropriate time.

The same site has the questions of the previous years olympiad (all levels ). Practicing from them alone should be enough to clear the ZIO and INOI provided that you are good at logical reasoning.

Thanks bro! I had already checked the site. I guess now that I'm an aops I'll automatically know when the registrations open next year. :p And as far as logical reasoning is concerned, I'm not too bad I guess :)

will there be a class wise cut-off ??
12thies will get screwed then !! :P
how many from 12th r they selecting ??

observing what the selections were from ZIO....
i do not expect a different cut-off for class 12...
acc. to me... it will be the same for all...

but i do not know this from nywhr...
im just saying what i expect it to be...

any guesses how much an O(N*N*N) wud fetch for the first  1 ??
(not much i know .......but still... :P)

N cube??
nothing...
coz it will work only if n <= 300
the question said n <= 6000 for 90% of the cases...
i wudnt expect more than one test case with n <= 300

thanx...
watch out at the ICO server..
i might overtake you
:P

results out..  :jump: woohoo!!! :jump: i made it... :jump:

this the answer i could come up with

#include<iostream>
using namespace std;

int f(int x, int y,int A,int B,int C){
    return A*x*x +B*y*y + C*x*y;
}
int main(){
    int x,y,a,b,c,score=0;
    cin>>x>>y>>a>>b>>c;
    score+=f(x,y,a,b,c);
    H:
    while(x!=0 && y!=0){
        if((x+y)%2==0){
            if(f(x-1,y+1,a,b,c)>f(x,y-1,a,b,c)){
                score+= f(x-1,y+1,a,b,c);
                if(x>0){
                    x--;
                    y++;
                }
            }
            else{
                score +=f(x,y-1,a,b,c);
                if(x>0)
                y--;
            }

        }
        else{
             if(f(x-1,y+1,a,b,c)<f(x,y-1,a,b,c)){
                score+= f(x-1,y+1,a,b,c);
                if(x>0){
                    x--;
                    y++;
                }
            }
            else{
                score +=f(x,y-1,a,b,c);
                if(y>0)
                    y--;
            }

        }
    }

        if(x!=0){

                score+= f(x-1,y+1,a,b,c);

                x--;
                y++;

                goto H;

                }

        while(y!=0){
            score +=f(x,y-1,a,b,c);
            if(y>0)
                y--;

        }
  cout<<score;
}


Let G be a graph with v vertices. Show that if each vertex has degree at least $v/2$, then $G$ has a Hamiltonian cycle.

[quote="t0rajir0u"]Is graph theory really an Intermediate topic?   :|[/quote]

Well I've seen it on what I would call intermediate-level problems... this one is pure pigeonhole.

A Hamiltonian cycle is just a path that "hits" all vertices exactly once.

this follows imediately from Ore's thm.
if you dont know that, then the following is a sketch of a solution.
first, since the degree of each vertex is at least $\frac{v}{2}$ then the graph is connected.
now define $P=v_{0}...v_{n}$ to be the maximum path.
since $P$ is maximal, then at least $\frac{v}{2}$ of the verticies $v_{0},v_{1},...,v_{n-1}$ are adjacent to $v_{n}$ and $v_{i}v_{n}$ is an edge for at least $\frac{v}{2}$ of these verticies. By pigeonhole, there exists a $v_{i}$ that has both properties, and from there its easy that graph must contain a hamiltonian cycle.


function
integration
calculus
calculus computations

Does exist $f$:$[1,+\infty[\rightarrow [1,+\infty[$ continous such that $\int_{1}^{+\infty}\frac{f(t)}{\sqrt{t}}dt <+\infty$ and $g(t)=\sqrt{t}f(t)$ is increasing ?

No, no such function. The condition implies that $f(t)\ge\frac C{\sqrt{t}}$ and that makes the integral diverge.


For each positive integer $n$, let
\begin{eqnarray*} S_n &=& 1 + \frac 12 + \frac 13 + \cdots + \frac 1n, \\ T_n &=& S_1 + S_2 + S_3 + \cdots + S_n, \\ U_n &=& \frac{T_1}{2} + \frac{T_2}{3} + \frac{T_3}{4} + \cdots + \frac{T_n}{n+1}. \end{eqnarray*} Find, with proof, integers $0 < a, b,c, d < 1000000$ such that $T_{1988} = a S_{1989} - b$ and $U_{1988} = c S_{1989} - d$.


Prove that for $ x,y,z>0$,

$ \frac{x}{(x\plus{}y)(x\plus{}z)}\plus{}\frac{y}{(y\plus{}x)(y\plus{}z)}\plus{}\frac{z}{(z\plus{}x)(z\plus{}y)}\leq \frac{9}{4(x\plus{}y\plus{}z)}$.

[hide="I hope this is right"]Inequality is homogeneous, so let $ x\plus{}y\plus{}z \equal{} 1$. Then $ x\plus{}y \equal{} 1\minus{}z$, etc. Multiply through by $ (1\minus{}x)(1\minus{}y)(1\minus{}z)$.

$ \sum x(1\minus{}x) \leq \frac{9}{4} (1\minus{}x)(1\minus{}y)(1\minus{}z)$

Expanding the LHS and RHS gives.

$ 1 \minus{} \sum x^2 \leq \frac{9 (\sum xy \minus{} xyz)}{4}$

Now the simplifying starts.

$ 1 \minus{} \sum x^2 \minus{} 2 \sum xy \leq \frac{\sum xy \minus{} 9xyz}{4}$

$ 1 \minus{} (x\plus{}y\plus{}z)^2 \equal{} 0 \leq \frac{\sum xy \minus{} 9xyz}{4}$

$ 9xyz \leq xy \plus{} yz \plus{} zx$

$ 9 \leq \frac1x \plus{} \frac1y \plus{} \frac1z$

$ \frac{3}{\frac1x \plus{} \frac1y \plus{} \frac1z} \leq \frac{1}{3} \equal{} \frac{x\plus{}y\plus{}z}{3}$, true by AM-HM.[/hide]

$ < \equal{} >$
$ 2(xy \plus{} yz \plus{} zx)/[(x\plus{}y)(y\plus{}z)(z\plus{}x)]<\equal{} 9/4(x\plus{}y\plus{}z)$
$ < \equal{} >$
$ 8(xy \plus{} yz \plus{} zx)(x\plus{}y\plus{}z)<\equal{}9(x\plus{}y)(y\plus{}z)(z\plus{}x)$
$ < \equal{} >$
$ x(y^2 \plus{} z^2) \plus{} y(x^2 \plus{} z^2) \plus{} z(x^2 \plus{} y^2) >\equal{}6xyz$
which is true by AM-GM . QED

my sollution ..

[hide]Let $ x\plus{}y\equal{}a, y\plus{}z\equal{}b, z\plus{}x\equal{}c \equal{}> x\plus{}y\plus{}z\equal{}\frac{a\plus{}b\plus{}c}{2}$

The inequality become :

$ \frac{x}{a \cdot c}\plus{} \frac{y}{a \cdot b} \plus{} \frac{z}{b \cdot c} <\equal{} \frac{9}{2 \cdot (a\plus{}b\plus{}c)}$

$ 2 \cdot x \equal{} a\plus{}c\minus{}b$ and so on . $ \equal{}>$

$ \frac{a\plus{}c\minus{}b}{a \cdot c} \plus{} \frac{a\plus{}b\minus{}c}{a \cdot b} \plus{} \frac{b\plus{}c\minus{}a}{b \cdot c} <\equal{} \frac{9}{a\plus{}b\plus{}c}$

So we have to proove that : $ \frac{a^2\plus{}2ac\plus{}c^2\minus{}b^2}{a \cdot c} \plus{} \frac{a^2\plus{}2ab\plus{}b^2\minus{}c^2}{a \cdot b} \plus{} \frac{b^2\plus{}2bc\plus{}c^2\minus{}a^2}{b \cdot c} <\equal{} 9$ which is equal to :

$ \frac{a}{c}\plus{}2\plus{}\frac{c}{a}\minus{}\frac{b^2}{ac} \plus{} \frac{a}{b}\plus{}2\plus{}\frac{b}{a}\minus{}\frac{c^2}{ab} \plus{} \frac{b}{c}\plus{}2\plus{}\frac{c}{b}\minus{}\frac{a^2}{bc}<\equal{}9$

($ \frac{1}{a}\plus{}a<\equal{}2$)

The inequality become :

$ \frac{b^2}{ac} \plus{} \frac{c^2}{ab} \plus{} \frac{a^2}{bc} <\equal{} 3$

With the inequality of rearangements

let $ a<b<c \equal{}> a^2<b^2<c^2, \frac{1}{ab}>\frac{1}{ac}>\frac{1}{bc}$.

So $ \frac{a^2}{bc} \plus{} \frac{b^2}{ac} \plus{} \frac{c^2}{ab}<\frac{a^2}{ab}\plus{}\frac{b^2}{bc}\plus{}\frac{c^2}{ac}$

So all we gotta do now its to show that : $ \frac{a}{b}\plus{}\frac{b}{c}\plus{}\frac{c}{a}<3 <\equal{}> a^2c\plus{}b^2a\plus{}c^2b <\equal{} 3abc$ (which can be proven by doing AM-GM inequality [/hide]

If we were to write up a formal proof, would it be more appropriate to write these steps in reverse order?

(Starting with the AM-GM step and finishing with the inequality in in the question)

I think that it is acceptable to write out proofs "in that order" as long as you maintain reverse implications throughout the proof. Often people like to put question marks over (in)equalities and show that they hold.

[hide]$ \implies \frac{2(xy\plus{}yz\plus{}zx)}{(x\plus{}y)(y\plus{}z)(z\plus{}x)} \le \frac{9}{4(x\plus{}y\plus{}z)}$

$ \implies 8(xy\plus{}yz\plus{}zx)(x\plus{}y\plus{}z) \le 9(z\plus{}y)(y\plus{}z)(z\plus{}x)$

$ \implies 8(3xyz\plus{}\sum_{\text{cyclic}}x^2y) \le 9(2xyz \plus{} \sum_{\text{cyclic}}x^2y)$

$ \implies 6xyz \le \sum_{\text{cyclic}}x^2y$
which is true from AM-GM.[/hide]

[quote="chickendude"]If we were to write up a formal proof, would it be more appropriate to write these steps in reverse order?[/quote]
I haven't read any of the posts in question, but the answer is an unequivocal yes: writing proofs the way you discovered them ([i]especially[/i] inequalities) runs a strong risk of making the (incorrect!) argument, "X implies something true, therefore X is true."  It's much clearer and less error-prone to present your proof beginning with true things and then working your way to your conclusion.

[quote="E^(pi*i)=-1"]Prove that for $ x,y,z > 0$,

$ \frac {x}{(x \plus{} y)(x \plus{} z)} \plus{} \frac {y}{(y \plus{} x)(y \plus{} z)} \plus{} \frac {z}{(z \plus{} x)(z \plus{} y)}\leq \frac {9}{4(x \plus{} y \plus{} z)}$.[/quote]
[hide="Solution"]We can rewrite this problem into:
\[ \sum_{cyc}\frac {x(x \plus{} y \plus{} z)}{(x \plus{} y)(x \plus{} z)}\leq \frac 94;\]
Or equivalently
\[ \sum_{cyc}\frac {yz}{(x \plus{} y)(x \plus{} z)}\geq \frac 34\]
But
\[ \sum_{cyc}\frac {yz(y \plus{} z)}{(x \plus{} y)(y \plus{} z)(z \plus{} x)}\geq \frac 34;\]

\[ \iff 4\sum_{sym}x^2y\geq 3\sum_{sym}x^2y \plus{} 6xyz;\]

\[ \iff \sum_{sym}x^2y\geq 6xyz;\]
Which is a direct application of the AM-GM inequality.[/hide]
Edit: Sorry for reviving this old thread. :oops: :)


Hi,

I found this expression, which is related to Fourier transform. By substituting $\omega$ with $\omega + m \Omega$, the author showed

$x(t) = \int_{(2m -1)\pi/T}^{(2m +1)\pi/T} X(i \omega) e^{i\omega t} d\omega = \int_{-\Omega/2}^{\Omega/2} X(i (\omega + m \Omega)) e^{i(\omega+ m \Omega) t} d\omega$

where $\Omega \triangleq 2 \pi /T$, $m$ is integer number, $T$ is sampling interval, and $X(i \omega) \triangleq \int_{-\infty}^{\infty} x(t) e^{-i\omega t} dt$.

Can someone explain how the author obtained the $\int_{-\Omega/2}^{\Omega/2}$?

Sorry, there was a typo in my statement. It should be

...substituting $\omega$ with $m \Omega$,...


The problem description goes as follow ---

We need to find the number of permutation {1,2,3..n}  such that the following conditions --

1. i < j < k
2. a[i] > a[j] > a[k]

[b]Don't[/b] hold simultaneously.

For example ,

for n = 3 , we have Total Permutation = 5.
for n = 4 , we have 14.

After Analysing this series , 1 2 , 5 , 14 it turns out to be Catalan Numbers.

So It is easy to find solution for any n

But suppose we are given n and also the prefix which must be used , then how can we tell the number of permutation ?

example
n = 5
Prefix = 3,

Then the total number of permutation is 9

if n = 5
and Prefix = 1,4

then the total number of permutations is 3.

So finally we need to find how many permutations satisfy the above mentioned two conditions with a  given prefix ?
How can we solve this problem ?

Thanks

Let's denote by $ S^{\pi}_n(321)$ the number of permutations of length $ n$ with prefix $ \pi$ that satisfy your conditions (they avoid the pattern 321).

First, some simplifications: suppose that in the prefix we have a descent $ \ldots b \, a \ldots$ with $ b > a$.  Then note that the answer is 0 unless every one of the values $ 1, 2, \ldots, a \minus{} 1$ appear before $ a$ in the prefix.  So, we must go through and check that this is the case for every descent; if it's not, then the answer is 0 and that's easy enough.

Suppose this condition does hold for prefix $ \pi$, so the answer is nonzero.  Then in fact there is only one piece of data about $ \pi$ that matters: if the maximum value in $ \pi$ is $ k$ and there are $ p$ values less than $ k$ not used in $ \pi$ and $ q$ values greater than $ k$ not used in $ \pi$, we have $ S_n^\pi(321) \equal{} S_{p \plus{} q \plus{} 1}^{p \plus{} 1}(321)$, i.e., this is just the number of 321-avoiding permutations of length $ p \plus{} q \plus{} 1$ that begin with $ p \plus{} 1$.  So we need only enumerate 321-avoiding permutations by their first symbol.

At this point, the most efficient way to the answer is to compute a few values and look in the [url=http://www.research.att.com/~njas/sequences]OEIS[/url], where we find the Catalan triangle [url=http://www.research.att.com/~njas/sequences/A033184]A033184[/url], with several other combinatorial representations and a nice formula down at the bottom.


vector
superior algebra
superior algebra solved

I hope You can help me :roll:

[size=150][b]R2=R*R [/b][/size]is a vector space over [b][size=150]R [/size][/b](reals). Is [b][size=150]Z2=Z*Z[/size][/b] a vector space over [b][size=150]Z[/size] [/b](integers)?

I will be very-very grateful for very simple explanation.  :help:

Thanks
Tanja

uhm..
no, since $\mathbb{Z}$ is not a field, and a vector space is a set closed under sum and scalar product, with coefficients in a field...
i think $\mathbb{Z}^2$ is called a modulus on $\mathbb{Z}$.

I  :read: your reply.
I am very [b]grateful.[/b]

Thank You [size=150]very [/size]much :)


(A.Zaslavsky, B.Frenkin, 10--11) In a triangle, one has drawn perpendicular bisectors to its sides and has measured their segments lying inside the triangle.

a) All three segments are equal. Is it true that the triangle is equilateral?

b) Two segments are equal. Is it true that the triangle is isosceles?

c) Can the segments have length 4, 4 and 3?


quadratics
linear algebra
matrix
algebra
quadratic formula

My teammate asked me
"Do you know how to write and solve quadratic equations in
matrix form? Solving the quadratic equations by plugging them into the matrix option in the calculator?" (instead of using the quadratic formula)

I did not understand what she meant but maybe you do...
Please help! Thanks  :lol:

Maybe she meant simultaneous equations? If she did, do the matrix form and do math, rref.


Hi,

It appears that the Mathcamp application website may be generating spurious "username already taken" errors.  We're investigating the problem, but so far we haven't been able to reproduce it.  If this has happened to you, I would be grateful if you could please send me a private message describing the circumstances under which this happened (which day, what time, what o/s and browser you are using, and the usernames you tried to create); please also try logging into the system using the usernames you tried to create, and using the password you tried to use, to see if those accounts are working for you now, and let me know the results.

thanks!
Dave

[quote="MithsApprentice"]Okay this isn't a bug, but it's about the application. On one of my recommenders, it has a "send email" notification button. What exactly is that for?[/quote]

It's necessary in order for your recs to be submitted online: when you click that button, it sends an email to your recommender and gives them instructions for submitting their rec.

[quote="alan"]not sure if this is a bug, but when i go to the online app site, the page that eventually loads only says "No instance available"[/quote]

very much a bug.  we're trying to isolate what is causing the database to crash.


parameterization
analytic geometry
search
geometry
circumcircle
calculus
geometry theorems

How to express the equation of a circle in the barycentric form?
What is the parameter form about a circle?
luisgeometria,can you help me with it?
THANKS

You can find a lot about trilinear and barycentric coordinates in the site http://mathworld.wolfram.com, just make a search with keywords "barycentric coordinates" and "trilinear coordinates".  In the entry about the circle, you can also find the equation of a circle in trilinear coordinates, then just convert trilinear to barycentric...  I seem to remember the site I mention has quite a bit about trilinear, not so much about barycentric.  :(   The fact that one is converted into the other by scaling using the sidelengths transforms nearly all results in trilinear coordinates into results in barycentric...  :)

To answer your question more directly, the equation of a circle in trilinear coordinates $ \alpha: \beta: \gamma$ is $ (l\alpha\plus{}m\beta\plus{}n\gamma)(a\alpha\plus{}b\beta\plus{}c\gamma)\plus{}k(a\beta\gamma\plus{}b\gamma\alpha\plus{}c\alpha\gamma)\equal{}0$, now convert to barycentric and enjoy! :D

The circumcircle has the nice property that, in trilinear, its equation is $ a\beta\gamma\plus{}b\gamma\alpha\plus{}c\alpha\gamma\equal{}0$.  Again, converte into barycentric and enjoy!  :D

Dear Mathlinkers,
you can see an interesting site with a lot of barycentric calculus
http://webpages.ull.es/users/amontes/pdf/geoba.pdf.
Sincerely
Jean-Louis

I wonder if there is some materials about barycentrics in the English version.


OK... 1 vs 100 is over, time for a new game. (although not a game show)

1/2 the average is a game in which each person picks a number from 1-100. After everyone picks, I average the numbers and take 1/2 of it. If you are below 1/2 the average, you are out. If you are above 1/2 the average, then your number is subtracted from 1/2 the average, and that is the number of points you get. If you get 100 total points, you are out. If you do not pick a number by the deadline, you automatically pick 100. Signup in this post.

[quote="lotsofmath"]If you are above 1/2 the average, then your number is subtracted from 1/2 the average, and that is the number of points you get. If you get 100 total points, you are out. [/quote]
Does this mean that if you are not out, then you will get negative points or zero?
Because if you are above 1/2 the average, subtracting from 1/2 the average will get negative results. (small number minus big number = negative number)

You do not subtract your number from 1/2 the average. You subtract 1/2 the average from your number. (sorry, i made a typo.)

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=149694
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=151415
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=154425
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=168049
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=170873

Hmm, somebody stole my idea.  Anyway, I'd suggest not starting up a game like this right before summer, as many people are likely to go away and not get a chance to play.  I was planning on starting up HTA 6 in September, and I don't think you'll be able to get a good game going before then.

me is going back to china in exactly 1 week! yay!  :D  :D  :D

I want to sign up :)

[quote="chenhsi"]so why wouldnt everyone pick 100?

if everyone picks 100, then the average would be 100 and half of that would be 50 so no one is eliminated[/quote]Yes, but those who pick 100 will be out by the 3rd round, since each of them will have 50 points from each round, and after 2nd round they'll get 100 points each. In fact, people from that hypothetical group will be wise to pick something close to 50, since that'd be as close to the 1/2 of average as possible without being lower than it, and last them alot more rounds.

And because many people will think this way, people might want to pick 25, or lower, etc until you feel it gets unsafe to pick that low.

Basically, don't forget that the rules also say when you total to 100 points, you're out.


Let $x,y,z$ be positive reals such that $x^6+y^6+z^6=3$.
Find the maximum value of the following equality.

\[x^3yz(y+z)+y^3zx(z+x)+z^3xy(x+y)\]

By Cauchy we have:
$x^3y^2z\leq\frac{3x^6+2y^6+z^6}{6}$
By the same way we have
$x^3yz(y+z)+y^3zx(z+x)+z^3xy(z+y)\leq6$
The equal hold for x=y=z=1 ;)

You are right!  :) Thank you,Stun. :)

kunny


[hide="Some Ideas"]1. If both $ a$ and $ b$ are even, $ a\not| bc\plus{}1$. At most one of the variables can be even.

2. If $ a\equiv b\mod n$, then $ bc\plus{}1\equiv1\mod n$, and $ a\not| bc\plus{}1$. All three variables must be relatively prime.

Thinking of more...[/hide]

The problem is posed in Junior High school mathematics Olympiad at Novosibirsk in Russia 1963.

In Japan, two problems have been posed in the past in university entrance exam.

Here are:

[color=blue] Waseda University entrance examination 1990

Let $ a,b,c\ (a < b < c)$ are distinct positive integers such that the product of any two of $ a,b,c$ has the residue of 1 when divided by the third number.

(ⅰ)　Find the quotient when $ a \plus{} b$ is divided by $ c$?

(ⅱ)　Find the quotient when $ a \plus{} c$ is divided by $ b$?

Find the values of $ a,\ b,\ c.$[/color]

[color=green] Tokyo Institute of Technology entrance exam 1978

Let $ a,\ b,\ c\ (1 < a < b < c)$ be integers such that  $ (ab \minus{} 1)(bc \minus{} 1)(ca \minus{} 1)$ is divisible by $ abc.$

(1) Show that $ ab \plus{} bc \plus{} ca \minus{} 1$ is divisible by $ abc.$

(2) Find $ a,\ b,\ c.$ [/color]

[quote="kunny"]Waseda University entrance examination 1990

Let $ a,b,c\ (a < b < c)$ are distinct positive integers such that the product of any two of $ a,b,c$ is divisible  by the third number.

(ⅰ)　Find the quotient when $ a \plus{} b$ is divided by $ c$?

(ⅱ)　Find the quotient when $ a \plus{} c$ is divided by $ b$?

Find the values of $ a,b,c.$[/quote]
Can't $ a,b,c$ be any three consecutive powers of any integer, the only exception being $ a\equal{}1$?

Sorry I made a typo. I will edit the problem. :blush:

4 the second question, I got a,b,c = (2,3,5)
what i did was:
                    let s = abc, then s |  s(1/a+1/b+1/c-1/s)
                    since (1/a+1/b+1/c-1/s)<=2, (it can only equal to 1)
                   so abc+1 = ab+bc+ca; and here I got stuck, but I just plugged 2,3,5 in and it worked. but do u have a better way to solve it?

[hide="The original problem"]$ a|bc \plus{} 1\land b|ca \plus{} 1\land c|ab \plus{} 1\implies abc|(ab \plus{} 1)(bc \plus{} 1)(ca \plus{} 1)$, and that, after expanding, yields $ abc|ab \plus{} bc \plus{} ca \plus{} 1$

Hence $ {1\over a} \plus{} {1\over b} \plus{} {1\over c} \plus{} {1\over abc}$ must be integer.

All of $ a,b,c$ must be distinct: if e.g. $ b \equal{} c$ then $ b|ac \plus{} 1$ can't hold. WLOG assume $ a < b < c$. Then

$ {1\over a} \plus{} {1\over b} \plus{} {1\over c} \plus{} {1\over abc}\leqslant{1\over 2} \plus{} {1\over 3} \plus{} {1\over 4} \plus{} {1\over 24} \equal{} {9\over 8}$, hence

$ {1\over a} \plus{} {1\over b} \plus{} {1\over c} \plus{} {1\over abc} \equal{} 1$

Assume $ a\geqslant 3$. Then

$ {1\over a} \plus{} {1\over b} \plus{} {1\over c} \plus{} {1\over abc}\leqslant {1\over 3} \plus{} {1\over 4} \plus{} {1\over 5} \plus{} {1\over 60} \equal{} {4\over 5}$, so we can't have a solution in that case. Therefore $ a \equal{} 2$, giving

$ {1\over b} \plus{} {1\over c} \plus{} {1\over 2bc} \equal{} {1\over 2}\iff bc \minus{} 2b \minus{} 2c \minus{} 1 \equal{} 0$

Than can be rewritten as $ (b \minus{} 2)(c \minus{} 2) \equal{} 5$, yielding $ b \minus{} 2 \equal{} 1, c \minus{} 2 \equal{} 5$. So, the only solution could be $ (2,3,7)$ (with permutations) and the checkback works.[/hide]

[quote]a,b,c are >1 and are integers. The product of any two of a,b,c plus 1 can be divided by the third number. Find a,b,c. (i.g a|(bc+1))
[/quote]
[hide]no two can be the same: assume the numbers are a,a,b. then a does not divide ab+1, contradiction.

from the given, we know that $ (ab \plus{} 1)(bc \plus{} 1)(ca \plus{} 1)\equiv 0\pmod{abc}$.
expanding and simplifying, $ ab \plus{} bc \plus{} ca \plus{} 1\equiv 0\pmod{abc}$.

we can show that $ ab \plus{} bc \plus{} ca \plus{} 1 < 2abc$.
since no two are the same, WLOG, let $ 1 < a < b < c$.
assume $ ab \plus{} bc \plus{} ca \plus{} 1\ge 2abc$.
then $ ab \plus{} 1\ge bc(a \minus{} 1) \plus{} ca(b \minus{} 1) > bc(a \minus{} 1)$. however, $ ab \plus{} 1 < bc(a \minus{} 1)$, because $ bc > ab \plus{} 1$, and $ a \minus{} 1$ is at least 1, so contradiction.

thus, since $ ab \plus{} bc \plus{} ca \plus{} 1$ is a multiple of $ abc$, but is $ < 2abc$, $ ab \plus{} bc \plus{} ca \plus{} 1 \equal{} abc$.

$ abc \equal{} ab \plus{} bc \plus{} ca \plus{} 1 < 3bc \plus{} 1\implies \minus{} 1 < bc(3 \minus{} a)$. Thus, $ a < 3 \implies a \equal{} 2$.

thus, $ 2b \plus{} bc \plus{} 2c \plus{} 1 \equal{} 2bc\implies bc \minus{} 2b \minus{} 2c \equal{} 1\implies (b \minus{} 2)(c \minus{} 2) \equal{} 5$, $ b \equal{} 3,c \equal{} 7$.

the only solution is $ \boxed{2,3,7}$.[/hide]


Prove that if number

10^n + 10^(n-1) +....+ 10 +1 is prime => n is prime.

 :huuh:

The last exponent should be $ n\minus{}1$ (otherwise, it's not true for $ n\equal{}1$).

In this case, our number is $ \underbrace{11\cdots 1}_n$ which is divisible by $ \underbrace{11\cdots 1}_d$ for any divisor $ d$ of $ n$.

So if $ \underbrace{11\cdots 1}_n$ were prime, its only divisors could be itself and 1. In particular, the only possible divisors $ d$ of $ n$ are 1 and $ n$. Since $ n\equal{}1$ does not produce a prime, $ n$ must be prime.


Find all functions $ f: R \to R$ such that $ f(x \plus{} y)f(f(x) \minus{} y) \equal{} xf(x) \minus{} yf(y)$

Blarg, the above reply appeared after I finished writing this. Oh well, I'll post it anyway since I think it's more explicit than the linked to solutions.

First let's clean up easy solutions. In particular, $ f(x) \equal{} 0$ for $ x \neq 0$ and $ f(0) \equal{} c$ for any fixed $ c$ works. To see this, note that $ xf(x)$ is always $ 0$ no matter what $ x$ is, so the RHS is always $ 0$. So if this solution didn't work the LHS would have to be nonzero somewhere, meaning $ x \plus{} y \equal{} 0$ and $ f(x) \minus{} y \equal{} 0$. This implies $ x \plus{} f(x) \equal{} 0$, which obviously has no solutions. Thus the above solution works.

Let $ S$ be the set of all $ s$ such that $ f(s) \equal{} 0$. From putting $ x \equal{} y$ it is clear that $ S$ is nonempty. Since we assumed the above solution away there exists a nonzero element not contained in $ S$.

Put in $ y \equal{} 0$. We get $ f(x)f(f(x)) \equal{} xf(x)$ (1). Thus for $ x \notin S$, we get $ f(f(x)) \equal{} x$.

Suppose that $ f(a) \equal{} f(b)$ and $ a,b \notin S$. Then the above gives $ a \equal{} f(f(a)) \equal{} f(f(b)) \equal{} b$, so $ f$ is one-to-one on nonzero outputs.

Pick any $ x \notin S$, so $ f(f(x)) \equal{} x$. Put in $ (x, \minus{} y)$ and then $ (f(x),y)$ into the equation to get, respectively,
$ f(x \minus{} y)f(f(x) \plus{} y) \equal{} xf(x) \plus{} yf( \minus{} y)$
$ f(f(x) \plus{} y)f(x \minus{} y) \equal{} f(x)x \minus{} yf(y)$
Subtracting these two equations from each other gives $ yf( \minus{} y) \equal{} \minus{} yf(y)$. So if $ y \neq 0$, we have $ f(y) \equal{} \minus{} f( \minus{} y)$.

Pick $ y \notin S$, $ y \neq 0$ (which exists due to the solutions we assumed away) and $ x \in S$. We get $ f(s \plus{} y)f( \minus{} y) \equal{} \minus{} yf(y)$. Applying $ f(y) \equal{} \minus{} f( \minus{} y)$, this reduces to $ f(s \plus{} y) \equal{} y$. If there is more than one element in $ S$, say $ s_1, s_2$, then this contradicts our pseudo-injectivity: that $ f(a) \equal{} f(b) \neq 0$ implies $ a \equal{} b$. This is because $ f(s_1 \plus{} y) \equal{} f(s_2 \plus{} y) \equal{} y \neq 0$. So $ S$ has only one element $ s$. If $ s \neq 0$, then $ f(s) \equal{} \minus{} f( \minus{} s) \equal{} 0$, so $ \minus{} s \in S$, contradiction. Thus $ S$ has only $ 0$, meaning $ f(x) \equal{} 0$ if and only if $ x \equal{} 0$.

To finish, take $ x \equal{} y \neq 0$, giving $ f(2x)f(f(x) \minus{} x) \equal{} 0$. $ f(2x) \neq 0$, so $ f(f(x) \minus{} x) \equal{} 0$ implying $ f(x) \equal{} x$. This is the only other solution.

could someone please check this solution?

[hide=Solution]
Let $P(x,y)$ denote the given assertion.
$P(x,0)\implies f(x)f(f(x))=xf(x)\implies f(f(x))=x\ \forall\ x$ such that $f(x)\neq 0.$ Note that $\boxed{f\equiv 0}$ is a solution. Now assume there exists $x$ such that $f(x)\neq 0.$ Firstly, notice that this gives pseudoinjectivity, or that $f(a)=f(b)\implies a=b$ unless $f(a)=0.$ Let $S$ be the set of all $x$ such that $f(x)\neq 0.$

Then $P(x,f(x))\implies f(x+f(x))f(0)=xf(x)-f(x)f(f(x))=0,$ so we must have $f(x+f(x))=0$ or $f(0)=0$ for all $x\in S.$

Case 1: $f(x+f(x))=0.$
$P(x,-x)\implies 0=f(0)f(x+f(x))=xf(x)+xf(-x)\implies f(x)=-f(-x)$ unless $x=0.$
$P(x+f(x),y)\implies f(x+f(x)+y)f(-y)=-yf(y)=yf(-y)\implies f(x+f(x)+y)=y$ for all $y$ such that $x,y\in S,y\neq 0.$

Thus, $P(x+f(x),f(y)-x)$ implies that $f(f(x)+f(y))=f(y)-x$ for all $x,y$ such that $x,y,f(y)-x\in S, y\neq 0.$

If $f(f(y)-x)=0,$ by taking $f$ of both sides in $f(f(x)+f(y))=f(y)-x,$ we must have $f(x)+f(y)=0$ if $f(x)+f(y)\in S$ or $f(y)-x=f(f(x)+f(y))=0\implies x=f(y)$ otherwise.

The first case implies that $f(x)=-f(y)=f(-y),$ and since both sides are nonzero, by pseudoinjectivity we get $x=-y.$ The second gives $x\neq f(y),$ or in other words, $f(f(x)+f(y))\neq 0.$

Now switching $x$ and $y$ in $f(f(x)+f(y))=f(y)-x,$ we get $f(x)-y=f(y)-x\implies f(x)+x=f(y)+y$ for all  $x,y\in S$ such that $y\neq 0, x\neq -y$ (since $x=f(y)$ gives an identity, we may ignore that restriction). Hence $x=1\implies f(y)+y=f(1)+1=c$ for some constant $c$ unless $y=-1,0.$ But $x=2\implies f(-1)-1=f(2)+2=f(1)+1=c,$ so we may conclude that $f(x)=-x+c$ for all $x$ such that $f(x)\neq 0,x\neq 0.$

Assume for the sake of contradiction that there exist distinct $x,y$ such that $f(x)=-x+c,f(y)=0.$

Subcase 1: There exists nonzero $y$ such that $f(y)=0.$ Then $P(x,y)\implies f(x+y)f(-y)=-y(y+c).$ If the RHS is nonzero, then $f(x+y)=-x-y+c, f(-y)=y+c$ and $-x-y+c=-y\implies x=c,$ or there only exists one $x$ in $\mathbb{R}-S.$ $P(0,x)\implies f(x)f(f(0)-x)=-xf(x)\implies f(f(0)-x)=-x.$ If $x\neq 0,$ then $f(0)-x=x\implies x=f(0)/2.$ Then taking $f$ of both sides gives $f(0)-x=f(-x)\implies -x=x,x=0,$ contradiction. Now, it is easy to confirm that $\boxed{f(x)=0\ \forall\ x\neq 0,\ f(0)=c}$ is a solution.

Else, RHS is $0$ so $y=-c\ (y\neq 0)$ so $f(x-c)f(c)=0\implies f(c)=0.$ But $y=c$ yields $f(x+c)f(-c)=-2c^2\implies c=0,$ contradiction.

Subcase 2: The only $y$ such that $f(y)=0$ is $y=0.$ Then $f(x+f(x))=0\implies x+f(x)=0\implies f(x)=-x\ \forall\ x,$ which is not a solution.

Case 2: $f(0)=0.$
$P(0,y)\implies f(y)f(-y)=-yf(y)\implies f(-y)=-y\implies f(y)=y$ or $f(y)=0.$ Assume there exist distinct $x,y$ such that $f(x)=x,f(y)=0,x\neq 0.$ Then $P(x,y)\implies f(x+y)f(x-y)=x^2\implies x^2-y^2=x^2\implies y=0,$ so $y=0$ is the only $y$ such that $f(y)=0.$ Hence we may conclude $\boxed{f\equiv \text{Id}}$ which is another solution.
[/hide]


The director of a prison decides to free one of the prisoners by the following method. First he arranges all the prisoners
in a circle, then he starts removing every other prisoner from the circle until only one remains. The last prisoner in the circle is set free. For instance assume that there are five prisoners numbered 1, 2, 3, 4, 5; then the director starts removing in this order prisoners 2, 4, 1, 5, so 3 is the last one and is set free. If there are initially N prisoners, which one will be the lucky one?


abstract algebra
vector
function
superior algebra
superior algebra unsolved

Hi! I have a question (propably stupid...):

Why, when each element of group is in order 2 ($ \forall a\in G: a^2 \equal{} 1$), does exist an homomorphism (diffrent from identity)?

The answer is affirmative if the group has more than two elements... Do you see [i]why[/i]?

When the group is not abelian, then we could find $ a\in G: f(x)\equal{}axa^{\minus{}1}$ is ok.
When the group is abelian, then $ f(a)\equal{}a^{\minus{}1}$ is homomorphism, but it's identity, when $ \forall a\in G: a^2\equal{}1$, and in this case I don't know, what I should do...

Sorry, but that question makes no sense. A homomorphism needs two objects (groups), but you have just one. As the problem is trivial for endomorphisms (there is alway the zero one), you probably want automorphisms. Please be more carefull next time.

Also note that such a group must be abelian by $ xyxy \equal{} (xy)^2 \equal{} e \equal{} x^2y^2$. Even more, it must be a vector space over $ \mathbb F_2$ (field with two elements), so you may want to check your result for vector spaces (and note that if it's 1-dimensional, there is no other automorphism than the identity).

[hide]The group is a direct sum of cyclic groups or order two. So, the function induced by interchanging the generators of any two of the $ \mathbb{Z}_{2}$ summands provides you with a nontrivial automorphism of $ G$.[/hide]

Of course, you're right-I mean automorphism. Sorry, it's a new staff for me.
But could you explein a bit more, what do you mean with "it must be a vector space...than identity)."? I know, I'm stupid, but actually, I don't know, what a vector space is...

edit: coquitao: ok, it is, but what follows with that?

See the new version of my post, [b]Kibu[/b].

It's obviously or I should prove it? I really don't get it:(...

But thanks a lot for your help:)!

edit: I only want to say, that now, after 18 houers, I understand that! Thanks a lot!:)


$ a,b,c$are positive numbers such that $ a \plus{} b \plus{} c \equal{} 3$,prove that
$ (ab \plus{} bc \plus{} ca \minus{} 17)^2 \plus{} 20abc\geq 216$

I have a ugly solution...so I am looking foward to yours....

Sorry for my mistake...Now I correct it.

$ q^2\plus{}73\plus{}20r\geq 34q$
since $ p\equal{}3$ the problem turn to
$ 81q^2\plus{}73p^4\plus{}540pr\geq 306p^2q$
from schur it remains to prove that
$ 13p^4\plus{}81q^2\geq 66p^2q$
$ (13p^2\minus{}27q)(p^2\minus{}3q)\geq 0$ which is obvious

[quote="arqady"][quote="Jianxing113725"]$ a,b,c$are positive numbers such that $ a \plus{} b \plus{} c \equal{} 3$,prove that
$ (ab \plus{} bc \plus{} ca \minus{} 17)^2 \plus{} 20abc\geq 216$

[/quote]
The following stronger inequality is true too.
Let $ a,$ $ b$ and $ c$ are non-negative numbers such that $ a \plus{} b \plus{} c \equal{} 3.$ Prove that:
\[ (ab \plus{} bc \plus{} ca \minus{} 17)^2 \plus{} 21abc\geq 217
\]
But with the same conditions $ (ab \plus{} bc \plus{} ca \minus{} 17)^2 \plus{} 22abc\geq 218$ is wrong already. :wink:[/quote]

 :( My method can't solve this strongger one...Could you share your solution here.

from schur $ 21r\geq 28q\minus{}63$ then $ (q\minus{}3)^2\geq 0$


geometry
circumcircle
projective geometry
geometry proposed

Let ABC be a triangle, the his circumcircle [b][i]C[/i][/b]=[b][i]C[/i][/b](O, R) and the point P. I note the second intersections A', B', C' of the lines AP, BP, CP respectively with the circle [i][b]C[/b][/i] and the intersections $\displaystyle E \in AC \cap A'B'$, $\displaystyle  F \in AB \cap A'C'$,  $\displaystyle S \in AA \cap B'C'$, $ %Error. "display" is a bad command.
R \in A'A' \cap BC$. Prove that the points P, E, F, S, R belong to the same line. (XX is the tangent in the point X$\in$[i][b]C[/b][/i] at the circle [b][i]C[/i][/b]).

The collinearity of $P,E,F$ is a consequence of Pascal's Theorem for the inscribed hexagon $ABB'A'C'C$, that of $P,E,S$ a consequence of the same theroem applied for $AACC'B'A'$, and that of $P,F,R$ follows from the application of the same theorem for $A'A'C'CBA$.

P.S.

I suppose that by $AA$ you mean the tangent in $A$ to the circle, and the same for $A'A'$. I don't think it's standard notation; you should mention stuff like this.


function
algebra
polynomial
functional inequalities

Suppose that $ f$ is a real-valued function for which \[ f(xy)+f(y-x)\geq f(y+x)\] for all real numbers $ x$ and $ y$.

a) Give a non-constant polynomial that satisfies the condition.
b) Prove that $ f(x)\geq 0$ for all real $ x$.

[quote="April"]Suppose that $ f$ is a real-valued function for which
\[ f(xy)+f(y-x)\geq f(y+x) \]
for all real numbers $ x$ and $ y$.

$ a.$ Give a nonconstant polynomial that satisfies the condition.
$ b.$ Prove that $ f(x)\geq 0$ for all real $ x$.[/quote]

$ a.$ $ f(x)=x^{2}+4$
Proof : $ f(xy)+f(y-x)-f(x+y)=(xy)^{2}+4+(y-x)^{2}-(x+y)^{2}$
So $ f(xy)+f(y-x)-f(x+y)=(xy)^{2}-4xy+4$
So $ f(xy)+f(y-x)-f(x+y)=(xy-2)^{2}\geq 0$
So $ f(xy)+f(y-x)\geq f(x+y)$

$ b.$ Investigate then the case where $ xy=y+x$, that's to say $ y=\frac{x}{x-1}$. Then the inequation becomes $ f(y-x)\geq 0$. So we always have $ f(\frac{x}{x-1}-x)\geq 0$

So $ f(\frac{x(2-x)}{x-1})\geq 0$ $ \forall x\in %Error. "mathBB" is a bad command.
{R}-\{1\}$

But the equation $ \frac{x(2-x)}{x-1}=a$ is equivalent to $ x^{2}+(a-2)x-a=0$ and this equation always has real roots$ \neq 1$ (discriminant is $ a^{2}+4>0$).
So, for any real $ a$, exists $ x\neq 1$ such that $ \frac{x(2-x)}{x-1}=a$, and so $ f(a)\geq 0$

So $ f(a)\geq 0$ $ \forall$ $ a\in%Error. "mathBB" is a bad command.
{R}$

How would one go about finding such a polynomial for a)? (And I'm also curious what other polynomials suffice)

I solved it by looking at part b). I knew that the easiest nonconstant polynomial such that $f(x) \ge 0$ for all real $x$ would have to be something of the form $x^2 +c$. Now finding $c$ is easy by just completing the square.

Not sure if this works:

From the given inequality we have:
f(0) $\geq$ 0

Suppose there exists a k such that f(k)<0.
Substituting x=x, y= $\frac{k}{x}$ into the original equation gives:

f(k)+f(0) $\geq$ f(x+$\frac{k}{x}$).

The function g(x)= $\frac{k}{x}$ for some constant k has a range of all real values (besides k) for all x (besides x=0).

So f(x) $\leq$ f(k)+f(0) < f(0).

But f(0)=f(0). Since f(k) is a finite negative value, the function has a discontinuity at f(0). This is a contradiction since all polynomials are continuous.

So f(x) $\geq$ 0 for all x.

[quote=tigerche](a) is easy, just plug $f(x)=x^2+4$ into the equation

(b):
-First of all, by letting $x=0$ we have $f(0) \geq 0$.
-Substituting $x=t$,$y=0$ and $x=-t$, $y=0$ gives $f(t) = f(-t)$ and $f(0)=0$.
-Substituting $x=y=t$, we get $f(t^2) \geq f(2t)$.
-Lastly, substituting $x=-t$, $y=t$ gives $f(t^2)+f(2t) \geq 0$. Combining this with $f(t^2) \geq f(2t)$, we get $f(t^2) \geq 0$. Paired with the fact that $f(t)=f(-t)$, we get the conclusion.[/quote]

Substituting $x=t$,$y=0$ and $x=-t$, $y=0$ doesn't give $f(t) = f(-t)$


linear algebra
matrix
graph theory
combinatorics open
combinatorics

The (ij) element of the biadjacency matrix B of a bipartite graph is the number of egdes going from vertex i to vertex j.
My question is: is there a way of extracting from B the information of whether the graph is connected?
Thanks!

The graph is disconnected if for some vertices $ i,j$ there is no path between them. This amounts to saying that for all $ n$ the $ i,j$th element $ (B^n)_{ij}$ of $ B^n$ is zero.

So graph is connected iff for some positive $ \lambda$ all elements of
\[ \sum_{k \equal{} 0}^\infty \lambda^k B^k\]
are positive. The series is convergent to $ (I \minus{} \lambda B)^{ \minus{} 1}$ for $ \lambda$ small enough ($ 1/m$, where $ m$ is the number of vertices in $ B$, is always sufficient).

Thus the recipe:

Compute the inverse to $ I \minus{} B/m$ and check if there are some zeroes.

Maybe, there is a simpler tool, I don't know.