[hide]Let segments PD, PE and PF be perpendicular to AB, BC and CA respectively, where points D,E and F lie on the sides of the triangle. One of the segments PD, PE and PF is the smallest distance from point P to a side of the triangle, while one of the segments PA, PB and PC is the longest.

If angle PCF  :le: 30 degrees, than sin(PCF)*PC = PF  :le: (0.5)(PC) and we are done. (So long as any one of the three possible smallest segments is less than half of any one of the possible longest three, the proof is complete.)  The same argument can be applied to angle PCE and segment PE, so the proof is complete if angle BCA :le:60 degrees.

Let's look at the case where angle BCA > 60 degrees. Angles PFC and PEC are right angles, so angle EPF < 120 degrees.

Now if angle PAD :le: 30 degrees, then PD is less than or equal to half of PA; if angle PBD :le: 30 degrees, PD :le: .5(PB). If either of these cases occur, the proof is complete. If both angle PAD and angle PBC > 30 degrees, angle APB <120 degrees.

Since both angles CPF and APB are less than 120 :^o:, the sum of angles APF and BPE > 120  :^o: . Then at least one of the two angles > 60 :^o:. Assume that this angle is APF: if APF > 60 :^o:, since angle PFA is right angle PAF < 30:^o:, sin PAF * AP = PF < .5(AP), and the proof is complete. [/hide]

I really like your proof a lot, Jennifer, but I think you can make it simpler.  Call the feet of the perpendiculars from P to AB, BC, and CA C', A', and B' respectively.  Then consider the six angles A'PB, BPC', C'PA, APB', B'PC and CPA'.  Their sum is 360 degrees, which means that one of them must be at least 60 degrees.  Without loss of generality, take it as BPC'.  Using the cosine function on that angle in right triangle BPC', BP >= 2PC'.  Then, as you said, the longest distance from P to the triangle is at least BP, while the shortest is at most PC'.  Thus, the longest is at least twice the shortest.

I think the Erdos Mordell ineq works perfectly here:

PD, PE, PF are the distances from P to the sides BC, CA, AB. Then PA+PB+PC >= 2(PD+PE+PF), which, in turn, means that max (PA, PB, PC) >= 2*min (PD, PE, PF); we combine this with max distance (P, point on ABC) >= max (PA, PB, PC) and we get the desired ineq.


modular arithmetic
number theory unsolved
number theory

first (a,b,x)=(0,0,0),(0,1,1)
so $ b\ge 2$. trying mod 3,4,5 you have (a,b,x)=(2A+1,4B,2X+1) for some $ (A,B,X) \in N^3$.
if you scompone the equation we observe that $ (2^{2B}\plus{}2X\plus{}1,2^{2B}\minus{}2X\minus{}1)\equal{}1$ so you have the system, with solution such that $ 2^{2B\plus{}1}\equal{}3^{2A\plus{}1}\plus{}5^{2A\plus{}1}$
can you conclude? :wink:
paolo

I don't see how conclude but say me : why did you think about mod 3, 4 and 5 ?

Thanks.

if you see mod 3 so b=2B for some integer B, if you see mod 4 so a=2A+1 and x=2X+1 for some integers A,X.
then you have $ 2^{2B} \minus{} (2X \plus{} 1)^2 \equal{} (2^B \plus{} 2X \plus{} 1)(2^B \minus{} 2X \minus{} 1) \equal{} 15^{2X \plus{} 1}$ so $ 2^{B \plus{} 1} \equal{} 3^{2A \plus{} 1} \plus{} 5^{2A \plus{} 1} \equal{} (3 \plus{} 5)(5^{2A} \plus{} ... \plus{} 3^{2A})\equiv 8 \pmod {16}$.
is it clear?

[quote="bboypa"]$ \equal{} 15^{2X \plus{} 1}$ [/quote]

Are you sure it isn't $ 15^{2A \plus{} 1}$ ? But I didn't understand why we have $ 2^{B \plus{} 1} \equal{} 3^{2A \plus{} 1} \plus{} 5^{2A \plus{} 1}$ : where does it come from ?

Thank you  :oops:

you must have the system:
i)$ 2^B \plus{} 2X \plus{} 1 \equal{} 5^{2A \plus{} 1}$
ii)$ 2^B \minus{} 2X \minus{} 1 \equal{} 3^{2A \plus{} 1}$
no?
and what is i)+ii) ?

[quote="Ramanujan47"]Hi,

Can someone give me HINTS in order to solve this equation in N : $ x^2 \plus{} 15^a \equal{} 2^b$ ?

I thought use mod 4 (because of square and $ 2^b$) but that didn't give me nice things with the exception of $ x$ and $ a$ odd  :(

Thanks.[/quote]
[hide]Mod 3 the LHS is 1, so b must be even.
Let b=2k
$ (2^{k}\plus{}x)(2^{k}\minus{}x)\equal{}15^{a}$
$ (x\plus{}2^{k},2^{k}\minus{}x)\equal{}(x,2^{k\plus{}1})$
But since x is odd (mod 4) we have that the two terms are coprime, meaning one is $ 3^{a}$ and the other is $ 5^{a}$ or that one is 1 and the other is $ 15^{a}$

For the first case we have that
$ 2^{k}\plus{}x\equal{}5^{a}$
$ 2^{k}\minus{}x\equal{}3^{a}$
This gives us that $ 2^{k\plus{}1}\equal{}3^{a}\plus{}5^{a}$
a must be odd, because if it's even then the RHS is 2 mod 4.
Mod 16 tells us that a is 3 mod 4.
Let a=4q+3.
$ 2^{k\plus{}1}\equal{}27 \cdot 81^{q}\plus{}125 \cdot 625^{q}$
Mod 16 gives us 152 for the RHS, but clearly this isn't true for $ k\geq 3$ so $ k<3$
Checking, we see that k=2 gives us a=1 as a solution, and that k=1 has no solution. So this case has one solution $ (x,a,b)\equal{}(1,1,4)$

For the second case, we have that
$ x\plus{}2^{k}\equal{}15^{a}$
$ 2^{k}\minus{}x\equal{}1$
$ 2^{k\plus{}1}\equal{}15^{a}\plus{}1$
$ 2^{k\plus{}1}\minus{}15^{a}\equal{}1$
By Catalan-Mihailescu we have that this has no solutions for k>0 and a>1, so a must be 1, which means that k=3, giving us the solution set $ (7,1,6)$[/hide]
Nice porblem :)


function
limit
advanced fields
advanced fields unsolved

Let $ E\subset \mathbb{R}^n$ has positive measure. How to construct a decreasing sequence
\[ E \equal{} E_0\supset E_1\supset E_2\supset E_3\supset \cdots
\]
such that
\[ m(E_0) > m(E_1) > m(E_2) > \cdots
\]
where each $ m(E_i)$ is positive.

Thanks for your help.

For $ r \ge 0$ let $ E(r) \equal{} \{x\in E\colon |x|\le r\}$. Then $ f(r) \equal{} m(E(r))$ is a continuous function such that $ f(0) \equal{} 0$ and $ \lim_{r\to\infty}f(r) \equal{} m(E) > 0$. Use the intermediate value theorem.

My first version of this post began with
[quote]Let $ x_1$ be one of coordinates, and let $ E(t) \equal{} \{x\in E\colon x_1 < t\}$[/quote]
Why did I change it?   :?:

Actually I have considered that construction too. For this construction not all $ E(r)$ has positive measure. Now how to selects $ r$ so that $ m(E(r))>0$.

He already said to use the intermediate value theorem ;)


[quote="Inspired By Nature"]Solve for x, y, and z.
$5x+2y+3z=21$
$6x+8y+3z=32$
$5x+6y+10z=11$
I wasn't sure about the difficulty level, so mods can feel free to move it if need be. :)[/quote]
[hide]$5x+2y+3z=21;\,6x+8y+3z=32;\,5x+6y+10z=11$

Subtract the second from the first to get $-x-6y=-11,$ or $x=11-6y.$

Subtract the third from the first to get $-4y-7z=10,$ or $z=\frac{-10-4y}{7}.$

Now, substitue $x$ and $z$ into the first equation to find $y.$

$5(11-6y)+2y+\frac{3(-10-4y)}{7}=21\Longrightarrow y=1$

Plug $y$ back into the other two equations to get $x$ and $z.$

$x=11-6y\Longrightarrow x=5$

$z=\frac{-10-4y}{7}\Longrightarrow z=-2$

The answer is $(5,\,1,\,-2).$[/hide]

Aha! Time for Cramer's Law!

Put the coefficients in a matrix.
It should look like this:
$\begin{pmatrix}5 & 2 & 3 \\ 6 & 8 & 3 \\ 5 & 6 & 10 \end{pmatrix}$

Now we want to solve for X.

Take the determinant of the above matrix. Call this coefficient determinant "D".
$D = 208$

Now we substitute the answer row for the X row:
$\begin{pmatrix}21 & 2 & 3 \\ 32 & 8 & 3 \\ 11 & 6 & 10 \end{pmatrix}$

We find the determinant of this and call it $D_{x}$
$D_{x}= 1040$
By Cramer's Rule, $\frac{D_{x}}{D}= X$
$\frac{1040}{208}= X$
$X = 5$

Use this this process to solve for Y and Z.

This is much faster than gaussian elimination...

[quote="DiscreetFourierTransform"]Aha! Time for Cramer's Law!

Put the coefficients in a matrix.
It should look like this:
$\begin{pmatrix}5 & 2 & 3 \\ 6 & 8 & 3 \\ 5 & 6 & 10 \end{pmatrix}$

Now we want to solve for X.

Take the determinant of the above matrix. Call this the general case D.
$D = 208$

Now we substitute the answer row for the X row:
$\begin{pmatrix}21 & 2 & 3 \\ 32 & 8 & 3 \\ 11 & 6 & 10 \end{pmatrix}$

We find the determinant of this and call it $D_{x}$
$D_{x}= 1040$
By Cramer's Rule, $\frac{D_{x}}{D}= X$
$\frac{1040}{208}= X$
$X = 5$

Use this this process to solve for Y and Z.[/quote]
I agree that this is faster, but could you please explain how you find the determinant?

[quote="DiscreetFourierTransform"]Sure.
Take the given first matrix above.
$\begin{pmatrix}5 & 2 & 3\\ 6 & 8 & 3\\ 5 & 6 & 10 \end{pmatrix}$
To find the determinant of a 3 x 3 matrix, we need to add up the down diagonals and subtract the up diagonals. To do this, we need to extend the matrix so it is 3 x 5.
We get:
$\begin{pmatrix}5 & 2 & 3 & 5 & 2\\ 6 & 8 & 3 & 6 & 8\\ 5 & 6 & 10 & 5 & 6 \end{pmatrix}$
Now we multiply out the down diagonals:
$(5)(8)(10)+(2)(3)(5)+(3)(6)(6)$
and subtract the up diagonals.
$-(5)(8)(3)-(6)(3)(5)-(10)(6)(2)$
Multilplying and combining leads to
D = 208, like I said.

If this whole down and up diagonals thing confuses you, look at this:[url]http://www.purplemath.com/modules/determs2.htm[/url]
That should clear up any questions.[/quote]
Thank you. :)

Now I'm not sure that that's faster. :rotfl:

I'll do another example with how to find Y. It should be pretty self-explanatory if you look at the the similarities between finding X and Y.
This time, I know the determinant of the coefficient matix is 208.
I'll find Y.

Take the initial coefficient matrix, and substute the answer column into the Y column.

$\begin{pmatrix}5 & 21 & 3 \\ 6 & 32 & 3 \\ 5 & 11 & 10 \end{pmatrix}$

Take the determinant of this, like I showed how to do above.
It comes out that
$D_{y}= 208$
$\frac{D_{y}}{D}= \frac{208}{208}$
$Y = 1$

Well, for really long systems of equations that you're sure have a definite solution, it works wonders.
Also, if you have a TI Calculator, it can automatically calculate determinants, which makes life a lot faster, and makes Cramer's Rule a viable solution strategy to these problems.

This only works if you can rearrange the equations into the form:
$X+Y+Z = N$
$AX+BY+CZ = DN$
$EX+FY+GZ = HN$... and so forth.
If there are, say, ten equations, and you have ten variables you need to solve for, then using this is MUUUUCH faster.
You just get a 10 x 10 matrix and find the determinants and you're golden.

[quote="DiscreetFourierTransform"]Stupid random question, but I live in Redwood City, i_like_pie.
Where do you go to school?
I'm from Menlo School in Atherton. I might meet you at some math competetion someday soon, and that would be fun.  :lol:[/quote]
I'll PM you. :)

has anyone noticed what happens when you sum the three equations? makes regular old algebra a bunch easier...

[quote="Inspired By Nature"]Solve for x, y, and z.
$5x+2y+3z=21$
$6x+8y+3z=32$
$5x+6y+10z=11$
I wasn't sure about the difficulty level, so mods can feel free to move it if need be. :)[/quote]

Add all the equations:

$5x+2y+3z=21$
$6x+8y+3z=32$
$5x+6y+10z=11$

$16x+16y+16z = 64$
$x+y+z=4$

Now subtract multiples of that from each of the original equations:

$3x+z=13$
$3x+5y=20$
$y+5z=-9$

Now it gets easier.  Subtract equation 1 from equation 2:

$5y-z = 7$

Use that with the thrid equation:

$y+5z=-9$
$5y-z = 7$

Now a system of two equations, solvable by substitution or elimination.  We'll do elimination:

$y+5z=-9$
$(5)(5y-z)= (5)(7)$

$y+5z=-9$
$25y-5z= 35$

Add them up:

$26y = 26$
$\boxed{y=1}$

Substitute back into any equations you want, and find:

$\boxed{x=5; y=1; z=-2}$


geometry
incenter
circumcircle
Euler
geometry proposed

Let $ ABC$ be a non-equilateral triangle with its incircle touching $ \overline{BC}$, $ \overline{CA}$ and $ \overline{AB}$ at $ A_1$, $ B_1$ and $ C_1$, respectively, and let $ H_1$ be the orthocenter of triangle $ A_1B_1C_1$. Prove that $ H_1$ is on the line passing through the incenter and circumcenter of triangle ABC.

