Author Topic: TT's Maths Thread (Read 119439 times) Tweet Share

TrueTears · « **Reply #30 on:** November 13, 2009, 01:11:55 pm »

Quote from: humph on November 13, 2009, 04:15:21 am

Here's a neat proof of 1. using matrix methods:
Consider $A = \begin{pmatrix}a & b \\ c & d \\ \end{pmatrix}$ and its transpose $A^T = \begin{pmatrix}a & c \\ b & d \\ \end{pmatrix}$ . Then
$A A^T = \begin{pmatrix}a & b \\ c & d \\ \end{pmatrix} \begin{pmatrix}a & c \\ b & d \\ \end{pmatrix} = \begin{pmatrix}a^2 + b^2 & ac + bd \\ ac + bd & c^2 + d^2 \\ \end{pmatrix} = \begin{pmatrix}1 & 0 \\ 0 & 1 \\ \end{pmatrix} = I$
where $I$ is the identity matrix. This implies that $A^T = A^{-1}$ (so $A$ is an orthogonal matrix), and so we must have that
$\begin{pmatrix}1 & 0 \\ 0 & 1 \\ \end{pmatrix} = I = A^{-1} A = A^T A = \begin{pmatrix}a & c \\ b & d \\ \end{pmatrix} \begin{pmatrix}a & b \\ c & d \\ \end{pmatrix} = \begin{pmatrix}a^2 + c^2 & ab + cd \\ ab + cd & b^2 + d^2 \\ \end{pmatrix}$
so by equating entries, we obtain the result.

(Long) Edit: /0 gave me a major hint by showing that $ad - bc = \pm 1$ , which is a necessary (but not sufficient) condition for the matrix $A = \begin{pmatrix}a & b \\ c & d \\ \end{pmatrix}$ to be orthogonal. The proof above though shows that the conditions of the question are necessary and sufficient for $A$ to be orthogonal. That is,
$\begin{array}{lll} a^2 + b^2 = 1 & \hspace{5.7cm} a^2 + c^2 = 1 \\ c^2 + d^2 = 1 & \Longleftrightarrow A = \begin{pmatrix}a & b \\ c & d \\ \end{pmatrix} \text{ is orthogonal} \Longleftrightarrow b^2 + d^2 = 1 \\ ab + cd = 0 & \hspace{5.7cm} ac + bd = 0 \\ \end{array}$

This basically follows from the fact that a $n \times n$ matrix with real entries $A$ ,
$A^T A = I \Longleftrightarrow \left \langle Au , Av \right \rangle = \left \langle u , v \right \rangle \text{ for all } u,v \in \mathbb{R}^n$ .
Here $\left \langle u , v \right \rangle = u^T v$ denotes the standard inner product of two (column) vectors $u = \begin{pmatrix}u_1 \\ \vdots \\ u_n \\ \end{pmatrix}, v = \begin{pmatrix}v_1 \\ \vdots \\ v_n \\ \end{pmatrix} \in \mathbb{R}^n$ . It is closely related to the dot product;
$\left \langle u , v \right \rangle = u^T v = \begin{pmatrix}u_1 & \cdots & u_n \\ \end{pmatrix} \begin{pmatrix}v_1 \\ \vdots \\ v_n \\ \end{pmatrix} = u_1 v_1 + \ldots + u_n v_n = (u_1, \ldots, u_n) \cdot (v_1, \ldots, v_n).$
The linearity of the inner product means that we only need to show that
$A^T A = I \Longleftrightarrow \left \langle Ae_i , Ae_j \right \rangle = \left \langle e_i , e_j \right \rangle \text{ for all } 1 \leq i,j \leq n,$
where $\{e_i : 1 \leq i \leq n\}$ is some basis for $\mathbb{R}^n$ . We can clearly choose $e_1 = \begin{pmatrix}1 \\ 0 \\ \vdots \\ 0 \\ \end{pmatrix}, \ldots, e_n = \begin{pmatrix}0 \\ \vdots \\ 0 \\ 1 \\ \end{pmatrix}$ , so that $\left \langle e_i , e_j \right \rangle = \delta_{ij}$ , where $\delta_{ij}$ is the Kronecker delta. We can then prove the result:

If $A^T A = I$ , then
$\left \langle Ae_i , Ae_j \right \rangle = (Ae_i)^T(Ae_j) = e_i^T A^T A e_j = e_i^T e_j = \left \langle e_i , e_j \right \rangle.$

