I have an $n \times n$ sheet of stamps, from which I've been asked to tear out blocks of three adjacent stamps in a single row or column. (I can only tear along the perforations separating adjacent stamps, and each block must come out of the sheet in one piece.) Let $b(n)$ be the smallest number of blocks I can tear out and make it impossible to tear out any more blocks. Prove that there are real constants $c$ and $d$ such that \[ \dfrac{1}{7} n^2 - cn \leq b(n) \leq \dfrac{1}{5} n^2 + dn  \] for all $n > 0$.

For the upper bound, suppose first that $n=5k$. Now break the sheet up into rows and tile each row with $1 \times 5$ rectangles. In the odd rows, place a $1 \times 3$ piece covering the 3 leftmost squares of each $1 \times 5$ rectangle. In the even rows, place a $1 \times 3$ piece covering the 3 rightmost squares of each $1 \times 5$ rectangle. It is obvious that no more $1 \times 3$ pieces can be placed in the resulting board, and we have used $5k^2$ pieces in total, that is, a fifth of $25k^2=n^2$. If $n$ is not a multiple of $5$, let $n=5k+r$ with $0 \leq r \leq 4$ and apply the previous strategy in the bottom left $5k \times 5k$ part of the board. Cover the rest of the board with as many $1 \times 3$ pieces as you want. It's easy to see that the rest of the board has $(5k+r)^2-(5k)^2=(10k+r)r$ squares, and in any case, if after that we have problems with the boundaries of the $5k \times 5k$ part of the board, it would take at most $10k-1$ (the number of squares on the boundary, this is a very rough bound) to correct them. Besides, since $r \leq 4$, we would be using at most $5k^2+40k+16+10k-1$ pieces, that is, $5k^2+50k+15 \leq 5k^2+65k=n^2/5+13n$, so $b(n) \leq n^2/5+13n$.

For the lower bound, suppose we've covered the board so that no more $1 \times 3$ pieces can be placed with $n^2/7-cn$ pieces. Place the $n \times n$ board on an infinite board and tile the infinite board with $1 \times 3$ rectangles in the obvious way, either horizontally or vertically. Choose the more popular orientation (if in the covering of the $n \times n$ board there are more horizontal pieces, tile with horizontal $1 \times 3$ rectangles, otherwise tile vertically). Suppose WLOG that the covering has more horizontal pieces and we've tiled with horizontal rectangles. Then there are at least $n^2/14-cn/2$ horizontal pieces and at most $n^2/14-cn/2$ vertical pieces.

Now, if we number the columns $\pmod 3$, there will be a number $x$ in ${0, 1, 2}$ for which the number of horizontal pieces with their leftmost square in a column $\equiv x \pmod 3$ is maximal. Move the tiling of the infinite board so that the leftmost squares of the $1 \times 3$ rectangles are $\equiv x \pmod 3$. Now, the idea is that each $1 \times 3$ rectangle contained in the $n \times n$ board must have at least one covered square, but the vertical pieces kill at most $3$ rectangles each, the horizontal pieces $\equiv x$ kill at most $1$ and the other horizontal pieces kill at most $2$. By our choice of the tiling, at least one third of the horizontal pieces is $\equiv x$, and the number of killed rectangles is at most

\[ [\dfrac{1}{2} \times \dfrac{1}{3}+2 \times \dfrac{1}{2} \times \dfrac{2}{3}+3 \times \dfrac{1}{2}](\dfrac{n^2}{7}-cn)=\dfrac{7}{3}(\dfrac{n^2}{7}-cn)=\dfrac{n^2}{3}-\dfrac{7cn}{3}. \]

Now the number of $1 \times 3$ rectangles contained in the $n \times n$ board is $\dfrac{n^2}{3}$ minus some number that is bounded by $en$ for some large enough constant $e$ (as the number of rectangles lost at the boundaries is no more than $4n$), so setting a large enough $c$ will make it impossible for all rectangles to be killed, and this finishes the problem.

Simpler proof for the lower bound:

Each block I tear out can prevent at most 14 other blocks from being torn out (5 parallel to it and 9 perpendicular to it). There are $ 2n(n\minus{}2) \equal{} 2n^2 \minus{} 4n$ total blocks on the board. Since we need make it so that we cannot tear out anymore blocks, we must have $ 14 b(n) \ge 2n^2 \minus{} 4n$ or $ \frac{n^2}{7} \minus{} \frac{2n}{7} \le b(n)$.

If I'm not mistaken, we can strengthen the lower bound...

Let $R$ be the $n\times n$ sheet of stamps. Call a square or block [i]good[/i] if it has been torn out and [i]bad[/i] otherwise, and suppose we've torn out $b(n)$ blocks so that no bad blocks remain. Let $X$ be the number of pairs of neighboring squares with one good and one bad.

First consider a good block $B$ (note that a good square must be part of a good block), which is surrounded by eight squares. Since there are two blocks next to $B$, and there are no bad blocks in $R$, we must have a good square in both. Thus $X\le(8-2)b(n)=6b(n)$.

Now consider a bad square $S$, which is surrounded by four squares. If three or more of these four squares are bad, then we have a bad block, so at most two of them are bad. Hence if $S$ is not on the border of $R$, then it must border at least two good squares. But there are at least $(n-2)^2-3b(n)$ bad squares not on the border of $R$, so $X\ge2(n-2)^2-6b(n)$.

Finally, we have
\[6b(n)\ge X\ge2(n-2)^2-6b(n)\implies b(n)\ge\frac{1}{6}(n-2)^2,\]which is clearly sufficient.

Lower bound:
Let $h$ and $c$ be the total number of horizontal and vertical blocks, respectively. Let $h_i$ and $c_i$ be the number of horizontal blocks and vertical blocks torn out in row $i$. Note that every horizontal block torn out prevents us from tearing out at most $5$ other horizontal blocks in row $i$, and each vertical block torn out prevents us from tearing out at most $3$ other vertical blocks in row $i$. Thus, $5h_i + 3c_i \ge n - 2$. Since each vertical block torn out is in $3$ rows, summing over all rows, each vertical block is counted 3 times and each horizontal block counted once, so
\[ \sum_{i = 1}^{n} (5h_i + 3c_i) = 5h + 9c \ge n(n - 2)\]
By using the same method for columns, we also get $9h + 5c \ge n(n - 2)$.
Adding the two equations gives us
\[14h + 14c = 14b(n) \ge 2n^2 - 4n \implies b(n) \ge \dfrac {n^2 - 2n} {7}\]

Does this work for the lower bound?

Let $x$ be equal to the number of squares covered by a $1 \times3$ block

For any square S, consider the 4 squares adjacent to it.

If S is empty, at least 2 of these squares must be covered.
If S is covered, and the center piece of a block, at least 2 of these must be covered.
If S is covered, and the edge piece of a block, at least one of these must be covered.

Thus (up to some linear error term because of the perimeter blocks)

$$ x \ge \frac{2\cdot open + 2\cdot center + edge}{4} $$
Since $\frac{1}{3}$ of all covered squares are center squares, we have $$ 4x \ge 2(n^2 - x) + \frac{2x}{3} + \frac{2x}{3}$$ which rearranges to $x \ge \frac{3}{7}n^2$ as desired

[quote=gubsheep]One bad way to approach the lower bound is to observe that, in any $3 \times 7$ rectangle on the grid, at least $9$ of these squares must be covered by $1 \times 3$ blocks (this can be done with casework). $\frac{9}{21} = \frac{3}{7}$, and the result follows via a contradiction argument.[/quote]

Why are you saying it's the "bad way" ? It's what I did, and it seems pretty straightforward despite the few caseworks...

[quote=MarkBcc168]Am I allowed to tear out the square which is not on the boundary? (In other words, am I allowed to make holes?)[/quote]

Yes. You can tear out the squares in any order.

[hide=Sketch]
First we show the upper bound. Note that if $10\mid n$, then we can cut the blocks given by $(1+5k,1+2\ell),(2+5k,1+2\ell),(3+5k,1+2\ell)$ and $(3+5k,2+2\ell),(4+5k,2+2\ell),(5+5k,2+2\ell)$, which removes $\frac{1}{5}n^2$ blocks, and leaves no blocks that can be removed. This shows the upper bound.

For the lower bound, note that there are $2n(n-2)$ blocks, and removing a block bars at most $13$ other blocks, so we have at least $\frac{2n(n-2)}{14}=\frac{1}{7}n^2-\frac{2}{7}n$ blocks to be removed before we stop. This shows the lower bound.
[/hide]

If whatever written below is correct the lower bound can be strengthened to $\frac{4}{23}n^2$ from $\frac{1}{6}n^2$...

Let a [i] tromino [/i] denote a block of $3$ stamps which satisfy the condition in the problem. Call a tiling of an $n \times n$ grid [i] full [/i] if no more trominos can be added to the tiling. \\

We first prove the upper bound. Note that there is a full tiling of a $5 \times 5$ grid with exactly $5$ trominos: indeed, in the first, third, and fifth rows, add a tromino that covers the first three squares of the row, and in the second and fourth rows, add a tromino which covers the last three squares. This is clearly a full tiling (since the maximal size of a contiguous group of untouched squares in the grid is $2$). Now, let $n = 5k + r$, where $k, r$ are integers are $r < 5$. Partition the top-left $5k \times 5k$ grid of the $n \times n$ grid into non-overlapping $5 \times 5$ grids. In each such grid, repeat the above described tiling for the $5 \times 5$ grid. It is clear that this tiling of the top-left $5k \times 5k$ grid is full. Now, there are $r$ rows and $r$ columns which have so far been untouched; in each such row or column, we can clearly use at most $\frac{n}{3}$ trominos. Hence, these $2r$ rows and columns will contribute at most $\frac{2nr}{3} \leq \frac{2 \cdot 4}{3}n = \frac{8}{3}n$ trominos, so we may take $d = \frac{8}{3}$. This proves the upper bound. \\

Now, we prove the lower bound. Consider a graph on the set of all possible trominos of the $n \times n$ grid. Connect two trominos with an edge if they intersect. Note that there are $2n(n - 2)$ vertices in this graph. The maximal degree of a vertex in this graph is $13$: for any given tromino, there are at most $9$ trominos intersecting it which are perpendicular to it,  and $4$ trominos intersecting it which are parallel to it. Now, consider a full tiling of the $n \times n$ grid. This corresponds to a maximal independent set of the graph. Suppose there are $j$ vertices in this independent set. Every vertex of the graph must be either adjacent to this set or in the set. However, the maximum number of vertices adjacent to this set is $13j$. Hence, we have
\begin{align*}
	13j + j&\geq 2n(n - 2) \\
	j &\geq \frac{1}{7}n^2 - \frac{2}{7}n \\
\end{align*}
This implies that we can take $c = \frac{2}{7}$, completing the proof. $\Box$

Not so Quick sketch (very bashy lol): $b = \frac{2}{5}$ and $c = \frac{2}{7}.$
[size=150]PROOF FOR UPPER BOUND:[/size]
Bash out cases for $n = 1, 2, 3, 4, 5, 6, 7, 8, 9.$ $b(n) = 5$. This means $\frac{3}{5}$ of the tiles in a $5\times 5$ are teared out. This will be important
We proceed with induction. Base case is done.

For all the rest of $n = 2k + m$ for $k \ge 2$ and $0 \le m \le 4$, consider $n = 2(k-1) + m $.
We can split this $2(k-1) + m$ into 4 "different" groups of rectangles. An $m \times m$ rectangle, $k-1$ total $m \times 5$ rectangles, $k-1$ total $5 \times m$ rectangles, and $(k-1)^2$ total $5 \times 5$ rectangles. We then add one $m \times 5$ rectangle, one $5 \times m$ rectangle, and $2k-1$ total $5\times 5$ rectangles.

Because we assume it works for $2(k-1) + m$, we let each of the rectangles from each of the $4$ groups have the same "tiling". It is easily proven that this leaves room for no blocks to be teared out.

Next, because everything except for the $m\times m$ rectangle has a dimension of $5$ in it, we can see that $\frac{3}{5}$ of the tiles in these rectangles are teared out, so if $A$ is the area of a specific rectangle, there are a total of $\frac{A}{5}$ blocks that are teared out. Therefore, not including the $m\times m$ square, there are a total of $\frac{n^2-m^2}{5}$. This is an integer because we defined m as the remainder of $n/5$.

Finally, we just need to count how many blocks are teared out in the $m\times m$ rectangle. We could just let $d$ be arbitrarily large and $dn \ge T$ where $T$ is the total number of blocks teared out in the $m\times m$ rectangle, but $d = \frac{2}{5}$ is specific.

There are a lot of proofs for the lower bound already.

[hide=Super, super easy for a USAMO 6? Rough sketch]
For the upper bound we can construct a series of "staircases" of all vertical blocks offset by one space, each staircase separated by two white spaces per column. This gives the bound $\frac{n^2}{5}+O(n)$. Now for the lower bound we consider row by row. WLOG there are at least as many horizontal blocks as vertical blocks. Possibly ignoring at most two blocks to the left of the first black square in a row, we find that each block can be followed by at most two white squares. Thus if it is horizontal there are $3$ black and $2$ white and vertical gives $1$ black and $2$ white squares. But by the assumption there are thus at least as many black as white squares, so the number of black squares is at least $\frac{n^2}{2}+O(n)$ so the number of blocks is at least $\frac{n^2}{6}+O(n)$ which is definitely larger than $\frac{n^2}{7}$ as desired.
[/hide]

