1. What are the zeros of $k(x)= 2x^{3}-3x^{2}-10x+15$?
2. What expression best describes the left end-behavior of $g(x) =-5x^{3}+7x+19$? (Ex. As x ->, g(x) ->)
3. $y = x^{5}-3x^{2}+7$ has a real zero between what numbers.

3.
[hide]
you can use the medium value theorem
we consider $\ P(x)=x^{5}-3x^{2}+7$
$\ P(0)=7 \geq 0$
$\ P(-2) =<0$
then there exist c £ R btw 0 and -2 such that P(c)=0
[/hide]

Bump.  Need an answer to #2 please.

Thanks [b]anyone[/b] and [b]goldbach[/b].

2.[hide] $g(x)=-5x^{3}+7x+19$ is of odd degree (thus different behavior on both ends) with negative coefficients which means that As $x \to-\infty$, $g(x) \to \infty$ (and that's the left end behavior).[/hide]

Ugh, this looks suspiciously like homework.


modular arithmetic
pigeonhole principle
Divisibility
number theory
IMO Shortlist
combinatorics

Determine the smallest integer $n\geq 4$ for which one can choose four different numbers $a,b,c$ and $d$ from any $n$ distinct integers such that $a+b-c-d$ is divisible by $20$.

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

I think it should be $9$.

Let's work $\pmod{20}$, so when I say distinct, for example, I mean distinct $\pmod{20}$. If we look at systems consisting of distinct numbers, then we see that $7$ suffice, because they form $21$ pairs, so there must be two pairs with the same sum, and two such pairs cannot share one of the members. If a number appears more than once, then no other number can appear more than once, and a certain number cannot appear more than three times, so the number we're looking for is at most $9$ (in the case $a,a,a,b,c,d,e,f,g$). If we find a counterexample for $8$, we will have shown that the answer is $9$. Here are $8$ numbers for which $a+b-(c+d)\ne 0,\ \forall a,b,c,d$ distinct: $0,0,0,1,2,4,7,12$. This shows that the answer is $9$.

Sorry to revive such an old post, but I don't see why the answer can't be seven.

I also don't understand what you mean in this part:
[quote]If a number appears more than once, then no other number can appear more than once, and a certain number cannot appear more than three times, so the number we're looking for is at most 9 (in the case a,a,a,b,c,d,e,f,g).[/quote]

This solution was found in collaboration with [b]yugrey, SkinnySanta, antimonyarsenide[/b].

First, remark that $8$ fails due to $1,21,41,2,3,5,8,13$.

Now to prove given $9$ elements we can find the four $a,b,c,d$.

First suppose there are four elements in the set $a,b,c,d$ such that $a \equiv b \pmod{20}$ and $c \equiv d \pmod{20}$. But then $20|(a+c - b - d)$, so we can assume at most one element is repeated modulo $20$. It is clear this repeated residue modulo $20$ can appear at most $3$ times. Thus remove repeats in our set and we are left with at least $7$ elements.

Now consider all sums $a+b$ modulo $20$ for $a,b$ in our modified set. Note that if $a+b \equiv c+d \pmod{20}$ for distinct sets $\{a,b\}, \{c,d\}$, then $20|(a+b-c-d)$, contradiction (note that we cannot have $a \equiv c \pmod{20}$ or $a \equiv d \pmod{20}$ because then it would follow $\{a,b\} = \{c,d\}$ due to us taking out repeated elements modulo $20$), so it follows the pairs are distinct modulo $20$. But there are at least $\dbinom{7}{2} = 21 > 20$, so two must be equal and therefore we are done as any $9$ element set then has $4$ $a,b,c,d$ satisfying the problem condition.

Well, we can shorten the solution as follow:

First, we list 8 "failed" number (mod $ 20 $ ): $ 1,1,1,2,3,5,8,13 $

Second,  we count how many sums of the form $ a+b (\mod 20) $ there are in $n $ given numbers, it is $ n \choose 2 $
if $ n\geq 7 $ then $ {n\choose 2} \geq {7\choose 2} =21>20 $ then by the Pigeonhole Principle we get the answer is $ 9 $

Editted :D

[quote="dinoboy"]You forgot about duplicates modulo $20$ :wink:

That makes the answer $9$.[/quote]

Oops, I forgot it  :P

You still haven't justified why when there are $9$ numbers we can find at least $7$ distinct ones.

For $n=8$; the example set(s) are already given.

For $n=9$, let the set be $S=\{a_1,\dots,a_9\}$; there are $\binom{9}{2}=36$ distinct pairs. Clearly; two of them must occupy the same congruence class in modulo $20$. Now, if those pairs share no common elements; we are done. If not, they share exactly one element (since they are distinct pairs). Without loss of generality, let $p_1=(a_1,a_2)$, and $p_2=(a_1,a_3)$. We have $a_2\equiv a_3\pmod{20}$. Now, erase $a_2$ and $a_3$; and consider $S'=\{a_1,a_4,a_5,\dots,a_9\}$. Since $|S'|=7$; there are $\binom{7}{2}=21$ pairs, two of which are congruent in modulo $20$. If, again, they are distinct, we are done. If not, there are $a_i$ and $a_j$ (as above), such that, $a_i\equiv a_j\pmod{20}$. Hence, it suffices to take, $(a,b,c,d)=(a_i,a_2,a_j,a_3)$.

I can give a proof like this .

Let there are \(n,n\geq 4\) numbers \(a_1,a_2,.....a_{n-1},a_n\), all are distinct. Now if for four distinct numbers \(a+c-b-d\) is divisible by 20 then
\(|(a-b)(mod 20)|=|(c-d)(mod20)|\). Where the modulos vary from -9 to 10 over the integers. So, in sake of simplification we say that the order pair of two elements, let \((a_i,a_j)=|(a_i-a_j)(mod 20)|\). And we shall work with this pairs from now on.

So, our goal is to prevent four numbers from satisfying the given condition (\(20|a-b+c-d)\) . So to do that we have put our maximum effort not to give any of those disjoint pairs (\((a_p,a_q)=(a_k,a_l)\), p,q,k,l all are distinct) to be equal, namely . Intersecting pairs may be equal because we are asked for four distinct numbers. So, to do this we will proceed like this.

Let,\(0\leq (a_p,a_k)=r\leq 10\). And let, all \(r\)'s are used to prevent equality with the best effort. Without loss of generality we take \((a_1,a_2)=0\). Now, if any of the values \((a_p,a_q)=0;p,q=3,4,....n-1,n\), then we are failed (we will have for distinct numbers \(a_1,a_2,a_k,a_l;k,l \in\){\(3,4,...n-1,n\)} such that
\(20|a_1-a_2+a_k-a_l\) ).

So, to prevent them from being \(0\) we should give them other \(9\) values (\(1,2...10\)). Now, there are \(A=\)\(\frac{(n-2)(n-3)}{2}\) numbers of pairs with no \(a_1\),\(a_2\) .

Now, if we have two equal-valued disjoint pairs in \(S=\) {\((a_p,a_q) ;p,q=3,4,....n-1,n\)} then we are failed. But if two intersecting \((a-p,a_q)=(a_p,a_k)\) pair with a common element \(a_p\) are of equal values then \((a_p,a_q)~(a_p,a_k)=(a-q,a_k)=0\) or \( 2r\);  as we had taken modulus ;\((a-q,a_k)\) surely may not be only \(0\) but \(2r or 2r(mod 20)\).  Then we will be failed again.

So, we have \(\frac{(n-2)(n-3)}{2} > 2*10 \geq 21 \Rightarrow n-2 \geq 7 \Rightarrow n\geq 9 \). We can take two non-disjointpairs equal \(\rightarrow\) at most "twice" because the equality of pairs does not imply the fail of our prevention. But an extra equality fails our prevention.

So, the least such \(n\) is equal to \(9\).

The answer is $n=9.$ When $n=8$, we have $(0,1,2,4,7,12,20,40)$

Clearly, if we have from these $9$ numbers, at least $7$ distinct residues $\pmod 20$, then we are done, because from these $7$ distinct residues, there are $21$ sums, so we can find two such that $a+b\equiv c+d\pmod 20.$ If the seven numbers are distinct $\pmod 20$ then $a,b,c,d$ must be four different numbers.

Now, if we have $a,b,c,d$ all equivalent $\pmod 20$, then $a+b-c-d\equiv 0\pmod 20$, we're done. If $a,b$ are equivalent and $c,d$ also are, then $a+c-b-d\equiv 0\pmod 20$, and we're also done. Thus, at most one residue is repeated, and each residue is repeated at most thrice, so we can find $7$ distinct residues, as desired.

[quote=huashiliao2020]Excellent! Surprised little posts, it's a straightforward problem...
The answer is 9. Indeed, our problem rephrased is that a+b=c+d mod 20, and if they're all distinct, 7 numbers suffices with 21 pairs. On the other hand, if some number is repeated, no other numbers can be repeated otherwise we take that a_1+b_1=a_2+b_2 where a_1=a_2 and b_1=b_2. To find a lower bound the "worst" case scenario is when there's three of one number, with the rest distinct, this means our answer is 9. Finally, it is easily seen that 0,0,0,1,2,4,7,12 that has 8 numbers does not work (it is easy to find a counterexample since for simplicity and trial just start with 3 0s, then, place as many small numbers as you can without satisfying the problem, namely 3 doesnt work since 3+0=2+1, 5,6,8,9,11 similarly, and 10+1=7+4). $\blacksquare$
In contest, do we have to give a counterexample? A friend told me that I should to be safe but I'm not sure..[/quote]

This is a correct proof. In contest you must give a counterexample for full credit as the counterexample is part of the proof that that is indeed the smallest value. If it said instead 'prove there exists n' then there is no need.

$\color{magenta}\boxed{\textbf{SOLUTION N3}}$

Let, $S={a_1,a_2,....a_n}$

If we have $a_i\equiv a_j \pmod {20}$ and $a_k\equiv a_l \pmod {20}$ for $i \ne j \ne k \ne l$ Then set,
$a=a_i,b=a_k,c=a_j,d=a_l$ and we are done

So, Assume we don't have this case, Then we can have atmost $3$ elements having same residue module $20$ call $a_x,a_y,a_z$

Remove any two of them to get
$S'={a_1,a_2,...a_x,...a_n}, |S'|=n-2$

Now consider all of the numbers of the form $(a_i+a_j)$ for $i\ne j$
If we get $a_i+a_j\equiv a_k+a_l \pmod {20}$ we are done again

So, Assume all of the sums have different residues modulo $20$
There are $\binom{n-2}{2}$ sums

We always get $a_i,a_j,a_k,a_l \in S'$ such that
$a_i+a_j\equiv a_k+a_l \pmod {20}$ if $\binom{n-2}{2} \ge 20$

Gives, $n\ge 9$

So, $n_{min}=9 \blacksquare$

We claim that $n=9$, the counter example for $n=8$ is $\{0,0,0,1,2,4,7,12\}$. If $n=9$, then if there exists elemnts s.t. $a \equiv b$ and $c \equiv d$ (all in mod $20$) then we're done, so assume this does not happen, similarly a number cannot repeat more than 3 times. Since $\binom{7}{2} = 21 > 20$, we're done.


algebra
polynomial
function
quadratics
analytic geometry
LaTeX
arithmetic sequence

Well since $ f(0) \equal{} 12$, the constant term of the polynomial will be 12.

I would suggest "predicting" that the solution is of the form $ y \equal{} Ax^2 \plus{} Bx \plus{} 12$ and then put the values you have into it to generate equations which you can solve, to find $ A$ and $ B$.

If the quadratic doesn't give you the correct answer (which you can check) move onto a cubic guess: $ y \equal{} Ax^3 \plus{} Bx^2 \plus{} Cx \plus{} 12$ and solve three simultaneous equations.

Make a table of the input and output values, and calculate the differences (basically, make columns labeled $ f(x), D_{1}, D_{2}, ... , D_{n}$, and find the differences of the two adjacent terms in the previous column). If the values are constant in the $ n^{th}$ difference, the polynomial is of degree $ n$. For this problem, the $ 3^{rd}$ differences are constant ($ \minus{}144$), so the function is a cubic.

[quote="iniquitus"]No need to guess, or to solve the cubic regression.

