geometry
geometric transformation
rotation
function

Wally's Key Company makes and sells two types of keys. Mr. Porter buys
a total of 12 keys from Wally's. Determine the number of possible
arrangements of Mr. Porter's 12 new keys on his keychain (Where
rotations are considered the same and any two keys of the same type are
identical.)

[hide="A Start"]
Taking types of keys being $ X$ and $ Y$, we have a keychain $ K$ such that it has 12$ A$'s and $ B$'s. There is a [url=http://en.wikipedia.org/wiki/Bijection]bijection[/url] (heh I just learned about this a few days ago) between the $ A$ type to $ B$ types and vice versa, we can consider a case with $ n$ $ B$'s and $ 12\minus{}n$$ B$'s, so we need to consider the numbers $ 1,2,3,4,5,6$ types of $ B$'s.[/hide]

I don't know how to progress with this now. Help?

[hide="Solution"]There are
- $ p(1) \equal{} 2$ sequences of period 1
- $ p(2) \equal{} 2^2 \minus{} 2 \equal{} 2$ sequences of period 2
- $ p(3) \equal{} 2^3 \minus{} 2 \equal{} 6$ sequences of period 3
- $ p(4) \equal{} 2^4 \minus{} 2^2 \equal{} 12$ sequences of period 4
- $ p(6) \equal{} 2^6 \minus{} 2^3 \minus{} 2^2 \plus{} 2 \equal{} 54$ sequences of period 6
- $ p(12) \equal{} 2^{12} \minus{} 2^6 \minus{} 2^4 \plus{} 2^2 \equal{} 4096 \minus{} 64 \minus{} 16 \plus{} 4 \equal{} 4020$ sequences of period 12.
(hint for computing these: Mobius inversion)

If the keys in the chain make a sequence of period $ k$, then they have $ k$ total symmetries. So the answer is
$ p(1)/1 \plus{} p(2)/2 \plus{} \ldots \plus{} p(12)/12 \equal{} 2 \plus{} 1 \plus{} 2 \plus{} 3 \plus{} 9 \plus{} 335$
$ \equal{} \boxed{352}$
unless I made an arithmetic error.

[/hide]
General problem:
Wally's Key Company makes and sells $ k$ types of keys. Mr. Porter buys a total of $ n$ keys from Wally's. Determine the number of possible arrangements of Mr. Porter's $ n$ new keys on his keychain (Where rotations are considered the same and any two keys of the same type are identical.)

[hide="Non-closed form answer without proof"]Let $ g : \mathbb{N}^2 \rightarrow \mathbb{N}$ be such that $ g(n,k)$ is the answer to the problem (so the answer to the OP is $ g(12,2)$). If $ \mu(n)$ is the mobius function, then
$ g(n) \equal{} \sum_{d \mid n} \frac{\sum_{m \mid d}\mu(m) k^{d/m}}{d}$

Equivalently, $ g$ is the unique function that satisfies
$ \sum_{d \mid n}\mu(d)k^{n/d} \equal{} n \sum_{d \mid n}\mu(d) g(n/d,k)$
for all $ n,k \in \mathbb{N}$.

Does anyone know how to solve this?[/hide]


My blog is sort of like an encyclopedia(hence the name), so one of my contributors made a nice table of contents for it. I'd like to move it to the front of the blog, right before the first entry, so I was wondering if it's possible to do so. Thanks in advance! :)

The thing about a [i]blog[/i] is that it's based on the entries of the writer, and if the entries could be shuffled around, then it really isn't a [i]blog[/i] now is it?

However, if you maniuplate some CSS, then you might be able to create a menu (#H34N1 has a pop-up menu for his shoutbox or something) for your table of contents.

alternatively, you could periodically post it again or post a link to the entry into your sig


Here's an easy one:

Let $ABC$ be a triangle. Prove that:

$\frac{1}{S}\cdot\sum\frac{ab}{a+b}\leq\frac{1}{a}\cdot\sin B+\frac{1}{b}\cdot\sin C+\frac{1}{c}\cdot\sin A$,

where $S$ is the area of triangle $ABC$.

We write 1/a*sinB as c/2S and we do the same for the others. Then we have to prove  \sum 2ab/(a+b) <=   \sum a, which is well known (AM-HM).

Yeah... told you it was an easy one. Try to solve the other one. That's easy too.


inequalities
geometry
geometric transformation
rotation
inequalities proposed

my sollution not very nice  :P :
by concavity of $ \sqrt {x}$ (jensen inequality) :

$ LHS\leq\,3\sqrt {\frac {2(a^2 + b^2 + c^2 + d^2) - 2(a + c) - 4(b + d) - 2(ac + bd) + 10}{6}}$

$ \iff$   $ LHS\leq\,3\sqrt {\frac {30 - 2(a + c) - 4(b + d) - 2(ac + bd)}{6}}\leq\,3\sqrt {\frac {30}{4}}$

 :D

[quote="vipCD_A1"]For $ a,b,c,d$ such that $ a^2 \plus{} b^2 \equal{} c^2 \plus{} d^2 \equal{} 5$ Prove that:

$ \sqrt {\frac {(a \minus{} 1)^2 \plus{} (b \minus{} 2)^2}{2}} \plus{} \sqrt {\frac {(c \minus{} 1)^2 \plus{} (d \minus{} 2)^2}{2}} \plus{} \sqrt {\frac {(a \minus{} c)^2 \plus{} (b \minus{} d)^2}{2}}\leq \frac {3\sqrt {30}}{2}$

[/quote]
My solution for it :)

[quote="mehdi cherif"]wath do you think about the mine ??[/quote]
I am sorry since you have posted it :( before but I did it independent indeed.

For $ A(1,\ 2), P(a,\ b),\ Q(c,\ d)\in x^2 + y^2 = 5$, the inequality becomes $ \overline{AP} + \overline {AQ} + \overline {PQ}\leq 3\sqrt {15}$.

The equality holds when $ \triangle{OPQ}$ is an equilateral triangle with side length of $ \sqrt{15}$ for ${ P,\ Q\in (\frac{-1+2\sqrt{3}}{2},\ \frac{-2-\sqrt{3}}{2}),\ (\frac{-1-2\sqrt{3}}{2},\ \frac{-2+\sqrt{3}}{2}})$ which can be  easily obtained with the rotation of matrix.


So, does anyone else here do it or have any idea what it's about? Our team captain just coerced me into signing up because they need a full B team. I seem to be signed up for Astronomy and Disease Detectives--I'm not even entirely sure what that means. I thought people here might have some idea about this, since the captain claims that all the cool math people also participate in sci-oly.

What the heck is this? I WANT TO TAKE IT AND FAIL LIKE USUAL!!!!!!!

well, it's basically a team of 15 (or 17 if you have alternates) people doing like 20+ events in all areas of science, even engineering.  So you should kind of find the rule sheet and look over which areas are tested, if you even care.

So yeah...I recall that in Northern California La Mira Loma won a lot? my school dominated So Cal for like 11 years already...

Yeah, it was on Saturday. Regionals, not states, so we had nothing to fear from Mira Loma. I'm not going to states because I was on the B team, but the A team is going and they have resolved to smash everyone else. We'll see how it goes.


A few technical questions related to number theory:

1. What are the divisors of $-1$?

2. What are the divisors of a negative integer, like $-6$?

3. Does $0$ have any divisors?

4. What is the GCF of $0$ and some positive integer $n$?

5. What is the GCF of two negative integers, like $-8$ and $-12$?

6. What is the GCF of a negative integer and a positive integer, like $-8$ and $12$?

Well, you can count positive and negative divisors for any number. For example the divisors for $\pm 6$ are $\{ \pm 1, \pm 2, \pm 3, \pm 6 \}$. So for $-1$ it's just $\{ \pm 1 \}$.

3. 0 has infinite divisors. Any integer technically divides 0.
4. Using 3, it's n.
5. Consider positive factors only. (So 4)
6. Same as 5.

OK, thanks.  That stuff has been bugging me for a while.


abstract algebra
group theory
superior algebra
superior algebra unsolved

[size=150]Can anyone prove the following? It will be really helpful...

1. A finite abelian group that is not cyclic contains a subgroup of type $ (p, p)$ for some prime $ p.$

2. If $ B$ is a subgroup of finitely generated abelian group $ A,$ then the rank of $ A$ is equal to the sum of the ranks of $ B$ and $ A/B.$[/size]

[size=150]Hi,

I found the solution for the first question.

But still figuring out how to do the second one.

Can anyone help??[/size]

$ \mathbb{Q}$ is flat, and $ rank(A) \equal{} dim(A \otimes \mathbb{Q})$.


Let $AB$ and $CD$ be two perpendicular diameters of a circle with center $O$. Consider a point $M$ on the diameter $AB$, different from $A$ and $B$. The line $CM$ cuts the circle again at $N$. The tangent at $N$ to the circle and the perpendicular at $M$ to $AB$ intersect at $P$. Show that $OP=CM$.

[quote="justdudxit"]Show that $OP+CM$ equals what?[/quote]
To show that OP=CM. It follows from the fact that P, O, M and N are cyclic. Hence <OCN=<ONC=<OPC=<POD, hence $CM \parallel OP$. So CMPO is a parallelogram. So CM=OP.

Yes, I'll post more about it in the African forum later, I'm in a bit of a hurry now. I'll also post my solutions later.

Let <MCO = $\alpha$ and <CMO = $90-\alpha = \beta$.  Using the parallel postulate, we find that POD = $\alpha$.  Furthermore, MOD = $90-\alpha$ = $\beta$.  Taken together with the fact that OMP = 90, we see triangles MOP and OMC are congruent, hence OP = CM.


function
integration
search
real analysis
real analysis unsolved

Let $ f:\mathbb{R}\to (0,\infty) $ a  derivable function on $[a,b]$ Prove that there is a point $ c\in (a,b) $ such that

                  $ \frac{f'(c)}{f(c)} =\frac{\int_{a}^{c} f(t)dt- \int_{c}^{b} f(t)dt}{\int_{a}^{c} f(t)dt \cdot\int_{c}^{b} f(t)dt} $ ;)

Don't worry, Cezar, as someone said on the site, there are two possibilities: either the problem is really extremely hard (which I doubt), either it is very easy. I would add another possibility: either it is too ugly. Guess which part belongs to this problem.  ;)

I don't know, Harazi. If you are saying that this problem is ugly then it means that the members of the National Board Olympiad are......(I prefer not to say).I'm teling this to you because this problem was awarded at }motto contests" in 1976.  :D So I think it remains to say that this problem is quite easy which is very true. ;)

Yes, sometimes they are. Sorry to tell you, but such problems can be created on an industrial scale. Just take some wierd functions and apply Rolle to them. I apologize if it is based on a really nice idea, but to my shame I have never, but never seen a smart idea in this kind of problems. They are all the same. And to speak about those who select the problems, just look on our "shortlist" for national olympiad and you will see the quality I was speaking.  ;)

And to prove I'm right, apply Rolle to $ e^{f(x)}\cdot\int_{a}^{x}{ f(u)du}\cdot\int_{x}^{b}{ f(u)du}$. :P   You see, there's nothing beautiful here, it's just guessing (or knowing how to guess  ;) ) the right function. And I maintain my opinion about most of the "honorable" members of the Board (of course, there are also magnifient teachers, nobody says no, but they are a few...).

I'm sory to tell you this, but at some point I don't agree with you. I think  there is a new idea to construct a function and the apply Rolle's theorem. Well,by Rolle's, we can deduce tones of theorems even hard ones sometimes.Here, I know what I'm talking, because I have demonstated some numerical analisys theorem just constructing a function and applying Rolle's theorem. ;) and think Numerical Analisys I'll study when I'll be graduating. :D

 By the way, take a numerical Analysis book and will see some theorems and their proofs are so hard and so long.
 In conclusion, I think constructing such functions are necessary to improve something. ;)

Ok, be it as you wish, but I find much more interesting the analysis I'm doing than spending my time with the search of some functions which are good at nothing else than creating huge formulas. Sorry.

Excuse me,I'm telling you that I've demonstrated formulas just using Rolle's formula which are one of the best in approximation. Isn't that interresting. What this world will do without approximation? ;) Formulas that great mathematicians like: Newton,Cotes, Russel,Bourbaki, Richardson,Abramovitz,D.D Stancu were trying to discover. This kind of formulas were used in computer scince. ;)

Oh, believe me, it would be much nicer, especially for me. I'm doing quite a lot of physics now and then you'll see approximations. So please don't remind me about such extraordinary fields. And I'm happy to see your great results in analysis. Have you thought to send them to some great magazines?  ;)

