pigeonhole principle
linear algebra
matrix
inequalities
combinatorics solved
combinatorics

My idea is very stupid and simple, but I bet someone can find a more direct and nice solution. Take a graph G in which you connect two non-disjoint subsets. Suppose G doesn't have triangles. We prove it has at least 51 vertices of degree t most 50. Otherwise, we can find 51 vertices of degree at least 51. Take A one of them. Then A must be connecte to a vertex of degree at least 51. Let it be B. Then it's trivial to show that we can find C such that C is joined to A and B, contradiction. Thus, we can find A_1,...,A-50 vertices of degree at most 50. Then A_1 is disjoint from at least 50 subsets, so it has at most $\frac{n}{51} $ elements. The same for A_2,...,A_50 and it's done.

In a different topic, someone asked why the following is true:

[quote="harazi"] A_1 is disjoint from at least 50 subsets, so it has at most $\frac{n}{51}$ elements.[/quote]

In fact, the reason is simple: Since the vertex $A_{1}$ of the graph $G$ has degree at most 50, there are at most 50 subsets $A_{i}$ (with $i\neq 1$) which are not disjoint from $A_{1}$. Thus, the remaining at least 50 subsets $A_{i}$ (with $i\neq 1$) are disjoint from $A_{1}$.
So the set $A_{1}$ is disjoint from at least 50 of the subsets $A_{i}$. Thus, $A_{1}$ is disjoint from the union of these 50 subsets. But, according to the problem, the union of 50 subsets $A_{i}$ has more than $\frac{50}{51}n$ elements. Hence, since the set $A_{1}$ is disjoint from this union, it has less than $n-\frac{50}{51}n=\frac{1}{51}n$ elements.

By the way: nice problem, Harazi!

  Darij

My idea is slightly different.  Define the graph $ G$ like Harazi's solution.  Suppose that $ G$ is triangle-free.

I will prove that all vertices in $ G$ are of degree at most $ 50$.  If this is false, then there is a vertex $ v$ adjacent to at least $ 51$ other vertices: $ v_{1},v_{2},\dots,v_{51}$.  Consider the sets represented by $ v_{2},v_{3},\dots,v_{51}$.  The union of these sets has more than $ 50n/51$ elements.  Hence, by the Pigeonhole Principle, one of them, say $ v_{51}$ has more than $ n/51$ elements.  Consider $ v_{1},v_{2},\dots,v_{50}$.  The union of them has more than $ 50n/51$ elements.  Therefore, some vertex in $ v_{1},v_{2},\dots,v_{50}$ must be adjacent to $ v_{51}$; WLOG let it be $ v_{1}$.  Thus, $ vv_{1}v_{51}$ is then a triangle, contradicting our assumption.

The rest is actually the same.  In fact, there are at least (not necessarily disjoint) $ 18$ triangles, if I'm not mistaken.  Can you please check my argument?

Suppose we have only at most $ 17$ triangles: $ a_{1}b_{1}c_{1}$, $ a_{2}b_{2}c_{2}$, ..., $ a_{k}b_{k}c_{k}$, where $ k\leq 17$.  Hence, there are at least $ 101\minus{}3\cdot17 \equal{} 50$ vertices not in these triangles.  Let's call these vertices "free vertices."  Similar to the previous part, a free vertex $ v$ can have at most degree $ 50$ (otherwise, there must be another triangle).  Therefore, at least $ 50$ vertices are not connected to $ v$ and thus, $ |v| < n/51$.  This is true for all free vertices.    Hence, the union of their corresponding sets has less than $ 50n/51$ elements, a contradiction.

The bounds are incredibly weak. This question was used at a UK selection camp, and I produced the following solution, which disregards $ A_{101}$ entirely.

Let $ S_1 \equal{} A_1\cup A_2 \cup ... \cup A_{25}$ and $ S_2,S_3,S_4$ three more unions of 25 $ A_i$ such that all 100 are covered.
Let $ T_{i,j} \equal{} X \backslash (S_i \cup S_j)$.
The question tells us that $ |T_{i,j}| < \frac {|X|}{51}$, so the union of all $ T_{i,j}$ has size less than $ \frac {6|X|}{51}$, so there are lots of elements of $ X$ belonging to no $ T_{i,j}$. But each of these must be in at least three $ S_i$, and therefore be common to at least three $ A_i$, so there exist three $ A_i$ containing such a point, and thus with nonempty pairwise intersections.

The weakness of the bounds actually leads to a similar argument involving only 64 $ A_i$. Joseph Myers then managed to show (using Freddie Manners', another UK student's, method) that with the strong condition of needing a common point to 3 different $ A_i$, that 59 $ A_i$ is the maximum number of $ A_i$ required for such a point to exist, and that this bound is sharp (there's a counterexample for 58).

Not sure if this is the same thing

Consider a graph with sets as verticies and common elements as edges. Now since each element is contained in at most 2 sets each edge corresponds to a element. Now take 50 elements and the other 51. The other 51 must only have 1/51 *n of the edges and so must the 50 (or else just add one) amongst themselves yet the 50 has 50/51n. Thus at least 49/51n of the edges are connecting the sets now divide the 51 into 25 and 26 and the 50 into 25 and 25 and note that each of the 49/51n connect one of the 4 possible pairings but that means one of the pairings has 49/51n/4 =><=

By this reasoning we need only 5/6n for this to work :starwars:

Hi all. Sorry for digging this very old post back up, but I think there's one method that hasn't been covered by the above discussion, which is pretty simple (I think) but powerful enough to give the sharp bound mentioned by Ilthigore 2 posts up (3 years ago?!). I'm guessing that this is probably the method that Freddie Manners used as well.

Consider an incidence matrix with columns labelled $A_1, A_2, \ldots, A_{101}$ and rows labelled $x_1, x_2, \ldots, x_n$, where the $x_j$ are the elements of set $X$. Mark a '1' in column $A_i$ and row $x_j$ if $x_j \in A_i$, and '0' otherwise.

Assume on the contrary that there does not exist three distinct $A_i$ with all three pairwise intersections nonempty. Now we count the number of 50-tuples in the rows of the table which contain all '0's. So for example a row with 50 '0's count as 1 50-tuple, and a row with 51 '0's count as 51 50-tuples. On one hand, since each row contains at most two '1's, each row contains at least 99 '0's. Hence the number of 50-tuples is at least $\binom{99}{50}n$.

On the other hand, for each choice of 50 $A_i$, their union contains at least $\frac{50}{51}n$ elements of $X$. Hence if we consider the columns corresponding to these 50 $A_i$, there are at most $\frac{1}{51}n$ rows whose intersection with the 50 columns consists of all '0's. Thus by summing over all choices of 50 $A_i$, the number of row '0' 50-tuples is less than $\frac{1}{51}\binom{101}{50}n$.

Comparing these two bounds, we get

\[\binom{99}{50} > \frac{1}{51}\binom{101}{50} \iff \frac{1}{51}\frac{101 \cdot 100}{(101 - 50) \cdot (100 - 50)} > 1\].

The last inequality is obviously false. In fact, it is still false if we replaced all occurences of 101 by 59. Hence our initial assumption was false and we are done.

@hello123: Please be more precise. I think you are confusing sets and elements, but I am not sure because your posting is too brief.

@angyansheng: A little correction:

[quote="angyansheng"]On the other hand, for each choice of 50 $A_i$, their union contains at least[/quote]

more than

[quote="angyansheng"] $\frac{50}{51}n$ elements of $X$. Hence if we consider the columns corresponding to these 50 $A_i$, there are at most[/quote]

less than

[quote="angyansheng"] $\frac{1}{51}n$ rows whose intersection with the 50 columns consists of all '0's. Thus by summing over all choices of 50 $A_i$, the number of row '0' 50-tuples is less than $\frac{1}{51}\binom{101}{50}n$.

Comparing these two bounds, we get

\[\binom{99}{50} > \frac{1}{51}\binom{101}{50} \iff \frac{1}{51}\frac{101 \cdot 100}{(101 - 50) \cdot (100 - 50)} > 1\].
[/quote]

The first $>$ should be an $<$.

i think this works
[hide]assume the contrary.
Now, suppose that A101 shares a common element with 51 or more subsets.  WLOG suppose that they are A1, A2, A3, ..., A51, ...  We know that if any of A1 and A2, A1 and A3, ..., A50 and A51 share a common element, our assumption has been contradicted.  That means that A1, ..., A51 are all mutually exclusive.  Now, suppose b1 is the number of elements in A1, and so on.  Then b1+...+b51<=n, so clearly, one of b1+...+b50, b1+...+b49+b51, b1+...+b48+b50+b51, ..., b2+...+b51 <= 50n/51.  That cannot be according to the question, since the number of elements in the union of any 50 subsets > 50n/51.
Now we know that no subset shares a common element with 51 or more subsets.  That means every subset does not share any elements with at least 50 subsets.  Now, we see that since the union of any 50 subsets contains more than 50n/51 elements, there exists a subset (say A1) that contains more than n/51 elements.  Now, since it does not share any elements with 50 other subsets (say A2 to A51), those 50 cannot have a total of 50n/51 elements, since the number of elements in the union of A1 to A51 would then be greater than n/51+50n/51=n, but that is a clear violation of the constraints given.
Okay now we are done.[/hide]

[quote=Valentin Vornicu]Let $n\geq 2$ be a positive integer, and $X$ a set with $n$ elements. Let $A_{1},A_{2},\ldots,A_{101}$ be subsets of $X$ such that the union of any $50$ of them has more than $\frac{50}{51}n$ elements.

Prove that among these $101$ subsets there exist $3$ subsets such that any two of them have a common element.[/quote]

[b][color=#f00]Claim:[/color][/b] Atleast $50$ sets have greater than $\frac{n}{51}$ elements.
[b][color=#f00]Proof:[/color][/b] Trival by PHP.
Obviously two of them have an intersection or else $51=101$, contradiction so some two them $A_X=B$ and $A_Y=C$ have an non empty intersection.
So FTSOC assume that for all $A_i$ we must have the intersection of $B$ and $C$ empty then there are $101-2=99$ possibilities for $A_i$ and obviously atleast 50 of them (by PHP) have an empty intersection with $B$ and by by the claim each have $\frac{n}{51}$ elements a total of $n$ elements when we sum up or implying all the other sets are empty, contradiction.

It is known that $X$ is a set with $102$ elements. Suppose $A_1, A_2, ..., A_{101}$ is a set of subset of $X$ such that the sum of every $50$ of them has more than $100$ elements. Prove that there are $1 \le i <j <k \le 101$ such that $A_i \cap A_j$, $A_i \cap A_k $and $A_k \cap A_j$ are not empty.
[url=https://artofproblemsolving.com/community/c4h2685439p23297220]Indonesia 2014 [/url]


Find all values of $m, n$ and $p$ with $p^{n}+144 = m^{2}$ where $m$ and $n$ are positive integers and $p$ is a prime.


Prove that If $ \square{AEML}$, $ \square{BGNF}$, $ \square{CIOH}$ are circumscriptible, $ \square{DKPJ}$ is also circumscriptible.

Thanks in advance for interests  :blush:

Hello, I think this is pretty natural.

Let $X,Y,Z$ be the incenters of $AEML,BGNF,CIOH$ and denote their inradii by $r,s,t$. Also define $W=QZ\cap RX$.

Clearly we need to show that that $W$ is the incenter of $DKPJ$, i.e. $W$ is equidistant from all four sides of $DKPJ$, or since $QX/QY=r/s$, $RZ/RY=t/s$, etc.
\[t\frac{QW}{QZ}=r\frac{RW}{RX}\Longleftrightarrow\frac{QX/QY}{RZ/RY}=\frac{QW/QZ}{RW/RX}\Longleftrightarrow\frac{[QXZ]}{[RXZ]}=\frac{[QWY]}{[RWY]}.\]But this follows from the fact that $Q$ and $R$ are harmonic conjugates with respect to $XZ\cap QR$ and $YW\cap QR$, so we're done.


Two circles touch internally at A. The tangent at a point P on the small circle cuts the larger circle at Q and R. Prove that AP bisects angle RAQ.

call O the center of the beggest circle and K of the smaller. Call H the projection of A on QR, we have $ \angle QAH \equal{} \angle RAO$ and $ \angle KAO \equal{} \angle KPA \equal{} \angle PAH$ so $ \angle QAP \equal{} \angle RAP$.

As it seems I underestimated that problem. Thank you for the valuable opinions.

Dear Mathlinkers,
let S be the second intersection of AP with the big circle and Ts the tangent to this circle at S.
We have, Ts // QR (by homothetie); in consequence, the triangle SQR is S-isosceles and we are done.
Sincerely
Jean-Louis


[quote="Knuth's_check"]I was just wandering if the Introduction to number theory class would be held again sometime during 2006/2007. I really wanted to enroll in it, although I would have to miss a copious amount of class due to traveling etc.[/quote]

At the earliest, probably next summer.


We will solve an expansive problem of two problems in this topic and http://www.mathlinks.ro/viewtopic.php?t=288700 :
Given two lines $ d$ and $ d'$, a cirlce $ (O)$ which cuts d at two points A,B. Draw a second circle satisfying simultaneously conditions:
i/ Orthogonal to the icrlce $ (O)$
ii/ Its center lies on the line $ d$
iii/ Tangent to the line $ d'$
It's night in my country now :sleeping:, perhaps I will post the solution tomorrow  :play_ball:

[quote="mr.danh"]
Expansive problem:
Given two lines $ d$ and $ d'$, a cirlce $ (O)$ which cuts $ d$ at two points $ A$,$ B$ ($ A$ is closer to $ d$ than $ B$) . Draw a second circle satisfying simultaneously conditions:
i/ Orthogonal to the icrlce $ (O)$
ii/ Its center lies on the line $ d$
iii/ Tangent to the line $ d'$
[/quote]
[hide="My construction"]See at the picture 1
Let H be the orthogonal projection of B on d'. The circle of diameter BH cuts the circle (B;BA) at F. Let E be the orthogonal projection of F on BH. Denote C be the midpoint of BE. Draw the circle (C) of diameter BE, it meets the segment AC at D. Draw the circle (A;AD). Construct two tangent lines from B to the circle (A), they cut the line d' at two points P,Q. Then, the incircle of triangle BPQ is just the wanted circle which satisfying three conditions of the problem.
[/hide]

In the problem of this topic, denote AB be the common chord of two given circle. By the above method, we can draw the circle orthogonal to one of given circles, tangent to the given line such that its center lies on the line AB. Then, this circle is just the wanted circle of jrrbc's problem.
See at the picture 2.

[quote="jrrbc"]If you have a geogebra html file with this construction and with steps activated, please put it online.

 :([/quote]
Sorry, I don't know how to use Geogebra. But I think my construction is rather clearly. In addtion, I added some illustratable figures. Please read in more details or point out unclear parts in the construction.  :)
Beast regards.

it's a genius construction,  please could you show all steps

i can't see the d and d' just begin the construction

 :(

[b]Problem:[/b]
Given two circles $ (O_1)$, $ (O_2)$ and a line $ d'$. Draw a third circle orthogonal to $ (O_1)$, $ (O_2)$ and tangent to the line $ d'$.

[b]Construction:[/b]
Let A,B be the intersections of $ (O_1)$ and $ (O_2)$. Draw the line $ d$ through A and B.
Let H be the orthogonal projection of B on d'. The circle of diameter BH cuts the circle (B;BA) at F.
Let E be the orthogonal projection of F on BH.
Denote C be the midpoint of BE. Draw the circle (C) of diameter BE, it meets the segment AC at D.
Draw the circle (A;AD). Construct two tangent lines from B to the circle (A), they cut the line d' at two points P,Q.
Then, the incircle of triangle BPQ is just the wanted circle.


Evaluate $ \arctan \sqrt {5 \minus{} 2\sqrt {5}}$ with steps shown.
No calculators or table of trig values allowed.

$ \tan^2 x \equal{} 5\minus{}2\sqrt{5}$
$ \sec^2 x \equal{} 6\minus{}2\sqrt{5} \equal{} (\sqrt{5}\minus{}1)^2$
$ \sec x \equal{} \sqrt{5}\minus{}1$
$ \cos x \equal{} \frac{1}{\sqrt{5}\minus{}1} \equal{} \frac{\sqrt{5}\plus{}1}{4}$

which I believe is $ \cos (\pi/5)$, so our answer is $ \boxed{\frac{\pi}{5}}$

facis, that's exactly what I had except the last line. Is there any other way to jump from $ \cos x$ to $ x$ without taking a guess?

you kindof have to know some (not a ton) of trig values.  This particular one I proved here:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=202083[/url]

Knowing this with the 30, 45, and 60 degrees and formulas, you can find just about every answer you are likely to be expected to find by hand.  The $ \sqrt{5}$ in the original problem is a dead giveaway that our answer is something like $ 36$, $ 72$, $ 54$, $ 108$, or $ 144$ degrees

[quote="leoxnlin"]Well, you'll always have to "take a guess", I mean, there is no mathematical rigor or lack thereof in the process. If it turned out that $ \cos x \equal{} 1/2$, you'd still have to "take a guess" and say that $ x \equal{} \pi / 3$.[/quote]
I disagree with this example; one can find that $ x\equal{}\pi/3$ from $ \cos x\equal{}1/2$ without any memorization of the value of $ \cos(\pi/3)$ by doubling the side with length $ 1$ of the $ 1\minus{}2\minus{}\sqrt3$ triangle to transform it into an equilateral triangle (with three sides of measure 2 each), from which it follows simply that $ x\equal{}\pi/3$.


hello

i am ahaving a apromlem understandin this question... please help by solving it STEP BY STEP.... A SIMILAR QUESTION MIGHT BE IN THE TEST AND I NEED HELP THANKS

how many solutions are there to the eaquation x1 + x2 + x3 + x4 + x5 + x6 = 29
WHERE XI,, I = 1,2,3,4,5,6 IS NONNEGATIVE INTEGER SUCH THAT

a) xi> 1 for i=1,2,3,4,5,6?
b) x1 >=1, x2 >=2, x3 >=3, x4 >=4, x5 >5 and x6>=6?
c)c<= 5?
d) x1 < 8 and x2 >8?

[hide]Think of this problem as dividing 29 indistinguishable objects into 6 groups.  Put the objects in a row, and split them into 6 groups by putting 5 dividers in between the objects.

For the first question, since each group gets at least one object, we can only put at most one divider between each pair of consecutive objects.  There are 28 possible places for our dividers, and we must fill 5 of them.  The answer is $\binom{28}{5}$.

The other questions can be solved using the same idea, but they require a little more thought.[/hide]

[quote="Art of Owna"]How is a 28C5, isnt it say xi is greater than 1 not greater or equal to 1 wouldnt it be 22C5[/quote]
You're right, I misread the problem.


trigonometry
calculus
derivative
calculus computations

Find the general solution of $ \frac {dy}{dx} \equal{} \frac {y \minus{} x}{y^2 \plus{} x^2}$.

Can someone please help. Thank you very much. :P

[quote="Carcul"]Switch to polar coordinates.[/quote]

And we have

$ \frac{dr}{d\varphi}\equal{}r\frac{r\cos\varphi\plus{}\sin\varphi(\sin\varphi\minus{}\cos\varphi)}{\cos\varphi(\sin\varphi\minus{}\cos\varphi)\minus{}r\sin\varphi}$...

For a homogeneous equation like this, there's a standard procedure. Let $ y\equal{}xu.$ Then $ \frac{dy}{dx}\equal{}u\plus{}x\frac{du}{dx}.$ We have

$ u\plus{}x\frac{du}{dx}\equal{}\frac{xu\minus{}x}{x^2u^2\plus{}x^2}$

$ x^2\frac{du}{dx}\plus{}xu\equal{}\frac{u\minus{}1}{u^2\plus{}1}.$

That isn't particularly attractive. Let's flip it over and try it the other way: $ x\equal{}vy.$

$ \frac{dx}{dy}\equal{}\frac{y^2\plus{}x^2}{y\minus{}x}$

$ v\plus{}y\frac{dv}{dy}\equal{}\frac{y^2\plus{}y^2v^2}{y\minus{}yv}$

$ \frac{dv}{dy}\equal{}\frac{1\plus{}v^2}{1\minus{}v}\minus{}\frac{v}{y}$

At this point: not linear, not separable, doesn't seem to belong to any of the other special cases (like Bernoulli or Riccati). I don't see a method.

Any way a power series solution is obtainable?  Surely in principle I can multiply two power series for the denominator and again in principle, divide two series for the quotient.  Take the derivative of the series for the left side, equate coefficients and bam, done deal . . . or no?


counting distinguishability function probability

There are 3 distinguishable men and 10 indistinguishable doughnuts. How many ways are there to distribute the doughnuts among the 3 men, if no man can have more than 4 doughnuts?

Well here it goes .
Consider that each man receives xi doughnuts i=1,2,3 .
Therefore x1 + x2 + x3 =10
Then no. of ways = coeff of $ x^{10}$ in the expansion of $ ((x^0 \plus{} x^1 \plus{} ..... \plus{} x^4))^3$
So find it  :)

I am not sure, but me thinks that I it's $ \binom{9}{2}$.
I think this is donuts and dividers problem..

hmm, DK, your's includes (8,1,1), which isn't valid, and a lot of other ones that don't work

[quote="madness"]How? Whats your proof?[/quote]
Dunno... I think I am going to change my answer..
12 spaces and you can only put dividers at 11 places.. $ \binom{12}{11}$dunno..

Forget it and just brute force it..

(4,4,2)- can be arranged in 6 different ways.

(3,3,4)- can be arranged in 6 different ways.

So 12??

No, generating functions yields $ 6$

DK, there aren't 6 ways to arrange (4,4,3), because the 4 occurs twice

[hide="hint"]
I assume a man could have no doughnuts?

The number of ways to distribute $ n$ indistinguishable balls into $ k$ distinguishable boxes is $ \binom{n \plus{} k \minus{} 1}{k \minus{} 1} \equal{} \binom{10 \plus{} 3 \minus{} 1}{3 \minus{} 1} \equal{} \binom{12}{2} \equal{} 66$. The number of cases where exactly one man has 4+ doughnuts is $ 3(\binom{6 \plus{} 2 \minus{} 1}{2 \minus{} 1} \plus{} \binom{5 \plus{} 2 \minus{} 1}{2 \minus{} 1} \plus{} \binom{4 \plus{} 2 \minus{} 1}{2 \minus{} 1} \plus{} \binom{3 \plus{} 2 \minus{} 1}{2 \minus{} 1}$  $ \plus{} \binom{2 \plus{} 2 \minus{} 1}{2 \minus{} 1} \plus{} \binom{1 \plus{} 2 \minus{} 1}{2 \minus{} 1} \plus{} \binom{0 \plus{} 2 \minus{} 1}{2 \minus{} 1})$
$ \equal{} 3(\binom{7}{1} \plus{} \binom{6}{1} \plus{} \binom{5}{1} \plus{} \binom{4}{1} \plus{} \binom{3}{1} \plus{} \binom{2}{1} \plus{} \binom{1}{1})$
$ \equal{} 3(7 \plus{} 6 \plus{} 5 \plus{} 4 \plus{} 3 \plus{} 2 \plus{} 1) \equal{} 3(28) \equal{} 84$ (we multiply by 3 because the men are distinguishable). We can get a similar (but slightly more complex and even more case-worky) figure for two men, and obviously not all three men can have 4+. We add those and take the complement.

I would do it myself, but it requires long casework and it's late....
[/hide]

Why are you trying to sound so technical when a kindergartner can list the 6 options in under 2 minutes?
EDIT:
My apologies to Temperal.
OK. Maybe this is a classroom problem, where you are expected you to practice the use of a certain ingenious technique taught in class. In that case, I have no idea what was expected.

Thanks for the replies.

Madness, can you please explain that a bit more in-depth? I don't quite understand it.

Thank you for your reply, Temperal. However, is there a general formula (like $ \binom{n \plus{} k \minus{} 1}{k \minus{} 1}$ for this kind of problem?

[quote="Zhero"]
Thank you for your reply, Temperal. However, is there a general formula (like $ \binom{n \plus{} k \minus{} 1}{k \minus{} 1}$ for this kind of problem?[/quote]

Yes; it's often a good tool, but sometimes requires a bit of boring casework with it.

Would a moderator please delete KMST's spam?

With limited possiblities brute force is actually the best method

Balls and urns is plausible but you have to subtract all the cases where men have 5,6,7,8,9,10 donuts, then multiply by 3 (3 men) and then subtract overcounts

temperal
sry i am kind confused by the forumla
is it the number of ways to distribute [i]n [/i]indistinguishable balls into [i]k [/i][b]distinguishable [/b]boxes, or is it the number of ways to distribute [i]n [/i]indistinguishable balls into [i]k [/i][b]indistinguishable [/b]boxes

It would seem that from a set of 10 donuts we can take subsets from them.  The donuts may be selected 1 at a time or 2 at a time...  up to 4 at a time. Taking them 1 at a time ie $ \binom {10}{1}\;\;$ We may also take 2 at a time $ \binom{10}{2}\;\;$ or 3 at a time up to 4 at a time.  No subset of donuts may be made greater than 4.

Adding up all the possible subsets of donuts represents the total number of sets from which 3 men may make selections ie
$ \binom {10}{1} \plus{} \binom {10}{2} \plus{} \binom {10}{3} \plus{} \binom {10}{4} \equal{} 385 \;$  ways to make subsets of donuts for the 3 men to select from.  If each man may NOT select a donut then add 3 or 388 ways.

From a set of 385 (or 388) 3 men may make selections.  The question then becomes how many subsets of 3 can be made from a set 385 (or 388) ?

$ \binom {385}{3} \equal{} 9437120\;\;$

Sounds reasonable to me...?

[hide]The generating function is $ (1\plus{}x\plus{}x^{2}\plus{}x^{3}\plus{}x^{4})^{3}\equal{}(1\plus{}2x\plus{}3x^{2}\plus{}4x^{3}\plus{}5x^{4}\plus{}4x^{5}\plus{}3x^{6}\plus{}2x^{7}\plus{}x^{8})(1\plus{}x\plus{}x^{2}\plus{}x^{3}\plus{}x^{4})$.

The coefficient of $ x^{10}$ is thus $ 3\plus{}2\plus{}1\equal{}\boxed{6}$.[/hide]

Well obviously the answer is 6.
Let the men be denoted by m1,m2,m3.
The only valid solns are the permutations of 4 4 2 and 3 3 4 doughnuts resp (as the men are different and doughnuts are the same)
= 3+3 = 6

Obviously generate fns as I had done earlier. CatalystOfNostalgia had earlier expanded the generated fn.
In genl. if there are m men and d doughnuts and each men cannot have more than k doughnuts then
the Answer is:
Coefficient of $ x^d$ in the expansion of $ (x^0\plus{}x^1\plus{}x^2............x^k)^m$

[quote="Temperal"][quote="Zhero"]Thanks for all the replies. Madness, yes, the answer is pretty clearly 6; but what if, instead, I had 5 men, 20 doughnuts, and no man can have more than 16?

vector2, I am completely lost by your explanation. What do you mean by "take the donuts one at a time?"

Temperal, could you please explain how you arrived at the number of ways there are to distribute more than 4 doughnuts to exactly one man?[/quote]
We consider one man having 4 doughnuts, then 5,, etc., and apply the formula I gave earlier.

I didn't think of the generating functions way, which is clearly much easier.[/quote]

Not 4, it says no more than 4, but you can still have 4dounuts so its

Total number of ways for any men can have any amounts of donuts - 3 (number of ways in which 1 man has 5 donuts + number of ways 6 donuts + 7donuts + 8 donuts + 9 donuts + 10donuts) + 3

because there are 3 overlaps (550,055,505)
multiply by 3 for 3men.

[quote="Zhero"]
vector2, I am completely lost by your explanation. What do you mean by "take the donuts one at a time?"
[/quote]

Perhaps I don't understand the question, but the problem sounds like fundamental "counting" theory to me.
[url]http://en.wikipedia.org/wiki/Combination[/url]    is a good short article.

Part 1:
If I have 10 donuts, How many arrangments (sets) of 1 donut are possible? $ \binom {10} {1} \equal{} 10$
If I have 10 donuts, How many arrangments (sets) of 2 donuts are possible? $ \binom {10} {2} \equal{} 45$
If I have 10 donuts, How many arrangments (sets) of 3 donuts are possible? $ \binom {10} {3} \equal{} 120$
If I have 10 donuts, How many arrangments (sets) of 4 donuts are possible? $ \binom {10} {4} \equal{} 210$
$ 10 \plus{} 45 \plus{} 120 \plus{} 210 \equal{} 385$ possible arrangments of donuts.

Part 2
Once we know how many possible combinations of donuts the 3 men can select from. It is the same calculation to determine how many ways 3 men can select 1 of those sets from a set 385.

$ \binom {385} {3} \equal{} 9437120$  Which I hope is the right answer?

If the 3 men have the option of not selecting a donut, then we have to add those additional 3 possiblitities to the count.
IE 388  in lieu of 385.

$ \binom {388} {3} \equal{} 9660036$

(my calculator has a nCr( ) function to do the math)  Hope I haven't steered ya wrong.

But all the doughnuts are the same so the probability of taking any valid no. of doughnuts is the same

vector2, keep in mind that the doughnuts are indistinguishable. That should reduce your answer by A LOT.

[quote="madness"]Obviously generate fns as I had done earlier. CatalystOfNostalgia had earlier expanded the generated fn.
In genl. if there are m men and d doughnuts and each men cannot have more than k doughnuts then
the Answer is:
Coefficient of $ x^d$ in the expansion of $ (x^0 \plus{} x^1 \plus{} x^2............x^k)^m$[/quote]

I don't know much about generating functions besides their definition, so how do you derive this formula?  :maybe:

Each man has one way to get 0 donuts, one way to to get 1 donuts... all the way up to k donuts. Since there are m men, the whole generating function is $ (1\plus{}x\plus{}x^2\plus{}\cdots\plus{}x^k)^m$. This includes all possible numbers of donuts that could be distributed. However, since there are $ d$ donuts, we want the coefficient of the $ x^d$ term.

[quote="Zhero"]vector2, in part 2, I think you are severely overcounting. We are only restricted to the solutions in which the arrangements of donuts equal 10. For instance, your solution counts the distribution in which each man receives one donut.
[/quote]

Then perhaps I've steered you in the wrong direction. Maybe I've provided the answer to the wrong problem...  I should have realized "distributing the donuts" means distributing ALL the donuts.

[quote="Zhero"]vector2, in part 2, I think you are severely overcounting. We are only restricted to the solutions in which the arrangements of donuts equal 10. For instance, your solution counts the distribution in which each man receives one donut.

Also, I really don't know much about generating functions. Sorry. If anyone can explain them to me (or tell me where an explanation is), I'd be much obliged.[/quote]
Meet the Wiki: [url]http://www.artofproblemsolving.com/Wiki/index.php/Generating_functions[/url]


[img]http://i25.tinypic.com/2cnxvdk.jpg[/img]

how do u find the maximum velocity?

I'm not really well-versed in waves but whenver you have a function that gives position, which I believe you have, you take the derivative to find its velocity.  Then to find the maximum velocity, you take the derivative of velocity, set it to zero, solve for the value, then plug it in.


real analysis
calculus
calculus computations

why do they have a convolution process in the solution?

[img]http://i33.tinypic.com/nz2bv4.jpg[/img]

Never mind it, it's just product, not convolution.


This comes from a finance-related question, where to solve the question requires finding out the sum to infinity of kr/(r+1)^k (r=interest rates is given). Please help me and also explain each of the steps to solve the sum to infinity?

(Sorry I just can't figure out how to use latex)

Do you mean $\sum_{k=1}^{\infty}{\frac{kr}{(r+1)^k}}$?

EDIT: reddevilz beat me to it ;)

Sorry, I didn't see his post before. I was referring to the initial question.

[hide]
$\sum_{k=1}^{\infty}{\frac{kr}{(r+1)^k} = \frac{r}{r+1}+\frac{2r}{(r+1)^2}+\frac{3r}{(r+1)^3}+...}$

We split this into infinite infinite geometric series (no, that is not a typo):

$\frac{r}{r+1}+\frac{r}{(r+1)^2}+...$
$\frac{r}{(r+1)^2}+\frac{r}{(r+1)^3}+...$
$\frac{r}{(r+1)^3}+\frac{r}{(r+1)^4}+...$
...

Evaluating each of these we have

$\frac{r}{r+1}+\frac{r}{(r+1)^2}+... = \frac{\frac{r}{r+1}}{1-\frac{1}{r+1}} = 1$
$\frac{r}{(r+1)^2}+\frac{r}{(r+1)^3}+... = \frac{\frac{r}{(r+1)^2}}{1-\frac{1}{r+1}} = \frac{1}{r+1}$
$\frac{r}{(r+1)^3}+\frac{r}{(r+1)^4}+... = \frac{\frac{r}{(r+1)^3}}{1-\frac{1}{r+1}} = \frac{1}{(r+1)^2}$
...

So we have yet another infinite geometric series to evaluate:

$1+\frac{1}{r+1}+\frac{1}{(r+1)^2}+... = \frac{1}{1-\frac{1}{r+1}} = \frac{r+1}{r}$.

I hope I did that right.[/hide]

[quote="Priapus"]isn't that the same thing?[/quote]
look at the time they were posted... they are within one minute of each other.... ;)

OK, I think I got the solution. Look at the edit I put in my previous post.

I agree. Only this time, you beat me to the solution... by 16 hours... ;) (I was about to post solution...)

Must say i am impressed with the infinate infinate geometric series!

[quote="Campbell"]I checked the answer and it's right! Thanks to all of you (especially paladin8 and xxreddevilzxx) for your help! Man, you guys are the best![/quote]

if i were u i would give props to paladin8. he was the first one to solve it. (although i was there to post the solution, only to see paladin beat me to it, by some 16 hours.) ;)


A gardener plans to build a fence to enclose a square garden plot. The perimeter of the plot is 96 feet, and he sets posts at the corners of the square. The posts along the sides are set 6 feet apart. How many posts will he use to fence the entire plot?

Since a square has a "start" and an "end", all we have to do is $ \frac{96}{6}$ to get our answer of $ \boxed{16}$


linear algebra
matrix
superior algebra
superior algebra solved

assume that $A=[a_{ij}]_{i,j=1}^{n}$ which $a_{ij}=1$iff $i|j$ and $a_{ij}=0$ otherwise, find $A^{-1}$.

Your matrix has 1 on the main diagonal and 0 bellow it, so the determinant is 1.

oh!! excuse me for my silly question :blush:  :blush:  (it's due to being busy these days ) btw I has edited it.

Let $B=(b_{i,j})_{i,j=\overline{1,n}}$ such as $B\cdot A=I_n$.

Let $\mu:\mathbb{N}\to \mathbb{Z}$ defined by:
$\mu(1)=1$;
$\mu(n)=0$ if n is not square free;
$\mu(p)=-1$ if p is prime;
$\mu(a\cdot b)=\mu(a)\cdot \mu(b)$ if gcd(a,b)=1.

$\mu$ is called the Mobius function.
We have the following formula: Let $f,g:\mathbb{N}\to\mathbb{C}$ such as $\sum_{d|n}f(d)=g(n)$. Then $f(n)=\sum_{d|n}\mu(\frac{n}d)\cdot g(d)$. This is called the Mobius inversion formula.

Then $\sum_{k=1}^n b_{i,k}a_{k,j}=\delta_{i,j}$.
This is equivalent to $\sum_{k|j} b_{i,k}=\delta_{i,j}$.

$\delta_{i,j}=\{\begin{array}{cc}1,\ if\ i=j\\ 0,\ if\ i\neq j\end{array}$.

Using Moebius's inversion formula, we get
$b_{i,j}=\sum_{d|j}\mu(\frac{j}d)\delta_{i,d}$ [b](1)[/b]

We see from (1) that if $i\nmid j$ then $\delta_{i,d}=0\ \forall \ d|j$ so $b_{i,j}=0$.
If $i|j$, then $\delta_{i,d}\neq 0\Leftrightarrow i=d$, so $b_{i,j}=\mu(\frac{j}i)$.

Overall:
$b_{i,j}=\{\begin{array}{cc}0,\ if\ i\nmid j\\ \mu(\frac{j}i),\ if\ i|j\end{array}$.


Here is the list of schools competing in the MAML state math meet on Friday.

[b]LARGE SCHOOLS[/b]
Amherst Regional High School
Acton-Boxborough Regional High School
Algonquin Regional High School
Andover High School
Belmont High School
Boston Latin School
Brookline High School
Canton High School (medium school competing as large)
Concord-Carlisle Regional High School
Dartmouth High School
Falmouth High School
Lexington High School
Lincoln-Sudbury Regional High School
Minnechaug Regional High School
Shrewsbury High School
Westford Academy

[b]MEDIUM SCHOOLS[/b]
Bedford High School
Burlington High School
Deerfield Academy
Dighton-Rehoboth Regional High School
East Longmeadow High School
Hudson High School
Longmeadow High School
Marblehead High School
Nashoba Regional High School
Plymouth North High School
Sharon High School
St. John's High School
Wayland High School
Westborough High School
Weston High School

[b]SMALL SCHOOLS[/b]
Austin Preparatory School
Bancroft School
Bromfield School
Dover-Sherborn High School
Hopedale Junior-Senior High School
Joseph Case High School
Leicester High School
Lynnfield High School
The MacDuffie School
Maimonides School
Manchester-Essex Regional High School
Pingree School
Thayer Academy
Worcester Academy

Teams will be arriving at Shrewsbury High School at 1:15 on Friday.  Directions:  http://www.wocomal.org/directions/maml.html

Best of luck to everyone!

Rick Yanco
Worcester Academy

How were schools supposed to hear about this?  I am a student at Lincoln-Sudbury and our math team advisor did not know about this meet until I saw this topic last week.  As a result of the limited notice, we were unable to field a team.

your advisor should have known about this

Well, if it makes you feel any better, it was my error.  The final list I received was " large: acton boxboro,algonquin reg., amherst reg., andover, belmont, boston latin, brookline,canton, concord carlisle, dartmouth, falmouth, lexington, minnechaug, shrewsbury, westford acad., : medium : bedford, deerfield acad., dighton rehoboth, hudson, marblehead, nashoba, plymouth north, sharon, st. john's, wayland, westboro, weston, : small : austin prep, bancroft, bromfield, case, dover sherborn, hopedale, lynnfield, macduffie, maimonides, manchester-essex, pingree, thayer acad., worcester acad."

I went through my database to select all of the schools that were going (my database generates the directions page at http://www.wocomal.org/directions/maml.html) and apparently I checked LSRHS by mistake, because you can confirm that it isn't in the email I received.  The database generated the original list above.

Actually Leicester is in the original list because they were invited to go, but they chose not to.  I didn't uncheck them.  A few weeks before that email I was asked to find enrollments for Longmeadow, E Longmeadow, and Burlington, so I assumed they were going and checked them.  Apparently they weren't invited after all!

My apologies.  I'm trying to keep you students in the loop, but bad information is worse than no information.

Richard Yanco
Worcester Academy


Let $ a_n$ and $ b_n$ be two infinite arithmetic progressions with positive terms, so that the sequence defined by $ x_n\equal{}\frac{a_n}{b_n}$ contains only positive integers. Prove that $ x_n$ is constant.

{xn} is convergent, combining with the fact that {xn} are integer numbers, we got {xn} eventually becomes constant. Then we could prove that {xn} must be constant easily

For those interested in a "formal" solution, you would just take mto's idea, write for example $ a_n \equal{} a_0 \plus{} dn$, $ b_n \equal{} b_0 \plus{} Dn$ where $ d,D$ are obviously integers, and $ \lim_{n\to\infty}x_n \equal{} \frac {d}{D}$ must be integer, so $ d \equal{} rD$ for some integer $ r$.  Then, $ \frac {a_n}{b_n} \minus{} r \equal{} \frac {a_0 \minus{} rb_0}{b_0 \plus{} nD}$ is integer for all $ n$, and since $ a_0 \minus{} rb_0$ is constant, then it must be 0, and $ x_n \equal{} r$ for all $ n$...

UNLESS...   :huh:

of course!   :oops: if $ D \equal{} 0$, $ d\neq0$, then it suffices that $ b_0$ divides $ a_0$ and $ d$.  We then find the weak point, not of the solution, but of the problem: if $ b_n$ is constant, and $ a_0$ and $ d$ are multiples of $ b_0 \equal{} b_n$, then $ x_n$ is a sequence of increasing positive integers.   :oops:  In this case, the above solution does not work because $ x_n$ is a sequence of integers, but without a limit!  :o

Add the condition that sequence $ b_n$ is not constant, or that sequence $ x_n$ is bounded, and the solution as stated above is correct, and $ x_n$ is indeed constant as shown.  Otherwise, you may get the previous counterexample...   :P


Given $ n$ consecutive positive integer numbers.Prove that the number of $ n$ positive integer numbers is divisible by $ k$( $ k$ is odd, $ k\leq n$ ) is $ [\frac {n}{k}] \minus{} [\frac {n}{2k}]$

It is not true .  :wink:  For example $ k\equal{}3,n\equal{}5$ and consider the sequence .
Solution is follow :
Call the sequence is $ m\plus{}1,...,m\plus{}n$ then the number is :
$ [\frac{m\plus{}n}{k}]\minus{}[\frac{m}{k}]$

I'm not sure the result is $ [\frac{n}{k}]\minus{}[\frac{n}{2k}]$ but in your example $ k\equal{}3,n\equal{}5$ we have $ [\frac{n}{k}]\minus{}[\frac{n}{2k}]\equal{}1$
and in five number from $ 1$ to $ 5$ only the number $ 3$ is divisible by $ 3$ so the result is $ 1$. Is it true?ttsphn
and i think your result maybe true but you can prove this :)

The 5 sequence consider is $ 3,4,5,6,7$ it mean that this result depend on the first term of the consective sequence as I post.

oh, i see. but why you found that result and can you post your proof,please? :D


trigonometry function algebra polynomial invariant geometry symmetry

I attended a lecture last month at Trent University about a new theory called rational trigonometry that I've been thinking alot about since. It claims to be revolutionary in that it dispenses with all the usual complicated trig functions and relations and establishes a trig based entirely on elemental arimetric and algebra. I must say, I was impressed and fascinated. It seemed like such an elegant approach to trig... I have since visited the lecturing professor's website and downloaded the first few chapters of his new book on the subject and am still as intrigued as ever. (website http://wildegg.com)  Has anyone else heard of this new theory, and if so...what are your thoughts on it?

[quote="krista"]I attended a lecture last month at Trent University about a new theory called rational trigonometry that I've been thinking alot about since. It claims to be revolutionary in that it dispenses with all the usual complicated trig functions and relations and establishes a trig based entirely on elemental arimetric and algebra. I must say, I was impressed and fascinated. It seemed like such an elegant approach to trig... I have since visited the lecturing professor's website and downloaded the first few chapters of his new book on the subject and am still as intrigued as ever. Has anyone else heard of this new theory, and if so...what are your thoughts on it?[/quote]
I must know more...Do you have links?

I'm sorry I forgot to include the lecturing professor's website in my initial message... here it is     http://wildegg.com

Anyways, hope you have time to take a look at it, and let me know what you think.
Thanks,

Krista

Where did you find the sample chapters? It looks extremely interesting. ;)

I'm sorry for being so disorganized... the lecturing professor gave us all two websites and I must have got them confused, but on rechecking my notes I found the website with his downloadable chapters...it is  http://web.maths.unsw.edu.au/~norman

Talk to you soon,

Krista

I want it, but it costs alot of money and I have to ship from austrailia :(

I agree...it is alot of money... but I've always had a special liking for trig, and I will probably get the book anyways, just based on what I've seen so far. If you're interested, I can let you know what I think of it once I've read it.... thanks for your interest though. :) If you do decide to get the book too, let me know, and we can compare notes as we go along.

Krista

Hmm, I wouldn't buy it. It seems same as trig, just instead of working with d and theta you have to work with the artificially concevied quadrature (d^2) and spread (sin(theta)^2)

$d^2$ and (I think) $sin^2(\theta)$ are the polynomial (resp. rational) functions of lowest degree on pairs of points (resp. pairs of lines) which are
(a) invariant under isometries
(b) vanish when the points/lines are equal,
and they (c) generate all other such functions.

In this sense it is the most fundamental or simplest possible approach to geometry if one wants the computations to work nicely in coordinates.   It is impressive that somebody goes to book length in 2005 to make that point.   However, I think the author is deluded when he disparages the use of angles, as they are inherent in the rotational symmetry (which, as you can see from the above, is part of the whole [i]raison d'etre[/i] of such an approach), and they are naturally coordinatized by circle-valued quantities; the $\theta$'s are unavoidable.

Edit:  the above should read "work nicely [i]without[/i] coordinates", i.e. use isometry-invariant quantities to avoid the need for introducing coordinates.   Coordinates do not work well with the author's approach as they are based on distance along a given line being a linear, not quadratic, function.   This means that the real problem is not going from dimension 2 to 3 as the author states, but dimension 2 to dimension 1.


search
modular arithmetic
floor function
induction
number theory unsolved
number theory

One day I think about following sequence.
$ a_{1}=1$,
$ a_{n}$ := smallist positive integer $ x$ such that $ x\not= a_{1}, \cdots a_{n-1}$, $ n|a_{1}+\cdots+a_{n-1}+x$.
For example, 1,3,2,6,8,4,11,5,14, ...
I think $ \{a_{i}\}$ is permutation of positive integer, But I can't prove it.
Is it true? anyone can give a proof?

I tried to search in [url]http://www.research.att.com/~njas/sequences/Seis.html[/url],
But I couldn't find this sequence. instead, I found A019444, this sequence looks like same, but another definition.
and there is some property.
It looks like $ a_{a_{n}}=n$,
and I think there exist two sets $ A,B$ such that A, B is disjoint ,$ A\cup B=N$, $ n\in A \Rightarrow a_{n}\sim \frac{\sqrt{5}+1}{2}n$ and $ n\in B\Rightarrow a_{n}\sim \frac{\sqrt{5}-1}{2}n$.
Anyone have a idea?

It looks like this is a [i]very[/i] interesting sequence.

However let's create a slightly different sequence (I think it is more easy to work with):

$ b_{0}=0$

$ b_{n}$ is the smallest positive integer such that $ \sum_{i=0}^{n}b_{i}\equiv 0\pmod{n+1}$ and $ b_{n}\not\in \{ b_{0},\dots ,b_{n-1}\}$

(actually $ b_{n-1}=a_{n}-1$ if I'm not mistaken)

Now let's say that two guys (Albert and Barbara) are playing this game:

There are two columns of coins on a table, and at each move a player can remove k coins from a column or k coins from both, where k is a positive integer. Who removes the last coin is the winner. Albert starts.

Let $ X\subset N^{2}$ be the set of the starting positions where Barbara wins (playing correctly).

(x;y) is the position where there are x coins in the fist column and y in the second.

Now: $ X=\{ (n;b_{n})\; |\; n\in N\}$

This game was posted on an Italian math forum and it was discovered that:

$ X=\{ (\lfloor n\phi\rfloor ;\lfloor n\phi^{2}\rfloor )\; |\; n\in N\}\cup\{ (\lfloor n\phi^{2}\rfloor ;\lfloor n\phi\rfloor )\; |\; n\in N\}$ where $ \phi=\frac{1+\sqrt{5}}{2}$

(Now you will have understood what are the two disjoint sets...)

Bye!

Let's say:

$ A=\{ \lfloor n\phi\rfloor\; |\; n\in\mathbb{N}\}-\{ 0\}$

$ B=\{ \lfloor n\phi^{2}\rfloor\; |\; n\in\mathbb{N}\}$

It is well-known that, since $ \frac{1}{\phi}+\frac{1}{\phi^{2}}=1$, $ A\cap B=\emptyset$ and $ A\cup B=\mathbb{N}$

Let's define an other sequence.

If $ n\in A$ then $ c_{n}=\lfloor n\phi\rfloor+1$

If $ n\in B$ then $ c_{n}=\left\lfloor \frac{n}{\phi}\right\rfloor$

You can easily prove by induction that:

$ \sum_{i=0}^{n-1}c_{i}=\left\lfloor \frac{n}{\phi}\right\rfloor n$

Moreover, if $ n\in A$ (and so $ c_{n}>n+1$), we have that $ c_{n}-(n+1)\in\{ c_{0},\dots ,c_{n-1}\}$

So, $ \forall\; i\in\mathbb{N}: \; b_{i}=c_{i}$

Now, if $ n\in A$, then $ n=\lfloor k\phi\rfloor$ for some natural k. And $ c_{n}=\lfloor k\phi^{2}\rfloor$ so $ c_{n}\in B$ therefore $ c_{c_{n}}=\lfloor k\phi\rfloor=n$

The case when $ n\in B$ is analogous.

This problem was supposed at  L(Spb)MO 2004
One of solutions was essentially the same as written above: correspondence n\to a_n can also be defined in terms of Fibonaccy positional system

Finally I solved it with Yoon-Joo Kim and Doo-Sung Park in Korean Team Intensive training.
But my solution is quite messy.
I define two sets $ A, B$ such that
$ n\in A \iff \{\frac{\sqrt{5}-1}{2}n\}>\frac{\sqrt{5}-1}{2}$
$ n\in B \iff \{\frac{\sqrt{5}-1}{2}n\}<\frac{\sqrt{5}-1}{2}$ or $ n=1$.
Let $ A(x)$ and $ B(x)$ be a first $ x$ number in $ A,B$.
I proved that $ a_{1}+\cdots+a_{n}=n[\frac{\sqrt{5}-1}{2}n+1], f[A(n)]=B(n), f[B(n)]=A(n)$ by induction.
Therefore, $ a_{a_{n}}=n$, so there are all integer in range in $ a_{n}$.

and there are another my conjectures about it.
If we change $ a_{1}$, several terms in the sequence are change, but after first some terms, it became same as original sequence or +1 of original sequence.
i.e. for any integer $ x=b_{1}$, there are sufficiently large integer $ N(x)$ such that $ a_{n}=b_{n}$ or $ a_{n}+1=b_{n}$ for all integer greater than $ N(x)$.
I calculated the sequence for some values, but it was always true.
anyone have a idea?

[quote="Little Gauss"]One day I think about following sequence.
$ a_{1} = 1$,
$ a_{n}$ := smallist positive integer $ x$ such that $ x\not = a_{1}, \cdots a_{n - 1}$, $ n|a_{1} + \cdots + a_{n - 1} + x$.
For example, 1,3,2,6,8,4,11,5,14, ...
I think $ \{a_{i}\}$ is permutation of positive integer, But I can't prove it.
Is it true? anyone can give a proof?[/quote]
Actually this problem was used at Sankt-Petersburg City Olympiad 2004 as the last problem for 10th grade...
But its statement was a little different than yours,it asked to prove that ${ a_{a_n}}=n$,which makes the problem easier,i guess :roll:

It is true!  here is link to solution

http://www.mathlinks.ro/viewtopic.php?p=1110937#1110937

[quote="Erken"][quote="Little Gauss"]One day I think about following sequence.
$ a_{1} \equal{} 1$,
$ a_{n}$ := smallist positive integer $ x$ such that $ x\not \equal{} a_{1}, \cdots a_{n \minus{} 1}$, $ n|a_{1} \plus{} \cdots \plus{} a_{n \minus{} 1} \plus{} x$.
For example, 1,3,2,6,8,4,11,5,14, ...
I think $ \{a_{i}\}$ is permutation of positive integer, But I can't prove it.
Is it true? anyone can give a proof?[/quote]
Actually this problem was used at Sankt-Petersburg City Olympiad 2004 as the last problem for 10th grade...[/quote]
I believe it first appeared in Quantum journal Sept/October 1996 issue, and its author is A. Shapovalov.
See http://mathforum.org/wagon/fall96/p818.html


arithmetic sequence
combinatorics unsolved
combinatorics

Each positive integer is colored either red or blue .Prove that there exist an infinite increasing sequence of positive integers$ k_{1},k_{2},...$ such that the sequence
$ 2k_{1},k_{1}+k_{2},2k_{2},k_{2}+k_{3},2k_{3},k_{3}+k_{4},2k_{4},...$
is monochromatic

we prove by contradiction,assume that the length of every red and blue sequence 2x_1...2x_k such that x_i+x_{i+1} has the same colour is bounded
So we take a red sequence 2a_1..2a_n of maximal length,it's mean that for every x>a_n such that 2x is red 2(2x-a_n) is blue;otherwise choose a_{n+1}=2(2x-a_n) 2a_{n+1} and a_{n+1}+a_n is red
Take a blue sequence  2b_1..2b_m of maximal length we have for every y>b_t such that 2y is blue 2(2y-b_t) is red;otherwise choose b_{t+1}=2(2y-b_t)
So for every y;x>max {a_n;b_t} such that 2x is red;2y is blue we have 2(y-x)\neq\ a_n-b_t;otherwise the number 2(2x-a_n)=2(2y-b_t) has two colour,contradiction.Assume a_n-b_t=k>0 so take a progression 2a;2a+k;2a+2k.. with 2a>a_n all term must have same colour by above claim

My main method is as follow:otherwise, show that for $ y$ large enough and $ y$ is colored $ blue$ then:
$ 2(y\minus{}a_{m}),2y\minus{}a_{m}\minus{}b_{n},2(y\minus{}b_{n}),2y\plus{}a_{m}\minus{}3b_{n},2(y\plus{}a_{m}\minus{}2b_{n}),...$
are all $ red$ ( note that : this is a arithmetic progression with $ k\equal{}a_{m}\minus{}b_{n}$)
Choose $ k_{1}\equal{}y\minus{}a_{m},k_{2}\equal{}y\minus{}b_{n},k_{3}\equal{}y\plus{}a_{m}\minus{}2b_{n}....$
we got a infinite sequence as desired.Contradiction!
QED


There is a 6x6 array of numbers.  All the numbers are 0-9.  You may add 1 to every number in a row, a column or the upper-left-to-lower-right diagonal; however, after each addition, the numbers are taken mod 10.  So 5 6 7 1 9 4 would become, after 2 additions, 7 8 9 3 1 6.   If there is no limit to how many additions you can make, what is the maximum sum of the values of all of the numbers?  The initial array is contained in "milk.in" and your program should output to "milk.out".

This is a paraphrased version.

Beyond using 13 nested for-loops I can't figure this one out (of course, 13 nested for loops would fail)

http://activities.tjhsst.edu/sct/lectures/2008/adhocadvanced.pdf

I thought I saw this problem somewhere.
Said to be one of the most difficult usaco problems.

I'm not sure if I still stand by my statement that this was one of the hardest USACO problems ever, although the scores from that contest seem to indicate this.

Certainly it was pretty hard, but the difficulty of USACO has increased dramatically in past years.


integration limit logarithms function Euler calculus inequalities

[hide="Solution"]
The sum diverges to infinity.  Simple proof:

$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + ... > 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + ... = 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + ... = \infty$
[/hide]

[hide="Proof #2"]
Bound the series above an integral.  We have

$\int_{k=1}^{n+1} \frac{1}{x} < \sum_{k=1}^{n} \frac{1}{k}$

Taking the limit, we have

$\lim_{n \to \infty} \int_{k=1}^{n+1} \frac{1}{x} = \lim_{n \to \infty} \ln (n+1) = \infty < \lim_{n \to \infty} \sum_{k=1}^{n} \frac{1}{k}$

Q.E.D.
[/hide]

[hide="Proof #3"]
Consider the generating function $G(x)$ of the series.  We have $G(x) = \sum_{k=1}^{\infty} \frac{x^k}{k}$.  We have $G'(x) = \sum_{k=1}^{\infty} x^{k-1} = 1 + x + x^2 + x^3 + ... = \frac{1}{1 - x}$, so integrating back gives us $G(x) = - \ln (1 - x) + C$.  Our original series is given by $G(1)$.  Then simply write $\lim_{x \to 1^{-}} G(1) = \lim_{x \to 1^{-}} - \ln (1 - x) + C = \infty$

Q.E.D.
[/hide]

Possibly the most beautiful and interesting thing i have seen is that we can use this series to prove there are an infinity of primes! Due to Euler, who came up with an amazing factorisation of the harmonic series! Check it out:

$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+ \cdots=\left(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3} \cdots \right) \left(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}+\cdots \right) \left(1+\frac{1}{5}+\frac{1}{5^2}+\frac{1}{5^3} \cdots \right) \cdots$

To see why this is true, consider trying to multiply it out. By the unique prime factorisation theorem, we'll get every term in the harmonic series once and only once. But each of those bractets is finite! But since the harmonic series is divergent, there then must be an infinity of primes!

The sum tends to infinity because
$\\\lim_{R\rightarrow \infty}\int^{R}_1\frac{1}{x}\ dx\\ =\lim_{R\rightarrow \infty}\ln R=\infty$

Masoud Zargar

Also:
let S be that sum
1. Since there are infinitely many primes, let take the sum of the power of all that primes, and $S>\sum^{\infty} \frac{p}{p-1}>1\cdot \infty$

2.using associative propriety $S-\frac{S}{2}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+...=\frac{1}{1}+\frac{1}{3}+\frac{1}{5}...$ but every element of the LHS in less then the corrispondent in the RHS, so S=\frac{2}{2}S+kS, but it isn't true that $S\to 0$, so $S\to \infty$

[quote="JohnConstantine"]Also:
let S be that sum
1. Since there are infinitely many primes, let take the sum of the power of all that primes, and $S>\sum^{\infty} \frac{p}{p-1}>1\cdot \infty$[/quote]

I don't understand.  $\sum^{\infty} \frac{p}{p-1}$ doesn't even have terms that tend to zero, so you can't say that $S$ is greater than it without assuming $S \to \infty$ - or do you mean $\prod^{\infty} \frac{p}{p-1}$, which is equal to $S$ by the two expansions of $\zeta(1)$?   :huh:

Even more powerful (but has a more or less elementary prove):
$\sum_{p\in \mathbb{P} ; p \equiv 1 \mod 4} \frac{1}{p}$ and $\sum_{p\in \mathbb{P} ; p \equiv 3 \mod 4} \frac{1}{p}$ diverge.

Indeed, this generalizes to the much more deeper result that $\sum_{p\in \mathbb{P} ; p \equiv a \mod m} \frac{1}{p}$ diverges for any coprime $a,m$.

[quote="seamusoboyle"]I think he means the second one, which is pretty much what i did...

As an exercise, try your hand at proving:

$\sum_{\text{p prime}} \frac{1}{p}$

diverges, a much more powerful result.[/quote]

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=44490

[quote="seamusoboyle"]I find it hard to believe it has an elementary proof as it would result in an elementry proof of Direchlets theorem...[/quote]
No, that would only be an elementary prove for Dirichlets theorem for $n=4$...

Try this thread

http://www.artofproblemsolving.com/Forum/viewtopic.php?t=51675

Thanks blahblahblah, I was hoping that there would be (fairly) easy way to prove it, but alas, math dosen't always work out that way.

There are somewhat elementary methods in that thread - look near the bottom.

[quote="draperp"]Interestingly enough, \[ \frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}+...=\frac{\pi^2}{6}  \]

I've read this but does anyone know where the proof is?  (I think it was Euler who proved it.)[/quote]

I believe I have given on the forum already a proof by Fourier Series (Euler's proof is, I think, not very rigorous), you might try searching for it or a similar proof.

Similarly, $\frac{1}{1^4} + \frac{1}{2^4} + \frac{1}{3^4} + ... = \frac{\pi^4}{90}$  :D

Euler's proof is presented in a non-rigorous way.  You need to know something about integral functions of order 1 in order to make it rigorous, which requires a dose of complex analysis.

Yeah, those are values of riemann-zeta function... The later sums get more crazy (as if they aren't crazy to begin with).  According to mathworld, Euler evaluated all the even powered ones up to 26...

$\zeta(3)$ is a constant that, like the other odd integral values of $\zeta(x)$, cannot be expressed directly in terms of $\pi$.   :(

[quote="pavel25"]Evaluate the infinite sum: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\ldots$[/quote]
Use the fact that for  $j,k \in{\mathbb N}^{*}\; ,\; j\ge 2,$ we have $\left(1+\frac{1}{k}\right)^{k}< e <\left(1+\frac{1}{j-1}\right)^{j}$ which implies (using logarithms) \[(\pounds)\; \; \; \;\left\{\begin{array}{ccccc}{lclcl} \ln{(k+1)}-\ln{k}&<& \frac{1}{k}&, & k\in \{1,2,...,n-1,...\}\ &&&&\  \ln{j}-\ln{(j-1)}&>&  \frac{1}{j}& , & j\in \{2,3, ...,n,...\}\ \end{array}\right.\] If $H_{n}: =  \sum_{k=1}^{n}\frac{1}{k}\; ,\; \gamma_{n}: = \sum_{k=1}^{n}\frac{1}{k}\;-\; \ln{n},$   then by suming  above inequalities $(\pounds)$ one finds \[\left\{\begin{array}{c}{c} \frac{1}{n}+\ln{n}<  H_{n}<  1+\ln{n}\; \Longrightarrow\; \lim_{n\to \infty}H_{n}=\infty \ 0 <\gamma_{n}< 1\; . \end{array}\right.\] [b]--- Regarding[/b] $\zeta(3)$ If someone is interested to find informations about $\zeta(3) ,$ let us remind that today this constant is called  [b] Apery constant [/b] (see Roger Apery).  The Apery's Constant is defined as \[\zeta(3)=\sum_{k=1}^{\infty}\frac{1}{k^{3}}=1.20205690315959428539973816151144999076498629234049...\; .\] The designation of  $\zeta(3)$  as Apery's constant is new but well-deserved. In 1979,  Roger Apery stunned the mathematical world with a miraculous  proof that  $\zeta(3)$  [b]  is irrational .[/b]   The above expression is very slow to converge.  Another formula is \[(**)\; \; \; \; \; \zeta(3)= \frac{5}{2}\sum_{k=1}^{\infty}(-1)^{k-1}\frac{1}{k^{3}{2k \choose k}}\; \; \; \; \; \; \mbox{(R.Apery)}\] which was the  starting point of Apery's  incredible proof of the irrationality of  $\zeta(3) .$  Since 1980, many  formulas  $\zeta(3)$  were discovered.
  However a " [b] [u]  difficult question [/u]  [/b] "  is to prove the equality   ([b] try to give a short proof  ! [/b] ) \[\begin{array}{c}{\parallel c\parallel }\hline\hline \ \displaystyle \sum_{k=1}^{n}\frac{1}{k^{3}}-\frac{5}{2}\sum_{k=1}^{n}\frac{(-1)^{k-1}}{k^{3}{2k\choose k}}=  \sum_{k=1}^{n}\frac{(-1)^{k}}{2k^{3}{n+k\choose k}{n\choose k}}\ \ \hline\hline \end{array}\; , \; \; \; \mbox{ (also establihed by R.Apery)},\] which in fact proves (**) .

     [b]References regarding $\zeta(3)=$ Apery's constant[/b]
[1] T. Amderberhan ,  [i] Faster and faster convergent series for  $\zeta(3) ,$ [/i]  Electronic J. Combinatorics  3 (1996).
[2] T. Amderberhan ,  D. Zeilberger , [i]  Hypergeometric series acceleration  via the WZ method, [/i] Electronic  J.  Combinatorics ,   (Wilf  Festschrifft Volume ) 4 (2) (1997).
[3] R. Apery , [i] Irrationalite de  $\zeta(2)$ et  $\zeta(3) ,$ [/i]  Asterisque 61 (1979)  11-13.
[4] D.H. Bailey , P.B. Borwein , S. Plouffe , [i] On the Rapid Computation of Various  Polylogarithmic Constants , [/i]  Mathematics of Computation 66 (1997) 903-913.
[5] D.H. Bailey , D.J. Broadhurst , [i] Parallel Integer  Relation Detection : Techniques and Applications , [/i] Mathematics of Computation  (to appear), see also    http://front.math.ucdavis.edu/math.NA/9905048
[6] J.M. Borwein , D.M. Bradley , R.E.Crandall , [i]   Computational strategies for the  Riemann zeta function , [/i]  CECM preprint 98:118 (1998).
 [7] P. Borwein , [i]  An Efficient Algorithm for the Riemann Zeta Function , [/i]  (to appear).
[8] D.J. Broadhurst , [i] Polylograithmic ladders , hypergeometric series and the ten  milionth digits of  $\zeta(3)$ and  $\zeta(5) ,$ [/i]  (Preprint) (1998).
[9] R.E. Crandall , [i] Topics in Advanced Scientific Computation, [/i]  Springer, New York, 1995.
[10] S. Finch ,  [i] Favorite Mathematical Constants ,  [/i]    http://www.mathsoft.com/asolve/constant/apery/apery.html
[11] A.Lupas , [i] Formulae for some classical constants ,[/i]   Schriftenreihe des Fachbereichs Mathematik,  SM-DU-485 , (2000) , Gerhard Mercator Universitaet Duisburg, 70-76.
[12] A. van der Poorten , [i] A Proof that Euler missed ... Apery's proof of the  irrationality of  $\zeta(3) ,$  [/i] Math.Intelligencer 1 (1979) , 196-203.
[13] D. Zeilberger , [i] Closed Form (pun intended !) , [/i]  Contemporary Mathematics 143  (1993) 579-607.
[14] H.S. Wilf , D. Zeilberger , [i] Rational functions certify combinatorial   identities, [/i] Jour. Amer.Math.Soc. 3 (1990) 1147-158.
[15]  H. Wilf , [i] Accelerated series for universal constants , by the WZ method , [/i]   Discr.Math.Theoret.Comp.Sci. 3 (1999) 189-192 .

[b]--- Regarding[/b]  $\zeta(2) .$  We give a proof  which needs  following facts :
---Riemann integral , integration by parts,
--- ,, telescoping-products or  sums " , i.e. $\prod_{k=1}^{n}\frac{T_{k}}{T_{k-1}}= \frac{T_{n}}{T_{0}}\; \; ,\; \; \sum_{k=1}^{n}(T_{k-1}-T_{k})=T_{0}-T_{n},$
---  the inequalities   (  $a\ge 0\; ,b\ge 0\; \; ; x\in [0,\pi/2)\;$ ): $\; \min(a,b)\le \sqrt{ab}\le \max(a,b) \; , \; \; (*)\; \sin x \le x\le \tan{x}.$
 Let us consider the sequence $\displaystyle (\Omega_{n})_{n\ge 0}$ with \[\Omega_{n}= \frac{1}{4^{n}}{2n \choose n}=\frac{1\cdot 3\cdot \cdots (2n-1) }{2\cdot 4\cdots (2n)}=\frac{(2n-1)!!}{(2n)!!}\; \; ,\; \; \Omega_{0}=1\; ,\] where  for $k\in{\mathbb N}\; , z\in{\mathbb C}$ we have denoted  ${z\choose k}\; : = \frac{z(z-1)\cdots (z-k+1)}{k !}.$  Further we  denote \[\begin{array}{c}{|c|}\hline  I_{n}= \int_{0}^{\frac{\pi}{2}}\cos^{n}x\; dx\; \; \; , \; \; \; \;  C_{n}= \int_{0}^{\frac{\pi}{2}}x^{2}\cos^{n}x\; dx \ \hline \end{array}\; (n\in{\mathbb N}).\] [color=green][b]Step 1[/b] [/color] ( [i] Properties  of  [/i] ${\left(I_{n}\right)_{n\ge 0}}.$  )  We have \[\left\{\begin{array}{cc}{ll}A) \; & I_{0}= \frac{\pi}{2}\; \; \; ,\; \; \;  I_{1}= 1\ &\ B) \; &  nI_{n}= (n-1)I_{n-2}\; ,\; (n\ge 2)\ &\ C) \; & I_{2n}= \frac{\pi}{2}\Omega_{n}\; ,\;  I_{2n+1}= \frac{1}{(2n+1)\Omega_{n}}\; .\ \end{array}\right.\] [color=green] [b] Step 2 [/b] [/color]  $\left(A_{n}\right)_{n\ge 0}$ [b] with [/b]  $A_{n}= (n+1)I_{n}I_{n+1},$ [b] is a   constant sequence . [/b]  More precisely  $(n+1)I_{n}I_{n+1}=\frac{\pi}{2}\; .$
[b]Proof:[/b]  Multiplying the equalities $ (n+1)I_{n+1}= nI_{n-1}\; ,\; nI_{n}=\ds (n-1)I_{n-2},$ we obtain $A_{n}=A_{n-1}=\ldots = A_{0}=I_{0}I_{1}=\frac{\pi}{2}.$
 Therefore   $\; \;  I_{n}I_{n+1}=\frac{\pi}{2(n+1)}\; .$
[color=green] [b]Step 3 [/b] [/color]  ( [i] Wallis-type Inequalities [/i] :)   $ \frac{1}{\sqrt{n\pi+\frac{\pi}{2}}}\le  \Omega_{n}\le  \frac{1}{\sqrt{n\pi}}\; \; ,\; \; n \in{\mathbb N}^{*}\; .$
[color=green] [b]Step 4 [/b] [/color]  ([i]  A relation  between   $(I_{n})_{n\ge 0}$   and  $(C_{n})_{n\ge 0}$ . [/i] )  Integrating by parts,  we give  $C_{0}= \frac{\pi^{3}}{24}\; , \;  C_{1}= \frac{\pi^{2}}{4}-2$  and \[\begin{array}{c}{|c|}\hline I_{j}= \frac{j(j-1)}{2}C_{j-2}-\frac{j^{2}}{2}C_{j}\ \hline \end{array},\; \; (j\ge 2)\; .\] [color=green] [b]Step 5[/b] [/color] [i] (Two identities).[/i]  We have \[\left\{\begin{array}{ccc}{lcl} \sum_{k=0}^{n}\frac{1}{(2k+1)^{2}}&=& \frac{\pi^{2}}{8}-\frac{2n+1}{2}\Omega_{n}C_{2n+1}\ &&\  \sum_{k=1}^{n}\frac{1}{(2k)^{2}}&=& \frac{\pi^{2}}{24}-\frac{1}{\pi}\cdot \frac{C_{2n}}{\Omega_{n}}\; \ ; . \end{array}\right.\] [color=green] [b]Step 6 [/b] [/color] ( [i] Some inequalities[/i] ). We have \[\left\{\begin{array}{c}{c} \frac{1}{4n+6}\le  \frac{\pi^{2}}{8}-\sum_{k=0}^{n}\frac{1}{(2k+1)^{2}}\le  \frac{1}{4n}\ \  \frac{1}{4n+4}\le  \frac{\pi^{2}}{24}-\sum_{k=1}^{n}\frac{1}{(2k)^{2}}\le  \frac{1}{4n-2}\hsp .\ \end{array}\right.\] [color=green][b] Proposition [/b][/color] [b] For $n\in \{1,2,\ldots \}$ \[\begin{array}{c}{|c|}\hline  \frac{1}{n+1}\le \frac{\pi^{2}}{6}-\sum_{k=1}^{n}\frac{1}{k^{2}}\le \frac{1}{n-0.5}\; ,\; \;  \frac{1}{4n+6}\le  \frac{\pi^{2}}{8}-\sum_{k=0}^{n}\frac{1}{(2k+1)^{2}}\le  \frac{1}{4n}\ \hline \end{array}\; .\] [/b]   [b]  Therefore  [/b]   $ \zeta(2): = \sum_{k=1}^{\infty}\frac{1}{k^{2}}= \frac{\pi^{2}}{6}\;$    and  $ \sum_{k=0}^{\infty}\frac{1}{(2k+1)^{2}}= \frac{\pi^{2}}{8}$.

Please see also a nice paper by  [b] Robin Chapman [/b] , [i] Evaluating $\zeta(2)$ [/i],  : http://www.maths.ex.ac.uk/~rjc/etc/zeta2.pdf

[quote="seamusoboyle"]So whose going to evalute $\zeta (3)$?

I propose a race![/quote]
The prize: the Fields Medal!  :lol: It's interesting that we can find analytic solutions to even values, but have no idea how to express odd values in analytic form...

To flip2004: did you have that page already made, and you just copy-pasted it, or did you just spend like half an hour typing that up for this thread?  It's an impressive work, but you may have gone a bit overboard just for this thread ;-)

[quote="seamusoboyle"]To flip2004: did you have that page already made, and you just copy-pasted it, or did you just spend like half an hour typing that up for this thread?  It's an impressive work, but you may have gone a bit overboard just for this thread ;-)[/quote] Thanks  for interest ! Indeed I am interested on this subject , and I  have many informations regarding  this subject ,
 i.e.  $\zeta$ [b] function of Riemann [/b] .  Because I am an ... old man ,... I have time  for such interesting questions. Let us note that   [b]  my earlier posted message(s)  will be improved[/b]  :   [b] It's a delightful  subject !  [/b] , Regards, Alex.Lupas (=flip2004)

Indeed it is a fascinating subject! Eular contuctured that $\zeta (3)$ can be expressed in terms of $\pi$ and $\ln {2}$

Thats about the best we can do!

PS: When did i type that quote, i dont remember at all!


geometry
inequalities
inequalities unsolved

In any convex quadrilateral with sides $ a \leq b \leq c \leq d $ and area $F$ prove

$ F \leq \frac{3\sqrt {3}}{4}c^2  $

The inequality is rewritten as:

\[(-a+b+c+d)(a-b+c+d)(a+b-c+d)(a+b+c-d) \leq 27c^{4}.\] We substitute $x=-a+b+c+d$, $y=a-b+c+d$, $z=a+b-c+d$, $t=a+b+c-d$.

Then $\displaystyle \frac{x+y-z+t}{4}=c$ and  $x \geq y \geq z \geq t.$

Thus we have: $\displaystyle xyzt \leq 27 (\frac{x+y-z+t}{4})^{4}.$  The left side of the inequality is maximum when $z=y$ while the right side of the inequality is minimum (we have fixed x,y and t).

Then we just prove that $\displaystyle xy^{2}t  \leq 27( \frac{x+t}{4})^{4}.$

Because $xy^{2}t \leq x^{3}t$,  we just have to prove $\displaystyle x^{3}t \leq (\frac{x+t}{4})^{4}$, and then it follows that the above inequality is also true.$\displaystyle \frac{x}{3}+\frac{x}{3}+\frac{x}{3}+t \geq 4\sqrt[4]{\frac{x}{3} \cdot \frac{x}{3} \cdot \frac{x}{3} \cdot t}$, hence $\displaystyle 27(\frac{x+y}{4})^{4} \geq x^{3}t$. The END.


I just noticed that this forum is a "serious discussion of games". That said, where is the discussing of video games?

Make some! There was a brawl thread a while back but it died.

I think we all recognize that in practice, the correct description for this forum is not "serious discussion of games" at all.


inequalities
linear algebra
matrix
vector
linear algebra unsolved

Let $r(A)$ be the spectral radius of a matrix. Prove that if $A$ has nonnegative entries, then $r(A)\leq r(\frac{A+^{t}A}{2})$.

First let us show that for any matrix $ A $ with non-negative
entries, the spectral radius $ r(A) $ is it's eigenvalue. Using
this it is not hard to solve the problem. Indeed, suppose that we
have some vector $ v $ of norm $ 1 $ such that $ Av = \lambda v $,
for $ \lambda = r(A) $. Then we have $ ( \frac{A+A^{t}}{2} v,v) =
\frac{1}{2} ( (Av,v) + (A^{t}v,v) ) = \frac{1}{2} ( (Av,v) +
(v,Av) ) = \frac{1}{2} ( \lambda + \lambda ) = \lambda $, and we
know that for a symmetric matrix $ \frac{A+A^{t}}{2} $ we have
that $ r(\frac{A+A^{t}}{2}) = max_{ |w| = 1 } ( \frac{A+A^{t}}{2}
w,w) \geqslant ( \frac{A+A^{t}}{2} v,v) = \lambda = r(A) $. Now
let us prove that if $ A $ has non-negative entries, then $ r(A) $
is it's eigenvalue ( about this point I am not sure ). We can
assume that $ r(A) > 0 $. First of all, it is known that for $
|\mu| < \frac{1}{r(A)} $ the series $ 1+\mu A + \mu^{2}A^{2} +
\ldots $ converges absolutely and equals to $ (1- \mu A )^{-1} $.
For a complex matrix $ B= (b_{ij}) $, denote by $ ||B||_{1} = \sum
|b_{ij}| $ . Take some $ |\mu| < \frac{1}{r(A)} $ , and consider
the series $ 1+\mu A + \mu^{2}A^{2} + \ldots $. We have that $ ||
1+\mu A + \mu^{2}A^{2} + \mu^{3}A^{3} + \ldots ||_{1} \leqslant
||1||_{1} + |\mu| ||A||_{1} + |\mu^{2}| ||A^{2}||_{1} + |\mu^{3}|
||A^{3}||_{1} + \ldots =   ||1||_{1} + || |\mu| A||_{1} + ||
|\mu|^{2} A^{2}||_{1} + || |\mu|^{3} A^{3}||_{1} + \ldots $. But
the series $ 1 + |\mu| A  + |\mu|^{2} A^{2} + |\mu|^{3} A^{3} +
\ldots $ is a series of matrices with nonnegative entries,
therefore we have $ ||1||_{1} + || |\mu| A||_{1} + || |\mu|^{2}
A^{2}||_{1} + || |\mu|^{3} A^{3}||_{1} + \ldots = || 1 + |\mu| A +
|\mu|^{2} A^{2} + |\mu|^{3} A^{3} + \ldots ||_{1} $, so $
||1||_{1} + || |\mu| A||_{1} + || |\mu|^{2} A^{2}||_{1} + ||
|\mu|^{3} A^{3}||_{1} + \ldots = || 1 + |\mu| A + |\mu|^{2} A^{2}
+ |\mu|^{3} A^{3} + \ldots ||_{1} = || (1 - |\mu| A )^{-1} ||_{1}
$. Therefore we obtain that for every $ \mu $, such that $ |\mu| <
\frac{1}{r(A)} $ we have $ || (1 - \mu A)^{-1} ||_{1} \leqslant ||
(1 - | \mu | A)^{-1} ||_{1} $. Therefore for every $ \lambda $,
such that $ | \lambda | > r(A) $ , $ || ( \lambda - A)^{-1} ||_{1}
\leqslant || ( | \lambda | - A )^{-1} ||_{1} $. Now suppose that $
\lambda_{0} $ is an eigenvalue of $ A $, such that $ | \lambda_{0}
| = r(A) $. Then take $ \lambda_{n} := (1+\frac{1}{n}) \lambda_{0}
$, therefore $ \lambda_{n} \rightarrow \lambda_{0} $. Then we have
that $  || ( \lambda_{n} - A)^{-1} ||_{1} \rightarrow \infty $,
therefore $ || ( | \lambda_{n} | - A)^{-1} ||_{1} \rightarrow
\infty $, but $ | \lambda_{n} | \rightarrow | \lambda_{0} | = r(A)
$, so we get that $ ( | \lambda_{0} | - A) = (r(A) - A) $ is not
invertible, so $ r(A) $ is an eigenvalue of $ A $.

I hope it is correct.

I studied your solution and I think it is correct. Nice fact, I did not know that the spectral radius for a non-negative matrix is in fact an eigenvalue.


Can any body give me the main chinese olympiads problems??
I`ve search it but I didnt get anything usefull so any body could help me??
I need the recent 7-8 years in english
thanx


calculus integration articles Support Putnam

i know tons of people in this forum are chinese so what do u think of the anti-japanese situation, whos been following it? anything really bad happen where yall living? do u thin k japan will ever admit to their wrongs in WWII??

i really don't care.  the past is the past, forget about it.
i have nothing against japan, but many of the adults who lived through times have

I am not Japanese, but I know the emperor Hirohito never admitted his war guilt.

i followed for  a while..knowing how bored i am..

the situation died down after Asian-Afro meeting. China is now controlling many of the protest for some people are just trying to make matter worse on purpose cause they might dislike the government. At the beginning of the thing it was not controlled and widely spread.

China had got stronger at foreign policies by not stepping down and demanding an apologize from the japanese.
Although the japan is not going to stepping not for a formal apologize like Germany did after WWII. Germany is doing a great job on apologizes about WWII and I think the Japanese people need to learn from that.

I think the Japanese probably should apologize, but I don't really care that much.  For me, the past is the past, and I don't know that one generation must apologize for a previous one, when they really didn't have much of a role.  Of course many adults who lived at an earlier time would not agree.

Does anyone here think it might also have to do with Japan wanting a permanant seat on the Sercurity Council?  My social teacher thinks so, or at least is contemplating it.

Japan wanting a permanent seat on the Security Council is nuts. Period.

Er...not to be racist, but a happen to know of many Japanese people who are still not satisfied with the results of past wars against China. Of course, the Chinese calling the Japanese "re ben gui" might lower them to the same level. But still...hehe...

Wouldn't apologizing make it [i]easier[/i] to make it to the Security Council? :? whoa I make the Security Council sound like the IMO team or something...

[quote="nonIMO"][quote="MithsApprentice"]Of course, the Chinese calling the Japanese "re ben gui" might lower them to the same level.[/quote]

Do you mean 日本鬼 ? In my nonChinese opinion, it is less offensive than the word used by Japanese extremists.[/quote]
what do they use??

Sorry [b]shobber[/b], a bit of horrible misunderstanding from myself... I've read your signature just after I wrote something like "I would appreciate if someone corrects me" in the topic about "World's most popular language". I thought you are just laughing at me and even wanted to leave MathLinks.  :) Never mind.  :D

[quote="nonIMO"]Do you mean 日本鬼 ? In my nonChinese opinion, it is less offensive than the word used by Japanese extremists.[/quote]

Yes and yes lol

Although *mutters*...i did type the wrong phonetics on that one...*sigh*

[quote="shobber"]well, i see lots of people are answering this post, but how many of you are Chinese? :?[/quote]

Does it really matter? People should be aware of current events, nationality or not.

My parents are chinese, I consider myself Canadian though.

me=chinese

the problem is the Japanese look down to Asian countries...

They consider them as lower being cause Japan owned they all in WWII and they think they only lost due to America's nukes...

isnt this topic about anti-japanese situation not whether china is communist or not???

There is not much to say about communist. I only wanna say that:
China has got his own style.

Besides

[quote=bubala]You ought to read 1984. Can someone who has lived in China explain all the horrible things about communism. They'd know better than me.
[/quote]

what's that??

1984 is a famous book about autocracy.

There is another book , Animal Farm, which is also famous.

[quote="bubala"] yes, China is slowly becoming capitalist but as of right now it is still communist.  Not like the USSR was, but it's still communism.  And the government considers itself to be communist anyhow.[/quote]

USSR is desperately off-topic item here, but you were the first to introduce it. To start with, comparison of China and USSR looks strange to me (softly speaking), at least because the first has one of the fastest growing economies of the world (and not only economy) at the present time and the second ceased to exist long time ago. To end with, even if all the world will tell me, that USSR was a communist state I will oppose, asking a simple question: "can you point any official publication, published in the USSR during its existence, where it would be called communist state?" As I know, the official [b]aim[/b] was to achieve communism but the official [b]status[/b] until its end was "socialist state" in all official publications.

This topic has off-topic branches. I'll not post to it any more, because I don't want to worsen it further and also because politics is the less favourite topic for myself.[/b]

It seems that many of you guys don't support China in many things(such as taiwan problem and so on), and I think the, ONLY, reason is "China is communist". Am I right?

[quote="Yossarian"]One of the major points of 'nineteen eighty-four' (that's the full title) is that you're going to be in really big trouble when your leaders start to believe their own lies, and no one does anything about it. Especially the ones that go 'we need to do this for their own good, for national security, etc. And everything is just fine and dandy. Everyone's happy. Those people that complain are bad bad people who just want to wreck our beautiful country.'

But anyway, with regards to the topic... Some of you (ok, many) may find it overly alarmist, but a few of us are worried that an unrepentant Japan, if militarised, may pose security problems to other east asian countries in the mid term, especially if the Chinese regions undergo another upheaval. Such an upheaval is not an impossibility - I personally believe that the present system in the PRC has to go. If they move too fast, something might give (remember the USSR?). If they move too slowly, something might give too! The current social situation in mainland China is not stable. It isn't what you'd call unstable either, but growing pressures may be a problem in future.

Of course, if everything goes well, China remains strong, the N. Korean and Taiwan issues don't get out of hand... then I don't see any problem with the Japanese. They can remilitarise all they like, but with enough time, their culture will adapt and become more peaceable. Or so I hope. The problem is that there is a significant risk that things will not go well. In which case a militarily weak and repentant Japan would be preferable. I'd rather they export pop culture than occupying armies.

Ok, I admit that it may be somewhat alarmist, but nonetheless, I believe that it is a valid concern.

Recent APhO: 1st China, 2nd Indonesia, 3rd China (*ahem* a province of). Guess who's 4th?[/quote]

Aha!!!!!!!! :)  :D
One of my schoolmates has taken part in APHO, he got 8th place in all the participant, and 2or4?(not sure) in Chinese Team. (I also hope I could do well in CPhO 2005, that's my last chance, because I failed in 2004 :( )

Is forth Singapore?

Well, Stratfor thinks that China is headed for a big crisis in the mid term. That would be a problem for its neighbours as well. The so-called 'communist' government is one thing holding China back. Not that democratisation would automatically make China strong, but it could [i]potentially[/i] do so.

And by the way, someone you all know was the top female participant in the recent APhO.
Singapura boleh!

i think the opposite...look at US today...they are heading into a bigger crisis today with democractic government

different type of government have their pros and cons...so there is no perfect government...

SEE!!

you guys all heated up and started to talk (viciously ) about the communism problem!

same goes with Japan!

so, just shut up with anit-japanese thing

Shinwoo, that was hardly vicious.  In fact, it's been a quite civil, benign conversation since the last time you posted.  If you don't like the content of this thread, you are welcome to not look at it, and you are always welcome to contribute in some way meaningfully to it, but you are just being silly.

[quote="shinwoo"]so, just shut up with anit-japanese thing[/quote]

I don't think posters here who saw that will appreciate your postings very much. I don't myself, because I have thought it out seriously and posted accordingly. I am sure other people have at least thought about this issue seriously. None of these people are actually posting arguments towards each other... they are gently denying one another, which doesnt cause any problem. You, on the other hand, is posting in a very inappropriate language. Like JBL said, it is your right to not look at the post if you don't want to. However, it is not your right to make inappropriate language and contradictory points.

But in any case, most of the outrage should be directed at the politicians. I doubt chinese should blame the japanese for electing Koizumi (can't remember the spelling offhand) and company, the same way people don't blame the americans for voting Bush.
*ducks under table*
I hope they don't.

After all, in most elections foreign policy isn't the primary factor, unless there's a really big crisis.

But anyway, like most spats recently, this seems to have died down a bit. It will never really go away. I can't imagine Japan doing a tenth of what the Germans did and are still doing. Sometimes I even think that the Germans are a little overboard with their apologies. But that never hurt anyone. Japan was releasing a bunch of convicted war criminals at the same time Germany was going on a witch hunt for Nazi officials. Clearly people were not and still aren't convinced about Japan's commitment to pacifism. Is that too much to ask of them?

Now I will try to figure out why I'm spending more time here then doing math. Especially with my first Putnam half a year away. (Assuming the visa process goes through okay)


What percent of 300 is 550? include diagrams

since 550 is bigger than 300, the answer is going to be more than 100%.

if you take 100% of 300 away from 550, you get 250.

now, all you have to find is what percent of 300 is 250.

[hide] since $\frac{250}{300} = \frac{5}{6} = .8333 \ldots$,

$\frac{250}{300} =83. \bar {3} \%$

so finally, 550 is $183. \bar {3} \%$ of 300. [/hide]

This seriously should not be in Getting Started.


Does anyone here, well, can tell me all three cubic formulas and write them down? I searched and got a lot of formulas.

What do you mean by all three cubic formulas? Like, $1^3 + 2^3 + \ldots + n^3 = \displaystyle\left(\frac{n(n+1)}{2}\right)^2$?

I think he means the solution to ax^3+bx^2+cx+d=0

Yes, I meant the solution to that question.


Let $ S$ be a (possibly infinite) set of odd naturals. Show that there exists a sequence $ (x_{n})_{n=1}^{infty}$ such that the series of kth powers of this sequence converges iff $ k \in S$.


trigonometry
inequalities
inequalities proposed

If $\alpha_i\in\left[\left.0,\frac\pi2\right)\right.$, $i=\overline{1,n}$ then prove the following inequality
$\cos\alpha_1\cdot\cos\alpha_2\cdot\ldots\cdot\cos\alpha_n\left(\tan\alpha_1+\ldots+\tan\alpha_n\right)\le\frac{(n-1)^{\frac{n-1}2}}{n^{\frac{n-2}2}}$

a nice solution.
but I have a similar one without convex function.

I think I have to apology for I am not able to use Latex.
first we note f(a1，a2，……an）=sina1*sina2?cosn+???+cosan*sina2?sinan(we assume a1 <= a2 <=? <= an)
we prove that a1=a2=?=an,when  f(a1，a2，……an）is max.
because  f(a1，a2，……an）=<f((a1+an)/2,a2,?,(a1+an)/2)(it's not hard)
then the problem is to calculate nx^n :sqrt: 1-x^2
it is also not hard


conics
analytic geometry
geometry proposed
geometry

Let $ P$ be a point in the plane of triangle $ ABC$, not lying on the lines $ AB,BC,CA$. Denote by $ AA_b,A_c$ the intersections of the parrallels through $ A$ to the line $ PB,PC$ with $ BC$. Define analogously $ B_a,B_c,C_a,C_b$. Prove that $ A_b,A_c,B_a,B_c,C_a,C_b$ lie on the same [b]conic[/b]. :D
[i](Proposed by Mihai Miculita)[/i]

Let $(u:v:w)$ be the barycentric coordinates of $P$ WRT $\triangle ABC.$ Then cevian $PB$ has equation $ wx - uz = 0$ and infinite point $ P_{\infty}\equiv ( - u: u + w: -w).$ Thus, parallel to $ PB$ passing through $ A$ has equation $ wy + (u + w)z = 0$ $\Longrightarrow$ feet of the cevians $ AA_b,AA_c$ have coordinates

$ A_b \equiv{} (0: u + v: - w) \ , \  A_c \equiv{} (0: - v: u + v)$

Similarly we get the coordinates of $B_a,B_c$ and $C_a,C_b$ as

$ B_a \equiv{} (v + w: 0: - w) \ \ , \ \ B_c \equiv{} ( - u: 0: u + v)$

$C_a \equiv (v + w: - v: 0) \ \ , \  \ C_b \equiv ( - u: u + v: 0)$

$ \frac {AC_b}{C_bB} \cdot \frac {AC_a}{C_aB} \cdot \frac {CB_c}{B_cA} \cdot \frac {CB_a}{B_aA} \cdot \frac {BA_c}{A_cC} \cdot \frac {BA_b}{A_bC}= \frac {- uvw(u + w)(u + w) (u + w)}{ uvw(u + w) (u + w)(u + w)} = 1$

By Carnot's theorem we conclude that these 6 points lie on a same conic.


hello, you must write it with $ x$ signs.
Sonnhard.


function
integration
real analysis
real analysis solved

How do you show that if $f$ is absolutely continuous and $f'=0$ a.e then $f$ is constant ?

Well, this is the fundamental theorem for Newton-Leibniz's formula, i.e. $\int_a^b f'(x)dx = f(b)-f(a)$ if $f$ is absolute continuity.

To prove the statement, we need Vitali's Covering Theorem.


$(1)$ Show that the number of primes of the form $4n+3$ is infinite.

$(2)$ Show that the number of primes of the form $6n+5$ is infinite.

Posted [url=http://www.mathlinks.ro/Forum/viewtopic.php?&t=106257]here[/url]. Mind the generalization: if $\phi(a)=2$, then the set of all primes of the form $an-1$ is infinitely large.


Asymptote
LaTeX
rotation
vector
parameterization
geometry
complex numbers

Say I want to draw 5 circles that are tangent to each other and in a "bowling pin" patters (3 in the bottom row, two in the row above, and one on top), and have an Equilateral Triangle circumscribed around it, how would I do so?

Is there a way that could be generalized to, say, 15 circles?

Erm... You mean [b]6[/b] circles? OK, here is one possible code
[asy]pair A=2*dir(0), B=2*dir(120);
int n=6;
for(int i=0;i< n;++i)
for(int k=0;k< i+1;++k)
draw(circle(i*A+k*B,1),blue);
draw(2*dir(210)--(n-1)*A+2*dir(-30)--(n-1)*A+(n-1)*B+2*dir(90)--cycle,linewidth(1)+red);[/asy]

I have 2 questions:

What does "dir*" do (or anything with "*" after it for that matter), I know in $ \text{\LaTeX}$ is hides the number of the section...

How can I make a line going from the center of one of the corner circles to the vertex of the equilateral triangle. (In other words, what would we use to draw the path).
[/u]

The star is the operator for multiplication in Asymptote. dir(60)*path rotates the path with 60 degrees around the origin.

[quote="happyme"](In other words, what would we use to draw the path).
[/quote]
:what?: The [b]draw();[/b] command, of course.

What would we draw it from (how would we know what hte center of that circle was)?

draw((something)--(something));

what would the somethings be?

I apologize if it sounds a bit impolite, but did you bother to try to understand the code I wrote? You have all the centers of the circles and the verteces of the triangle right there :roll: OK, here are all three line segments you wanted:
[asy]pen p=brown+linewidth(0.75);
pair A=2*dir(0), B=2*dir(120);
int n=5;
for(int i=0;i< n;++i)
for(int k=0;k< i+1;++k)
draw(circle(i*A+k*B,1),blue);
draw(2*dir(210)--(n-1)*A+2*dir(-30)--(n-1)*A+(n-1)*B+2*dir(90)--cycle,linewidth(1)+red);
draw(2*dir(210)--(0,0),p);
draw((n-1)*A--(n-1)*A+2*dir(-30),p);
draw((n-1)*A+(n-1)*B--(n-1)*A+(n-1)*B+2*dir(90),p);[/asy]

Okay, I shall tell you all that I understood from the code, and maybe you could fill in the parts that I don't understand.

1. "pair A=2*dir(0), B=2*dir(120);"  You define 2 pairs (A,B) and thats pretty much all I understand (aside from dir(120) is a "path" (what path) rotated around the origin).

2. int n=6; You have an integer $ n$ whose value is 6.

3. "for(int i=0;i< n;++i)
for(int k=0;k< i+1;++k)"

This step basically generalizes what I asked (to make it easy to change the amount of circles) from what I can tell.

4. draw(circle(i*A+k*B,1),blue); This command draws a circle (but how does it draw the circles in the triangular form) and does some multiplication with the variables i and k shown earlier...

Thats pretty much how little I understand, could you explain some more?

Thanks for your help.

OK, let's go over it slowly :)

1) dir(a) returns a pair (think of pairs as of vectors or complex numbers) with absolute value $ 1$ and argument (angle with the horizontal direction) $ a$ in degrees. When you multiply it by $ 2$, you just get twice longer vectors. So, my $ A$ and $ B$ are just these 2 vectors:
[asy]size(50);
pair A=2*dir(0),B=2*dir(120);
draw(D((0,0))--D(MP("A",A)),Arrow);
draw(D((0,0))--D(MP("B",B,W)),Arrow);[/asy]

2) $ n$ is the number of circles along the side of the triangle. That is the parameter you can change to get more or fewer circles in your picture.

3) You are correct. The circles are centered at the lattice points $ i*A\plus{}k*B$. The whole lattice looks like this:
[asy]size(350);
int n=4;
pair A=2*dir(0),B=2*dir(120);
for(int i=-n;i< n+1;++i)
for(int k=-n;k< n+1;++k)
{
D(MP("("+string(i)+","+string(k)+")",i*A+k*B,6));
if((i>=0)&&(i<n)&&(k>=0)&&(k<=i)) D(CR(i*A+k*B,0.25),linewidth(2));
}[/asy]
but you need only the part in black. Now, I hope, you can easily see why the loops ar set this particular way.

4) Now come the verices of the triangles. They are almost the same as the centers of the corner circles, which are the origin, $ (n\minus{}1)*A$ and $ (n\minus{}1)*A\plus{}(n\minus{}1)*B$. All I need is to shift them a bit out, which is exactly what those $ 2*dir()$ in the last draw command do (I leave the elementary geometry allowing to figure out by how much and in what directions the shifts have to be made to you).

Hope this helps a bit :)

(I'm sorry I'm bothering you so much with my nooby questions).

In Step 3, where you center the circles at the lattice points, how do you get a lattice point if you multiply the integer by vectors, since you say that if you "multiply it by $ 2$, you just twice a long vector.

Also, in the first code that you gave me, you have:

[code]
pair A=2*dir(0), B=2*dir(120);
int n=5;
for(int i=0;i< n;++i)
for(int k=0;k< i+1;++k)
draw(circle(i*A+k*B,[b]1[/b]),black);
draw(2*dir(210)--(n-1)*A+2*dir(-30)--(n-1)*A+(n-1)*B+2*dir(90)--cycle,linewidth(1)+black);
[/code]

What is the ",1" and what does it do?

If you can tell, I understand all the steps aside from the one where you generate the circles and their centers.

[quote="happyme"][code]
pair A=2*dir(0), B=2*dir(120);
int n=5;
for(int i=0;i< n;++i)
for(int k=0;k< i+1;++k)
draw(circle(i*A+k*B,[b]1[/b]),black);
draw(2*dir(210)--(n-1)*A+2*dir(-30)--(n-1)*A+(n-1)*B+2*dir(90)--cycle,linewidth(1)+black);
[/code]
What is the ",1" and what does it do?[/quote]
The first argument in [b]circle()[/b] is the center; the second is the radius. :)

[quote="happyme"]
In Step 3, where you center the circles at the lattice points, how do you get a lattice point [/quote]
I also add vectors: $ i*A\plus{}k*B$ gives the linear combination of $ A$ and $ B$ with the coefficients $ i$ and $ k$, which is exactly what a lattice point is :)


Let $ a,b,c>0$ prove that

\[ (a\plus{}b\plus{}c)^6\ge 27(a^2\plus{}b^2\plus{}c^2)(ab\plus{}bc\plus{}ca)^2\]

\[ (a\plus{}b\plus{}c)^9\ge 3^6(a^2\plus{}b^2\plus{}c^2)^2(ab\plus{}bc\plus{}ca)(abc)\]

The first inequality is equivalent to $ p^6\minus{}27(p^2\minus{}2q)q^2\ge 0$, or $ (p^2\plus{}6q)(p^2\minus{}3q)^2\ge 0$ which is alway true. (Or we can rewrite back to the form of a,b,c: $ (a^2\plus{}b^2\plus{}c^2\plus{}8ab\plus{}8bc\plus{}8ca)(a^2\plus{}b^2\plus{}c^2\minus{}ab\minus{}bc\minus{}ca)^2\ge 0$)

About the second inequality, try substituting a=b=1,c=2, we will get $ 262144\ge 262440$, which is totally wrong.


trigonometry
geometry
geometric transformation
reflection
induction
combinatorics proposed
combinatorics

Prove that the number of tiling a chessboard $8\times8$ by $2\times1$
dominoes is $\leq2^{30}$.

I was in the jury of Kolmogorov'97 :P

As I remember, there was conjecture (?) that this number is a perfect square.

I think that I've read somewhere that someone has found the exact number, some physicist as I remember(?!). I'm not sure.

yah it first appeared in Physica(1961);the paper by Kastelyn,titled 'The Statistics of dimers on a lattice'.i think it has also appeared on several other papers;the result is the following:
   The number of tilings ofa $2m\times 2n$ rectangular board by dominoes is $\displaystyle 4^{mn}\prod_{j=1}^{m}\prod_{k=1}^{n}\left( \cos^2\frac{j\pi}{2m+1}+\cos^2\frac{k\pi}{2n+1}\right)$.

Isn't this a nice problem? Will someone please put any solution?

Take a corner. It must be covered by a domino - only 2 ways. In this way we take 32 corners, and cover the board. Whether the first domino is put upright or left-right doesn't matter because you can reflect the board, so they will not be distinct. Also, the last domino is fixed. So number of tilings is less than $2^{30}$.... Is this right?

I don't believe you're right, kueh. Are you actually using induction?
Please explain better.

Nope. I am using the fact that in any incomplete tiling there must be a corner. It must be covered, so there's only two ways it can be covered.

Sorry, but I can only understand from your solution that the number of tillings is at most $2^{31}$.

Myth, can you write the official solution of this problem? I suppose you know it.


For $a,b,c\ge0$ prove that

$a^{4}+b^{4}+c^{4}\geq a^{3}b+b^{3}c+c^{3}a$

or equivalently (according to http://www.mathlinks.ro/Forum/viewtopic.php?t=103773)

$[4,0,0]\ge[3,1,0]$

[hide="solution"]Well, that is easy. Just sum AM-GM of the form

$\frac{a^{4}+a^{4}+a^{4}+b^{4}}{4}\geq a^{3}b$

implies desired result. Equality occurs iff $a=b=c$.

Note that our inequality can be valid for all reals.[/hide]

Prove that

[code]a^{3}+b^3+c^3 \geq a^2b + b^2c + c^2a[/code]

[b]a, b, c are postive number[/b] :D

Why don't work Code, at my computers?

[quote="Fitim"]Prove that

[code]a^{3}+b^3+c^3 \geq a^2b + b^2c + c^2a[/code]

[b]a, b, c are postive number[/b] :D[/quote]

But that is another problem, please create a new one topic about it.

More generally, if you have a related problem, or a new one, just create a new topic. Don't post it in some old thread.

The convention on $[n,n,n]$ you use is very nonstandard, and the problem is a trivial consequence of rearrangement, just like many of its generalisations. (Fitim's problem is not what one usually calls a 'different' problem, by the way)


probability
combinatorics proposed
combinatorics

Let $ n > 1$ and $ 1 < k < 2^n$. Let R be an n-element set. A collection S of subsets of R is said to be [i]chainable[/i] if we can put the subsets in S into a sequence $ A_1$, ..., $ A_k$ such that the intersection of $ A_i$ and $ A_{i \plus{} 1}$ contains exactly 1 element for $ 1 \le i \le k \minus{} 1$. If we choose a collection of k subsets of R at random (with each possible collection being equally likely), find the probability that it is chainable, in terms of k and n.

For example, if $ n \equal{} 5$, and $ k \equal{} 3$, the collection $ \{1,2,3\}$, $ \{3,4\}$, $ \{4,5\}$ is chainable. Note that by 'collection,' we mean that all elements are distinct, and the collection is unordered.

This seems rather hard in general.

For $ k \equal{} 0$, the empty set is chainable and so the answer is 1.

For $ k \equal{} 1$, any single set is chainable and so the number of chainable sets is $ 2^n$.

For $ k \equal{} 2$, let us first count the number of ordered pairs of subsets that form a chain.  For any given subset of size $ i$, we can choose the element of intersection in $ i$ ways and choose the rest of the second subset in $ 2^{n \minus{} i}$ ways, so the number we seek is $ \sum_{i \equal{} 0}^n \binom{n}{i} \cdot i \cdot 2^{n \minus{} i}$.  A tiny bit of manipulation shows that this is equal to $ n 2^{n \minus{} 1} \sum_{j \equal{} 0}^{n \minus{} 1} \binom{n \minus{} 1}{j} \left(\frac {1}{2}\right)^{j} \equal{} n 3^{n \minus{} 1}$.  From these ordered pairs we need to remove the $ n$ pairs of a single-element set with itself, then divide by two for unordering to get $ \frac {n(3^{n \minus{} 1} \minus{} 1)}{2}$.

For $ k \equal{} 3$, we can do something similar but uglier for ordered triples: choose the middle subset to be of size $ i$; then we have $ i\cdot 2^{n \minus{} i}$ choices for the left and right subset.  This gives $ \sum_{i \equal{} 0}^n \binom{n}{i} i^2 4^{n \minus{} i}$, and some manipulations slightly more complicated than in the preceding case show that this is equal to $ (n^2 \plus{} 4n)5^{n \minus{} 2}$.  Figuring out what to subtract off is a fair bit uglier: after removing those cases where the middle set is equal to one or both of the outer sets, we must consider separately those triples in which the sets have pairwise intersections of size 1 (and this also comes in two cases depending on whether the three sets have a common element or not).  None of this is very hard, but I also don't feel particularly inclined to do it myself.

For larger $ k$, we can't get away with using just a single sum anymore, and the potential complications in going from ordered to unordered sets are far greater.  I think the ordered problem is probably tractable in general, but I'm not so sure about the question that was actually asked.

Is there a simple construction that shows that the set of nonempty subsets of an $ n$-set is chainable?