Medium | Discrete Maths |

There is a 6x8 rectangular chocolate bar made up of small 1x1 bits. We want to break it into the 48 bits. We can break one piece of chocolate horizontally or vertically, but cannot break two pieces together! What is the minimum number of breaks required?

Answer

47

Solution

For a chocolate of size mxn, we need mn - 1 steps. By breaking an existing piece horizontally or vertically, we merely increase the total number of pieces by one. Starting from 1 piece, we need mn - 1 steps to get to mn pieces.

Another way to reach the same conclusion is to focus on "bottom left corners of squares": Keep the chocolate rectangle in front of you and start drawing lines corresponding to cuts. Each cut "exposes" one new bottom left corner of some square. Initially, only one square's bottom left corner is exposed. In the end, all mn squares have their bottom left corners exposed.

Another way to reach the same conclusion is to focus on "bottom left corners of squares": Keep the chocolate rectangle in front of you and start drawing lines corresponding to cuts. Each cut "exposes" one new bottom left corner of some square. Initially, only one square's bottom left corner is exposed. In the end, all mn squares have their bottom left corners exposed.

Medium | Discrete Maths |

Assume 100 zombies are walking on a straight line, all moving with the same speed. Some are moving towards left, and some towards right. If a collision occurs between two zombies, they both reverse their direction. Initially all zombies are standing at 1 unit intervals. For every zombie, you can see whether it moves left or right, can you predict the number of collisions?

Hint

On every collision, assume that the two zombies don't reverse direction but simply cross each other.

Solution

Since we can assume that zombies can pass through each other, for a zombie moving right, count the number of zombies to its right moving left. Add this number for every right moving zombie. That is the number of collisions.

Source: CSEblog

Enable Like and Comment Medium | Discrete Maths |

An infection spreads among the squares of an nXn checkerboard in the following manner. If a square has two or more infected neighbors, it becomes infected itself. (Each square has 4 neighbors only!). Prove that you cannot infect the whole board if you begin with fewer than n infected squares.

Hint

Invariance

Solution

Perimeter of infected area can't increase. It stays constant or decreases. Initially maximum perimeter is 4*k if k blocks are infected. But to infect all blocks, the perimeter must increase to 4*n, k<n. This is not possible

Source: P. Winkler

Enable Like and Comment Medium | Probability |

A & B are alternately picking balls from a bag without replacement. The bag has k black balls and 1 red ball. Winner is the one who picks the red ball. Who is more likely to win, the on who starts first, or second?

Hint

Look at k=0,1,2,3... Write down probability of starter being a winner.

Answer

Begin!

Solution

A & B keep on picking the balls without looking at their color. After all balls have been picked, the one who starts the game will have more balls (if k=even, total balls=odd) and hence higher probability of winning.

Solution by Palak Bhushan:

(prob of A winning in first chance = 1/(k+1)) +

(prob of A winning in 3rd chance = (1-(1/k+1))*(1-1/k)*1/(k-1) = 1/(k+1)) + ... +

(prob of A winning in 2r+1-th chance = 1/(k+1)) + ... .

When k=2n+1, there are n+1 such terms, giving the prob as (n+1)*1/(k+1)=1/2.

When k=2n, there are n+1 such terms, giving prob as (n+1)*1/(k+1)=(n+1)/(2n+1)>1/2.

Hence, doesnt matter who starts first when k is odd.

The first player has higher chance of winning when k is even

Solution by Palak Bhushan:

(prob of A winning in first chance = 1/(k+1)) +

(prob of A winning in 3rd chance = (1-(1/k+1))*(1-1/k)*1/(k-1) = 1/(k+1)) + ... +

(prob of A winning in 2r+1-th chance = 1/(k+1)) + ... .

When k=2n+1, there are n+1 such terms, giving the prob as (n+1)*1/(k+1)=1/2.

When k=2n, there are n+1 such terms, giving prob as (n+1)*1/(k+1)=(n+1)/(2n+1)>1/2.

Hence, doesnt matter who starts first when k is odd.

The first player has higher chance of winning when k is even

Source: 40 Puzzles

Enable Like and Comment Medium | Probability |

A postman brought N letters to a house with two letter-boxes. Since the two boxes were empty, he puts 1 mail in each of the two mail boxes. Then he chooses one of boxes with probability proportional to number of letters present in that box, and puts the 3rd letter in it. He does this for all subsequent letters. What is the expected number of letters in the box with lower letters?

Hint

This can be made equivalent to randomly splitting a deck of n cards into two parts. (n>2)

Solution

Suppose I have a stack of 2 black cards and one red card. Initially I put red between 2 black cards. Now I add black cards randomly between any two cards (so, initially it is either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be: if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent.

Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest box contains n/2 letter or 1 letter (or any number of letters between 1 and n/2) are all same. So, expected number of letters in the smaller box is asymptotically n/4

Now this way, we are getting all possible combinations in which one red and n black cards can be mixed, we see that the probability that the red card is at height h is independent of h. So, the probability that the smallest box contains n/2 letter or 1 letter (or any number of letters between 1 and n/2) are all same. So, expected number of letters in the smaller box is asymptotically n/4

Source: P. Winkler

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |