$n$ is an even positive integer. There are $n$ names in a container.  $n$ people with corresponding names (no repetition of names) randomly pick a name from the container and put it back. However, if a "pair" occurs (two people get each others name), then their names are removed from the container. Let $x$ be the amount of rounds it takes to finish the container. What is the expected value of $x$?

[quote="The Zuton Force"]I suppose it could be done recursively.

By the way, specify that $n$ is even, because if $n$ is odd, it doesn't work :o[/quote]

fixed.

[quote="The Zuton Force"]I suppose it could be done recursively.
[/quote]

explanation? thanks.

The question is slightly unclear -- is the following right?  Each person reaches in, pulls out a name, remembers it, and puts the slip back.  We keep going around the circle.  If at any time someone picks out the name of someone who has picked out his name, both of them leave the game.  So, I keep a running total of all of the names I've ever picked out.

This doesn't look "Intermediate" to me at all -- I recommend that it be moved to Olypiad Combinatorics somewhere.  (A recursion isn't promising because when one pair leaves the game, many other players still have lists that they're keeping track of.)

In that case, a recursive solution seems more reasonable, although we need to know whether everyone gets a different slip (a permutation) or whether we're choosing with replacement (which is what is suggested by the original problem, I think).

Another variation would be to throw out people who draw their own names, as well.

[quote="surge"][quote="paladin8"]The way I interpreted is that each round, we start with a set of people and no information from previous rounds. Everyone picks a slip and if A picks B and B picks A, they are removed. After removing all such pairs, repeat.[/quote]

That's exactly how I interpreted it. Also, if you pick yourself, you put your name back and pick again. How would you do such a problem?[/quote]

Yeah, that is what i meant. sorry for not phrasing correctly.

I think if we alter the problem slightly we can solve it and get some insight for solving the whole problem.  Let's say that one person picks a name from the bag (not his own - otherwise retry and disregard that draw) and the persons name who is chosen picks next until he picks the first persons name.  Let $X_{i}$ denote the random variable of the number of draws taken in the $i^{th}$ round $(i =1,2,3...,k)$.  Let $Y = X_{1}+X_{2}+\cdots+X_{k}$, then $E[Y] = E[X_{1}]+E[X_{2}]+\cdots+E[X_{k}]$.  With this setup $X_{i}$ has a Geometric Distribution, which has a simple formula for the expected value: $\frac{1-p}{p}$, where $p$ is the probability of drawing the corresponding name.  Then $E[X_{1}] = \frac{\frac{n-1}{n}}{\frac{1}{n}}= n-1$.  Removing those two names, $E[X_{2}] = \frac{\frac{n-3}{n-2}}{\frac{1}{n-2}}= n-3$.  We know that these numbers are all odd since $n$ is even.  We see the pattern forming: $E[Y] = 1+3+5+\cdots+n-5+n-3+n-1$.  There are $k$ rounds and so the expected value is $k^{2}$,(the sum of the first $k$ consecutive odd integers is $k^{2}$).  But $k$ is the last round after all but one pair is eliminated so $k = \frac{n}{2}$ and $k^{2}= \boxed{\frac{n^{2}}{4}}$


Find the number of positive integers $x$ satisfying the following two conditions:
1.  $x<10^{2006}$
2.  $x^{2}-x$ divisible by $10^{2006}$
 :wink:


geometry
rectangle
perimeter
trigonometry
ARML
similar triangles

[quote="frt"]Rectangle $ABCD$ is inscribed in rectangle $EFGH$ such that each side of rectangle $EFGH$ contains exactly one vertex of rectangle $ABCD$. If $AB=2$, $BC=3$ and the perimeter of rectangle $EFGH$ is $5\sqrt{6}$, find the area of rectangle $EFGH$.[/quote]

[hide]
Because $\angle A, \angle B, \angle C, \angle D$ are $90^{\circ}$, $\angle EAD + \angle FAB = 90^{\circ}$ and so on... Label $\angle EAD$ $theta$ and label $\angle FAB$ $\alpha$. We have then: \[ 3\cos{\theta} + 2\sin{\alpha} = EF \] and \[ 3\sin{\theta} + 2\cos{\alpha} = EH \]. This simplifies to $5\cos{\theta} = EF$ and $5\sin{\theta} = EH$. $EF + EH = 5\sqrt{6}/2$, so $\cos{\theta} + \sin{\theta} = \sqrt{6}/2$ this means that $2\cos{\theta}\sin{\theta} = 1/2 \implies \cos{\theta}\sin{\theta} = 1/4$ when you square it and use $\cos^2{\theta} + \sin^2{\theta} = 1$. The area of the triangle is $EF \cdot EH = 25\sin{\theta}\cos{\theta} = \frac{25}{4}$[/hide]

yes...this can be done with similar triangles instead of getting into that trig...eventhough they are essentially the same thing...and labeling the sides of the smaller rectange x,y...

(i wonder if this is just like #8 on the arml hw  :P )


List all the things you want to do for your pleasure or amusement before you die!

NO ACADEMIC OR CAREER GOALS HERE (something like kissing your coworker who isn't your boy/girlfriend is fine)
Some ideas:
-things you want to eat, touch, smell, etc
-places you want to go and what you want to do there
-places you want to nap
-things you want to say and to whom

-Make sure I wont be in pain when I die
-Get a Wii (may never happen)
-Kiss my coworker who isn't my girlfriend
-Nap in a trash can (when I have time)
-Find something to do tommorow

Cant think of any more right now.  :D

successfully using a math pickup line on somebody who isn't, like, a math nerd would be pretty sweet

1-finish all the animes worth watching. (which, by the way, isnt as many as u think.)
2-meet the author of one of my fav mangas (preferably Watsuki, if he's still alive.)
3-eat at least 20 flavors of pie. (already to 9...!)
4-rule a country.
5-assasinate a world leader.
6-run a manga shop.
7-shake the hand of a world leader.
8-run an oriental supermarket.
9-see a solar eclipse.
10-live.

ok 5 and 7 really dont go together... but o well.

Shake hands with him and then stab him with a knife! And start a rebellion and conquer the country!

Or, become a world leader and shake hands with yourself.

[quote="dreambold22"]ah, either would work out nicely... although i DO prefer swords...[/quote]

good luck hiding a sword in your meeting with a world leader ;]

ummm before i die i wanna:

live!

True, swords are better...

So, hide a sword! It's not that hard!

Swords would be hard to hide because back then, they wore it on their belts, which is too obvious. You can also try having a sword sheath on your back, but that would be hard to reach (and obvious). Thus, the only place to hide a sword when walking in public would be under your clothes, which is bad for two reasons:
1) It would touch your...(Probably wont want to know)...I'm not going to continue the sentence.
2) You might cut yourself.

Knives are much more concealed than swords (and more common).

Also, if you are that crazy about swords, you can bring an accomplice and let the accomplice have the sword and sneak up, which wouldn't be very subtle.

um actually, in ancient japan lots of gang members and assasins would carry around "cane swords", swords in thier sheaths disguised as canes and either worn on the back or actually used as a cane. believe me, it's not that hard to pull that sword out from behind ur back. i've practiced it with an umbrella and its case, hoping that one day i would be able to preform it with a real katana. or maybe just for fun.

Yes, but still, a sword on your back would still be very obvious, and are you going to waste a trip to japan just to buy a cane sword thing when youre not even old?

they're actually quite cheap. it's cause they break quite easily, but not before getting the job at hand done. and they are NOT obvious. only the maker of a cone sword could spot it as a real sword. plus i could just get some buddies in japan to mail one over for me.

Back to the happier thoughts...

happier thoughts = not killing, assassinating, cutting yourself, stabbing, etc.

ah... right. sorry. got off topic. (by the way, i wasnt talking about stabbing myself. just the assasinating part.)

That's also not the most intelligent thing to post on a public forum in a politically stressed climate  :roll:

1. Settle down with a family
2. Live to see my kids get married -- all of them
3. Have easy access to a lake, on which I can scull
4. Not hate/be hated by anyone
5. Learn Hindi
6. Travel to the Caribbean, México, and New Zeland
7. Try a case in the US Supreme Court

I realize the last is arguably a career goal. But it's so much more than that :)

I'll list more later if I feel like it

hehehe, I have a huge list I actually wrote about on either live journal or facebook.  Anyways...

I want to get married someday before I die.
I want to write my name in the sand of as many beaches in as many countries as I can...at least once on a continent.
I want to learn how to sail =D

1. Visit every continent (except Antartica).
2. Get married and live to see my grandchildren.
3. Buy many expensive things in 1 shopping trip.
4. Convince my parents to let me get a gmail account (they don't want me to chat)

1. Marry an attractive young lady
2. Meet and hopefully kill a republican
3. Meet and have dinner with Barack Obama
4. Ride a bike across the US
5. Visit every single country for at least a week...so 3 years of my life at least...
6. Laugh at least once a day
7. Get a job
8. Have kids
9. Send all my kids to college
10. Watch my kids get married
11. Die before all my kids
12. Go sky diving
13. Meet an NBA all star
14. Go streaking
15. Egg at least 5 more peoples houses
16. Get a nice car
17. Cause terrible pain to someone I hate

Thats about it.

The only thing I really want to do before I die is ask out the girl I have a crush on, but I am shy as heck and don't have the guts to do it.  :(

Other things include
- Going to Europe
- Going to every Qdoba in the US (probably won't be achieved)
- Getting married and having a family

-things you want to eat, touch, smell, etc: uh... pulak would not allow me to say it...
-places you want to go and what you want to do there: ditto...
-places you want to nap: ditto...
-things you want to say and to whom: random expletives at famous people

[quote="dreambold22"]you've never cried or actually felt sad or upset? wow... i wish i could be like that... u must be one happy person...[/quote]

I've cried, I just didn't feel really sad or upset... It seems whenever I see someone else cry, they are always so deeply upset that it's the end of the world.

I hate crying and I dont know why, but I cry more easily than other people. I remembered that I cried for misspelling a word at the District spelling bee in 4th grade, but I just won last year (6th grade).  :winner_first: If only my spelling was as good as my math... I also get very angry at myself if I get at least 25% of the problems wrong at the end of each chapter in the introduction series.

[quote="polymathpi"]Hm.. I have a lot of goals, but they aren't really special (to anyone else but me)

-Earn the IB diploma (I know it's academic, but please? IB is my life right now, the only reason I'm allowed to go to my school)
-Earn $ \$$1,000,000 and then donate it to charity
-Deliver meals to impecunious families
-Travel to France so I can put my French learning to good use
-Get with a guy who's just as nerdy as I am (There's more to the specifications but...)
-Break 14 seconds for my 100m time, as well as break 30 seconds for 200m (I'm so slow!)
-Open a restaurant with my best friend (as we planned)
-Tell my brother all my thoughts about him ( :cursing: ) without getting yelled at by my parents
-Tell my sister how much she's screwed up her life as well as my family's (without her going all army soldier on me)(and no, her joining the army is not what she did wrong)
-Go to Belgium and eat Belgian waffles
-Live on the streets for two nights (just to know what it feels like)
-Foster kittens
-Say something that changes someone's life for the better
-Cry and actually feel sad or upset
-Love someone so much that I'm blind to everything else
-Realize what everything means and why it happens...and then die in peace

It might be awhile before I accomplish all of this.  :maybe:[/quote]

HMM....THAT WAS QUITE INSPIRATIONAL.

<nothing>

I feel like I would be fairly ambivalent if I were to die, say, now

And how old are you???Comeon there has to be something you want to do.

i want to die.
but i cannot accomplish this before i die. :roll:

Things I want to do before I die:
UM.....
Jump of a burning plane without a parachute 100,000 feet in the air and land without injury  :rotfl:  (NOT LIKELY)
RULE THE WORLD
Win $ \$$4 billion in some super awesome legendary violin competition
Be the only one to survive the most deadly terrorist bombing in the world without injury and as a result of that become hailed as a worldwide celebrity, earning billions every month and using the money to buy sporty cars and pie  :P
Punch the president in front of national tv
Drive a car off Mount Everest
Eat every single flavor of ice cream in the world
Open the most successful business in the world
Adopt 5 dogs and eat 3 of them
Invent a medicine that cures every single disease in the world (GONNA TAKE SOME TIME)
Defeat Gary Kasparov in a game of chess
Drive a jet
Break the sound barrier over a church in the middle of a sermon (PROBABLY NOT GOING TO HAPPEN)
Become VP of Microsoft
Travel across the United States in a go cart
Interview some really corrupt and evil business man, then kill him and donate all his money to charity  :P
SEE THE WORLD END
Die and then be resurrected, then die a few seconds later

It's going to take some time...

You know what your problem is? You don't live! Live! Live! Life is a banquet and most poor suckers are starving to death.

1) Walk across the US.
2) Walk across Canada.
3) Walk across Mexico.
4) Go down Rocky Falls in a barrel.
5) Fall down the grand canyon with a parachute, with the video posted on youtube.
6) Make a video that trumps Monty Python's work.
7) Insult every single world leader simultaneously.
8) Say "I lost" on national TV.
9) Rickroll Rick Astley.
10) Bomb Uruguay with rotten tomatoes.


What is the maximum number of horses in a chessboard $ 5\times 5$ such that two horses can not attack each other?

My solution:
Because exits knight's tour with table $ 5\times 5$ then we can't lay two knights in two consecutive cell in this tour. It mean maximum number of knight is $ 13$, we can lay at cell $ 1,3,5...,25$ in this tour. (At $ 13$ cells have same colour in chess board).


linear algebra
matrix
algebra
polynomial
linear algebra unsolved

Suppose $ X\in M_n(\mathbb F)$. Prove that $ \text{trace }X \equal{} 0$ if and only if there exist $ A,B\in M_n(\mathbb F)$ which $ X \equal{} AB \minus{} BA$

This has been discussed many times.
This is a file from another topic about the same question.

