Medium | Discrete Maths |

A group of students are sitting in a circle with the teacher in the center. They all have an even number of candies (not necessarily equal). When the teacher blows a whistle, each student passes half his candies to the student on his left. Then the students who have an odd number of candies obtain an extra candy from the teacher. Show that after a finite number of whistles, all students have the same number of candies.

Hint

Look at minimum & maximum count of candies.

Solution

1. The maximum number of candies held by a single student can never increase.

2. The minimum number of candies held by a single student always strictly increases, unless the student to his right also has the minimum number of candies, in which case the length of the longest consecutive segment of students who have minimum number of candies strictly decreases. Thus eventually the minimum has to strictly increase.

3. Since the minimum has to strictly increase in a finite number of steps and cannot go beyond the maximum, all the numbers must eventually be equal in atmost n(max-min) steps.

2. The minimum number of candies held by a single student always strictly increases, unless the student to his right also has the minimum number of candies, in which case the length of the longest consecutive segment of students who have minimum number of candies strictly decreases. Thus eventually the minimum has to strictly increase.

3. Since the minimum has to strictly increase in a finite number of steps and cannot go beyond the maximum, all the numbers must eventually be equal in atmost n(max-min) steps.

Source: puzzletweeter

Enable Like and Comment Medium | Discrete Maths |

A rectangular table has 100 coins with unit radius, placed on it such that none of the coins overlap, and it is impossible to place any more coins on the table without causing an overlap. Using this specific configuration, find a special configuration of 400 coins which covers the table with overlaps.

Covering means for every point on table there is a coin above it.

Covering means for every point on table there is a coin above it.

Hint

Create coins of radius 2 from the center of all coins. Notice that these coins fill up entire table, they are just bigger than what we are given.

Solution

Consider just one of these coins, with center P. It follows that the center Q of any other coin cannot lie within the coin of radius 2 with center P because it must be at least 2 units away. Thus, we construct all of these coins of radius 2, concurrent with each of the coins of radius 1. If the set of coins of radius 2 did not cover the rectangle entirely, then we could place a coin of radius 1 in this region, contradiction. Thus, the set of coins of radius 2 entirely covers the rectangle.

We now have 100 coins of radius 2 that entirely covers the rectangle. Scale this by a factor of 1/2 in both planar dimensions. Now we have 100 coins of radius 1 that entirely covers a rectangle that is a quadrant of the original rectangle. By placing four of these sets together, we get 400 coins of radius 1 that entirely covers the original rectangle.

We now have 100 coins of radius 2 that entirely covers the rectangle. Scale this by a factor of 1/2 in both planar dimensions. Now we have 100 coins of radius 1 that entirely covers a rectangle that is a quadrant of the original rectangle. By placing four of these sets together, we get 400 coins of radius 1 that entirely covers the original rectangle.

Source: CSEblog

Enable Like and Comment Medium | Discrete Maths |

On a table you have a square made of 4 coins at the corner at distance 1. So, the square is of size 1×1. In a valid move, you can choose any two coin let’s call them mirror and jumper. Now, you move the jumper in a new position which is its mirror image with respect to mirror. That is, imagine that mirror is a centre of a circle and the jumper is on the periphery. You move the jumper to a diagonally opposite point on that circle. With any number of valid moves, can you form a square of size 2×2? If yes, how? If no, why not?

Hint

Invariance

Answer

No!

Solution

Source: Saurabh Joshi's Blog

Enable Like and Comment Hard | Discrete Maths |

An optimist and a pessimist are examining a sequence of real numbers. The optimist remarks, ‘Oh jolly! The sum of any eight consecutive terms is positive!’ But the pessimist interjects, ‘Not so fast, the sum of any five consecutive terms is negative.’ Can they both be right? Atmost how large can this sequence be?

Hint

One easy proof is to construct rows, starting from ai, and satisfying one of the sum properties - optimist or pessimist. The column sum can follow the other property. Try making a contradiction.

Answer

11

Solution

Suppose such a sequence with terms {ai} has length 12

a1+a2+...+a5<0

a2+a3+...+a6<0

..

a8+a9+...+a12<0

Note that rows sums are negative and column sums are positive. This is contradiction to the total sum! So max length of sequence is 11. This sequence can be constructed but we wont cover the instruction. Example: 1 at positions 1,3,4,6,8,9,11 and -1.6 at positions 2,5,7,10.

a1+a2+...+a5<0

a2+a3+...+a6<0

..

a8+a9+...+a12<0

Note that rows sums are negative and column sums are positive. This is contradiction to the total sum! So max length of sequence is 11. This sequence can be constructed but we wont cover the instruction. Example: 1 at positions 1,3,4,6,8,9,11 and -1.6 at positions 2,5,7,10.

Source: Arthur Engel

Enable Like and Comment Hard | Discrete Maths |

We want to construct a structure made as follows: imagine that two long cylindrical pillars each with radius 1 intersect at right angles and their centers also intersect. What is the volume of this intersection?

Answer

16/3

Solution

If you cut the intersection by a horizontal plane at distance z from center, the cut will be a square with side-length 2*sqrt( 1-z^2). Integrate to get volume 16/3.

Another way is to imagine the largest possible sphere inscribed at the center of intersection. The sphere should have a radius of 1. At each cut perpendicular to the z-axis, the circle from the sphere is inscribed in the square from the intersection as well, So Area of cut-circle = (Pi/4)*Area of cut-square. This is true for all z, hence Volume of sphere = (Pi/4)*Volume of Intersection, this also gives 16/3

Another way is to imagine the largest possible sphere inscribed at the center of intersection. The sphere should have a radius of 1. At each cut perpendicular to the z-axis, the circle from the sphere is inscribed in the square from the intersection as well, So Area of cut-circle = (Pi/4)*Area of cut-square. This is true for all z, hence Volume of sphere = (Pi/4)*Volume of Intersection, this also gives 16/3

Latest solved Puzzles

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

© BRAINSTELLAR |