geometry
rectangle
algorithm
geometric transformation
rotation
induction

We define a [i]chessboard polygon[/i] to be a polygon whose sides are situated along lines of the form $ x \equal{} a$ or $ y \equal{} b$, where $ a$ and $ b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles. Finally, a [i]tasteful tiling[/i] is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $ 3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

[asy]size(300); pathpen = linewidth(2.5);
void chessboard(int a, int b, pair P){
 for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j)
  if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6));
 D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle);
}
chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12));

/* draw lines */
D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy] a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.

only proved a), I think my proof is correct. I proved by doing "move"s(every time you meet a distasteful tiling, you turn the direction of that 4 cells' tiling), after each move, you will get a completely new arrangement of tiling.(For this part, I suppose if an arrangement will appear twice, then let it be the initial arrangement, now I put 1 counter in the 4 cells after each move, which means after some moves all the cells will have an even number of counters in it. Since we never do "move" at the same 4 cells continuously, every time there will be a new cell which the counter turns from 0 to 1. Eventually it will get to the 4 corner cells. But it's obvious that the 4 corner cells can only be moved at most once. Which means there will always be some cells with odd counters in it. Which means no arrangement will appear twice). After each move, the number of distasteful tilings may change or not, but the point is if it never gets to 0, it means it will always be a possible "next move", which means there will be a new arrangement. Since the total arrangement number is limited, the number of distasteful tilings have to get to 0 after some moves.

That's what I did, but I said that every 2x2 square cannot be "moved" back to its original position, so if some specific 2x2 square is distasteful, it can never be distasteful again, similarly with any other 2x2 square. So therefore, this process must be finite, and eventually it will become tasteful.

This is a bit hard to explain without a picture, but I'll try anyways. Solution by Paul Christiano.

[hide="part a"]
Every time we have a 2x2 grid that is illegal, note that rotating it 90 degrees makes it legal. Consider the algorithm of starting at the top left and going down to the bottom left, performing this rotation operation every time we encounter an illegal grid. I claim that this process will only happen finitely many times before we get to a tasteful tiling.

Indeed, if we look at any square that has no squares to its immediate left or immediately above it, then one can check that the 2x2 grid starting there can only be rotated at most once. In particular, either it will be rotated after finitely many other operations, at which point we can just ignore it because it will never change again, or it will never be rotated, at which point we can ignore it from the beginning. Either way, finiteness of our algorithm on this grid reduces to finiteness of our algorithm on a smaller grid, so we can imply induction to see that our algorithm will terminate.
[/hide]

[hide="part b"]
We will proceed by induction on the size of the grid. Consider the upper-left corner of the grid. Then there exist two potential ways to cover this square: either we can place a rectangle that is part of one of the illegal 2x2 grids, or we can place it the other way. Call the first way "bad" and the second way "good". What we will show is that if the bad choice can be extended to a tasteful tiling, then the good choice cannot be extended to any tiling. This will establish the desired result. WLOG the bad choice consists of placing a tile vertically (the two cases are symmetric so we'll only deal with this one).

Suppose that the bad choice leads to a tasteful tiling. Note that the bad choice forces a sequence of tiles to be placed going diagonally downwards until there is a hole in the grid (call these the "forced squares"). Then, since the grid is simply connected, removal of these diagonal tiles must split the grid into at least two components. Consider the set of components below the diagonal (call these the "lower squares"). By assumption they can be tiled, so they must contain the same number of dark and light grid squares. But now consider the diagonal of squares that makes up the bottom edge of the forced squares. These are all one color, call the color $ C$. Take the set $ S$ of the forced squares together with all of the lower squares with color $ C$. If we were to place the good tile at the beginning instead of the bad tile, then if we consider the remaining squares, $ S$ is adjacent to less than $ |S|$ squares with the color other than $ C$. This implies that there is no way to come up with a valid tiling covering $ S$, since any such tiling would have to cover equally many squares of each color. Thus the good choice cannot lead to any tiling, which is what we wanted to show, so we are done.
[/hide]

Basically, the only way to tile them tastefully was to start in the middle and layer the other tiles outward, if you know what I mean. I also tried to prove that was the only way by doing

l W G
l G W

and showing that there was no possible way to create a square corner while avoidind distaste. The way to tile them was:

l W G l W G l W G l... (2 rows if needed) in the middle. When you add an outer layer, they are staggered, so there is no possible distaste since there are no 2 x 2 squares.

Kinda hard to explain w/o picture.

The solution seems good. Thanks!

By the way, had Paul Christiano solved every single problem? If so then he may get perfect! wow!

Paul was a senior last year.  He's at MIT now, so I assume he was just trying the problems for fun.

The solution seems nice, but I don't understand the part about the forced squares and the diagonal.

I have a very neat existence proof:

Choose a number $ r>1$. Assign to the tile with lower left corner at $ (a,b)$ the weight $ (\minus{}r)^{a\plus{}b}$. Shade the squares with positive weight, noting that they are at locations with $ a\plus{}b$ even.

Sum the weights of all tiles, multiplied by $ 1$ for those in horizontal dominos and $ \minus{}1$ for those in vertical dominos. A $ 2\times 2$ distasteful block with lower left corner at $ a\plus{}b$ contributes $ \minus{}r^{a\plus{}b}(r\minus{}1)^2$, while its tasteful counterpart gives $ r^{a\plus{}b}(r\minus{}1)^2$.
There are finitely many possible sums, and finitely many tilings, so some tiling has a maximal sum. If this maximum had any distasteful blocks, we could reverse them to increase the sum. This doesn't happen, so the maximum is  tasteful tiling.

- JSteinhardt: I'm not at all convinced that that argument handles irregular grids. If that "upper left" tile isn't uppermost, we may be able to escape- in particular, if the tile one spot up and one to the right is in the grid, we can put a vertical tile there. Then that tile might not even be a corner...

Very elegant proof.  But does it address part b)?

No, it doesn't. The method doesn't rule out two local maxima.

I've been working on part (b); so far I can say a lot about the structure of a minimal counterexample, but I can't rule it out completely. Uniqueness is false if we allow holes in the middle, by the way.

So I guess I forgot to add in a few lemmas that I thought weren't needed, but now I realize you do. Essentially if there is anything that is adjacent to only one other square then there is only one possible way that you can place a tile to cover that square, so we can rule out all those cases. Then if we consider the top row and go as far left as possible we can safely apply the same argument as before from that square.

EDIT: Nevermind I see your objection, if I do that then my WLOG is no longer appropriate because I've broken symmetry.

I think I've made the breakthrough I needed.
[hide="Uniqueness"]Suppose by way of contradiction that we have a chessboard polygon with more than one tasteful tiling. Moreover, assume that this polygon has minimal area among chessboard polygons with this property.
Overlay two tasteful tilings of this polygon, and look at how its squares are connected by dominoes. Each square is connected to either one or two other squares; one if its domino is unchanged, two if its dominoes are different. We get a graph on the squares, with some number of loops of changed dominoes and some two-square islands of unchanged dominoes. Any of those loops together with all squares inside it is itself a chessboard polygon with two tasteful tilings, so we may assume that there is only one loop, which includes all squares on the boundary.

Consider some lower left corner, and call its location $ (0,0)$. We first consider the case in which this corner is shaded: $ \begin{array}{ccc}U & & \\
| & & \\
S & - & U\end{array}$
Since the loop must come back around, and can't do this through the third quadrant, $ (1,1)$ must be in the polygon. We can't have the domino at $ (1,0.5)$ in the same tiling as the domino at $ (0,0.5)$, so $ (1,0)$ must connect in another direction; either (a)$ \begin{array}{ccccc}U & & S & & \\
| & & \times & & \\
S & - & U & - & S\end{array}$ or (b) $ \begin{array}{ccc}U & & S \\
| & & \times \\
S & - & U \\
& & | \\
& & S\end{array}$
In case (a), we can't have the domino at $ (1.5,1)$ in the same tiling as $ (1.5,0)$. If the loop comes back around to that spot from $ (2,0)$, it must come through $ (2,1)$ before $ (1,1)$, and $ (1.5,1)$ will be in the same tiling. Since that tile can't be in the loop, it can't be in either tiling at all. $ (1,1)$ must be connected to something, and a domino at $ (1,1.5)$ is the only possibility: $ \begin{array}{ccccc} & & U & & \\
& & | & & \\
U & & S & \times & U \\
| & & \times & & \\
S & - & U & - & S\end{array}$
Again, we must include $ (2,1)$, and we can't link it to $ (2,2)$, so the domino at $ (2.5,1)$ must be in at least one tiling. If it's in both, the pair of fixed dominoes we have forces another fixed domino at $ (2,2.5)$, which forces one at $ (3.5,2)$, and so on. This process continues indefinitely, only stopping at the edge of the polygon. When it does, we have a wall that we can't close the loop around, and we have a contradiction. The alternative is to make it part of the loop:
$ \begin{array}{ccccccc} & & & & U & & \\
& & & & | & & \\
& & U & & S & \times & U \\
& & | & & \times & & \\
U & & S & \times & U & - & S \\
| & & \times & & | & & \\
S & - & U & - & S & & \end{array}$
That choice means we can't have $ (2.5,2)$, for the same reasons we couldn't have $ (1.5,1)$ before. We get another fixed tile at $ (2,2.5)$, and again we can see that this configuration must grow indefinitely for a contradiction.

We can also reflect across $ x = y$ and reverse colors to get case (a'): that $ \begin{array}{ccc}U & & \\
| & & \\
S & & U \\
| & & \\
U & - & S\end{array}$ leads to a contradiction, as a ladder of fixed horizontal dominoes leads to failure.

Now, case (b). We can't connect $ (1, - 1)$ to $ (0, - 1)$ because of the domino at $ (0.5,0)$ in the same tiling. If we connect $ (1, - 1)$ to $ (2, - 1)$, we're right back where we started, with a shaded lower left corner and either (a) or (b) one down and one to the right. Since the polygon is finite, we can't keep doing this forever, and eventually we must make a different choice. WLOG it's this time, and we have the domino at $ (1, - 1.5)$:
$ \begin{array}{ccccc}U & & S & & \\
| & & \times & & \\
S & - & U & & S \\
& & | & & \times \\
& & S & & U \\
& & | & & \\
& & U & & S\end{array}$
Turning right now puts us in case (a'), and we already know that doesn't work. If we do anything else, we must eventually reach another lower left corner, somewhere down and possibly leftward. If it's (a) or (a'), we're done, and if it's (b) we go through the whole thing again. The only remaining choice is (b'):
$ \begin{array}{ccc}\times & & \\
S & & U \\
| & & \\
U & - & S\end{array}$
Relabel coordinates so that the lower left $ U$ is $ (0,0)$. Now, how did we get here? We can't have $ (0.5,1)$ in the loop because it is distasteful with $ (0,5,0)$. We don't have $ (0,1.5)$ because that's case (a'). That leaves only $ ( - 0.5,1)$- and the only way to include that domino is for there to be another lower left corner somewhere upward and left of here. That's impossible by the location we're at, and we have a contradiction.

If we start with an unshaded corner square, simply exchange the pairs ((a), (a')) and ((b), (b')), working upward and leftward rather than downward and rightward.[/hide]

Those fake pictures were a pain, but it's unreadable without something. Does anyone know a better (longer) horizontal dash symbol in $ \text{\LaTeX}$?

[Added in edit][quote="krakola45"]...but I said that every 2x2 square cannot be "moved" back to its original position, so if some specific 2x2 square is distasteful, it can never be distasteful again[/quote]
Not true. In large polygons, many of the distasteful blocks will return; in a $ 2n\times 2n$ square, it takes $ n+8\binom{n+1}{3}=\frac{n(8n^2+6n-8)}{6}$ moves to go from the worst arrangement (no tasteful $ 2\times 2$ blocks) to the best, or half that from a random tiling to the tasteful tiling on average. The average number of times each $ 2\times 2$ block is moved is proportional to the linear size, and a block in the middle can move twice in something as simple as a $ 4\times 4$ board.

I have a feeling that a lot of people are wrong in subtle ways, and didn't solve as much of this problem as they thought.

Jmerry, I think you need to be more rigorous on what you mean by "some lower left corner." Some polygons don't have a "lower left corner."  Do you mean the square for which $ a\plus{}b$ is a minimum?

The definition of a lower left corner: any square in the polygon for which neither the square directly below nor the square directly to the left is in the polygon. Every polygon must have at least one, and some polygons have many.
Minimizing $ x\plus{}y$ would make the argument simpler, though. In that case, we can't keep going down in case (b).

Whoa, looks like you've used a similar approach to my original one, but I was not satisfied with the casework involved.

[hide="possible improvement"]
OK so let's say you have the closed loop that you described. We can assume it's minimal so that the tilings agree on everything inside it.
[hide="aligned tiles"]
In the loop, try to show that you can't have two dominoes from different tilings sharing a long side.

Proof idea: Assume you can. Start from one of the two dominoes and traverse the loop in one direction. Try to show that the loop "closes itself in" during the traversal so that it cannot be completed.
[/hide]
[hide="odd areas"]
Consider a path along the edges of the tiles that goes alternately one unit horizontally and one unit vertically. Try to prove that it does not enclose equal numbers of black and white squares.

Proof idea: Start from some vertex on the path, and draw a line to every other vertex. This forms a polygon with sides at 45 degrees with the grid, and this polygon encloses an area that is balanced in color composition, i.e. the black area enclosed equals the white area. Try to show that adding in the vertices we skipped when drawing this polygon upsets the balance.
[/hide]
[hide="hamsters"]
Release a hamster at a vertex inside the loop, and tell it to go alternately one unit vertically or horizontally along the edges of the dominoes (of either tiling, since they coincide, at least in the interior). This is guaranteed to be possible by the absence of distasteful blocks. Try to arrange so that it does not exit the loop by arguing that if it tries to, at least one of the tilings is blocking it.

The hamster will enclose an area with unbalanced color composition, but this is impossible, since dominoes cover one of each color.
[/hide]
[/hide]

The first two parts look good. The hamster will get confused when it runs into the middle of a tasteful block- remember, those are really just the same as distasteful blocks except for coloring. That idea also needs an argument that there are no tasteful blocks inside.

Ahh, but it misses all of those because of how rhythmically it is running. If you set the first step correctly, it should exactly be a question of whether there is a distasteful block obstructing it every time, and there should be no problems.

I see now. The specific fix: go horizontally if the tile to the upper right is shaded, and vertically if it's unshaded. You can enter the middle of a distasteful block that way, but not a tasteful block.

[quote="Yongyi781"]Lol hamsters... if only I had the liberty not only to write a boilerplate proof in the given time but also to add humor to it...[/quote]Well, we're not working in real time here. The last time I actually competed in the USAMO was 2000, and I first saw these problems Thursday morning.

[quote="azjps"]We define a [i]chessboard polygon[/i] to be a polygon whose sides are situated along lines of the form $ x \equal{} a$ or $ y \equal{} b$, where $ a$ and $ b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles. Finally, a [i]tasteful tiling[/i] is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $ 3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

[asy]size(100); pathpen = linewidth(2.5);
void chessboard(int a, int b, pair P){
 for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j)
  if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6));
 D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle);
}
chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12));

/* draw lines */
D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy] a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.[/quote]

Can any chessboard polygon with even size bigger or equal to 4 be tiled uniquely tastefully?

A polygon in the shape of a "T" Tetris piece can't be tiled with dominoes at all.

Weirdly, a shape consists of a 3*3 square without the central square doesn't have unique tiling.

AAC
B  C
BDD

BAA
B  C
DDC

I don't think this is a polygon in strict definition. But obviously any correct proof needs to address this.(i.e. contains some argument regarding to no "holes" inside) Anyone notice this?

The assumption that the polygon has no internal gaps is critical to the proofs that do "suppose there are two tilings, take a 'cycle' of dominoes on which they differ, and get a contradiction using the interior."

Here's (hopefully?) another proof for uniqueness. (I'm sure it's similar in spirit to other things above, so sorry for reviving if it's a bit redundant. Most of it is just setting up for the last few paragraphs.)

[hide]Suppose otherwise, and take a minimal counterexample $G$ (with $\ge 2$ nonempty tasteful tilings).

Consider any corner $v$ (WLOG lower left with only upper and right neighbors and facing [b]outside[/b] the interior of the polygon) bordered above and to the right by $u,w$ respectively, so either $vu$ or $vw$ is a domino; also let $v'$ denote the square to the upper right of $v$. If $G\setminus\{v,u\}$ cannot be tiled (with dominoes), then every tiling of $G$ must contain $vw$, and so $G\setminus\{v,w\}$ must have at least two tasteful tilings (by removing $vw$ from the tasteful tilings of $G$), contradicting the minimality of $G$. Hence (by symmetry) $G\setminus\{v,u\}$ and $G\setminus\{v,w\}$ can both be tiled, whence they each have their own [b]unique[/b] tasteful tiling by part (a) and the minimality of $G$. (*)

Now consider the two (distinct) tasteful tilings of $G$ corresponding to $vu$ and $vw$ (as determined in (*)). Overlaying them as in previous posts and considering cycles/loops, $G$ must consist of (by minimality of $G$) a boundary cycle $\mathcal{B}$ (with an even number of squares and including the boundary of the actual polygon) composed of two disjoint tilings ("1 mod 2 shifts" of each other) and an interior $\mathcal{I}$ composed of fixed dominoes (i.e. the same for the two tilings).

Because $u,v,w\in\mathcal{B}$ and the corner $uvw$ faces outside the polygon, we need $v'\in G$ in order to reach $v,w,u$ in this order along the (boundary) path. We can show that $G\setminus\{u,v,w,v'\}$ cannot be tiled (this is of course also true if $v$ is any corner, not necessarily a lower left one). (**) Indeed, suppose to the contrary that it can be tiled, so it has a unique tasteful tiling by minimality. We assume WLOG by symmetry about the line $y=x$ (in regards to the distasteful configurations) that $v$ is black. Now note that adding $wv'$ (which is a vertical white-black domino, viewed from bottom to top) to the tasteful tiling of $G\setminus\{u,v,w,v'\}$ yields a tasteful tiling of $G\setminus\{u,v\}$ itself (since the only distasteful configuration $wv'$ can be part of is $\{vu,wv'\}$, and $u,v$ are not in $G\setminus\{u,v\}$), which must in turn be unique by minimality. Thus we must get the unique tasteful tiling of $G\setminus\{u,v\}$ (which must contain domino $wv'$!) when we remove domino $vu$ from the unique tasteful tiling of $G$ containing $vu$, contradicting the fact that $\{vu,wv'\}$ is a distasteful configuration.

Consider the smallest real $r$ such that $a+b=r$ for the center $(a,b)$ of some square in $G$ (which must be in $\mathcal{B}$). By the minimality of $r$, the boundary path (made of B's in the diagram below, with $(a,b)$ somewhere in the middle) must zigzag along the line $x+y=r$ until it "leaves" (it loops eventually, so it must) for the first time at $B_i$ on the left and $B_f$ on the right. Clearly $B_f$ is either above or to the right of $B_l$, and if it's above $B_l$, then there exists a tiling of $G$ with dominoes $B''B'$ and $B_lB_f$, contradicting (**) if we take $u=B'$, $v=B''$, $w=B_l$, and $v'=B_f$ (i.e. for the corner at $B''$). Hence $B_f$ is to the right of $B_l$, and similarly, $B_i$ is above $B_u$. Thus we have, for some $k\ge 0$, a sub-configuration in $G$ of the form
[code]B_i Z
B_u X_0 Y_0
B   B   X_1 Y_1
    B   B   X_2 Y_2
        ...
            B   B'  X_k Y_k
                B'' B_l B_f[/code]resting along the line $x+y=r$ (some squares may not be in $G$; note that all the B's in this diagram form a complete subsection of the boundary path).

Note that $X_kY_k$ is not a fixed interior domino, or else $X_kY_k$, $B_lB_f$, and $B'B''$ are all dominoes in the same tiling (one of the two tasteful ones mentioned in (*)), whence tiling instead by $B'B''$, $X_kB_l$, and $Y_kB_f$ yields that $G\setminus\{B',B'',B_l,X_k\}$ can be tiled, contradicting (**) (as before, for the corner at $B''$). Similarly, $X_0Z$ is not a fixed interior domino.

If one of $X_0,X_k$ lies in $\mathcal{I}$, WLOG $X_0$ (by symmetry about $y=x$), then we show by induction that $X_jY_j$ is a fixed interior domino for $0\le j\le k$ and $X_{j+1}$ is in the interior (for $0\le j\le k-1$). For the base case, we see that $X_0Z$ cannot be a domino (by the previous paragraph), so $X_0Y_0$ is a domino, which forces $Y_0\in\mathcal{I}\implies X_1\not\in\mathcal{B}$ (if $k\ge 1$; this is because every boundary square has two neighbors in the boundary path). Then, assuming the inductive hypothesis for some $1\le j\le k$, $X_j$ must belong to a domino (since it's in the interior). Yet $X_jY_{j-1}$ cannot be a domino since $X_{j-1}Y_{j-1}$ is already a fixed (interior) domino, so $X_jY_j$ must be a domino and $X_{j+1}\not\in\mathcal{B}$ (as long as $1\le j\le k-1$; again, this is because every boundary square has two neighbors in the boundary path), completing the inductive step. But then $X_kY_k$ is a fixed interior domino, contradicting the previous paragraph again.

Otherwise, if $X_0,X_k\in\mathcal{B}$, then in order for us to traverse $B_i,X_0,B_f$ (in this order) along the boundary, $X_0$ must appear before $Y_0$, and so $B_u,B_i,Z,X_0$ must appear on the boundary in this order. Thus $B_iB_u$ and $ZX_0$ are dominoes in the same tasteful tiling of $G$, so $B_i$ must be black (to avoid a distasteful configuration). Analogously (for $X_k$), $B_f$ must be white, contradicting the fact that $B_iX_0X_1\ldots X_kB_f$ lie on a diagonal and therefore all have the same color.

[b]Edit:[/b] It seems that the official solution also uses extremal stuff and orientations, but in a much cleaner way (the issue seems to be that I tried to forget about the tasteful part after part (a), working with an equivalent statement that didn't contain anything about tastefulness... I guess I should not do this in the future, at least during tests).[/hide]

[b]Edit:[/b] OK so I was looking at [url=http://en.wikipedia.org/wiki/Domino_tiling#Thurston.27s_height_condition]these necessary and sufficient conditions for domino tilings to exist[/url] (since I thought they could simplify my roundabout way above), and it seems that Thurston's height function (which applies to chessboard polygons here; see section 4 [url=http://www.cimat.mx/ciencia_para_jovenes/pensamiento_matematico/thurston.pdf]here[/url]) provides a very natural setting for this problem (it's pretty close to what [b]probability1.01[/b] did, but I guess more unified), since it embodies the notion of path orientation really well (in any path with height changing $+1\pmod{4}$ from one vertex to the next, the color of the square on the left remains the same).

The idea is that if we set the height function to be 0 at some arbitrary point on the boundary, then there's a unique "maximal" tiling, which must be tasteful. For more details, refer to [url=ftp://ftp.ens-lyon.fr/pub/LIP/Rapports/RR/RR1999/RR1999-25.ps.Z]this paper[/url], which also explores a lot further (if you can't access it most of the ideas are [url=http://math.stackexchange.com/a/36109]here[/url]).

[hide="EDIT: Oops I misread the problem, this only works for rectangles"]
Easy stuff: A $a \times b$ rectangle can be tiled by dominoes if and only if $a$ is even or $b$ is even.
[hide="Existence"]

Suppose $a,b$ are both even

We use induction on $ab$. Our base case will be $ab = 0$. For the inductive step, suppose the top left corner is white. (If not, we can rotate the entire rectangle by 90 degrees.) We can tile the top and bottom rows. Now we can ignore them. We are left with a smaller rectangle, so we are done in this case.

Now suppose WLOG $a$ is odd, $b$ is even

Rotate the rectangle such that the top row has an even number of squares.
Suppose the top left corner is white. (If not, we can rotate the entire rectangle by 180 degrees.) Now we tile the top row. Now we can ignore the top row. We are left with a smaller rectangle which has both side lengths even, QED.

[/hide]

[hide="Uniqueness"]

Lemma: Let $X$ be a white square in the top row. Then in any tasteful tiling, the domino which contains $X$ must be horizontal.

Proof. Suppose not. Then the idea is that you get an infinite string of dominoes moving down and to the right, and that this string cannot be truncated cleanly. I think this idea is present in above posts

Now suppose $a,b$ are both even. We use induction. There is only one tasteful tiling when $a=0$ or $b=0$. For the inductive step, we can assume the top left corner is white (as noted above). Then the top row must be tiled with horizontal dominoes. Similar remarks apply to the bottom row. Then there is a smaller rectangle remaining which has a unique tiling.

Suppose $a$ is odd, $b$ is even. We can assume that the top row has an even number of squares, and that the top left corner is white. The top row must be tiled with horizontal dominoes. We are left with a smaller rectangle with both side lengths even, QED.

[/hide]

[/hide]

@mathcool2009: the chessboard polygon need not be a rectangle.

Here is the proof of (a) from the official solutions, by induction: let $\mathcal P$ denote the chessboard polygon which can be tiled by dominoes.

Consider a [i]lower-left[/i] square $s$ of the polygon, and WLOG is it black (other case similar). Then we have two cases: [list] 	[*]If there exists a domino tiling of $\mathcal P$ 	where $s$ is covered by a vertical domino, 	then delete this domino and apply induction 	on the rest of $\mathcal P$. 	This additional domino will not cause any distasteful tilings.

[*]Otherwise, $s$ is covered by a horizontal domino. 	Again delete this domino and apply induction 	on the rest of $\mathcal P$. 	The resulting tasteful tiling should not 	have another horizontal domino adjacent to the 	one covering $s$, because otherwise 	we could have replaced that $2 \times 2$ square 	with two vertical dominoes to arrive in the first case. 	So this additional domino will not cause any distasteful tilings. [/list]

Here is my proof of (b): Suppose for contradiction there are two distinct tasteful tilings. Overlaying the two tilings on top of each other induces several [i]cycles[/i] of overlapping dominoes at positions where the tilings differ.

Henceforth, it will be convenient to work with the lattice ${\mathbb Z}^2$, treating the squares as black/white points, and we do so. Let $\gamma$ be any such cycle and let $s$ denote a lower left point, and again WLOG it is black. Orient $\gamma$ counterclockwise henceforth. Restrict attention to the polygon $\mathcal Q$ enclosed by $\gamma$ (include points of $\gamma$ as part of the tiling).

In one of the two tilings of $\mathcal Q$, $s$ will be covered by a horizontal domino; in the other tiling $s$ will be covered by a vertical domino. We focus on the latter one. Observe that we now have a set of dominoes along $\gamma$, such that $\gamma$ points from the white point to the black point within each domino.

Now impose coordinates so that $s = (0,0)$. Consider the stair-case sequence of points $p_0 = s = (0,0)$, $p_1 = (1,0)$, $p_2 = (1,1)$, $p_3 = (2,1)$, and so on. By hypothesis, $p_0$ is covered by a vertical domino. Then $p_1$ must be covered by a horizontal domino, to avoid a distasteful tiling. Then if $p_2$ is in $\mathcal Q$, then it must be covered by a vertical domino to avoid a distasteful tiling, and so on. We may repeat this argument as long the points $p_i$ lie inside $\mathcal Q$. (See figure below; the staircase sequence is highlighted by red halos.)

Let $x$ denote the first point of this sequence after $p_1$ which is on $\gamma$, and WLOG that point is white (black case is similar). Let $y = p_1 = (1,0)$ so the line segment $\ell$ joining $xy$ has slope $1$ (in the black case use $y=(0,0)$ instead).

Now $x$ is tiled by a vertical domino whose black point is to the right of $\ell$. But the line segment $\ell$ cuts $\mathcal Q$ into two parts, and the orientation of $\gamma$ has this path also entering from the right. This contradicts the fact that the orientation of $\gamma$ points only from white to black within dominoes. This contradiction completes the proof.

:o :o :o @v_Enhance how do you make those cool diagrams

[quote=awang11]I'm confused, isn't the first one a "distasteful tiling" as well?[/quote]

No, the color of the squares matters in the definition of the two illegal configurations.

[quote=Kalymat]hello everyone,
  I am new in this program. I love math a lot and i'm pretty good at it...sometimes. Can anyone please explain the question to me. I was lost. If a polygon is a closed figure why are it's sides situated on lines that pass through the interior of said polygon. and if it divides into unit suares why do i see 1x2 rectangles 9white and grey)?[/quote]

If you are new to olympiads I would not recommend starting with a 45m problem

An unsolved idea. For each domino, place an arrow pointing from white to black, so the bad $2\times 2$ squares are all counterclockwise.


inequalities
algebra
polynomial
calculus
inequalities proposed

Let $a,b,c,d>0$ be real numbers for which $a^2 + b^2 + c^2 + d^2 = 1$. Prove that the following inequality holds: $(1-a)(1-b)(1-c)(1-d) \geq abcd$

Divide both sides by abcd. You get:
$\frac{1-a}{a}\frac{1-b}{b}\frac{1-c}{c}\frac{1-d}{d} \geq 1 \Longleftrightarrow \sqrt[4]{\frac{1-a}{a}\frac{1-b}{b}\frac{1-c}{c}\frac{1-d}{d}} \geq 1$.
Now from GM-HM we have: $\sqrt[4]{\frac{1-a}{a}\frac{1-b}{b}\frac{1-c}{c}\frac{1-d}{d}} \geq \frac{4}{\frac{a}{1-a}+\frac{b}{1-b}+\frac{c}{1-c}+\frac{d}{1-d}}$. So we only need to prove that $\frac{4}{\frac{a}{1-a}+\frac{b}{1-b}+\frac{c}{1-c}+\frac{d}{1-d}} \geq 1 \Longleftrightarrow \\ \frac{a}{1-a}+\frac{b}{1-b}+\frac{c}{1-c}+\frac{d}{1-d} \leq 4 \Longleftrightarrow \\ -(\frac{a}{a-1}+\frac{b}{b-1}+\frac{c}{c-1}+\frac{d}{d-1}) \leq 4 \Longleftrightarrow \\ -(1+\frac{1}{a-1}+1+\frac{1}{b-1}+1+\frac{1}{c-1}+1+\frac{1}{d-1}) \leq 4 \Longleftrightarrow \\ \frac{1}{a-1}+\frac{1}{b-1}+\frac{1}{c-1}+\frac{1}{d-1} \geq -8$.
 I was tempted to mess around with some polynomials and calculus here (convexity and the like), but gave it up. But there is another method here for sure, since the inequality is really nice  :)

This problem had been posted here many time. It's even in Old and New Inequality. I sure that there's somthing wrong in Neworder Solution.

Yes, there's an error in my solution  :( If it's possible, I'll try to fix it.

Well, I give up - I thought it would be possible to prove the last one (with -8) using Jensen ($x=a^{2}, f(x)=\frac{1}{sqrt{x}-1}$, but the finction isn't always convex.


Consider a rectangular grid of $ 10 \times 10$ unit squares. We call a [i]ship[/i] a figure made up of unit squares connected by common edges. We call a [i]fleet[/i] a set of ships where no two ships contain squares that share a common vertex (i.e. all ships are vertex-disjoint). Find the greatest natural number that, for each its representation as a sum of positive integers, there exists a fleet such that the summands are exactly the numbers of squares contained in individual ships.

The maximum is $ 25$
if $ m > 25$ then there is no fleet for the partition $ 1 \plus{} 1 \plus{} \cdots \plus{} 1 \plus{} 1 \equal{} m$,
by partitioning the grid on $ 25$ non overlapping $ 2x2$-squares and with only one ship on each square.

For any other partition of $ 25$ match some of those squares and paint the resulting ship.

Moreover for any $ 2k$x$ 2m$ grid the maximum is $ km$


Duke college Columbia AMC AIME ARML MATHCOUNTS

Here is what I have for SC/NC that I know of:

[url=http://ahsimc.com/]AHSIMC[/url] Sept. 13, 2004
[url=http://www.math.duke.edu/dumu/]Duke Math Meet[/url] October 30, 2004
USC Aiken - Nov 22, 2004
Winthrop-Wylie Mathematics Competition Nov 22, 2004
[url=http://www.math.sc.edu/contest]USC Columbia[/url]-Jan 29, 2005
[url=http://www.unl.edu/amc/]AMC 10/12[/url] Feb 1 and/or Feb 16, 2005
[url=http://www.math.armstrong.edu/tournaments/hstournament.html]Armstrong Atlantic State University[/url] (in Georgia) Feb 19, 2005
[url=http://155.225.48.46/highcomp/2004stuf/2004.htm]Citadel[/url]- a few Wednesdays in February I believe
[url=http://math.cofc.edu/mathmeet/default.php]College of Charleston Math Meet[/url] Feb 26, 2005
[url=http://www.unl.edu/amc/]AIME[/url] March 8 or 22, 2005
[url=http://math.furman.edu/tournament/tournament.html]Furman Wylie Math Tournament[/url] March 19, 2005
Quest  (in Charleston) I think this is around March/April
[url=http://www.coastal.edu/mathlab/contest.html]Coastal Carolina[/url]-  April 1, 2005
[url=http://www.arml.com/]ARML[/url] June 3/4, 2005
[url=https://math.uww.edu/mathmeet/index.htm]UW-Whitewater/UT-Dallas Middle/High School Mathematics Meet[/url]  April 14, 2005

[url=http://192.154.43.167/goebel/statecon/state.htm]North Carolina State Mathematics Contest[/url] Various (look on site)
[url=http://www.natassessment.com/]National Assessment and Testing[/url] Various (look on site)
[url=http://www.mualphatheta.org/index.htm]Mu Alpha Theta[/url] Various (look on site)
[url=http://www.mandelbrot.org/]Mandelbrot[/url] Various (look on site)
[url=http://www.mathleague.com/]Math League[/url] Various (look on site)
[url=http://www.asan.com/asa/asma1.htm]American Scholastic[/url] Various (look on site)
[url=http://neverland.ncssm.edu/~morrison/mathContests/atlanticPacific.html]Atlantic-Pacific Math Contest[/url] Various (look on site)

If you know of some math competitions that you go to please feel free to post here.  For those times I just put what I remember.  Most of them have confirmed dates so if you are interested ask and I ll give you the exact date.

[I'm still working on/updating this page.]

Duke Math Meet, NC State Math Contest (and qualifying regionals). Pfft, I do think that's it for me. Maybe with a bit of luck I can go back to CofC

Actually, since I'm starting/running a math club at my school, competition ideas would be helpful (both local and not). This year we did AHSIMC (21st!!), Mandelbrot, and the Duke Math Meet, and hopefully we'll also do the NC State Math Contest. Next year I hope to also do Atlantic-Pacific, Math League, and that ARML Power Round-ish thingy.

I was thinking of perhaps trying to get a small group together to go to another local competition. So which one would you all suggest?

Also, what would you suggest for getting money. My current plan is: a) pester the principal b) call all the companies in Research Triangle Park in alphabetical order. Given that I only several hundred, I think this will be sufficient, but what would be a good plan c)?

Any sage advice?

Enloe HS students have started a new middle school math contest called NEMO.  This is suppose to be similar to mathcounts with addition area like national masters round.

for info:

nemosupport@gmail.com

joe, you forgot USAMO....there's this one kid at my school who probably made it this year. he's a bit weird and possibly anorexic, also likes to run alot.

[quote="joml88"]David, there is a dfiirence between thin and anorexic.  The former apples to people who aren't fat.  The latter applies to people who almost never eat.  A peson can eat a LOT and still be skinny (like me).  And I think the last part of your comment would explain why I am thin even though I eat a lot i.e. I run a lot.[/quote]
jeeze, i was just kidding. you always borrow money from me to eat; i know you're not anorexic. i guess it wasn't [i]funny[/i].

Yet Another Competition: [url=http://www.math.ncsu.edu/undergrad/ncsu_contests/]Todd Fuller[/url]. It's only for seniors in Wake County, though.


A bell rings every 2 hours, a second bell rings every 3 hours, and a third bell rings every 4 hours. If all 3 bells ring at 9:00 AM., at what time will all 3 bells next ring?

We want $\text{lcm}(2,3,4)=12$, so the next time will be at 9 PM.

[quote="Interval"]Great to know the answer BUT HOW did you get it?

I post questions to learn HOW TO solve questions on my own, see?[/quote]

Well your question is basically asking that when will the next 3 bells ring at the same time. Do solve this, you must recognize this question as a least common multiple question. Meaning that you will find the least common multiple that rings from 2,3, and 4 hours.

Of course you can also map the whole thing out but the $\text{lcm}$ is easier.

Generally, for these problems, you simply take the least common multiple.

More problems to try:
1. Planet X revolves once around its star every 4 Earth years, Planet Y revolves once every 5 years, and Planet Z revolves every 12 years. If the star and the 3 planets were collinear, in order, 2 years ago, how long will it be till this occurs again?

2. 3 people, A, B, and C, are running around a mile long circular track. Person A is running at 10 mph, Person B runs at 5 mph, and Person C runs at 6 mph. If they all begin to run at the same time at the same place in the same direction, how long will it be till the next meeting of all three?

Thank you for the great replies.

Thank you for the extra similar questions.

However, the EXTRA QUESTIONS do not give a time when the events began.

In that case, how can I, after finding the LCM, know the [next time] for the two posted questions?

When a problem asks when the next time is without giving an original time, they usually mean how much time until whatever it is occurs. If I say that I to church every seven days, and I went to church on sunday, when will be the next time I go to church? next sunday. But if I am now at church, when will I be at church next? the question doesn't specify when 'now' is so you just say 7 days 'from now', whenever now is.

btw I'm not in church now.


function
ratio
arithmetic sequence
geometric sequence

[quote="PPonte"]I started the study of sequences some days ago and I am searching for tricks, hints, that could help me find the general term of a sequence. I am following the strategy of drawing the points of the sequence and then I try to find the expression of a function that contains those points. But, unfortunately, this is not helping me with the sequence I am dealing now. Would you please tell me your strategies/tricks?

Thank you.  :lol:[/quote]

one important things is, for example, to find the nth number of a sequence. Do you know how to do that?

[quote]one important things is, for example, to find the nth number of a sequence. Do you know how to do that?[/quote]

That's exactly for what I am looking tricks.

An important thing to memorize are the formulas for the $n^{th}$ term of a geometric and arithmetic sequence. Also, the formula for an infinite geometric sequence. Lastly, the formulas for the sum of a finite geometric and arithmetic sequence.

Moreover, know how to recognize the basic telescoping series. Lastly, know how to recognize patterns to help you evaluate the series. For examples, multiplying the sum by 2 and then subtracting it from the original sum and see if you can eliminate some portions ($2S-S$).

nth term of an arithmetic sequence: a1 + (n-1)d where d is the difference of a1 and a2
nth term of an arithmetic sequence: a1 * (r^(n-1)) where r is the ratio

example: find the 4th term of the arithmetic sequence 1..3...5...
answer: 1 + (3*2) = 7
example: find the 4th term of the geometric sequence 1...1/2...1/4...
answer: 1 * (1/2^3) = 1/8

sum of an arithmetic sequence: (a1 + an)(n)/2
sum of a geometric sequence: a(1-(r^n)/1-r or something, cant remember specifically

The basic sequences like arithmetic,geometric,harmonic have to be memorised or you could derive them whenevr you want.They are helpful for other series as well like the arithmetico geometrico series.

Many times for the nth term,you have to basically notice the way the terms are progressing and then evaluate the sigma thing(if ur finding sum or something)

Theres another way to find the nth term which works almost everytime(might be tedious sometimes but is important if you can't cleverly find the nth term) this is the [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=Fun+story+problem&t=74937]link[/url] to what i'm talking about.

And there are some tricky ways lke what surge said.......And if you are finding sum and stuff,telescoping helps a lot.


Asymptote
LaTeX
calculus
derivative
linear algebra
matrix
articles

Is there any way to label points on an Asymptote picture with matrices?

Asymptote understands only the basic $ \text{\LaTeX}$, so you often cannot use any "derivative" environments like \begin{matrix}, \begin{aligned}, or even \text. Instead you have to resort (in the matrix case) to the tabular environment, which works just fine:
[asy]size(200);
dot((0,0)); dot((1,1)); draw((0,0)--(1,1));
label("$\left[\begin{tabular}{cc}
1 & 2
\\
3 & 4
\end{tabular}\right]$",(0,0),S,fontsize(8));
label("$\left[\begin{tabular}{cc}
5 & 67
\\
89 & 0
\end{tabular}\right]$",(1,1),N,fontsize(8));[/asy]

I consulted with people who know Asymptote better than I and was told that you can teach the Asymptote to recognize various commands from $ \text{\LaTeX}$ packages by including the usepackage() command into your code. The one needed for matrices is amsmath, so you can do this:
[asy]size(150);
usepackage("amsmath");
pair A=(0,0), B=(1,1);
draw(A--B); dot(A);
label("$\begin{pmatrix}x&y\\z&t\end{pmatrix}$",A,S);[/asy]

I used one of the example "asis"
[code]\documentclass{article}
\usepackage[pdftex]{graphicx}
\usepackage{asymptote}
\begin{document}
 \begin{asy}
size(200);
dot((0,0)); dot((1,0)); draw((0,0)--(1,1));
label("$\left[\begin{tabular}{cc} 1 & 2 \\
3 & 4 \end{tabular}\right]$",(0,0),S,fontsize(8));
label("$\left[\begin{tabular}{cc} 5 & 67 \\
89 & 0 \end{tabular}\right]$",(1,1),N,fontsize(8));
\end{asy}
\end{document}[/code]

and could run it successfully on my Microsoft Windows system after having real struggle with all kind of Ghosts.

Now I modified the above running file to :
[code]\documentclass{article}
\usepackage[pdftex]{graphicx}
\usepackage{asymptote}
\begin{document}
 \begin{asy}
 size(200);
dot((0,0)); dot((1,0)); draw((0,0)--(1,0));
\end{asy}
\end{document}[/code]

and it gives me error message "test1_1.pdf does not exist on input line 8."

Am I missing something?

help will be appreciated.

 :huh:
inoit.

[asy]size(200);
dot((0,0)); dot((1,0)); draw((0,0)--(1,1));
label("$\left[\begin{tabular}{cc} 1 & 2 \\
3 & 4 \end{tabular}\right]$",(0,0),S,fontsize(8));
label("$\left[\begin{tabular}{cc} 5 & 67 \\
89 & 0 \end{tabular}\right]$",(1,1),N,fontsize(8));[/asy]

Hmm... It seems to work here. (I just copied your code) Maybe you are missing a package on your TeXnic center.

One problem is that Asymptote often goes nuts if the picture is one-dimensional as yours, especially when it is executed in batch mode. So, the first thing to try is to add dot((1,1)); to your code and see if it works after that. If not, what are the Asymptote error messages you are getting?


find all real solutions:
$ x^2 \plus{} y^2 \equal{} z^2$

are you sure it's real? it's too easy: $ (x,y,\pm\sqrt{x^2\plus{}y^2})$

if $ x,y,z$ are integers, the solutions are $ (m^2\minus{}n^2,\pm 2mn,\pm(m^2\plus{}n^2))$ (it is the well-known pythagorean triple)

[quote="aadil"]i thought it was a tough problem?[/quote]
m and n are to be amicable numbers by the way...

[quote="t0rajir0u"]I'm not sure what that's a translation of, but [url=http://en.wikipedia.org/wiki/Amicable_number]amicable number[/url] means something quite different in English.  The condition that guarantees uniqueness is that $ (m, n) \equal{} 1$ and exactly one of $ m, n$ is even.[/quote]
dont amicable numbers mean no.s with opposite parity??

The integer solutions to this equation are [[Pythagorean triples]].


abstract algebra
superior algebra
superior algebra unsolved

Show every abelian extension of Q is contained in (some)cyclotomic extension. :roll:

http://en.wikipedia.org/wiki/Kronecker-Weber_theorem

look up the proof, it's very long :-P

am attaching sol. i found some time back on net.really elegant!


how far do you think that the raptors will make it this year in the play-offs? There already down 2-0, but I think that they can make a comback. Anyone else watching them?

ya, the pistons are gona win this year
Boston ruined hawks!! go Boston


find the sum of the roots of the equation $\left( {x^2 - 3x} \right)^2 - \left( {3x^2 - 9x} \right) = 4$

[hide]After simplifying the expression, you get $x^4-6x^3+6x^2+9x-4=0$.

Then, you apply the factor theorem etc. and you get $(x-4)(x+1)(x^2-3x+1)=0$

From the last factor ($x^2-3x+1$), you don't need to find the roots because the sum is $3$, so $4-1+3=\boxed{6}$[/hide]

Solution:

[hide]Factoring out a 3 in the second term and replacing x^2-3x with y,

y^2-3y-4=0

This factors to:

(y-4)(y+1)=0

Plug x^2-3x back in,

x^2-3x+1=0 and
x^2-3x-4=0

The sum of the roots of these two separate equations are 3 and 3.

Thus the total is [b]6[/b][/hide]


geometry
AwesomeMath
summer program
MathZoom
Ross Mathematics Program
PROMYS
MathPath

Is there a big post somewhere on the site comparing different math camps and aops users experiences with them?

Is there a guide somewhere for deciding which math camp to ship your kids off to?

There's no grand-daddy post, but http://www.artofproblemsolving.com/Forum/viewtopic.php?t=183359 has some good information.

Where to go? When you consider the most popular camps, it's rarely a matter of quality differences. Each one has a different kind of intent. You should first figure out what experience you're looking for, and then look closer at the camps available in that area, since each one handles things like leisure time differently.

Here's one way to look at them.

[b]Contest Preparation[/b] - You'll largely learn problem solving techniques that will bring up your AMC/AIME/USAMO scores.
-- AwesomeMath
-- Mathzoom?
-- MOP

[b]Guided Exploration[/b] - You'll probably study only one topic for the duration, and outside instruction is minimal. Much of what you learn comes from your own effort.
-- Ross
-- PROMYS
-- RSI

[b]Classes in Higher Math[/b] - You're given a wide variety of classes on college-level topics. You can get a wide exposure, although there are generally opportunities to go deep into one subject.
-- Mathpath (middle school only)
-- Mathcamp
-- HCSSiM?

(Disclaimer: This is from my perception alone and not guaranteed to be accurate. There are probably a lot of good camps that I missed, also.)


Kathy ran up a hill at 4 miles per hour and down the same hill at 6 miles per hour. How many miles per hour was her average speed? Express your answer as a decimal to the nearest tenth.

find the geometric mean?

sqrt(4x6) = 2sqrt6

2sqrt6 = approx. 4.9

idk if this is right.

Suppose the distance is 1 miles.
Total time is: $ \frac {1}{4} \plus{} \frac {1}{6} \equal{} \frac {5}{12}$
Average speed = $ \frac {Distance}{Time} \equal{} 2: \frac{5}{12} \equal{} \boxed{4.8}$

HArmonic mean actually $ \frac{2\times{4\times{6}}}{4\plus{}6}\equal{}\frac{48}{10}\equal{}4.8$


Putnam
floor function
logarithms
calculus
integration
function
induction

Let $ x_0 \equal{} 1$ and for $ n\ge0,$ let $ x_{n \plus{} 1} \equal{} 3x_n \plus{} \left\lfloor x_n\sqrt {5}\right\rfloor.$ In particular, $ x_1 \equal{} 5,\ x_2 \equal{} 26,\ x_3 \equal{} 136,\ x_4 \equal{} 712.$ Find a closed-form expression for $ x_{2007}.$ ($ \lfloor a\rfloor$ means the largest integer $ \le a.$)

The general form is

$ x_n = \frac1{2\sqrt {5}}[(2 + \sqrt {5})(3 + \sqrt {5})^n + (\sqrt {5} - 2)(3 - \sqrt {5})^n].$

So in particular,

$ x_{2007} = \frac1{2\sqrt {5}}[(2 + \sqrt {5})(3 + \sqrt {5})^{2007} + (\sqrt {5} - 2)(3 - \sqrt {5})^{2007}].$

Here's the proof, by induction. This works for $ n = 0.$ Assume it works for $ x_n.$

$ x_n\sqrt {5} = \frac12[(2 + \sqrt {5})(3 + \sqrt {5})^n + (\sqrt {5} - 2)(3 - \sqrt {5})^n]$

We claim that $ u_n = \frac12[(2 + \sqrt {5})(3 + \sqrt {5})^n + (2 - \sqrt {5})(3 - \sqrt {5})^n]$ is an integer.

We see that by multiplying it out by the binomial theorem; all of the terms with $ \sqrt {5}$ cancel out, and all of the other terms double, so that when divided by 2, they make integers.

$ x_n\sqrt {5} - u_n = (\sqrt {5} - 2)(3 - \sqrt {5})^n,$ and this is between $ 0$ and $ 1.$

Hence, $ \lfloor x_n\sqrt {5}\rfloor = u_n.$

After sufficient manipulative algebra, we can show that

$ 3x_n + u_n = \frac1{2\sqrt {5}}[(2 + \sqrt {5})(3 + \sqrt {5})^{n + 1} + (\sqrt {5}-2)(3 - \sqrt {5})^{n + 1}]$

My path to discovering this was quite circuitous. I was concentrating on $ (3 + \sqrt {5})^n - x_n$ which is:

$ 3 + \sqrt {5} - x_1 = \sqrt {5} - 2$

$ (3 + \sqrt {5})^2 - x_2 = 6\sqrt {5} - 12$

$ (3 + \sqrt {5})^3 - x_3 = 32(\sqrt {5} - 2)$

${ (3 + \sqrt {5})^4 - x_4} = 168(\sqrt {5} - 2)$

At that point, I actually hand-calculated $ x_5 = 3728$ to get

$ (3 + \sqrt {5})^5 - x_5 = 880(\sqrt {5} - 2).$

Eventually I realized what the numbers $ 1,6,32,168,880$ were: if you write $ (3 + \sqrt {5})^n = a_n + b_n\sqrt {5},$ they're $ b_n.$

Eventually this worked around to the formula you see above.

$ x_{2007}$ is quite large, of course. Using a calculator (and logarithms), I estimate it as $ 1.047\times 10^{1443}.$

A similar way to do this is to define the sequences (of integers)
\[ a_n \equal{} \frac {\left( 3 \plus{} \sqrt {5}\right)^n \plus{} \left( 3 \minus{} \sqrt {5}\right)^n}{2}
\]

\[ b_n \equal{} \frac {\left( 3 \plus{} \sqrt {5}\right)^n \minus{} \left( 3 \minus{} \sqrt {5}\right)^n}{2\sqrt {5}}
\]
(you can show they satisfy nice linear recurrences to prove they're integral) and then prove $ x_n \equal{} a_n \plus{} 2b_n$ by induction. ($ a_n$ and $ b_n$ are chosen to satisfy $ a_n\plus{}b_n\sqrt{5}\equal{}\left( 3\plus{}\sqrt{5}\right)^n$, so the pattern was noticeable quickly.)

To deal with the floor function in the inductive step, we have $ x_n\sqrt {5} \equal{} 5b_n \plus{} 2a_n \plus{} \left( \sqrt {5} \minus{} 2\right) \left( 3 \minus{} \sqrt {5}\right)^n$. Since $ a_n,b_n$ integers and $ 0\leq \left( \sqrt {5} \minus{} 2\right) \left( 3 \minus{} \sqrt {5}\right)^n < 1$, we get $ \left\lfloor x_n\sqrt {5}\right\rfloor \equal{} 5b_n \plus{} 2a_n$. The rest is algebraic computation.

In hindsight, the first tactic to try should've been to replace the given recursion with a simpler one.  The floor function and radical are reminiscent of second-order linear recurrences, so that's a good guess.  The simpler recursion is given by $ x_{n \plus{} 1} \equal{} 6x_n \minus{} 4x_{n \minus{} 1}$ by calculation on the first four terms given.  With a numerical value of $ x_5$ handy, this conjecture would be strongly supported, especially as $ \sqrt{5}$ occurs in the closed-form of the recursion above.

Let $ r_n \equal{} \left\lfloor x_n \sqrt{5} \right\rfloor$. Since $ x_n \in Z$, $ x_n \sqrt{5} \notin Z$ so $ r_n < x_n \sqrt{5} < r_n \plus{} 1$. From here I tried to find a recurrence for $ r_n$ in terms of the rest by examining $ x_{n\plus{}1} \sqrt{5} \equal{} 3x_n \sqrt{5} \plus{} r_n \sqrt{5}$. As it turns out $ r_{n\plus{}1} \equal{} 3r_n \plus{} 5x_n$. It is easy:
$ (x_n \sqrt{5} \minus{} r_n) > 0; (3 \minus{} \sqrt{5})(x_n \sqrt{5} \minus{} r_n) > 0 \Rightarrow 3r_n \plus{} 5x_n < 3x_n \sqrt{5} \plus{} r_n \sqrt{5}$ and  $ (x_n \sqrt{5} \minus{} r_n) < 1 < \frac{1}{3 \minus{} \sqrt{5}} \Rightarrow (3 \minus{} \sqrt{5})(x_n \sqrt{5} \minus{} r_n) < 1 \Rightarrow 3x_n \sqrt{5} \plus{} r_n \sqrt{5} < 3r_n \plus{} 5x_n \plus{} 1$. Thus we have $ x_{n\plus{}1} \minus{} 3x_n \equal{} r_n \Rightarrow x_{n\plus{}2} \minus{} 3x_{n\plus{}1} \minus{} 3x_{n\plus{}1} \plus{} 9x_{n} \equal{} r_{n\plus{}1} \minus{} 3r_n \equal{} 5x_n \Rightarrow  x_{n\plus{}2} \minus{} 6x_{n\plus{}1} \plus{} 4x_n \equal{} 0$.

a sketch of what I did:
$ x_{n\plus{}1}\equal{}3x_n\plus{}[x_n\sqrt{5}]\equal{}6x_n\plus{}1\minus{}[x_n(3\minus{}\sqrt{5})]\equal{}6x_n\plus{}1\minus{}[(3\minus{}\sqrt{5})[(3\plus{}\sqrt{5})x_{n\minus{}1}]]\equal{}6x_n\minus{}4x_{n\minus{}1}$
and the last step is quite easy to show :)

I found X_n at the last minute so i didn't have time to prove it. (Proof is pretty easy by using induction) May I expect any partial credit? :(

I am mad at myself for not guessing the formula. I did "see" $ 5$ and $ 13$ (a factor of the $ 3^{rd}$ term) as Fibonacci numbers but didn't find factors of the fourth and fifth terms of the sequence. I should have done so. I guess sleeping for only two hours the night before took its "toll" on me!

Does anyone have a intuitive method that could suggest how to obtain the recurrence relation that the solutions have? It did not even occur to me that it could be expressed as a recurrence during the test. I was fiddling with $ (3\plus{}\sqrt{5})^{n}$ and $ (3\minus{}\sqrt{5})^{n}$. But it did not help me much

The standard idea: The dominant term of the sequence is clearly some multiple of $ (3\plus{}\sqrt{5})^n$. We get exponential solutions $ r^n$ from linear recurrences $ x_{n\plus{}k}\plus{}a_{k\minus{}1}x_{n\plus{}k\minus{}1}\plus{}\cdots\plus{}a_0x_n$, where $ r^k\plus{}a_{k\minus{}1}r^{k\minus{}1}\plus{}\cdots\plus{}a_0r^0\equal{}0$.

Since our sequence is all integers, we want an integer polynomial that $ 3\plus{}\sqrt{5}$ is a root of- $ x^2\minus{}6x\plus{}4$ is the simplest. We then guess that $ x_{n\plus{}2}\minus{}6x_{n\plus{}1}\plus{}4x_n$ is small- we could handle a $ (\minus{}1)^n$ or a $ 1$ or something. Using the listed values, that quantity is zero for $ n\equal{}0,1,2$; conjecture that it's always zero.

We then explicitly solve the recurrence $ y_{n\plus{}2}\minus{}6y_{n\plus{}1}\plus{}4y_n\equal{}0$ with initial conditions $ y_0\equal{}1,y_1\equal{}5$, and show that $ y_{n\plus{}1}\equal{}3y_n\plus{}\lfloor y_n\sqrt{5}\rfloor$.

This is essentially what I did during the contest.

Would they expect a rigorous proof that $ (3\plus{}\sqrt{5})^n\plus{}(3\minus{}\sqrt{5})^n$ and $ \frac{\sqrt{5}}{2}((3\plus{}\sqrt{5})^n\minus{}(3\minus{}\sqrt{5})^n)$ are integers? I explained how the terms canceled out (to some detail), but it wasn't as rigorous as finding a recurrence, for example.

Did you write them explicitly as sums of binomial coefficients?  That sounds like it would be fine to me.

Alternately, it's enough to show that they're equal to their conjugates in $ \mathbb{Z}[ \sqrt {5} ]$.  :)

I wasn't that explicit, as I was running out of time when writing up that solution (3 hours is so short :!:)... oh well, I can settle for just a few points on this problem.


points $A,B$ are fixed. find the set of all feet of perpendicular s from $A$ to all possible straight lines

Through $B$.

We call $C_1$ the circle with diameter $AB$.
We look at two staight lines, say $k$ and $l$, through $B$, and call the feet of the perpendiculars to them from $A$, $O$ and $P$ respectively. Now, because $\angle AOB=\angle APB=\frac{\pi}{2}$, $ABOP$ is a cyclic quadrilateral, in circle $C_1$.

So it is proven that any two points $O$ and $P$ are elements of $C_1$, so the locus we were searching for is a circle with diameter $AB$.


Given real numbers $ a,b,c$. Prove that

$ \max\{|ac \plus{} b|,|a \plus{} bc|\}\geq\min\{|a \plus{} b|,|a \minus{} b|\}.$

Notice that the right hand side is equal to $ \parallel{}a|\minus{}|b\parallel{}$, and the left hand side
is symmetric on $ a$ and $ b$, so, we may assume that $ |a|\leq|b|$.

When $ |c|\leq 1$,  we have
 $ (ac\plus{}b)^2 \minus{} (a\plus{}bc)^2 \equal{} (b^2\minus{}a^2)(1\minus{}c^2)$.
In this case, $ \max\{|ac\plus{}b|, |a\plus{}bc|\} \equal{} |ac\plus{}b|$.  It is easily followed that
$ |ac\plus{}b| \geq \parallel{}b|\minus{}|ac\parallel{} \geq \parallel{}b| \minus{} |a\parallel{}$.

When $ |c|\geq 1$, then let $ d\equal{}1/c$,  we have $ |d|\leq 1$.  By using the above result,
we get
$ \max\{|ad\plus{}b|,|a\plus{}bd|\} \geq \parallel{}b|\minus{}|a\parallel{}$,
multiply both sides by $ |c|$,  then ....


AMC
USA(J)MO
USAMO
Putnam
MATHCOUNTS
AIME
AMC 12

So, what's everyone's goals in terms of math comps this year? State your grade too.

Mine...is to make USAMO as 9th grader. I'll almost be done with AOPS2, so I'm hoping to do well on the AIME..

Also to be top freshman in all the local math leagues and whatnot.

Grr.

I'm in 10. My goal is to make mop. well, thats not going to happen either.

[quote]My goal is to make the third group in the Putnam, but it's not going to happen.[/quote]

By "third group", do you mean the third place group in the competition? And also, doesn't that sorta depend on how smart the kids are that go to your school, and not solely yourself?

By the way, my goal is to make USAMO (hears chuckling from the crowd). And, if things go well this year and MOP does indeed expand to accomodate 60 people, then perhaps to make MOP (crowd breaks out into laughter).

..

Yeah, well, maybe I'm setting the standards a bit high with that MOP part, and I'm certainly not at that level right now, but you never know.

Mmm, mine's a bit lower than everyones...
Make it to MATHCOUNTS Nationals
Make it to AIME
Win MAML (middle school; I'd rather compete for my high school but the schedules don't work out and I don't qualify)

For next year:
Make it to AIME (hey, I'm just being realistic :) )
Get a decent score on MAML High School Version :)
Finish AoPS 1 and 2

Yup, being very realistic about my skills.

[quote="TheSouthpaw"]So, what's everyone's goals in terms of math comps this year? State your grade too.[/quote]

I'm forty-something years old, a coach of a math team of homeschoolers in Minnesota. My goal is to have a full roster of kids grades 3 through 8 to attend the Minnesota Junior High Mathematics League

http://members.aol.com/mathleague

have a few kids in our group, oldest grade 7 (I think), take the AMC-8, field a MATHCOUNTS team for the first time ever (oldest kid probably grade 7), POSSIBLY have a few other kids (grade 9) take the AMC-10, and kick serious posterior in the sixth grade regional competition in the Math Masters of Minnesota

http://www.mathmastersmn.org/

contest. Oh, yeah, and to work through at least some of AoPS book 1 myself before the end of this school year.

12th grader. (or as they say it across the border, "senior". [i]*shudder*[/i])

Goal is to score top 10 in the COMC (or at least, make the CMO), get invited to winter camp (yeah, slim chance ~_~), respectable score for Euclid, good score on CMO (2nd group, or dare I hope, honourable mention)... write AMC-12 and AIME, -if I can-, because the school administration doesn't have any teachers to supervise...

Of course, it'd be nice to make the IMO team, but I don't see that happening at all.  :?

Which all culminates into a fat scholarship for me to go to University of Toronto.

[quote]12th grader. (or as they say it across the border, "senior". *shudder*) [/quote]

...or behind the border as well.  :D

[quote="Fierytycoon"]Hmm, Tare, you could probably make AIME easily if you take the AMC12...as long as you don't do something stupid like pull an all-nighter the day before the AMC12.[/quote]
Mmm, I doubt that...*sigh* I need more time...I want to drop all subjects except math and cooking :lol:
Do you need to know all the material in AoPS 2 for AMC12 or just AoPS1?

8; make it to MC nats,
do fairly well on preSATs
perfect on AMC 8
finish AoPS 1 & 2

[quote]Do you need to know all the material in AoPS 2 for AMC12 or just AoPS1?[/quote]

Both, I would say.

Putnam results are strange. The highest group is the Putnam Fellow (top 5). Then the next ten or so is another group. Then the next ten or so is another group. It is my goal to make it into that group. That is ridiculous, isn't it? I know I'm not that smart, but according to the professor who teaches the Putnam seminar, a person can do very well by being pounded with tons of problems. I have learned so much from his seminars already... problems I could never solve before are now simple to me.

Oh, so those groups are for individuals, and not school teams?

My goal is to make Hon. Mention on the USAMO.  I'm a senior this year so making MOP is not really feasible :(.

[quote="ComplexZeta"]Right. I can't control how the other two people on my team do, so I can't really make that an individual goal. Oh yeah, if I can't make my other goal, at least I want to beat Jon Lowd. He was at my high school and now at my college (also a freshman). My parents always make fun of me when he beats me, so I will have to beat him.[/quote]
While competition might increase your motivation, it shouldn't be the reason why you're trying to good on the test...oh well :)

[quote]While competition might increase your motivation, it shouldn't be the reason why you're trying to good on the test...[/quote]

Why not?

Well...sooner or later you'll lose yourself in the heat and trust me, it gets ugly when that happens. Just look at the examination war in Asia...

my goals: go through art and craft, make 2nd level of MAML Olympiad and do well on it, get a solid score on AIME, start doing better on local meets.  I just had one today and did pretty poorly....

nope.  There are only like 2 leagues in MA though i think (maybe 3 or so).  GBML are quite a bit tougher than the ones i just did (our arml coach passed some out last year)... mine probablly are not any harder than the state or national mathcounts contests.  How did you do?  Does your school usually make it to states?  One of the questions on the team round I actually did not too long ago when i was practicing out of the AOPS book to prepare.  That was kind of neat.

Wait, cats..., it wasn't the NEML, so what was it?

Our school, Lexington, is probably the best in the state undisputed, so we most of the time win New England. I didn't do so well, even though I was on B team. Got 13/18. Maybe I'll see you at MAML Level 2 or MML or something.Where do you go?

the NEML is a mail-in contest, but the one i just did was something we actually had to go to some other place.  It was for worcester county.

A 13 is not that bad.  If you'd keep that for an average you'd probablly be top 10-20.

10th grade.  I want to make it to USAMO and possibly MOSP.  Also, I will try to go through the AoPS books methodically.

-interesting_move


If you get an indeterminate form that is negative, then do you multiply the L'Hospital Rule's quotient limit by negative 1?

ie:

$\lim_{x\to a}\frac{f(x)}{g(x)}=-\frac{\infty}{\infty}$

then

$\lim_{x\to a}\frac{f(x)}{g(x)}=\lim_{x\to a}-\frac{f'(x)}{g'(x)}$

$\lim_{x\to a}f(x)g(x) =-0( \infty)$

then

$\lim_{x\to a}f(x)g(x) =\lim_{x\to a}-\frac{f'(x)}{(\frac{1}{g(x)})'}$

No. Apply the usual rule to $\lim \frac{-f(x)}{g(x)}$ and see what happens.

What do you mean? Is that the limit if it's a negative indeterminate form?


Trinni is fascinated by triangle numbers $(1,3,6,10,15,21...)$ and recently coming across a clock she found that she could rearrange the 12 numbers $1,2,3,4....12$ around the face so that each adjacent pair added up to a triangle number. She left the 12 in its usual place: what number did she put where the 6 would usually be?

The figure shows a cube of side 1 on which all 12 face diagonals have been drawn- creating a network with 14 vertices (the original eight corners plus the six face centres) and 36 edges (the original 12 edges plus 4 extra edges on each face). What is the lenght of the shortest path along the edges of the network which passes through all 14 vertices?

Is there a PROPER way of doing such problems, I know the chances will be slim but still Im just curious.
 :?  :(

Im sorry for the 2nd one youll have to draw the figure yourselves.

Well even if there was a proper way to do 1, chances are it wouldn't be faster than just figuring out numbers that sum to triangular numbers.

This was from a contest 1 hour long which had 30 problems. If you do try and figure out the numbers then it is time consuming.
The other one is the same. Is there a method for the 2nd one except hit and trial?

#1 really doesn't take very long, since there are few numbers that can go in each place. For example, you know that the numbers next to 12 are 3 and 9. The only number that can be next to 3 is 7. It's fairly simple to figure out which numbers go where. It would probably take much longer to actually find equations and things like that. :)

:blush:  :blush:   I see it now but still it does take a bit longer to get the correct combination.


function
analytic geometry
calculus
calculus computations

Let a function $ y\equal{}\frac{ax\plus{}b}{cx\plus{}d} (c \neq 0,ad\minus{}bc \neq 0)$ with graph $ (\epsilon)$
Find all points M in the coordinate plane (Oxy) such that:
a) From M we can't draw any tangent line to $ (\epsilon)$
b) From M we can draw a tangent line to $ (\epsilon)$
c) From M we can draw two tangent lines to $ (\epsilon)$

[quote="kunny"]From $ y \equal{} \frac {ax \plus{} b}{cx \plus{} d} \equal{} \frac {a}{c} \minus{} \frac {ad \minus{} bx}{c(cx \plus{} d)}\ \left(x\neq \minus{} \frac {d}{c}\right)$, the tangent line at $ \left(t,\ \frac {at \plus{} b}{ct \plus{} d}\right)\ (t\neq \minus{} \frac {d}{c})\ c\neq 0,\ ad \minus{} bc\neq 0)$ is $ y \equal{} \frac {ad \minus{} bc}{(ct \plus{} d)^2}(x \minus{} t) \plus{} \frac {at \plus{} b}{ct \plus{} d}.$

$ \therefore c(cy \minus{} a)t^2 \plus{} 2c(dy \minus{} b)t \plus{} d^2y \minus{} (ad \minus{} bc)x \minus{} bd \equal{} 0\ \cdots [*].$

Case 1: $ cy \minus{} a \equal{} 0\Longleftrightarrow y \equal{} \frac {a}{c}, \ [*]\Longleftrightarrow 2(ad \minus{} bc)t \plus{} d^2y \minus{} (ad \minus{} bc)x \minus{} bd \equal{} 0.$

For a), since $ ad \minus{} bc\neq 0,\ [*]$ has real roots, so the answer is $ \boxed{y\neq \frac {a}{c}}.$

For b), the answer is $ y \equal{} \frac {a}{c}.$

For c),  $ [*]$ can't have two solutions as $ ad \minus{} bc\neq 0.$

Case 2: $ cy \minus{} a\neq0\Longleftrightarrow y\neq \frac {a}{c}.\ [*]$ is a qudratic equation with respect to $ t$,

$ Discriminant/4 \equal{} \{c(dy \minus{} b)\}^2 \minus{} c(cy \minus{} a)\{d^2y \minus{} (ad \minus{} bc)x \minus{} bd\}$

$ \equal{} c(ad \minus{} bc)(cxy \minus{} ax \plus{} dy \minus{} b)$.

Since $ c(ad \minus{} bc)\neq 0$, Summuryzing the above gives the answer as follows.

For a), $ D < 0\Longleftrightarrow c(ad \minus{} bc)(cxy \minus{} ax \plus{} dy \minus{} b) < 0$ and $ y\neq \frac {a}{c}.$

For b), $ D \equal{} 0\Longleftrightarrow cxy \minus{} ax \plus{} dy \minus{} b \equal{} 0\Longleftrightarrow y \equal{} \frac {cx \plus{} d}{ax \plus{} b}.$

For c), $ D > 0\Longleftrightarrow c(ad \minus{} bc)(cxy \minus{} ax \plus{} dy \minus{} b ) > 0$ and $ y\neq \frac {a}{c}.$[/quote]
Thanks very much!


Find all $ f: R\rightarrow R$ such that for any $ x,y\in R$,

$ f(x\plus{}y)\equal{}f(x)\plus{}2f(y)$ or $ f(x\plus{}y)\equal{}2f(x)\plus{}f(y)$?


Can someone please direct me to some counting/probability problems (w/ solutions would be nice) at the Aime level. Thanks.

For starters, go though all the old contests & pamphlets. That gives you plenty to start with.

[quote="Calculus"]Sorry for the lack of clarity, I have already worked through past AIMEs.[/quote]

How about my AWESOME mock AIME? You'll have to search "Mock AIME III" yourself though...

[quote="Calculus"]Sorry for reviving this thread. I managed to go through HMMT, anyone have more problem resources?
h[/quote]

If you covered all AIME and HMMT counting, you should have fairly good amount of skills for counting. I don't see why you need to worry about them. I meant this with assumption that you solved all problems purely by your own (i.e. there wasn't single problem that you struggled with). If there were any, try to create similar problem and solve that one. That way, you can make sure that you understood the problem 100%.


limit
real analysis
real analysis unsolved

Prove that if $f: (0,\infty) \to \mathbb{R}$ satisfies $f(xy) \leq \frac{f(x)}{y}+f(y)$ for $x>0,y>0$ then $\lim_{x \to \infty}f(x)$ exists.

[quote="gnosis"]one of the first things I've noticed is that for $x=1$ we would get $f(1)\geq y$ for $y>0$ which seems rather strange... :?  :read:[/quote]
No,it seems it way you typo: put $x=1$ and you'll get $f(y) \leq \frac{f(1)}{y}+f(y)$, i.e. $0 \leq \frac{f(1)}{y}$, which simply means that $f(1) \geq 0$.

:blush: thanks.
If it helps I also got that since $f(x^2)\leq f(x)\left(1+\frac{1}{x}\right)$ we will have that for $x>1$ $f(x^{2^n})\leq \frac{1-\frac{1}{x^{2^{n+1}}}}{1-\frac{1}{x}}f(x)$ so if $\exists\lim_{x\to\infty}f(x)$ then $\lim_{x\to\infty}f(x)\leq \inf_{x>1}\frac{x f(x)}{x-1}$
I'll be thinking about it.


geometry
3D geometry
tetrahedron
sphere
incenter
geometric transformation
homothety

Tetrahedron $ABCD$ in which $AB=CD$ is given. Sphere inscribed in it is tangent to faces $ABC$ and $ABD$ respectively in $K$ and $L$. Prove that if points $K$ and $L$ are centroids of faces $ABC$ and $ABD$ then tetrahedron $ABCD$ is regular.

Let $I$ be the incenter of $ABCD$, and let $N$ be its projection onto $AB$. Also let $M$ be the midpoint of $AB$. $N$ must coincide both with the projection of $L$ onto $AB$ and with that of $K$, so, in particular, these two must coincide. It folows from this that $AB\perp LK$ (so $AB\|CD$, since $CD\|LK$).

Since $IL=IK$, we also have $NL=NK$, but $NL,NK$ have lengths equal to one third of the $C$, and, respectively, $D$-altitude in $ABC$ ($ABD$). Moreover, these altitudes cut $AB$ in the same point $P$, which is the image of $N$ through a homothety of center $M$ and ratio $3$. This means that $ABC,ABD$ are congruent.

Suppose $AN>NB$ (which is equivalent to $AP>PB$). If $Q$ is the intersection between the plane $(CID)$ and $AB$, then, since $I$ and $N$ lie on different sides of the plane $(CMD),\ Q$ and $N$ must lie on different sides of $M$, i.e. $AQ<QB$. The areas $[ACD],[BCD]$ of the triangles $ACD,BCD$ satisfy $\frac{[ACD]}{[BCD]}=\frac{AQ}{QB}$, so $[ACD]<[BCD]\ (*)$. At the same time, from $AP>PB$ it follows that $[ACD]>[BCD]$, contradicting $(*)$. Something similar happens if we assume that $AN<NB$, so it must be that $M=N=P=Q$, i.e. $DA=DB=CA=CB$.

The above, together with $AB=CD$, implies $[BDA]=[BDC]$ for example, and since the plane $(BDI)$ divides $AC$ into a ratio equal to the ratio of the areas $[BDA],[BDC]$, it must cut $AC$ in the middle, i.e. $B,D,I,K$ are coplanar. Similarly, $A,D,I,K$ are coplanar, so $D,I,K$ are collinear. In the same way we show that $C,I,L$ are collinear. In the isosceles triangle $CMD$ the altitudes $CIL,DIK$ divide the sides $DM,CM$ respectively in the ratio $\frac 13$. From here (and from $AB=CD$) we find that $\frac{MD}{AB}=\frac{\sqrt 3}2$, exactly what it should be in order to make $ABD$ (and thus all faces of $ABCD$) equilateral.


probability
geometry
3D geometry
tetrahedron
inequalities
trapezoid

1.  Xena, Yolanda, and Zachary, three geometry students, are to generate random numbers in the interval [0, 2] on their calculators.  Their teacher has promised no homework for the whole class tonight if the sum of three students' numbers is at least 1 but no more than 2.  Find the exact probability of a homework-free night for the class.

2.  An eight foot stick and twenty-two foot stick are both randomly broken into two parts.  What is the probability that the longer part of the 8 foot stick is longer than the shorter part of the 22 foot stick.

If you could explain how to solve these problems in simple terms, I would be grateful.

1 solution:
[hide]
1) Think about a simpler problem. $ X\plus{}Y$ has to be on $ [1,2]$ with the same random bounds. This turns out to be a square with the area we want to be bound by the points $ (0,2) (2,0) (1,0) (0,1)$. But what if $ X\plus{}Y$ has to be on$ [0.7,1.7]$. Then it is bound by $ (0,1.7) (1.7,0) (.7,0) (0,.7)$.

Notice that this region is also a quadrilateral (which is just a big triangle minus a smaller triangle).
What if $ X\plus{}Y$ has to be on $ [0.3,1.3]$?
What if $ X\plus{}Y$ has to be on $ [0.1,1.1]$?
What if $ X\plus{}Y$ has to be on $ [0,1]$?
What if $ X\plus{}Y$ has to be on $ [0,.7]$?
Do you see what is happening?

With all of these questions, it is basically as if we set Z to be $ 0,.3,.7,.9,1,$ and $ 1.3$
This is basically as if we stack each of these smaller regions up to make a solid. This solid turns out to be a big tetrahedron minus a small tetrahedron, with our total possibles being a big cube.

So the volume of the big tetrahedron turns out to be: $ \frac{1}{3}(2)(\frac{1}{2}\cdot2\cdot2)\equal{}\frac{4}{3}$
$ \frac{1}{3}(\text{height})(\text{base area})$
The smaller is: $ \frac{1}{3}(1)(\frac{1}{2}\cdot1\cdot1)\equal{}\frac{1}{6}$
Subtracting gives the volume we are interested in, and dividing by the big cube of possibles we get the probability:
$ \dfrac{\frac{4}{3}\minus{}\frac{1}{6}}{2\cdot2\cdot2}\equal{}\dfrac{\frac{7}{6}}{8}\equal{}\dfrac{7}{48}$
[/hide]

2 solution
[hide]
First think about the longer part. Really we are taking half of the stick and adding some random length on the interval $ [0,4]$ to the half length, and subtracting that length from the other half.
The same style of thinking applies to the 22 length, but instead we are subtracting it from 11.
Aligning these two half lengths with the x and y axes.
For any $ x$ value we choose, $ 4\plus{}x$ is how long the 8 foot break will be.
For any $ y$ value we choose, $ 11\minus{}y$ is how long the 22 foot break will be.
We want $ 4\plus{}x>11\minus{}y$
$ x\plus{}y>7$
Graph this inequality, and this gives what we want in relation to our $ 4$x$ 11$ rectangle.
We get what we want is a quad with points: $ (0,7) (0,11)(4,11)(4,3)$.
Use whatever method you want to find this area (shoelace, triangle + quad, or trapezoid)
The are is: $ 24$
Our total area is $ 4\cdot11\equal{}44$.
Probability is $ \dfrac{24}{44}\equal{}\dfrac{6}{11}$
[/hide]


inequalities
calculus
real analysis
real analysis unsolved

I put it here because I believe there exist a solution with calculus (Langrange Multipliers etc)

Let $x,y,z>0$ and $xyz=1$ prove that
$2\sqrt{3(x^{y}+y^{z}+z^{x})}+x+y+z\geq 9$

I hardly believe that there are normal people who would start to make computations based on Lagrange multipliers just to solve this problem...

It's been long time since I'm no longer searching solutions for such problems. I'm sorry, I hope someone will find the nice solution you want, but it's definitely not me.


I was using the View Source feature in Yap until quite recently, when, after an upgrade of my Miktex installation (web-update), it stopped working. It always gives me the following error
[quote]Cannot open the TeX source file: the DVI page contains no source links.[/quote]
This only happens with newly compiled documents. Old DVI files apparenlty still "contain the source links" and I am able to double-click in Yap to get WinEdt to open the associated .tex file.

Any ideas what can be wrong?  :?

It appears that either WinEdt is not issuing the command to include source specials or MiKTeX is ignoring the command. I am guessing here, but I suspect you installed WinEdt after installing the old version of MiKTeX so WinEdt knew it had to alter things (such as miktex.ini). Perhaps a simple way is to reinstall WinEdt over itself (another guess as I don't have WinEdt).

If you invoke latex --src yourfile.tex from the command line does it produce the source specials? If so, then WinEdt may not be issuing them - http://groups.yahoo.com/group/WinEdt/message/5312 mentions how to check this.

I presume Yap knows about WinEdt otherwise it wouldn't work on older files (check in Yap, Options, Inverse Search)

Thanks Steve! :)

I noticed that the --src option was missing on my WinEdt since upgrading MikTex (perhaps that had something to do with it) and I've reinstalled it. Now everything works perfectly (--src option is enabled).

By the way, could anyone show me how to make dvi document?
Thanks.

Far too little information to say. If you are using the [url=http://www.artofproblemsolving.com/LaTeX/AoPS_L_Downloads.php]AoPS system[/url] then just change the dropdown box in TeXnicCenter to say LaTeX => DVI. If you are using the command line then [code]latex filename[/code] defaults to DVI output. If ... ([i]who knows what your system is[/i]).

Ok but how are you using it? What editor are you using? Are you generating pdf files but want to change to dvi? Have you just downloaded MiKTeX?

Without information it's difficult to advise except to follow the [url=http://www.artofproblemsolving.com/LaTeX/AoPS_L_About.php]AoPS tutorial[/url]. Using TeXnicCenter as recommended there means you only have to press a button to get a DVI file.

In my document, the author asked user to [i]save TeX doc (in MS Word) under the type "Plain text", loading LaTeX and get dvi file[/i]. And I understood nothing!  :)

Using Word as a text editor is highly amusing and rather sad! Tex documents are plain text files but full of commands as to how it is to print. It would be better to use Notepad to write the file as Word will only hinder not help.

What I suggest is follow AoPS instructions and download TeXnicCenter then edit your document there. Then, assuming there are no errors, press the DVI button and you will get your document.

If you are really, really desperate you could use the command line (Start, Run, cmd) and say latex filename but you may run into path problems (files can't be found). TeXnicCenter takes care of all this for you so is much easier to use.

Word is meant for word processing and is not good for typesetting which is what LaTeX does, so it's best not to mix the two.

PS I hope the tex document has been written in LaTex code, so begins with \documentclass and ends with \end{document} and has lots of similar commands inbetween.

Hello, everybody.
I’ve passed the school exam in mathematics. Now I want to make a [u]pdf[/u] file contains all the problems. But I’m not good at $LaTeX$.
Here’s the document that I typed.
[b]Is there any error in [u]this document?[/u][/b] (See and compare the orders between two part I and II.

Part I
[quote]
\documentclass[10pt,twoside,a4paper]{article}
\maketitle
\title{School Team Test}
\author{Lovasz}
\begin{document}
\begin{flushleft}
\begin{enumerate}

\item [Arithmetics]
Find all integer solution for $\sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}=y$.

\item [Algebra]
Find all contiuous functions $f: \mathbb{R^+} \to \mathbb{R^+}$ which satisfies:
\[ f \left( \frac{1}{f(xy)} \right) = f(x) f(y)  \]

\item [Inequality]
If $a,b,c>0$ then:
\[ \frac{ab+bc+ca+a^2}{b+c+2a}+\frac{ab+bc+ca+b^2}{c+a+2b}+\frac{ab+bc+ca+c^2}{a+b+2c} \le a+b+c  \]

\item [Calculus]
Find:
\[ \int \frac{dx}{\sin x}  \]

\item [Geometry]
The convex hexagon $ABCDEF$ has all angles equal. Prove that:
\[ AB-DE=EF-BC=FA  \]

\end{enumerate}
\end{flushleft}
\end{document}
[/quote]

And this is all I want to display in the pdf file:
Part II

[quote]
[b]SCHOOL TEAM TEST[/b]
[b]Lovasz[/b]

[b]1. [Arithmetics] [/b]
Find all integer solution for $\sqrt{x+\sqrt{x+\sqrt{x+\cdots}}}=y$.

[b]2. [Algebra] [/b]
Find all contiuous functions $f: \mathbb{R^+} \to \mathbb{R^+}$ which satisfies:
\[ f \left( \frac{1}{f(xy)} \right) = f(x) f(y)  \]

[b]3. [Inequality] [/b]
If $a,b,c>0$ then:
\[ \frac{ab+bc+ca+a^2}{b+c+2a}+\frac{ab+bc+ca+b^2}{c+a+2b}+\frac{ab+bc+ca+c^2}{a+b+2c} \le a+b+c  \]

[b]4. [Calculus][/b]
Find:
\[ \int \frac{dx}{\sin x}  \]

[b]5. [Geometry] [/b]
The convex hexagon $ABCDEF$ has all angles equal. Prove that:
\[ AB-DE=EF-BC=FA  \] [/quote]

Please remind me if there’s something is incorrect. Thanks.

I can’t understand why I worked with WinEdt5.4,
I wrote:

[quote]
\documentclass[10pt,a4paper]{article}
\begin{document}
If a,b,c>0 then \frac{a}{b}+\frac{b}{c}+\frac{c}{a}+\sqrt[3]{3} > 4 .
\end{document}
(I deleted the LaTeX tags [b]dollar[/b]))
[/quote]
The result I got:

[quote]
Document class
If $a,b,c>0$ then $ab+bc+ca+\sqrt{}[3]3>4$.
[/quote]
What’s the matter? Or I had some troubles.
And the tags \[ also doesn’t work.
(Sorry, I wrote one tag only, the rest is ?])

[quote="Lovasz"]Is there any error in this document? (See and compare the orders between two part I and II. [/quote]It would help if you would explain exactly what the problem is. The document looks OK so what sort of error do you think is there? The two parts look the same at a first glance so you must show where in the documents the problem arises.

It would be useful to leave out dollar signs where you want to just show the LaTeX code.

Thanks, stevem.

I wrote:

[quote]
\documentclass[10pt,a4paper]{article}
\begin{document}
If a,b,c>0 then \frac{a}{b}+\frac{b}{c}+\frac{c}{a}+\sqrt[3]{3} > 4 .
\end{document}
(I deleted the LaTeX tags [b]dollar[/b]))
[/quote]
The result I got:

[quote]
Document class
If $a,b,c>0$ then $ab+bc+ca+\sqrt{}[3]3>4$.
[/quote]
What’s the matter? Or I had some troubles.
And the tags \[ also doesn’t work.
(Sorry, I wrote one tag only, the rest is ?])[/quote]

There's nothing wrong with the document which compiles correctly for me. What does the log say about problems?

It said: [b]Undefined control sequence![/b]
But I've found that [b]\frac{...}{...}[/b] doesn't work, while [b]{a \over b}[/b] is okay.
Morever, [b]\sqrt[n]{t}[/b] isn't, too. The choice of this TeX system is [b]\root{n}\of{...}[/b].

[quote="Lovasz"]It said: [b]Undefined control sequence![/b][/quote]Which command is this referring too?

[quote="Lovasz"]But I've found that [b]\frac{...}{...}[/b] doesn't work[/quote]Explain 'doesn't work'

[quote="Lovasz"]The choice of this TeX system is [b]\root{n}\of{...}[/b].[/quote]Eh? What TeX system? Where do you get \root{n}\of{...} from? There is no TeX command I know of called  \root unless it has been defined in some package.

Again I must emphasise that we aren't mind readers so you are really going to have to explain what you are using in much more detail because you appear to be using a strange system. It would also help if you attached the tex log for a simple example document.

[quote="stevem"][quote="Lovasz"]It said: [b]Undefined control sequence![/b][/quote]Which command is this referring too?[/quote]
Don't mind about it. :D
[quote="Lovasz"]But I've found that [b]\frac{...}{...}[/b] doesn't work[/quote]Explain 'doesn't work'
It means $\frac{a}{b} \to \boxed{ab}.$

I click "PdfTeX" only. The others, i.e. "TeX", "LaTeX" don't give anything. They required something, I don't remember. I'll tell you about it later.

Thanks for that. But I seem to have failed to convince you that it is virtually impossible to diagnose your problem without proper information. So, trying for the last time, please, as an absolute [i]minimum[/i], supply the following:
[list=1][*]The log file that LaTeX creates when you create a DVI/PDF file
[*]Explain [i]in detail[/i] where you got the message[quote]The choice of this TeX system is \root{n}\of{...}.[/quote][*]the editor you are using to compile the document[/list]

Thanks, stevem.
Sorry, but I'm new at using $\LaTeX$, so I can't understand what's editor.

But when I click the symbol "LaTeX" to try dvi file, it requires installing [b]Hungarian-Hyph-Miktex[/b] (Hyphernation patterns). I don't know what it is.

Anyway, thanks for helping me. :)

hello,

editor is the program you use to type in you text, eg notepad, texniccenter, emacs winedt...

for the hypnation (how words are split over 2 lines ), probably you have something like
[code]\usepackage[hungarian]{babel}     [/code] in your preamble, but for some reasing it wont work...

A

Sorry, but it needs a path in computer, not an order.


I am a current student, I found the forum extremely useful. Thank you very much that you exist to help students in maths. I am preparing for exam on maths now and I am studying very hard. As usual everyone could encounter a problem in understanding some issues in maths. I am struggling particularly with equations and if you are able to help me I will be very happy. I worked through some examples for which I am not absolutely sure in the results, so may I ask you for support.

The first one is-

1-Find the value of b for the following equation when x=4 and y=12

•	b = 8x-2y

•	3x2 + 2y = 2b

•	(2y2 – x3 )2 = 3b
                                  4

•	2 = (3x)2 - y
b

My calculations

b = 8x-2y

b = 32 – 24

b = 8

3x2 + 2y = 2b

(12)2 + 24 = 2b

2b = 144 + 24    note should I change the + to – to the RHS

2b = 168

1 (2b) = 1 (168 )
      2            2

      2b = 168
2	2

      b = 84

(2y2 – x3 )2 = 3b
                      4

( (24)2 – (4)3 )2 = 3b
                            4

( 576 – 64 )2 = 3b
                         4

( 512 )2 = 3b
                 4

262144 = 3b
                 4

3b  = 262144
 4

4 3b = 4 (262144)
    4

3b = 1048576
 3            3

b = 349525.33
2 = (3x)2 - y
b

2 = ( 12 )2 - 12
b

2 =  144 - 12
b

1   2   =   1   (132)
2   b         2

b = 132
        2

b = 66

My last question is concerned with other type of equations. Please could you guide me through the process of solving them. I couldn’t find the same type on your website in order to understand them. Thank you!!!!

6x + 7     - x -  11   = 0
     2                  2

and the second one:

x + 3  = 1 + x + 1
 x -2            2(x-3)

[/list]

Due to the fact that I really can not copy directly from m/word in the forum pages, I attached pdf file with the equations clearly understood,

Please help me Iam not that good in maths but Iam trying my best,,, :(  :(

Thank you very much,,,  :blush:


function
algebra
polynomial
combinatorics unsolved
combinatorics

how I can find the generating function of :
$ a_n \equal{}2a_{n\minus{}1}\plus{} 3^n \minus{}n^2$ and $ a_0\equal{}0$

How familiar are you with the general theory?  The characteristic polynomial needs to have roots $ 2, 3, 1, 1, 1$.  The first is for handling the coefficient of the recursion, the second for the $ 3^n$ term, and the third to handle the $ n^2$ term.  Alternately, have you tried just multiplying by $ x^n$ and summing over all $ n$?  That gets you the correct answer with little effort.

yes.it is true.but I want to know there is not a way that we do  not eliminate $ 3^n$ and $ n^2$.because if from the first we  multiply $ x^n$ we can not earn the answer

It's not clear what you're trying to say, but it is not difficult either to manipulate the recursion to eliminate both the $ 3^n$ and $ n^2$ terms, nor to solve for the generating function directly without making any such step.  The only things you need to know are $ \sum 3^n x^n$, $ \sum n^2 x^n$ and how to do basic manipulations on generating functions.

I edit my mistake that JBL siad to me in next comment.and we have:
f(x)=$ \displaystyle\sum_{m \equal{} 0}^{\infty}\ a_m x^m$
$ f(x) \equal{} a_0 \plus{} a_1 x \plus{} a_2 x^2 \plus{} ..... \plus{} a_m x^m \plus{} .....$
$ \minus{} 2xf(x) \equal{} \minus{} 2a_0x \minus{} 2a_1 x^2 \minus{} 2a_2 x^3 \minus{} ..... \minus{} 2a_m x^{m \plus{} 1} \minus{} .....$
then
$ f(x)(1 \minus{} 2x) \equal{} a_0 \minus{} (a_1 \minus{} 2a_0)x \minus{} (a_2 \minus{} 2a_1)x^2 \minus{} .......$
then
$ f(x)(1 \minus{} 2x) \equal{} 0 \minus{} (3^1 \minus{} 1^2)x \minus{} (3^2 \minus{} 2^2)x^2 \minus{} .....$
then
$ f(x)(1\minus{}2x) \equal{}\minus{} \displaystyle\sum_{m \equal{} 1}^{\infty}\ (3^m\minus{}m^2) x^m$
we can not calculate f(x) according to x.what I have to do?

[quote="michael.jackson_1958"]$ f(x)(1 - 2x) = a_0 - (a_1 - 2a - 0)x - (a_2 - 2a - 1)x^2 - .......$
then
$ f(x)(1 - 2x) = 0 - (3^n - n^2)x - (3^n - n^2)x^2 - .....$[/quote]  You appear to be very confused (as well as somewhat sloppy -- why are your subscripts becoming subtraction?).  The coefficient $ a_n$ is a function of $ n$.  The $ n$s go away when you look at particular coefficients, i.e., there is no $ n$ in $ a_1$.  Once you fix this (and it's clearer what's supposed to happen if you leave everything in summations), you should be able to finish without difficulty.

You could also try beginning like this:
\begin{align*} \sum_{n \geq 0} a_n x^n & = a_0 + x \sum_{n \geq 0} a_{n + 1} x^n \\
& = x \sum_{n \geq 0} (2a_n + 3^{n + 1} - (n + 1)n^2) x^n \\
& = 2x \sum_{n \geq 0} a_n x^n + \sum_{n \geq 1} 3^n x^n - \sum_{n \geq 1} n^2 x^n. \end{align*}


trigonometry
real analysis
real analysis unsolved

Give an example of bounded sequence $(a_n)_{n \geq 1}$ which is not convergent, but for which $a_{n+1} - a_n$ tends to 0 as n tends to infinity.

Of course I didn't see the "Bounded" condition. You see this sequence works : \[ a_n=1-1+\frac12+\frac12-\frac12-\frac12+\dots +\underbrace{\frac 1m+\dots+\frac1m }_{m\mbox{ times}}-\underbrace{\frac 1m-\dots-\frac1m }_{m\mbox{ times}}+\dots \]


In a triangle $ ABC$ with $ AB\equal{}20, AC\equal{}21$ and $ BC\equal{}29$, points $ D$ and $ E$ are taken on the segment $ BC$ such that $ BD\equal{}8$ and $ EC\equal{}9$. Calculate the angle $ \angle DAE$.

[quote="moldovan"]In a triangle $ ABC$ with $ AB \equal{} 20, AC \equal{} 21$ and $ BC \equal{} 29$, points $ D$ and $ E$ are taken on the segment $ BC$ such that $ BD \equal{} 8$ and $ EC \equal{} 9$. Calculate the angle $ \angle DAE$.[/quote]

 [geogebra]efba383b4924ceaf873966e24683a6a0113b9936[/geogebra]

$ 20^2\plus{}21^2\equal{}29^2$, so $ \angle BAC\equal{}90^{\circ}$

Now let $ \angle DAE\equal{}x^{\circ}$

$ CD\equal{}CA \Rightarrow \angle EDA\equal{} \angle CAD$
$ BE\equal{}BA  \Rightarrow \angle DEA\equal{} \angle BAE$

So in $ \triangle DAE$, $ x^{\circ}\plus{}(90^{\circ}\plus{}x^{\circ})\equal{}180^{\circ}$
$ \Rightarrow \angle DAE\equal{}x^{\circ}\equal{}45^{\circ}$


Let ABCD be a square of side length 140 cm. Let M, N, P and Q be the midpoints of the four sides. We draw four circles having its centers at the four corners of the square and another four circles having its centers at the four points M, N, P and Q. All the circles that we will draw in this problem have the same radius of 35 cm. Finally we draw a circle having its center at the center of the square and of course having its radius equal 35 cm. How many square centimeters are in the area inside the square but outside all the nine circles? The answer is x*(4-Pi). Find x.

Sorry about all the posts, I just did a practice sprint round and I couldn't figure out a lot of them...

Don't be sorry!  These problems are fun!

[hide]After you draw a diagram, divide the square into 4 equal squares.  You can see that each small square has 4 quarter circles in it.  So, the area of the weird region in the small square is 4900 - 1225*Pi.  There are 4 small squares in total, so multiply that by 4 to get 19600  - 4900*Pi, which = 4900*(4 - Pi).  So, Our x is 4900.[/hide]


inequalities
combinatorics unsolved
combinatorics

[tex]x_1<x_2<...<x_n[/tex]
[tex]y_i[/tex] is a permutation of the [tex]x_i[/tex].We have that [tex]x_1+y_1<x_2+y_2<...<x_n+y_n[/tex].Prove that [tex]x_i=y_i[/tex]

I think we should discuss how to choose appropriate sections for problems.

It sufficies to prove that $y_1=x_1$. Indeed, suppose the contrary. Then $y_2\neq x_1$, otherwise $x_1+x_2\leq x_1+y_1<x_1+x_2$ -- contradiction. Moreover if $y_1,y_2,...,y_k\neq x_1$ then $y_{k+1}\neq x_1$, otherwise one of the numbers $y_1$, ..., $y_k$ is at least $x_{k+1}$ and we obtain contradiction.

Rrrr.. Too fast :)

We can prove more: for any permutation $\sigma$ of $1,2,\ldots,n$, except for the identical one, there are $i<j$ s.t. $\sigma(i)\ge j$ and $\sigma(j)\le i$. We apply this to the indices of the $x_i$'s and we obtain what we want.

[quote="Myth"]I think we should discuss how to choose appropriate sections for problems.
[/quote]

What do you mean?

Pierre.

I meant that in my opinion it is for Inequalities section. Though now I have some doubts.

Hmm...according to the statement and the solution it is not a shock to find it here.
Remind that it is the unsolved problems section so that a problem has to be post according to its statement (since the proposer does not know the answer )

Pierre.