geometry
geometric transformation
reflection
function

Okay, here's a question I've thought about for a couple days and haven't solved, so I figured I'd toss it out here.  It has to do with a generalization of Setofallsets' question in the Mandelbrot Problem Corner from last year.  Reduced to my point of stuckness, though, my question is this:

What is  :Sigma: ki*C(m, i)2 where the summation is from i = 0 to m?  The cases k = 0 and k = 1 are both known to me.  I think I could get k = -1, although I haven't really tried.  But I want a general form, and I haven't even been able to get the case for k = 2.  Any ideas?

By the way, does anyone know if there's a nice html way to write C(m, i) so it looks sort of like (mi)?

Note: edited to reflect typo.

Can't you just pull km out of the summation?  Perhaps you mean ki, not km.

I'm not sure how to interpret your sum. Surely it can't be k^m*C(m,i)^2, because then you could factor k^m out, nor is it k^(m*C(m,i)^2) because then it is trivial for k=0,1.

If it is k^i*Binomial[m,i]^2

Mathematica gives a simple form in terms of the 2F1 function

\sum=2F1(-m,-m;l;k)

Oops.  It should be k^i.  What the heck does that mean, fairy?

here is the most i have right now:

the desired sum

=  [ x^n ] in (1 + (k+1)x + kx^2)^n

does [ x^n ] mean the coefficient of x^n?


geometry
3D geometry
sphere
incenter
circumcircle
angle bisector
Iran

Let $ABC$ be a triangle, and let $w$ be a circle passing through $A$ and $C$. Sides $AB$ and $BC$ meet $w$ again at $D$ and $E$, respectively. Let $q$ be the incircle of the [b]circular[/b] triangle $EBD$, i. e. the circle which touches the segments $BD$ and $BE$ and internally touches the circle $w$. Suppose the circle $q$ touches the arc $DE$ at $M$. Prove that the line $MI$ is the angle bisector of the angle $AMC$, where $I$ is the incenter of triangle $ABC$.

sorry , i dont know whot u mean by a circular triangle and ,u havent specified the point F as well as y.
regards

Ops...
By a circular triangle, I mean a figure surounded by sides BE, BD and arc DE of circle w (w is passing through A, C, D, E). So M is the point of tangency circles w and q.
I hope now is ok. Sorry again!

This problem follows from next trivial lemma:

Lemma. Let ABC be a triangle. X and Y are points on
AB and BC respectively such that BX=BY. I -- incenter of ABC.
Let M be the second point of intersection of circumcirles
of AXI and CYI.

Then circumcirle of XMY touches

1) AB and BC (in X and Y)

2) circumcircle of AMC (in M)

To prove the first part we can observe, that \angle XMY =(\angle A+\angle C)/2.

To prove the second part it is only need to prove that
\angle XMA=\angle XYM+\angle MCA.

Let \phi=\angle AXI=\angle CYI

We have \angle XMA= \angle XIA =\pi - \angle A/2 -\phi=
\pi-\phi-1/2(\pi-\angle B-\angle C)=\pi/2+\angle B/2-\phi+\angle ICA=
\pi/2+\angle B/2-\phi+\angle ICA=\angle XYC - \phi -\angle MCI+\angle MCA=\angle XYM +\angle MCA, since \angle MCI=\angle MYI.

[color=red][Moderator edit: Typo corrected][/color]

Dear Mathlinkers,
This result from Protassov (1994) can be seen on
http://perso.orange.fr/jl.ayme  vol. 2  Un remarquable résultat de Vladimir Protassov
Sincerely
Jean-Louis


Can someone plz explain cyclic notation? It's really confusing me. why isn't (abcd) the same as (a)(b)(c)(d) or (ab)(cd)?

cyclic notation has been explained many, many times, but since I myself is too lazy to go look up, I will give you the definition.

What cyclic does basically is adding all the terms of given formula of variables in ALL PERMUTATIONS.

ex. $\sum_{cyc}abc = abc + bca + cab = 3abc$
$\sum_{cyc}ab+c = ab+c + bc+a + ca+b = (a+b+c)+(ab+bc+ca)$-------- 1.

we can rewrite 1. as:
$\sum_{cyc}c + \sum_{cyc}ab = \sum_{cyc}ab+c$, which is the same thing we started with. From this, we can see that the cyclic sums are distributive.

I think that wasnt a good explanation, but you get the idea.

[quote="filletwho"]I guess my confusion lies with a specific statement-

[quote]Count the number of ways to arrange beads on a necklace, where there are different colors
of beads, and total beads arranged on the necklace.

If the bead positions are called a,b,c, and d, here are the permutations that map the necklace into itself:
(a)(b)(c)(d), (abcd), (ac)(bd), (adbc), (ad)(bc), (ac)(b)(d), (ab)(cd), and (bd)(a)(c).
[/quote]

I really don't understand what they're doing here. What do those parenthesis do and how is (abcd) the same as (adbc)?[/quote]

i dont understand your problem, but i can ask ur last question.... why is (abcd) equal to (adbc):

$\sum_{cyc}abcd = abcd + abdc + acbd + .... = 24abcd$(there are 24 ways to arrange abcd)
$\sum_{cyc}adbc = adbc + abdc + adcb + .... = 24abcd$(there are 24 ways to arrange abcd as well)

Wait... those last two were definitely symmetric sums because there are $4!$ terms in each, whereas a cyclic sum would only have $4$ terms I think.

[url=http://artofproblemsolving.com/Forum/viewtopic.php?highlight=cyclic+symmetric&t=15896]Here[/url] is a link discussing Muirhead, but, perhaps more importantly, the difference between cyclic and symmetric sums explained by billzhao.

As for (abcd), I'm pretty sure it means a->b, b->c, c->d, d->a so (abcd) would not be the same as (adbc). It's not a cyclic sum, but, as the topic suggests, cyclic notation in general within a set/group.

[quote="filletwho"]I guess my confusion lies with a specific statement-

[quote]Count the number of ways to arrange beads on a necklace, where there are different colors
of beads, and total beads arranged on the necklace.

If the bead positions are called a,b,c, and d, here are the permutations that map the necklace into itself:
(a)(b)(c)(d), (abcd), (ac)(bd), (adbc), (ad)(bc), (ac)(b)(d), (ab)(cd), and (bd)(a)(c).
[/quote]

I really don't understand what they're doing here. What do those parenthesis do and how is (abcd) the same as (adbc)?[/quote]

To understand these, you need to understand permutations first.

A permutation on the set S={a,b,c,d} is simply a one-one map from S to itself.

(a)(b)(c)(d) is the identity map on S

(abcd) is a map f: S-->S such that f(a)=b, f(b)=c, f(c)=d, f(d)=a

(ac)(bd) is a map f: S-->S such that f(a)=c, f(c)=a, f(b)=d, f(d)=b

etc.

Ususally, permutations are talked about in elementary group theory.

Ignore everything before what fuzzylogic said -- it has nothing whatsoever to do with your problem.  What they are describing is the set of all possible structures for permutations of 4 things, where the notation is described by fuzzylogic.

:( I almost had it in the last sentence... but I agree, don't bother reading my post unless you want to know about cyclic sums.


The sum of $ n$ consecutive positive integers is 100. What is the greatest possible value of $ n$?

Let the first be a, then:
$ na\plus{}\frac{(n\minus{}1)n}{2}\equal{}100$ from which greatest n is 8, and a=9

Right there are 8 terms of positive integers, and the middle one is 9. What sequence is this?

The actually answer is 5, for the sequence 18,19,20,21,22

See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1932038741&t=242429]here[/url]

Bugi your solution would work, but remember if the median is a whole number it must be an odd number of terms.

Sorry to revive, but Bugi is correct. The sequence is $ 9,10,11,12,13,14,15,16$. Since when did the mean/median have to be an integer? :P  :wink: Refer to [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1406994#1406994]this[/url].

I do not understand how to solve equation

na + (n-1)n/2 = 100


[b]Defining Circular Derangement :[/b]
Given a circular permutation, a Circular Derangement is a rearrangement in which none of the originally adjacently-placed pairs is retained in the same manner.
That is, For every adjacently-placed pair $ (a,b)$ [this means $ a$ is to the left of $ b$], a Circular Derangement must not have $ a$ immediately to the left of $ b$.
[b]
Problem:[/b]
Find a generic formula for the number of Circular Derangements of a circular permutation of $ n$ objects.
Or, Find a neat Recursive formula for the same.

For those who want to "cheat," this is sequence [url=http://www.research.att.com/~njas/sequences/A000757]A000757[/url] in the [url=http://www.research.att.com/~njas/sequences]OEIS[/url].

Does anyone has a good idea on deriving the formula?

Here's the idea behind building one of the recursions.  Think of a circular derangement of $ [n]: \equal{}\{1, \ldots, n\}$ is a circular permutation of $ [n]$ such that $ i$ is not followed by $ i \plus{} 1$ for any $ i$ and $ n$ is not followed by $ 1$.

Now take a circular derangement of $ [n]$ for $ n \geq 3$ and think about what happens if you remove $ n$.  Basically there are four possibilities:

1) The result is a circular derangement of $ [n \minus{} 1]$.
2) The result isn't a circular derangement of $ [n \minus{} 1]$ because previously we had that $ n$ was between $ i$ and $ i \plus{} 1$ for $ 1 \leq i \leq n \minus{} 2$.
3) The result isn't a circular derangement of $ [n \minus{} 1]$ because previously we had that $ n \minus{} 1$ was followed by $ 1$.
4) Both (2) and (3) simultaneously.

We can fix problem (2) in the following way: after erasing $ n$, also erase $ i \plus{} 1$ and replace $ j$ with $ j \minus{} 1$ for all $ j > i \plus{} 1$.  The result is a circular permutation of $ [n \minus{} 2]$.
We can fix problem (3) in the following way: after erasing $ n$, also erase $ n \minus{} 1$.  The result is a circular permutation of $ [n \minus{} 2]$.
We can fix problem (4) by applying both fixes above.  The result is a circular permutation of $ [n \minus{} 3]$.

Now figure out, for each circular permutation of $ [n \minus{} 1]$, $ [n \minus{} 2]$ and $ [n\minus{} 3]$, how many times we produce it as the image of one of these transformations.  The result is one of the recursions listed in the link I gave.


if $ f$ is $ \sigma\{f_t: t\in T\}$ measurable, show that there exists a countable subset $ S\subset T$ such that $ f$ is $ \sigma\{f_t: t\in S\}$ measurable.

thanks

$ \sigma\{f_t: t\in T\}$ is the smallest $ \sigma\minus{}$algebra such that each $ f_t$ is measurable

any hints are welcome


probability
invariant
combinatorics unsolved
combinatorics

THERE ARE 100 BLACK AND 101 WHITE BALLS IN A BOX. WE TAKE TWO BALLS AT RANDOM.

IF THESE BALLS COLOURS ARE SAME THEN WE TAKE THESE BALLS OUTSIDE OF THE BOX  AND PUT A BLACK BALL IN THE BOX INSTEAD OF THEM.

IF THESE BALLS COLOURS ARE DIFFERENT THEN WE PUT THE WHITE BALL IN THE BOX AND PUT THE BLACK ONE OUTSIDE OF THE BOX.

WE CONTINUE THIS PROCEDURE UNTIL THE BOX CONTAINS ONLY ONE BALL...

WHAT IS THE PROBABITY OF THIS BALL ( THE LAST BALL IN THE BOX )  HAVE THE COLOUR WHITE ?

[quote="JoeBlow"][hide="hint:"]Parity.[/hide]
[hide="answer:"]The probability is $ 1$.[/hide][/quote]

HOW CAN IT BE ?

I SHOWED THAT IT CANNOT BE 0 OR 1 BUT COULDN'T FİND THE EXACT SOLUTION...

HOW DID YOU FIND IT?

[quote="JoeBlow"]Ok, here's the hint in more words.  Can the number of white balls be even after one turn?  How about after two turns?  Can it ever be even? How does that relate to the probability of the last ball being white?

This argument instantly generalizes to $ m$ black balls and $ n$ white balls.  The last ball is white if $ n$ is odd, and it is black if $ n$ is even.[/quote]

OK OK I SEE IT NUMBER OF WHITE BALLS ARE INVARIANT IN MOD 2 SO LAST BALL IS ALSO WHITE THANKS :)


$ABC$is an acuted-triangle
prove sum $(sinA)^3(cos(B-c))^2$…<=3$sinAsinBsinC$

Dear HuHuHu!
I check you ineq for $A=50,B=60,C=70$ then:
$LHS=1,8995187..$
$RHS=1,8702155...$
And $LHS>RHS$?

somethings 're wrong here  :blush: . let 's check again

Oh yes.I've solved the ineq which sign reverse.
I have the result it's true.
And your ineq needs reverse sign,isn't it hahaha?

I am sure the inequality is right.Someone have proof it. :)

Oh yes,You are right.
I made a mistake because I did solve your ineq,I solve an other:
$sinA^3cos^2\frac{B-C}{2}+sinB^3cos^2\frac{C-A}{2}+sinC^3cos^2\frac{A-B}{2} \ge 3sinAsinBsinC$
This one is true,too.

 :)  :)


Does anyone know when the AMC national/state/district statistics come out on the site?

They should come out soon; after all, it has been over two weeks since the B test.
But I don't think there's much use for this thread; it'll come out when it does, and the AMC people will no doubt tell us to stop nagging.


