How many regions (open or closed) can n straight lines give at the maximum?

Let f(n) denote the number of regions for n lines no three of which coincide in one point. This latter condition will guarantee the maximum. Obviously, f(0)=1, f(1)=2, f(2)=4, f(3)=7, etc.

Now, given n-1 lines, there are already f(n-1) regions. With the introduction of the n-th line, imagine the points of intersection of the pre-existing n-1 lines fall on one side of the n-th line. So, on one side of the n-th line -- where the points of intersection lie -- you still have f(n-1) regions, whereas on the other side of the n-th line, you now have n regions. So, for these n lines before us, the total number f(n) of regions must be equal to f(n-1)+n.

So, f(n)=f(n-1)+n. With the initial condition(s) given earlier, this gives us f(n)=1+n(n+1)/2.

we can use induction to prove the same,

Base case:
if n = 1, regions (planes) = 2

Induction Hypothesis:
Addition of a new line adds
---------------------------------------------
|n
---------------------------------------------

regions to the regions formed by previous
---------------------------------------------
|n-1
---------------------------------------------
lines, i.e.

f(n) = n + f(n-1)

Upon simplifying the above, we get f(n) = 1 + n(n+1)/2

Weighting Puzzles One Side Weighing & two side Weighing

Puzzle 1:

The puzzle is if the shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1, 3 and 4 only. Now the question is how many minimum weights and names the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also. Answer for this puzzle is given below.

Solution :


This is simply the numbers 2^0,2^1,2^2 ... that is 1,2,4,8,16... So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, and 512. Comments your suggestions or other answers.

Puzzle 2:


This is same as the above puzzle with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg. Answer for this puzzle is given below.

Solution:


For this answer is 3^0, 3^1, 3^2... That is 1,3,9,27,81,243 and 729.

Dropping Eggs from a Building - 100 Story Building Famous Google Puzzle

Source:: Heard From Googlear in Bangalore

You stand before a 100-story building with two eggs. Using only these two eggs, you must figure out the highest floor from which you can drop an egg such that the egg won't break when it hits the ground (we'll call this the "highest safe floor"). Every floor is equally likely to be the highest safe floor, including the top floor, and it's also just as likely that the egg will break from every floor. You can assume that if you drop an egg and it doesn't break, its shell is just as strong as it was before you dropped it.

If you want to minimize the expected number of drops you have to perform, what strategy should you use for picking which floors to drop the eggs from? You should write a program to solve this problem.


Answer: The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.

Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.

Can we do even better? Yes we can (Bob, the builder). What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).

Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 – 20
15 – 20
16 – 21

So picking any one of the intervals with 19 maximum tries would be fine.

2nd Solution Discussed With Friends You Can Find This @ Many Places

Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.

Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.


Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.


(For strict computer science students, well this problem can be solved using binary search on the number of drops needed to find the highest floor.)

Now let x be the answer we want, the number of drops required.

So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.

Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task


Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

So we could write it as

(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).


3rd way to Approach Suggested by Galye Lakemann


Observation: Regardless of how we drop Egg1, Egg2 must do a linear search. i.e., if Egg1 breaks between floor 10 and 15, we have to check every floor in between with the Egg2
The Approach:
A First Try: Suppose we drop an egg from the 10th floor, then the 20th, …
»»If the first egg breaks on the first drop (Floor 10), then we have at most 10 drops total.
»»If the first egg breaks on the last drop (Floor 100), then we have at most 19 drops total (floors 10, 20, ...,90, 100, then 91 through 99).
»»That’s pretty good, but all we’ve considered is the absolute worst case. We should do some “load balancing” to make those two cases more even.
Goal: Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the first drop or the last drop.
1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100.
5. Solve for X+(X-1)+(X-2)+…+1 = 100. X(X+1)/2 = 100 -> X = 14
We go to Floor 14, then 27, then 39, … This takes 14 steps maximum.

Please feel free to correct or post any comment on the solution or the answer.


4th way to Solve it Purely Computer Science Way
Dynamic Programming

Solution

The key insight to solving this problem is to realize that if you drop and egg and it doesn't break, then you are essentially going to be performing the same problem for a building of a shorter size. For example, if you were to drop an egg from floor 60 and it didn't break, you would then be solving the same problem for floors 61-100, which is like solving it on a 40-story building.

