linear algebra
combinatorics proposed
combinatorics

I am feared if this problem has been posted before. It is a great Graph (or Linear Algebra) problem used in many problems like [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=5656]this one[/url] or a problem from Russia 1999.
Assume that there are number of switches $S_{1},S_{2},\dots,S_{n}$ and number of lamps $L_{1},L_{2},\dots,L_{n}$. Each lamp is on or off. Each switch can change the condition of some of the lamp with the following conditions. $S_{i}$ changes the condition of $L_{i}$ and if $S_{i}$ changes the condition of $L_{j}$ then $S_{j}$ also changes the condition of $L_{i}$. Prove that if all of lamps are off then we can switch all of them on by selecting some of the switches.

It was posted [url=http://www.mathlinks.ro/Forum/viewtopic.php?highlight=linear&t=5976]here[/url] by Darij.

[i]Edit.[/i] Omid, the russian problem was already posted by Remike in thread I gave a link to.

Here is the problem from Russia 1999 :
Suppose all of numbers from $1,\dots,1000000$ are written on blackboard, each number can be white or black, They are white at first. At each step we can choose a number like $n$ and change its color, and also change the color of all numbers $m$ that $gcd(m,n)>1$. Prove that we can change all of them to black.

This problem has also a complicated [i]number theoric [/i]solution


A garden area is 30 ft long and 20 ft wide. A path of uniform width is set around the edge. If the remaining garden area is 400 feet^2. What is the width of the path?

Does anybody have a clue...I sure dont? Help!!!!

[hide="HINT"]
Let the width be $x$.
Then $(20-2x) ( 30-2x) = 400$.
Solve for $x$.
[/hide]

[hide]Since the garden with the path is $600m^{2}({30}\times{20})$, and the remaining area of the garden is $400m^{2}$, then the area of the path is $200m^{2}(600-400)$.
Supposing the width is $x$,
$2(30x)+2x(20-2x)=400$
$60x+40x-4x^{2}=400$
$100x-4x^{2}=400$
$25x-x^{2}=100$
$x^{2}-25x=-100$
$x^{2}-25x+100=0$

You can just solve the equation.[/hide]

My method uses a quadratic equation, which corresponds with the title; [b]Quadratic Land Scaping[/b]


floor function
calculus
derivative
inequalities

Prove that $\lfloor \sqrt[3]{n}+\sqrt[3]{n+1}+\sqrt[3]{n+2}\rfloor =\lfloor \sqrt[3]{27n+26}\rfloor$ for all positive integers $n$.

Let $ n \plus{} 1 \equal{} m$ then we need to show that
\[ \lfloor \sqrt [3]{m \minus{} 1} \plus{} \sqrt [3]{m} \plus{} \sqrt [3]{m \plus{} 1}\rfloor \equal{} \lfloor \sqrt [3]{27m \minus{} 1}\rfloor.
\]
For $ m < 10$ this equality can be verified instantly. For the rest of the proof assume that $ m\geq 10$.

It easy to see (comparing derivatives) that for $ m\geq 10$,
\[ (\sqrt [3]{m \minus{} 1} \plus{} \sqrt [3]{m \plus{} 1})^3 > 8m \minus{} \frac {8}{27}.
\]
Also, according to the power mean inequality, comparing the arithmetic and the power $ \frac{1}{3}$ means of $ m\minus{}1$ and $ m\plus{}1$, we have
\[ 2\sqrt [3]{m} > \sqrt [3]{m \minus{} 1} \plus{} \sqrt [3]{m \plus{} 1}.
\]
Therefore,
\[ 2\sqrt [3]{m} > \sqrt [3]{m \minus{} 1} \plus{} \sqrt [3]{m \plus{} 1} > 2\sqrt [3]{m \minus{} \frac {1}{27}}
\]
implying that
\[ \sqrt [3]{27m} \equal{} 3\sqrt [3]{m} > \sqrt [3]{m \minus{} 1} \plus{} \sqrt [3]{m} \plus{} \sqrt [3]{m \plus{} 1} > 3\sqrt [3]{m \minus{} \frac {1}{27}} \equal{} \sqrt [3]{27m \minus{} 1}.
\]
Since there cannot be any integer strictly in between $ \sqrt [3]{27m \minus{} 1}$ and $ \sqrt [3]{27m}$, we have
\[ \lfloor \sqrt [3]{m \minus{} 1} \plus{} \sqrt [3]{m} \plus{} \sqrt [3]{m \plus{} 1}\rfloor \equal{} \lfloor \sqrt [3]{27m \minus{} 1}\rfloor.
\]
Q.E.D.


I just took the 2005 State round.  (and 2006, and 2007, and 2008, but that's beside the point)  Anyway, I scored a 42 (this wasn't under timed conditions, finished in ~25 minutes for sprint and ~5 minutes total for target).  I misread #1 on Target, misread #24 on Sprint, and mis-arithmeticed (that's not a word, is it?) #25.

Anyway, whenever I go back and check my work in a real timed condition, I don't catch my misreads.  I only catch my arithmetic errors 1/2 times.  I'd like some tips on a) avoiding misreads and b) making sure my arithmetic doesn't fail.

Thanks in advance.

First of all, have you read [url=http://www.artofproblemsolving.com/Resources/AoPS_R_A_Mistakes.php]this[/url]?

Yes, and I used those strategies on AIME.  I ended up with 2 arithmetic errors.

Don't check your work then. Take out a whole new sheet and do the problem again.


I offer you two sealed envelopes.  I tell you that one has twice as much money as the other one, but I don't tell you which envelope is which.  You choose an envelope and open it and find it has $10, at which point you can keep the money that you find inside it, or switch and keep the money in the other envelope.  What is the expected value of your winnings if you switch to the other envelope?  Express your answer as a dollar value.

The two possibilities for the other envelope are $ \$20$ and $ \$5$.  Thus, the answer is $ \frac{20\plus{}5}{2}$, or $ \boxed{\$12.50}$.


conics
parabola
ellipse
analytic geometry
algebra
system of equations
linear algebra

Conic section can be written as ax^2 + bxy +cy^2 + dx + ey = 1.  The points are (-1,0) (0,1) (-2,2) (1,5) (6,0). How do you find the equation to the conic? Then suppose to define it as a parabola, ellipse, or hyerbola.

How else?  This is linear algebra.  Plug in the coordinates to the general form and set up a system of equations for the coefficients.


Let  $ a, b, c$ be positive real numbers. Prove o disprove that

$ \sum\frac{a \plus{} 3b}{b(b \plus{} c)^2} \ge \frac{9}{ab \plus{} bc \plus{} ca}$ .

_________________
 :idea:  :lol:

[quote="nguoivn"]It's obviously because:
$ \sum\ \frac {a \plus{} b}{b(b \plus{} c)^2} \geq\ \frac {9}{2(ab \plus{} bc \plus{} ca)}$   (with Am-GM)
And using Iran 96
 :maybe:  :ninja:[/quote]

Dear nguoivn, I wait for a more elegant resolution
Sorry  :)

[quote="nguoivn"]It's obviously because:
$ \sum\ \frac {a \plus{} b}{b(b \plus{} c)^2} \geq\ \frac {9}{2(ab \plus{} bc \plus{} ca)}$   (with Am-GM)
 :maybe:  :ninja:[/quote]
Using Am-Gm, we need to prove:
$ (ab\plus{}bc\plus{}ca)^3 \geq\ \frac{27}{8}(ab\plus{}bc)(bc\plus{}ca)(ca\plus{}ab)$
It's Am-Gm  :)
Verry sorry because I have some problems with some terminal tests . So, I don't have time to post full proof. After 7 days, I'll post my full proofs for your ineqs.  :blush:


The list of USAMO qualifiers is now posted on http://www.unl.edu/amc/

Congrats to 26 qualifiers from Canada (3 AB, 7 BC, 14 ON, 2 QC).

Shi Danny	12	Sir Winston Churchill HS Calgary AB
Sun Jarno	12	Western  HS Calgary AB
Sardarli Mariya	9	McKernan Edmonton AB
Lim Ursula Anne	8	Burnaby North SS Burnaby BC
Chen Chuan Shi	11	Boston Academy Coquitlam BC
Park Sooyoun	11	Gleaneagle SS Coquitlam BC
Cheng Robin	11	Pinetree SS Coquitlam BC
Zhou Jonathan	11	Pinetree SS Coquitlam BC
Sun Julian	12	Sir Winston Churchill SS Vancouver BC
Zhu Yu Qi	11	University Hill SS Vancouver BC
Liu Zhiqiang	11	Don Mills CI Don Mills ON
Zeng Joe	10	Don Mills CI Don Mills ON
Rickards James	9	Colonel By SS Gloucester ON
Sun Chen	11	A B Lucas SS London ON
Wong Ming Jinq	12	A B Lucas SS London ON
Choi Wonjohn	10	Elpis College Mississauga ON
Chen Richard	11	Olympiads School North York ON
Zhou Kevin	9	Olympiads School North York ON
Guo Leo	11	Dr Norman Bethune CI Scarborough ON
Alman Joshua	11	University Of Toronto Schools Toronto ON
Schneider Jonathan	11	University Of Toronto Schools Toronto ON
Ban Frank	12	Vincent Massey SS Windsor ON
Duyck James	11	Vincent Massey SS Windsor ON
Wen Weinan Peter	12	Vincent Massey SS Windsor ON
Hu Zhebin	12	Marianopolis College Montreal QC
Lvov Nikita	12	Marianopolis College Montreal QC

[quote="Complex_Ninja"][quote="sdkudrgn88"]Apparently I'm from Don Mills, ON.

It's actually Toronto, but for some reason, they have really old names in the sheets. Or it could be the fact that the teachers accidentally put "Don Mills, ON" on the location stamp. I mean, I'd understand "North York", but "Don Mills"?

BTW, I'm the 10th-grader, "Zeng, Joe".[/quote]

What was your score on the AIME and did you take AMC 12?[/quote]

No, I took AMC 10 (150). I forget what my score on the AIME was, but it was definitely at least 7, which brings me above both the index (220/215) and AIME (7/7) requirements.

[quote="sdkudrgn88"]
No, I took AMC 10 (150). I forget what my score on the AIME was, but it was definitely at least 7, which brings me above both the index (220/215) and AIME (7/7) requirements.[/quote]

220 is really good. Anyone know why Alex Song is not on the list? Did he even take AMC/AIME this year?

[quote="jix"]Didn't make it, oh well, guess I'll try again next year.[/quote]
Jix? That's you? I guess it's because you only answered 7 questions... and because you care about physics more. XD

[quote="giovanni"]220 is really good. Anyone know why Alex Song is not on the list? Did he even take AMC/AIME this year?[/quote]
Sorry, don't know who he is. I think I've heard the name before...

And it might be higher than 220 (Perhaps 230 or 240, if I'm lucky). All I know is that I made it and I desperately need practice.

[quote="soledad42"]This year they actually posted all Canadians before the Americans on the qualifiers list. Hopefully (or more like a wish) that this pattern will resume on the USAMO winners/HM list.[/quote]

What if there is none? :P

My observations:

1. Danny posts every time after Jarno does.

2. I post every time after Danny does.

3. Chen made it. :rotfl:

And I post every time you guys start posting :P
Yes, a moose will be writing USAMO this year :rotfl:

[quote="soledad42"]This year they actually posted all Canadians before the Americans on the qualifiers list. Hopefully (or more like a wish) that this pattern will resume on the USAMO winners/HM list.[/quote]

Well, then again, it's only because Canada is alphabetically before USA. The one Korean qualifier also appeared between Canada and USA.

I wonder if the USA will allow Canadians to qualify for MOSP... then it would be an even greater brain drain, which would suck.

[quote="U§ername"]J.S= Julian Sun? o.o[/quote]

J.S = Julian Sun, Jon Schneider, Jarno Sun. So, which one would you like? :)


Circle P of radius 9 is tangent to sides AD and DC of rectangle ABCD with dimensions DC=24 and BC=x. Circle Q of radius 6 is tangent to AB, BC, and circle P. What is the value of x?

[geogebra]46ea88d0a7666d88b34f22a2d9daaf4eacfd69d0[/geogebra]
$ (x\minus{}15)\equal{}12$, so $ x\equal{}27$


The equilibrium constant for the reaction CO(g) + H2O(g) <-----> CO2(g) + H2(g) is 4 at 1000 K. When equilibrium mixtures of CO and H2O are heated to 1000 K, the percentage of CO2 formed at equilibrium is:

A)67
B)33
C)50
D)78

The words used "[u]equilibrium mixtures[/u] of CO and H2O" are confusing me. Does anyone know the solution?

The question is better phrased as:

When an [b]equimolar[/b] mixture of CO and H2O are heated to 1000K, what is the percentage mole fraction of CO2 at equilibrium?

In that case, the answer should be 33%


aya mishe too fazaye 4 bo'odi parche baft? :)

[quote="hoda_h21"]age beshe too fazaaye se bodi nakh risid ehtemaalan beshe too fazaaye 4 bodi ham paarche baft.[/quote]

alan risidan nakh to fazaye chand bodi anjam mishe?

in harf az rooye nazarieye zir gofte mishe:
fazaye $4$ bodi az nazare ma (fazaye $3$ bodi) mese fazaye $3$ bodi tooye bode dovome
yani didane bode chaharom dar bode sevom mese didane bode sevom tooye bode dovome

tooye fazye 4 bodi har gere dar fazaye 3 bodi baz mishe. Hamoon tor ke har gere dar fazaye 2 bodi dar fazaye 3bodi baz mishe


geometry
trigonometry
inequalities
circumcircle
geometry proposed

$ABC$ is an arbitrary triangle. $A',B',C'$ are midpoints of arcs $BC, AC, AB$. Sides of triangle $ABC$, intersect sides of triangle $A'B'C'$ at points $P,Q,R,S,T,F$. Prove that \[\frac{S_{PQRSTF}}{S_{ABC}}=1-\frac{ab+ac+bc}{(a+b+c)^{2}}\]

I have made this problem as follows before.

Find the minimum value of $\frac{S_{PQRSTF}}{S_{ABC}}.$