This problem is well know.
After the inversion with center I radius r, the circumcircle (ABC) becomes the nine-point circle of triangle $ A_1B_1C_1$, so the Euler line $ IH_1$ of triangle $ A_1B_1C_1$ passes through the circumcenter O of triangle ABC.

Dear Mathlinkers,
let I be the incenter of ABC and O the circumcenter of ABC.
H1I is the Euler line of A1B1C1.
ABC is the tangentiel triangle of A1B1C1.
Accordling to Gob's theorem, H1I go through O.
Sincerely
Jean-Louis


inequalities
logarithms
number theory proposed
number theory

Prove that $ w(3^{k} \plus{} 1) < w(3^{k} \plus{} 2)$ for infinitely many positive integers $ k$.

It would be nice to know what $ w(n)$ is to start with. Is it the number of distinct prime factors in the factorization of $ n$ as the title suggests or anything else? :?

Fedja, it was surely $ \omega(\cdot)$ then Max DR was referring to. I have just sent one private message to him for knowing the source of this beautiful problem, and he said "[i]Germany TST 2006[/i]". Incidentally I was yet able to prove this statement replacing $ 3^k$ with $ 2^k$, but when I searched for the original text, I found a bit [i]different[/i] problem:
[i]"Show that there exist infinitely many positive integer n such that $ \omega(n)<\omega(n\plus{}1)<\omega(n\plus{}2)$."[/i]
Seeing this one, I had to modify my previous proof, especially for the missing condition $ \omega(n)<\omega(n\plus{}1)$ that makes this problem a bit harder.
Now the question is, why Max DR have posted the problem in this form? Do you know a possible solution in this form (and surely verifying the here additional easier condition $ 3^k\plus{}1$ is not a power of a prime, so it is not a power of 2), or is it only a your idea about a possible solution? (And I [i]hope[/i] [...] it is not the second..).
However I have posted my proof to the original TST problem [url=http://bboyjordan.wordpress.com/2009/11/04/fnfn1fn2-for-infinitely-many-n/]here[/url], in the Proposition 1(and if you are interested in, you can try to prove other proposition 2 and 3 that I'll complete to write their solution at least next week..).

The $ 2^k$ case (and the Germany TST) is relatively easy: all we need to show is that there is $ k$ such that $ 1 < \omega(2^k \plus{} 1)\le\omega(2^{k \minus{} 1} \plus{} 1)$. Consider the interval $ k\in [K \plus{} 1,2K]$.

The first inequality holds unless $ 2^k \plus{} 1 \equal{} p^\ell$ for some prime $ p$. If $ p$ is such a prime, then $ 2^{2^s} \plus{} 1 \equal{} p^m$ where $ s$ is the power of $ 2$ in $ k$. Moreover, if $ k \equal{} {2^s}u$ where $ u\ge 3$ is odd, then $ u$ must be divisible by $ 2^{2^s} \plus{} 1$: otherwise the second (bigger) factor in the factorization $ 2^k \plus{} 1 \equal{} (2^{2^s} \plus{} 1)(\dots)$ is not divisible by the first one. Thus, we must have $ k \equal{} 2^s$ or $ k\ge 2^{2^s}$.

There is only one $ k$ of the first kind in the interval $ [K \plus{} 1,2K]$.

Also, for given $ s$ such that $ 2^{2^s} \plus{} 1 \equal{} p^m$, we may have only one $ k\in[K \plus{} 1,2K]$ such that $ 2^k \plus{} 1$ is a power of $ p$ because no two numbers $ 2^k \plus{} 1$ with $ k$ in this interval divide each other.

Thus we can have at most $ \log\log K$ bad values of $ k$ from the viewpoint of the first inequality and, thereby, an interval of length $ \frac {K}{\log\log K}$ on which it holds. If on this interval $ \omega$ increases strictly, then at its right end we have $ \omega(2^k \plus{} 1)\ge \frac {K}{\log\log K}$. Thus, $ 2^{2K} \plus{} 1$ must be greater than the product of the first  $ \frac K{\log\log K}$ primes. But the product of the first $ N$ primes is at least $ N!$, which is about $ e^{N\log N}$ on the rough scale and we immediately come to a contradiction.

Now, with $ 3^k$ nothing like that works...


how many of [url=http://www.skytopia.com/project/imath/imath.html]these[/url] can you do?
youd better be able to do the dice roll

What's the problem with that webpage?  When I move my cursor over the text, it disappears, making it very difficult to read.


In a factory that makes lights bulbs, 0.04 percent of the bulbs made  are defective.  What is the minimum number of bulbs made in which you would expect to find one defective bulb?

(a) 250

(b) 1250

(c) 2500

(d) 4000

I don't get it.

The expected number of defective bulbs is 0.04% of the total number of bulbs.

"What is the minimum number of bulbs made in which you would expect to find one defective bulb?"
is basically asking
"1 is 0.04% of what number?"

I did not understand the wording of the question.

I do understand 1/0.0004 = 2500

Thanks!


geometry
trigonometry
circumcircle
function
algebra
polynomial
Rational Root Theorem

Find all the triangles such that its side lenghts, area and its angles' measures (in degrees) are rational.

It can be verified that for a rational number not nule  $q$ we  have $\sin{q}$ is irrational.Actually it is transcendent,but we don't need. :)

[quote="mateivld"]It can be verified that for a rational number not nule  $q$ we  have $\sin{q}$ is irrational. Actually it is transcendent,but we don't need. :)[/quote]

This does not answer the question. Surely $30^\circ,\ 90^\circ,\ 150^\circ \in (0^\circ,\ 180^\circ)$ are all rational (in degrees) and $\sin 30^\circ = \sin 150^\circ = \frac{1}{2},\ \sin 90^\circ = 1$ are also rational. Besides, plenty of angles rational in degrees have sines algebraic irrational. (All of them, except for those few with rational sines.)

By the problem condition, the circumradius $R = \frac{abc}{4S}$ is rational, hence $\sin A = \frac{a}{2R},\ \sin B = \frac{b}{2R},\ \sin C = \frac{c}{2R}$ are all rational. We cannot make a triangle with any selection of angles from $\{30^\circ,\ 90^\circ,\ 150^\circ\},$ we need some other angle $\theta$ rational in degrees, such that $\sin \theta$ is rational. Let $\theta \in [0^\circ,\ 180^\circ].$ Then $\phi = 90^\circ-\theta \in [-90^\circ,\ +90^\circ],$ $\phi = \frac{m}{n}\cdot 360^\circ$ (where $n > 0,$ $-n \le 4m \le+n$) is also rational, and $\cos \phi = \sin \theta,\ 2 \cos \phi = \frac{p}{q}$ are also rational. We can take p, q so that $p \ge 0,\ q > 0,\ \gcd(p,\ q) = 1.$ Since $0 \le \cos \phi \le 1,$ we also have $p \le 2q.$

$2 \cos 2 \phi = 4 \cos^{2}\phi-2= \frac{p^{2}}{q^{2}}-2= \frac{p^{2}-2q^{2}}{q^{2}}.$

Assume that $\gcd(p^{2}-2q^{2},\ q^{2}) = d > 1.$ Since d divides $q^{2},$ it divides both q and $2q^{2}$, and since d divides both $p^{2}-2q^{2}$ and $2q^{2},$ it also divides $p^{2}$ and consequently p, so that $\gcd(p,\ q) \ge d > 1,$ which is a contradiction. Hence $\gcd(p^{2}-2q^{2},\ q^{2}) = 1$ as well. Assuming q > 1, the denominators $q_{k}= q^{2^{k}}$ of $2 \cos 2^{k}\phi = \frac{p_{k}}{q_{k}}$ then grow without bounds for $k \longrightarrow \infty.$ But cosine is a periodic function with the period $360^\circ.$ Thus for every n, the sequence $\frac{p_{k}}{q_{k}}= 2 \cos 2^{k}\phi = 2 \cos \left(\frac{2^{k}m}{n}\cdot 360^\circ\right),$ $k = 0,\ 1,\ 2,\ ...$ contains at most n different values $2 \cos \left(\frac{l}{n}\cdot 360^\circ\right),\ l = 0,\ 1,\ ...,\ n-1,$ which contradicts $q_{k}\longrightarrow \infty.$ As a result, q = 1 and the only rational cosines of rational angles $-90^\circ \le \phi \le 90^\circ$ are given by $2 \cos \phi = p \le 2,$ where p = 0, p = 1, or p = 2. Hence $\cos \phi = 0,$ $\cos \phi = \frac{1}{2},$ or $\cos \phi = 1,$ so that $\phi \in \{0^\circ,\ \pm 60^\circ,\ \pm 90^\circ \}$ and $\theta = 90^\circ-\phi \in \{0^\circ,\ 30^\circ,\ 90^\circ,\ 150^\circ,\ 180^\circ \}.$ In conclusion, triangles satisfying the problem condition do not exist.

[quote="anonymous1173"]is it a known problem :?:[/quote]
I think that it is connected with the well-known problem of triangles with integer lenghts od heights, angle bisectors and sides.

Yes, it is a well known problem. Another way is to consider complex roots of poynomial $z^{n}-1 = 0,$ because an angle rational in degrees $\theta = \frac{m}{n}\cdot 360^\circ$ is the angle $\angle A_{0}OA_{m}$ of a regular n-gon $A_{0}A_{1}...A_{n-1}$ with center O. This polynomial has roots $z_{m} = \cos \left(\frac{m}{n} \cdot 360^\circ\right) +$ $ \text{i}\sin\left(\frac{m}{n} \cdot 360^\circ\right),$ $m = 0,\ 1,\ ...,\ n-1.$ The polynomial in z can be transformed into a polynomial in $x = 2 \cos \theta$ with integer coefficients and leading coefficient 1, by factoring as much as possible and then substituting $x = z+\frac{1}{z}$ in each factor. By the rational root theorem, the only possible rational roots of the polynomial in x are integers, and since $|x| = 2|\cos \theta| \le 2,$ only the integers -2, -1, 0, +1, +2.

Yeah, my problem is also very interesting and simillar. :P

Alternatively, for any angle $\theta$ which is a rational multiple of $\pi$, we have that $e^{i \theta}$ and $e^{-i \theta}$ are both algebraic integers. Hence, so is their sum $2 \cos \theta.$ If $\cos \theta$ was to be rational, then so would $2 \cos \theta$ and hence $2 \cos \theta \in \mathbb{Z}$. This gives that $\theta$ is a multiple of $\frac{\pi}{3}.$ Then finish as above.


How many different rectangles can be formed by connecting four of the dots in a $ 4\times 4$ square array of dots as in the figure below, such that the sides of the rectangle are parallel to the sides of the grid? [asy]size(2cm,2cm); for (int i=0; i<4; ++i) {   for (int j=0; j<4; ++j)   { filldraw(Circle((i, j), .05), black,  black);  } }[/asy]

Why not include the 'choose' method in the solution?

That only works if the sides of the rectangle are parallel to the sides of the square (unless I'm missing something here).

EDIT;  sorry

[quote="GameBot"]How many different rectangles can be formed by connecting four of the dots in a $ 4\times 4$ square array of dots as in the figure below, [b]such that the sides of the rectangle are parallel to the sides of the grid[/b]? [asy]size(2cm,2cm); for (int i=0; i<4; ++i) {   for (int j=0; j<4; ++j)   { filldraw(Circle((i, j), .05), black,  black);  } }[/asy][/quote]

Exactly.

Well, you need to choose 2 parallel horizontal lines and 2 parallel vertical lines out of 4 each, so jbatterson was right 4 years ago!!!!

I thought the question asked how many different rectangles can be formed, so then a $1\times1$ rectangle should be counted only once, and so on with the
$1\times2$...

I know what choosing is, but I don't get either of the two solutions below:[quote=math154]Once you've selected two points on two adjacent sides, a rectangle is determined (do you see why?).

Thus, the answer is [hide=click to reveal solution]$ \dbinom42\dbinom42\equal{}\boxed{36}$.[/hide][/quote]
What do you mean by adjacent sides? How do you know you don't overcount? Why multiply twice?
[quote=MattDrohung][hide=click to reveal solution]Nine choose two squares and you get 36 rectangles. :D [/hide][/quote]

Where did 9 come from?

[quote]What do you mean by adjacent sides? How do you know you don't overcount? Why multiply twice?[/quote]

Quite a mouthful. There are $4$ vertical lines and $4$ horizontal lines. There's $\binom{4}{2}$ ways to choose a pair of vertical lines and $\binom{4}{2}$ ways to choose a pair of horizontal lines, which will determine the sides of a rectangle. You can also show that the sides of a rectangle will map to a pair of vertical and horizontal lines, so there's a bijection and no overcount.

This question is confusing; it seems like you have to create rectangles that only pass through 4 points :huh:

I still don’t understand the choose method.

No need, since it is a countable amount of squares, you can use casework. However if it were bigger, you would just have to notice you always need two pairs of horizontal lines and vertical lines to create rectangles. That is why he did $\binom{4}{2}*\binom{4}{2}=\boxed{36}$

[quote=ythomashu][hide=Alternative Solution]Two points not on the same row or column make the diagonal of one rectangle. There are 16 points for the first one, and then 9 points for the second one. Since rectangles have four vertices, we divide the product of 16 and 9 by 4. so the answer is 36[/quote]

I get the choose method, but not this one.

What about the diagonal ones? What in the problem statement does not allow the two diagonal ones?

woah
we have ntblue and ntred
is there a correlation? what does NT mean? (other than number theery)

[quote=mop][quote=je100]What are combinations?
(I need an easier way than counting them all by hand lol)[/quote]

If we want to choose $k$ distinguishable objects from a set of $n$ objects such that the order of the $k$ distinguishable objects DOES NOT matter, there are $\binom{n}{k}$ ways to do this. If we want to chosoe $K$ distinguishable objects from a set of $n$ objects such that the order of the $k$ distinguishable objects DOES matter, there are $_{n}P_{r}$ ways to do this. $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ for $n\ge k$ and is undefined for $n<k$, and $_{n}P{k}=\frac{n!}{(n-k)!}$ with the same restrictions as $\binom{n}{k}$. Notice that $_{n}P_{k}=k!\cdot\binom{n}{k}$. This is because when the order does matter, there are $k!$ ways to arrange the $k$ objects, because there are $k$ ways to choose the first object, $k-1$ ways to choose the second object (because the first one was already chosen), etc.,[/quote]

:o

Wow, that's amazing. Thank you! :)

[quote=smarty101][hide=different solution]The formula for how many rectangles is $\frac{(m+1)\cdot{m}\cdot{n}\cdot(n+1)}{4}$ where $m$ and $n$ are the two numbers in the $m$ by $n$ grid. Plugging this in, we get $36$[/hide][/quote]

Oh, this is much much faster! Thank you for the formula, it will help with my competitions!

[hide=another alternative sol]
The number of ways to choose 1 point from the bottom side is $\binom41=4.$ The number of ways to choose 1 point from the top side is also $\binom41=4.$ However, this overcounts the "rectangles" that are made by choosing the bottom leftmost point. Subtracting 7 for overcounting, we get $(4)(4)-7=9$ rectangles for the bottom leftmost corner.

To find the total number of rectangles in the triangle, we can multiply the number of rectangles in one corner by four to get $9\cdot4=\boxed{36}.$

sry if it's not clear
[/hide]


inequalities
induction
number theory unsolved
number theory

Let the sequence $ F_n$ defined by $ F_0\equal{}0$, $ F_1\equal{}1$ and $ F_n\equal{}F_{n\minus{}1}\plus{}F_{n\minus{}2}$ for $ n\geq2$.Prove the following:
$ (1)$ $ F_1^2\plus{}F_2^2\plus{}...\plus{}F_n^2\equal{}F_nF_{n\plus{}1}$,                $ n\geq1$

$ (2)$ $ \dfrac{1}{n^2}\sum^n_{i\equal{}1}{(\dfrac{T_i}{F_i})^2}\geq \dfrac{T_{n\plus{}1}^2}{9F_nF_{n\plus{}1}}$.

($ T_n$ is defined by $ T_n\equal{}\dfrac{n(n\plus{}1)}{2}$)

The first identity is an easy induction:
$ n\equal{}1$: $ {F_1}^2 \equal{} 1*1 \equal{} {F_1}{F_2}$
$ n \longrightarrow n\plus{}1$: $ {F_1}^2 \plus{} {F_2}^2 \plus{} {F_3}^2 \plus{} ... \plus{} {F_n}^2 \plus{} {F_{n\plus{}1}}^2 \equal{} {F_n}{F_{n\plus{}1}} \plus{} {F_{n\plus{}1}}^2$ by our inductive hypothesis.

Now, $ {F_n}{F_{n\plus{}1}} \plus{} {F_{n\plus{}1}}^2 \equal{} {F_{n\plus{}1}}({F_n} \plus{} {F_{n\plus{}1}}) \equal{} {F_{n\plus{}1}}{F_{n\plus{}2}}$ by the definition of the fibonacci sequence.  Hence the identity is established.

[quote="Inequalities Master"]$ (2)$ $ \dfrac{1}{n^2}\sum^n_{i \equal{} 1}{(\dfrac{T_i}{F_i})^2}\geq \dfrac{T_{n \plus{} 1}^2}{9F_nF_{n \plus{} 1}}$.

($ T_n$ is defined by $ T_n \equal{} \dfrac{n(n \plus{} 1)}{2}$)[/quote]

By Cauchy on the sequences $ F_1,F_2,...,F_n$ and $ \frac{T_1}{F_1},\frac{T_2}{F_2},...,\frac{T_n}{F_n}$ we have

$ \left(F_1^2\plus{}F_2^2\plus{}\cdots\plus{}F_n^2\right)\left(\displaystyle\sum_{i\equal{}1}^n\left(\frac{T_i}{F_i}\right)^2\right)\ge\left(T_1\plus{}T_2\plus{}\cdots\plus{}T_n\right)^2$

From (1) we have $ F_nF_{n\plus{}1}\equal{}F_1^2\plus{}F_2^2\plus{}\cdots\plus{}F_n^2$.  We also change to the notation $ T_i\equal{}\binom{i\plus{}1}{2}$ to get

$ F_nF_{n\plus{}1}\displaystyle\sum_{i\equal{}1}^n\left(\frac{T_i}{F_i}\right)^2\ge\left(\binom{2}{2}\plus{}\binom{3}{2}\plus{}\cdots\plus{}\binom{n\plus{}1}{2}\right)^2$

Using the Hockey Stick Identity we get

$ F_nF_{n\plus{}1}\displaystyle\sum_{i\equal{}1}^n\left(\frac{T_i}{F_i}\right)^2\ge\binom{n\plus{}2}{3}^2$

$ \Rightarrow F_nF_{n\plus{}1}\displaystyle\sum_{i\equal{}1}^n\left(\frac{T_i}{F_i}\right)^2\ge\binom{n\plus{}2}{2}\frac{n^2}{9}$

$ \Rightarrow \frac{1}{n^2}\displaystyle\sum_{i\equal{}1}^n\left(\frac{T_i}{F_i}\right)^2\ge\frac{T_{n\plus{}1}^2}{9F_nF_{n\plus{}1}}$

and the inequality is proven.

Sorry for such a question:
What is Hockey identity?


algebra polynomial function search LaTeX

I need the following polynomial function terms defined in easy math language.

Can you help me?

*degree

*gap

*hole

*corner

*cusp

*continuous

Refer to a previous post of mine.

[quote="t0rajir0u"]You ask a lot of questions on the forum that are obviously from a math class.  Do you feel that your teacher is not doing an adequate job preparing you for your homework?  You might want to consider getting a tutor rather than cluttering the forum with homework.[/quote]

[quote="Interval"]I guess I'll just have to search online for all definitions.[/quote]

Yes and as a reference, try to attempt some of the problems with the help of a mathbook and if u are relaly stuck then you can post the question with some of the work you have done in LATEX!!!


Nice to meet you kt!

Long time no see zㅋㅋㅋ

It easy to show when you expand

ㅋㅋㅋ 희빈형은 잘 지내요?

전개라... 전개는 저도 귀찮아서 아직 안 해봄 ㅋ

ps 이제 gt로 바뀐 듯 ㅋㅋㅋ 여권때문에 ㅋ


limit
inequalities
algebra unsolved
algebra

Let be given a sequence of non-negative real numbers:$a_1,a_2,....,a_n$ satisfy:$\sum_{1}^\infty a_n<+\infty$
For each number $x>0$ denote $N(x)=$ the number of $a_i$ such that $a_i>x$.
Prove that:$\lim_{x\rightarrow 0}x.N(x)=0$

Let $j$ be a positive integer.  Then we have the following inequality:
\[ xN(x) \le (j-1) x + \sum_{i=j}^\infty a_i \, .  \]
Taking the limit as $x$ approaches 0, we get
\[ \limsup_{x \rightarrow 0^+} xN(x) \le \sum_{i=j}^\infty a_i \, .  \]
Taking the infimum over all $j$, we get
\[ \limsup_{x \rightarrow 0^+} xN(x) \le 0 \, .  \]


draw through a point $P$ inside an angle a segment ,wich cuts off a triangle of minimum area.

segment AB must have AP = PB in distance.

Let XOY be the angle.  Wlog P is on or below the angle bisector of the angle.  Draw AB with AP = PB and P on AB.   Draw CD with P on CD, where A,B,C,D are all on the angle XOY.  Put A and C on OY.

If C is to the right of A, then we have to show [AOB] < [COD]  iff [BPD] < [PAC] iff PD < PC  which can be easily shown; similarily for left.


function
calculus
derivative
trigonometry
inequalities
real analysis
real analysis unsolved

Proove that there exists only one function $f : \mathbb{R} \to \mathbb{R}$ which has arbitrary derivatives
such that $f'(0) =1$ and $\forall n\in \mathbb{N}~\forall x\in \mathbb{R}~|f^{(n)}(x)| \leq 1$
where $f^{(n)}$ means the $n^{th}$-derivative of $f$.
Give $f$.

Good luck.

Fabrice

[quote="Moubinool"]$f(x)=\sin x$[/quote]
Wow! It is the shortest proof I ever seen.

$f(x)=x$.
May be I am missing something but there are at least two solutions.

As I am used to $\mathbb{N}=\{1,2,\ldots\}$ and ${\mathbb{N}}_{0}=\{0,1,2,\ldots\}$.Anyway let's wait for [b]fabrice[/b].   :)

[quote="Myth"]Yes, you are missing one detail: Fabrice assumes $0\in\mathbb{N}$ (I think :? )[/quote]

Of course I mean $f$ is the $0^{th}$-derivative of $f$ :-)
Thus you have to assume the inequality for $f$
- i.e.  $\forall x\in \mathbb{R}~~|f(x)|\leq 1$  -

And for Moubinool, it is not enough to give
the solution without any proof  ;-)

Good luck.

Fabrice

A couple of quick observations: first, $f$ is entire (that is, given everywhere by a power series with an infinite radius of convergence.) Even stronger than entire: its Fourier transform (as a temepered distribution) is supported on a particular interval. (I don't want to try to use that last one.)


never mind, i figured it out.  sorry about this.

You have a formula to calculate the variance given the generating function, and you have an expression for the generating function.  So, get differentiating.

It's extremely rude to delete the contents of your post like that.


$x+y+z=1$ Prove that:$ax+by+cz+2\sqrt{(ab+ac+bc)(xy+xz+yz)}\leq a+b+c $

See http://www.mathlinks.ro/Forum/viewtopic.php?t=22605 .

  darij


quadratics
Diophantine equation
number theory
number theory proposed

Let a, b be positive integers. a, b and a.b are not perfect squares.

Prove that at most one of following equations

        $ ax^2 \minus{} by^2 \equal{} 1$ and $ ax^2 \minus{} by^2 \equal{} \minus{} 1$

has solutions in positive integers.

I don't follow.  In the $ a \equal{} 1$ case, any solution $ (x, y)$ to the second equation determines a solution $ (x^2 \plus{} by^2, 2xy)$ to the first.

[quote="Namdung"]@Rust: No need. If (a, b) > 1 then both of equations has no solutions and it is OK.
@t0rajir0u: a, b are not perfect squares![/quote]

I think (a, b)=1 is needed. If both of equations has no solutions, it is NOT ok.
The question is asking about one of the equation must have a solution.

Dear Stephen.

The statement of problem is "Prove that at most one of following equations has solutions", not "at least one". So if even we have (a, b) = 1, both of them can have no solutions!

And I'm not agree with you that the question about one equation must have solution.

A good problem . Here is my solution basing on an old result posted in AMM .
Lemma 1 : If the Pell's equations $ x^2 \minus{} dy^2 \equal{} ^{ \plus{} }_{ \minus{} }1$ have solution then $ x \plus{} y.\sqrt {d} \equal{} (p \plus{} q\sqrt {d})^2$ where $ |p^2 \minus{} dq^2| \equal{} 1$ and  $ (x,y)$ is a root of Pell's equation $ x^2 \minus{} dy^2 \equal{} 1$ (we only consider d is not a perfect square )
It is a fundamental property of the Pell's equation .
Lemma 2 (From the AMM ) Let $ x,y$ are two positive integer such that $ x \plus{} xy$ and $ y \plus{} xy$ are all perfect squares then exactly one of x,y is a square .
Proof  : Because $ x(y \plus{} 1)$ and $ y(x \plus{} 1)$ are both perfect squares so exist $ a,b,m,n,p,q$ such that :
\[ x \equal{} am^2,y \plus{} 1 \equal{} an^2,x \plus{} 1 \equal{} bp^2,y \plus{} 1 \equal{} bq^2
\]
Hence we have : $ bp^2 \minus{} am^2 \equal{} 1,an^2 \minus{} bq^2 \equal{} \minus{} 1$ .
From this equality we have :
\[ (am^2 \plus{} bq^2) \minus{} ab(2mq)^2 \equal{} (am^2 \minus{} bq^2)^2 \equal{} 1, (anp \plus{} bmq)^2 \minus{} ab(mp \plus{} nq)^2 \equal{} \minus{} 1
\]
By the lemma we have $ am^2 \plus{} bq^2 \equal{} u^2 \plus{} abv^2$ with $ |u^2 \minus{} abv^2| \equal{} 1$ .
Note that $ 2x \plus{} 1 \equal{} am^2 \plus{} bq^2$  so $ 2x \plus{} 1 \equal{} u^2 \plus{} abv^2$ . Solve this equation ,we obtain $ x$ or $ x \plus{} 1$ is a square . That ends the proof .
Now consider our problem . Suppose both of equations have integer solution $ (u,v)$ and $ (z,t)$ .Then we have :
\[ au^2 \minus{} bv^2 \equal{} 1, az^2 \minus{} bt^2 \equal{} \minus{} 1
\]
Let consider two numbers : $ x \equal{} au^2,y \equal{} bt^2$ then $ x \plus{} xy$ and $ y \plus{} xy$ are all perfect squares . By the lemma 2 ,at least one of them is a square ,then we have at least on of a or b is a square, this gives contradiction .

[quote="TTsphn"]Lemma 1 : If the Pell's equation $ x^2 \minus{} dy^2 \equal{} 1$ has solution then $ x \plus{} y.\sqrt {d} \equal{} (p \plus{} q\sqrt {d})^2$ where $ |p^2 \minus{} dq^2| \equal{} 1$ .
It is a fundamental property of the Pell's equation .[/quote]
That's just wrong.

Still wrong, for example if $ d\equal{}3$.

[quote="ZetaX"]Still wrong, for example if $ d \equal{} 3$.[/quote]
If d=3 then the second equation $ x^2 \minus{} dy^2 \equal{} \minus{} 1$ doesn't have  solution in N .
[quote="Namdung"]The statement of lemma should be:

Theorem. If d is not perfect square and (a, b), (m, n) are fundamental solutions (minimal solutions in positive integers) for
       $ x^2 \minus{} dy^2 \equal{} 1, x^2 \minus{} dy^2 \equal{} \minus{} 1$ respectively
then we have $ a \equal{} m^2 \plus{} dn^2$ and $ b \equal{} 2mn$

Note that the second equation may have no solutions, but it is no problem with the statement of theorem.

But I think in provided above solution there are other misteakes.[/quote]
Yes , lemma 1 follows from this fact . All roots of the Pell equation (1) $ x^2 \minus{} dy^2 \equal{} 1$ are :
\[ x_k \equal{} \frac {(a \plus{} b\sqrt {d})^k \plus{} (a \minus{} b\sqrt {d})^k}{2}, y_k \equal{} \frac {(a \plus{} b\sqrt {d})^k \minus{} (a \minus{} b\sqrt {d})^k}{2\sqrt {d}}
\]
Then by it is easy to show that $ x_k \plus{} \sqrt {d}y_k \equal{} (a \plus{} \sqrt {d}b)^k \equal{} (m \plus{} \sqrt {d}n)^{2k} \equal{} (x \plus{} \sqrt {d}y)^2$ . That ends lemma 1 .

This does not seem like an Olympiad problem, it's known and old results for anyone fond of NT.  :)

[quote="nghi.nguyen"]No, it is a very good problem. It's not a well-known result. The solution posted above is incorrect.[/quote]

1) It is good problem, I'm sure.
2) But it is well-know result also: D.T. Walker "On Diophantine equation $ mx^2 \minus{} ny^2 \equal{} \pm 1$" AMM, Volume 74, No 5, 1967. http://www.jstor.org/stable/2314877.
3) The solution provided above is subtracted form AMM 1995. It is correct but maybe not in details.

I send here another solution (detailed).

Hello guys I'm going to post my solution to this problem. I hope to receive feedback on it.

From problem statement we know that a can not be the same as b.

Step 1: Prove that not the two equations can have solutions in integers.

We have both equations:

ax^2 - by^2 = 1
ax^2 - by^2 = -1

We obviously know that both equations have real solutions. So adding them we get:

2ax^2 - 2by^2 = 0

Equivalent to

ax^2 = by^2

Taking the square root of it to leave the equation in terms of x and y we have

(sqrta)x = (sqrtb)y

or:

(sqrta)x/(sqrtb) = y

Since a is not the same as b and neither is a perfect square, their square roots are irrational numbers. If x is an integer, then y can not be an integer. If y is an integer then x = (sqrtb)/(sqrta) which is not an integer either. Therefore we've proven that both equations can NOT have solutions in integers.

Step 2: Prove that the equations can have solutions in integers.

We're not trying to prove that there is infinite number of integer solutions in this step, we're going to prove that there exists at least one solution in integers so as to satisfy that there are solutions in integers in the first place.

1) For the first equation:

ax^2 - by^2 = 1. Setting x = y,

ax^2 - bx^2 = 1 <==> x^2 (a - b) = 1.

Therefore (1, 1) is solution for a - b = 1. Note a > b

