If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
Question: What are the smallest and largest multiples of 11 that are made up of the nine digits 1,2,3,4,5,6,7,8,9?
123456789
123456798
123456879
123456897
123457689
123457698
123457869
123457896
123457968
123457986
..................
..................
..................
987654312
987654321
Answer:
If $A=a_1a_2a_3a_4a_5a_6a_7a_8a_9$ is a multiple of 11, then we know the difference $(a_1+a_3+a_5+a_7+a_9)-(a_2+a_4+a_6+a_8)$ is also a multiple of 11, say $11x$.
Note that $a_1+a_2+\cdots+a_9=1+2+\cdots+9=45$ and hence $a_1+a_3+a_5+a_7+a_9=(45+11x)/2$ and $a_2+a_4+a_6+a_8=(45-11x)/2$.
Note that if $x=3$, then $a_2+a_4+a_6+a_8=6$ which is impossible. Likewise $x\ne -3$. Therefore $x$ can only be $1$ or $-1$.
Therefore either $a_1+a_3+a_5+a_7+a_9=28, a_2+a_4+a_8+a_9=17$ or $a_1+a_3+a_5+a_7+a_9=17, a_2+a_4+a_8+a_9=28$.
To get the smallest multiple of 11, we would like to see $A=12345\ldots$. Both $1+3+5+a_7+a_9=28$ and $1+3+5+a_7+a_9=17$ are impossible (the latter one is possible only if $\{a_7, a_9\}=\{2,6\}$ but we already have $a_2=6$.).
Try $A=1234\ldots$. Now $1+3+a_5+a_7+a_9=28$ is possible if $\{a_5,a_7,a_9\}=\{7,8,9\}$ (and so $\{a_6,a_8\}=\{5,6\}$) but $1+3+a_5+a_7+a_9=17$ is impossible. Therefore the smallest multiple of 11 is $A=123475869$.
To get the largest multiple of 11, we would like to see $A=98765\ldots$. Now $9+7+5+a_7+a_9=28$ is possible if $\{a_7,a_9\}=\{3,4\}$ (and so $\{a_6,a_8\}=\{1,2\}$). Thus the largest multiple of 11 is $A=987652413$.
Friday, April 19, 2013
Friday, April 12, 2013
Arithmetic sequence of primes
If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
Question: Suppose a, a+d, a+2d, ..., a+(n-1)d are primes. Find the largest possible n, under the condition that d cannot be a mulitple of 10.
a must be odd, otherwise a+2d is an even number greater than 2 and thus not a prime.
If d is odd, then a+d is an even prime greater than 2 and thus not a prime.
If d is even and not a multiple of 10, then one of a, a+d, a+2d, a+3d, a+4d have the last digit being 5 and hence it must be 5. Note that there is only one odd prime, i.e. 3, which is smaller than 5. Therefore it is only possible if a=5 or a+d=5.
If a+d=5 then a=3, d=2. The sequence is just 3,5,7.
The only case left is that a=5 and then a+5d is a multiple of 5. Therefore n is at most 5.
You can try to search using the table.
5, 11, 17, 23, 29 is a prime sequence with d=6.
5, 17, 29, 41, 53 is a prime sequence with d=12.
Therefore the largest possible n=5.
What if d is allowed to be a multiple of 10?
No matter how large n is, we can construct a sequence a, a+d, a+2d, ..., a+(n-1)d of primes. It is the famous Green-Tao theorem, proved by Ben Green and Terence Tao in 2004.
Question: Suppose a, a+d, a+2d, ..., a+(n-1)d are primes. Find the largest possible n, under the condition that d cannot be a mulitple of 10.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
(Table of primes up to 1000)Answer: Lets make a guess. We claim the largest possible n≥5.
a must be odd, otherwise a+2d is an even number greater than 2 and thus not a prime.
If d is odd, then a+d is an even prime greater than 2 and thus not a prime.
If d is even and not a multiple of 10, then one of a, a+d, a+2d, a+3d, a+4d have the last digit being 5 and hence it must be 5. Note that there is only one odd prime, i.e. 3, which is smaller than 5. Therefore it is only possible if a=5 or a+d=5.
If a+d=5 then a=3, d=2. The sequence is just 3,5,7.
The only case left is that a=5 and then a+5d is a multiple of 5. Therefore n is at most 5.
You can try to search using the table.
5, 11, 17, 23, 29 is a prime sequence with d=6.
5, 17, 29, 41, 53 is a prime sequence with d=12.
Therefore the largest possible n=5.
What if d is allowed to be a multiple of 10?
No matter how large n is, we can construct a sequence a, a+d, a+2d, ..., a+(n-1)d of primes. It is the famous Green-Tao theorem, proved by Ben Green and Terence Tao in 2004.
Friday, April 5, 2013
1, 11, 111, 1111 ....
If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
(Easter Holiday gives me another excuse to be lazy....)
A simple number theory question: Show that there is at least one (and hence infinitely many) multiples of p among 1b, 11b, 111b, 1111b, 11111b,... for all but finitely many prime numbers p. Here 11111b etc are numbers written with base b numerals.
Answer after the good-looking easter eggs :P
Let n(k)=111...1b denote the number with k 1's. Note that
n(k)=$b^{k-1}+b^{k-2}+b^{k-3}+\cdots+1$=(bk-1)/(b-1).
We claim that when p is not a factor of b, then n(k) is a multiple of p for some k.
Use factor theorem, we know that $x^{k-1}+x^{k-2}+x^{k-3}+\cdots+1=(x-1)q(x)+k$. Consequently, n(k)=k mod (b-1). Therefore if p is a factor of b-1 (and hence not a factor of b), then p divides n(b-1).
By Fermat's little theorem, we know that if p is not a factor of b, then p divides bp-1-1. Therefore if p is neither a factor of b nor a factor of b-1, then p divides n(p-1).
The claim is proved. Please note that if n(k) is a multiple of p, then so is n(2k), n(3k), and so on.
(Easter Holiday gives me another excuse to be lazy....)
A simple number theory question: Show that there is at least one (and hence infinitely many) multiples of p among 1b, 11b, 111b, 1111b, 11111b,... for all but finitely many prime numbers p. Here 11111b etc are numbers written with base b numerals.
Answer after the good-looking easter eggs :P
Let n(k)=111...1b denote the number with k 1's. Note that
n(k)=$b^{k-1}+b^{k-2}+b^{k-3}+\cdots+1$=(bk-1)/(b-1).
We claim that when p is not a factor of b, then n(k) is a multiple of p for some k.
Use factor theorem, we know that $x^{k-1}+x^{k-2}+x^{k-3}+\cdots+1=(x-1)q(x)+k$. Consequently, n(k)=k mod (b-1). Therefore if p is a factor of b-1 (and hence not a factor of b), then p divides n(b-1).
By Fermat's little theorem, we know that if p is not a factor of b, then p divides bp-1-1. Therefore if p is neither a factor of b nor a factor of b-1, then p divides n(p-1).
The claim is proved. Please note that if n(k) is a multiple of p, then so is n(2k), n(3k), and so on.
Wednesday, March 27, 2013
Permutation and Group
If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
A permutation of a permutation, is the product of the two permutations?
Right. The multiplication is not commutative, i.e in general ab≠ba. For example $$\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$$ but $$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}.$$
What happens if I keep permuting using the same permutation?
If you keep permuting with same permutation, you will eventually return to the initial configuration. For example $$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} =\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix} =\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}.$$ The identity permutation, usually denoted by (1), is the permutation that changes nothing. We know that, say, there are n objects, then applying the same permutation for n! times will always end up to be the identity permuation, i.e. $$\tau^{n!}=(1)$$
Can I say τn!-1=1/τ?
Not quite. But you can write τn!-1=τ-1, meaning that it is the multiplicative inverse of τ in the permutation multiplication.
Muliplication with an identity element and inverses. It is a group!?
Right. It is a group.
For every element α of a group G, we define a function Aα(g)=αg. It is not hard to see that Aα is a bijection and so it is a permutation. Indeed we have AαAβ=Aαβ. Hence if we identify α with Aα, we see that each element of a group is indeed a permutation of the group!
A permutation of a permutation, is the product of the two permutations?
Right. The multiplication is not commutative, i.e in general ab≠ba. For example $$\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}$$ but $$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}=\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}.$$
What happens if I keep permuting using the same permutation?
If you keep permuting with same permutation, you will eventually return to the initial configuration. For example $$\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix} =\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix} =\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}.$$ The identity permutation, usually denoted by (1), is the permutation that changes nothing. We know that, say, there are n objects, then applying the same permutation for n! times will always end up to be the identity permuation, i.e. $$\tau^{n!}=(1)$$
Can I say τn!-1=1/τ?
Not quite. But you can write τn!-1=τ-1, meaning that it is the multiplicative inverse of τ in the permutation multiplication.
Muliplication with an identity element and inverses. It is a group!?
Right. It is a group.
For every element α of a group G, we define a function Aα(g)=αg. It is not hard to see that Aα is a bijection and so it is a permutation. Indeed we have AαAβ=Aαβ. Hence if we identify α with Aα, we see that each element of a group is indeed a permutation of the group!
Friday, March 22, 2013
Permutations
If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
Permutation of n objects is just a bijection on the set of these n objects?
Right. If we don't specify the set, we means a permutation on the set {1,2,3,...,n}.
How to present a permutation?
Of course, we can present it as a bijection, e.g.
$$f(x)=\begin{cases}1 & x=1\\3 & x=2\\2 & x=3\end{cases}$$ However, traditionally we have a simpler presentation
$$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)$$ which is, I believe, self-explanatory. The lower part is the new arrangement.
Why not just write (1 3 2)?
It is because we already use this symbol for a special type of permutations-the cycles. For instance (1 3 2) refers to the permutation f(1)=3, f(3)=2 and f(2)=1, i.e. $$\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right).$$
It is easy to see cycles are interesting, mathematically?
First, we have to understand the multiplication of two permutations. If we consider two permutations $f$ and $g$ as two bijections on {1,2,3,...,n}, then their product is just the permutation $(fg)(x)=f\circ g(x)=f(g(x))$, that means if $g(r)=s$ and $f(s)=t$ then $(fg)(r)=s$. For instance, $$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right)=\left(\begin{matrix}1&2&3\\2&1&3\end{matrix}\right).$$ It is known that every permutation is a product of cycles.
So cycles are the primes for permutations?
Not quite. The transpositions (i,j), i.e. the cycles of two elements, are the primes. Every permutation can be written as a product of transpositions. e.g. $$\left(\begin{matrix}1&2&3&4&5\\3&5&4&1&2\end{matrix}\right)=(1\, 3\, 4)(2\, 5)=(1\, 4)(1\, 3)(2\, 5).$$
Permutation of n objects is just a bijection on the set of these n objects?
Right. If we don't specify the set, we means a permutation on the set {1,2,3,...,n}.
How to present a permutation?
Of course, we can present it as a bijection, e.g.
$$f(x)=\begin{cases}1 & x=1\\3 & x=2\\2 & x=3\end{cases}$$ However, traditionally we have a simpler presentation
$$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)$$ which is, I believe, self-explanatory. The lower part is the new arrangement.
Why not just write (1 3 2)?
It is because we already use this symbol for a special type of permutations-the cycles. For instance (1 3 2) refers to the permutation f(1)=3, f(3)=2 and f(2)=1, i.e. $$\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right).$$
It is easy to see cycles are interesting, mathematically?
First, we have to understand the multiplication of two permutations. If we consider two permutations $f$ and $g$ as two bijections on {1,2,3,...,n}, then their product is just the permutation $(fg)(x)=f\circ g(x)=f(g(x))$, that means if $g(r)=s$ and $f(s)=t$ then $(fg)(r)=s$. For instance, $$\left(\begin{matrix}1&2&3\\1&3&2\end{matrix}\right)\left(\begin{matrix}1&2&3\\3&1&2\end{matrix}\right)=\left(\begin{matrix}1&2&3\\2&1&3\end{matrix}\right).$$ It is known that every permutation is a product of cycles.
So cycles are the primes for permutations?
Not quite. The transpositions (i,j), i.e. the cycles of two elements, are the primes. Every permutation can be written as a product of transpositions. e.g. $$\left(\begin{matrix}1&2&3&4&5\\3&5&4&1&2\end{matrix}\right)=(1\, 3\, 4)(2\, 5)=(1\, 4)(1\, 3)(2\, 5).$$
Thursday, March 14, 2013
1=0!?
If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
(Growing lazy, not a good sign....)
I have seen a proof, saying that 1=0!?
Which one do you mean '"1=0!"?' or '"1=0"!?', uh?
You got the trick. Why do we use "!" for factorial?
I am not a historian, I don't know why Christian Kramp choose n! to represent factorial.
Why does 0!=1?
Lets first consider the definition of factorial. The n! is the number of ways to permute n objects. In the set theory language, n! is the size of the set of all bijective maps on a set of n elements.
Let A be a set. A bijective map or a bijection or a permutation is a subset F of A×A such that
On {x,y,z}, we have six permutations, right?
Yes. They are
On empty set ∅, ...?
Note that ∅ equals to and is the only subset of ∅×∅. There is no way we can violate the two conditions, and so ∅ is the bijection on ∅. Therefore 0!=1.
(Growing lazy, not a good sign....)
I have seen a proof, saying that 1=0!?
Which one do you mean '"1=0!"?' or '"1=0"!?', uh?
You got the trick. Why do we use "!" for factorial?
I am not a historian, I don't know why Christian Kramp choose n! to represent factorial.
Why does 0!=1?
Lets first consider the definition of factorial. The n! is the number of ways to permute n objects. In the set theory language, n! is the size of the set of all bijective maps on a set of n elements.
Let A be a set. A bijective map or a bijection or a permutation is a subset F of A×A such that
- For any elements a∈A, there exists a unique F(a)∈A such that (a,F(a))∈F.
- For any elements a∈A, there exists a unique F-1(a)∈A such that (a,F-1(a)∈F.
On {x,y,z}, we have six permutations, right?
Yes. They are
- (F(x), F(y), F(z))=(x, y, z)
- (F(x), F(y), F(z))=(x, z, y)
- (F(x), F(y), F(z))=(y, x, z)
- (F(x), F(y), F(z))=(y, z, x)
- (F(x), F(y), F(z))=(z, x, y)
- (F(x), F(y), F(z))=(z, y, x)
On empty set ∅, ...?
Note that ∅ equals to and is the only subset of ∅×∅. There is no way we can violate the two conditions, and so ∅ is the bijection on ∅. Therefore 0!=1.
Thursday, March 7, 2013
Cardinal Numbers
If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.
(A blog a week, keep my lazy away.... sort of)
Ordinal numbers are about order. Cardinal numbers are about quantities. In the previous post, we know what is an ordinal number. What is a cardinal number?
A cardinal number is a set of sets such that whenever we pick two sets in it, we can pair up their elements. If two sets lie inside the same cardinal number, we say that they are of the same cardinality.
For example, {a,b,c} and {x,y,z} are of the same cardinality, as we can pair up their elements as (a,x), (b,y) and (c,z).
A natural number is a cardinal number. Isn't it?
Well, we use a natural number as the representative of its cardinal number.
For example, {a,b,c} and 3={0,1,2} are of the same cardinality, and so we say that {a,b,c} has 3 elements.
So, if the elements of a set can be labelled as 0,1,2,...,n-1, then the set has n elements. Right?
Exactly. It is just our usual sense of numbers. However, we are used to label the elements with 1,2,3,...,n instead.
The first infinite cardinal number is still ω={0,1,2,3,...} ?
Yeah. Unlike ordinal numbers, 1+ω=ω=ω+1.
The sum of cardinal numbers are defined by, #A+#B=#(A×{0} ∪ B×{1}).
For example, 3+4=#{a,b,c}+#{x,y,z,w}=#{(a,0),(b,0),(c,0),(x,1),(y,1),(z,1),(w,1)}=7.
So, m+n=n+m?
Right. It is easy to see that A×{0} ∪ B×{1} and A×{1} ∪ B×{0} should have the same cardinality.
I guess the product of two cardinal numbers is (#A)(#B)=#(A×B)?
Good. For example
3×4
=(#{a,b,c})(#{x,y,z,w})
=#{(a,x),(a,y),(a,z),(a,w),(b,x),(b,y),(b,z),(b,w),(c,x),(c,y),(c,z),(c,w)}
=12.
Again, we have m×n=n×m.
(A blog a week, keep my lazy away.... sort of)
Ordinal numbers are about order. Cardinal numbers are about quantities. In the previous post, we know what is an ordinal number. What is a cardinal number?
A cardinal number is a set of sets such that whenever we pick two sets in it, we can pair up their elements. If two sets lie inside the same cardinal number, we say that they are of the same cardinality.
For example, {a,b,c} and {x,y,z} are of the same cardinality, as we can pair up their elements as (a,x), (b,y) and (c,z).
A natural number is a cardinal number. Isn't it?
Well, we use a natural number as the representative of its cardinal number.
For example, {a,b,c} and 3={0,1,2} are of the same cardinality, and so we say that {a,b,c} has 3 elements.
So, if the elements of a set can be labelled as 0,1,2,...,n-1, then the set has n elements. Right?
Exactly. It is just our usual sense of numbers. However, we are used to label the elements with 1,2,3,...,n instead.
The first infinite cardinal number is still ω={0,1,2,3,...} ?
Yeah. Unlike ordinal numbers, 1+ω=ω=ω+1.
The sum of cardinal numbers are defined by, #A+#B=#(A×{0} ∪ B×{1}).
For example, 3+4=#{a,b,c}+#{x,y,z,w}=#{(a,0),(b,0),(c,0),(x,1),(y,1),(z,1),(w,1)}=7.
So, m+n=n+m?
Right. It is easy to see that A×{0} ∪ B×{1} and A×{1} ∪ B×{0} should have the same cardinality.
I guess the product of two cardinal numbers is (#A)(#B)=#(A×B)?
Good. For example
3×4
=(#{a,b,c})(#{x,y,z,w})
=#{(a,x),(a,y),(a,z),(a,w),(b,x),(b,y),(b,z),(b,w),(c,x),(c,y),(c,z),(c,w)}
=12.
Again, we have m×n=n×m.
Subscribe to:
Posts (Atom)