Small step of logic or a giant leap of math … take your pick!

October 17th, 2004 admin

There are a 100 people trying to get onto the same flight you are. The airplane has a 100 seats. You are all ready to board. You are the last one in the line of passengers at the gate. The first guy walks in to the flight and promptly realizes that he does not have his boarding pass on him and does not remember his seat number. So he picks one at random, hoping his charm will take care of the after effects. Every one else takes their assigned seat if it is available. If someone is already sitting on it they quietly look for an empty one and sit there. By the time you get in there is only 1 seat left. What is the probability that the seat which remains is indeed the one originally assigned to you?
This problem, I heard on National Public Radio’s show called Car Talk a couple of weekends back, and immediately set to solving it. I solved it in about 15 minutes with relatively straight forward mathematics, but had the nagging feeling that the problem did not deserve the insight-less fiddling around with drone mathematics, and instead had a much more elegant and insightful, logical solution. I had to wait for the next show for the answer, which as I suspected was crisp and short. The first thing I tried to do was to get to the answer. Once I got there I would decide if I was satisfied by my method or not. This brute-fore technique meant I started with the probability the first guy got his assigned seat. Denoting that by P₁, I concluded,

P₁ = P(first guy picks his assigned seat)

= 1/100

P₂ = P(second person picks his assigned seat)

= p(first person does not pick the second person’s assigned seat)

= 1 - p(first person picks second person’s seat)

= 1 - 1/100

= 99/100

P₃ = p(third person gets his assigned seat)

= p(neither of the first two take his seat)

= 1 - p(either of the first two take his seat)

= 1 - p(first takes third’s seat OR second takes third’s seat)

= 1 - p(first takes third’s seat) - p(second takes third’s seat)

The probability that the first takes third’s seat is 1/100.

The probability that the second takes third’s seat is p(first takes second’s seat and second takes third’s seat), because second would only ever try to sit anywhere other than his assigned seat, if first has already occupied his rightful seat. Therefore this probability becomes p(first takes second’s seat). p(second takes third’s seat). The reason the probabilities get multiplied in the previous line is because the probability of first taking seconds seat is independent of the probability of second taking third’s seat once he decide to choose a random seat. p(first takes second’s seat) = 1/100 and p(second takes third’s seat)= 1/99 since second has 99 seats to choose from when he enters the plane.

continuing our equation from above

= 1 - 1/100 - 1/100.1/99

= 99/100 -1/100.1/99

= (1/100).(99-1/99)

= (1/100).(99.99 - 1)/99

= (1/100). (99 + 1).(99 - 1)/99 using P²-1 = (p+1).(p-1)

= 98/99

If we continue this lengthy procedure and keep our thoughts straight we will see that

P₄ = p(fourth person gets his assigned seat) = 97/98

P₅ = p(fifth person gets his assigned seat) = 96/97 and so on … till we find out

P₁₀₀ = p(100^th person gets his assigned seat) = 1/2

The answer is deceptively simple and has something about it that makes us wonder if this headlong dive into mathematical woods is necessary. An even stronger whiff of suspicion is leant by the seeming irrelevance of the total number of people trying to board the flight. I would have gotten a similar pattern with 50, 80, 200 or 200 million passengers. I felt sure that there was an easier way to figuring this out. I thought for a while, talked about it to a couple of my accommodating friends over lunch, and decided to wait for the answer on NPR’s “Car Talk” show hosted by Click and Clack the Tappet brothers.