Here is my solution. You see if $A$ is a matrix which has $n$ different eigenvalues, then if $AB=BA$, you could conclude easily that there exist polynomial $p$ which$B=p(A)$. if you consider the linear operator $f: \mathcal M_n (\mathbb R) \rightarrow \mathcal M_n (\mathbb R)$ which $f(X)=AX-XA$ then $\mbox {Rank } f=n^2-n$. All of matrices that all of elements of their main diagnal is zero are in $\mbox{Im }f$. Now for $S\in \mathcal M_n (\mathbb R)$ if $\mbox{Trace}(S)=0$ then according to [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=89027]this topic[/url] there exist $P\in \mathcal M_n (\mathbb R)$ which all elements of main diagnal of $P^{-1}SP$ are zero. So there exist $X\in \mathcal M_n (\mathbb R)$ which $P^{-1}SP=AX-XA$. So $S=(PAP^{-1})(PXP^{-1})-(PXP^{-1})(PAP^{-1})$, and everything is proved. :D  :D


algebra
polynomial
number theory
least common multiple
group theory
combinatorics unsolved
combinatorics

I'm not sure if this belongs in combinatorics, number theory, or what....but here goes! (Sorry about me never learning TeX, so that it's hard to read...)

Consider the (periodic) sequences defined by setting a_0 = a, a_1 = b, and a_n = a_(n-1) + a_(n-2) (mod k) with a, b positive integers less than k. Show that, for any k, the period length of any sequence divides the maximum period length of all the sequences.

There may or may not be a solution based on group theory, but I'm wondering if there's an easier way...

Without loss of generality we can assume that $k=p^s$ is the power of prime. The minimal polynomial for the sequence $a_0 = a, a_1 = b, a_n = a_{n-1} + a_{n-2}$ over $\mathbb{Z}_k$ is defined as
\[ M_{a,b}(x) = \frac{F(x)}{\gcd(F(x),ax+b-a)}  \]
where $F(x)=x^2 - x - 1$ is a characteristic polynomial.
It is easy to see that $M_{a,b}(x)\mid M_{0,1}(x)=F(x)$ for any $a$ and $b$ implying that the period of any sequence divides the period of the sequence $u_0 = 0, u_1 = 1, u_n = u_{n-1} + u_{n-2}$.

Let $p$ be the period of a particular Fibonacci-type sequence mod $k$, and let $p_{max}$ be the maximum of all such periods.

If you add the sequence of period $p$ and the sequence of period $p_{max}$, then you get a third Fibonacci-type sequence mod $k$ of period $\text{lcm}(p,p_{max})$.

By definition of $p_{max}$, $\text{lcm}(p,p_{max}) \le p_{max}$.  But $p_{max} | \text{lcm}(p,p_{max})$, so $\text{lcm}(p,p_{max}) = p_{max}$, which means that $p | p_{max}$.

[quote="nsato"]Let $p$ be the period of a particular Fibonacci-type sequence mod $k$, and let $p_{max}$ be the maximum of all such periods.

If you add the sequence of period $p$ and the sequence of period $p_{max}$, then you get a third Fibonacci-type sequence mod $k$ of period $\text{lcm}(p,p_{max})$.[/quote]
That's not always the case.

For example, let $k=3$.
The sequence $0,1,1,2,0,2,2,1,0,1,\dots$ has period $p_{max}=8$.
The sequence $0,2,2,1,0,1,1,2,0,1,\dots$ has period $p=p_{max}=8$.
But their sum $0,0,0,\dots$ has period $1$ which is not $lcm(p,p_{max})=8$.

[quote="nsato"]You're right, I should have specified $p < p_{max}$.  The argument still works.[/quote]
Then you need to prove the following claim:
[quote="nsato"]If you add the sequence of period $p$ and the sequence of period $p_{max}$, then you get a third Fibonacci-type sequence mod $k$ of period $\text{lcm}(p,p_{max})$.[/quote]
It is immediately clear only that the period of the sum of these two sequences is a [b]divisor[/b] of $\text{lcm}(p,p_{max})$.

You're right; I just assumed that if you add a sequence of period $a$ and a sequence of period $b$, then you get a sequence of period $\text{lcm}(a,b)$, but in general this is not the case.

I feel like this should have an easy solution; I will have to think more about it.


Let E, F be the projection of B, C onto AC, AB; M, N are the midpoints AC, AB, respectively. K is the intersections of EN, FM. Prove that AK is perpendicular to the Euler line of triangle ABC. :blush:

$ 1). \{K\} \equal{} EN\cap FM\Rightarrow K\in GH; \\
2). \{P\} \equal{} MN\cap EF\Rightarrow AP\perp GH.\\
\mbox{If G\equal{}centroid and H\equal{}orthocenter }\Rightarrow \mbox{ GH\equal{}Euler line of }\triangle{ABC}.$


Let $2001$ point on a circle. Find the number way to write one of three characters $A,B,C$ at a point such that between the 2 same consecutive characters, there are exactly even other characters.


Let ABCD be quadrilateral inscribed in a circle with center O. Prove that sum of the angles AOB and COD = 180°.

Is it true first of all? (i was pointed out by someone that it is only possible if AC and BD are perpendicular diameters).

It is not true for all cyclic quadrilaterals.

Consider

$ \angle A\equal{} 110$
$ \angle B\equal{} 60$
$ \angle C\equal{} 70$
$ \angle D\equal{} 120$

Yeah, that's not true. What IS true is that A+C=B+D=180º

Well, its is true not if the quadrilateral is cyclic, but if the circle is inscribed in the quadrilateral (that is, the circle is tangent to the sides).  :)


inequalities
function
inequalities proposed

For any three positive reals a, b, c, we have

$\frac{a\sqrt{a^2+3bc}}{b+c}+\frac{b\sqrt{b^2+3ca}}{c+a}+\frac{c\sqrt{c^2+3ab}}{a+b} \ge \ a+b+c$

My method in http://www.mathlinks.ro/Forum/viewtopic.php?t=33515 can be applied again. The only changed thing is the function, where the denominator has one more factor $b+c$. But that does not affect the increasing property of the function. I think $\frac{a}{b+c}$ can be replaced by any arrays $x,y,z$ similarly sorted as $a,b,c$.


algebra
polynomial
inequalities solved
inequalities

For $a,b,c\ge0$ prove or disprove:

$2(a^{6}+b^{6}+c^{6})+6a^{2}b^{2}c^{2}\ge\\\ge(a^{5}b+ab^{5}+b^{5}c+bc^{5}+c^{5}a+ca^{5})+2(a^{3}b^{3}+b^{3}c^{3}+c^{3}a^{3})$

[hide="some notes"]Note that if $c=0$ then it becames $2(a^{6}+b^{6})\ge(a^{5}b+ab^{5})+2a^{3}b^{3}$ what is trivial.
Second note that it is related to http://www.mathlinks.ro/Forum/viewtopic.php?t=56369[/hide]

Wrong for a = b = 4 and c = 1 again...

  darij

if $a=x,b=c=1$, then this is equivalent to
$x(x-1)^{2}(x^{3}+x^{2}+x-1)\geq0$,
and this is false to $x$ which is close enough to make $x^{3}+x^{2}+x-1$ negative.


(From Mock AMC 1, #16-20)

Here are the fourth five problems from the first AMC Mock Contest.  Please post your solutions here so that we can hear different methods of doing each problem.

I have also included the source for each problem.

16.  For what values of p does the equation px:^2: - 4x + p = 0 have non-real solutions?
(A) -2 < p < 2
(B) p > 2 or p < -2
(C) p > 2
(D) p < 2
(E) all real values of p

Source: ?

17. There are four integers a, b, c, d such that d = 5a + 3b + 5c and d = 4a + 5b + 4c.  Suppose 131 :le: d :le: 150.  What is the value of a + b + c?
(A) 11
(B) 22
(C) 33
(D) 44
(E) 55

Source: MMPC, Round 1, 1998

18. What is the coefficient of x^5*y^2*z^2 in the expansion of (x+y+2z)^9?
(A) 126
(B) 756
(C) 6048
(D) 2016
(E) 3024

Source: CSU Math Tournament, 2000

19. Consider the triangular array
1
2 3
4 5 6
...........

What is the sum of the elements in the 100th row?
(A) 1000100
(B) 1000000
(C) 500000
(D) 500050
(E) 5000050

Source: Univ. Maryland 1998 Round 1

20. The quadratic polynomial f(x) satisfies f(0) = 3, f(1) = 5, f(2) = 8.  Find f(5).
(A) 22
(B) 23
(C) 24
(D) 25
(E) none of the above

Source: Univ. Maryland 1998 Round 1

- mathfanatic

16) Discriminant is 16 - 4p:^2: < 0. p:^2:>4, [b]B[/b].

17) Ahha! I cheated here, didn't use the info about d being between those two values. Subtracting our two equations gives a - 2b + c = 0, so a+b+c = 3b. Only one multiple of 3 in the answers. [b]C[/b].

18) Think of it written out in 9 separate brackets. We have to choose 5 of them for the xs, 9C5 ways. Out of the other 4 brackets, we have to choose 2 for the ys, 4C2 ways. Finally, our coefficient is 9C5 x 4C2 x 2^2 for the z bit. [b]E[/b].

19) First calculate first number in the nth row: You can see its 1, 1+1, 1+1+2, 1+1+2+3.. which is 1 + n(n-1)/2. So first number in 100th row is 4951. There are 100 elements in the row, so sum = 50(2x4951 + 99), which is [b]D[/b].

2)) Just bash this out with algebra. It is of form ax:^2: + bx + 3. a+b = 2, 4a+2b = 5. a=0.5, b=1.5. f(5) = [b]B[/b].

Yeah!  Go TripleM.

The only question remaining is why no one else is answering...sigh...you don't have to answer them all, guys...if you've got a solution to one, throw it out there.  *prays*

um. all my solutions correlate with MMM except for the ones i posted. how many solutions do you expect for not-so-hard problems??

well if you didn't have the answer choices for 17,  you could multiply the 2nd equation and add it to the first to get 3d = 13(a+b+c), and since  131 :le: d :le: 151, and there's only 1 multiple of 13 there, you know the answer.

[quote="TripleM"]
18) Think of it written out in 9 separate brackets. We have to choose 5 of them for the xs, 9C5 ways. Out of the other 4 brackets, we have to choose 2 for the ys, 4C2 ways. Finally, our coefficient is 9C5 x 4C2 x 2^2 for the z bit. [b]E[/b].

i think you recount it for 3 more times. Mine is 9C5*4C2=756 [B], I can't see why I have to multiply it with 2^2.


inequalities
number theory solved
number theory

Find the solution of the following inequality for positive integers  $a,b,c $such that  $a>b>c.$

$ab+1\leqq abc\leqq bc+ca+ab+1$

Well, I do not see where we have to use the lattice...maybe is there a geometric interpretation...

Since $a,b,c$ are positive integers, the left inequality is clearly equivalent to $c \geq 2$.
Now, if $c \geq 3$ then the right inequality would implies that
$2ab \leq bc + ca + 1$.
But $b \geq c+1$ and $a \geq c+2$ then $2ab = ab + ab \geq ac+a+bc+b > ac + bc + 1$, a contradiction.

It follows that $c=2$ and the right inequality becomes :
$ab \leq 2a+2a+1$ which is equivalent to $(a-2)(b-2) \leq 5$.
Since $a-2 > b-2 \geq 1$ we easily deduce that the solutions are $b=3$ and $a \in \{4,5,6,7 \}$.

Pierre.

Thank you for your reply, Pierre!

My solution is exactly same as yours.

kunny


Hey Guys!

Our lovely math teacher gave us the following exercise:

Prove the following statement:
In an acute-angled triangle ABC meets the median-line m_b the bisecting line b_a and the altitude a_c in one point if the circle around the foot of the altidude A_c through A meets the bisecting line b_a and BC in one point.

To make it more understandable I made a short sketch of such an Triangle:

[url=http://img228.imageshack.us/my.php?image=trianglewd2.jpg&s=1][img]http://img228.imageshack.us/img228/4327/trianglewd2.th.jpg[/img][/url]

Greetz, Piero

Have you read the instructions on the backside of the paper your lovely math teacher gave you? Locked until 8 March 2008 (that is one week after the deadline).

  darij


calculus
integration
number theory proposed
number theory

Find all n is integer such that there exist a regular polygonal n vertices which they lie on the interal point.

[hide]This is famous problem, answer $n=4$  :wink:  [/hide]


Following the example of Palytoxin, I have copied the first 78 problems of the MATHCOUNTS Problem Solving Marathan into an attached PDF. Sorry it couldn't be as good as Palytoxin's. That would take a LOT of time and effort!

wow, thanks chess64, i am going to print this and try to do it...again thanks for your time. :)

it doesn't really matter how good it is, but if anyone even attempts to do this, it is a great accomplishment  :)

[quote="anirudh"]I was talking about me[/quote]

Oh..., I see. I thought you meant that you would try to make the PDF too.

Now I see that you mean you will try to complete the problems. In that case, it is considered spamming. We don't need to know that you're going to do it. That's what I made the PDF for, so that's what most people are going to do. ;)


1)  Find the first 3 positive integers $x$ for which $\sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}$ is an integer.

2)  Find a polynomial $f(n)$ with integer coefficients such that for all positive integers $n$, $\sqrt{f(n)+\sqrt{f(n)+\sqrt{f(n)+\cdots}}}$ is an integer.

1.
[hide]let $y=\displaystyle \sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}$
$y=\sqrt{x+y}$
$y^2=x+y$
$y(y-1)=x$
so the first 3 occur when $y = 2,3,$ or $4$ so $x=\boxed{2,6, 12}$[/hide]

[quote="Danbert"]2)  Find a polynomial $f(n)$ with integer coefficients such that for all positive integers $n$, $\sqrt{n+\sqrt{n+\sqrt{n+\cdots}}}$ is an integer.[/quote]

I suppose you mean $f\left(\sqrt{n+\sqrt{n+\sqrt{n+\cdots}}}\right)$, because the fact that $\sqrt{n+\sqrt{n+\sqrt{n+\cdots}}}$ is an integer or not does not depends on $f$. Nevertheless

[hide="What about..."]$f(x)=x^2-x$[/hide]

Sorry, stupid mistake in typing.  A fine example of what I post at 1 in the morning... :D

It's fixed now.

What do you mean by at least two square roots?

