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 Hard | Discrete Maths |

A group of 5 people want to keep their secret document in a safe. They want to make sure that in future, only a majority (>=3) can open the safe. So they want to put some locks on the safe, each of the locks have to be opened to access the safe. Each lock can have multiple keys; but each key only opens one lock. How many locks are required at the minimum? How many keys will each member carry?

Hint

For each group of 2 ppl, there must be a lock which none of them have a key to.

Answer

10 locks, 6 Keys.

Solution

For each group of 2 ppl, there must be a lock which none of them have a key to. But the key of such a lock will be given to the remaining 3 ppl of group. Thus, we must have atleast 5C2 = 10 Locks. Each lock has 3 keys, which is given to unique 3-member subgroup. So each member should have 10*3/5 = 6 keys.

Hard | Discrete Maths |

We have a beam balance (with two pans to compare weights) and a positive integer N. How do we select fewest number of pebbles to weigh all possible integers from 1 to N

Solution

We will require the set (1,3,9.....3^x )

where x is lowest integer with 3^x > N. This is true because each number now has exactly one ternary representation. Any 2*3^i can always be represented as 3^(i+1) - 3^i. So, there is a unique way of representing a number in the form of sigma s_i*3^i where s_i belongs to {0, 1, -1}. So, this is optimal

Verify that this can be used to weigh all integers from 1 to N

Number of pebbles = log_{base:3} (2N+1)

Solution by Palak Bhushan

If each weight w_i has k copies, then 2k+1 combinations can be weighed using them (from -k*w_i to 0 to k*w_i). So, if we choose w_i = (2k+1)^{i-1}, i=1...p, then everything till k*((2k+1)^p - 1)/((2k+1)-1) = ((2k+1)^p-1)/2 can be weighted, thus requiring p=log_{2k+1} (2N+1) number of distinct weights.

where x is lowest integer with 3^x > N. This is true because each number now has exactly one ternary representation. Any 2*3^i can always be represented as 3^(i+1) - 3^i. So, there is a unique way of representing a number in the form of sigma s_i*3^i where s_i belongs to {0, 1, -1}. So, this is optimal

Verify that this can be used to weigh all integers from 1 to N

Number of pebbles = log_{base:3} (2N+1)

Solution by Palak Bhushan

If each weight w_i has k copies, then 2k+1 combinations can be weighed using them (from -k*w_i to 0 to k*w_i). So, if we choose w_i = (2k+1)^{i-1}, i=1...p, then everything till k*((2k+1)^p - 1)/((2k+1)-1) = ((2k+1)^p-1)/2 can be weighted, thus requiring p=log_{2k+1} (2N+1) number of distinct weights.

Source: leino

Enable Like and Comment Latest solved Puzzles

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

© BRAINSTELLAR |