Since the x-values are in an arithmetic progression, we may use method of finite differences with the y-values.
(It's just repeatedly taking differences of consecutive values)

We have:

Row 1: $ 12 \; \minus{} 4 \; \minus{} 164 \; \minus{} 612 \; \minus{} 1492 \; \minus{} 2948 \; \minus{} 5124$
Row 2: $ 16 \; 160 \; 448 \; 880 \; 1456 \; 2176$
Row 3: $ 144 \; 288 \; 432 \; 576 \; 720$
Row 4: $ 144 \; 144 \; 144 \; 144$

Since the values become constant in Row 4, these coordinates map to a $ Cubic$ $ Function$.

Edit: Ops Metafor posted before I finished  :D
How do you make spaces in Latex?[/quote] I hadn't thought of doing it like that.

You can either use [code]\quad , \qquad , \: or \; [/code]. (I think that's all of them, but you can also get negative spacing somehow).

There's also

[code]\  (press 'space' after the slash) ;  \! [/code]

Additionally, you could make a table:

\begin{tabular}{|c|ccccccc|} \hline f(x) & 12 & - 4 & - 164 & - 612 & - 1492 & - 2948 & - 5124 \\
D_{1} & - 16 & - 160 & - 448 & - 880 & - 1456 & - 2176 & ... \\
D_{2} & - 144 & - 288 & - 432 & - 576 & - 720 & ... & ... \\
D_{3} & - 144 & - 144 & - 144 & - 144 & ... & ... & ... \\
\hline \end{tabular}

[hide="Code"][code]\begin{tabular}{|c|ccccccc|}
\hline
f(x) & 12 & -4 & -164 & -612 & -1492 & -2948 & -5124 \\
D_{1} & -16 & -160 & -448 & -880 & -1456 & -2176 & ... \\
D_{2} & -144 & -288 & -432 & -576 & -720 & ... & ... \\
D_{3} & -144 & -144 & -144 & -144 & ... & ... & ... \\
\hline
\end{tabular}[/code]
[/hide]

In my table (the one I wrote on a piece of paper in order to solve this problem), I used columns instead of rows, but it doesn't really matter, as long as you make the correct calculations (remember that the subtraction is $ f(x + h) - f(x)$, where $ h$ is the common difference, though the only thing that would change, if you did the inverse, is the sign).


So the problem is: [i]Let $ x,y,z$ be positive real numbers. Prove that the following inequality holds:[/i]

$ \displaystyle\sum_{cyc}\frac{x}{x\plus{}\sqrt{(x\plus{}y)(x\plus{}z)}}\leq 1.$

From [color=blue]Cauchy-Schwarz inequality[/color] we get:

$ \displaystyle\sum_{cyc}\frac{x}{x\plus{}\sqrt{(x\plus{}y)(x\plus{}z)}}\leq \displaystyle\sum_{cyc}\frac{x}{x\plus{}\sqrt{xy}\plus{}\sqrt{xz}}\equal{}\displaystyle\sum_{cyc}\frac{\sqrt{x}}{\sqrt{x}\plus{}\sqrt{y}\plus{}\sqrt{z}}\equal{}1.$

Done.

It would be better if you had written $ \sum_{cyc}\frac{x}{x\plus{}\sqrt{(y\plus{}x)(x\plus{}z)}}$ if you say that by Cauchy.


complex analysis
function
algebra
domain
trigonometry
complex analysis unsolved

Is there a holomorphic function $f: \mathbb{C} \to \mathbb{C}$ such that
(i) $f(\frac{1}{n}) = \frac{n}{n+1}$ for all $n \in \mathbb{N} \setminus \{0\}$?
(i) $f(n) = \frac{n}{n+1}$ for all $n \in \mathbb{N} \setminus \{0\}$?

(i) Yes.  Take $f(z)=\frac{1}{z+1}$, which is holomorphic on $\mathbb{C}-\{-1\}$, satisfies the condition and can be extended analytically at $-1$. This extension answers the question, and is the only possibility since a holomorphic function on a domain is entirely determined by its values on any set of points of the domain containing a limit point.

(ii) Take the function $f(z)=\frac{z}{z+1}$, extended analytically at $-1$. This time the solution is not unique because it is always possible to construct a power series with given values on a closed discrete set.

Also it is clear that no entire function can satisfy the conditions (i) and (ii) simultaneously.

You can't just ignore poles like that. The nice rational functions you tried are not analytic on the whole complex plane.

An example that actually works in the second case: $\frac{\sin(\pi (x+1))}{\pi(x+1)^2}+\frac{x}{x+1}$, extended to be $1$ at $x=-1$.

[Edit: Now I see how to fix it]

Oops ... the singularities were not removable  :blush:

I agree with your example for the second case (and from my previous remark, it is not unique). Actually maybe there's a typo (the pole is at $-1$, so it should be $\frac{z}{z+1}-\frac{sin(\pi z)}{\pi(z+1)^{2}}$, extended to be $1$ at $-1$).

Also, for the first case: if such a function $f$ exists, $f(z)=\frac{1}{z+1}$ on $\mathbb{C}-\{-1\}$. Since such a function cannot be extended analytically at $-1$, $f$ cannot exist.

Sorry I don't understand your last post ... are you talking about my post #4 or #5, or both are wrong? Thanks.

I'm talking your post disputing my example- I did not make a typo. Your other post is fine- we can't extend that function in the first case, and your argument is right.

I've just plugged it in in Maple and that tends to confirm my claim: the limit of your expression is even not defined at point $z=-1$, while mine tends to $1$. The mess comes from transforming $sin(\pi x) = -sin(\pi (x+1))$ because we are studying the limit at $z=-1$ ... Well sorry if I am wrong on that  :blush:  :blush:  but I don't want to overlook something important.

I wasn't thinking in that direction- I've got it fixed now.


Let $ 3\leq a;b;c \leq 4$ Prove that
$ (a\plus{}b\plus{}c)(\frac{ab}{c}\plus{}\frac{bc}{a}\plus{}\frac{ca}{b}) \geq 3(a^2\plus{}b^2\plus{}c^2)$

THis inequality is equivalent to
$ \frac{1}{2}(a\plus{}b\plus{}c)(\sum {a^2(b\minus{}c)^2})\geq abc[\sum {(a\minus{}b)^2}]$
$ \Leftrightarrow S_a(b\minus{}c)^2\plus{}S_b(c\minus{}a)^2\plus{}S_c(a\minus{}b)^2\geq 0$
with $ S_a\equal{}\frac{1}{2}(a\plus{}b\plus{}c)a^2\minus{}abc,S_b\equal{}\frac{1}{2}(a\plus{}b\plus{}c)b^2\minus{}abc,S_c\equal{}\frac{1}{2}(a\plus{}b\plus{}c)c^2\minus{}abc$
WLOG we may assume that $ 4\geq a\geq b\geq c\geq 3$ then $ S_a\geq S_b\geq S_c$
and $ S_b\plus{}S_c\equal{}\frac{1}{2}(a\plus{}b\plus{}c)(b^2\plus{}c^2)\minus{}2abc\geq 0$
$ \Leftrightarrow 9(b^2\plus{}c^2)\minus{}4abc\geq 2bc(9\minus{}2a)\geq 0$
now we are done!

Let$ 14 \leq a;b;c \leq 15$Prove that
$ \frac{a\plus{}b\plus{}c}{2abc} \geq\sum\frac{a}{b^3\plus{}c^3}$

Let  $ 3 \leq a;b;c \leq \frac{10}{3}$ Prove that:
$ \frac {1}{(2a \minus{} b)^2} \plus{} \frac {1}{(2b \minus{} c)^2} \plus{} \frac {1}{(2c \minus{} a)^2} \geq \frac {9}{(ab \plus{} bc \plus{} ca)}$

This is VMO inequality
If a,b,c$ \geq$o then
$ \sum\frac{1}{(a\minus{}b)^2} \geq \frac{4}{ab\plus{}bc\plus{}ca}$

[quote="tran300491"]This is VMO inequality
If a,b,c$ \geq$o then
$ \sum\frac {1}{(a - b)^2} \geq \frac {4}{ab + bc + ca}$[/quote]
Assume a=max{a,b,c}  By AM_GM

$ \sum\frac{1}{(a-b)^2}
=\frac{(b-c)^2}{(a-b)^2(a-c)^2}+\frac{1}{(b-c)^2}+\frac{2}{(a-b)(a-c)}
\geq\frac{4}{(a-b)(a-c)}
\geq\frac{4}{ab+bc+ca}$

 :rotfl:


vector
calculus
integration
linear algebra

Find all integer solutions to :

40a+24b+120c=16

Good bye..............

Rewrite it as $5a+3b+15c=2$.
This is an equation of plane $P$ in the space, and we are looking for integer points on that plane.
Direct checking shows that $A(1,-1,0),B(-2,-1,1)$ and $C(-2,4,0)$ belong to $P$.
It follows that each point $M$ from $P$ satisfies $AM = \alpha AB + \beta AC$ (as vectors), so that :
$a=-3\alpha -3 \beta +1$
$b=5\beta -1$
$c=\alpha$.

If $M$ is an integer point, it follows that $\alpha $ is an integer, and then $\beta = \frac p 5 = \frac q 3$ for some integers $p,q$. Since $\gcd(3,5)=1$ we deduce that $\beta $ is an integer too.
Conversely, if both $\beta $ and $\alpha$ are integers, clearly $M$ is an integer point.

Therefore, the solutions are the triples of the form :
\[(-3\alpha -3 \beta +1,5\beta -1,\alpha)\]
where $\alpha, \beta$ are arbitrary integers.

Pierre.

40a+24b+120c=16 => 5a+3b+15c=2
In mod 3, this becomes
5a=2 (mod 3) => a=3a'+1
for some integer a'
Similarly, in mod 5 we have
3b=2 (mod 5) => b=5b'+4
Substituting back into the original equation, we obtain
5(3a'+1)+3(5b'+4)+15c=2
                   15(a'+b'+c)=-15
                                    c=-a'-b'-1
Therefore, the equation is satisfied by and only by
a=3a'+1
b=5b'+4
c=-a'-b'-1
for integral values of a' and b'.

...and letting
alpha=-a'-b'-1
beta=b'+1
show that our answers are equivalent.

I like Pierre's solution, it's very natural (e.g, was the first thing I thought of) to anyone who knows some basic linear algebra or some basic facts about vectors.


(i) The vector $ u \equal{} \frac{3}{13}i \plus{} bj\plus{}ck$is perpendicular to the vector $ 4i\plus{}k$ and to the vector $ 4i \plus{} 3j\plus{}2k$. Find the values of $ b$ and $ c$, and show that $ u$ is a unit vector.

(ii) Calculate, to the nearest degree, the angle between the vectors $ 4i \plus{}k$ and $ 4i\plus{}3j\plus{}2k$.

[hide="(i)"]
the dot product of 2 perpendicular vectors is zero.

Thus,

$ (\frac{3}{13}i \plus{} bj \plus{} ck).(4i \plus{} k) \equal{} 0 \ \Rightarrow \ \frac{12}{13} \plus{} c \equal{} 0$

$ (\frac{3}{13}i \plus{} bj \plus{} ck).(4i \plus{} 3j \plus{} 2k) \equal{} 0 \ \Rightarrow \ \frac{12}{13} \plus{} 3b \plus{} 2c \equal{} 0$

solving for [b]b[/b] and [b]c[/b] gives

$ b \equal{} \frac{4}{13} \ and \ c \equal{} \frac{\minus{}12}{13}$

$ u \equal{} \frac{3}{13}i \plus{} \frac{4}{13}j \plus{} \frac{\minus{}12}{13}k$

$ | u | \equal{} \sqrt{\frac{3^2 \plus{} 4^2 \plus{} 12^2}{13^2}} \equal{} 1$

[b]u is a unit vector[/b].
[/hide]

[hide="(ii)"]
If $ \theta$ is the angle between $ 4i \plus{} k$ and $ 4i \plus{} 3j \plus{} 2k$,

$ cos (\theta) \equal{} \frac{(4i\plus{}k).(4i\plus{}3j\plus{}2k)}{\sqrt{4^2 \plus{} 1^2}.\sqrt{4^2 \plus{} 3^2 \plus{} 2^2}}$

$ \theta \equal{} cos^{\minus{}1}(\frac{18}{ \sqrt{493} })$

[/hide]

Thanks, Nora-91. Our answers agree.

I was tempted to use the vector (or cross) product and then the fact that we know the i-component of the vector u.l


superior algebra
superior algebra unsolved

Let $p$ be prime.

[A] Suppose that $p \neq 2$. Show that $\frac{\mathbb{Q}_{p}^\times}{\left(\mathbb{Q}_{p}^\times\right)^{2}}\cong \mathbb{Z}_{2}\oplus \mathbb{Z}_{2}$.

[B] Suppose that $p = 2$. Show that $\frac{\mathbb{Q}_{p}^\times}{\left(\mathbb{Q}_{p}^\times\right)^{2}}\cong \mathbb{Z}_{2}\oplus \mathbb{Z}_{2}\oplus \mathbb{Z}_{2}$.

each $x \in \mathbb{Q}_{p}^{x}$ can be uniquely written in the form $p^{n}u$ where $n \in \mathbb{Z}$ and $u \in \mathbb{Z}_{p}^{x}$. hence, $\mathbb{Q}_{p}^{x}\cong \mathbb{Z}\times \mathbb{Z}_{p}^{x}$, and $\mathbb{Q}_{p}^{x}/ (\mathbb{Q}_{p}^{x})^{2}\cong \mathbb{Z}/2 \times \mathbb{Z}_{p}^{x}/(\mathbb{Z}_{p}^{x})^{2}$. further, we have $\mathbb{Z}_{p}^{x}\cong \text{lim}_{n}(\mathbb{Z}/p^{n})^{x}$. so let's determine $(\mathbb{Z}/p^{n})^{x}/{(\mathbb{Z}/p^{n})^{x}}^{2}$. For $n=1$, this is clearly trivial for $p=2$ and $\cong \mathbb{Z}/2$ for $p \neq 2$. now assume $n>1$. it is known that $(\mathbb{Z}/p^{n})^{x}$ is cylic for $p \neq 2$, thus the quotient ist $\cong \mathbb{Z}/2$, and for $p = 2$ we have $(\mathbb{Z}/2^{n})^{x}\cong \mathbb{Z}/2 \times \mathbb{Z}/2^{n-2}$, so that the quotient is $\cong \mathbb{Z}/2 \times \mathbb{Z}/2$.

finally, we compute for $p \neq 2$ : $~~~\text{lim}_{n}(\mathbb{Z}/p^{n})^{x}/{(\mathbb{Z}/p^{n})^{x}}^{2}\cong \text{lim}_{n}\mathbb{Z}/2 \cong \mathbb{Z}/2$,

and for $p=2$: $~~~\text{lim}_{n}(\mathbb{Z}/p^{n})^{x}/{(\mathbb{Z}/p^{n})^{x}}^{2}\cong \text{lim}_{n}(\mathbb{Z}/2 \times \mathbb{Z}/2) \cong \mathbb{Z}/2 \times \mathbb{Z}/2$

and conclude
\[\mathbb{Q}_{p}^{x}/ (\mathbb{Q}_{p}^{x})^{2}\cong \left\{ \begin{array}{cc}\mathbb{Z}/2 \times \mathbb{Z}/2 & p \neq 2 \\ \mathbb{Z}/2 \times \mathbb{Z}/2 \times \mathbb{Z}/2 & p = 2 \end{array}\right. \]


inequalities
function
inequalities proposed

If $ a,b,c$ are positive numbers such that $ a\plus{}b\plus{}c\equal{}3$, then

$ \frac {9}{abc}\plus{}16\ge\frac{75}{ab\plus{}bc\plus{}ca}$.

[hide="hint"]

After homogenizing the ineq (multiplying first fraction with $ (a\plus{}b\plus{}c)/3$, number $ 16$ with $ 9/(a\plus{}b\plus{}c)^{2}$) and multiplying the ineq with $ abc$ you get a linear ABCable function... so there are only two cases to check, according to ABC theorem: trivial $ abc\equal{}0$ and also an easy one: $ (a\minus{}b)(b\minus{}c)(c\minus{}a)\equal{}0$ Correct me if I'm wrong... :)

[/hide]

That proof is dedicated to mr Alexandru Lupas
Here is my solution
By Voc Quoc Ba CAn lemma (posted by Vasc ) we have that
If $ a\plus{}b\plus{}c\equal{}3$ and $ ab\plus{}bc\plus{}ca\equal{}\frac{9\minus{}q^{2}}{3}$ , $ q\geq 0$ then if $ abc\equal{}r$ $ r\leq\frac{(3\minus{}q)^{2}(3\plus{}2q)}{27}$

So we have to prove that
$ \frac{9\cdot 27}{(3\minus{}q)^{2}(3\plus{}2q)}\plus{}16\minus{}\frac{75\cdot 3}{9\minus{}q^{2}}\geq 0$ which is equivalent to

$ \frac{2q^{2}(4q\minus{}3)^{2}}{(q\minus{}3)^{2}(q\plus{}3)(3\plus{}2q)}\geq 0$  which is obviously true . :)

Here's my proof, using ABC method:

First, after homogenizing the inequality we get $ \frac{3(a\plus{}b\plus{}c)}{abc}\plus{}\frac{144}{(a\plus{}b\plus{}c)^{2}}\geq\frac{75}{ab\plus{}bc\plus{}ca}$, or $ (144(ab\plus{}bc\plus{}ca)\minus{}75(a\plus{}b\plus{}c)^{2})abc\plus{}3(a\plus{}b\plus{}c)^{3}(ab\plus{}bc\plus{}ca)\geq 0$ which is linear in terms of $ abc$, and because of that, it is ABCable, and the $ LHS$ function has its maximum if

1) $ abc\equal{}0$, a trivial case
2) $ (a\minus{}b)(b\minus{}c)(c\minus{}a)\equal{}0$ the case in which, if we take $ b\equal{}c$, our inequality can be transforrmed into the form $ (a\minus{}b)^{2}(a\minus{}2b)^{2}\geq 0$ which is obviously true.

