If $a,b,c>0$ find $A$ such that   $\frac{1}{a+b-c}+\frac{1}{b+c-a}+\frac{1}{c+a-b}\geq A$

$\frac{1}{a+b-c}+\frac{1}{b+c-a}+\frac{1}{c+a-b}-\frac{9}{a+b+c}=\frac{8(a^3+b^3+c^3+3abc-a^2b-ab^2-b^2c-bc^2-c^2a-ca^2)}{(a+b+c)(a+b-c)(b+c-a)(c+a-b)}$
Therefore, your inequality is true only when $a,b,c$ are sides of a triangle. (Take, for instance, $a=1$, $b=1$ and $c=10$ to verify your inequality is wrong.)
If $a,b,c$ are sides of a triangle, it can be easily proved by Cauchy-Schwarz.

:?:

Taking $a=3x$, $b=c=x$, $LHS = \frac{-1}{3x} \rightarrow -\infty$ when $x \rightarrow 0^+$ so no lower bound exists ??

I think he wants us to find $A$ in terms of $a,b,c$.


Vieta
inequalities
vector
absolute value
geometric series
complex numbers
triangle inequality

Suppose that the coefficients of the equation $x^n + a_{n-1} x^{n-1} + ... + a_1 x + a_0 = 0$ are real and satisfy $0 < a_0 \le a_1 \le ... \le a_{n-1} \le 1$.  Let $z$ be a complex root of the equation with $|z| \ge 1$.  Show that $z^{n+1} = 1$.

I have an elegant solution of this but I wanted to see if there was a more straightforward and/or general way - Vieta's sums?  I don't know  :|

hmm yea the solution in the aops book is pretty nice and i got a maybe start on another solution? i ono this is what i did so far
(it's a backwards proof for now but you can just "reverse" the direction of the proof if anyone finishes it...)

you want to show $z^{n+1} = 1$, so you start with:

$z^{n+1} - 1 = (z-1)(z^n + z^{n-1} + \ldots + z + 1) = 0$

you can further simplify this by noting that:

$z^n + a_{n-1} z^{n-1} + \ldots + a_1z + a_0 = 0$

hence, we have:

$(z-1)[ (1-a_{n-1})z^{n-1} + (1 - a_{n-2})z^{n-2} + \ldots + (1-a_1)z + (1-a_0)] = 0$

keeping in mind that this proof is backwards so far, if we were to give a forwards proof, when we reach this point we'd mention that if $z=1$, then our result follows, thus we want to show that the terms in the brackets equals 0

but yea this is where i got stuck...

Here's an alternate solution:
First, prove that for at least one root to have an absolute value that is at least 1, $a_0,a_1,a_2,a_3...a_{n-1}=1$.

Then, $z^n+z^{n-1}+z^{n-2}+...z+1=0$ and thus $(z-1)(z^n+z^{n-1}+z^{n-2}+...z+1)=z^{n+1}-1=0$

well, here is my proof...that is totally different

we have $|z_i| \ge 1$, use this relation on all of the roots (every root must be $\in \mathbb{C}$) and multiply them
$|z_1|*|z_2|*...*|z_{n-1}|*|z_n| \ge 1$ (complex modulus is distributive)
$|z_1*z_2*...*z_{n-1}*z_n| \ge 1 \implies a_0 \ge 1$, and intersection with $0<a_0 \le 1$, $a_0=1$, and that forces $a_i=1$ for $i=1,2,...n-1$, so then it is trivial as our equation becomes
$\sum_{k=0}^n z^k=\frac{z^{n+1}-1}{z-1} \implies z^{n+1}=1$ (using sum of a geometric series)

I think by complex, he is implying the roots can have both real and imaginary components, not that they necessarily do.

i was not sure about that...the way that i interpreted complex is in the form a+bi, where a and b are real, i don't see why b cannot be 0, we know that all elements of the real set are also in the complex set, furthermore, when we solve it the other way, all the roots have |z|=1, even -1 when n is odd
all i can think of now is that if you use decartes, there is no sign variation

[quote="t0rajir0u"][quote="gotztahbeazn"]hmm how do u kno all the roots are complex?[/quote]

$\mathbb{R} \in \mathbb{C}$ :)

That is, the set of complex numbers includes the set of purely real numbers, so all the roots are obviously complex.[/quote]
sorry if u would consider me a nitpicker, but i think notation should be right ;)

actually $\mathbb{R} \subset \mathbb{C}$ and $\mathbb{R} \not\in \mathbb{C}$, but $\forall x\in \mathbb R: x\in\mathbb C$ ;)

so would you guys say that my solution is correct? it seems to make the problem pretty easy, and you circumvent all the stuff with the triangle inequality that the solution manual has,
also saying "a complex root" is ambiguous because we do not know if that implies that the imaginary part is nonzero, since when it says $|z| \ge 1$ if z is a complex root of the equation, it kind of seems that there would be other roots that are not complex, and the only option would be for real numbers to not be considered complex...but that is a false statement :huh:
would any mods like to offer us their wisdom?

Yes, that's my problem with your proof.

Personally, I wanted to go with the idea that if [i]any[/i] of the roots had $|z| \ge 1$ then the coefficients all had to equal $1$, but my proof relies on a geometric argument that only really holds strongly for the first root, and I haven't figured out how to extend it to all the possible roots:

First assume the coefficients do not all equal $1$.  Take the root with the smallest argument.  Then $z^n + a_{n-1} z^{n-1} + ...$ describes the vector sum of a polygon with equal angles and sides in decreasing order.  Take the largest side, which has length $|z|^n$, and draw a regular $n$-gon with that side that contains the original one - it becomes clear that at the end of the vector summation, the inside polygon will not be closed, that is, $z^n + ... \neq 0$ and $|z| \ge 1$ is not a solution - hence, the inside polygon must be regular and all the coefficients equal $1$, from which the result follows.

But for the other roots the polygon's vertices aren't drawn in order...

[quote="Altheman"][quote="gotztahbeazn"][quote="Altheman"]

we have $|z_i| \ge 1$, use this relation on all of the roots (every root must be $\in \mathbb{C}$)[/quote]

well how do u kno the magnitude of all the roots is $\ge 1$ though? the problem only specifies for one root $z$[/quote]

that holds for any "complex root" of the equation...

another thing that one might have to go through is proving that there are no real roots, except -1 when n is odd, it is easy by decartes to show that there are no positve roots, and it is also obvious that 0 is not a root since $a_0>0$, but i don't know about showing that there are no real roots, i think that you could use the synthetic division thing to put a lower bound at -1, but that does not cover (-1,0)[/quote]

Nonono, this problem is far too easy if all the roots have $|z| \ge 1$, I am certain the book means that only one of the roots has this property.

[quote="t0rajir0u"]
Nonono, this problem is far too easy if all the roots have $|z| \ge 1$, I am certain the book means that only one of the roots has this property.[/quote]

but all of the roots do have that property (after you solve it another way)

I haven't seen a proof of that and I don't even think it's necessary to solve the problem  :huh:


Let's be given $x\in R$ and $x>2$
Define the sequence $x_n$ as follow : $x_0=1, x_1=x, x_{n+1}=(\frac{x_n^2}{x_{n-1}^2}-2)\cdot x_n$
Prove that $\sum_{i=0}^n \frac{1}{x_i}<\frac{1}{2}\cdot (x+2-\sqrt{x^2-4}) \forall n\in N$

Oops  :blush:  it's just a typo, I corrected it :D

basilar case: $x=2\to$$x_{i+1}={x_i}$ $\forall i\in\mathbb{N}$
$x+2-\sqrt{x^2-4}=\sqrt{x^2-4}(\sqrt{\frac{x-2}{x+2}}+1)$
Let's define $\delta_i=\frac{x_i}{x_{i-1}}$: from $\delta_{1+i}=\delta_i^2-2$
$\displaystyle \prod_{i=1}^n \delta_i=a_n$
so the sum of the reciprocals of $a_i$s and from here I think you can proceed as vietnamesegauss89 did...Nice solution :), writing the terms as function of limit,that's nice ...are you in the IMO team?


http://story.news.yahoo.com/news?tmpl=story&cid=1894&e=2&u=/ap/20031208/ap_on_sc/science_competition

Amazing.  Yahoo! news actually writes about something useful.  In other news, we had Ozzy Osbourne get in an ATV accident, a murder conviction for Rep. Janklow, and more...

Congratulations to the winners of Siemens-Westinghouse.

What a surprise: another Stuyvesant student.  :o

Hmm.  I don't have any idea who that is.  Long?


A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?

$ \textbf{(A)} \ 8! \qquad \textbf{(B)} \ 2^8 \cdot 8! \qquad \textbf{(C)} \ (8!)^2 \qquad \textbf{(D)} \ \frac {16!}{2^8} \qquad \textbf{(E)} \ 16!$

1234567890 wrote:Elemennop wrote:[hide]The given problem is equivalent to the number of distinct permutations of aabbccddeeffgghh, which is . D.[/hide]

Hold on.... why is this so? I'm confused.   (I'm bad at combinatorics, if you haven't noticed)

if you dont care about order they are put on in, its just the number of ways to arrange 16 items, . so, concider a possible arrangement. for each foot, either he puts on socks first or shoes. if he puts on shoes first, it doesnt count. so, because for each foot, there are two ways, but only one counts, devide by .

Oh, yeah..... I feel dumb. :lol:
The sad thing was that I did a type of problem like that a few days ago.

[quote="badandy"]I have to disagree.

there are 8 slots that need to be filled with 8 socks which means 8! ways.  then those same slots have to be filled with 8 shoes which is another 8! ways.  the sock has to go on first.  therefore (8!)^2 combinations.

another way i looked at is with trees.  for the first foot there 8*8 ways to pick sock then shoe.  for the second foot there are 7*7 ways to pick sock and shoe.  for both feet, there are (8*8)*(7*7) different ways to realize sock/shoe pair up.  continuing for all 8 feet you get (8*8)*(7*7)*...*(2*2)*(1*1) = (8!)^2

what do you think?[/quote]

The question is asking for how many different ways can the spider put on the shoes and socks. Your answer is the number of distinct arrangements of those socks and shoes.

[quote="badandy"]I'm still not seeing the reason behind the solution.

I did a small example with 2 socks, 2 shoes and 2 feet.  using the first method, the answer should be:

4!/2^2 = 6

I did see that if you start with the foot 1 then go to foot 2 there are 4 ways to do this.  If you start with foot 2 then go to foot 1 there are 4 ways to do this.  The total orders for putting on socks then shoes is 8 ways.

What am i missing?[/quote]

With the example of 2 socks, 2 shoes, and 2 feet:

From the first foot to second foot there are three ways: sock on the 1st foot, then 2nd foot, then 2 ways to put on the shoes. The third way is sock on 1st foot, shoe on 1st foot, sock on 2nd foot, shoe on 2nd foot. From 2nd foot to 1st foot yields the same thing, so the total is 6.

The reasoning behind the solution to the original problem is that you have 16 objects to put on (8 socks and 8 shoes), so there are $16!$ different possible sequences in how they are put on. However, this includes the sequences where the shoe is put on before the sock of a particular leg. These occur the same number of times as where the sock is put on before the shoe, so $16!$ is divided by $2$ for each shoe and sock pair. There are $8$ of them, so the answer is $\displaystyle \frac{16!}{2^8}$.

The total number of ways to order the 16 obects, 16!.

Taking into account that the shoes must be put on second, each pair of shoe/socks, has a 50% chance of having been put on in the correct order, thus, there is a 1/2^8 chance that all the shoes were put on after the correspording sock.

ANS: 16/2^8

[quote="badandy"]I did a small example with 2 socks, 2 shoes and 2 feet.[/quote]
I did a similar thing.

[hide]I first noticed that we have the format that if there are $n$ socks, $n$ shoes, and $n$ feet, the answers are in the following formats: $\text{(A)} \ n! \qquad \text{(B)} \ 2^n \cdot n! \qquad \text{(C)} \ (n!)^2 \qquad \text{(D)} \ \frac{(2n)!}{2^n} \qquad \text{(E)} \ (2n)!$

Plugging in 2 for $n$, you get $\text{(A)} \ 2! \qquad \text{(B)} \ 2^2 \cdot 2! \qquad \text{(C)} \ (2!)^2 \qquad \text{(D)} \ \frac{4!}{2^2} \qquad \text{(E)} \ 4!$
or
$\text{(A)} \ 2 \qquad \text{(B)} \ 8 \qquad \text{(C)} \ 4 \qquad \text{(D)} \ 6 \qquad \text{(E)} \ 24$

I came up with six possible ways for 2 socks/shoes/feet, so the answer would be $\boxed{\text{D}}$.[/hide]

mna851 wrote:Elemennop wrote:[hide]The given problem is equivalent to the number of distinct permutations of aabbccddeeffgghh, which is . D.[/hide]

How does this account for the fact that a sock must go on before a shoe?

Each letter corresponds to one of the spider's feet.  The first time a letter appears, the spider puts a sock on the corresponding foot.  The second time a letter appears, the spider puts a shoe on the corresponding foot.

this is a case of complementary counting where we count when the shoe goes on prior to the sock.  If you want a nice explanations see the introduction to probability by david patrick

