Toss And Toss

We toss coin to choose one from two. But Taheri has invented a new tossing method named Dhele Dei .You can choose one from many people with this method . In this method, he gives each person a tossing code and tosses a coin according to necessity . For example, if Hiron has a code like TTHHT , the tossing outcomes are T, T,H,H and T respectively and Taheri tosses the coin just 5 times, Hiron will be selected. Taheri always tosses the coin not more than his necessity. The tossing code is changeable to toss the coin fewest times.

P r o b l e m : Problem : If Taheri want to choose 3 people from 2050 people, how many times he have to toss a coin?

29 29 33 33 36 36 35 35

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Joshua Lowrance
Sep 30, 2019

When you flip a coin x amount of times, there will be 2 x 2^x unique solutions. This means that if you have 2 x 2^x people, you can flip a coin x amount of times. However, if you have more than 2 x 2^x people, you will need more than x coin flips.

In this case, there are 2050 2050 people. The closest power of 2 2 is 2048 = 2 11 2048=2^{11} . If there were 2048 2048 or less people, we could only do it will 11 11 coin flips. However, because 2050 2050 is greater than 2 11 2^{11} , we need 12 12 coin flips to determine the first person.

When we are determining the second person, we only have 2049 2049 people. It is still greater than 2 11 2^{11} , so we still need 12 12 coin flips.

However, when choosing the third and final person, we only have 2048 2048 people, which is less than or equal to 2 11 2^{11} . Because of this, we only need 11 11 coin flips to determine the third person.

Overall, we needed 12 + 12 + 11 = 35 12+12+11=35 coin flips.

I think you can do it with even less number of coin flips. Assuming that the order does not matter, ( 2050 3 ) \binom{2050}{3} is the number of object we need to choose from. There would be approximately 29 29 bits(coin flips) required to label that number of objects.

A Former Brilliant Member - 1 year, 8 months ago

Log in to reply

According to the rule, obviously the order matters.

arifin ikram - 1 year, 8 months ago

Log in to reply

"OBVIOUS", what is obvious, you nimrod? :D

A Former Brilliant Member - 1 year, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...