I he means it must be at least $\sqrt {x + \sqrt { x}}$, and you can add more radicals with x-s if you want.

[quote="white_horse_king88"][quote="Myth"]An additional problem ;)

Prove that $\sqrt{x+\sqrt{x+\sqrt{x+\sqrt{\cdots+\sqrt{x}}}}}$ is not an integer for all integer $x$ if there are at least two square roots.[/quote]

Um, I'm not going to do some fancy proof, but I reasoned this out.

[hide]We want to show that if there's at least 2 square roots, for all integers $x$ the expression isn't an integer.

It's obvious that if $x$ is not a perfect square, $\sqrt{x}$ isn't an integer.

Begin with $\sqrt{x + \sqrt{x}}$. Let $x = n^2$, where $n$ is a positive integer.
$\sqrt{n^2 + n} = y \Rightarrow n^2 + n = y^2$, where $y$ is a positive integer.
$n^2 + n > n^2$, obviously, so $n^2 + n \ge (n+1)^2$. If $n^2 + n \ge (n+1)^2$, then $n \le -1$. This is a contradiction, so the original statement is proven?[/hide]
This is a contradiction, so the original statement is proven?
[/quote]

No my friend, it is not proven, scentially because you are considering the most particular case of all. It ask for the most specific case of all, because it ask for any integer $x$ and any number of roots, as long as there are at least two, but you consider the case where $x$ is a perfect square and the expression has exactly two roots. For that specific case, your solution is correct. But if you see, you already did most of the dirty work. An idea that you can consider

[hide="Idea"]
If $n$ is an integer and $\sqrt{n+y}$ is also an integer, then $y$ has to be an integer.
[/hide]

That should solve the problem. There is also the other direction of bounding  and bounding, but that may not work too well, I haven't tried yet.

By the way Myth, it is pretty nice question, I mean, it seems to be challenging enough for the forum on which it is posted but not out of reach  :D .


Prove that in any triangle:
$ \cdot \sum \frac{cos^3{\frac{A}{2}}}{sin{\frac{A}{2}}}\plus{}\cdot \sum cos A \le \frac{1}{3\sqrt{3}}$

Really?

$ A\equal{}B\equal{}C\equal{}\frac{\pi}{3} \ \ \Rightarrow \ \ \sum_{cyc}\frac{\cos^3 \frac{A}{2}}{\sin \frac{A}{2}} \plus{} \sum_{cyc} \cos A \equal{} \frac{9\sqrt{3}}{4} \plus{} \frac{3}{2} \geq \frac{1}{3\sqrt{3}}$

[quote="Kouichi Nakagawa"]Really?

$ A = B = C = \frac {\pi}{3} \ \ \Rightarrow \ \ \sum_{cyc}\frac {\cos^3 \frac {A}{2}}{\sin \frac {A}{2}} + \sum_{cyc} \cos A = \frac {9\sqrt {3}}{4} + \frac {3}{2} \geq \frac {1}{3\sqrt {3}}$[/quote]
I'm sorry! Problem:
Prove that:
${ \sum_{cyc}\frac {\cos^3 \frac {A}{2}}{\sin \frac {A}{2}} + \frac{3\sqrt{3}}{2}(\sum_{cyc} \cos A}) \le \frac {9\sqrt{3}}{2}$

___________
I've edited! Sorry hell_ever.

[quote="NguyenDungTN"][quote="Kouichi Nakagawa"]Really?

$ A \equal{} B \equal{} C \equal{} \frac {\pi}{3} \ \ \Rightarrow \ \ \sum_{cyc}\frac {\cos^3 \frac {A}{2}}{\sin \frac {A}{2}} \plus{} \sum_{cyc} \cos A \equal{} \frac {9\sqrt {3}}{4} \plus{} \frac {3}{2} \geq \frac {1}{3\sqrt {3}}$[/quote]
I'm sorry! Problem:
Prove that:
$ \sum_{cyc}\frac {\cos^3 \frac {A}{2}}{\sin \frac {A}{2}} \plus{} \frac {\sum_{cyc} \cos A}{6\sqrt {3}} \le \frac {1}{2\sqrt {3}}$[/quote]

But this is also false!
Put $ A\equal{}B\equal{}C\equal{}\pi/3$


geometry
rectangle
perimeter
Pythagorean Theorem

A rectangle is circumscribed by a circle. The circle has radius $ 6$; the rectangle has perimeter $ 28$. Find the area of the rectangle.

[hide="Solution"]Since the rectangle is circumscribed in a circle, it's diagonal is the circle's diameter, which is $ 2\cdot 6 \equal{} 12$.  Call the rectangle's length $ l$, and it's width $ w$.  We are given that $ 2l \plus{} 2w \equal{} 28\implies l \plus{} w \equal{} 14$.  By Pythagorean Theorem, $ l^2 \plus{} w^2 \equal{} 12^2 \equal{} 144$.  We can square both sides of $ l \plus{} w \equal{} 14$ to yield $ l^2 \plus{} w^2 \plus{} 2lw \equal{} 196$.  Substituting yields $ 144 \plus{} 2lw \equal{} 196\implies lw \equal{} 26$.  Thus, the area of the rectangle is $ \boxed{26}$[/hide]


algebra
polynomial
analytic geometry
inequalities

What is the largest value  of k < 9 for which a polynomial y=f(x) with integer coefficients can have a graph that passes through (3,9) and (8,k)

This was from the High School Math Contest book.

This [i]is[/i] from [i]High School Math Contests[/i]; the latest volume to be specific.
[hide="Solution"]
Let $ f(x)\equal{}\left( 3 \minus{} x \right) \plus{}9$
Then $ f(3)\equal{}9$ and $ \boxed{f(8)\equal{}4}$.
[/hide]

um the answer that my teacher gave us was [hide="this"]5...[/hide] but she didn't explain

The solution in the [i]HS Math Contest[/i] book shows
[hide="this"]
$ 4$.
[/hide]

[quote="AstroPhys"]This [i]is[/i] from [i]High School Math Contests[/i]; the latest volume to be specific.
[hide="Solution"]
Let $ f(x) \equal{} \left( 3 \minus{} x \right) \plus{} 9$
Then $ f(3) \equal{} 9$ and $ \boxed{f(8) \equal{} 4}$.
[/hide][/quote]

Why did you let $ f(x) \equal{} \left( 3 \minus{} x \right) \plus{} 9$?
And how did you deduce that $ f(8) \equal{} 4$?

[hide="Hinty Explaination"]
Make the x-coordinate of the first point a zero of some polynomial with integer coefficients. Add 9 to the that polynomial and it yeilds $ f(x)$.
Just find $ f(8) \equal{} 3 \minus{} 8 \plus{} 9 \equal{} 4$.
[/hide]

The book has a couple methods in the solution for this but, I do not know if this is one of them.

I don't see why there can't be a higher degree polynomial other than linear ones?

How come you just assume the maximum is when $ f(x)\equal{}(x\minus{}3)\plus{}9$? Why not $ f(x)\equal{}(x\minus{}3)g(x)\plus{}9$?

Well, $ g(x)$ has to be a polynomial with integer coefficients. Thus $ g(8)$ is an integer, and $ f(8) \equal{} \minus{}5 \cdot g(8) \plus{} 9$. Since we have $ f(8) < 9$, it follows that we maximize $ f(8)$ by letting $ g(8) \equal{} 1$.

[quote="azjps"]Well, $ g(x)$ has to be a polynomial with integer coefficients. Thus $ g(8)$ is an integer, and $ f(8) \equal{} \minus{} 5 \cdot g(8) \plus{} 9$. Since we have $ f(8) < 9$, it follows that we maximize $ f(8)$ by letting $ g(8) \equal{} 1$.[/quote]

Yea, ok. Thanks. Stupid me.

Of course there can be higher degrees, just for simplicity I used the first degree.
Actually, I just looked and the book uses a similar approach to solving it with linear ploynomial.
The method 123456789 is using is also used
[hide="as"]
paraphrased
$ f(x)\equal{}(x\minus{}3)g(x)\plus{}9$ would sastisfy the restrictions with $ g(x)$ being a ploynomial with integer coefficients.
Then $ f(8)\equal{}k\equal{}5 \cdot g(8) \plus{}9 < 9$.
Solving the inequality for integer $ g(8)$, $ g(8) \le \minus{}1$.
Since $ k$ needs to be a maximum, let $ g(8)\equal{}\minus{}1$ and $ \boxed{k\equal{}\minus{}5\plus{}9\equal{}4}$.
[/hide]


Let S be the set of all integers in the form 2^x*3^y (x,y are integers) that have units digit 8.  Find the sum of the reciprocals of all the elements of S.

Is this a challenge, or do you want to know how to do it?

Just a challenge...I'm curious to see how others solve it.

[hide]all numbers will be of the form 2^(4a)*3^(4b)*6^c*3, 0:le:c<3, a:ge:1, b:ge:0. 1/3(1/1+1/6+1/36+1/216)=259/648. We multiply this by (1/16+1/256+1/16^3+...)(1+1/81+1/81^2+...)=1/15*81/80. So, we have 259/648*1/15*81/80=259/9600. Hmm...probably some minor arithmetical errors somewhere...or maybe the whole thing's wrong. Anyways, Correct?[/hide] That's an interesting signature you've got there...

[hide]I found 91/400 ...

If it's correct (it involves many ugly sums) I will say how I found it.

"all numbers will be of the form 2^(4a)*3^(4b)*6^c*3"

I'm not sure I understand this because 2^3=8 (or 2^7) has unit digit 8 and is not of this form     [/hide]

Si, mystic.  I think I did it the way you did and I discovered some flaws with that.  What about the case 2^3+3^0?

Belenos is right.  Mystic is missing something....I think its 2^3.

I'm too lazy to check the other solutions, but here's mine: (2^a (mod 10), 3^b (mod 10)) can be (2, 9), (4, 7), (8,1), or (6,3). The sum of the reciprocals of the first is 72/1295, the second is 12/1295, the third is 162/1295, and the fourth is 27/1295. Thus the sum is 273/1295=39/185. Is that right?

Nope...

The sum of the recipocals of 2^a = 8 mod 10 and 3^b = 1 mod 10 is 1/8(1+1/16+1/16^2+.....)(1+1/81+1/81^2+....).

The other 3 cases are similar.

If Simon had known how to sum infinite series, his answer would have been 91/400. Don't ask.


trigonometry
logarithms
integration
calculus
real analysis
real analysis unsolved

Evaluate $ \displaystyle\sum_{n\equal{}0}^\infty \dfrac{(\minus{}1)^n}{an\plus{}b}$ where a and b are positive integers.

$ \sum_{n\equal{}0} ^\infty \frac{(\minus{}1)^n}{an\plus{}b}\equal{}\frac{1}{2a} \left[\psi\left(\frac12\plus{}\frac{b}{2a}\right)\minus{} \psi\left(\frac{b}{2a}\right)\right]$

After that you can use the digamma theorem.
$ \psi\left(\frac {p}{q}\right) \equal{} \minus{} \gamma \minus{} \ln(2q) \minus{} \frac {\pi}{2}\cot\left(\frac {p\pi}{q}\right) \plus{} \sum_{k \equal{} 1}^{q \minus{} 1} \cos\left(\frac {2\pi p k}{q}\right)\, \ln\,\sin\left(\frac {k\pi}{q}\right)$

See this [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=154709]link[/url].

The nicest answer is that it's $ \int_0^1 \frac{x^{1\minus{}b}}{1\plus{}x^a}\,dx$. That integral is doable, but it isn't nice in general.

Making that a sum from $ \minus{}\infty$ to $ \infty$ gives a much cleaner result.
See also [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?&t=21316]here[/url].


invariant
combinatorics
algorithm
IMO Shortlist

Let $n$ be an integer greater than 2. A positive integer is said to be [i]attainable [/i]if it is 1 or can be obtained from 1 by a sequence of operations with the following properties:

1.)  The first operation is either addition or multiplication.

2.) Thereafter, additions and multiplications are used alternately.

3.)  In each addition, one can choose independently whether to add 2 or $n$

4.)  In each multiplication, one can choose independently whether to multiply by 2 or by $n$.

A positive integer which cannot be so obtained is said to be [i]unattainable[/i].

[b]a.)[/b]  Prove that if $n\geq 9$, there are infinitely many unattainable positive integers.

[b]b.)[/b]  Prove that if $n=3$, all positive integers except 7 are attainable.

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

[b]a)[/b]
First suppose that $n$ is even. Then all odd numbers $>n+1$ are unattainble, since after a multiplication in the sequence the number becomes and remains even.

So we may assume that $n$ is odd.
We define +attainable to mean an attainable integer, where the last operation in the sequence to reach it is +2 or +n, similarly x-attainable for multiplication.

We prove that no integers $\equiv-2 \mod (n-2)$ are +attainable.
Suppose that $t \equiv-2 \mod (n-2)$ is the least counterexample to this claim. Whether this addition be +2 or +n, the previous member of the sequence is $u \equiv-4 \mod (n-2)$. This must have been obtained by multiplication, and since it is not divisible by $n$, it must be a multiplication of $2$ that was the last operation before $u$. Thus the member of the sequence before $u$ is $\equiv-2 \mod (n-2)$, and this number must have been +attainable and $<t$, a contradiction.

But there are infinitely many odd integers $\equiv-2 \mod (n-2)$, and none of them can be x-attainable since they are divisible by neither $2$ nor $n$. Hence all these integers are unattainable.

[b]b)[/b]
Define a sequence $b_{i}$ as follows: $b_{0}=0, b_{1}=7$, $b_{n+1}=2(b_{n}+1)$. ($n \geq 1$).

We prove by induction that all integers not in this sequence are +attainable. [color=red](*)[/color]

