Jump to content

Who am I?


Recommended Posts

13 minutes ago, dimreepr said:

What's the most efficient algorithm to determine who's written on my forehead? 

You're just a speck of dust in an endless void, asking questions. 

Link to comment
Share on other sites

12 minutes ago, koti said:

You're just a speck of dust in an endless void, asking questions. 

Nice try but that's just a binary split search of each letter, the most efficient of the least efficient method, guessing. :P

Edited by dimreepr
Link to comment
Share on other sites

24 minutes ago, koti said:

You're just a speck of dust in an endless void, asking questions. 

The whole point of asking questions in party game "guess who am I?" is to limit possible answers.

Your question didn't move you any way forward in it.. so you basically wasted question..

 

 

Link to comment
Share on other sites

 

38 minutes ago, koti said:

Did I win?! 

@dimreepr

No. You didn't propose any algorithm..

In binary search algorithm we split the all possible answers by two, so if we have initially e.g. 1 mln possible answers:

/2 = 500k

/2 = 250k

/2 = 125k

/2 = 62.5k

/2 = 31250

/2 = 15625

/2 = ~7812

/2 = ~3906

/2 = ~ 1953

[.......]

(repeat couple more times, and reach 1 possible answer)

It's basically equation [math]f(x)=\frac{N}{2^x}[/math] - possible answers left..

1) Am I living organism? Yes

2) Am I famous? Yes

3) Am I Woman? Yes

4) Do I have dog? Yes

5) Do I have pink car? Yes

6) Am I Paris Hilton? YES ;)

 

When there is 7.6 bln of people around the world, we can find anybody in the worst (but optimal) case in log2( 7.6*10^9 ) = 33 questions..

But that would require entire knowledge about the all 7.6 bln of people..

It's called "data partitioning"

https://en.wikipedia.org/wiki/Binary_space_partitioning

https://en.wikipedia.org/wiki/Partition_(database)

 

ps. dimreepr OP question could be rephrased to: is it possible to ask such a question which will eliminate the more possibilities than division the all possible answers by 2.. e.g. "Am I woman?" Is dividing entire population by 2, but "Am I am celebrity/politician/scientist?" is not, as very small amount of people are celebrity/politician/scientist..

 

Edited by Sensei
Link to comment
Share on other sites

Write a list of everyone's names (about 8 billion at the moment).

Then the first question is  "Am I in the first or second half of the list?"

That crops it down to about 4 billion.

You discard the "wrong" half of the list and keep the half with "you" in it.

Then you ask if you are in the first or second half of the remaining list.

 

Keep going, and you will find out who you are in 30 questions or so.

I  Read once of a Russian TV show based on the similar idea- 20 questions- which degenerated into unwatchability  when a team of two mathematicians armed with the dictionary (from which the words were chosen by the host) employed this tactic.

Link to comment
Share on other sites

I'm sorry everyone, my bad, I assumed. The parameters of the game are that both parties know of the person in question, be they famous or friend/acquaintance.   

Edited by dimreepr
Link to comment
Share on other sites

20 minutes ago, dimreepr said:

I'm sorry everyone, my bad, I assumed. The parameters of the game are that both parties know of the person in question, be they famous or friend/acquaintance.   

Nice. That gives me a huge advantage from the start. :D

Link to comment
Share on other sites

1 hour ago, dimreepr said:

I'm sorry everyone, my bad, I assumed. The parameters of the game are that both parties know of the person in question, be they famous or friend/acquaintance.   

Well, you could ask that as a first question...

Link to comment
Share on other sites

On 15.07.2018 at 4:22 PM, dimreepr said:

I'm sorry everyone, my bad, I assumed. The parameters of the game are that both parties know of the person in question, be they famous or friend/acquaintance.   

Quote

What's the most efficient algorithm to determine who's written on my forehead? 

Either I, and later John Cuthber, proposed using binary search algorithm. It can be used on alphabetically sorted list of available names of famous and/or personally known persons. It gives 33 questions for finding anybody living on the entire planet. But it can be used on any sorted list of data.

https://en.wikipedia.org/wiki/Binary_search_algorithm

If we limit only to English alphabet, a-z, there is 26 letters. You can find the first letter of surname in log2(26) = ~5 questions. Later the same with first name.

Yet another one for gender. Yet another one for whether person is famous or friend.

You could ask for age as well using binary search algorithm. If we limit age to range 0...128, exact age will be found in log2(128) = 7 questions (but I doubt such precision is needed).

e.g. age of person is higher than 64? No.  age of person is higher than 32? No. Age of person is higher than 16? Yes (this gives range 17...32)

19 questions to know: initials, age, sex and famous/friend status.

 

 

It can be also done with month of birth log2(12)= ~4 questions, and day of birth log2(31)=~5 questions.

 

Edited by Sensei
Link to comment
Share on other sites

2 hours ago, Sensei said:

Either I, and later John Cuthber, proposed using binary search algorithm.

As have I:

On 7/14/2018 at 2:50 PM, dimreepr said:

that's just a binary split search of each letter, the most efficient of the least efficient method, guessing. :P

2 hours ago, Sensei said:

It can be used on alphabetically sorted list of available names of famous and/or personally known persons.

A well put question has the potential to wipe out more than 50% of the potential list, such questions in series would converge on the answer faster

 

Link to comment
Share on other sites

17 minutes ago, dimreepr said:

A well put question has the potential to wipe out more than 50% of the potential list, such questions in series would converge on the answer faster

That's true if potential list is not balanced and you will be lucky to have answer in chunk of the list that has smaller quantity of answers.

e.g. "am I woman?" with a list of 10% women and 90% men (list is not balanced), and answer "yes" will reduce list to 10% (and you will reach the correct answer quicker), but answer "no" will reduce list only to 90% (and you will reach correct answer slower)..

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

 

 

Link to comment
Share on other sites

37 minutes ago, Sensei said:

That's true if potential list is not balanced and you will be lucky to have answer in chunk of the list that has smaller quantity of answers.

e.g. "am I woman?" with a list of 10% women and 90% men (list is not balanced), and answer "yes" will reduce list to 10% (and you will reach the correct answer quicker), but answer "no" will reduce list only to 90% (and you will reach correct answer slower)..

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

4

Fair enough +1.

Link to comment
Share on other sites

  • 3 months later...

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.