We have: $\frac{S_{PQRSTF}}{S_{ABC}}=1-\frac{ab+bc+ca}{(a+b+c)^{2}}$
$\Longleftrightarrow\frac{S_{AST}+S_{BFP}+S_{CQR}}{S_{ABC}}=\frac{ab+bc+ca}{(a+b+c)^{2}}$
$\Longleftrightarrow\frac{AS\cdot AT}{AB\cdot AC}+\frac{BF\cdot BP}{BA\cdot BC}+\frac{CQ\cdot CR}{CB\cdot CA}=\frac{\sin A\cdot \sin B+\sin B\cdot\sin C+\sin C\cdot\sin A}{\left(\sin A+\sin B+\sin C\right)^{2}}$
$\Longleftrightarrow\frac{AS\cdot AT}{AB\cdot AC}+\frac{BF\cdot BP}{BA\cdot BC}+\frac{CQ\cdot CR}{CB\cdot CA}= \frac{1}{4}\left(\tan\frac{A}{2}\tan\frac{B}{2}\frac{1}{\cos^{2}\frac{C}{2}}+\tan\frac{B}{2}\tan\frac{C}{2}\frac{1}{\cos^{2}\frac{A}{2}}+\tan\frac{C}{2}\tan\frac{A}{2}\frac{1}{\cos^{2}\frac{B}{2}}\right)$
On the otherhand, we have:
$\frac{AT}{AB}=\frac{\sin\widehat{AC'T}}{\sin\widehat{BC'T}+\sin\widehat{AC'T}}=\frac{\sin\frac{B}{2}}{\sin\left(A+\frac{B}{2}\right)+\sin\frac{B}{2}}=\frac{\sin\frac{B}{2}}{2\cos\frac{C}{2}\cos\frac{A}{2}}$
Similar: $\frac{AS}{AC}=\frac{\sin\frac{C}{2}}{2\cos\frac{A}{2}\cos\frac{B}{2}}$
Hence: $\sum \frac{AS\cdot AT}{AB\cdot AC}=\sum\frac{1}{4}\tan\frac{B}{2}\tan\frac{C}{2}\frac{1}{\cos^{2}\frac{A}{2}}\quad\mathbb{QED}$

From this problem, we have: $S_{PQRSTF}\ge\frac{2}{3}S_{ABC}$
On the otherhand, we also have that: $\boxed{S_{PQRSTF}\le\frac{2}{3}S_{A'B'C'}}$

[color=darkblue][b]Proof.[/b] Denote $S\equiv [ABC]$, $S_{h}\equiv [PQRSTF]$, $S'\equiv [A'B'C']$.

Suppose $\{P,Q\}\subset BC$, $\{R,S\}\subset CA$, $\{T,F\}\subset AB$.

Prove easily that $AA'\perp B'C'$. Thus, $\{\begin{array}{c}B'A=B'I\ ,\ IB\cdot IB'=2Rr\\\ \frac{TA}{TB}=\frac{B'A}{B'B}\end{array}$ $\Longrightarrow$

$\frac{TA}{IB'}=\frac{TB}{IB'+IB}=\frac{c}{2\cdot IB'+IB}$ $\Longrightarrow$ $TA=$ $\frac{c\cdot IB'}{2\cdot IB'+IB}=$
$\frac{c\cdot IB'\cdot IB}{2\cdot IB'\cdot IB+IB^{2}}=$ $\frac{c\cdot 2Rr}{4Rr+\frac{ac(p-b)}{p}}=$ $\frac{4Rrp\cdot c}{8Rrp+2ac(p-b)}=$
$\frac{abc\cdot c}{2abc+2ac(p-b)}=$ $\frac{bc}{2b+(a+c-b)}=$ $\frac{bc}{2p}\Longrightarrow$ $\boxed{TA=\frac{bc}{2p}}$. Therefore,
$S_{h}=S-\sum(\frac{bc}{2p})^{2}\sin A=S-\frac{S}{4p^{2}}\cdot\sum bc=S\cdot[1-\frac{ab+bc+ca}{(a+b+c)^{2}}]$.
$ab+bc+ca=p^{2}+r^{2}+4Rr\Longrightarrow$ $\boxed{S_{h}=\frac{r}{4p}\cdot(3p^{2}-r^{2}-4Rr)}$.
[b]Remarks.[/b]

$1.\blacktriangleright\{\begin{array}{c}3(ab+bc+ca)\le (a+b+c)^{2}\Longrightarrow \boxed{S_{h}\ge \frac{2}{3}\cdot S}\\\ S'=2R^{2}\cos\frac{A}{2}\cos\frac{B}{2}\cos\frac{C}{2}=\frac{pR}{2}\Longrightarrow \boxed{S'=\frac{pR}{2}}\ge pr=S\Longrightarrow \boxed{S'\ge S}\end{array}$.

$2.\blacktriangleright\sqrt 3\le\frac{4R+r}{p}\le\frac{p}{3r}$ $\Longrightarrow$ $S_{h}=\frac{r}{4p}\cdot[3p^{2}-r(4R+r)]\le$
$\frac{r}{4p}\cdot [(4R+r)^{2}-r(4R+r)]=$ $\frac{Rr(4R+r)}{p}\le$ $\frac{Rp}{3}=$ $\frac{2}{3}\cdot S'$ $\Longrightarrow$ $\boxed{S_{h}\le\frac{2}{3}\cdot S'}$.
In conclusion, $\boxed{\frac{2}{3}\cdot S\le S_{h}\le\frac{2}{3}\cdot S'}$.[/color]

Thank you, [color=indigo][b]Mr. Virgil Nicula[/b][/color] :lol:
And now, I'll present my solution. (more ugly)

Denote: $I=AA'\cap BB'\cap CC';\, X=AA'\cap BC$
We have:
 $S_{PQRSTF}\le\frac{2}{3}S_{A'B'C'}\Longleftrightarrow\sum S_{A'PQ}\ge\frac{1}{3}S_{A'B'C'}\Longleftrightarrow\sum\frac{S_{A'PQ}}{S_{A'B'C'}}\ge\frac{1}{3}\\ \Longleftrightarrow\sum\left(\frac{PQ}{B'C'}\right)^{2}\ge\frac{1}{3}\Longleftrightarrow\sum\left(\frac{PQ}{BC}\cdot\frac{BC}{B'C'}\right)^{2}\ge\frac{1}{3}\\ \Longleftrightarrow\sum\left(\frac{AI}{IX}\cdot\frac{\sin A}{\sin\frac{B+C}{2}}\right)^{2}\ge\frac{1}{3}\Longleftrightarrow\sum\left(\frac{a}{a+b+c}\cdot 2\sin\frac{A}{2}\right)^{2}\ge\frac{1}{3}\\ \Longleftrightarrow\sum a^{2}\sin^{2}\frac{A}{2}\ge\frac{1}{12}\left(\sum a\right)^{2}\quad (*)$
Now, WLOG, assume that: $a\ge b\ge c\Longrightarrow 90^\circ >\frac{A}{2}\ge\frac{B}{2}\ge\frac{C}{2}>0\Longleftrightarrow\sin\frac{A}{2}\ge\sin\frac{B}{2}\ge\sin\frac{C}{2}$
And then, applying the [b]Chebyshev Inequality[/b], we have:
$\sum a^{2}\sin^{2}\frac{A}{2}\ge\frac{1}{3}\left(\sum a^{2}\right)\left(\sum\sin^{2}\frac{A}{2}\right)\ge\frac{1}{9}\left(\sum a\right)^{2}\cdot\frac{3}{4}=\frac{1}{12}\left(\sum a\right)^{2}$

[hide="Open question..."] [quote] The triangle $ABC$ has the incircle center $I.$ The line $AI,\,BI,\,CI$ cut the circumcircle of triangle $ABC$ respectively at $A',\,B',\,C'.$ Sides of triangle $ABC$ intersec sides of triangle $A'B'C'$ at points $P,\,Q,\,R,\,T,\,S.$ Hence we have:
\[\boxed{\frac{2}{3}S_{ABC}\le S_{PQRSTF}\le \frac{2}{3}S_{A'B'C'}}\]
[/quote]
Is this result right when we change $I$ by circumcentre center, orthocentre or centroid of triangle $ABC$? [/hide]

[color=darkblue][b][u]Remark (extension).[/u][/b] For a interior point $P$ of $\triangle ABC$ denote : $\{\begin{array}{c}m(\widehat{PAB})=x\\\ m(\widehat{PBC}=y\\\ m(\widehat{PCA})=z\end{array}$ ;

the second intersections $A'$, $B'$, $C'$ of the lines $AP$, $BP$, $CP$ respectively

with the circumcircle of $\triangle ABC$ ; the points $\{\begin{array}{c}S\in AC\cap B'C'\\\ T\in AB\cap B'C'\end{array}$.

Then $\{\begin{array}{c}AT\sin (A+y+z)=AS\sin (y+z)=2R\sin z\sin (B-y)\\\\ \boxed{[ATS]=2R^{2}\cdot\frac{\sin^{2}z\sin^{2}(B-y)}{\sin (y+z)\sin (A+y+z)}}\end{array}$.

Try the previous particular case $\{\begin{array}{c}x: =\frac{A}{2}\\\\ y: =\frac{B}{2}\\\\ z: =\frac{C}{2}\end{array}\|$ $\Longrightarrow$ $AT=AS=\frac{bc}{2p}$ a.s.o.

I think that this relation can be used for another problems.

[/color]


Does anyone here sit for the Australian Mathematics Competition? It doesn't seem to be well known worldwide although the questions are challenging and interesting.

I don't, so I haven't got to see the questions yet.  Do you know where we could find questions?

I'm afraid it's pretty hard to find Australian Math Competition questions on the Internet because they are strictly copyrighted. You can see some samples at the website http://www.amt.edu.au/ though.  :)

I can't see the samples on the site.  Could you show where I can find the samples?

Thanks

The exact URL address is here:

http://www.amt.edu.au/wuamc.html

Have fun.

Thanks

These questions seem easier than the questions that you posted on the Getting Started Forum.

Yeah.. that's because the questions I posted on the getting started forum are from the more recent competitions (2000 and later) while those on the website are from 2000 and before. The questions have been getting harder lately.

I was placed within the top 1% in 2005, and will be sitting the test again.

It is ony July 27

Hmm that is good news. However since I'm in the senior division, I will only have to be the top 5% to get a high distinction.  :lol:

Hehe, special cut-offs  :lol:

I'll still be doing the intermediate paper, but I'm sure there will some questions that are used for both categories.

Next Thursday baby!


If $ a, b, c$ are positive intergers and $ a^2\plus{}b^2\plus{}c^2\equal{}2(ab\plus{}bc\plus{}ca)$, prove that $ a, b, c$ are perfect squares.

try $ a\equal{}2$  $ b\equal{}2$  $ c\equal{}8$


Could anybody let me know about " Fréchet–Urysohn fans"? or give some links about it?

thanks


I want to offer you an idea of earnings,
an idea which will help you, and if not,
then you can forget about everything that could improve your life!
And when you'll be asked " you knew about this, you had an opportunity,
and you didn't take it, and now you live so bad,
you could have been with us on the top ! " What will you answer ? See
this video,
and think about it - http://www.fit.lv/video/wellness.htm .
If you are interested and you are determined to live better,
write me and I'll tell you all about this - fitline1@gmail.com


The points $ (0,0)$, $ (1,7)$, $ (6,8)$, $ (10,3)$, $ (2,2)$ and $ (0,0)$ are connected in order to form a pentagon. How many square units are in the area of the pentagon?

[asy]pair A=(0,0), B=(1,7), C=(6,8), D=(10,3), E=(2,2);

for(int n=0; n <= 10; ++n)
draw((n,0)--(n,10)^^(0,n)--(10,n));

draw(A--B--C--D--E--cycle);

dot(A^^B^^C^^D^^E);

label("$A$",A,SW);
label("$B$",B,NW);
label("$C$",C,NE);
label("$D$",D,SE);
label("$E$",E,SE);[/asy]

So,
A:Area A of all the polygon's vertices are grid points
I:Interior points located in the polygon
B:Boundary points placed on the polygon's perimeter
$ A \equal{} I \plus{} \frac {B}{2} \minus{} 1 \equal{} 39 \plus{} \frac {6}{2} \minus{} 1 \equal{} \boxed{41}$.
(By [url=http://en.wikipedia.org/wiki/Pick%27s_theorem]Pick's theorem[/url])

Is there a way to do this quickly, in your head?


real analysis
real analysis unsolved
partial differential equations

$ Lu\equal{}\minus{}\sum_{i,j\equal{}1}^n (a_{ij}u_{x_i})_{x_j}$, where $ a_{ij}$ are $ C^{\infty}$. And $ \lambda _1>0$ is principal eigenvalue of $ L$.
Then if $ u$ is a weak solution of the equation: $ Lu\equal{}\lambda _1 u$ on $ U$ and $ u\equal{}0$ on $ \partial U$, and $ u$ is not identically zero,

prove: $ u>0$ on $ U$ or $ u<0$ on $ U$.

Evans' book "PDE" gave a proof: he proved that $ u^\plus{}$ and $ u^\minus{}$  are both weak solutions of the equation above (and hence both smooth).
And by strong maximum principle, $ u^\plus{}$ and $ u^\minus{}$  are both positive. But then why $ u\equal{}u^\plus{}\minus{}u^\minus{}$ is wither positive or negative?
Did I miss something obvious? is it because of $ u$ has to be smooth?

(Evans p339).

[quote]And by strong maximum principle, $ u^\plus{}$ and $ u^\minus{}$ are both positive.[/quote]
More precisely: each of them is either positive everywhere, or identically zero. Since $ u^\plus{}$ and $ u^\minus{}$ cannot be both positive at the same point (look at their definitions), one of them has to be identically zero.


Let $ a,b,c$ positive reals. Prove that

$ \sum(\sqrt{a}\plus{}\sqrt[3]{b}\plus{}\sqrt[6]{c})\leq\frac{3}{4}\sqrt[3]{\frac{(a\plus{}b)^2(b\plus{}c)^2(c\plus{}a)^2}{abc}}\plus{}6$

From the AMGM, $ \sum \sqrt{a}\plus{}\sqrt[3]{b}\plus{}\sqrt[6]{c}\leq\sum_{cyc}\frac{a\plus{}1}{2}\plus{}\frac{b\plus{}2}{3}\plus{}\frac{c\plus{}5}{6}$
$ \equal{}(a\plus{}b\plus{}c)(\frac{1}{2}\plus{}\frac{1}{3}\plus{}\frac{1}{6})\plus{}\frac{3}{2}\plus{}2\plus{}\frac{5}{2}\equal{}a\plus{}b\plus{}c\plus{}6$.

So we only have to prove $ \frac{3}{4}\sqrt[3]{\frac{(a\plus{}b)^{2}(b\plus{}c)^{2}(c\plus{}a)^{2}}{abc}}\geq a\plus{}b\plus{}c\iff 27\prod_{cyc}(a\plus{}b)^2\geq64abc(a\plus{}b\plus{}c)^3$

Now from AMGM, $ \sum_{sym}a^2b\geq6abc\iff9\prod(a\plus{}b)\geq8(a\plus{}b\plus{}c)(ab\plus{}bc\plus{}ca)$
$ \therefore27\prod_{cyc}(a\plus{}b)^2\geq\frac{64}{3}(a\plus{}b\plus{}c)^2(ab\plus{}bc\plus{}ca)^2\geq64(a\plus{}b\plus{}c)^3abc$ from Newton's inequality.

[quote="bakerbakura"]From the AMGM, $ \sum \sqrt {a} \plus{} \sqrt [3]{b} \plus{} \sqrt [6]{c}\leq\sum_{cyc}\frac {a \plus{} 1}{2} \plus{} \frac {b \plus{} 2}{3} \plus{} \frac {c \plus{} 5}{6}$
$ \equal{} (a \plus{} b \plus{} c)(\frac {1}{2} \plus{} \frac {1}{3} \plus{} \frac {1}{6}) \plus{} \frac {3}{2} \plus{} 2 \plus{} \frac {5}{2} \equal{} a \plus{} b \plus{} c \plus{} 6$.

So we only have to prove $ \frac {3}{4}\sqrt [3]{\frac {(a \plus{} b)^{2}(b \plus{} c)^{2}(c \plus{} a)^{2}}{abc}}\geq a \plus{} b \plus{} c\iff 27\prod_{cyc}(a \plus{} b)^2\geq64abc(a \plus{} b \plus{} c)^3$

Now from AMGM, $ \sum_{sym}a^2b\geq6abc\iff9\prod(a \plus{} b)\geq8(a \plus{} b \plus{} c)(ab \plus{} bc \plus{} ca)$
$ \therefore27\prod_{cyc}(a \plus{} b)^2\geq\frac {64}{3}(a \plus{} b \plus{} c)^2(ab \plus{} bc \plus{} ca)^2\geq64(a \plus{} b \plus{} c)^3abc$ from Newton's inequality.[/quote]

Thanks my Friend  :)


quadratics
algebra
quadratic formula
polynomial
Rational Root Theorem

Find all natural numbers $n$ such that $x^4+nx^2+9$ is factorizable.

[quote="E^(pi*i)=-1"][hide]If we write $y=x^2$, we have $y^2+ny+9$.  9 can be factorized as 9*1, -9*-1, 3*3, and -3*-3, so n could be 10, -10, 6, or -6 (the sums of the four pairs).[/hide][/quote]

I am afraid you missed the case where $x^4 + nx^2 + 9$ can be factored into a linear and cubic factor.   :)  (Edit:  Or, at least, failed to show that no new solutions are produced in this case)

[quote="E^(pi*i)=-1"][hide]If we write $y=x^2$, we have $y^2+ny+9$.  9 can be factorized as 9*1, -9*-1, 3*3, and -3*-3, so n could be 10, -10, 6, or -6 (the sums of the four pairs).[/hide][/quote]
$n$ is a natural number ;)

Your logic is correct, but there are other possible cases, too. Can you find more? :)

factorable over what? integers, rationals, reals, imaginary?

but we need to do the case work for:
4 linears, 2 linears and 1 quadratic, 1 linear 1 cubic, 2 quadratic

we can apply the quadratic formula to factor with the factor theorem, and also use the rational root theorem for the cubic/linear

Well, what I meant was:

Find all natural numbers $n$ such that $x^4+nx^2+9$ can be written as a product of two or more factors, where each factor has integer coefficients.

But this doesn't mean that each factor has to be linear. For instance, $x^4+10x^2+9=(x^2+1)(x^2+9)$ (which is one of the answers that E^(pi*i)=-1 got) still counts although you could factorize it further to get $(x-i)(x+i)(x-3i)(x+3i)$. It doesn't matter whether you end up with linear factors or not.

Hope this clarifies Altheman's question... Or is this still unclear?

So, wait - we're factoring over $\mathbb{C}$?  That is, could we find a factoring with integer complex coefficients that can't be expressed as a product of two or more factors with integer real coefficients?

Ok, think this way...

Let's say you don't know anything about imaginary numbers.
$x^4+10x^2+9$ is still factorizable since it can be expressed as $(x^2+1)(x^2+9)$.

In order to factor this [i]completely[/i], the expression becomes a product of factors where each factor contain imaginary numbers, but that's not what I'm talking about... Does it make sense? :|

Sorry for the confusions.

P.S. I think there would be so many possibilities for $n$ if you were allowed to factor over complex numbers. :roll:

just saying that it is [b]over integers[/b] is what i was looking for

to factor it into a linear and a cubic, by rrt, rational roots iff factors of 9, (noticing the x^2) we set f(1,3,9)=0 to solve for n, then factor

then we can use the y=x^2, and do the same rational root thing to simplify into quadratics

the only thing that this does not cover is if the quadratics that it is factored into have nonzero x terms but we do know that the x terms will have to be opposite for the sum of the roots to be 0...so expand
$(x^2-ax+b)(x^2+ax+c)$
and compare coefficients


logarithms
combinatorics unsolved
combinatorics

A graph $G$ with $n$ vertices is called [i]cool[/i] if we can label each vertex with a different positive integer not greater than $\frac{n^2}{4}$ and find a set of non-negative integers $D$ so that there is an edge between two vertices iff the difference between their labels is in $D$. Show that if $n$ is sufficiently large we can always find a graph with $n$ vertices which is not cool.

Unless I'm messing up my calculations, you can actually get all the way up to $n^2/k$ for any $k>2$ and still have uncool graphs.

A graph is completely determined by the labellings of the vertices and the set $D$.

There are $\frac{(\frac{n^2}{4})!}{(\frac{n^2}{4}-n)!}<(\frac{n^2}{4})^n$ choices for the how to label the vertices and $2^{\frac{n^2}{4}}$ choices for the set $D$, so there are at most $(\frac{n^2}{4})^n (2^{\frac{n^2}{4}})$ cool graphs.

The number of graphs on $n$ vertices, however, is $2^{\frac{n^2-n}{2}}$ (each edge is either in the graph or not in the graph).

Taking logs, the log base 2 of the number of cool graphs is at most $n( 2 \log n - \log 4) +\frac{n^2}{4}$
The log base 2 of the number of total graphs is $\frac{n^2-n}{2}$.  Since there are more total graphs than cool graphs for large $n$, some graph must not be cool.

Even if this is right, it's rather nonconstructive.  Can anyone give an example of uncool graphs on arbitrarily many vertices?


superior algebra
superior algebra unsolved

I have solved a problem & I am not sure whether its correct or not.

I haven't read your solution, I just looked at the problem:

Show that a non-trivial normal group $N$ of a $p$-group $G$ has non-trivial intersection with the cente $Z$ of $G$.

Here's a solution. From what I could tell, it's different from yours.

Consider the action by conjugation of $G$ on $N$, and write the class equation (if that's what it's called in English :)):

$|N|=|N\cap Z|+\sum Orb(x)$, where the sum is taken after a set of representatives $x$ for the non-trivial orbits of the action. Since the orbits in the sum satisfy $|Orb(x)|=[G:C_G(x)]$, where $C_G(x)$ is the centralizer of $x$, and the orbits are non-trivial, it means that the sum is divisible by $p$, because all its terms are divisible by $p$. Since $|N|$ is also divisible by $p$, we get $p||N\cap Z|$, and, since $|N\cap Z|\ge 1$, we find that $N\cap Z\ne\{1\}$, Q.E.D.

Yes its a very nice solution.I have done the problem after some hard work & I will highly appreciate if anyone can say whether its correct or not.

by the way my sol. uses the cosets & the 1-1 correspondence between left & rt cosets.But the basis is the same.


AMC
AMC 12
AMC 12 B
probability
geometry

i dont get solutions packets so who knows the answers :D i already acknowledged that i suck and probably did horrible (and by horrible no, i didn't get a 144)

lol  :)

[quote="unimpossible"]lol

at first i thought i got 126.
then 120
then 114
now im at 108.

lol[/quote]
Same here, excapet I went from 114 to 108...not much of a drop.
BTW, I just really need the answer to 13...or whatever was the weird equilateral triangle and square concerning probability.

#13 wasn't probability, but:

EBCDC AACAB ABBCC BCEBB EEACB

dude, the AMC is becoming very very tricky, the four E's are at 1,18,21,22. There is a total of one D. on the A, there was one E, and eleven D's.

Eh, whatever.
I mean the problem concerning equilateral triangle ABE which is inscribed in a square, and you pick a point and what's the probability that that point is between 1/3 and 2/3 from AD.

EDIT:Uh...I'm pretty sure it was...

That was #13, but it asked for the area of the region, not the probability.

CatalystOfNostalgia: Thanks a lot for the answers.

Oops, my bad. Confused it with something else.
Doesn't matter, I got it right :)


function
real analysis
real analysis unsolved

$f$ is differetiable on $[a,b]$ and $f'(x) = 0 \mbox{ a.e. } x\in[a,b]$. Show that $f$ is a constant function on $[a,b]$.

Let $A$ such that : $A = \{a \in [a,b] | f'(x)\neq 0\}$
$f'(x) = 0 \mbox{ a.e. } x\in[a,b] \Longrightarrow A$ is  countable set.
Let $x_0$ such that $f'(x_0)=0$. But  $f'$ has the Darboux property so if $f'(u)\neq 0=f'(x_0)$ then there is a set $B$ such that $f'(B) = ]0,f'(u)]$ so $B$ is uncountable .
But $B \subset A \Longrightarrow A$   uncountable set : contradiction !
Finally $f'(x)=0 \forall_{x\in [a,b]} \Longrightarrow f(x)=constant$
:cool:  Of course there is less complicated proof, because $\{x\in  [a,b] | f'(x)=0\} $ is dense in $[a,b]$ :cool:

[quote="grobber"]I think you only know that $A$ has measure zero, not that it is countable... :?[/quote]

:cool:  God said to me : Man, If usual_mesure(A)=0 then A is countable ! :cool:

Is it true?

[I'm sure it's not true :)]

Of course it's not true...Think about Cantor's set...  :?

There is a theorem : $f$ is differentiable on $[a,b]$ and $f' \in L([a,b])$, then $f$ is absolutely continuous on $[a,b]$.

The conclusion follows from the theorem immediately.... But I'd like not to use it... (the proof of the theorem is not that simple...)

:blush:  My  God , big mistake !  :blush:


linear algebra
matrix
group theory
superior algebra
superior algebra unsolved

Yes it is. (If $ C\equal{}\mathbb{C}$ ;-) )

I have already found a solution in a book. It is not trivial at all.

Well, nobody said that it is easy ;-)

But if you like, have a look in Artin - Algebra. There is a very elementary proof (it uses just a few matrix calculations and some very simple facts from group theory) that $ PSL_{2}(K)$ is simple for $ K\neq\mathbb{F}_{2}$ and $ K\neq\mathbb{F}_{3}$.


quadratics
algebra
quadratic formula
algebra theorems

I've got a pretty good prove concerning the summation of different powers of two roots:
$x_{1}^{n}+x_{2}^{n}$ can be found by a recurrence relation.
However, how can I find that of the difference between them ?
$x_{1}^{n}-x_{2}^{n}$
Is it a little similar?

I assume that $ x_{1}$ and $ x_{2}$ are the roots of a quadratic equation $ ax^{2}+bx+c=0$, where $ a\neq 0$. Then if $ x$ is either root, $ ax^{n}+bx^{n-1}+cx^{n-2}=0$, or $ x^{n}=\frac{-bx^{n-1}-cx^{n-2}}{a}$. I plug in $ x_{1}$ and $ x_{2}$ respectively for $ x$ and subtract the two resulting equations, getting $ x_{1}^{n}-x_{2}^{n}=\frac{-b(x_{1}^{n-1}-x_{2}^{n-1}-c(x_{1}^{n-2}-x_{2}^{n-2})}{a}$. This is a recurrence for $ x_{1}^{n}-x_{2}^{n}$; now I need initial conditions. Clearly $ x_{1}^{0}-x_{2}^{0}=0$. Using the quadratic formula, I find $ x_{1}^{1}-x_{2}^{1}=\frac{\pm\sqrt{b^{2}-4ac}}{a}$. (The double signs occur because differences, unlike sums, depend on the order in which the roots are listed.) Choosing one sign arbitrarily, you can build up $ x_{1}^{n}-x_{2}^{n}$ for any nonnegative integer $ n$.


Julia jogs at a rate of six miles per hour. What is her rate in feet per second?
Express your answer as a decimal to the nearest tenth.


I haven't got a lot of problems on the math chat today (sadly) and I'm posting some extra problems instead.

Five animals ---> A,B,C,D, and E --- are either wolves or dogs. Dogs always tell the truth while wolves always tell lies. A claims that B is a dog. B claims that C is a wolf. C claims that D is a wolf. E claims that A is a dog. D claims that B and E are different kinds. The number of wolves is:

A) 1
B) 2
C) 3
D) 4
E) 5

This question was adopted from one of the European Math Contest. Forgot what it was called.

[hide]Either A is a wolf, or A is a dog. From there, we can figure out what the others are. If A is a dog, then D, B, and E are dogs. Since D will tell the truth that B and E are different, this way won't work. That means that A, B, D, and E are all wolves, or (d).[/hide]


I went with lifeisacircle, dragon96, and Nerd_of_the_Ages. Miller Middle School pwned all. I got a measly 15th place out of all eighth graders. Darn. Oh well, at least I have a cewlish looking trophy xD

[quote="eggylv999"]1st place 7th grade :D  :D  :D

Redwood teamA was 2nd[/quote]

I will pwn you at teh next one!!!

jkjk

What was your score, and how hard were teh problems?

hmm... im lucky u didn't go. u probably would've beat me on cd.
and NOBODY comment on my ... CLUE: tiebreakers
ANYWAYS...
the problems were insanely easy, (hence how i got first in both cd and indi)
and Victor got destroyed (if u know who he is)

Eh, I probably wouldn't have even made cd.

Anyone going to the [url=http://mathleague.org/jhevents.php]next one[/url]?

[quote="Nerd_of_the_Ages"]OH, now I know you. Didn't you once post a vid on youtube of you playing melee on temple and repeatedly saying yummy? Anyway, gratz. I pretty much screwed my team's score. Doh.[/quote]

yes.  :D

Am I allowed to join someone else's team when I get there?  Because I'm not sure how many people on my team will come, and someone *cough cough* has offered for me to join their team, even though I don't go to their school :D

eggy, I will PWN YOU IN CD if I make it xD

[quote="Nerd_of_the_Ages"]Dude, in the award ceremony, we were sitting right behind your team. ak909090 was screwing with your orange and playing with a yo-yo.

Also, apparently the reason we did not get a team prize was because dragon96 is a 7th grader and we have an 8th grade team, so his score wasn't counted.[/quote]

Terman, right?

Who's Terman?

Nay, that team is from Hopkins (like me, but I didn't go)

Who's terman? NotA? None of use are named Terman.

No not Terman (wherever that is). Hopkins

HAY!  WY IZ Y'ALL IGNORINZ ALL MI POSTS?

$ \text{\LaTeX}$

I went there... 6th place 7th grade...

I remember that orange! That was pretty retarded.

Ummmm... why were you guys like "Who are you? Go AWAY!!!" When I approached you during chapter???

I didn't go to chapter...

I was feeling pretty stupid when our teacher was doing the try-outs.

I went. Not that Kennedy is the smartest of schools, or anything.

Please don't revive threads. I see you are new, so that's okay for now. But in the future, note that you shouldn't post on a thread that is more than thirty days old unless you are asking a question for clarification or bringing up a very important note.

Wasn't this thread for miller math marathon, AIME15 whose team are u gonna join.

varunrocks, this topic is already mentioned as a revived topic, please don't continue posting here.


We have that $ n \in \mathbb{N}^*$. Solve the equation:
\[ \cos^n{x}\minus{}\sin^n{x}\equal{}1.\]

[quote="linker"]We have that $ n \in \mathbb{N}^*$. Solve the equation:
\[ \cos^n{x} \minus{} \sin^n{x} \equal{} 1.
\]
[/quote]
[hide]
For x from 0 to 90, x=0 is the only solution, since both sin and cos are positive but at most 1, and it works for all n.
For x from 90 to 180, cos is negative, and sin is positive. If n is even then the only solution is 180, and all even n work. For odd x, cos is negative, and sin is positive, so no solution.
For x from 180 to 270, cos is negative and sin is negative, so if n were even, there'd be no solutions, as cos is increasing from -1 and sin is decreasing from 0. If n is odd, 270 works.
For x from 270 to 360, cos is positive and sin is negative, but the value is too large, as it's strictly increasing from 270 to 360, so we have for ordered pairs (n,x)
(n,0)
(2k,180)
(2k+1,270)[/hide]


sometimes it's just slow, so be patient and wait for it to load.

or just log out of the classroom and log back in again. thats what i do!

[quote="aufha"]What might be a cause for why new text in the classroom stops appearing for periods of time?

Sometimes I realize that text stops appearing because when I click "view current transcript," the class is much farther ahead than what I see in the chatroom window. What would you do if you were me?[/quote]

Unfortunately, a small percentage of our users have this problem.  Nearly all of them can clear it up by switching to Opera (http://www.opera.com).  We're working on upgrading the classroom, but it will still be 6-12 months before we move away from our current Java chat client.

I am very sure that the problem is Firefox 3.  (What's funny is the beta version didn't have this problem :P )
Once I switched to Opera, it worked a lot better.
:)

Yeah, a lot of people are having trouble with Firefox 3.

The text keeps freezing with me too.  I tried opera and it works sometimes but sometimes the text still freezes.  :(

In the old days you could keep clearing the text and it would unfreeze. Doesn't work anymore :(

Oh well, Opera FTW


When I am installing the complete system of MikTex, I am asked to specify the location of the local package repository. What should I type in now?

The directory in which you have downloaded the miktex packages (assuming you have downloaded them already from the internet).

I have tried, but this didn't work. I was told that the folder didn't represent a valid package directory.

[quote="leepakhin"]I was told that the folder didn't represent a valid package directory.[/quote]That means that you haven't yet downloaded the packages. In that case select "Internet package repository" and download them (the setup file you have does not contain all the files miktex needs).

Where to select? I know now. Thank you very much.

You are welcome. And please stop double-posting (posting one post after another). You can use the [b]edit[/b] button if you forgot to add something and no one has replied yet.


calculus
derivative
function
analytic geometry
graphing lines
slope

Meh, it has something to do with differential calculus, but that's about all I know :)

The derivative of a function is its slope. You don't need to know it for competitions though...although i guess it could potentially be helpful with problems that ask you to find the max/min of something...

the derivative of a function with respect to a variable is a measure of the rate of change of that function with respect to that variable at the given input. so, if you are taking a graphical perspective, if the function is graphed on the y-axis and the variable that you are differentiating with respect to is graphed on the x-axis, the derivative is indeed the tangent line, or "slope", but the more general concept is simply the rate of change.

You can think in terms of physics. The position of an object can be graphed with respect to time. Its rate of change (its derivative) is its velocity. Now the rate of change of the velocitiy (the second derivative of the original function) is acceleration.

the derivative is like the instantaneous rate of change, or slope

take the limit as h approaches 0 of (f(x + h) - f(x))/h

The derivative is the [u]function[/u] that will give a slope at a certain point on a graph. It is found by lim( f(x+h)-f(h))/h. To see why picture a curve and 2 points on it. (x,F(x)) and (x+h, f(x+h)) as the points. Picture the secant line through these points. Its slope is found as the expression above in the limit. As these  two points get closer, with h getting smaller, the slope of the tangent AT the point is that limit. It doesnt really fit the standard definition of slope. Say you want to know were the curvy graph of x^3-5x^2 turns. At the turns the slope is 0. Find the derivative function and set it equal to 0. Solve. It is 3x^2-10^x.I use x because plugging the same x that u would into the function gives you the slope at that point. Or you could plug the x if the problem gives it to you before finding the limit above into that limit expression. But It factors to (3x-10) * x. The tangent has slope 0 at (0,0) and (10/3, -18and 42/99) draw it. and try it with somethin easy like x^2.
Brayden Ware 9th grade


[hide="hint_1"] The sum corresponds to the probability of a certain coin game[/hide]

[hide="hint_2"] The answer is 1[/hide]

[hide="solution"] We note that for each value of $i$, $\binom{i-1}{n-1}2*2^{-i}$ corresponds to the probability that we will flip $n$ heads or tails out of $i$ total flips, with the $n$-th head/tail on the $i$-th flip. Obviously, the sum of this probability from $n$ to $2n-1$ should be 1. [/hide]


function
algebra
polynomial
real analysis
real analysis solved

Prove that if the function $f:\mathbb{R}^2\rightarrow [0,1]$is continuous and its average on every circle of radius one equals the function value at center of the circle,then f is constant.

Or, more generally, let $\mu$ be a compactly supported measure whose Fourier transform vanishes only at the origin. If $f*\mu=0$, then $f$ is constant. The statement is next to obvious if you know the theory of generalized functions but I do not know a completely elementary solution...

The measure $\mu$ that fedja is referring to in this case is normalized arclength measure on the unit circle minus the Dirac $\delta.$ The Fourier transform is (some scaling of) $J_0(r)-1$ and does indeed vanish only at the origin.

Just be sure we acknowledge the role that the boundedness of $f$ plays here. If we leave that condition out, then $f$ can be any harmonic function.

Note that a harmonic function that is also a tempered distribution (i.e., grows no faster than a polynomial) must be a polynomial - and the Fourier transform of a polynomial is supported at the origin.

The (slightly more elementary) path to the proof should go something like this:

1. Show that $f$ must be a harmonic function.

2. Invoke the harmonic function version of Liouville's theorem: a bounded harmonic function on the entire plain must be constant.


A trooper is hidden 50 feet from a highway. Two second after a truck passes, the angle theta between the highway and the line of observation from the patrol car to the truck is measured.

(a) If the angle measures 20 degrees, how fast is the truck traveling? Express your answer in terms of miles per hour.

(b) If the speed limit is 65 miles per hour and a speeding ticket is issued for speeds of 5 miles per hour and more over the limit, for what angles should the trooper issue a ticket?

[hide="Hint"]Use basic trig to find the distance from the highway to the truck. Then just use distance formula ($ d=rt$).[/hide]

[hide="Guide to solving (a)"]A lot of the questions you asked have to do with trignometry. So let's use the trig identities to help us solve this one. First, we start with a picture (see attached picture)

We know the distance from the road to the police is 50 ft. Let's say the distance the truck travels is $ x$

In the first case, the angle $ \theta$ is 20 degrees.

Since we are dealing with the two sides of the triangle that are opposite and adjacent to $ \theta$, it makes sense for us to use tangent.

$ \tan \theta = \frac{opposite}{adjacent}$

$ \tan (20) = \frac{x}{50}$

We can cross multiply to get

$ 50 \tan (20) = x \; ft$

Now we know $ x$ in terms of distance, and we are given a time of $ 2 \; seconds$

We can use the definition of distance to figure out the truck's speed, or rate.

$ distance = (rate)(time)$

We want to find to find rate so isolate that:

$ rate = \frac{distance}{time}$

Plug in the variables we know and we get:

$ rate = \frac{x \; ft}{2 \; sec}$

Plug in $ x$ and we get:

$ rate= \frac{50 \tan (20) \; ft}{2 \; sec}$

As always, we check our units to make sure the answer makes sense. Our units are in ft/s and we are looking for a rate, so yes, it checks out.

Hopefully this explanation was clear

Part (b) is an extension of this, except you're now solving for a different variable. Give it a shot using what you now know.[/hide]


probability
floor function
number theory
arithmetic sequence
AMC

AMC is approaching fast, and I think I'm going to spend rest of my time on my own (sorry, folks!). But here are last 8 problems of my favorite topic... Number Theory!

1. (AMC 10A 2003 #20) A base-10 three digit number $ n$ is selected at random. Which of the following is closest to the probability that the base-9 representation and the base-11 representation of $ n$ are both three-digit number?
A) 0.3
B) 0.4
C) 0.5
D) 0.6
E) 0.7

2. (AMC 12A 2003 #18) Let $ n$ be a 5-digit number, and let $ q$ and $ r$ be the quotient and remainder, respectively, when $ n$ is divided by 100. For how many values of $ n$ is $ q\plus{}r$ divisible by 11?
A) 8180
B) 8181
C) 8182
D) 9000
E) 9090