For the second equation:

ax^2 - by^2 = -1. Setting x = y,

ax^2 - bx^2 = -1 <==> x^2 (a -b) = -1.

Obviously x^2 > 0 so it cannot equal -1. From here we know that when a - b = -1, (1, 1) is a solution. Notice a < b.

2) In a more general way the first equation may be rewritten as

x^2 = (by^2+1)/a. We know there exist many if not infinite integer solutions to x^2 = by^2+1, so setting a to be equal to by^2+1 gives an integer x, x = 1. Otherwise note a can be a divisor of a non-perfect square by^2+1 of the form ak^2 that upon division, it transforms into a perfect square. Such a configuration exists in many ways, one of them we may set by^2+1 to be some 2k^2. Letting a = 2 we get in our equation that x^2 = k^2.

For the second equation we similarly have

x^2 = (by^2 - 1)/a. As in the first case we know there exist multiple integer solutions. In particular there are infinite integer solutions to x^2 = by^2 -1. Setting a to be equal to by^2 - 1 gives an integer x, x = 1. Otherwise a can be a divisor of a non-perfect square by^2 - 1 of the form at^2. that upon dividing it, the whole thing becomes a perfect square. From the first case we know such a configuration exists.

We have already proven that both equations may not have integer solutions at the same time.

***
By having shown that there do exist solutions in integers for both equations separately, though not solutions in integers for both at the same time, we have completed our proof.

*******

What do you think?

@TheLivingShadow: What a pitty but your solution is absolutely wrong. Two equations have solutions does not mean their have common solutions.

Dear Namdung,

Thanks for posting the link and also the solution. I've read your solution and it's very good. I'd like to post an alternative proof to the Lemma in your solution.

First, let me state the lemma as follows:

Lemma: Let $ (a,b)$ be the minimal solution to the equation $ x^2 \minus{} ABy^2 \equal{} 1$ (where $ a > 0, b > 0$). Assume that the equation $ Ax^2 \minus{} By^2 \equal{} 1 \; (1)$ has a solution. Then equation $ (1)$ has a solution $ (x_0,y_0)$ such that $ (x_0\sqrt {A} \minus{} y_0\sqrt {B})^2 \equal{} a \minus{} b\sqrt {AB}$.

Note that $ (x_0,y_0)$ is the solution that you need to finish off the proof. It also follows from the minimality of $ (a,b)$ that $ (x_0,y_0)$ is the minimal solution to equation $ (1)$, but we don't need this fact to complete the proof.

Proof of Lemma: Let $ (x_1,y_1)$ be a solution to $ (1)$. We can check that the number $ (x_1\sqrt {A} \minus{} y_1\sqrt {B})^2$ belongs to the ring $ \mathbb{Z}[\sqrt {AB}]$ and has norm 1. So it is a power of the fundamental unit and it follows that $ (x_1\sqrt {A} \minus{} y_1\sqrt {B})^2 \equal{} (a \minus{} b\sqrt {AB})^m$ for some positive $ m$. If $ m \equal{} 1$ we're done. Suppose $ m > 1$. Let $ 2n$ be the greatest even number that is $ \le m$. Write
\[ (x_1\sqrt {A} \minus{} y_1\sqrt {B})(a \plus{} b\sqrt {AB})^n \equal{} x_0\sqrt {A} \minus{} y_0\sqrt {B}.
\]
Then $ (x_0\sqrt {A} \minus{} y_0\sqrt {B})^2 \equal{} (a \minus{} b\sqrt {AB})^{m \minus{} 2n}.$ If $ m \equal{} 2n$ then the right hand side equals 1 while the left hand side doesn't (because $ AB$ is not a square). So $ m \minus{} 2n \equal{} 1$ and we are done.

Additional comment: if $ Ax^2 \minus{} By^2 \equal{} \minus{} 1$ also has a solution then the same proof shows that it has a solution $ (x_2,y_2)$ such that $ (x_2\sqrt {A} \minus{} y_2\sqrt {B})^2 \equal{} a \minus{} b\sqrt {AB}$. It follows that $ x_2\sqrt {A} \minus{} y_2\sqrt {B} \equal{} \pm(x_0\sqrt {A} \minus{} y_0\sqrt {B})$. However, this implies that $ x_2\sqrt {A} \minus{} y_2\sqrt {B}$  and $ x_0\sqrt {A} \minus{} y_0\sqrt {B}$ have equal norms, a contradiction. QED

Suppose for the sake of contradiction that both Diophantines have solutions. We first claim that the Diohpantine $x^2-aby^2=-1$ also has a solution. Suppose we have integers $x_0,y_0,x_1,y_1$ with $ax_0^2 - by_0^2 = 1$ and $ax_1^2 - by_1^2 = -1$. Then $(ax_0)^2 - ab y_0^2 = a$, and $(ax_1)^2 - ab y_1^2 = -a$. Let $u=ax_0x_1 - b y_0 y_1$ and $v = x_1 y_0 - x_0 y_1$. Then
\[\frac{ax_0 + \sqrt{ab} y_0}{ax_1 + \sqrt{ab} y_1} = \frac{a(ax_0 x_1 - by_0 y_1 + \sqrt{ab}(x_1 y_0 - x_0 v_1))}{(ax_1)^2 - (ab)y_1^2} = -(u + v \sqrt{ab}).\]
Rearranging and multiplying by its conjugate, we get
\[ a = (ax_0)^2 - ab y_0^2 = ((ax_1)^2 - ab y_1^2) (u^2 - ab v^2) = -a(u^2 - ab v^2) \implies u^2 - ab v^2 = -1. \]
Now let $p+q \sqrt{ab}$ be a minimal solution to $p^2 - ab q^2 = -1$. Note that squaring $ax_0^2 - by_0^2 = 1$ yields $(ax_0^2 + by_0^2)^2 - (2x_0y_0)^2 ab = 1.$ Because $p+q\sqrt{ab}$ is a minimal solution, $ax_0^2 + by_0^2 + 2x_0y_0 \sqrt{ab}$ is necessarily an even power of $p + q \sqrt{ab}$; in particular, it equals $(r+s \sqrt{ab})^2 = (r^2 + s^2 ab) + 2rs \sqrt{ab}$ for some integers $r,s$. We thus have $ax_0^2 + by_0^2 = r^2 + s^2 ab$ and $rs = x_0y_0$. Because $(ax_0^2) + (by_0^2) = (r^2) + (s^2 ab)$ and $(ax_0^2)(by_0^2) = (r^2)(s^2 ab)$, the sets $\{ax_0^2, by_0^2\}$ and $\{r^2, s^2 ab\}$ must be the roots of the same quadratic, so the sets are equal. Thus, $r^2$ must equal one of $ax_0^2$ or $by_0^2$, which is impossible since $a$ and $b$ are not squares.

EDIT: Fixed some typoes.

[quote="Zhero"]Then $(ax_0)^2 - ab y_0^2$, and $(ax_1)^2 - ab y_1^2 = -1$.[/quote]

Unless you're hiding many, many steps I think this is wrong. This would imply $a|(-1) \implies a = \pm 1$, which would let you finish the problem immediately. Is there a typo here?

Yeah, I made a number of typoes in that post, sorry. Hopefully they've all been fixed now.

Anyhow, in the process of fixing my typoes, I found an even cleaner solution. :P
[hide]Suppose for the sake of contradiction that both Diophantines have solutions. Since
\[  (ax_0 x_1 + by_0 y_1)^2 - ab (x_0 y_1 + x_1 y_0)^2 = (ax_0^2 - by_0^2)(ax_1^2 - by_1^2) = -1, \]
 the Diophantine $x^2-aby^2=-1$ also has a solution. Let $p+q \sqrt{ab}$ be its minimal solution. Squaring $ax_0^2 - by_0^2 = 1$ yields $(ax_0^2 + by_0^2)^2 - (2x_0y_0)^2 ab = 1.$ Because $p+q\sqrt{ab}$ is a minimal solution, $ax_0^2 + by_0^2 + 2x_0y_0 \sqrt{ab}$ is necessarily an even power of $p + q \sqrt{ab}$; in particular, it equals $(r+s \sqrt{ab})^2 = (r^2 + s^2 ab) + 2rs \sqrt{ab}$ for some integers $r,s$. We thus have $ax_0^2 + by_0^2 = r^2 + s^2 ab$ and $rs = x_0y_0$. Because $(ax_0^2) + (by_0^2) = (r^2) + (s^2 ab)$ and $(ax_0^2)(by_0^2) = (r^2)(s^2 ab)$, the sets $\{ax_0^2, by_0^2\}$ and $\{r^2, s^2 ab\}$ must be the roots of the same quadratic, so the sets are equal. Thus, $r^2$ must equal one of $ax_0^2$ or $by_0^2$, which is impossible since $a$ and $b$ are not squares. [/hide]
[hide="Motivation for identities"]
We have
\begin{align*}
-1
&= (ax_0^2 - by_0^2)(ax_1^2 - by_0^2) = (\sqrt{a}x_0 + \sqrt{b}y_0)(\sqrt{a} x_0 - \sqrt{b} y_0)(\sqrt{a}x_1 + \sqrt{b}y_1)(\sqrt{a} x_1 - \sqrt{b} y_1)  \\
&= (ax_0 x_1 + b y_0 y_1 + \sqrt{ab}(x_0 y_1 + x_1 y_0))(ax_0 x_1 + by_0 y_1 - \sqrt{ab}(x_0 y_1 + x_1 y_0)) = (ax_0 x_1 + by_0 y_1)^2 - ab (x_0 y_1 + x_1 y_0)^2,
\end{align*}
and
\begin{align*}
1
&= (ax_0^2 - by_0^2)^2 = (\sqrt{a}x_0 + \sqrt{b} y_0)^2 (\sqrt{a} x_0 - \sqrt{b} y_0)^2 = (ax_0^2 + by_0^2 + 2x_0 y_0 \sqrt{ab}) (ax_0^2 + by_0^2 - 2x_0 y_0 \sqrt{ab}) \\
&= (ax_0^2 + by_0^2) - (2x_0 y_0)^2 ab.
\end{align*}
[/hide]


algebra
polynomial
trigonometry
invariant
algebra proposed

Suppose $w$ is the fifth root of unity, find the 5-degree polynomial with roots $1+1,w+w^2,w^2+w^4,w^3+w^6,w^4+w^8$.
One can do it by brute force, but is there a more elegant solution?

thank you so much. I came across this problem when trying to do another problem

The original problem that I was working on is this:
Suppose $P(x) = x^5+x^2+x+1$ has roots $a_1,a_2,...,a_5$. Find a fifth degree polynomial whose roots are $a_1^5,...,a_5^5$
Please tell me if there is a beautiful solution to this problem.

My solution is like this (just the outline):
Suppose the polynomial we're looking for is $Q(x)$, then $Q(x^5) = P(x)P(wx)P(w^2x)P(w^3x)P(w^4x)$.
Now let $m = x^5+1$, then
$Q(x^5) = (m+x^2+x)(m+(wx)^2+(wx))(m+(w^2x)^2+w^2x)...(m+(w^4x)^2+(w^4x))$