hello, why couldn't 8! work.. .?

if the sock must be put on before the shoe, then couldn't we count a sock and a shoe as one unit? then 8!?

Because you can put on the sock for foot 1, then the sock for foot [b]2[/b], etc... You don't necessarily have to put on the sock and shoe for foot x consecutively.

[quote="Sayan"][quote="MSTang"]Why doesn't my solution work:

[hide]
First the spider can put on his eight socks in some order, giving $8!$ ways. Then the spider can put on his eight shoes, giving $8!$ again. Thus the answer is $(8!)^2.$
[/hide][/quote]
It is not necessary that the spider has to put all the socks at first, then shoes. It may put one sock then one shoe in 1st leg, then...[/quote]

To continue with this line of thought:[hide]
There are $8!$ ways to put in the socks: $s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8$.
Then we will put in the shoes.
There is only 1 slot for $S_8$, so the order becomes $s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8,S_8$,
so there are 3 slots for $S_7$,  and then there will be 5 slots for $S_6$ etc.
So it is $8!*(1*3*5*...*15)$, which is the same answer.[/hide]


induction
number theory
prime numbers
number theory solved

Let $P$ be the set of prime numbers. Consider a subset $M$ of $P$ with at least three elements. We assume that, for each non empty and finite subset $A$ of $M$, with $A \neq M$, the prime divisors of the integer $( \prod_{p \in A} ) - 1$ belong to $M$.
Prove that $M = P$.

yey, my problem strikes again :P:P this may be a little unfair, as this has been posted on the forum also (I know that I posted it :), but also can be found in the RMC booklet last of last year).

check out this topic http://www.mathlinks.ro/viewtopic.php?t=3886&highlight=rom%2A+tst+2003

A nice problem has to be shared as often as possible :D

As I said in another topic, I didn't take part of the selection of the problems. Otherwise I would eliminate it because of mathlinks and that a similar one (without the restriction that $A \neq M$ ) has been proposed and solved (by me!!!) on the forum of the french candidates.....When I saw this problem on the exam paper monday (it was for the thusday) I told our team leader Claude Deschamps about it (he turns into green) but it was too late because the exams is not centered at one place but is on different towns in France and we have to use people who are absolutely not involved into olympiads.... Fortunately, none of the candidates seems to have remind it.

Pierre.

my initial problem was without the restriction $A\neq M$, but I decided to make it a little harder for the TST :P

I think a very interesting problem arises if instead of the product -1 we consider the product+1. It seems to be true too... but is probably harder.

psykyk

well actually, that question was the first question. It derived from Euclid's proof of the existance of an infinity of primes. :P
indeed it is harder.

hi guys i m  new member  :blush: , i m from morocco , i already participate in IMO 01 and IMO 02 ,this is what i did about the problem ( just excuse my mathematical english  ;) )

i think it's evident to say that M is infinite!
so bye induction if p1 , p2 ,...,pn are the n first prime numbers and if they belongs to M.
let p be the next prime as we know M is infinite so there is at least a class of equivalence modulo p which contains an infinity of primes from M, let's take p-1 prime from this class ,this subset of M verify (by fermat's theoreme n^(p-1) congru 1 (mod p))the condition so p is in M.
and so M eats every prime
sorry i know u did th problem but i just wanna participate :) by the way valentin i remember u :)[/tex][/i]

[quote="pbornsztein"]You are welcome  :)

In another hand, I think that proving the set is infinite is the hardest part of the problem (you would loose at least 4 points for that  :D , Claude was pityless).

Pierre.[/quote]I was too at the TST marking in Romania ... :D:D

i will check my papers guys
sorry!
it seems that i forgot the A  <> M

lets [tex]p_1,....,p_n[/tex] be the primes in M, with [tex]p_1<...<p_n[/tex]
[tex]A={p_1,p_2,....,p_n-1}[/tex]
the product X(A) of the elements of A : X(A)-1 is divisibl by[tex] p_n[/tex]
so let r be the exposant
[tex]X(A)=1+{p_n}^{r}[/tex]
or [tex]X(A)=(1+p_1^{x}p_n^{y})p_1[/tex]
y couldn't be 1 if not  p_1:equiv: 1(mod p_n) wich is absurde
so
[tex]X(A) :equiv: 1(mod p_1)[/tex]
now
[tex]A={p_2,p_3,....,p_n}[/tex]
[tex]p_n :equiv: 1(mod p_1)[/tex]
so [tex]p_n :equiv: 1(modX(A))[/tex]
absurde
so the M is finite
[/tex]

sorry

[tex]
frac{X(A)}{p_1}[/tex] :equiv: [tex]1(mod p_1)[/tex]
sorry !!


Michela wants to go from her house to Angela's house, but he needs to stop at the market on the way. She may only travel to the right and down. What is the number of distinct paths that Michela can take?

im thinking that there should be a picture on that prob...

This is the picture with Michela's house in the top left and Angela's house at the bottom right. I'm just confused on whether if you go on either of the four corners you reach the market or if the market is only one point on the map.

I think that Michela has to go to the bottom-left corner of the market, so there are $_3C_1=3$ ways to go to the market and $_5C_2=10$ ways to go to Angela's house, so $3 \cdot 10=\boxed {30}$.


Nine cyclists $A_1, A_2, A_3, A_4, A_5, A_6, A_7, A_8, A_9$ are cycling in that order. Suddenly, they want to change positions in a way that the leader changes and no one is behind the same person. In how many ways can they do it?

Can anyone find an easy solution?

There is a classical problem very similar to this one, but it doesn't require to change the leader.

This problem has already been posted on the forum not long ago, but I cant find the link right now. The solution I made uses recursions, but it is not really elegant


Two dice are rolled and the smaller number is subtracted from the larger number.  What is the probability that the difference of the two dicfe is a prime number?


function Support calculus derivative algebra polynomial integration

In class recently, my professor gave a proof that any constant coefficient partial differential equation has a weak solution on a bounded subset of $R^n$. That is, if
$|\alpha| = \alpha_1 + \alpha_2 + ... + \alpha_n$
and
$L = \sum_{|\alpha|<k}\frac{\partial^{\alpha_1}}{\partial x_1}\frac{\partial^{\alpha_2}}{\partial x_2}...\frac{\partial^{\alpha_n}}{\partial x_n}$
then for any bounded $\Omega \subset R^d$ and $f \in L^2(\Omega)$, there exists some $u \in L^2(\Omega)$ that is a solution to the PDE $Lu = f$ in the weak sense. In fact, there is a bounded operator $K$ such that $LKf = f$ in the weak sense for any $f$.

Now, I'm going to outline the proof and point out what I don't understand and why, and hopefully someone can help me.

$\textbf{Lemma: }$ $\exists c \in R$ such that $\varphi \in C^\infty_0(\Omega) \Rightarrow \|\varphi\|_{L^2(\Omega)} \le c\|L^*\varphi\|_{L^2(\Omega)}$.

That is, for any infinitely differentiable function of compact support, the norm of the image of the function under the adjoint of $L$ is bounded below by a constant multiple of the norm of the original function, and this constant depends only on the space $\Omega$.

Thing I Don't Understand #1: Why is this the most difficult part of the theorem? (We'll get into more detail with this later when I return to prove the lemma.)

Now, let's assume the lemma for now. It seems that part of the purpose of this lemma is to demonstrate that $L^*$ is one-to-one, and therefore $L$ is onto. However, I have no idea why it is important that we know this. That's Thing I Don't Understand #2.