Observe that this is true of all integers $b_{0}< m < b_{1}$ and $b_{1}< m < b_{2}$.
Assume that it is true of all integers $b_{k-1}< m <b_{k}$ and $b_{k}< m < b_{k+1}$. Then all the even integers $b_{k+1}, b_{k+1}+2, ... ,b_{k+2}-4$ are x-attainable. From this all integers $b_{k+1}+1 < m < b_{k+2}$ are +attainable. Note that $3|b_{n}-1$. By the inductive hypothesis, $\frac{1}{3}(b_{k}-1)$ is +attainable, so $b_{k}-1$ is x-attainable and so $b_{k+1}+1$ is +attainable.
Hence all integers $b_{k+1}< m < b_{k+2}$ are unattainable, and [color=red](*)[/color] is true by induction.
Since $b_{k}+1$ is always +attainable, $2(b_{k}+1)=b_{k+1}$ is x-attainable. Hence $b_{2}, b_{3}...$ etc. are all attainable also. Therefore all positive integers except $b_{1}=7$ are 3-attainable.

I am probably being stupid, but why does $n$ not divide numbers of the form $k(n-2)-4$ (-4 modulo n-2)? If $n$ divides $k+2$, then that is not true, right? If so, I'm not quite sure how to patch up the hole in the otherwise very elegant proof...

A way to fix the above proof:
[hide][quote]We prove that no integers $\equiv-2 \mod (n-2)$ are +attainable.
Suppose that $t \equiv-2 \mod (n-2)$ is the least counterexample to this claim. Whether this addition be +2 or +n, the previous member of the sequence is $u \equiv-4 \mod (n-2)$. This must have been obtained by multiplication, and since it is not divisible by $n$, it must be a multiplication of $2$ that was the last operation before $u$. Thus the member of the sequence before $u$ is $\equiv-2 \mod (n-2)$, and this number must have been +attainable and $<t$, a contradiction.[/quote]
While it's false that $u$ can't be divisible by $n$, it doesn't matter: we have in any case
\[\frac{u}{2}\equiv \frac{u}{n} \equiv -2 \mod n-2\]
which produces the desired contradiction.

[quote=]But there are infinitely many odd integers $\equiv-2 \mod (n-2)$, and none of them can be x-attainable since they are divisible by neither $2$ nor $n$. Hence all these integers are unattainable.[/quote]

While it isn't true that [b]every[/b] integer $\equiv -2 \mod n-2$ is not divisible by either 2 or $n$, it's enough to show that there are infinitely integers that do satisfy this. Take for example the set of positive integers of the form
\[kn(n-2)-2\]
where $k$ is odd. They are not divisible by either $2$ or $n$, and are congruent to $-2$ modulo $n-2$. Anyway, cool idea!
[/hide]

[b]Part A[/b]
Let $n$ be odd. Note that since $\gcd(2,n-2,n)=1$ there are infinitely many positive integers $a\equiv -2\pmod {n-2}$ such that $a$ is divisible by neither $2$ nor $n.$
\\$~$\\
Suppose $a$ is attainable then a's predecessor, $b$, would've been $\equiv -4\pmod {n-2}$ so $b\neq 1$ Now, let $b$'s predecessor be $c$ and we have $a\equiv 2c+2\pmod {n-2}$ and so $c\equiv -2 \pmod {n-2}$. Now, continuing this process we can infinitely generate numbers in our list that is $\equiv -2\pmod {n-2}$ which is a contradiction.
\\$~$\\
Let $n$ be even. Note that almost every odd number then is unattainable.

[b]Part B[/b]
Call a number $a$ $A$-good if it is attainable with the move that got to $a$ being addition. Call it $M$-good if it is attainable with the move that got to $a$ being multiplication.
\\$~$\\
Note that $3,4,5,6$ are $A$-good and if $a$ is $A$-good then $2a+2,2a+3,3a+2,3a+3$ are all $A$-good. Thus, we have any number in $\{8,9,\dots,15\}$ is $A$-good, from multiplying $2$ and adding $2$ or $3$.
\\$~$\\
Now, if any positive integer in $[a+1,2a+1]$ is $A$-good then $2a+4,2a+3,\dots,4a+5$ are $A$-good and if we can show that $2a+3$ is $A$-good then we have $[2a+3,4a+5]$ are $A$-good which implies all numbers except the sequence $b_0=7,b_n=2b_{n-1}+2$ and the number $2$ are $A$-good.
\\$~$\\
To look at $2a+3$ we note that this number is one more than any number in the sequence $b$ so it is equivalent to $2$ mod $3.$ Thus, it remains to show that $\frac{2a+1}{3}$ is not in sequence $b.$ Note that the sequence $b_n$ has terms $\equiv 7\pmod 9$ and so $\frac{2a+1}{3}\equiv 2\pmod 3$ so it is not a term in the sequence. Thus, it is $A$-good.
\\$~$\\
We now only need to show that numbers in $b_n,n\ge 1$ are $M$-good. This reduces to showing $b_{n-1}+1$ is $A$-good, which is true. Note that $2=1\times 2$ is attainable. Thus, we are done.

[quote=AliAlavi]a) after 2t+1 operation the maximum value of number that we can make is f(t)=n^t+n^(t-1)+...+1
and the operations can make less than g(t)=2^(2t+1)
so f(t)-g(t) is a Increment function[/quote]

For example, let $f(x)=x^2,g(x)=x$?

Solution to part (b) is extremely confusing.

First, define an addable integer to be one which is attainable with the last operation being addition. Similarly, define a multiplicable integer to be one which is attainable with the last operation being multiplication. For the sake of convenience, let $1$ be both addable and multiplicable.
[b]a.)[/b] Clearly when $n$ is even we are done. Otherwise, consider the sequence $a_1=n+4$, and defined recursively as $a_{i+1}=2a_i+n$ for $a_i\not \equiv 1\pmod n$ and $a_{i+1}=4a_i+n+4$ for $a_i\equiv 1\pmod n$. It's important to note that we always have $a_i\equiv 1\pmod 2$ and $a_i\not \equiv 0,2\pmod n$. I claim that every term in the sequence is unattainable. It's easy to see that $a_1=n+4$ is unattainable. Now, suppose that $a_i$ is unattainable and $a_i\not\equiv 1\pmod n$. Then note that if $a_{i+1}$ is attainable then the last two operations must be $\times 2$ followed by $+n$. This implies that $a_i$ is addable, a contradiction. Otherwise, suppose that $a_i\equiv 1\pmod n$. Then if $a_{i+1}$ is attainable then $2a_i+2$ is addable. This implies that $a_i$ is addable, a contradiction.
[b]b.[/b] We attempt to find all numbers which aren't addable. If we work backwards, we see that we can always find a path which leads back to either $1$ or $2$ (the proof being one by contradiction). For example, we have $$20\rightarrow 18\rightarrow 9\rightarrow 6\rightarrow 3\rightarrow 1$$ and $$34\rightarrow 32\rightarrow 16\rightarrow 14\rightarrow 7\rightarrow 4\rightarrow 2.$$ Ignore every other step; they are irrelevant to the solution. Now, if a number isn't addable, then any paths leading from it must end at $2$. If this occurs, then the second to last number in the sequence is either $6$, $7$, $8$, or $9$. Checking, we find that if the number is $6$, $8$, or $9$, there is some alternate path which leads back to $1$. Now, consider the sequence $b_1=7$, and $b_{i+1}=2b_i+2$ for all $i\ge 1$. Consider our sequence after $k$ steps. Then I claim that the last numbers in the path must be $b_k,b_{k-1},\dots,b_1,2$. We have already shown the base case of $k=1$. Otherwise, note that the $k+1$th to last number in the path must be $2b_{k-1}+2$, $2b_{k-1}+3$, $3b_{k-1}+2$, or $3b_{k-1}+3$. If it's one of the last three, we can just find a new path where the $k$th to last number isn't $b_{k-1}$ by selecting different operations for that step. However, if $2b_{k-1}+2$ is the $k+1$th to last number, we're forced to have the $k$th to last number be $b_{k-1}$.

This is enough to imply that all numbers in this path, if we continued infinitely, aren't addable, while all numbers not in this path are. For all even numbers in the path, we can note that they are multiplicable since we can just divide by $2$ and obtain an addable number. The only odd number in the path is $7$. This is unattainable by finite case check. We are done. $\blacksquare$

[quote=AliAlavi]a) after 2t+1 operation the maximum value of number that we can make is f(t)=n^t+n^(t-1)+...+1
and the operations can make less than g(t)=2^(2t+1)
so f(t)-g(t) is a Increment function[/quote]

+1 ^2 contradicts this


logarithms
inequalities
calculus
derivative
function
algebra unsolved
algebra

[quote="freemind"]Let $x_{1}$, $x_{2}$, $\ldots$, $x_{n}$ be $n$ real numbers in $\left(\frac{1}{4},\frac{2}{3}\right)$. Find the minimal value of the expression: \[ \log_{\frac 32x_{1}}\left(\frac{1}{2}-\frac{1}{36x_{2}^{2}}\right)+\log_{\frac 32x_{2}}\left(\frac{1}{2}-\frac{1}{36x_{3}^{2}}\right)+\cdots+ \log_{\frac 32x_{n}}\left(\frac{1}{2}-\frac{1}{36x_{1}^{2}}\right).  \][/quote]
by the rearrange Inequality we have:
$RHS=\log_{\frac 32x_{1}}\left(\frac{1}{2}-\frac{1}{36x_{2}^{2}}\right)+\log_{\frac 32x_{2}}\left(\frac{1}{2}-\frac{1}{36x_{3}^{2}}\right)+\cdots+ \log_{\frac 32x_{n}}\left(\frac{1}{2}-\frac{1}{36x_{1}^{2}}\right)\geq \sum_{i=1}^n {\log_{\frac 32x_{i}}{(\frac12-\frac{1}{36x_{i}^{2})}}}$
ang then we should miniumize the expression $\log_{\frac 32x}{(\frac12-\frac{1}{36x^{2}})}$
but I can't solve it.
Who have the interest?

Let ${f(x)=\log_{\frac{3}{2}x}{(\frac{1}2-\frac{1}{36x^{2}})}=\log( {72x^2}\over {36x^2-2}})/\log( {2\over {3x}}).$ Taking the first derivative, and apart from some positive factors, we get the term $\log[ 2^y\cdot{{y+1}\over 8}\cdot ( 1+{1\over y})^y],$ where $y=18x^2-1.$ Clearly every term in the logarithm is an increasing function in $y,$ and the logarithm becomes zero at $y=1,$ which is in the allowed range of values for $y,$ namely $1/8<y<7.$ Thus, $y=1\leftrightarrow x=1/3$ is the only value for which $f'(x)=0.$ Checking the second derivative at $x=1/3$ we see that this value corresponds to a minimum, which is $f_{\rm min}=2.$

First we see that $\frac{3}{2}x_{i}<\frac{3}{2}\cdot\frac{2}{3}=1$.
Now from AM-GM we have: $\frac{1}{4}\leqslant \frac{\frac{1}{(6x_{i})^{2}}+\frac{(6x_{i})^{2}}{16}}{2}$ so as the base of the logarithms is smaller than 1 we have:
$\sum_{i=1}^{n}\log_{\frac{3}{2}x_{i}}\left(\frac{1}{2}-\frac{1}{36x_{i+1}^{2}}\right)\geqslant \sum_{i=1}^{n} \log_{\frac{3}{2}x_{i}}\left(\frac{(6x_{i+1})^2}{16}\right)$. Finally, using AM-GM we have:
$2\sum_{i=1}^{n} \log_{\frac{3}{2}x_{i}}\left(\frac{6x_{i+1}}{4}\right)\geqslant 2n\sqrt[n]{\prod_{i=1}^{n}\log_{\frac{3}{2}x_{i}}\left(\frac{3}{2}x_{i+1}\right)}$.
Now if we denote $\frac{3}{2}x_{i}=y_{i}$ we have: $\sum_{i=1}^{n} \log_{\frac{3}{2}x_{i}}\left(\frac{1}{2}-\frac{1}{36x_{i+1}^{2}}\right)\geqslant 2n\sqrt[n]{\frac{\prod \lg y_{i+1}}{\prod \lg y_{i}}}=2n$


If  a,b,c are  positive numbers, such as $ abc\equal{}1$   then

                                                    $ a^{4}c\plus{}b^{4}a\plus{}c^{4}b\ge ab\plus{}bc\plus{}ca$

[quote="NguyenDungTN"][quote="soruz"]If  a,b,c are  positive numbers, such as $ abc \equal{} 1$   then

                                                    $ a^{4}c\plus{}b^{4}a\plus{}c^{4}b\ge ab\plus{}bc\plus{}ca$[/quote]
Inequality equivalent to:
 $ a^{4}c\plus{}b^{4}a\plus{}c^{4}b\ge abc(ab\plus{}bc\plus{}ca)$

Which is true by Muirhead! [4,0,1]>>[2,2,1][/quote]
Are you sure? :wink:

[quote="NguyenDungTN"][quote="soruz"]If  a,b,c are  positive numbers, such as $ abc \equal{} 1$   then

                                                    $ a^{4}c\plus{}b^{4}a\plus{}c^{4}b\ge ab\plus{}bc\plus{}ca$[/quote]
Inequality equivalent to:
 $ a^{4}c\plus{}b^{4}a\plus{}c^{4}b\ge abc(ab\plus{}bc\plus{}ca)$

Which is true by Muirhead! [4,0,1]>>[2,2,1][/quote]
note that muirhead is true for symmetric sums...
so by muirhead we get that:
$ a^{4}b\plus{}a^{4}c\plus{}b^{4}c\plus{}b^{4}a\plus{}c^{4}a\plus{}c^{4}b\geq 2(a^{2}b^{2}c\plus{}a^{2}c^{2}b\plus{}b^{2}c^{2}a)$

[quote="soruz"]If  a,b,c are  positive numbers, such as $ abc \equal{} 1$   then

                                                    $ a^{4}c\plus{}b^{4}a\plus{}c^{4}b\ge ab\plus{}bc\plus{}ca$[/quote]

Just BCS,
$ a^{4}c\plus{}b^{4}a\plus{}c^{4}b \equal{}\frac{a^{3}}{b}\plus{}\frac{b^{3}}{c}\plus{}\frac{c^{3}}{a}\equal{}\frac{a^{4}}{ab}\plus{}\frac{b^{4}}{ac}\plus{}\frac{c^{4}}{ac}\geq\frac{(a^{2}\plus{}b^{2}\plus{}c^{2})^{2}}{ab\plus{}bc\plus{}ca}\geq\frac{(ab\plus{}bc\plus{}ca)^{2}}{ab\plus{}bc\plus{}ca}\equal{} ab\plus{}bc\plus{}ca$


