Medium | Discrete Maths |

An 8x8 chessboard can be entirely covered by 32 dominoes of size 2x1. Suppose we cut off two opposite corners of chess (i.e. two white blocks or two black blocks). Prove that now it is impossible to cover the remaining chessboard with 31 dominoes.

Hint

The two diagonally opposite corners are of the same color.

Solution

The two diagonally opposite corners are of the same color. A domino covers adjacent faces & hence a domino always covers 1 black and 1 white square. The 31 dominoes will cover 31 blacks and 31 whites. The chess has 30 & 32 square instead. Hence this can't be done.

Source: Martin Gardner

Enable Like and Comment Medium | Discrete Maths |

13 Apples, 15 Bananas and 17 Cherries are put in the magic hat. When ever a collision of two different fruits occurs, they both get converted into the third type. For example 1 Apple and 1 Banana can collide to form 2 cherries. No other collision is holy. Can a sequence of such magical collisions lead all 45 fruits to give just one type?

Hint

This can't be done. Try to create a function of A,B,C which remains constant during a collision to get contradiction.

Solution

Create the invariant function f(A,B,C) = (0A+1B+2C)mod3, this function remains constant during a collision. But f(13,15,17) = 1 is not same as any of final states f(45,0,0)=f(0,45,0)=f(0,0,45)=0. Hence this can not be done.

A refreshment to this old trick was given by Aritro Pathak:

call the no of times apples are increased by 2 as A, bananas increased by 2 as B, and cherries increased by 2 as C. if we need 45 apples,total increments - decrements of apple = 32

but increments of apple = 2*A;

when ever 2 banana's are created, 1 Apple is lost, similarly for 2 cherries

decrements = B+C

thus we have 2A-B-C=32, -2B+C+A=15, -2C+B+A=17. Subtract the last two to get 2=3*(B-C) which is impossible. similar cases for when you want 45 of either cherries or bananas.

A refreshment to this old trick was given by Aritro Pathak:

call the no of times apples are increased by 2 as A, bananas increased by 2 as B, and cherries increased by 2 as C. if we need 45 apples,total increments - decrements of apple = 32

but increments of apple = 2*A;

when ever 2 banana's are created, 1 Apple is lost, similarly for 2 cherries

decrements = B+C

thus we have 2A-B-C=32, -2B+C+A=15, -2C+B+A=17. Subtract the last two to get 2=3*(B-C) which is impossible. similar cases for when you want 45 of either cherries or bananas.

Medium | Discrete Maths |

There are 51 ants sitting on top of a square table with side length of 1. If you have a square card with side 1/5, can you put your card at a position on the table to guarantee that the card encompasses at least 3 ants?

(updated: square card was originally disk of radius 1/7)

(updated: square card was originally disk of radius 1/7)

Hint

Pigeonhole principle

Solution

To guarantee that the card encompasses at least 3 ants, we can separate the square into 25 smaller areas (squares of side 1/5 each). Applying the generalized Pigeon Hole Principle, we can show that at least one of the areas must have at least 3 ants. The card is large enough to cover any of the 25 smaller areas. Done!

Medium | Discrete Maths |

On a 2D complex plane, all the integer-component points are coloured either White or Black. Is Possible to find a rectangle parallel to axis which has all corners of same color?

Solution

asd

Source: Top Quant Interview

Enable Like and Comment Medium | Discrete Maths |

In a circle are light bulbs numbered 1 through n, all initially on. At time t, you examine bulb number t, and if it’s on, you change the state of bulb t + 1 (modulo n); i.e., you turn it off if it’s on, and on if it’s off. If bulb t is off, you do nothing. Prove that if you continue around and around the ring in this manner, eventually all the bulbs will again be on.

Hint

It doesn't matter what the rules are, only thing that matters is that all bulbs should not go off!

Solution

Suppose every orientation of light bulbs & position of current pointer (t modulo n) forms a different state. Since all bulbs don’t go off, we must repeat a state after finite number of steps. Also notice that every state has a unique pre-state. Suppose the two states are at time T1 & T2. Notice that at time 0 all bulbs are on. Thus moving backwards from both states, we arrive at T2-T1, where all bulbs are on again.

Source: P. Winkler

Enable Like and Comment Latest solved Puzzles

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

© BRAINSTELLAR |