Now to simplify this expression, we know that it's invariant with the transformation $x \to wx$,
so the product must have only $x^{10},x^5,$ and constant terms. Finding $x^{10}$ and constant is easy, but to find $x^5$, it became the first problem that I posted.
Suppose $Q(x^5) = x^{10}+ax^5 + m^5$ ($a$ may depend on $m$ too).
Substituting $x=1$ gives $m^5+1+a = (m+2)(m+w+w^2)(m+w^2+w^4)(m+w^3+w^6)(m+w^4+w^8)$
And according to the solution of the first problem, it becomes $m^5 -5m^2 +5m -2$ (note that the sign is reversed because now the roots are $-2,-w-w^2,-w^2-w^4,...$
Thus $a = -5m^2+5m-3$
Therefore $Q(x^5) = x^{10} + (-5m^2+5m-3)x^5 + m^5$, where $m = x^5+1$
So $Q(y) = y^2 +(-5m^2+5m-3)y+m^5$ where $m = y+1$

Is my solution correct, or is there a better way to do the original problem?


By chance, does anyone recognize what my avatar is? There's a reason I'm only asking this in this particular forum

Well, yeah, but I put as the description under my gallery of avatars. So anyone who looked at that would know that. I mean, who knows what it means/was used for?

three-foot crow is the national bird of 'Koguryo' which is the ancient Korean empire about 1C B.C.~ 7C A.D.

In fact, the name 'Korea' originated from 'Koryo' that is the successor country of 'Koguryo'. :lol:

Unique is right.

No wonder why the picture looked familiar..

more info. goguryeo was founded by jumong, the prince of puyo. the 3 legged crow was the flag of goguryeo. generations later,king damdeok united korea, but it split shortly after he died


calculus
integration
geometry
rectangle
topology
real analysis
real analysis unsolved

I'm curious to see if the following holds true, and if so, why. I'm trying to use it in a proof of Clairaut's Theorem:

Let $ A$ be open in $ \mathbb{R}^n$ and let $ f,g : A \to \mathbb{R}$ be continuous maps. Then if $ \int_Q f \equal{} \int_Q g$ for any rectangle $ Q \subset A$ we can conclude $ f\equal{}g$.

Also, if this is true, can the continuity hypothesis be relaxed? All of the above integrals are Riemannian, if it makes a difference.

Well, I thought it was true, but I've no idea where to begin. I tried using a nested sequence of rectangles about a given point, but couldn't get it to go through. Am I working too hard?

A hint on the proof: Use the Fundamental Theorem of Calculus, and step one dimension at a time. I think "continuous" can be relaxed to "continuous in each variable separately, but we can't allow jumps.

Can we do like this? Suppose $ f(x)>g(x)$ for some $ x$.
Consider the set $ B: \equal{}\{x\mid f>g\}$. It is open set in $ A$ hence we can find a rectangle $ Q\subset B\subset A$ such that
$ \int_Q f >\int_Q g$.

Oh, that works too, and it's much simpler.


Triangle $ ABC$ has $ AB\equal{}13$ and $ AC\equal{}15$, and the altitude to $ \overline{BC}$ has length $ 12$. What is the sum of the two possible values of $ BC$?

$ \textbf{(A)}\ 15\qquad
\textbf{(B)}\ 16\qquad
\textbf{(C)}\ 17\qquad
\textbf{(D)}\ 18\qquad
\textbf{(E)}\ 19$

[hide="Answer"]
You have two right triangles of $ x^2 \plus{} 144 \equal{} 225$ and $ y^2 \plus{} 144 \equal{} 169$, where $ x \plus{} y \equal{} BC$ which yield $ x^2 \equal{} 81$ and $ y^2 \equal{} 25$ giving you answers $ \pm 9$ and $ \pm 5$.

This gives you four equations from $ BC\equal{}x\plus{}y$: $ 9 \plus{} 5$,$ \minus{} 9 \plus{} 5$,$ 9 \minus{} 5$,$ \minus{} 9 \minus{} 5$ Since only $ 9 \plus{} 5 \equal{} 14$ and $ 9 \minus{} 5 \equal{} 4$ yield positive answers, you have $ 14 \plus{} 4 \equal{} 18 \implies \boxed{(D)}$
[/hide]

This was the problem that I spent maybe 10 minutes on trying to figure out why there was only one answer, eventually realizing "Oh, duh, the altitude doesn't have to be inside the triangle"

*Facepalm*

Well, here's my sol.
This is a variant of an SSA problem, so the triangle will have two solutions, the sum of the segments of BC to each altitude, and the difference of the segments of BC to each altitude.
We call the altitude to segment BC AD, where D lies on the line BC.
Doing Pythagorean Theorem, we have BD=5 and CD=9. 5+9=14 and 9-5=4.
14+4=18 [D].


vector
abstract algebra
inequalities
linear algebra
matrix
linear algebra unsolved

1. Let $ A,B \in \mathcal{M}_{n} \left( \mathbb{C} \right)$ two matrices such that $ AB\equal{}A\plus{}B$. Prove that $ rank{(A)}\equal{}rank{(B)}$.

2. Let $ A,B, X \in \mathcal{M}_{n} \left( \mathbb{C} \right), rank(X)\equal{}1$, $ rank{(A)} \leq n\minus{}2$ such that $ A\plus{}B\equal{}AB$. Prove that $ \det{(B\plus{}X)}\equal{}0$.

3. Let $ B\equal{}(b_{ij})_{1 \leq i,j \leq n} \in \mathcal{M}_{n} (\mathbb{R})$, where $ b_{ij}\equal{}p_i \cdot p_j$ with $ p_1, p_2, \dots, p_n \in \mathbb{R}$. Prove that $ A\equal{}I_n\plus{}B$ is invertible ($ \det{A} \neq 0$).

[quote="turcas_c"]1. Let $ A,B \in \mathcal{M}_{n} \left( \mathbb{C} \right)$ two matrices such that $ AB \equal{} A \plus{} B$. Prove that $ rank{(A)} \equal{} rank{(B)}$.[/quote]Show that $ \ker(B)\subset\ker(A)$ and $ \ker(A^t)\subset\ker(B^t)$.
[quote]2. Let $ A,B, X \in \mathcal{M}_{n} \left( \mathbb{C} \right), rank(X) \equal{} 1$, $ rank{(A)} \leq n \minus{} 2$ such that $ A \plus{} B \equal{} AB$. Prove that $ \det{(B \plus{} X)} \equal{} 0$.[/quote]Again $ \ker(A^t)\subset\ker(B^t)$. Using the representation $ X \equal{} q\cdot p^t$. Then show that $ \ker(A^t)\cap q^\perp$ is non-trivial to construct a non-zero vector in $ \ker((B \plus{} X)^t)$.
[quote]3. Let $ B \equal{} (b_{ij})_{1 \leq i,j \leq n} \in \mathcal{M}_{n} (\mathbb{R})$, where $ b_{ij} \equal{} p_i \cdot p_j$ with $ p_1, p_2, \dots, p_n \in \mathbb{R}$. Prove that $ A \equal{} I_n \plus{} B$ is invertible ($ \det{A} \neq 0$).[/quote]Note that $ B \equal{} p\cdot p^t$. Then use that $ \ker(A)\subset\mathbb R p$ to see that $ \ker(A)$ is trivial.

thanks for your solutions :).

Sincerely, I don't know so much about the Kernel of a linear operator :D.

I'm looking forward for more "elementary solutions" involving ranks, or something like that.

Catalin

[quote="turcas_c"]1. Let $ A,B \in \mathcal{M}_{n} \left( \mathbb{C} \right)$ two matrices such that $ AB=A+B$. Prove that $ rank A=rank B$.[/quote]

[quote="Third edition"]Show that  $ \ker B\subset \ker A$  and $ \ker A^{t}\subset \ker B^{t}$.[/quote]

$ A$ and $ B$ are $ n\times n$ matrices, therefore they represent the mappings from some $ n$ dimensional vector space $ U$ into some $ n$ dimensional vector space $ V$.

We know also that $ \dim U=\dim{ im{A}}+\dim{\ker A}$, $ rank A=\dim{imA}$ and $ rank A=rank A^{t}$.

Therefore $ \ker B\subset \ker A$ means $ \dim{\ker B}\leq \dim{\ker A} \Rightarrow \dim{im {B}}\geq\dim{im{ A}} \Rightarrow rank{B}\geq rank{A}.$ (1)

Similarly for $ \ker A^{t}\subset \ker B^{t}$ we conclude $ rank{A}=rank{A^{t}}\geq rank{B^{t}}=%Error. "rank" is a bad command.
{B}$. (2)

From (1) and (2) it follows $ rank A=rank B$.

How to show $ \ker B\subset \ker A$?

If $ x\in\ker B$, then $ ABx=A(Bx)=A(0)=0=(A+B)x=Ax+Bx=Ax \Rightarrow x \in \ker A$.

Similarly we show that $ \ker A^{t}\subset \ker B^{t}$, just that we have to use $ (AB)^{t}=B^{t}A^{t}$ and $ (A+B)^{t}=A^{t}+B^{t}$. So $ B^{t}A^{t}=A^{t}+B^{t}$.

I hope I am not wrong.

[quote="turcas_c"]2. Let $ A,B, X \in \mathcal{M}_{n} \left( \mathbb{C} \right)$, $ rank(X)\equal{}1$, $ rank(A)\leq n\minus{}2$ such that $ A\plus{}B\equal{}AB$. Prove that $ \det(B\plus{}X)\equal{}0$.[/quote]

$ \det(B\plus{}X)\equal{}0 \Leftrightarrow rank(B\plus{}X)<n$.

If $ \ker B \cap \ker X$ is non-trivial, then there exists $ x\neq 0$, such that $ x\in \ker B\plus{}X \Rightarrow \dim B\plus{}X<n$ (from the dimension equation as in the previous post).

Now we know that $ \dim \ker B\plus{}\dim \ker X\equal{} \dim {(\ker B\plus{} \ker X)}\plus{} \dim{(\ker B \cap \ker X)}$.

We also know that
$ \dim {(\ker B\plus{} \ker X)}\leq n, \dim \ker X \equal{}n\minus{}1,\dim \ker B \equal{}\dim \ker A \geq 2 \Rightarrow \dim{\ker B \cap \ker X}\geq 1.$

Hence there exists $ x\neq 0$, such that $ (B\plus{}X)x\equal{}0.$

1. I will firstly prove the followin lemma: if $ T$ is invertable then $ rank(AT) \equal{} rank(A)$, where $ A \in \mathcal{M}_n(\mathbb{C})$.

We know that $ rank(AT) \leq \min \{rank(A), rank(T)\} \equal{} rank(A)$ and from Sylvester's inequality we also have that

$ rank(AT) \geq rank(A) \plus{} rank(T) \minus{} n$ , so $ rank(AT) \geq rank(A)$.So $ rank(AT) \equal{} rank(A)$.

And now since from $ AB \equal{} A \plus{} B$ we get $ A(B \minus{} I) \equal{} B$ and since $ B \minus{} I$ is invertable, just use the above lemma.

2.From 1. we get that $ rank(A) \equal{} rank(B)\leq n \minus{} 2$ , this implies $ B^* \equal{} O_n$.Since $ rank(X) \equal{} 1$ we have that
$ det(B \plus{} X) \equal{} det(B) \plus{} Tr(B^*X)$, and from here the conclusion easily follows.

3. task:

If we show that $ \ker A$ is trivial, we are done.

We denote $ x \equal{} (x_{1},x_{2},\ldots,x_{n})$ and $ p \equal{} (p_{1},p_{2},\ldots,p_{n})$.

We study $ Ax \equal{} 0$ and get:

$ x_{1} \plus{} p_{1}(\left\langle x,p \right\rangle) \equal{} 0 \Rightarrow x_{1} \equal{} \minus{} p_{1}(\left\langle x,p \right\rangle)$
$ x_{2} \plus{} p_{2}(\left\langle x,p \right\rangle) \equal{} 0 \Rightarrow x_{2} \equal{} \minus{} p_{2}(\left\langle x,p \right\rangle)$
$ \vdots$
$ x_{n} \plus{} p_{n}(\left\langle x,p \right\rangle) \Rightarrow x_{n} \equal{} \minus{} p_{n}(\left\langle x,p \right\rangle)$

Using this in $ \left\langle x,p \right\rangle$ we get $ \left\langle x,p \right\rangle \equal{} (\left\langle x,p \right\rangle)( \minus{} p^{2}_{1} \minus{} p^{2}_{2} \minus{} \ldots \minus{} p^{2}_{n})$.

[b]1. case:[/b] $ 1\plus{} p^{2}_{1} \plus{} p^{2}_{2} \plus{} \ldots \plus{} p^{2}_{n} \equal{} 0$

But $ 1\plus{} p^{2}_{1} \plus{} p^{2}_{2} \plus{} \ldots \plus{} p^{2}_{n}$ is always greater than $ 0$, hence case 1 is not possible.

[b]2. case:[/b] $ \left\langle x,p \right\rangle \equal{} 0$

$ \Rightarrow Bx \equal{} 0 \Rightarrow Ax \equal{} Ix \plus{} Bx \equal{} Ix \equal{} x \equal{} 0 \Rightarrow \ker A$ trivial $ \rightarrow A$ invertible.

I have worked with $ x$ having dimension $ n\times 1$. If we have the matrix $ X \equal{} n \times m$, then for all $ m$ columns we can assume as above and get that $ X \equal{} 0.$

Another version of (1):

$ AB\minus{}A\minus{}B\equal{}0$ so $ AB\minus{}A\minus{}B\plus{}I\equal{}I$ or $ (A\minus{}I)(B\minus{}I)\equal{}I.$

Since $ A\minus{}I$ and $ B\minus{}I$ are inverses, they commute, and hence $ A$ and $ B$ commute.

Suppose $ Ax\equal{}0.$ Then $ Bx\equal{}ABx\minus{}Ax\equal{}BAx\minus{}Ax\equal{}0.$

By a very similar argument, if $ Bx\equal{}0,$ then $ Ax\equal{}0.$

So we were asked to show that $ \dim\ker A\equal{}\dim\ker B$ but in fact we have something stronger, namely $ \ker A\equal{}\ker B.$

Another solution for (3).

We can write:

$ B \equal{} C_1 \cdot D_1$ where $ D_1 \equal{} \left( \begin{array}{cccc} p_1 & p_2 & \dots & p_n \\
0 & 0 & \dots & 0 \\
\dots & \dots & \dots & \dots \\
0 & 0 & \dots & 0 \end{array} \right)$ and $ C_1 \equal{} \left( \begin{array}{cccc} p_1 & 0 & \dots & 0 \\
p_{2} & 0 & \dots & 0 \\
\dots & \dots & \dots & \dots \\
p_{n} & 0 & \dots & 0 \end{array} \right)$.