Another important realization is that if your first egg breaks, you must go down to the the highest floor that you know is "safe" (or to the bottom floor if you don't know of any safe floors), and then go up one floor at a time, dropping the egg at each floor until it breaks. This is the only way to ensure that you'll then find the highet safe floor.

Let's generalize these ideas. Assume we decide to drop the first egg from floor k.

* If it breaks, then we'll have to go down to floor 1 and drop the second egg from each floor up to (k-1), or until it breaks. In this case, we expect about k/2 more drops on average, since each of the floors below floor k is is equally likely to be the highest safe floor. In fact, the exact number of drops to expect on average is (1 + 2 + ... + (k-1) + (k-1)) / k. We'll leave it as an exercise to the reader to see why.
* If it doesn't break, then it's as if we're considering the same problem on a building of size (100 - k), where the bottom floor is floor k+1.
* There is some probability of the first egg breaking from floor k. It's actually fairly straightforward to see that this probability is (k/101), because there are 101 possible scenarios (the scenarios in which each floor is the highest safe floor, plus the scenario in which all floors are unsafe). For the general case of an n-floor building, this probability is k/(n+1)
* Thus the probability of the egg not breaking is (1 - k/101), or for the general case, (1 - k/(n+1))

This leads us to define the "Best" formula. The function Best(n), should return the best number of expected drops we can attain for a builing with n stories. We also define the function Best(n,k), which should return the best expected number of drops we can attain for a building with n stories if our first drop is from floor k.

Best(100, k) = 1
+ (probability_of_breaking_from_floor_k * expected_number_of_drops_with_sequential_dropping_starting_at_floor_1)
+ (probablity_of_not_breaking_from_floor_k * Best(100-k))

This formula is based on basic probability theory. The first 1 in the sum is for the current drop. Then we add the expected number of additional drops if the current egg does or does not break, each weighted by the probability of that situation occurring. This gives us the expected total number of drops.

We are looking for Best(100), which we can find by calculating Best(100,k) for all values of k between 1 and 100, and picking the one that returns the minimal value. The value of k associated with this minimal value is the floor we should drop the first egg from.

This formula isn't solveable as is, because it is recursive (it includes a call to the Best() function within itself). But we can see that the recursive call to Best() always uses a number less than 100. This suggests that if we can build up the values for Best() starting at Best(1), then we can use a program to iteratively build up a solution for Best(100).

And that is exactly what we'll do. Below is a program written in the Ruby programming language which solves the problem for 100 floors (though you can change the value), and finishes by printing out the proper floors to drop the egg as the dropping progresses.

Algorithm

PRINT_DEBUG = false
MAX_FLOORS = 100

def probability_of_breaking(cur_floor, num_floors)
return (cur_floor.to_f / (num_floors.to_f + 1.0))
end

def expected_drops_with_final_egg(num_floors_to_check)
if num_floors_to_check == 0
return 0.0
elsif num_floors_to_check == 1
return 1.0
else
numerator = (1..(num_floors_to_check-1)).to_a.inject(0){|p,c| p + c} + (num_floors_to_check * 2)
denominator = num_floors_to_check + 1
return (numerator.to_f / denominator.to_f)
end
end

expected_best = {0 => {:best_num_drops => 0.0, :best_start_floor => 0}}
for num_floors in 1..MAX_FLOORS
cur_best = nil
best_start_floor = nil
puts "======================= #{num_floors} Floors ======================="
for start_floor in 1..num_floors
#if the egg breaks from the current floor, we have to start from the highest floor below the current floor
# where we know the egg won't break from (or floor 1 if we haven't tested from any floors below the current floor)

puts "--- Starting on #{start_floor} of #{num_floors} floors ---" if PRINT_DEBUG
break_probability = probability_of_breaking(start_floor,num_floors)
floors_above = num_floors - start_floor
floors_below = start_floor - 1
expected_floors_if_breaks = expected_drops_with_final_egg(floors_below)
expected_floors_if_does_not_break = expected_best[floors_above][:best_num_drops]
best_expected_drops = 1.0 +
(break_probability * expected_floors_if_breaks) +
((1.0 - break_probability) * expected_floors_if_does_not_break)
puts " probability of breaking: #{break_probability} --- if breaks: #{expected_floors_if_breaks} --- if not: #{expected_floors_if_does_not_break} --- expected drops: #{best_expected_drops}" if PRINT_DEBUG

if cur_best.nil? or best_expected_drops < cur_best cur_best = best_expected_drops best_start_floor = start_floor end end expected_best[num_floors] = {:best_num_drops => cur_best, :best_start_floor => best_start_floor}
end

for k in expected_best.keys.sort
puts "#{k} floors: #{expected_best[k].inspect}"
end


num_floors = MAX_FLOORS
puts "===== For #{num_floors} floors, we expect an average of #{expected_best[num_floors][0]} drops ====="
effective_num_floors = num_floors
base_floor = 0
while true
drop_floor = base_floor + expected_best[effective_num_floors][:best_start_floor]
floors_above = num_floors - drop_floor
effective_floors_below = drop_floor - base_floor - 1

puts "Drop from floor #{drop_floor}"
puts " If it breaks there, you can expect #{expected_drops_with_final_egg(effective_floors_below)} more drops"

effective_num_floors = floors_above
base_floor = drop_floor

break if drop_floor >= num_floors - 1
end

Knight Tour - Yet Another Chess Problem

Source : Heard From My Friend Who Went to Crack Amazon

The Knight's Tour is a famous chess problem, in which a knight starts on the top-left square of an ordinary chessboard and then makes 63 moves, landing on every square of the chessboard exactly once (except for the starting square).

Can you complete the Knight's Tour? For a further challenge, can you find a "closed" solution, meaning that the knight can make a 64th move to land back on the starting square (thus making the solution circular)?





Solution
This pictures shows a non-cyclical solution. The strategy is to essentially cover the border (outer 3 rows/columns) first, and then cover the inner part of the board. We'll leave a cyclical solution as a challenge to the reader




More Info
http://en.wikipedia.org/wiki/Knight%27s_tour

You need to check that your friend, Bob, has your correct phone number…Google Puzzle

You need to check that your friend, Bob, has your correct phone number…

but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?


Solution Started From Funniest Way to Deepest Thing of Computer Science

Funny Solutions

it is funny with all these technologies nowadays, I would opt for following as answer for 2.

Write on paper question ....."Bob Can you verify if you have my correct number without revealing to Eve and without talking to me in any of following methods?

1. E-mail me at abc@xyz.com

2. MMS me to my phone number that "If I get this MMS, then Bob has my correct number"

3. Go to my internet website account (facebook) OR even linked.com and write me a message for what number you have

4. Use communicator chat software or gtalk or yahoo messenger and ping me the number that you have

5. mathematically compute like checksum or decode and send me coded number with decoding steps. on paper back to Eve.


Computer Science Way of Thinking

Public key Cryptography
here is my public key, pls encrypt my phone you have with it and send back to me.
key=num-reveres of num

e.g if my no is 9740852296
the key=2818271817 eve can't read it as eva dopn't have my number so she can't predict & she has to lot of computation which only possible she know my number or some its digits ..so she can't decode the my key

(we can also extend the explanation so i write on the paper that bob i am sending you key to decode it reverse the key & then decode using logic you have so the same thing bob has to do in its side & same he write back to me..m not using this in this solution )

then bob decode it using computation he tries all the way +,-*,/, %,xor all possible way to decode if he has my correct phone number then suppose he try to subtract my key from my phone number he has so if has correct phone number then after subtracting the key from my number he will send 9740852296-2818271817=6922580476 & he also write that after decoding reverse it so i will get my original number e.g. 9740852296 so i can say bob has my correct phone number else it would have been some other value & after reversing it i wont get my exact no so i can say bob don't have my correct number..


Hurray i think i have done..Please Correct me if i am wrong

More Depth This Solution provide by Ankul

Click here


Ask Bob to Hash the phone number using a string hashing technique :
T[256] = permutation of 0...255
H[0] = 0
H[i] = T[ H[i-1] xor C[i] ]
H[n] is the final hash value

Since this hash function gives different hash values for permutations of same string, so a hash collision will not occur when two strings are permutation of each other.

This is a one-way hash function and cannot be decrypted back to the original phone number.

When I will get the hash key from Bob, I will find the hash value for my actual phone number and then match it with the hash key given by Bob.

Now, if hash values don't match, Bob has wrong phone number of mine.
Otherwise, there can be two cases :

1. He has correct phone number.
2. He has incorrect phone number but still gives same hash value (collision).

To decide between these two cases, I can ask Bob to also send me the frequency of each digit in the number that he has. This way, I will be able to decide if the two numbers are permutations of each other or not. If, the frequency of any of the digit in my actual number doesn't matches with the frequency given by him, that means the 2nd case is applicable, otherwise 1st case (phone numbers match) because a permutation of same string cannot give same hash value for this hash function.

Thus, I will ask Bob to send me the hash value and the frequency of each digit in his phone number. Eve has no way to find the phone number.

Cheers
WgpShashank

9 Digit Number Problem Every nth number formed by n digit is Divided By Every nth digit

Arrange the digits 0 to 9 such, that the number formed by the
first digit is divisible by 1, the number formed by the first two
digits is divisible by 2, that formed by the first three digits
divisible by 3, and so forth, thus the number formed by the first
9 digits will be divisible by 9 and that formed by all 10 digits
divisible by 10.

Here is what we would do.

_ _ _ _ _ _ _ _ _ _

those are my ten blanks.

Now let's start asking questions.

Since the whole thing has to be divisible by 10, the last number
must be a zero.

And since the first five digits must be divisible by 5, the fifth
digit must be a 5 or 0, but we have already used 0 so it must be a
five.

One last quickie is that the 2nd, 4th, 6th, and 8th and last
digits must be even, so all the rest are odd

So let's look at we have. I'll write the digits that could go in a
certain place under where they could go:


_ _ _ _ 5 _ _ _ _ 0
1 2 1 2 2 1 2 1
3 4 3 4 4 3 4 3
7 6 7 6 6 7 6 7
9 8 9 8 8 9 8 9

Now things get trickier.

Let's start with the 4th spot.

Any number is divisible by 4 if the last two digits are divisible
by 4

So what are the two-digit numbers divisible by 4 that begin with
an odd number that is not 5?

12 16 32 36 72 76 92 96

Hey, so the 4th digit is either a 2 or a 6.

Now, let's look at the 8th digit. If the first 8 digits are
divisible by 8, then they are divisible by 4 also. So if we apply
the same logic as above, we find that the 8th digit is either a 2 or
a 6.

So spaces 2 and 6 must be 4 or 8.

That narrows it down. So we have this:

_ _ _ _ 5 _ _ _ _ 0
1 4 1 2 4 1 2 1
3 8 3 6 8 3 6 3
7 7 7 7
9 9 9 9



Now for my next trick let's recall that every third space must be
divisible by 3. So every three numbers must sum to be divisible
by 3.

In particular spaces 4, 5, and 6 must sum to 3, and we already
have a five. So either we have

2 5 8 or 6 5 4

in positions 4, 5, and 6.

That is good stuff. That means we have either this:

_ 4 _ 2 5 8 _ 6 _ 0
1 1 1 1
3 3 3 3
7 7 7 7
9 9 9 9

or this:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 1 1
3 3 3 3
7 7 7 7
9 9 9 9

Let's check each of the four digits we could put in the 8th place.
Since a number is divisible by 8 if its last 3 digits are, we need
number in the 6th, 7th, and 8th places to be divisible by 8. We see
that 816 and 896 work in the first case, and 432 and 472 work in the
second case. So we have:

_ 4 _ 2 5 8 _ 6 _ 0
1 1 1 1
3 3 9 3
7 7 7
9 9 9

or this:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 3 1
3 3 7 3
7 7 7
9 9 9


Let's look at the 9th place now. Recall that 1+2+3+4+5+6+7+8+9 = 45,
so we don't need to worry about the 9th place - it will always work
out.

Let's look at the 1st and 3rd places. In case 1, only 147 and 741 are
options. In case 2, we could have 183, 189, 381, 387, 783, 789, 981, or
987. Note that 387 and 783 don't work, because then we don't have any
digits left for the 7th digit.

So our first case becomes:

_ 4 _ 2 5 8 9 6 3 0
1 1
7 7

We can just check the two numbers this can give rise to, namely 1472589630
and 7412589630. Since neither of them are divisible by 7, case one must be
a dead end. So we have to work with case two if we want a solution:

_ 8 _ 6 5 4 _ 2 _ 0
1 1 3 1
3 3 7 3
7 7 7
9 9 9

(and the first 3 digits are 183, 189, 381, 789, 981, or 987)

If we look at the 7th, 8th, and 9th digits to see if we can get them to sum
to three, we see that only 321, 327, 723, and 729 are options.

So which of our options for digits 1,2,3 and 7,8,9 can we use together? In
order to not repeat digits, we could use these:

183 and 729
189 and 327
189 and 723
381 and 729
789 and 321
981 and 327
981 and 723
987 and 321

This means that the only possible solutions to the puzzle are these:

1836547290
1896543270
1896547230
3816547290
7896543210
9816543270
9816547230
9876543210

This is now a small enough number of cases that we can check them by hand.
The first thing we should do is check the first 7 digits for divisibility by
seven. Here are the results:

1836547/7 = 262363.857142857...
1896543/7 = 270934.714285714...
1896547/7 = 270935.285714286...
3816547/7 = 545221
7896543/7 = 1128077.57142857...
9816543/7 = 1402363.28571429...
9816547/7 = 1402363.85714286...
9876543/7 = 1410934.71428571...

There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passen

There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passengers.



This is equal to 1-(probability that they all carry different number of passengers). That probability in paranthesis is equal to (m+1)!/((m+1-n)! * (m+1)^n). This is given that (m+1) >= n. If (m+1) < n, then the probability is 1.

- m+1 because maximum m passengers mean m+1 different possiblities (a bus could carry 0 passengers).
- The first bus has (m+1) possibilities in terms of number of passengers. The second has m+1, the third has m+1 and so on. Total number of orderings possible is (m+1) ^ n.
- For the number of passengers to be different in each bus, first bus has m+1 possibilities, second has m, third has m-1 nd so on. For n buses, this is equal to (m+1)!/(m+1-n)!. Dividing this by (m+1)/n gives the possibility. Subtract this number from one to find at least two buses with the same amount of passengers.


Solved by James