Not even 20 mohs imo.
Replace tearing out stamps with covering/tiling them. Consider a sheet with every possible block of stamps drawn out already (on top of each other). It is clear that there are $2n(n-2)$ of these. It is also not hard to verify that any block of stamps covers at most 14 blocks, including itself: 9 blocks with opposite orientation and 5 with similar orientation. If there are no more blocks to be covered, this means that every block of stamps is covered. In order for this to happen, we need at least
$$\frac{1}{14}\cdot 2n(n-2)=\frac{1}{7}n-\frac{2}{7}n$$
stamps, so $\tfrac{1}{7}n^2-cn \leq b(n)$. This establishes the upper bound.

It remains to prove the upper bound. Note that we only care about the asymptotic behavior of $n$, since if $b(n)$ is large for some interval that doesn't extend infinitely in the positive direction, we can just make $d$ extremely large to account for this. By selecting an appropriate choice of $d$ such that $b(n)\leq \tfrac{1}{5}dn$ for $n \in \{1,2,\ldots,15\}$, it suffices to verify $n \geq 16$.
Now let $f(n)$ denote the largest positive multiple of $5$ such that $n \equiv f(n) \pmod{3}$ and $n \geq f(n)$. Note that for $n \geq 16$ this function is well-defined, since $\{5,10,15\}$ covers all residues mod 3. Also observe that $n-f(n) \leq 15$.
Define a "cool tiling" to be a tiling of a 5x5 sheet of stamps that looks as shown:
[asy]
unitsize(35);
for(int i=0; i<=5; ++i) {
draw((0,i)--(5,i));
draw((i,0)--(i,5));
}

fill((0.2,0.2)--(0.2,0.8)--(2.8,0.8)--(2.8,0.2)--cycle,red);
fill((0.2,2.2)--(0.2,2.8)--(2.8,2.8)--(2.8,2.2)--cycle,red);
fill((0.2,4.2)--(0.2,4.8)--(2.8,4.8)--(2.8,4.2)--cycle,red);
fill((2.2,1.2)--(2.2,1.8)--(4.8,1.8)--(4.8,1.2)--cycle,red);
fill((2.2,3.2)--(2.2,3.8)--(4.8,3.8)--(4.8,3.2)--cycle,red);
[/asy]
where red bars represent stamps torn out/blocks tiled. It is clear that by repeating this tiling and mirroring alternating rows (but not columns), we obtain a tiling that involves $5k^2$ blocks in a $5k \times 5k$ grid. Here is an example for $k=3$.

[asy]
unitsize(12);
for (int j=0; j<=10; j+=5) {
for (int k=0;k<=10; k+=5) {
for(int i=0; i<=5; ++i) {
draw((j,i+k)--(5+j,i+k));
draw((j+i,k)--(j+i,5+k));
}
if (k==5) {
fill((j+0.2,k+1.2)--(j+0.2,k+1.8)--(j+2.8,k+1.8)--(j+2.8,k+1.2)--cycle,red);
fill((j+0.2,k+3.2)--(j+0.2,k+3.8)--(j+2.8,k+3.8)--(j+2.8,k+3.2)--cycle,red);
fill((j+2.2,k+0.2)--(j+2.2,k+0.8)--(j+4.8,k+0.8)--(j+4.8,k+0.2)--cycle,red);
fill((j+2.2,k+2.2)--(j+2.2,k+2.8)--(j+4.8,k+2.8)--(j+4.8,k+2.2)--cycle,red);
fill((j+2.2,k+4.2)--(j+2.2,k+4.8)--(j+4.8,k+4.8)--(j+4.8,k+4.2)--cycle,red);
} else {
fill((j+0.2,k+0.2)--(j+0.2,k+0.8)--(j+2.8,k+0.8)--(j+2.8,k+0.2)--cycle,red);
fill((j+0.2,k+2.2)--(j+0.2,k+2.8)--(j+2.8,k+2.8)--(j+2.8,k+2.2)--cycle,red);
fill((j+0.2,k+4.2)--(j+0.2,k+4.8)--(j+2.8,k+4.8)--(j+2.8,k+4.2)--cycle,red);
fill((j+2.2,k+1.2)--(j+2.2,k+1.8)--(j+4.8,k+1.8)--(j+4.8,k+1.2)--cycle,red);
fill((j+2.2,k+3.2)--(j+2.2,k+3.8)--(j+4.8,k+3.8)--(j+4.8,k+3.2)--cycle,red);
}
}
}
[/asy]

Now for the general construction. For any $n \geq 16$, we can use the tiling shown above to tile the $f(n) \times f(n)$ square in the lower left. Then we can cover all of the remaining stamps. Here is an easily generalizable example for $n=16$:

[asy]
unitsize(12);
for (int i=0; i<=16;++i) {
draw((0,i)--(16,i));
draw((i,0)--(i,16));
}
draw((0,10)--(16,10),linewidth(2));
draw((10,0)--(10,10),linewidth(2));
for (int j=0; j<=5; j+=5) {
for (int k=0;k<=5; k+=5) {
if (k==5) {
fill((j+0.2,k+1.2)--(j+0.2,k+1.8)--(j+2.8,k+1.8)--(j+2.8,k+1.2)--cycle,red);
fill((j+0.2,k+3.2)--(j+0.2,k+3.8)--(j+2.8,k+3.8)--(j+2.8,k+3.2)--cycle,red);
fill((j+2.2,k+0.2)--(j+2.2,k+0.8)--(j+4.8,k+0.8)--(j+4.8,k+0.2)--cycle,red);
fill((j+2.2,k+2.2)--(j+2.2,k+2.8)--(j+4.8,k+2.8)--(j+4.8,k+2.2)--cycle,red);
fill((j+2.2,k+4.2)--(j+2.2,k+4.8)--(j+4.8,k+4.8)--(j+4.8,k+4.2)--cycle,red);
} else {
fill((j+0.2,k+0.2)--(j+0.2,k+0.8)--(j+2.8,k+0.8)--(j+2.8,k+0.2)--cycle,red);
fill((j+0.2,k+2.2)--(j+0.2,k+2.8)--(j+2.8,k+2.8)--(j+2.8,k+2.2)--cycle,red);
fill((j+0.2,k+4.2)--(j+0.2,k+4.8)--(j+2.8,k+4.8)--(j+2.8,k+4.2)--cycle,red);
fill((j+2.2,k+1.2)--(j+2.2,k+1.8)--(j+4.8,k+1.8)--(j+4.8,k+1.2)--cycle,red);
fill((j+2.2,k+3.2)--(j+2.2,k+3.8)--(j+4.8,k+3.8)--(j+4.8,k+3.2)--cycle,red);
}
}
}
for (int i=0; i<10;++i) {
fill((10.2,0.2+i)--(10.2,0.8+i)--(12.8,0.8+i)--(12.8,0.2+i)--cycle,red);
fill((13.2,0.2+i)--(13.2,0.8+i)--(15.8,0.8+i)--(15.8,0.2+i)--cycle,red);
}
for (int i=0; i<16;++i) {
fill((0.2+i,10.2)--(0.8+i,10.2)--(0.8+i,12.8)--(0.2+i,12.8)--cycle,red);
fill((0.2+i,13.2)--(0.8+i,13.2)--(0.8+i,15.8)--(0.2+i,15.8)--cycle,red);
}
[/asy]
It is clear that such a tiling uses:
$$\frac{1}{5}f(n)^2+2f(n)(n-f(n))+(n-f(n))^2 \leq \frac{1}{5}n^2+30n+225.$$
Picking a large enough $d$, we have $\tfrac{1}{5}n^2+dn\geq \tfrac{1}{5}n^2+30n+225$. Hence it is possible to tile the $n \times n$ grid with $\tfrac{1}{5}n^2+dn$ blocks, so $b(n) \leq \tfrac{1}{5}n^2+dn$. This establishes the upper bound. $\blacksquare$

Call a set of 3 in a rows of either orientation a tromino.

$\textbf{Lower Bound: }$. Note that there are $2\cdot n \cdot (n-2)=2n^2-4n$ tromino. Then, note that each tear deals with at most $3\cdot 3$ verticals + $5$ horizontals, for a total of 14 trominos precluded by each tear. Thus, since all trominos are precluded,
\[14\cdot b(n) \geq 2n^2-4n\]
Or,
\[b(n)\geq \frac{1}{7}n^2-\frac{2}{7}n\]
$\blacksquare$.

$\textbf{Upper Bound: }$. We provide a construction, in each of the odd columns, number the squares from $1\to n$, then for all $k\geq 0$, tear the triplets $(5k+3,5k+4,5k+5)$. In the even columns, for all $k\geq 0$, tear $(5k,5k+1,5k+2)$. Finally, note that depending on $n$, the bottom row may have that half of the columns are empty there, and if those columns have $\geq 3$ empty squares, make a tear there. Thus, the total number of trominos used here is at most
\[b(n) \leq n\cdot\lceil \frac{n}{5}\rceil \leq \frac{1}{5}n^2+n\]
$\blacksquare$.

For the upper bound, let $n = 5k+r$. For the $5k \times 5k$ grid, on each row, (identify a block by its center piece) tear the blocks $2 \pmod 5$ and $4 \pmod 5$ alternately, which works. This uses $\frac{1}{5} (5k)^2 = 5k^2$ blocks. For the remaining grid, cover everything with blocks, which uses at most $10kr + r^2 \le 40k + 16$ blocks (yes this is terrible bounding but no one cares about constants). So a total of at most $5k^2 + 40k + 16 = \frac{1}{5} n^2 + 8n$ blocks are used so we may pick $d = 8$.

For the lower bound, define the [i]weight[/i] of a block in a particular row/column to be $3$ if its in the opposite orientation of the row/column and $5$ otherwise, this denotes the number of squares the block ensures needn't be tiled by other new blocks. Clearly, every row/column must have weight at least $n-2$ so the total weight summed across the entire board must be at least $2n(n-2)$. But also, each block has a weight of at most $9$ perpendicular to it and $5$ parallel to it, which is at most $14$. So we have $14b(n) \ge 2n(n-2) \implies b(n) \ge \frac{1}{7}n^2 - \frac{2n}{7}$ so picking $c = \frac{2}{7}$ works. $\blacksquare$

Here is a proof of the lower bound only (for $c=\frac{2}{7}$).
Suppose that we have cut out a maximal number of blocks. To each removed block assign the blocks intersecting it (including the removed block itself). It is easy to see that there are at most $14$ blocks assigned to each block. In addition, each block is assigned to at least one removed block. Hence $14b(n) \geq 2n(n-2)$ (this is the number of blocks), so we are done.

Note that there are a total of $n(n-2)$ possible ways to cut a horizontal block and as many to cut a vertical one. Each cut block renders at most $14$ other ones not possible to be cut out, so $14b(n)\ge 2n(n-2)$ which gives us our lower bound.
\\$~$\\
Now, to prove the upper bound we simply need to find successful cases. First, let $5k$ be the smallest multiple of $5$ less than $n$. Now, cut the bottom-left $5k\times 5k$ into $5k$ vertical strips, and in the left-most vertical strip cut out the lowest possible block, then going up: skip two and cut the next three out, and so on. In the second left-most strip, do the same but skipping one at the beginning. In the third left-most strip, do the same but skipping two at the beginning. In the fourth left-most strip, do the same as the first left-most strip, and repeat this process every three.
\\$~$\\
Now, we see that this gives us $b(5k)\le 5k^2$, which proves what we want about $n=5k$. Additionally, note that even if we cut blocks super suboptimally in the remaining top horizontal lines and right vertical lines, we will only ever cut out $O(n)$ strips, so we are done.


aug 21

The message is too small. Please make the message longer before submitting.

there, long enough?

couple of things

1) star99, r u from ct? star 99.9?
2) u can do it in latex and it passes the message filter
3) star99's school starts early
4) totally zealuous, who do u agree with?

5) this message is too big. make it smaller before submitting

jk

[quote="mtms5467"][quote="akalra1"]i personally think summer break is too long

it gets boring after teh frist 2 weeks of doing nothing[/quote]
Really? How much break do you get? My school has really long breaks, we got out June 8th, and we have really long Winter/Spring vacations too. But we don't get a lot of other days off, like Columbus day, etc. Also, all Wednesdays are half days! (8:00-1:30) but other days dismissal's at 3:30. Our period schedulings are also really weird. But it's a private prep school so I guess the schedule can be as different as they want it to be... :roll:[/quote]

you are lucky! But our school gets out 2:26 everyday not 3:30 :)

We had no half days this year...

2:26? Not a "rounder" time like 2:25 or 2:30? :P jk.

At what time does your school start in the morning, nonie?

[quote="mtms5467"][quote="shobber"]Sometimes I really hope that I was born in the US. You have such a long summer vacation!