So we consider the pre-Hilbert space $H_0$ which is the space of all functions that are $C^\infty_0(\Omega)$, and let $H$ be the closure of that space. Take the norm to be $\|f\|_0 = \|L^*f\|_{L^2(\Omega)}$ (notice that $L^*: H \rightarrow L^2(\Omega)$.

So we consider the linear functional $l: \varphi \rightarrow (\varphi, f)$ for some fixed $f$ and $\varphi \in H_0$ (the usual $L^2$ inner product, I believe). Then

$|(\varphi, f)| \le \|\phi\|_{L^2(\Omega)}\|f\|_{L^2(\Omega)} \le c\|L^*\varphi\|_{L^2(\Omega)}\|f\|_{L^2(\Omega)} = c\|\varphi\|_0\|f\|_{L^2(\Omega)}$.

I don't get the point of this, though I can see why it is true (Cauchy-Schwartz and the Lemma). I also don't get what follows, though I do know the Riesz representation theorem. The claim is that there exists some $U \in H$ such that $l(\varphi) = (L^*\varphi, L^*U)$.

Then we pick $u = L^*U$, and thus $(\varphi, f) = (L^*\varphi, u)$, so $u$ is the weak solution we wanted.

Now, we also need to prove that lemma. Observe that if $(u, L^*\varphi) = (f, \varphi)$ for all $\varphi \in C^\infty_0(\Omega)$, then we can use the Plancherel identity to see that $(\widehat{u}, \widehat{L^*\varphi}) = (\widehat{f}, \widehat{\varphi})$. But derivatives get turned into polynomials, so what we'd like to see is that $\|\widehat{\varphi}\| \le c\|P\widehat{\varphi}\|$ where $P$ is the polynomial corresponding to $L^*$. (Stein calls it the characteristic polynomial; is this really the characteristic polynomial of that linear operator, by the standard lin alg definition?)

Anyway, we now have two sub-lemmas.

Lemma 1a: suppose $\Omega = (-M, M)$ (a subset of the real line) and $g \in L^2(R)$ is supported on $[-M, M]$. Then
$\widehat{g}(\xi) = \int_{-M}^M g(x) e^{-2\pi i\xi x}dx$
can be extended to an analytic function on the complex plane, and furthermore
$\int |\widehat{g}(\xi + i\eta)|^2d\xi \le e^{4\pi M|\eta|}\|g\|^2_{L^2}$.

Lemma 1b: If $F$ is holomorphic on the complex plane, then for any polynomial $Q(z) = z^m + a_{m-1}z^{m-1} + ... + a_1z + a_0$, we have

$|F(0)|^2 \le \frac{1}{2\pi}\int_0^{2\pi}|Q(e^{i\theta})F(e^{i\theta})|^2d\theta$.

If we take $Q = P$, $F(z) = \widehat{g}(\xi + i\eta)$, $\eta = \sin(\phi)$, shift $\xi$ by $\cos(\phi)$, and finally apply Lemma 1b to the result of Lemma 1a, then we have the result of the original Lemma 1.

Now, there was a lot of information and very little proof near the end there. I'm not even certain everything is right as I don't have any intuition for functions on the complex numbers, so I can't check this very well. Lemma 1a seems reasonable to me, but I have no idea about the reason for 1b, except that the professor was saying some vague thing about the polynomial not causing any harm when $|z| = 1$ and this is just like the much more basic averaging result about holomorphic functions.

So, I'm not looking for a full explanation of this theorem, because it is pretty long and hardcore, but if there's any particular part of my confusion that you think you might be able to address, that would be great. Thanks!

You probably figured this out by now, but here it is anyway:

Thing #1: Lemma is the hardest part because it is Calculus. The rest of the proof is mere functional analysis.  :lol:  The stuff about completion expresses the fact that although Lemma applies to $C^{\infty}$ functions, it only involves the $L^{2}$ norms of the function and its derivatives of certain orders. This makes it possible to define an appropriate Hilbert space (a Sobolev space, actually), in which abstract functional nonsense can be used. Of course, you must know that the linear functional is bounded before you apply the Riesz representation.

Thing #2: you want to know that $L$ is onto, because that's what the theorem says...

Thing #3: the characteristic polynomial of a differential operator is not the same thing as the characteristic polynomial of a matrix. Just a different kind of game that goes by the same name.


What is the reason that certain materials have different differences in energy between the conduction band and the valence band?  I understand that for metals it is the relative attraction between the valence electrons and the nucleus, and since the attraction is quite low there is essentially no energy difference between the valence band and the conduction band (this allows delocalized electrons).  But for semi conductors, why would the gap for one semiconductor be greater/less than another?

This might help:

http://en.wikipedia.org/wiki/Wide_bandgap_semiconductors#Motivation_Driving_Utilization_in_Devices


This is my first year going to nats, how hard is it? how intense it the competition?
could u please help me, im both exxcited and nervous......i heard its fun...oh yeah how does the room system work....do u stay in like a hotel with ur team or what?

thanks in advance
ReseesPieces

Yes it's very intense, but actually, it seemed to me as the competition wasn't really the major part of Nats.

You basically get roomed with another competitor, although it doesn't have to be your team.
The best part is definitely hanging out with other people. You get to meet amazing people who share common interests. Also, it's pretty cool how this year is in Disney World.

I remember only spending about a couple hours actually worrying about the competition. The rest was much more fun.

dude... nats is soooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo fun. you're going to disney. lucky. You're probably going to stay with one of your team, or just your parents or family. And is it exciting? You betcha.  :wink:

EDIT: Crap... someone posted before me.

As for difficulty, the step from states to nats is much larger then from chapter to states (in my opinion) You will probably want to look at some problems but just be happy that you are going. The problems arent actually too hard (well some are) but they just take a lot of time.

This is my first time going to nats also, so i'm quite curious.
How much free time do we have in our rooms and what do we usually take there for fun?
Do some ppl take things like iPods, laptops, etc?

I suppose you could spend all your time besides the competition/meals/banquet/other stuff in your room, but that is bad.

I think you can bring whatever you want. Just make sure not to disturb other people.

Haha me and this person from Michigan got talked to by security because *some* person from Michigan locked his room's door, which locked us outside...

My first Nats trip was last year, and it was amazing. Most AoPSers are not surrounded by those at their own level intellectually, and meeting people from all over the nation (and world!) is very exciting. One way you get to know other people is pin trading (People from every state are given 57 pins, you go around and trade pins with others and try to collect as many different ones as possible, which is very fun). Yes, the difficulty is great, but you made Nats, so you have proved you can do well here (dont worry if you dont, the experience itself is rewarding enough. Thats not to say don't try, by all means try your hardest).

Everyone stays in a hotel where the competition is held (I hear last years compatred to other years was bad, but I didn't mind, I wasn't raised in 5-stars).You room with people of your own gender, usually from the same state as you. There is a box on the forms they give you if you make nationals thats asks who you would prefer to room with. You are not allowed to room with your parents if they go with you. Don't be suprised if you room with someone not on your team, remember this is not only a great mathematical experience, but a great social one as well. And if you have a talkative roomie (like me :) ), be prepared to be a) annoyed or b)talking with them!

Teams arrive Thursday, when you have plenty of time to relax/ practice. Friday is test day, Saturday is Sightseeing and awards, Sunday is go home day (Iff they keep it like last year)!

People often bring iPods, laptops too. My team brought a Wii last year (Midnight Brawlfest!) but the TV didnt support it. :P

 :!: Keep in mind how lucky you are to be going, and remember it for the rest of your life :!:
I mean, just Google Disney Lake Swan resort!

Last year was my 3rd and last year going to nats, my 2 cents:
I would say that in general, the experience is about meeting people and having fun, and less about the actual competition.  In 8th grade, I went in with some goals and expectations (which I unfortunately didn't meet), but the previous two years I basically just went and had fun.  The amount of preparation you do depends on the team, with some teams meeting 30+ times (they were all from the same school), to a few (our state team) to none at all.

Random tip for the pins (if you want a complete set):
Most trading happens thursday night, some on friday (test day), and little after that.  I had most of the pins by Fri night.  Also, there are always some states that bring 0 or very few pins.  A pin economy basically springs up for those 4 days, trading can get intense :D

Each person treats the actual mathematics part of it differently, with people going for the 2nd or 3rd time having more expectations I think.  Most people know they don't have a shot of winning, so they're there to have fun, but some are very focused.  I distinctly remember Justin Ahmann saying that he didn't trade any pins prior to the rounds.

The rooming situation seems to have already been explained.

I apologize for the disorganization of this post, and, if you have any other questions, PM me.

[quote="echen"]As for difficulty, the step from states to nats is much larger then from chapter to states (in my opinion) [/quote]

Actually, I believe that the opposite of this is true, as you actually need a step up in "cleverness" from chapter to states, but from states to nationals, the only change is that the problem writers artificially increase the amount of time needed to solve the problems by making calculations and that sort of thing more tedious.

(whoa, I made a serious post in the mathcounts forum. also some random person says yay.)

regarding difficutly levvel what should we average on the sprint rounds...not saying i wont strive for perfect(although that wont happen) but what is an okishly good score like on the 1990-2008 tests....the ones before were basic computation type things ....

I think for more recent tests, around $ 40$ is the general consensus for a decent score, but I haven't seen as much discussion of older tests.

keeping in mind that the old tests were much easier, i would say yes, a "decent score" would have been higher. :w00tb:

A 40 is a definite spot in the top 10. I'm pretty sure it's been that way for at least the last 5 years.

2007 Data from Nationals (the only one I have of the 3, oddly)
To make Countdown-36, upper quartile-30, Median 25, lower quartile-19
(I think this is right...)

This year will be my second year going to Nats, and it is just AMAZING. Enjoy every moment there. Study hard before hand, and just relax once you are there. It is very fun to meet so many people from all over the country and world, and awesome to watch the countdown and masters rounds (of course only if you aren't in them can you watch). They plan other activities too, and there's also time for team touring. The hotels, atleast last year and this year, are top of the line. As far as rooms, they are for two people each. You will probably be paired with someone from another state, as long as you don't request to be with anyone in particular. Good Luck there! Maybe I'll see you without knowing it!

How do they pair roommates together? Do they just draw names from a hat?

Well if you have a preference, they usually try to accommodate you. If not, I think it's random.

Ugh.  Please stop talking about how cool nats is :(

It makes me sad that I won't be going :(

(probably)

lol, Darryl Wu and Bobby Shen room buddies.  Lets see who gets the black eye first...

If any one of you makes CD, I'll be watching you either winnng or phailing.

BTW, will that weird announcer dude who calls the state names be there again?  He was uber-annoying.

[quote="AIME15"]Ugh. Please stop talking about how cool nats is Sad

It makes me sad that I won't be going Sad

(probably)[/quote]

1) You're not sure as to if you made nats or not...
2) Instead of making many other people stop discussing something terribly relavent, possibly don't look at that topic? Call me crazy, but I think that's a little selfish.

No!!!! Here is the site to Nats: http://www.swandolphin.com/home.html And I'm not going!!!!! NO NO NO NO!! Please don't look at the site if you're not going. If you are, please don't brag. It makes me want to cry. I don't know why I posted it, but don't look if you didn't make it!! Next year will probably be at Yellowstone National Park.... Grumble... I heard that Disney is 895 per night!! Yellowstone.. grumble.... 50 bucks per night.. No TV...  :mad:

[quote="tinytim"][quote]BTW, will that weird announcer dude who calls the state names be there again? He was uber-annoying[/quote]

There actually isn't a live "announcer" announcing the state namesat the beginning of the Countdown Round. Mathcounts uses a recording that was probably made 10 years ago(?).  :wink:[/quote]

So, if I bribe some state to come in late, the whole system can be messed up?

*goes to Bank of America and picks up ATM machine.  Goes home and gets the cash inside.  Goes to his friends who are in the KS nats team and bribes them* :D

ughh hated the dude who was on the stage conducting the countdown round....i was just like ewww

anyway, my dad was going to come....but was wonderin how many parents on average actually do come to the competition.............

Addressing the parents:
I have no exact figures, but I assure you lots of parents will be there.  I would wager at least each team has one parent along, if not more.  And, if he goes, he should have plenty to do, talking with other parents, watching masters round, and I assume this year the seminar for parents during the actual competition will be given (by Mr. R?).  If any parents go, I recommend they attend the awards banquet and the Friday night special event, the meals and other stuff seems sorta like a waste of money...

Yes, there are quite a few parents.
I pretty much completely agree with Quickster. They should go to most of the events like the feature event, masters round, award ceremony, cd round, and during the written competition, the "After Mathcounts" Seminar talk by Richard Rusczyk. The extra meals cost a lot, and they probably won't be much different from a normal restaurant meal. They would have to pay their own way, of course.

oh, Mr. R will be at nats, nice...

will the nats contestants be able to meet him?

If it's like the last 3 years, AoPS should have a table there thursday afternoon and evening, with pins and t-shirts (to trade for your pins), books, class stuff, etc.  Lots of people are advertising there, the companies, some summer camps, all sorts of people

[quote]So, if I bribe some state to come in late, the whole system can be messed up?

*goes to Bank of America and picks up ATM machine. Goes home and gets the cash inside. Goes to his friends who are in the KS nats team and bribes them* [/quote]

007math, You should get the states to come out in reverse alphabetical order. that would be really funny.

And I totally agree with you about the annoying cd round guy, Resees. I don't get why he asked all those annoying questions. It would be funny if all the people who made the cd round put down exactly the same hobbies.

:D that would be somethin....

another question; what do u guys average on the sprint rounds like from 2000-2008

Eh, most people here are probably better than me, but I hit 27+ on a good day.  I need to learn arithmetic.

my average on state sprints is 22-23   :(

I average about 24-29 for nats targets and sprints combined  :( . I know, kind of sad. Last year- got a 20 at nats :( . I know, very sad.

As long as you have fun and try your best......cheesy

Well, it's good to have fun, BUT NOT TOO MUCH... If you slack like I did (and failed) then you will die. (echo...) I failed because I thought I was going to just go to Nats since I was a beast, but apparently not. Read my sig.   :(

[quote="tinytim"]Be able to consistently get 7s or perfects on targets before you train speed for the sprint round.[/quote]

That's easier than a 28 on a Sprint :)

In my opinion Target questions are easier than the last 8 on Sprint.  They're more like

First pair: somewehre from 10-15 sprint
Second: 12-18
Third: 15-20
Last pair: 20-30 (sometimes extremely easy sometimes extremely hard)


floor function
logarithms
calculus
integration
calculus computations

Hey,

[b]1. The problem statement, all variables and given/known data.[/b]
Find the positive integer $ n$ for which,
$ {{\lfloor}{{\log_{2}}1}{\rfloor} + {\lfloor}{{\log_{2}}2}{\rfloor} + {\lfloor}{{\log_{2}}3}{\rfloor} + \dots + {\lfloor}{{\log_{2}}n}{\rfloor}} = {S}{,}{\,}{\,}{\text{where}}{\,}{\,}{S \in \mathbb{M}}$

Where $ {\lfloor}{x}{\rfloor}$ denotes the greatest integer less than or equal to $ x$. (For example, $ {\lfloor}{\pi}{\rfloor} = {3}$.)

[b]2. Relevant equations.[/b]
$ {\mathbb{M} = \{{0},{1},{2},{\dots},\}}$

[b]3. The attempt at a solution.[/b]
[hide="My Attempt at a Solution."]
For the given sum, $ {S}{,}{\,}{\,}{\text{where}}{\,}{\,}{S \in \mathbb{M}}$,
$ {{\lfloor}{{\log_{2}}1}{\rfloor} + {\lfloor}{{\log_{2}}2}{\rfloor} + {\lfloor}{{\log_{2}}3}{\rfloor} + \dots + {\lfloor}{{\log_{2}}n}{\rfloor}} = {S}$

Which can be rewritten as,
$ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {S}$

Then again rewritten as,
${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\sum_{j = 0}^{m}}{{j}{{2}^{j}}} + {C}}$

Where,
$ {m \in \mathbb{M}}{\,}{\,}{\text{and}}{\,}{\,}{C \in \mathbb{M}}$

Note that we want $ {C}$ to be postive since the original summation has no negative terms.
In order to find $ {n}$ we want to get as close as possible or equal to $ {S}$ by collecting terms of powers of two without going over.
The reason we do not want to go over is that would result in the constant $ {C}$ being negative and therefore inaccurately
representing the original summation.
So the problem can now be rewritten as,
${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}} + {C}}$

Note from here the constant $ {C}$ can be reexpressed as,
$ {C} = {k(m + 1)}$

Where,
$ {k \in \mathbb{M}}$
Note that here $ {k}$ represents the number of terms of $ {m + 1}$ needed to add to the summation, $ {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}}$ to reach the sum, $ {S}$.
So now we have,
${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}} + {{(}{k(m + 1)}{)}}}$
${ {\sum_{i = 1}^{n}}{{\lfloor}{\log}_{2}{i}{\rfloor}} = {\max{(}{\sum_{j = 0}^{m}}{{j}{{2}^{j}}}{)}} + {{k(m + 1)}}}$

From here it seems like the next step is to evaluate the summation,
$ {\sum_{j = 0}^{m}}{{j}{{2}^{j}}}$

However even if I evaluate the expression in terms of $ {m}$, I still then need to figure out some way of choosing $ {m}$ such that it will maximize,
$ {\sum_{j = 0}^{m}}{{j}{{2}^{j}}}$
and then still find $ {k}$ in order to find $ {n}$.

Here is where I think some calculus might be useful, can we somehow convert the summation to an integral and use methods in calculus to evaluate that integral and then maximize it? I'm not too familiar with the techniques for converting summations to integrals and visa versa so, how would I proceed from this step?
[/hide]
Thanks,