Here is their version of the answer, in my words. If someone chooses the seat assigned to the first person then there will be no more need for any seat exchanges. If someone chooses your seat (you are the last one to get on the plane), your probability to get the seat assigned to you is 0. Lets think about the first assertion. If the first person sits by chance on his assigned seat, passengers 2,3,4 … 100 will not notice any problem and will sit on their assigned seat. Say passenger 1 sits on some other seat say number n. The first passenger to note a problem will be passenger assigned seat n. Up until that point all passengers happily seat themselves into their assigned seats. Say passenger assigned to n sits on a seat numbered m, the a similar logic applies and only passenger assigned to m, will notice a problem. If any of these passengers who choose a seat randomly, choose seat originally assigned to passenger 1, no one after them will notice any problem, since the only person who could have noticed a problem is passenger 1 himself who is already seated. Therefore a subset of the total number of passengers will make a decision to choose a seat at random. If they choose the seat assigned to person 1, you are guaranteed to get your seat. If they choose the seat assigned to you, you are guaranteed to not get your seat. To a person choosing a seat at random, your seat is no different that the first person’s seat. So irrespective of the number of people (both total and one’s who have to choose), it’s just a matter of is your seat chosen first or is the first person’s seat chosen first. Therefore due to the symmetry in the argument the answer is 1/2.

Posted in Tidbits | No Comments »

2’s Complement, and the trick to negate it

October 15th, 2004 admin

“2’s complement” is an often heard phrase in the world of computers. It is a notation used to represent numbers to ease subtraction. The intuitive binary number notation only stays positive, adding higher powers of 2 to the number as you keep adding 1’s to the left of a number. The most intuitive way to denote a negative of a number is to place a “-” symbol to its left. So if in decimal -5 is negative of 5, why can we not live with -101 for negative 101 (101 is binary for decimal 5) in binary? We can, but this “-” symbol is an abstraction useful to think about the number. A computer, which can only identify a 1 or a 0 (a high or a low voltage), needs to represent the “-” symbol using a trick.The easy trick would be to have an understanding that the first bit of any binary-represented number would indicate if the number is positive or negative. So if a number starts with 1, that indicates that treat the rest of the number as a positive binary number and negate it. If the number starts with a 0 that indicates that the number is positive. Unfortunately every sane number starts with a 1. If a number starts with a 0, the 0 is simply ignored (not to mention it looks strange). So to represent decimal 5 as 101 is fine but to represent it as 0101 looks a little odd. So then the way to make this first-bit-1-for-negative scheme work we need to associate a place value for the sign-representing leftmost digit. So say we want our number system to be capable of representing all numbers from -12 to 12, we will need to use 4 bits at least, for 12 is 1100. And then we can say the fifth bit from the right will be used to represent sign. So 12 becomes 01100 and -12 becomes 11100. And one that fact is made understood 5 represented as 00101 does not look as questionable. This scheme has two representations for 0, 00000 and 10000. In this scheme therefore, out of the 32 unique arrangements possible using 5 bits, 15 represent positive numbers, 15 represent negative numbers and there are 2 representations for 0. This scheme is called the sign-magnitude representation.

Yet another way to represent the fact that a number is negative would be to again have an understanding that the number is a represented using a fixed and predetermined number of bits, the left most bit being 1 indicates negative and being 0 indicates positive, and that the way you flip a positive number is to flip each of its individual bits. The positive number starts off with a 0 as its highest order bit, by definition, and therefore the flip of all the bits flips this bit too and makes it negative. The fact that for every pattern of bits there is a unique flipped pattern, guarantees that we have a unique negative number for each positive number, that can be easily identified. So if we say we will use 5 bits to represent a number and 5 is 00101, -5 is 11010. How we recognize 11010 to be -5 is we notice the “-” from the first bit and notice the 5 by flipping the bits back and calculating the resulting value in decimal. Only one small glitch is that this representation provides two equally acceptable versions of 0, namely 00000 and 11111 (since 0 = -0). So at another level of abstraction, this just means that out of the 32 different patterns possible using 5 bits, this scheme has 15 positives, 15 negatives and 2 0’s. This scheme is called 1’s complement representation.

2’s complement is another notation where the first or leftmost bit actually represents a negative offset. The remaining bits work the same way as for normal positive binary numbers. So in the most intuitive notation, 101 means 1*2² + 1*2⁰, or 5, and in the 2’s complement notation 101 means -1*2² + 1*2⁰, or -3. This representation has a unique representation for 0 (00000) and a unique representation for 15 positives, and 16 negatives! That is because 10000 means -16! There is therefore no duplication and the 32 variations of the 5 bits represent 32 unique numbers. Instead of 3 bits say we want to use 4 bits to represent 5. 5 would then be represented as 0101.But what about -3? The leftmost bit needs to be 1 to give the number a negative offset. The offset is -2³ and that is -8. So to get the end value to be -3 we need the remaining three bits to value +5. So -3 in 4 bits is 1101. And this indicates the phenomenon called sign bit extension. 101 is -3 and extending the sign bit (the most significant bit) on the left by repeating it makes the number 1101, which still is -2! In 2’s complement notation, in general the sign bit may be extended to the left (i.e. repeated on the left) without changing the value of the number.

The trick to negate a 2s complement number is often taught as “flip all bits and add a 1″. What is happening here? Let’s give it a shot first. 3 is 011 in 3 bit 2’s complement representation. Flip the bits and we get 100. Add a 1 and we get 101, which we saw earlier was 2’s complement representation for -3. Why this works is pretty straightforward once we see what’s going on. When the bits of an n bit positive number N are flipped essentially we end up with a number of value 2ⁿ - N. Why?

N = 0 x_n-2 x_n-3 . . . x₀ (where x_i is 1 or 0)

-2^n-1 2^n-2 2^n-3 . . . 2⁰ (corresponding power of 2)

= 0.(-2^n-1) + x_n-2.2^n-2 + x_n-3.2^n-3 . . . + x₀.2⁰

= x_n-2.2^n-2 + x_n-3.2^n-3 . . . + x₀.2⁰

N’ = N flipped

= 1 x_n-2‘ x_n-3‘ . . . x₀‘

-2^n-1 2^n-2 2^n-3 . . . 2⁰ (corresponding power of 2)

= 1.(-2^n-1) + x_n-2‘.2^n-2 + x_n-3‘.2^n-3 . . . + x₀‘.2⁰

N + N’ = 1.(-2^n-1) + (x_n-2+x_n-2‘).2^n-2 + (x_n-3+x_n-3‘).2^n-3 . . . + (x₀+x₀‘).2⁰

= 1.(-2^n-1) + 1.2^n-2 + 1.2^n-3 + … + 1.2⁰

= 1.(-2^n-1) + (2^n-1 - 1)

That last reduction essentially is based on the observation that 111₂ = 1000₂ - 1 and so on.

Therefore

N + N’ = -1

Therefore rearranging,

N’ + 1 = -N

Posted in Tidbits | No Comments »

Becoming a rememberer -an aid to remembering annually recurring events … like birthdays.

July 17th, 2004 admin

Here is a miraculous solution to the age old problem of forgetting birthdays and anniversaries. A perl script that can send you email every morning about what’s coming up for the next week, so not only do you remember, but you have enough time to set up something special … like a surprise birthday cake!
OK enough of the introduction. Essentially it is a simple perl script that I run on my Unix machine. At it has already proven its worth. So this is for those of you who are looking for a similar tool.

#!/usr/bin/perl
#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

#Written by: Anil Krishna

#On: July 10th 2004

#Purpose: This perl script sends an email to a given address, with a listing of events that are going to happen in the nesr future. The “nearness” is described by a variable called $warnZone in the script.

#Dependency: This program needs a dateslist.txt file to contain the dates and corresponding events.
#The dateslist.txt file should contain the dates in the following format for this perl script to work right.
#month_in_digits date_in_digits String Describing the event
#example:
#1 1 New Year’s
#8 15 India’s Independence
#8 15 bright’s Birthday; email address: bright@tubelight.com