Mine is from 7.7 to 8.31. I think it is acceptable but still not long enough.[/quote]
Is the school day really long in China? I hear they also give thick packets of work to be done over the summer, is that true?[/quote]
Not my school. But indeed, most schools give students a lot of work to do. But I think that although I don't consider my homework to be "thick packets", it may still be "thick packets" for you.

My school day ends at 7.7 and restart at 8.31, then ends at around 1.10, and start one month later.

[quote="akalra1"]no offense to american school systems, but the math classes up to sixth grade dont really make a difference. u just learn the basics, u could learn that in a week if u were homeschooled

i guess china has a real math curriculum[/quote]
It's just practice. The workload is higher there. Also, I think their standard curriculum is a year or two ahead of the one here.

[quote="joml88"][quote="akalra1"] u just learn the basics, u could learn that in a week if u were homeschooled[/quote]

If/when I have a child, I'll pay you a considerable amount of money to teach it all of elementary school math during his/her's first week of 1st grade.  Deal? :D[/quote]

deal

we will work 25 hours a day, drilling all those facts into her / him

[quote="akalra1"]i personally think summer break is too long

it gets boring after teh frist 2 weeks of doing nothing[/quote]

Not if you actually do stuff...

yea, but wen u do NOthing, it kinda gets boring

My school starts August 14th, too early  :mad:

I'm kinda mixed about summer ending, school can sometimes be fun for the social aspect and stuff...but it's more stressful and I can't wake up at 10:30 anymore.

for summer camp, i usually wake up at 700 or 730

school, 700

weekends.... 1100

My summer camp was a wilderness camp in the Maine backcountry. We usually woke up 6:30-7:30, depending on how much travel we were doing that day.

Year round weekends I wake around 8:30. Although if nothing was planned for that day and I got really little sleep the previous night, I might wake up 9-10.

For me its September 6th.

They sent us a math packet on August 1st.  :|

[quote="mtms5467"]Wow, you wake up 10:30 in the summer? I wake up around 7:30! Normally during the school year I wake 6-6:30.[/quote]

You're surprised by that?
I wake up at 1-2pm during summer :|

For me school starts on august 21st...

I'm going back monday, I'm preparing for SATs.
I wake up sometimes 8:30, half the time 7:30, rarely 6:30


calculus
derivative
function
logarithms
trigonometry
calculus computations

Obtain the derivative of the following function:

f(x) = exp(sin2x)

Use the Chain Rule twice.  $[f(g(h(x)))]' = f'(g(h(x))\cdot [g(h(x))]' = f'(g(h(x)))\cdot g'(h(x))\cdot h'(x)$ for $f$,$g$, and $h$ appropriate to your question.

[hide="Example"]
Find the derivative of $\sin{(2e^{x})}$.  Then you could think $f(x) = \sin{x}$, $g(x) = 2x$, and $h(x) = e^{x}$ so that $f(g(h(x))) = \sin{(2e^{x})}$.
When you get used to it, it becomes automatic.  $[\sin{(2e^{x})}]' = \cos{(2e^{x})}\cdot [2e^{x}]' = \cos{(2e^{x})}\cdot 2 \cdot [e^{x}]' = \cos{(2e^{x})}2e^{x}$.[/hide]

Yes that is correct for any "a" and just subbing in e = a will give the required result. The derivation goes something as follows:

y = a^(sin2x)

Taking natural logs of both sides:
lny = ln(a^(sin2x))

Applying power law of logs:
lny = (sin2x)lna

Differentiating each side implicitly with respect to x and tidying:
(1/y)(dy/dx) = 2(Lna)cos2x
(dy/dx) = y(ln(a^2))cos2x

Substitute y as a function of x:

(dy/dx) = (a^(sin2x))(Ln(a^2))cos2x

Try to derivate the function:
$f(x)=x^{\sin{2x}}$.

I got the derivative as:

f'(x) = (x^(sin2x - 1))(x(cos2x)ln(x^2) + sin2x)

Here is the derivation:

For convenience, let y = f(x)

y = x^(sin2x)
Lny = Ln(x^(sin2x)) = (sin2x)Lnx
(1/y)(dy/dx) = 2(cos2x)(lnx) + (sin2x)/x = (cos2x)Ln(x^2) + (sin2x)/x
dy/dx = y( (cos2x)Ln(x^2) + (sin2x)/x) = (x^(sin2x))( (cos2x)Ln(x^2) + (sin2x)/x)
= (x^(sin2x - 1))(x(cos2x)Ln(x^2) + sin2x)

You are wrong. Note:
$x^{\sin{2x}}=e^{\sin{2x}\ln{x}}$

Yes that is another way to do it, but why is my solution incorrect? Please tell me at which point my proof goes astray.

As I can see, you used $d(x^{a})=ax^{a-1}\,dx({a}\in{R},x>0)$.
But in your case exponent is not constant, it is function of $x$.

It doesn't matter whether it is constant or not. I used the product rule differentiate afterwards which accounted for the fact that x is variable.

SORRY. I saw that you have $x^{\sin{2x}-1}$ in final line and I thought you made a mistake. I didn't look the rest of it. I have to be more carefull :blush: .

using your method:

y = x^(sin2x)
y = e^((sin2x)Lnx)
dy/dx = (2(cos2x)Lnx + (sin2x)/x)e^((sin2x)lnx)
dy/dx = ((cos2x)Ln(x^2) + (sin2x)/x)(e^(Lnx))^(sin2x)
dy/dx = ((cos2x)Ln(x^2) + (sin2x)/x)x^(sin2x)
dy/dx = (x^(sin2x))((cos2x)Ln(x^2) + (sin2x)/x)
dy/dx = (x^(sin2x - 1))(x(cos2x)Ln(x^2) + (sin2x))

[quote="Ognjen09"]Try to derivate the function:
$ f(x) \equal{} x^{\sin{2x}}$.[/quote]
$ f(x) \equal{} x^{\sin{2x}}\ \stackrel {(\ln)}{\implies}\ \ln f(x) \equal{} \sin 2x\cdot\ln x\ \stackrel {(')}{\implies}$

$ \frac {f'(x)}{f(x)} \equal{} 2\cos 2x\cdot\ln x \plus{} \frac 1x\cdot\sin 2x\ \implies$

$ f'(x) \equal{} x^{\sin{2x}}\cdot\left[2\cos 2x\cdot\ln x \plus{} \frac 1x\cdot\sin 2x\right]$ .


Let be $ \alpha\ ,\ \beta\ ,\ \gamma$ the angles of a triangle . Prove that :

$ ctg\ \alpha \ , \ ctg\ \beta \ , \ ctg\ \gamma$ are in arithmetic progression $ \Longleftrightarrow \cos\ 2\alpha\ ,\ \cos\ 2\beta\ ,\ \cos\ 2\gamma$ are in arithmetic progression .

If you're meaning the cotangents of those angles,
then it would be:

[quote="Pain rinnegan"]Let be $ \alpha\ ,\ \beta\ ,\ \gamma$ the angles of a triangle . Prove that :

$ cot\ \alpha \ , \ cot\ \beta \ , \ cot\ \gamma$ are in arithmetic progression
$ \Longleftrightarrow \cos\ 2\alpha\ ,\ \cos\ 2\beta\ ,\ \cos\ 2\gamma$ are in arithmetic progression .[/quote]

$ \mathrm{ctg}\,x$ is a completely legitimate notation for $ \cot x$, used mostly in Europe.

Also: $ \mathrm{tg}\,x\equiv\tan x$ and $ \mathrm{cosec}\,x\equiv\csc x$

Suppose $ 2\cot \gamma \equal{} \cot \alpha \plus{} \cot \beta$, then $ \cot \alpha \plus{} \cot \beta \equal{} 2\cot(\pi \minus{} \alpha \minus{} \beta) \equal{} \minus{} 2 \cdot \frac {\cot \alpha \cot \beta \minus{} 1}{\cot \alpha \plus{} \cot \beta}$ $ \Longrightarrow (\cot \alpha \plus{} \cot \beta)^2 \equal{} \minus{} 2 \cot \alpha \cot \beta \plus{} 2$. Multiplying out gives
\[ 4\cot \alpha \cot \beta \equal{} 4 \minus{} \csc^2 \alpha \minus{} \csc^2 \beta,
\] and clearing denominators and factoring gives
\[ 4\sin 2\alpha \sin 2 \beta \equal{} (4\sin^2 \alpha \minus{} 1)(4 \sin^2 \beta \minus{} 1 ) \minus{} 1.
\] We have $ 1 \minus{} 4\sin^2 \alpha \equal{} 2 \cos 2\alpha \minus{} 1$, so $ 4\sin 2\alpha \sin 2 \beta \equal{} (2\cos 2\alpha \minus{} 1)(2 \cos 2\beta \minus{} 1 ) \minus{} 1$ $ \Longrightarrow \cos 2\alpha \plus{} \cos 2\beta \equal{} 2\cos 2(\alpha \plus{} \beta) \equal{} 2\cos 2\gamma$, as desired.


limit
number theory proposed
number theory

let $f: \mathbb{N}\longrightarrow \mathbb{N}$ be one to one function.  $k$ is a fixed positive integer such that$f(n)\le n^k$

provethat there exist infty prime $q$ such that $f(x)\equiv 0(\mod q)$ has answer in prime numbers.

Suppose there is just an finite amount of divisors of the values of $f$ and call them $p_1,p_2,...,p_m$.
Then for $n> p_i$ the amount of numbers only divisible by those and smaller than $n^k$ is at most $\prod_{k=1}^m (log_p(n^k)+1) \leq \prod_{k=1}^m log_p(n^{k+1}) \leq (k+1)^m log_{2}(n)^m$.
But $\lim_{n \to \infty} \frac{(k+1)^m log_{2}(n)^m}{n}=0$, so there are not enough such numbers for big $n$ such that all values of $f$ can be different. Contradiction.


calculus
articles
trigonometry
analytic geometry
vector
AMC
USA(J)MO

[quote="matt276eagles"]This year, I took Honors Algebra II in school.  I found that I already knew almost all of the curriculum.  Only a few subjects were mildly new to me, and I think I could have taught myself those subjects in a few weeks.

I am expected to take Honors Precalculus next year, but I'm afraid that the same thing will happen to me again, so I'm considering skipping to Calculus.  I don't want to fall into the so-called calculus trap, but then again I don't want to waste another year of math class learning stuff I already know.

Any insights?  I would like to hear from other people who have skipped high-school math courses, as I'm sure there are many on this forum.  :)[/quote]

I would look through the Precalculus curriculum and see if you know it all (comfortably) already or not.

In my school, you must take an exam to be able to skip a class. If you do good on that exam, there shouldn't be much problem with skipping (usually those exams are comprehensive).

I don't know how your school does the skipping thing though...

By contrast, I am a big advocate of doubling up math courses. But they do have to be [b]good[/b] math courses, which are hard to find in United States schools. I see you are already aware of Richard Rusczyk's [url=http://www.artofproblemsolving.com/Resources/AoPS_R_A_Calculus.php]calculus trap[/url] article, so I won't belabor that point, but I might recommend seeing if your school will let you take a different precalculus course, for example the [url=http://www.ctd.northwestern.edu/learning/courseshonors.html#26]Math and Computers Honors[/url] course offered by the Center for Talent Development, or one of the EPGY courses.

With any luck, you should be able to skip pre-cal. Do you know trig? At our school, in the.... er, we'll call it the honors program.... in the honors program, everyone takes honors algebra ii and honors trig in 10th grade. then (under our new system) you take a test, and about half the class goes into cal bc, and the other goes into cal ab (under the old system, it was either cal bc or pre-cal). this has worked pretty well for us, but then again, our alg ii teacher taught us with the aim that we would not need pre-cal. in the regular program, it went alg ii, pre-cal, cal ab. however, they learned trig in pre-cal class, while we learned it in alg ii. also, i found that when we got to physics (and cal3), we were WAY behind on polar and 3d stuff. basically, they had to teach us polar coordinates, vectors, and working in 3d all in calculus/physics. which worked out okay but made things kind of hard for me for a while in physics, because i had a really hard time, spatially, with 3d vectors (not a hard concept, i know, but i'm VERY visual).

so that's how we worked, right, so you probably need to go over your pre-cal curriculum with that teacher and ask about those concepts, make sure you know them.

Basically same as Steinhardt said.  Just see how the precal material looks to you.  I don't know how good the math teachers are at your school (they're not impressive at mine) but precal is precal and you can only learn the same standard curriculum so many ways.  You're one of the freshmen usamo qualifiers aren't you?  Doing so well on the aime just shows you can do much harder problems than they give you in school anyway, so you should have a good grasp on alg II and precal anyway.
Personally, I had straight 100s in geom (not to brag), skipped alg II, then made all 100s in precal.  Still didn't learn anything in there (except how to use my calculator for some stat functions) and wondered whether just taking ap cal my sophomore year instead would have been better.  Understanding the calculus trap,  I think we should also understand that we have to take calculus and those harder classes sometime and postponing an inevitability to waste away in a class where you won't learn anything (or a negligible amount given it's yearlong) is a bad idea.

Well, in my case, I greatly regret that I took Pre-Calc, because, basically I knew almost all the stuff.
It feels like I've just wasted one year in that math class :(
Now, I'm pushing my younger brother to take Calc. next year (his soph. year). My brother is in Alg. 2 / Trig. (freshman).

usually they have you take a challenge test to skip a course.  be aware of the fact that they probably won't agree to let you even take the test if you are already 'advanced' so you might want to have a teacher directly recommend you to the counselor or who ever needs to know.

I skipped my college math course all the time. I made an A in it.
However, the professor doesn't usually like it when someone is in front of the class reading a biology book.
She left me alone because I always aced the tests.

I suggest you sit in the back of the class.

You could always go to your local college and CLEP out of some courses.
It costs about $50 USD per test, and most colleges want you to get 70% of the questions right to pass.

Afterwards when you have college credit, you could tell your teachers to screw off.

Thanks for all the advice, everyone.

As far as I know, my school doesn't have special tests to see if you're able to skip a class.  I have talked to one of my teachers about skipping Precalc, and she said that it might be possible to take the Precalc midterm and final over the summer - not as a test to determine whether I would be allowed to skip, but just for me to make sure I know all the stuff I'm supposed to know.

My freshman year was basically wasted doing alg2/trig.  So, I asked the head of the department if I could go into calculus sophomore year (that was this year) instead of the precalc course he teaches.  I had looked at the curriculum and made sure I knew everything.  Little did I know that he taught things outside the curriculum.  He teaches in a way which appeals to interested, (dare I say it?) smart students.  Although I knew a lot of the things in his class, I learned new stuff, and understood many things in a new light.  To top it off, I took calculus (which is normally taught by a different teacher) concurrently through the EPGY program with Stanford, and took the AP.  The net result is better than taking calculus.  I would say that worked well.

Well, getting to answering your question, I would suggest talking to the teachers.  If there's anything you don't know, you can cover it with them.  I don't know about your school, but my school has a cousre called Math Seminar.  The head of the department (who's really really smart and really good at teaching, also teacher honors precalc) teaches it.  He develops a different curriculum each year, but the class does problem solving, and does various kinds of math.  This year, they had number theory for part of the year I know, and have problem sets.  I'm sure it's also taught at a fast pace.  They can also do projects.  A course like that would be ideal I think.

But whether or not you learn something depends on who teaches the course...

I am currently a freshman taking Algebra II. At our school, anyone who takes an exam to skip Pre-Algebra (or who doubles up) can take Alg 1 7th, geo 8th, etc...

Like with many people, I mostly know the concepts I've been learning. The head of the math department at our school will let me take the precalc midyear and final over the summer so that I can get into BC Calc next year.

This year, I tried to skip Algebra II, but didn't succeed. Although I knew most of the concepts, I was somewhat rusty on my algebra. So, after about half a year of pointless classes, I talked to the math department head, with a proposal that I get to skip class, and only have to come when there's a test. After some discussion, we've started it, and it's working out well. I've been doing the homework (sometimes) to make sure I can do all the problems of the class quickly enough, but I [i]don't[/i] have to sit and listen to my teacher tell us what complex numbers or logarithms are when I already know that.

Hopefully I won't make the same mistake I made with Algebra II and actually do some problems for the Pre-Calc test (at our school the course is called Trig/Analytic Geo/Intro to Calc Honors). Unfortuneately, my school's math department has a strong focus on memorization-type math and especially, not on problem-solving.

Calculus next year shouldn't be too hard, except for the fact that the teacher (head of math department) gives hardly any partial credit ---> you can get a 90 for adding wrong. Heck, I already know most of the major concepts in calculus (limits, integrals, derivatives), there are just various random details and problems that I'll learn.

So just make sure you understand trig, algebra, functions and graphing, etc well enough to learn calculus. Maybe even learn a little bit about calculus on your own to see what you think of it.

Regarding the calculus trap, make sure you have a good hold into problem-solving, but otherwise, calculus is a pretty interesting topic  ;)

The teacher in charge of it at my school hates it when people skip. She makes the precalc test ridiculously hard...with calculus on it.

Her: "The test is really hard. Last year, only 1/42 people passed, but who knows, you might be that one in a million."  :huh: She teaches statistics too...

Precalc has always seemed to me like a rather vaguish kind of topic where your teacher could really teach it in many different ways.  I would suggest you talk to some precalc teachers at your school to find out what they do with their classes, it is possible to have a very hard/interesting class in almost any subject, even if you think you know the material.  I skipped precalc and it took me a while to finally figure out all those stupid polar coordinate shapes haha.  Little holes like that really shouldn't be a problem and I don't think somebody motivated like yourself would really have trouble in calculus.  Something about math in general though, it is not always good enough to know material, it is important that you do lots of problems that use the material.  I find that in my case you just forget all of the arguements or techniques if you don't ever use them.  So I would suggest not just looking at some books and being like, oh I know what that means, but rather do some pretty involved problems in that subject area.  I don't know how that might be feasible, but it seems to me that there is a huge difference between knowing something and being able to use it.

I'm attempting to place out of precalculus as well. Good luck (though I'm sure you won't need it)  :P

Yeah I felt like this after about 2 days of algbra 2 and thought ohh there can't be 2 years of math I already know.

for skipping Algbra 2 it was pretty easy I just had to learn some stuff about logs and trig took about 1 or 2 hours during my study hall and I passed the final with a 88%

for pre calc its a lot of the same but a little more analysis in graphing, some extra trig, more matrices,and polar graphing

i estimate it would take about a week of 1-2 hours every other day to truely understand all of there topics

have fun


trigonometry
induction
function
inequalities
triangle inequality

1. is it true that cos(cos(cos(cos...x converging?
will it converge to the same number every time?

2.is it true that if x is an integer, x^(x+1)>(x+1)^x where x>2

i discovered these seemingly true properties while playing with a calculator

[hide]Use logs on the second one [/hide]

for the cos one, does it matter what mode you are in? it seems like it would, because for instance
[tex]\cos{(\cos{0})}[/tex] is not the same in both modes...

however, i do believe it converges in both... for degrees because (this may not be a very rigorous proof but oh well) [tex] \cos{x} < x [/tex] for all [tex] x > \sim .9998 [/tex] which is when [tex] \cos{x} = \arccos{x} [/tex]. It keeps decreasing (or increasing) until you get there. I am guessing this is because then [tex] \cos{\cos{x}} = x [/tex] and it starts all over again...

its the same with radians except obviously a different number.

I'd suspect either mode would have similar results, but I'm not sure.

1) let f(x) = cos(x)

then f(f(......n......(x)) converges to a fixed point, because |f'(x)|  :le: 1

The same thing holds true for sin(x), but this is relatively useless because we all know that sin(0)=0, so that is the desired fixed point.

This is a rather appropriate introduction to fixed-point iteration, which I can elaborate upon a bit if anyone wants to know about it.

Lets prove it by induction:

Proposition:  x^(x+1)  :ge: (x+1)^x, for x :ge: 3, x E Z+

Basis Step:  3^4 = 81  :ge: 4^3 = 64

Inductive Step: x^(x+1)  :ge: (x+1)^x, for x :le: k

Then we multiply both sides by k.

so we have:

k^(k+2)  :ge: k(k+1)^(k)

But k  :le: (k+1), so we have that:

k^(k+2)  :ge: (k+1)^(k+1), as desired.

Hence the proposition is true for all x E Z+, x :ge: 3

[quote="JBL"]That wasn't the question he was asking.  Or, rather, it is only a first step.  He wanted to know if it converged to the same value for all x.[/quote]

The answer is yes, because cos(x) has only one fixed point.

Why?

Assume f(x) = x-cos(x) = 0 at least twice in x E R.  Then we can apply Rolle's Theorem.  Let the zeros be a,b, a < b.  Clearly, a,b E [-1,1] because |cos(x)|  :le: 1.  The function is clearly differentiable and continuous everywhere.

Then f'(x) = 1 + sin(x).  But if f'(x) = 0, then sin(x) = -1.  However, the smallest positive and negative zeros of sin(x) are - :pi: /2, 3 :pi: /2, neither of which are contained inside [-1,1].  Hence x-cos(x) has at most one real solution (easily verified by the intermediate value theorem), and hence it has only one fixed point.

#1: Consider a_n defined recursively, with a_0 given and a_n = cos(a_(n-1)), where we measure the angle in radians (I'm pretty sure the essential behavior is the same for angles in degrees). Then lim n--> infinity a_n exists and is indepedant of a_0.

Because cos(x) is bounded, -1 =< a_1 =< 1. Without loss of generality assume a_1 >= 0 (the proof for a_1 < 0 is similar).

 Then
a_2 is between cos(1) and 1.
a_3 is between cos(1) and cos(cos(1))
a_4 is between cos(cos(cos(1))) and cos(cos(1))
In general,  a_(2n) is between cos(...(1)) (iterated 2n - 1 times) and cos(....(1) (interate 2n - 2 times),

 while a_(2n-1) is between  cos(...(1) (interated 2n - 2 times) and cos(...(1) (interated 2n -1 times).

 This all follows from the fact that cos(x) is decreasing on [0, 1]. It appears that a_(n+1) must occupy a smaller interval that a_n. We must show that in the limit, this interval is a single point. Because the endpoints of the intervals are a_m for m = 1, 2, 3... for a_0 = 1 where m --> infinity as n --> infinity, it suffices to show that a_n --> L for a_0 = 1.

I claim that a_n --> L where L satisfies L = cos(L). Such a number exists - consider f(x) = cos(x) - x. Then f(0) = 1 > 0 and f(1) = cos(1) - 1 < 0 so by the intermediate value theorem cos(L) = L for some L in between 0 and 1.

Actually, in general if you have a sequence in the form of a_n = f(a_n-1) where f is continuous then if a_n approaches a limit L then L = f(L) (by taking the limit of both sides).

We want to show that for all e > 0 there exists an N such that |a_n - L| < e for n > N. Taylor expanding cos(x) about L where L is defined about we find that cos(x) = cos(L) - sin(L)(x - cosL)  - (cos(L)/2)(x - cos(L)^2 ....

So |a_n+1 - L| = |(cos(a_(n)) - cos(L)| (by definition of L and a_n)
 < = sin(L)|a_n - cos(L)| + (cos(L)/2)|a_n - cos(L)|^2 ... (by the triangle inequality)

 < = 0.9|a_n - cos(L)| + 0.9|a_n - cos(L)|^2 ... (because surely sin(L) and cos(L) < 0.9)

= 0.9|e^|a_n - cos(L)| -1|.

So by induction, |a_(n+m) - L| < = (0.9)^m |e^|a_n - cos(L)| - 1|.

But e^|a_n - cos(L)| - 1 is constant with respect to m and (0.9)^m goes to zero as m increases so the last expression gets arbitrary small as m increases and we must have a_n --> L.

#2: We can take logs of the inequality without reversing it because ln(x) is an increasing function:

(x+1)ln(x) > x ln(x+1). Because x > 2, x> 0 and we can divide by x and x + 1 and maintain inequality: ln(x)/x > ln(x+1)/(x+1).

This is true if f(x) = ln(x)/x is decreasing on [3, infinity].
But f'(x) = [1 - ln(x)]/x^2 < 0 iff ln(x) > 1 or x > e. So f'(x) is decreasing on [3, infinity] so original inequality is certainly true for x > = 3.

There is an easier way to get a bound on |cos(an) - L|.  By the Mean Value Theorem, |cos(an) - L| :le: |sin(c)| |an - L|, where c is between an and L.  Because an is between -1 and 1 for n :ge: 1, we have |sin(c)| :le: sin(1) :le: 0.9.  Thus the differences from L are getting exponentially small.

[quote="blahblahblah"]
k^(k+2)  :ge: k(k+1)^(k)

But k  :le: (k+1), so we have that:

k^(k+2)  :ge: (k+1)^(k+1), as desired.
[/quote]

First of all, I don't see why k :le: k+1 gives us the last equation.  Second of all, why does the last equation do anything?  It's not even true; 3^5 = 243 < 256 = 4^4.  Could you clarify?

[quote="JBL"]Right -- in the first case, you made the smaller side [i]larger[/i] when you switched k to (k + 1) which does not preserve the inequality as you claimed.  Additionally, the final form you reached is the wrong form.[/quote]

Agh, shoot me.  Next time, I'm using calculus.

[tex]\displaystyle\frac{(n+1)^n}{n^n} = \left(1+\frac{1}{n}\right)^n < e < n[/tex]

Thanks Ravi, I had a feeling that what I was doing was somewhat convoluted. I haven't taken analysis yet but I really like it and hope to eventually learn how to do epsilon delta proofs fluidly.


a polynomial has alway 1 real root which doesnt change, always two complex conjugate roots which only changes by some numbers after the decimal point, not before decimal point, overall it has 5 roots,the coefficients are all real. the sign variation is always 5.
with this much information given, what else can we find out about this polynomial?

I believe the word you're looking for is (edited) "quintic."  And I don't quite understand what you mean by "change."  Is this a polynomial whose coefficients and roots are unknown or varying?

No it is quintic ($deg(f(x))=5$) sorry about my spelling, yes the coefficients are unknown, i mean it is for example 1 of out 60 numbers (prob of coefficients $= \frac{1}{60}$) which are known, but is varying each time. the coefficients are real numbers never complex.
the 2 complex conjugate roots are similar before the decimal point, but changes after the decimal point each time. i mean the roots are like (for example: $x=2.12345\pm5.3421i,1.6543\pm3.0987i$
for every polynomial the roots changes after the decimal points only ($x=2.02545\pm5.4429i,1.6543\pm3.1987i$). i hope i have xplained well

I don't really understand the motivation behind this problem.  Why the arbitrary decision to make the variation in the complex roots occur after the decimal point, for example?


algebra
polynomial
superior algebra
superior algebra theorems

Greetings. I am just beginning to learn about homomorphisms and other attributes of the algebraic structures. I am having trouble going through the following argument which shows that a certain mapping induces an isomorphism betw. two rings.

 Feel free to add as little as you like, as even the slightest nudge in the right direction would be appreciated! (-:

1. Let $ F \equal{} \mathbb{F}_2$ and $ h(x) \equal{} x^3 \plus{} x \plus{} 1$. [color=red]Then...[/color] $ h(x)$ is irreducible in $ F[x]$
2. In $ F[x]/h(x)$, let $ \alpha \equal{} [x]_{h(x)}$. [color=red]Then...[/color] $ \alpha^3 \plus{} \alpha \plus{} 1 \equal{} 0$
3. Consider the map $ \phi$ from $ F[x]$ to $ F[x]/h(x) \equal{} F[\alpha]$ given by $ \phi(q(x)) \equal{} q(\alpha^3)$. [color=red]Then...[/color] the minimal polynomial of $ \alpha^3$ over $ F$ is $ g(x) \equal{} x^3 \plus{} x^2 \plus{} 1$
4. From $ \alpha^3 \plus{} \alpha \plus{} 1 \equal{} 0$ we have $ (\alpha^3)^2 \plus{} (\alpha^3)^3 \plus{} 1 \equal{} 0$, [color=red]and so...[/color] $ \alpha^3$ is a root of the polynomial $ g(x) \equal{} x^3 \plus{} x \plus{} 1 \equal{} 0$
5. But $ g$ is irreducible, so $ g$ is then the minimum polynomial of $ \alpha^3$, [color=red]and so:[/color] (Steps 4 and 5 taken together are perhaps the most enigmatic!)
6. $ \phi$ induces a 1-1 homomorphism $ F[x]/g(x)\rightarrow F[x]/h(x)$ which is actually an isomorphim (since the two fields have dim. 3 as vectorspaces over F.)

Thanks,

Losl

1. A polynomial of degree $ \leq 3$ in a field is irreducible iff it has no roots.

2. It is $ \alpha^3 \plus{} \alpha \plus{}1 \equal{} [x]^3\plus{}[x]\plus{}[1] \equal{} [x^3\plus{}x\plus{}1]\equal{}[h(x)]0$ in $ F[x]/h(x)$.

3. Note that $ \alpha^3 \equal{}\minus{}\alpha\minus{}1$. But 3 is exactly what you prove in 4 and 5!

4. This is wrong, in 3 you have shown that the minimal polynomial is not $ x^3\plus{}x\plus{}1$ but $ x^3\plus{}x^2\plus{}1$. And see 3 again.

5. See 1 and 3 again.

6. Use the homomorphism theorem.

i don't think we can avoid the conclusion of 4. step, since: $ \alpha^3\plus{}\alpha\plus{}1\equal{}0$ then $ \alpha^6\plus{}\alpha^9\equal{}0$ and so we must have
$ (\alpha^3)^2\plus{}(\alpha^3)^3\plus{}1\equal{}0$, and so $ \alpha^3$ must be a root of $ g(x)\equal{}x^3\plus{}x^2\plus{}1$. There is something fishy going on...

There's really nothing terribly surprising here; it's a well-known fact that any two finite fields with the same cardinality are isomorphic. Your calculations here show that the elements of the field of order $ 8$ can be partitioned into the base field elements $ 0$ and $ 1$, the roots of $ x^3\plus{}x\plus{}1\equal{}0$, and the roots of $ x^3\plus{}x^2\plus{}1\equal{}0$. The zeros of $ x^3\plus{}x\plus{}1$ are $ \alpha,\alpha^2$, and $ \alpha^4$, while the roots of $ x^3\plus{}x^2\plus{}1$ are $ \alpha^3,\alpha^5$, and $ \alpha^6\equal{}\alpha^{\minus{}1}$.

the automorphism $ F[x] \to F[x], x \mapsto x\plus{}1$, maps $ h \mapsto g$. thus, it induces an isomorphism $ F[x]/(h) \to F[x]/(g)$.


geometry
3D geometry
pyramid
Pythagorean Theorem

The point $ P$ is the midpoint of the altitude of the regular three side pyramid. $ P$ is linked with $ A , B$ of the base of the pyramid with segments $ PA$ and $ PB$.
Find the angles between these segments.

[hide]Let $ AB\equal{}2$. The distance from the foot of the altitude to $ AB$ is $ \frac{\sqrt{3}}{3}$. We can calculate the distance from the foot of the altitude to $ P$ using the Pythagorean Theorem: $ \frac12\sqrt{2^2\minus{}\left(\frac{2\sqrt3}3\right)^2}\equal{}\frac{\sqrt{3}}{3}$

We pythag this again to find that the distance from $ P$ to $ AB$ is $ 1$. Since $ PAB$ is isosceles and $ AB\equal{}2$, $ PAB$ is a 45-45-90 triangle with $ \measuredangle APB \equal{} \boxed{90^\circ}$.[/hide]

good job! Very well shown how to solve this problem. You could nearly solve everything with Pythagoras, that guy was really smart.


inequalities
function
logarithms
inequalities proposed

Hi [b]Lagrangia[/b].Nice problem.To prove the given inequality we will prove two other inequlities:
[b]a)[/b]
$\sum_{i=1}^{n}{\frac{1}{1+x_{i}}}\leq\frac{n}{1+\sqrt[n]{x_{1}\*x_{2}{\cdots}{x_{n}}}}$
,for $x_{i}\in{(0,1]},i=\overline{1,n}.$
It is easy one.All we have to do is to write Jensen inequality for the function $f(x)=\frac{1}{1+e^{x}},x\in{(-\infty,0]},$for the points $y_{i}=\ln{x_{i}}\leq0$.
[b]b)[/b]
As you guess the second inequality is
$\frac{n}{1+\sqrt[n]{x_{1}\*x_{2}{\cdots}{x_{n}}}}\leq\frac{x_{1}+x_{2}+\cdots+x_{n}}{\frac{x_{1}+x_{2}+\cdots+x_{n}}{n}+{x_{1}\*x_{2}{\cdots}{x_{n}}}}$
If we denote $x_{1}+x_{2}+\cdots+x_{n}=A,\sqrt[n]{x_{1}\*x_{2}{\cdots}{x_{n}}}=B$ then the inequality above is equivalent to the $A{\geq}n\*{B^{n-1}}$ which is obvious because $A{\geq}n\*{B}{\geq}n\*{B^{n-1}}(B\leq1$,because $x_{i}\leq1$)(for $n\geq2$).
Cheers! :D  :D


Hi there,

I've found a problem in a contest that I don't know how to approach.
It'd be great if you can give me some tips to know how to get started

[code]
There're 400 cards, each one has its number written in the back. We know the 400 numbers are different.
I have to order the cards from highest to lowest, following this procedure: Choose three cards and ask your assistant to inform you which one is the highest and which one the lowest (he can't tell what the numbers are)
Determine how many times this procedure should be used to order the cards.[/code]

Thanks in advance!

With questions like these, if you don't know what to do it helps to try it out with small cases (in this case, smaller decks) and see if you can generalize.

For example, with a 9 card deck you can do it in 6 tries... see if you can devise a way yourself.

i think the answer is 399 for a 400-card deck. I'm working on a solution.


assume point $N$ on $BC$ such that $BN=NC$ and points $A,D$ at the same side of $BC$ such that $\angle AND=135$ prove that:
$AD<BA+CD+\frac{\sqrt{2}}{2}BC$

[quote="amir2"]You know we cannot always choose $D$ with that condition.
maybe you meant $\angle ADN=135^{\circ}$
or $\triangle ABC$ is somehow that exsist such $D$.[/quote]
NO!!!!
Im exactly sure about that
those were the only conditions
and also that $C,D$ are at the same side of $AB$

See http://www.mathlinks.ro/Forum/viewtopic.php?t=2429 for a solution and a generalization.

  darij


The following message was on the Mathcounts message board (students) after screening by Mathcounts people.

___________________________________________________
Topic:  winning chapter scores (1 of 1), Read 5 times
Conf:  MATHCOUNTS Students
From:  Internet Safety
Date:  Tuesday, February 27, 2007 06:12 PM

hey everyone! i am curious on what the winning scores were for the Ohio chapter competition. at my chapter the top score was a [color=red]<remainder of message deleted by moderator rcv>[/color]

__________________________________________________________

[size=75][color=red]<This is probably a mistake by MATHCOUNTS.  It doesn't change the rules that you are not permitted to discuss scores on AoPS until the end of the competition window.  Read the Announcements.>[/color][/size]

note that only 5 people have read it...

-jorian

are you in the north central ohio chapter.  I think that is what it is called, because i am, and made states.  BTW, we can't post scores  until March 7th  now.

[quote="XXX"]

[size=75][color=red]<This is probably a mistake by MATHCOUNTS.  It doesn't change the rules that you are not permitted to discuss scores on AoPS until the end of the competition window.  Read the Announcements.>[/color][/size][/quote]

Somebody thinks he can do a better job than the Mathcounts people. Somebody said that Mathcounts made a mistake.  Haha....

Nobody's perfect, unless you are the first.

MATHCOUNTS has made mistakes before...even at the national competition - why do you think we have a protest procedure?  If you decide to """""""follow MATHCOUNTS,""""""" we will ensure your speedy banning from this forum.  Thanks.


inequalities
trigonometry
symmetry
function
vector
inequalities unsolved

Distinct points $A, B , C, D, E$ are given in this order on a semicircle with radius $1$. Prove that
\[AB^{2}+BC^{2}+CD^{2}+DE^{2}+AB \cdot BC \cdot CD+BC \cdot CD \cdot DE < 4.\]

Assume that $A,E$ are on the ends of the diametre.

[hide="Why?"] If this is not the case then we simply map $A,E$ to be the ends of the diametre and the lengths of $AB$ and $DE$ would increase and the inequality becomes stricter.[/hide]

Apply the Law of Cosine and we can conclude that our original inequality is simply:

$AB . BC.CD+BC.CD.DE <-2AB.BC. \cos \angle ABC-2DE.CD. \cos \angle CDE$

To prove the above inequality, it is sufficient to show that $AB.BC.CD <-2AB.BC. \cos \angle ABC$ and that $BC.CD.DE <-2CD.DE. \cos \angle CDE$. By symmetry, it is sufficient just to prove one of them. Let's say to want to prove that $CD <-2 \cos \angle ABC$.

Let $O$ denote the centre of the circle. We shall calculate everything in radians.

Since $\frac{\pi}{2}-\frac{arcCE}{2}= \frac{\pi-arcCE}{2}= \frac{arcAC}{2}= \pi-\angle ABC$ and $CD= 2 \sin \frac{arcCD}{2}$. So essentially what we are trying to prove is just $\sin \frac{arcCD}{2}< \sin \frac{arcCE}{2}$.

Since $0<arcCD<arcCE< \pi$ and the fact that sine function is an increasing function on the inteval $[0,\frac{\pi}{2}]$. Our inequality is apparent.

[quote="arkhammedos"]use vectors :wink:[/quote]
I DO NOT UNDRESTANT


modular arithmetic
number theory
number theory solved

Inspired by a problem in intermidiate section:

if N = 10^n   (given n is positive integer)
and  (using decimal notation)

 m  is  the last (k)  digits of  (N+3)^((N+2)^(N+1))

Given k <= n

prove that  m == 1 mod (2^k)
and m == -9   mod (5^k)

(Moderators - Newbee here .. move it if it is appropiate)

This is Number theory instead of Algebra.

If we prove it for $n=k$ we got it for all values $k<n$ as well. So your problem becomes simply:
[quote="Gyan"]For all $n \in \mathbb{N}$ the number $A$ is formed by the last $n$ digits of $(10^n+3)^B$ with $B=(10^n+2)^{10^n+1}$. Prove $A$ is equivalent to $1 \bmod 2^n$ and to $-9 \bmod 5^n$.[/quote]

Here you go:[list][*]$\phi(2^n)=2^{n-1}$
$so\ 3^{2^{n-1}} = 1 \bmod 2^n.\ B=0 \bmod 2^{2^n+1}\ so\ A = 1 \bmod 2^n$.

[*]$\phi (5^n) = 4.5^{n-1}$
$(10^n+2)^{10^n+1} = 10^n+2 = 2 \pmod{5^n}$ and since $B=0 \bmod 2^n$ we get $B=5.10^{n-2}+2 \bmod 4.5^{n-1}$[/list]

Now $A = 3^B = 3^2.3^{5.10^{n-2}}=9.(-1)=-9 \pmod{5^n}$.


A little English-problem:

Are "lines" the ones with beginning and ending or the ones without beginning and ending?

line is "without begining and ending".
a segment has a point of begining and a point of end.

hope it's clear enough now. :)


We have an angle (less than 180 degree) with it's top in point P. We also have point A inside the angle (interior). Points X and Y are laying on different legs of this angle and |PX| = |PY|.

We must prove that when the sum: |AX| + |AY| is the smallest (minimum), the equation belove is correct:

    Angle XAP is equal to angle YAP.

Sorry that i didn't use TeX (still learning it)

P.S Point A is "standing still", and can be anywhere inside the triangle. We only move X and Y points

Someone has an Idea how to solve it?
I am trying to solve it for month and still can't do it!

Not until October 8, 2007.
http://www.mathlinks.ro/Forum/viewtopic.php?t=165196

  darij


number theory
prime numbers
number theory proposed

this idea was also used to solve this prob:
prove that for all prime p there exist a prime q such that for all natural number n, q doesn't divide (n^p)-p.(IMO03)
in fact q can be the prime that divide ((p^p) - 1)/(p - 1) and not congruent to 1 modulo p^2. it's easy to prove that q satisfies the conditions.

[quote="TTsphn"][quote="vahagn.aslanyan"]Let  p be a prime. Prove that there exists a prime  q which satisfies the following conditions:
(i)   p|q-1
(ii)  for all natural a,k,m, if q^k|a^(p^m)-1, then q^k|a^p-1 .[/quote]
That's is an old problem with some  steps .I will display my solution :
[u]Lemma 1 [/u]:  Let p be a  prime , exist infinite prime numbers q such that $ p\parallel{}q \minus{} 1$ .
Suppose the contradiction for any prime q such that $ p|q \minus{} 1$ then $ p^2|q \minus{} 1$ . Take a be an integer such that p is not divisor of $ a \minus{} 1$ and consider number $ \frac {a^p \minus{} 1}{a \minus{} 1}$ . We knew that if a prime is a divisor of this number then it is congruent to 1 mod p or it is equal to p . But because $ p\not | a \minus{} 1$ so $ p\not | \frac {a^p \minus{} 1}{a \minus{} 1}$ , which means that all prime divisors of this number are  greater than p . Base on the assumption we have $ q\equiv 1 (\mod p^2)$ , and therefore $ a^p\equiv a (\mod p^2)$ for all  integer a such that $ a \minus{} 1$ and p are relative prime . It gives contradiction when we chose a such that $ p\parallel{}a$ . Lemma 1 has been proven .
Lemma 2 : If q be a prime divisor of number $ \frac {a^{p^m} \minus{} 1}{a^p \minus{} 1}$ where $ m > 1$ then $ q\equiv 1 (\mod p^2)$ or $ q \equal{} p$
This lemma is so obvious .
Lemma 3 : $ \gcd(\frac {a^n \minus{} 1}{a \minus{} 1},a \minus{} 1) \equal{} \gcd(a \minus{} 1,n)$ .
By lemma 3 , iff d be a common prime divisor of $ a^p \minus{} 1$ and $ \frac {a^{p^m} \minus{} 1}{a^p \minus{} 1}$ then $ d \equal{} p$ .
Ok ,consider our problem . Take a prime q such that $ p\parallel{}q \minus{} 1$ . Suppose exist an integer a such that $ q^k|a^{p^m} \minus{} 1$ ,we must show that $ q^k|a^p \minus{} 1$ .
The first ,we will show that $ q|a^p \minus{} 1$ . Suppose the contradiction , we must have $ q|\frac {a^{p^m} \minus{} 1}{a^p \minus{} 1}$ . Because $ q > p$ so by lemma2 , $ q\equiv 1 (\mod p^2)$ ,this is impossible . Therefore $ q|a^p \minus{} 1$ .By lemma 3 , q can't be a divisor of $ \frac {a^{p^m} \minus{} 1}{a^p \minus{} 1}$ and it is easy to show that $ q^k|a^p \minus{} 1$ . Thus q satisfies all conditions of problem .[/quote]
Thank you very much.
Nice  sloution  :)

My solution is similar to shoki's solution.
Your solution is nice too, TTsphn! :)
Thank you!!!!

From TTsphn's solution we can generalize the problem:
Let p be a prime. Prove that there exist infinitely many primes q which satisfy the following conditions:
(i) p|q-1
(ii) for all natural a,k,m, if q^k|a^(p^m)-1, then q^k|a^p-1.

And we can make a little different problem:
Let p be a prime. Prove that there exist infinitely many primes q which satisfy the following conditions:
(i) p|q-1
(ii) for all natural a,k,m, if q^k|a^(p^m)+1, then q^k|a^p+1.

[quote="vahagn.aslanyan"]From TTsphn's solution we can generalize the problem:
And we can make a little different problem:
Let p be a prime. Prove that there exist infinitely many primes q which satisfy the following conditions:
(i) p|q-1
(ii) for all natural a,k,m, if q^k|a^(p^m)+1, then q^k|a^p+1.[/quote]
This problem is not true if p=2 and when p>2 ,it becomes the first if we change a to -a .   :wink:


inequalities
geometry
3D geometry
tetrahedron
geometry solved

Let OABC be a right tetrahedron - i. e., the angles < BOC, < COA, < AOB are all right. Let A', B', C' be the feet of the altitudes of triangle ABC. Prove that $OA+OB+OC\geq \sqrt{2}\cdot \left( B^{\prime }C^{\prime }+C^{\prime }A^{\prime }+A^{\prime }B^{\prime }\right) $.

I know a solution but I would like to see a simpler one. I'm bad in stereometry, so there's a good chance that I overlook something trivial.

  Darij

Let $a = OA$, $b = OB$, $c = OC$.  Then by some calculations, we get
\[B'C' = \frac{a^2 \sqrt{b^2 + c^2}}{\sqrt{(a^2 + b^2)(a^2 + c^2)}},\]
so the inequality becomes
\[a + b + c \ge \sum \frac{a^2 \sqrt{2(b^2 + c^2)}}{\sqrt{(a^2 + b^2)(a^2 + c^2)}},\]
which in turn becomes
\[(a + b + c) \sqrt{(a^2 + b^2)(a^2 + c^2)(b^2 + c^2)} \ge 2 \sqrt{2} (a^2 b^2 + a^2 c^2 + b^2 c^2).\]
I haven't checked, but it's probably just squaring and Muirhead from here.

Well, of course, that's right, but this was the not-so-nice solution I already knew.  :(

In fact, if we set a + b + c = 1, then your final inequality

$\left( a+b+c\right) \sqrt{\left( a^{2}+b^{2}\right) \left( a^{2}+c^{2}\right) \left( b^{2}+c^{2}\right) }\geq 2\sqrt{2}\left( a^{2}b^{2}+a^{2}c^{2}+b^{2}c^{2}\right) $

takes the form

$\sqrt{\left( a^{2}+b^{2}\right) \left( a^{2}+c^{2}\right) \left( b^{2}+c^{2}\right) }\geq 2\sqrt{2}\left( a^{2}b^{2}+a^{2}c^{2}+b^{2}c^{2}\right) $,

i. e.

$\left( a^{2}+b^{2}\right) \left( a^{2}+c^{2}\right) \left( b^{2}+c^{2}\right) \geq 8\left( a^{2}b^{2}+a^{2}c^{2}+b^{2}c^{2}\right) ^{2}$.

This is an inequality of Harazi and Andreescu; it is problem 107 in the book

  Titu Andreescu, Vasile Cîrtoaje, Gabriel Dospinescu, Mircea Lascu, [i]Old and new Inequalities[/i], Zalau, GIL 2004,

and it was also discussed in the [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=14569]thread "Hard, but nice"[/url]. In that thread, I gave one geometric interpretation of this inequality; in my above posting, I gave another one. I actually thought that somebody could find a simpler proof of one of the two geometric interpretations; this would, of course, yield a new proof of the Harazi-Andreescu inequality. But I fear the geometric interpreations are not really simple either.

  Darij


Let $ a$, $ b$, $ c$ three positive real numbers such that $ a\plus{}b\plus{}c \equal{} 1$. Prove that
\[ \frac{a^{3}\plus{}3abc}{(b\plus{}c)^{2}}\plus{}\frac{b^{3}\plus{}3abc}{(c\plus{}a)^{2}}\plus{}\frac{c^{3}\plus{}3abc}{(a\plus{}b)^{2}}\plus{}\frac{1}{2}\geq\frac{a}{b\plus{}c}\plus{}\frac{b}{c\plus{}a}\plus{}\frac{c}{a\plus{}b}\]

I don't think this holds: counter example $ (a,b,c)\equal{}(1/8,3/8,4/8)$.

Dear [b]ductrung[/b]
There is a typo in [b]pohoatza[/b]'s statement. It should be $x+y+z=3$. His inequality is correct with the new condition.

But your inequality is not so interesting. :wink:


function
trigonometry
calculus
calculus computations

I got
$ \displaystyle\sum_{n\equal{}1}^\infty\frac{(\minus{}1)^n}{n^2} \equal{} \frac{\pi^2}{24}\minus{}1$

is this correct?

Mathematica says the sum is $ \minus{}\frac{\pi^2}{12}$. I'll check it using Fourier...

You think well. It can be shown with Fourier as follows:

function called "parabolic cup" is defined as the 2pi-periodical widening of function $ x^2$ defined on $ < \minus{} \pi,\pi >$. Its Fourier series is

$ f(x)\sim \frac {\pi^2}{3} \plus{} 4\sum_{n \equal{} 1}^\infty\frac {( \minus{} 1)^n}{n^2} \cos nx$. The result immediately follows for $ x \equal{} 0$.

:) Yes, you are absolutely  right.
Another way :
There is $ 14 \minus{} 18$ different  ways  as I know how to show that $ \zeta(2) \equal{} \frac {\pi^{2}}{6}$ two  ways from them is simplest (I mean 8-th grade peoples can understand it)

Ok Let's believe that $ \sum_{k \equal{} 1}^{\infty} \frac {1}{k^{2}} \equal{} \frac {\pi^{2}}{6}$
now consider :
\[ \sum_{k \equal{} 1}^{\infty} \frac {( \minus{} 1)^{k}}{k^{2}} \equal{}
\]

\[ \equal{} \minus{} \left( \frac {1}{1^{2}} \plus{} \frac {1}{3^{2}} \plus{} \frac {1}{5^{2}} \plus{} ... \right) \plus{} \left( \frac {1}{2^{2}} \plus{} \frac {1}{4^{2}} \plus{} \frac {1}{6^{2}} \plus{} ... \right)
\]
thus we have
\[ \equal{} \minus{} \left( \frac {1}{1^{2}} \plus{} \frac {1}{3^{2}} \plus{} \frac {1}{5^{2}} \plus{} ... \right) \plus{} \frac {1}{2^{2}}\left( \frac {1}{1^{2}} \plus{} \frac {1}{2^{2}} \plus{} \frac {1}{3^{2}} \plus{} ... \right)
\]
or
\[ \equal{} \minus{} \left( \frac {1}{1^{2}} \plus{} \frac {1}{3^{2}} \plus{} \frac {1}{5^{2}} \plus{} ... \right) \plus{} \frac {1}{2^{2}} \zeta(2)
\]
now note that
\[ \frac {1}{1^{2}} \plus{} \frac {1}{3^{2}} \plus{} \frac {1}{5^{2}} \plus{} ... \equal{} \zeta(2) \minus{} \frac {1}{4}\zeta(2)
\]
hence
\[ \equal{} \minus{} \left( \zeta(2) \minus{} \frac {1}{4}\zeta(2) \right) \plus{} \frac {1}{2^{2}} \zeta(2) \equal{} \minus{}\frac{\zeta(2)}{2}\equal{}\minus{} \frac {1}{12}\pi^{2}
\]
I'm right? :roll:

You're right! Nice solution, [b]Extremal [/b];)


Given triangle $ ABC$. Point $ M$ is the projection of vertex $ B$ to bisector of angle $ C$. $ K$ is the touching point of the incircle with side $ BC$. Find angle $ MKB$ if $ \angle BAC \equal{} \alpha$.

[i]Author: V.Protasov[/i]

EASY to know :M,B,K,I are concyclic;<MKB=<MIB=180-<BIC=180-(90+α/2)=90-α/2.


An equilateral triangle of side length $ 10$ is completely filled in by non-overlapping equilateral triangles of side length $ 1$. How many small triangles are required?

$ \textbf{(A)}\ 10 \qquad
\textbf{(B)}\ 25 \qquad
\textbf{(C)}\ 100 \qquad
\textbf{(D)}\ 250 \qquad
\textbf{(E)}\ 1000$

[hide="Solution"] The ratio of the sides is 1/10, so the ratio of their areas is 1/100. Therefore, we need 100 little ones to equal the area, and thus to fit in the big one. C.[/hide]

or

[hide="long drawn out solution"]The area of the entire thing is $ \frac{10^2\sqrt{3}}{4}$ and the area of each of the smaller ones is $ \frac{\sqrt{3}}{4}$. so if you divide $ \frac{10^2\sqrt{3}}{4}$ by $ \frac{\sqrt{3}}{4}$, then you get $ \frac{10^2}{1} \equal{} 100 \longrightarrow \fbox{\mbox{C}}$.[/hide]

Catalyst's way was far slicker.

[hide="Another Solution"]
if 2 similar polygons are a and b, then a^2 / b^2 is the ratio for areas.
Getting 10^2 / 1^2, you get 100/1, 100, and so 100 smaller triangles fit
[/hide]
[hide="Solution 2"]
If you try to draw some of it, you get 1 small triangle on the first row, 3 on the next, etc.
Side length of bigger is 10, so 10 terms of sequence
1 + 3 + 5 + 7...19
(the odds)
[/hide]
Lol during the test I assumed that a area^2 / b area^2 would work
Didn't feel like finding square roots(I used Heron's theorem)
 :wallbash_red: [/hide]


they wanted to keep the results secret until the weekend but we've got them *hahaha*  :D

and the (semi-official, who knows what will happen) German IMO team for 2004 is:

Peter SCHOLZE
Christian SATTLER
Matthias OHST
Annika HECKEL
Michail SHKOLNIKOV

and yes, I have merely forgotten it,

Darij GRINBERG

although I have completely messed up the last two TSTs !!

  dg

darij grinberg did you qualify for the 2003 IMO? (just wondering)

yey!! :) contrats! lots of them Darij, you deserved it :P [img]http://www.daciaclub.ro/images/smiles/valuri.gif[/img]

My congrats to Darij as well.  :)

[quote="darij grinberg"]Annika HECKEL
[/quote]

Hey valiowk, one more girl who is going to IMO...  :)

[quote="Valiowk"]Congrats Darij! :)

Hm I see the German team is so important they need their own thread ;) (just kidding :lol: )[/quote] you can make your own singaporean thread :P :)

Thanks to all for the congratulations! By the way, I see I should also have mentioned

Christopher WULFF.

He has achived very good scores in the exams, much better than it was sufficiant to go to the IMO, but he is going to visit the USA in July and hence he hasn't the time to participate in the IMO.

  Darij

Heyi!! congratz Darij, ya deserve it... Mess 'em up! =)

and don't you tell anybody about your "true" nationality.  :D

Good luck Darij! I knew you'd qualify :).

Great job! You have my congratulations!  :D

[quote="darij grinberg"][quote="darij grinberg"]and the (semi-official, who knows what will happen) German IMO team for 2004 is:[/quote]

Semi-official, indeed. Against all expectances, this evening Langmann said that

Christopher WULFF

is intended to participate instead of

Annika HECKEL.

  dg[/quote] damn  :maybe:  is this for sure?

The configuration has changed again, actually now

Annika HECKEL

will go to the IMO, since

Christopher WULFF

has decided for going to the USA in July. I hope this is the final result and it won't be altered another time...

  darij

[quote="Annika"][quote="Valentin Vornicu"] damn  :maybe:  is this for sure?[/quote]

It's nice to be supported... but why am I?

Annika  :cool:[/quote] hmmz, a member of mathlinks community? :) if you wish I'd wish you weren't coming to IMO 2004 Greece, it's ok, I can manage that :P