Conversely, if $\left \langle Ae_i , Ae_j \right \rangle = \left \langle e_i , e_j \right \rangle$ , then
$\delta_{ij} = e_i^T (A^T A) e_j,$
which is the entry of the $i$ -th row and $j$ -th column of $A^T A$ , which implies that $A^T A = I$ .

So the original question can be restated as:
If $\delta_{ij} = e_i^T (A^T A) e_j$ , show that $\delta_{ij} = e_i^T (A A^T) e_j$ , and the result holds because both expressions are equivalent to $A$ being an orthogonal matrix. The result can clearly also be generalised to the $n \times n$ dimensional case, though of course it can't be written down so neatly.

There's also a similar problem for complex matrices; instead of considering orthogonal matrices, we consider unitary matrices. A matrix with complex entries is unitary if $A A^{*} = A^{*} A = I$ ; here $A^{*}$ denotes the conjugate transpose of $A$ , obtained by taking the transpose of $A$ and conjugating each entry.

Thus the complex version of question 1. is

$\begin{array}{lll} |a|^2 + |b|^2 = 1 & \hspace{5.2cm} |a|^2 + |c|^2 = 1 \\ |c|^2 + |d|^2 = 1 & \Longleftrightarrow A = \begin{pmatrix}a & b \\ c & d \\ \end{pmatrix} \text{ is unitary} \Longleftrightarrow |b|^2 + |d|^2 = 1 \\ a\overline{b} + c\overline{d} = \overline{a}b + \overline{c}d = 0 & \hspace{5.2cm} a\overline{c} + b\overline{d} = \overline{a}c + \overline{b}d= 0 \\ \end{array}$