:starwars: Frendly conversation  "cezar lupu "  versus " harazi" :starwars:                 :D
Anyway, another one : if $f(x)$ is a continue and odd function  then $\displaystyle \forall a \exists c  ,   f(c)=ln(2+c^2)\int_a^c f(x).dx$
 :cool: Do you follow me ?  :cool:

[quote="cezar lupu"]Of course I have a paper which will be published very soon in "Analele Universitatii Bucuresti".I hope before 6 October. Even Mr. I.Rosca and Gh.Grigore told me that the proofs are very easier and they agreed to publish it. ;)[/quote]
What is it about?

Some intermediate value formulas. If you want I'll send you a copy after this will be published. ;)


http://www.artofproblemsolving.com/Forum/weblog.php?w=960

Zhang got 180,000+ views in three days. I'm pretty sure the server would "die" if that really happened, so methinks this a bug?

It's displaying for all of us, and we all use different browsers and everything, so it's not a browser/OS/skin/etc. specific thing.

[quote="Temperal"][quote="ZhangPeijin"]Umm, All I can think of is that someone went crazy with a bot...[/quote]

That's called a Denial of Service (DoS) attack, which would at least AoPS down dramatically. I haven't notice any changes in the speed of AoPS recently, so I think it's a bug.[/quote]We did have a DoS attack last week that took the site down for 45 minutes. It's curious as to why our hosts hardware firewalls weren't able to stop it to begin with ...

I just have one question. Why do a DoS attack here?

I don't think DoS attack had anything to do with it because his blog was made after it had already had happened.

[quote="hunter34"]I just have one question. Why do a DoS attack here?[/quote]
1) Some people DoS random sites.
2) We do actually have one or two trolls.
3) (Silly one) A rival maths forum is trying to take us down!


For a sequence of numbers from $ 1,2,3, \cdots, n$ let $ p$ be the largest prime that exists in this sequence. Show that there $ p<n<2p$

[quote="Kono"]For a sequence of numbers from $ 1,2,3, \cdots, n$ let $ p$ be the largest prime that exists in this sequence. Show that there $ p < n < 2p$[/quote]

What a bad problem. Ask your teacher to be careful when creating olympiad training problems :

1) the problem is wrong :
Take $ n\equal{}1$ and no largest prime number exists.
Take $ n\equal{}2$ and largest prime is $ 2$ and $ 2<2<4$ is wrong.
Take $ n\equal{}3$ and largest prime is $ 3$ and $ 3<3<6$ is wrong ..
So, for example, it's wrong for any prime $ n$

2) when it will be corrected, it will be, as Pluristiq said, Bertrand's postulate ot Chebyshev's theorem.
And it seems strange to ask for a demonstration of this theorem in an olympiad training problem.


inequalities
calculus
calculus computations

Given $ \frac {1 \minus{} tx}{x}\le0$

How does one conclude that:
$ x \ge t$ and $ x < 0$ when $ t > 0$.

and $ \frac {1}{t}\le x < 0$ , when $ t < 0$

Thanks.

hello, let us consider three cases.
1. $ t=0$ here we have $ \frac{1}{x} \le 0$, this implies $ x<0$.
2. $ t<0$,in this case it can't be $ x>0$. If $ x$ would be greater than zero we got: $ tx \geq 1>0$. This is a contradiction to $ x>0$ and $ t<0$, summary we got:
$ \frac{1}{t} \geqq<0$ and $ t<0$.
3. $ t>0$. A simple calculation shows the result $ x<0$ or $ x \geq \frac{1}{t}$.
Sonnhard.


Gauss
linear algebra
matrix
geometry
linear algebra solved

I have worked this problem out on three different sheets of paper and I really think I am missing something very simple.  I need things explained to me in very simple terms because I am not very proficient in linear algebra.

[color=darkblue]solve for x' and y' in terms of x and y using Gauss-Jordan Elimination.

x=3/5 x' - 4/5 y'
y=4/5 x' + 3/5y'[/color]

I worked this problem out the way I thought I was supposed to and ended up with just x'=7/5x  and y'= -1/5y.
However, the answer given is:

x' = 3/5x + 4/5y
y' =-4/5x + 3/5y

What did I do wrong?

Apply Gauss-Jordan Elimination at the matrix

$\left( \begin {array}{cc |cc} 3/5 & -4/5&1&0 \\\ 4/5& 3/5 & 0&1 \end{array} \right)$

and try to bring the matrix $\left( \begin {array}{cc} 3/5 & -4/5 \\\ 4/5& 3/5 \end{array} \right)$ in the form $\left( \begin {array}{cc } 1&0 \\\ 0&1 \end{array} \right)$.

Then the other block will be the matrix of the coefficients you are searching.
This is another way to find the inverse of a matrix.

It seems that you used Gauss-Jordan Elimination at the matrix $\left( \begin {array}{cc |c} 3/5 & -4/5&1 \\\ 4/5& 3/5 & 1 \end{array} \right)$ .

You should do it for the matrix $\left( \begin {array}{cc |c} 3/5 & -4/5&x \\\ 4/5& 3/5 & y \end{array} \right)$.  :)

:) I wanted to thank you for such a detailed and simplistic explanation of how to do this.  I don't understand the really mathematical terms some replies come in.  I am going to be a high school geometry and financial math teacher, but I am required to take this linear algebra course so I can graduate in May. Thanks again.  I hope to get other replies like your on future problems I may have. :blush:


Set M consists of the positive odd integers less than 92 which are multiples of 3 or 5. What is the sum of all of the elements in M?

[hide]30 multiples of 3... so 15*31*3 is sum of those. (Gaussian sum thingy mixed in)
18 multiples of 5... so 9*19*5 is the sum of those.
6 multiples of 15, so 3*7*15 is the sum of those.
Add first two, subtract last one. You have a calculator.[/hide]


[hide="hint"]WLOG assume that $ c=1$, setting $ \sqrt{ab}=x$, by $ a+b\geq 2x$ that inequality is true iff following inequality are true $ 120x^{2}\leq (2x+1)[4x^{2}+(2x+4)^{2}]\forall x>0$.[/hide]


In the game of Racko you have 10 slots for cards to go in. At the start, cards are dealt to each player and put in order that they were dealt starting from the 'highest slot'.  The cards are numbered 1-60.  The object is to get all of your cards in order, by means of drawing and switching in a discard pile.  When all your cards are in order, you call "Racko" and the hand is over.

What is the probabilty that you will be dealt a "Racko"?

[quote="deej21"]The way I understand it... you're dealt 10 cards, and you want the probability they are in increasing/decreasing order.

You have 10 distinct cards, and there is only one way they can be in the right order, so $\frac 1 {10!}$?[/quote]
Aren't there 2 ways, increasing and decreasing?

Is "in order" defined as...

$c_1<c_2<c_3<c_4<...$

or

$c_1=c_2-1=c_3-2=c_3-3...$

because if it's the first definition than I believe it's $\frac{2}{10!}$, but if you are required to get $10$ cards that are consecutive and in numerical order then I believe my answer is correct.


geometry
circumcircle
incenter
trigonometry
geometry unsolved

In acute-angled $\bigtriangleup ABC$, $H$ is the orthocenter, $O$ is the circumcenter and $I$ is the incenter. Given that $\angle C > \angle B > \angle A$, prove that $I$ lies within $\bigtriangleup BOH$.

guess no one bothered with this one, but I'll give an approach (I'll leave it for those that care to finish... :D ) Two steps: first show that angleCBH < angleCBI < angleCBO (I lies within angle HBO), this is really easy once you simplify everything. Second, prove that IY (Y being the perpendicular foot of I on AB) is not long enough to reach line segment OH. This is proven by assigning X and Z to be the perpendicular feet of H and O on AB, respectively. Then, showing that (|HX|-|OZ|)*(|YZ|/|XZ|) > |IY|-|OZ|. I give fair warning that this is a nasty and commutative trig thing, it's really not a pleasure doing it. But it works!  :D

Here's a nice way to do it. Since that $O, H$ are isogonal conjugates, $AI, BI, CI$ bisects $\angle HAO, \angle HBO, \angle HCO$ as well. Let $AI, BI, CI$ intersect $OH$ at $K_a, K_b, K_c$, drop perpendiculars $OP_a, OP_b, OP_c$ to $BC, AC, AB$. Since $AB>AC>BC$, $OPc<OP_b<OP_a \Rightarrow CH<BH<AH$ from the well-known fact that $AH=2OP_a$ and similarly for $B, C$. It follows that $\frac{CH}{CO}<\frac{BH}{BO}<\frac{AH}{AO}$, which means \[\frac{HK_c}{K_cO}<\frac{HK_b}{K_bO}<\frac{HK_a}{K_aO}\]Therefore $AI$ intersects segment $OK_b$ and $CI$ intersects segment $HK_b$, therefore they concur inside $\bigtriangleup BOH$, as desired.


[quote="chess64"]Triangle $ABC$ is isosceles with base $AC$. Points $P$ and $Q$ are respectively on $CB$ and $AB$ such that $AC=AP=PQ=QB$. Find $\angle B$. (AHSME 1961)[/quote]

Diagram?

The problem didn't come with one. ;) That's why it's hard.

shobber's answer is indeed correct.

[hide="Explanation"]

Set $\angle B = x$. Now, we have a lot of isosceles triangles so let's investigate each one of them. For $\triangle BQP$, we have $QB = QP$ so $\angle QPB = \angle B = x$ and $\angle BQP = 180-2x$. Below $\triangle BQP$ is $\triangle AQP$ with $QP = AP$. Since $\angle AQP$ is an exterior angle, it will have measure of $2x$. $\angle AQP = \angle QAP = 2x$ and thus, $\angle QPA = 180-4x$. Now, $\angle BPC = 180^\circ$ so $\angle APC = 180-(180-4x) - x = 3x$. For $\triangle APC$, we have $AP = AC$. Hence, $\angle APC = \angle ACP = 3x$ and $\angle PAC = 180-6x$. And let's look at the big triangle $ABC$. $\angle A = \angle C$ since $AC$ is the base.

Now, $\angle A = \angle QAP + \angle PAC = 2x+180-6x = 180-4x$ and $\angle C = \angle ACP = 3x$. They're equal so setting them equal lets us to find $\angle B$.

$180-4x = 3x\\
180 = 7x\\
x = \frac{180}{7}$ degrees.

QED [/hide]

Hope this was clear enough!

[hide="solution"]
In $\triangle{ABC}$,
Let $\angle{PAC}=180-2x$ and $\angle{PAQ}=y$,
So, from some results we get $\angle{BQP}=180-y$ Giving $\angle{B}=\frac{y}{2}$
At point $P$ we see a linear equation forming,
$\frac{y}{2}+(180-2y)+x=180$ - $\boxed1$
we also know that,
$y+180-2x=x$,
as $\angle{A}=\angle{C}$
Solving this we get $\angle{B}=\frac{180}{7}$
[/hide]


algebra
polynomial
irrational number
number theory

How would you go about proving that a number, say, $e$ , is transcendental, assuming you already know that it is irrational.  I know how to prove that $e$ is irrational, but how could you ever prove that $e$ can't be the root of a polynomial with integer coefficients with a finite degree?

i dont know, but ive read this is extremely difficult and ugly

Gelfond's Theorem could be useful, nevertheless, I do not think that there is an elementary proof for that.

Well, I can tell you a way to prove that some numbers are trancendental, but it doesn't work for numbers like e and pi.

Let us take an irrational number that can be approximated "really closely" by rational numbers.  An example of this is a number like 0.10100100000010000000000000000000000001000...

where the number of zeroes between 1's are 1!, 2!, 3!, 4!, etc.  With a fraction of relatively small denominator (say, 1010010000001/10000000000000), we have an accuracy to 10^-47 or so.  (This can be formulated in a rigorous way.)  Anyhow, it can be shown that any number with infinitely many such "very accurate" approximations is trancendental.  But, most trancendental numbers don't have such accurate approximations.

There is a beatifully written book entitled "Making Transcendence Transparent: An Intuitive Approach To Classical Transcendental Number Theory" by Burger, Edward B. and Tubbs, Robert.  There you will find a motivated proof of transcendence of e.

Boris


Find the last wo digits from the following:

$ 2^{2002}\left( 2^{2003} \minus{}1\right)$


[quote="guile"]1.) Determine all integral solutions of $ 54x \plus{} 21y \equal{} 906$ and $ 87x \plus{} 51y \equal{} 603$
2.) Determine all solutions in positive integers:  $ 123x \plus{} 360y \equal{} 99$[/quote]

$ ax \plus{} by \equal{} c$ has solutions if $ d \equal{} (a,b)|c$ and the solutions are:
\[ x \equal{} x_0 \plus{} kb',\: y \equal{} y_0 \minus{} ka', k\in\mathbb{Z}
\]
where $ x_0,y_0$ are particular solutions of the original equation and $ a' \equal{} \frac {a}{d},\: b' \equal{} \frac {b}{d}$

[quote="guile"]1.) Determine all integral solutions of $ 54x \plus{} 21y \equal{} 906$ [/quote]
For the first equation
\[ x\equal{}16\plus{}78k, y\equal{}2\minus{}18k, k\in\mathbb{Z}\]
For the second:
\[ x\equal{}4\plus{}17k,\: y\equal{}5\minus{}29k,\: k\in\mathbb{Z}\]

[quote="madness"]In fact 2. has no solution!!!!![/quote]

[hide="Proof:"]Since the coefficients of the equation are positive, the minimum of that equation is at (1,1), and the equation has a value of 483, which is greater than 99, therefore the equation cannot have a value of 99.[/hide]


[Note:  I originally posted this in the intermediate forum, but didn't get any comprehensible responses, so I'm posting it here.]

A driver in a car is in the desert, 10 km from the nearest point, $ N$, on a long, straight road.  The driver can cover 30 km/h in the desert, and 50 km/h on the road.  What is the shortest time for the driver to reach a point on the road that is:

(a) 20 km from $ N$?
(b) 30 km from $ N$?

Which part didn't you understand? I will try to clarify.

Thanks, math154.  I'll try to respond in the intermediate forum.  I really appreciate your help.


A rectangular table has legs of unequal length. Two legs on one diagonal of the table measure 24 and 28 inches and a third elg measures 30 inches. What should the fourth leg measure so that the table can rest on a levle floor without wobbling?

A. 20 in
B. 22 in
C. 24 in
D. 26 in
E. There is no such measure

[hide="Hint"]Notice that the midpoint of one diagonal is also the midpoint of the other diagonal, since the table is rectangular.[/hide]

[hide="Solution"]Call the table ABCD, then leg A is 24 inches, leg B is 30 inches and leg C is 28 inches. Let the point where the two diagonals AC and BD intersect be $ M$. Since M is the midpoint of AC, the perpendicular height of M is:

$ \frac {24 + 28}{2} = 26$

Since M is also the midpoint of BD:

\begin{align*}\frac {30 + D}{2} & = 26 \\
D + 30 & = 26*2 = 52 \\
D & = 22\Rightarrow\boxed{B}\end{align*}

Of course, this is all assuming the table's legs are perfectly straight with reference to the ground, and the legs are all at the corners of the table.[/hide]


A cart with wieght $m\text{ N}$ is placed on top of a desk.  A pully with a string is attached to it; on the other end of the string, a mass of $n\text{ N}$ is attached.  The cart is on earth ($g=9.8\text{ m/s}^2$).  How long does it take the cart to travel $k\text{ m}$, where the length of the string and the top of the desk are $>k$?

Masoud Zargar

consider the system together. the total force on it is just the weight of the hanging mass i.e $n N$  and the mass is $(m+n)/g$ so the net
acceleration is $ng/(m + n)$  .then using second kinematics equation,
$S = ut + 1/2 at^2$ or simply as$2k = at^2$
or $t = sqrt( 2k/a)$
wher $a= ng/m+n$
is the required time.


Prove the following multiplicative property of the gcd:
$ (ah,bk)\equal{}(a,b)(h,k)\left ( \frac{a}{(a,b)},\frac{k}{(h,k)} \right )\left ( \frac{b}{(a,b)},\frac{h}{(h,k)} \right )$

i already tried using Bezout identity and $ (a,b)\equal{}\frac{a\cdot b}{[a,b]}$


ok many of us are pretty much familiar with the sum of the first $n$, $n^2$, and $n^3$. in view of the recent topic discussion in [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=42048]Sum of first n squares[/url], lets extend a little more (it doesnt hurt, does it?  :P ), and lets go and find the formula for the sum of the first $n^4$. please show your method and creativity, dont just state the formula otherwise it is [b]rubbish[/b] (as riddler suggested :D). ONE BIG RULE: NO MATH INDUCTION PLEASE, i dont like induction  :harhar:

Well, we know that the sum 1-> n of  (x+1)^5-(x^5), (which is also equal to 5x^4+10x^3+10x^2+5x+1) sums to (n+1)^5-1 because the whole thing telescopes. Knowing the formula for x, x^2, and x^3, we can plug them in to get
(sum 1->n 5x^4)+10((n(n+1)/2)^2)+10n(n+1)(2n+1)/6+5(n(n+1)+1=(n+1)^5 -1.

Expanding this and isolating x should give us the answer

ok, that idea i applied it in my previous linked post, i found there are small mistakes in your post :D but basically this method works (i call it russian sum powers method because i saw it first in a russian monograph). is there anybody that has other insightful ideas beside this? no advanced Bell numbers please  :blush:


AMC
AMC 10
MATHCOUNTS
AIME
USA(J)MO
USAMO
AIME I

First, What book would you recommend for a rising 9th grader who scores ~132 on amc10 and scores high 30s, low 40s, on state level mathcounts. I picked out Volume 1, but not untirely sure it would be hard/easy for me. Btw, this is out of two choices: Volume 1 or Volume 2.

Second, If I got the Volume 1 book, how important is the solution book that goes with it. Like, is the solution book a must-need if i got Volume 1?

I'm not sure about your first question, but for the second: you need to get the solution's manual.

If you are doing good on a competition, then review what you have missed on, and get the right book to learn the material to help you with the competition.

[quote="simo14"]I would go with AOPS 2- most of volume 1 will be review. Some of it will be hard, but you can just take it slow and post questions on the forums.[/quote]

I never did Volume 1, sucked at Mathcounts, and I'm still not that smart, but I've been trying out Volume 2. I would suggest getting Volume 2 (and you need the solutions, they're absolutely necessary).

But, if you find it hard, you need to patient and try as hard as you can to solve the problems without (almost never) looking in the solution guide for the answer.

Also, Volume 2 is (I find) a great start to some introductory high school math.

Volume 2, since you're starting high school and should start working on that material. With those scores, I would guess that you have most of Volume 1 mastered--those were about the scores I was getting after working through most of Volume 1 (my 8th grade).

If you can qualify for AIME, I highly recommend starting with volume 2; volume 1 would be most useful for someone preparing for AMC 10 or Mathcounts. In addition to volume 2, you might also want to check out Problem Solving Strategies by Arthur Engel, which is another excellent book for preparing for higher levels of math competitions.

Try [url=http://www.amazon.com/exec/obidos/ASIN/0821804308/artofproblems-20]Mathematical Circles[/url].  It's more simple-proof oriented than AMC/AIME, but it teaches problem solving well.

[quote="HiDN428"]what other books could also help me on amc/aime? Like the one blackbelt mentioned.[/quote]

PSS is probably mostly non-applicable for amc/aime.... PSS is more for usamo training.

For amc/aime, ACoPS is good.

[quote="blackbelt14253"][quote="pythag011"]For amc/aime, ACoPS is good.[/quote]

Actually, I was wondering if ACoPS would be good for usamo?[/quote]

ACoPs is medium AIME - beginning USAMO level


ratio
quadratics
logarithms
function
algebra
quadratic formula

Find B/A if log(base4)A=log(base6)B=log(base9)(A+B)

Is there some kind of rule about multiplying bases? I reduced the first and third parts to log(base2)A=log(base3)(A+B), and got stuck. Can someone help or tell me a rule I might be missing?

BTW, the answer is [hide]The Golden Ratio[/hide][/code]

[hide]We can rewrite the equations as

log A / log 4 = log B / log 6

log A / log 2 = log (A + B) / log 3.

Let x = log 2, y = log 3, then

log A / 2x = log B / (x + y)

log A / x = log (A + B) / y.

Cross-multiply the two to get

(x + y) log A = 2x log B

y log A = x log (A + B)

Subtract the second one from the first one,

x log A = 2x log B - x log (A + B)

log A + log (A + B) = 2 log B

log (A2 + AB) = log B2

A2 + AB = B2

Divide both sides by A2,

1 + B / A = (B / A)2

(B / A)2 - B / A - 1 = 0

Use the quadratic formula to get

B / A = (1 :pm: :rt5:) / 2. We have to discard the negative answer (B and A are both positive), so

B / A = (1 + :rt5:) / 2 = the golden ratio.[/hide]

Or:
Log4A = Log6B = Log9(A + B) = x
4x = A
6x = B
9x = A + B

Multiplying the first and third together, and squaring the second, we get
A(A + B) = 36x = B2.
B2 - AB - A2 = 0.
(B/A)2 - (B/A) - 1 = 0.
B/A = (1 :pm: :sqrt:(1 + 4))/2
A and B must both be positive.
B/A = :phi:

Very Nice problem! And nice solutions Osiris and JBL!

Wow, excellent solutions. Thanks so much!

Now since that problem has been solved, try this one:

log[size=75]25[/size]p = log[size=75]9[/size]q = log[size=75]15[/size](p + 3q)

Solution: [hide]No solutions.  Reason:  p, q must be positive, or else you can't take a logarithm of them.  Thus, p + 3q is greater than p.  However, we have log25p = log15(p + 3q), and since logyx is an increasing function of x and a decreacing function of y, this implies that p > p + 3q.  (In other words, when you switch 25 to 15, you also have to switch p to something smaller, in this case p + 3q, in order not to change the value of the function.)[/hide]

JBL wrote:Solution: [hide]No solutions.[/hide]

[hide]It has solutions, it's just that they just are not real.[/hide]


linear algebra
matrix
linear algebra unsolved

I was wondering if someone had an elegant construction to find a basis of invertible matrices for $\mathbb{L}(V)$.

Here is $V$ an $n$-dimensional vectorspace, and $\mathbb{L}(V)$ is the vectorspace of all linear transformations on $V$.

for example, a matrix can be uniquely decompose as a sum $M=D+B$ where $D$ is diagonal with zero trace, and $B$ as equal elements on the diagonal. This leads to the following basis: $Id$, $\{Id+E_{i,j}\}_{1 \leq i \neq j \leq n}$, $\{Id-n E_{i,i}\}_{1 \leq i \leq n-1}$


superior algebra
superior algebra unsolved

[quote="Iorderinfinite"]need help with this one.

if A and B are n x n matrices, show that it is impossible for

AB-BA=I

where I is the n x n identity. (hint* traces are helpful).[/quote]

Hello.
It is known that Tr(AB) = Tr(BA), thus Tr(AB - BA) = O.
On the other hand, Tr(I) = n, thus AB - BA cannot be equal to I.

Friendly,
P.

... assuming that the base field has characteristic 0. e.g,

[1,0;1,1] [1,1;1,1] - [1,1;1,1] [1,0;1,1] = [1,0;0,1]  in characteristic 2.


group theory
abstract algebra
superior algebra
superior algebra unsolved

Suppose G a group finite then:
G is a T-group soluble in only if only subgroups of G are pronormal
HOW TO DEMONSTRATE?
HELP-ME PLEASE :-((((
THANKS
SASTRA

Why did you post the question again with minimal changes¿ ( http://www.mathlinks.ro/Forum/viewtopic.php?t=129372 )
There is an Edit-Button!
This was about the 13th time you did this.
Next time this happens, I will delete both threads about it, not just one ;)

And pease stop with this "HOW TO DEMONSTRATE", in general with capitalizing whole lines of text.


I think you're just proving what the expression is mod 9, not mod 3^(n+1). The second part may be inducted on n, but the first part is weaker: it's just proved for mod 9. Unless I'm not seeing something...

I've posted this before....... :?

Base case: For $n =1$, we have $2^3 + 1 = 9$, which is divisible by $3^{1+1} = 9$

-Induction hypothesis:
Assume $2^{3^k}+1$ is divisble by $3^{k+1}$

-Now we must show that $2^{3^{k+1}}+1$ is divisble by $3^{k+2}= 3*3^{k+1}$ using our induction hypothesis.

$2^{3^{k+1}}+1 = {(2^{3^k})}^3 +1$

Factoring as a sum of cubes, we have:

${(2^{3^{k}} + 1)({(2^{3^k})}^2 - 2^{3^k} + 1)}$

Now $2^{3^{k}}+1$ is divisible by $3^{k+1}$ by our inductive hypothesis. So it remains to show that ${(2^{3^k})}^2 - 2^{3^k} + 1$ is divisible by $3$. Consider everything $\mod 3$.

${(2^{3^k})}^2 \equiv 1 \mod 3$

$2^{3^k} \equiv 2 \mod 3$

$1 \equiv 1 \mod 3$

$1-2+1 = 0$. So ${(2^{3^k})}^2 - 2^{3^k} + 1$ is divisible by $3$.

So ${(2^{3^{k}} + 1)({(2^{3^k})}^2 - 2^{3^k} + 1)} = 2^{3^{k+1}}+1$ is divisible by $3^{k+2}$, and induction is complete.

So the statement is proved. QED

[color=red][Quote] -->[/color]
${(2^{3^k})}^2 \equiv 1 \mod 3$

$2^{3^k} \equiv 2 \mod 3$

$1 \equiv 1 \mod 3$

I can see the last is true (obviously) and that if we know the second is true then so is the first, but how [i]do[/i] we know that the second is true?
(Unless is it some Fermat's Mini or something like that...)

I seem to recall seeing  this  (or a VERY similar to this problem)  in  a  recent USAMO /IMO(1998 or later)  too...

wow those are pretty glaringly simple! thanks

[quote="M4RI0"]Really simple :D :

$2^{3^k} \equiv (-1)^{3^k} \equiv -1 \equiv 2 \mod 3$[/quote]
I dont quite follow what you're doing here

[quote]I dont quite follow what you're doing here[/quote]
All mod 3...
, 2 is congurent to -1, and  and  $3^{anthing}$ is odd, and $(-1)^{any \ odd \ number}$ will be (-1) which is same as 2 .. (All mod 3, of course)

I have proven this one before

[quote="shyong"]Letting $3^n=3m$ and $2^{3^n}+1=a_n$ then the question want us to prove $3^{n+1}|a_n$

We see that $a_n=2^{3^n}+1=2^{3m}+1=(2^m+1)(4^m-2^m+1)=(a_{n-1})(4^m-2m+1)$

but $4^m-2^m+1\equiv 0\mod 3$

Hence it can be reduce to $a_n\equiv (a_0)3^n\equiv 3^{n+1}\mod 3$   since $a_0=3$[/quote]

so we can see that you can only reduce it to $3^{n+1}$ but not $3^{n+2}$

 :)

By [b]LTE[/b],
$v_3(2^{3^{n}}+1)=v_3(2+1)+v_3(3^{n})=n+1$.
Therefore we proved (ii).The answer of (i) is $\boxed{\mathbb N}\blacksquare$ :coool:

i)equivalent with $2^{2\cdot 3^n}\equiv 1 mod 3^ n$ which is true  by Euler
ii)lets assume the contrary so we must prove that $4^{3^n}\equiv 1 mod 3^{n+2}$ or $3^{n+2}|4^{3^n}-1^{3^n}$ by LTE we have $v_3(4^{3^n}-1^{3^n})=v_3(4-1)+v_3(3^n)=n+1$

[quote=Rushil](i) Determine the set of all positive integers $n$ for which $3^{n+1}$ divides $2^{3^n} + 1$;

(ii) Prove that $3^{n+2}$ does not divide $2^{3^n} + 1$ for any positive integer $n$.[/quote]

We can apply LTE here,
Since $3$ is an odd prime and $3|2+1$, we can say,
$v_3(2^{3^n}+1)=v_3(2+1)+v_3(3^n)$
$\implies v_3(2^{3^n}+1)=n+1$

So, $3^{n+1}||2^{3^n}+1$ for all positive integer $n$.

a) $\forall$ odd n,  $3^{n+1} \mid 2^{3^n}+1$. Now we just need to prove it by induction.\\
(b) Since $p=3$ which is a odd prime and $p\nmid 2 \cdot 1$ and $p \mid 2+1$ we can apply LTE here,
\[\nu_3(2^{3^n}+1)=\nu_3(3)+\nu_3(3^n)=n+1\]
This shows that the largest power of 3 dividing the expression is $n+1$.


trigonometry
algebra
function
domain
algebra unsolved

We can see that $ x\equal{}2$ is a root.

Squaring both sides and bringing all terms to the left,

$ x^6 \minus{} 6x^{4} \plus{} 9x^{2} \minus{}x\minus{}2\equal{}0$

$ (x\minus{}2)(x^{2} \plus{} x \minus{}1)(x^{3}\plus{}x^{2}\minus{}2x\minus{}1)\equal{}0$

The second factor gives $ x\equal{} \frac{\minus{}1 \pm \sqrt{5}}{2}$, that is $ \frac{1}{\phi}$ and $ \minus{}\phi$.

I'n not sure about the cubic yet, but I hope this is helpful..

How could I have missed that: it seems so obvious now! Thanks.

Although it is much better to use kunny's substitution and use trigonometry,I am going to do it by Algebra alone (not wise in this case)

Given: $ x^3 \minus{} 3x \equal{} \sqrt {x \plus{} 2}\implies x^3 \minus{} 3x\ge 0\implies x\in \left[ \minus{} \sqrt {3},\ 0\right]\cup \left[\sqrt3{},\infty\right)$

Now take square of both side,

$ \implies x^6 \plus{} 9x^2 \minus{} 6x^4 \equal{} x \plus{} 2$

$ \implies x^6 \minus{} 6x^{4} \plus{} 9x^{2} \minus{} x \minus{} 2 \equal{} 0$ ----(i)

By plugging $ \ x \equal{} 2$ we get LHS of (i) = 0

$ \implies x^5(x \minus{} 2) \plus{} 2x^4(x \minus{} 2) \minus{} 2x^3(x \minus{} 2) \minus{} 4x^2(x \minus{} 2) \plus{} x(x \minus{} 2) \plus{} 1(x \minus{} 2) \equal{} 0$

$ \implies (x \minus{} 2)(x^5 \plus{} 2x^4 \minus{} 2x^3 \minus{} 4x^2 \plus{} x \plus{} 1) \equal{} 0$

$ \implies (x \minus{} 2)\left[x^3(x^2 \plus{} x \minus{} 1) \plus{} x^2(x^2 \plus{} x \minus{} 1) \minus{} 2x(x^2 \plus{} x \minus{} 1) \minus{} 1(x^2 \plus{} x \minus{} 1)\right] \equal{} 0$

$ \implies (x \minus{} 2)(x^2 \plus{} x \minus{} 1)(x^3 \plus{} x^2 \minus{} 2x \minus{} 1) \equal{} 0$

$ \implies (x \minus{} 2)\left(x \plus{} \frac {\sqrt {5} \plus{} 1}{2}\right)\left(x \minus{} \frac {\sqrt {5} \minus{} 1}{2}\right)(x^3 \plus{} x^2 \minus{} 2x \minus{} 1) \equal{} 0$

Considering the domain of the problem we get $ \ \boxed{\boxed {x \equal{} 2, \minus{} \frac {\sqrt {5} \plus{} 1}{2}}}$

Now only thing left to solve $ \ x^3 \plus{} x^2 \minus{} 2x \minus{} 1 \equal{} 0\ .$ For this let $ \ f(x) \equal{} x^3 \plus{} x^2 \minus{} 2x \minus{} 1$

Observe the following:

$ \ f( \minus{} 2) \equal{} \minus{} 8 \plus{} 4 \plus{} 4 \minus{} 1 < 0,\ f( \minus{} \sqrt {3}) \equal{} \minus{} 3\sqrt {3} \plus{} 3 \plus{} 2\sqrt {3} \minus{} 1 \equal{} 2 \minus{} \sqrt {3} > 0,$

$ \implies\text {one root of}\ f(x) \equal{} 0\ \in( \minus{} 2,\ \minus{} \sqrt {3})$

$ f( \minus{} 1) \equal{} \minus{} 1 \plus{} 1 \plus{} 2 \minus{} 1 \equal{} 1 > 0,\ f(0) \equal{} \minus{} 1 < 0$,

$ \implies\text {one root of}\ f(x) \equal{} 0\ \in( \minus{} 1,\ 0)$

$ f(1) \equal{} 1 \plus{} 1 \minus{} 2 \minus{} 1 < 0,\ f(\sqrt {3}) \equal{} 3\sqrt {3} \plus{} 3 \minus{} 2\sqrt {3} \minus{} 1 \equal{} 2 \plus{} \sqrt {3} > 0$

$ \implies\text {one root of}\ f(x) \equal{} 0\ \in(1,\ \sqrt {3})$

$ \implies$ the only root which lies in our domain is $ \ \boxed{\boxed{\alpha\ \in( \minus{} 1,0)}}$ such that  $ \ \alpha^3 \plus{} \alpha^2 \minus{} 2\alpha \minus{} 1 \equal{} 0$

Now we can use Cardano's mathod to solve the equation  $ \ x^3 \plus{} x^2 \minus{} 2x \minus{} 1 \equal{} 0\ .$


Can somebody please tell me the solution to the following (easy suppose) problem:
Let n=p*q and let we know an integer "a" such that (p-1)|a but NOT (q-1)|a. Show how we can find factors of n.

Thanks

Take a random $x \bmod n$ and consider $x^a-1 \bmod n$.


Hey guys, I am now entering my sophomore year of High School in Stuyvesant High School (NYC) and I need a plan for when school starts in the Fall. I have little to no knowledge about college, and I got off to a horrible start here (80 average first semester). However, I've been working A LOT harder and I managed to break a 90 average the 2nd semester, with an 85 overall average. I aspire (like everyone else) to attend an ivy league.
I need to know, in my remaining 3 years here. What can I do to maximize my chances for admisson to these schools? I also understand colleges look at the percentile in which you graduate in. Will this hurt my chances for admission badly? Most students here DO attend ivy leagued schools, and thats the biggest problem. I need to stick out, but how? I need a plan.

You definitely are sticking out by going on AoPS.

Just do what you love and love what you do (this quote is by Richard Rusczyk, the founder of AoPS).

It's true that colleges ask your school for your class rank, but I don't think Stuy ranks its students.

Decide what you're passionate about and actively participate in clubs and jobs that support those interests.

Research colleges, not so that you know what to say to them or to find out what kind of people they look for, but to see if they offer what you need. Then you can show that you fit, and you'll actually be happy where you end up.

Also, talk with your teachers and counselors. They'll give you information, and more importantly, they'll write your recommendations.

About my low GPA for freshmen year, do you think if I strived for a 95+ average my sophomore, jr, and senior year that it can overshadow the mere 80?

This is something you should ask your school's counselor(s) about.  They're the real experts on these things, and at a school like Stuy I would expect they're very good at what they do.

When you apply to college, you'll have 6 semester's worth of grades. If they see that you tripped up one semester and did well the following semesters, they'll give weight to the later semesters.

Look for ways to get involved in school organizations (based on what you're interested in), or considering doing your own personal projects. Also, don't sit on your bum over the summer -- go and look for interesting things to do. Taking classes over the summer is usually not the best use of your time. Look for interesting opportunities to work, volunteer, intern, do labwork, do research, etc. You can do some of these during the year, too.

Actually, I suggest you take a look at an actual college application form. You'll see things like employment history, extracurricular activities, awards and distinctions, and several other things.

Also, as you're going along, connect the dots in your head and justify to yourself what you're doing/planning. This will make it much easier for you to give a good interview, write an effective resume, write powerful essays, and, if you talk to your teachers, get good recommendations (that's another thing too -- look out for people you might want rec's from).

[quote="Mij"]Just do what you love and love what you do (this quote is by Richard Rusczyk, the founder of AoPS).[/quote]

He definitely got that from the Life is Good shirts :wink:


Mike Tyson's motorized boat must cross the river Vedea having the extremely large width of $30$ meters. We know that the speed of the boat compared to the water's speed (i mean the relative speed) is $v_s=10 \frac{m}{s}$; also, the river flows at $2 \frac{m}{s}$.

[b]a)[/b] Determine the absolute speed of the boat when the angle between the moving direction of the boat and the water flow is $\alpha$;

[b]b)[/b] How must the boat be oriented s.t. the crossing of the river is made on the shortest path; what's this distance? in what time is this done?

[b]c)[/b] How must the boat be oriented s.t. the crossing is made in the shortest time and what's the time?

i got confused when i read the solution in the book.. i want to see other solutions

Use vectors to represent the motion of the boat the water and the relative motion of the boat.
Try to solve it, you must get it.
If I had a scanner I would have given you the solution but it is too difficult to write it on computer.

b) for shortest distance cosider the perpendicular distance (only if the boat can go that way) or else try doing some maths.

c) for shortest time. Make the boat move perpendicularily by its own. The water may displace it but its velocity in the perpendcular direction is maximum in this case.

Hope you could understand.

Can you tell me your results? You don't need to write the whole solution.
(The solution from the book tells me that my answers are wrong.)

Math is math.

This means that once one models a problem with a mathmatical model, one can solve the mathmatical model, then translate the solution back into the world of the problem.

Problem A is simply a trig problem with the sides the speed of the boat (10 m/s) and the river flow (2 m/s) and an angle (alpha) between the two.  Forget the units, solve for the third side of the triangle, then remember the units.  QED

Problem B is similar.  The shortest path (measured relative to the banks, not the flowing river) is simply straight across the river.  One need to orient the boat with an angle upstream sufficient for the upstream component of the boat's movement to exactly offset the river flow (2 m/s).  This is also a trig problem.  Set the units and the river/boat aside for a while (you'll get back to it later).  The hypotnose of the right triangle is 10, one side is 2, solve for the other side.  Go back to the river/boat problem, restore the units m/s and the first part is QED.
     Part 2 of Problem B is tricky, one must use the component of the speed directed across the river to determine the time, and forget the part of the speed directed to keep the boat on course.  QED

Problem C is a conceptual problem.  Let's leave Mike and his boat behind (we'll be back).  Assume I am saving money for two things: say a new computer and some new clothes.  If I have a fixed income (allowance), how can I earn the computer the fastest?  (By putting all my allowance towards that and none towards the new clothes (or anything else)).  You may be thinking this is simple.  You're right and it is all you need to solve the physics problem.  If one assumes that the river banks are parallel one would like to direct all the boat's speed (spending all the displacement covered) towards reaching the other bank and none of the boat's speed (no displacement covered) towards fighting the current.  Head straight across the river.  Note that the time for crossing is independent of the river's speed.  That simply changes how far downriver one end up and the total speed relative to the river banks.

Hope this helps.

So anyway, the results are:

a) $\sqrt{104+40\cos\alpha}$ m/s.
b) Boat's direction is almost perpendicular to the river - the velocity vector is $(-2, 4\sqrt{6})$. The distance is 30 m and the time is $\frac{5\sqrt{6}}{4}$ s.
c) Perpendicular to the river, time 3 s.

if 10 m/s is the speed of the boat relative to the water, then wouldnt the answers to parts b and c be the same. I say this because I thought that the speed of the boat relative to the water would be the magnitude of the vector sum of the boat's velocity and the water's velocity. If 10 m/s is a constant, then it wouldnt matter which direction the boat was pointing in as long as the speed of the boat relative to the water points upward. This would simultaneously cause the boat to cross in the least time and in the shortest distance.

Not quite.

Let's slow down and think for a minute.  The boat moves relative to the water in which it is floating.  So the velocity of the boat relative to the water is the speed of the boat 10 m/s.  There is no need to consider the speed of the water (relative to the shore) unless one is interested in the boat's speed, direction or movement relative to the shore.

The shortest distance, relative to the shore is directly across the river, if possible (it is in this case).  (Shortest distance between two points (in this case a point and a line) is a straight line (in this case a line perpendictular to the line).

However, if one wanted the shortest time (think fuel consumption, traffic, passenger illness or leaking issues), one needs to have all the boats velocity (10 m/s) directed to cross the river and none of it directed to keep the boat from going down river.  One crosses in the shortest time, but ends up as far down the river as the water flows when crossing.  In modern times, it usually is important to land where the docking facility is so one usually tries to cross perpendicular to the river's banks.  However, if one needed to go relatively far down river after crossing to reach one's dock, the fastest crossing becomes a question again.  (The mighty Mississippi River might have such an issue, most smaller steams wouldn't have a need to cross then go down river.)

Anyway it used to be a bigger real concern than it is now. (If one is suddendly swimming and wants (or needs) to limit the time spend swimming to shore, this again becomes critical.  One might not have the ability to swim fast enought to reach the direct shore, no matter how long one swam.

An interesting question and a classical one.

oops, my definition of relative speed was wrong. i thought that the relative speed of the boat with respect to the water is the vector sum of the velocity of the boat and the velocity of the water. Thats why I believed that parts b and c are the same answer. Its actually that the vector sum of the relative velocity of the boat and the velocity of the water equal the absolute speed of the boat, right?


search
function
number theory unsolved
number theory

Let $x,y,z$ be positive integers s.t.

$xy=z^{2}+1$

then show that there are positive integers $a,b,c,d$ s.t. $x=a^{2}+b^{2}, y=c^{2}+d^{2}, z=ac+bd$


Oh the unspeakable burden of proof  :lol:

[quote="mdk"]one solution, (1,1).[/quote]

Strangely, I found that solution too. Well, you know what they say about great minds  :wink:

[quote="Phelpedo"]Find all positive integers $x,y$ such that $7^{x}-3^{y}=4$.[/quote]

I think this might have to deal with some sort of modular arithmetic.

And yeah, $(1,1)$ is obvious.

Mod 4 gives x and y are of the same parity.
Evenness leads to a contradiction.
For odd... ill leave someone else do that  :lol:

[quote="boxedexe"]This problem isn't that difficult.  Notice that $7^{x}-3^{y}=4=7-3$.  Then use Euler's Congruency Formula $a^{\varphi (m)}\equiv 1\pmod m, \gcd (a,m)=1$.[/quote]

There doesn't seem to be a convenient choice of $m$....?

[hide="partial solution"]Consider the equation mod 7. $-3^{y}\equiv4\mod7$, or $3^{y}\equiv3\mod7$. Thus, $3^{y}=3+7k$ for $k\in Z$. Substituting into the original equation, we have:
\begin{eqnarray*}7^{x}-3-7k&=&4\\ 7^{x}&=&7+7k \end{eqnarray*}
Now the question is just find all $k$ for which $7+7k$  is a power of 7 and $3+7k$ is a power of 3. From this it appears there are no other solutions, but I don't know how to prove it. Obviously, $k$ has to be a multiple of three. But other than that, I'm pretty stumped as to finding a general solution.[/hide]

[hide]
Suppose there's a solution other than (1,1). Then $y\geq 2$, so we get
\[7^{x}\equiv 4\pmod{9}\Rightarrow x\equiv 2\pmod{3}\]
Now we choose a mod that divides by $7^{3}-1$ but not $7-1$ (we need this to make good use of $x$ mod 3). 19 is the only possible choice. In this case, we get
\[3^{y}\equiv 4-49\equiv 12\pmod{19}\Rightarrow y\equiv 15\pmod{18}\]
(That last computation can be sped up by noting that if $3^{y}\equiv 12$, then $3^\frac{y-1}{2}\equiv \pm 2$). In particular, $y\equiv 6\pmod{9}$. Now look at $\frac{3^{9}-1}{3-1}=13\cdot 757$. That second factor happens to be prime, so hopefully we can avoid using such a big mod and try mod 13. Now letting $x=3k+2$, we get
\[5\equiv 7^{x}\equiv 10\cdot 5^{k}\pmod{13}\Rightarrow 5^{k}\equiv 7\pmod{13}\]
But $5^{k}$ must be one of $\pm 1,\pm 5$ mod 13 so we finally get a contradiction! Therefore (1,1) really is only solution.
[/hide]

[quote="scorpius119"][hide]
Suppose there's a solution other than (1,1). Then $y\geq 2$, so we get
\[7^{x}\equiv 4\pmod{9}\Rightarrow x\equiv 2\pmod{3}\]
Now we choose a mod that divides by $7^{3}-1$ but not $7-1$ (we need this to make good use of $x$ mod 3). 19 is the only possible choice. In this case, we get
\[\boxed{\boxed{3^{y}\equiv 4-49}}\equiv 12\pmod{19}\Rightarrow y\equiv 15\pmod{18}\]
(That last computation can be sped up by noting that if $3^{y}\equiv 12$, then $3^\frac{y-1}{2}\equiv \pm 2$). In particular, $y\equiv 6\pmod{9}$. Now look at $\frac{3^{9}-1}{3-1}=13\cdot 757$. That second factor happens to be prime, so hopefully we can avoid using such a big mod and try mod 13. Now letting $x=3k+2$, we get
\[5\equiv 7^{x}\equiv 10\cdot 5^{k}\pmod{13}\Rightarrow 5^{k}\equiv 7\pmod{13}\]
But $5^{k}$ must be one of $\pm 1,\pm 5$ mod 13 so we finally get a contradiction! Therefore (1,1) really is only solution.
[/hide][/quote]
[hide="Okay, I quoted your whole post but look at the double boxed part"]
I believe it should be
\[3^{y}\equiv 7^{x}-4\equiv 49-4\equiv 45 \mod{19}\]
(don't reduce the $45$ yet) and a different solution follows. Indeed,
\[3^{y-2}\equiv 5\mod{19}\implies 3^{y-3}\equiv 8\mod{19}\implies 3^{y-4}\equiv 9\mod{19}\implies y\equiv 6\mod{18}\implies y\equiv 3\mod{9}\]
So consider:
\[7^{x}-3^{y}\equiv 4\mod{13}\implies 49(7^{3})^{k}-27(3^{9})^{m}\equiv-3(5)^{k}-1\equiv 4 \mod{13}\]
Or
\[5^{k}\equiv 7\mod{13}\]
which,interestingly, finishes exactly the same as yours!!! (Because $y$ still satisfies $3|y$, $9\not|y$)[/hide]

[quote="Phelpedo"]Find all positive integers $ x,y$ such that $ 7^{x} \minus{} 3^{y} \equal{} 4$.[/quote]
Sorry to revive an old topic, but here is an alternate solution to this problem that has not been mentioned yet (at first, it will look like [b]scorpius119[/b]'s solution, but the end is different):
[hide="Solution"]
Clearly, if any of $ x$ or $ y$ is equal to $ 1$, then we get the solution $ (x,y) \equal{} 1$.  Now, if $ x,y\ge 2$, then look at the equation $ \bmod 9$.  Thus, $ 7^x \minus{} 3^y\equiv 4\bmod 9\implies 7^x\equiv 4\bmod 9\implies x\equiv 2\bmod 3$.  Now, look at the equation $ \bmod 7$.  This gives that
\[ 7^x \minus{} 3^y\equiv 4\equiv \minus{} 3\bmod 7\implies 3^y\equiv 3\bmod 7\implies 3^{y \minus{} 1}\equiv 1\bmod 7\implies y \minus{} 1\equiv 0\bmod 6\implies y\equiv 1\bmod 6\implies y\equiv 1\bmod 3
\]
Let $ y \equal{} 3k \plus{} 1$.  Now, look at the equation $ \bmod 13$ (notice that $ 3^3\equiv 1\bmod 13$).  Thus, we have that
\[ 7^x \minus{} 3^y\equiv 4\bmod 13\implies 7^x \minus{} 3^{3k}\cdot 3\equiv 4\bmod 13\implies 7^x \minus{} 3\equiv 4\bmod 13\implies 7^x\equiv 7\bmod 13\implies 7^{x \minus{} 1}\equiv 1\bmod 13\implies x \minus{} 1\equiv 0\bmod 12\implies x \minus{} 1\equiv 0\bmod 3\implies x\equiv 1\bmod 3
\]
This is a contradiction since we earlier said that $ x\equiv 2\bmod 3$.  Hence, the only solution is $ (x,y) \equal{} \boxed{(1,1)}$. [/hide]

EDIT to [b]Fraenkel[/b]: If $ y\ge 2$, then $ 3^y\equiv 0\bmod 9$, so $ 4\equiv 7^x \minus{} 3^y\equiv 7^x \minus{} 0\equiv 7^x\bmod 9$.

[quote="Fraenkel"]$ (4 \plus{} 3)^x \minus{} 3^y \equal{} \sum_{i \equal{} 0}^{x}{4^i3^{x \minus{} 1}} \minus{} 3^y$[/quote]

Unfortunately, this should be $ \sum_{i \equal{} 0}^{x} {x \choose i} 4^i 3^{x \minus{} i}$.

Edit:  You also can't assume that $ 4a \plus{} b \equal{} 4c \plus{} d \implies a \equal{} c, b \equal{} d$.


The Waterloo Seminar is now officially over  :( , although some people are still getting home as I am posting this  :pilot: .

To avoid making the previous thread even longer, let us create new threads for discussions and keep them at reasonable lengths.

I will upload some photos after I take care of some other things. I know that a lot of the participants have also taken pictures. It would be nice if we could share them (unfortunately, we cannot upload many pictures onto AoPS-MathLinks. One alternative is to use some other site, such as Yahoo! Photos, and link there).

... i just got back from the seminar, i'll be posting pictures soon :roll: .... seeing the pictures at this time makes me even sadder

maybe we should have one place to upload all our pictures???

[quote="Elyot"]YAY!  Seminar was so sweet.  I'm missing people already.  Definitely the best math camp I've ever been to.  Lectures were OK, problem sets were fun, but best of all was doing all kinds of fun crap with you people.  Great times were had by many.  I'll write a bit more when I'm less tired.

For transferring files, we can try yousendit.com, although it only stores your files for 7 days (and a limited # of downloads until the sender has to upload it again).  Just go to the site, enter your own email address, and copy-paste the link it gives you.

Here's the pseudo tee logo:

[url=http://s47.yousendit.com/d.aspx?id=2SOC9SOLSQN4C2DI2D70D8RKNF]http://s47.yousendit.com/d.aspx?id=2SOC9SOLSQN4C2DI2D70D8RKNF[/url]

Most people upload 2 or 3 times to increase the # of downloads available.  If this one runs out, I'll upload again.[/quote]

Heh, don't forget getting into crap too, lol.  Good times...

We were thinking that we should set up a wiki site...cuz those have been the best ones do far.  Maybe more on this later if I have time...

Blah miss camp.

if u guys havent heard someone set up an msn groups site:

http://groups.msn.com/WaterlooSeminar2005/_whatsnew.msnw

I've uploaded my photos [url=http://photos.yahoo.com/z_yufei]here[/url]. Enjoy!

Hi. I'm back!
This year's seminar was great. :)  There are a few things that many people wanted to see from my so called "bible".
[quote="8th Army"]Seminar was so good
Mau, 24, Connect 4, Mafia....so fun and involves tons of brain exercise...[/quote]
By the way, the game is not Mau. It's Mao.

[b]My Mao rules[/b]
Only 6 out of 15 rules were used this year due to lack of Mao games :( .

[hide="Balancing Line"]After A, 2, or 3 is played, next, second next, or third next person to play need to say "balancing line"(no one got this one since it was a short game).[/hide]

[hide="I do not get it"]If you enforce a rule to someone beside you, you need to say "I don't get it"(Only Brandon got this one. Others were so confused by this rule).[/hide]

[hide="Happy Birthday!"]If three consecutive cards with same parity is played, you need to say "Happy Birthday"(No one got this one, even though the rule seemed to be simple and played for long time).[/hide]

[hide="For left-handers"]You need to play 6 with left hand(Another rule with short time. No one got it).[/hide]

[hide="No longer spades"]By playing 9 or 10, you change the spade rule with the suit of the card you played(I'm quite sure that no one got it, even though most of the people played correctly).[/hide]

[hide="fourteen of stars"]Adding fourteen of stars. Easy to get the rule.[/hide]

[b]Mafia probability table[/b]
My former mafia table only went up to 15 people, but this table shows up to 25. I'll try to put the table with the inspector soon.

[hide="the table"]Probability that mafia win without inspector
# of mafia	  1	  2	  3	  4	  5
____________________________________________________
3 players	66.7%
5 players	53.3%	86.7%
7 players	45.7%	77.1%	94.3%
9 players	40.6%	70.2%	88.6%	97.5%
11 players	36.9%	64.8%	83.5%	94.2%	98.8%
13 players	34.1%	60.5%	79.2%	90.9%	97.1%
15 players	31.8%	57.0%	75.5%	87.8%	95.0%
17 players	30.0%	54.0%	72.2%	84.9%	92.9%
19 players	28.4%	51.5%	69.3%	82.2%	90.8%
21 players	27.0%	49.3%	66.8%	79.8%	88.8%
23 players	25.9%	47.4%	64.5%	77.5%	86.8%
25 players	24.8%	45.6%	62.4%	75.4%	85.0%[/hide]

[b]Make 24[/b]
I have posted both the list of impossible cases and the program to generate the list. You can find it [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=38886]here[/url]

[quote="Sunny"]Heh, did anyone figure out my "I tought I taw a Putty tat!"   "I did, i did, I did see a putty tat!"

I never got to use my hippo rule...oh well, I'll save it.[/quote]
So that's what it was. No wonder I couldn't pronounce them well. :D

[quote="lightrhee"]
So that's what it was. No wonder I couldn't pronounce them well. :D[/quote]

Lol, watching you and alan say "I thought i saw a pretty cat" was amusing though.  Still, how can you have never seen looney tunes?!?!?!?!

I found [url=http://rec-puzzles.org/new/sol.pl/competition/games/connect.four]this[/url], which tells me that first player of 'connect 4' have a winning strategy.

Apparently, this was solved by building an AI and the AI found the winning strategy. :D

I actually read the full 92-page Master's Thesis.  It was quite interesting.  The coolest thing was to actually read the rules by which you can play to win or draw in most game situations... from then, they just had to code a computer to solve for the opening book.

[quote="lightrhee"][quote="Elyot"]I actually read the full 92-page Master's Thesis.  It was quite interesting.[/quote]
 :o You were reading 92-page-long-thesis? Wow.

BTW, how come you are so good at  :ddr: ? How much did you practice?[/quote]

WOW, there's a DDR emoticon!   It's sooooo cool...i'm so surprised :D

[quote="Elyot"]Where do you live?  If you write Fermat and you're say, provincial champion of Nova Scotia, then you can score yourself a really easy invitation.  If you live in Toronto, then it's a lot tougher.[/quote]

argh yea i kno....i beat like pei and manitoba and saskatchewan and all those place this year...but those damn dmci people stole my $200!! grrr....it sucks livin in toronto

[quote="d.lam.86"][quote="chann23"][quote="Elyot"]Where do you live?  If you write Fermat and you're say, provincial champion of Nova Scotia, then you can score yourself a really easy invitation.  If you live in Toronto, then it's a lot tougher.[/quote]

argh yea i kno....i beat like pei and manitoba and saskatchewan and all those place this year...but those - dmci people stole my $200!! grrr....it sucks livin in toronto[/quote]
I think otherwise. The reality is that living in a populated city full of brilliant minds only makes us strive to be better. Once reaching that success, it feels great that you've accomplished a lot compared to the wide spectrum of minds in Toronto.[/quote]

So true.

[quote="Sunny"][quote="d.lam.86"]D`oh; I live in Toronto so yeah, it's a mission impossible!  :ninja: I doubt my enriched math teacher will let me skip a grade.  :roll:  :blush: It's practically impossible for me.[/quote]

I honestly think skipping a grade will have no difference whatsoever on your mark.  This isn't high school math, they generally won't teach you how to write a math contest.[/quote]

That reminds me of a funny question I've always thought about.

Does the USA curriculum teach their students about problem solving?  :huh:

[quote="d.lam.86"][quote="kool_dudy"]

That reminds me of a funny question I've always thought about.

Does the USA curriculum teach their students about problem solving?  :huh:[/quote]
I heard a rumour that education in the U.S. has been on a downslide ever since the Bush government. Anyone care to justify?  :huh:[/quote]
PM Bubala. He should know. :rotfl:

HEY!!!!!!!

PAUL FINALLY GOT ME ALL THE VIDEOS!!!!

Altogether, they are HUGE.  So I'm not sure what to do with them.

Sadly, the one video of the actual event is way too dark, only would make sense if you were there.  But a lot of the others are hilarious.

ANy ideas?

Haha, Paul is hilarious..Neways, how big are they?  I'm pretty sure you can still upload them onto the MSN groups thingy.  :)

Bleh I know nothing about this.  Right now they're all zipped together, and there are a lot of videos...at least 8.

102MB

The MSN site will let me upload 3MB.  Heh

Try uploading a few times to http://www.yousendit.com and sending us the link they put in the email message.

You could try editing the videos a little... brightening stuff up is easy in programs like premiere... idunno what you've got on your set, but maybe there's something that will allow you to improve the quality of the movie a little.

What's going on? I'm confused.  :? A whole new topic just errupted out of nowhere. Fill me in?  :)

[quote="Sunny"]awesomeness.  After an hour of waiting, they're up,

http://s20.yousendit.com/d.aspx?id=0RLF6SDYFNBT70O68U90GKLBGY

When you open it, view in order by number...enjoy.[/quote]
awesomeNESS...  :roll: (just kidding)  :lol:


AMC
USA(J)MO
USAMO
trigonometry
geometry
graph theory

About how long does it take for students to get their scores and (possible) MOSP invitations?  I'm getting anxious already and grading probably hasn't even started yet.... :P

As it is written in the teacher's manual which u can find on amc website, grading takes place on april 22-24. The results are mailed on may 3, but they notify u by phone if you made it to mosp and stuff or not. It won't take too long

Did anyone read the S-I letter? ;)
It says MOSP participants will be notified by phone, shortly after the grading of the USAMO, on April 21, 22, and 23.

[quote="tcs09"]Did anyone read the S-I letter? ;)
[/quote]

I'll bet this puts a smile on Prof. Dunbar's face :)

Does any body know how many graders there are workingat the same time?  Also, does each test paper only get graded once or is it checked twice or thrice by others?

From the pictures, it looks like they are discussed. I just hope the graders are in a good (meaning generous) mood when they come to my paper.

hm... i'm amazed they're graded so fast if they are discussed.

They probably don't sleep or eat during those days -- just sit there around a table and discuss :lol:

[quote="MCrawford"][quote="mna851"]Wow thats amazingly quick.  They are going to grade 430 USAMO papers which can consist of at most 6 full length proofs in 2-3 days.[/quote]

I know.  I'm growing suspicious that they're hogging the only functional time machine.[/quote]
 :rotfl: Maybe
I think what really happens is initially they have like 50 graders who represent "the 1st round" where they mark the solutions according to the scheme. the papers out of contention of hon men are left out, the rest(about 30-40) are given to the smart markers for round 2. there they discuss the solutions and decide on tiebrakers.

If it takes 15 minutes to grade a problem, and the average USAMOer answers 1 problem out of 6, then we're already up to 15*1*430/(60*24) = 4 days... wow. (of course, that's if  they're discussed)

EDIT: Woah, I just noticed that April 22-24 includes a weekend... thank you graders for taking your weekend to grade our paper!

[quote="probability1.01"]Considering there are a lot of graders, it should take much less than 15 minutes per problem over the entire group. I'm sorry nr1337, but looks like your proof for 4 days gets a 0 :D.[/quote]

Depending on the handwriting, however, it may take much longer.... :) (*cough cough mine cough cough*)
How could my proof get a 0... there wasn't even enough information in the problem!

Is anyone else getting really really really excited...?

[quote="rrusczyk"]I think the number of graders is closer to 20.

As for those 'thank yous', I suggest sending one to the staff at Lincoln - a few of them pull something near an all-nighter to get the papers ready to send to Boston for grading this weekend.

The grading, I imagine, is great fun.[/quote]

Heh, sounds like my english teacher, he's very reliable, pulls an all-nighter if he has to.

As for AMC...

THANKYOU  :lol:  :heli:  :thumbup:

Eh let's hope one of those many graders notices that I did all the hard work and just messed up at the end on problem 1  :roll:

[quote="rem"]It would be nice to be a marker. You get to laugh at funny solutions and decide the fate of some of the contestants(*that's relatively deep :rotfl: *")[/quote]

lol
On my last proof #6, I thought I proved it, but then noticed a serious flaw which...destroyed it......so i ended saying something like that "I just proved that my proof was very flawed and wrong".

[quote="rem"][quote="filletwho"]The graders will be happy when they see my papers...all blank...[/quote]
When you are really desperate and you know you won't solve a problem, draw some funny picture or write a joke or a ridiculous solution -- you got nothing to lose, but it's funny.[/quote]
Like my entire #6?
"Therefore, my claim follows. Q.E.D."
Someone else: "Shouldn't it be, 'therefore, [i]your[/i] claim follows?'"?

Also, I personally know of two people who didn't even bother to show up for the USAMO this year... so yeah...

[quote="rem"][quote="filletwho"]The graders will be happy when they see my papers...all blank...[/quote]
When you are really desperate and you know you won't solve a problem, draw some funny picture or write a joke or a ridiculous solution -- you got nothing to lose, but it's funny.[/quote]

Well...nothing to gain either.  :lol:

[quote="rem"]When you are really desperate and you know you won't solve a problem, draw some funny picture or write a joke or a ridiculous solution -- you got nothing to lose, but it's funny.[/quote]
If you do that on a MOP test, you may achieve the coveted 0/1.0 score. 1.0 style scores are rare, but it's a little easier to get one when you know the math is wrong.
(For points purposes, the math and style scores are multiplied)

[quote="rem"][quote="filletwho"]The graders will be happy when they see my papers...all blank...[/quote]
When you are really desperate and you know you won't solve a problem, draw some funny picture or write a joke or a ridiculous solution -- you got nothing to lose, but it's funny.[/quote]

Yeah, I hope thay haven't already heard about the one with the blonde, the brunette, and redhead in a bar...  :P

[quote="rem"][quote="filletwho"]The graders will be happy when they see my papers...all blank...[/quote]
When you are really desperate and you know you won't solve a problem, draw some funny picture or write a joke or a ridiculous solution -- you got nothing to lose, but it's funny.[/quote]

Heh, someone I know at school told me to write something like:

[quote] Dear Sir or Madam,

Please have mercy and give me one point on this problem.

Signed, Yours Truly, USAMO Participant[/quote]

Especially the dear sir or madam and write a letter part lol

When in doubt, follow the advice of this person...
http://www.acad.sunytccc.edu/instruct/sbrown/pic/miracle.jpg

[quote="MCrawford"][quote="mna851"]Wow thats amazingly quick.  They are going to grade 430 USAMO papers which can consist of at most 6 full length proofs in 2-3 days.[/quote]

I know.  I'm growing suspicious that they're hogging the only functional time machine.[/quote]

As a WOOT grader, I can appreciate firsthand the challenge of grading olympiads. Even though mathematics generally boils down to "rigorous or not rigorous", there really is a surprising degree of flexibility so far as writing style. And 2000+ proofs is a lot!

[quote="calc rulz"]
Heh, sounds like my english teacher, he's very reliable, pulls an all-nighter if he has to.

As for AMC...

THANKYOU  :lol:  :heli:  :thumbup:

Eh let's hope one of those many graders notices that I did all the hard work and just messed up at the end on problem 1  :roll:[/quote]

Yeah, my english teacher works on our english papers late into the night as well.  It makes sense though...to get a degree in english you're inevitably going to spend much of the middle of night on writing for many of your nights.

Err...sorry for going off topic  :oops:

[quote="probability1.01"]On MOP tests, sometimes you can draw random pictures and assume you know how to do arithmetic. However, in these cases you are prone to getting OWNED by graders (like Tiankai).  :blush:[/quote]

[hide="Get owned enough times, and you might get a free eraser!"]
(reference to the worst-style-point-average prizes)[/hide]

[quote="Phelpedo"][quote="nirvanatear"][quote="jackb1115"]In my proof for #1, I arranged the possible values of the fractional parts in a circle, and then was like "let's imagine we have a bunny hopping around the circle in intervals of s/p."  And I proved the thing to.

I hope they take that as a "proof," even though it wasn't really ... conventional.  The reasoning is sound, but I'm sure it's not something they are used to seeing.

Oh well, if nothing else it will make the grader smile.  And, as one of my friends put it, I win "Kick A--" points.

JB[/quote]
hey
thats exactly how my friend did it..
he said he used trig but i didnt find this question provable by trig..[/quote]

Well this solution is certainly "original." You might win the originality award if it's correct.[/quote]
all the questions require originality.
i have never seen olympiad questions b4, all of them seem unsolvable to me..

[quote="probability1.01"][quote="Phelpedo"][quote="probability1.01"]Too bad there is no "originality" award :P. Anyway unfortunately I could not do any such thing on my proofs, since I basically didn't have any extra time :(.[/quote]

Isn't there the Clay Mathematics award, presented to the person with the most original solution to a problem?[/quote]

Haha, they're not going to give that for bunnies ;). But that gives me an idea... maybe MOP could have a "Mud Mathematics Award" for complete solutions that have the most sheer awesomeness elements (like lemons).[/quote]

That would consequently generate so much absurdity that the graders would go insane :)

I think Clay actually has potential this year (unlike last year where it went to a Geo problem ... come on). Problem 5 looks like it might have some pretty creative solutions.

[quote="darktreb"]I think Clay actually has potential this year (unlike last year where it went to a Geo problem ... come on). Problem 5 looks like it might have some pretty creative solutions.[/quote]

What's with this attitude of yours towards geometry? :(  :(  :(

And come on, you gotta admit, Sherry's solution was original ... how often do you see someone use continuity to solve a classical Euclidean geometry problem

Speaking of originality, on another olympiad test today, I inducted on the number of holy grails. Later, I changed it to the number of grails, since I needed a special type of grail to be holy. Yeah, it was a graph theory problem. :D

*another* olympiad test?!

hmm, I was going to ask for sherry's solution, but I decided to use google instead

for other people who don't want to take the trouble, though, I found it here: http://www.claymath.org/news/sgong2.pdf

Yeah, the Colorado Math Olympiad, in Colorado Springs. I know, I must be crazy to take 13 hours of olympiad tests in four days...but it was fun, and I did much better on that one than on the USAMO.

maybe they only have a few people grading. Because the expand this year, the grading time will be longer. maybe till next wednesday or Friday. see
http://www.maa.org/ecomtpro/members/committees/index.cfm?step=2&cou_num=00303628&cou_name=Competitions&com_num=00303636&com_name=Subcommittee%20for%20the%20United%20States%20Mathematical%20Olympiad

maybe only these people are grading.


logarithms
trigonometry
function
AoPSwiki
trig identities

Well I hope you ordered AoPS vol 2, since in the beginning, they go over logarithms and trig identities very well.

But other than that, you can take a look at the AoPSWiki or the MathWorld articles.

thank you (yes, volume 1+2 were the first ones i put on the list)

where is mathworld? (sry if im being a noob ;-) )

[quote="e=mc2.kroll"]are there any real good books on trig functions and/or logarithmical properties?

besides the aops ones (my copies havent arrived yet -.- )

any internet resources would be helpful, too.[/quote]

just go get an algebra 2 book it explains it very well

[quote="e=mc2.kroll"]are there any real good books on trig functions and/or logarithmical properties?

besides the aops ones (my copies havent arrived yet -.- )

any internet resources would be helpful, too.[/quote]

Volume 1 is a really good book if you do not know anything about logs, or trig. Volume 2 is good if you have gotten good at using them.


analytic geometry
linear algebra
matrix
function
trigonometry
algebra
polynomial

There are four identical objects with masses m between two walls.Theyare attached to each other and to the walls by 5 identical springs with spring constant k.Find the frequencies of oscilation.

I think I get it.. they are in one line right?

Then here it goes:
Let the coordinates of the masses be: $ x_1$, $ x_2$, $ x_3$ and $ x_4$, let the positive direction be to the right.

Then the equations of motion:

$ m\ddot x_1 =-kx_1 +k(x_2-x_1)$

$ m\ddot x_2 =k(x_1-x_2)+k(x_3-x_2)$

$ m\ddot x_3 =k(x_2-x_3)+k(x_4-x_3)$

$ m\ddot x_4 =k(x_3-x_4)-kx_4$

Where $ k$ is the spring constant.
Lets use the following substitution: $ \omega_0^2=\frac{k}{m}$

Now using matrix notation, we get:
$ \begin{pmatrix} \ddot x_1 \\ \ddot x_2 \\ \ddot x_3 \\ \ddot x_4 \end{pmatrix}   =-\omega_0^2  \begin{pmatrix} 2 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \end{pmatrix} \cdot \begin{pmatrix}  x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}$

Now let:
 $ u =\begin{pmatrix}  x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}$ and $ B= \begin{pmatrix} 2 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 2 \end{pmatrix}$

Then our equation:

$ \ddot u = -\omega_0^2 B \cdot u$

Now lets look for the solution in the: $ u=a e^{-i\omega t}$ form, here $ a$ are the normal moduses.

Then we have:
$ -a \omega^2 e^{-i\omega t} = -\omega_0^2 B \cdot a e^{-i\omega t}$

That is:

$ B\cdot a =\frac{\omega^2}{\omega_0^2} a$

So we see that $ a$ is an eigenvector of $ B$ and $ \lambda=\frac{\omega^2}{\omega_0^2}$ is the eigenvalue.

So then the eigenfrequencies of the system are:

$ \omega_l = \omega_0 \sqrt{\lambda_l}$

from here its just calculation.
Solve the eigenvalue problem of the $ B$ matrix and you are done.

You can also give the time functions of the balls, with given initial conditions by solving the differential equations.

Here is a method to do that:

We have the $ \omega_l = \omega_0 \sqrt{\lambda_l}$ eigenfrequencies. now lets look for $ u(t)$ in the following form:

$ u(t)= \sum_l a^l (A_l \cos {\omega_l t} + C_l \sin{\omega_l t})$
Here $ a^l$ is the $ l$-th normalmodus
and
$ \dot u (t) = \sum_l a^l (-\omega _l A_l \sin {\omega_l t} + \omega_l C_l \cos{\omega_l t})$

now the initial conditions:

$ u(0)=u_0 = \sum_l a^l A_l$ now lets multiply this by the left  eigenvectors $ b^m$ of $ B$. and use that $ a^l \cdot b^m = \delta_{lm}$ here $ \delta_{lm}$ is kroneckers delta.
So then, we get the $ A_l$ coefficents: $ A_l =u_0 b^l$

Similarly for the other initial condition:

$ \dot u(0) = v_0 = \sum_l a^l C_l \omega_l$, so from here :

$ C_l \cdot \omega_l = b^l v_0$
So the solution:

$ u(t)=\sum_l \left ( b^l u_0 \cos{\omega_l t} + b^l v_0 \frac{\sin{\omega_l t}}{\omega_l} \right )$

So you just have to solve the full eigenvalue problem of $ B$. That is find the $ \lambda_l$ eigenvalues, $ a^l$ right eigenvectors, and $ b^l$ left eigenvectors.

It is interesting that this can be generalised, and we can derive the wave equation from it. For The determinant of the "eigenmatrix" we get a second order recursion and the solution will be the Chebisev polynomials, and from here using a few limits we get it. if someone is interested I can show it. just post a reply...

Isn't that the wave equation for the phonon?
I really want to see it 'cause people told me I'll be able to better understand wave-particle duality with this. I would have tried it myself, but I don't know much Linear Algebra.

So lets put $ N$ masses next two each other and connect them with spring, with spring constants $ k$.  Let the distance between two masses when in equilibrium be $ a$.
Let the total mass be $ Nm \equal{} M$, and the total "length" of the system be: $ Na \equal{} L$.
Now we take the folloing limits:
$ N\to \infty$
$ m\to 0$ ,$ M \equal{}$ const. (THe mass of the system be constant)
$ a\to 0$ , $ L \equal{}$  const.
$ k\to \infty$, and $ \frac {k}{N} \equal{} \phi \equal{}$const.

So now as above let's write the equation of motion of the $ l$-th mass:

$ m\ddot u_l \equal{} k(u_{l \minus{} 1} \minus{} u_l) \plus{} k(u_{l \plus{} 1} \minus{} u_l)$

Now using the above notation, and making a few adjustments:

$ \frac {M}{N} \ddot u_l \equal{} k\left (\frac {L}{N} \right )^2 \left (\cfrac{\frac {u_{l \plus{} 1} \minus{} u_l}{a} \minus{} \frac {u_l \minus{} u_{l \minus{} 1}}{a}}{a} \right )$

So here we have:
$ \ddot u_l \equal{} k \frac {N}{M}\left (\frac {L}{N} \right )^2\left (\cfrac{\frac {u_{l \plus{} 1} \minus{} u_l}{a} \minus{} \frac {u_l \minus{} u_{l \minus{} 1}}{a}}{a} \right )$

Now using some more substitutions:
Let: $ c^2 \equal{} k \frac {N}{M}\left (\frac {L}{N} \right )^2 \equal{} \frac {\phi L^2}{M}$

So our equation:

$ \ddot u_l(t) \equal{} c^2 \left (\cfrac{\frac {u_{l \plus{} 1} \minus{} u_l}{a} \minus{} \frac {u_l \minus{} u_{l \minus{} 1}}{a}}{a} \right )$

Now let's use a few limits:

We have:
 if $ a\to 0$, then:
$ u(x,t) \equal{} \lim u_l(t)$

And: $ \frac {\partial u}{\partial x} \equal{} \lim \frac {u_l(t) \minus{} u_{l \minus{} 1}(t)}{a}$

Hence we get from our equation above:

$ \frac {\partial^2 u(x,t)}{\partial t^2} \equal{} c^2 \frac {\partial^2 u(x,t)}{\partial x^2}$

Which is a wave equation.

Thanks a lot.
Let $ u(x,t)$ be a solution of this equation,
The total energy in the system is given by $ U\equal{}\frac{1}{2}\int_0^L ku(x,t)^2 dx$.
Now if we put the boundary conditions $ u(x,t)\equal{}0$ $ \forall$ $ x\leq 0$ and $ x\geq L$, we should get certain discrete solutions for $ u(x,t)$.
How do we calculate these solutions and thier energy?

So our equation is:
\[ \frac {\partial^2u}{\partial t^2} \equal{} c^2\frac {\partial^2 u}{\partial x^2}
\]
The boundary conditions you said are: $ u(0,t) \equal{} u(L,t) \equal{} 0$

I will show Daniel Bernoulli's solution to the differential equation.

Let's look for the $ u(x,t)$ function as the product of two functions, out of which one is a function of only $ x$ the other is of only $ t$:
\[ u(x,t) \equal{} X(x)T(t)
\]
If this function is a solution of the equation, then we should get an equality.
Now lets calculate the partial derivatives:
\[ \frac {\partial u}{\partial x} \equal{} X'(x)T(t) \, \, \, ,\frac {\partial^2u}{\partial x^2} \equal{} X''(x)T(t)
\]

\[ \frac {\partial u}{\partial x} \equal{} X(x)T'(t) \, \, \, ,\frac {\partial^2u}{\partial x^2} \equal{} X(x)T''(t)
\]
Writing this in the equation:
\[ X(x)T''(t) \equal{} c^2X''(x)T(t)
\]
We can separate the variables, so:
\[ \frac {T''(t)}{T(t)} \equal{} c^2\frac {X''(x)}{X(x)}
\]
Now observing the above equation we see, that the left side is only a function of $ t$ and the right side is only a function of $ x$. For arbitrary $ t$ and $ x$ this can only be if, the right and left sides are both constant, and obviously then the same constant. Let this constant be $ \minus{} \alpha^2$. (we chose it in this form due to physical reasons)
So:
\[ \frac {T''(t)}{T(t)} \equal{} c^2\frac {X''(x)}{X(x)} \equal{} \minus{} \alpha^2
\]
Writing this in two separate equations:
\[ \frac {T''(t)}{T(t)} \equal{} \minus{} \alpha^2
\]

\[ c^2\frac {X''(x)}{X(x)} \equal{} \minus{} \alpha^2
\]
As we see with this method, we broke down the solution of our second order partial differential equations, to solving two ordinary second order homogenous differential equations. These are:
\[ T''(t) \plus{} \alpha^2 T(t) \equal{} 0
\]

\[ X''(x) \plus{} \frac {\alpha^2}{c^2} X(x)
\]
Everyone can solve these, so I will just write the solution, $ u(x,t)$
\[ u(x,t) \equal{} (A\cos{\alpha t} \plus{} B\sin{\alpha t})\left (C\cos{\frac {\alpha}{c}x} \plus{} D\sin{\frac {\alpha}{c}x} \right )
\]
Here $ A$, $ B$, $ C$, $ D$ and $ \alpha$ are constants. Now we only have to use the boundary and initial conditions to calculate them.

According to the $ u(0,t) \equal{} 0$ boundary condition:
\[ (A\cos{\alpha t} \plus{} B\sin{\alpha t})C \equal{} 0
\]
For arbitrary $ t$ this can only be if $ C \equal{} 0$.

According to the other $ u(L,t) \equal{} 0$ boundary condition:
\[ (A\cos{\alpha t} \plus{} B\sin{\alpha t})\left (D\sin{\frac {\alpha}{c}L} \right ) \equal{} 0
\]
Here $ D$ cannot be zero, since then the solution would be zero, since we already know that $ C \equal{} 0$, so we need that:
\[ \sin{\frac {\alpha}{c}L} \equal{} 0
\]
That is:
\[ \frac {\alpha L}{c} \equal{} k\pi \, \, \, \, \, (k \equal{} 1,2,3,\dots)
\]
From here:
\[ \alpha \equal{} \frac {kc\pi}{L}
\]
Since $ \alpha$ can take on infinite values, we can as well put an index for it:
\[ \alpha_k \equal{} \frac {kc\pi}{L}
\]
So now taking the boundary condition into account, our solution is:
\[ u_k(x,t) \equal{} (A_k\cos{\frac {kc\pi}{L} t} \plus{} B_k\sin{\frac {kc\pi}{L} t})D_k\sin{\frac {k\pi}{L}x}
\]
We wrote indices for the $ u$, $ A$, $ B$, $ C$, $ C$ constants also, because we have a solution for every $ k$. We know that the sum of the particular solutions of a homogenous differential equation is also a solution hence:
\[ U(x,t) \equal{} \displaystyle\sum_{k \equal{} 1}^{\infty}u_k(x,t) \equal{} \displaystyle\sum_{k \equal{} 1}^{\infty}(A_k\cos{\frac {kc\pi}{L} t} \plus{} B_k\sin{\frac {kc\pi}{L} t})D_k\sin{\frac {k\pi}{L}x}
\]
Is also a solution to the differential equation.

Let $ A_kD_k \equal{} E_k$ and $ B_kD_k \equal{} F_k$ now:
\[ U(x,t) \equal{} \displaystyle\sum_{k \equal{} 1}^{\infty} \left[E_k(\cos{\frac {kc\pi}{L}t})\left ( \sin{\frac {k\pi}{L}x} \right ) \plus{} F_k(\sin{\frac {kc\pi}{L}t})\left ( \sin{\frac {k\pi}{L}x} \right ) \right ]
\]
Now we need an initial condition. Let this be $ U(x,0) \equal{} f(x)$ here $ f(x)$ is some function.

Using this we get:
\[ \displaystyle\sum_{k \equal{} 1}^{\infty} E_k \sin{\frac {k\pi}{L}x} \equal{} f(x)
\]
We can get the $ E_k$ coefficients from the fourier series of the continuous $ f(x)$ function.

Let the other initial condition be $ U'(x,0) \equal{} g(x)$

Now lets differentiate $ U(x,t)$ with respect to $ t$:
\[ \frac {\partial U}{\partial t} \equal{} \displaystyle\sum_{k \equal{} 1}^{\infty} \left[ \minus{} (\frac {kc\pi}{L}E_k\sin{\frac {kc\pi}{L}t})\left ( \sin{\frac {k\pi}{L}x} \right ) \plus{} (\frac {kc\pi}{L}F_k\cos{\frac {kc\pi}{L}t})\left ( \sin{\frac {k\pi}{L}x} \right ) \right ]
\]
Now according to the above initial condition:
\[ \displaystyle\sum_{k \equal{} 1}^{\infty}\frac {kc\pi}{L}F_k\sin{\frac {k\pi}{L}x} \equal{} g(x)
\]
We can get the $ F_k$ similarly as before, from the Fourier series of $ g(x)$

Thus we solved it fully.

I hope all of it was clear :D

Thanks.

Is it always true that $ u(x,t)$ can be written as $ u(x,t)\equal{}X(x)(T(t)$?

I think I can work out the rest.

Sorry for the late reply :D

Here is my answer
For a mathematician NO, for a physicist YES. If you understand what I mean :wink:


(a) Prove that there is a convex hexagon with congruent angles and sides of lengths $1,2,3,4,5,6$ (not necessarily in this order).
(b) Prove that there are exactly two types of hexagon that fulfill the conditions in (a).

yes, the main idea, is that in an echiangular hexagon $ABCDEF$ we have the relation : $|AB-DE| = |BC-EF| = |CD-FA|$, and the conclusion follows for $1$ and $3$.

One (complicated) way to prove pohoatza's claim is the following:

Suppose that $A,B,C,D,E,F$ are written in counter-clockwise order and let $\omega = \cos \left( \frac{\pi}3 \right)+i \sin \left( \frac{\pi}3 \right)$.
If $a_{0}= AB, a_{1}= BC, a_{2}= CD, a_{3}= DE, a_{4}= EF, a_{5}= FA$, then
\[a_{0}+a_{1}\omega+a_{2}\omega^{2}+a_{3}\omega^{3}+a_{4}\omega^{4}+a_{5}\omega^{5}= 0 . \]
Hence, $\omega$ is the root of the real polynomial $P = a_{0}+a_{1}X+a_{2}X^{2}+a_{3}X^{3}+a_{4}X^{4}+a_{5}X^{5}$.
It's easy too see that the minimal polynomial of $\omega$ is $M = X^{2}-X+1$.
Hence, $M | P$, i.e. $P = MQ$, where $\deg Q = 3$.
Letting $Q = a X^{3}+b X^{2}+c X+d$, we get that
\[P = a X^{5}+(b-a) X^{4}+(a-b+c) X^{3}+(b-c+d) X^{2}+(c-d) X+d . \]
Hence, $a_{5}= a, \, a_{4}= b-a, \, a_{3}= a-b+c, \, a_{2}= b-c+d, \, a_{1}= c-d, \, a_{0}= d$.
Therefore, $\left| a_{3}-a_{0}\right| = \left| a_{4}-a_{1}\right| = \left| a_{5}-a_{2}\right| = \left| a-b+c-d \right|$.


Err...
How many regions are formed inside a regular octagon when all the diagonals are drawn?

Team round from somewhere xD... There's supposed to be a formula, but I'm really. lazy.

I think theres a formula like

x(x-3)/2 equals numbers of diagonals or something like that

I'm not that amazing at math..

dont know if that helps
  :maybe:

EDIT: I think the answer is 24,but there is probably some asian way to do it
JK

[hide]
there's 20 diagonals

so, think about it, try and find a pattern

3-sides 0 diagonals 1 region
4-sides 2 diagonals 4 regions
5-sides 5 diagonals 11 regions
6-sides 9 diagonals 24 regions

See a pattern?

Take the differences
1 region -0 regions=1
4 regions-1 region=3
11-4=7
24-11=13

so

1,3,7,13

If you look, it is +2,+4,+6... So, you add (8+13)+24 to get

45 regions for a 7-sided

and (21+10)+45 to get 76 regions for an octagon.

I'm not entirely sure if I'm right, but I'm pretty sure.[/hide]

[quote="mathcrazed"]That's wrong. I already tried that.[/quote]

And could you enlighten us on why that's wrong? Thanks :).

I don't know why it's wrong, but the answer is incorrect (according to my coach)...

when you draw all the long diagonals, they only intersect in 1 point in the center.  therefore there are only 8 regions for the long diagonals.... so you've overcounted

... There are more than 76 regions, so no, he hasn't.

Infinity4ever: you can count regions of overlap  :wink:

The formula for this is absolutely awful...look on Wolfram Mathworld under Regular Polygon Division.

[hide][url]http://www.math.rutgers.edu/~erowland/ngoncalculator.html[/url]

Going to that site gives the answer as 80.....[/hide]
if you look at regions formed by regular polygons........
Triangle = 0
Square = 4
Pentagon = 11
Hexagon = 24
Septagon = 50
Octagon = 80
Nonagon = 154
Decagon = 220
11 - gon (forgot name) = 375
Dodecagon = 444

I don't see a pattern at all, but I just wanted to put that out there. I checked out mathworld, and it didn't make much sense....


The problem makes absolutely no sense.  What is $x$?  And how is $f$ defined at points other than $104^{3}$?

Where is the problem from?  It's nonsense.

If the whole equation is linear, it would work.[/hide]

yes but perhaps the 11,3,&2 are gotten by doing something to 104^3?!

this problem is from the Vestavia 2005 Alg I test

Do you have a copy of it?  How should the problem read?

Well if it 104x^3, then x=1/2, then hence plug in x=1/2 into your equation and you get your answer.

Do you have links to these questions?


calculus
integration
calculus computations

Solve:
\[ \frac{1}{2}f''\equal{}f^3\minus{}f,\; f(0)\equal{}f'(\infty)\equal{}0\]

It can be reduced to the following integral:

\[ \int \frac{df}{\sqrt{f^4\minus{}2f^2\plus{}C_1}}\equal{}x\]

$ C_1$ is an integration constant.

Using the initial conditions, the elliptic integral, arising can be averted...


search
combinatorics unsolved
combinatorics

Initially numbers from 1 to 1000000 are all colored black. A move consists of picking one number, then change the color (black to white or white to black) of itself and all other numbers NOT coprime with the chosen number. Can all numbers become white after finite numbers of moves?

Edited by pbornsztein

[quote="anand.oza"]Isn't the answer "yes", because you can pick a large prime (so that there are no multiples of it in the given range), and thus change every number to white?[/quote]

My bad, should read all other numbers NOT coprime with the chosen number :blush:

Moderators, could you let me edit the original post? Put "not" before "coprime".

It is a particular case of a more general result which states that for any finite simple graph there is a set $ S$ of vertices such that any vertex of the graph is connected to an odd number of vertices in $ S$.
Have a look here :
http://www.mathlinks.ro/Forum/viewtopic.php?search_id=1313015583&t=5976

I think this problem is also discussed in this thread.

Pierre.