-[u][b][url=http://www.artofproblemsolving.com/Forum/profile.php?mode=viewprofile&u=33715]APSStudent[/url][/b][/u]

looking at $ S(n)\equal{} \sum_{k\equal{}1}^n \lfloor{\log_2 k \rfloor}$

we get $ \lfloor{\log_2 (2^k\plus{}c) \rfloor}\equal{}k$ for each $ c\equal{}0,1,..., 2^k\minus{}1$

so letting $ n'\equal{}\lfloor{\log_2 n \rfloor}$, and $ c'\equal{}n\minus{}2^{n'}$ we get

$ S(n)\equal{}\sum_{k\equal{}0}^{n'\minus{}1} k2^k\plus{}n'(c'\plus{}1)$

$ \sum_{k\equal{}0}^m k2^k \equal{} \sum_{k\equal{}1}^m k2^k \equal{} \sum_{k\equal{}1}^m \sum_{j\equal{}k}^m 2^j \equal{} \sum_{k\equal{}1}^m (2^{m\plus{}1}\minus{}2^k)\equal{}2\plus{}(m\minus{}1)2^{m\plus{}1}$

so you first just find the right m such that $ (m\minus{}1)2^{m\plus{}1}\le S\minus{}2 < m2^{m\plus{}2}$

and then $ c\equal{}\frac{S\minus{}2\minus{}(m\minus{}1)2^{m\plus{}1}}{m}\minus{}1$ and $ n\equal{}2^m\plus{}c$ is your solution..
im not sure you can solve for m explicitly..?


geometry
3D geometry
analytic geometry
graphing lines
slope

respond in spoiler extra pts for generalizing. due date is sunday sept. 28, 6 PM est
1. Find the volume of a cube whose total surface area is equal to the sum of the lengths of all its edges.

2. Find the next two terms of this sequence: 245, 125, 65, 35, ... extra pts to anybody who can tell me why this is a bad question.

3. Find the equation of a line parallel to 3x-5y=15 that intersects the line y=x at x=3.

4. Solve for x in terms of c: (x+c)/(x+1)=(c+1)

5. Chris's monthly allowance is $10 in Jan., $20 in Feb., and increases by $10 each month. Pat's allowance starts at 10 cents and doubles each month. At which month will Pat be able to hire agents that can hunt down Chris? (At which month will Pat's allowance start to increase Chris's)

[hide]

1) 6s^2=12s

    s=sqrt(2)

2) 20, 12.5

    It breaks the pattern of integers in the 2nd value we had to find

3) y=3/5*x + 6/5

4) x=-1/c

5) 2^x=100x

    x approx = 10 weeks

[/hide]

Here are my answers:

[hide]

1. 12x = 6(x^2)

2x=x*x

x=2

Volume = 8

2. 245-120=125

125-60=65

65-30=35

The steps go down by a factor (dividend?) of 2 each time.

35-15=20.

3. The slope of the first line is 3/5. The point from the second is (3, 3) In point slope, y-2=3/5(x-2).

4. (x+c)/(x+1)=(c+1)

x+c = xc+x+c+1

0=xc+1

xc=-1

x=-1/c

5. On the 11th month, Pat will get 110. So, next month (December), Pat will get 120. (Just in time for Christmas!)[/hide]


If there are $29$ people to feed with one pizza and each person is allowed exactly one piece (not exactly the same size), how many cuts must be made?

*the answer is not $29$*

*work must be shown*

:maybe:

[hide]Find a pattern. The first cut will slice the pizza into 2 pieces. The second cut put it into 4 pieces. The third one will put it into 7. The pattern is triangular numbers starting with #2. Eventually you get to the 7th number wich is 29 so there are 7 cuts.[/hide]

but wouldnt the third cut make the pizza into $6$ pieces?

No, because when you went from the first cut to the second you added 2. So then we will have to add 3 which is 7, and so on...

The cuts don't have to go through the center so you just want the number of intersections to be maximized.


If $ 0 < b \le a$ . Show that  $ a\plus{}b\minus{}2\sqrt{ab} \ge \frac{(a\minus{}b)^2}{2(a\plus{}b)}$

[quote="Nebraska boy"]If $ 0 < b \le a$ . Show that  $ a \plus{} b \minus{} 2\sqrt {ab} \ge \frac {(a \minus{} b)^2}{2(a \plus{} b)}$[/quote]

Ineq
$ <\equal{}>2(a\plus{}b) \ge (\sqrt{a}\plus{}\sqrt{b})^2$


if $2x^{2}-5xy+7x+2y^{2}+y-15=(2x+ay+b)(cx+dy+e)$, where a,b,c,d,e are integers find the value of a+b+c+d+e.

is there a quick way to do this?

[quote="iamagenius"][quote="Altheman"]hint: let x=0[/quote]
if x=0, then (ay+b)(dy+e)=(2y-5)(y+3)
if y=0 then (2x+b)(cx+e)=(2x+3)(x-5)

where do i go from here?[/quote]

since the answer has $2x^{2}$ in it, the other term of x has to have a coefficient of 1.


(A.Zaslavsky) Given three points $ C_0$, $ C_1$, $ C_2$ on the line $ l$. Find the locus of incenters of triangles $ ABC$ such that points $ A$, $ B$ lie on $ l$ and the feet of the median, the bisector and the altitude from $ C$ coincide with $ C_0$, $ C_1$, $ C_2$.

I'll restate the notation of the problem differently:

[quote](A.Zaslavsky) Given three points $ M,$ $ V,$ $ D$ on the line $ \ell.$ Find the locus of incenters of triangles $ ABC$ such that points $ A,$ $ B$ lie on $ \ell$ and the feet of the median, the bisector and the altitude from $ C$ coincide with $ M,$ $ V,$ $ D.$[/quote]
Let $ I,I_c$ be the incenter and C-excenter of $ \triangle ABC.$ $X,Y$ are  the tangency points of $ (I),(I_c)$ with $ \ell \equiv AB.$ Since the points $ C,V,I,I_c$ are harmonically separeted, so are their orthogonal projections $ D,V,X,Y$ onto $ \ell.$ $ M$ is also midpoint of segment $ XY,$ hence by Newton's theorem $ MX^2 \equal{} MY^2 \equal{} MV \cdot MD \equal{} \text{const}$ $ \Longrightarrow$ $ X$ is a fixed point between $ D,V.$ Therefore the locus of $ I$ is the perpendicular line $ \tau$ to $ \ell$ through $ X.$


Fortunately for me, Latex was already on my machine before I got it (my brother).  I want to get all my friends to use it because of its superior efficiency, but I really don't know how to get it, especially for a PC (I'm an Apple user).  I have searched the web, but it has been largely futile.  Can anyone tell me where I should send people online to get it (both Mac and PC)?

For PC, http://www.miktex.org. Thats all you need, as long as you don't mind writing them up in notepad and compiling in DOS.

Plus download the nice free German made Texnicenter. It gives you a nice GUI (don't know how TripleM lives with dos screens). Plus you should download AFPL Ghostscript 8 and GSView 4. To view those attractive postsrcipt files.
[url]http://www.texniccenter.org/front_content.php?idcat=50[/url]

Since I'm DOS illiterate and too lazy to download Texnicenter, i just drag the icon of my notepad document and drop it onto an icon called "Latex", and then to view my files I use YAP (yet another previewer), which came with my Miktex download. It works rather nicely.

(If you're lazy like me, this is the way to go!)

Yea but umm...what's the file path for the Latex icon?  I can't find it on mine.

It should be in C:\texmf\miktex\bin\
Though you can go straight to pdf format by using one of the other ones in there, I forget its name.

[quote="nr1337"]Is anyone else's computer like this:

In order for me to compile [tex]\LaTeX[/tex] on my computer, I have to be in C:\texmf\miktex\bin\ or else my computer will say that latex does not exist.[/quote]

What do you mean? Thats where the program that compiles it is, so the computer has to know where that is. Of course you don't need to store the files that you are making in there, as long as you give it the correct address.

If you mean that in order to execute LaTeX on your document you have to be in that folder, then your problem is that C:\texmf\miktex\bin\ is not in your path.

What I mean is that I have to save my documents in C:\texmf\miktex\bin or else they won't compile.

edit: never mind. I think I got it.

[quote="Anonymous"][tex]\LaTeX[/tex] is a typesetting program that lets you do fun stuff like this:

[tex]
\displaystyle{\int_2^5 {\arccos \frac{1}{\sqrt[3]{x}}}\, dx }

\displaystyle{e=\sum_{k=0}^\infty \frac{1}{k!}}
[/tex][/quote]

I didn't know that Guests could post now.

They can't. Well, they could, only in this forum, for a few hours. Then it was fixed :)

I didn't notice I wasn't logged in, so I accidentaly posted in the "Guest" account without knowing it.

Having problems making my equations look bigger.  The \displaystyle{} you use here, is that equivalent to displaymath{}?  This is the code that i'm working with, and it doesn't seem that the displaymath{} is making things look any bigger...

\begin{displaymath}
\begin{flushleft}
$\frac{N}{2}$=$2^{a-1}$\cdot$3^b$\cdot$5^c$\cdot$11^d$    (i) \newline
\\*
$\frac{N}{3}$=$2^a$\cdot$3^{b-1}$\cdot$5^c$\cdot$11^d$    (ii)\newline
\\*
$\frac{N}{5}$=$2^a$\cdot$3^b$\cdot$5^{c-1}$\cdot$11^d$    (iii) \newline
\\*
$\frac{N}{11}$=$2^a$\cdot$3^b$\cdot$5^c$\cdot$11^{d-1}$   (iv)
\end{flushleft}
\end{displaymath}

Is there something wrong with the code, something I need to add, or...?

As far as I know, the main difference that displaymath does is that (in normal latex, not here I don't think) it puts your formulas etc on a new line, instead of inserting them on the same line. So its not as much "making them look bigger"..

Hm, well is there anything that you do to format to make the equations look bigger, as with the \displaystyle here?  (i'm assuming that \displaystyle only works for the board, just cause i didn't see it in the 'short guide to texing' manual... let me know if i'm wrong).


pigeonhole principle
combinatorics
AMC
AIME
AIME I
recursion
combinatorics solved

A mail carrier delivers mail to the nineteen houses on the east side of Elm Street.  The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day.  How many different patterns of mail delivery are possible?

[hide]If 1 represents a house with mail and 0 represents a house without mail, then the 19 houses will have strings of 10's and 100's, with a possible 1 at the end and/or a 0 or 00 at the beginning.

If $a_k$ represents the number of ways to fill up a $k$ character string with 10's and 100's, then the number is given by:
first house 1, last 0: $a_{19}$; first 1, last 1 or first 01, last 0: $a_{18}$ each; first 01, last 1 or first 00, last 0: $a_{17}$ each;
first 00, last 0: $a_{16}$.
Total: $a_{16}+2a_{17}+2a_{18}+a_{19}$

A recursive formula for $a_k$: Start with $a_1=0$, $a_2=a_3=1$. For $k>3$, the first string can be 10 or 100.
If it is 10, there are $a_{k-2}$ ways. If it is 100, there are $a_{k-3}$ ways.

Then $a_k=a_{k-2}+a_{k-3}$. $a_{16}+2a_{17}+2a_{18}+a_{19}=a_{17}+2a_{18}+2a_{19}=a_{18}+a_{19}+a_{20}=a_{20}+a_{21}=a_{23}$.

After some computation using the recursion, find $a_{23}=\boxed{265}$.[/hide]

[hide]There are actually only five cases needed to be considered:

We know from Pigeonhole that the least number of houses must receive mail is 6, and the most is, by the same logic, 10 is the maximum.

For 6, consider the string x_.
There are six x_ strings lined up in a row, already assuring that the x's, or the houses that received mail, are separated. There are 8 positions to place the 7 "_"s, which indicate a house with no mail. Thus, the number of arrangements is $\binom{8}{7}$.

For 7, the same reasoning applies.
There are seven x_ strings lined up. There are 9 positions for the remaining 5 "_"s, and so the number of arrangements is $\binom{9}{5}$.

For 8, by the same logic, is $\binom{10}{3}$.

For 9, is $\binom{10}{1}$, which differs because the 18 houses already filled up leaves no room for the "extra" space of 2 "_"s designated in the cases where more than 1 house was unfixed.

For 10, there is only one arrangment.

$\binom{8}{7} + \binom{9}{5} + \binom{10}{3} + \binom{10}{1} + 1 = 265$

[/hide]

[hide]
We can define a recursive function $P_x$ for the number of choices at house $x$.
$P_1 = 2$
$P_2 = 3$
$P_3 = 4$
$P_4 = 5$
and in general $P_n = P_{n-2} + P_{n-3}$

because what you can have in $P_n$ is dependent on either 2 houses before(if you have pattern $uu$ or $um$ or 3 houses before $muu$. I designate houses that recieve mail as $m$ and houses that don't as $u$.

so $P_5 = 7$ and $P_6 = 9$ and $P_19 = 351$[/hide]

Hmm... I agree with gauss and agolsme. Here's my solution:

[hide]Clearly, there can only be $6, 7, 8, 9, 10$ houses which the mail deliverer goes to. If we draw out the houses as _, we have:

_ X _ _ X _ _ X _ _ X _ _ X _ X _ X _
a1   a2    a3     a4     a5    a6   a7  a8

where the X's are the houses delivered to.

Denote the distances between houses as above. The above is shown when $7$ houses are present. The number of solutions to the $7$ house case is simply the number of solutions to the equation:

$a_{1}+\cdots+a_{8}= 12,$ where $0 \le a_{1}, a_{8}\le 2, 1\le a_{2}, \cdots, a_{7}\le 2.$

This is the same as:

$a_{1}+\cdots+a_{8}= 6,$ where $0 \le a_{1}, a_{8}\le 2, 0\le a_{2}, \cdots, a_{7}\le 1.$

The number of solutions to this is simply the coefficient of $x^{6}$ in the equation:

$(1+x+x^{2})^{2}(1+x)^{6},$ which is $113,$ after manipulation.

Applying the same logic to the rest of the cases, we have our answer as:

$7+113+183+47+1 = 351.$[/hide]

[quote="agolsme"][hide]
We can define a recursive function $ P_x$ for the number of choices at house $ x$.
$ P_1 \equal{} 2$
$ P_2 \equal{} 3$
$ P_3 \equal{} 4$
$ P_4 \equal{} 5$
and in general $ P_n \equal{} P_{n \minus{} 2} \plus{} P_{n \minus{} 3}$

because what you can have in $ P_n$ is dependent on either 2 houses before(if you have pattern $ uu$ or $ um$ or 3 houses before $ muu$. I designate houses that recieve mail as $ m$ and houses that don't as $ u$.

so $ P_5 \equal{} 7$ and $ P_6 \equal{} 9$ and $ P_19 \equal{} 351$[/hide][/quote]
Could anyone use different ways to get recursive function $ P_n \equal{} P_{n \minus{} 2} \plus{} P_{n \minus{} 3}$ ?

A problem in this year's Massachusetts Math Olympiad: Level 2 involved this same recursion. The scenario was the same, too, except instead of houses getting mail, it was seats being occupied by students.

To see the problem and solution, [url=http://www.matharchive.org/olympiad/2007-08/200708_olympiad_2s.pdf]click here (PDF)[/url].
- The problem is number (2) on page 4, particularly (2c) and (2e)
- The solution begins on page 5

I am linking this because it contains a detailed discussion of this particular recursion.

Official Solutions

[hide="Solution 1"]
The first condition implies that at most ten houses get mail in one day, while the second condition implies that at least six houses get mail.  If six houses get mail, they must be separated from each other by a total of at least five houses that do not get mail.  The other eight houses that do not get mail must be distributed in the seven spaces on the sides of the six houses that do get mail.  This can done in 7 ways: put two at each end of the street and distribute other four in $ \binom{5}{4} \equal{} 5$ ways, or put one in each of the seven spaces and an extra one at one end of the street or the other. If seven houses get mail, they create eight spaces, six of which must contain at least one house that does not get mail. The remaining six houses that do not get mail can be distributed among these eight spaces in 113 ways; six of the eight spaces can be placed at each end of the street and two intermediate spaces be selected in $ \binom{6}{2} \equal{} 15$ ways; and two houses can be placed at one end of the street and four spaces selected for a single house in $ 2 \binom{7}{4} \equal{} 70$ ways. Similar reasoning shows that there are $ \binom{9}{4} \plus{} 1 \plus{} 2 \binom{8}{2} \equal{} 183$ patterns when eight houses that get mail, and $ 2 \plus{} \binom{10}{2} \equal{} 47$ patterns when nine houses get mail. When ten houses get mail, there is only one pattern, and thus, the total number of patterns is 7+113+183+47+1 = 351. [/hide]

[hide="Solution 2"]
Consider $ n$-digit strings of zeros and ones, which represent no mail and mail, respectively. Such a sequence is called [i]acceptable[/i] if it contains no occurrence of 11 or 000. Let $ f_n$ be the number of acceptable $ n$-digit strings, let $ a_n$ be the number of acceptable $ n$-digit strings in which 00 follows the leftmost 1, and let $ b_n$ be the number of acceptable $ n$-digit strings in which 01 follows the leftmost 1. Notice that $ f_n \equal{} a_n \plus{} b_n$ for $ n \geq 5.$ Deleting the leftmost occurrence of 100 shows that $ a_n \equal{} f_{n\minus{}3},$ and deleting 10 from the leftmost occurrence of 101 shows that $ b_n \equal{} f_{n\minus{}2}$. It follows that $ f_n \equal{} f_{n\minus{}2} \plus{} f_{n\minus{}3}$ for $ n \geq 5$. It is straightforward to verify the values $ f_1 \equal{} 2, f_2 \equal{} 3, f_3 \equal{} 4,$ and $ f_4 \equal{} 7$. Then the recursion can be used to find that $ f_{19} \equal{} 351$. [/hide]

 :)

Call a sequence of $ A$s and $ B$s good if and only if
i) there are no more than two $ B$s in a row
ii) There are no $ A$s in a row

Let $ a_n$ denote the number of good sequences that have $ A$'s on both ends that have a length of $ n$. The rightmost entry of $ a_n$ is $ A$. Then it is followed by either two $ B$'s or one $ B$. If we remove those, have an $ A$ on the right, so $ a_n\equal{}a_{n\minus{}2}\plus{}a_{n\minus{}3}$. Note that $ a_1\equal{}1$, $ a_2\equal{}0$, $ a_3\equal{}1$.

Now $ a_n$ restrict our problem somewhat. Consider the ends of the sequence. If it is in the same form, put a dash. Otherwise, take the $ B$s
i) -;- so $ a_n$ here.
ii) -;$ B$ so $ 2a_{n\minus{}1}$ here. (the $ B$ can be on either side)
iii) -;$ BB$ so $ 2a_{n\minus{}2}$ here.
iv) $ B$;$ B$ so $ a_{n\minus{}2}$ here.
v) $ B$;$ BB$ so $ 2a_{n\minus{}3}$ here.
iv) $ BB$;$ BB$ so $ a_{n\minus{}4}$ here.

Hence we want \[ s_n\equal{}a_n\plus{}2a_{n\minus{}1}\plus{}3a_{n\minus{}2}\plus{}2a_{n\minus{}3}\plus{}a_{n\minus{}4}\]  Using the recursion for $ a_n$,
$ 1,0,1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65$ are the first $ 19$ terms.

Then our answer is $ (1,2,3,2,1)\cdot (65,49,37,28,21)\equal{}\boxed{351}$.

If someone wouldn't mind clarifying agolsme's reasoning behind his recursion, I would be grateful.
Thanks.

See Silverfalcon's second solution. The trick in the argument is to remove the [b]first[/b] "100" or "10" occurs...This simplifies the casework a lot and leads to a nice solution! I think that agolsme didn't consider all cases, but came up with the correct recursion anyway (either that or his explaination isn't very clear).

I don't know if this recurrence hold true, could someone check.
Let $a_n$ be the number of sequences for which the first house gets mail and let $b_n$ be the number of sequences when the
first house does not get mail. Then we see that:
$a_n+1=b_n$
$b_n+1=a_n-1+a_n$

This was 2001 AIME I question 14.
[hide="Solution"]
Define $M_n$ as the number of arrangements for $n$ houses.
Define $I_n$ the number of arrangements for $n$ houses where the first house got mail.
Define $X_n$ the number of arrangements for $n$ houses where the first house got no mail.
Clearly, $M_n = I_n+X_n$.

Since if the first house got mail, the second house must not have gotten mail, and the $I_n=X_{n-1}$.
$1, (), (), (),...   which-is (I_n)$ is the same as $1, 0, (), (), (),...   which-is (X_{n-1})$.

$M_n = X_n+X_{n-1}$

For any sequence that starts with a $0$, the next $2$ terms must either be $0, 1$ or $1, 0$.

From this, we can deduce $X_n=X_{n-2}+X_{n-3}$:
[hide="Deduction"]
$0, (), (), (),... which-is(X_n)$
This has 2 cases:
$0, 1, 0, (),... which-is(X_{n-2})$       or       $0, 0, 1, 0, (), (), (),... which-is(X_{n-3})$
$X_n=X_{n-2}+X_{n-3}$
[/hide]

Starting from the first $3$ terms $1, 2, 2,...$, we have $1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, ...$.
$M_{19} = X_{19}+X_{18}$
$M_{19} = 200+151=\boxed{351}.$
[/hide]

For more questions like this, you can look at the application of Fibonacci numbers and other recurrences in combinatorics.

[hide="Solution"]For each house, let $A$ denote getting mail and $B$ denote not getting mail. Let $a_n$ denote the number of sequences that end in $A$ and let $b_n$ denote the number of sequences that end in $B$. If a sequence ends with an $A$, then the second-to-last house is a $B$, so we get $$a_n=b_{n-1}.$$ If a sequence ends with a $B$, then the second-to-last house can be an $A$, in which case the third-to-last house is $B$; or the second-to-last house is a $B$, which leaves no restrictions on the third-to-last house. Thus, we have $$b_n=a_{n-2}+a_{n-1},$$ establishing our recurrence.
We can easily derive $a_1=1, a_2=1, b_1=1,$ and $b_2=1$. From here, we can use the recurrences to construct $a_n$ and $b_n$ up to $n=19$. We find that $a_{19}=151$ and $b_{19}=200$, so the total number of patterns of mail delivery is $151+200=\boxed{351}$.[/hide]

[hide=Solution]Like the above solution, denote $a$ as getting mail and $b$ as not getting mail. Obviously $a_n=b_{n-1}$ but $b_n$ is tricky because you could go multiple routes but only $1$ route is amazing. Anyway $b_n=a_{n-2}+b_{n-2}$ and adding up and calling the whole recursion $c_n$ we get $c_n=c_{n-2}+b_{n-1} \implies c_n=c_{n-2}+c_{n-3}$ and this is very easy to work with. Since $c_1=2, c_2=3, c_3=4,$ we can get as our final answer $c_{19}=\boxed{351}$ after crunching the numbers. My motivation was that I hate excess number crunching if it can be avoided and I've seen recursions before that can take many forms so my goal was to find the best form. [/hide]

[quote=Dex_Max][quote=worthawholebean][quote="linj"]Thank you very very much. I am just so bad in this type of questions. Do you know what can I do to improve? Or Do you know how I can get more practice on it?[/quote]
Do more of them. That's how to get better.

Read books too.[/quote]

What kind of books are helpful? Do you have any specific book recommendations?[/quote]

Intermediate Counting and Probability is the best.

Denote $A_n$ the number of ways the mail carrier can deliver mail to $n$ homes such that the last two homes both receive no mail.
Denote $B_n$ the number of ways the mail carrier can deliver mail to $n$ homes such that the last home receives mail, but the second to last home doesn’t receive mail.
Denote $C_n$ the number of ways the mail carrier can deliver mail to $n$ homes such that the last homes doesn’t receive mail, but the second to last home does.

If the last two homes both receive no mail, then the third to last home must receive mail and the fourth to last home must not receive mail. Therefore, $$A_n = B_{n-2}$$
If the last home receives mail, while the second to last home does not, then the third to last home can either receive mail or not receive mail. Therefore,
$$B_n = A_{n-1} + C_{n-1}$$
If the last home does not receive mail, while the second to last home does, then the third to last home must not receive any mail. Therefore,
$$C_n = B_{n-1}$$
Therefore, $$A_n + B_n + C_n = B_n +B_{n-1} + B_{n-2}$$
If we can calculate the intermediate $B$ then we are done! Now, all we need is a recursive formula for $B$!. Note that
$$B_n = A_{n-1} + C_{n-1} \implies B_n = B_{n-3}+B_{n-2}$$
using the recursive formulas we created above. It is not hard to see that $B_1 = 0$, $B_2 = 1$, and $B_3 =2$. Therefore, we can calculate all the intermediate $B$ easily with some computaiton.
$$A_{19} + B_{19}+C_{19} = B_{19} +\cdot B_{18} + B_{17} = \boxed{351}$$

[hide=Basic but Well Explained Recursion Solution]

[b]Motivation: [/b]We see this large bashy counting problem if we approach it incorrectly and we realize that the MAA wouldn't expect anyone to do this (let us forget about AOIME #9). So we start thinking of elegant ways to solve this. States? No. Recursion? Yes! So we consider sequences of length $n$, make a general formula, and apply it for 19.

[b]Basic Observations:[/b] First we will define some mathematically helpful notation. To denote a house getting mail, we put a "$1$" and not getting mail gets a "$0$" in the $n$ digit string of letters for the number of ways to deliver mail to $n$ houses. If no two adjacent houses ever get mail on the same day, our string can never have $2$ adjacent "$1$"s. Then we look at the next condition. If there are never more than $2$ houses that don't get mail on the same day, our string can never have $3$ consecutive "$0$"s. So we are looking for the number of binary strings of length $n$ with no $2$ consecutive $"1"$s or $3$ consecutive $"0"$s.

[b]Forming the Recursion:[/b] We will define the quantity asked for in the last question for a string of $k$ digits as $S_k$. As per the problem, we want $S_{19}$, but we will stick to our plan of finding the formula for $S_n$ and continuing. We see that this string of $n$ digits must start with either a "$1$" or a "$0$". We can create two sub-recursions to count this easier, $a_n$ and $b_n$, for starting with "$1$" or "$0$" respectively. Obviously $S_n=a_n+b_n$, since the first digit must be either of those two. If a sequence starts with a 1, the next digit must be a 0. After that 0, we can either have a 1 or another 0. If we choose a 1, we have recursed to the case of $a_{n-2}$. If we add another 0, the digit after that must be a 1, and we have recursed to the case of $a_{n-3}$. So $a_n=a_{n-2}+a_{n-3}$. Now if the sequence starts with 0, we can either have a 1 which leads to $a_{n-1}$ or a 0 which leads to $a_{n-2}$ since a 1 must follow. So $b_n=a_{n-1}+a_{n-2}$. Adding these two for $S_n$, we get that $S_n=a_{n-1}+2a_{n-2}+a_{n-3}$.

[b]Making the Tables and Solving:[/b] We have a formula for $S_n$ along with the original formula for $a_n$! We want $S_{19}$ which by our formula is equivalent to $a_{18}+2a_{17}+a_{16}$. Now we need to find what those values are using the recursive formula for $a_n$. To start out, we know that $a_1$ is 1 because the first term of 1 is the only term. We can calculate more to see that $a_2$ is 1 because it must be a 1 and a 0. We do this again and see that $a_3=2$ since we can add on a 0 or 1 to our $a_2$ sequence. We now use our formula to calculate the next terms of $a_n$ from $4 \leq n \leq 18$ as 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, and 114. Remember what we are looking for and see that our answer is $114+2(86)+65$ or $\fbox{351}$.

[b]Conclusion:[/b] We have now solved the problem, so I will go over some major points. The hardest part of this problem was the intuition in my opinion. Once the problem solver sees that there is an elegant recursion solution and is familiar with the method even with multiple recursions, the problem becomes easy. Given that the test is 3 hours long and this is #14, this isn't an impossible test problem.

[/hide]

Groupsolved with [b]lpieleanu.[/b] (note these are just sketches cuz we worked on miro)
The main idea is just to BASH RECURRENCES and everything is straightforward from there. Indeed, let a_n=b_n+c_n, with b_n=ends with 0 (where 0s represent no mail), c_n=ends with 1 (where 1s represent yes mail), then b_n=c_(n-2) (for 100 binary) + c_(n-1) (for 10 binary); c_n=b_(n-1) (for 01 binary). Hence we get c_n=c_(n-3)+c_(n-2), and b_n=b_(n-3)+b_(n-2), and evidently a_n has the same recurrence. Bashing a_19 (since these are small terms and general form characteristic polynomial had INCREDIBLY COMPLICATED solutions), we get an answer of 351. $\blacksquare$

NOTE: this mgihtve not been the best and efficient way but it was striaghforawrd

[b]Solution:[/b] Let getting mail be $1$ and not getting mail be $0$. Essentially we want to find all the possible 19-letter strings composed of $0$s and $1$s where there can be no more than two consecutive $0$s and no number of  $1$s in a row (sound familiar? THAT'S CUZ IT IS. IT IS LITERALLY 2019 AMC 10B #25 AHHHH  SO COOL). Anyhow, we proceed with making the recursive formula: $f(n) = f(n-2) + f(n-3)$ (similar logic to 2019 AMC 10B #25). Then just bash to get that $f(19) = \boxed{351}$.


let $n$ be a natural number and $a_1,a_2,...,a_{2n-1}$ be integers. prove that we can choose $n$ ones of $a_i$s such that their sum be divisable by $n$.

I saw this problem few years ago on [i]sci.math[/i]:
[url=http://groups.google.com/groups?q=g:thl2777196494d&dq=&hl=fr&lr=&selm=3B7D3F16%40MailAndNews.com&rnum=31]Robin Chapman's solution[/url]

Have a look here :
http://www.mathlinks.ro/Forum/viewtopic.php?t=28929

Pierre.


why is the -gt component included for solving part b of 26b.

i would assume that substituting k = 0 would cancel out the mg terms, and thus yield v = v0

file is attached.

Why is it included?  Because there's still a gravitational force acting on the object as it goes through the air.  Taking $ k\rightarrow 0$ just make the situation more and more like the object is under the influence of only gravity.


function
limit
calculus
derivative
ratio
algebra unsolved
algebra

Find all functions $f: [0,1]\rightarrow[0,1]$ such that for every $x\in [0,1]$ :
$\lim_{n\to\infty}\sum_{i=1}^{n}f^i(x)$ exist.

Is $i$ the $i$-th derivative of $f$?

Sorry if that's a stupid question, I just a starter in the olympiad section.

Usually it would mean to re-iterate $i$ times. Eg:

$f^3(x)=f(f(f(x)))$

The sequence $a_n = f^n (x)$ cannot be alternating, so it must satisfy one of the ratio test, the root test, the comparison test, etc. and it must converge to zero.

So, to find the most obvious example, any $f(x) = ax^n$ where $0 \le a < 1$ and $n \ge 1$ or $a = 1, n > 1$ would work by either ratio or root test.  More generally, by ratio test it is required that $\lim_{n \to \infty} \frac{ f^n (x) }{ f^{n-1} (x) } < 1$ for all values of $x$ in the domain.

(Erm, I'm never really sure what to answer for these questions.  Couldn't there exist a class of functions that can't be described algebraically but that would still satisfy the property?)

:huh:

I think thare are a lot of nasty functions...
Any map such that $f^i(x)$ gets eventually $0$ works...
E.g. take any bijection between $\mathbb{N}$ and $\mathbb{Q} \cap [0;1]$; then define $f(q)$ for rational $q \neq$ as it's predecessor and $f(0)=0$ ; additionally take any mapping from the irrationals to the rationals; this gives for sure a very nasty function with the desired property.

There a lot more examples, but any characterisation of all such functions seems impossible.

[quote="ZetaX"]
Any map such that $f^i(x)$ gets eventually $0$ works...[/quote]

No, I suspect functions of the form $f(x) = \frac{ cx^p }{x^p + 1}, 0 < p \le 1, c > 0$ diverge by limit comparison to the harmonic series even though $\lim_{i \to \infty} f^i (x) = 0$, and that is why I had trouble characterizing all functions that satisfy the given property  :|

Your functions don't fulfill my property ;) (I think you confuse 'eventually get $0$' with 'approaches $0$')
The 'eventually gets $0$'-property is trivially sufficent.
And as I said, it's as good as impossible to characterize them all, see the examples.

Yes, I agree that they are many such functions.  Trying to characterize them all is [size=75]almost[/size] impossible.

By the way, I like the notation \[ f^3 (x) = f(f(f(x)))  \] instead of \[ f^3 (x) = (f(x))^3  \]
It complies with inverse function notation \[ f^{-1} (x)  \]
That is also why I don't like \[ sin^2 (x) = (sin(x))^2  \].


Jeremy made a Venn diagram showing the number of students in his class who own types of pets. There are 32 students in his class. In addition to the information in the Venn diagram, Jeremy
knows half of the students have a dog, $ \frac{3}{8}$ have a cat, six have some other pet and five have no pet at all. How many students have a cat, a dog and some other pet?

[asy]unitsize(50);
import graph;
pair A = (0,-1); pair B = (sqrt(3)/2,1/2); pair C = (-sqrt(3)/2,1/2);
draw(Circle(A,1.2) ^^ Circle(B,1.2) ^^ Circle(C,1.2));
label("10",A); label("2",B); label("9",C); label("$z$",(0,0)); label("$w$",(B+C)/2); label("$y$",(A+B)/2); label("$x$",(A+C)/2);
label("Cats",2.4C,C); label("Other Pets",2.4B,B); label("Dogs", 2.4A,A);[/asy]

[quote="damianoT"]if 3/8 must have a cat and we know there are 9 people who have a cat, 9+x+w+z=3/8(32), so 9+x+w+z=12 ->
x+w+z=3, but the 3 numbers must be integer positive, so the solution must be x=w=z=1.... very simply!!!!![/quote]

Not so fast, damianoT! ;)

There are 9 people who have [i]only[/i] a cat. Since 12 people have cats, this means that 3 have cats in conjunction with some other pet.

The variables $w$,$x$,$y$, and $z$ have to be non-negative integers, but they do not necessarily have to be positive integers. It would be perfectly legimate for one of the variables to have a value of zero. For example, if $w=0$ then that simply means that none of the students own a cat and some other pet that is not a dog (i.e. a cat and a fish, a cat and a bird, etc.)

This was a good problem!

[hide="Here's how I solved it:"]

We have $32 \times \frac{1}{2}=16$ students with dogs, $32 \times \frac{3}{8}=12$ students with cats, $6$ with something else, and $5$ with no pets at all. This means that $32-5=27$ students have at least one pet.

We use the Venn diagram to set up the following equations:
Total pet equation: $9+10+2+w+x+y+z=27$
Dog equation: $10+x+y+z=16$
Cat equation: $9+w+x+z=12$
Other equation: $2+w+y+z=6$

When we isolate the variables on the left, these equations become:
Total: $w+x+y+z=6$
Dog: $x+y+z=6$
Cat: $w+x+z=3$
Other: $w+y+z=4$

Now, we can solve for $w$, $y$, and $x$ by subtracting the Dog, Cat, and Other equations, respectively, from the Total Equation:
Total - Dog: $(w+x+y+z) -(x+y+z)=6-6$, which gives us $w=0$.
Total - Cat: $(w+x+y+z)-(w+x+z)=6-3$, and so $y=3$.
Total - Other: $(w+x+y+z)-(w+y+z)=6-4$, meaning that $x=2$.

Substitute these values into any of the four equations above and you'll see that $z=1$.

Since $z$ is the variable at the heart of the Venn diagram, it represents the number of students who own a dog, a cat, and some other kind of pet as well. As we now see, there is only $\boxed{1}$ student in that category.[/hide]

[hide="Here is the completed Venn diagram for the problem:"]
[asy]unitsize(50);
import graph;
pair A = (0,-1); pair B = (sqrt(3)/2,1/2); pair C = (-sqrt(3)/2,1/2);
draw(Circle(A,1.2) ^^ Circle(B,1.2) ^^ Circle(C,1.2));
label("10",A); label("2",B); label("9",C); label("1",(0,0)); label("0",(B+C)/2); label("3",(A+B)/2); label("2",(A+C)/2);
label("Cats",2.4C,C); label("Other Pets",2.4B,B); label("Dogs", 2.4A,A);[/asy][/hide]

Tim

[quote=pokemonJJ]lololololol[/quote]

Ayyy what a revive!

[hide]
Once you attain the system
\begin{align*}
& w + x + y + z = 6 \\
& x + y + z = 6 \\
& w + x + z = 3 \\
& w + y + z = 4,
\end{align*}
you can take advantage of the near-symmetry in the last three equations by adding them, which yields
$$2w + 2x + 2y + 2z + z = 13.$$
Plugging in the first equation gives $2 \times 6 + z = 13,$ and the rest is straightforward.
[/hide]


Έστω $ a,b,c$ θετικοί ακέραιοι. Αποδείξτε ότι $ \frac{a^{2}b\plus{}a^{2}c\plus{}b^{2}a\plus{}b^{2}c\plus{}c^{2}a\plus{}c^{2}b\minus{}6abc}{a^{2}\plus{}b^{2}\plus{}c^{2}\minus{}ab\minus{}bc\minus{}ca}\geq \frac{16abc}{\left(a\plus{}b\plus{}c\right)^{2}}$

Η ανισότητα γράφεται και:

$ \frac {\frac {a \plus{} b}{c} \plus{} \frac {b \plus{} c}{a} \plus{} \frac {c \plus{} a}{b} \minus{} 6}{16} > \equal{} \frac {a^2 \plus{} b^2 \plus{} c^2 \minus{} ab \minus{} bc \minus{} ca}{(a \plus{} b \plus{} c)^2}$

Σπάζοντας το κλάσμα στο β μέλος αρκεί να αποδείξουμε ότι:

$ \frac {a \plus{} b}{c} \plus{} \frac {b \plus{} c}{a} \plus{} \frac {c \plus{} a}{b} \minus{} 6 > \equal{} 16 \minus{} \frac {48(ab \plus{} bc \plus{} ca)}{(a \plus{} b \plus{} c)^2}$

Εφαρμόζοντας τη γνωστή ταυτότητα τώρα αρκεί να δείξουμε ότι:

$ \frac {(a \plus{} b)(b \plus{} c)(c \plus{} a)}{abc} \plus{} \frac {48(ab \plus{} bc \plus{} ca)}{(a \plus{} b \plus{} c)^2} > \equal{} 24$

που ισοδυναμεί με:

$ \frac {(a \plus{} b)(b \plus{} c)(c \plus{} a)}{abc} > \equal{} \frac {24(a^2 \plus{} b^2 \plus{} c^2)}{(a \plus{} b \plus{} c)^2}$

το οποίο αποδεικνύεται εύκολα με muirhead αλλά δεν μπορώ να βρω κάτι καλύτερο. :P

[color=red]Edit: Τελικά δε βγαίνει εύκολα ούτε με muirhead λάθος εκτίμηση, υπάρχει άθροισμα με μικρότερο μεγιστοβάθμιο εκθέτη αριστερά... είναι αρκετά σφιχτή, θα ψάξω μήπως βρω κάτι καλύτερο...[/color]

Ωραία άσκηση ! Λόγω συμμετρίας υποθέτουμε ότι $ a\geq b\geq c$
Η ανισότητα γράφεται $ \frac{\sum c(a\minus{}b)^2}{\sum (a\minus{}b)^2}\geq\frac{8abc}{(a\plus{}b\plus{}c)^2}$  που ισοδυναμεί με

$ \sum c(a\minus{}b)^2((a\plus{}b\plus{}c)^2\minus{}8ab)\geq 0$ . Επειδή είναι $ a\geq b\geq c$ θα έχουμε $ a(c\minus{}b)^2((a\plus{}b\plus{}c)^2\minus{}8cb)\geq 0$ επομένως αρκεί νδο

$ c(a\minus{}b)^2((a\plus{}b\plus{}c)^2\minus{}8ab)\plus{}b(a\minus{}c)^2((a\plus{}b\plus{}c)^2\minus{}8ac)\geq 0$  . Όμως $ (a\plus{}b\plus{}c)^2\minus{}8ab\plus{}(a\plus{}b\plus{}c)^2\minus{}8ca\equal{}2(b\plus{}c\minus{}a)^2$ άρα ο μεγαλύτερος από τους

$ (a\plus{}b\plus{}c)^2\minus{}8ab,\ (a\plus{}b\plus{}c)^2\minus{}8ca$ είναι μη αρνητικό και εύκολα βλέπουμε ότι ο μεγαλύτερος είναι ο $ (a\plus{}b\plus{}c)^2\minus{}8ca$

Επιπλέον $ b(a\minus{}c)^2\geq c(a\minus{}b)^2$ και αφού $ (a\plus{}b\plus{}c)^2\minus{}8ca\geq 0$  θα είναι

$ b(a\minus{}c)^2((a\plus{}b\plus{}c)^2\minus{}8ca)\geq c(a\minus{}b)^2((a\plus{}b\plus{}c)^2\minus{}8ca)$ επομένως αρκεί νδο

$ c(a\minus{}b)^2((a\plus{}b\plus{}c)^2\minus{}8ab)\plus{}c(a\minus{}b)^2((a\plus{}b\plus{}c)^2\minus{}8ac)\geq 0$ που ισοδυναμεί με

$ 2c(a\minus{}b)^2(b\plus{}c\minus{}a)^2\geq 0$ το οποίο προφανώς ισχύει !  :)


[quote="Silverfalcon"]yeah.. It's odd topic but here it goes:

I'm a student who plans to major on physics. I already started independent studying for physics and to be honest, I like it very much compare to chemistry or biology. So far, I took biology on my freshman year, chemistry on my sophomore year (which is now) and will be taking physics in junior year (next year). Originally, I was planning to take Adv. Biology and Adv. Chemistry on my senior year. I want to become a doctor but right now, I don't know if my original decision would be smart or not.

I want to know which one's better:

1. Take Adv. Biology and Adv. Chemistry to get decent grip on all the sciences (btw, these classes are NOT AP level; they're below AP --> No AP science class on my school)
2. Since I'll be doing independent study for AP Physics B in my senior year, maybe try to take physics class at local college?
3. Just take one science and practice for AP. If so, which one?[/quote]
Option 3-Adv.Chemistry. We all know Biology is the wussy science.

a whole bunch of my friends commented that taking AP chem- i guess it would also apply to adv chem in your case- is alot more helpful for a premed than AP bio... it gives a better grouonding in the science at the molecular level which helps understand bilogical processes better once you take it in college- thats if you stay with the med school track!

yea seriously... bio is a wussy science, dont take it. Or do what im doing and take only because it's so easy to ace. But focus on physics. So concentrate on physics, but have a little bit of bio and chem but keep physics as your number 1 priority.


[quote="tarquin"]The sum of the first three terms of a geometric sequence of positive integeres is equal to seven times the first term, and the sum of the first four terms is 45. What is the first term of the sequence?[/quote]

[hide="Answer"]
I used guess and check.
You start with 3, add 6, add 12 and add 24 to get 45 as the fourth number.
3+6+12=21
21/3=7
First term is 3.
[/hide]

You are right. By algebra, I think it would take a shorter time unless you are lucky.

[quote="09husbri"]I agree, but to put in my two cents,
[hide]You could figure out that the common ratio of the sequence is 2 since the sum of the first three terms is equal to seven times the first term. x+2x+4x=7x, after all. That would make it easier.[/hide][/quote]

Hmm... I never thought of that. Thanks. I'll keep that in mind.

[hide] The sum of the first three terms is a+ar+ar^2=7a, which simplifies to 1+r+r^2=7. Solving this equation using quadratics or factoring gives r=2. Thus, a+2a+4a+8a=45 (sum of first four terms). This gives 15a=45, or a=3.

Answer: 3[/hide]

I like 09husbri's way the best.  It seems to work the best for me.

[hide]If $y$ is the common ratio, and $x$ is the first term then $x + xy + xy^2 = 7x$ which is $x(1 + y + y^2) = 7x$ so $ y + y^2 - 6 = 0$. Solving, $y$ can be 2 or -3, but we see that the only answer that makes $x$ come out positive is 2, so $x + 2x + 4x + 8x = 45$ which means that $x = 3$.[/hide]


Let $\{X_n\}$ and $\{Y_n\}$ denote two sequences of integers defined
as follows:
$X_0 = 1,X_1 = 1,X_{n+1} = X_n + 2X_{n-1} (n = 1, 2, 3, . . . )$,
$Y_0 = 1, Y_1 = 7, Y_{n+1} = 2Y_n + 3Y_{n-1} (n = 1, 2, 3, . . . ).$
Thus, the first few terms of the sequences are:
$X : 1, 1, 3, 5, 11, 21, . . .$,
$Y : 1, 7, 17, 55, 161, 487, . . .$.
Prove that, except for the “$1$,” there is no term which occurs in both sequences.

Masoud Zargar

Nice ! Prove easily that for any $\{n,m\}\subset N\ ,\ x_n=\frac 13\left[2^{n+1}+(-1)^n\right]\ ,$
$y_m=2\cdot 3^m+(-1)^{m+1}$ and $x_n=y_m\Longrightarrow n=m=0$
$($ appear four cases w.r.t. the parity of the natural numbers $m,n\ )\ .$


induction
ratio
LaTeX
geometric sequence

Prove that, for any integer $a_{1}>1$, there exist an increasing sequence of positive integers $a_{1}, a_{2}, a_{3}, \cdots$ such that \[a_{1}+a_{2}+\cdots+a_{n}\; \vert \; a_{1}^{2}+a_{2}^{2}+\cdots+a_{n}^{2}\] for all $n \in \mathbb{N}$.

nice!

the idea of the induction is see that, if $a_1+...+a_n | {a_1}^2 + ... + {a_n}$, and $k = \frac{{a_1}^2 + ... + {a_n}^2}{a_1+...+a_n}$

$a_{n+1} = k$ holds.

our problem is that k is not sufficient big. to solve this is easy!  :wink:

There is another interesting method.  If a_1 = 2, then the increasing geometric sequence starting with 2 and having common ratio 3 satisfies the condition.  If a_1 > 2, then the increasing geometric sequence starting with a_1 and having common ratio a_1 - 1 satisfies the sequence (this is easy to verify, but I don't know Latex so I didn't prove my assertions here).  And we are done.


function
real analysis
real analysis unsolved

I have the function f(x)=x-π for xεQ and f(x)=0 for xεR/Q. How can I show that f is continuous at π and discontinuous at all other points?

Thx

1) Any open interval, such as $ (x_0 \minus{} \delta,x_0 \plus{} \delta)$, contains both rational and irrational points.

2) Draw the graphs $ y \equal{} 0$ and $ y \equal{} x \minus{} \pi$. These are two lines intersecting only at $ x \equal{} \pi$. Over any open interval on the real axis, the graph of your function contains points on both lines.


Let N* = {1, 2, 3, ...}. Let f be a bijection N -> N such that for every n in N*, we have either f(n + 1) = f(n) - 1 or f(n + 1) = 4f(n) - 1. Find all possible values of f(1999).

I don't manage to start this ...

i don't understand. If f is a bijection N->N then
there exists a unique n so that f(n)=0 and then
 f(n+1)=-1 impossible

where am i wrong ?

There doesn't exist any n such that f(n) = 0, since f is a bijection N* -> N*.
Since N* = {1, 2, 3, ...}, 0 does not belong to N*.

Now this could be a very little part of the solution.

Take a in N* such that f(a) = 1. Then certainly f(a + 1) = 3.
(Otherwise we would have f(a + 1) = 0, contradiction since 0 is not in N*.)
Now take a certain b in N* such that f(b) = 2.
If f(b + 1) = f(b) - 1 = 1 then a = b + 1.
Otherwise f(b + 1) = 4f(b) - 1 = 7. Then certainly b > a + 1.

So f, which is a permutation, should look like
(1) x, x, ..., x, 2, 1, 3, ... or
(2) x, x, ..., x, 1, 3, x, x, ..., x, 2, 7, ...

Oh, this seems to be a good approach ! I'll continue.

[quote="Arne"]So f, which is a permutation, should look like
(1) x, x, ..., x, 2, 1, 3, ... or
(2) x, x, ..., x, 1, 3, x, x, ..., x, 2, 7, ...

Oh, this seems to be a good approach ! I'll continue.[/quote]

Also notice that if f(n) = 2 f(n-1) must equal 3.  Also if f(n) = 1 f(n-1)=2.  This allows us to remove the x's and simplify Arne's two cases to

(1) 2, 1, 3,...
(2) 1, 3, 2, 7...

From here all that remains is to prove that those two sequences are uniquely defined given that they are bijections.  This is a bit of a notational inconvenience so I won't do it right now, but in the end there should be a pattern involving powers of 2.

hmm I belive that the main trick is to go backwards.

Say we have f(1)=2, f(2)=1, f(3)=3. Then take f(k)=4 for some k. Then f(k-1)-1=4 => f(k-1)=5 because the other case is not possible modulo 4. Same f(k-2)=6, f(k-3)=7. Now either we have f(k-4)=8 or f(k-4)=(7+1)/4=2 which means that k-4=1 and thus f(k-3)=f(2)=1=7 contradiction. Thus f(k-4)=8 and in the same manner f(k-5)=9, f(k-6)=10, f(k-7)=11. Now if f(k-8)=12 we go on in the same manner and obtain f(k-11)=15 and we cannot have f(k-12)=(15+1)/4=4 because we have already obtained 4 above. Thus we obtain a infinite decreasing sequence of positive integers k-1,k-2,.... which is imposible.

Therefore we MUST have f(k-8)=(11+1)/2=3 and thus k-8=3 so the function looks like 2,1,3,11,10,9,8,7,6,5,4, ...

Let us now compute f(12)=4-1=3 no possible so f(12)=15. But then there is a k such that f(k)=12 from which we can only get f(k-1)=13, f(k-2)=14, f(k-3)=15, so we can continue 15,14,13,12. Now we have f(16)=47 and taking k such that f(k)=16 we obtain that k=47. Thus f(48)=4.16-1=63 and f(63)=48, f(64)=4.48-1, f(191)=64, f(192)=4.64-1, f(255)=192, f(256)=4.192-1, f(767)=256, f(768)=4.256-1, f(1023)=768, f(1024)=4.768-1=3071 and thus f(1999)=3071-975=2096.

I guess that the second case can be treated in the same way. :)


$ x,y,z$ positive number  $ x \plus{} y \plus{} z \equal{} 3$  and $ 0\leq k \leq 9$

Prove that:

$ \frac {x \plus{} y}{xy \plus{} k} \plus{} \frac {y \plus{} z}{yz \plus{} k} \plus{} \frac {z \plus{} x}{zx \plus{} k}\geq \frac {6}{1 \plus{} k}$

By full expansion I have obtained:

$ 2k^2\sum a^6 \plus{} 3k(k \plus{} 3)\sum ab(a^4 \plus{} b^4) \plus{} 18(k^2 \minus{} 54)a^2b^2c^2 \plus{} 6k(6 \minus{} k)\sum a^2b^2(a^2 \plus{} b^2) \plus{} 2(27k \minus{} 7k^2)\sum a^3b^3 \plus{} 6k(k \minus{} 9)abc\sum a^3 \plus{} 3(k \minus{} 9)(k \minus{} 6)abc\sum ab(a \plus{} b) \geq 0$

but now I cannot go on. :(

Can you please help me, Arqady or someone other.

Thank you very much. :)

[quote="manlio"]

$ x,y,z$ positive number $ x \plus{} y \plus{} z \equal{} 3$ and $ 0\leq k \leq 9$

Prove that:

$ \frac {x \plus{} y}{xy \plus{} k} \plus{} \frac {y \plus{} z}{yz \plus{} k} \plus{} \frac {z \plus{} x}{zx \plus{} k}\geq \frac {6}{1 \plus{} k}$

