function
algebra
polynomial
trigonometry
Support
real analysis
real analysis unsolved

So, [url=http://mathworld.wolfram.com/GibbsPhenomenon.html]Gibbs' phenomenon[/url] is a well-known behavior of the Fourier series of a function with a jump discontinuity. Near the discontinuity, there is always a bit of a bump in the approximation. You can prove this by superposition -- subtract a jump (and possibly a kink) to leave a smooth function. Then you have one (or two) simple functions to deal with, and one well-behaved one.

Anyway, what I'm wondering is this: When we make similar series with other orthogonal functions, does this phenomenon still occur? How similar is it? Do we approach the problem in a similar way?

I think the most simple and approachable functions we could look at are the Legendre polynomials. I tried to do this a while ago, and I think some of the equations on Mathworld might be wrong on the Legendre polynomial page. Anyway, I didn't get too far -- I had some problems making all of my series converge. But there are a lot of other families of functions that we can look at. The Bessel functions are interesting too.

Does anyone know about this, or is anyone willing to guide me a little in how I might investigate it myself?

Thanks!

You probably need to be more specific with the conditions you want than merely orthonormal. Take for instance, the Haar system. Then any particular partial sum of the Haar series for an integrable function $f$ will be a step function, with its value on any particular interval equal to the average of $f$ on that interval. Hence, locally and globally, the partial sum of the series stays with any interval containing the range of $f.$ That's antithetical to the Gibbs phenomenon, the hallmark of which is partial sums that spill out to the outside of the local range of the original function.

You've still got an interesting question; it just needs some refining.

I really don't know what restrictions I should put on, though. (By the way, we might want to leave off "normal" -- I thought neither Legendre polynomials nor Bessel functions are normalized.) Perhaps just if the approximating functions must be continuous?

I checked out a book a while ago about orthogonal functions and Fourier series, but I don't recall that he discussed this problem. Also I didn't get to read the whole book before it was due, and I didn't renew it because I had too much schoolwork. And now it is 1500 miles away, safely in Fine Hall Library awaiting my return in September.

I don't know how I'd approach the general question, anyway. I suppose that's why I was posting. Certainly I could probably hack away at particular cases, but it is very tedious, especially when you are working with incorrect identities (or perhaps I just misinterpreted the notation).

I might look at the Legendre polynomial case again to get a feeling for it, though. A guy once gave me an intuitive explanation for the phenomenon: if we have an approximation by trig functions, and we add some more higher frequency ones to improve the approximation, we can zoom in on the point of discontinuity until the new higher frequency ones look like the old ones from before. But the jump looks just the same when we zoom in on it, so in some sense adding higher frequency polynomials isn't really helping. But that doesn't seem like it extends to these other ones. I mean, the higher Legendre polynomials don't look like the lower ones when we zoom in, do they? I guess the Bessel functions might, since they're sorta like damped trig functions, but I'm not really familiar with them so I'm not sure.

A couple of hints. First: normalization has nothing to do with anything. The norms of the members of the orthogonal set are part of the projection formula in any case. Having the set be orthonormal is a minor convenience, nothing more.

Second: the Haar basis is multiscale - a prototype of a wavelet basis. High-index members of the family have very small supports. This contrasts sharply with the trigonometric basis, in which each member of the basis is supported on the whole interval - in fact, there's a great homgeneity of behavior, in which the basis element looks about the same on any inteval of given lenght, at any location. The classic special functions - Legendre polynomials, or other polynomial families orthogonal with respect to some weight, or one of the many orthogonal families crafted from Bessel functions - they're all more like the trigonometric basis, with large support and some similiarities in behavior over different parts of the domain.

Go ahead and deal with specific cases. Maybe the first one should be trying to represent $\text{sgn}(x)$ on $[-1,1]$ as a sum of Legendre polynomials. That should be sufficiently computationally tractable (using something like Maple or Mathematica or some programming language) that you should be able to draw graphs.


I am new to LaTeX and am trying to use it for the USAMTS. This is my first year in the contest, and I am getting some errors when compiling the PDF file for my solutions. It compiles fine, but can somebody tell me if the following errors will prevent a successful solution submission?
I found no \citation commands --- while reading file C:\[...extremely long file path...]\USAMTS\solutions.aux

I found no \bibdata command --- while reading file C:\[...extremely long file path...]\USAMTS\solutions.aux

I found no \bibstyle command --- while reading file C:\[...extremely long file path...]\USAMTS\solutions.aux

(There were 3 error messages)

Couldn't find input index file C:\[...extremely long file path...]\USAMTS\solutions nor C:\[...extremely long file path...]\USAMTS\solutions.idx

Usage C:\Program Files\MiKTeX 2.8\miktex\bin\makeindex.exe [-ilqrcgLT] [-s sty] [-o ind] [-t log] [-p num] [idx0, idx1 ...]

And BTW, what is a "bad box" and an "Overfull \hbox"? I am getting those during compiling too, although they do not seem to be actual errors.

Any help would be greatly appreciated.
Thanks!

All those so-called errors are only telling you that you haven't used citations, indexes or references which is correct, so they can be ignored. The only errors you need to worry about are the ones in the last line of TexnicCenter's window where it says:
Latex-Result: n Error(s), m Warning(s), x Bad Boxes, y Page(s)

It is vital that n is 0, and desirable that m is also 0. Bad boxes can come about because you put \\ on a line by itself for example, and overfull \hbox if things are too wide eg go into the margins and also gives a bad box. They aren't vital but if you press F11 in TexnicCenter (or the icon at the top right of the toolbar) it will tell you where the problem is.


Can I buy Aops books from highperception using AOPS gift cards?

No, they do not accept our gift certificates.  The certificates are only valid on orders placed directly from Art of Problem Solving.


symmetry
superior algebra
superior algebra unsolved

Let S be a nonempty set, and let sigma be in Sym(S). For x, y in S define x~y if sigma^n(x)=y for some n in the integers. Show that ~ defines an equivalence relation on S.
I know that I have to show the following but how do I start:

1. Reflexivity: x ~ x

2. Symmetry: x ~ y --> y ~ x

3. Transitivity: x~y and y~z  -->x~z

Make yourself clear, that 1. n=0 and 2. negative values for n are allowed, and 3. appy the rule for composing iterations of a mapping: $f^n(f^m(x)) = f^{n+m}(x)$.

LiMa


Is it generally the case that not many people (if any) get a perfect score on the AIME?

Yes, last year there were like less than or equal to three perfect scorers.

See this URL for AIME stats:

[url]http://www.unl.edu/amc/e-exams/e7-aime/archiveaime.shtml[/url]


trigonometry
inequalities proposed
inequalities

If $a,b$ are real numbers with $a^{2}+b^{2}=16$  then find the maximum value of
$A=a+9a\sqrt{3}+9b-b\sqrt{3}$

set $a=4\cos \theta,b=4 \sin \theta$
Also it can be proved by cauchy directly. :D


[quote="bigbang195"]a,b,c >0 Prove that !
 $ \sum \frac {a^2 \plus{} 2bc}{b \plus{} c}\ge \frac {3}{2}(a \plus{} b \plus{} c)$[/quote]

$ \Longleftrightarrow 2\sum a^2(a\minus{}b)(a\minus{}c)\plus{}\sum a(b\plus{}c)(a\minus{}b)(a\minus{}c)\geq 0.$


[quote="Zamfirmihai"]$ x,y,z\geq 0;x+y+z=3$. Prove that:
$ \frac{\sum{x^{2}}+xyz+1}{5}\geq \frac{xy+yz+zx}{3}$[/quote]

of course it's not hard..you can trivialy homogenize it :P


[hide]All of those negative and positive integers cancel out, except for 10001.
$\boxed{Answer: 10001}$
[/hide]

2? or 3? :P

[hide="answer"]heh, it'd be 10001 surely ;)[/hide] [/hide]

[quote="236factorial"]I hope you're reading the question right.  :roll:[/quote]
what? i thought i did it correctly...i did it again and got the same answer... :?

There looks like three zeros between the ones.  :P

[quote="math92"][hide]
everything cancles out exept 0 and 1001.  $1001+0=\boxed{1001}$[/hide][/quote]

I noticed my mistake.
Read the question right, math02.  :D

oh... :)
[hide]
the answer is $10001$[/hide]


algebra
polynomial
induction
algebra proposed

[quote="Maxim Bogdan"]Let $ n$ and $ k$ be two positive integers. Determine all monic polynomials $ f\in\mathbb{Z}[X],$ of degree $ n,$ having the property that $ f(n)$ divides $ f\left (2^{k}\cdot a\right ),$ forall $ a\in\mathbb{Z},$ with $ f(a)\neq 0.$[/quote]

[u]Lemma[/u] : if $ P\in\mathbb Z[X]$ and $ d|P(x)$ $ \forall x\in\mathbb Z\backslash\{$ some finite subset of $ \mathbb Z\}$, then $ d$ divides all coefficients of $ P(x)$
Obvious (thru induction on degree, for instance)

Let then $ h(x) \equal{} f(2^kx)$ : $ f(n)$ divides $ h(x)$ $ \forall x$ such that $ f(x)\neq 0$. So, thru lemma, $ f(n)$ divides all coefficients of $ h(x)$, so $ f(n)|2^{kn}$ (coefficient of $ x^n$, since $ f(x)$ is monic).
So $ f(n) \equal{} \pm2^u$ (for some $ u\leq kn$)

Since $ f(0) \equal{} 0$ or $ f(n)|f(0)$, we get $ f(0) \equal{} 2^ub$ for some $ b\in\mathbb Z$

Let $ f(x) \equal{} xg(x) \plus{} 2^ub$. We know that :
1) $ \pm2^u \equal{} ng(n) \plus{} 2^ub$ and so $ 2^u | ng(n)$
2) $ 2^u | 2^kag(2^ka)$ $ \forall a$ such that $ f(a)\neq 0$ and so, thru lemma, $ 2^{\max(0,u \minus{} k)}$ divides all coefficients of $ g(2^kx)$.

Hence all the solutions :

Let any $ g(x) \equal{} \sum_{i \equal{} 0}^{n \minus{} 1}a_ix^i\in\mathbb Z[X]$ with $ a_{n \minus{} 1} \equal{} 1$ and let $ u\leq \min(v_2(ng(n)),k \plus{} ki \plus{} v_2(a_i))$ $ \forall i\in[0,n \minus{} 1]$. Then $ \boxed{f(x) \equal{} xg(x) \pm 2^u \minus{} ng(n)}$

sorry,pco...but about your lemma...what about $ d=2,P(x)=x^{2}+x $? :maybe:


Dear Mathlinkers,
let ABC be a triangle, (1) the incircle, I the center of (1), DEF the contact triangle of ABC, D', F' the antipoles of D, F wrt (1), D" the second point of intersection of AD' with (1), and B* the point of intersection of DF' and FD".
Prouve synthetically : AI is perpendicular to BB*.
Sincerely
Jean-Louis

Let $ DF\cap AI\equal{}\{P\}. PD''\cap (O)\equal{}\{F''\}$. We will show that $ F''\equiv F'.$
$ M\equal{}AD'\cap BC$. We have $ D,D'',M,P$ lies on $ (DM)$
So $ \angle D'D''F''\equal{}\angle PD''M\equal{}\angle PDM\equal{}\angle FDB\equal{}90^o\minus{}\angle B/2$
But $ \angle D'D''F'\equal{}\frac{1}{2}\angle FID\equal{}90^o\minus{}\angle B/2$ therefore $ F''\equiv F'$.
We get $ AI, FD, F'D''$ concur at $ P. BB*$ is the polar of $ P$ wrt $ (I)$ then $ BB*\perp IP$.
We are done.

Dear Livetolove and Mathlinkers,
thank you for your proof. I think that it is posible to avoid the concept of polar by using the Lascases's result.
Sincerely
Jean-Louis


Find all natural numbers n for which:

n2^(n-1) +1 is a perfect square

thanks

$ n2^{n\minus{}1}\plus{}1\equal{}k^2 <\equal{}> n2^{n\minus{}1}\equal{}(k\minus{}1)(k\plus{}1)$ we have that not both numbers $ k\minus{}1$ and $ k\plus{}1$ are divisible by $ 4$ so one of them is divisible by $ 2^{n\minus{}2}$ so for large $ n$ where by large i mean $ 6$ or greater we get easy contradiction because $ 2^{n\minus{}2}>2n\plus{}2$ easy to check the rest..$ 5$ is the only solution.

Let $ n2^{n \minus{} 1} \plus{} 1 \equal{} m^2$, where $ m\in\mathbb N$. We may assume that $ n\ge 3$, since $ n \equal{} 1,2$ doesn't work. Then $ m$ is odd; let $ m \equal{} 2k \minus{} 1$. Our equation becomes
\[ n2^{n \minus{} 3} \equal{} \left(\frac {m \plus{} 1}{2}\right)\left(\frac {m \minus{} 1}{2}\right) \equal{} k(k \minus{} 1)
\]
Hence $ (k,k \minus{} 1) \equal{} (x,y2^{n \minus{} 3})$ or $ (x2^{n \minus{} 3},y)$ for $ x,y\in\mathbb N$ such that $ xy \equal{} n$.

First let $ (k,k \minus{} 1) \equal{} (x,y2^{n \minus{} 3})$. Note that $ t < 2^{t \minus{} 3} \minus{} 1\,\forall t\ge 6$. This implies $ x\le n < 2^{n \minus{} 3} \minus{} 1\le y2^{n \minus{} 3} \minus{} 1 < y2^{n \minus{} 3} \plus{} 1 \equal{} x$, contradiction for $ n\ge 6$. Again, if $ (k,k \minus{} 1) \equal{} (x2^{n \minus{} 3},y)$ we get $ y\le n < 2^{n \minus{} 3} \minus{} 1\le x2^{n \minus{} 3} \minus{} 1\equal{}y$ for $ n\ge 6$, contradiction again. Thus $ n\le 5$. Simple casework shows that among $ n \equal{} 3,4,5$ only $ n \equal{} 5$ works.

great solutions

Beacuse of You I can learn interesting ideas


I don't think those are the sides of a triangle...

[quote="Hawk Tiger"]not true.a=1.5,b=0.5,c=0.5[/quote]

[quote="Hawk Tiger"]sorry for the typo.a=1.5,b=1.c=0.51[/quote]

I think for this value it is true

[quote="Jumbler"]Let $a,b,c$ be sidelengths of a triangle.

Show: $a^{3}+b^{3}+c^{3}-3abc\geq 2\max \{|a-b|^{3}, |b-c|^{3}, |c-a|^{3}\}$[/quote]

hmm...we use the fact that : $a^{3}+b^{3}+c^{3}-3abc\geq a(b-c)^{2}+b(c-a)^{2}+c(a-b)^{2}$

$\Rightarrow \sum{a^{3}}+3abc\geq \sum{ab(a+b}$, which is schur:)

and now the triangle ineq, so: $a>|b-c|$

$\Rightarrow a^{3}+b^{3}+c^{3}-3abc\geq |b-c|^{3}+|c-a|^{3}+|a-b|^{3}$

and now it remais us to prove that $|b-c|^{3}+|c-a|^{3}+|a-b|^{3}\geq 2\cdot max{|b-c|^{3},|c-a|^{3},|a-b|^{3}}$, and now we can asume without lack of generality that $|a-b| \geq |b-c| \geq |c-a|$. so it remais us to prove that:

$|b-c|^{3}+|c-a|^{3}\geq |a-b|^{3}$, in other words to prove that $|a-b|^{3}$ , $|b-c|^{3}$, $|c-a|^{3}$ can be the sides of a triangle, which can be proved easily i think :) but i don`t have any more time :)


function
real analysis
real analysis unsolved

Let $K$ be a subset of $\mathbb{R}^{d}$. Prove or disprove that $K$ is compact if and only if for any function $f: K\to K$ such that $\parallel f(x)-f(y)\parallel <\parallel x-y\parallel $ for all $x\ne y$ and for any $x_{0}\in K$ the sequence $x_{0},f(x_{0}),f(f(x_{0})),...$ is convergent.

I think a sequence increasing to $1$ (but not containing $1$) would be a counterexample in $\mathbb R$.

That "convergent" should refer to convergence in $K$.
It's still false. $\mathbb{Z}$ is a counterexample; all $f$ with that property are constant.


linear algebra
matrix
algebra
polynomial
search
function
integration

Let $A,B\in M_n (\mathbb{C})$ such that $|det(A+zB)|\leq1$, for any $z\in\mathbb{C}$ with $|z|=1$.
 Prove that $|det(A)|\leq1$  and  $|det(B)|\leq1$. ;)

Guess what.. I didn't see the $\det B$ at first, but it still works:

For every $|z|=1$ we have $|\det(zA+B)|=|z|^n\cdot\left|\det\left(A+\frac 1zB\right)\right|=\left|\det\left(A+\frac 1zB\right)\right|\le 1$.

[quote="grobber"]Just apply the Maximum Modulus principle to the polynomial $P(z)=\det(A+zB)$ :).[/quote]

  Grobber,can u elaborate.I'm afraid I don't this principle. :?

I did your Google search for you :):

[url]http://www.google.ro/search?hl=ro&q=maximum+modulus+principle&btnG=C%C4%83utare+Google&meta=lr%3Dlang_en[/url]

All you had to do was type "maximum modulus principle" in the Google search engine :).

The simplest proof is that nonconstant analytic functions map open sets to open sets.  This is a rather important property of analytic functions.

$p(z)=det(A+zB)=det(A)+\sum_{k=1}^{n}c(k)z^k$ with $c(n)=det(B)$

$|\int_{0}^{1}det(A+e^{i.q.x}B)dx|\leq \int_{0}^{1}|det(A+e^{i.q.x}B)|dx \leq 1$
where $q \in N$

$|det(A)+\sum_{k=1}^{n}c(k)\int_{0}^{1}e^{i.k.q.x}dx|\leq 1$

But for $1\leq k \leq n$, $\int_{0}^{1}e^{i.k.q.x}dx$ tend to $0$ when $q$ tend to +oo

This gives $|det(A)|\leq 1$

For  $|det(B)|\leq 1$ use post 4 of grobber

I think these proofs are more complicated than the problem askes. More generally, if $p$ is a polynomial which is at most 1 on the unit circle, then $ |p(0)|\leq 1$ and the leading coefficient of $p$ is at most 1 in absolute value. Why? Simply because they are Fourier coefficients of the polynomial. Thus each one of them can be expressed in the form $\frac{1}{2\cdot\pi}\int_{0}^{2\cdot\pi}{ p(e^{ix})e^{-ikx}dx}$. Now, apply modulus inequality.


How come, somtimes when I log on, I find that all the new posts that I haven't read have now become old posts (with a white tag instead of a yellow one)? I haven't clicked the mark all posts as read button, and it's not because I haven't signed on in a while, since, for example, just about 10 minutes ago, I closed the forum window by accident, and when I signed on again, all the posts are now considered read. Is it something with my computer?

This happens to me too, so I usually resort to reading the times of the posts.

I believe when you close the forum window, you are considered "logged out". And when you log out, all posts become read and then any posts made after the time you logged out are considered "unread" when you next sign on.


algebra
polynomial
algorithm
modular arithmetic
counting
distinguishability
induction

For a polynomial $ P(x)$ with integer coefficients, $ r(2i \minus{} 1)$ (for $ i \equal{} 1,2,3,\ldots,512$) is the remainder obtained when $ P(2i \minus{} 1)$ is divided by $ 1024$. The sequence
\[ (r(1),r(3),\ldots,r(1023))
\]
is called the [i]remainder sequence[/i] of $ P(x)$. A remainder sequence is called [i]complete[/i] if it is a permutation of $ (1,3,5,\ldots,1023)$. Prove that there are no more than $ 2^{35}$ different complete remainder sequences.

I think you are wrong. There are $ 2^{45}$ different complete remainder sequences.

The problem as listed in the book I was given has 35. It's possibly the book I have has a typo... I should note that at least one person (and possibly 2 or 3) got near-perfect scores on this test, so this problem was solved; on the TST itself, the given problem must have been correct.

I think the first thing to do is to check your proof again.

Yes, I am wrong.
My solution. We can consider $ x_k \equal{} 2^k \minus{} 1,k \equal{} 1,2,3,4$ and consruct
$ P(x) \equal{} a_0 \plus{} a_1(x \minus{} x_1) \plus{} a_2(x \minus{} x_1)(x \minus{} x_2) \plus{}a_3(x\minus{}x_1)(x\minus{}x_2)(x\minus{}x_3) \plus{} P_1(x)(x\minus{}x_1)(x\minus{}x_2)(x\minus{}x_3)(x\minus{}x_4)$.
For all odd x $ 1024|P_1(x)(x\minus{}1)(x\minus{}3)(x\minus{}7)(x\minus{}15).$
 If $ P(x)$ give complete remainders, then $ aP(x)\plus{}b$ give complete remainders too, if a -odd,b - even. It reduce to case, when
$ P(x)\equal{}x\plus{}(x\minus{}1)(x\minus{}3)(a_2\plus{}a_3(x\minus{}7))$. We have $ 2^{18}$ variants to reduce.
If $ a_2\equal{}a_2'\mod 128, a_3\equal{}a_3'\mod 16$, then $ P(x)\equal{}x\plus{}(x\minus{}1)(x\minus{}3)(a_2'\plus{}a_3'(x\minus{}7))\mod 1024$.
If $ a_3\not \equal{}0$, then $ P(x)\equal{}P(2^k\minus{}x)$ for some x and some k>1. Therefore we had not  completely remainders.
For any $ a_2$ (128 variants) $ P(x)\equal{}x\plus{}a_2(x\minus{}1)(x\minus{}3)$ had completely remainders.
Therefore exactly $ 2^{25}$ different completely remainders sequence.

still, the exponent is 35...so the problem is not solved yet

[quote="Rust"]
For all odd x $ 1024|P_1(x)(x \minus{} 1)(x \minus{} 3)(x \minus{} 7)(x \minus{} 15).$
[/quote]

Why? Take $ x\equal{}5$.

Yes. It is my mistake. For all odd x $ 2^{11}|(x\minus{}1)(x\minus{}3)(x\minus{}5)(x\minus{}7)(x\minus{}9)(x\minus{}11).$
Therefore P(x) equavalent to $ x\plus{}(x\minus{}1)(x\minus{}3)[a_2'\plus{}a_3'(x\minus{}5)\plus{}a_4'(x\minus{}5)(x\minus{}7)\plus{}a_5'(x\minus{}5)(x\minus{}7)(x\minus{}9)].$
$ 0\le a_2'<2^7,0\le a_3'<2^6,0\le a_4<2^3,0\le a_5'<2^1$.
Therefore number of complete remainders no more than $ 2^{18}*2^{7\plus{}6\plus{}3\plus{}1}\equal{}2^{35}.$
But all variants don't give complete remainders.

[hide]
Using the division algorithm, we have:

$ P(x) \equal{} b_1 \plus{} (x\minus{}1)(b_3 \plus{} (x\minus{}3)(b_5\plus{}(x\minus{}5)(b_7 \plus{} \cdots$
$ \plus{} (x\minus{}1021)(b_{1023} \plus{} (x\minus{}1023)(R(x)))\cdots)$

For some integers $ b_1, b_3, ... b_{1023}$ and $ R(x)$ a polynomial with integer coefficients. Now, we have the following congruences $ \pmod{1024}$:

$ b_1 \equiv r(1)$

$ 2b_3\plus{}b_1 \equiv r(3)$

$ 4\cdot 2 b_5 \plus{} 4 b_3 \plus{} b_1 \equiv r(5)$

$ \cdots$

$ 2^n n! b_{2n\plus{}1} \plus{}$ terms with $ b_i$ with $ i < 2n\plus{}1$ $ \equiv r(2n\plus{}1)$

$ \cdots$

Now, for every occurrence of $ b_{2k\plus{}1}$ in the above equations, it occurs as

$ 2^{k} \frac{n!}{(n\minus{}k)!} b_{2k\plus{}1}$

It is easy to show $ k! | \frac{n!}{(n\minus{}k)!}$ (i.e. the binomial coefficients are integers). Therefore, the above expression always has as many powers of 2 as $ 2^k \cdot k!$. On the other hand, for $ k > 5$ this power exceeds $ 1024$, so it makes no contribution to the congruence $ \pmod{1024}$!

Therefore the total number of complete remainder sequences is at most the number of ways to choose $ b_1$ through $ b_{11}$ that give distinct remainder sequences. Since the powers of $ 2$ associated with each of these is $ 0, 1, 3, 4, 7, 8$, respectively (that is, whenever $ b_i$ occurs it has at least that many powers of 2 in its coefficient), $ b_1$ through $ b_{11}$ have $ 2^{10}, 2^{9}, 2^{7},2^6, 2^3,2^2$ different choices respectively that gives distinguishable remainder sequences.

For example, since $ b_5$ always goes with at least $ 2^3$, any $ b_5 ' \equiv b_5 \pmod{2^7}$ will give the same remainder sequence, so there are at most $ 2^7$ distinguishable choices for $ b_5$.

Now, at this point we have at most $ 2^{10\plus{}9\plus{}7\plus{}6\plus{}3\plus{}2} \equal{} 2^{37}$ distinct complete remainder sequences. To show that there are only at most $ 2^{35}$, we need two improvements.

First, $ b_1$ must be odd, since $ a_1$ is odd. There are thus only $ 2^9$ choices for $ b_1$.

Next, note that $ b_3$ is the only other term in any of the sums that is ever multiplied by no more than a factor of 2. So, if $ b_3$ is even, then all $ r(2i\plus{}1)$ are congruent to $ b_1$ $ \pmod{4}$, which contradicts completeness. Therefore $ b_3$ is odd and there are only $ 2^8$ choices for $ b_3$.

We have made the desired improvements and are done.

Note: this interpolation method is pretty useful for modular problems. For example, see http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=344711 [/hide]

[hide]I think we can strengthen this to $2^{32}$.

First note that $P(x+2^5 k)\equiv P(x)+2^5 k P'(x)\pmod{2^{10}}$. If $x$ is an odd integer, then because the numbers $P(x+2^5 k)\pmod{2^{10}}$ are distinct for $1\le k\le 2^5$, $P'(x)$ must be odd (and we only care about its value $\pmod{2^5}$).

Furthermore, suppose we know what $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$ are. If we also know $P(1)\pmod{2^{10}}$, then by induction on $1\le j\le5$ we know what $P(1),P(3),\ldots,P(2^j-1)$ are modulo $2^j$. Indeed, the base case is trivial, and if we know $P(1),P(3),\ldots,P(2^j-1)\pmod{2^j}$ then
\[P(x+2^j k)\equiv P(x)+2^j k P'(x)\pmod{2^{j+1}}\]for all $0\le k\le1$ and odd $1\le x\le 2^j-1\le 2^5-1$. Thus we know $P(1),P(3),\ldots,P(2^5-1)\pmod{2^5}$ and $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$, so by the first paragraph we know $P(1),P(3),\ldots,P(2^{10}-1)\pmod{2^{10}}$ by taking all $1\le k\le 2^5$ and odd $1\le x\le 2^5-1$.

Clearly there are $2^9$ ways to choose $P(1)$, and the number of ways to choose a sequence $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$ for $P'\in\mathbb{Z}[x]$ is just the number of ways to choose $P'(1),P'(2),\ldots,P'(2^5)\pmod{2^5}$ divided by $2$ (since we know that $2|P'(a)-P'(b)$ if $a,b$ are both odd, and there are clearly just as many sequences with $P'(1)$ odd as with $P'(1)$ even). Writing the Newton interpolation polynomial
\[P'(x)=\sum_{k=0}^{2^5-1}\Delta^k[P'](0)\binom{x}{k}\equiv\sum_{k=0}^{2^5-1}a_k\binom{x}{k}\pmod{2^5}\forall x\in\mathbb{Z},\]we need $v_2(a_k)\ge v_2(k!)$ for all $0\le k\le 2^5-1$ (all other terms in the denominators are invertible; we can see the equivalence to being in $\mathbb{Z}[x]$ by considering the $[x^k]$ coefficients in reverse order), so for $0\le k\le1$ we have $2^5$ choices for $a_k\pmod{2^5}$, for $2\le k\le3$ we have $2^4$ choices, for $4\le k\le 5$ we have $2^2$ choices, for $6\le k\le 7$ we have $2^1$ choices, and for $8\le k\le 2^5-1$ we have $2^0=1$ choice. Thus we have an upper bound of
\[2^9\cdot\frac{1}{2}\cdot 2^{2(5+4+2+1)}=2^{32}.\][/hide]

[b]Edit.[/b] This is wrong; see below.

[hide]Now I think we can even strengthen this to $2^{20}$, but this feels pretty fishy so hopefully people can check it. :maybe:

[b]Lemma:[/b] If $Q\in\mathbb{Z}[x]$, there are at most (actually, exactly, but this is unnecessary for the problem) $2^{12}=2^{5+4+2+1}$ possible sequences $(Q(1),Q(3),\ldots,Q(2^5-1))\pmod{2^5}$.

[i]Proof:[/i] Let $R(x)=Q(2x+1)$, so Newton interpolation yields
\[Q(x)=R\left(\frac{x-1}{2}\right)=\sum_{k\ge0}\Delta^k[R](0)\binom{\frac{x-1}{2}}{k}=\sum_{k\ge0}a_k\binom{\frac{x-1}{2}}{k},\]where it's clear that
\begin{align*}
(a_0,a_1,\ldots,a_{2^4-1})\pmod{2^5}
&\longleftrightarrow (R(0),R(1),\ldots,R(2^4-1))\pmod{2^5} \\
&\longleftrightarrow(Q(1),Q(3),\ldots,Q(2^5-1))\pmod{2^5}.
\end{align*}Suppose for the sake of contradiction that $v_2(a_k)<v_2(k!)+k$ for some $k\ge0$, and let $k_0$ be the largest such $k$. Then $[x^{k_0}]Q(x)\not\in\mathbb{Z}$, which is impossible. Thus $v_2(a_k)\ge v_2(k!)+k$ for all $k\ge0$, so we have $2^5$ choices for $a_k\pmod{2^5}$ for $k=0$, $2^4$ choices for $a_k\pmod{2^5}$ for $k=1$, $2^2$ choices for $a_k\pmod{2^5}$ for $k=2$, $2^1$ choices for $a_k\pmod{2^5}$ for $k=3$, and $2^0$ choices for $a_k\pmod{2^5}$ for $k\ge4$, for a total of at most $2^{5+4+2+1}=2^{12}$ possibilities.$\blacksquare$

As proven in the first half of my previous post, there's a bijection between complete remainder systems and $2^4+1$-tuples
\[(P(1)\pmod{2^{10}},P'(1)\pmod{2^5},P'(3)\pmod{2^5},\ldots,P'(2^5-1)\pmod{2^5})\]such that $P(1),P'(1)$ are odd (and thus $P'(3),\ldots,P'(2^5-1)$ are also odd).

Hence there are $2^9$ choices for $P(1)\pmod{2^{10}}$ and at most $\frac{2^{12}}{2}$ choices for $(P'(1)\pmod{2^5},P'(3)\pmod{2^5},\ldots,P'(2^5-1)\pmod{2^5})$ by the lemma and symmetry (since $Q(1)$ is obviously equally often odd as even over all polynomials with integer coefficients), so finally, there are at most $2^{9+12-1}=2^{20}$ complete remainder systems in total.[/hide]

[b]Edit.[/b] This is wrong; see below.

[quote="math154"]Furthermore, suppose we know what $P'(1),P'(3),\ldots,P'(2^5-1)\pmod{2^5}$ are. If we also know $P(1)\pmod{2^{10}}$, then by induction on $1\le j\le5$ we know what $P(1),P(3),\ldots,P(2^j-1)$ are modulo $2^j$. Indeed, the base case is trivial, and if we know $P(1),P(3),\ldots,P(2^j-1)\pmod{2^j}$ then
\[P(x+2^j k)\equiv P(x)+2^j k P'(x)\pmod{2^{j+1}}\]for all $0\le k\le1$ and odd $1\le x\le 2^j-1\le 2^5-1$.[/quote]Wow, this is one of the stupidest things I've ever written. Fortunately, we can use the same Newton interpolation method to prove that $2^{35}$ is in fact [url=http://arxiv.org/pdf/1008.1012.pdf]the best bound possible.[/url]

Shift everything by $1$ so that we're working with $(r(0),r(2),\ldots,r(2^{10}-2))$ and complete remainder sequences are instead permutations of $(0,2,\ldots,2^{10}-2)$. (More concretely, take $P(x)\to P(x+1)-1$.) This isn't very important but it simplifies Lemma 1 slightly. Let $C$ denote the set of polynomials yielding complete remainder sequences. For any $P\in\mathbb{Z}[x]$, let $R(P)$ be the remainder sequence of $P$ and for convenience, let $R(S)=\{R(P):P\in S\}$ for any set $S$.

[b]Lemma 1.[/b] $P(x) = a_0+a_1x+\cdots+a_dx^d\in\mathbb{Z}[x]$ lies in $C$ iff $2\mid a_0$ and $2\nmid a_1$.

[i]Proof.[/i] First we note that $P$ maps even integers to even integers iff $P(0)$ is even, so $P$ yields a complete remainder sequence iff $2\mid a_0$ and $P$ is injective mod $2^{10}$ over even residues. But \[ \frac{P(2u) - P(2v)}{2u-2v} = \sum_{k=1}^{d}a_k \frac{(2u)^k-(2v)^k}{2u-2v}\equiv a_1\pmod{2} \] for distinct integers $u,v$, so $P$ is injective iff $2\nmid a_1$ (if $2^{10}\mid P(a)-P(b)$ for two distinct even residues $a,b$, we must have $2\mid a_1$, while if $2\mid a_1$, we get $2^{10}\mid P(2^{n-1})-P(0)$), as desired. $\blacksquare$

[b]Lemma 2.[/b] Call a polynomial $P\in\mathbb{Z}[x]$ [i]reduced[/i] if $0\le [x^k]P<2^{10-k-v_2(k!)}$ for all nonnegative integers $k$. If $T$ denotes the set of reduced polynomials, then every remainder sequence is achieved by a unique polynomial $P\in T$. As a simple consequence, $R:T\to R(\mathbb{Z}[x])$ is a bijection.

[i]Proof.[/i] Take a remainder sequence $\alpha\in R(\mathbb{Z}[x])$ and polynomial $P(x) = a_0+a_1x+\cdots+a_dx^d\in\mathbb{Z}[x]$ of degree $d$ such that $\alpha=R(P)$. Define the two-step finite differences $b_k = \Delta^k_2[P](0) \equiv \Delta^k_2[\alpha](0) \pmod{2^{10}}$. By Newton interpolation, $P(x) = \sum_{k=0}^{d} b_k \binom{x/2}{k}$. Since $a_d\in\mathbb{Z}$, we must have $2^d d!\mid b_d$; by a simple reverse induction, we get $2^k k!\mid b_k$ for all $k$. Let $c_k = b_k/(2^k k!)$, extend indices so that $a_k,b_k,c_k=0$ for $k>d$, and note that $\alpha$ uniquely determines $(b_k\pmod{2^{10}})_{k\ge0}$ (and vice versa). It thus suffices to show that exactly one choice of $(c_k)_{k\ge0}$ leads to a reduced polynomial $P\in T$. But $v_2(2^k k!) = k+v_2(k!)$, so for fixed $k$, $b_k\pmod{2^{10}}$ uniquely determines $c_k\pmod{2^{10-k-v_2(k!)}}$ (and vice versa). Yet the polynomials $2^k k! \binom{x/2}{k} = x(x-2)\cdots(x-2k+2)$ form a basis of $\mathbb{Z}[x]$, so for fixed $\alpha$, exactly one sequence $(c_k)_{k\ge0}$ corresponds to $(a_k)_{k\ge0}$ with $P\in T$, and we're done. $\blacksquare$

Combining the two lemmas, we see that $|R(C)|$ is equal to the number of $P\in T$ with $2\mid a_0$ and $2\nmid a_1$, or equivalently,
\[ \frac{1}{2}\frac{1}{2}\prod_{k\ge0}2^{\max(10-k-v_2(k!),0)} = 2^{-1-1+10+9+7+6+3+2} = 2^{35}, \]as desired.

[b]Comment.[/b] It's not hard to find the number of distinct $(r(1),r(2),r(3),\ldots,r(2^{10}-1))\pmod{2^{10}}$ by writing $P(x) = P_0(x)(x-1)^{2^{10}}+P_1(x) x^{2^{10}}$---we can work with $P_0$ and $P_1$ separately for the even and odd residues, respectively, to get $(2^{37})^2$ sequences.

Brilliant Problem. It is same as Rust's proof, but I'm writing this proof hoping this is more readable.

Following terms are divided $2^{10}=1024$ when $x$ is odd.
\begin{align*}
(x-1)(x-3)(x-5)(x-7)(x-9)(x-11)\\
2^2 \times (x-1)(x-3)(x-5)(x-7)(x-9)\\
2^3 \times (x-1)(x-3)(x-5)(x-7)\\
2^6 \times (x-1)(x-3)(x-5)\\
2^7 \times (x-1)(x-3)\\
2^9 \times (x-1)
\end{align*}
Thus we can reduce any polynomial into $a_5 x^5 + a_4 x^4 + a_3 x^3 +a_2 x^2 + a_1 x^1 + a_0$ with
\begin{align*}
0 \le a_5 < 2^2, \; 0 \le a_4 < 2^3 ,\; &0\le a_3 < 2^6\\
0 \le a_2 < 2^7, \;0 \le a_1 < 2^9 ,\; &0\le a_0 < 2^{10}
\end{align*}
Since $P($odd$)$ is odd, $a_0+a_1+...+a_5$ is odd. Also, you can easily see that $P(x+512)-P(x)$ is $2$ times odd number. This gives $a_5+a_3+a_1$ even. Here we get $2^{2+3+6+7+9+10} / 2^2 = 2^{35}$ possibility at most. (Note that not every polynomial gives such nice remainders.)


[img]http://www.mathlinks.ro/Forum/viewtopic.php?mode=attach&id=14955[/img]

 :(

$ (a\plus{}b)^2\minus{}2ab(1\plus{}\cos C) \equal{} c^2$ and $ ab \sin C \equal{} 2pr$, so

$ (a\plus{}b)^2\minus{}c^2\equal{}4pr \frac{1\plus{}\cos C}{\sin C}$ but $ \frac{1\plus{}\cos C}{\sin C} \equal{} \cot \frac{C}{2}$, so

$ \cot \frac{C}{2} \equal{} \frac{(a\plus{}b)^2\minus{}c^2}{4pr}$ then we can costruct $ \angle BCA$ and we know $ h_a \equal{} \frac{(a\plus{}b\plus{}c)r}{c}$.

1 first we draw a segment KL with length b+a and mark $ \frac {b \plus{} a \minus{} c}{2}$  from  K on the opposite side L on line KL to other point say M
2 now we construct a circle such  that is tangent to KL at M with radius r
3 from K we draw the other tangent KH and extend it to point G such that KG=KL
4 now we take distance c and mark it on GL from K at point say W
5from W we draw a parallel to KG and let it intersect at KL at R
RWK is the required triangle

4 now we take distance c and mark it on GL from K at point say W

?

:rotfl:

[quote="jrrbc"]4 now we take distance c and mark it on GL from K at point say W

?

[/quote]
why what is the problem have i made a silly mistake?? if i have not then  :P  and if i have then :oops:

4 now we take distance c and mark it on GL from K at point say W

now we take distance c and mark it on GL  (from G or from L ?)
from K at point say W  ???

 :(

if you really have a problem then please elaborate else [size=200]DON'T SPAM[/size]

4 now we take distance c and mark it on GL from K at point say W

now we take distance c and mark it on GL (from G or from L ?)
from K at point say W ???

[b]i have written FROM K[/b]

c< b+a ?

i think with your construction b+a<c    sorry, but forget about

 :(

actually c<b+c and thats why the thing is possible
put the pointed end of the compass on K
then set distance c on the compass
now let this arc cut GL at W
this is possible as (b+a) sin (c/2) $ \le$ c :lol:


trigonometry
LaTeX
geometry unsolved
geometry

Given a triangle $ ABC$ that $ \hat{ABC}\equal{}2\hat{ACB}\equal{}40^o$ $ D$ is a point that outside triangle on side $ BC$ that $ \hat{BAD}\equal{}2\hat{ABC}$ and $ AB\equal{}AD$ Find $ \hat{BCD}$

Oh! I think you are mistake. In your suppose have contradict each other. You shoud see your post.

No [i]thanhnam2902[/i], everything is correct. I  found it by trigonometry, it is $ 10^\circ$, but I haven't found a syntethic solution yet.

[quote="suleymansoyler"]I found without trigonometry...(please click .gif and wait a little, i can't use latex just now,but i'm learning.)[/quote]

Anyway Nice proof without words  :) .But Which programs did u use to make the diagram and tomake the gif.?

[p.s. I use Cabri to create diagrams]

Hi Ahiles! $ \angle BCD \equal{} 10^0$ is true. I will post the solution of this problem.

Since all angles are divisible by 20, it is a good idea to use a regular 9 gon (nonagon) since any angle from a vertex intercepting n sides is 20n degrees.
Suleymansoyler's solution utilizes only 3 sides of the regular 9 gon.


(I looked for a thread on this book, but couldn't find one, so if somebody knows of an existing one, please let me know!)

I was having trouble with the following example problem (3.4, the very first example):

Let $ f : \mathbb{N} \rightarrow \mathbb{N}$ be a function satisfying:
$ f(1) \equal{} 1$
$ f(2n) \equal{} f(n)$
$ f(2n\plus{}1) \equal{} f(2n) \plus{} 1$
for all positive integers n. Find the maximum value of $ f(n)$ where $ 1 \leq n \leq 1994$

They used induction to prove that $ f(n)$ is equal to the number of 1's in the binary representation of n. I'm familiar with induction, but they didn't explicitly state the inductive hypothesis used, so I was having trouble following it. If you're familiar with this one, any help would be appreciated! (the book didn't give the source, so I didn't have any luck looking it up).

The inductive hypothesis is $ f(n) \equal{} \text{number of 1s in binary expansion of } n$. You do it by strong induction and then considering cases where $ n$ is even or odd.

Ah, I understand it now. I wasn't familiar with strong induction. Thanks!

Edit: Nevermind, I'm confused again.

Through strong induction, we're supposed to show that if it's true for all integers less than n, then it's true for n. But it seems like each case (even or odd) is incomplete without the other.

For example, the book says that if n is even, then $ n \equal{} 2m$ for some integer m, which is obviously true, and explains why they both have the same number of 1's in binary expansion. From the given properties, $ f(n) \equal{} f(2m) \equal{} f(m)$ It then says that if it's true for m (our inductive hypothesis), which is clearly smaller than n, than it's true for n, which is our "inductive step". But what if m is odd? For example, when n = 6, then we have $ f(6) \equal{} f(3)$. But we haven't actually proved it true for n=3.

The same goes for the odd cases. If $ n \equal{} 2m \plus{} 1$, then f(n) = f(m) + 1. But if m is even, then this case of the induction doesn't cover it.

So isn't it some sort of circular reasoning?

(I'm not trying to argue against the solution, by the way. I'm just trying to understand it)

What if both cases are considered together for the induction?  With casework, we can prove the odd and even values for m.


Correct, althugh there was an extra step in there...it's so miniscule it won't make much of a difference (and it'll get you the same answer) but oh well.


limit
geometric series
calculus
calculus computations

How can this limit be solved $\lim_{n\to \infty}n\; sin(2 \pi e n!)$ ?

The limit is $2\pi.$

The key observation is that we can write $n!e=m+x$ where $m\in\mathbb{Z}$ and $\frac1{n+1}<x<\frac1n.$

In particular,

$x=\sum_{k=1}^{\infty}\frac1{(n+1)(n+2) \cdots(n+k)}$ and

$\frac1{n+1}<x<\sum_{k=1}^{\infty}\frac1{(n+1)^{k}}= \frac1n.$

Using your hint the solution is straightforward. But I have 2 essential questions :
1) Why en! = m+x
2) Why $\sum_{k=1}^{\infty}\frac{1}{(n+1)^{k}}\n=\frac{1}{n}$ ?  :idea:

1) because any real number, such as $en!$, can be split into integer and fractional parts.

2) because the sum of a geometric series is (initial term)/(1-common ratio).


We randomly select  4  prime numbers without replacement from the first  18  prime numbers. What is the probability that the sum of the four selected numbers is odd? Express your answer as a common fraction in lowest terms.

[hide="solution"]There must be one 2 included in the 4 primes.  The probability that a 2 is never chosen is $\left(\frac{17}{18}\right)^{4}$.  Therefore the probability that a two is chosen is $\boxed{1-\left(\frac{17}{18}\right)^{4}}$[/hide]

[hide]well, you have to have a 2, so lets assume you get a 2, then there are 17 choices left, and you can choose any 3 so 17C3, there are a total of 18C4 different possibilities so (17C3)/(18C4) is 2/9[/hide]

[hide]
The only way it will be odd is if 2 is one of the prime numbers chosen. So, 1/18 * 4 because you have 4 shots to get 2.
The answer is $\frac{2}{9}$.[/hide]


inequalities
logarithms
inequalities unsolved

Find $ \max(k) \in \mathbb{R}$ that satisfies the equation
\[ \sum_{cyc}\left(\frac{a}{b\plus{}c}\right)^k\geq2\]
for all $ a,b,c\geq0$.

I think the $ max$    $ k$ is which satisfying $ 2^k\equal{}1.5$ so $ k$ is about $ 0.58496249$
I will tell you why when you ask because the solution is very long and possibly wrong :D  :D

[quote="Unidranix"]I think the $ max$    $ k$ is which satisfying $ 2^k \equal{} 1.5$ so $ k$ is about $ 0.58496249$
I will tell you why when you ask because the solution is very long and possibly wrong :D  :D[/quote]
So you mean $ max(k)\equal{}log_{2}{3}\minus{}1$, right?
Can you post your solution, please? Since I would like to see a solution.
Thanks anyway.

[quote="Unidranix"][hide="Proof"]$ \[ \sum_{cyc}\left(\frac {a}{b \plus{} c}\right)^{k} \equal{} \[ \sum_{cyc}\left[1 \plus{} \left(\frac {a}{b \plus{} c} \minus{} 1\right)\right]^{k}$
Because:  $ \frac {a}{b \plus{} c} \minus{} 1\ge \minus{} 1$ so by bernoulli inequality:
$ \equal{} \[ \sum_{cyc}\left[1 \plus{} \left(\frac {a}{b \plus{} c} \minus{} 1\right)\right]^{k}\ge\[ \sum_{cyc}\left[1 \plus{} k\left(\frac {a}{b \plus{} c} \minus{} 1\right)\right]$
$ \equal{} 3 \plus{} k\left(\sum_{cyc}\left(\frac {a}{b \plus{} c}\right) \minus{} 3\right)$
By nesbitt inequality:
$ \equal{} 3 \plus{} k\left(\sum_{cyc}\left(\frac {a}{b \plus{} c}\right) \minus{} 3\right)\ge3 \plus{} k\left(\frac {3}{2} \minus{} 3\right)$
$ \equal{} 3 \minus{} 1.5k$
Therefore, [size=150][i]L.H.S[/i][/size]$ \ge3 \minus{} 1.5k$
                [size=150][i]L.H.S[/i][/size]$ \ge2$
So I think the max k is $ \frac {2}{3}$.[/hide]

Done

[hide="P.S"]First time I use the inequality:
$ \[ \sum_{cyc}\left(\frac {a}{b \plus{} c}\right)^{k}\geq\frac {3}{2^n}$
But later, I found that this inequality only works for $ n\ge\frac {2}{3}$
 :blush:  :blush:  :blush:  :blush:
[/hide]

[hide="Is this spam?"]By the way, can anyone help me? [url]http://www.mathlinks.ro/viewtopic.php?t=277766[/url][/hide][/quote]
How could that be possible? Try $ a \equal{} b \equal{} c \equal{} 1$, then we have LHS$ \equal{} \displaystyle3\left(\frac {1}{2}\right)^k$.
Since we want it to be at least $ 2$. So $ \displaystyle3\left(\frac {1}{2}\right)^k\geq2$, that is $ \displaystyle k\leq\log_{2}{3} \minus{} 1 < \frac {2}{3}$

Edit: Since the inequality holds when $ \displaystyle k\equal{}\frac{1}{2}$. So $ \displaystyle\frac{1}{2}\leq max\left\{k\right\}\leq\log_{2}{3}\minus{}1$, that is, it is enough to consider when $ 0<k<1$
So actually by Bernoulli's inequality, we have $ \[ \sum_{cyc}\left[1 \plus{} \left(\frac {a}{b \plus{} c} \minus{} 1\right)\right]^{k}\le\[ \sum_{cyc}\left[1 \plus{} k\left(\frac {a}{b \plus{} c} \minus{} 1\right)\right]$ which is not useful here.


abstract algebra
group theory
superior algebra
superior algebra unsolved

if abelian group has subgroups of order m,n respectively. then show it has subgroup of order least common multipleof m and n.

Classification of abelian groups (or some workaround with Sylow theorems) even shows that there is a subgroup for all divisors of group order.


algebra
polynomial
calculus
integration
induction
real analysis
real analysis unsolved

Hi guys, i know there are a few integral rules to prove this, however, i'm wondering if this can be done through induction?

[img]http://i3.photobucket.com/albums/y82/fuzzfuzz/proof3.jpg[/img]

how about an approximation of this: [img]http://i3.photobucket.com/albums/y82/fuzzfuzz/proof3.jpg[/img]

As for what is true - you can say this:

As $n\to\infty,\,\sum_{i=1}^ni^b=\frac1{b+1}n^{b+1}+O(n^b),$ provided $b>-1.$

The cases of $b=1,\,b=2\,$ and $\b=3.$ should be at least a little bit familiar.


Let P be a polynomial with positive coefficients. Prove that if P(1/x) \geq 1/P(x) holds for x=1, then it holds for every x>0

please be carefull when posting ...

you might mean x \geq 1 rather than x=1, in which case the problem is trivial, because P(x)P(1/x) \geq 1 than it's obvious that P(1/x) P(x) \geq 1 for all 0<x<1.

Yes, well that's how I found the problem the problem . x=1 Maybe there is a mistake.

where did you find this problem anyway ?

It is very simple problem. And, of cause, x=1.

Let P(x)=anxn+...+a1x1+a0.

P(x)P(1/x)=\sum aiaj(xi-j+xj-i) \geq \sum aiaj*2 = P(1)*P(1/1) \geq 1 !!!

right ... anyway you like it the problem is very easy.


$ n \equal{} \sum_1^{(n \minus{} 1)/2}C_n^{2i}(4i \minus{} n)$

$ n > 2, n$ is odd.

Is it true? It is so funny.

Yes this formula holds.

Let's prove it!

$ n \equal{} \sum_1^{(n \minus{} 1)/2}\binom{n}{2i}(4i \minus{} n) \equal{} 2\sum_1^{(n \minus{} 1)/2}(\binom{n}{2i}2i) \minus{} n\sum_1^{(n \minus{} 1)/2}\binom{n}{i} \equal{} 2n\sum_1^{(n\minus{}1)/2}\binom{n\minus{}1}{2i\minus{}1} \minus{} n(2^{n\minus{}1}\minus{}1) \equal{} 2n2^{n\minus{}2} \minus{} n2^{n\minus{}1} \plus{} n \equal{} n$

PS: It's true that :$ \sum_1^{(n \minus{} 1)/2}(\binom{n}{2i}2i) \equal{} n\sum_1^{(n\minus{}1)/2}\binom{n\minus{}1}{2i\minus{}1}$ because in the LHS we have the number of ways of forming a group of even size and then choosing one of it's members as a leader and in the RHS we have the number of ways of choosing a leader out of $ n$ people and then forming a group of odd size with the remaining $ n\minus{}1$


geometry
trigonometry
geometric transformation
reflection
circumcircle
incenter
similar triangles

Let triangle ABC, and incircle I is tangle BC,CA,AB at X,Y,Z respectively.
Let AA', BB' , CC' is altitude from vertex A,B,C to BC,CA,AB respectively/
Let M,N,P is incircle of triangle AB'C' , BC'A' , CA'B'
1)Prove that M,N,P is orthocenter of triangle AYZ,triangle BZX,triangle CXY
2)Prove that the common tangent outside difference BC of circle (N) and circle (P) pass the orthocenter of triangle XYZ

1) From the similar triangles $\triangle AB'C' \sim \triangle ABC,$ it follows that: $\frac{_{AM}}{^{AI}}=\frac{_{B'C'}}{^{BC}}=\cos A.$ Since $AI$ is the circumdiameter of $\triangle AYZ$ issuing from $A,$ we deduce that $M$ is the orthocenter of $\triangle AYZ.$ Analogously, $N,P$ are the orthocenters of $\triangle BZX$ and $\triangle CXY$

2) $M,N,P$ are the reflections of $I$ across $YZ,ZX,XY.$ If $U$ denotes the orthocenter of $\triangle XYZ,$  then $M,N,P$ are the circumcenters of $\triangle YUZ,$  $\triangle ZUX$ and $\triangle XUY,$ i.e. sidelines of $\triangle MNP$ are the perpendicular bisectors of $UX,UY,UZ$ $\Longrightarrow$ reflection of $U$ across $NP$ lies on $BC,$ i.e. $U$ lies on the common external  tangent of $(N),(P),$ different from $BC.$ Hence, common external tangents of $(M),$ $(N),$ $(P),$ different from $BC,CA,AB,$ concur at $U.$

Dear Luis and mathlinkers,
thank Dear Luis for given this link for a future article.
You can have a look on
http://perso.orange.fr/jl.ayme   vol. 5  the Feuerbach-Ayme theorem
Very sincerely for your help
Jean-Louis

(1)
Let $N$ be the orthocenter of $\triangle BGK$ and then $\triangle NBM\sim\triangle IBG$
$\triangle GBM\sim\triangle CBF$ $~$ $\Longrightarrow$ $~$ $BN/BI=BM/BG=BF/BC$ and $\triangle NBF\sim\triangle IBC$
$\angle BFN=\angle ICB$ , $\angle BFD=\angle BCA$ and then $FN$ bisect $\angle BFD$
Thus, $N$ is the incenter of $\triangle BFD$ and likewise, the same is true for the others.

[quote="Luis González"] $\frac{_{AM}}{^{AI}}=\cos A.$ Since $AI$ is the circumdiameter of $\triangle AYZ$ issuing from $A,$ we deduce that $M$ is the orthocenter of $\triangle AYZ.$ [/quote]
Why?

@mudok

Because in an arbitrary $\triangle ABC$ with orthocenter $H$ and circumradii $R$, $AH=2R\cos A$ or $AH=2R\cos (180^\circ-A)$.

I think that in his solution, Luis assumed that $A<90^\circ$, which is without loss of generality, so $M$ is the orthocenter of $\triangle AYZ$.


Find all the quadruples $(x, y, z, p)$ of positive integers such that $x > 2$, the number $p$ is prime and $x^{y}= p^{z}+1.$

I don't understand... isn't it Mihalescu's?

Right! But I want an elementary solution and because I posted in Forum index » High School » Pre-Olympiad.


limit
trigonometry
calculus
calculus computations

Find the limit:

$ \lim_{n\to \infty}\Big [{\prod_{i\equal{}3}^{n}{\cos{\frac{\pi}{i}}}}\equal{}\cos{\frac{\pi}{3}}\cdot \cos{\frac{\pi}{4}}\cdots \cos{\frac{\pi}{n}}\Big ]$


vector
linear algebra
matrix
algebra
polynomial
geometry
function

How many lines can one place in $\mathbb R^n$ so that all angles between them are the same? I know the answer for $n=2,3$ and $7$ ($3$, $6$, and $28$ respectively). A colleague of a friend of mine told me that the answer for $n=4$ is $6$ and for $n=5$ is $10$, though I haven't verified the proof. For an arbitrary $n$, I know only that the answer is between $n+1$ and $\frac{n(n+1)}{2}$.

This is an interesting question.

I've been using strongly regular graphs to look for examples; I think I can verify $f(5)\ge10$ and $f(6)\ge16$.

For those 10 vectors in 5-space: I don't know what they are, but their matrix of inner products is $3I+P-Q$, where $P$ is the matrix of a Petersen graph and $Q$ is the matrix of its complement. This matrix has eigenvalues 6 and 0, each of multiplicity 5. Since it has rank 5, it should be possible to write it as the product of a $5\times10$ and its transpose.

For 16 vectors in 6-space, I have $3I+Q-P$, where $P$ is the graph on 16 vertices with valence 5 and no triangles and $Q$ is its complement: $P^2=5I+2Q$.
$Q-P$ has eigenvalues $5$ with multiplicity $6$ and $-3$ with multiplicity $10$, so $3I+Q-P$ has rank 6.

The graphs don't have to be strongly regular, but there is a graph marking the signs of the inner products; I'm using strongly regular graphs because it's easy to calculate minimal polynomials. In general you get third degree polynomials; the two examples above simplify to degree 2.

Using the complete graph gets you the disallowed solution of setting all the lines equal; using it the other way gets you the lower bound $f(n)\ge n+1$.
One basic fact about $f$: it is a nondecreasing function.

How do you get that upper bound? What does the example at 7,28 look like? I don't expect the geometry to generalize, but there might be something to look for in the graph.

[quote="jmerry"]
How do you get that upper bound? What does the example at 7,28 look like? [/quote]
The upper bound follows from [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=33713]my discussion with remgenesis[/url]: if a configuration of more than $\frac{n(n+1)}{2}$ lines had existed, one would be able to construct an example when the global maximum of his function is attained at a point with too many non-zero $p_j$ in a way similar to my construction of the matrix of rank $2$ that requires $3$ non-zero $p_j$. Probably there exists a less roundabout proof but that is how the problem appeared. As to $28$ lines in $\mathbb R^7$, just take the lines through the center and the midpoints of $1$-dimensional edges of the regular $7$-dimensional simplex. Unfortunately, for $n\neq 7$ this construction results in $2$ different angles.


geometry
3D geometry
tetrahedron
perimeter
advanced fields
advanced fields unsolved

you know that there is cute result that in 2dimension convex region for every $n$ there is n-gon billiard motion.is it true for higher dimension?

"bounded convex region", I suppose.

Consider the regular tetrahedron with the base at $xy$-plane. If a billiard ball never hits the base, then each collision decreases the $z$-component of its velocity. Therefore, no periodic trajectory can avoid touching the base. For the same reason such a trajectory must hit the other faces of the tetrahedron. Thus the answer is no for $n=3$.

Now what if the boundary is smooth? We'll definitely have a positive answer for $n=3$ (just consider the triangle with maximal perimeter) but the case $n=4$ is not so obvious ;)


analytic geometry
geometry
3D geometry
icosahedron
USAMTS
search
inequalities

That's not fair because there may be a great problem that can be trivialized by a very obscure, unknown formula that can be cited.

Pretty much, to trivialize a problem, a citation would have a formula or statement of some sort that corresponds identically to what the problem is asking.  For example, if you tell a bunch of first graders to find the sum $ 1^2\plus{}2^2\plus{}3^2\plus{}\cdots \plus{}100^2$, someone could trivialize it by just pulling out the formula for the sum of squares.  Of course, this is just a simple example.  On the other hand, on round 2 problem 5, it was okay to cite the coordinates of the icosahedron because it still took some more steps to solve the problem.  So basically, if a problem says:  Given *something* find *something else* and you cite something that says:  Given *something* then *something else* is equal to _______ , it's probably trivializing it.

So if you trivialize a problem, you won't get credit? I don't mean trivializing as in a "one-formula" trivializing but making the problem significantly simpler.

I'm not too sure if points will be deducted or not, but if you cite something like a theorem or equation, it's always better to find a resource that has a proof, and then put that proof into your solution.

Well, personally, I'd be kind of wary if some obscure formula completely trivialized the problem. But, if whatever is cited(especially if it's a formula!) is not proven at the same source as where you get it, I'd prove it.

Your time would be better spent looking for elementary solutions that don't rely on nontrivial results that you cannot prove, than asking these questions. Such things will only matter if you have no such solution at the deadline, in which case your only choice would be to submit your solution relying on whatever, and to hope for credit.

Hmm, I used an elementary result that I can prove in my solution... but it's pretty well-known. Whatever. (I proved it anyway.)

[quote="Wikipedian1337"]From reading the past discussions, it seems that the buzz is that you can cite something as long as it does not trivialize the problem. Could someone show an example of a problem (i.e. from anywhere) that is "borderline" between being trivialized and not being trivialized by a citation? (Technically, since I never mentioned a specific problem, I'm just asking for general info, not help.)[/quote]
You can even cite something that trivializes the problem and receive full credit. We people who check the problems before including them on the USAMTS will be embarrassed at having not spotted the trivialization, but that is our fault not yours.

For an example, look at Problem 5/4/15 (year 15, round 4, problem 5, http://www.usamts.org/Tests/us1504.pdf). It is entirely based on a result by the Italian mathematician Eugenio Calabi. The numerical answer is also found in [i]The Book of Numbers[/i], by John H. Conway and Richard K. Guy, though the proof is not. So theoretically, a participant could have read the original paper by Eugenio Calabi and learned both the answer and the proof. But the chance was so small (we did not mention Calabi's name in the problem) that we decided that the risk was acceptable. If I recall correctly, no-one cited the original paper or [i]The Book of Numbers[/i].

People have used specialized theorems or a powerful general-purpose techniques to solve other problems much more easily than working from scratch. If you check through the official solutions, you can find a few of those solutions. That is fine with us. Good research of the mathematical literature counts as good mathematics.

[quote="t0rajir0u"]If a cited result trivializes a problem, then it's not a good problem.[/quote]
I agree.

[quote="ZzZzZzZzZzZz"]That's not fair because there may be a great problem that can be trivialized by a very obscure, unknown formula that can be cited.[/quote]
We have rejected some problems because an obscure formula could lead to a boring solution. We don't want to offer boring problems. I am afraid that a very obscure formula would slip past our notice; fortunately, it would also escape the notice of the students working on the problem, so none of us would have to worry about it.

On the other hand, I was surprised to encounter Jim Loy's web page at http://www.jimloy.com/geometry/obtuse.htm about a mathematical fallacy that Lewis Carroll published. It uses the same diagram as Problem 4/1/19 (http://www.usamts.org/Solutions/Solution4_1_19.pdf)! I found it while looking up some geometric fallacies for a high school talk one week before grading Problem 4/1/19. So an occasional related reference does slip past us.

Erin Schram
USAMTS grader

There's an accidental extra parenthesis, the correct link is [url=http://www.usamts.org/Tests/us1504.pdf]here[/url]

What is the proper way to cite another's theorem? I've looked on the FAQ and can't find anything that suggests how to precisely do so.

I don't think there's a "proper" way to do it for USAMTS. I have to cite something as well and put the cite at the top of the proof and then referenced it later in the proof when I needed it.

I did something like this:

... $ \text{blahblahblah's formula}^1$ states...

...$ \text{this can be proven}^1$ as follows...
..............

*then at the end of the solution*

1.  http://www.blahblahblah.com/blahblahblah

I think this is how people on wikipedia cite stuff.  Maybe it's subscript, but I'm quite sure that using superscript is a proper method.

Is wikipedia.org considered a reliable source? Can we cite it on USAMTS?

None of my teachers at school permits references from wikipedia...but maybe it's different for math. Anyway, usually wikipedia cites from other websites like mathworld or planetmath, so why don't you just search on those ones?

As for the format, I would like to use:
<name>:<content><label>
<website address>

Wikipedia has a few interesting entries that cover techniques not covered on MathWorld.  Occasionally those results aren't easily available elsewhere.

So am I allowed to use wikipedia.org if I can't find the results on other reputable sources?

Well, you can just work through the thing you're citing. Have yourself check if Wikipedia is reliable in that case. Or if they don't provide a proof... look somewhere else?

I don't trust wikipedia for math, it used to say that Karamata's Inequality was a trivial consequence of Quadratic Reciprocity.

I just found something I needed on wikipedia, but of course I checked the math to make sure it worked.  I was just saying that I thought using superscript numbers was a proper way to cite stuff.


Isn't this a bit easy for this section?

Anyways, $N(C+R)=CR$ (as long as $R\not=-C$)

So $NR+NC=CR$, and hence $NR-CR=NC$.  We may factor out the $R$ to get

$(N-C)R=NC$, and so it's clear that

$R=\frac {NC}{N-C}$ (again, as long as $N\not=C$)

It may be easy for this section of the site but it was not easy for me.


Hi, I was wondering if anyone knows a website made for people to debate about various topics, kinda like how Mathlinks is a site made for people to solve problems and talk about solutions.

Well, if it's about serious-ish stuff, the Round Table is fine. If it's less serious, use G&F, and if you're surveying, use Polls. So AoPS isn't too bad  :lol:


Hey! :D
Well, here's the problem :
Let : 1/(a+b+c) = 1/a + 1/b + 1/c.
Prove that two numbers are additive inverses (opposite)

Good luck! :)

ps : if you want me to write the equality using latex, I can do so, but, I thought it was easy to understand it even without using latex ;)

Multiply through by $(a+b+c)(abc)$.  We get $a^2(b+c)+b^2(a+c)+c^2(a+b)+2abc=0$, which is just $(a+b)(a+c)(b+c)=0$.

$\frac{1}{a+b+c}=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}$

$\Longleftrightarrow \frac{1}{a+b+c}=\frac{ab+bc+ca}{abc}$

$\Longleftrightarrow abc=(ab+bc+ca)(a+b+c)$

$\Longleftrightarrow ab(a+b)+bc(b+c)+ca(c+a)+2abc=0$

$\Longleftrightarrow (a+b)(b+c)(c+a)=0$

Therefore, the statement is true.

EDIT- I guess I was late... :P

Thanks a lot for your answers dudes!
Really nice :)


geometry
perimeter
inequalities
triangle inequality
combinatorics unsolved
combinatorics

For any natural numbers $n$, ( $n \geq 3$), let $f(n)$ denote the number of congruent integer-sided triangles with perimeter $n$. Show that

(i) $f(1999) > f (1996)$;

(ii) $f(2000) = f(1997)$.

[quote="Rushil"] let $f(n)$ denote the number of congruent integer-sided triangles with perimeter $n$.[/quote]

I think it should be "incongruent integer-sided triangles".

(a) Let a, b, c be the sides of a triangle with a+b+c = 1996, and each being a positive
integer. Then a+1, b+1, c+1 are also sides of a triangle with perimeter 1999 because
a < b + c =⇒ a + 1 < (b + 1) + (c + 1),
and so on. Moreover (999, 999, 1) form the sides of a triangle with perimeter 1999,
which is not obtainable in the form (a+1, b+1, c+1) where a, b, c are the integers and
the sides of a triangle with a + b + c = 1996. We conclude that f(1999) > f(1996).
(b) As in the case (a) we conclude that f(2000) ≥ f(1997). On the other hand, if
x, y, z are the integer sides of a triangle with x+y+z = 2000, and say x ≥ y ≥ z ≥ 1,
then we cannot have z = 1; for otherwise we would get x + y = 1999 forcing x, y to
have opposite parity so that x − y ≥ 1 = z violating triangle inequality for x, y, z.
Hence x ≥ y ≥ z > 1. This implies that x − 1 ≥ y − 1 ≥ z − 1 > 0. We already
have x < y + z. If x ≥ y + z − 1, then we see that y + z − 1 ≤ x < y + z, showing
that y + z − 1 = x. Hence we obtain 2000 = x + y + z = 2x + 1 which is impossible.
We conclude that x < y + z − 1. This shows that x − 1 < (y − 1) + (z − 1) and
hence x − 1, y − 1, z − 1 are the sides of a triangle with perimeter 1997. This gives
f(2000) ≤ f(1997). Thus we obtain the desired result.


When the base of a triangle is increased $10 \%$ and the altitude to this base is decreased $10 \%$, the change in area is

A. $1 \%$ increase
B. $\frac{1}{2} \%$ increase
C. $0 \%$
D. $\frac{1}{2} \%$ decrease
E. $1 \%$ decrease

Uhh....why is an AHSME problem in MATHCOUNTS??? :?

Because it's simple enough for MathCounts students to solve, and it's good practice.

Okay :D BTW, Silverfalcon, where do you get all these old AHSME's from?  :)


MATHCOUNTS
trigonometry
Problem Potpourri
geometry
rectangle
algebra
polynomial

I was wondering if there what formulas or niche subject areas you need to understand to solve or simplify a lot of problems.  Since I only have AoPS Intro to Algebra, I don't know a lot of tricks/techniques for geometry, counting/probability, and number theory.  Could you please post something here?  Also, I'm not sure which forum to put this in, so could a mod please move it to another forum if necessary?

I think this is in the right forum. For geometry, but maybe not [i]absolutely necessary[/i]:

Pythagorean Theorem (duh)
Shoelace Theorem
Pick's Theorem
Heron's Formula
The concept of similar and congruent triangles

For Geometry:

angle chasing
similar and congruent triangles
area & perimeter (including funky areas)
right triangles (pythag, pythag triples, ect.)

For C&P:

Casework
Complementary Counting
principle of inclusion exclusion
Balls and Urns
Distinguishability

Alcumus can help a lot, it made counting and probability my strongest point when before it was probably my weakest.

For NT:

Primes and composites
counting divisors
Base numbers
modular arithmatic

Good idea, mewto5555.  MC tests at least 3 problems every Sprint Round with squares and cubes.  Also, I think a couple were left out in the all important coordinate geometry section(probably more, but here are a few I actually knew)-
y=mx+b format
distance formula
midpoint formula
reflections, rotations

And how do "dilations" work anyways?(google doesn't work very well for this)

It's also helpful to know how to calculate the sum of a sequence.
For example: 1 + 2 + 3 +...+ 100  or 2 + 4  + 6 +...+ 100

how do you calculate the sums of a sequence?

Sum=median x number of terms

Also note that median=average of first and last terms, and number of terms=(last term-first term)/difference + 1

[quote="PowerOfPi"][quote="Mewto55555"]Memorize your squares up to 2500 and your cubes up to 8000 AT LEAST.[/quote]
Is that really necessary? It takes a lot longer to memorize than just to hand multiply... unless you are in a countdown. I think squares and cubes up to 1000 is enough.[/quote]
It'll also speed you up on sprint round. Also I heard that Mr. Boyd (coach of TX National Championship teams 2005, 2007-2009) makes his kids memorize the squares and cubes.

When did I say that? Anyways, look at tip of the week 3 or 4 or search for it on the AoPS Wiki or google. It is a way to count things.

Also, to find the sum of a sequence, you might want to see [hide="these"][url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=291425]this[/url], [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=291245]this[/url], and [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=291056]this[/url][/hide].

[quote="maybach"]Considering Mewto5555's performance at nats, he's definitely right.

Also, Powerofpi, what do you mean by "balls and urns"?[/quote]

@The first line: HORRIBLE LOGIC. I suggest never memorizing anything, but his way probably gives better mathcounts results. (Though my way is still better obviously.)

Things you should know (NOT MEMORIZE):

Squares,cube (If you want good results; not necessary, do not do if you are doing mathcounts as something just for fun)
Coordinates
AREA (Huge one. So far every mathcounts geometry problem I've seen can be solved using area.)
Pythagorean theorem.
Bases
Vieta
Factoring polynomials
Rational root theorem
Trivial INequality
AM-GM (not required)
CASEWORK (Huge one... the ugliest and bashiest problems i've ever seen all came from mathcoutns)
Multiplication rule for combinatorics
Addition rule for combinatorics
Combinations and permutations
Triangle Inequality

Not necessary but sometimes helpful:

Modular Arithmetic (Not sure if it shoudl be here or above)
TRIG!
AM-GM
Ptolemy
Balls and Urns
Burnside's Lemma
Polya Enumeration Theorem
Menelaus/Ceva
Cauchy
Lagrange INterpolation (Both for polynomials and mods.)

Things that Mewto would say that only I would say is useful but still can be used on some problems (Typically very few though)

Combinatorial Nullstellensatz
Prime Number Theorem
Green-Tao theorem (I heard bobby shen uses this combined with Dirichlet a lot)
Primes can be expressed as sum of squares only if they are 1 mod 4 or 2 mod 4
Quadratic residues/Primitive Roots
SOS
Schur, Muirhead, Jensen

Things you should never use. Ever.

Overthinking the problem and using advanced methods on it (Although the things in above section can be useful, it is VERY VERY VERY VERY RARE, so rare that you shoudl pretend its never useful)
Trying to think of a "creative" way to solve the problem; mathcounts can be reduced to a set of tricks; its not that much creative thinking at all

You still haven't answered the question about "balls and urns".

I think I was the one who mentioned Balls and Urns  :P

Have you tried this?

[url]http://lmgtfy.com/?q=Balls+and+Urns[/url]

Trig isn't required for anything, but it can be incredibly useful.

First example: one of the national targets in 2008, the one that asked for the ratio of areas of two triangles, could be solved immediately by recalling the area of a triangle is $ \frac{1}{2}\cdot{ab\cdot{\sin{C}}}$.

Second example: one of the national sprint problems this year (in the mid 20s, forget which) had something about a right triangle. Here, you could find the sine/cosine of the angles, find the sides, and then again use $ \frac{1}{2}\cdot{ab\cdot{\sin{C}}}$ to find the answer. (I forgot to divide by two for this  :P )

So, trig isn't necessary, but you should know it, as it can be very helpful.

Let's examine pythag's list.

I agree with basically everything in the first group. AM-GM is probably only useful for those optimization problems where they want to find the maximum area of some rectangle, etc. RRT probably isn't useful; I've never used it since all the polynomials you get in Mathcounts are easy to factor or find the roots of.

Now the second group.

Modular arithmetic is very, very helpful. It should've been in the first group.
Refer to the above paragraph for AM-GM.
I've used Ptolemy once, and that was only on the School Sprint #29 from this year, which was a direct application of it. However, David says a bunch of Mathcounts problems reduce to this and I've never actually tried using it much, so I don't know.
Balls and urns is also very good to know.
Polya Enumeration Theorem is a generalization of Burnside's Lemma, and I think it's pretty useful. However, you can just memorize the number of distinct rotations of common solids, so I dunno.
Menelaus/Ceva is basically drawing a parallel line/similar triangles/mass points/area ratios, so they aren't necessary. Still pretty important to know at least one of the methods.
I'm going to say Cauchy is pretty much useless. The only thing that occurs to me is if you wanted to find the maximum value of something like $ x^2\plus{}y^2$ by using Cauchy on $ (x^2\plus{}y^2)(a^2\plus{}b^2)\ge{(ax\plus{}bc)^2}$ so you can divide and find the answer. I don't think that's ever come up on Mathcounts though...
Lagrange Interpolation-no way. There are hardly any polynomials on Mathcounts other than quadratics or easily factorable cubics/quartics.

Last group left.
I'm just going to say that everything in this group is not useful for Mathcounts at all. Inequalities basically come up in optimization problems, and only those that are very common, like the one mentioned above for AM-GM. Why would you need Schur, Muirhead, or Jensen? Same for SOS.
...Why would you need to know how the primes are distributed?
The quadratic residues might be useful for bashing something, but primitive roots probably would not be. The stuff about primes 1 or 2 (mod 4) is probably not very useful, but it makes more sense than the others.
I'm not even going to comment on Combinatorial Nullstellensatz/Green-Tao theorem.

So basically, take the first two lists minus Lagrange Interpolation, and you should be good.

[quote="xpmath"]Trig isn't required for anything, but it can be incredibly useful.

First example: one of the national targets in 2008, the one that asked for the ratio of areas of two triangles, could be solved immediately by recalling the area of a triangle is $ \frac {1}{2}\cdot{ab\cdot{\sin{C}}}$.

Second example: one of the national sprint problems this year (in the mid 20s, forget which) had something about a right triangle. Here, you could find the sine/cosine of the angles, find the sides, and then again use $ \frac {1}{2}\cdot{ab\cdot{\sin{C}}}$ to find the answer. (I forgot to divide by two for this  :P )

So, trig isn't necessary, but you should know it, as it can be very helpful.

Let's examine pythag's list.

I agree with basically everything in the first group. AM-GM is probably only useful for those optimization problems where they want to find the maximum area of some rectangle, etc. RRT probably isn't useful; I've never used it since all the polynomials you get in Mathcounts are easy to factor or find the roots of.

Now the second group.

Modular arithmetic is very, very helpful. It should've been in the first group.
Refer to the above paragraph for AM-GM.
I've used Ptolemy once, and that was only on the School Sprint #29 from this year, which was a direct application of it. However, David says a bunch of Mathcounts problems reduce to this and I've never actually tried using it much, so I don't know.
Balls and urns is also very good to know.
Polya Enumeration Theorem is a generalization of Burnside's Lemma, and I think it's pretty useful. However, you can just memorize the number of distinct rotations of common solids, so I dunno.
Menelaus/Ceva is basically drawing a parallel line/similar triangles/mass points/area ratios, so they aren't necessary. Still pretty important to know at least one of the methods.
I'm going to say Cauchy is pretty much useless. The only thing that occurs to me is if you wanted to find the maximum value of something like $ x^2 \plus{} y^2$ by using Cauchy on $ (x^2 \plus{} y^2)(a^2 \plus{} b^2)\ge{(ax \plus{} bc)^2}$ so you can divide and find the answer. I don't think that's ever come up on Mathcounts though...
Lagrange Interpolation-no way. There are hardly any polynomials on Mathcounts other than quadratics or easily factorable cubics/quartics.

Last group left.
I'm just going to say that everything in this group is not useful for Mathcounts at all. Inequalities basically come up in optimization problems, and only those that are very common, like the one mentioned above for AM-GM. Why would you need Schur, Muirhead, or Jensen? Same for SOS.
...Why would you need to know how the primes are distributed?
The quadratic residues might be useful for bashing something, but primitive roots probably would not be. The stuff about primes 1 or 2 (mod 4) is probably not very useful, but it makes more sense than the others.
I'm not even going to comment on Combinatorial Nullstellensatz/Green-Tao theorem.

So basically, take the first two lists minus Lagrange Interpolation, and you should be good.[/quote]

Lagrange Interpolation is not for polynomials, its for modular arithmetic.

Quadratic Residues/Primitive Roots is useful for counting things modulo n, thats its main use in mathcounts.

Okay, well solving the system of congruences can be pretty helpful, but as I don't know much about Lagrange Interpolation with mods stuff, I can't really say anything. I am betting it is rather too much for Mathcounts.

[quote="PowerOfPi"][quote="Mewto55555"]Memorize your squares up to 2500 and your cubes up to 8000 AT LEAST.[/quote]
Is that really necessary? It takes a lot longer to memorize than just to hand multiply... unless you are in a countdown. I think squares and cubes up to 1000 is enough.[/quote]

I mean clearly its not NECESSARY, you can get by fine deriving them by hand, but sometimes it saves a bit of time, and every bit of time is crucial.

Clearly once you've got all of the basic concepts down and can solve every problem (and not screw up), it then comes down to streamlining the process, so you have time to get everything done AND time to check (and backup time if you are being stupid and taking forever on #1 cuz you're nervous).

[quote="Poincare"][quote="maybach"]Thanks!  I just learned Pick's formula on Wickipedia.  A=i+b/2, which means the area of the figure equals the number of interior points plus half the number of boundary points.  I could've used that for a couple of practice questions! :)[/quote]

IMO, this is a wrong approach. Unless you understand the formula's derivation,  you'll never be able to use it to its full extent. Buy Vol 1 or the intro series or just look up the formula's on AoPsWiki (not normal wiki) as you find them in problem solutions[/quote]

In [i]my[/i] opinion, your approach is wrong. While you shouldn't memorize formulas, I am not one of those HEY YOU HAVENT PROVEN IT SO YOU CANT USE IT. For example, Poincare, can you find the formula for the volume of a sphere? Or have you just memorized it?

What I do is I just memorize formulas, then go through like 5 or 6 examples to show why it works. Pre-MC I had a random formula sheet. I'm not going to go through and say, derive $ \frac{n^2(n^2\minus{}1)}{12}$ squares in an nxn grid...

[quote="Mewto55555"]Pre-MC I had a random formula sheet.[/quote]
Do you still have it? That could be useful.

Also, notice the title of this thread: "you NEED to know", not "you might want to know".

I don't think any of those are worth memorizing except Peter Xu's formula.

Indeed, that is the only formula I have ever consciously used.

Dang that was pretty much the formula sheet I used, as a matter of fact I think that is where I got the sheet? I guess I should probably thank you for it now (all I really did was skim it the night before though and only memorize that one formula I posted).

EDIT: Looking through, I see if I had reached page 7 I would have won Nationals written. darn.

EDIT THE SECOND: Mewto's infamous coin formula:

The number of ways to make n cents (n is an integer, 11-49) out of pennies, nickels, dimes, and quarters is $ 3\plus{}\frac{(\lfloor\frac{n}{5}\rfloor)(\lfloor\frac{n}{5}\rfloor\minus{}1)}{2}$

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1062010#1062010]LOL, this brings back many memories...[/url]

Like out of my first $ 100$ posts it is arguably the most productive.

I think I like told you it and then you posted it in an FTW discussion thread and everyone started saying it was incorrect. :P

wouldn't it be easier just to memorize the mathcounts handbook which includes most of wat was stated by the other ppls  :huh:
 For Geometry: memorize all area, surface area, volume, and know how to use similarity
 and u should know bases they might have base questions sometimes

Well yeah, you will need those, but if you want to save time, Victor's formula sheet helps. I mean, 2 people who made countdown, and 100% of all Master's Round winners from Missouri have used that sheet.


Please help me with this triangle problem

Thank You

[hide]
Let $\theta = \angle CAB$. We have $BCDE = \triangle ACD-\triangle ABE$ which is,
\[(18)(12)\sin{\theta}/2-72 = (6)(12)\sin{\theta}/2 \]
so
\[\sin{\theta}= \frac{8}{9}\]
Now, we know that $\triangle BFE = \triangle ABE-\triangle ABF$
so $\triangle BFE = ((6)(9)-(3)(9))\frac{4}{9}= 12$
so $\fbox{12}$ is the answer.
[/hide][/hide]

$\theta\ne\angle CAB$.

Its impossible unless $\theta=180^\circ=\pi$ :wink:

Can somebody explain it better because i dont understand what he did.
I didnt take sin of a straight line. Please somebody explain


how do you differentiate

2x^2 - 4xy + 3y^2 = 3 ?

cheers this is really urgent and id really appreciate a quick reply

I assume KellyGGG wants "implicit differentiation".


Compute: $ 1.\overline{1} \times 0.01$. Express your answer as a common fraction.

but on ftw, I put 1/90 and It was incorrect..

it says answer is 1/75

It must have been a different question, because $\frac{1}{90}$ is the correct answer for this problem


[quote="t0rajir0u"][hide="Big hint"] $\frac{120}{(k-1)k(k+1)}= \frac{60}{k-1}-\frac{120}{k}+\frac{60}{k+1}$ [/hide][/quote]

[hide="if you dont know how t0rajir0u got that click here"]
It's called Partial fraction decomposition.

Basically, you factor the denominator, and you write them as separate fractions.

In this case:

$\frac{120}{(k-1)k(k+1)}= \frac{A}{k-1}+\frac{B}{k}+\frac{C}{k+1}$

Then, you can cross multiply and plug in $k=1,0,-1$ to solve for $A, B,$ and $C$ respectively. Then you end up with what t0rajir0u got.
[/hide]


Given two orthogonal circles with intersect at $ A$ and $ B$, we draw a third circle with center $ A$ and radius $ AB$. Let $ C$ and $ D$ be the points beside $ B$ where this third circle meets the other two. Prove that $ CD$ is a diameter of the third circle.

[hide="proof"]If the two circles are orthogonal then $ r_1^2+r_2^2=O_1O_2^2$ where $ O_1$ and $ O_2$ are the centers of the two circles.
The quadrilateral $ O_1BO_2A$ is inscriptible, therefore $ \{\begin{array}{cccc} \angle AO_1B=2\alpha \\
\angle  AO_2B=180-2\alpha \end{array}$
$ \{\begin{array}{cccc} \Delta O_1BA \equiv \Delta O_1CA \implies \angle O_1AC =90-\alpha=\angle O_1AB\\
\\
\Delta O_2BA \equiv \Delta O_2AD \implies \angle O_2AD=\alpha=\angle BAO_2 \end{array}$ $ \implies$ that $ C,A,D$ are collinear points,$ A$ is the circles's center $ \implies$ $ \overline{CAD}$ diameter.[/hide]


vector
linear algebra
combinatorics unsolved
combinatorics

Let $ A_1;A_2;..A_m$ and $ B_1;...B_p$ be subsets of $ |{1, 2, ..., n\}}$ such that $ A_i\cup B_j$ is an odd number for all $ i, j$ .Prove that $ mp\le 2^{n-1}$
Elementary proof , please!

Sure it shouldn't be $ mp\leq 2^n$ ?

EDIT: Found the original problem. $ A_i\cup B_j$ should be $ \left|A_i\cap B_j\right|$. Then it is correct.
Most linear algebra over $ \mathbb{F}_2$ can be directly translated into combinatorics. For instance, the sum of two vectors in $ \mathbb{F}_2^n$ corresponds to the symmetric difference $ \left(A\cup B\right)\setminus\left(A\cap B\right)$ of two subsets $ A$ and $ B$ of $ \left\{1,2,...,n\right\}$. Vector subspaces correspond to families of subsets closed under symmetric difference. Affine subspaces correspond to families of subsets closed under symmetric difference of an [i]odd[/i] amount of subsets. And so on. But simply talking about vectors is in most cases way more enlightening.

EDIT2: See http://www.mathlinks.ro/viewtopic.php?t=290708 for a linear-algebraic proof of both the correct problem and my version (well, you will have to replace the $ A_i$ and the $ B_j$ by their complements to get from the $ \left|A_i\cup B_j\right|$ version to the $ \left|A_i\cap B_j\right|$ one).

  darij

Yes, darij. It must be $ \left|A_{i}\cap B_{j}\right|$ .
But your proof is still hard, It doesn't seem to be an elementary one  :( . Can you help me again?


limit
real analysis
real analysis unsolved

For a real number $ x$, let $ \{x\}$ denote $ x \minus{} [x]$, where $ [x]$ is the largest integer less than or equal to $ x$. Show that:

\[ \lim_{n\rightarrow\infty}\{\left(2\plus{}\sqrt{3}\right)^{n}\}\equal{}1.\]

Consider $ a_n \equal{} (2\plus{}\sqrt{3})^n \plus{} (2\minus{}\sqrt{3})^n$. The characteristic equation of $ a_n$ is $ x^2 \minus{} 4x \plus{} 1 \equal{} 0$, so $ a_{n\plus{}2} \minus{} 4a_{n\plus{}1} \plus{} a_n \equal{} 0$.

Also, $ a_0 \equal{} 2$ and $ a_1 \equal{} 4$. This shows that all the terms of $ a_n$ is integer.

Since $ 0 < 2\minus{}\sqrt{3} < 1$. $ \left\{ (2\plus{}\sqrt{3})^n \right\} \equal{} 1 \minus{} (2\minus{}\sqrt{3})^n$. Clearly this converges to $ 1$.

Generalization based on sos440's solution: If $ p,q\in \mathbb{N}^*$ and $ p \minus{} q > 1$ then
\[ \lim_{n\to \infty}\left \{\left( \frac {p \plus{} \sqrt {p^2 \minus{} 4q}}{2} \right)^n \right \} \equal{} 1
\]
The original problem is the case $ p \equal{} 4,q \equal{} 1$.


function
real analysis
real analysis unsolved

Find $ f: ( \minus{} 1,\infty)\to{R}$ which is derivable for $ 2$ times with the twice derivate continuous, so that for every $ x\in( \minus{} 1,\infty)$we have:
      $ (f^{'}(x))^2 \equal{} f^{''}(x)$  , $ f(0) \equal{} 1$  , $ f'(0) \equal{}\minus{} 1$

From your wording, it's hard for me to decide if the problem is to find some function, or find all functions.

$ f(x)\equal{}1\minus{}ln(x\plus{}1)$ is a solution, though showing that it's the only one could be tricky.

perfect answer LydianRain...

But even i don think there exists any other solution for this ....

PS. it would be convinient if u post the full solution and hide it LydianRain

Just one function that respect the properties must be found. Please, could you post the full solution

Well, if you just need to find one function, I think that I [i]did[/i] post the full solution... but here's how I got there:

[hide]If you write the equation as $ f'(x)\equal{}{f''(x)\over {f'(x)}}$, and integrating (and using the initial condition) we get $ f(x)\equal{}1\plus{}ln(\minus{}f'(x))$ near $ 0$. (we don't need to be too rigorous here, since we're just looking for one solution, but we should be careful about the initial conditions--and the minus sign!)  We can write this as $ g'(x)\equal{}e^{\minus{}g(x)}$, where $ g(x)\equal{}1\minus{}f(x)$.

From this, it seems reasonable to write $ g(x)\equal{}ln(h(x))$, and this equation becomes $ h'(x)\equal{}1$, so $ h(x)\equal{}x\plus{}c$, and the result follows immediately from there.

Come to think of it, that seems to prove that there are no other solutions. :)[/hide]


Problem

for all real number except 1, find all polynomial P(x) that satisfy

{x^100-1}over{x-1} ≤ (x+1)P(x^2)


[quote="xxxxtt"]Prove that there exists a polinomial from Z[X] wich has as root the number sqrt2003(5-2sqrt(6))+sqrt2003(5+2sqrt(6)) where sqrt2003 is the 2003 order root[/quote]
============
Put   a = sqrt2003(5-2sqrt(6)), b = sqrt2003(5+2sqrt(6)) then ab = 1 and
a^2003 + b^2003 = 10. But a^2003 + b^2003 is symmetric in a, b so it can be express via (a+b) and a.b. But we have a.b = 1 so a^2003 + b^2003 = P(a+b), P belong to Z[x]. We conclude that a+b is the root of P(x) - 10 = 0.

We can show more general result: sum, product, root of two algebraic numbers is again algebraic.

Note: Algebraic number is number which is root of an polynomial with integer coefficients.

Namdung


Must use geometry and not calculus.

Find the length of the longest pole that can be moved around the corner shown in the figure below.  At all times the pole must lie flat on the floor.  Express your answers in terms of a and b.

How do I add the figure 1st and foremost?

It might just be my computer but I don't see the figure.

There is no picture around dude............

It's been posted a few times before - and moved to the calculus section. Here's [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=24520]one such topic.[/url]


Let r be a root of x2 + 5x + 7 = 0. Compute (r-1)(r+2)(r+6)(r+3).

[hide]From the first and third expressions, we get (r^2+5r-6) and the 2nd and 4th give (r^2+5r+6)... Multiplying these and substituing in r^2+5r = -7, we get (-13)(-1) = 13.[/hide]

you have to work through it just a little before it gets really easy. here's what I did:

[hide]you find that a root of the quadratic is  (:rt3: /2)i-5/2

so then i just plugged it into the expression we were given to solve for to see if anything happens. look.

(( :rt3: /2)i-7/2)*(( :rt3: /2)i+7/2)*(( :rt3: /2)i-1/2)*(( :rt3: /2)i+1/2)

now we just have two differences of squares.

so -13*-1 = 13

[/hide]

there might be an easier way, but this still only takes you about two minutes.

their ways are a lot easier, so nvm gauss lol

Your way works just fine codeblue. There's still yet another way to solve this one. See if you can find it. hint: [hide]If r is a root of x2 + 5x + 7 = 0, then r2 = -5r - 7 [/hide]

And here's another problem similar to that one. If r and s are the roots of x2 + x + 7 = 0, compute the numerical value of 2r2 + rs + s2 + r + 7.

And here's another problem similar to that one. If r and s are the roots of x^2 + x + 7 = 0, compute the numerical value of 2r^2 + rs + s^2 + r + 7.

[hide]r + 7 = -r^2, so we have r^2 + rs + s^2 = (r+s)^2 -rs = (-1)^2 - 7 = -6.[/hide]

[hide]the value is (r+s)^2-rs+r^2+r+7. We have r+s=-1, rs=7, and r^2+r+7=0. So, answer is -6[/hide]


Given that $ \log_{4n} 40\sqrt{3}\equal{}\log_{3n} 45$, find $ n^3$.

Re-write the expression as $ \frac{\log{40\sqrt{3}}}{\log{4n}}=\frac{\log{45}}{\log{3n}}$.  Do some cross multiplication and use some properties of logs to get
$ \log{n}=\frac{\log{45}\log{4}-\log{40\sqrt{3}}\log{3}}{\log{40\sqrt{3}}-\log{45}}$
Make sure you see how I got this (assuming I did the math right.  Then of course we find that
$ n=10^{\frac{\log{45}\log{4}-\log{40\sqrt{3}}\log{3}}{\log{40\sqrt{3}}-\log{45}}}$
so by cubing this, we get $ n^{3}$.

[hide="My hint"]
$ \frac {log(40\sqrt {3})}{log(4n)} \equal{}\frac {log (45)}{log(3n)}$
$ \frac {log(40\sqrt {3})}{log(45)} \equal{}\frac {log(64n^3)}{27n^3}$
Then we obtain :
$ k.log(40.\sqrt {3})\equal{}log(64n^3)$ then $ (40\sqrt {3})^k \equal{} 64n^3$
$ k.log(45)\equal{}log(27n^3)$ then $ (45)^k \equal{} 27n^3$
$ \frac {8}{\sqrt {3}}^k\equal{}(\frac {4}{3})^2$ then $ k\equal{}2$ and $ n\equal{}75$. I am sorry if there exist some of my words that are wrong.
[/hide]

At Qruni, if your final answer is 75, then our answers agree and it should be right.

I originally did it JRav's method and then got a new idea.

[hide="My Start"]Exponentializing them, we have $ (4n)^{x} \equal{} 40\sqrt {3}$ and $ (3n)^x \equal{} 45$. Dividing, we have $ \left(\dfrac{4}{3}\right)^{n} \equal{} \frac {8\sqrt {3}}{9}$.[/hide]

Now how do I find $ n$?

[quote="#H34N1"]Dividing, we have $ \left(\dfrac{4}{3}\right)^{n} \equal{} \frac {8\sqrt {3}}{9}$.[/hide]

Now how do I find $ n$?[/quote]

[hide="Under the assumption that n is rational..."] Write $ \frac{8 \sqrt{3}}{9} \equal{} 2^3 3^{\minus{} \frac{3}{2} } \equal{} 4^{ \frac{3}{2} } 3^{\minus{} \frac{3}{2} } \equal{} \left( \frac{4}{3} \right)^{ \frac{3}{2} }$.   [/hide]


calculus
integration
trigonometry
calculus computations

How can we find the integral

${\int_{s=0}^{n}\frac{\sin\pi s}{\pi (s-l)}\, ds}$

where $0\leq l\leq n$ are both integers  :?:

A well known fact is the

${\int_{u=0}^{+\infty}\frac{\sin\pi u}{u}{\,du=\frac{\pi}{2}}}$


calculus
integration
calculus computations

compute the indefinite integral

$\int\frac{1}{x^{2}(x^{2}+1)^{2}}dx$


limit
function
algebra
domain
calculus
calculus computations

Find $ x \in \mathbb{R}$ for which there exist the limit of

\[ f(x) = \{
\begin{array}{llll}
{x^2 }& for & x = \frac{n-1}{n} &{ n \in N^+}\\
 {}& & &{}\\
{x }& for & x \neq \frac{n-1}{n} &{ n \in N^+}\end{array}\]

what do you mean "there exist the limit of"?

Did you mean Continuous??Look at  $ n\equal{}1$.

Actually, the most straightforward interpretation would be this:
For which values of $ x$ does the limit $ \lim_{t\to x} f(t)$ exist, where $ f(x)\equal{}\begin{cases}x^2&x\equal{}\frac{n\minus{}1}{n}\text{ for some }n\in\mathbb{N}^\plus{}\\ x&\text{otherwise}\end{cases}$

[quote="jmerry"]Actually, the most straightforward interpretation would be this:
For which values of $ x$ does the limit $ \lim_{t\to x} f(t)$ exist, where $ f(x) \equal{} \begin{cases}x^2 & x \equal{} \frac {n \minus{} 1}{n}\text{ for some }n\in\mathbb{N}^ \plus{} \\
x & \text{otherwise}\end{cases}$[/quote]
Your intepretation is correct. But what is the solution? Thank you.

Look at three cases:
Case 1: $ x\equal{}\frac{n\minus{}1}{n}$ for some $ n$
Case 2: $ x\equal{}1$, the limit of those points
Case 3: everything else.

[quote="jmerry"]Look at three cases:
Case 1: $ x \equal{} \frac {n \minus{} 1}{n}$ for some $ n$
Case 2: $ x \equal{} 1$, the limit of those points
Case 3: everything else.[/quote]
Yes, I agree. Anyway I am not sure what you mean with "some $ n$".
The function $ f(x)$ for all points of the sequence $ \frac {n \minus{} 1}{n}$ with $ n>0$ assume the value $ \left(\frac {n \minus{} 1}{n}\right)^2$. The sequence has a limit $ 1$, when $ n \rightarrow \infty$ and since $ x \rightarrow 1$ when $ n \rightarrow \infty$ the $ \lim_{t\to 1}f(t)\equal{}1$.

For $ x \rightarrow 0$ the limit is $ 0$

For $ x_0 \ne  \frac {n \minus{} 1}{n}$ the $ \lim_{t\to x_0}f(t)\equal{}x_0$

In conclusion, the limit exists $ \forall x \in \mathbb{R}$.

Any comment? Thanks

"for some" is just a shorthand for being a member of that set.

The problems with your argument:
- What's the limit as $ t\to\frac{n\minus{}1}{n}$? You didn't really address that.
- There's nothing special about zero.
- $ 1$ is special, as we can get close to there in both cases of the domain of $ f$. You need to say more about it.

[quote="jmerry"]"for some" is just a shorthand for being a member of that set.

The problems with your argument:
- What's the limit as $ t\to\frac {n \minus{} 1}{n}$? You didn't really address that.
[/quote]
Yes you're right. I was a bit confused.

In that case the limit is $ \frac {n \minus{} 1}{n}$ since $ \forall \varepsilon >0$ and for $ \left| x \minus{}  \frac {n \minus{} 1}{n} \right| < \varepsilon$, $ x \ne \frac {n \minus{} 1}{n} \Rightarrow \left | f(x) \minus{} \frac {n \minus{} 1}{n} \right| < \varepsilon$, since $ f(x) \equal{} x$.
So when $ x_0 \equal{} \frac {n \minus{} 1}{n}$ we have $ \lim_{t\to x_{0}}f(t)\equal{}\frac {n \minus{} 1}{n} \ne f(x_{0})$

[quote="jmerry"]- There's nothing special about zero.
- $ 1$ is special, as we can get close to there in both cases of the domain of $ f$. You need to say more about it.[/quote]
As said in previous post, when $ x \to 1$, $ n \to \infty$ and so the restriction of $ f(x)$ to the domain $ \left\{x\equal{}\frac {n \minus{} 1}{n}, n >0 \right\}$ has limit and this limit is $ 1$.

The other restriction of $ f(x)\to 1$ when $ x \to 1$

So when $ x_0 \equal{} 1$ we have $ \lim_{t\to 1}f(t) \equal{} 1$

What do you think about that?


function
induction
algebra unsolved
algebra

Let $ f(x)$ be a continuous functions on $ [0,1]$ and:
1. $ f(0) \equal{} 0$ and $f(1) \equal{} 1$, and
2. When $ a\in (0,1), x,y\in [0,1] , x\leq y$, \[ f\left(\frac {x \plus{} y}{2}\right) \equal{} (1 \minus{} a)f(x) \plus{} af(y).\]
Find $ f\left(\frac {1}{7}\right)$.

[quote="Elementaryyy"]$ f(x)$ is a continuous functions on $ [0,1]$ and:
1. $ f(0) \equal{} 0 , f(1) \equal{} 1$
2. $ f(\frac {x \plus{} y}{2}) \equal{} (1 \minus{} a)f(x) \plus{} af(y)$ when $ a\in (0,1), x,y\in (0,1) , x\leq y$

Find $ f(\frac {1}{7})$

I want a simple solution.[/quote]

Set $ x\to 0$ in 2. Continuity gives $ f(\frac y2) \equal{} af(y)$

Set $ y\to 0$ in 2. Continuity gives $ f(\frac x2) \equal{} (1 \minus{} a)f(x)$

So $ a \equal{} \frac 12$ (since $ f(1) \equal{} 1$ and so $ f(x)$ is not all zero) and $ f(\frac {x \plus{} y}2) \equal{} \frac {f(x) \plus{} f(y)}2$

This is a very classical equation whose immediate unique solution (since continuous and $ f(0) \equal{} 0$ and $ f(1) \equal{} 1$) is $ f(x) \equal{} x$

[hide="why ?"]
Let $ 0<a<b<1$. It's immediate to show thru induction that $ f(\frac p{2^q}a\plus{}(1\minus{}\frac p{2^q})b)\equal{}\frac p{2^q}f(a)\plus{}(1\minus{}\frac p{2^q})f(b)$ $ \forall q\in\mathbb N$, $ \forall p\in\mathbb N_0\cap[0,2^q]$

Then setting $ q\to \plus{}\infty$ and using continuity : $ f(x)\equal{}\frac{f(b)\minus{}f(a)}{b\minus{}a}(x\minus{}a)\plus{}f(a)$ $ \forall x\in[a,b]$

Setting then $ a\to 0$ and $ b\to 1$ and using continuity again, we get $ f(x)\equal{}x$
[/hide]

So $ f(\frac 17) \equal{} \frac 17$

Because $ x\leq y$ then if $ y\equal{}0$ then $ x\equal{}0$ so we can not have
$ f(\frac{x}{2}) \equal{} (1\minus{}a)f(x)$

[quote="Elementaryyy"]Because $ x\leq y$ then if $ y \equal{} 0$ then $ x \equal{} 0$ so we can not have
$ f(\frac {x}{2}) \equal{} (1 \minus{} a)f(x)$[/quote]

You're right  :oops:

[quote="Elementaryyy"]$ f(x)$ is a continuous functions on $ [0,1]$ and:
1. $ f(0) = 0 , f(1) = 1$
2. $ f(\frac {x + y}{2}) = (1 - a)f(x) + af(y)$ when $ a\in (0,1), x,y\in [0,1] , x\leq y$

Find $ f(\frac {1}{7})$

I want a simple solution.[/quote]

Next trial :)

Let $ P(x,y)$ be the assertion $ f(\frac{x+y}2)=(1-a)f(x)+af(y)$

$ P(0,1)$ $ \implies$ ${ f(\frac 12})=a$

$ P(0,\frac 12)$ $ \implies$ $ f(\frac 14)=a^2$

$ P(\frac 12,1)$ $ \implies$ $ f(\frac 34)=2a-a^2$

$ P(\frac 14,\frac 34)$ $ \implies$ $ f(\frac 12)=(1-a)a^2+a(2a-a^2)=3a^2-2a^3$

And so $ a=3a^2-2a^3$ and so $ a(a-1)(2a-1)=0$ and so $ a=\frac 12$ (since $ a\in(0,1)$

and so $ f(\frac {x + y}2) = \frac {f(x) + f(y)}2$

This is a very classical equation whose immediate unique solution (since continuous and $ f(0) = 0$ and $ f(1) = 1$) is $ f(x) = x$

[hide="why ?"]
Let $ 0 < a < b < 1$. It's immediate to show thru induction that $ f(\frac p{2^q}a + (1 - \frac p{2^q})b) = \frac p{2^q}f(a) + (1 - \frac p{2^q})f(b)$ $ \forall q\in\mathbb N$, $ \forall p\in\mathbb N_0\cap[0,2^q]$

Then setting $ q\to + \infty$ and using continuity : $ f(x) = \frac {f(b) - f(a)}{b - a}(x - a) + f(a)$ $ \forall x\in[a,b]$

Setting then $ a\to 0$ and $ b\to 1$ and using continuity again, we get $ f(x) = x$
[/hide]

So $ f(\frac 17) = \frac 17$

I think it is true.
My solution are too long.

My solution:
Let $ P(x,y)$ be the assertion $ f(\frac {x \plus{} y}2) \equal{} (1 \minus{} a)f(x) \plus{} af(y)$
$ P(0, 1)\Rightarrow f(\frac {1}{2}) \equal{} a$
$ P(x, 0)\Rightarrow f(\frac {x}{2}) \equal{} (1 \minus{} a)f(x)$
$ P(7x, x)\Rightarrow f(4x) \equal{} (1 \minus{} a)f(7x) \plus{} af(x)\Rightarrow \frac {1}{(1 \minus{} a)^2}f(x) \equal{} (1 \minus{} a)f(7x) \plus{} af(x)$
$ x \equal{} \frac{1}{7}$, we have $ f(\frac {1}{7})$

P\s: Elementaryyy is ThieuSax

[quote="thanhtra_dhsp"]My solution:
Let $ P(x,y)$ be the assertion $ f(\frac {x \plus{} y}2) \equal{} (1 \minus{} a)f(x) \plus{} af(y)$
$ P(0, 1)\Rightarrow f(\frac {1}{2}) \equal{} a$
$ P(x, 0)\Rightarrow f(\frac {x}{2}) \equal{} (1 \minus{} a)f(x)$
$ P(7x, x)\Rightarrow f(4x) \equal{} (1 \minus{} a)f(7x) \plus{} af(x)\Rightarrow \frac {1}{(1 \minus{} a)^2}f(x) \equal{} (1 \minus{} a)f(7x) \plus{} af(x)$
$ x \equal{} \frac {1}{7}$, we have $ f(\frac {1}{7})$
[/quote]

$ P(x,y)$ is true only for $ x\leq y$, so $ P(x,0)$ or $ P(7x,x)$ are true only for $ x\equal{}0$

[quote="thanhtra_dhsp"]My solution:
Let $ P(x,y)$ be the assertion $ f(\frac {x \plus{} y}2) \equal{} (1 \minus{} a)f(x) \plus{} af(y)$
$ P(0, 1)\Rightarrow f(\frac {1}{2}) \equal{} a$
$ P(x, 0)\Rightarrow f(\frac {x}{2}) \equal{} (1 \minus{} a)f(x)$
$ P(7x, x)\Rightarrow f(4x) \equal{} (1 \minus{} a)f(7x) \plus{} af(x)\Rightarrow \frac {1}{(1 \minus{} a)^2}f(x) \equal{} (1 \minus{} a)f(7x) \plus{} af(x)$
$ x \equal{} \frac {1}{7}$, we have $ f(\frac {1}{7})$
[/quote]
Do you read  $ x \leq y$

P/s: Thanhtra_dhsp : Anh che'e'e'e'e'm


Is this problem solved as a simultaneously equation. Can someone please clearly show how this problem can be solved?

The average temperature for November 1st 2nd and 3rd was 20 degrees. The average temperature for November 2nd 3rd and 4th was 24 degrees.
On November 1 the temperature was 20 degree.
What was the temperature on the 4th of November?

Thank you

Let the temperature on November 1st,2nd 3rd and 4th be a,b,c, and d respectively.
Then, (20+b+c)/3=20;=>b+c=40.
And (b+c+d)/3=24;=>b+c+d=72.
From this we get d=32.

Thanks for that.
The answer from the back of the book says 26 degrees but it may be wrong??

I'm pretty sure the answer is $ 32$, unless you typed the question wrong.

Let $ N_{i}$ denote the temperature on the $ i$th day.

Then, from the problem statement,

$ \frac{N_1\plus{}N_2\plus{}N_2}{3}\equal{}20 \implies N_1\plus{}N_2\plus{}N_3\equal{}60$.

The next sentence gives us

$ \frac{N_2\plus{}N_3\plus{}N_4}{3}\equal{}24 \implies N_2\plus{}N_3\plus{}N_4\equal{}72$.

Subtracting the first equation from the second gives

$ N_4\minus{}N_1\equal{}12 \implies N_4\equal{}N_1\plus{}12$.

Since $ N_1\equal{}20$, $ N_4\equal{}\boxed{\boxed{\boxed{32}}}$.

That's the right method, I did make an error with the first average, 20 instead of 22.
Thank you all for explaining the method :lol:

An important thing to note is that $ N_2\plus{}N_3\equal{}40$, but we don't actually know the values of $ N_2$ and $ N_3$.  It is interesting because you can solve for some of the variables, but not all of them.


Hi all this makes me

Knowing that:

$ a^{\minus{}1}\plus{}b^{\minus{}1}\plus{}c^{\minus{}1}\equal{}0$

Simplify:

$ A\equal{}\displaystyle\frac{a^4\plus{}b^4\minus{}c^4}{a^3\plus{}b^3\plus{}c^3\plus{}abc}$

Greetings  :D

hello, i think you mean
$ A\equal{}\frac{a^{4}\plus{}b^{4}\plus{}c^{4}}{a^{3}\plus{}b^{3}\plus{}c^{3}\plus{}abc}$
Sonnhard.

If this is the book I saw was so sure that the wrong way and you say goes

$ a\plus{}b\plus{}c$

Greetings  :D


Trapezoid $ ABCD$ has bases $ \overline{AB}$ and $ \overline{CD}$ and diagonals intersecting at $ K$. Suppose that $ AB\equal{}9$, $ DC\equal{}12$, and the area of $ \triangle AKD$ is $ 24$. What is the area of trapezoid $ ABCD$?

$ \textbf{(A)}\ 92 \qquad
\textbf{(B)}\ 94 \qquad
\textbf{(C)}\ 96 \qquad
\textbf{(D)}\ 98 \qquad
\textbf{(E)}\ 100$

[hide]$ \triangle ACD, \triangle BCD$ will always have the same area because they have the same base and same altitude. Thus, $ [AKD]\equal{}[ACD]\minus{}[KCD]\equal{}[BCD]\minus{}[KCD]\equal{}[BCK]$. $ \triangle AKD, \triangle BKC$ both have area 24.

Now, similar triangles. $ \triangle ABK \sim \triangle CDK$ so $ AB/CD\equal{}AK/CK\equal{}9/12$, let $ AK\equal{}3x$ and $ CK\equal{}4x$ for some value $ x$.

If two triangles share the same altitude their area ratio is the area of their bases. So $ [AKD]/[KCD]\equal{}3/4$ thus $ [KCD]\equal{}32$. Similarly $ [KBC]/[ABK]\equal{}4/3$ thus $ [ABK]\equal{}18$.

Hence $ [ABCD] \equal{} 18 \plus{} 24 \plus{} 24 \plus{} 32 \equal{} 98$ and the answer is $ \boxed{D}$.[/hide]

well yea but you should know they both should have area 24 anyways...no matter what the trapezoid is.

its just easier to see it since if its isosceles, both tiranlges are congruent.

[quote="not_trig"]When they ask questions like this, you know the answer's going to be a constant... so, assume it's isosceles. This is kind of cheating, but it works![/quote]

What do you mean by that ?

The answer is going to be a constant?

Thank you.

He's saying that since it is a multiple choice question, the answer would be the same no matter how you fill in the details for the initial conditions, so it would help to consider a special easy-to-calculate case like the isosceles case. However, such obviously wouldn't work for proof-based questions etc.