[b](1)[/b] This inequality is related to Schur's inequality

$ (a+b+c)^{3}+9abc\ge 4(a+b+c)(ab+bc+ca)$,

because it is equivalent to

$ \frac{48}{(a+b+c)^{3}}+\frac{1}{abc}\ge\frac{25}{(a+b+c)(ab+bc+ca)}$.

[b](2)[/b] For nonnegative numbers, ABC Principle is a particular case of the EV-Theorem.
EV-Theorem establishes the following particular statements for nonnegative numbers ${ a_{1}, a_{2},...,a_{n}}$:

(a)  For $ a_{1}+a_{2}+...+a_{n}= constant$ and $ \sum_{sym}a_{1}a_{2}= constant$ (or $ \sum a_{1}^{2}= constant$), the product $ P = a_{1}a_{2}...a_{n}$
is maximal when ${ 0\le a_{1}= a_{2}= ... = a_{n-1}\le a_{n}}$, and is minimal when either $ a_{1}= 0$ or ${ 0 < a_{1}\le a_{2}= a_{3}= ... = a_{n}}$.

(b)  For $ a_{1}+a_{2}+...+a_{n}= constant$ and $ a_{1}a_{2}...a_{n}= constant > 0$, the sum $ S =\sum a_{1}^{2}$ (or $ -\sum_{sym}a_{1}a_{2}$)
is maximal when ${ 0 < a_{1}= a_{2}= ... = a_{n-1}\le a_{n}}$, and is minimal when ${ 0 < a_{1}\le a_{2}= a_{3}= ... = a_{n}}$.


function counting distinguishability calculus integration

How many six digit numbers can be formed from 0,1,2,....8,9 such that,every number contains exactly 3 distinct digits??

[hide="Hint 1"]
Let $ a,b,c$ be the distinct digits. Then consider the solutions to $ \#(a)\plus{}\#(b)\plus{}\#(c)\equal{}6$.
[/hide]

[hide="Hint 2"]
Following the previous hint, now consider the generating function $ G(x)\equal{}\left(1\plus{}x\plus{}\frac{x^{2}}{2!}\plus{}\frac{x^{3}}{3!}\right)^{3}$. [/hide]

Going off of Tenoreoz's hint 1, the number of solutions to $ \#a + \#b + \#c = 6$ can be found as follows:

consider a set of six objects, in a row.  We can break these objects into groups by placing dividers between them.  We want $ 3$ groups, so we need $ 3 - 1 = 2$ dividers to accomplish this.  There are $ 6 - 1 = 5$ possible places for the dividers to go, and hence $ \binom{5}{2} = 10$ solutions.  (Note that #a, #b, and #c are considered distinct by this process.)

So we have $ 10$ ways to choose how many a's, b's and c's.

Now let $ a$ be the first digit, so it is anywhere from $ 1$ to $ 9$, and thus has $ 9$ possibilities.  $ b$ and $ c$ both have $ 9$ and $ 8$ possibilities, respectively, since they can be any digit except one already chosen.

hmmm... I'm having trouble with orderings of a's b's and c's.... I suppose it should be distinguishable premutations....

Nevermind, try this:

every digit has $ 3$ possibilities: an $ a$, $ b$, or $ c$, for a total of $ 3^6$ possibilities.  But we must subtract off numbers where one of these digits are never used, of which there are $ 3\cdot (2^6 - 1)$ - $ 3$ ways to choose the digit never used and $ 2^6 - 2$ choices for the remaining digits - the $ - 2$ is to not remove the cases where we have only one digit used.  There are three of these, and can be subtracted out separately, for $ 3^6 - 3(2^6 - 2) - 3 = 540$ ways to choose positions for $ a$, $ b$ and $ c$.  But for our purposes, $ a$, $ b$ and $ c$ are indistinguishable so we divide by the number of orderings of the variables: $ 540/3! = 90$

Then we choose values for $ a$ $ b$ and $ c$.  Whichever is first has $ 9$ possibilities; the others, $ 9$ and $ 8$, for a total of $ 9*9*8=648$ choices for our numbers.  Placing them into the different arrangements of digits, we have $ 90*648 = 58320$ possibilities.

[quote="Tenoreoz"][hide="Hint 1"]
Let $ a,b,c$ be the distinct digits. Then consider the solutions to $ \#(a) \plus{} \#(b) \plus{} \#(c) \equal{} 6$.
[/hide]

[hide="Hint 2"]
Following the previous hint, now consider the generating function $ G(x) \equal{} \left(1 \plus{} x \plus{} \frac {x^{2}}{2!} \plus{} \frac {x^{3}}{3!}\right)^{3}$. [/hide][/quote]

Can you explain the generating function?

[quote="cdymdcool"]
Can you explain the generating function?
[/quote]

Sorry I gave the wrong function, but the idea still remains.

We are seeking positive integral solutions $ (\#(a),\#(b),\#(c))$ to
\[ \#(a) \plus{} \#(b) \plus{} \#(c) \equal{} 6
\]
Since each variable contributes at least 1 and at most 4, the contributions of each variable can be modeled by the generating function $ G(x) \equal{} (x \plus{} x^{2} \plus{} x^{3} \plus{} x^{4})^{3}$. However, once the number of solutions is found, we wish to find the number of the distinguishable permutations of these solutions. Hence, we divide out the number of permutations with
\[ G'(x) \equal{} \left(x \plus{} \frac {x^{2}}{2!} \plus{} \frac {x^{3}}{3!} \plus{} \frac {x^{4}}{4!}\right)^{3}
\]
This is known as the [b]exponential generating function[/b]. Now with this, we compute the coefficient of $ \frac {x^{6}}{6!}$, which turns out to be 540. The solution then follows as facis has it, dividing out the variable orderings with $ \frac {540}{3!} \equal{} 90$, etc...

That is almost the exponential generating function - but not quite  The actual exponential generating function is
\
$ e^x = 1+x+\frac{x^2}{2!} + \frac{x^3}{3!} + \ldots$

Which is just the Taylor Series for $ e^x$.  Plugging this in, you then have $ (e^x-1)^3$ as your generating function, which expands to $ e^{3x}-3e^{2x}+3e^x-1$.  Now we can proceed in two ways: either plug into the series we have above, or use Taylor's theorem to generate the new Taylor's series for our generating function.

We may as well just plug in, so taking the $ n$th term of each exponential in the generating function we have $ \frac{(3x)^n - 3(2x)^n + 3 x^n}{n!} = \frac{3^n - 3\cdot 2^n + 3}{n!}x^n$.

But up to this point we have only done $ \sum_{\#a+\#b+\#c=n} \frac{1}{(\#a)!(\#b)!(\#c)!}$, so we need to multiply by $ n!$ to really be summing up distinguishable permutations.

As I noted before, we need to divide out $ 3!$ for the arrangements of the variables and multiply by $ 9*9*8$, giving that there are $ 108(3^n - 3\cdot 2^n + 3)$ $ n$ digit numbers with exactly $ 3$ distinct digits.


Let $ N$ is the point of side $ \overline{AC}$ of triangle $ \triangle ABC$ such that $ AN \equal{} 2NC$ and $ M$ is the point of the side $ \overline{AB}$ such that $ \overline{MN}$ is perpendicular to $ \overline{AB}$. Knowing that $ \overline{AC} \equal{} 12$ cm and the centroid $ G$ of triangle  $ \triangle ABC$  belongs to the segment $ \overline{MN}$, determine the length of the segment $ \overline{BG}$.

NOTE: centroid is the point of intersection of the medians of the triangle.

CK ㅗ AB, K on AB. AG intersect BC,CK at P,Q.

AG : GP = 2:1, MN parralel with CK. So AG : GQ = 2:1

So, P=Q ,  angle ABC=90.

You can know MG : GN = 1:1 (by  Menelaus' theorem)

AM:MB=2:1,  MN:MG=2:1, So tr MGB and tr AMN are similar.

BG:AN=1:2,  AN=8     →  BG=4

Q.E.D

Thanks, but I don't understand your method, first what's ㅗ  ? And : ? What's Menelaus' theorem ? And how to use this theorem ? And →   ?

I'm sorry, I'm very confused.  :(

sorry:-)  CKㅗAB means CK and AB are perpendicularity.

And Menelaus' theorem is too long to I can't explain here. I'm not good at English.

But, you can find Menelaus' theorem in internet easily. It's well Known theorem.

And, → : It dosen't have means. Just my simbol. You can ingnore that.


I thinks it is not hard, but I can not find a solution. :|  :wallbash_red:  :wallbash_red:
Let a,b,c are positive numbers. Prove that
$ \sum_{cyc} \frac {1}{a^7\plus{}b^7\plus{}c}\le 1$

[quote="thegod277"]
Let a,b,c are positive numbers. Prove that
$ \sum_{cyc} \frac {1}{a^7 \plus{} b^7 \plus{} c}\le 1$[/quote]
Try $ a \equal{} b \equal{} c \equal{} \frac {1}{2}.$ :wink:

[quote="thegod277"]I thinks it is not hard, but I can not find a solution. :|  :wallbash_red:  :wallbash_red:
Let a,b,c are positive numbers. Prove that
$ \sum_{cyc} \frac {1}{a^7 \plus{} b^7 \plus{} c}\le 1$[/quote]
Using the inequalty $ a^7 \plus{}b^7 \geq a^5b^2 \plus{}b^5a^2$ we only need to prove that
\[ (\frac{1}{a^3\plus{}b^3\plus{}c^3})(\frac{a^2\plus{}b^2\plus{}c^2}{a^2b^2c^2})\le 1\]
and we know that $ a^3\plus{}b^3\plus{}c^3\geq a^2\plus{}b^2\plus{}c^2$
so the problem solved


MATHCOUNTS
blogs
quadratics
geometry
3D geometry
icosahedron
dodecahedron

Who will win?
Out of honesty (not bias), I think Massachusetts has a great chance, with 3 returners (although 2 barely got in the top half, not mentioning names *coughmecough*).

Don't you think this is a little too early for this?

I mean shouldn't we wait "For Just a Little While"?

yes we should wait...
but state pride forces me to choose Illinois... despite my doubt that they will win... and my lack of faith in polls like these... oh well.

If you are going to do a poll, can you include all of the 57 'places' even if no one is going to vote for some of them. That way, you can [i]clearly[/i] see the distribution.

That is a good idea, except he wouldn't have patience to type that much in a poll.

I am going for Michigan even though all of us Michiganders know some one else is going to win.

[quote="Ubemaya"]California will obviously win, because we have no returnees.[/quote]
How does that suggest California will win? :?

Or maybe s/he is thinking that, in MathCounts history, California wins when it has no returnees (2003).

Since  I hope to be coaching you and Mass at Nats next year jclarke, I'll vote for you(us)

Mr Frost

[quote="jclarkemathL314159"]Scratch that, not anymore[/quote]

How can people still be voting for Michigan even if we did so horrible in 2006 as a team?

I'm voting for michigan even though we are doing bad.

Because Treething did it this year, and we forgot all about him.  So, I am just being on the safe side saying that someone from New Jersey will make it in '07.

What place did Treething come in in 7th grade? I know he got 39th in 6th. And what place did Neal Wu get in 6th grade?

Treething got 36th in 6th Grade, 63rd in 7th Grade, and 1st in 8th Grade.

Neal Wu
I don't know what he got in 6th Grade (didn't make top 57, I think), 1st (9th Written) in 7th Grade, and 3rd in 8th Grade (1st Written).

Good Job to both of these mathletes.

[quote="mathgeniuse^ln(x)"]
Neal Wu
I don't know what he got in 6th Grade[/quote]

Why don't you ask him.

I don't think it really matters what he got in 6th grade cause all that matters is what he got in 7th and 8th Grade.

[quote="Fanatic"]Back on topic for a sec--

I'm the lone Indiana vote :)... I think we have 5th, 10th (slamchess) and 21st returning X_X. Oh, and a 6th grader that rivals Greg Gauthier (who made it in Illinois in 6th).

So our chances aren't good.[/quote]

Out of curiosity, what makes you think this 6th grader is on par with Greg?

[quote="mathgeniuse^ln(x)"]Yeah, he did win everything.  How much money did he receive again?  I know he had four trophies.  What were his prizes?[/quote]
8000 for 1st Written
2000 for Master
8000 for 1st Countdown
2000 for Team

That's 20k

[quote="pgpatel"]Greg got first in everything. He was also the last national champion that a lot of people predicted.[/quote]

I be I'll be the next  :rotfl:  ;)

[quote="mathgeniuse^ln(x)"]He also won stuff other than checks right?[/quote]

Yes, he won like 4 trips to space camp :P and a laptop

[quote="mathgeniuse^ln(x)"][quote="jclarkemathL314159"]

I be I'll be the next  :rotfl:  ;)

[/quote]

[hide=" ;) "]I think you spelled something wrong.[/hide][/quote]

I think you mean I bet.

Yes, that is what I think as well.

This is sort of random but how many perfect scorers on the AMC 10A were 7th Graders.  We had one from our state and he has a chance at making it to countdown at Nationals next year.

Michigan will win.  Besides what 50 are you talking about?


inequalities
geometry
inequalities proposed

[quote="encyclopedia"]Let $ ABC$ be triangle with median $ m_a$ of $ A$ bisector $ w_b$ of $ B$ and altitude $ h_c$ of $ C$ and area $ S$ prove that
\[ m_a^2 \plus{} w_b^2 \plus{} h_c^2\ge 3\sqrt {3}S
\]
[/quote]
Yes,It is very nice but easy (we only need some  alternatives for $ m_a,w_b,h_c$  :lol: ).Enjoy this harder problem.
With the same condition.Prove that
\[ h_a\plus{}m_b\plus{}w_c \le \frac{\sqrt {3}}{2}(a\plus{}b\plus{}c)
\]
It is called as Jack Garfunkell inequality.Thank you

[quote="Allnames"][quote="encyclopedia"]Let $ ABC$ be triangle with median $ m_a$ of $ A$ bisector $ w_b$ of $ B$ and altitude $ h_c$ of $ C$ and area $ S$ prove that
\[ m_a^2 \plus{} w_b^2 \plus{} h_c^2\ge 3\sqrt {3}S
\]
[/quote]
Yes,It is very nice but easy (we only need some  alternatives for $ m_a,w_b,h_c$  :lol: ).Enjoy this harder problem.
With the same condition.Prove that
\[ h_a \plus{} m_b \plus{} w_c \le \frac {\sqrt {3}}{2}(a \plus{} b \plus{} c)
\]
It is called as Jack Garfunkell inequality.Thank you[/quote]

hmm I don't understand, you mean yours is stronger than mine?

hello, here you will find something about Garfunkel's inequality
http://forumgeom.fau.edu/FG2004volume4/FG200419.pdf
Sonnhard.


function
logarithms
analytic geometry
graphing lines
slope
percent

What is semi-log graph paper?

Anyway, I would simply choose 2 of the points that are roughly in the middle (where a line "should") and then connect those points and find the equation of that line...  I'm pretty sure that is simply the definition of what a best line of fit is, though...

The best way is to grab a calculator and use the LinReg function (on a TI-83+ series calculator, anyway).

Sorry, a semi log graph paper uses base-ten logarithms as the y-axis, and the intervals are a bit skewed.

Basically, a plot of points may appear to be a curve in the Cartesian plane, but when plotted correctly on a semi-log graph paper, they turn into a linear line.

Example [url=http://www.science-projects.com/SemiLog0.htm]here[/url]

[quote="7h3.D3m0n.117"]How would you find the equation of the line of best fit on a semi-log graph paper?[/quote]

After obtaining your list of observations such that $ x$ are the explanatory and $ y$ are the response variables, you need to convert the given $ y$ observations to $ \log y$ on another list (this will help with creating the slope for the semi-graph paper, which is of the form $ \frac {\Delta y}{\Delta x} \equal{} \frac {\log (y_1) \minus{} \log (y_2)}{x_1 \minus{} x_2}$).

After doing that and using the LinReg function (with your original $ x$ variables and your new $ \log y$ list) on a TI-83 or 84, the final equation for the semi-log graph should be in the form $ \hat{y} \equal{} ax \plus{} 10^b$ (let the $ b$ value given from the calculator be the exponent of $ 10$ to represent the $ y$-intercept), knowing $ a \equal{} r\frac {s_y}{s_x}$ and $ b \equal{} \bar{y} \minus{} a\bar{x}$ where $ \bar{x}$ and $ \bar{y}$ are the means of their sets of observations and $ s_x$ and $ s_y$ are the standard deviations and $ r$ is the correlation (this is between list $ x$ and $ \log y$).

If you were to graph the function on a Cartesian plane, the power equation should be $ \hat{y} \equal{} 10^{ax \plus{} b} \equal{} 10^{ax}10^{b}$.

I plotted the equation after LinReg and tested some generic points from my data set [(3, 3000) and (4, 2027)] and they didn't match up at all.

Here is my data:

[hide="x"]
1.7
2.1
2.7
3.3
3.8
4
6
6.1
[/hide]

[hide="y"]
9416
6557
4361
3000
2322
2027
725
570
[/hide]

Any reason for $ \hat{y}$ instead of just regular $ y$?

EDIT: After some Googling, I found that to find slope on a regular log graph (there's a difference? they all seem the same) had

$ \frac {\Delta y}{\Delta x} \equal{} \frac {\log (y_1) \minus{} \log (y_2)}{\log{(x_1)} \minus{} \log{(x_2)}}$

instead.

[quote="7h3.D3m0n.116"]Any reason for $ \hat{y}$ instead of just regular $ y$? [/quote]

Not really. In statistics, we commonly allow $ \hat{y}$ to represent the predicted values (the values generated by inputing a value of $ x$ into the equation) and just let $ y$ represent the observations (this helps distinguish them from the predicted values as we check for errors, like plotting residuals, if we do so).

Regarding the slopes, there's a difference between a [url=http://www.science-projects.com/SemiLog0.GIF]Semi-Log[/url] and a [url=http://faculty.matcmadison.edu/kmirus/GraphPaperLogLog.bmp]Log-Log graph[/url] (notice for Semi-Log graphs, the bottom, or $ x$, intervals aren't skewed whereas the Log-Log graphs have the intervals of both axis skewed).

For a Semi-Log graph paper, the slope is $ \frac {\Delta y}{\Delta x} \equal{} \frac {\log{y_1} \minus{} \log{y_2}}{x_1 \minus{} x_2}$

whereas the slope for Log-Log is $ \frac {\Delta y}{\Delta x} \equal{} \frac {\log{y_1} \minus{} \log{y_2}}{\log{x_1} \minus{} \log{x_2}}$ (do you see the difference?).

As for your data, I instead got a very close match with the method I stated above (with just converting the $ y$ list to $ \log(y)$, not doing the same for the $ x$ list).

Could you tell me how you did it?

Yes I noted the grid differences on example graphs on several webpages  :) .

Let's see:

In my TI-83+ calculator

$ L_1$ contains my $ x$ values. Similarly, $ L_2$ consists of $ y$ values and $ L_3$ consists of $ \log{y}$ values. I then used LinReg(ax+b) $ L_1$ $ L_3$ and it came up with $ y \equal{} \minus{}.25986x \plus{} 4.364$ (decimals were approximated).

I did the same method on my TI-83+ and got the same result (one command that might make it easier with transferring the created functions over to $ Y_1$ is to type in LinReg(ax+b) $ L_1, L_3, Y_1$ [you can find $ Y_1$ by hitting Vars, go to Y-Vars, Function, and then select $ Y_1$]). I still got a good match against a scatterplot relation of $ L_1, L_3$ (my correlation was $ r \equal{} \minus{} .9968431211$).

I apologize for repeating this, but to directly answer the original question:
For a Semi-Log Graph, I believe the equation should be $ y \equal{} ax \plus{} 10^b$ after obtaining $ y\equal{}ax\plus{}b$ from comparing the scatterplots of $ L_1, L_3$. The reason we're changing the $ y$-intercept to $ 10^b$ is the fact the graph doesn't require us to convert $ y$ to $ \log(y)$ to begin with, but we did the conversions anyway to find the slope.

As for the explanations, I apologize if I was being somewhat unclear or too hasty :maybe: .

[quote="Patterns_34"]I still got a good match against a scatterplot relation of $ L_1, L_3$ (my correlation was $ r \equal{} \minus{} .9968431211$).[/quote]

Ah, I see, it works on my calculator now. I guess my method of checking the line was inputting a value of $ x$ and it only returned a $ y$ value that was less than 10, instead of one in the thousands. I understand everything now, thanks for your help, Patterns!  :)

Part of my lab has me extrapolate $ y$ using my equation based on $ x$. However, using the equation $ y \equal{} ax \plus{} 10^b$ leaves me with a number that is usually less than 10 although the correct number should be in the thousands.

EDIT: I've figured out how to extrapolate the others, although my line of best fit equation gives me a huge error percentage (ranging from $ 8$% - $ 21$%).

EDIT 2: After crunching some numbers, my average percent error was $ 13$% which is pretty significant in this lab. Is there any way to improve the accuracy or is this the best I can do?

[quote="7h3.D3m0n.177"]However, using the equation $ y \equal{} ax \plus{} 10^b$ leaves me with a number that is usually less than 10 although the correct number should be in the thousands. [/quote]
Weird, if I recall, $ 10^b$ should be greater than $ 21,000$ or so.
I'm not exactly familiar with working with a Semi-log Graph, but for a layout like $ L_1, L_2$ for the Cartesian Plane and transforming the equation as $ y \equal{} 10^{ax \plus{} b}$ leaves an exponent graph that appears very close to the layout of the data. Last time I checked though, the residuals (basically $ \hat{y} \minus{} y$) didn't look pleasing (some were in the 100s, one was even in the 1,000s  :o ).

There might be better ways, but I will recheck once I get my tools back.
Converting the $ L_2$ list to logs, then using the line of best fit for $ L_1, L_3$ and retransforming that line of best fit (which is what we did) for the Cartesian Plane layout is the best I can think of at this point.

I'll review and see what else I could do.

[b][Edit][/b] There's also the possibility that the line of best fit is working fine, but there is some piece of data that's skewing it.

By looking at the residuals against $ L_1, L_3$, the first and second-last data pieces seemed to have a significant residual (around .05) compared to the other data sets with residuals around the negatives and around -.02s or more (but below 0) (this is also considering the fact we're comparing residuals with small numbers, which yield huge differences when exponents of 10).
After eliminating those 2 pieces of data, I got a much better list of residuals (some, even $ \sum (\hat{y}\minus{}y)$, decreased by a factor of 10) and a stronger correlation.

However, doing what I just did can easily fall under subject of bias and is often frowned upon for good reason :( .
The most I can recommend at this point is to try the experiment again or just hold the two points highlighted as suspects. Other than that, that's the best I can think of.

There is no hope of doing the experiment again, since it was a gel electrophoresis, which takes a long time to set up (and my lab turn-in is tommorow) and run.

The lab said there could be a $ \pm 10$% error rate so I was just wondering if the extra 3% would be significant at all.

Alright. The line of best fit we just did is the best I can come up with.

In general, I don't see percentage errors from other students go as low as $ \pm 15\%\minus{}\pm20\%s$, even if they were annoyingly accurate (although most I've seen were more like in the $ \pm30\%$s, but it widely varies).

Good luck with your lab.


inequalities
calculus
calculus computations

suppose $ a_n>0$.  Show if $ \sum a_n$ converges, then so does $ \sum a_n^p$ for any $ p>1$.

$ \sum a_n$ converges iff $ \sum \frac{a_n}{a_1}$ converges.  WLOG we have $ a_1 \equal{} 1$.  Then $ \sum a_n^p < \sum a_n$.

Use the inequality:

$ a_{1}^{p}\plus{}a_{2}^{p}\plus{}\cdots\plus{}a_{n}^{p}<(a_{1}\plus{}\cdots\plus{}a_{n})^{p}$.

[quote="t0rajir0u"]$ \sum a_n$ converges iff $ \sum \frac {a_n}{a_1}$ converges.  WLOG we have $ a_1 \equal{} 1$.  Then $ \sum a_n^p < \sum a_n$.[/quote]

This is not quite what you meant.  (Your manipulation actually did nothing to ensure that all terms are less than $ 1$.)  One can repair this either by replacing $ a_1$ with some upper bound on the terms of the sequence (since a convergent series requires the terms go to 0 and so be bounded) or by truncating the sequence at the point such that all later terms are less than 1 (since finitely many terms can't affect convergence).

Sorry, I seem to have implicitly assumed $ a_n$ was monotonic.  Truncating the sequence was the obvious way to go, but I tried to be too tricky  :oops:


[hide="Big Hint"] What are the roots of $1+x+...+x^{n-1}$? [/hide]


function
induction
combinatorics proposed
combinatorics

hello dears!

I'd be thankful if you can help me in solving the following recurrence...

P(n) =  Summation(k=0..n-1) [P(k)*P(n-k)] and boundary condition is
P(1) = 1

we are required to find the tight upper and lower bounds of the summation.

Something is wrong. The summation starts with k=0 but P(0) is not defined.

Maybe $P(0)=1$ :?: but if $P(0)=1$ then we a term $P(n)=P(0)*P(n)$ so we cannot difine $P(n)$ in this way. so it is $k=1,2,3,...,n-1$ ;)

The Answer is $(n+1){2n\choose n}$
You can prove it by generating function or easier with induction :trampoline:


number theory
least common multiple
number theory unsolved

Find all triples $(a,b,c)$ of natural numbers, such that $LCM(a,b,c)=a+b+c$

$(2k,k,k)$ and $(3k,2k,k)$ and their symmetric permutations.

I don't think the first triples is a solution because in that case the lcm is $2k$ and not $4k$.

Now assume that $a \leq b \leq c.$ Let $m = \text{lcm} (a,b,c).$
Thus $c < a+b+c \leq 3c$ and $a+b+c = m$ is a multiple of $c$. Thus $m=3c$ or $m=2c.$ But in the first case, we would have $a=b=c$ so that $m=c \neq 3c$ a contradiction.
Thus $a+b+c = m = 2c$ so that $a+b = c$ and $m = 2(a+b).$
As above, we have $2b < 2(a+b) \geq 4b$ and $m = 2(a+b)$ is a multiple of $b$.
Thus $m=3b$ or $m=4b.$
But, in this last case, we would have $a=b$ and $c = 2a$ so that $m=2a \neq a+b+c$, a contradiction (as noticed above).
Therefore $m=3b$ which means that $2a = b.$ Thus $(a,b,c) = (a,2a,3a)$ which is a solution.

Thus, the solutions are the triples of the form $(a,2a,3a)$ where $a$ is any positive integer, and all their permutations.

Pierre.

oops. I proved that $lcm(a,b,c)=abc$ and then i tried to solve $abc=a+b+c$. I used some bounding but i forgot to exclude the case (a,b,c)=(2,1,1). Sorry..

$gcd(a,b,c)=k$ with $ a=ka_1 , b=kb_1 , c=kc_1$ so $lcm(a,b,c)=ka_1b_1c_1=a+b+c=ka_1+kb_1+kc_1$

from the last equation we have $a_1b_1c_1=a_1+b_1+c_1$ suppose $ c\leq b\leq a$

if $c_1\geq 2$ , $2b_1c_1>b_1+c_1+2$ thus $c_1=1$

if $b_1\geq 3$ , $3a_1>a_1+4$ thus $b_1=1$ or $b_1=2$

now if $b_1=1$ , $a_1=a_1+2$ contradiction! thus the only solution is $(1,2,3)$ and the triples that satisfy the conditions of the problem are $(k,2k,3k)$


function
logarithms
limit
real analysis
real analysis unsolved

Suppose that $f_{1}$ & $g_{1}$ are two functions so that $f_{1},g_{1}: [1/{e^{\frac{1}{e}}},+\infty) \rightarrow \mathbb{R}$ and $f_{1}(x)=g_{1}(x)=x$. Also for every natural number bigger than one like $n$ we have $f_{n}(x)=x^{\frac{1}{f_{n-1}(x)}}$ and ${g_{n}(x)=\log_{g_{n-1}(x)}x}$. Prove that the limits $\lim_{n\to \infty}f_{n}(x)$ and $\lim_{n\to \infty}g_{n}(x)$ exist and $\lim_{n\to \infty}f_{n}(x)=\lim_{n\to \infty}g_{n}(x)=\phi(x)$ where $\phi: [1/{e^{\frac{1}{e}}},+\infty) \rightarrow \mathbb{R}$. Now prove that if $\psi: [1/{e},+\infty) \rightarrow \mathbb{R}$,and $\psi(x)=x^{x}$ then $\phi=\psi^{-1}$.

[quote="jUaNi"]i think there is a problem with the g's, but i already have the f's part...i'll post it tomorrow...[/quote]
Tomorrow would have been July the 6th but today is the 11th... :chief:

i was absent, i'm sorry...when i was posting my solution i realized i had a mistake, but my proof works for $x\leq e^{e}$. note that $f_{1}(x)\geq f_{3}(x)\geq f_{5}(x)\geq\cdots\geq f_{6}(x)\geq f_{4}(x)\geq f_{2}(x)$ (it's an easy induction). this implies that $\{f_{2k-1}(x)\}_{k\in\mathbb{Z}^{+}}$ and $\{f_{2k}(x)\}_{k\in\mathbb{Z}^{+}}$ are convergent, since they are monotone and bounded. each limit point must be a fixed point of the function $f(\alpha)=x^{\frac{1}{x^{\frac{1}{\alpha}}}}$, which is equivalent to be a root of the equation $g(\alpha)=\alpha^{x^{\frac{1}{\alpha}}}-x=0$. it's easy to see that $g'(\alpha)=\frac{\alpha^{x^{\frac{1}{x}}}x^{\frac{1}{\alpha}}}{\alpha^{2}}\left(\alpha-\ln \alpha \ln x\right)$, so, for $x\leq e^{e}$, $g'(\alpha)\geq 0$, $g(1)=1-x\leq0$, $g(x)=x^{x^{\frac1x}}-x\geq 0$, hence, there is only one root (unfortunately for bigger x, there are 3 roots) and both sequences converge to the same limit, so the sequence of the problem converges and it converges to a fixed point of $h(\alpha)=x^{\frac{1}{\alpha}}$. this fixed point is the real number $\beta$ such that $\beta^\beta=x$, which is the wanted value. for bigger x, i think the sequences diverge. i tried with a calculator for $x=27$ and it seemed to stop in two points (i suppose they are the two roots of $g(\alpha)$ different of the root of $h(\alpha)$), but right now i don't have access to heavy math programs to try there


geometry
pigeonhole principle
parallelogram
combinatorics unsolved
combinatorics

Find the least m for which any five equilateral triangles of the total area
m can cover an equilateral triangle of area 1.

I think I have a proof for up to 8 equilateral triangles of total area $ m$:

Let the original triangle be $ T$
Let triangle $ t_i$ have area $ a_i$ for $ 1 \leq i \leq 8$
WLOG $ a_i \geq a_{i \plus{} 1} \,\forall\, 1 \leq i \leq 7$
To simplify things I shall use a scale such that a triangle of unit side length has area 1 :P

If $ m < 2$,

Consider the configuration $ a_1 \equal{} a_2 \equal{} \frac {m}{2}$ and $ a_i \equal{} 0 \,\forall\, 3 \leq i \leq 8$
By pigeonhole at least one of the vertices of $ T$ will not be covered by $ t_1$ or $ t_2$
Thus there exists a point in $ T$ within arbitrarily small distance of it that is not covered by any triangle
(assuming a triangle with zero area still covers one point)
$ \left(\Rightarrow\Leftarrow\right)$

If $ m \geq 2$,

We prove that $ t_1$,$ t_2$,$ t_3$,$ t_4$ will suffice to cover the original triangle
Clearly it is sufficient to consider the case where $ a_5 \equal{} a_6 \equal{} a_7 \equal{} a_8$
$ a_1 \leq 1$ otherwise we are done
Place $ t_1$,$ t_2$ completely within $ T$ such that they cover distinct vertices of $ T$
This leaves an area that can fit within a parallelogram of side lengths $ 1 \minus{} \sqrt {a_1}$,$ 1 \minus{} \sqrt {a_2}$
If $ \sqrt {a_3} \plus{} \sqrt {a_4} \geq \left(1 \minus{} \sqrt {a_1}\right) \plus{} \left(1 \minus{} \sqrt {a_2}\right)$
then this parallelogram can obviously be covered by aligning $ t_3$,$ t_4$ at distinct $ 60^\circ$-angle vertices

Thus it remains to prove that
for $ \sum_{i \equal{} 1}^{8}{a_i} \equal{} 2$, $ 1 \geq a_i \geq a_{i \plus{} 1} \geq 0 \,\forall\, 1 \leq i \leq 7$,
we have $ \sum_{i \equal{} 1}^{4}{\sqrt {a_i}} \geq 2$
Note that $ \sqrt {x}$ is concave over $ x \geq 0$

Case 1: $ 0 \leq a_5 \leq \frac {1}{7}$
$ \{1,1 \minus{} 6a_5,a_5,a_5\} \succ \{a_1,a_2,a_3,a_4\}$
So $ \sum_{i \equal{} 1}^{4}{\sqrt {a_i}}$
$ \geq 1 \plus{} \sqrt {1 \minus{} 6a_5} \plus{} 2\sqrt {a_5}$
$ \geq min\left\{ 1 \plus{} \sqrt {1 \minus{} 0} \plus{} 2\sqrt {0} , 1 \plus{} \sqrt {1 \minus{} \frac {6}{7}} \plus{} 2\sqrt {\frac {1}{7}} \right\}$ since $ 1 \plus{} \sqrt {1 \minus{} 6x} \plus{} 2\sqrt {x}$ is concave over $ 0 \leq x \leq \frac {1}{6}$
$ \equal{} min\left\{ 2 , 1 \plus{} 3\sqrt {\frac {1}{7}} \right\}$
$ \equal{} 2$

Case 2: $ \frac {1}{7} \leq a_5 \leq \frac {2}{8}$
$ \{2 \minus{} 7a_5,a_5,a_5,a_5\} \succ \{a_1,a_2,a_3,a_4\}$
So $ \sum_{i \equal{} 1}^{4}{\sqrt {a_i}}$
$ \geq \sqrt {2 \minus{} 7a_5} \plus{} 3\sqrt {a_5}$
$ \geq min\left\{\sqrt {2 \minus{} 1} \plus{} 3\sqrt {\frac {1}{7}} , \sqrt {2 \minus{} \frac {7}{4}} \plus{} 3\sqrt {\frac {2}{8}} \right\}$ since $ \sqrt {2 \minus{} 7x} \plus{} 3\sqrt {x}$ is concave over $ 0 \leq x \leq \frac {2}{7}$
$ \equal{} min\left\{ 1 \plus{} 3\sqrt {\frac {1}{7}} , 2 \right\}$
$ \equal{} 2$

$ (QED)$

I am pretty sure it holds true for any number of triangles>1, but obviously this method would not work. Is there a generalized proof?


For question 467 in AOPS Volume 1, the question asks:

How many odd positive integers are factors of 480?

We know 480 is (2^5)(3)(5). Thus, it has 6(2)(2)=24 odd factors. However, and power of 2 contributes to an even number, so we only consider 3^0, 5^0, 3^1, and 5^1 as possible odd factors. They equal 1, 1, 3, and 5 factors, so there are only 3 distince positive odd factors of 480.

However, the solution manual says there are (1+1)(1+1) = 4 positive factors, but I though two of them are the same and the question demands distinct factors.

Can someone shed some light?

Thanks.

Never mind, I just figured out my mistake. I obviously forgot to count 3^1 * 5^1 = 15, so there are indeed the four odd factors: 1 ,3 , 5, 15.


function
algebra
Canada
functional equation

From condition :Exist an rational $ x_$ such that : $ f(x_0)=0$
Take $ x=y=0$ then $ f(3f(0))=0$ so $ x_0=3f(0)$
Take $ x=y=x_0$ then $ f(0)=3x_0$
So $ x_0=0$ and $ f(x_0)=0$
Take $ x,y=0$ then
$ f(f(x))=x,f(f(2x))=2x$
Take $ x \to f(x),y\to f(y)$ then
$ f(2x+y)=2f(x)+f(y)$
This is Cauchy function so $ f(x)=f(1)x$
Replace to the equation we have : $ f(1)=1,-1$
So have two function :
1. $ f(x)=x$
2. $ f(x)=-x$

Would it be considered acceptable to just say "this is Cauchy's functional equation, so it is $ f(x)\equal{}f(1)x$ over the rationals?

[quote="worthawholebean"]Would it be considered acceptable to just say "this is Cauchy's functional equation, so it is $ f(x) \equal{} f(1)x$ over the rationals?[/quote]To avoid a possible depunctation I would definitely write up the quick solution (2 lines are not that hard) of this particular problem.

Sorry i don't know what is cauchy function and how it work? Help me with some guide!

[quote="AwesomeToad"]Sorry to revive, but if I'm thinking right, the above solutions don't work if $f$ is not continuous? How do we know (or where is it given) that $f$ is continuous?

@above: Cauchy Functional Equation: If $f$ is continuous and $f(x)+f(y)=f(x+y)$ for all $x,y$ in domain of $f$, then $f(x)=cx$ for some constant $c$.[/quote]
It works here!the domain of $f$ in this case is $\mathbb{Q}$ so,we don't need continuity to conclude!else,if the domain was $\mathbb{R}$ then you will need a constraint like continuity,boundedness or monotonicity to conclude as above.otherwise if there is no such constraint then some other "wild" solutions(than linear ones) do exist.
see here:
http://sunejakobsen.wordpress.com/2010/12/20/cauchy%E2%80%99s-functional-equation-i/

[quote="Complex_Ninja"][hide="This works too?"]If $ f(x)$ is of degree $ n$, then the right side and left side have the same degree iff $ n \equal{} 1$, since the degree of the LS is $ n^n$ and the RS is $ n$ and we need $ n^n \equal{} n$ which only works if $ n \equal{} 1$. From there finish off by letting $ f(x) \equal{} ax \plus{}b$, to get $ f(x) \equal{} \pm x$[/hide][/quote] $ f $ is not a polynomial.

[quote="anonymouslonely"]$f$ is not a polynomial.[/quote]

Actually, we might be able to do the same thing without assuming $n$ is an integer.

@constatin07: Thanks. :)

Slightly different, but going the same place:

$f$ is clearly surjective. Assume there exists $a \neq b$ with $f(a)=f(b)$. Then, plugging in $x=y=a$ yields $f(3f(a))=3a$ and $x=y=b$ yields $f(3f(b))=3b \implies 3a = 3b$ contradiction, so $f$ is bijective.

Let $r$ be the sole root of $f$, we then have $f(3f(0))=0 \implies r=3f(0)$. We also have $f(0)=f(3f(r))=3r \implies r=0$

But now plugging in $x=0$ yields $f(f(y))=y$ for all rational $y$, and plugging in $y=0$ yields $f(2f(x))=2x$

Letting $2x=k$, we have $f(f(k)+f(y))=k+y$ for all rational $k,y$.

F'ing both sides gives that $f(k)+f(y)=f(k+y)$, so since this is Cauchy's equation we have $f(x)=cx$ for some rational $c$.

Substituting back in gives $f(2cx+cy)=2c^2x+c^2y=2x+y$ for all $x,y \implies c=\pm{1}$, so our only solutions are $\boxed{f(x)=\pm{x}}$

I apologize to everyone for my solution being very similar to that of [b]Mewto55555[/b]. :blush:

Let $P(x,y)$ be $f(2f(x)+f(y))=2x+y$.Obviously $f$ is bijective.

・[b]$f(0)=0$[/b]
Since $f$ is surjective,∃$w\in \mathbb Q$ s.t. $f(w)=0$.$P(0,0)\rightarrow f(3f(0))=0$.Since $f$ is injective,$w=3f(0)$.$P(w,w)\rightarrow f(0)=3w$.Thus $w=9w\rightarrow w=0$

・f satisfies [b]Cauchy Equation[/b]
$P(x,0)\rightarrow f(2f(x))=2x,P(0,y)\rightarrow f(f(y))=y$.Then $f(2f(x)+f(y))=f(2f(x))+f(f(y))$.Since $f$ is surjective,
$\forall a\in \mathbb Q,\forall b\in \mathbb Q:f(a+b)=f(a)+f(b)$.

Hence ∃$c\in \mathbb Q$ s.t. $f(x)=cx$.Substituting into $P(x,y),2c^2x+c^2y=2x+y\Leftrightarrow 2(c^2-1)x=-(c^2-1)y$.Thus $c^2-1=0\rightarrow c=\pm{1}$.Therefore the answer is
$\boxed{f(x)=x(\forall x\in \mathbb Q),f(x)=-x(\forall x\in \mathbb Q)}$ which are both satisfy the condition.$\blacksquare$ :coool:

[hide = Solution]
We claim $f(x) = x, f(x) = -x$ are only functions that work. One can easy show these work by plugging them in.
P(0,0) yields $f(3f(0)) = 0$. Let $a = 3f(0)$. P(a,a) yields $f(0) = 3a = 9f(0) \implies f(0) = 0$.
Notice that P(0,x) yields $f(f(x)) = x$ (involution), which implies injectivity. Notice that P(x,0) yields $f(2f(x)) = 2x$. Injectivity implies $f(2x) = 2f(x) \forall x$.
Notice that we can apply $f(x)$ to both sides of original equation to get
$$f(f(2f(x)+f(y))) = 2f(x) + f(y) = f(2x) + f(y) = f(2x+y)$$
Substituting $b = 2x$, we obtain $f(b)+f(y) = f(b+y)$, and since $f : \mathbb{Q} \rightarrow \mathbb{Q}$, $f(x) = cx$ for some constant $c$. Plugging back to original equation, we obtain
$$c(2cx+cy)=2x+y \implies 2c^2x + c^2y = 2x+y \forall x,y \implies c \in \{\pm1\}$$
[/hide]

[hide=Solution]Here is my solution (just for the purpose of keep-sake, so I apologize in advance if my solution is same to some other solution already posted above).
[quote=April]Determine all functions $ f$ defined on the set of rational numbers that take rational values for which
\[ f(2f(x) \plus{} f(y)) \equal{} 2x \plus{} y,
\]
for each $ x$ and $ y$.[/quote]
We will set $x=y=0$ to obtain
$$f(3f(0))=0$$
Now we set $x=3f(0)$ and obtain
$$f(f(y))=6f(0)+y~~~~~(1)$$
Now set $x=f(a)$ and $y=f(b)$:
$$f(2f(f(x))+f(f(y)))=2(f(x))+f(y)$$
$$or,~~f(f(2f(f(x))+f(f(y))))=f(2(f(x))+f(y))$$
$$or,~~f(f(2(6f(0)+x)+6f(0)+y))=2x+y$$
$$or,~~f(f(18f(0)+2x++y))=2x+y$$
$$or,~~24f(0)+2x+y=2x+y$$
$$Hence~~ f(0)=0$$
Putting this back in equation $(1)$ we obtain,
$$f(f(y))=y$$
for all rationals.
Now
$$f(f(2f(x)+f(y)))=f(2x+y)$$
$$\Longrightarrow 2f(x)+f(y)=f(2x+y)~~~~~(2)$$
Substituting $y=0$ in $(2)$ we get
$$2f(x)=f(2x)$$
Hence we can write $(2)$ as
$$f(2x)+f(y)=f(2x+y)$$
And this is Cauchy's functional equation $f(x+y)=f(x)+f(y)$ over $\mathbb{Q}$! We know that this equation has the solution $f(x)=kx$ for any rational $x$, where $k\in\mathbb{Q}$.
Let us substitute the function $f(x)=kx$ to the original equation we obtain $k=\pm 1$.
So the only functions $f$ that satisfy the equation are
$$\boxed{f(x)=x,f(x)=-x}$$ for all rational $x$.
it is indeed easy to check that both of them indeed satisfy the equation(It was not really necessary to check that this functions work because we had already put the functions under trial when we proved that $k=\pm 1$).
[/hide]

Is this wrong?
Let $P(x,y)$ denote the assertion - $f(2f(x) + f(y)) = 2x + y$
$P(x,x)$ gives:
$$f(3f(x)) = 3x$$
Define $g(x) = 3f(x)$ (this is unnecessary, but I'm aiming for max rigour),so:
$$g(g(x)) = 9x$$
Making $g$ both surjective and injective. Since, $f = \frac{g}{3}$, this also gives that f is bijective as well.
So, the original equation becomes additive. As additivity over rationals implies linearity of the function, we get that $f(x) = ax$ for some $a$. Plugging back in the equation, this gives that only $f(x) = \pm x$ satisfy this, which is indeed true.

[hide=Solution:]
Let, $P(x,y)$ be assertion:
$$f(2f(x)+f(y))=2x+y$$
[b]Claim (i):[/b] $f$ is bijective.
$$P(x,0) \implies f(2f(x)+f(0))=2x \implies \text{ f is surjective}$$
Now, assume there exists $f(x)=f(y)$ for $x,y \in \mathbb{Q}$, then
$$f(2f(x)+f(0))=f(2f(y)+f(0)) \implies x=y$$
So, injective. Proved.

[b]Claim (ii): f(0)=0[/b]
Suppose $\exists c \in \mathbb{Q}$ such that $f(c)=0$. Then,
$$P(c,c) \implies f(0)=3c$$
$$P(0,0) \implies f(3f(0))=f(c) \implies c=3f(0) \implies f(0)=0$$
Proved.

[b]Claim (iii):[/b] Function is cauchy function over $\mathbb{Q}$.
$$P(0, 2f(x)+f(y)) \implies f(2x+y)=2f(x)+f(y)$$
then, $y=0 \implies f(2x)=2f(x)$
$$\implies f(2x+y)=f(2x)+f(y)$$
which is Cauchy function over $\mathbb{Q}$. Hence, $f(x)=cx$.
Plugging the solution in original equation,we get,
$$f(2cx)=2x \implies 2c^2x=2x \implies c= \pm 1$$

Hence, the solutions to the given functional equation are $f(x)=x$ and $f(x)=-x$.

[quote=April]Determine all functions $ f$ defined on the set of rational numbers that take rational values for which
\[ f(2f(x) \plus{} f(y)) \equal{} 2x \plus{} y,
\]
for each $ x$ and $ y$.[/quote]

Let $P(x,y)$ be the assertion
$f(2f(x)+f(y))=2x+y$

$f$ is bijective
$P(0,0)\implies f(3f(0))=0$
$P(3f(0),3f(0))\implies f(0)=9f(0)$
$\implies f(0)=0$

$P(0,x)\implies f(f(x))=x$ (*)
Take $f$ for two sides
$\implies f(f(2f(x)+f(y))=f(2x+y)$
$\implies 2f(x)+f(y)=f(2x+y)$
Put $y=0\implies f(2x)=2f(x)$
Therefore, $f(2x)+f(y)=f(2x+y)$
Put $x=\frac{x}{2}\implies f(x+y)=f(x)+f(y)$
It's Caushy functional equation

$\implies f(x)=cx$
Substitute it in (*)
$c^2x=x \implies c^2=1$
$\implies$ either $c=1$ or $c=-1$

Therefore the solutions are $f(x)=x$
and $f(x)=-x$
And we won a pizza :P

Let $P(x,y)$ be the assertion, \\
$P(0,0) \Rightarrow f(3f(0))=0$\\
$P(3f(0),x) \Rightarrow f(f(x))=6f(0)+x \Rightarrow f \ \ \textrm{is bijective}$\\
$P(0,f(x)) \Rightarrow f(0)=0 \Rightarrow f(f(x))=x$
$P(f(x),0) \Rightarrow f(2x)=2f(x)$
Take $u=f(2x), v=f(y)$, the original function becomes \[f(u+v)=f(u)+f(v), \] $f$ is linear on $\mathbb{Q}$.
Plugging in $f(x)=cx$, we get $f(x)=\pm x. \ \ \blacksquare$

$P(x,y)$ is the assertion $f(2f(x)+f(y))=2x+y$.
Fixing $x$ and letting $y$ vary, we see that $f$ is bijective. Let $f(k)=0$.
$P(k,x)\Rightarrow f(f(x))=2k+x$
$P(f(x),f(y))\Rightarrow f(6k+2x+y)=2f(x)+f(y)$
Plugging this back in, we get:
$$f(f(6k+2x+y))=2x+y$$
So $8k+2x+y=2x+y$, and we get $k=0$ and $f(0)=0$.
Then $f(f(x))=x$.
$P(f(x),f(y))\Rightarrow f(2x+y)=2f(x)+f(y)$
Setting $y=0$ here yields $f(2x)=2f(x)$, so $f(2x+y)=f(2x)+f(y)$ and $f$ is additive, so linear. Solutions, after checking: $\boxed{f(x)=x}$ and $\boxed{f(x)=-x}$

By guessing we can see here that $f(x)=x$ satifies here
[b][color=#f00]Claim:[/color][/b] $f$ is bijective function.
[b][color=#00f]Proof:[/color][/b] Lets suppose $f(a)=f(b)$ and suppose $P(x,y)$ is the assertion of the functional equation.\\
$P(x,a)$\[\implies f(2f(x)+f(a))=2x+a\]
$P(x,b)$\[\implies f(2f(x)+f(b))=2x+b\]
since we can see here that $f(2f(x)+f(a))=f(2f(x)+f(b))$ then we can say that $2x+a=2x+b\implies a=b$ hence we can say that $f$ is injective\\
$P(0,y)$\[f(2f(0)+f(y))=y\]hence we can say that $f$ is bijective since this is surjective.$\square$\\

Putting $P(0,0)$\[\implies f(2f(0)+f(0))=0\implies f(3f(0))=0\]
now putting $x=3f(0)$ in the orignal equation we have
\[\implies f(2f(3f(0))+f(y))=2\cdot3f(0)+y\implies f(f(y))=6f(0)+y\]as we know that $f$ is bijective so it should follow involution so we can say that $f(0)=0$\\
Putting $P(f(x),f(y))$\[\implies f(2f(f(x))+f(f(y)))=2f(x)+f(y)\implies f(2x+y)=2f(x)+y\]
Putting $P(x,0)$\[\implies f(2x)=2f(x)\]and we can see that this is cauchy's functional equation so that solution of this functional equation should be $f(x)=cx$ where $c$ is some constant.\\
Now puttting $f(x)=cx$ in the orignal equation and we have
\[\implies f(2cx)=2x\implies 2c^2x=2x\implies c^2=1\implies c=\pm1\]
hence the solution of the functional are $f(x)=x$ and $f(x)=-x$ and we are done.$\blacksquare$ :D

Let $P(x,y)$ the assertion of the given F.E.
$P(0,x)$
$$f(2f(0)+f(x))=x \implies f \; \text{bijective}$$
Let $c$ such that $f(c)=0$
$P(c,c)$
$$3c=f(0)$$
$P(0,0)$
$$3f(0)=c \implies f(0)=0=c$$
$P(0,x)$
$$f(f(y))=y \implies f \; \text{involution}$$
$P(f(x),f(y))$
$$f(2x+y)=2f(x)+f(y) \implies f \; \text{linear}$$
Since $f(0)=0$ let $f(x)=ax$ where $a$ is a rational number.
$$2a^2x+a^2y=2x+y \implies a=\pm 1 \implies f(x)=\pm x$$
Now assume that exists $a,b$ such that $f(a)=a$ and $f(b)=-b$.
$P(a,b)$
$$\pm(2a-b)=2a+b \implies \text{contradiction!!}$$
Thus the solution is:

$\boxed{f(x)=\pm x \; \forall x \in \mathbb Q}$

And we are done  :blush:

A better solution than my previous one:
Let $P(x,y)$ be the given assertion.
$P(2f(a)+f(b),2f(b)+c)\Rightarrow f(4a+4b+c)=4f(a)+4f(b)+f(c)$
Setting $a=b=c=0$, we have $f(0)=0$. Then setting $c=0$, we obtain the assertion $Q(x,y):f(4x+4y)=4f(x)+4f(y)$
$Q(x,0)\Rightarrow f(4a)=4f(a)$
$Q(0.25x,0.25y)\Rightarrow f(x+y)=f(x)+f(y)\Rightarrow f(x)=cx$ for some $c\in\mathbb Q$. Testing, only $\boxed{f(x)=x}$ and $\boxed{f(x)=-x}$ work.

Let $P(x, y)$ be assertion
[b]Claim:[/b] $f(0)=0$
[i]Proof:[/i]
$P(0, 0)$: $f(3f(0))=0$
$P(3f(0), 3f(0))$: $f(0)=9f(0)$ so $f(0)=0.\square$
Now $P(0, y)$: $f(f(y))=y$
$P(f(x), 0)$: $f(2x)=2f(x)$
$P(f(x), f(y))$: $f(2x+y)=2f(x)+f(y)=f(2x)+f(y)$
and this is Cauchy over rationals, putting $f(x)=cx$ into original, we have $c^2=1$, therefore answers are $\boxed{f(x)=x, \forall{x}\in \mathbb{Q}}$, $\boxed{f(x)=-x, \forall{x}\in \mathbb{Q}}$.

Let $P(x,y)$ denote the assertion that \[ f(2f(x) + f(y)) = 2x + y,
\]

Claim: $f$ is bijective.
Surjectivity is obvious.

Suppose $f(a)=f(b)$.

$P(x,a): f(2f(x)+f(a))=2x+a$
$P(xb): f(2f(x)+f(a))=2x+b$.
Comparing gives $a=b$ $\blacksquare$.

Let $k$ satisfy $f(k)=0$.

$P(k,x): f(f(x))=2k+x$.

$P(f(x),f(y)): f(6k+2x+y)=2f(x)+f(y)$.

So we have $f(f(6k+2x+y))=8k+2x+y$ and $f(f(6k+2x+y))=f(2f(x)+f(y))=2x+y$.

Thus, $8k=0\implies k=0\implies f(0)=0$.

So $f$ is an involution.

$P(f(\frac{x}{2}),0): f(x)=2f(\frac{x}{2})$.

$P(f(\frac{x}{2}),f(y)): f(x+y)=f(x)+f(y)$.

Claim: $f(x)=kx$ for some rational constant $k$.
Proof: This is Cauchy's FE over $\mathbb{Q}$, but I'll prove it. Let $Q(x,y)$ denote the assertion that $f(x)=f(y)$ and $f(1)=k$.

$Q(0,0): f(0)=2f(0)\implies f(0)=0$.

$Q(1,1): f(2)=2k$.

$Q(x-1,1): f(x)=f(x-1)+k$, so by induction, we have $f(x)=kx\forall k\in \mathbb{N}$.

$Q(x,-x): f(x)=-f(-x)$, so $f(x)=kx\forall k\in \mathbb{Z}$.

Note that $f(x+x_1+x_2+\ldots+x_n)=f(x)+f(x_1)+f(x_2)\ldots +f(x_n)$. So $f(q\cdot \frac{p}{q})=qf(\frac{p}{q})\implies kp=qf(\frac{p}{q})\implies f(\frac{p}{q})=\frac{kp}{q}$ $\blacksquare$.

Since $f$ is an involution, $\boxed{f(x)=x}$ or $\boxed{f(x)=-x}$. Both these solutions work.

Denote the assertion by $P(x,y).$ We claim that the only functions that work are $f(x)=x$ and $f(x)=-x.$ We show there are no more.

$P(0,0)$ and subsequently $P(3f(0),0)$ imply $f(0)=0.$ Then $P(0,x)$ gives $f$ is involutive. Taking $f$ of $P(x,y)$ we get $Q(x,y): f(2x+y)=2f(x)+f(y).$ $Q(x,0)$ implies $f(2x)=2f(x).$ Thus $f$ is additive and $f(x)=ax.$ Checking it we are done.

Claim: $f$ is bijective. Obviously, $f$ is surjective due to the right hand side. Now, suppose that $f(x_1)=f(x_2).$ Then, $$f(2f(x_1)+f(y))=f(2f(x_2)+f(y))\rightarrow 2x_1+y=2x_2+y\rightarrow x_1=x_2,$$ so $f$ is injective.\\

Claim 2: $f(0)=0.$ Let $c$ be the unique value for which $f(c)=0.$ If we plug in $x=c$, we get that $$f(f(y))=y+2c.$$ In particular, letting $y=c$, we have $$f(f(c))=f(0)=3c.$$ We can then apply $f$ to both sides of the original equation: $$f(f(2f(x)+f(y)))=f(2x+y).$$ We can use $f(f(y))=y+2c$ to get $$2f(x)+f(y)+2c=f(2x+y).$$ Let $x=0$ so that this becomes $$f(y)+8c=f(y),$$ so therefore $c=0$. and $f(0)=0$.\\

Since $c=0$, we now have $$2f(x)+f(y)=f(2x+y).$$ Letting $y=0$, we have $$2f(x)=f(2x),$$ so we can replace that equation with $$f(2x)+f(y)=f(2x+y).$$ Let $z=2x$ so that this is $$f(z)+f(y)=f(z+y).$$ This is Cauchy, and since we are only in rationals, we have $f(x)=kx$ for some $x$. However, we see that only $k=1,-1$ work, so we have $f(x)=x$ or $f(x)=-x.$

Instructive problem.

Let $P(x, y)$ denote the above assertion.
$P(x, x)$ gives us $f(3f(x)) = 3x$.
$P(3f(x), 3f(y))$ gives us $f(6x+3y) = 6f(x) + 3f(y)$.
Note that $x = y = 0$ in this new equation gives us $f(0) = 0$, now putting in $x$ and $y$ as zero individually gives us $f(6x) = 6f(x), f(3y) = 3f(y)$.
Therefore $f(6x+3y) = f(6x) + f(3y) \implies f(a+b) = f(a) + f(b)$, but this is nothing but Cauchy's functional equation.
Substituting $f(x) = cx$ in the original equation gives us $f(x) = x \forall x$ or $f(x) = -x \forall x$.


Consider a matrix $ T\equal{}\begin{pmatrix}t_{00}&t_{01}\\t_{10}&t_{11}\end{pmatrix}$ acting on homogeneous forms of degree $ d$ in $ x_0, x_1$:

$ T^*: S_d \to S_d$
by $ T^*(F(x_0,x_1))\equal{}F(x_0 t_{00}\plus{}x_1 t_{10},x_0 t_{01}\plus{}x_1 t_{11})$.

Show that $ T^*$ is linear and compute its determinant in terms of $ det(T)$.

[hide]
For any scalar $ A$ and $ B$, and for any $ F(x,y)$,$ F(a,b)$ in $ S_d$, we have that :
$ T*(AF(x,y)+BF(a,b))=AF(x{t}_{00}+y{t}_{10},x{t}_{01}+y{t}_{11})+BF(a{t}_{00}+b{t}_{10},a{t}_{01}+b{t}_{11})$
$ A.T*(F(x,y))+B.T*(F(a,b))$
The matrix representation of the linear operator $ T*$ is $ T^'$, where $ T^'$ is the transpose of matrix $ T$, then $ det(T*)=det(T)$
[/hide]


2005 boxes were arranged around a stadium.There are a numbers of balls in each boxes(must not be equal).Suppose that we have anough ball to play this game:each times,choose 6 consecutive boxes and put one ball into each boxes.After finite times,can we play such that 2005 boxes have the same number of the balls?
(What happen if we replace 2006 boxes to 2005 boxes)

Let $a_k$ be the number of balls in the $k$_th box, with $k \in \Z/2005\Z$, and let $b_k=a_k-a_{k-1}$ for all $k$.

Adding a ball to six consecutive boxes is equivalent to replacing $b_k$ by $b_k+1$ and $b_{k+6}$ by $b_{k+6}-1$.

By doing this operation for all $k$ except one we get the inverse operation (that is removing $1$ to $b_k$ while adding it to $b_{k+6}$.

We can thus make $b_k$ become $0$ while only changing $b_{k+6}$.
Apply this principle to $b_0$, then $b_6$, $b_{12}$, ... , $b_{6n}$, ... , $b_{6*2003}$.
The only $b_k$ that can still be non-zero is $b_{6*2004}$, so it must also be $0$ since $\sum \left(b_k\right)=0$.

We thus have equalized the number of balls in each box.

(it works only because $6$ and $2005$ are coprime.)

For 2006, just consider a case where the number of balls is odd.


AMC AIME function algebra polynomial calculus derivative

Merry Christmas, Happy Chanukah, and/or Happy New Year! If you are a Buddhist in China... happy winter solstice!

Santa has fifteen presents to place in a circle under a Christmas tree (starting with one directly north). He has four kinds of wrapping paper, and packages wrapped in the same paper look identical. He insists that he not place two packages with the same wrapping paper next to each other, but is worried that he will not be able to make the base of every tree look different (when looking directly north). How many ways are there to wrap and place the packages?

Come on guys, any partial solutions? It's just some recursion. And it's good AIME practice.

Or is it just that it's the holidays, and you don't want to think about it?

Here is what I got (I haven't done recursion recently, so I may have slightly messed up):

Sorry I didn't post earlier, but I was busy & on vacation.

[hide]For a generic case of $n$ presents, we will generate each arrangement using previous arrangements.

Looking at each arrangement or $n-1$, we can see that to create an arrangement for $n$ presents, we simply insert a present in between two presents.  There will be two choices for this present's wrapping paper because the ones on either side will have different colored paper, leaving two choices.

However, this only counts the arrangements where the present is added between two different presents, excluding ones where the present is added between two of the same presents.  To account for this, look at each arrangement of $n-2$ presents.  Two presents will be added, one will match, leaving the other with 3 arrangements.

Thus, the recursion is $S_{n}=2S_{n-1}+3S_{n-2}$, so for 15 presents, there are $14,348,904$ arrangements, where $S_{k}$ is the number of arrangements of $k$ presents.

$S_{2}=12$
$S_{3}=24$
$S_{4}=84$
$\vdots$

I am still working on the general formula - I'll post it when I get it.[/hide]

[hide="solution"]As b-flat said, f(n+2)=2f(n+1)+3f(n). Notice that f(2)=12 and f(3)=24. In fact, f(1)=0! In such a recurrence, I suggest you try the third term to make sure it works. Hopefully, this will help you notice that f(1) is not 4. It is 0 because the single element is adjacent to itself, which breaks the rules.

To solve a recurrence, turn $f(n+0)$ into $n^{0}$, $f(n+1)$ into $n^{1}$, $f(n+2)$ into $n^{2}$, etc. and solve for n: $n^{2}=2n+3$ so $n=-1$ or 3. Then $f(n)=a*(-1)^{n}+b*3^{n}$ for constants a and b. Then $f(1)=3b-a=0$ and $f(2)=9b+a=12$. Solving, b=1 and a=3, so $f(n)=3^{n}+3(-1)^{n}$ and $f(15)=3^{15}-3=14,348,904$.[/hide]

Thanks for the help on generating a generic formula, I'd forgotten how to do that  :blush:

Nice problem, by the way!

Thanks, I wish I could claim the credit. It's from the 2005 University of Illinois at Urbana-Champaign comprehensive exam (I think this is some sort of math competency exam, possibly a graduate school entrance exam). I got it from $MO_{s}P$. It was, in fact, the last problem on a handout, and thus supposedly the hardest. See, $MO_{s}P$ isn't too bad :).

See if you can prove the generic formula for a solution to a recurrence.  Of course it's possible to simply "guess" the result and prove it satisfies the recurrence, but there are other solutions.  Generating functions offer the slickest attack and the method can be generalized to solve more complicated recurrences (for example f(n+2)=a*f(n+1)+b*f(n)+c).   There is also a nice approach via Linear Algebra that is perhaps more transparent to the non-generatingfunctionologist :) .  If anybody has another natural proof (perhaps one based on a counting argument?) I'd be very happy to see it.

jb05-Have you ever read 102 Combinatorial Problems?
If not, then the following is quite nice:
An a by b chessboard can be tiled with some combination of 1 by m and n by 1 bricks (note that bricks cannot be rotated).  Prove that it can be covered either entirely with 1 by m bricks or entirely with n by 1 bricks.  Solve it and I'll post something harder :)

By the way, at several colleges I know of the comprehensive exam is taken after a few years (1 or 2) of grad school, though that may not be the case everywhere.  It determines whether one is ready to start work on a PHD.

I do have that book. Here is a much easier proof for the general formula that also generalizes to linear differential equations (and linear difference equations and tons of other stuff too) ;). In fact, the weird operator notation isn't necessary, it just makes it a lot easier to stomach, I think.

Let $E$ be an operator such that $E^{n}f(x)=f(x+n)$ (that is, $Ef(x)=f(x+1)$ and multiplication of such operators represents iteration). Note that $E^{n}a^{x}=a^{n}a^{x}$ (with respect to x) so that if we apply any function of E to $a^{x}$, we can replace $E$ by $a$ and treat as arithmetic. Then a general linear recurrence can be written $(c_{n}E^{n}+...+c_{1}E+c_{0})f(x)=F(E)f(x)$. Note that if the roots of the polynomial in $E$ are $r_{1}, r_{2}, ..., r_{n}$ and $f(x)$ is of the form $a_{1}r_{1}^{x}+a_{2}r_{2}^{x}+...+a_{n}r_{n}^{x}$, then $F(E)f(x)=a_{1}F(E)r_{1}^{x}+...+a_{n}F(E)r_{n}^{x}=a_{1}F(r_{1})r_{1}^{x}+...+a_{n}F(r_{n})r_{n}^{x}=0$. It isn't hard to prove that this provides a unique function for each choice of the first n-1 terms of the sequence, and that only one such function exists, so this must be unique.

The equation for differential equations is similar in that $\Delta f(x)$ (the derivative) can be calculated for $f(x)=c^{x}$ by replacing $\Delta$ with $\ln{c}$. By the way, try proving that $\Delta=ln{E}$

[quote="jb05"] It's from the 2005 University of Illinois at Urbana-Champaign comprehensive exam [/quote]

2003 North Carolina State Mathematics Contest has a similar problem:

The tips of a five-pointed star are to be painted red, white and blue. How many ways can this be done if no adjacent points can be the same color?

There is a general formula for n presents and m kinds of wrapping paper. Just go one more step from $f(n)=3^{n}+3(-1)^{n}$ .

Your solution is identical, effectively, to the generating function method I spoke about earlier.  The operator notation is interesting however... I have seen that sort of argument applied several times but never formalized in such generality :).

What do you think of 102?


probability
symmetry
LaTeX
induction
modular arithmetic

how many 7 digit numbers divisible by 3 is possible using 0,1,2,3,4,5,6.repetition is allowed.

there are too many cases when i solve this question,pl suggest some another way.

[hide="Dunno if helps"]Maybe you can find the number of solutions to

$ 0a_0 \plus{} a_1 \plus{} 2a_2 \plus{}...6a_6 \equal{} 3k$  or $ \equiv 0 \mod 3$

$ a_0 \plus{} a_1 \plus{} a_2 \plus{} ... \plus{} a_6 \equal{} 7$ , where $ a_0 \neq 7$[/hide]

moderators  please  move this.

and  ayush  this  is not  surely  a  questions that 13+  guy  must be doing/  or rather  say this is not the right place to post it

[color=green]I don't know if you meant the question was too easy or too hard, but it should stay here. ~Mod[/color]

I'm tired and have a migraine, but I couldn't help trying this problem.  I struggled with case work like you, getting some ideas but then realizing that I would still need more cases.

I think this idea will work
[hide]

The difficult thing to understand in this problem is that throwing in the 0 digit doesn't effect the probability that the sum is divisible by 3.  It's clear that with adding 1,2,3,4,5,6 all mods of 3 are equally likely and thus have a 1/3 chance... 0 doesn't change that because if you pair it alternately with each of the numbers, it is 0 mod 3 with only 3 and 6 but not 1,2,4,5.  So the answer should be 6*7^6*1/3.  The lack of a 0 in the left digit slot doesn't matter because its presence or absence in the set of numbers doesn't change the chance of divisibility by 3.

 [/hide]

I feel much better about this idea than the previous one I formulated  :blush: haha

[quote="b555"]instead  of  using the idea of permutations  and combinations  what u can do is  use  the  idea  of  ARITHMETIC PROGRESSIONS   here.

 let the smallest 7 digit number divisible by 3 be x   and  the  largest 7 digit number divisible  by 3  be  y.

    now  we have  an AP  with  x as  first term  and y as last term  and common difference  3.

               so  we have    y= x + (n-1)3   where  n  is the number of such 7 digit numbers.

     now u know x  , u know  y .  so u can evaluate  `n`  which  is the required answer.

as u have seen it  becomes  a case bash if u use  permutations only.[/quote]
my friend How can you say answer is 6*7^6*1/3.because continuity  breaks after some interval.example
1000000
1000001
1000002
1000003
1000004
1000005
1000006
now next number is not in series .we can use 7 as digit

[quote="b555"]ayush  i think  u have  totally misunderstood the  point  of my explanation.

i suggest u kindly have  a relook  at wat  i have  said in my warlier post[/quote]
can you explain it bit further what you want too say.

b555, your solution doesn't take into account the digit restrictions: it counts lots of numbers that have the digits 7, 8 and 9.  ayush is right.

This problem is well-suited to a recursive approach: let $ a_n$ be the number of $ n$-digit numbers with digits 0, 1, ..., 6 that are divisible by 3, let $ b_n$ be the number of $ n$-digit numbers with digits 0, 1, ..., 6 that leave a remainder of 1 when divided by 3, and let $ c_n$ be the number that leave a remainder of 2 when divided by 3.  The number you want is $ a_7$.  Since the divisibility rule for 3 is so simple, it's relatively easy to see that $ a_{n \plus{} 1} \equal{} 3a_n \plus{} 2b_n \plus{} 2c_n$ -- just consider what happens when you erase the units digit of one of the numbers counted by $ a_{n \plus{} 1}$.  Then find similar recursions for $ b_{n \plus{} 1}$, $ c_{n \plus{} 1}$.  You also have some initial values that are easy to compute.  Then you can either use the recursions to compute the value you're interested in or use them to find a closed formula.

winternights1's solution is quite sketchy but fundamentally sound: using the same notation from the previous paragraph, we have that $ a_1 \equal{} b_1 \equal{} c_1 \equal{} 2$, so we're in a nice symmetric situation.  Choosing a random new units digit from the given options is as likely to toss us from the "divisible by 3" pile into the "1 mod 3" pile as into the "2 mod 3" pile, and similarly for the other three cases, so we always stay symmetric.  Thus exactly one third of all such numbers will be divisible by 3.  Note that the symmetries involved here (the equal initial values and the symmetry of the set of digits involved) are both essential, and that this solution becomes at best heuristic and at worst completely wrong if one or both of these symmetries are missing.

Some requests relating to forum etiquette: please use proper spelling and grammar (including punctuation, capitalization, etc.) to the extent possible, as it makes posts much easier to understand.  Likewise, please use LaTeX when appropriate, for readability.  Finally, there's never a good reason to quote the entire post immediately preceding yours: you are responding to it by default.

So the system is

$ a_{n\plus{}1}\equal{}3a_n\plus{}2b_n \plus{} 2c_n$
$ b_{n\plus{}1}\equal{}3b_n\plus{}2a_n\plus{}2c_n$
$ c_{n\plus{}1}\equal{}3c_n\plus{}2a_n\plus{}2b_n$

$ a_1\equal{}b_1\equal{}c_1\equal{}2$ (exclude 0)

but how to find the closed-form though?

Well, the easiest way is at this point to prove by induction that $ a_n = b_n = c_n$ for all $ n$ ;)

If this weren't available to us, we could proceed as follows: from the first equation we have $ a_{n + 1} - 3a_n = 2b_n + 2c_n$.  Then the second equation implies
\begin{align*} b_{n + 1} - 3b_n & = 3(b_n - 3b_{n - 1}) + 2(a_{n} - 3a_{n - 1}) + 2(c_n - 3c_{n - 1}) \\
& = 3(b_n - 3b_{n - 1}) + 2(2b_{n - 1} + 2c_{n - 1}) + 2(c_n - 3c_{n - 1}). \end{align*}
Do something similar in the third equation and you've eliminated $ a_n$; then repeat again with the resulting two equations to eliminate $ b_n$ and you'll have solved for $ c_n$.  Then you can take this back to find $ a_n$ (or could have the sense to eliminate $ b_n$ and $ c_n$ instead of eliminating $ a_n$ so you don't have to take anything back anywhere).

[quote="JBL"]b555, your solution doesn't take into account the digit restrictions: it counts lots of numbers that have the digits 7, 8 and 9.  ayush is right.[/quote]

ya   sorry  i  was  considering all the  7 digit  numbers.   got  my mistake.

Thanks JBL.  I'm glad to know I'm not both sketchy and unsound.  I like your recursion solution; I never thought of seeing it that way.  Sorry about the lack of Latex, I just started posting 2 days ago and will learn how to use it... right after this  :lol:

Can you salvage my explanation without your recursion by

1) giving a good reason for saying that using a set of numbers equally representing 0 mod 3, 1 mod 3, and 2 mod 3 as digits will have exactly 1/3 of the formed numbers divisible by 3.  Like, say, use the word symmetry, as you suggested.

2) Instead of writing out the sums of 0 and 1 through 6, say that substituting in a 0 for a given digit is still just as likely to make the number 0, 1, or 2 mod 3 because all digits in the 6^7 calculation all digits ought to have been used the same amount.

3) Substituting in 0's for any group of digits keeps the same probability of the number being divisible by 3 EXCEPT if you replace all 7 digits with 0's... in this case the number is 100% likely to be divisible by 3.  But this doesn't happen because the first digit can't be a 0.

Would this be better, JBL?  I think 3) is the most important correction... 2) is just more completely expressed than before.