Putnam
modular arithmetic
linear algebra
matrix
induction
floor function
function

Let $ n$ and $ k$ be positive integers. Say that a permutation $ \sigma$ of $ \{1,2,\dots n\}$ is $ k$-[i]limited[/i] if $ |\sigma(i)\minus{}i|\le k$ for all $ i.$ Prove that the number of $ k$-limited permutations of $ \{1,2,\dots n\}$ is odd if and only if $ n\equiv 0$ or $ 1\pmod{2k\plus{}1}.$

Solution I overheard after the test:

The parity of the number of $ k$-limited permutations is precisely the determinant of the matrix with $ 1$s at every entry within $ k$ entries of the main diagonal taken $ \bmod 2$.  (Note that in the permutation expansion of the determinant $ \text{sgn}(\pi) \equiv 1 \bmod 2$, so over $ \mathbb{F}_2$ the determinant and the [url=http://en.wikipedia.org/wiki/Permanent]permanent[/url] are identical.)  I haven't gone through the details, but the rest is linear algebra.

This is a lovely problem! There are several ways to approach it, I think.

Here's one way. Fix $ k$ and consider $ n \ge 0$ (with the convention that there is exactly one permutation on the empty set). Let $ A(n)$ be the $ n \times n$ matrix defined by
\[ A(n)_{ij} \equal{} \left\{\begin{array}{lc} 1 & \textnormal{ if }|i \minus{} j| \le k, \\
0 & \textnormal{ otherwise}. \end{array} \right.
\]
For example, if $ k \equal{} 2$,
\[ A(5) \equal{} \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 \\
\end{bmatrix}.
\]
$ \prod_{i \equal{} 0}^n A(n)_{i \sigma(i)} \equal{} 1$ if $ \sigma$ is $ k$-limited, and $ \prod_{i \equal{} 0}^n A(n)_{i \sigma(i)} \equal{} 0$ otherwise. Hence the number of $ k$-limited permutations on $ n$ is
\[ \sum_{\sigma \in S_n}\prod_{i \equal{} 0}^n A(n)_{i \sigma(i)}.
\]
This is the unsigned determinant (known as the "permanent"). There are lots of nice results known about permanents, for instance the MacMahon Master Theorem, all of which are totally distracting. All we really need is that the permanent is congruent to the determinant modulo 2.

It turns out that $ \det A(n)$ (over the real numbers) is either $ 0$ or $ \pm 1$. We want to show that $ \det A(n) \equal{} \pm 1$ if $ n \equiv 0, 1 \mod 2k \plus{} 1$ and that $ \det A(n) \equal{} 0$ otherwise.

One way we can prove this is by induction on $ n$. The base cases $ n \equal{} 0, 1, \ldots 2k$ follow with the convention that $ \det A(0) \equal{} 1$ and noting that $ \det A(n) \equal{} 0$ for $ n \equal{} 2, \ldots , 2k$, since for such $ n$, $ A(n)$ has two rows of all-ones.

Now we consider $ A(n)$ for $ n \ge 2k \plus{} 1$. For $ i \equal{} k, k \minus{} 1, \ldots, 1$ (in that order), we add $ \minus{} 1$ times row $ i$ to row $ i \plus{} 1$. This gives a matrix with a $ 1$ in positions $ (2, k \plus{} 2), (3,k \plus{} 3), \ldots , (k \plus{} 1, 2k \plus{} 1)$, where these are the only nonzero entries in these rows. Thus we can clear the nonzero entries from these columns. Then we slide rows $ 2$ through $ k \plus{} 1$ down $ k$ rows, so that they now occupy rows $ k \plus{} 2$ through $ 2k \plus{} 1$. These operations change the determinant only up to sign. The resulting matrix is block upper-triangular. The upper-left $ (2k \plus{} 1) \times (2k \plus{} 1)$ block is itself upper-triangular, with ones on its diagonal. The lower-right $ (n \minus{} 2k \minus{} 1) \times (n \minus{} 2k \minus{} 1)$ block is $ A(n \minus{} 2k \minus{} 1)$. Hence $ \det A(n) \equal{} \pm \det A(n \minus{} 2k \minus{} 1)$, and the result follows by induction.

Probably there is a slicker way to compute this determinant.

A completely different way to approach this problem is to use enumeration (seriously, who would think?). One strategy I tried was to use an involution on $ k$-limited permutations, where we biject permutations $ \sigma, \pi$ of $ \{1,\ldots,n\}$ by
\[ \pi(n \plus{} 1 \minus{} i) \equal{} n \plus{} 1 \minus{} \sigma(i).
\]
(This "flips" the permutation.) We only have to worry about fixed points of this involution, which are "symmetric" permutations. This suggests that we only look at the "first half" of permutations (I'm being very rigorous here). If $ f(n)$ denotes the number of $ k$-limited permutations on $ \{1,\ldots,n\}$, we should be able to show that
\[ f(n) \equiv f\left(\left\lfloor\frac {n}{2}\right\rfloor\right) \plus{} f\left(\left\lfloor\frac {n}{2}\right\rfloor \minus{} 1 \right) \plus{} \cdots \plus{} f\left(\left\lfloor\frac {n}{2}\right\rfloor \minus{} k \right) \mod 2,
\]
whence the result would follow by induction (this induction is very nice -- it takes a minute of thought to see). I got attached to this approach and spend a lot of time on it. (Someday I'll learn that I should solve B1 before toiling away at B6.)

Perhaps we can also use the fact that taking the inverse of a permutation preserves $ k$-limitedness, meaning that we only need consider permutations with cycles of length at most $ 2$. Inclusion-Exclusion might be helpful. (I'm sure if I ask my professor he'll tell me some nonsense about Rook polynomials.)

I tried counting permutations, and restricting to involutions. I was able to do the special cases up to $ k\equal{}3$ that way. Generalizing didn't work well.

OK, here's the inclusion-exclusion version. The key is to start with $ k$-limited functions, and try to count the permutations.

Consider all $ k$-limited functions from $ \{1,2,\cdots,n\}$ to $ V\equal{}\{\minus{}k\plus{}1,\minus{}k\plus{}2,\cdots,n\plus{}k\}$. There are $ (2k\plus{}1)^n$ of these. One of these functions is a permutation if and only if its range excludes all of $ S_0\equal{}\{\minus{}k\plus{}1,\minus{}k\plus{}2,\dots,0,n\plus{}1,n\plus{}2,\cdots,n\plus{}k\}$ but none of the numbers inbetween. For each set $ S$ of integers, we can count those functions that miss it: let $ N(S)\equal{}\prod_{j\equal{}1}^{n} (2k\plus{}1\minus{}|S\cap\{j\minus{}k,j\minus{}k\plus{}1,\dots,j\plus{}k\}|)$ be this number.

By Inclusion-Exclusion, the functions which have all of $ \{1,2,\cdots,n\}$ as their range is $ \sum_{S_0\subseteq S\subseteq V} (\minus{}1)^{|S|\minus{}|S_0|}N(S)$. We only care about its parity, so we can ignore the powers of $ \minus{}1$. More importantly, we can ignore all $ S$ for which $ N(S)$ is even. Since $ N(S)$ is defined as a product of integers, it is even when any of these integers is even.
If we ever have exactly one of $ j$ and $ j\plus{}2k\plus{}1$ in $ S$, one of $ 2k\plus{}1\minus{}|S\cap\{j,j\plus{}1,\dots,j\plus{}2k\}|$ and $ 2k\plus{}1\minus{}|S\cap\{j\plus{}1,j\plus{}2,\dots,j\plus{}2k\plus{}1\}|$ is even and the other is odd, making $ N(S)$ even. If $ N(S)$ is odd, the elements of $ S$ are thus partitioned into an even number of arithmetic sequences with common difference $ 2k\plus{}1$, which continue as far as possible. How many such sets are there? If the $ 2k$ values in $ S_0$ cover $ m$ residues mod $ 2k\plus{}1$, there are $ 2^{2k\plus{}1\minus{}m}$ collections of arithmetic sequences, $ 2^{2k\minus{}m}$ of which have the proper even size.
The total number we're looking at is even if $ m<2k$ and odd if $ m\equal{}2k$. We have $ m\equal{}2k$ if and only if the two halves of $ S_0$ don't overlap mod $ 2k\plus{}1$. This happens exactly when $ n\plus{}k\equiv \minus{}k\mod 2k\plus{}1$ or $ n\plus{}1\equiv 1\mod 2k\plus{}1$, which can also be written $ n\equiv 0\text{ or }1\mod 2k\plus{}1$.

A side note: in the most interesting cases, exactly one term in that giant inclusion-exclusion expression is odd, and that one term has the value $ \pm 1$.

Here's a (hopefully) complete involutions/restrictions proof. Unfortunately, I wasn't able to piece all of this together on the test, but the restriction I had was close to this one and I worked out the analysis of the last paragraph...

First we restrict to involutions, that is, map $ \sigma\rightarrow\sigma^{\minus{}1}$ and note that this map has order 2 and the fixed points are just the involutions. Then we apply a different map, by the following rule: If there exists some maximal $ m\ge n\minus{}k$ with $ \sigma(m)\ge n\minus{}k$, we "switch" $ m$ and $ n$, that is, if $ \sigma(n)\equal{}n$ and $ \sigma(m)\equal{}m$, let $ \sigma'(m)\equal{}n$ and $ \sigma'(n)\equal{}m$; if $ \sigma(n)\equal{}n$ but $ \sigma(m)\neq m$, let $ \sigma'(n)\equal{}\sigma(m)$, $ \sigma'(\sigma(m))\equal{}n$ and $ \sigma'(m)\equal{}m$; if $ \sigma(m)\equal{}m$ but $ \sigma(n)\neq n$, let $ \sigma'(m)\equal{}\sigma(n)$, $ \sigma'(\sigma(n))\equal{}m$ and $ \sigma'(n)\equal{}n$; finally, if $ \sigma(n)\neq n$ and $ \sigma(m)\neq m$, let $ \sigma'(n)\equal{}\sigma(m)$, $ \sigma'(\sigma(m))\equal{}n$, $ \sigma'(m)\equal{}\sigma(n)$ and $ \sigma'(\sigma(n))\equal{}m$. In all of these cases, let $ \sigma'(j)\equal{}\sigma(j)$ for all other $ j$. If no such $ m$ exists, fix $ \sigma$.

This process clearly makes $ \sigma'(m)\ge n\minus{}k$ again, and $ m$ remains maximal; if $ m<a<n$, $ \sigma'(a)\equal{}\sigma(a)<n\minus{}k$. Therefore, this switch has order 2, and pairs up all involutions where $ \sigma$ is not fixed. We now analyze the case where $ \sigma$ is fixed.

If $ n\equal{}0$ or $ 1$, there is only one permutation and it is $ k$-limiting for every $ k$, an odd number as desired.  Otherwise, as $ \sigma(n\minus{}1)<n\minus{}k$, we must have $ \sigma(n\minus{}1)\equal{}n\minus{}k\minus{}1$. Then $ \sigma(n\minus{}2)<n\minus{}k$, so we must have $ \sigma(n\minus{}2)\equal{}n\minus{}k\minus{}2$ since $ n\minus{}k\minus{}1$ is already taken. Continuing in this fashion, $ \sigma(n\minus{}j)\equal{}n\minus{}k\minus{}j$ for each $ 1\le j\le k$, and we also get that $ n\ge2k\plus{}1$ in the process (as $ \sigma(n\minus{}k)\equal{}n\minus{}2k\ge1$). $ \sigma$ is an involution, so we also have $ \sigma(n\minus{}k\minus{}j)\equal{}\sigma(n\minus{}j)$ for the same $ j$, and finally, by process of elimination, $ \sigma(n)\equal{}n$. Therefore, $ \sigma$ fixes $ \{n\minus{}2k,n\minus{}2k\plus{}1,\ldots,n\}$, so it fixes $ \{1,2,\ldots,n\minus{}2k\minus{}1\}$ with no restriction. Therefore the number of involutions fixed by this mapping is $ 0$ if $ n<2k\plus{}1$ and the total number of $ k$-limiting involutions for $ n\minus{}2k\minus{}1$. Therefore, by induction on $ n$ with base cases $ 0,1,2,\ldots,2k$, the number of $ k$-limiting permutations is 1 if $ n$ is congruent to 0 or 1 mod $ 2k\plus{}1$. We are done.

A clarification: $ m$ is maximal among values $ <n$ and $ \ge n\minus{}k$ with that property. It's also simpler if you just forget about involutions, and exchange the values of $ \sigma(m)$ and $ \sigma(n)$ in your map.

Given the matrix intepretation above, it suffices to show that $ A$ is invertible (with mod-2) coefficients iff $ n \equiv 0,1 \pmod{2k\plus{}1}$.

If it is not 0 or 1, then we can easily write two different ways of constructing the all-ones vector (1,1,1,...,1) as a sum of rows. A sketch: we use some "full" (2k+1) width blocks of ones, and
patch together on the sides to fill up the entire row. For n different from 0 or 1 mod (2k+1), it's pretty easy to show that there's more than one way of doing this.

Now, to show that if it is 0 or 1, then A is invertible: if we take a relation $ a_1e_1 \plus{} \dots \plus{} a_ne_n \equal{} 0$, where $ e_i$ is the $ i$th elementary basis vector, then inspection at coordinate $ m$
shows us that $ \sum_{i \equal{} m\minus{}k}^{m\plus{}k} a_i \equal{} 0$. (Again, everything mod 2). Therefore, $ a_{m\minus{}k}\equal{}a_{m\plus{}k\plus{}1}$ for every $ 1 \le m < n$. ($ a_j \equal{} 0$ for $ j < 1$ or $ j > n$). So, these
coefficients are periodic. Furthermore, $ m \equal{} 1, \dots, k$ tells us that $ a_{k\plus{}2},a_{k\plus{}3}, \dots, a_{2k\plus{}1} \equal{} 0$, while $ m \equal{} n\minus{}1, \dots, n\minus{}k$ give $ a_{n\minus{}k\minus{}1}, \dots, a_{n\minus{}2k} \equal{} 0$.

Now we have our two cases; using periodicity, if $ n \equal{} 0 \pmod{2k\plus{}1}$, this last condition gives $ a_{k}, \dots, a_{1} \equal{} 0$. So that just means we need to check $ a_{k\plus{}1}$. But then $ a_{k\plus{}1} \equal{} \sum_{i\equal{}1}^{2k\plus{}1} a_i \equal{} 0$. So all is good.

If $ n \equal{} 1 \pmod{2k\plus{}1}$, the last condition gives $ a_{k\plus{}1} \equal{} \dots \equal{} a_2 \equal{} 0$. Along with the first relation we just need to check that $ a_1 \equal{} 0$. This follows since $ a_1 \equal{} \sum_{i\equal{}1}^{k\plus{}1} a_i \equal{} 0$.

Therefore, by periodicity, the relation is trivial, so $ A$ is invertible.

This last part is the hard part, which is why I just quickly sketched the noninvertibility. Will gladly post fuller proof if asked.

Parity and pairings go in hand.

Let $S$ be the set of numbers in $[1,k+1]$ such that for all $s\in S, \sigma(s)\in [1,k+1]$.

I claim the number of permutations with $|S|\ge 2$ is even. Fix $S$. Then there are $|S|!$ permutations of $S$, and an integral ways to permute $[n]\backslash S$, so the number of k-limited permutations with this $S$ is even.

If $|S|=1, S=\{1\}$, so we can see $\sigma(x)=k+x$ for $2\le x\le k+1$. ($S=\{1\}$ cannot happen for $n< 2k+1$). Note if $\sigma$ works, then $\sigma^{-1}$ works, so we only need to count $\sigma$ is an involution i.e. $\sigma(k+x)=x$ for $2\le x\le k+1$. Therefore, we can reduce this to the answer for $n-(2k+1)$.

Finally, we can verify the result for $n=0,1$, as needed.


A 51-digit number $ N$ consists of fifty $ x's$ and one $ y$, where $ x$ and $ y$ are both digits from among 0 to 9. If $ x\equal{}2$, $ N$ is divisible by 17 and $ y$ is the 17th digit from the right, $ y$ equals what?

[hide="Hint"] Consider the number $ M$ consisting of fifty-one $ x$'s and write it in a better form.  :) [/hide]

ok i'm stuck at

$ Y \equal{} (5*1111111111111112)$(mod $ 17$)
but i can't get any closer :(

I used $ a^{16}$(mod $ 17)\equal{}1$

[hide]ok i got Y=6[/hide]

if i'm right i'll post a solution.

You are right. :)

And great question by the way!

Here's my solution but i don't get 6: could somebody point out my mistake?

Suppose the number has 51 $ x$s like t0rajir0u recommended. If we write the number out in decimal base form, we have:\[ N \equal{} 2\cdot10^{0}\plus{}2\cdot10^{1}\plus{}2\cdot 10^{2}\plus{}2\cdot 10^{3}\plus{}\cdots\] Consider each digit $ \text{mod}17$. We have $ 2\cdot 10^{0}\equal{} 2\text{mod}17$, $ 2\cdot 10^{1}\equal{} 2\cdot 10 \equal{} 20 \equal{} 3\text{mod}17$, and $ 2\cdot 10^{n\plus{}1}\equal{} 10\times 2\cdot 10^{n}$ in general.

Going through each digit from left to right, the digits follow the pattern $ 2,3,13,11,8,12,1,10,15,14,4,6,9,5,16,7\text{mod}17$ and repeat every 17th digit. The sum of these mods is $ \frac{16\cdot17}{2}\equal{} 136 \equal{} 0\text{mod}17$. So a number of 51 digits consists of three cycles of the mods above and is divisible by 17. The 17th digit from the right is $ 2\cdot 10^{1}6\equiv 2\text{mod }17$, so we obtain $ 1\cdot 10^{16}\equiv\frac{2}{2}\equal{} 1\text{mod }17$. Suppose the digit 2 in the 17th place from the right were replaced by a digit other than 2. For the number to be still divisible by 17, that digit $ n$ multiplied by $ 10^{16}$ must give $ 7\text{mod}17$. But it is impossible to do this as we have $ 7\plus{}n\equiv 7\text{mod}17$ which has no solutions if $ n$ is a digit. So $ y \equal{} 2$ also?

[quote="aidan"]Here's my solution but i don't get 6: could somebody point out my mistake?

[u]Here's the mistake:[/u]
... Going through each digit from left to right, the digits follow the pattern $ 2,3,13,11,8,12,1,10,15,14,4,6,9,5,16,7\text{mod}17$ and repeat every 17th digit. The sum of these mods is $ \frac{16\cdot17}{2}\equal{} 136 \equal{} 0\text{mod}17$. So a number of 51 digits consists of three cycles of the mods above and is divisible by 17.[/quote]

The digits repeat every [b]17th[/b] digit -- but they repeat in blocks of [b]16 digits[/b]. So a number of 48 digits consists of three cycles of the mods and is divisible by 17.

I made a mistake also though. I put y in the 17th digit from the left, not the 17th digit from the right as the problem asked for. So I believe the answer is [hide]y = 1.[/hide]

hmmm i still get 6?

my solution is really hard to show on a computer.

[hide="My solution"]
Call our number N.
\begin{eqnarray*}N & = & 2222...222+(y-2)\cdot 10^{16}\\ & = & 2\cdot\left(\frac{10^{51}-1}{9}\right)+(y-2)\cdot 10^{16}\end{eqnarray*}

Recall by Fermat's Little Theorem that $ a^{p-1}\equiv 1\bmod{p}$ for primes p.

So $ 10^{16}\equiv 1\bmod{17}$
Therefore, $ N\equiv 2\cdot\left(\frac{10^{3}-1}{9}\right)+(y-2)\bmod{17}$
$ N\equiv 2(111)+(y-2)\bmod{17}$
$ N\equiv 1+(y-2)\bmod{17}$
$ N\equiv y-1\bmod{17}$

We want y such that $ N\equiv 0\bmod{17}$, so $ y = 1$.[/hide]

oh yep you're right  :) .

i split the 2's where Y was and i made an exponent error :( .

very nice solution.

one doubt..how did u put y-2 in the first equation?why is it not y?[/quote]

$ y$ is a digit of a number that is otherwise $ x$'s.  Since we have replaced it with an $ x$, the difference to be accounted for is $ y\minus{}x$ multiplied by the appropriate power of ten.

[quote="aidan"]Ok, nice one =P So with my method we get that a number consisting of 51 $ 2$s is equivalent to $ 2\plus{}3\plus{}13 \equal{} 18\text{ mod }17$. So since $ 1\cdot 10^{16}$ is $ 1\text{ mod }17$ we just have to reduce the 17th digit from the right to $ \boxed{1}$ and we have a $ 17\text{ mod }17$ number. Woot!

But i like gauss202's solution especially the use of Fermat's.  :D[/quote]

how did you get 2+3+13?

$ y$ = 1 is the right answer. Nice solution gauss.

[quote="unimpossible"]how did you get 2+3+13?[/quote]

The mods in the cycle follow a sequence of $ 2,3,13\ldots\text{ mod }17$ going across the digits from right to left, starting from the units digit. They repeat in blocks of 16 digits. So the 49th, 50th and 51st digit from the right would have the same value mod 17 as the 1st, 2nd and 3rd digit (as they are all 2s).


Let $a,b,c\in\mathbb {R^*}$ satisfing the condition.Prove that:
\[\frac{1}{a^2+b^2+ab}+\frac{1}{a^2+c^2+ac}+\frac{1}{b^2+c^2+ac}\le \frac{9}{(a+b+c)^2} \]

I am not sure what $\displaystyle\mathbb {R^*}$ means...  but if it includes the set of positive real numbers then the inequality is false:
Just set $(a,b,c)=(0.1,0.2,10)$.

Okay, I didn't realized that:  This ineq is already posted here http://www.mathlinks.ro/Forum/viewtopic.php?t=6364 .

[quote="harazi"]This is just incredible! Posted 6 times in 3 days.[/quote]This means that it is a very popular inequality :D :D

The following more general ineq holds for $p \ge 7/8$:

$\displaystyle \frac{1}{a^2+b^2+pab}+\frac{1}{a^2+c^2+pac}+\frac{1}{b^2+c^2+pac}\ge \frac{27}{(2+p)(a+b+c)^2}$

$ \frac {23}{8b^2 \plus{} 7bc \plus{} 8c^2} \plus{} \frac {23}{8c^2 \plus{} 7ca \plus{} 8a^2} \plus{} \frac {23}{8a^2 \plus{} 7ab \plus{} 8b^2} \minus{} \frac {27}{(a \plus{} b \plus{} c)^2}$

$ \equal{} \sum{\frac {(b \minus{} c)^2\left[10bc\left(1012b^2 \plus{} 819bc \plus{} 1012c^2\right) \plus{} (b \plus{} c \minus{} a)^2\left(665a^2 \plus{} 1472b^2 \plus{} 1288bc \plus{} 1472c^2\right)\right]}{2(a \plus{} b \plus{} c)^2\left(8b^2 \plus{} 7bc \plus{} 8c^2\right)\left(8c^2 \plus{} 7ca \plus{} 8a^2\right)\left(8a^2 \plus{} 7ab \plus{} 8b^2\right)}}$

$ \geq0.$

See also here : http://www.mathlinks.ro/viewtopic.php?t=29347


parameterization
quadratics
vector
logarithms
algebra
linear equation
linear algebra

We can solve the  regression problem $ y_i \approx ax_i\plus{}b$ with given data $ x_i$ by easily modeling as
$ c \equal{} \left[\begin{array}{ccccc} a\\
b \end{array}\right]$ ,   $ \quad A \equal{} \left[\begin{array}{ccccc} 1 & x_1 \\
1 & x_2 \\
\vdots & \vdots  \\
1 & x_n \end{array}\right] \quad$,    $ \hat{y} \equal{} Ac$
and then using least squares property.

But, How can I formulate $ y_i \approx c e^{ax_i}$ as above (linear regres. problem) using regr. parameters $ a$ and $ c$.
I think of a quadratic Taylor expansion of exponential but then elements of $ c$ vector are $ c, ac, a^2c$(they are not independent as a and b in the previous example and cannot be solved as a linear equation problem, I think.). Can you come up with an idea ??

$ \log y_i \approx ax_i \plus{} \log c$ is a linear regression problem.


[hide]
Volume of a rectangular prism = lwh
The volume of one block is 9*9*4=324
The volume of the structure she wants to build is 4*36*144=20736 (remember to convert feet to inches)

So, she needs 20736 / 324 = [64 blocks][/hide]

[quote="Interval"]Tina’s preschool has a set of cardboard building blocks, each of which
measures 9 inches by 9 inches by 4 inches. How many of these blocks
will Tina need to build a wall 4 inches thick, 3 feet high, and 12 feet
long?[/quote]
[hide]First convert the 3 and the 12 to inches so you don't forget later. So the volume of the bigger one is $36\cdot144\cdot4$. The volume of the smaller one is $9\cdot9\cdot4$. So you want how many of these that you can fit so its just $\frac{36\cdot144\cdot3}{9\cdot9\cdot4}$. Canceling out stuff you get that the answer is 64.[/hide]


inequalities
trigonometry
inequalities proposed

[quote="zhaobin"]Prove that in a acute-triangle $ABC$,then:
\[ \frac{\cos B \cos C}{\cos A}+\frac{\cos C \cos A}{\cos B}+\frac{\cos A \cos B}{\cos C} \ge \frac{3}{2}  \][/quote]
Firstly, by the Cosine Rule,
$\frac{\cos B \cos C}{\cos A}=\frac{\frac{c^2+a^2-b^2}{2ca}\cdot\frac{a^2+b^2-c^2}{2ab}}{\frac{b^2+c^2-a^2}{2bc}}=\frac{(c^2+a^2-b^2)(a^2+b^2-c^2)}{2a^2(b^2+c^2-a^2)}$
Now we let $x=b^2+c^2-a^2$, $y=c^2+a^2-b^2$ and $z=a^2+b^2-c^2$. Since $\triangle ABC$ is acute, $x,y,z$ are positive. We need to prove
$\sum_{cyc}\frac{yz}{x(y+z)}\geq\frac32$
If we further let $p=yz, q=zx, r=xy$ where $p,q,r$ are positive real numbers, we have to prove
$\sum_{cyc}\frac{p}{q+r}\geq\frac32$
which is just Nesbitt Inequality. :)

Thanks.
That is also my proof.And the inequality is easy :) ,but I think it is nice :lol:
I think there will be another solution(At least I have another one.)

[quote="leepakhin"][quote="zhaobin"][quote="e.lopes"]hint to a simple proof:

let $A_1$ the foot of the perpendicular line trought $A$ to $BC$.

see that $\frac{HA}{HA_1} = \frac{cosA}{cosB.cosC}$[/quote]
and then?[/quote]
And then $\frac{\cos B \cos C}{\cos A}=\frac{HA_1}{HA}=\frac{S_{\triangle BCH}}{S_{\triangle CAH}+S_{\triangle ABH}}$ and we can finish by Nesbitt Inequality. :D[/quote]
Oh,Yes...Thanks


inequalities
search
inequalities unsolved

$ (1)$ Let $ a,b,c,d\geq0$ s.t. $ a^2\plus{}b^2\plus{}c^2\plus{}d^2\equal{}1$.Prove that:
$ (1\minus{}a)(1\minus{}b)(1\minus{}c)(1\minus{}d)\geq abcd$
$ (2)$ Let $ x_1,x_2,...,x_n\geq0$, $ n>2$, s.t. $ x_1^2\plus{}x_2^2\plus{}...\plus{}x_n^2\equal{}1$.Prove that:
$ (1\minus{}x_1)(1\minus{}x_2)...(1\minus{}x_n)\geq(\sqrt{n}\minus{}1)^nx_1x_2...x_n$.

I would be greatful if someone helped me. :(

[quote="gauravpatil"][quote="M.A"][hide] use SMV theorem to kill these inequalities  :wink: [/hide][/quote]
can you show how does the tranformation that to the rhs[/quote]
See here: http://reflections.awesomemath.org/2006_6/2006_6_mixing.pdf

thanks a lot
but i still dont get it which transformation to apply

Sorry,but can someone solve at least the first one without SMV :?: By the way, how to apply SMV in these inequalities ?Help,please!


vector
combinatorics proposed
combinatorics

A very nice problem:

We have a finite set $M$ and a collection $\mathcal C$ of ordered triples of elements in $M$ with the following properties:

(a) if $(A,B,C)\in\mathcal C$, then $(A,C,B),(B,A,C)\in\mathcal C$;
(b) for every $A,B\in M$ (not necessarily distinct), there is a unique $C$ s.t. $(A,B,C)\in\mathcal C$;
(c) if $(A,B,C),(C,D,E),(B,D,F)\in\mathcal C$, then $(A,E,F)\in\mathcal C$.

Find the possible values of the number of elements of $M$.

i am not sure if i am right,(i.e.i haven't fully explored other possibilities) but i guess the answer is $2^n,n\geq 0$.
one thing to note is that since for each $(a,b)\in M^2$ there is a unique $c\in M$ s.t. $(a,b,c)\in \mathcal{C}$ one can associate a binary operator $*$ and denote that $c$ by $a*b$.
note then that this binary operator is commutative(by the given condition). one can also(easy) show that $a*a=x\Rightarrow x*x=x$.now if for another $y\neq x,y*y=y$ then note that $x*x=x,(x*y)*(x*y)=z\Rightarrow x*(x*y)=z\Rightarrow y=z$. But then $x*(x*y)=y,(x*y)*(x*y)=y\Rightarrow x*y=x$ but then again, $x*(x*y)=y,x*(x*y)=x$ so $x=y$, contradiction. In other words the 'zero element' is unique.
the other condition gives that every element is of order $2$ hence we have effectively a finite vector space over $\mathbb{Z}_2$.(of course i am jumping here since  associativity needs to be proved but i guess it is possible)

I did pretty much the same thing, and I didn't check everything either. I hope it does work :).


After speaking with many students who are able to have independent study time during school and/or who have run out of math to take at school, we are considering designing an independent study problem solving program.  Students enrolled in such a course would receive the following:

1) Enrollments in some of our online courses.
2) Weekly readings and assignments from a few textbooks (e.g., AoPS, Zetiz, Engel).
3) The usual course message board access.
4) Periodic office hours with AoPS instructors.