#Usage: To use this script, create the dateslist.txt file. You can add to it as appropriate. Set the $from and $to variable to point to appropriate addresses. Set the $warnZone to any other number if you want. Right now it is set to 7, which means the program will warn you about events happening in the next 7 days (including today). And you would likely want to run this program with some regularity. I run this program once a day. The way I automate that is by creating a crontab entry in a Unix machine where I store these files. Crontab is a table where you can specify time periods for autoamtically having the system run executable programs such as this one. The way it typically works is do a “crontab -e” call on your Unix machine. It will open up a file for you to edit (using the system’s default text editor. Type in the following command to have it run the program every morning at 6 AM. “0 6 * * * ~/date.pl”. What this is saying is at 0 minutes, 6 hours, every day of the month, every month, every day of the week, run ~/date.pl. You would have to change the path to this perl script according to where it is located on your Unix machine. You could also choose to run this script only every Thursday midnight, by doing this to the crontab, “0 0 * * 4 path/to/your/foleder/file.pl”. By the way, just as “crontab -e” lets you edit the crontab, “crontab -l” lists the current crontab entries.

#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

#find today’s day of month (mday) and month (mon)
($sec, $min, $hour, $mday, $mon, $year, $wday, $yday, $isdst) = localtime (time);

#day of year = yday+1 (since the count starts from 0 in perl)
$today_doy = $yday+1;

#array defining days in months, and variable defining num days in year
if($year%4 == 0){
@dpm=(31,29,31,30,31,30,31,31,30,31,30,31);
$daysThisYear = 366;
}
else{
@dpm=(31,28,31,30,31,30,31,31,30,31,30,31);
$daysThisYear = 365;
}

#read the entries in the table of dates and see if there is any that is close. Close is defined as being within nearEnough (defualt 7) days.
$warnZone = 7;
open(DATES,”dateslist.txt”) or die “dateslist.txt could not be opened \n”;
while ($line = )
{
($event_month, $event_dateInMonth, @event) = split(” “, $line);
$event_doy=0;
for($i=1;$i<=$event_month;$i++){
if($i<$event_month){
$event_doy += $dpm[$i-1];
}
else{
$event_doy += $event_dateInMonth;
}
}
$proximity = $event_doy-$today_doy;
#if the event is in the same year as today then proximity is positive, and its being withing the warnZone is good enough.
#if the event is in the next year, then proximity return a negative value. daysThisYear + proximity indicate the real proximity of the event, and its being withing the warnZone is good enough.
if( ($proximity >= 0 && $proximity <= $warnZone) || ($proximity < 0 && $daysThisYear + $proximity <= $warnZone ) )
{
$content .= “@event on $event_month/$event_dateInMonth \n”;
}
}

#send email with the above collected content content.
use Net::SMTP;
$from = “krishnaa\@us.ibm.com”;
$to = “mvvak\@yahoo.com”;
$subject = “Important Upcoming Dates”;
$relay = “ladodger.raleigh.ibm.com”;
$smtp = Net::SMTP->new($relay) || die “Can’t open mail connection: $!”;

$smtp->mail($from);
$smtp->to($to);
$smtp->data();
$smtp->datasend(”To: $to\n”);
$smtp->datasend(”From: $from\n”);
$smtp->datasend(”Subject: $subject\n”);
$smtp->datasend(”\n”);
$smtp->datasend(”$content\n”);
$smtp->dataend();
$smtp->quit();

Posted in Tidbits | No Comments »

Swapping or a circular shift without temporary storage

May 10th, 2004 admin

Normally, when you want to swap (exchange the values of) two variables, the most intuitive way is to store the value of one in a temporary variable. Overwriting the safely-stored variable’s value with the other one. And then overwriting the other variables value with the stored variables value. At this point since the swap is done the temporary variable may be deleted.
An interesting, thought provoking and equally symmetric way of doing the same action, without the use of a temporary storage is by using the bitwise XOR operation. The way it works is:

x = x xor y
y = x xor y
x = x xor y
How this works is seen upon a minor expansion of the above three statements, and with a faith in the associativity of the XOR operation (basically that means you can change the order of the operands being operated upon by the XOR operator).
x = x xor y
y = x xor y , but the vaule of x is now x xor y from the first statement. Therefore
= x xor y xor y
= x xor 0, since y xor y = 0
= x
x = x xor y
= (x xor y) xor x
= x xor x xor y
= 0 xor y
= y
Taking the same logic one step further, you can actually make cyclic moves of variable values. What I mean by that is, if you have A, B, C … N, then using the same principle, we can move the value of variable A into B, the original value of B into C, and so on till finally the original value of variable N moves into A. The way this would work is

A = A xor B xor C xor … xor N
B = A xor B xor C xor … xor N
C = A xor B xor C xor … xor N
.
.
.
N = A xor B xor C xor … xor N
These N+1 statements achieve the required effect. The only glitch here is that we might have been better off using one temporary variable and be done with much shorter statements that do not require all the variables in every statement. So the intuitive way might work better for example in a microprocessor where the system resources are critical and run time is dependent on the number of operands. The intuitive way is
Temp = N
N = M
.
.
.
C = B
B = A
A = Temp

Posted in Tidbits | No Comments »

Big-Endian and Little-Endian Storage Schemes - How to remember …

May 8th, 2004 admin

Computer systems today primarily store “words” of data in either Little or Big Endian format, in the physical memory. By “word” I mean a piece of data that is larger than a byte. Typically a word is defined as 2 or 4 bytes, and halfwords, double words, quadwords are extrapolations thereof. Intel machines store data in their memory, in Little Endian format and IBM PowerPC architecture stores data in Big Endian format. The differences are critical when writing a compiler or when transferring a piece of data written for one system to another.
Simple way to remember is: Little Endian means, the little end (least-significant byte) of the multi-byte word goes into memory first. First here means a lower memory address. And Big Endian is vice-versa.

Infact, the origin of these words is from Jonathan Swift’s Gulliver’s Travels, where in the Lilliput kingdom, a decree by the King, that eggs be broken from the little side, caused a rebellion by a faction called the Big Endians, who were used to breaking their eggs from the bigger end.

Posted in Tidbits | No Comments »

Some simple summations

April 12th, 2004 admin

Old problems are sometime good to sit and ponder because you know that the solution is not beyond you, but at the same time you can challenge yourself to get back into the frame of mind of thinking about these issues. One such problem is the summation
1 + n + n(n-1)/2 + n(n-1)(n-2)/2.3 + … + n + 1
Do you know of a way to reduce this? How about using plain algebra?

Sum of all fears or fear of some sums

I love my work at IBM, when it leads an unsuspecting me around a boring corner, and brings me before a teasingly recognizable view … a pattern which you know you have seen before, but never expected to see here. And a little staring and thinking brings back a feared-forgotten world of wonderfully rich supporting mathematics. I was reading up a paper on RAID (Redundant Array of Inexpensive Disks) Technology, when I was led into thinking about this problem.
I want to prove that
ⁿC₀ + ⁿC₁ + ⁿC₂ + … + ⁿC_n = 2ⁿ
Mind the direction, it goes from the summation to the single term. After toiling with it for a while I sent out a note to my IIT Guwahati egroup and recieved the expected enthusiasm for not just finding the solution, but raising new sub-questions. Here I will provide some intersting points that came out of the discussion and the three ways of proving the equality. The one I was after in particular, a purely algebraic way of getting from LHS (left hand side) to RHS (right hand side), still eludes me.
I had figured out that proving the LHS, starting out from the RHS is easy.
2ⁿ = (1+1)ⁿ = ⁿC₀ + ⁿC₁ + ⁿC₂ + … + ⁿC_n, by the binomial expansion. Interstingly enough this gives rise to another question. How do you show that the binomial expansion is correct? What is the binomial expansion saying? And what is all this ⁿC_k business?

Many of my friends suggested the mathematical induction approach to the problem. That is show that for the trivial case it holds. That is, say n=1.
¹C₀ + ¹C₁ = 2 = 2¹
Let us say it holds for n = k. That is,
^kC₀ + ^kC₁ + ^kC₂ + … + ^kC_k = 2^k
Then what happens when n = k+1? If we can show that the equality still holds, we would have proven the equality by mathematical induction.
LHS would now look like,
^k+1C₀ + ^k+1C₁ + ^k+1C₂ + … + ^k+1C_k+1
Taking a general term in this series to be ^k+1C_l, we can simplify that term using the definition of ⁿC_k.
^k+1C_l = (k+1)!/l! . (k+1-l)!
= (k+1) . k!/(k+1-l) . (k-l)! . l!
= [(k+1)/(k+1-l)] . ^kC_l
= [1 + l/(k+1-l)] . ^kC_l
= ^kC_l + [l/(k+1-l)].^kC_l
= ^kC_l + [l/(k- l+1)].^kC_l
= ^kC_l + [l/(k- l+1)].[k!/l! . (k-l)!]
= ^kC_l + k!/(l-1)! . (k-l +1)!
= ^kC_l + k!/(l-1)! . (k- (l-1))!
= ^kC_l + ^kC_l-1
Thus using this breakdown for every term from the second to the second to last,
^k+1C₀ + (^kC₁ + ^kC₀) + (^kC₂ + ^kC₁) + … + (^kC_k + ^kC_k-1) + ^k+1C_k+1
Separating the first and second terms in the bracketed pairs, and the first and last term into two groups
[^k+1C₀ + ^kC₁ + ^kC₂ + … + ^kC_k] + [^kC₀ + ^kC₁ + … + ^kC_k-1 + ^k+1C_k+1]
Since the first term in the first bracket and the last term in teh second bracket sum are same as ^kC₀ and ^kC_k respectively, we effectively have
[^kC₀ + ^kC₁ + ^kC₂ + … + ^kC_k] + [^kC₀ + ^kC₁ + … + ^kC_k-1 + ^kC_k]
which from our assumption step in the induction process, is
2ⁿ + 2ⁿ
= 2ⁿ⁺¹

Another way to prove the same idea is to show that LHS and RHS describe the same thing. This is like showing LHS = X and RHS = X, so LHS = RHS. Instead of getting very formal about the proof, I will stick to a light hearted example here. I am repeating the example I wrote in our egroup discussion, as is …
Lets say Anupam Singh comes back home after a hard day at work. Then he decides to go play pool with Nadeem sahab. After getting beaten badly multiple number of times, he decides to give up. He puts all the pool balls (numbered 1 to 15) into his backpack and says enough is enough. He is ready to go back home. Nadeem, being the smart alec he is, tells him, I want to play so give me the balls back. Anupam Singh says OK I will put my hand into the backpack, and take out whatever I choose to take out. You will get only those balls to play with. Obviously Nadeem has no clue how to play pool with less than 15 balls (forget the cue ball for now, that is supplied by CK). So suspecting foul play he says, “You can’t trick me. You will keep taking out fewer balls everytime.”. Anupam says, “OK, I will promise you this, I will take out a different set of balls every time. So eventually you will get all the 15 balls out and then you can play with them all.” Nadeem being the innocent smart alec that he is, says OK. (CK is meanwhile way ahead of the game, for he has already calulated in his notebook that Nadeem is done for the night). How many times can Anupam Singh take a unique combination of balls out of his backpack before he finally has to take them all out?
He can take out nothing at all the first time. He then has to take out at least one ball the next time. In order to not repeat a combination, he can choose each single ball once, making that 15 (or n) times. He can choose 2 out of the 15 in ¹⁵C₂ ways. When he decides to take out only 3, he can do that ¹⁵C₃ ways… by next morning, he has exhausted the following number of options.
¹⁵C₀ + ¹⁵C₁ + ¹⁵C₂ +… ¹⁵C₁₄… and so finally he decides to take out all the 15 in ¹⁵C₁₅ =1 way.
Looked at another way, every time Anupam Singh draws out a combination from the bag, he either takes out ball no. 1 or does not, either takes out ball no. 2 or does not , … ,either takes out ball no. 15 or does not. This means there are 2 possibilities for ball 1 AND 2 possibilities for ball 2 AND …2 for ball 15. i.e, there are 2^15 ways of doing this not-so-intelligent a deal. So therefore, ¹⁵C₀ + ¹⁵C₁ + ¹⁵C₂ +… ¹⁵C₁₅ = 2¹
LHS leads to RHS. No induction.
If you know how to solve it directly from LHS to RHS using simple algebra, I would appreciate your pointers to it.