[hide="hint"]Base 7
[/hide]

[hide="solution"]Notice divisibility rule for base 7 is the same as in base 10 since $ 7 \equiv 10 \pmod 3$. We need to count the number of 7 digit base 7 numbers divisible by 3, which is $ \frac {7^7 \minus{} 7^6}{3} \equal{} 2\cdot 7^6$.[/hide]


limit
Euler
logarithms
real analysis
real analysis unsolved

The sequence $ \{T_n\}$ is defined by $ T_1 \equal{} 1$ and, if $ n>1$,
\[ T_n \equal{} 1\plus{}\frac{2}{n^2}\left(\sum_{k\equal{}1}^{n\minus{}1}kT_k\right)\,.\]
Prove that
\[ \lim_{n\rightarrow\infty} \frac{T_n}{\ln(n)} \equal{} 2\,.\]

Please give me an idea how to deal with it.  Thank you in advance.

Here is one possible approach :). Let $ U_n\equal{}\sum_{k\equal{}1}^n kT_k$. Then $ U_n\equal{}\frac{n\plus{}2}{n}U_{n\minus{}1}\plus{}n$. Now let $ V_n\equal{}\frac{U_n}{(n\plus{}1)(n\plus{}2)}$. Then $ V_n\equal{}V_{n\minus{}1}\plus{}\frac n{(n\plus{}1)(n\plus{}2)}$. Thus $ V_n\equal{}V_1\plus{}\sum_{k\equal{}2}^n \frac k{(k\plus{}1)(k\plus{}2)}$. The last sum can be computed with any power precision using [url=http://en.wikipedia.org/wiki/Euler%27s_summation_formula]Euler-MacLaurin[/url] (for the rough result you mentioned the leading $ \log n$ term plus just the mere existence of the asymptotic series is already more than enough but you can get as precise expression for $ T_n$ as you wish this way).


rotation
combinatorics unsolved
combinatorics

Hey guys, here is a problem I haven't been able to solve.

The lock on a safe consists of three wheels A, B, and C, each of which may be set in eight
different positions. Due to a defect in the mechanism, the door will open when any two of
the wheels are in the correct position. Thus anybody can open the safe in 64 tries by letting
B run through all 8 position for each position of A. . What is the minimum number of tries that is guaranteed to
open the safe?

I think the problem is from the shortlist of the 1988 IMO. Does anyone know a nice solution?

Thanks

I think it should be half that, i.e. $32$ combinations, but I haven't proven it. I think I worked out a set of $32$ combinations, but I didn't have the patience to check whether it really works or not. It did work for all of the few random combinations of the lock I picked, but that's no proof :).

PS: It is from ISL 1988 and it's solved here: http://www.mathlinks.ro/Forum/viewforum.php?f=177. The download section is really cool. Unfortunately it is not online right now... But try again soon.  :)

PPS: Back then I was not sure either. Look [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=916]here[/url].

I would gladly write the solution, but I don't have one.

A try is checking whether a certain combination works or not. We're not concerned with moves of the wheels or anything like that. For example, you move the wheels to get the combination $1\ 2\ 3$ and check whether it's good. This is a try.

As PMV mentioned, it's obvious that we can crack the safe by operating only on the first two wheels in $64$ tries. However, I think it can be done in $32$ moves (I haven't checked if it actually works), and I also think this is the smallest number. I might very well be wrong though.

