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

Several gas stations on a circular trek have between them just enough gas for one car to make a complete round trip. Prove that if you start at the right station with an empty tank you shall be able to make it all the way around.

Hint

Induction

Solution

Take N=2 gas stations. Assume their capacities are x1 and x2 (in terms of distance). Now, x1+x2 = 1. Assume y1 and y2 be clockwise distances from 1 to 2 and 2 to 1 (clockwise), y1+y2 = 1. Hence we cant have x1<y1 and x2<y2 both. Thus, let x1 >= y1. In this case we start with station 1 and complete the journey. Assume the path is possible for N=K stations, we want to prove for N = K+1 stations, using same argument as above, xi>=yi for some i, and hence reaching xi with zero fuel ensures reaching x(i+1). Thus we merge xi and x(i+1), and the problem is reduced to N=K stations, which we assumed!

Another method is to imagine having a big tank with enough gas for a round trip and enough room for going through the motions of emptying every gas station on your way. Start at any station and mind to record the amount of gasoline on reaching gas stations on your way around. At the end of the trip, when you pull into the station of departure with the original amount of gas, check your list. The station marked with the least number is the one where you want to start on an empty tank.

Another method is to imagine having a big tank with enough gas for a round trip and enough room for going through the motions of emptying every gas station on your way. Start at any station and mind to record the amount of gasoline on reaching gas stations on your way around. At the end of the trip, when you pull into the station of departure with the original amount of gas, check your list. The station marked with the least number is the one where you want to start on an empty tank.

Source: P. Winkler

Enable Like and Comment Hard | Discrete Maths |

Can you pack 53 bricks of dimensions 1x1x4 into a 6x6x6 box? The faces of the bricks are parallel to the faces of the box

Hint

See its cousin called Domino Covering in which two opposite corners of a checkerboard are removed.

Answer

No!

Solution

Divide the volume of 6x6x6 box into 2x2x2 mini cubes. Imagine each of these mini cubes is either fully red or fully blue such that it forms a 3D checkerboard pattern on the box. This will restrict 14-13 restriction on cube colors, say 14 blue and 13 red. Now, putting bricks into box, parallel to faces, each brick will be half blue and half red, so 52 bricks fill all the red cubes and there is no way to place a 53rd brick.

Source: Xinfeng Zhou

Enable Like and Comment Medium | Discrete Maths |

There is a crazy clock in Alice's Dream, it has two hands initially pointing at 12. The minute hand moves clockwise, making 5 rounds (with varying speeds) and comes back to 12. In the same time, the hour hand goes anti-clock wise, finishing 4 rounds and returns to 12. How many times did the two cross each other ? (Cross means meet & pass through, hence ignore start & end)

Answer

8

Solution

In the reference frame of minute hand, hour hand moves exactly (5+4) = 9 rounds anti-clockwise with varying speeds (by adding total angular distance covered). 'Cross' occurs just in between two consecutive rounds. Thus hour hand crosses minute hand exactly 9-1=8 times. Same answer in ref. plane of hour-hand.

Source: Self

Enable Like and Comment 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 Latest solved Puzzles

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

© BRAINSTELLAR |