You knew I was a member of MathLinks although i only postet twice and although you only knew my first name? Not bad...

Annika :cool:

It was indeed a long shot :P ... although MathLinks has almost 1k members now, I like to belive that I can recognize whether a username/name is registred on ML or not :P:)

Actually I believe a good many of us could tell that it was you, since we saw you post in the other thread (with most of the MathLinks participants names) also :)

or maybe cos she's a girl (one of the few)??   ;)

kennyworm


Fin the interger part of
$ A\equal{}\sqrt[n]{1\minus{}\frac{x}{2008}}\plus{}\sqrt[m]{1\plus{}\frac{x}{2008}}$
where $ x$ is a real number in $ [\minus{}2008;2008]$ and $ m,n$ are natural numbers, $ m\geq n\geq 2$

http://www.mathlinks.ro/viewtopic.php?t=209756

What exactly is the source of this problem?


[quote="nguoivn"]Given $ a, b, c \geq\ 0$ and $ a \plus{} b \plus{} c \equal{} 2$.
Prove that: $ \sqrt {\frac {a \plus{} b}{a^2 \plus{} kab \plus{} b^2}} \plus{} \sqrt {\frac {b \plus{} c}{b^2 \plus{} kbc \plus{} c^2}} \plus{} \sqrt {\frac {c \plus{} a}{c^2 \plus{} kca \plus{} a^2}} \geq\ 2 \plus{} \frac {1}{\sqrt [4]{2}}$
With $ k \equal{} 2\sqrt {2} \minus{} 2$  :)[/quote]
The general problem also trues and can be proved by Am-Gm:  :)
Given $ a, b, c, n \geq\ 0$ and $ a \plus{} b \plus{} c \equal{} 2$.
Prove that: $ \sqrt [n] {\frac {a \plus{} b}{a^2 \plus{} kab \plus{} b^2}} \plus{} \sqrt [n] {\frac {b \plus{} c}{b^2 \plus{} kbc \plus{} c^2}} \plus{} \sqrt [n] {\frac {c \plus{} a}{c^2 \plus{} kca \plus{} a^2}} \geq\ 2 \plus{} \sqrt[n]{\frac{2}{2\plus{}k}}$
With $ k \equal{} 2\sqrt {2} \minus{} 2$