But we know that $ \det(I_n \plus{} B) \equal{} \det(I_n \plus{} C_1D_1) \equal{}$
\[ \equal{} \det(I_n \plus{} D_1C_1) \equal{} \left| \begin{array}{cccc} 1 \plus{} \sum_{k \equal{} 1}^n{p_k^2} & 0 & \dots & 0 \\
0 & 1 & \dots & 0 \\
\dots & \dots & \dots & \dots \\
0 & 0 & \dots & 1 \end{array} \right| \equal{} 1 \plus{} \sum_{k \equal{} 1}^n p_k^2 > 0
\]
.

I used that $ AB$ and $ BA$ have the same characteristic polynomial.

Let $ p \equal{} [p_1,p_2,...,p_n]$ when $ B \equal{} p^{T}p$ easy $ B^{2} \equal{} \parallel{}p\parallel{}^{2}B$,$ rank(B) \leq 1$,$ \parallel{}p\parallel{}^{2} \equal{} pp^{T}$
1) if rank(B)=0 (p=0)when we have prove !
2)if $ rank(B) \equal{} 1$,$ B \equal{} Tdiag(0,0,...,\parallel{}p\parallel{}^{2})T^{ \minus{} 1}$ implies $ \det(A) \equal{} 1 \plus{} \parallel{}p\parallel{}^{2}\geq 1$
from here we have calculate $ A^{ \minus{} 1}$ as $ A^{\minus{}1}\equal{}I_n\minus{}(I_n\plus{}\parallel{}p\parallel{}^2)^{\minus{}1}B$ Iedit mistake ! thanks ! :blush:
 :roll:

I use 1) $ Rank(A)\equal{}Rank(B)$ then $ Rank(B) \leq n\minus{}2$ , $ Rank(X)\equal{}1$ then $ Rank(B\plus{}X) \leq Rank(B)\plus{}Rank(X) \leq n\minus{}1$
Implies $ \det(B\plus{}X)\equal{}0$
Sorry if i am wrong !
 :spider:

Assuming [quote="turcas_c"]1. Let $ A,B \in \mathcal{M}_{n} \left( \mathbb{C} \right)$ two matrices such that $ AB \equal{} A \plus{} B$. Prove that $ rank{(A)} \equal{} rank{(B)}$.[/quote]
we see that in
[quote]
2. Let $ A,B, X \in \mathcal{M}_{n} \left( \mathbb{C} \right), rank(X) \equal{} 1$, $ rank{(A)} \leq n \minus{} 2$ such that $ A \plus{} B \equal{} AB$. [/quote]
$ rank(B) \le n \minus{} 2$. Then $ rank(B \plus{} X)$ is at most $ n \minus{} 1$, since the column space of $ B \plus{} X$ is contained in the space spanned by the columns of $ B$ and any nonzero column of $ X$. Hence  $ \det{(B \plus{} X)} \equal{} 0$.

For part 3, just compute $ A^{ \minus{} 1} \equal{} (I_n \plus{} pp^T)^{ \minus{} 1} \equal{} I_n \minus{} (1 \plus{} |p|^2)^{ \minus{} 1}pp^T$, where $ p \equal{} (p_1, \dots, p_n)^T$.


But here's a cute "counterexample" (not a real one, but sort of a counterexample :)): find an infinite poset in which all antichains are finite, but which cannot be covered with finitely many chains.

This is not a counterexample to the statement in post number $1$, because although all antichains are finite, there are antichains which are arbitrarily large.

[quote="fleeting_guest"][quote="Remike"]Does it really matter that $P$ is finite?[/quote]

No.  There is an infinite version of Dilworth theorem, as well.[/quote]
And where can I find a proof of infinite version? It's really interesting. I had been looking for the proof for some time but I found nothing.

excuse me could someone explain what is meant by "chain" and "antichain" in poset and how the statement is proven.

[quote="fleeting_guest"][quote="Remike"]Does it really matter that $P$ is finite?[/quote]

No.  There is an infinite version of Dilworth theorem, as well.[/quote]

how is this version?

[quote="billzhao"]Let $P$ be a finite poset (partially ordered set). Denote $W$ its width (the length of the longest antichain) and $L$ its length (also known as height, the length of the longest chain). Then

1) $P$ can be covered with $L$ antichains
2) $P$ can be covered with $W$ chains
3) $|P|\leq L \cdot W$[/quote]  The proof can be found [url=http://www.math.cmu.edu/~af1p/CombinatorialAnalysis/Class14.pdf]here[/url].

Is the notion of "antichain" used in Dilworth's theorm different from the notion of antichain found here:
http://www.cut-the-knot.org/pigeonhole/sperner.shtml

I have a rather dumb question:

Look here at a proof of Dilworth's Theorem:
 http://ocw.mit.edu/NR/rdonlyres/Mathematics/18-997Spring2004/FC143A49-2C1F-4653-85C4-C08A74990438/0/co_lec6.pdf

I don't understand why we have to consider two cases. I think that considering only the second case suffices.

Please tell me if this is correct. I have the hunch that I misunderstood the proof.


analytic geometry
graphing lines
slope
group theory
abstract algebra
superior algebra
superior algebra unsolved

Let $\mathcal K$ be a field of characteristic $p$, $p \equiv 1 \left( \bmod 4 \right)$.

(a) Prove that $-1$ is the square of an element from $\mathcal K.$

(b) Prove that any element $\neq 0$ from $\mathcal K$ can be written as the sum of three squares, each $\neq 0$, of elements from $\mathcal K$.

(c) Can $0$ be written in the same way?

[i]Marian Andronache[/i]

a) divide the nonzero elements into pairs $\{a, -a\}$ and choose from each exactly one number. Take their product $P$:
$P^2 = ((-1)^{\frac{p-1}{2}} P) P = \prod_{x \in K \backslash \{0\}} x = -1$, the last one by Wilson's (generalized) theorem.

b) Take a nontrivial ($xy \neq 0$) solution to $x^2+y^2=1$. Such a solution exists for $p$ big enough ($p>5$ should suffice; $p=5$ can be checked manuelly). Now any nonzero element $n$ can be written as sum of two squares:
$n=a^2+b^2$. Now this can with (when necessary two times) using of $b^2 = (bx)^2+(by)^2$ brought into what we want by $n=a^2+(bx)^2+(by)^2$.

c) for $p>5$ yes: let $P,x,y$ be defines as above, then $(Px)^2+(Py)^2 +1^2 =0$.

[quote="ZetaX"]
b) Take a nontrivial ($xy \neq 0$) solution to $x^2+y^2=1$. Such a solution exists for $p$ big enough ($p>5$ should suffice; $p=5$ can be checked manuelly). Now any nonzero element $n$ can be written as sum of two squares:
$n=a^2+b^2$.[/quote]

Why?

There are $p-1$ solutions to $x^2+y^2=1$ iff $p \equiv 1 \mod 4$ and $p+1$ solutions to $x^2+y^2=1$ iff $p \equiv 3 \mod 4$.
To see this, do the same as you do to find the rational solutions to $x^2+y^2=1$:
See this as the unit circle and draw a line with slope $\lambda$ (from the desired field, so rational or from the finite field here) through some point $P$ on the circle, lets take $P=(1,0)$.
Then the line is given by $y=\lambda x +1$, and setting this into $x^2+y^2=1$ yields $(1+\lambda^2) x^2 + 2 \lambda x + 1 =1$.
This means that either $x=0$, so $y = \pm 1$, or $(1+\lambda^2) x = - 2 \lambda$.
Now iff $\lambda^2 \neq -1$ (this is the point where the cases $\mod 4$ occure) we have $x= \frac{- 2 \lambda}{1+\lambda^2}$ and then $y = \frac{1- \lambda^2}{1+\lambda^2}$.
Conversly, for any point $(x,y)$ with $x \neq 0$ on the circle we can take the slope $\lambda = \frac{y-1}{x}$.

Now lets see (we can forget the previous part ;) ) that by
$(x,y) \to \lambda = \frac{y-1}{x}$
and
$\lambda \to (x,y) = \left( \frac{- 2 \lambda}{1+\lambda^2} , \frac{1- \lambda^2}{1+\lambda^2} \right)$
we are given a bijection between those $\lambda$ with $\lambda^2 \neq -1$ and those points $(x,y)\neq (0,-1)$ with $x^2+y^2=1$.
Thus the above result follows.

This also shows us that just using any $\lambda$ with $\lambda^5 \neq \lambda$ gives us a desired point (so already $\lambda =2$ will do most times).