Let $ S \equal{}\{1,2,3, \ldots, 2n\}$ ($ n \in \mathbb{Z}^\plus{}$). Ddetermine the number of subsets $ T$ of $ S$ such that there are no 2 element in $ T$ $ a,b$ such that $ |a\minus{}b|\equal{}\{1,n\}$

Here is my approach to solving this problem:

First determine the total number, $ Sk$ of sets of size $ k$ with the following property:
There is at least one pair x, y in this set such that $ |x\minus{}y| \equal{} {1,n}$.

Then total number of sets of size k which satisfy the required condition = $ 2n\choose k$ – $ Sk$

The answer to the problem = $ \sum_{k \equal{} 1}^{2n}$  {$ 2n\choose k$ – $ Sk$}

I am trying to figure out the expression for $ Sk$ now... :)

[quote="KRIS17"]Here is my approach to solving this problem:

First determine the total number, $ Sk$ of sets of size $ k$ with the following property:
There is at least one pair x, y in this set such that $ |x \minus{} y| \equal{} {1,n}$.

Then total number of sets of size k which satisfy the required condition = $ 2n\choose k$ – $ Sk$

The answer to the problem = $ \sum_{k \equal{} 1}^{2n}$  {$ 2n\choose k$ – $ Sk$}

I am trying to figure out the expression for $ Sk$ now... :)[/quote]

Notice that for all $ k > n$ there is always a pair with $ |x \minus{} y| \equal{} 1$

Here is an ugly expression for Sk:

Let A be the set containing k elements of which at least one pair x, y satisfies |x-y| =1.
Let B be the set containing k elements of which at least one pair x, y satisfies |x-y| = n.

Now $ Sk$ = number of sets satisfying both A,B = $ n(A\cup B)$ = $ n(A) \plus{} n(B)$ – $ n(A\cap B)$

$ n(A)$ = $ (2n \minus{} 1)$ * $ 2n \minus{} 2\choose k \minus{} 2$

$ n(B)$ = $ (n)$ * $ 2n \minus{} 2\choose k \minus{} 2$

$ n(A\cap B)$ = $ (2n \minus{} 2)$ * $ 2n \minus{} 4\choose k \minus{} 4$ + $ (2n \minus{} 1)$ *$ (n \minus{} 2)$ * $ 2n \minus{} 6\choose k \minus{} 4$

$ Sk$ = $ (3n \minus{} 1)$ *$ 2n \minus{} 2\choose k \minus{} 2$ - $ (2n \minus{} 2)$ * $ 2n \minus{} 4\choose k \minus{} 4$ - $ (2n \minus{} 1)$ * $ (n \minus{} 2)$ *$ 2n \minus{} 6\choose k \minus{} 4$

As [i]mszew[/i] pointed out that for all $ k > n$ there is always a pair with $ |x \minus{} y|$ = 1, we need sum for k from 1 to n only.

So, the answer is = $ \sum_{k \equal{} 1}^{n}$ {$ 2n\choose k$ - $ Sk$} where $ Sk$ is given above.

I don't think this is an acceptable answer, however I do not yet know of a nicer solution.

[i]kihe_freety5[/i], do you have a solution to this problem? :?:

Not obvious that the answer should be nice.  The first few terms are 1, 3, 6, 16, 37, 91, 218, 528, 1273 ....  Not in the [url=http://www.research.att.com/~njas/sequences/index.html]OEIS[/url].  If we let $ f(n, k)$ be the number of such subsets with $ k$ elements, then it seems that for fixed $ i \geq 1$, $ f(n, n \minus{} i)$ is a polynomial in $ n$ of degree $ i$, and similarly for fixed $ i \geq 0$, $ f(n, i)$ is a polynomial in $ n$ of degree $ i$.

We could instead define $ h(n; S)$ to be the number of subsets of $ \{1, \ldots, n\}$ with no two elements that differ by an element of $ S$.  Then, for example, $ h(n; \emptyset) \equal{} 2^n$, $ h(n; \{1\}) \equal{} F_n$ (the $ n$th Fibonacci number), $ h(n; \{2\})$ is given by [url=http://www.research.att.com/~njas/sequences/A006498]A006498[/url] in the OEIS, $ h(n; \{1, 2\})$ is given by [url=http://www.research.att.com/~njas/sequences/A000930]A000930[/url], and similarly $ h(n; S)$ has a simple linear recurrence relation.  But I don't think this really helps us write a nice formula for the objects in question.

[b]JBL wrote:[/b]
[quote]The first few terms are 1, 3, 6, 16, 37, 91, 218, 528, 1273 ....[/quote]

What software did you use to calculate the above terms? I use a very crude method of extracting terms.

Perhaps the reason to think that a nicer solution exists is that, the question was asked in a math olympiad exam.

Just a simple script on Mathematica.  Brute-force computation, i.e., I had it generate all subsets and then delete out those that contained two illicit values.

Hey, KRIS17 you overconted while calculating Sk, for example:

$ n(A) \equal{} (2n \minus{} 1)*$$ 2n \minus{} 2\choose k \minus{} 2$ when you say that you are counting many times those sets that contain more than one pair $ (x;y)$ with the property $ |x \minus{} y| \equal{} 1$

sorry, my school is HUS and no one solved it in our team!! I failed in it

Incomplete Idea: Partition the set into pairs $ (1,n \plus{} 1), (2,n \plus{} 2), \ldots (n,2n)$. The conditions forbid us to pick both elements of these pairs, so we can pick one of them or neither. Now we just need to eliminate the consecutive ones. For instance, if we pick an element from $ (1,n \plus{} 1)$, this leaves $ 2$ choices of what to do with $ (2,n \plus{} 2)$ - instead of picking either element or nothing, we can now pick only one element or nothing.

Using two recursive sequences, you can get that the number of valid subsets for $ n$ with neither $ 1$ nor $ n \plus{} 1$ in them (call this sequence $ a_n$) satisfies $ a_n \equal{} 2a_{n \minus{} 1} \plus{} a_{n \minus{} 2}$ with $ a_0 \equal{} a_1 \equal{} 1$ and has the explicit formula
\[ a_n \equal{} \frac {(1 \plus{} \sqrt {2})^n \plus{} (1 \minus{} \sqrt {2})^n}{2}.
\]
Likewise, if $ b_n$ is the number of valid subsets with either of $ 1$ or $ n \plus{} 1$ in them, then this also satisfies $ b_n \equal{} 2b_{n \minus{} 1} \plus{} b_{n \minus{} 2}$ with $ b_0 \equal{} 0, b_1 \equal{} 2$ and has explicit formula
\[ b_n \equal{} \frac {(1 \plus{} \sqrt {2})^n \minus{} (1 \minus{} \sqrt {2})^n}{\sqrt {2}}.
\]
The answer would be $ a_n \plus{} b_n$, but there is one problem: the adjacency of $ n$ and $ n \plus{} 1$ has not been accounted for. I'm thinking there's a way to use the recursion some more to take care of this overcount, but I have not pinned it down. I feel like this is very close.

EDIT: Completed, see my next post.

[b]ThiagoSPinheiro wrote:[/b]

[quote]Hey, KRIS17 you overconted while calculating Sk[/quote]

 :oops_sign: You are right, I did overcount.

Here are the revised expressions:
$ n(A)$ = $ 2n \minus{} 2\choose k \minus{} 2$ + $ 2n \minus{} 3\choose k \minus{} 2$ + $ 2n \minus{} 4\choose k \minus{} 2$ + ...+ $ k \minus{} 2\choose k \minus{} 2$

$ n(B)$ = $ 2n \minus{} 2\choose k \minus{} 2$ + $ 2n \minus{} 3\choose k \minus{} 2$ + $ 2n \minus{} 4\choose k \minus{} 2$ + ...+ $ k \minus{} 1\choose k \minus{} 2$

I will post $ n(A\cap B)$ tomorrow, I need to sleep now  :sleeping: .

[b]ThiagoSPinheiro[/b], do you agree with the above formulas?

Got something that matches JBL's sequence. The form is horrendous, but I didn't expect any better.

Building off of my previous post: Condition on the first pair $ (k,n \plus{} k)$ to not have a number chosen.
- If neither of $ (1,n \plus{} 1)$ is chosen, we can do the rest arbitrarily for $ a_n$ ways.
- If $ (k,n \plus{} k)$ is the first not chosen, we have to pick one of $ (1,n \plus{} 1)$ to be in it. This uniquely determines the pairs $ (2,n \plus{} 2)$ through $ (k \minus{} 1,n \plus{} k \minus{} 1)$. Now we can work backwards from $ (n,2n)$ to $ (k \plus{} 1,n \plus{} k \plus{} 1)$ to figure out how many ways to do the remaining pairs. If $ 1$ was picked, we can do the rest in $ a_{n \minus{} k \plus{} 1}$ ways. If $ n \plus{} 1$ was picked, we can't use $ n$ when we work backwards, so this is effectively a $ b_i$ case for $ b_{n \minus{} k \plus{} 1}/2$ ways.
- There is a possibility that all pairs have a number chosen and the size of the subset is $ n$. This case can be computed to have $ 1$ valid subset for even $ n$ and $ 2$ for odd $ n$.

Combining all of these cases results in having to compute partial sums of $ a_i$ and $ b_i$, but once it's all tidied and simplified, the final answer is
\[ \frac {(3 \plus{} \sqrt {2})(1 \plus{} \sqrt {2}) ^n \plus{} (3 \minus{} \sqrt {2})(1 \minus{} \sqrt {2})^n \minus{} 2 ( \minus{} 1)^n}{4}.
\]

The number of terms required to express $ n(A\cap B)$ turned out to be much much more than I had thought earlier. I regret wasting my time on this seemingly impossible and highly intractable problem. Well for those who care here goes my procedure to determine $ n(A\cap B)$, which is the total number of sets of size $ k$ taken from {1, 2, 3, ...2n}with the following property: There is at least one pair x, y in this set such that that |x-y| =1 and |x-y| =n

EDIT: I had missed Steps N-1) and N) in my earlier post, now they are added to make the solution complete.

[hide="click here to unhide"]
[u]Step 1) [/u]Let us find the number of sets of size k that contain {1, 2} satisfying both A & B.
Start with {1, 2, n+1} we have 3 elements which satisfy both A & B. Now we need k-3 elements to choose from 2n-3 elements
This can be done in $ 2n \minus{} 3\choose k \minus{} 3$ ways.

Now start with {1, 2, n+2} we have 3 elements that satisfy A & B. Need k-3 elements from 2n-4 (We don’t want n+1). This can be done in $ 2n \minus{} 4\choose k \minus{} 3$ ways.

Now we need {1, 2} and some other pair {i, i+n}, where 3<=i<=n

So start with {1, 2, 3, n+3} we have 4 elements that satisfy A & B. Need k-4 elements from 2n-6 (we don’t want n+1, n+2}. This can be done in $ 2n \minus{} 6\choose k \minus{} 3$ ways.

Next take {1, 2, 4, n+4}. Need k-4 from 2n-7 (we don’t want n+1, n+2, n+3)

Next take {1, 2, 5, n+5}. Need k-4 from 2n-8 (we don’t want n+1, n+2, n+3, n+4)
…
…
…
Finally take {1, 2, n, 2n}. Need k-4 from n-3 (we don’t want n+1, n+2, n+3, n+4, …n+n-1)

So the required sum = $ 2n \minus{} 3\choose k \minus{} 3$ + $ 2n \minus{} 4\choose k \minus{} 3$ + $ 2n \minus{} 6\choose k \minus{} 4$ + $ 2n \minus{} 7\choose k \minus{} 4$ +…. + $ n \minus{} 3\choose k \minus{} 4$

[u]Step 2) [/u]Let us find the number of sets of size k that contain {2, 3} satisfying both A & B.
Now start with {2, 3, n+2}. Need k-3 from 2n-4 (we don’t want 1)
Next take {2, 3, n+3}. Need k-3 from 2n-5 (we don’t want 1, n+2)

Now we need {2, 3} and some other pair {i, i+n}, where 4<=i<=n

So start with {2, 3, 4, n+4). Need k-4 from 2n-7 (we don’t want 1, n+2, n+3)
Next take {2, 3, 5, n+5). Need k-4 from 2n-8 (we don’t want 1, n+2, n+3, n+4)
…
…
…
Finally take (2, 3, n, 2n). Need k-4 from n-3 (we don’t want 1, n+2, n+3, …, n+n-1)

So the required sum = $ 2n \minus{} 4\choose k \minus{} 3$ + $ 2n \minus{} 5\choose k \minus{} 3$ + $ 2n \minus{} 7\choose k \minus{} 4$ + $ 2n \minus{} 8\choose k \minus{} 4$ +…. + $ n \minus{} 3\choose k \minus{} 4$

Now, repeat the above steps starting with sets containing elements {3,4}, {4,3}, ...

[u]Step N-2)[/u] After repeating the above process several times we reach a set containing {n-2, n-1}. Let us find the number of sets of size k that contain {n-2, n-1} satisfying both A & B.
Start with {n-2, n-1, n+n-2}. Need k-3 from 2n- (3+n-3) = n (we don’t want 1, 2, …, n-3)
This can be done in $ n\choose k \minus{} 3$ ways.

Next take {n-2, n-1, n+n-1}. Need k-3 from 2n – (3 + n-3 +1) = n-1 (we don’t want 1, 2, …, n-3, n+n-2)

Now we need {n-2, n-1} and some other pair {i, i+n}, where n<=i<=n. This means i=n.

So we take {n-2, n-1, n, n+2n}. Need k-4 from n-3 (we don’t want 1, 2, 3, …, n-3, n+n-2, n+n-1)