3. (AMC 12A 2003 #23) How many perfect squares are divisors of the product $ 1! \cdot 2! \cdot 3! \cdots 9!$?
A) 504
B) 672
C) 864
D) 936
E) 1008

4. (AMC 12A 2004 #25) For each integer $ n \geq 4,$ let $ a_n$ denote the base-n number $ 0.\overline{133}_n$. The product $ a_4a_5\cdots a_{99}$ can be expressed as $ \frac{m}{n!}$, where $ m$ and $ n$ are positive integers and $ n$ is as small as possible. What is the value of $ m$?
A) 98
B) 101
C) 132
D) 798
E) 962

5. (AMC 12A 2002 #20) Suppose that $ a$ and $ b$ are digits, not both nine and not both zero, and the repeating deciaml $ 0.\overline{ab}$ is expressed as a fraction in lowest terms.  How many different denominators are possible?
A) 3
B) 4
C) 5
D) 8
E) 9

6. (AMC 10A 2002 #22) A set of tiles numbered 1 through 100 is modified repeatedly by the following operation: remove all tiles numbered with a perfect square, and renumber the remaining tiles consecutively starting with 1. How many times must the operation be performed to reduce the number of tiles in the set to one?
A) 10
B) 11
C) 18
D) 19
E) 20

7. (AMC 12B 2007 #21) The first 2007 positive integers are each written in base 3. How many of these base-3 representations are palindromes?
A) 100
B) 101
C) 102
D) 103
E) 104

