Who am I?

[dimreepr]

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

[koti]

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. 

[dimreepr]

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. 

Edited July 14, 2018 by dimreepr

[Sensei]

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..

 

 

[koti]

1 hour ago, dimreepr said:

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

Did I win?! 

[dimreepr]

10 minutes ago, koti said:

Did I win?! 

Given the topic, no... 

[Sensei]

 

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 log₂( 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 July 14, 2018 by Sensei

[koti]

16 hours ago, dimreepr said:

Given the topic, no... 

No sh**t ?

[John Cuthber]

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.

[dimreepr]

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 July 15, 2018 by dimreepr

[mistermack]

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. 

[dimreepr]

16 minutes ago, mistermack said:

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

Well now you know  I look forward to your answer.

[mistermack]

It's my mum. She's the only person I know.

[dimreepr]

Just now, mistermack said:

It's my mum. She's the only person I know.

I'm sorry, did I put this topic in the joke fora? 

[John Cuthber]

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...

[Sensei]

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 log₂(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 log₂(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 log₂(12)= ~4 questions, and day of birth log₂(31)=~5 questions.

 

Edited July 17, 2018 by Sensei

[dimreepr]

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. 

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

 

[Sensei]

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

 

 

[dimreepr]

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.

[JosefinaHarrison]

It depends upon the potential, there may be n number of answer to the above-mentioned question.