To show that any $n$ is sum of two squares, we could e.g. do the same as above (well it can be simplified, but lets do it this way):
For any square $s$ itself we get $p \pm 1$ solutions (depending on $p$, the $-$ sign is the case here; but this holds for any $p$) to $x^2+y^2=s$.
For $x^2+y^2=0$ there is either one ($p \equiv 3 \mod 4$) or there are $p$ ($p\equiv 1 \mod 4$) solutions.
Since there are $p^2$ pairs $(x,y)$ and $\frac{p-1}{2}$ squares, we need just to count that there is some nonsquare being sum of two squares.
Now by $(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2$, the nonzero sums-of-two-squares build a subgroup of the multiplicative group. But since it contains more than half of the elements (all squares and at least one nonsquare), it is the whole group, done.
Additionally, one could as above find the number of solutions again, they should be the same everytime.

Your fiels does not need to have p elements. It can have $p^k$, hence there are more than $\frac{p-1}{2}$ squares.

I used $p$ for the number of elements of the field... (the properties for the characteristic are just spam, I don't think we really need them; also for the first part $p \equiv 1 \mod 4$ with $p$ being the number of elements suffices).

A much easier(I think) solution for part b:

Since $p$ is odd, we have that the characteristic of $K$ is not $2$, ie $1+1 \ne 0$. Since $2$ and $p$ are coprime, we have integers $u$, $v$ such that $2u+pv=1$, so $1+1$ is a unit. Edit: The last sentence is, of course, useless.

Denote $1+1$ by $2$ and its inverse by $2^{-1}$.

Since $2 \in Z(K)$, we can see that $(x+2^{-1})^2 = x^2+x + 2^{-2}$. By part a, we know that $-1=a^2$, with $a \in <1>$.

So $x = (x+2^{-1})^2  + (ax)^2 + ( a2^{-1} ) ^2$.

[quote="math_mat"]Since $p$ is odd, we have that the characteristic of $K$ is not $2$, ie $1+1 \ne 0$. Since $2$ and $p$ are coprime, we have integers $u$, $v$ such that $2u+pv=1$, so $1+1$ is a unit.[/quote]
Now, that you re-opened this old thread; why do you need that $2u+pv=1$ in order to get that $2=1+1$ is a unit? Since $0\neq 2 \in K$, it follows $2$ is a unit, as the entire $K^* = K \setminus\{0\}$ is made of[b] units[/b].


The value of the expression $ \frac{(304)^5}{(29.7)(399)^4}$ is closest to

\[ \textbf{(A)}\ .003 \qquad
\textbf{(B)}\ .03 \qquad
\textbf{(C)}\ .3 \qquad
\textbf{(D)}\ 3 \qquad
\textbf{(E)}\ 30
\]

[hide="Click for solution"]
Estimate each of the quantities to obtain the approximation:

$ \frac{300^5}{30(400)^4}\equal{}\frac{300}{30} \left (\frac{300}{400} \right )^4\equal{}10 \left (\frac{3}{4} \right )^4\equal{}10 \left (\frac{81}{256} \right ) \approx 10 \left (\frac{1}{3} \right ) \approx 3$, or $ \boxed{\textbf{(D)}}$.
[/hide]

[quote="AIME15"]The value of the expression $ \frac {(304)^5}{(29.7)(399)^4}$ is closest to
\[ \textbf{(A)}\ .003 \qquad \textbf{(B)}\ .03 \qquad \textbf{(C)}\ .3 \qquad \textbf{(D)}\ 3 \qquad \textbf{(E)}\ 30
\]
[/quote]

[hide="A quick approach"]

\[ \frac{(304)^5}{(29.7)(399)^4}\approx \frac{(10^2)^5}{10\cdot(10^2)^4} \equal{} \frac{10^{10}}{10^9} \equal{} 10\]

The factors of $ 3$ involved give: $ \frac{3^5}{3\cdot 3^4} \equal{} 1$.

$ 3.99$ is actually greater than $ 3$ and therefore the answer is approximately $ 10$, but not greater than $ 10$, therefore the best choice is $ \boxed{D}$.[/hide]


Given a positive integer $ m\geq 3$, and $ x(x\plus{}1)(x\plus{}2)\cdots
  (x\plus{}m)\equal{}a_{m\plus{}1}x^{m\plus{}1}\plus{}a_mx^m\plus{}\cdots \plus{}a_1x$. Obviously, $ a_{m\plus{}1}\equal{}1$,
  $ a_m\equal{}\frac{m(m\plus{}1)}{2}$, $ a_1\equal{}m!$. How to determine $ a_{m\minus{}1},  a_{m\minus{}2},\cdots
  ,a_2$ in terms of $ m$?
   If you have got a solution, please email me
miwalin@163.com


algebra
functional equation
algebra unsolved

Find $ f:R^{+}--->R^{+} $ satisfying :
 $ f(x)\geq x $ and $ f(f(x)-x)=2x $

Let $g(x) = f(x)-x.$
Then $g(x) \geq 0$ for all $x$ and the functional equation leads to $g(g(x)) + g(x) = 2x$ for all $x$. (1)
Let $a \geq 0$ be given. Let $U_n = g^n(a)$ where $g^0(a) = a$ and $g^{n+1}(a) = g(g^n(a))$. From (1), we deduce that for all $n$ we have $U_{n+2} + U_{n+1} - 2U_n = 0$.
Soving this linear relation of order 2, we deduce that $g^n(a) = U_n = b  + c(-2)^n$ for all $n$, where $b = \frac {2a + g(a)} 3 $ and $c = \frac {a-g(a)} 3 $.
Now, if $a - g(a) > 0$, choosing $n$ odd and sufficientely large we obtain $g^n(a) < 0$. A contradiction.
And if $a-g(a) < 0$ we obtain the same contradiction by choosing even and sufficientely large $n$.
Thus $a=g(a)$.
Since $a$ is arbitrary, we deduce that $f(x) = 2x$ for all $x$.

Conversely, it is easy to verify that $f(x)=2x$ is indeed a solution.

Pierre.


In the combinatorial proof for the well known formulae - $ f_{n} \equal{} f_{n \plus{} 1}f_{n \minus{} 1} \plus{} ( \minus{} 1)^n$
when we divide it into two cases for n -odd , even
for n- even,
$ f_{n} \equal{} f_{n \plus{} 1}f_{n \minus{} 1} \plus{} 1$
the book i follow proves it by tail swapping..
and for the even case i dont know why we are adding that extra one.. in both cases there is a fault free tiling( i accept) but why subtract for odd and add for even case?? i hope someone can help me..


function
real analysis
real analysis unsolved

It's a problem I've encounted while playing with maths, I don't know if it really belongs in this section...

I have a function;

$f(x) = \frac{a^x}{\displaystyle{\sum_{i=0}^{(x-1)} a^i}}$

I want to find a continuous version (if possible) of this function. I know that with Maple, when I'm writing this function;

[code]f:=x-> s^x/sum(s^i,i=0..x-1);[/code]

I can evaluate it like it was a continuous function.

The sum in the denominator can be easily found: it is $\frac{a^x-1}{a-1}$, so it is natural to extend your function to the set of real (or even complex) values of $x$ by the formula $f(x)=(a-1)\frac{a^x}{a^x-1}$.


floor function
function
combinatorics proposed
combinatorics

Quite interesting problem  problem :

Solve the following equation with an combinatorical(OR what ever the adj of combinatorics is ) argument.

[color=blue]Problem [/color]
Let $n \in \mathbb{N}$ then prove :

$\sum_{k=0}^{n} 2^k \binom{n}{k} \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor} = \binom{2n+1}{n}$

We can also calculate this sum by [b]gernarating function[/b].And we also can the similar sum as:
$A=\sum_{k=0}^n a^k\binom{n}{k}\binom{m-k}{[\frac{m-k}{2}]}$ for reals $a$,and intergers $m$and$n$.
$B=\sum_{k=0}^n \binom{k}{[\frac{k}{2}]}\binom{n-k}{[\frac{n-k}{3}]}$

i think it will work or something similar
we have $n$ pairs each consisting of one boy and one girl, and we have their teacher
we can choose from them $n$ persons in $\binom {2n+1}{n}$ ways. other way is
to choose at first $k$ pairs, then we have $2^k$ ways to choose one person from each pair, after that we choose from $n-k$ pairs $\lfloor \frac{n-k}{2} \rfloor$ and we will take now everyone from each pair, and if $k+2\lfloor \frac{n-k}{2} \rfloor=n-1$ then we will take the teacher and we have $n$ persons now

Oh,can you post a combinatorical proof for my problems?I think they must be solved by [b]Gernerating function[/b]


Well, in a bizzare display of ridiculous hope, Matt decided that he wants to know Evan O'Dorney's or Paul Christiano's perspective on the IMO this year. Last I heard, both of them made the IMO team?

Anyways, I'd love to hear some stories, or indications about the difficulty of the problems.

dude last I heard evan doesn't have an AoPS account and Paul rarely is on AoPS. Also, last I heard they are still touring in Spain :wink:

however this would be pretty cool

Last I heard, I completely detached myself from everything math-related after coming back from ARML, almost 2 months ago.

So I have no clue about the IMO & happenings at all~

The result is out:
[url]http://www.imo-official.org/results.aspx[/url]

I think he means 70th something place.

Paul got 23, Evan got 26. Both silver medals. Good job!

[quote="james4l"][quote="moogra"]Yeah and Alex Zhai got perfect score, evan got 70 something.[/quote]

Huh? the highest possible is 42.

Didn't Evan get 29?[/quote]

I meant 76th place.
Paul got a little lower ranked but I think he got a medal.
I think everyone in the US got at least an honorable mention

I outfatted the entire USA IMO team plus Matt Superdock (combined) at MOP.


limit
logarithms
parameterization
ratio
number theory

Use the prime number theorem to figure out how many prime numbers there are up to 10.

[quote="Altheman"]yes, it is something like $\lim_{x\rightarrow\infty} \frac{x}{\ln{x}} \approx$the number of prime numbers below $x$[/quote]You can write this as $\frac{n}{\ln{n}}\sim\pi(n)$.

Yes, but an answer dealing with the prime number theorem eludes me.  Why do they use $\pi$?  I mean, what does the $\pi$ notation tell use in this case?

[quote="krustyteklown"]It's an approximation and for large values, so I don't quite get the point.[/quote]

I don't want to be too pedantic, but the prime number formula is so useful because it is asymptotically correct.  The idea is that approximations usually break down as the parameters or variables become very large, but the larger $n$ is, the closer $\pi(n)$ is to $n/\ln n$.

Yea, what I meant was it wouldn't be too practical to plug in 10
What do you mean by approximations break down as stuff gets bigger?
I've always thought they get more accurate, like for example the calculated ratio of Fibonacci

But $\pi (22)\sim \frac{22}{\ln 22}$ is a bit closer to 8. So in the increasing interval, (20,22), the approximation actually gains accuracy. :D
I guess you have to think of the approximation in terms of significant figures or orders of magnitude. The difference between the approximation and $\pi(x)$ does approach 0 as n approaches infinity. Maybe someone should post the proof? I forgot how it goes. :(  :blush:

[quote="boxedexe"]I believe in the prime number theorem, the higher you go, the approximation loses is approximate accuracy.  For example:
$\pi(10)\sim\frac{10}{\ln 10}\approx 4$, however, $\pi(20)\sim\frac{20}{\ln 20}\approx 7\neq 8$.  Therefore, as $n\rightarrow\infty$, the prime number theorem loses its accuracy. :(

Masoud Zargar[/quote]

No, you are incorrect.  The prime number theorem states that

$\lim_{n\to\infty} \frac{\pi(n)}{\frac{n}{\ln n}}=1$

so, in fact, the larger $n$ gets, the better an approximation it is.  You're looking at tiny, tiny numbers and trying to draw conclusions from them - of course they're going to be wrong.  But in asymptotics, we don't care about the small cases, only the long term behavior.

Interesting.  So as n approaches infinity, it gains accuracy.  I suppose that is a good thing. :)

Okay, If you really want to have fun, see if you can prove, for $n>7$

$\frac{\ln 2} 4 < \frac{\pi(n)}{\frac{n}{\ln n}} < 30 (\ln 2)$

(The point here is one can  find two numbers  so that the ratio is always between these tow numbers, as n  tends to  infinity the  both upper and lower bounds tend to 1,)

The above is a little harder (But not too advanced, I think  for  bright high-schoolers) ,, (Notice that I have used "ln 2" to give hint(s)   for the  proof, I could have easily  used say ,  (1/6) on left hand side and 21 on the right hand side))
A much simple problem, see if you can prove  ...
$\lim_{n\to\infty} \frac{\pi(n)} n =0$

(For solutions, you can of course, look in any Number Theory  book, ask some one, surf the net etc .. as these are well known problems)


algebra
polynomial
function
Rational Root Theorem

i had 110 questions to do over the weekend and im finally almost done.i have a few questions that i cant seem to understand, i hope someone can help me!

list all the possible rational zeros of f using the rational zero theorem then find all the zeros of function.

f(x)=x^3-5x^2-14x
f(x)=x^3+4x^2+9x+36
f(x)=x^4+x^3-2x^2+4x-24

i would greatly appreciate the helpp!
thankss!

When you have $ a_{n}x^n \plus{} .... \plus{} a_{0}$
List of all rational root is divisors of $ a_{0}$, by divisors of $ a_{n}$

$ f(x) \equal{} x^3 \minus{} 5x^2 \minus{} 14x\equal{}x(x^2\minus{}5x\minus{}14)$
Rational roots $ \pm \frac {(1,2,7,14)}{(1)} \equal{} \{\pm 1,\pm 2,\pm 7,\pm 14\}$

I'm gonna let you do others  :D

Rational Root Theorem:

This states that for a polynomial $ a_b x^b \plus{} a_{b \minus{} 1} x^{b \minus{} 1} \plus{} ... \plus{} a_2 x^2 \plus{} a_1 x \plus{} a_0$, all rational roots are in the form $ \frac {p}{q}$, where $ p$ is a factor of $ a_0$ and $ q$ is a factor of $ a_b$.

For example, in the polynomial $ 3x^3 \plus{} 7x^2 \minus{} 2x \plus{} 2$ (I totally made that up) we know that [b]if the polynomial has rational roots[/b], the possible roots are: $ \frac {1}{1}$, $ \frac {1}{3}$, $ \frac {2}{1}$, and $ \frac {2}{3}$. This does not mean that ALL of these roots work, or that even ANY of these roots work. What this means is that of all the rational roots of the function, only the above four are eligible to be one. This theorem is very helpful when you are root hunting. Now you can apply this to the polynomials you have.

EDIT: darn, napoleon beat me. :)


linear algebra
matrix
modular arithmetic
algebra proposed
algebra

Let $A$ be a symmetric $n\times n$ $\{0, 1\}$-matrix with all the diagonal entries equal to $1$. Show that there exist indices $1\leq i_1<i_2 < \cdots < i_k \leq n$ such that $A_{i_1}+A_{i_2}+\cdots +A_{i_k}=(1,1,\ldots,1) \pmod{2}$, where $A_i$ denotes the $i$-th column of $A$.


abstract algebra
absolute value
algebra unsolved
algebra

In every cell of a $ 60 \times 60$ board is written a real number, whose absolute value is less or equal than $ 1$. The sum of all numbers on the board equals $ 600$.
Prove that there is a $ 12 \times 12$ square in the board such that the absolute value of the sum of all numbers on it is less or equal than $ 24$.

Denote by $ a \Box b$ the square of vertices $ (a, b)$, $ (a, b \plus{} 12), (a \plus{} 12, b)$ and $ (a \plus{} 12, b \plus{} 12)$.

Suppose by absurd there are no squares whose module of the sum of its numbers is $ \le 24$. The difference of the sums of the numbers of the square $ a \Box b$ and of the square $ a \Box b \plus{} 1$ or $ a \plus{} 1 \Box b$ is at most $ 12 \plus{} 12 \equal{} 24$ (when you "move" the square, 12 little squares are lost and 12 little squares are won, but each square makes a difference of at most 1 unit). But a difference of $ 24$ units can´t change the sign of a number keeping its module $ > 24$. So two neighbor squares have the same signs. Then all the squares have the same sign. Partitioning the $ 60 \times 60$ table in $ 25$ squares of side $ 12$ and adding the numbers on the squares, we get more than $ 24.25 \equal{} 600$. Absurd.

P.S.: I put the above comment in the Google translator and the Portuguese version was what I call "horrible". Is there any stupid English mistake here?

Other P.S.: where can I find Argentina MO 2008?


algebra
polynomial
function
domain
advanced fields
advanced fields unsolved

[quote="windowlistener"]hi ..

A function $f$ is analytic in a domain $D$ , for each point $z \in  D$ there is a non-negative integer $n_z$ s.t. $f^{n_z} (z) =0$. Show that $f$ must be a polynomial function of $z$ in $D$.

wl[/quote]

D is not countable, whence there exists a positive integer $n_z$ such that $f^{n_z}(z)=0$ for a non-countable number of $z \in D$. But $f^{n_z}$ is analytic, whence the set of its zeroes is countable, OR $f^{n_z}$ is constant. Whence it is constant, which implies that $f$ is a polynomial.

[quote="Owca"]Taylor series for $f$ will be finite in neighbourhood of a every point - isn't it enough? :oops:[/quote]

How do you prove that ?

[quote="windowlistener"]hi ..

for each point $z \in  D$ there is a non-negative integer $n_z$ s.t. $f^{n_z} (z) =0$[/quote]

... so there will be maksimum $n_z$ terms in this series...
...but I could be wrong...


The first problem: [hide]If the centers are 8 in apart and the pulley radii are 1 and 5, the closest point between the two circles is 2 in.  A taut belt stretches around 1/2 the circumferences of both circles and goes through air.  The circumference of the circles is 10pi and 2pi so combined and halved yields 6pi.  The parts that go through air form a quadrilateral with 2 right angles.  Notice that if we added a right triangle, we would have a rectangle.  A rectangle's opposite sides are the same length so the right triangle has sides 5-1=4 and 8.  4^2+8^2=80 so sqrt(80) is 4sqrt(5).  That's the length of one half of the part that goes through air because the other part goes under the wheel is the same length.  We have 8sqrt(5)+6pi.[/hide]

[quote="SirErnest"]i used to know how to do this but I forgot

A taut belt connects two pulleys.  If the pulley centers are 8 inches apart and the pulley radii are 1 inch and 5 inches, then the belt length is...

A flag in the shape of an equilateral triangle is suspended by two of its corners from the tops of two vertical poles of lengths 8 and 11 as shown.  If the third corner just touches the ground then the area of the flag is...

Sorry I don't have pictures[/quote]

Unless I'm missing something, don't we have to know how far apart are the two poles? Perhaps someone should make a diagram so I can understand it?

The second one is solvable.  Knowing the distance would trivialize it.  The key is that its an equilateral triangle.  There's probably a better way to do this cuz mine was very very messy, but I got it by calling the distance between the poles $d$ and assigning another variable to the distance from the base of the 8 pole to the point that the flag touches the ground.  Then you got 3 equal lengths by pythagorean in only 2 variables and assuming I mad no mistakes in calculations (which I probably did) I got
[hide]$\frac{97}{3}\sqrt{3}$[/hide]

I figured the first one out and I didn't get what dengmi got.  I made a line from the center of the small circle perpendicular to the radius of the big circle which is perpendicular to the cord.  That makes a rectangle.  The line just drawn, the radius of the large circle, and the line connecting the two centers forms a right triangle with hypotenuse of 8 and one leg of 4.  The other leg is 4sqrt3.  Now the circular parts are 2/3 * 10pi because that section of the arc is 240 degrees and the small circle is 1/3 *2pi because that arc is 120 degrees.

8sqrt3 + 22pi/3

i got the same as ernest for number 1

if you really did use half of the circle, the line would intersect through the circle

for number 2

hint

[hide]try and find the distance between the 2 poles in 2 ways and set them equal[/hide]


Let \[ a,b \in \mathbb{R}
\]
If the roots of the equation \[ x^2  \minus{} ax \minus{} b
\]
have absolute value less than 1 , show that the following conditions hold:\[ (i)|b| < 1,(ii)a \plus{} b < 1,(iii)b \minus{} a < 1
\]

In each case, Vieta will lead directly to the solution.


(Version 1 of my last post was wrong!)

Find all solutions if any

$ q_1,q_2,p$ be primes

$ q_1q_2 \equiv 2 \mod p$
$ (q_1\minus{}1)(q_2\minus{}1) \equiv 2 \mod p\minus{}1$

This has an infinitude of solutions but no general formula.

E.g. take $ p$ to be any prime. Let's take $ p \equal{} 11$

The first congruence $ q_1q_2 \equiv 2 \bmod 11$ has ten solutuons in residue classes, let's pick $ q_1 \equiv 1, q_2 \equiv 2 \bmod 11$
The second congruence is $ (q_1 \minus{} 1)(q_2 \minus{} 1) \equiv 2 \bmod 10$ has 20 solutions, let's pick $ q_1 \equiv 3, q_2 \equiv 7 \bmod 10$

Combining these solutions gives $ q_1 \equiv 23, q_2 \equiv 57 \bmod 110$

So we just have to pick primes from these residue classes to get solutions and by Dirichlet there are infinitely many in this case.


induction
number theory unsolved
number theory

Given integer n >= 4, find the least integer f(n) such that:
for any positive integer m, there are at least three pairwise coprime elements in every subset of {m, m + 1, ..., m + n - 1} with f(n) elements.

very good problem...
 the idea is taking the numbers mod 6. And, let g(n) be the maximum number of multiples of 2 or 3 that can be found in n consecutive numbers (i.e., g(n) = max{#multiples of 2 + #multiples of 3 - #multiples of 6} in n consecutive numbers)  For example, g(6) = 4 because we take 2,3,4,5,6,7 and 2,3,4 and 6  are four numbers multiple of 2 or 3. It is easy to see that g(6k+a)=kg(6)+g(a) = 4k+g(a).  It's clear that f(n)>g(n), because if we take g(n) numbers such that none of them is coprime with 6 then when you choose 3 of them there will be two that are both either divisible by 2 or by 3. And, we'll show that f(n)=g(n)+1. Clearly (well, not so clearly, but it's not very dificult to see this), f(4)=4, f(5)=5, f(6)=5, f(7)=6, f(8)=7, f(9)=8. Let n = 6k+a with a=4,5,6,7,8 or 9.  g(n) = 4k+g(a), and then f(n) >= 4k+g(a)+1. I want to see that this is suficient for the requiremente of the problem. We have now n consecutive numbers, and we divide them into k alfa-groups of 6 consecutive numbers and a beta-group of "a" numbers. Since there are 4k+g(a)+1 numbers in the subset we consider, then either there are at least 5 numbers from the same alfa-group, or there are at least g(a)+1 numbers from the beta-group. We will have at least f(6) numbers in a group of 6 consecutive numbers, or at least f(a) numbers in a group of "a" consecutive numbers, so by induction in that group of numbers there will be a group of 3 pairwise coprime numbers, and we are done.
 the exact solutions are, if n=6k+a with a=4,...,9, f(n)=4k+a-1 .
 please, tell me about any corrections or mistakes....

 RaMlaF...

your answer is right.
The answer can be expressed uniformly by f(n) = [(n + 1)/2] + [(n + 1)/3] - [(n + 1)/6] + 1, n >= 4. Where [x] means the largest integer not greater than x.


LaTeX
inequalities proposed
inequalities

[quote="Math pro"]find x,y such that
1.   $ x^2 \plus{} y^2 \plus{} x^2y^2 \equal{} 1 \plus{} 2xy$
2.   $ (x \minus{} 1)(xy \plus{} 1) \equal{} 1 \minus{} xy$[/quote]
Is it your  problem in $ LATEX$
I think,$ : denta$ is a useful way

[quote="Math pro"]I don't think so,denta is not useful! :D
use ineq please[/quote]
How r u using ineq on eqn.??


If an infinitely differentiable function $f : \mathbb{R} \Longrightarrow \mathbb{R}$ takes rational values at rational $x$ is it true that $f'(x)$ is rational for all rational $x$ ?
Is $f'(x)$ rational for at last one rational $x$ ?

Anyone interested in a counter example for the first question (a nice counterexample BTW) ?
Or shouldn't I "spoil" the problem so fast ?

I'm not going to get all numerical about it, but this should work (for the first question) :):

The function will be of the form $f(x)=\sum_{n\ge 1}a_n(x-q_1)\cdot\ldots\cdot(x-q_n)\ (*)$, where $(q_n)_{n\ge 1}$ is an enumeration of the rationals.

Clearly, for each $n$, we can find $\varepsilon_n>0$ such that whenever $a_n\in I_{\varepsilon_n}=(-\varepsilon_n,\varepsilon_n)$, the series $(*)$ converges absolutely for every $x$. Moreover, if we choose the $a_n$'s to be rational, we'll have $f(\mathbb Q)\subset\mathbb Q$, as desired. Now suppose we want $f'(q_1)\not\in\mathbb Q$. We have $f'(q_1)=a_1+a_2(q_1-q_2)+a_3(q_1-q_2)(q_1-q_3)+\ldots\ (**)$. This will be irrational if $a_n,\ n\ge 2$ are of the form $\frac 1{(q_1-q_2)\cdot\ldots\cdot(q_1-q_n)N_n!}$ for example, where $N_n$ are positive integers which increase fast enough to make $(**)$ a [url=http://mathworld.wolfram.com/LiouvilleNumber.html]Liouville number[/url].

P.S.

[quote="{x}"]Or shouldn't I "spoil" the problem so fast ?[/quote]

You should [i]never[/i] "spoil" a problem. There should be like a death penalty for that :).

Excellent ! This is [i]exactly[/i] (to $10^{-2}$ close) the counterexample I was thinking of. (It's even more elegant, since it does kill the two questions at once).

Does it kill the two questions at once? :? If it does, it was not my intention.

The $a_n$'s are chosen so that $f'(q_1)$ is irrational, whereas in order to get a counterexample for the second question you need $f$ such that $f'(q_n)$ is irrational for all $n\ge 1$. If this idea works for a counterexample to the second question (and I don't know if it does), it still needs work.


A train is moving forward at 2 m/s. At the instant it begins to accelerate by 0.8 m/s/s,  a passenger drops a quarter, which takes 0.5 seconds to hit the ground.

a) Relative to the spot of the floor, where does the quarter land? (in terms of toward the rear/front of the train)

b) Relative to an observer next to the tracks, where does the quarter land? (in terms of forward or backward)

[quote="OVB"]A train is moving forward at 2 m/s. At the instant it begins to accelerate to 0.8 m/s, a passenger drops a quarter, which takes 0.5 seconds to hit the ground.

a) Relative to the spot of the floor, where does the quarter land? (in terms of toward the rear/front of the train)[/quote]
From the passenger's point of view the coin falls straight down. It is in precisely the same position relative to the front/rear of the train as it was when he dropped it.

[quote="OVB"]b) Relative to an observer next to the tracks, where does the quarter land? (in terms of forward or backward)[/quote]
From the point of view of an observer beside the track, not moving with the train, the coin appears to move forward as it falls. Applying the correct kinematic equation will tell you how far the coin appears to move forward.

[quote="Kent Merryfield"]But the train is does not have constant velocity - it is accelerating.

OVB said, "At the instant it begins to accelerate to 0.8 m/s, ..."

This makes no sense. Suppose we interpret this as "At the instant it begins to accelerate [b]by[/b] $0.8 m/s^{2},$" then we can reason as follows:

To an observer on the train, the coin appears to be accelerating backwards at 0.8 m/s^2. In the half second it takes it to fall, the horizontal displacement will be $\frac12at^{2}$, or 0.1 m. The coin lands 10 cm behind the position it was dropped from.

(This ignores air resistance - the air in the train car will, more or less, be accelerating along with the train.)[/quote]

Kent,

The coin is "on the train" along with the passenger who dropped it. At the moment it is released the acceleration of the coin relative to a stationary reference frame is: $0.8\hat{i}-9.8\hat{j}\text{ m/s}^{2}$. Likewise the acceleration of the passenger relative to a stationary reference frame is $0.8\hat{i}\text{ m/s}^{2}$.  Therefore, the acceleration of the coin relative to the passenger is: $a_{rel}= a_{c}-a_{p}= 0.8\hat{i}-9.8\hat{j}\text{ m/s}^{2}-0.8\hat{i}\text{ m/s}^{2}=-9.8\hat{j}\text{ m/s}^{2}$, aka "gravity." As far as the passenger is concerned, the coin falls straight down from the point where he dropped it.

Why should the coin continue to experience horizontal acceleration after it is dropped? That would require a horizontal force to be applied to it. There is a horizontal force applied to the passenger, accelerating him. That force is applied through the contact of the passenger's feet with the floor of the train car (or of the body with a seat, if he's sitting). But the only agency capable of applying any horizontal component of force to the free-falling coin would be the air. That force is likely to be rather weak, and I chose to ignore it.

While it is falling, the coin is not "on" the train in any meaningful sense. It is true that the train's initial 2 m/s velocity with respect to the tracks is irrelevant to problem (a), as the passenger and the coin also have that initial velocity. But once the coin is released from the passenger's hand, the passenger and the coin experience differing accelerations.

Relative to the observer by the tracks, the coin does not appear to have any horizontal acceleration, but does have that 2 m/s intial velocity. From that point of view, it hits the floor 1 m ahead of where it was dropped - but by that time the passenger, who is experiencing horizontal acceleration, is 1.1 m ahead of his original position.

[quote="Kent Merryfield"]Why should the coin continue to experience horizontal acceleration after it is dropped? That would require a horizontal force to be applied to it.[/quote]
Indeed it would.  :oops: I had not considered the necessity of contact, only that the locomotive is accelerating [b]all[/b] of the train's contents -- including coins dropped by fumble fingered passengers.

d'oh! It was a components problem and I didnt think..in terms of components. Silly me. :rotfl:


search
combinatorics unsolved
combinatorics

On a given 2008x2008 chessboard, each unit square is colored in a different color. Every unit square is filled with one of the letters C, G, M, O. The resulting board is called [i]harmonic[/i] if every 2x2 subsquare contains all four different letters. How many harmonic boards are there?

[hide]Notice that, unless the first row is something like C,G,C,G,C,G,...,C,G, then the whole board is uniquely determined by the first row. Why? If the first row is not such, then there are two squares seperated by only one square that are different, like
C (something here) G. If the something here is C or G, the board will not be harmonic. Let's say the first row is CMG. Then the next row has to be GOC. It's sort of easy to see this.

But how many none-C,G,C,G,C,G,...,C,G boards can generate boards? It is easy to see it is only possible if the first row does something like repeat between elements of (C, G) and (M, O). By PIE, the number of rows with this property (and being none-C,G,C,G,C,G,...,C,G) is $ 6\cdot 2^{2008}\minus{}12\minus{}12$ There are 12 C,G,C,G,C,G,...,C,G sequences. Each time you go to a new row, there are 2 ways to choose the new row. So there are $ 12\cdot 2^2007 \equal{}  6\cdot 2^{2008}$ such harmonic boards. So there are $ 3\cdot 2^{2010}\minus{}24$ harmonic boards.[/hide]

A very similar problem appeared [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=1025088310&t=156356]here[/url] and I posted this question as a follow-up, but no one responded  :(

[quote="pythag011"][hide]Notice that, unless the first row is something like C,G,C,G,C,G,...,C,G, then the whole board is uniquely determined by the first row. Why? If the first row is not such, then there are two squares seperated by only one square that are different, like
C (something here) G. If the something here is C or G, the board will not be harmonic. Let's say the first row is CMG. Then the next row has to be GOC. It's sort of easy to see this.

But how many none-C,G,C,G,C,G,...,C,G boards can generate boards? It is easy to see it is only possible if the first row does something like repeat between elements of (C, G) and (M, O). By PIE, the number of rows with this property (and being none-C,G,C,G,C,G,...,C,G) is $ 6*2^{2008} \minus{} 12 \minus{} 12$ There are 12 C,G,C,G,C,G,...,C,G sequences. Each time you go to a new row, there are 2 ways to choose the new row. So there are $ 12*2^2007 \equal{} 6*2^{2008}$ such harmonic boards. So there are $ 3*2^{2010} \minus{} 24 harmonic boards.$[/hide][/quote]

tsk tsk tsk

a simplification
[hide]
if the first row contains more than two letters, then it's easy to see that the whole board is determined by the first row and that the first column contains only two letters, so this is exactly like the case when the first row contains two letters.  hence by inclusion-exclusion, we count $ \binom{4}{2}*2^{2008}$ twice, and then subtract out all the ways for both the first row and first column to contain just two letters, i.e. for the whole board to be uniquely determined by the top-left 2x2 square, which is 4!
[/hide]

[quote="CatalystOfNostalgia"]The Americans seem to have had an advantage on this problem...we did the similar problem at MOP.[/quote]

Indeed, I'm sure almost everyone has done this exact problem before except with different notation.

oh i find new solution but it give wrong!
my solution:
suppose the color $C,G$ new color that name is $X$ and $M,O$ new color that name is $Y$ know see that problem is change to how way we can color this chessboard so that in any 2*2 we have exactly to $X$ and to $Y$ so we have:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=877703&sid=a0af64642a02c450d04c68cdab088e0c#p877703
so we an color it in $(2^{2009})-2$way and in $4$ way we can color $X,Y$ with $M,O,C,G$ please help me!

[quote=reveryu][quote=Mosquitall]Hint  : Note that first two rows uniquely determine letters from other squares.[/quote]

I noticed that but I still confuse why counting the way its answer is4!2^2006*2^2006 is wrong.[/quote]

Because this way you also count the condition like below:

$R  G  B. ...$
$B  Y  R. ...$
$G  R$
$.   .  .$