Binomial Expansion

The way I think about binomial expansion is this way.
Lets say, taking a pretty general case, you want to expand
(a+b)ⁿ
= (a+b)(a+b)(a+b)…(a+b) with n terms. Call this equation 1.
This can be written as a SUM of products. These product terms should basically satisfy the following property. They should be all the various products of a’s and b’s such that the total number of a’s and b’s are n. Why? Because you are trying to go to each bracketed pair in the above equation 1 and picking either the a or the b from the (a+b). There is no other go. You have to choose either of the two from every term. And no two product terms should pick the exact same sequence of a’s and b’s. Meaning if you have chosen aabbbbbbb (as an example with n=7) you can not choose aabbbbbb again, though you can choose abbbbbba, which effective shows that there are repeating terms in the sum of products form of equation 1. (Actually that sum of products is the binomial expansion)
So the terms can be only of the following types
all a’s (aaaaaaa for the case n=7)
n-1 a’s and 1 b (aaaaaab, aaaaaba,… etc)
n-2 a’s and 2 b’s … and so on till
all b’s
This means all we need to do is figure out how many terms of each product there are (since we saw earlier that there can be multiples).
How many “all a’s” terms? How many ways can you choose no b’s (all a’s) from the n (a+b) terms in equation 1? ⁿC₀ ways.
How many “n-1 a’s and 1 b” terms? How many ways can you choose 1 b from n (a+b) terms in equation 1? ⁿC₁ ways.
And so on.
So the sum of products becomes
ⁿC₀. aⁿ + ⁿC₁. a^n-1. b + ⁿC₂. a^n-2.b² +…+ ⁿC_n. bⁿ
BTW, ⁿC₀, ⁿC₁ are by definition “number of ways to choose 0 or 1 out of n” To prove the ⁿC_k = n!/(k!.(n-k)!) is another interesting but simple problem.

What is ⁿC_k? Why is ⁿC_k = n!/(k!. (n-k)!) ?

Say you have n balls labeled 1 through n. And you have to choose k balls, with no importance given to the order of choosing. The numbers of unique ways you can choose, provided the order of choosing is unimportant, only the set chosen is important, is called “n choose k” and denoted by the shorthand notation ⁿC_k.
You can choose the first ball in n ways, because you have n to choose from from the first ball. Once you choose the first ball, you have only n-1 remaining (since you cannot choose the first ball again). You’ll have n-2 choices to choose the third ball and n-(k-1) ways to pick the k^th ball. You wanted k balls. So there are
n ways to choose the 1^st AND you have n-1 ways to choose the 2^nd AND … n-(k-1) ways to choose the k^th ball.
= n.(n-1).(n-2).(n-3)…(n-(k-1))
= n.(n-1).(n-2).(n-3)…(n-(k-1))[(n-k)(n-k-1)…3.2.1]/[(n-k)(n-k-1)…3.2.1]
= n!/(n-k)!
But we have overlooked an important fact here. There is no check in the above calculation to ensure that we do not end up with the exact same combination of balls, chosen in a different order, in different attempts. For example if there are 3 balls, choosing 1,2 and then 3 will be the same effective combination as choosing 2,3 and then 1. Hence we have to divide the above number by the number of ways the same set of k chosen balls could have shown up, in unique choice orders. This is basically a way of saying how many ways can k balls be uniquely ordered. The way to think of that is, the first ball can be placed in any one of k positions, starting from position 1 in the ordering to position k. Once the first ball has been placed, the second one only has a choice of k-1 positions. And similarly the second ball has k-2 options and the final ball has only one place it can go. Therefore this means there are k.(k-1).(k-2)…2.1 ways to arrange k balls in k positions. This is k!.
Hence the number we are after, ⁿC_k
= number of ways to choose k balls from n balls / number of unique orderings that the same choice of k balls can take while choosing the k balls from n balls
= n!/(n-k)! / k!
= n!/(k! . (n-k)!)
Interstingly, the intermediate result we got n!/(n-k)! is the number of permutations of k objects from a set of n unique objects!