By full expansion I have obtained:
$ 2k^2\sum a^6 \plus{} 3k(k \plus{} 3)\sum ab(a^4 \plus{} b^4) \plus{} 18(k^2 \minus{} 54)a^2b^2c^2 \plus{} 6k(6 \minus{} k)\sum a^2b^2(a^2 \plus{} b^2) \plus{} 2(27k \minus{} 7k^2)\sum a^3b^3 \plus{} 6k(k \minus{} 9)abc\sum a^3 \plus{} 3(k \minus{} 9)(k \minus{} 6)abc\sum ab(a \plus{} b) \geq 0$
[/quote]

I've got the same, but with $ x,$ $ y$ and $ z.$  :lol:
It's equivalent to
$ 2k^2\sum_{cyc}(x^6\plus{}2x^5y\plus{}2x^5z\minus{}x^4y^2\minus{}x^4z^2\minus{}4x^3y^3\plus{}x^2y^2z^2)\plus{}$
$ \plus{}k(9\minus{}k)\sum_{sym}(x^5y\plus{}4x^4y^2\plus{}3x^3y^3\minus{}3x^4yz\minus{}3x^3y^2z\minus{}2x^2y^2z^2)\plus{}$
$ \plus{}18(9\minus{}k)\sum_{cyc}(x^3y^2z\plus{}x^3z^2y\minus{}2x^2y^2z^2)\geq0.$

Thank you very much, Arqady.

You are really very clever. :)


is this sum convergent
$\sum^\infty{\frac{\sqrt[n]{n}-1}{n}}$ ?

Since $\frac {\sqrt[n] {n} } n \geq \frac 1 n$ I don't see how it could be convergent...

Pierre.

I editet first post, please, have a look

We have $\sqrt[n]n=e^{\frac{1}{n}\ln n}\sim 1+\frac{\ln n}{n}$ as $n\to \infty$. Therefore $\frac{\sqrt[n]{n}-1}{n}\sim \frac{\ln n}{n^2}$ and the series converges.


induction
quadratics
algebra
number theory
divisibility tests

Prove the following statements [b]by induction[/b]:

(a) for all integers $ n\ge 0$, the number $ {5}^{2n} \minus{} {3}^n$
(b) for any integer $ n\ge 1$, the integer $ {2}^{4n \minus{} 1}$ ends with an 8.

[hide="(b)"]Base case: $ 2^{4\minus{}1}\equiv 2^3\equiv 8 \mod 10$.
Inductive step: Assume $ 2^{4k\minus{}1}\equiv 8\mod 10$, for some $ k\ge1$.
Now, show that $ 2^{4(k\plus{}1)\minus{}1}\equiv 8\mod 10$.
$ 2^{4(k\plus{}1)\minus{}1}\equiv 2^{4k\minus{}1 \plus{} 4}\equiv 2^{4k\minus{}1}\cdot 2^4  \equiv 8\cdot 16 \equiv 8 \mod 10$.[/hide]

Your problem statement for (a) is incomplete  :)

Also, I hope you don't mind me asking -- why are you so keen on seeing only induction proofs for everything?
If you, at some point, tell us why you are looking for induction, we might even be able to offer constructive ideas.
For example, if your objective is to get an idea of some of the techniques people use to execute the inductive step, we can point you to many examples of worked-out problems and such.

From the title, the missing words are "is divisible by 11."

Yawn.
[hide="a)"]Base case- n=1
$ 5^2 \minus{} 2^1 \equal{} 22 \equiv 0 \mod 11$

Now, assume that $ 5^{2n} \minus{} 3^n \equiv 0 \mod 11$.
Multiply this through by 25.
$ 25\cdot5^{2n} \minus{} 25\cdot3^n \equiv 0 \mod 11$.

Subtract $ 22\cdot 3^n$ from $ 25\cdot5^{2n} \minus{} 25\cdot3^n$.
$ 22\cdot 3^n$ is divisible by 11 for whole numbers n, so

$ 25\cdot5^{2n \plus{} 2} \minus{} 3\cdot3^n \equiv 0 \mod 11$.
Which implies $ 5^{2(n \plus{} 1)} \minus{} 3^{n \plus{} 1} \equiv 0 \mod 11$.

QED.[/hide]

We can use a concept of induction (a "domino" effect) in another way, too:

[b]Base Cases:[/b] [i]Divisibility by 11 holds for $ n \equal{} 0$ and $ n \equal{} 1$:[/i]
$ 11$ divides $ 1 \minus{} 1 \equal{} 0$, and also $ 25 \minus{} 3 \equal{} 22$

[b]Inductive Step:[/b] [i]If divisibility by 11 holds for $ n \minus{} 1$ and for $ n$, it is true for $ n \plus{} 1$. Note that:[/i]

$ a^{n \plus{} 1} \minus{} b^{n \plus{} 1} \equal{} (a \plus{} b)(a^n \minus{} b^n) \minus{} ab (a^{n \minus{} 1} \minus{} b^{n \minus{} 1})$

Or, for this particular case, $ a \equal{} 25$ and $ b \equal{} 3$:

$ 25^{n \plus{} 1} \minus{} 3^{n \plus{} 1} \equal{} 28(25^n \minus{} 3^n) \minus{} 75 (25^{n \minus{} 1} \minus{} 3^{n \minus{} 1})$

But the two terms on the right are divisible by $ 11$, so the LHS must also be divisible by $ 11$.

[b]Conclusion:[/b] [i]Therefore $ 25^n \minus{} 3^n$ is divisible by $ 11$ for all $ n \in \mathbb{N}^*$.[/i]

[b]Notes:[/b] [i]Observe that a sequence $ S_n \equal{} a^n \plus{} b^n$ satisfies the recurrence $ S_{n \plus{} 1} \equal{} (a \plus{} b) S_n \minus{} ab S_{n \minus{} 1}$, which rearranges to $ S_{n \plus{} 1} \minus{} (a \plus{} b) S_n \plus{} ab S_{n \minus{} 1} \equal{} 0$. Now consider the similar looking quadratic equation $ x^2 \minus{} (a \plus{} b) x \plus{} ab \equal{} 0$. Can you see the link?[/i]

I've never used induction before, can someone tell me if this is correct

First $ n\equal{}1$
$ 25\minus{}3 \equal{} 22 \equiv 0 \mod 11$

So for induction we have to prove that

$ 5^{2(n\plus{}1)} \minus{} 3^{n\plus{}1} \equiv 5^{2n} \minus{} 3^n \mod 11$

$ 5^{2(n\plus{}1)} \minus{} 5^{2n} \plus{} 3^{n} \minus{}3^{n\plus{}1} \equiv 0 \mod 11$

$ (25\minus{}1)5^{2n} \plus{} (1\minus{}3)3^n \equiv 0 \mod 11$

$ 22.5^{2n} \plus{} 2(5^{2n}\minus{} 3^n) \equiv 0 \mod 11$

$ 11.2.5^{2n} \equiv 0 \mod 11$

This is divisible by 11 there for the statement holds...

The contents are correct, however your proof of the inductive step flows backwards. When you write a proof, the general flow should be:

[i]statement, therefore statement, therefore statement, ..., therefore conclusion[/i]

As opposed to:

[i]statement, which is true if statement, which is true if statement, ... which is true if statement, which is true. Thus, the original statement is true.[/i]

Take a look at textangle's proof, which starts from a known (or rather, an assumed) fact (true for n), executes logical steps, and arrives at the conclusion (true for n+1).

But this is not a problem of you misunderstanding induction. It is generally considered better proof writing if you work forwards. Also, this reduces the possibility of you making an irreversible step, which might happen while working backwards.

Consider: 1=2. Multiply both sides by 0 to get 0=0, a true statement. Thus, 1=2 is proven. The step "multiply by zero" is not reversible, leading to an incorrect proof. Usually, usage of irreversible steps are not this blatant, but this illustrates the possibility.

[quote="Textangle"]Yawn.
[/quote]Eliminate this and the attitude that spawned it, and you've got the proper post.

[quote="ocha"]I've never used induction before, can someone tell me if this is correct

First $ n \equal{} 1$
$ 25 \minus{} 3 \equal{} 22 \equiv 0 \mod 11$

So for induction we have to prove that

$ 5^{2(n \plus{} 1)} \minus{} 3^{n \plus{} 1} \equiv 5^{2n} \minus{} 3^n \mod 11$

$ 5^{2(n \plus{} 1)} \minus{} 5^{2n} \plus{} 3^{n} \minus{} 3^{n \plus{} 1} \equiv 0 \mod 11$

$ (25 \minus{} 1)5^{2n} \plus{} (1 \minus{} 3)3^n \equiv 0 \mod 11$

$ 22.5^{2n} \plus{} 2(5^{2n} \minus{} 3^n) \equiv 0 \mod 11$

$ 11.2.5^{2n} \equiv 0 \mod 11$

This is divisible by 11 there for the statement holds...[/quote]
we dont use modulo in induction i think.
We have to replace n by k and derive an expression and then replacing n by k+1 we have to derive an expression in the same form as the previous.
You cant use mod in high school , not in India atleast.

[quote="Zed_darkx"]we dont use modulo in induction i think.[/quote]
Every argument that consists of simplifying an expression $ \bmod 11$ can be rewritten as an argument by subtracting appropriate terms.  Using "modulo" is not actually introducing a new concept here - it's just convenient notation.  (ocha is not, for example, citing any theorems other than the basic properties of congruence.)


How many ways are there to tile a $ 10 \times 2$ rectangle with $ 3 \times 2$ red tiles, $ 2 \times 1$ green tiles, $ 1 \times 1$ blue tiles and $ 1 \times 3$ yellow tiles if we have an unlimited supply of each type of tile?

[hide="Hint"]REcursion seems good in this problem.[/hide]


the larget of 2 #s is 1 less than 8 times the smaller. their sum is 179. find the #s

let two numbers be x and y, and x is the larger number.

x=8y-1

y+8y-1=179, 9y=180, y=20.

answer : 20, 159


I have a question about the avatars: Is there any way to make the size limit bigger? Because I had a little animation I wanted to put as my avatar, and the size was 22 or something and the limit was 21. (Not sure if it's kb or something...)

I think it might affect the server data use completely, but just asking.

Just go to paint (or someother photo editer) and resize it, making the size smaller.

Sorry, it's an animation. Never mind the above.

You can google image resizers. Many of them do animations.


logarithms
inequalities
calculus
calculus computations

Show that it is not true that for every error $\frac{1}{m}$ there exists $n$ s.t. $|\Sigma_{k=1}^{n}r^{k}-\frac{r}{1-r}|<\frac{1}{m}$, $\forall r$ in $0<r<1$.

One approach: $\sum_{k=1}^{n}r^{k}$ is bounded by $n$ for all $0<r<1$, and $\frac{r}{1-r}\to\infty$ as $r\to 1$.

A more direct approach: $\sum_{k=1}^{n}r^{k}=r\frac{1-r^{n}}{1-r}$. Therefore, $\sum_{k=1}^{n}r^{k}-\frac{r}{1-r}=-\frac{r^{n+1}}{1-r}$. Set $r=1-1/n$.

thanks. I was thinking of the same approach as your more direct approach.
I just got stuck setting up r to formulate a counterexample.
I was thinking of actually plugging in concrete numbers.... :P

Anyways, thank you for your reply.

Actually, I guess the approach was a bit different, I don't know if this is a valid approach..
but here it goes:

We want to counter the statement that there exists $n$ for every error $\frac{1}{m}$ s.t.

$|\sum_{k=1}^{n}r^{k}-\frac{r}{1-r}| < \frac{1}{m}$

$|\sum_{k=1}^{n}r^{k}-\frac{r}{1-r}| = |-\frac{r^{n+1}}{1-r}| < \frac{1}{m}\forall r$

Getting rid of the abs signs,

$|-\frac{r^{n+1}}{1-r}| = \frac{r^{n+1}}{1-r}< \frac{1}{m}$

Simplifying this, we get:

$r^{n+1}< \frac{1-r}{m}$

Taking the log and simplifying again:

$n+1 < \frac{\ln (1-r)-\ln m}{\ln r}$

$n < \frac{\ln (1-r)-\ln m}{\ln r}-1 = \frac{\ln(\frac{1-r}{r})-\ln m}{\ln r}$

Considering the case where $m=2$ and $r=\frac{1}{2}$, we get to the following result:

$n < \frac{-\ln 2}{-\ln 2}= 1$

Since $n \geq 1$, a contradiction arises, and therefore, the statement is not true.

You divided an inequality by $\ln r$, which is negative.

o, that was one terrible mistake i've made....

Is there any kind of algebraic way to show that the statement is false?

Also, going back to your more direct approach, i just have one question concerning your method..

why exactly do you set $r=1-\frac{1}{n}$?


Ring Theory
group theory
abstract algebra
superior algebra
superior algebra unsolved

Let $ S$ be an unitary ring and $ R$ a subring of $ S$ with characteristic $ m$. Prove that the characteristic of $ S$ is $ m$.

My professor asked me to prove this without using homomorphism. I found the following proof, but professor thinks it makes an easy thing to seem too complicated.

As $ R$ is a subring of $ S$ and $ 1\cdot m\equal{}0$ in $ R$, $ 1\cdot m\equal{}0$ in $ S$ because the addition in $ R$ is the restriction of the addition in $ S$. Alike, if for all $ m^\prime$ satisfying $ 1<m^\prime <m$ we have $ 1\cdot m^\prime \ne 0$ in $ R$, we have $ 1\cdot m^\prime\ne 0$ in $ S$.

Is there more elementary way to prove the theorem?

I think that's as simple as it gets.  1 has the same additive order in any additive subgroup of S that contains it.

One thing that needs to be cleared up though is whether your definitions of 'ring' and 'subring' include a unit.  Given you say 'Let S be a unitary ring', it sounds like they don't.  But in that case, a subring need not contain the unit of S, even if it happens to be unitary, and in that case the characteristics need not be equal.  For instance, (0,1) is the unit of R = {0} + Z/2Z, which has characteristic 2.  R is a subring of S = Z/4Z + Z/2Z, the unit of which is (1,1), and S has characteristic 4.