So the required sum = $ n\choose k \minus{} 3$ + $ n \minus{} 1\choose k \minus{} 3$ + $ n \minus{} 3\choose k \minus{} 4$

[u]Step N-1)[/u] Let us find the number of sets of size k that contain {n-1, n} satisfying both A & B.
Start with {n-1, n, n+n-1}. Need k-3 from 2n- (3+n-2) = n-1 (we don’t want 1, 2, …, n-2)
This can be done in $ n \plus{} 1\choose k \minus{} 3$ ways.

Next take {n-1, n, n+n}. Need k-3 from 2n – (3 + n-2 +1) = n-2 (we don’t want 1, 2, …, n-2, n+n-1)

Now we need {n-1, n} and some other pair {i, i+n}, where n+1<=i<=n. So there is no other set.

So the required sum = $ n \minus{} 1\choose k \minus{} 3$ + $ n \minus{} 2\choose k \minus{} 3$

[u]Step N)[/u] Let us find the number of sets of size k that contain {n, n+1} satisfying both A & B.
Start with {n, n+1, n+n}. Need k-3 from 2n- (3+n-1) = n-2 (we don’t want 1, 2, …, n-1)
This can be done in $ n \minus{} 2\choose k \minus{} 3$ ways.

Now we cannot take {n, n+1, n+n+1}, because n+n+1 does not exist in our original set of numbers.

So the required sum = $ n \minus{} 2\choose k \minus{} 3$

So $ n(A\cap B)$ is given by the combinatorial sums from parts  1) to  N)
[/hide]

The solution and answer of Mellow Melon is right.

And I think his approach is the only approach for this problem: to establish recurrent relation

We have a recurrent relation:   $ S_n \equal{} S_{n\minus{}1} \plus{} 3S_{n\minus{}2} \plus{} S_{n\minus{}3}$  where $ S_0 \equal{} 1, S_1\equal{}3, S_2\equal{}6$

[b]Namdung wrote:[/b]
[quote]We have a recurrent relation: $ S_n \equal{} S_{n\minus{}1} \plus{} 3S_{n\minus{}2} \plus{} S_{n\minus{}3}$ where $ S_0 \equal{} 1, S_1 \equal{} 3, S_2 \equal{} 6$  [/quote]

[i]Namdung[/i], can you please provide your solution? It would be very enlightening to see it :)

I tried to write the solution here, please see the attached file.

I hope that the solution is right and understandable.

We can also compute as follows. Notation as in Namdung's answer.

Let $f(E) = E^2-2E-1$. We have $f(E)a_n = 0$ and $f(E)b_n = 0$ and
\begin{align*}
f(E)(c_n - c_{n-2}) = f(E)(b_{n-1} + b_{n-2}) = 0
\end{align*}
Hence
\begin{align*}
f(E)c_n = f(E)c_{n-2}
\end{align*}
When $n=2m$ is even, we have
\begin{align*}
f(E)c_{2m} &= f(E)c_{2m-2} = \cdots = f(E)c_0 \\
&=c_2 - 2c_1 - c_0 \\
&= 4 - 2 \cdot 1 - 1 \\
&=1
\end{align*}
When $n=2m+1$ is odd, we have
\begin{align*}
f(E)c_{2m+1} &= f(E)c_{2m-1} = \cdots = f(E)c_1 \\
&=c_3 - 2c_2 - c_1 \\
&= 8 - 2 \cdot 4 - 1 \\
&=-1
\end{align*}
Hence we can write $f(E)c_n = (-1)^n$. We now have
\begin{align*}
f(E)S_n = f(E)a_n - f(E)c_{n-2} = (-1)^{n+1}
\end{align*}
Thus $S_n$ satisfies the recurrence relation
\begin{align*}
S_{n+2} - 2S_{n+1} - S_n = (-1)^{n+1}
\end{align*}
This is a non homogeneous recurrence relation with characteristic roots $1 \pm \sqrt{2}$ and the general solution can be written as
\begin{align*}
S_n = A(1+\sqrt{2})^n + B(1-\sqrt{2})^n + C(-1)^n
\end{align*}
 Using $S_1 = 3, S_2 = 6$ and $S_3 = 16$, we can obtain
 \begin{align*}
 A = \dfrac{3+\sqrt{2}}{4}, \, B = \dfrac{3-\sqrt{2}}{4}, \, C = -\dfrac{1}{2}
 \end{align*}
 and we obtain the same expression for $S_n$ as before.\\

We'll associate each valid subset to a $n-$digit string with characters from the set $\{N, F, S\}$ as follows. For each $1 \le i \le n$, the $i$th digit of the string is $N$ if none of $i, n+i$ are in the subset, $F$ is $i$ is in the subset, and $n+i$ if $S$ is in the subset. From the condition, $i, n+i$ wouldn't both be in the subset. Then, we can easily see that it suffices to find that number of strings in $\{N, F, S\}^n$ such that there are no two consecutive $F$'s, no two consecutive $S$'s, and the string doesn't start with $S$ and end with $F.$

It's quite easy to establish a linear recursion on the number of strings without two consecutive $F$'s or two consecutive $S$'s. Then, we can also establish a linear recursion on the number of strings starting with $S$, ending with $F$, and without two consecutive $F$'s or two consecutive $S$'s. Subtracting would yield the desired formula.

$\square$


algebra
polynomial
function
number theory
prime numbers
number theory unsolved

S={a|a is a primitive root modulo p,$1\leq{a}\leq{p-1}$}
calculate
 $\sum_{x\in{S}}x$ (mod p)

to t0rajir0u thank you but the problem not solved there.

The solution is, as t0rajir0u wanted to point out, exactly $\mu(p-1) \mod p$.
This for example follows from standard theorems on orders and cyclotomic polynomials.

[quote="Rust"]Let $S_{p}=\sum_{x\in{S}}x$. It is easy to chek, that $S_{2}=1,S_{3}=2$.
If $p>3$ then we have $\phi(p-1)$ primitive roots.
If $p=1(mod 4)$  x is primitive root, then p-x primitive root too. Therefore $S_{p}=\frac{p\phi (p-1)}{2}$ for $p=1(mod 4)$.
But for $p=3(mod 4)$ can be $p\not |S_{p}$. For example $S_{7}=3+5=8$, $S_{11}=23$.[/quote]thank Rust can you prove this:
The sum of all primitive roots [of a prime number p ] is either=0(mod p)  (when p-1 is divisible by a square), or=-1,+1  (mod p) (when p-1  is the product of unequal prime numbers; if the number of these is even the sign is positive but if the number is odd, the sign is negative.

Calculate mod p is easy. Because all primitive roots are roots of cyclotomic polinom
\[\prod_{d|p-1}(x^{(p-1)/d}-1)^{\mu(d)}. \]

is there elementary solution?(without use the cyclotomic polinom )

Define elementary or accept cyclotomic polynomials as elementary (they are!).

ok  cyclotomic polinom is elementary.
but I dont know any thing about cyclotomic polinomials.I need a proof without cyclotomic polinomials.

What about the converse: learn something about cyclotomic polynomials.

Let $\zeta$ be a primitive root modulo $n.$ Then all primitive roots modulo $n$ can be obtained as the powers $\zeta^{k}$ where $(k,n)=1.$
The sum of all primitive roots modulo $n$ can be computed using the inclusion-exclusion principle as
\[\sum_{k=1\atop (k,n)=1}^{n}\zeta^{k}= \sum_{d\mid rad(n)}\mu(d) \sum_{k=1}^{n/d}\zeta^{kd}\]
where $rad(n)$ is the product of all distinct prime factors of $n$ and $\mu$ is Moebius function. It is easy to see that the inner sum equals 0 if $d\ne n$ and equals 1 otherwise. Therefore, the sum of all primitive roots modulo $n$ is $\mu(n).$

I'll complete the proof started by Rust Let f(P) be sum of the roots of the monic polynomial P. (counted with multeplicity)
Then $f(PQ) = f(P)+f(Q)$
From the fact that
$\prod_{d \mid n}\Phi_{d}= x^{n}-1$ (where $\Phi$'s are cyclotomic polynomials)
we deduce:
$\sum_{d \mid n}f(\Phi_{d}) = 0$ for n>1
and  $f(\Phi_{1}) = 1$.

But then $f(\Phi_{n})$ is Moebius' function!

This concludes the proof started by Rust.


linear algebra
matrix
advanced fields
advanced fields unsolved

Let $f: \mathbb{R}^{n}\rightarrow\mathbb{R}$, $f\in C^{2}(\mathbb{R}^{n})$, $x\in\mathbb{R}^{n}$ such that $H_{f}(x)$, the Hessian matrix of $f$ is positive definite.

Prove that $\nabla f(x)^\mathtt{T}d\leq-\frac{\parallel \nabla f(x)\parallel .\parallel d\parallel }{\parallel H_{f}(x)\parallel .\parallel [H_{f}(x)]^{-1}\parallel }$

Where $d\in\mathbb{R}^{n}$ satisfies $H_{f}(x)d=-\nabla f(x)$ and $\parallel .\parallel =\parallel .\parallel _{2}$


superior algebra
superior algebra unsolved

Show that, for every number field $K$, there exists a finite extension $L$ such that every ideal of $K$ becomes a principal ideal.

Let $ {I_1,...,I_r}$ be a finite set of ideals that generate the class group and let $ I_1^{t_1}\equal{}(a_1),\cdots I_r^{t_r}\equal{}(a_r)$. The field $ L\equal{}K(\sqrt[t_1]{a_1},\cdots \sqrt[t_r]{a_r})$ satisfies this property.


An object explodes while it is in the air and breaks into two pieces $A$ and $B$. The two pieces go on the level plane in opposite direction at $v = 3$ and $4 m/s$, respectively. Because of earth's gravity, they fall down at $g = 9.8 m/s^2$. How far apart are they when their velocity vectors are perpendicular to each other.

Oh, sure :). Well, the velocity vectors of A and B will have constant horizontal components - 3 m/s and 4 m/s - only the vertical component will change (increase). Since they're both accelerating at the same rate, they will both have the same vertical speed at any given time and let's denote $v_h$ this speed in moment when the two vectors are perpendicular. We know that two vectros are perpendicular when their scalar product is zero:

$(-3)\times(4)+v_h\times v_h=0$
$v_h=\sqrt{12}$

A and B will have vertical speed $\sqrt{12}\text{ m/s}$ after $\frac{\sqrt{12}}{9.8}\text{s}$ and their distance will be $\frac{7\sqrt{12}}{9.8}\text{m}$.


a, b, c are all positive then prove bc/(b+c) + ac/(a+c) + ab/(a+b) <=(a+b+c)/2

$ \frac{bc}{b\plus{}c} \leq \frac{b\plus{}c}{4}$  :wink:

[hide="Hint"] Use $ \frac{ab}{a\plus{}b}\leq \frac{a\plus{}b}{4}$[/hide]

[quote="tdl"][hide="Hint"] Use $ \frac {ab}{a \plus{} b}\leq \frac {a \plus{} b}{4}$[/hide][/quote]
great thank you


given $ a,b,c>0$. Prove that:
$ (a^2\plus{}b^2\plus{}c^2)(b\plus{}c\minus{}a)(c\plus{}a\minus{}b)(a\plus{}b\minus{}c) \le\ abc(ab\plus{}bc\plus{}ca)$
 :)

case 1, if $ a,b,c$ aren't lengths of side of a triangle, suppose that $ a \equal{} max\{a,b,c\}$
thus $ (a^2 \plus{} b^2 \plus{} c^2)(a \plus{} b \minus{} c)(b \plus{} c \minus{} a)(a \plus{} c \minus{} b)\leq 0 \leq abc(ab \plus{} bc \plus{} ca)$
case  2, if $ a,b,c$ are lengths of side of a triangle, put that, $ a \equal{} x \plus{} y$ ,$ b \equal{} y \plus{} z$ ,$ c \equal{} z \plus{} x$
then, the inequality becomes,
$ (x \plus{} y)(y \plus{} z)(z \plus{} x)\left((x \plus{} y \plus{} z)^2 \plus{} 3(xy \plus{} yz \plus{} zx)\right)) \geq 16xyz(x^2 \plus{} y^2 \plus{} z^2)$
Now, let put, $ x \plus{} y \plus{} z \equal{} p$ , $ xy \plus{} yz \plus{} zx \equal{} q$ ,$ xyz \equal{} r$ ,then the inequality becomes,
$ (pq \minus{} r)(p^2 \plus{} q)\geq 16r(p^2 \minus{} 2q)$ that's what I found, cans someone complet my solution?

[quote="quykhtn-qa1"]given $ a,b,c > 0$. Prove that:
$ (a^2 \plus{} b^2 \plus{} c^2)(b \plus{} c \minus{} a)(c \plus{} a \minus{} b)(a \plus{} b \minus{} c) \le\ abc(ab \plus{} bc \plus{} ca)$
 :)[/quote]
WLOG we can assume that $ a\plus{}b \geq c,b\plus{}c \geq a,c\plus{}a \geq b$;

the inequality is equivalent to:

$ \frac{abc}{(b\plus{}c\minus{}a)(c\plus{}a\minus{}b)(a\plus{}b\minus{}c)}\minus{}1 \geq \frac{a^2\plus{}b^2\plus{}c^2}{ab\plus{}bc\plus{}ca}\minus{}1$

$ \Leftrightarrow \frac{\sum (a\minus{}b)^2(a\plus{}b\minus{}c)}{(b\plus{}c\minus{}a)(c\plus{}a\minus{}b)(a\plus{}b\minus{}c)} \geq \frac{\sum (a\minus{}b)^2}{ab\plus{}bc\plus{}ca}$

