What’s cooking

October 25th, 2004 admin

Today, after a long time, I was in the mood for some cooking. I prepared multiple dishes and decided that this is a rare enough occurance that deserves a snap (hard proof). Thanksgiving weekend has started and I have some time at hand. So I decided to try out some new and old recepies. For the new ones, Kavita was giving me directions on the phone. I ended up making spinach dal, spicy Brinjal curry, dry Cauliflower curry and Okra(Ladiesfinger) fry.

Posted in Cooking | No Comments »

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 »