(Can you tell I'm procrastinating from studying algebraic topology? )

Thanks humph! The first method is awesome but don't really understand the 2nd one lolz.

Thanks again

TrueTears · « **Reply #31 on:** November 13, 2009, 01:21:35 pm »

Quote from: /0 on November 13, 2009, 03:28:42 am

For 1. a good formula is

$(a^2+b^2)(c^2+d^2) = (ac+bd)^2+(ad-bc)^2$

But I'm not sure how to apply it yet

For 2.
The rational root theorem says a factor is $(n+1)$ , then after complete factorisation I think grouping factor pairs might work

Thanks I was figuring around with that formula for 1, getting close now.

Ahh rational root theorem, let me try fiddle around that now.

Thanks /0

TrueTears · « **Reply #32 on:** November 13, 2009, 02:30:40 pm »

Quote from: TrueTears on November 12, 2009, 09:11:30 pm

Quote from: TrueTears on November 12, 2009, 06:41:56 pm
Amazing Ahmad, thank you so much!

Also:

1. Prove that for $n \in N$

$\left \lfloor \sqrt{n} + \sqrt{n+1} \right \rfloor = \left \lfloor \sqrt{4n+2} \right \rfloor$

Where do I start with this?

2. The function $f : Z \to Z$ satisfies $f(n) = n - 3$ if $n \ge 1000$ and $f(n) = f(f(n+5))$ if $n<1000$ . Find $f(84)$
Just random brainstorming for Q 1...

Consider first the perfect squares: $\sqrt{1}, \sqrt{4}, \sqrt{9}, \sqrt{16}, \sqrt{25}...$ $= 1, 2, 3, 4, 5...$

It can be seen that the largest difference between the perfect squares is 1.

Thus for $\sqrt{n}$ and $\sqrt{n+1}$ the difference between them will be smaller than 1.

This implies that $\left \lfloor \sqrt{n} \right \rfloor = \left \lfloor \sqrt{n+1} \right \rfloor$ IFF n+1 is NOT a perfect square.

$RHS = \left \lfloor \sqrt{4(n+\frac{1}{2})} \right \rfloor = \left \lfloor 2\sqrt{(n+\frac{1}{2})} \right \rfloor = \left \lfloor \sqrt{(n+\frac{1}{2})} + \sqrt{(n+\frac{1}{2})} \right \rfloor$

kk I'm leaving this question for now, coming back to it later... brain just can't break through it rofl

Taking a different approach today:

First ignore the floor function.

Consider $\sqrt{n} + \sqrt{n+1}$ and $\sqrt{4n+2}$

After plugging in some numbers we see $\sqrt{n} + \sqrt{n+1} < \sqrt{4n+2}$

But let's prove it anyway:

Squaring both sides: $(\sqrt{n} + \sqrt{n+1})^2 < 4n+2$

$n + 2\sqrt{n(n+1)} + n + 1 < 4n+2$

$2\sqrt{n(n+1)} < 2n+1$

$4n(n+1) < (2n+1)^2$

$4n^2+4n < (4n^2 + 4n + 1)$

Which is true.

Now if we can prove that there exists no integer q such that $\sqrt{n} + \sqrt{n+1} < q < \sqrt{4n+2}$

then that means the integer parts of $\sqrt{n} + \sqrt{n+1}$ and $\sqrt{4n+2}$ are equal which implies that their floor function is also equal.

THANK YOU AHMAD FOR HELP! I GOT IT NOW!

Squaring both sides yields $(\sqrt{n} + \sqrt{n+1})^2 < q^2 < 4n+2$

$2n+1+2\sqrt{n^2+n} < q^2 < 4n+2$

$2\sqrt{n^2+n} < q^2-2n-1 < 2n+1$

$4n^2+4n < (q^2-2n-1)^2 < 4n^2+4n+1$

This is impossible since there are no integers which exists between 2 consecutive numbers! Thus no q exists!

$\therefore \forall n \in \mathbb{N}$ $\left \lfloor \sqrt{n} + \sqrt{n+1} \right \rfloor = \left \lfloor \sqrt{4n+2} \right \rfloor$

kamil9876 · « **Reply #33 on:** November 13, 2009, 03:03:13 pm »

nice solution

although the proving the inequality bit needs to be fixed up. If A implies something that is true, that doesn't neccesarily mean A is true.

I proved that inequality when I did my solution like this:

since the difference between consequtive squares increases, then that means that the difference between consecutive square roots decreases. So:
$<br />\sqrt{n+0.5}-\sqrt{n}>\sqrt{n+1}-\sqrt{n+0.5}$ (1)

since n,n+0.5,n+1 are in arithmetic progression this is true and the result follows:
$<br />2\sqrt{n+0.5}>\sqrt{n}+\sqrt{n+1}$
$\sqrt{4n+2}>\sqrt{n}+\sqrt{n+1}$

yeah in my solution I didn't explicitly use that inequality but I used some consequences of (1)

nice work

TrueTears · « **Reply #34 on:** November 13, 2009, 03:15:02 pm »

Thanks kamil ^.^

Quote

2. Find all integer solutions $(n,m)$ to $n^4+2n^3+2n^2+2n+1=m^2$

I think I got this question now.

So using rational root theorem n+1 is a factor.

Thus the polynomial can be factorised into $(n+1)^2(n^2+1) = m^2$

Now $n^2+1 = \left(\frac{m}{n+1}\right)^2$

Which means $n^2 + 1$ is a perfect square.

Let $q^2 = n^2 + 1$ where $n,q \in \mathbb{N}$

$q^2 - n^2 = 1$

$(q-n)(q+n) = 1$

since q and n are integers:

$q-n = 1$ and $q+n = 1$

or $q-n = -1$ and $q+n = -1$

Thus $n = 0$ and $q = 1$

Subbing this back in yields $1 = \left(\frac{m}{1}\right)^2$

Thus $m = \pm 1$ and $n = 0$

kamil9876 · « **Reply #35 on:** November 13, 2009, 03:20:24 pm »

TrueTears · « **Reply #36 on:** November 13, 2009, 06:24:31 pm »

Geometric interpretation of Q 1: (Thanks for hints Ahmad xD)

Consider the 2 vectors $ai+bj$ and $ci+dj$ .

These 2 vectors are unit vectors since they both have a magnitude of 1.

$(ai+bj).(ci+dj) = ac+bd = 0$

Thus these 2 vectors are perpendicular to each other at the origin.

Now since they have the same magnitude, lets rotate the vector $ci+dj$ 90 deg anticlockwise.

Thus the coordinate $(c,d)$ goes to $(-d,c)$ .

This maps exactly onto $(a,b)$ which means $(a,b) = (-d,c)$

so $a = -d$ and $b = c$

Subbing this into each of the 3 equations given gives each of the other 3 results.

TrueTears · « **Reply #37 on:** November 13, 2009, 08:42:29 pm »

Another question, where do you even start with it?

1. How many of the first 1000 positive integers can be expressed in the form:

$\left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor$ ?

I've never been good with these "how many" questions, how do you approach these questions? Do you just simply list every possibility or...?

2. Determine the triples of integers $(x,y,z)$ satisfying the equation $x^3 + y^3 + z^3 = (x + y + z)^3$

How to factorise this elegantly? Do I have to expand the RHS...?

kamil9876 · « **Reply #38 on:** November 13, 2009, 08:48:06 pm »

ahh combinatorics, one of my favourite problem solving topics

It ussually requires counting things in clever ways with patterns etc.

Unfortunately i don't have enough time atm for these questions, but I'll give you a hint, notice that the LCM of (2,4,6,8) is 24.

so when x varies from 0 to 3/24=1/8, all the terms are 0 except the last, then as you increase, to 4/24,5/24,6/24... etc. You may notice that the the value of the each individual term increases by 1 or stays constant, so theoretically if you keep going like this you will not miss any numbers , now try to look for some patterns.

e.g: the [8x] term has a period of 3 lots of 1/24, while the [6x] term has a period of 4 lots of 1/24. by period I mean how much the x has to increase to make the term increase by 1.

Over9000 · « **Reply #39 on:** November 13, 2009, 09:40:37 pm »

Sorry to hijack ur thread TT but does anyone know which books are good for beginners to number theory and stuff not too dissimilar to whats in this thread. Ive heard of the art of problem solving series of books, can anyone suggest any other books that might be helpful for a beginner like me, not too advanced.

Ahmad · « **Reply #40 on:** November 13, 2009, 09:46:56 pm »

Art and Craft of Problem Solving

TrueTears · « **Reply #41 on:** November 13, 2009, 09:49:35 pm »

Thanks for the hint kamil I think I got it now.

So let's just check $p \in [1, 24]$ and $q = 24$ where $x = \frac{p}{q}$

$\frac{1}{24}, \frac{2}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 0$

$\frac{3}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 1$

$\frac{4}{24}, \frac{5}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 2$

$\frac{6}{24}, \frac{7}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 4$

$\frac{8}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 5$

$\frac{9}{24}, \frac{10}{24}, \frac{11}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 6$

$\frac{12}{24}, \frac{13}{24}, \frac{14}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 10$

$\frac{15}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 11$

$\frac{16}{24},\frac{17}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 12$

$\frac{18}{24}, \frac{19}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 14$

$\frac{20}{24}\to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 15$

$\frac{21}{24}, \frac{22}{24}, \frac{23}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 16$

$\frac{24}{24} \to \left \lfloor 2x \right \rfloor + \left \lfloor 4x \right \rfloor +\left \lfloor 6x \right \rfloor +\left \lfloor 8x \right \rfloor = 20$

So up until the first 20 integers we recorded 12 possible results.

Thus for the first 1000 integers we require $12 \times 50 = 600$ results.

Over9000 · « **Reply #42 on:** November 13, 2009, 10:18:15 pm »

Quote from: Ahmad on November 13, 2009, 09:46:56 pm

Art and Craft of Problem Solving

Any others that could be helpful for beginners to this stuff?

kamil9876 · « **Reply #43 on:** November 13, 2009, 10:34:33 pm »

yeah TT that's my initial idea, it's the right track, however I thought about how to simplify it and here is a method.

So expanding on that idea of an increment of 1/24, let x=a/24:

y=[a/12]+[a/6]+[a/4]+[a/3]

now we want to answer this question: when a goes from a=k to a=k+1, does y increase or stay constant?

for which values of k does this happen? if a goes to k+1 and k+1 is a multiple of 3 then the last term will increase, and some others may to. if k goes to k+1 and k+1 is a multiple of 4 then the second term will increase and others may or may not. So really the only numbers where we will not increase if if k goes to some number that is either a multiply of 3 nor a multiply of 4. All such numbers are, congruent to modulo 12:

3,4,6,8,9,12.

hence we will only notice a change 6 times when a increases by 12. hence only 12 times when a increases by 24. and TT's last line follows

kamil9876 · « **Reply #44 on:** November 13, 2009, 10:49:15 pm »

Quote from: Over9000 on November 13, 2009, 10:18:15 pm

Quote from: Ahmad on November 13, 2009, 09:46:56 pm
Art and Craft of Problem Solving
Any others that could be helpful for beginners to this stuff?

Once you become a UOM student, my young paladin, you will have access to a library rich with a plethora of such books that will further entertain and nourish these intellectual thoughts. If you want specific number theory problems there are some nice newby books there too that i started with. And once you lvl up to mathematical pr0ness you can even read books by famous mathematicians on a research lvl

Search the forums now!

We have moved!

Author Topic: TT's Maths Thread (Read 119439 times) Tweet Share

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Over9000

Re: TT's Maths Thread

Ahmad

Re: TT's Maths Thread

TrueTears

Re: TT's Maths Thread

Over9000

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

kamil9876

Re: TT's Maths Thread

Recent Posts

User:
Password: