Jump to content

Competition


Guest Sean Ash

Recommended Posts

Guest Sean Ash
http://plus.maths.org/competition/Quote: ''The competition is open to new writers of any age and from any background who can explain a mathematical topic or application they think the world needs to know about. The winning entries will be read by an international audience of over two hundred thousand in the June 2008 issue of Plus, and the winners will receive an iPod and signed copies of popular maths books by some of the best science writers today...''I have written an article for the competition which you can see at the link above. The closing date is the end of this month and I would like your opinion and welcome any constructive criticism. The interplay between proof and intuition.It is not the purpose of this article to discuss what constitutes the notion of proof but rather to explore the various ways in which the same problem or theorem can be viewed and seen. Some ways will be seen to be rigorous whilst others less rigorous yet more intuitive. Suppose we wish to prove the statement nCr+nCr+1=n+1Cr+1. In words that is to say, the sum of the number of ways of choosing r things from n and the number of ways of choosing r+1 things from n is equal to the number of ways of choosing r+1 things from n+1 things. You may recall the definition of nCr is n!/r!(n-r)! since there are n ways in which the first thing can be chosen after which, there are n-1 for each of them and carrying on in this way down to n-r+1 we obtain n(n-1)…n-r+1. We then divide this number by r! since we have already counted each way r! times. By algebraic manipulation the statement is seen to be valid, (try to verify this) however let us look at another way in which the statement is seen to be ‘naturally’ justified.First we label one of the n+1 different things as X, and notice that each of the n+1Cr+1 ways either includes or excludes X. Moreover the number of ways to choose r+1 things from n+1 including X is nCr since there are n things after we take away X from n+1 and we must select r ways so that each of these will include X. Similarly one may note that the number of ways to choose r+1 from n+1 excluding X is nCr+1 since we must still select r+1 from the remaining n. However as we noted earlier n+1Cr+1 can be split into two groups, the first including X whilst the other excluding X. The validity of the original statement is now clear since there are precisely nCr ways including X and nCr+1 ways excluding it, the sum of which is n+1Cr+1. Which argument is more appealing? Both methods are equally valid, only the latter method appears more natural and intuitive while the former seems to hide the ‘real explanation’.Let us take another example from elementary combinatorics. We wish to find the number of 5 digit numbers there are, each containing only the digits 1, 2 and 3 at least once. Rather than simply guessing at random, it should be clear that we must make use of the formula for nCr in some way. What possible ways are there to ‘see’ this problem? Well the middle 3 digits can either be one of 3 cases:1) All permutations of [1,2,3] (Note there are 3*2*1=6 permutations)2) [111], or [222], or [333]3) The possible permutations of 112, 223, 113, 221, 331 and 332 each of which there are 3 ways (by swapping the last two then the first two digits, or by noting that we simply apply the permutation formula nPr where n=r=3 and then halving the result as each permutation ‘repeats’ itself once.)Now for each of these 3 cases how many ways can the first and the last ‘spaces’ be filled? In case 1) we get 6 possible digits ([1,3] [2,3] and [1,2]) but there are 3 more ([1,1] [2,2] [3,3]) therefore (6+3)*6=54In case 2) for each, there are two ways to fill in the first and last spaces. Eg [2,3] and [3,2] in [111]. Therefore 3*2=6Lastly, in case 3) for each there are (4+1) ways. Therefore 18(4+1)=90Adding up all three cases, we get 54 + 6 + 90 = 150 which is the total number of 5 digit numbers each only containing 1,2,3 at least onceYet another way to see the problem in a slightly different light is to note that we can have one 1, two 1's or three 1's in the 5 digit number. We cannot have four 1's because then one of the other digits (2 or 3) won't be used. So, we consider the following three cases depending on how many 1's are present in each 5 digit number.Case 1) One 1: It is easy to check that only possible cases are 12333, 12233,12223 and their permutations. So, the number of ways equals 5!/3! + 5!/(2!2!) + 5!/3! = 20 + 30 + 20 = 70.Case 2) Two 1's: Again, the only possible cases are 11233, 11223 and their permutations. So, the number of ways equals 5!/(2!2!) + 5!/(2!2!) = 30 + 30 = 60.Case 3) Three 1's: The only possible case is 11123 and its permutations. So, the number of ways equals 5!/3! = 20.Adding all three cases, we get 70 + 60 + 20 = 150 which of course is the desired result.In the above, I have used the following result to count my permutations. If there are n objects such that there are a of one kind, b of another kind, c of yet another kind, and so on... (a + b + c + ... = n) then the total number of permutations (if the n objects are placed adjacent to each other in a straight line) equals n!/(a!b!c!...).It is for the reader to decide in what sense each method of calculation is more or less revealing and intuitive.I will take one last example which is a famous one. The proof of the irrationality of the square root of two. Or to put it another way, there are no whole numbers a and b such that a/b=squareroot of 2 where the squareroot of 2 is regarded as the symbol which when squared gives 2. The usual proof is by disproving the negation of the statement rather than directly proving the statement itself. We first hypothesise that the greatest common divisor of a and b is 1 so that a and b are coprime. Squaring both sides we get a^2/b^2=2 therefore a^2=2b^2. Since the right hand side is even, a itself must be even since an odd number squared is odd and every number is either odd or even. So let a=2x for some number x. Then substituting 2x for a, we get 4x^2=2b^2. By the same reasoning b itself must be even. However by hypothesis we asserted that a and b were coprime Given that all the steps we took so far are valid, and we have arrived at a contradiction, we must be forced to conclude that the square root of 2 cannot be expressed as a/b where a and b are integers.Yet in what sense should we be forced to believe that this is really the case? Well let me give another different argument. a^2=2b^2 or a*a=2*b*b ( as in the first proof)You may recall that every number can be written as a combination of prime numbers e.g. 60=2^2*3*5. Suppose that a and b are written as a product of primes so that on the left hand side we have e*e*f*f*g*g…=2*h*h*I*I*j*j… but the left hand side has an even number of prime factors whereas the right side has an odd number since 2 is ‘left out’. Therefore this is a contradiction! This result presumes that any number can be written as a unique combination of prime numbers a justification of which is as follows: Suppose that a number can be written as a combination of primes in the following two ways: a*b*c…and d*e*f… where the a,b,c,d,e,f.. are prime numbers. By hypothesis a*b*c…= d*e*f… and so we may divide both sides by a so that one of the numbers on the right hand side must be divisible by a. Let this number be d. But a and d are both prime which means the only divisors are itself and 1. Therefore a must equal d. Continue in this way….and we conclude that a=d, b=e, c=f, in other words, there is only one way to write the number as a combination of primes.Which argument was more illuminating out of the two? In my opinion, the latter argument is short and simple and compels me to believe that indeed the square root of two cannot be written in the form a/b. The former on the other hand is not as short, and is less direct in its approach.As a schoolboy mathematics was always a (boring) subject consisting of just a collection of facts to be learnt but now as a young student in my twenties, I am relearning the same facts and one of the delights is being able to see the 'same thing' in 'different ways'. Hopefully in this short article I have been able to show the various ways in which different concepts in maths can be thought about. The reader is invited to try to prove each example for himself in yet other ways.
Link to comment
Share on other sites

Guest Sean Ash

By the way the reason I am posting here is precisely because the article is intended for the lay person. Again I am looking for any constructive criticism.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...