$ \Leftrightarrow \sum(a\minus{}b)^2(\frac{1}{(b\plus{}c\minus{}a)(c\plus{}a\minus{}b)} \minus{} \frac{1}{ab\plus{}bc\plus{}ca}) \geq 0$

It suffices to prove that:

$ \sum (a\minus{}b)^2(\frac{bc\plus{}ca\plus{}a^2\plus{}b^2\minus{}c^2\minus{}ab}{(b\plus{}c\minus{}a)(c\plus{}a\minus{}b)}) \geq 0$

$ \Leftrightarrow  \sum (a\minus{}b)^2(\frac{c(a\plus{}b\minus{}c)\plus{}(a^2\plus{}b^2\minus{}ab)}{(b\plus{}c\minus{}a)(c\plus{}a\minus{}b)}) \geq 0$

which is true.

Peine: You have some mistakes in you calculations. Please check them again ;)

[quote="quykhtn-qa1"]given $ a,b,c > 0$. Prove that:
$ (a^2 \plus{} b^2 \plus{} c^2)(b \plus{} c \minus{} a)(c \plus{} a \minus{} b)(a \plus{} b \minus{} c) \le\ abc(ab \plus{} bc \plus{} ca)$
 :)[/quote]
Obviously we can assume $ a,b,c$ are sides of a triangle. Let $ a \equal{} x\plus{}y, b \equal{} y\plus{}z, c \equal{} z\plus{}x$.
Then we have:
$ ((x\plus{}y\plus{}z)(xy\plus{}yz\plus{}zx)\minus{}xyz)( (x\plus{}y\plus{}z)^2 \plus{} xy\plus{}yz\plus{}zx) \ge 16xyz( (x\plus{}y\plus{}z)^2 \minus{} xy\minus{}yz\minus{}zx)$
Let $ 3u \equal{} x\plus{}y\plus{}z, 3v^2 \equal{} xy\plus{}yz\plus{}zx, w^3 \equal{} abc, u^2 \equal{} tv^2$, so $ t \ge 1$. Then, we have to prove:
$ (9uv^2\minus{}w^3)(3u^2\plus{}v^2) \ge 16w^3(3u^2 \minus{} v^2) \iff$
$ w^3(51u^2\minus{}15v^2) \le 9uv^2(3u^2\plus{}v^2)$
From $ (a\minus{}b)^2(b\minus{}c)^2(c\minus{}a)^2 \ge 0$ we get:
$ w^3 \le 3uv^2 \minus{} 2u^3 \plus{} 2\sqrt{(u^2\minus{}v^2)^3}$.
So we just have to porve:
$ (3uv^2 \minus{} 2u^3 \plus{} 2\sqrt{(u^2\minus{}v^2)^3})(51u^2\minus{}15v^2) \le 9uv^2(3u^2\plus{}v^2) \iff$
$ (3\sqrt{t} \minus{} 2\sqrt{t}t \plus{} 2\sqrt{(t\minus{}1)^3})(51t \minus{} 15) \le 9\sqrt{t}(3t\plus{}1) \iff$
$ 9\sqrt{t}(3t\plus{}1) \minus{} (3\sqrt{t} \minus{} 2\sqrt{t}t \plus{} 2\sqrt{(t\minus{}1)^3})(51t \minus{} 15) \ge 0$
$ \sqrt{t}(102t^2\minus{}156t\plus{}53) \minus{} (t\minus{}1)(2\sqrt{(t\minus{}1)})(51t \minus{} 15) \ge 0 \iff$
$ (t\minus{}1) \left ( \sqrt{t}(102t\minus{}54) \minus{} \sqrt{(t\minus{}1)}(102t \minus{} 30) \right ) \ge 0 \iff$ (since $ t \ge 1$)
$ \sqrt{t}(102t\minus{}54) \ge \sqrt{(t\minus{}1)}(102t \minus{} 30) \iff$
$ t(102t\minus{}54)^2 \ge (t\minus{}1)(102t\minus{}30)^2 \iff$
$ 5508t^2\minus{}4104t \plus{} 900 \ge 0$, which is obviously true since $ t \ge 1$. QED

[quote="FelixD"]@Mathias: are you now arqady?^^[/quote]
Haha.. I stole his method :P

If $ a,b,c$ isn't triangle sides it's obvious. Let $ b\plus{}c\minus{}a\equal{}2x$, $ a\plus{}c\minus{}b\equal{}2y$, $ a\plus{}b\minus{}c\equal{}2z$. So inequality equivalents to;

[If we take; $ x^3yz\plus{}y^3xz\plus{}z^3xy\equal{}T(3,1,1)$, $ x^2y^2z\plus{}x^2z^2y\plus{}y^2z^2x\equal{}T(2,2,1)$, $ x^4y\plus{}xy^4\plus{}y^4z\plus{}yz^4\plus{}x^4z\plus{}zx^4\equal{}T(4,1,0)$

$ x^3y^2\plus{}x^2y^3\plus{}x^3z^2\plus{}x^2z^3\plus{}y^3z^2\plus{}y^2z^3\equal{}T(3,2,0)$]

$ 16.T(3,1,1)\plus{}16.T(2,2,1) \leq T(4,1,0)\plus{}4.T(3,2,0)\plus{}14.T(2,2,1)\plus{}8.T(3,1,1)$ iff

$ 2.T(2,2,1)\plus{}8.T(3,1,1)\leq T(4,1,0)\plus{}4T(3,2,0)$ which is obviously true by Muirhead.  :wink:

[quote="Mathias_DK"]$ ((x \plus{} y \plus{} z)(xy \plus{} yz \plus{} zx) \minus{} xyz)( (x \plus{} y \plus{} z)^2 \plus{} xy \plus{} yz \plus{} zx) \ge 16xyz( (x \plus{} y \plus{} z)^2 \minus{} xy \minus{} yz \minus{} zx)$
[/quote]
Nice ineq, quykhtn-qa1 (althought it's not strong)  :) . Using the well-known: $ (x\plus{}y)(y\plus{}z)(z\plus{}x)(x\plus{}y\plus{}z) \geq\ 24xyz(x^2\plus{}y^2\plus{}z^2)$, we only need to prove:
$ (x\plus{}y)(y\plus{}z)(z\plus{}x)(\sum\ x^2\plus{}5 \sum\ xy) \geq\ 48xyz(xy\plus{}yz\plus{}zx)$
(obviously trues by Am-Gm)  :maybe:

[quote="nguoivn"][quote="Mathias_DK"]$ ((x \plus{} y \plus{} z)(xy \plus{} yz \plus{} zx) \minus{} xyz)( (x \plus{} y \plus{} z)^2 \plus{} xy \plus{} yz \plus{} zx) \ge 16xyz( (x \plus{} y \plus{} z)^2 \minus{} xy \minus{} yz \minus{} zx)$
[/quote]
Nice ineq, quykhtn-qa1 (althought it's not strong)  :)  we only need to prove:
$ (x \plus{} y)(y \plus{} z)(z \plus{} x)(\sum\ x^2 \plus{} 5 \sum\ xy) \geq\ 48xyz(xy \plus{} yz \plus{} zx)$
(obviously trues by Am-Gm)  :maybe:[/quote]
why only need to prove this in equality?? :(

Because your ineq is:
$ (x\plus{}y)(y\plus{}z)(z\plus{}x)(\sum\ x^2 \plus{} 3\sum\ xy) \geq\ 16xyz(\sum\ x^2\plus{} \sum\ xy)$
Using: $ xyz(x^2\plus{}y^2\plus{}z^2) \leq\ \frac{1}{24}(x\plus{}y)(y\plus{}z)(z\plus{}x)(x\plus{}y\plus{}z)^2$
So, we only need to prove:
$ (x\plus{}y)(y\plus{}z)(z\plus{}x)(\sum\ x^2 \plus{} 3\sum\ xy) \minus{} \frac{2}{3}(x\plus{}y)(y\plus{}z)(z\plus{}x)(x\plus{}y\plus{}z)^2 \geq\ 16xyz\sum\ xy$
<=> $ (x\plus{}y)(y\plus{}z)(z\plus{}x)(\sum\ x^2\plus{}5 \sum\ xy) \geq\ 48xyz(xy\plus{}yz\plus{}zx)$  :wink:

[quote="nguoivn"]Because your ineq is:
$ (x \plus{} y)(y \plus{} z)(z \plus{} x)(\sum\ x^2 \plus{} 3\sum\ xy) \geq\ 16xyz(\sum\ x^2 \plus{} \sum\ xy)$
Using: $ xyz(x^2 \plus{} y^2 \plus{} z^2) \leq\ \frac {1}{24}(x \plus{} y)(y \plus{} z)(z \plus{} x)(x \plus{} y \plus{} z)^2$
So, we only need to prove:
$ (x \plus{} y)(y \plus{} z)(z \plus{} x)(\sum\ x^2 \plus{} 3\sum\ xy) \minus{} \frac {2}{3}(x \plus{} y)(y \plus{} z)(z \plus{} x)(x \plus{} y \plus{} z)^2 \geq\ 16xyz\sum\ xy$
<=> $ (x \plus{} y)(y \plus{} z)(z \plus{} x)(\sum\ x^2 \plus{} 5 \sum\ xy) \geq\ 48xyz(xy \plus{} yz \plus{} zx)$  :wink:[/quote]
Now,I understood :blush:


Let $ a_1;a_2;a_3;a_4;a_5$ be non-negative real numbers whose sum equal 1.
Prove that $ a_2a_3a_4a_5\plus{}a_1a_3a_4a_5\plus{}a_1a_2a_3a_5\plus{}a_1a_2a_3a_4 \leq \frac{1}{256}\plus{}\frac{3275}{256}a_1a_2a_3a_4a_5$
When does the equality occur?

Mixing variables!
Noone is interested in it!:(

It seems that this guy is trying to cheat. Most of the problems he posted and call for solutions are recent problems in a problem solving competition in Vietnam.


Let t be an integer and G be the group with generators x and y and relations xyx^-1 =y ^t
 and x^3=1

Find necessary and sufficient condition on t for G to be finite,

In case G is finite determine its order

If t is not 1 then $y=x^{3}y x^{-3}=y^{t^{3}}$ so y has the finite order $t^{3}-1$. Its not that difficult to show, that in this case the group has to be isomorphic to a semidirect product $\mathbb{Z}_{t^{3}-1}\ltimes\mathbb{Z}_{3}$ and hence its order is $(t^{3}-1)3$.
If t=1, then the group is infinite and isomorphic to $\mathbb{Z}\times\mathbb{Z}_{3}$.


Let $ n$ be a positive integer. Prove that:
$ \sum_{k \equal{} 1}^{n}L_k^2\geq \frac {(F_{2n \plus{} 1} \minus{} 1)^2}{F_nF_{n \plus{} 1}}$
where $ F_n$ and $ L_n$ are Fibonaci and Lucas number!

PS:$ L_n \equal{} L_{n \minus{} 1} \plus{} L_{n \minus{} 2}$ with $ L_1 \equal{} 1,L_2 \equal{} 3$
$ F_n \equal{} F_{n \minus{} 1} \plus{} F_{n \minus{} 2}$ with $ L_1 \equal{} L_2 \equal{} 1$


probability
factorial
expected value
probability and stats

A permutation $ \pi$ is selected randomly through all $ n$-permutations.
a) if \[ C_a(\pi)\equal{}\mbox{the number of cycles of length }a\mbox{ in }\pi\] then prove that $ E(C_a(\pi))\equal{}\frac1a$
b) Prove that if $ \{a_1,a_2,\dots,a_k\}\subset\{1,2,\dots,n\}$ the probability that $ \pi$ does not have any cycle with lengths $ a_1,\dots,a_k$ is at most $ \frac1{\sum_{i\equal{}1}^ka_i}$

[quote="Omid Hatami"]A permutation $ \pi$ is selected randomly through all $ n$-permutations.
a) if \[ C_a(\pi)=\mbox{the number of cycles of length }a\mbox{ in }\pi\] then prove that $ E(C_a(\pi))=\frac1a$
b) Prove that if $ \{a_1,a_2,\dots,a_k\}\subset\{1,2,\dots,n\}$ the probability that $ \pi$ does not have any cycle with lengths $ a_1,\dots,a_k$ is at most $ \frac1{\sum_{i=1}^ka_i}$[/quote]

a) Let $K_n^a$ be the number of $n$-permutations with no cycle with length $a$. Then there are $\frac{1}{s!}\dbinom{n}{a,\dots,a,n-sa}(a-1)!^sK_{n-sa}=\frac{n!}{s!a^s}\frac{K_{n-sa}}{(n-sa)!}$ number of $\pi$ with $s$ cycles of length $a$. So probability of having $s$ cycles of length $a$ is $\frac{1}{s!a^s}\frac{K_{n-sa}}{(n-sa)!}$. Hence if $n=ma+r$ for some $0 \leq r<a$ and $1 \leq m$, then $\sum_{s=0}^{m}\frac{1}{s!a^s}\frac{K_{n-sa}}{(n-sa)!}=1 \hspace{5pt}(\star)$
 Thus
\begin{align*}
E(C_a(\pi))&=\sum_{s=0}^{m}s\cdot\frac{1}{s!a^s}\frac{K_{n-sa}}{(n-sa)!}=\sum_{s=0}^{m}\frac{1}{(s-1)!a^s}\frac{K_{n-sa}}{(n-sa)!}=\frac{1}{a}\sum_{s=0}^{m-1}\frac{1}{s!a^s}\frac{K_{n-a-sa}}{(n-a-sa)!}=\frac{1}{a}
\end{align*}
where the last equality follows from $(\star)$ by applying it with $(n-a,m-1,a)$ triplet instead of $(n,m,a)$.

b) this part isn't true. For example, probability of not having a cycle of length $n$ is $\frac{n!-(n-1)!}{n!}=1-\frac{1}{n}>\frac{1}{n}$ for $n\geq 3$.

Let's introduce the indicator $X_i$, which is equal to 1, if the number $i$ belongs to the cycle of length $a$. Then the expected value of the total number of cycles can be represented as $E(C)=E(\sum_i X_i /a)=\sum E(X_i) /a$. But $X_i$ are identically distributed, so $E(X_i)=E(X_1)$ and $\sum E(X_i)=nE(X_1)$.

Going further we obtain that $E(X_1)=P(X_1=1)$ and it is easy to show that it is equal to $1/n$. So we have $E(C)=\frac{n}{na}=1/a$.

No Factorials were harmed in the making of this proof ;)


[quote="turs12"]show that if p,q>0 and 1/p  + 1/q =1 and a,b>0 then

ab<=a^p/p + b^q/q[/quote]

Special case of Young inequality
http://mathworld.wolfram.com/YoungsInequality.html


Find all $x$ such that $\sqrt{19-x}+ \sqrt{97+x}=14$

[hide="Really big hint that gives away (at least) one of the answers"]
Substitute $x=a+3$  ;) [/hide]

[hide="Full solution"]
$\sqrt{a} + \sqrt{b} = \sqrt{a+b+2\sqrt{ab}}$, So
$14=\sqrt{ (97+x)+(19-x)+2\sqrt{1843-78x-x^2}}=\sqrt{116+2\sqrt{1843-78x-x^2}}$
$\implies 40=\sqrt{1843-78x-x^2} \implies 0=x^2+78x-243=(x-3)(x+81)$.
So our answers are $\boxed{x=3 \ , \ x=-81}$.

Or you could use my hint and see that $\sqrt{100+a}+\sqrt{16-a}=14 \implies a=0 \implies x=3$. Then you could see if the if the values of the two radicals could be switched, with the $\sqrt{97+x}$ radical being $4$ instead of $10$, which gives $x=-81$. It just seemed to make sense to me to check if the values of the two could be switched... does it usually work like that?[/hide]

edit: oops  :P  some little changes..

[quote="José"][quote="cincodemayo5590"][hide="Really big hint that gives away (at least) one of the answers"]
Substitute $x=a+3$  ;) [/hide][/quote]

What happens after I substitute???? Can you show us? I can't see it.[/quote]

 :) Read my full solution.

(also, im not sure whether there are imaginary solutions to this... do you know how to get them? b/c when you expand it out, it only gives a quadratic and not a quartic polynomial. Does that mean there are none?)

M4RIO they're not guranteed to be integers but you can still use that method to get $\ ab=40$

I didn't say $a$ and $b$ were integers, they could be imaginary or complex, but after solving we find they are integers.

[quote="t0rajir0u"][quote="cincodemayo5590"](also, im not sure whether there are imaginary solutions to this... [/quote]

Depends on exactly how you define the square root function for a complex number.  Which root to take?

Edit:  [hide="Why, another solution?"]
Let $x = u - 39$.  Then

$\sqrt{58 - u} + \sqrt{58 + u} = 14$

(This arrangement can also be reached by using $x = -u - 39$).  Squaring,

$116 + 2 \sqrt{58^2 - u^2} = 196$
$58^2 - u^2 = 40^2$
$u = 42$

Then $x = \boxed{3, -81}$. [/hide][/quote]

do you mean $\pm 42$?

lol, and all of these solutions are basically the same thing, for the most part.


geometry
3D geometry
probability
pyramid
symmetry
AMC
AIME

What is the probability that a point chosen randomly from the interior of a cube is closer to the
cube’s center than it is to any of the cube’s eight vertices?

[hide="solution"]The internal diagonal=sqrt(a^2+b^2+c^2).So the area for which the point will be closer to the center =abc-[{a-sqrt(a^2+b^2+c^2)/2}{b-...}{c-..}].
Let this value be [b]X[/b].Then probab.=[b]X[/b]/[b]abc[/b].[/hide]

this is a cube so all sides are same. using abc is not necessary, and your expressions are unclear without LaTeX...

while im here i might work on a solution...
[hide="this is a long solution :D"]
ehh so split the cube into 8 "octants" (like quadrants)
any point is closest to the vertex that lies in the same octant as the point and it does not matter which vertex if it lies on a boundary.
For convenience say the edge is 2, since the volume of the portion closer to the center of the cube than any vertex is proportional to the volume of the cube.
We plot the cube's center on the origin and we consider the octant in the positive x, y, and z direction.
then we can find the volume of the portion closer to the origin than (1,1,1) in this octant then multiply by 8.

the distances from a point (x,y,z) to the origin and the point (1,1,1) are
$ \sqrt {x^2 \plus{} y^2 \plus{} z^2}$ and $ \sqrt {x^2 \plus{} y^2 \plus{} z^2 \minus{} 2x \minus{} 2y \minus{} 2z \plus{} 3}$ respectively.
we wish to set the former less than or equal to the latter and solve

$ \sqrt {x^2 \plus{} y^2 \plus{} z^2} \le \sqrt {x^2 \plus{} y^2 \plus{} z^2 \minus{} 2x \minus{} 2y \minus{} 2z \plus{} 3}$

squaring both sides is valid, since distance is positive,

$ x^2 \plus{} y^2 \plus{} z^2 \le x^2 \plus{} y^2 \plus{} z^2 \minus{} 2x \minus{} 2y \minus{} 2z \plus{} 3$

$ 0 \le \minus{} 2x \minus{} 2y \minus{} 2z \plus{} 3$

$ 2x \plus{} 2y \plus{} 2z \le 3$

note that the requirement for being in the first octant is that $ 0 \le x,y,z \le 1$

if the upper bound was not present, we would have a pyramid with altitude and legs of base all of length 1.5 and all mutually perpendicular.
which would mean it has an area of $ 1.5^3 (\frac16)$ or $ \frac {9}{16}$

but $ \frac13 ^3$ of it is above the plane $ z \equal{} 1$ and the same proportions are outside of the upper bounds for x and y, for a total of  $ \frac19$ of the pyramid aforementioned outside of the octant.

so really only $ \frac12$ is closer to the origin in this octant and 4 in the whole cube for a total proportion of $ \frac48 \equal{} \boxed{\frac12}$

unfortunately, this answer couldve been found using intuition :D
[/hide]

[b]Two non-computational arguments:[/b]

Somewhat shorter:
[hide="Symmetry"]Verify that the "good" regions of each octant are congruent. Now, consider one octant. This is a cube.

Let vertex A be the one that is the center of the large cube. Let A' be the diagonally opposite vertex, which is a vertex of the large cube. Obviously the closest vertex to any point in this particular octant.

It is easily seen by symmetry that there are an equal number of points closer to A as there are that are closer to A', so the probability is just 1/2.[/hide]

Somewhat more interesting:
[hide="Overlapping Cubes"]Let two 2x2x2 cubes overlap such that the center of each is a vertex of the other. Consider the octant that is the intersection of both the cubes. Note that, by definition, the region of this octant that is the "good" region of one cube is the "bad" region of the other cube, and vice versa. Since the two cubes are symmetric, their good and bad regions are congruent, and it follows that the good and bad regions are equal in volume. Hence, the probability is 1/2.[/hide]

The set of points which satisfy this - that is, the set of points which lie at least as close to the center of the cube as to any vertex - forms a particular geometric shape. This shape is a polyhedron. More specifically, it is a semi-regular (Archimedean) solid. That is, it is a polyhedron each of whose faces is a regular polygon (although not all the same polygon) and each vertex has the same number of edges and the same number of each kind of face meeting.

Can you identify this solid? How many faces does it have, and what polygons are its faces? How many edges, how many vertices?

[hide="Hint."]In Zuton Force's "overlapping cubes" argument, what does the boundary surface he's talking about look like?[/hide]

Here's a [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=79319]link to an AIME problem[/url] that is related to the above post. One of the solutions in that thread is basically a spoiler to this problem.

It's a construction that's worth memorizing -- it will help you better understand certain equivalent crystal lattice structures when you study chemistry.

[quote="Kent Merryfield"]Can you identify this solid? How many faces does it have, and what polygons are its faces? How many edges, how many vertices?
[/quote]

[hide]The polyhedron is composed of regular hexagons and squares (with side length $ \sqrt {2}$ for a $ 2\times 2\times 2$ cube). There are $ 8$ regular hexagons which each cuts a octant in half. Since each hexagon is next to $ 3$ squares and each square is next to $ 4$ hexagons, there are $ 8\cdot 3/4 \equal{} 6$ squares. Thus in total there are $ 14$ faces. Because each vertex in a hexagon is in two octants, there are $ 8\cdot 6/2 \equal{} 24$ vertices. At last, by Euler's Formula, we know there are $ 24 \plus{} 14 \minus{} 2 \equal{} 36$ edges.[/hide]

EDIT: it is under the name of "truncated octahedron" in this [url=http://en.wikipedia.org/wiki/Archimedean_solid#Classification]list[/url].

That is correct, timwu. Now, what about the equivalent question [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=214530]here?[/url]


Putnam
function
number theory
greatest common divisor
calculus
derivative
integration

Find all continuously differentiable functions $ f: \mathbb{R}\to\mathbb{R}$ such that for every rational number $ q,$ the number $ f(q)$ is rational and has the same denominator as $ q.$ (The denominator of a rational number $ q$ is the unique positive integer $ b$ such that $ q\equal{}a/b$ for some integer $ a$ with $ \gcd(a,b)\equal{}1.$) (Note: $ \gcd$ means greatest common divisor.)

Pick an $ x$, $ \epsilon$ and choose $ \delta$ so that $ |x\minus{}y| < \delta$ implies $ |f'(x)\minus{}f'(y)| < \epsilon$, then choose $ m$, $ n$ such that $ x\minus{}\delta < \frac{2m\minus{}1}{2^n} < x < \frac{2m\plus{}1}{2^n} < x\plus{}\delta$, by some theorem there exists $ \frac{2m\minus{}1}{2^n} < \zeta < \frac{2m\plus{}1}{2^n}$ such that $ \frac{f(\frac{2m\plus{}1}{2^n})\minus{}f(\frac{2m\minus{}1}{2^n})}{\frac{2m\plus{}1}{2^n}\minus{}\frac{2m\minus{}1}{2^n}} \equal{} f'(\zeta)$, from the condition on denominators we see that $ f'(\zeta)$ is an integer, and since it's within $ \epsilon$ of $ f'(x)$, $ f'(x)$ is within $ \epsilon$ of an integer for every $ \epsilon$, so $ f'(x)$ is always an integer.

$ f'$ is now a continuous function from the reals to the integers, so it must be constant, and $ f$ is linear with integer slope. Then you play around a little (look at $ f(\frac{0}{1})$, $ f(\frac{1}{f'(0)})$) to find that $ f(x) \equal{} x\plus{}n$ or $ f(x) \equal{} \minus{}x\plus{}n$ for some integer $ n$.

Consider some real number $ x$.  By sandwiching $ x$ inside a Farey sequence, you can find two sequences of rational numbers $ a_n/b_n$ and $ c_n/d_n$ converging to $ x$ from below and above respectively such that $ a_n d_n \minus{} b_n c_n \equal{} 1$.  But then:
\[ \frac{f(a_n/b_n)\minus{}f(c_n/d_n)}{a_n/b_n \minus{} c_n/d_n} \equal{} \frac{b_n f(a_n/b_n) d_n \minus{} b_n f(c_n/d_n) d_n}{a_n d_n \minus{} b_n c_n}\]
But $ f(a_n/b_n) b_n, d_n, f(c_n/d_n)d_n, b_n$ are integers and $ a_n d_n \minus{}b_n c_n\equal{}1$ so the above is an integer.  But as $ n\rightarrow\infty$ this approaches $ f'(x)$, which must hence be an integer.  This is true for all $ x$ and  $ f'(x)$ is continuous, so $ f'(x)$ is constant.  It follows that $ f(x)\equal{}u\plus{}bx$ and it may be seen that the only possibility is $ b\equal{}\pm 1$ and $ u\in\mathbb{Z}$.

this is somewhat of how i felt about the exam as a whole.  It is clear that the only possibilities were +- x + n for some int. n.  So even a meager math student like myself who couldn't materialize a proof, could understand what was going on.

My version went in a few more steps: first, let $ \frac pq$ in lowest terms be arbitrary and choose $ a,b$ with $ aq\minus{}pb\equal{}1$ (The gcd is a linear combination). We have $ \frac{np\plus{}a}{nq\plus{}b}\minus{}\frac{p}{q}\equal{}\frac1{q(nq\plus{}b)}$. As in Ralph's argument, the difference quotients are integers; since $ \frac{np\plus{}a}{nq\plus{}b}$ converges to $ \frac pq$, the sequence of difference quotients converges to $ f'\left(\frac pq\right)$, which must be an integer.
Now, we find $ f'$ elsewhere by its continuity; every irrational number is a limit of a sequence of rationals, and a limit of integers is integer-valued as before. The rest is the same.

This has the advantage of being less technical: we're using the definition of the derivative directly, and one close enough fraction is more widely known than the full Farey sequence/tree.

I really liked this problem! It had both number theory and analysis without having analytic number theory. That is pretty tricky. zeb's argument is far more slick than mine, mainly because I was being stupid and decided to prove f' maps rational to \pm 1 instead of just to integers, as I should have done. Fun problem, still!

It looks like we dot not need from the derivative to be a priori continious.

Indeed, for any real $ a$ take large positive integer $ n$ and find the unique $ k$ such that $ k/n\le a<(k\plus{}1)/n$, then $ f(k/n)\equal{}f(a)\plus{}(k/n\minus{}a)f'(a)\plus{}o(1/n)$, analogously for $ k\plus{}1$ instead $ k$. Take the difference and multiple by $ n$, we get $ f(a)\equal{}n(f((k\plus{}1)/n)\minus{}f(k/n))\plus{}o(1)$, and since $ n(f((k\plus{}1)/n)\minus{}f(k/n))$ is an integer, so is $ f(a)$. Hence $ f'$ is integer in any point, hence it is constant (if $ f$ is not linear function, then $ (f(b)\minus{}f(a))/(b\minus{}a)$ is not constant and therefore takes not-integral values, and by Lagrange theorem $ f'$ takes the same not-integral values).

f(x) = x+n and f(x) = −x+n

I'm in grade 11 and I got this one. If you didn't, you are retarded.

A list of answers is not a solution. A solution must prove that there aren't any other answers. No points.


vector
AMC
AIME
USA(J)MO
USAMO
linear algebra
AoPS Books

Does anyone know of a linear algebra book that deals with problem-solving like the AoPS books?  I am planning to learn some linear algebra after taking AP Calc BC (possibly from AoPS), but I do not know of any worthwile texts.  I actually have a linear algebra textbook from when my mom was in college, but it does not discuss much that would be useful for problem-solving (particularly annoying is the lack of difficult problems).

Thanks in Advance! :lol:

I don't know what level you are looking for, but there are some resources available [url=http://agmath.com/1952.html]here[/url] and [url=http://www.coolmath.com/algebra/index.html]here[/url].

powerofpi, thats basic algebra.

Linear algebra is after Calculus.

Yeah, I'm looking for a text on the linear algebra that deals with vectors, matrices, linear transformations, homomorphisms, eigenvalues, eigenvectors, linear maps, the Gram-Schmidt process... The type of algebra that is considered "higher-level" (but not necessarily more difficult) than most of the algebra involved on, say, the AIME and USAMO.  The reason I want to learn linear algebra is that I think it will help me to gain more intuitive and informed insights on olympiad problems (like last year's USAMO #6).  I don't know how to get those insights, though, if the linear algebra book I use doesn't focus on problem-solving.  Does anyone know of a linear algebra text that would be good for olympiad problem-solvers?  (Any that some of you have used...)


$ x^3\plus{}2x\plus{}1\equal{}2^n$

x,n is natural number

find x,n

I think this is easy, but I can't solve that

Already posted : [url]http://www.mathlinks.ro/viewtopic.php?p=860863#p860863[/url]

COMMENT: I don't think so that this one is so easy As I am informed maximum score achieved on this question in Serbian M.O.2007, where it appeared, was 2 out of 7.


[hide]-1's and 1's cancel up to the 2000th power, and $-1^{2001}$ = -1. [/hide]

[hide]everything with a power below 2001 has a pair so everything cancels out exept -1^2001 and that equals -1[/hide]

[hide]
Since 2000 is even, all numbers cancel out except $-1^{2001}$ so the answer is -1.[/hide]

[quote="h78reg"]the sum S=(-1)^1+(-1)^2+.....+(-1)^2001 is equal to what?[/quote]

[hide]
$\text{The problem cancels out except } -1^{2001}, \text{ which is -1}$ :)[/hide]

[quote="math92"]please use hide thing[/quote]

I've given up  :rotfl:

since 2000 is even, all the -1s and 1s cancel out so answer si -1^(2001)=-1[hide][/hide]

your hide is messed up.  try to edit your post and fix it. :)

[quote="risinglegend"]-1[/quote]

A 2-character post isn't going to help much. Please learn to post solutions, or don't post at all  :roll:

Please, two character hidden posts don't aid anyone in solving problems. I, and your peers, would much rather have you write out solutions to assist everyone's problem solving abilities.

Also, this topic is 9 months old and many good solutions have been provided already.

I think we've exhausted this topic. Can a mod lock it please?


[hide]The current triangle given has a base of 48. Drawing the altitude splits the base into two equal segments, 24 each. The altitude is found by the pythagorean theorem (or recognizing that it's a 8-15-17 triple), which is 45.

Now pretend that half the base was 45 instead, and the height is 24. Leaving the legs equal, the area doesn't change. The base of this triangle is 45(2)=90, so x=90. [/hide]

[quote="Treething"][hide="answer"]
-48
[/hide]

too lazy[/quote]

You cannot have a negative length for a side of a triangle...

[quote="ch1n353ch3s54a1l"]A triangle has sides measuring 51 cm, 51 cm, and 48 cm. A second triangle is drawn with sides 51 cm, 51 cm, and x cm, where x is a whole number other than 48. If the two triangles have equal areas, what is the value of x?[/quote][hide="answer"] since the height of the first triangle is 45 (sq. root of 2025), the area of the first triangle is 1080 (24*45). 1080 must be the area of the second triangle too. then, just change the height and the half base to get the same area, and the base is 45*2 or $\ 90$.[/hide]

[quote="Treething"][hide="answer"]
-48
[/hide]

too lazy[/quote]

how did you get that?  :huh:


calculus
integration
function
trigonometry
calculus computations

1)
What to do with the following integral:

int [1/(cos(x))^4]

I wrote sin^2 + cos^2 in the numerator and got

int [(sin^2)/(cos^4)] + tan(x)

But what to do with the   int [(sin^2)/(cos^4)]  ?

Did I even take the right step?

2)
My second question is about continuous functions

If we have a function

f(x) =  arctg (x/(x-1))  for  x<1 and
           a + arctg (x/(x-1))  for  x>1

At which constant a can the function f(x) be defined in the point x=1 so that f(x) becomes a continuous function?

I have absolutely no idea how to start solving this. If I understand the definition of continuous functions correctly than the left limit of arctg (x/(x-1))  when x aproaches 1 from the left should equal the right limit of a + arctg (x/(x-1))  when x proaches 1 from the right.

But that still does not help me much.

What should be done?

Thank you for all the help which will be given.

Ok. I tried that. But got stuck. I still can't treat that as (tan(x))^2 becouse there is a product in the integral. Rewriting (cos(x)^2) like 1-(sin(x))^2 also didn't help. What next?

:( I'm lost.  :)

what was the first step?
 1+{f(x)}^{2}
What is this. Why?

$\int \frac{dx}{\cos^{4}x}= \int \sec^{2}x \cdot \sec^{2}x \cdot dx = \int (1+\tan^{2}x) \cdot d \tan x = \dots$

I still don't know where you're all going with this but I solved in a different way. Usin the substitution t = tan(x/2) which then makes cos(x)= (1-t^2)/(1+t^2) and dx = (2/(1+t^2))dt works great. It is probably a longer way but still. You get a fraction which you then transform in a sum of parcial fractions and from there on it all runs like clockworks.

Anyone has any ideas for the second question (about continuous functions)?

As $x\to 1$ from the left (often written as $x\to 1-$), the fraction $\frac{x}{x-1}$ tends to $-\infty$, so its $\arctan$ approaches $-\pi/2$.

As $x\to 1$ from the right (often written as $x\to 1+$), the fraction $\frac{x}{x-1}$ tends to $+\infty$, so its $\arctan$ approaches $\pi/2$.

The limits are not the same, which is why you need that constant $a$.


linear algebra
matrix
vector
algebra
polynomial

Show that the matrix
\[ \mathsf{A} \equal{} \begin{pmatrix} 0 & 1 & 0 \\ \minus{}4 & 4 & 0 \\ \minus{}2 & 1 & 2\end{pmatrix}\]has characteristic equation $ (t \minus{} 2)^3 \equal{} 0$. Explain (without doing any further calculations) why $ \mathsf{A}$ is not diagonalizable.

I know how to get the characteristic equation; then you have to prove there aren't enough independent eigenvectors - how do you do this without calculating eigenvectors?

If A were diagonalizable then A would be similar to the matrix of its eigenvalues, which on this case would be 2I. But then there would exist a non-singular matrix $ P$ such that $ A \equal{} P(2I)P^{ \minus{} 1} \equal{} 2I$, and $ A \neq 2I$. Therefore, A is not diagonalizable.

I get that, but there are some calculations being done :P Could we argue instead that if the eigenvalue of algebraic multiplicity 3 has 3 linearly independent eigenvectors, they must span $ \mathbb{R}^3$, and therefore [i]any[/i] vector is an eigenvector?

Calculations? That was just to explain that anything diagonalizable to a multiple of the identity is already that multiple of the identity. Carcul's argument is exactly what you're being asked for.

This is actually the same as Carcul's argument, but I'll make the vocabulary a little different. I'll talk about algebraic multiplicity.

The algebraic multiplicity of an eigenvalue $ \lambda$ is the exponent of the factor $ (t\minus{}\lambda)^k$ as a factor of the characteristic polynomial.

The geometric multiplicity of $ \lambda$ is the dimension of the eigenspace - that is, the dimension of the null space of $ A\minus{}\lambda I.$

The geometric multiplicity of an eigenvalue is always less than or equal to the algebraic multiplicity. (And always at least one, or else it's not an eigenvalue at all.)

Assuming that we can completely factor its characteristic polynomial into linear factors, a matrix is diagonalizable if and only if the geometric and algebraic multiplicities are equal for each eigenvalue.

The characteristic polynomial is $ (t\minus{}2)^3.$ That gives us an algebraic multiplicity of $ 3$ for the eigenvalue $ 2.$

But the only way for that to have a geometric multiplicity of $ 3$ would (by the rank-nullity theorem) be for $ A\minus{}2I$ to have rank zero - and the only rank zero matrix is the zero matrix. We can see at a glance that $ A\minus{}2I$ is not zero. Hence, the geometric multiplicity of $ 2$ as an eigenvalue is less than $ 3.$ It has to be $ 1$ or $ 2.$ (It happens to be $ 2$ but we don't really need to know that.) Since the geometric multiplicity does not match the algebraic multiplicity, the matrix is not diagonalizable.

Here's a true-false question from a test I gave last week:

If $ \mathbf{B}$ is $ 8\times 8$ and $ \mathbf{B}\minus{}9\mathbf{I}$ has rank $ 5,$ then $ (\lambda\minus{}9)^3$ is a factor of the characteristic polynomial of $ \mathbf{B}.$ (True or false?)

Thanks this was really helpful  :)

[quote="Kent Merryfield"]Here's a true-false question from a test I gave last week:

If $ \mathbf{B}$ is $ 8\times 8$ and $ \mathbf{B} \minus{} 9\mathbf{I}$ has rank $ 5,$ then $ (\lambda \minus{} 9)^3$ is a factor of the characteristic polynomial of $ \mathbf{B}.$ (True or false?)[/quote]

And this is true isn't it? If $ \mathbf{B} \minus{} 9\mathbf{I}$ has rank $ 5$, then its nullity is $ 3$ and the eigenvector $ \lambda \equal{} 9$ has geometric multiplicity $ 3$, requiring its algebraic multiplicity to be (edit: at least) $ 3$ as well.

Correct. The statement is true. The algebraic multiplicity of $ 9$ is at least $ 3$ - it might be more than that, but the statement would still be true.


[quote="madhuri"]let S be any set .show that the operation * defined by a*b=a is associative.is it commutative?give reasons for your answer???[/quote]
[hide=""Understand associative and commutative---rest of the problem is easy""]
Associative: For any $a,b,c\in S$, $(a*b)*c=a*(b*c)$
Commutative: For any $a,b\in S$, $a*b=b*a$

So, is * associative? Use the given definition:
$(a*b)*c=a*c=a$ and $a*(b*c)=a*b=a$

So, is * commutative? Again, use the given definition:
$a*b=a$ and $b*a=b$
[/hide]

[b]
Can you please give a gerneral introduction and a more detailed definition of $associative$ and $commutative$?[/b]


function
trigonometry
algebra
polynomial
algebra proposed

Given a real number $a$ and $f_1, f_2, ..., f_n$ additive functions from reals to reals such that $f_1(x)f_2(x)...f_n(x) = ax^n$ for all real number $x$. Prove that there exists $b$, which is a real number, and $i$, which is in the set {${{1,2,..,n}}$} such that $f_i(x) = bx$ for all real number $x$

I sort of remember posting this in the College Playground. I think Myth gave a solution. It was used in a Romanian TST (1997, I think).

Anyway, here's a proof (I believe it's very similar to what Myth did):

Assume for simplicity that $f_i(1)=1,\ \forall i$ (just divide each $f_i$ by $f_i(1)$). Then $f(p)=p,\ \forall p\in\mathbb Q$, so we get, for any $x\in\mathbb R$ and any $p\in\mathbb Q,\ \prod_{i=1}^n(p+f_i(x))=(p+x)^n$. Sine this polynomial identity holds for infinitely many reals $p$ (the rationals), it must hold for all of them, so the polynomials $P(t)=\prod_{i=1}(t+f_i(x))$ and $Q(t)=(t+x)^n$ are equal, meaning that for all real $x$ we have $f_i(x)=x$.

I think much stronger versions of this problem should hold though. I don't know what happens in the following case, for instance: assume that our condition is now that $g(x)=\prod_{i=1}^nf_i(x)$ does not change sign on $(0,\infty)$.

i already have done the prob before it was the same idea i think!


This was posted very recently:
[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=31344]www.mathlinks.ro/Forum/viewtopic.php?t=31344[/url]

[quote="keira_khtn"]For [tex]a,b,c[/tex] are positive reals.Find maximal value of function:
[tex]F(x,y,z)=4xyz-(a^2x+b^2y+c^2z)[/tex].
with [tex]x,y,z[/tex] are positive reals satisfing condition:
[tex]x+y+z=a+b+c[/tex].[/quote]

maybe 0

see shortlist !!!!! :)  :)  :)  :)  :)