Posted in Tidbits | No Comments »

A million days from now

February 21st, 2004 admin

I am reading a book called In Code - A young woman’s mathematical journey written by Sarah Flannery. In one of the chapters while trying to explain the concept of modulo arithmetic, she poses an interesting question along the lines of,
“Say today is Saturday, what day of the week will the millionth day from today be?”
The answer uses some very simple principles of modulo arithmetic. And I thought it was fascinating the way it is solved so easily. The question is simply,
If the days of the week are labeled 1,2…7 (for Monday, Tuesday, …, Sunday respectively) then the n^th day from today would be more than today by remainder when you divide n by 7.
n^th day from today = today + remainder when n is divided by 7 (or divided into 7, whichever convention you are comfortable with)
n^th day from today = today + n mod 7 (the mod part is therefore just another way of saying remainder)
But how do we find n mod 7? Especially when n is something huge like 1000000? That is where we need to make some useful observations about the modulus operator.
x mod a = y mod a, implies, x - y is divisible by a (figure shows why)

What can we say about xⁿ mod a and yⁿ mod a?
If x mod a = y mod a, then xⁿ mod a = yⁿ mod a.
In other words, if x - y is divisible by a then xⁿ-yⁿ is divisible by a too.
xⁿ mod a = yⁿ mod a is true only if xⁿ - yⁿ is divisible by a. Is that the case?
YES! And that is because xⁿ-yⁿ = (x-y)(some factor)
examples:
x²-y² = (x-y)(x+y)
x³-y³ = (x-y)(x² + xy + y²)
and so on.
Since x mod a = y mod a, ie x - y is divisible by a, (x-y)(some factor) is also divisible by a (since the “some factor” has no fractions and is therefore an integer).
OK, so what day is a million days from today?
million days from today = today + 100000 mod 7
how can we solve 1000000 mod 7?
Observe that 10 mod 7 = 3 (or in other words 3 mod 7)
10 mod 7 = 3 mod 7
Sqaring both sides confidently because we proved that exponentiation on both sides retains the equality,
100 mod 7 = 9 mod 7
Reducing right hand expression, by observing 9 mod 7 = 2 = 2 mod 7
100 mod 7 = 2 mod 7
Cubing both sides,
1000000 mod 7 = 8 mod 7
Observing that 8 mod 7 = 1
1000000 mod 7 = 1
a million days from now = today + 1 = Saturday + 1 = Sunday. (Something tells me that no one would worry about weekdays and weekends then)

Posted in Tidbits | No Comments »

Anagram, Anugram, Anigram

February 14th, 2004 admin

I chanced to realize that a signature I had used for my emails at work, “eleven plus two = twelve plus one” is infact what is called an anugram. An anugram is an anagram that also has truth associated with it. “west = stew” is therefore an anagram but not an anugram. Anigram is an animated anagram, that one might use on a webpage to show how anagrams work. The definition of an anigram is therefore restricted, shallow and quite unnecessary. A pangram is a sentence that has all the letters of the english alphabet. I am guessing that for languages like Indian languages, it would be harder to make such a restriction since it is rare to not find a vowel following a consonant. Most often he basic ‘a’ sound as in ‘bus’, is found following every consonant sound. Read up more about anagrams and create your own anagrams at the wordsmith website .

Posted in Tidbits | No Comments »