8. (AMC 12B 2007 #24) How many pairs of positive integers (a,b) are these such that gcd(a,b) = 1 and

$ \displaystyle \frac{a}{b} \plus{} \frac{14b}{9a}$

is an integer?
A) 4
B) 6
C) 9
D) 12
E) infinitely many

[hide="8"]
With a common denominator, this is $ \frac {9a^2 \plus{} 14b^2}{9ab}$.  Thus,
$ 9ab|9a^2 \plus{} 14b^2$, so $ 9a|9a^2 \plus{} 14b^2$.  Since $ 9a|9a^2$, we must have $ 9a|14b^2$.  Since $ a$ is coprime to $ b$ and $ 9$ does not divide $ 14$, we must have $ a|14$.

$ 9ab|9a^2 \plus{} 14b^2$, so $ b|9a^2 \plus{} 14b^2$.  Since $ b|14b^2$,  we must have $ b|9a^2$. Since $ b$ is coprime to $ a$, we must have $ b|9$.

$ a|14$ and $ b|9$ give us 2, 7, or 14 for a and 3 or 9 for b.  This is a total of $ 2 \cdot 3 \equal{} 6$ combos.  We can test them to make sure. ...EDIT and apparently some don't work  :(
[/hide]

8. Resolve it into $ \frac{9a^2\plus{}14b^2}{9ab}$...Notice that $ 9$ divides the top, so $ 9|b^2$, so $ 3|b$. Let $ 3b'\equal{}b$, so we simplify to get $ \frac{a^2\plus{}14b'^2}{3ab'}$. We notice that $ b'$ divides the top, and so $ b'|a^2$ but due to the coprime condition, $ b'\equal{}1$. Hence we are left with

$ \frac{a^2\plus{}14}{3a}$. So $ 3|(a^2\plus{}14)$, so $ a\equal{}1,2 (3)$. Then we note that $ a|14$ so $ a\equal{}1,2,7,14$. All of which satisfy that, so we have four possible solutions or A.

[hide="2"]$ q \plus{} r\equiv 100q \plus{} r \equal{} n\mod 11$. So we just look at the five digit numbers divisible by $ 11$, or floor (99999/11)-floor (10000/11)=9090-909=8181 or B[/hide]

[hide="6"]Say we have $ n$ tiles...then we take away floor (n^.5) tiles...

so we have a recurrence, a_0=100, a_{n+1}=a_n-floor ( a_n^.5)

Applying this, we get that a_18=1 so it is C[/hide]

[hide="7"]2007 in base 3 is 2202100

the only palindromes larger than this with 7 digits are 221x122 and 222x222 or 6
then we could all the palindromes with 7 or less digits...the first digit has two choices....it is $ 2*27\plus{}2*9\plus{}2*9\plus{}2*3\plus{}2*3\plus{}2\plus{}2\equal{}106$...subtracting the 6 extra gives $ 100$ or $ A$.[/hide]

[hide="4"]
For every number q of this form, $ q_r \equal{} \displaystyle\sum_{k \equal{} 1}^\infty \frac {1}{r^{ \minus{} (3k \minus{} 2)}} \plus{} \frac {3}{r^{ \minus{} (3k \minus{} 1)}} \frac {3}{r^{ \minus{} (3k)}}$, where r is the base. Splitting and summing, $ q_r \equal{} (\frac {1}{r} \plus{} \frac {3}{r^2} \plus{} \frac {3}{r^3})(\frac {1}{1 \minus{} \frac {1}{r^3}})$. This reduces to $ q_r \equal{} (\frac {r^2 \plus{} 3r \plus{} 3}{r^3})(\frac {r^3}{r^3 \minus{} 1}) \equal{} \frac {r^2 \plus{} 3r \plus{} 3}{r^3 \minus{} 1}$. Now, $ r^2 \plus{} 3r \plus{} 3$ looks suspiciously like the start of $ (r \plus{} 1)^3 \equal{} r^3 \plus{} 3r^2 \plus{} 3r \plus{} 1$, so we use something similar to SFFT. $ q_r \equal{} \frac {r(r^2 \plus{} 3r \plus{} 3) \plus{} 1 \minus{} 1}{r(r^3 \minus{} 1)} \equal{} \frac {r^3 \plus{} 3r^2 \plus{} 3r \plus{} 1 \minus{} 1}{r(r^3 \minus{} 1)} \equal{} \frac {(r \plus{} 1)^3 \minus{} 1}{r(r^3 \minus{} 1)}$. Now, we may multiply these terms from $ r \equal{} 4$ to $ r \equal{} 99$.

$ \frac {((4 \plus{} 1)^3 \minus{} 1)((5 \plus{} 1)^3 \minus{} 1)\cdots((99 \plus{} 1)^3 \minus{} 1)}{4 \cdot 5 \cdot 6 \cdots 99 \cdot (4^3 \minus{} 1)(5^3 \minus{} 1)\cdots(99^3 \minus{} 1)}$
Cancel the telescoping parts:
$ \frac {100^3 \minus{} 1}{\frac {99!}{3!} \cdot (4^3 \minus{} 1)}$
This equals $ \frac {6\cdot999999}{99!\cdot63}$, which in turn equals (now this is where no calculators really sucks) $ \frac {3\cdot6\cdot13\cdot21\cdot33\cdot37}{99!\cdot63}$.
Cancel the 21, the 33, and the 3, and we have $ \frac {2\cdot13\cdot37}{99!}$. m=962, E.
[/hide]

[quote="McDutchy"][hide="1"]
Simple. Find outer bounds.
$ 888_9$ is the largest the number could be, corresponding to $ 728_{10}$.
$ 111_{11}$ is the smallest the number could be, corresponding to $ 133_{10}$.
$ 728 \minus{} 133 \equal{} 595$, and $ \frac {595}{1000} \approx .6$. D.
[/hide]

[hide="2"]
A little more difficult.
First such $ n$ is $ 10010$. Without changing $ q$, we may get up to $ 9$ different values that are acceptable. Change $ q$by $ 1$, and our lowest possible $ n$ is now $ 10109$, and similar conditions to our previous value of $ n$ result. Therefore, in every 100 5 digit numbers, there are 9 possible values that satisfy the given conditions. However, the case where q is of the form $ 11k$ breaks this pattern. Since $ r \equal{} 0,11,\cdots,88,99$ are allowable, they have 10 values that work. Simplest way to account for this is to add in the number of possible $ q$ that are of the form $ 11k$.

$ 9\frac {10^6 \minus{} 10^5}{100} \plus{} \lfloor\frac {1000 \minus{} 100}{11}\rfloor \equal{} 8181$, so B is correct.
[/hide]

[hide="3"]
The given product reduces to $ 2^{30}\cdot3^{13}\cdot5^5\cdot7^3$. Since an odd power of a number contains the same number of perfect-square divisors as an even power, we may "round down" the odd powers to the next lowest even, producing $ 2^{30}\cdot3^{12}\cdot5^4\cdot7^2$. Now, square root this and apply the tau function.

$ \tau(\sqrt {2^{30}\cdot3^{12}\cdot5^4\cdot7^2}) \equal{} \tau(2^{15}\cdot3^6\cdot5^2\cdot7) \equal{} \Pi_{p_k|n} (a_k \plus{} 1)$.
This evaluates to $ (15 \plus{} 1)(6 \plus{} 1)(2 \plus{} 1)(1 \plus{} 1)$, which is equal to 672, B.
[/hide]

[hide="5"]
Every number of this form is based off of multiplying $ \frac {1}{99} \equal{} .\overline{01}$ by some number. For a denominator to be different than 99, it must share a factor with 99. This factor could be either 3,9,11, or 33. Thus there are 5 different possible denominators.
[/hide][/quote]

i disagree with your answer for 1. to begin with, your denominator should be 900 not 1000. there are 100-999=900 three digit numbers. second of all, 100_11 is the smallest number. therefore i got the answer as E

[quote="McDutchy"][hide="4"]
For every number q of this form, $ q_r \equal{} \displaystyle\sum_{k \equal{} 1}^\infty \frac {1}{r^{ \minus{} (3k \minus{} 2)}} \plus{} \frac {3}{r^{ \minus{} (3k \minus{} 1)}} \frac {3}{r^{ \minus{} (3k)}}$, where r is the base. Splitting and summing, $ q_r \equal{} (\frac {1}{r} \plus{} \frac {3}{r^2} \plus{} \frac {3}{r^3})(\frac {1}{1 \minus{} \frac {1}{r^3}})$. This reduces to $ q_r \equal{} (\frac {r^2 \plus{} 3r \plus{} 3}{r^3})(\frac {r^3}{r^3 \minus{} 1}) \equal{} \frac {r^2 \plus{} 3r \plus{} 3}{r^3 \minus{} 1}$. Now, $ r^2 \plus{} 3r \plus{} 3$ looks suspiciously like the start of $ (r \plus{} 1)^3 \equal{} r^3 \plus{} 3r^2 \plus{} 3r \plus{} 1$, so we use something similar to SFFT. $ q_r \equal{} \frac {r(r^2 \plus{} 3r \plus{} 3) \plus{} 1 \minus{} 1}{r(r^3 \minus{} 1)} \equal{} \frac {r^3 \plus{} 3r^2 \plus{} 3r \plus{} 1 \minus{} 1}{r(r^3 \minus{} 1)} \equal{} \frac {(r \plus{} 1)^3 \minus{} 1}{r(r^3 \minus{} 1)}$. Now, we may multiply these terms from $ r \equal{} 4$ to $ r \equal{} 99$.

$ \frac {((4 \plus{} 1)^3 \minus{} 1)((5 \plus{} 1)^3 \minus{} 1)\cdots((99 \plus{} 1)^3 \minus{} 1)}{4 \cdot 5 \cdot 6 \cdots 99 \cdot (4^3 \minus{} 1)(5^3 \minus{} 1)\cdots(99^3 \minus{} 1)}$
[b]Cancel the telescoping parts[/b]:
$ \frac {100^3 \minus{} 1}{\frac {99!}{3!} \cdot (4^3 \minus{} 1)}$
This equals $ \frac {6\cdot999999}{99!\cdot63}$, which in turn equals (now this is where no calculators really sucks) $ \frac {3\cdot6\cdot13\cdot21\cdot33\cdot37}{99!\cdot63}$.
Cancel the 21, the 33, and the 3, and we have $ \frac {2\cdot13\cdot37}{99!}$. m=962, E.
[/hide][/quote]

iv' seen this solution before. can you explain to me what part of the second to last expression telescopes?. that's the only part of your solution i don't understand. you say "cancel the telescoping parts: ...."

Top is just (5^3-1)(6^3-1)... (100^3-1) while bottom is (4^3-1)(5^3-1)...(100^3-1)

Do you see now? All terms in form $ n^3\minus{}1$ cancel out except for $ n \equal{} 100$ on the top and $ n \equal{} 4$ on the bottom.

Well crap. You're right, I messed that up.
[hide="1 should be this"]
$ 728_{10}$ still the upper limit.
$ 100_{11}$ the new lower limit, equivalent to $ 121_{10}$.
$ 728\minus{}121\equal{}607$, $ \frac{607}{900} \equiv .666$ New answer is E.
[/hide]

For #4, terms of the type $ (n^3\minus{}1)$ appear in both the numerator and denominator. Since the values of n belong to an arithmetic sequence, some terms will show up in both the numerator and denominator and thus may be canceled. They're called telescoping because they can be expanded out, like a telescope. [url=http://en.wikipedia.org/wiki/Telescoping_sum]Here's an explanation[/url]; although it may use addition instead of multiplication, it is still valid.


Let an isosceles triangle $ABC$ with $AB=AC$, a point $D$ on side $AC$ and a point $E$ on side $AB$ ,such that $BC=CD=DE=EA$.Find $\angle A$

[u] Babis[/u]

 [i]Can you send also a source for this problem , if possible ?[/i]

See the attached diagram.

Let $b=AB=AC, x=BC=CD=DE=EA$. Then $BE=DA=b-x$. Construct point $M$ inside $\triangle ABC$ such that $\triangle EMB\cong\triangle DEA$. If $\alpha=\angle BAC$, then $\angle MED=\pi-\angle AED-\angle BEM=\pi-(\pi-2\alpha)-\alpha=\alpha$. Since $EM=ED=x$, this means that $\angle EDM={\pi-\alpha\over 2}$. Also, $\triangle ADE$ is isosceles, giving $\angle ADE=\alpha$, hence $\angle CDM=\pi-\angle EDM-\angle ADE=\pi-{\pi-\alpha\over 2}-\alpha={\pi-\alpha\over 2}=\angle EDM$, therefore $\triangle EDM\cong\triangle CDM\implies MC=ME=x$. Hence $\triangle BMC$ is equilateral, which means that the base angle of $\triangle ABC$ is ${\pi\over 3}+\alpha$, giving $\alpha+2\left({\pi\over 3}+\alpha\right)=\pi\iff\alpha={\pi\over 9}=20^\circ$

Small simplification: After constructing point $M$, we have $\angle MED=EDA=\alpha$, hence $ME\#DC$, giving $MC\#DE$, so we get $MC=x$ directly.

Extend line $CE$ to $X$ where $AX$ is perpendicular to $CX$ Now the $\triangle ACX$  is half of $\triangle ABC$ [hide="because"]($\angle ECD = \angle DEC$ and their sum is $\angle EDA = \angle A$)[/hide] So  the $\triangle AXE$ is $90^{o}-60^{o}-30^{o}$ triangle  [hide="because"]($AX$  is half  of $BC=AE$)[/hide]
Once you know $\angle XAE$ is $60^{o}$ you get $\angle A = 20^{o}$ [hide="because"](Look at right angle triangle $ACX$[/hide]

Another solution, I think simplest yet. See the attached diagram.

$\triangle ABF\cong\triangle ABC, BG=BC$. By the construction and initial conditions, $GE=BC$. Now $BG\#CD\implies GD=BC$, hence $\triangle GED$ is equilateral, giving $\angle GED=60^\circ$. On the other hand $\angle BED=2\angle BAC$ (external angle in isosceles $\triangle ADE$) and $\angle BEG=\angle EBG=\angle BAC$. Thus $60^\circ=\angle GED=\angle BED+\angle BEG=3\angle BAC\iff \angle BAC=20^\circ$

Nice one!
 Another easy way is to choose a point $F$ on $AB$ such that $ED=DF$. Easy to see that $\angle BFC = \angle FBC \implies \triangle FDC$  is equilateral. Rest is easy.

Of course, direct trigonometric substitution  $\frac{a}{2 \sin (A/2)}= 2a \cos A+a$
will yield ($\cos 3A = 1/2$) too.


Prove that every nonempty subset of $ N$ has a least element.  (This is expressed by saying that $ N$ is well-ordered.)

let $ Y \subset N$ be a suppose-not candidate

then $ \forall y \in Y$, we know $ \exists y' \in Y$ s.t. $ y'<y$

since Y is non empty, we know $ \exists m_0 \in Y$ a natural number.

then we also know $ \exists m_1 \in Y, m_1 < m_0$

likewise $ \exists m_{k\plus{}1} \in Y, m_{k\plus{}1}<m_k< ... < m_0$ for any k

thus we have a monotone decreasing sequence of integers bounded below by 0.

but notice that each member of the sequence is distinct, yet infinitely many of them belong to the set $ R\equal{}[0,m_0] \cap N$, which has finite size, a clear contradiction

What definition of $ \mathbb{N}$ are you using?  In some definitions, this is given as an axiom and can be used to deduce the other properties of $ \mathbb{N}$.  (kenn4000, your last step actually requires the well-ordering principle; you need to prove that there are no natural numbers between $ 0$ and $ 1$, which requires well-ordering (again, depending on which definition you're using).)


calculus
integration
limit
calculus computations

This was confusing me so any help would be appreciated:

Use a suitable test to determine whether the following series converges or diverges:

sigma starting at j=2 and going to infinity of:
1/(j^4 - j)

I guess where my trouble lies is that I'm having problems integrating this expression.

So... don't integrate it. Compare to something simpler.

Don't double-post!  There is no reason whatsoever to post this separately from your other, nearly identical thread.

To study the nature of the series $\sum_{n=2}^{\infty}\frac{1}{n^{4}-n}$ its perhaps convenient to use the limit comparision test, where we compare the nature of a given series with a series whose nature we already know. For example, by using the Integral Test, one can show that the Dirichlet series $\sum_{n=1}^{\infty}\frac{1}{n^{p}}$ converge for p>1 and diverges for $p \le 1$. So, lets compare your series with the convergent series $\sum_{n=1}^{\infty}\frac{1}{n^{4}}$ by using a limit:

$\lim_{n\to\infty}\frac{\frac{1}{n^{4}-n}}{\frac{1}{n^{4}}}= \lim_{n\to\infty}\frac{n^{4}}{n^{4}-n}= 1$.

So, according to the limit comparision test, as this limit has a real value differente from zero, then the two series that we have compared have the same nature. As the one we used converges, so also your series converges.


Find all integers $x$ such that $x^2 + 3x + 24$ is a perfect square.

Is this posible,i'm not sure about it.....a little sleepy :D

[hide="hint"]look in mod 4...what can you say about a perfect square, once you have the equivalent for x^2, what can you say about x?[/hide]

um...shyong...isn't $b^2-4ac=0$ for a perfect square? :?


A point is chosen at random on the number line between 0 and 1, and the point is colored green. Then, another point is chosen at random on the number line between 0 and 1, and this point is colored purple. What is the probability that the number of the purple point is greater than the number of the green point, but less than twice the number of the green point?

Maybe there is a mistake, but I proved that you [i]can't[/i] solve this problem.

Uh... If you post this proof I would be very happy.

Turn the number line into the first quadrant of a Cartesian plane with both axes length of 1. Use the $x$ axis as all the possible values of  the green point and the $y$ axis for the purple point. The graph/shade all values such that the purple point is between the $x$ value and the $2x$ value;

The shaded area will make two triangles, one right, and one obtuse. Calculate the area, you should get .25. Or you could multiply the size of the triangles and the whole square in proportion to find the area. $.25=\boxed{\dfrac{1}{4}}$.

Hope this helps! I've tried to explain the best I could. :D

can you really just plot all points? is it possible to know the boundaries of the shaded area?


BTW, thanks for the help. You guys have really helped me to better understand this stuff.

The work done by a constant force of magnitude $\vec{F}$ on an object that moves a distance S along a straight line at angle $\theta$ with the direction of the force is $W=%Error. "magnitude" is a bad command.
\vec{F}S cos\theta$. The force $\vec{F}$ is measured to by 10N with a possible error of 0.1N; the distance S is measured to be 100m with a possible error of 0.01m; and the angle $\theta$ is measured to be $30^{\circ}$ with a possible error of $1^{\circ}$.
Use differentials to estimate the possible resulting error in the calculate work.

Okay so I setup the Equations:
$\Delta w=w_{F}(10,100,30)\Delta F+w_{s}(10,100,30)\Delta s+w_{\theta}(10,100,30)\Delta \theta+\epsilon_{F}\Delta F+\epsilon_{s}\Delta s+\epsilon_{\theta}\Delta\theta$
$w_{F}=Scos\theta$
$w_{s}=\left\|\vec{F}\right\|cos\theta$
$w_{\theta}=-\left\|\vec{F}\right\|sin\theta$
$\epsilon_{F}=0.1$  $\epsilon_{s}=0.01$  $\epsilon_{\theta}=1$

$\Delta w(10,100,30)=50\sqrt{3}\Delta F+5\sqrt{3}\Delta s-500\Delta \theta+0.1\Delta F+0.01\Delta s+\Delta\theta$

And this is where I got stuck. I think the error is related to the $\Delta$'s but am not sure.

Aren't $\Delta F=.1$, $\Delta s=.01$ and $\Delta \theta=1^\circ$? Just substitute those in and multiply out.

I thought calculus was done in radians. Is there an issue regarding using degrees rather than radians? Are correction factors or something needed?

Calculus can be done in radians or degrees. As long as the person doing the computations realizes that.

I already put the Errors in.

$\Delta$ is the change not the error.


The weights of three individual objects are to be estimated. Two different designs to obtain these estimates are being considered:

D1:
The three objects are weighed individually, seven times each.

D2:
i. Each object is weighed separately once.
ii. Then the objects are weighed two at a time in the three possible, different combinations.
iii. Finally, the three objects are weighed all together, once.
iv. This factorial design (steps i, ii, and iii) is repeated three times.

The two designs both use all of the n = 21 measurements for which funds are available.

Which design do you EXPECT to yield the more precise estimates of the individual weights of the three objects? Why? Show the details of your work.

What assumptions does your answer require?

Note: To answer this question you do no need to know, or use, the "y" values; nor do you need to estimate the residual mean squares.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Please help me solve this problem. If you know any websites that would be helpful, please tell me.

Let $w_{1},w_{2},w_{3}$ be the true weights of the object, and let $\epsilon$ be the measurement error (normally distributed r.v. with mean $0$ and variance $\sigma^{2}$).

D1: We sample $w_{i}+\epsilon$ 7 times, and take the average of all 7 measurement. The average has mean $w_{i}$ and variance $\sigma^{2}/7$.

D2: We sample $w_{i}+\epsilon$, $w_{i}+w_{j}+\epsilon$ ($i<j$), and $w_{1}+w_{2}+w_{3}+\epsilon$, each 3 times. But how are we going to combine these results to produce our estimates for $w_{i}$? This is an important part of the design, and it is missing from the statement. Let's try to estimate $w_{1}$ by adding $w_{1}+\epsilon$, $w_{1}+w_{2}+\epsilon$, $w_{1}+w_{3}+\epsilon$, and $w_{1}+w_{2}+w_{3}+\epsilon$ (3 tries each), then subtracting the sum of 3 samples of $w_{2}+w_{3}+\epsilon$ multiplied by two, and finally dividing by $12$. This random variable has mean $w_{1}$ and variance $(12\sigma^{2}+12\sigma^{2})/12^{2}=\sigma^{2}/6$. This is worse then D1. But maybe there is a better way to combine the measurement results?  :maybe:

Thank you for answering! This problem is indeed confusing...  :huh:
Mlok, can you please explain how did you get the variance in both designs?
Just to make sure -- you talked about mean w_i in Design 1 and mean w-1 in Design 2. Did you mean by the mean w_i the average of all samples of the weight w_i?

In D2 I took $w_{1}$ as an example. Same could be done for 2nd and 3rd weights.

The [url=http://en.wikipedia.org/wiki/Variance]variance[/url]of the sum of independent r.variables is the sum of their variances. Also, if you multiply a r.v. by a constant $k$, the variance get multiplied by $k^{2}$. This is all I used.

Now I see. Does your answer require any assumptions on these random variables? If yes, which ones?

mlok:
After carefully looking at the samples I noticed that it is possible to estimate w_1 by adding w_1 + e, w_1 + w_2 + e, w_1 + w_3 + e, w_1 + w_2 + w_3 +e (3 tries each), then subtracting the sum of 3 samples of w_2 + w_3 + e, w_2 + e, and w_3 + e, and then finally dividing by 12. The variance becomes 21 σ^2 / 12^2 instead of σ^2 / 6. This is suspicious (even though the variance is still greater than in the first design). It turns out that it is possible to estimate w_1 in different ways? What do you think?


Some boys and girls are having a car wash to raise money for a class
trip to China.  Initially 40\% of the group are girls.  Shortly thereafter two
girls leave and two  boys arrive, and then 30\% of the group are girls.
How many girls were initially in the group?

2 girls leave and the difference in percent is 10%. this means that 2 is 10% of the total number of people so
2*10=20 people and originally there were 8 girls


[quote="da ban man"][quote="cincodemayo5590"][hide="1"]
$w^{2}+w+1=0 \implies w+1=-w^{2}\text{ and }w^{3}=1$

So, we want $w^{2n}+1+(w+1)^{2n}= w^{2n}+1+w^{4n}= w^{2n}+w^{n}+1 \neq 0$. It's easy to see that for integer $n$ we must have $3|n$, so we want $\boxed{n=21 \implies C}$.[/hide]

[hide="2"]
\[S=\binom{90}{0}+\binom{90}{3}+...+\binom{90}{90}= \frac{1}{3}\left( (1+1)^{90}+(1+w)^{90}+(1+w^{2})^{90}\right) \]
where $w^{2}+w+1=0$. (Why is this true? :) ) So, by DeMoivre's Theorem,
\[3S= 2^{90}+(\frac{1}{2}+\frac{i \sqrt{3}}{2})^{90}+(\frac{1}{2}-\frac{i \sqrt{3}}{2})^{90}= 2^{90}+1 \text{cis}(90 \cdot \frac{\pi}{6})+1 \text{cis}(-90\cdot \frac{\pi}{6}) \]

\[\implies S = \boxed{\frac{2^{90}-2}{3}}\]
[/hide][/quote]
For number 2, isnt it suposed to be 2^90+2/3 not -2 beause its 60 degrees not 30?[/quote]
Actually, yes. Thanks for pointing that out. I'll edit.  :)

([b]EDIT[/b]): Grrrr, AoPS isn't letting me edit my post. Ah well. Whoever reads just, just keep in mind that the final answer to #2 is [hide="here"]\[S= \boxed{ \frac{2^{90}+2}{3}}\] [/hide]


I'm trying to make a program that software-whitens wave files, but I'm failing miserably.

I tested the entropy of a file containing random bits from HotBits, whitened the file, and the entropy was actually [i]lower[/i] than the first file!

I'm sure that it's some really obvious bug that I've overlooked, but I can't figure out what.

[code]
ifstream reader("random.wav", ios::binary); // the data is extracted from a wave file...
ofstream writer("out.txt", ios::binary); // ...and output to a text file

char in_char = 0;
char out_char = 0;

int collected_bits;

int main(){

    while(reader >> in_char){ // read one byte

        for(int a = 0; a < 4; ++a){ // take into account pairs of bits

            switch(in_char % 4){
                case 0:
                case 3:
                    // if 2 bits are the same, screw them
                    break;
                case 1:
                    // if they are different, take the first bit and discard the second
                    // in the case of 01, take the 0
                    out_char = out_char * 2; ++collected_bits;
                    // since I can't write individual bits to a file,
                    // I need to have an "out_char" queue to write 8 bits at a time.
                    if (collected_bits % 8 == 0){
                        writer << out_char;
                        out_char = 0;
                    }
                    break;
                case 2:
                    // in the case of 10, take the 1.
                    out_char = out_char * 2 + 1; ++collected_bits;
                    if (collected_bits % 8 == 0){
                        writer << out_char;
                        out_char = 0;
                    }
                    break;
            }

            // move onto the second set of bits
            in_char /= 4;
        }

        in_char = 0;

    }

    cout << "Total of " << collected_bits << " bits collected from random.wav.";
    cin.get();
    return 0;

}
[/code]

Help is greatly appreciated!

[quote="bus"]Well... the entropy [i]should[/i] be lower, shouldn't it?[/quote]

No, the point of Von Neumann whitening is to increase entropy in random but biased data.

[quote="paladin8"]You should be careful because the "char" type is signed, i.e. it ranges from -128 to 127. So when you read in binary data from the file, you'll be getting some negative values; then when you mod by 4, you'll probably see negative values as well, which will be incorrectly ignored in the switch statement.[/quote]

Damn, I knew it was a really simple bug... (The word filter filters out "d---m-n"? I don't understand, there are legitimate uses of that word...)

Now it works properly, thank you.

OK guys, let's not swear on a public forum.


geometry
geometric transformation
rotation

[quote]There is a notice printed on a sheet of paper that has to be posted on the wall. If every corner must be tacked down and there are four colors of tacks to choose from, how many ways can the notice be tacked?

what if there were 5 colors to choose from?[/quote]

[hide]$4^{4}=\boxed{256}$[/hide]

[hide]$5^{4}=\boxed{625}$.  the general formula is $n^{4}$[/hide]

[hide]simply $4^{4}=256$[/hide]

[size=75][color=darkred]Please remember to put hide tags when posting answers. Thanks.
-nebula42[/color][/size]

[hide]It is just 4^4=256.

Is this problem considering rotations and reflections.[/hide]

[quote="espark52"][quote="Ktradsb1"]what if there were 5 colors to choose from?[/quote]

that would make it $5^{4}=625$[/quote]
as nebula already said, "remember to put hide tags".


1)On a graph, a lattice point is an ordered pair (x,y) with integers x and y. Exactly 15 lattice points lie strictly in the interior of the triangular region with vertices (0,0), (N,0) and (N,N) where N>0. What is the value of N?
I couldn't get anywhere....

2)The numbers 3,5, and 7 are written on a blackboard.Select any two,x and y, erase them and write the new number x+y+xy.Repeat this process again until just one number remains. How many distinct numbers are possible for this final number? The answer isn't even in the answer key, so I didn't have any idea how to do this....

3)The length of a diagonal of a square is root of 2+root of 3 units. What is the area of the square?Express your answer in simplest form as a/b+root c, where a/b is a common fraction and c has no perfect square factors other than 1.

[hide="1)"]
Note that the number of interior lattice points in an $ n\times n$ triangle is $ \frac{(n-1)(n-2)}{2}.$ Set this equal to $ 15$ and solve for $ n.$ \begin{align*}\frac{(n-1)(n-2)}{2}&=15\\(n-1)(n-2)&=30\\n&=7,-4.\end{align*}Obviously, $ n$ must be positive so the answer is $ n=\boxed{7}.$

You can check it and see that there are indeed $ 15$ interior lattice points.[/hide]

[hide="2)"]
There are so few that you can brute force it.
\[ \{3\cdot5+3+5,7\}=\{23,7\}\Rightarrow\{23\cdot7+23+7\}=191\newline\{3,5\cdot7+5+7\}=\{3,47\}\Rightarrow\{3\cdot47+3+47\}=191\newline\{5,3\cdot7+3+7\}=\{5,31\}\Rightarrow\{5\cdot31+5+31\}=191.\] They're all the same number! Therefore, there's only $ \boxed{1}$ distinct outcome at the end.

[hide="In general..."]
Rewrite $ xy+x+y$ as $ (x+1)(y+1)-1.$ Instead of $ \{3,5,7\},$ we let the numbers be $ \{a-2,a,a+2\}.$ Now we can let $ x$ and $ y$ equal anything and continue, and it would be the same outcome.[/hide][/hide]

[hide="3)"]
The area of a square with diagonal $ d$ is $ \frac{d^2}{2}.$
[hide="somewhat unnecessary proof"]
The diagonal is $ d$ which means the side length is $ \frac{d}{\sqrt{2}}.$ The area is thus $ \frac{d^2}{2}.$ (This is from a 45-45-90 triangle).[/hide]
Just plug in the value for $ d,$ which is $ d=\sqrt{2}+\sqrt{3}.$ \[ \frac{d^2}{2}=\frac{(\sqrt{2}+\sqrt{3})^2}{2}=\frac{2+3+2\sqrt{6}}{2}=\boxed{\frac{5}{2}+\sqrt{6}}.\][/hide]

[quote="RoFlLoLcOpT"]

Rewrite $ xy \plus{} x \plus{} y$ as $ (x \plus{} 1)(y \plus{} 1) \minus{} 1.$
[/quote]

Just a note - you can learn more about this by watching [url=http://www.artofproblemsolving.com/Movies/simon1.php]this[/url].

[quote="RoFlLoLcOpT"]Where'd you find that? I couldn't find it in the resources section..[/quote]

I know where the resource section is...I just couldn't find it [b]in[/b] the resource section.

Go to the AoPSWiki article on SFFT, and also see the thread titled "Videos" in the Questions, Suggestions, and Announcements forum.

They still haven't come up with the olympiad video :ninja: .

[quote="SuperNerd123"]You realize on the sidebar there is a button called
"RESOURCES"[/quote]
Not everybody has that. Some people use the MathLinks board style.  :wink:

The SFFT videos were tests that were made a couple years ago.

[quote="ThinkFlow"]I will now show you the most awesome use of Google in the world.  :ninja:

[url=http://www.google.com/search?hl=en&as_q=&as_epq=&as_oq=&as_eq=&num=10&lr=&as_filetype=&ft=i&as_sitesearch=www.artofproblemsolving.com/Movies&as_qdr=all&as_rights=&as_occt=any&cr=&as_nlo=&as_nhi=&safe=images]Click this link.[/url][/quote]

[quote="RoFlLoLcOpT"][hide="1)"]
Note that the number of interior lattice points in an $ n\times n$ triangle is $ \frac {(n - 1)(n - 2)}{2}.$ Set this equal to $ 15$ and solve for $ n.$
\begin{align*}\frac {(n - 1)(n - 2)}{2} & = 15 \\
(n - 1)(n - 2) & = 30 \\
n & = 7, - 4.\end{align*}
Obviously, $ n$ must be positive so the answer is $ n = \boxed{7}.$

You can check it and see that there are indeed $ 15$ interior lattice points.[/hide]

[/quote]

just wondering, but how did you get that formula for the number of interior lattice points?

Visualize it. Starting from the bottom, there are $ n\plus{}1$ lattice points not on the bottom of the triangle. However, 2 of these are on the triangle and 1 is above the triangle. So the bottom is $ n\minus{}2.$ Then there are $ n\minus{}1,$ then $ n,$ and so on. The number of dots is the $ (n\minus{}2)th$ triangular number, which is $ \frac{(n\minus{}2)(n\minus{}1)}{2}.$
Of course, you could also test out smaller grids and find the formula.

Example...The red dots are the rejected ones and the blue ones work. Shown are the first two rows.
[asy]size(100);
import graph;
draw((0,0)--(6,0)--(6,6)--cycle);
dot((0,1),red);
dot((1,1),red);
dot((2,1),blue);
dot((3,1),blue);
dot((4,1),blue);
dot((5,1),blue);
dot((6,1),red);
dot((0,2),red);
dot((1,2),red);
dot((2,2),red);
dot((3,2),blue);
dot((4,2),blue);
dot((5,2),blue);
dot((6,2),red);[/asy]

I think he meant where you read about it.... Not how it was made...

I don't think there is a formula...you have to come up with it. You don't see that kind of problem every day so I would naturally assume there isn't a place to read it from.


如图，△ABC中，AB＝BC＝10，点M、N在BC上，使得MN＝AM＝4，∠MAC＝∠BAN，则△ABC的面积是＿＿＿＿。

答案好象对。先证角BAM=60度，再添高就做出来了。

[quote="Starfall"]这两道都是2003年上海市数学竞赛题,本人初二时参加了那次比赛,拿了个二等,此题我当时是用两次余泫定理做,答案好象是50根号57再除以19,我帮你查查[/quote]
能否传授一下经验？


pigeonhole principle
real analysis
real analysis theorems

I am not sure to go about proving using the pigeonhole rule that the set S of all real numbers of the form $a + bu$, where $a$ and $b$ are integers and $u$ is irational is dense.


$ (a,b,c,d)>0$

prove that:

$ \sum_{cyc}\frac{a}{b\plus{}2c\plus{}d}\ge 1$

By Cauchy-Schwartz,
$ \sum_{cyc} \frac{a}{b\plus{}2c\plus{}d} \sum_{cyc} a(b\plus{}2c\plus{}d) \geq (\sum_{cyc} a)^2$.
We will show that
$ (\sum_{cyc} a)^2 \geq \sum_{cyc} a(b\plus{}2c\plus{}d)$,
from which the inequality will follow.

However, this can be simply written out as
$ a^2 \plus{} b^2 \plus{} c^2 \plus{} d^2 \plus{} 2(ab \plus{} bc \plus{} cd \plus{} da \plus{} ac \plus{} bd) \geq 2(ab \plus{} bc \plus{} cd \plus{} da) \plus{} 4(ac \plus{} bd)$.
As $ a^2 \plus{} c^2 \geq 2ac$ and $ b^2 \plus{} d^2 \geq 2bd$, and the other terms cancel, we are done.


summer program
MathPath
geometry
ratio
analytic geometry
LaTeX
linear algebra

Source: Last year's MathPath qualifying quiz

In the figure, $FB=2AF$, $DC=2BD$, and $EA=2CE$ (that is, the points trisect the sides). Find the area of the shaded region.

I hope this is in the right forum.

Edit: Oops, I forgot to mention that the area of the big triangle is 1. :blush:

Please show your work.

[quote="tim1234133"]by way of trying to do it in my head (and with areals), i get [hide]1/7 (edited from 55/343: where did that come from?[/hide]
(are we assumng the area of the whole triangle is 1?[/quote]

Would you mind telling us how you came to that conclusion? :)

ok, ive gone over it now, hope it works...

[ABE]=2[BEC]
[ADC]=2[ADB]
[CBF]=2[CAF]
[BEC]=[ADB]=[CAF]
so the area of the triangle is equal to the sum of the areas of the three smaller triangles, in the corners.

B has areal coordinates (0,1,0)
D has areal coordinates (0,2/3,1/3)
AD meets BE at (1/7,4/7,2/7)

so, I can't do the Latex, but the area of the triangle marked by the points i mentioned is
the determinant of the matrix formed with (0,1,0),(0,2/3,1/3),(1/7,4/7,2/7) as the columns
which I think is 1/21.
By symmetry the same is true of the other small triangles, so the sum of the areas is 1/21+1/21+1/21=1/7

doubt thats clear, I'll try edit it when I have more time

[quote="mathnerd314"][quote="tim1234133"]by way of trying to do it in my head (and with areals), i get [hide]1/7 (edited from 55/343: where did that come from?[/hide]
(are we assumng the area of the whole triangle is 1?[/quote]
What are areals? I tried Wikipedia but got nothing useful.[/quote]
Typo for areas??

No, Tim mentioned "areal coordinates"...

[url=http://mathworld.wolfram.com/ArealCoordinates.html]Areal coordinates- from MathWorld[/url]

This is interesting but probably beyond GS level, so don't worry about it too much.

There are at least two other solutions (only involved with pure geometry), so try to find it ;)

(I already gave a hint for one of the geometric solutions, but I'll give more if necessary.)

I'm dead-ending again on this problem. :(

you can also use mass points for this problem

Can someone show a mass points solution? :)

[quote]$[BEC]=[ADB]=[CAF]$[/quote]

How is that concluded?

We are given DC=2BD,and we can use the formula for the area of a triangle

Area=1/2*base*height

Since the heights of triangles ADB and ADC are the same, and the base of ADC (DC)
 is twice the base of ADB (BD) the area of ADC is twice the area of ADB.

This means that ADC has area 2/3 and ADB area 1/3 (since the sum of their areas is the area of ABC, which is 1)
Similarly, ABE has area 2/3 and BEC has area 1/3.
Also, CFB has area 2/3 and CAF area 1/3.

That's about as far as I got on this problem.

I'll post one of my solutions using the hint I posted before:
[quote="frt"][hide="Hint for a different approach"]Draw a line from $D$ that is parallel to $CF$, and let $P$ be the intersecting point with $AB$.
Find $AF: FP$, which is also equal to another ratio... ;) [/hide][/quote]
[hide="Solution"]
Draw a line from $D$ that is parallel to $CF$, and let $P$ be the intersection with $AB$.

Since $PD\parallel FC$, $FP: PB=CD: DB=2: 1$.
We already know that $AF: FB=1: 2$, so combing these two ratio gives $AF: FP: PB=3: 4: 2$.

Then, let $G$ be the intersection between $AD$ and $FC$.
$FG\parallel PD$, so $AG: GD=AF: FP=3: 4$.

Therefore, $\triangle AGC=\triangle ADC\times\frac{AG}{AD} =\frac{2}{3}\cdot \frac{3}{7}=\frac{2}{7}$

Hence the area of the shaded region is $1-3\cdot \frac{2}{7}=\frac{1}{7}$
[/hide]


Why is the Zeroth Law of Thermodynamics not as intuitive as it seems?  It states that if A and B are in thermal equilibrium with C then A and B are in thermal equilibrium with each other.  My book just says that although it may seem obvious it isn't and that experiments show that it is true.

(Please keep the explanation on a not too high tech level)

Is the zeroth law the one that says if you throw two metal bars into a lake and wait until they are in equilibrium with the lake, they will be in equilibrium with each other?  Just making sure I understand what's being asked.  ;)

A little off topic, but love the avvy Joml88.  ;)  :lol:

Can't wait to play it this weekend...


quadratics limit function ratio logarithms conics hyperbola

On a $ 8$ x $ 8$ chessboard (or generally $ n$ x $ n$) a king is placed in one of the corners and it starts to move randomly in a possible neighbour square with an equal probability.
What is the expected value for the number of steps needed to achieve the opposite corner?

I got the same results as JBL with this simple (and most likely inefficient) Maple code.
[quote]n:=8;
P:=Matrix(1..n,1..n,symbol=p):
C:=Matrix(1..n,1..n):
Q:=Matrix(1..n,1..n):
for i from 1 to n do
for j from 1 to n do
for i1 from -1 to 1 do
for j1 from -1 to 1 do
if ((i+i1>0) and (i+i1<n+1) and (j+j1>0) and (j+j1<n+1)) then  Q[i,j]:=Q[i,j]+P[i+i1,j+j1];
C[i,j]:=C[i,j]+1;
end if; end do; end do; end do; end do;
Q:=Q-P:
eq:=[seq(seq(P[i,j]=Q[i,j]/(C[i,j]-1)+1,i=1..n),j=1..n)]:
eq[1]:=p[1,1]=0:
sol:=solve(eq):
eval(p[n,n],sol);
evalf(%);
[/quote]

The quadratic rate was to be expected, since we are solving a discrete version of $ \Delta u\plus{}C\equal{}0$. But what is the limit $ \lim_{n\to\infty}\frac{P(n)}{n^2}$?

So we are after the function $ F\colon \{1,\dots,n\}\times \{1,\dots,n\}\to [0,\infty)$ such that $ F(n,n) \equal{} 0$ and $ F(i,j)$ is the average of $ F$ over all neighbors of $ (i,j)$ plus $ 1$. More precisely, I'm interested in the limit of $ F(1,1)/n^2$, should it exist at all.
I first thought that $ F$ should look like $ G(i,j) \equal{} \frac {2}{3}(2n^2 \minus{} x^2 \minus{} y^2)$, which would lead to the limit of $ 4/3$. This does not agree with numerical evidence: the ratio $ F(1,1)/n^2$ is growing steadily and is over $ 7.37$ when $ n \equal{} 35$. So I plotted $ F$ for $ n \equal{} 35$ to see what's going on.
[img]http://www.math.tamu.edu/~lkovalev/files/chessking.jpg[/img]
This does not look like a paraboloid: the function has negative Hessian along the main diagonal. The boundary effects appear significant, but I don't know how to account for them.

My "educated guess" for large $ n$ would be $ \frac{16}{3\pi}n^2\log n\plus{}Cn^2\plus{}o(n^2)$ (perhaps, $ o(n^2)$ is even $ O(n)$ but I'm not betting too much on that) ;) Before telling where it comes from, I'd like to see how well it agrees with numerics (I'm clueless about the value of $ C$, so just use the best fit for $ n$ from $ 10$ to $ 35$, say, to verify this prediction).

I'm afraid $ n=35$ is not enough to distinguish between $ n^2\log n$ and $ n^2$.  :( More efficient code/software package may be needed. This is the graph of the expectation $ E_n$ divided by $ \frac{16}{3\pi}n^2\log n$:
[img]http://www.math.tamu.edu/~lkovalev/files/moves1.jpg[/img]
And this is the graph of ${ \frac{1}{n^2}(E_n-\frac{16}{3\pi}n^2\log n})$:
[img]http://www.math.tamu.edu/~lkovalev/files/moves2.jpg[/img]

The second graph suggests that I miscalculated the coefficient at $ n^2\log n$ :(. Let us see. We, indeed, are looking for a function in the $ n\times n$ square whose Laplacian equals $ -8/3$. If you look at the boundary conditions, you realize that the main part of them is $ 0$ normal derivative. Now you see immediately that this cannot be a nice smooth function $ n^2 u(x/n)$ in the limit because the corresponding Neumann boundary problem is unsolvable. This suggests that you must have a singularity at the corner. To make the boundary problem solvable, one would need to add the $ \delta$-measure to the Laplacian in the corner, which is OK because the corner value does not satisfy any equation. So, in the limit, we will have a function $ n^2 u(x/n)$ where $ u(y)$ is the unique $ 2$-periodic in each variable function whose Laplacian is $ -8/3$ throughout the plane except at the points of the lattice $ 2\mathbb Z^2$ where it is a multiple of the $ \delta$-measure. Since the total Laplacian over the period must be $ 0$, the coefficient at the $ \delta$-measure must be $ 32/3$, which corresponds to the singularity $ \frac {16}{3\pi}\log|y|$. Now it remains to plug $ |y|\approx 1/n$ to get the  formula I suggested. Since something is wrong with either my heuristics or mlok's graphs, let me ask this: for which value of $ A$ does the graph of ${ \frac{1}{n^2}(E_n-An^2\log n})$ look flat between $ 10$ and $ 35$? I still think it should be some rational number with small denominator times $ 1/\pi$ so $ \pi A$ would be interesting to see :).

Two natural candidates for $ A$ that produce flat-looking graphs of ${ \frac {1}{n^2}(E_n - An^2\log n})$ are $ \frac {19}{3\pi}$ and $ \frac {13}{2\pi}$. This is with $ A = \frac {19}{3\pi}$:
[img]http://www.math.tamu.edu/~lkovalev/files/moves193.jpg[/img]
This is with $ A = \frac {13}{2\pi}$:
[img]http://www.math.tamu.edu/~lkovalev/files/moves65.jpg[/img]
I also calculated $ E_{50}\approx 20180$ (took about an hour on my poor ol' laptop). This adds the point $ (50, 0.1855)$ to the first graph and $ (50, - 0.022)$ to the second. All things considered, I like $ \frac {19}{3\pi}$ more.

Update: using a more powerful computer, I found $ E_{75}\approx 49702.93448$. This adds the point $ (75, 0.132)$ to the first graph and $ (75, -0.097)$ to the second.

Okay, so I finally found time to rewrite this as a linear system in Matlab (code below) and pushed the upper limit to $ n=91$. Now $ A=\frac{19}{3\pi}$ does not look good anymore, increasing the likelihood that $ A=\frac{16}{3\pi}$ is indeed the right coefficient - it's just that $ n$ is still too small for this to be obvious. This is ${ \frac{1}{n^2}(E_n - An^2\log n})$ with $ A=\frac{19}{3\pi}$:
[img]http://www.math.tamu.edu/~lkovalev/files/moves91-1.jpg[/img]
And this is with $ A=\frac{16}{3\pi}$:
[img]http://www.math.tamu.edu/~lkovalev/files/moves91-2.jpg[/img]
Both graphs are shifted $ 9$ units to the left (I plotted starting with $ n=10$), but I did not bother to fix this.

Finally, the M-file that produced the data (compressed to take less space):
[quote]N=100; EM=zeros(N,1);
for n=2:N
A=zeros(n*n);
for i=1:n  for j=1:n
k=(i-1)*n+j;
if (k>1)
nb=-1;
for i1=-1:1  for j1=-1:1
if ((i+i1>0) && (i+i1<n+1) && (j+j1>0) && (j+j1<n+1))
    nb=nb+1;
end end end
for i1=-1:1  for j1=-1:1
if ((i+i1>0) && (i+i1<n+1) && (j+j1>0) && (j+j1<n+1))
    k1=(i+i1-1)*n+j+j1; A(k,k1)=-1/nb;
end end end end
A(k,k)=1;
end end
v=ones(n*n,1); v(1)=0; sol=A\v; EM(n)=sol(n*n)
end[/quote]

I thought of this a bit more and also came to the conclusion that $ \frac{16}{3\pi}n^2\log n$ is the right leading term. Moreover, I am inclined to believe that the next two terms are $ C_2n^2$ and $ \minus{}C_1n$ with positive $ C_2,C_1$, so the last mlok's graph should be just the usual $ y\equal{}\minus{}C_1/x$ hyperbola shifted up by $ C_2$. Since it is just a two parameter equation, we can try to find the best fitting parameters $ C_2$ and $ C_1$ and see if the error behaves in any decent way between 10 and 91 (I would like to say that it should be $ O(1)$ but I do not really have any hard evidence for that). If this prediction turns out to be in good agreement with numerics, we can try to prove something along these lines :)

yesterday I tried to do the computations with a simple C++ program, with a (Householder reflexion method) QR factorization to solve the linear system. It was way too slowww, so I was wondering what kind of algorithms does Matlab use to solve. The system is almost symetric (maybe positive definite), but Mlok did not specidy it to Matlab.. So what kind of algorithms are used ?

I don't know what Matlab does, but I know that speed is not the limiting factor here: my system runs out of memory around $ n \equal{} 100$ (when the matrix has size $ 10000\times 10000$). However, the matrix is sparse (which I did not tell Matlab either). So maybe I can improve this further. Or maybe some Mathematica fan will jump in and compute the values up to $ n \equal{} 1000$.  :lol:

I would be wary of making predictions based on the interval $ [10,91]$, seeing how the "best" value on $ [10,35]$ was only good on that interval.

[quote="mlok"]
I would be wary of making predictions based on the interval $ [10,91]$, seeing how the "best" value on $ [10,35]$ was only good on that interval.[/quote]
Depends on the kind of "predictions". The best value on $ [10,35]$ was the "best" for the pure $ n^2\log n\plus{}Cn^2$ law, which was just an (obviously) incorrect assumption. On the other hand, if you make a correct assumption about the formula, the constants should be possible to find from $ [10,35]$  already. The assumption I would like to make now is rather bold one but it is not too hard to verify: I believe that there exists an asymptotic series
\[ E(n)\equal{}\frac{16}{3\pi}n^2\log n\plus{}\sum_{k\equal{}2}^{\minus{}\infty}C_k n^k\]
which is an extremely strong statement because the first 3 unknown terms should already give you the answer with the error $ o(1)$. If such a series exists, the approximate values for the coefficients can be found without too much trouble. I would try to do it myself but, since you already made so many computations and know the values up to 91 with machine error precision, why not to make one more step :). In the worst case I'll be just proved to be wrong :P.

Sparse matrices in Matlab are awesome. :) It looks like [b]fedja[/b] is right concerning the hyperbolic shape. The graph of ${ \frac {1}{n}(E_n - \frac {16}{3\pi}n^2\log n})$ looks like a straight line on the scale of $ n\le 600$. I used the data for $ 100\le n\le 600$ for linear regression and got $ y = 1.692858*x - 15.389267$, but I don't see anything special about these numbers. I'm attaching the data up to 840, in increments of $ 10$.

By the way, $ E_{1000}\approx 13406916.77881$. Matlab solved this system with a million unknowns in a few minutes.

For [b]alekk[/b]: all I found in Matlab help was "The backslash operator employs different algorithms to handle different kinds of coefficient matrices".  :huh:

I am adding two more plots just to illustrate what [b]fedja[/b] wrote above. This is the graph of the expected number of moves on the $ 1000\times 1000$ board as a function of initial position.
[img]http://www.math.tamu.edu/~lkovalev/files/f1000.jpg[/img]
The same graph minus $ \frac{16}{3\pi}\log\sqrt{x^2\plus{}y^2}$ (rotated). This is a paraboloid-like graph except near the singularity, where the difference between discrete and continuous models remains substantial.
[img]http://www.math.tamu.edu/~lkovalev/files/f1000-2.jpg[/img]

I am not sure it can help, but here is a try with Fedja's idea:
Suppose that $ W(t) \equal{} (B_1(t), B_2(t))$ is a standard brownian motion living in $ \mathbb{R}^2$, starting from $ (1,1)$. Define $ \tau_r$ the time when this brownian motion satisfies $ d(W(t), 2 \mathbb{Z}^2) \leq r$. Now suppose that $ f: \mathbb{R}^2 \setminus \mathbb{Z}^2 \to \mathbb{R}$ is a function that is $ 2$-periodic in each variable and whose Laplacian is $ \minus{} \frac {8}{3}$. Then (consequence of Dynkin's formula):
$ E[f(W^{\tau_r})] \equal{} f(1,1) \plus{} E[\int_0^{\tau_r} \frac {1}{2} \Delta f (W(s)) ds] \equal{} f(1,1) \minus{} \frac {4}{3} E[\tau_r]$
Because $ E[f(W^{\tau_r})] \approx \frac {1}{2 \pi } \int_{[0;2 \pi]} f(r \cos(\theta), r \sin (\theta)) d \theta$, one can see that:
$ E[\tau_r] \approx \minus{} \frac {3}{4} \frac {1}{ 2 \pi} \int_{[0;2 \pi]} f(r \cos(\theta), r \sin (\theta)) d \theta$, (if $ f(1,1) \equal{} 0$)
So is it easy to find an asymtotic development of $ r \mapsto \frac {1}{2 \pi} \int_{[0;2 \pi]} f(r \cos(\theta), r \sin (\theta)) d \theta$ ?
And this could become more precise if one knows that $ f$ is almost constant on the circle $ C(0,r)$ ?? Is it true ?

That is close to the truth but not quite the truth because the difference between the discrete and the continuous models near the singularity is substantial: just the difference between discrete $ F(1,1)$ and $ F(2,2)$ is of order $ n^2$ and the Brownian motion model doesn't really know which of them is closer to the continuous $ F(1,1)$. Fortunately, the difference between the continuous and the discrete model should also allow an asymptotic expansion in pure powers of $ n$. I plan to return to this problem later when I have a bit more free time (unless somebody else solves it first :)).

[quote="fedja"]I thought of this a bit more and also came to the conclusion that $ \frac {16}{3\pi}n^2\log n$ is the right leading term. [/quote]

At least does anyone have a proof for the growth size being as: $ n^2\log n$, not talking about the leading term as: $ \frac {16}{3\pi}n^2\log n$ ?
At least some considerations that allow us to forsee the growth size as $ n^2\log n$ other than computations?


Let X,Y be two matrices, M_n (Z) so that X^3=Y^5=In and XY=YX. Prove that there exists k, k is naatural so that det(X+Y)=2^k.

Tiger Sander,
Germany.

X^15=Y^15=In, so X^15+Y^15=2In, so det(X^15+Y^15)=2^n. But because X and Y commute we get X^15+Y^15=

(X+Y)(X^14+X^13*Y+..+X*Y^13+Y^14), so det(X+Y) an be written as + or - 2^k. We should prove det(X+Y)>0. I think we cxan prove
det(X^14+X^13*Y+..+X*Y^13+Y^14)>0 by decomposing that polynomial (with complex numbers; give it a try). If we prove this it follows that det(X+Y)>0. As you can see, it's not complete, but I think it works like this.

so.. a full solution?! I haven't managed to do what you said ..  :oops:

thank you very much.
Tiger Sandre,
Germany.

:oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:  :oops:

Can someone help?
 :lol:  :lol:  :lol:  :lol:  :lol:  :lol:  :lol:  :lol:  :lol:  :lol:  :lol:  :lol:


Find all positive integers $m$,$n$ s.t: both of $m^{n}$ and $n^{m}$ are $\frac{m+n}{2}+1$ digit numbers.


For each positive integer $ n$, define $ f(n)$ as the number of digits $ 0$ in its decimal representation. For example, $ f(2)\equal{}0$, $ f(2009)\equal{}2$, etc. Please, calculate \[ S\equal{}\sum_{k\equal{}1}^{n}2^{f(k)},\] for $ n\equal{}9,999,999,999$.
[i]Yudi Satria, Jakarta[/i]

for each $ r$ from 0 thru 9, we compute $ N(r)$, the number of of $ k$ for which $ f(k) \equal{} r$. for $ f(k) \equal{} r$, $ k$ must contain at least $ r \plus{} 1$ digits, and at most 10 digits (in the context of this problem). the number of $ d$-digit numbers with exactly $ r$ 0's is $ 9^{d \minus{} r}\binom{d \minus{} 1}{r}$. So

$ N(r) \equal{} \sum_{d \equal{} r \plus{} 1}^{10}9^{d \minus{} r}\binom{d \minus{} 1}{r}$.

Thus

$ S \equal{} \sum_{r \equal{} 0}^{9}\sum_{d \equal{} r \plus{} 1}^{10}2^r\cdot 9^{d \minus{} r}\binom{d \minus{} 1}{r} \equal{} \sum_{d \equal{} 1}^{10} 9^{d} \sum_{r \equal{} 0}^{d \minus{} 1}(\frac {2}{9})^r \binom{d \minus{} 1}{r} \equal{} \sum_{d \equal{} 1}^{10} 9^{d}(\frac {2}{9} \plus{} 1)^{d \minus{} 1} \equal{}  \sum_{d \equal{} 1}^{10}9\cdot 11^{d \minus{} 1} \equal{} 9\cdot \frac {11^{10} \minus{} 1}{10}$.

[quote="pleurestique"] ... is $ 9\cdot 10^{d \minus{} r \minus{} 1}\binom{d \minus{} 1}{r}$....[/quote]

why? there should be some mistakes here?

i had it right the first time. now it's back to its original purity.