[quote="siuhochung"]can you see the link above? The answer is abc.[/quote]

Sorry I had a mistake

[quote="siuhochung"][quote="zhaobin"][quote="siuhochung"]can you see the link above? The answer is abc.[/quote]
sorry,can you show me when will the maximum hold?[/quote]

a=b=c=x=y=z[/quote]
I mean a,b,c have been fixed first.
another words,they are constant,maybe don't equal to each other

[quote="zhaobin"][/quote][quote="siuhochung"][quote="zhaobin"][quote="siuhochung"]can you see the link above? The answer is abc.[/quote]
sorry,can you show me when will the maximum hold?[/quote]

a=b=c=x=y=z[/quote][quote="zhaobin"]
I mean a,b,c have been fixed first.
another words,they are constant,maybe don't equal to each other[/quote]
take x=a, y=b, z=c. When a,b,c are not all equal, then equality case cannot hold.

and then what will the maximum be??
for example let$a=1,b=1,c=2$


geometry trapezoid symmetry counting distinguishability ratio rotation

Since I know a lot of us here have some cool problems to share, post them here!  Feel free to discuss solutions to them as well.

I'll start things off with an easy little geometry problem (not sure how original this is... it's impossible to come up with original euclidean questions nowadays).

Problem 1)

A cyclic quadrilateral ABCD and points P, Q, R, and S are chosen such that the following statements are true:

- P on segment AB, Q on segment BC, R on segment CD, and S on segment DA.
- AP=AS=CR=CQ.
- PQ is parallel to RS.
- Angles APS + CRQ = BPQ + DRS.

Prove that:
a) area(BPSD) = area(BQRD)
b) 1/9 < angles (SPQ*PQR)/(QRS*RSP) < 9

(Edited for clarification!  I hope this makes a bit more sense now!)

You know, there are forums for these things...

Yes, but I want a thread where just us Canadians can share some problems.  It's one thing to pose problems to strangers... it's a totally different thing to stump people that you know... it's so much more fun that way.

I was thinking of making a problem chain... where the person who solves my problem gets to post the next one, and the person who solves that one gets to post the next one, and so on... but I was afraid that not enough problems would get posted.  It makes it a lot more fun than just doing Olymon and Olympiad questions all the time.

So far, only 1 person has got this (Jenn Park).

Nobody else has any problems for me to try?   :o

[quote="lightrhee"]This is a problem I came up with. It was last year.

n people are randomly sent to one dimentional world. They each have a walkietalkie so that they can talk to each other. Show a strategy to make all of them meet at a same place.

It turns out to be an very easy problem(Janos solved it).[/quote]
Did anyone solve it? It's an easy problem!

Elyot, for your first problem, we can angle chase and prove that $PQRS$ is cyclic, from which it follows that it is an iscocelles trapezoid, and $\angle A=\angle C= \pi/2$. Part a) follows by symmetry, and part B holds since $\angle PSR = \angle QRS \leq {3 \over 2}\pi$, while $\angle SPQ = \angle RQP \geq {1 \over 2}\pi$.

For a) of your second problem, instead of two ants turning around when they meet, think of the two ants walking through each other and continuing. These two events are indistinguishable since the ants are not distinguishable. Thus, the maximum time is n+1, with an ant at position 0 facing the other end.

For b), we can use the same idea. there are ${n+1 \choose k}2^k$ possible arrangements overall. Let $t$ be the maximum time needed to walk off the stick from the beginning (We employ the continuing rule instead of turning around rule in collisions). It can be seen that the number of configurations with $t=i$ is
\[3\sum_{j=0}^{k-1}{2i-n-1 \choose j}{2n-2i+1 \choose k-1-j}2^j\]
From which it follows that the desired average is:
\[3\sum_{i=0}^{n}{\sum_{j=0}^{k-1}{{2i-n-1 \choose j}{2n-2i+1 \choose k-1-j}2^j}} \over {n+1 \choose k}2^k\]

I don't know how to simplify this. Also, I probably made some mistakes with indexes and such so this might be all wrong.

Unfortunately, I don't have a problem at this time for you guys to solve. I will post it when i have.

[quote="Elyot"]Here's my solution to the walkie talkie problem...
The first guy is the master so he stands still... the other n-1 guys follow the following instructions:
walk forward 1
walk backward 2
walk forward 3
walk backward 4
walk forward 5...
etc etc...

Eventually they will all meet the master, regardless of their positions or which direction they start off facing, after which they stay there and wait for the others.  I think that works, although I doubt it's optimal.

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

Here's another problem that yours reminded me of.  Part a is a version of a screwy CS problem... Part b is my own, but I doubt it's that original...

Please ask if you need clarification on anything.

There is a stick of length n cm, and k ants on it (n and k are integers, 1<=k<=n+1).  You get to position each of the k ants at a position somewhere along the stick... for simplicity you can assume that the ants start out at positions an integer distance from the end.  You also get to point the ants in a direction when you place them (toward one end of the stick or the other).  No two ants can be placed at the same location.

When you're done placing all the ants, they all start walking in whatever direction they're facing at a speed of 1 cm/second.  When two ants bump into each other, they both turn around and start walking in the opposite direction.  When ants come to the edge of the stick, they walk off the end of it.

a) Given n and k, what is the maximum time, in seconds, until the ants all walk off the end, when you can place them however you like?  Express the answer in terms of n and k.

b) Given all possible placements of ants on the stick, what is the average time, in seconds, until all of the ants fall off, expressed in terms of n and k?  This is actually pretty hard.  I'd like to see a nice solution to this one.  The first person to solve it gets a cookie from me at seminar![/quote]

Actually, I have seen the problem on problem section of Math Horizons(April 2004).

Good job with the geometry problem... my exact solution.  Probably easy for you though ;)

You picked up on the ants quite nicely... the first time I saw this problem, I struggled for a long time until I realized that the ants just pass through each other... it's a bit of a brain-twister.

Part b of the ants problem... yea it's pretty ugly.  As I said before, a nice solution earns you a cookie!

[quote="lightrhee"]

Actually, I have seen the problem on problem section of Math Horizons(April 2004).[/quote]

Yea it's a pretty classic one... but it's nice.  I love giving this one to kids about grade 9 and then showing them the solution.

Here's another problem... I'm gonna start numbering them:

Problem 4)
Find all n such that there exists a point P so that square ABCD has distances AP, BP, CP, DP in the ratio 6n:sqrt(50)*n:8n:5n+5

It's interesting but there is a non-ugly solution if you look hard enough.

[quote="pengshi"]Rotate $P$ with angle of rotation $\pi \over 2$ and with centre $B$, to $P'$. Then $PP'=10n$, and $\angle PCP'$ is $\pi \over 2$. This implies that $APC$ are colinear. Thus, by symmetry, $5n+5=\sqrt{50} n$, so $n=\sqrt{2}+1$.[/quote]

Shiz, you're fast.  Again, my exact solution... I'll have to come up with something really hard to stump you now... or perhaps you could post a problem and try to stump the rest of us.

Hi, guys, I am new here. I knew many of you guys are competing on international level of Olympiad math, which is way beyond me. But still I am eager to share some of my problems that I made up through exercises and some real life oberservation.  The question I will post maybe very easy for you guys,  but  I  couldn't entirely solve it up to this point. so if you can post the solution, it will be great! :)
The problem is a combinatorics, (I am pretty sure it is not orignial, but I haven't find it on the web. And I did think up the problem.) it  also related with a realife problem my teacher ask me to help him to figure out. (which I couldn't). I may post the problem later.
Here it goes:

Arrange number 1-n in a row in the following ways: 1 is not the 1st number; 2 is not the 2nd number; .....; n is not the n th  number.
How many such permutations are there? Can you also provide gerneral formula?
(I already find the recursive formula,  but it seems to me impossible to figure out the the general formula from it.)

Just google the phrase 'derangements...'.  The solution is a trivial application of the inclusion-exclusion principle, if you know it.

Use inclusion-exclusinn. The answer would be
\[\frac1{0!}-\frac1{1!}+\frac1{2!}-\frac1{3!}+\frac1{4!}-\frac1{5!}+\cdots \pm \frac1{n!}\]
which becomes $\frac1e$ as n becomes bigger.

[quote="lightrhee"]Last year's IMO members came up with this(we coundn't solve it). Prove that a 3-D space can be partitioned into non-simple knots.
We were trying to solve it for circles, instead of knots(I don't remember whether we solved it or not).[/quote]

O crap... don't even go there.  That is way too crazy pure math for me.  I don't even know where to begin on something like that...

If we call that one #5, and #6 the derangements problem, here's #7 by me again... I think most of you will be able to solve it without much difficulty

7) Call an n-ring a list of n>=3 real numbers k1, k2, k3, ..., kn such that k1=k2*k3, k2=k3*k4, k3=k4*k5, ... k(n-2)=k(n-1)*kn, k(n-1)=kn*k1, kn=k1*k2.  Let f(n) = the sum of all the elements in all unique possible n-rings.  Let g(x) = Sigma(i=3 to x, f(i)).
Find g(2005).

[quote="lightrhee"]Last year's IMO members came up with this(we coundn't solve it). Prove that a 3-D space can be partitioned into non-simple knots.
We were trying to solve it for circles, instead of knots(I don't remember whether we solved it or not).[/quote]

Actually, there is a very simple solution for the "partitional 3 space into circle" in a book. It's in the book they gave us during the waterloo seminar last year, called "mathematically puzzles, a connoisseur's collection".

Here is a problem that stumped everyone, even Jacob. (He claims to have a solution now). In a plane, can we have uncountably many non-intersecting shapes that are topologically equivalent to the letter "Y"?

For example, if we did letter "I", the answer would be yes, because, we just have many lines next to each other. If we did the letter "B" then the answer would be no, since we can pick a rational point in each of the "holes" and uniquely define a B. Since $Q^2$ is a countable set, there can only be countably many "B"'s.

What does "topologically equivalent to the letter Y" mean?  Isn't Y the same as I (ie it has no holes?) or do the shapes need to have 3 concave vertices or something?

My terminology was bad, but what I mean is,  a shape (consisted of curved lines, so no area), that has 3 branches, like a Y.

Sorry to intrude here, guys, but both of these have been discussed before on the forum:

the one with the topological $Y$'s:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=topological&t=6468[/url]

and the one with the partition of $\mathbb R^3$ into disjoint circles:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=circles&t=32829[/url]

Just thought you might be interested. They're really cool problems, if you ask me :).

9. (another Elyot original, not very hard at all)

Let the UBERCUBE be a k-dimensional hypercube in k-space that's made from n^k unit cubes glued together; ie it is an n by n by n by n ... (k times) hypercube.  Assume n must be a positive integer, and k is an integer > 2.  The ubercube is immersed in chocolate sauce so that all exposed sides become "chocolatey".  Next, any unit cube with chocolate sauce on it is pulled off the ubercube and placed in a pile.  Then, what's left of the ubercube is immersed in chocolate sauce again, and any unit cube with chocolate sauce on it is again pulled off and placed into the same pile.  The remaining portion of the ubercube (comprised of cubes totally void of chocolate) is chopped up into unit cubes, and they are placed in a second pile.  Call these cubes "vanilla".

As an example, if n=6 and k=4, there would be 1296 total pieces, 1040 of which would have been ripped off after the first dipping of chocolate sauce, 240 of which would have been ripped off after the second dipping of chocolate sauce, and only 16 of which would remain untouched after both dippings.  So the number of chocolatey cubes is 1280, and the number of vanilla cubes is 16.

If, after both dippings of chocolate, there are 65535 times as many chocolatey pieces as there are vanilla ones, determine all possible values of k.

Knowing some of you guys, it will likely take you a shorter period of time to solve this than it took me to post it.  Have fun.

Edit: At the request of my girlfriend, the word "paint" has been replaced by the word "chocolate sauce", "painted" by "chocolatey", and "unpainted" by "vanilla".

[quote="Elyot"]9. (another Elyot original, not very hard at all)

Let the UBERCUBE be a k-dimensional hypercube in k-space that's made from n^k unit cubes glued together; ie it is an n by n by n by n ... (k times) hypercube.  Assume n must be a positive integer, and k is an integer > 2.  The ubercube is immersed in chocolate sauce so that all exposed sides become "chocolatey".  Next, any unit cube with chocolate sauce on it is pulled off the ubercube and placed in a pile.  Then, what's left of the ubercube is immersed in chocolate sauce again, and any unit cube with chocolate sauce on it is again pulled off and placed into the same pile.  The remaining portion of the ubercube (comprised of cubes totally void of chocolate) is chopped up into unit cubes, and they are placed in a second pile.  Call these cubes "vanilla".

As an example, if n=6 and k=4, there would be 1296 total pieces, 1040 of which would have been ripped off after the first dipping of chocolate sauce, 240 of which would have been ripped off after the second dipping of chocolate sauce, and only 16 of which would remain untouched after both dippings.  So the number of chocolatey cubes is 1280, and the number of vanilla cubes is 16.

If, after both coats of paint, there are 65535 times as many chocolatey pieces as there are vanilla ones, determine all possible values of k.

Knowing some of you guys, it will likely take you a shorter period of time to solve this than it took me to post it.  Have fun.

Edit: At the request of my girlfriend, the word "paint" has been replaced by the word "chocolate sauce", "painted" by "chocolatey", and "unpainted" by "vanilla".[/quote]
It is an easy problem. After the two dipping, you left with k-dimemtional hypercube with length of n-4, so $65535(n-4)^k+(n-4)^k=n^k$, which is $65536(n-4)^k=n^k$. It follows that $(\frac{n}{n-4})^k=2^{16}$. If $\frac{n}{n-4}$ is not an integer, it does not work, so n-4|n and n-4|4. Therefore, possible n is 5, 6, or 8. We can easily prove that 5 and 6 doesn't work. The answer is n=8 and k=16.

Who is your girlfriend anyway? :D

My girlfriend's name is Annie Wraight... she likes math but she's not that much into contest-type stuff.  She did like this problem though.  If you go to my mp3 web page ([url=http://www.mp3unsigned.com/showband.asp?id=1315]www.mp3unsigned.com/showband.asp?id=1315[/url]) and click on gallery, then you can see a pic of her.

Good job solving #9.  Very easy, but kinda elegant.

Here's the follow-up question... it's harder, but still not too bad.
#9b)

Let the "UBERECTANGLE" be a 2k-dimensional rectangular prism made from (n^k)*(m^k) unit cubes.  Assume m and n are positive integers, m<=n, and k is an integer > 1.  The uberectangle is dipped in chocolate only once, and again, all pieces with any chocolate on them are deemed "chocolatey", and the rest of the pieces are deemed "vanilla".

Let C be the number of chocolatey pieces and V be the number of vanilla pieces.  The upper-dimensional chocolatier has ordered that the number of chocolatey pieces be an integer multiple of the number of vanilla pieces.  Let this multiple be a positive integer X (such that X=C/V).  The chocolatier has also insisted that vanilla pieces be rare, but not too rare such that they are impossible to come across, so he has restricted that 600<X<1500.

Determine all possible solutions (m,n,k) that satisfy this condition.  I think there are less than 10 solutions.

[quote="Elyot"]Here's my solution to the walkie talkie problem...
The first guy is the master so he stands still... the other n-1 guys follow the following instructions:
walk forward 1
walk backward 2
walk forward 3
walk backward 4
walk forward 5...
etc etc...

Eventually they will all meet the master, regardless of their positions or which direction they start off facing, after which they stay there and wait for the others.  I think that works, although I doubt it's optimal.

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

Problem 3)

Here's another problem that yours reminded me of.  Part a is a version of a screwy CS problem... Part b is my own, but I doubt it's that original...

Please ask if you need clarification on anything.

There is a stick of length n cm, and k ants on it (n and k are integers, 1<=k<=n+1).  You get to position each of the k ants at a position somewhere along the stick... for simplicity you can assume that the ants start out at positions an integer distance from the end.  You also get to point the ants in a direction when you place them (toward one end of the stick or the other).  No two ants can be placed at the same location.

When you're done placing all the ants, they all start walking in whatever direction they're facing at a speed of 1 cm/second.  When two ants bump into each other, they both turn around and start walking in the opposite direction.  When ants come to the edge of the stick, they walk off the end of it.

a) Given n and k, what is the maximum time, in seconds, until the ants all walk off the end, when you can place them however you like?  Express the answer in terms of n and k.

b) Given all possible placements of ants on the stick, what is the average time, in seconds, until all of the ants fall off, expressed in terms of n and k?  This is actually pretty hard.  I'd like to see a nice solution to this one.  The first person to solve it gets a cookie from me at seminar![/quote]

okay whoever first thought of the ants problem for computer science should just die (:P).  it is part of the waterloo's ACM team selection problem from last year.  if you've seen it before, you'll get it in 3 minutes.  or if you havent seen it before like me and who is slow it made just enough difference to knock me one place off the regional teams.  :(

[quote="pengshi"]Why can't there be infinitely many solutions, since the condition becomes
\[{1\over 1501} < {(n-2)^k(m-2)^k \over n^km^k} < {1\over 601}\]
Then you can choose some huge numbers for $n$ and $m$, and gradually increase $k$. This way, the expression will go from almost 1, and decrease by a very small factor each time, ensuring that they will eventually enter the range. Please tell me if I'm missing something very obvious.[/quote]

The thing you're missing is that I said x must be an integer.

[quote="lightrhee"]Elyot, you really like multidimemtional problem(I hate them). This problem seems to be too much work, while approach to the answer is obvious. Therefore, I am not going to solve the problem. :roll:[/quote]

Actually, there's a really quick way to get all the solutions by considering the parity of n... otherwise... yes I suppose you can just try a ton of cases.

I thought that problem was kinda interesting.  Multidimensional geometry is crazy enough that I like it.  I'm just bored of the typical algebra/geometry/number theory/inequality/combinatorics problems.  Instead, I'm trying to come up with something cool.  Maybe I'll post a more interesting multi-dimensional problem later.

To keep this thread alive, I have a easy plane geometry problem that I made.

Consider a triangle $ABC$ with incentre $I$, inradius $r$. Construct the perpendiculars to $AI$, $BI$, and $CI$, at $A$, $B$ and $C$ respectively. Let these lines meet at $A'$, $B'$ and $C'$. Let the circumradius of $A'B'C'$ be $R'$, prove that $4r \leq R'$.

[quote="pengshi"] Construct the perpendiculars to $AI$, $BI$, and $CI$, at $A$, $B$ and $C$ respectively. [/quote]
I don't get how you construct such perpendiculars. To $AI$ at $A$? I'm confused.

[quote="Singular"]lightrhee:  consider all lines perpendicular to AI.  There is exactly one line L from this family with the property that $A \in L$.  Draw this line.[/quote]
Oh. I get it now. :)

[quote="pengshi"]Consider a triangle $ABC$ with incentre $I$, inradius $r$. Construct the perpendiculars to $AI$, $BI$, and $CI$, at $A$, $B$ and $C$ respectively. Let these lines meet at $A'$, $B'$ and $C'$. Let the circumradius of $A'B'C'$ be $R'$, prove that $4r \leq R'$.[/quote]

Through some angle chasing we see that $I$ is the orthocentre of $A'B'C'$ (this is actually very easy to see the other way around, that the orthocentre of a triangle is the incentre of its orthic triangle). Let $R$ be the circumradius of $ABC$. By Euler, $2r \leq R$. By since the circumcircle of $ABC$ is the ninepoint circle of $A'B'C'$, we have $R' = 2R \geq 4r$, and we are done.

Nice solution! I just want to mention for those that don't know these theorems about ninepoint circles, that you can arrive at a solution by dialation with centre $I$ and factor 1/2. Then, show through angle chasing that the dialation image of $A'$, $B'$, $C'$, call them $A''$, $B''$, $C''$ , are in the circumcircle of $ABC$. In fact $A''$ is the midpoint of the arc between $B$ and $C$.


what is the order of stability
of allylic tertiary and benyllic carbocation?
the order in morrison is
tertiary >Allylic$ \approx$ Benzyllic
but what will u write if this appears in a question papers et in india ??

I dont exactly know what my Prof said but he said he disagrees on this count with Morrison .
Srini would have nved the notes by now. Ask him he's a thorough nv.

My book gives the same order of stability.

I have already posted on this forum an order of stability of carbocations (Pardesi, it was on one of your posts, can you find it?), and according to it, tertiary > benzylic > allylic.

[url=http://www.mathlinks.ro/viewtopic.php?search_id=840500212&t=161878]here[/url] is the post
the problem is not with the order i am sure about the one posted by u
but indian author think really big of resonance  :D
anything thas resonance or even the smell of it turns out to be exceptionally stable for them for get about w.r.t to what  :P

Maybe its bcos ' Resonance ' had 881 selections or whatever in last years IIT JEE  :P

the order in morisson is rite n dat is what should be written in question papers. i had the same doubt and i checked out the net.i dont remember where but ive come across  relative rates of nucleophilic substitution for the three compounds under similar conditions and tert butyl chloride was the most reactive. but i think it is mainly due to hyperconjugation and so if tertiary carbocation ahs lesser no. of alpha hydrogens the others cations will be more stable


What university r u guys going to next year? What course/program?

[quote="SM4RT"]I'm probably going to UW Engineering..[/quote]
Same here, probably mechatronics.

I am thinking about going into Acturial Science. What do you guys think- is it a good field/bad field, etc.?

I wanted to go into Actuarial Science for a while... not anymore though. Really for first year it doesn't matter. I guess the most you can do right now is look over the course descriptions and see if they sound interesting: [url]http://www.ucalendar.uwaterloo.ca/COURSE/course-ACTSC.html#ACTSC200S[/url]

[quote="D.P.L"]Im thinking engineering cos its kind of easy...[/quote]

lol i dunno about that...  :P

i am definitely going to phyics. theoretical i mean. cuz it's so fun

[quote="D.P.L"]Im thinking engineering cos its kind of [b]easy[/b]...[/quote]

 :roll:

For all you young'ins, university of waterloo is good fun, they math pretty hard at the place, so it feels like a home away from home.

Oh, the engineers are crazy. But thats true anywhere.

I hope they do... My calculus/geo.discrete teacher has yet to fill out my teacher recommendation  :mad:.

k ya thats a relief a little..because I need atleast a fall back if i dont get into engineering..

[quote="SM4RT"]So yeah I applied for engineering and computer science as my main program choices through the OUAC site. It turns out computer science one is due three weeks after you receive confirmation :o and well its been a few more days more then three weeks..do you think Waterloo will still accept my application..[/quote]

huh
?!

what do you mean due? what is due 3 weeks after you receive confirmation?

the site says AIF forms are due on March 1..

lol....meeee still in grade 10...im gonna start worrying about applying for college next year... :P ...me wanna go into actuarial science...any recommendations for college?????...and yea...does it matter wut region u live in?

college?
you don't wanna go to university?

and i heard acturial science is good pay, but very stressful

yes...apparently i meant university...college is just a shorter word for it...with only 2 syllables instead of 4... :rotfl:  :|  :|

contests supposed to have no effect on the admission itself. they do help in early admissions though. what waterloo does is look at ur avg, ur extracurricular activities and contest scores. u can earn up to 12% bonus. well, if u have like 95% avg with top 50 in contests, why bother trying to see if ur good enough? lol

if ur have say like <95% avg, ok in contests, ok extracurricular, they rather make u wait til may. no worries! i got mine back in may with money along with it. it's all good!

[quote="ssj4152"][quote="nneonneo"][quote="ssj4152"]Waterloo looks at your contest scores for admission.
don't you remember when you apply, they ask for your COMC, Fermat, Hypatia and Euclid scores.
I think if u wrote euclid in grade 11, and did well, they'll accept you early. i got accepted in january, 2 weeks after i applied.[/quote]
I wrote Euclid in grade 11, got 90+ (can't remember exact score OTOH), and I'm still waiting :([/quote]

What's your average. my average is in the low 90s, and i got 85 on euclid in grade 11. and which program did you apply
whats your class rank, and do you have any extracurricular activities?[/quote]
Mid 90s (high 90s if we discount the 2 lowest english marks). Class rank -- unknown (probably near the top, if I had to hazard a guess), applied for math and compsci programs, and I have Debate and a few other extracurricular things.

nneonneo: k i'm sure you shouldve got in by now..unless if ur english mark is <75..then they might wait...because i got into comp sci at waterloo like a long time ago (feb) and ur average + contest marks are higher then mine so i dont see y you didnt get in, you clearly deserve to over me lol..

ya check quest...that makes no sense that you didnt get in...unless if you dont have like 6 grade 12 courses (cuz i had like 7, since i did a few last year).. but ya check quest u soo should be in by now..

Hmm, I just checked Quest, and it seems they may be waiting for my transcript from the University, even though I told them that they did not need to wait for it. Meh, I will just have to send it in after the final mark shows up in a week or so.

o right u dont live in Ontario..u'll get in anyway

wow, applying to waterloo seems like a marathon. out here in bc, all they care about is your marks so everybody just memorizes answers from old provincials and get 95+ avg and <60 on euclid and get into university. and i cant memorize so i cant match up!!!


If $ A \equal{} 20^{\circ}$ and $ B \equal{} 25^{\circ}$, then the value of $ (1 \plus{} \tan A)(1 \plus{} \tan B)$ is

$ \textbf{(A)} \sqrt3 \qquad \textbf{(B)}\ 2 \qquad \textbf{(C)}\ 1 \plus{} \sqrt2 \qquad \textbf{(D)}\ 2(\tan A \plus{} \tan B)$
$ \textbf{(E)}\ \text{ none of these}$

Note that $ \tan{x\plus{}y} \equal{} \frac {\tan x \plus{}\tan y}{1\minus{}\tan x \tan y}$. Expanding the expression gives $ 1\plus{}\tan {20} \plus{} \tan {25} \plus{} \tan {20} \tan {25}$. $ \tan (20\plus{}25) \equal{} \tan {45} \equal{} 1 \equal{} \frac {\tan {20} \plus{} \tan {25}}{1\minus{}\tan {20} \tan {25}}$. Thus $ 1 \minus{} \tan {20}\tan{25} \equal{} \tan {20} \plus{} \tan {25}$. Substitution gives the expression a value of 2.