inequalities
induction
Divisibility Theory

Find all positive integers $(x, n)$ such that $x^{n}+2^{n}+1$ divides $x^{n+1}+2^{n+1}+1$.

Posted here also http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=76597

Putting $x=1,2,3$ we find that there is no solution. (Use inequalities)
So assume $x\ge 4$.
$x^n+2^n+1|x^{n+1}+2^{n+1}+1\Longleftrightarrow x^n+2^n+1|x(x^n+2^n+1)-(x^{n+1}+2^{n+1}+1)$
$\Longrightarrow x^n+2\leq (x-3)2^n+x$
By putting $x=4,5$ we find that this inequality is false if $n>1$.
And by induction, \[(x+1)^n+2=x^n+n\cdot x^{n-1}+...+1+2> x^n+2^n+1+2>(x-3)2^n+2^n+x+1\]$=(x-2)2^n+x+1$
So we must have $n=1$
Now the first condition becomes $x+3|x^2+5\Longleftrightarrow x+3|(x^2+5)-(x^2-9)=14$
As $x\ge 4$, we have $x+3=7,14\Longleftrightarrow x=4,11$. It's easy to see both of them are correct. So all the solutions are $(x,n)=(4,1),(11,1)$


If A, B, C, and D are four consecutive vertices of a regular polygon such that:

1/AB = 1/AC + 1/AD,

how many sides does the polygon have ?

Lets denote x=pi/n s we get that AB=2Rsinx; AC=2Rsin(2x) and AD=2Rsin(3x)

So we get that 1/sin(x)=1/sin(2x)+1/sin(3x). The equation is equivalent to:
1/sin(x)-1/sin(3x)=1/sin(2x) which gives 2sin(x)cos(2x)/(sin(x)sin(3x)) which is sin(4x)=sin(3x) and we get that 4x=(-1)^k3x+kpi, k is integer.
if k=2m we get that pi/n=x=mpi so we get that 2mn=1 impossible.
if k=2m+1 we get that pi/n=x=(2m+1)pi/7 so we get that n=7.

cheers! :D :D

Given that A,B,C and D are vertex of a regular polygon, ABCD is a cyclic quadrilateral. Then for Ptolemy theorem AB*CD + BC*DA = AC*BD and in this case, as AB = BC = CD and AC = BD, it holds that AB^2 + AB*DA = AC^2 which can be written as AC^2  AB^2 = AB*AD or AC   AB = AB*AD/(AC+AB) and dividing both member for AC*AB we have that:

1/AB  1/AC = AD/(AC(AC+AB)).

This result combined with the hypothesis  give:

(AC+AB)/AD = AD/AC.

Lets consider now the triangles ACD and ADC where C is on the extension of AC so that CC = AB = CD. This triangles are similar then < ADC = < ACD. This added whit the fact that CDC is isosceles and the fact that < ADC = 2< DAC give us the following result 7< DAC = Pi.


topology
advanced fields
advanced fields unsolved

[quote="gauss202"][quote="kalazealot"]Consider curve $T$ in $R^{3}$ defined by $y=x^{2}, z=x^{3}$, and line $N$ defined by $x+y=0, z=c$, $c$ constant.
Consider the surface $S$ of unoin of all the lines of the form of $N$ which meet $T$.

Why at (0,0,0) $S$ fails to be a submanifold of $R^{3}$?[/quote]

Is $S$ really a "surface"? If a line of the form of $N$ met $T$ at a point (x, y, z), then $x+x^{2}= 0$. So the only points at which they could intersect are $(0, 0, 0)$ and $(-1,1,-1)$. This would make $S$ the union of only two lines in $R^{3}$.[/quote]

Sorry, I meant "parallel transport" of line of the forms of $N$. And only study the local property of $S$.


How many ways are there to arrange the word $ FATHER$ such that vowels are two spots apart. (e.g. $ FATHER$ would work because $ T and H$ are in between $ A and E$)

I can't place the vowels without brute force . . .

[hide="Starter"]Let V represent a vowel and C represent a consonant. You can either have:

VCCVCC
CVCCVC
CCVCCV

Now place in the vowels and consonants.[/hide]

[hide="Full Solution"]
First, clump together 4 letters in the form VCCV. We have F,T,H,R for constants, and A,E for vowels. There are 2 ways to place the vowels, and $ \frac{4!}{(4\minus{}2)!}\equal{}12$ (order does matter), so there are 24 ways to form these 4 letters. This 4-letter piece can be placed in three ways inside the 6 spaces (see TZF's post above), so $ 24\cdot 6\equal{}\boxed{144}$
[/hide]

So how would that change if it were 2 or 3 spaces?

Would it just be:
x _ _ x x _
_ x _ _ x x
_ _ x _ _ x

The standard method is to use constructive counting.

So if the vowels had to have $ n$ spaces in between, you would start with

$ VCC\ldots CCVCC\ldots CCV\ldots$ ($ n$ C's in between each pair of V's), and then use balls and urns to find the number of ways to insert the remaining C's in the slots formed (before the first V, between the first two V's, etc.), and finally, multiply that by the number of arrangements of the V's and C's given their position.

That may be confusing, so an example is...number of rearrangements of $ 3$ distinct vowels and $ 10$ consonants given that the vowels must have at least $ 4$ consonants between them.

So we start with $ VCCCCVCCCCV$. Then, we have $ 10\minus{}4\minus{}4\equal{}2$ C's left to distribute in the $ 4$ slots (before the first V, between the first two V's, between the last two V's, and after the last V), which we can do in $ \dbinom{2\plus{}4\minus{}1}{4\minus{}1}\equal{}10$ ways.

Finally, there are $ 3!10!$ ways to distribute the V's and C's for a total of $ 3!10!10\equal{}\boxed{217728000}$ arrangements.

You have the six letters, F, A, T, H, E, and R. More importantly, you have the vowels A and E.

This seems like a problem that involves casework.

We know that there are three places where you can place the first vowel, because the second vowel has to be three letters to the right of it. There is only one place where the second vowel can go because it is always three letters to the right of the first vowel. There are two ways to have the vowels because there are two possible vowels for the first spot, and then there is only one vowel left for the spot three letters to the right of it. So, so far, there are six ways to arrange the vowels. Then we have four letters left, and there are 24 ways to arrange these. So the answer is 6 x 24, which is 144.

[quote="Yongyi781"][quote="math154"]
Finally, there are $ 3!10!$ ways to distribute the V's and C's for a total of $ 3!10!10 \equal{} \boxed{217728000}$ arrangements.[/quote]

Moreover, you can quickly check that math154's answer does not make sense. Without restriction, there would be $ 6! \equal{} 720$ arrangements. (No offense, math154.)[/quote]

So is my solution correct?

[quote="Yongyi781"][quote="math154"]
Finally, there are $ 3!10!$ ways to distribute the V's and C's for a total of $ 3!10!10 \equal{} \boxed{217728000}$ arrangements.[/quote]

Moreover, you can quickly check that math154's answer does not make sense. Without restriction, there would be $ 6! \equal{} 720$ arrangements. (No offense, math154.)[/quote]

Um...I was solving a different problem. :wink: It is rather obvious if you actually read my post: I was answering the above post.

In particular, I was solving

[quote="math154"]...That may be confusing, so an example is...number of rearrangements of $ 3$ distinct vowels and $ 10$ consonants given that the vowels must have at least $ 4$ consonants between them...[/quote]

Yes, you're solution is perfect.

Great job! :wink:

Yay!!! Finally I solve a high school basics level problem.  (i sound kind of stupid don't I)


linear algebra
matrix
combinatorics unsolved
combinatorics

Let $ A$ be a $ k\times k$ matrix for some positive integer $ k$. Let $ A_{i,j}$ denote the element in the $ i$th row and $ j$ column. The following properties are satisfied by every element of the matrix:
(i) If $ A_{i\minus{}1,j}$ exists, then $ A_{i\minus{}1,j}\ge A_{i,j}$
(ii) If $ A_{i,j\minus{}1}$ exists, then $ A_{i,j\minus{}1}\ge A_{i,j}$

Enumerate such matrices provided $ A_{1,1}\equal{}n\ge 2k\minus{}1$ where $ n$ is a positive integer.

Try keyword "plane partitions"; I believe they were originally enumerated by MacMahon and there are some reasonably nice product formulae for their generating functions.  Lots of information available in Stanley's [i]Enumerative Combinatorics[/i] and probably elsewhere.


hello

any one can help solve and explain this exercise in steps.
thankU

The Horner’s method is an algorithm that evaluates polynomials. The following pseudocode shows how to use this method to find the
value of anxn + an-1xn-1 + . . . + a1x + a0 at x = c.
procedure Horner(c, a0, a1, a2, . . . , an : real numbers)
y := an
for i := 1 to n
y := y × c + an-i
end {y = ancn + an-1cn-1 + . . . + a1c + a0}

a) Evaluate x2 + 5x + 3 at x = 2 by working through each step of the algorithm.

b) Exactly how many multiplications and additions are used by this algorithm to evaluate a polynomial of degree n at x = c? (Do not count additions used to increment the loop variable.)

Do you mean $x^{2}+5x+3$? a isn't very intermediate...

[hide="a"]x^2=4
5x=10
3=3
4+10+3=17[/hide]

thanx for the help... but how that relates to Horner’s method

ugh I'm not that good at computer style algorithms...

P.S. Do you mean

$a_{n}x^{n}+a_{n-1}x^{n-1}\cdots+a_{2}n^{2}+a_{1}x+a_{0}$?


are we supposed to go on the airplane by ourselves? Because when I tried searching for a flight, it said that you must be ages 15 and above to ride an airplane by yourself. And also, what should we bring for camp?

eh, I know lots of people that have been on planes by themselves...(people under age 12 even)

@jerry: I suppose you could drive down...it's about 7 hours right?  You could make it a vacation, then a week at camp :D

5-6 hours
meh...
my parents don't want to drive that far and then pick me up again after one week.
are you going? maybe we can carpool. Someone sends us there and the other picks us up.
I tried asking Ian and Jeffery (the person you were talking to on tuesday) and they couldn't come
my parents agreed if i can find someone to carpool with
the camp should be in Nocal sometimes...  :(  (maybe next year?)
then i'll defiently go

You can travel on an airplane as an unaccompanied minor.  Your parents go with you to the gate, and then the airline has someone supervising you all the way, and our staff will pick you up.  The returning flight will be the same, in reverse order.

Still don't know if I'm going yet.  Either MathZoom or AMSP.

Hm.  I'll check dates to see if I can go to both :D

@DrKevin: If I'm taking some AoPS summer courses, is it possible to still take them while I'm at MathZoom?

[quote="AIME15"]@DrKevin: If I'm taking some AoPS summer courses, is it possible to still take them while I'm at MathZoom?[/quote]
Internet is available, so it is possible.

Any estimate on your AIME score?

jerry125:
about the unaccompanied minor thing.
some airlines require under 15 to pay extra [northwest was extra 100-200 round trip] so u'll have ppl supervise you [i had to do that last yr going to amsp]
but i think there are some airlines that let you fly alone as long as u r not under 12 [united] or if u r flying with another person not under 15.
but you should check into different airlines because they have different policies.


This evening we'll have a Math Jam with Matt McGann, Assistant Director of Admissions at MIT, and MIT math professor Kiran Kedlaya, multiple IMO gold medalist & Putnam winner, and author of the most recent Putnam book.

The Math Jam is at 7:30 PM ET (4:30 PM PT).  Matt and Kiran will talk about MIT, then take questions.  Please ask good questions (but don't ask if you'll get in ;) )

Many thanks for lining up these math jam participants.

[quote="BornForMath"]How do I participate in a MathJam?[/quote]

Read the bottom of [url=http://www.artofproblemsolving.com/Community/AoPS_Y_Math_Jams.php]this page[/url]

The instructions are located at the bottom of this page:
[url=http://www.artofproblemsolving.com/Community/AoPS_Y_Math_Jams.php]www.artofproblemsolving.com/Community/AoPS_Y_Math_Jams.php[/url]

Yes, there will be a transcript, as usual for all math jams.

[quote="236factorial"][quote="aznvman8"]will a transcript of this session be available afterwords?  my internet is failing me due to the rain so its hard for me to stay online in the classroom.[/quote]

not quite on this topic, but what kind of internet do you use? I've never heard of an internet connection that uses some kind of satellite.[/quote]

My home internet connection (which I'm using right now) is a satellite connection.  And when it rains really hard, I have connection problems.  Of course, I live 30 miles east of San Diego, so it almost never rains :) .


geometry
function
algebra
domain
functional equation
arithmetic sequence

[quote="DPatrick"]
We're hoping to release the Round 4 scores on Monday, March 30.[/quote]

Is this possible? If not, is there an estimate of how long it will take?

It isn't even anywhere near the end of the day in California yet. Be patient, and don't be crushed if they aren't up today.

same; it took 2 protests on previous rounds, but w/e

I received a 3 on problem 4 with the comment "This only works for invertible functions."  Where in my solution do I assume that $ f$ is invertible?
[hide="Solution"]We claim that the only solution is $ f(n) = n$ for all nonnegative integers $ n$.

We first show that $ f(0)=0$.  Clearly, we have $ f(f(0) + f(0)) = 0$ and $ f(f(0) + f(1)) = 1$.  Adding these equations, we have

\[ f(f(0) + f(0))+f(f(0) + f(1)) = 1.\]

Taking $ f$ of both sides, we have
\begin{eqnarray*}
f(f(f(0) + f(0))+f(f(0) + f(1))) &=& f(1) \\
(f(0) + f(0)) + (f(0) + f(1)) &=& f(1) \\
3f(0) + f(1) &=& f(1) \\
3f(0) &=& 0 \\
f(0) &=& 0,
\end{eqnarray*}
as desired.

Next, because $ f(f(n)) = f(f(n) + f(0)) = n+0 = n$, we have that $ f(f(n)) = n$ for all nonnegative integers $ n$.

Thus, for any nonnegative integers $ m$ and $ n$, we have

\begin{eqnarray*}
f(f(m)) + f(f(n)) &=& m+n \\
f(f(f(m)) + f(f(n))) &=& f(m+n) \\
f(m) + f(n) &=& f(m+n).
\end{eqnarray*}

Substituting $ m=0$, we have
\begin{eqnarray*}
f(0) + f(n) &=& f(0+n) \\
n &=& f(n),
\end{eqnarray*}
as desired.

Indeed, if $ f(n) = n$, then for any nonnegative integers $ m,n$, we have
\[ f(f(m)+f(n)) = f(m+n) = m+n,\]
so our solution works.
[/hide]

I don't see how you turn $ f(0)\plus{}f(n)\equal{}f(0\plus{}n)$ into $ f(n)\equal{}n$.

I can't help you, since I have no clue what invertible means. But I think my solution merited a 4. At least a 3.

Beaten, but he showed that f(0)=0.

[quote="worthawholebean"]I don't see how you turn $ f(0) \plus{} f(n) \equal{} f(0 \plus{} n)$ into $ f(n) \equal{} n$.[/quote]
Ah... Thanks.  :(

Heh... 99.  Mistake: area of a triangle = base * height.  Grr.

I have the same problem with my #4. Where did I assume the function was invertible?
[hide="Solution"]First, we prove that $ f$ is bijective. If we keep $ m$ constant and vary $ n$, then the given functional equation can be represented as
\[ f(f(n)+C_1)=n+C_2\]
where $ C_1$ and $ C_2$ are constants(if $ m$ is kept constant, $ f(m)$ is also a constant by the definition of a function).

Assume for the sake of contradiction that for some $ n$, $ n+C_2$ can be obtained by plugging in at least two different values into $ f$. This implies that for that particular $ n$, $ f(n)+C_1$ takes on two different values. However, this cannot be true since $ C_1$ is a constant and $ f(n)$ can only output one value. Contradiction.

Therefore, a given value of $ f$ can only be obtained by only one value in its domain.

Now, we can solve the functional equation.

Substituting $ m=n=k$ into the given equation, we get
\begin{align}
\ f(2f(k)) & =2k \\
\ & = (k-1)+(k+1)\\
\ & = f(f(k-1)+f(k+1))\\
\Rightarrow 2f(k) &= f(k-1)+f(k+1)
\end{align}
Rearranging the terms in $ (4)$, we arrive at
\begin{align}
f(k)-f(k-1)=f(k+1)-f(k).
\end{align}
From (5), we may write
\[ f(1)-f(0)=f(2)-f(1)=f(3)-f(2)=...=f(q)-f(q-1) = c\] where $ c$ is some constant.
This implies that the values of $ f$ are in an arithmetic progression.

Since the values of an arithmetic progression have a linear relationship with their term-numbers, let $ f(x)=ax+b$, where $ f$ is defined on nonnegative integers taking nonnegative integer values.

Using (1), $ f(2f(k))= a(2(ak+b))+b = a(2ak+2b)+b = 2a^2k+ 2ab+b = 2k$.
Matching coefficients, $ 2a^2=2$ and $ 2ab+b=0 \Rightarrow a =\pm 1, b=0$.

Hence, $ f(x)=x$ and $ f(x)=-x$. However, we disregard $ f(x)=-x$ because it would give negative values for positive $ x$.

Therefore, the only solution is $ \boxed{f(x)=x}$. It is easy to verify that it works with the given functional equation.[/hide]

i dont see how the range quadrupling when the domain quadruples doesnt indicate a direct variation. i got a 2 on #4, so my total score was a 22, and my score for all rounds was 69

You had shown that $ f(n \plus{} C_2) \equal{} n \plus{} C_1$.  Then you proceeded:

[quote="kcn2rivers"]
Assume for the sake of contradiction that for some $ n$, $ n \plus{} C_2$ can be obtained by plugging in at least two different values into $ f$. This implies that for that particular $ n$, $ f(n) \plus{} C_1$ takes on two different values. However, this cannot be true since $ C_1$ is a constant and $ f(n)$ can only output one value. Contradiction.
[/quote]

You assume here that $ f(x) \equal{} n \plus{} C_2$ implies $ x \equal{} f(n) \plus{} C_1$.  In other words, you assume that $ f(n) \plus{} C_1$ is the only argument for which $ f$ outputs $ n \plus{} C_2$.  This is an unwarranted claim, since not all functions have to satisfy this.  For example, if the function $ g(n) \equal{} n^2$ satisfies $ g(x) \equal{} g(5) \equal{} 25$, does that imply $ x \equal{} 5$?  No, because $ g$ is not [url=http://en.wikipedia.org/wiki/Injective_function]injective[/url].

[quote="funtwo"]i dont see how the range quadrupling when the domain quadruples doesnt indicate a direct variation.[/quote]
You mean you showed that $ f(4n)\equal{}4f(n)$ for all nonnegative integers $ n$, and you think that that is enough to prove that $ f(n)\equal{}n\times f(1)$ for all nonnegative integers $ n$?

Here is a counterexample. Define the function $ f$ by $ f(0)\equal{}0$ and $ f(n)$ is the largest power of 2 that is a factor of $ n$ for all positive integers $ n$. Thus, $ f(1)\equal{}1$, $ f(2)\equal{}2$, $ f(3)\equal{}1$, $ f(4)\equal{}4$, $ f(5)\equal{}1$, $ f(6)\equal{}2$, etc. This is not a direct variation, yet $ f(4n)\equal{}4f(n)$ for all nonnegative integers $ n$.

It's easy to prove injectivity here though since:

$ f(x)\equal{}f(y)\implies f(x)\plus{}f(x)\equal{}f(y)\plus{}f(y)\implies f(f(x)\plus{}f(x))\equal{}f(f(y)\plus{}f(y))\implies x\plus{}x\equal{}y\plus{}y\implies x\equal{}y$

Then you can proceed however you want.

I'm assuming kcn2rivers didn't do that, though.

Ah I get it now...Thanks benzi and jvenezuela!


[hide=" :huh: "]
$ a\equal{}b$
$ \therefore a^{2} \minus{} b^{2} \equal{} 0$.
[/hide]

It is simple. $ a\equal{}b$ in this case so $ a^2\minus{}b^2\implies a^2\minus{}a^2\equal{}\boxed{0}$

[quote="airyork6=)"][quote="aanjohri"]If a = 17 ^ [9 (x^52) - 3 (x ^ 9) -1] + 17 ^ (3 (x^9) - 9 (x ^ 52) + 1)

And if b = 17 ^ [9 (x^52) - 3 (x ^ 9) -1] + 17 ^ (3 (x^9) - 9 (x ^ 52) + 1)

find a^2 - b^2  if x=2[/quote]

It is easier then I think!!! :rotfl:[/quote]

di yiu even know how to do it :huh:  and dont ever copy my user again

A bit too easy
[hide]$ a\equal{}b$
So, $ a^2 \minus{} b^2 \equal{} 0$[/hide]

Um... DUH?

Since the computations with $ x$ are the same, $ a\equal{}b$. This means that $ a^2\minus{}b^2\equal{}0$

Please, if 2-3 answers are already posted, there is no need to repeat the same thing over and over again.

where are all of you from?
the same country
or many diffirent countries