There would be the usual evaluated and audited options.

We are interested in student/teacher/parent feedback about this idea.

I love the idea. I have an TA period and 30 minutes every morning so I never like do school homework at my house. (the only thing i do when  I come is math.

I would do it, if it was at my level.  My school lets me arrange my curriculum, so it would be a great fit for me.

So...would this be like a math course?...kinda like the way we might take Alg II or Pre-cal or something?...except with math competition material...

Basically it would be a math course with problem solving material.  We would likely have 2 levels - 1 'intermediate' (think toughish AMC/AIME) and 1 advanced (Olympiad level).  Both will focus on developing the ability to solve multi-step problems, with some emphasis on writing proofs (particularly in the advanced class, but also in the intermediate).

You don't have to take it as part of your school curriculum, but if your school allows you to opt for external electives, this would fill the slot nicely.

Does that have to be during the school?
Like I have a lot~ free time after school which is after like 4:00 EST.
And one more question, when you are starting it? or is it gonna be free? I just love math practices...

The online classes will be the regular times (in the evening).  The independent study can be done at any time you want - thus, you can do this on your own time, or on school time.

The courses would start with the onset of next school year.  They won't be free.

[quote="rrusczyk"]The online classes will be the regular times (in the evening).[/quote]

This sounds like something we would be very interested in here. You are offering one online class soon that we would sign up for, but for the fact that the class meetings are on the same evening when A+MATH goes to the [url=http://www.itcep.umn.edu/umtymp/]University of Minnesota Talented Youth Mathematics Program[/url]. I THINK his class meetings will be on Thursday evenings for two more school years, but I don't set that schedule, so I can't guarantee it. Every few years a new UMTYMP entering class starts on a different day of the week--we have a local friend a few years ahead in the program who was always busy on Wednesdays. So as long as the evening you choose for the online class fits our schedule, I think we would be interested in the independent study class.

We would also be very interested in such a class - my son is one of those who has "run out of math classes" at his school. Consistent work in problem solving would be much better for his mathematical maturity than plunging on with college courses.  I also think it would be easier for him to "find the time" to do this if it were a year long math class, rather than a few ad-hoc classes and math jams scheduled on top of his "real" math class.

Great idea!

any followup on the independent study course? Summer vacation is coming, it is a good timing to start.

We're still in the process of designing it, but hope to list it some time in the next couple weeks.

i dont really understand how its an independent study thing.  how is it independent if there are still classes?

Could you like standardize the independent study thing into something that we can actually get grades and get graduation credit?

The classes are only part of the independent study - we will also be giving readings and assignments outside of these classes.  Hence the independent study.

As for school credit, if you connect us with the proper people at your school, we can affirm the completion of the course (i.e. for credit) for evaluated students.  This will require your school to agree, of course.


Let a,b,c are possitive numbers in [0;1]
Prove: \[ \frac{a}{{b^3 \plus{} c^3 \plus{} 7}} \plus{} \frac{b}{{c^3 \plus{} a^3 \plus{} 7}} \plus{} \frac{c}{{a^3 \plus{} b^3 \plus{} 7}} \le \frac{1}{3}\]

[quote="toancapba"]Let a,b,c are possitive numbers in [0;1]
Prove:
\[ \frac {a}{{b^3 \plus{} c^3 \plus{} 7}} \plus{} \frac {b}{{c^3 \plus{} a^3 \plus{} 7}} \plus{} \frac {c}{{a^3 \plus{} b^3 \plus{} 7}} \le \frac {1}{3}
\]
[/quote]
$ \sum_{cyc}\frac{a}{b^3\plus{}c^3\plus{}7}\leq\sum_{cyc}\frac{a}{b^3\plus{}2\plus{}c^3\plus{}2\plus{}3a}\leq\sum_{cyc}\frac{a}{3b\plus{}3c\plus{}3a}\equal{}\frac{1}{3}.$


function
trigonometry
calculus
derivative
algebra unsolved
algebra

I do not know if this problems solution involves calculus. If it belongs to oter topic than algebra, please some moderator move it.  Thanks.

Give a positiv integer $n$, define $f: \mathbb{R}\to \mathbb{R}$ by : \[f(x)=\sin x \cdot \sin 2x \cdot \sin 4x\cdot \dots\cdot \sin 2^{n}x.\] Prove that $\mid f(x)\mid \le(\frac 2{\sqrt 3})\mid f(\frac \pi 3)\mid $ for all real $x$.

Can we telescope $f(x)$? Somehow I can telescope if all the sines are changed to cosines.

Note: it works for $n=1, 2, 3, 4$ by graphing. (TI-83 Calculator: its cheating, but hey...) [*]

Now note: for $n=5$, we have $\mid f(x)\mid \le\mid f(\frac \pi 3)\mid$ [**],

so for general cases, let $n=5a+b$ where $a, b$ are integers, and $0\le\ b \le\ 4$, and apply both [*] and [**] results, and we have it!
 :lol:

Too bad we can't bring graphing calculators to contests  :blush:

P.S. The results that I used the graphing for can, I think be arrived in a number of other ways. One could find the max.  of $f(x)$ for those $5 n's$ by differentiation, or one could divide the interval of zero to $2pi$ and divide it into 384 pieces and examine each case separately, for $x$


Prove that the set of positive integers cannot be partitioned into three nonempty subsets such that, for any two integers $x$, $y$ taken from two different subsets, the number $x^{2}-xy+y^{2}$ belongs to the third subset.

Proof By Contradiction

Assume the existence of 3 such sets. Call them $ A, B, C$.

Assume that we have a number $ y \in A$. Consider two integers $ x,z < y$ in different sets, $ B$ and $ C$ respectively.

$ \begin{cases}
x \in B \\
y \in A \\
\end{cases} \Rightarrow x^2\minus{}xy\plus{}y^2 \in C$

However, also

$ \begin{cases}
z \in C \\
y \in A \\
\end{cases} \Rightarrow z^2\minus{}zy\plus{}y^2 \in B$

We consider the case for contradiction.

$ z^2\minus{}zy\plus{}y^2\equal{}x^2\minus{}xy\plus{}y^2 \Rightarrow (z\minus{}x)(y\minus{}(x\plus{}z)) \equal{} 0 \Rightarrow y\equal{}z\plus{}x$

Therefore each pair $ x,z$ whose sum is $ y$ will be in the same set.

Now consider $ y\plus{}1$ Clearly $ 1$ has been fixed to a set from the previous line. But this set is distinct from $ y$. However, from early, they must be in the same set. Contradiction

SimonM, your proof is far from complete. What you have shown is step 1 from [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1664852#p1664852]olorin's solution[/url]. (This is also Lemma 1 from the official solution.) You can't prove that $1$ and $y$ lie in different parts of the partition than $y+1$.


Aren't we supposed to do:

[code]$\frac{a}{b}$[/code]

which would lead to $\frac{a}{b}$? :maybe:

[quote="fedja"]I haven't been on the forum for a while and when I came back and tried to post, I discovered that, say, \frac 32 gives $\frac{3}{2}$ while \frac 3 2 gives $\frac{3}{ }2$. Normally, the spaces would be ignored by LaTeX in math mode. Have we switched to some new rules or is it just a small bug?[/quote]

It is not a bug. Mr. Vornicu is trying to make some LaTeX standards, so that different ways of $\LaTeX$ing the same thing will make the same picture, thus saving time and server space. \frac a b is improper markup anyway. You should always use \frac{a}{b}, which is much easier to read.

OK, you're actually right that \frac a b is ok, but it's good practice to use \frac{a}{b} since you might get used to it and accidentally write \frac 123 456 which would give you $\frac123456$ instead of $\frac{123}{456}$ :)

Oh, and this exception aside, if you just type your LaTeX normally, the server will automatically standardize your markup.

[quote="fedja"]Thanks, I got it. Is there any post describing the "proper" markup under the current AoPS standards in full? I agree that it makes sense to standardize such things a bit though, contrary to what chess64 said, \frac a b is a completely acceptable expression in the standard LaTeX when a and b are just two single symbols, and it worked perfectly well a few months ago; that's why I got a bit surprised to see that it no longer works. Anyway, thanks again for the clarification.  :)[/quote]Well,[code]$\frac ab$[/code] works. I have no idea why [code]$\frac a b$[/code] doesn't though ... it should be transformed automatically in [code]$\frac{a}{b}[/code]

PS Indeed [i]most[/i] of the spaces in $\LaTeX$ are ignored, however some of them are used to separated commands from variables. This is what happens here, my parser doesn't understand what the space between $a$ and $b$ represents ...


let f be a polynomial with real coefficients.  Show that all the zeros of f are real if and only if f2 cannot be written as the sum of squares f2 = g2 + h2 where g and h are polynomials with real coefficients and deg g != deg h.

one direction (the easy one):

[hide]

if f(x)2 = g(x)2 + h(x)2 and deg g != deg h then f does not have all real roots.

proof:

suppose f(r) = 0 with r real.

Then 0 = g(x)2 + h(x)2 => g(r) = h(r) = 0.

Therefore, f(x) | g(x) and f(x) | h(x).

WLOG suppose g has higher degree than h.

Then deg(g(x)2 + h(x)2) = 2deg g = 2 deg f => deg f = deg g > deg h. But f(x) | h(x) and h(x) is nonzero.

=><=.

[/hide]

other direction (the harder one I guess...): If f doesn't have all real roots, then we can find g and h such that f^2(x) = g^2(x)+h^2(h) and deg g !=deg h.

[hide]Since f doens't have all real roots, it can be factored as

f(x) = k (x-a_1)...(x-a_m) ((x-b_1)^2+c_1^2)...((x-b_n)^2+c_n^2)

where all the a_i, b_i, and c_i are real, m>=0, n>=1, and c_i !=0. (The quadratics on the second half of the factorization correspond to the quadratics with imaginary roots after the square has been completed.)

So, f^2(x) = k^2(x-a_1)^2...(x-a_m)^2 ((x-b_1)^2+c_1^2)^2...((x-b_n)^2+c_n^2)^2.

If I could prove that this last half is expressible as p^2(x) + q^2(x) with deg p != deg q, then we'd be done, since we would then have

f^2(x) = [k(x-a_1)...(x-a_m)p(x)]^2 + [k(x-a_1)...(x-a_m)q(x)]^2

where the two polynomials on the right would have different degree.

Proof of required lemma:

Using the identity (a^2+b^2)(c^2+d^2) = (ac+bd)^2+(ad+bc)^2, we see that the product of two sums of squares is another sum of squares. We may assume that deg p > deg q, and so we must show that in the identity (p^2(x)+q^2(x))((x-b_i)^2+c_i^2) = (p(x)(x-b_i)+q(x)c_i)^2 + (p(x)c_i-q(x)(x-b_i))^2, the two polynomials on the right have different degree. But this is apparent: the degree on the left is 1+deg p, and the degree on the right is less than or equal to max{deg p, 1+deg q}, which is <= deg p, which is < 1+deg p. Thus, the inductive step is complete and the lemma is proven by induction.

To clerify... the base case is (x-b_1)^2+c_1^2, which is a sum of squares of 2 polynomials differing in degree. Then, by the inductive step above, we can systematically multiply by the other 2n-1 factors which are all of the form (x-b_i)^2+c_i^2 to obtain yet another sum of squares of polynomials differing in degree.[/hide]


Calculate pH :

$ 50ml$ of $ 0.12M H_3PO_4$ $ \plus{}$ $ 20ml$ of $ 0.15 M$ $ NaOH$

Given $ K1$, $ K2$, $ K3$ of $ H_3PO_4$

[hide="IS this correct?"]
$ K1K2K3 \equal{} \frac {[H^\plus{}]^3 [PO_4^{3\minus{}}]}{[H_3PO_4]}$

Putting $ [PO_4^{3\minus{}}] \equal{} \frac{1 millimol}{70ml}$ and $ [H_3PO_4] \equal{} \frac {5 millimol}{70ml}$ , I can get $ [H^\plus{}]$ but I am not getting correct answer like this.[/hide]

Your assumption that $ PO_4^{2\minus{}}$ concentration will remain same is wrong, as it will hydrolyse in solution.

So can you guide me further, maybe through equations?

Anyone? I think this one is easier than the other.Why no replies?


What is the winning strategy in Nim if instead of making a turn a player may pass (not take any counters and pass the turn to the other player)? Passing is allowed only once during the game: if player A made this then he is not allowed to pass again, and also player B is not allowed to pass.

Any game with this particular passing rule is a win for the first player.  If the game without the passing rule is a first player win, then he simply follows the winning strategy and ignores the passing option.  Otherwise, the second player has a winning strategy for the no passing game, so the first player simply passes and takes the second player strategy.

[quote]If the game without the passing rule is a first player win, then he simply follows the winning strategy and ignores the passing option.[/quote]

But what if the second player will pass? then the first player will be forced to make a move in a safe position, and will lose.

Oh, I see... player B only can't pass if player A passes.

Of course, a second player win still turns into a win for the first player.  Otherwise, the first player wins in one move if he can, otherwise he must move to a losing position (of the original game), but not one in which his opponent can win in one move.  Play continues until a player can no longer do this, and then he loses.

I worked out some small N and P values for nim, but I didn't see a clear pattern.


Prove or disprove the following statements:

(a) Let $f: [0,1]\rightarrow[0,1]$ monotone increasing, then $\exists x\in[0,1]: f(x)=x$.

(b) Let $f: [0,1]\rightarrow[0,1]$ monotone decreasing, then $\exists x\in[0,1]: f(x)=x$.


symmetry
ratio
arithmetic sequence
geometric sequence

In how many positive four-digit integers that are not multiples of 1111 do the digits form an arithmetic sequence?

The differences of the sequences must satisfy $ d\equal{}\{\minus{}3,\pm2,\pm1\}$.

If the difference is $ \minus{}3$, then we can only have $ 9$ as the first digit.

If the difference is $ \minus{}2$, then our first digit can be $ 9,8,7,6$.

If the difference is $ \minus{}1$, then our first digit can be $ 9,8,\ldots,3$.

If the difference is $ 1$, then our first digit can be $ 1,2,\ldots,6$.

If the difference is $ 2$, then our first digit can be $ 1,2,3$.

Note that we could have used symmetry to speed up our calculations a little bit (i.e. note that $ 1$ has one fewer case than $ \minus{}1$ does, and $ 2$ has one fewer case than $ \minus{}2$).

Thus, the final answer is $ 1\plus{}4\plus{}7\plus{}6\plus{}3\equal{}\boxed{21}$.

[quote="math154"]Note that we could have used symmetry to speed up our calculations a little bit (i.e. note that $ 1$ has one fewer case than $ \minus{}1$ does, and $ 2$ has one fewer case than $ \minus{}2$).
[/quote]

What do you mean by symmetry? If there was, then wouldn't there be an even answer?

I wasn't sure what an arithmetic sequence was, so I gave up.  Is it like 1234?

An arithmetic sequence is a sequence of numbers that have a common [b]difference[/b]. An example would be 1, 2, 3, 4, ... (which has common difference 1). Another would be 1, 4, 7, 10, 13, ... (which has common difference 3).

A geometric sequence is similar. It is a sequence of numbers that have a common [b]ratio[/b]. An example would be 1, 2, 4, 8, ... (which has common ratio 2). Another would be 1, 1/2, 1/4, 1/8, ... (which has common ratio 1/2).

Hope this helps!

[quote=TheReaper10]This question is just time consuming not really hard[/quote]

Its not that time-consuming. There is only 21 cases.

[quote=heheman]YEA I SOLVE 190 CASES FOR AMC8 2019 PROBLEM 25  :coool::coool::coool::coool::coool:[/quote]

i asked


It's very easy!!
WLOG, assume that $abc=1$.
Notice that $\sum\frac{a}{bc}+\sum\frac{1}{a}\geq \sum\frac{4a}{a^{2}+bc}$ and $\sum\frac{a}{bc}\geq \sum\frac{1}{a}$........

[quote="j555"]$a$, $b$, $c$ $> 0$. Prove
$\frac{2a}{a^{2}+bc}+\frac{2b}{b^{2}+ca}+\frac{2c}{c^{2}+ab}\le\frac{a}{bc}+\frac{b}{ca}+\frac{c}{ab}$.[/quote]

I try it, just for fun:

after bunching it becames:

$(6,1,1)+2(5,3,0)\ge2(4,3,1)+(3,3,2)$

Well by Schur multiplied by $abc$ we have

$(n+1,1,1)+(n-1,2,2)\ge2(n,2,1)$

using left operation we get:

$(n+1,1,1)+(n,3,0)\ge2(n,2,1)$

for $n=5$ it becames $(6,1,1)+(5,3,0)\ge2(5,2,1)$

Now it remains to prove that

$(5,3,0)+2(5,2,1)\ge2(4,3,1)+(3,3,2)$

what are trivially three Muirheads. So we have our ineq with equality case iff $a=b=c$.

My notation and used theory can be found here:

http://www.mathlinks.ro/Forum/viewtopic.php?p=619876

[quote="j555"]$a$, $b$, $c$ $> 0$. Prove
$\frac{2a}{a^{2}+bc}+\frac{2b}{b^{2}+ca}+\frac{2c}{c^{2}+ab}\le\frac{a}{bc}+\frac{b}{ca}+\frac{c}{ab}$.

[hide="my solution"]
$\frac{4}{a^{2}+bc}\le\frac{1}{a^{2}}+\frac{1}{bc}$, so we just have to prove that
$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\le\frac{a}{bc}+\frac{b}{ca}+\frac{c}{ab}$, what is equivalent to
$ab+bc+ca\le a^{2}+b^{2}+c^{2}$. :P
[/hide][/quote]
Sorry I'm still learning inequalities, at least for now I can't understand your steps...

Well the first statement is just:
$\left( \frac{1}{a^{2}}+\frac{1}{bc}\right) (a^{2}+bc)\geq 4$ (trivial Cauchy)
$\implies \frac{2a}{a^{2}+bc}+\frac{2b}{b^{2}+ca}+\frac{2c}{c^{2}+ab}\leq \frac12 \left( \frac{1}{a}+\frac{a}{bc}+\frac{1}{b}+\frac{b}{ca}+\frac{1}{c}+\frac{c}{ab}\right)$
and if $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\le\frac{a}{bc}+\frac{b}{ca}+\frac{c}{ab}$
then
$\frac{2a}{a^{2}+bc}+\frac{2b}{b^{2}+ca}+\frac{2c}{c^{2}+ab}\leq \frac12 \left( \frac{1}{a}+\frac{a}{bc}+\frac{1}{b}+\frac{b}{ca}+\frac{1}{c}+\frac{c}{ab}\right)\leq \frac{a}{bc}+\frac{b}{ca}+\frac{c}{ab}$
So we want to prove:
$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{a}{a^{2}}+\frac{b}{b^{2}}+\frac{c}{c^{2}}\le\frac{a}{bc}+\frac{b}{ca}+\frac{c}{ab}$
I don't see how this is equivalent to $ab+bc+ca\le a^{2}+b^{2}+c^{2}$
what inequality is that one?

[quote="conceive"][quote="j555"]Very funny solution! :rotfl:[/quote]

Please in math forum only math. There is no reason to write posts like "very funny". It won't make better any problem solving abilities of anyone.

conceive

[Moderator edit: This post by Conceive was deleted. Stop spamming.][/quote]
[i]Very funny[/i] means that you tried to kill by Muirhead an easy inequality. It's as funny as killing a fly using a hammer.

Haha, funny! I think he was trying to kill with an even more general than Muirhead inequality, which generalizes Schur+Muirhead... talk about a tank vs. a fly... :spider: well thats not quite a fly but you can image...
anyway i'm sorry about my stupid question, if i thought about it for like 5 more seconds i wouldn't have been confused at all...

[quote="Albanian Eagle"][quote="conceive"]
I try it, just for fun:

after bunching it becames:

$(6,1,1)+2(5,3,0)\ge2(4,3,1)+(3,3,2)$

Well by Schur multiplied by $abc$
...[/quote]
it's ridiculous to continue that way
we already know that $(5,3,0)\geq (4,3,1)$ and $(6,1,1)\geq (3,3,2)$ from muirhead...[/quote]

I admit it. I didn't get it at first.


projective geometry
geometry
perpendicular bisector
angle bisector
geometry unsolved

Can someone prove this?

      Let w is a circle and A is any point(not inside w). Tangents from A to w touches w at D and E. Let B any point on the circle.And AB intersects w again C.(AB<AC).
DE intersects AC at T. Then AB:AC=BT:TC

(From definition of polar line; DE is the polar line of the point A)

This problem is related to harmonic sequence of points.

Let $w=(O,R)$

Let $K \in AO \cap DE$ and $F$ the midpoint of $BC$

The power of the point $A$ with respect to the circle $w$ is $AB \cdot AC = AO^{2}-R^{2}$

At first we will prove that $\boxed{AB \cdot AC = AF \cdot AT}\ (1)$

$\angle OKT = \angle OFT = 90^{o}\Rightarrow $ the quadrilateral $OKTF$ is cyclic $\Rightarrow  AK \cdot AO = AF \cdot AT \ (2)$

On the other hand, we have:

$OK \cdot AO = R^{2}\Rightarrow $

$(AO-AK) AO = R^{2}\Rightarrow $

$AO^{2}-R^{2}= AK \cdot AO$

$AB \cdot AC = AK \cdot AO \ \ (3)$

$(2) \wedge (3) \Rightarrow  (1)$

$\hline$
Now we have:

$(1) \Rightarrow  \frac{AT}{AB}= \frac{AC}{AF}\Rightarrow  \frac{AT-AB}{AB}= \frac{AC-AF}{AF}\Rightarrow  \boxed{\frac{TB}{AB}= \frac{CF}{AF}}\ (4)$

$(1) \Rightarrow  \frac{AT}{AC}= \frac{AB}{AF}\Rightarrow  \frac{AC-AT}{AC}= \frac{AF-AB}{AF}\Rightarrow  \boxed{\frac{TC}{AC}= \frac{BF}{AF}}\ (5)$

$\hline$
$(4) \wedge (5) \Rightarrow  \frac{TB}{AB}= \frac{TC}{AC}$

Just another solution...

Let $M,N$ be the points of intersection between the line $OA$ and the circle $(AN<AM)$

At first we'll prove that the division $(A,N,F,M)$ is harmonic:
[hide="Just play with fractions..."]$\frac{FM}{FN}= \frac{AM}{AN}\Leftrightarrow$

$\frac{OF+R}{R-OF}= \frac{OA+R}{OA-R}\Leftrightarrow$

$\frac{OF+R}{2R}= \frac{OA+R}{2OA}\Leftrightarrow$

$\frac{OF+R}{R}= \frac{OA+R}{OA}\Leftrightarrow$

$\frac{OF}{R}= \frac{R}{OA}$ , which is true.[/hide]

Since $C$ is on the circle with diameter $MN$ we have $\angle FCN = \angle ACN$

The ray $CF$ intersects the circle at the point $H$.

So the arcs $NH,NB$ are equal $\Rightarrow NB=NH \Rightarrow ON$ is the perpendicular bisector of $BH \Rightarrow FB=FH \Rightarrow$
$\triangle FBH$ isosceles $\Rightarrow \angle AFB = \angle AFH \Rightarrow FA$ is the external angle bisector of $\angle CFB$ in $\triangle CFB \Rightarrow$

$FT$ is the angle bisector of $\angle CFB \Rightarrow \frac{AB}{AC}= \frac{TB}{TC}$


I have one, just right after I fill my cup with water!!
Let A is a prime number, A'll be equal to X^b+Y^c. X,Y are also prime numbers, a,b are in N (N={0,1,...})!
Can it true??

It CAN be true, e.g.
7=2^2+3^1
Many many other examples.

But it doesn't always have to be true:

Note that if A is greater than 3, then either X=2, or Y=2. (Suppose otherwise. Then X, Y are both odd or both even. So the sum of their powers is even. But A is odd, which is impossible.) WLOG assume that X=2.

For A=5557 (a prime), we have
Then Y^c=5557-2^b

Testing values of b from 0 to 12 yields no solutions.

Ok!! Thanks for Ur help!! With the best regards!! May be U can give me Ur Yahoo ID??!!
Mine is Dao007forever, contact soon!!


This one is quite strange but nice :)

Let a(1), a(2), ..., a(n) be different positive integers. Prove that

a(1) + a(2) + ... + a(n) :ge: (2n + 1)(a(1) + a(2) + ... + a(n))/3.

[b]Solution:[/b]

Lets consider that 0<a1<..<an. Then we have that:
a1>=1,a2>=2,.., an>=n.
Lets denote b1=a1-1,..,bn=an-n. So we have now that:
b_(i+1)-bi=a_(i+1)-ai-1>=0, because a_(i+1)>=1+ai.

Now we see that:
sum (ai^2)=sum(bi+i)^2=sum(bi^2)+2*sum(ibi)+sumi^2)
 sum (ai)=sum(bi+i)=sum(bi)+sum(i)
Now we replace in the ineq and we get that:
3*sum(bi^2)+6*sum(ibi)>=(2n+1)*sum(bi).

because b1<=..<=bn we use cebasev's inequality!!!
3*sum(ibi)>=1/n*(sum (bi))*(sum(i))=n(n+1)/(2n) *sum(bi)=(n+1)/2 * sum(bi.

so we get in the end that: 3*sum(bi^2)+6*sum(ibi)>=3*sum(bi^2)+3(n+1)*sum(bi)>=(2n+1)*sum(bi)..

that's it!!!
cheers!!!