Hard | Strategy |

You are given N coins which look identical (assume N = 2^k). But actually some of them are pure gold coins (hence are heavy) and the rest are aluminum coins with thin gold plating (light). You are given one beam balance with two pans. What is the number of weighing required to separate the gold from fake coins? (all gold coins have equal weights & all fake coins too have the same weight)

Hint

Divide and conquer

Solution

It takes about (log N)^2 operations:

Divide the set of 2^k with d heavy coins into two sets, each with 2^(k-1) coins with floor(d/2) heavy coins. If we can do this, we can determine the number of heavy coins in O(log n)^2 operations.

Dividing the set can be done in O(log n). (*Later)

So, T(n) = T(n/2) + O(log n)

T(n) = O(log^2 n).

To be exact, this is k*(k+1)/2 . where k = log N

(*Sub-Algorithm)

Divide the set into two sets A and B of equal number of coins. Let A greater than B and to make both side of equal weight, I need to shift few coins from A to B and equal number of coins from B to A. So divide A into A1 and A2, and B into B1 and B2. Move A2 from A into B and B1 from B into A now if (A1,B1) is greater than (B2,A2) then I have not moved enough coins from A into B so as to make B part heavy enough hence you divide A1 into A11,A12 and move A12 in B side similarly u move B21 into A side on the other hand if (A1,B1) is less than (A2,B2) I have more than enough coins from A into B hence move B12 back into B and A21 back into A now measure again. Do it so on...

Note that we are doing this in O(log n) as each time the number of coins we are moving is reduced by half. So, In O(log n), we are done.

To prove that solution always exists, we do it by induction:

difference in the number of heavy coin after kth iteration cannot be more than 2^(n-1-k)

So, after n-1th iteration, it can be more that 1 coin. Hence, done. :)

Divide the set of 2^k with d heavy coins into two sets, each with 2^(k-1) coins with floor(d/2) heavy coins. If we can do this, we can determine the number of heavy coins in O(log n)^2 operations.

Dividing the set can be done in O(log n). (*Later)

So, T(n) = T(n/2) + O(log n)

T(n) = O(log^2 n).

To be exact, this is k*(k+1)/2 . where k = log N

(*Sub-Algorithm)

Divide the set into two sets A and B of equal number of coins. Let A greater than B and to make both side of equal weight, I need to shift few coins from A to B and equal number of coins from B to A. So divide A into A1 and A2, and B into B1 and B2. Move A2 from A into B and B1 from B into A now if (A1,B1) is greater than (B2,A2) then I have not moved enough coins from A into B so as to make B part heavy enough hence you divide A1 into A11,A12 and move A12 in B side similarly u move B21 into A side on the other hand if (A1,B1) is less than (A2,B2) I have more than enough coins from A into B hence move B12 back into B and A21 back into A now measure again. Do it so on...

Note that we are doing this in O(log n) as each time the number of coins we are moving is reduced by half. So, In O(log n), we are done.

To prove that solution always exists, we do it by induction:

difference in the number of heavy coin after kth iteration cannot be more than 2^(n-1-k)

So, after n-1th iteration, it can be more that 1 coin. Hence, done. :)

Source: CSEblog

Enable Like and Comment Hard | Strategy |

Two immensely intelligent players, A & B, engage in a game, the rules of which are as follows. For some natural number N, the board consists of numbers from 1 to N. Each player takes turns to strike off a (new) number from the board. But, to make sure N does't affect who wins, there is an added rule. Once you strike of a number, you also have to strike off all its divisors in that same chance, irrespective of whether any of those divisors were already marked. The player to strike off the last number on the board wins. Can A construct a winning strategy?

Solution

Source: Krishnamurthy Iyer

Enable Like and Comment Hard | Strategy |

N undercover agents have been found in don's lair. Less than half of them are terrorists and the rest are anti-terrorists. The nature of their job is so secret that there is no proof what so ever to testify who is who. Although each of them knows who was actual terrorist and who was anti because they worked in teams. A query consists of asking person i if person j is Anti. Anti will always speak truth but a terrorist may lie to confuse you. The goal is to find out one anti in fewest queries.

Hint

It can be done in less than N queries. End of a chain is testified by one anti somewhere in the middle.

Solution

Please note that this question cannot be solved with any algorithm if terrorists are more than or equal to anti, because terrorists can plan to always lie.

Solution by jadu, on CSE Blog, taking only N-1 queries

We will try to find a chain of persons (i1,i2,i3....im) such that each ij is queried about i(j+1) and answer is correct. Note that if such chain contains an anti then last person in the chain would be anti. So query person 1 about 2. If answer is yes query person 2 about 3. continue till answer is correct. suppose at some point person i when queried about person j says wrong, in that case remove person i and j from the chain, and continue query process by querying predecessor of i about successor of j. Here note that when we remove person i and j from the chain at-least one of them must be faulty. here for each person except the first one, we are querying once. Hence N-1 comparison in worst case. Think about the best case using this algorithm.

Solution by jadu, on CSE Blog, taking only N-1 queries

We will try to find a chain of persons (i1,i2,i3....im) such that each ij is queried about i(j+1) and answer is correct. Note that if such chain contains an anti then last person in the chain would be anti. So query person 1 about 2. If answer is yes query person 2 about 3. continue till answer is correct. suppose at some point person i when queried about person j says wrong, in that case remove person i and j from the chain, and continue query process by querying predecessor of i about successor of j. Here note that when we remove person i and j from the chain at-least one of them must be faulty. here for each person except the first one, we are querying once. Hence N-1 comparison in worst case. Think about the best case using this algorithm.

Source: Toad Puzzles

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 |