[quote="Myth"]Hi everyone!
What is try? Can we rotate two wheels at once?
My poor internet connection doesn't allow me to download such large files.
Grobber! Can you write solution here? Please...[/quote]

The answer is 32. Why downloading files you already have. Just check your file archive.   :D

For all the others: Look at http://imoshortlista.tripod.com/ . Download the 1988 document and have a look on page 9/10.  :)

Of course, you are right, Orlando!
I looked through it and found that ISL1988 has terrible appearance quality :(

I am impressed :o . Solution from Crux takes 4 (!) pages.


Determine whether the given function is a solution to the differential equation. If this function is a solution, determine whether it satisfies the indicated initial condition.

y=e^(2x)-2, y'=2y+4,y(0)=-2

hello, we have $ y^'(x)=e^{2x}\cdot2$ inserting this in our equation we have $ 2e^{2x}=2(e^{2x}-2)+4=2e^{2x}-4+4=2e^{2x}$, so our equation is fulfilled, but $ y(x)=e^{2x}-2$ satisfies not the initial conditon, because $ y(0)=e^0-2=-1\ne -2$.
Sonnhard.


Let sequence {$ x_n$}and$ k>0$ such that
$ x_1\equal{}1,x_{n\plus{}1}\equal{}x_{n}\plus{}\frac{1}{{x_{n}}^k}$
prove that exist a>0 such that $ lim\frac{x^a}{n}\equal{}m<>0$

$ x_{n\plus{}1}^{k\plus{}1}\equal{}x_n^{k\plus{}1}\plus{}k\plus{}1\plus{}\frac{k(k\plus{}1)}{2x_n^{k\plus{}1}}\plus{}...$
It give $ x_n\equal{}((k\plus{}1)n\plus{}\frac{k}{2}ln(n)\plus{}c\plus{}O(\frac 1n ))^{1/k\plus{}1}$.


[quote="cincodemayo5590"][quote="linzk3"]The raddi of two circles are log(16) and log(4) respectively.  Find the ratio of:
a.  the circumference of the large circle to that of the small circles

b.  the area of hte large circle to that of the small circle.

don't know how to approach this.[/quote]

[hide="Hint"]
$\log(4^{2}) = 2 \cdot \log(4)$.  :wink: [/hide][/quote]

4:1 ? :blush:

[quote="linzk3"][quote="cincodemayo5590"][quote="linzk3"]The raddi of two circles are log(16) and log(4) respectively.  Find the ratio of:
a.  the circumference of the large circle to that of the small circles

b.  the area of hte large circle to that of the small circle.

don't know how to approach this.[/quote]

[hide="Hint"]
$\log(4^{2}) = 2 \cdot \log(4)$.  :wink: [/hide][/quote]

confused... :blush:[/quote]
[hide="further hint :) "]
Let $\log 4 =x$, so that the circles have radius $x$ and $2x$. Now, what are the formulas for perimeter and area? Then, how do we find the ratios?[/hide]

[quote="cincodemayo5590"][/quote][quote="linzk3"][quote="cincodemayo5590"][quote="linzk3"]The raddi of two circles are log(16) and log(4) respectively.  Find the ratio of:
a.  the circumference of the large circle to that of the small circles

b.  the area of hte large circle to that of the small circle.

don't know how to approach this.[/quote]

[hide="Hint"]
$\log(4^{2}) = 2 \cdot \log(4)$.  :wink: [/hide][/quote]

confused... :blush:[/quote][quote="cincodemayo5590"]
[hide="further hint :) "]
Let $\log 4 =x$, so that the circles have radius $x$ and $2x$. Now, what are the formulas for perimeter and area? Then, how do we find the ratios?[/hide][/quote]

a. 4:1?
b. 9:1?

[quote="linzk3"][hide="quoted conversation "][/quote][quote="cincodemayo5590"][/quote][quote="linzk3"][quote="cincodemayo5590"][quote="linzk3"]The raddi of two circles are log(16) and log(4) respectively.  Find the ratio of:
a.  the circumference of the large circle to that of the small circles

b.  the area of hte large circle to that of the small circle.

don't know how to approach this.[/quote]

[hide="Hint"]
$\log(4^{2}) = 2 \cdot \log(4)$.  :wink: [/hide][/quote]

confused... :blush:[/quote][quote="cincodemayo5590"]
[hide="further hint :) "]
Let $\log 4 =x$, so that the circles have radius $x$ and $2x$. Now, what are the formulas for perimeter and area? Then, how do we find the ratios?[/hide][/quote][quote="linzk3"]
[/hide]
a. 4:1?
b. 9:1?[/quote]

Not quite.

[hide="The formulas are..."] \[\text{Perimeter }= 2 \pi r \] \[\text{ Area}= \pi r^{2}\] So, what is the perimeter and area of each, in terms of our $x$? [/hide]


geometry
3D geometry
tetrahedron
analytic geometry
function
geometric transformation
calculus

find the centroid of tetrahedron formed by the plane $ \frac{x}{a}\plus{}\frac{y}{b}\plus{}\frac{z}{c}\equal{}1$ and the coordinate planes.

A regular tetrahedron has, unambiguously, a center, which can be found by averaging the four vertices. Given any shape $ \Omega$ with centroid $ p,$ if we act on this space by an affine transformation $ T$ (the sum of a linear function and a translation), then $ T(\Omega)$ has centroid $ T(p).$ Furthermore, the average of the four vertices of a tetrahedron also transforms the same way under an affine transformation. Since we can find any arbitrary tetrahedron as the image of a regular tetrahedron under an affine transformation, it is always true that the centroid of a tetrahedron is the average of the four vertices.

The given tetrahedron has vertices $ (0,0,0),(a,0,0),(0,b,0),$ and $ (0,0,c).$ Its centroid is $ \left(\frac{a}4,\frac{b}4,\frac{c}4\right).$

The volume is $ \frac{abc}{6}$. The centeroid is $ \left(\frac{a}{4},\frac{b}{4},\frac{c}{4}\right)$.


The volume of a certain rectangular solid is $ 8 \text{ cm}^3$, its total surface area is $ 32 \text{ cm}^3$, and its three dimensions are in geometric progression.  The sums of the lengths in cm of all the edges of this solid is

$ \textbf{(A)}\ 28 \qquad \textbf{(B)}\ 32 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 40 \qquad \textbf{(E)}\ 44$

Let the three dimensions be $ \frac ar,a,ar$ so that $ a^3\equal{}8\implies a\equal{}2$ and $ a^2\plus{}\frac{a^2}r\plus{}a^2r\equal{}16\implies ar\plus{}a\plus{}\frac ar\equal{}8\implies4\left(ar\plus{}a\plus{}\frac ar\right)\equal{}\boxed{\textbf{(B)}\ 32}$.

Is it me, or was this on the Ct ArML this year?


calculus
integration
real analysis
real analysis unsolved

Let $ f: [0,1]\to\mathbb{R}$ be a differentiable function. Show that there exists $ c\in (0,1)$ such that

\[ \displaystyle (c\minus{}1)f(c)\equal{}f^{\prime}(c)\int_0^c (x\minus{}1)f(x)dx.\]

Hello
Did you miss something like , $ \[ \displaystyle \int_{0}^{1}f(x)dx\equal{}\int_{0}^{1}xf(x)dx\equal{}1. $ in ypothesis?
If you did so, then we can apply rolle to $ g\left( t \right) \equal{} \frac{{\int\limits_0^t {\left( {x \minus{} 1} \right)f\left( x \right)dx} }}{{{e^{f\left( t \right)}}}},t \in \left[ {0,1} \right]$

Well, some condition is surely missing: for $ f(x) \equal{} 1$ we have $ c \minus{} 1 \equal{} 0$ nowhere on $ (0, 1)$.  (There are also examples for which we do not have equality at the endpoints, e.g. $ f(x) \equal{} \frac{1}{x \plus{} 1}$.)


The following problem is confusing me so any help would be greatly appreciated!

Find the set of all matrices with respect to the standard basis for R^2 for all linear operators that take all vectors of the form [0, y] to vectors of the form [0, y'].

Applying the matrix $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$ to $[0,y]$, you get $[by,dy]$. So, anything with $b=0$ will do.