The polynomial P(x) has the property that P(1), P(2), P(3), P(4), and P(5) are equal to 1, 2, 3, 4, 5 in some order. How many possibilities are there for the polynomial P, given that the degree of P is strictly less than 4?
(Duke Math Meet 2013 Tiebreaker round)
Discussion:
Let \[P(x) = a x^3 + b x^2 + c x + d \]
Suppose P(1), P(2), P(3), P(4) are p,q,r,s respectively. Then in matrix notation we may write:
A mathematician’s bookshelf is probably more informative than his resume.
The idea of ‘book’ has been recently challenged by the advent of technology. Outstanding authors such as Hatcher (of ‘Algebraic Topology’ fame) prefers to keep an electronic copy of his book. This electronic copy is updated from time to time.
N. B. Vasilyev was the chief architect of Mathematical Olympiads in Soviet Union. This gem from erstwhile Soviet Union’s publication, explores loci of points in plane and space. The entire discussion is aided by geometric intuition. The authors occasionally use algebraic tools to augment the ideas. The holistic nature of the discussion is truly breathtaking.
(this is a continuing write-up mostly for personal records)
Before you read on, here is what I have found curious so far (this section is constantly changing):
This concerns a computational experiment (in SAGE platform) inspired by an article by Terence Tao on Nested Approximate Subgroup.
To learn more about SAGE please visit this link.
The basic question is very simple. Suppose A is a subgroup of a group B (both finite). Say the index of A in B i.e. [B:A] = K. Hence we will get K disjoint cosets of A that partitions B.
Suppose \[s_1 A, s_2 A ,… , s_k A\] be the K cosets. Let S = {\[s_1 , … , s_k \] } Then we may write B = SA.
What happens if an arbitrary element s acts (via conjugation) on subgroup A. That is if A = \[\{ a_1 , a_2 , … , a_n \} \] and \[A^s = sAs^{-1} = \{ s a_1 s^{-1} , s a_2 s^{-1} , … , s a_n a^{-1} \} \] then how different is A and \[A^s \]?
If A is normal in B then ofcourse \[A = A^s \] (by definition of normal subgroup)
However if A is not normal then? Turns out that the group action ‘approximately’ preserves A (I am deliberately using of some Terence Tao’s remarks here).
Here we take a pause and create the first set of computation. We examine \[S_4 \] that is 24 elements, compute it’s subgroups and identify normal subgroups. Next we focus on the non normal subgroups and make elements of \[S_4 \] We conjugation on them. Finally we will compare how different the conjugated sets are from actual subgroups.
We use this little program to:
1. Compute all subgroups of \[S_4 \]
2. Compute their conjugated cosets (with each element of the main group)
3. Compute intersection of the coset with the corresponding subgroup.
4. Find the ratio of length of this intersection with the length of the subgroup
G=SymmetricGroup(4)
G1=G.list()
mag=[]
sub=[]
sub.append(G1)
for k in range(0,23):
for r in range (0,23):
if (k<r): H=G.subgroup([G[k], G[r]]) H1=H.list() z=set(H1) length=[] for x in range(0,len(sub)): y=set(sub[x]) m = y.symmetric_difference(z) n= list(set(m)) t = len(n) length.append(t) lengthmin = min(length) if(lengthmin>0):
sub.append(H1)
print “The subgroup H is”
print H1
print “\n”
coset=[]
for p in G1:
b=p
d=p**(-1)
for a in H1:
e=(b*a)*d
coset.append(e)
print “The coset %s H %s is” %(b,d)
print coset
print “\n”
intcoset = list(set(H1) & set(coset))
num = float(float(len(intcoset))/float(len(H1)))
print num
mag.append(num)
coset = []
print len(sub)
print mag
[1.0, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.25, 1.0, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.5, 1.0, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 1.0, 0.25, 0.25, 1.0, 1.0, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 1.0, 0.5, 0.5, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 1.0, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 1.0, 1.0, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.5, 1.0, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 1.0, 0.5, 0.5, 0.5, 0.5, 0.5, 1.0, 1.0, 1.0, 0.5, 0.5, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.25, 1.0, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 1.0, 0.3333333333333333, 1.0, 0.3333333333333333, 0.3333333333333333, 0.3333333333333333, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 1.0, 0.25, 0.25, 0.25, 0.25, 0.25, 1.0, 1.0, 1.0, 0.25, 0.25]
The value ‘1.0’ says the conjugated set is exactly same as corresponding subgroup. 0.25 indicates that one fourth of the values of the coset match the original subgroup.
As far as \[S_4 \] is concerned, a glance at the values reveal \[[A : A \cap A^s ] \ge 3 \] for large majority of values.
Notice apart from the trivial subgroup consisting of identity element, we have considered all remaining 29 subgroups (including the three other normal subgroups). For each of those 29 subgroups we have computed 24 conjugated subgroups, with respect to each of the 24 elements of \[S_4 \]. Thus we found \[29 \times 24 = 696 \] conjugated subgroups.
Next we found the intersection set of each of 24 conjugations with corresponding subgroups, and found the ratio of order of intersection with order of subgroup.
Among the 696 values thus found, maximum value is obviously 1 (when, conjugated subgroup is same as original subgroup). Since \[A_4, V_4 , S_4 \] are normal in $S_4$, they will generate 72 one. Among remaining 624 values, it turns out that 240 values are less than or equal to 0.33.
So for about 60% of the cases (of non -normal subgroups), \[A \] and \[A^s \] have exactly half or all the elements in common.
One may be interested in those subgroups which are different that is whose conjugations have less than 33% element in common. Question is are those 0.33 or 0.25 values distributed all over the values generated? Actually not. They come in chunks. Then definitely there are some subgroups for which the values falls below 33%
So are there some subgroups whose cojugate subgroups are ill mannered? Turns out that for \[S_4 \] there are. We revised the code found in our program to find out how each subgroup is behaving. Here is the revised code.
The result is interesting:
Examples of Ill Mannered Subgroups of \[S_4 \]
[(), (1,3,4), (1,4,3)]
[(), (1,3,4), (1,4,3)]
[(), (1,4,2), (1,2,4)]
[(), (1,3,2), (1,2,3)]
[(), (1,2), (1,4,2), (2,4), (1,2,4), (1,4)]
[(), (1,2), (1,3,2), (1,3), (1,2,3), (2,3)]
[(), (1,3), (1,3,4), (3,4), (1,4,3), (1,4)]
[(), (3,4), (2,3,4), (2,4,3), (2,4), (2,3)]
This article is aimed at entry level Math Olympiad (AMC and AIME in U.S. , SMO Junior in Singapore, RMO in India). We have complied some of the most useful results and tricks in elementary number theory that helps in problem solving at this level. Note that only with a lot of practice and conceptual discussions, you may make practical use of these ideas.
In math olympiads around the world, number theory problems have many recurring themes. One such theme is the ‘LTE’ or lifting the exponent.
Consider the two number: 37 and 52
What is the remainder when we divide 37 by 7? 2 of course. And 52 produces remainder 3 when divided by 7. Suppose we want to know the remainder when the product of 37 and 52 is divided by 7.
Pythagoras is famous. Even those who do not like mathematics, have heard of Pythagoras’ Theorem (regarding right angled triangles). He lived about 2500 years ago and did about 2500 wonderful things (well may be a little less) but all that is not the subject matter of this note. We want to talk about the shattered dreams of this famous mathematician and how the pieces of those fragmented dreams created modern mathematics. Pythagoras
Pythagoras believed numbers are omnipotent. The world that we see, the sound that we hear and even the thoughts and emotions that stir our mind are nothing but different numerical expressions of varying complexity. He even produced a theory that ‘numerified’ the world of music.
Every number, for Pythagoras, originates from 1. 1 was the all powerful number for him. You want to make a 10? Put ten 1’s together and you have it. You want to make 3.2? First put three 1’s together; that makes a 3. Then break another ‘one’ into ten equal pieces (each is then of the value 1/10 or 0.1) Put two of those pieces together with the 3 that you made earlier and behold … you have 3.2.
In this way, claimed Pythagoras, you can make ANY number under heaven.
How can you make 1/3 = 0.3333333333 (and it goes on)? That is easy! Break the piece of ‘1’ into three equal pieces and take one of them. In this way you can make 3.24, 1000, 35.123, 0.6666666 (2/3 – put the length of two 1’s side by side, break the length into three equal parts, and you have it!)
The underlying idea of Pythagoras was this: any number is a ratio of two whole numbers (whole numbers being some multiple of 1). Such was the happy world of Pythagoras where every number was invariably extractable from 1.
Then came the NEMESIS… A right angled triangle whose two sides are of one unit length and the third side….. well Pythagoras started to measure it:
He put a ‘1’ unit length on the third side of the triangle. But the side was not fully covered. ‘it is greater than 1 unit’ he thought, ‘but two sticks of 1 unit length would be a little too longer’. So he broke another ‘1’ unit long stick into into 10 equal pieces and found, to his dismay, that four pieces would be a little too short and 5 would be a little to long than the remaining portion.
The third side is then a little greater than
1+ 4* (1/10) (=1.4)
Pythagoras again took a piece of 1/10 unit length and broke it into 10 parts. Each part is now of 1/100 length. If one of those ten small sticks are added to the remaining part of the third side, a little section still remains uncovered. However if he put two of the small sticks, it would again be a little too longer.
So the third side of the triangle is a little greater than
1+ 4*(1/10) + 1*(1/100) (=1.41)
In this way he tried for some time but it was always either a little more or a little less than the length of the third side. When this practical experiment failed, he tried a mathematical trick. He assumed the third side to be m/n (where m and n are positive integers). After all possible cancellations of common factors amongst numerator and denominator let the final ratio be a/b.
Now the famous Pythagoras’ theorem says that the square of the third side is equal to the sum of the squares of other two sides. As the ‘other two sides’ of our satanic triangle are each one unit long, sum of their squares is 2 (square of 1 is 1 and add to that another square of 1 which is also 1). Hence the square of (a/b) must be 2. Hence after cross multiplication we have
a^2 = 2*b^2
Thus a^2 must be even (since 2*b^2 is a multiple of 2 hence it is even).
Then ‘a’ must be even. (If a is odd, a*a = a^2 would be odd since odd times odd is odd)
Since ‘a’ is even, a = 2*t (since 2 is factor of a)
Hence a^2 = (2*t)^2 = 4*(t^2)
Thus 4*(t^2) = 2*(b^2) or b^2 = 2*(t^2)
But then b^2 is even and hence b is even.
But this makes both a and b even which is outrageous because initially we had no common factors amongst a and b (realize that all common factors of m and n are cancelled out to make a/b).
Pythagoras was doubly puzzled. He could not accept the fact that there is no ratio whose square is 2. He could not accept this because then his theory of number would become incomplete and hence no more omnipotent. His belief, his dream about the ‘numerified’ world would be shattered. When one of his students suggested that such a ratio (whose square is 2) does not exist, he became so angry that he drowned him in the ocean.
However ideas can never be drowned. In modern mathematics, we know that a ratio whose square is 2, does not exist. In fact the number whose square is 2, can never be ‘exactly’ determined in terms of decimal expression. It is approximately 1.41421356237309504880168872420969807856967187537694807317667973799… (up till 65 digits). But it is a never ending decimal.
Clearly such a number can be found by trial. A stupid method is to check out all the numbers (at least some them) which leaves 1 as remainder when divided by 5 (we choose 5 because it is the smallest).
6, 11, 16, 21, 26, 31, 36, 41,…
The above sequence of numbers leave 1 as a remainder when divided by 5. Now the second condition is that, our required number must generate 1 as a remainder when divided by 7. Clearly that number is one of the numbers of the above sequence. We check out the remainders when divided by 7.
| Number | Remainder when divided by 7 |
| 6 | 6 |
| 11 | 4 |
| 16 | 2 |
| 21 | 0 |
| 26 | 5 |
| 31 | 3 |
| 36 | 1 (WHOA!) |
So 36 is the first number that fulfills the second condition. It leaves remainder 1 when divided by 5 as well as 13. Note that 36 is the first number with such a character. 71, 106 etc. are other numbers with such characteristic.
Anyways, we move to the third condition now. The number must leave a remainder 1 when divided by 13. A little introspection will bring the idea of product + 1 to the forefront. Note that 36 = 5*7 + 1; 70=5*7(*2)+1; 106 = 5*7(*3)+1; i.e. each of the numbers which leaves remainder 1 when divided by 5 and 7, contains 5 and 7 (as prime factors) and 1 more (rightly so!).
Therefore our required number is 13*5*7*(any number from 1 toward infinity) +1. In short we write 455k + 1 where k is any natural number.
Now we move forward with the second problem.
Find all integers that leave a remainder of 3 when divided by 5, a remainder of 5 when divided by 7, and a remainder of 7 when divided by 11.
A brain-breaker idea will be to check out all the numbers that produce a remainder 3 when divided by 5. The following is the least of such numbers.
3, 8, 13, 18, 23, 28, 33, 38,
Then we shoot the numbers of the above sequence by 7 and find that 33 is a number that produces remainder 5 when divided by 7 (33=4*7 + 5). Can we guess a second number that produces remainder 5 when divided by 7? Clearly 68 is a second number with the same feature. Lets try 1 more (and while we do this lets us ask our brain the method it is using to compute the number). 103! Yes, we add 35 to the preceeding number (we still need to REASON why this works). But before that let us assure ourselves that 103 = 5*20 + 3 and 103 = 7*14 + 5. Also we need to be convinced that when we jumped 35 we did not miss any number with 3 and 5 as remainders when divided by 5 and 7 respectively.
| Number | Remainder when divided by 7 |
| 3 | 3 |
| 8 | 1 |
| 13 | 6 |
| 18 | 4 |
| 23 | 2 |
| 28 | 0 |
| 33 | 5 |
| 38 | 3 |
| 43 | 1 |
| 48 | 6 |
| 53 | 4 |
| 58 | 2 |
| 63 | 0 |
| 68 | 5 |
| 73 | 3 |
| 78 | 1 |
| 83 | 6 |
| 88 | 4 |
| 93 | 2 |
| 98 | 0 |
| 103 | 5 |
So we did not miss any one number.Hmm, that is good.And one more observation. The remainders are repeating (3164205 3164205 … so on). We will learn later that is a beautiful (and logical) consequence of the concept of divison.
So far so good. Our brain tells us: Find the first number with the character (remainder 3, 5, 7 when divided by 5, 7, 11) and add 5*7*11 to that to find all such numbers. The challenge is however to find that FIRST NUMBER.