12 ms·

33 Questions

283 points by splike 13y ago

jloughry 13y ago
These need to be questions that are invariant over a lifetime: - Were you born in the northern hemisphere or southern? $2^{33}$ is sufficient for those alive now, but the human population is a dynamic function. Set a bit when the person dies?
- azatris 13y ago
  The Northern Hemisphere has roughly 90% of the population[1]. That is far from 50% what we should be looking for. [1]: http://en.wikipedia.org/wiki/Northern_Hemisphere http://en.wikipedia.org/wiki/Northern_Hemisphere
  - sgustard 13y ago
    Are you born above or below the tropic of cancer then: replace with whatever latitude separates humans into equal groups.
    - splike 13y ago
      This make other questions based on geography useless (as in the second question). Thats not to say the already given second question is better than your one
- GuiA 13y ago
  Even with questions invariant over a lifetime, edge cases like identical twins (same gender, same age, likely same upbringing, etc) are likely to mess with it.
tlongren 13y ago
"As an example, having the questions "Are you male?" and "Are you below the median age?" will not work " First question is "Are you male?". Made me laugh.
- psuter 13y ago
  You can have one, but not both.
- splike 13y ago
  I should reword that sentence to make the point clearer. As psuter said, you can have one but not both
  - tlongren 13y ago
    It was much more clear after having it pointed out to me.
gkoberger 13y ago
Very interesting thought experiment. A few random thoughts: Reminds me of Panoptic by the EFF: https://panopticlick.eff.org/ https://panopticlick.eff.org/ Everyone's ID would change as time passed (if they move, if they age, if they get a sex change, etc). The best questions for this are inherently "irrelevant", since "relevant" questions tend to be statistically linked. So, questions like "Was the second letter of your first girlfriend's middle name between A and M?" is better than "Were you younger than 20 when you had your first girlfriend?", since we can likely guess the latter based on the other statistics. It's very unlikely every ID will be unique if only asking 33 yes/no questions. I mean, look at two twins living together -- very few questions will be able to differentiate between them. I think it's possible to do based on a random snapshot in time, however less possible if it's meant to last a lifetime. I also think the questions exist, but not in a manner that we'd be able to come up with on our own. As in, I believe that a program that knew every detail about every human could create 33 yes/no questions that differentiated people, however I don't believe we could do it ourselves. I also wonder how many questions would be required to ask non-yes/no questions and get a completely unique ID for everyone. For example, questions like "weight? languages spoken? birth place?".
- deleted 13y ago
  [deleted]
- buo 13y ago
  If you allow questions with n possible answers, then you need at least ceil(log_n(7e9)) questions, where log_n means logarithm base n. I don't know if there is a simple formula for the case where different questions allow different number of answers.
- Scarblac 13y ago
  But""Was the second letter of your first girlfriend's middle name between A and M?" is a bad question on many levels -- people who aren't attracted to females, people who are but have never had a girlfriend (including children), people who got married to their wife as the start of the relationship, and cultures where "girlfriend" would be hard to define because of that sort of thing. I can think of almost perfectly 50/50 questions based on odd/evenness of numbers (is your current weight in grams/age in hours/number of hairs odd or even) but those are completely time dependent.
deletes 13y ago
Seems impossible to me, for example what question would separate two identical twins( identical in dna and when born ). And let's say you find such a question, there is no way that question would divide half of the population.
- aroman 13y ago
  Well if you had conditional questions, you could ask who was born first.
  - deletes 13y ago
    That question doesn't even apply since you can only ask it to two twins, not a single person.
    - 30thElement 13y ago
      Going along with what someone said earlier, your last question can be "Were you born after someone who answered the previous 32 questions the same as you", which works to identify twins as well as people in general. Although I don't know how this would work for triplets (or any larger number of "twins" than 2); you'd have to make the previous 32 questions split them into groups of at most 2.
ZirconCode 13y ago
Just use: - Birthday (19~ bits) - Rough Location (remaining bits) And base the questions around those two, for example, where you born on a 1-15th, does the city you were born in start with the letter's a-k. This part would be an exercise in statistics, I would think. edit: And one bit for if you were the first to be born of two identical twins =p
- gkoberger 13y ago
  Triplets?
  - deletes 13y ago
    Just add time of birth. I don't see how you could split correctly with a bit for twins.
    - mef 13y ago
      What if time is unknown?
- deleted 13y ago
  [deleted]
- bnegreve 13y ago
  That would work if people birthdays were uniformly distributed among the dates. But that's not the case. (Most people born 100 years ago are now dead.)
  - ronaldx 13y ago
    As long as you split the distribution uniformly into categories with the same number of people, it doesn't matter that it's not uniform by date.
    - bnegreve 13y ago
      Yes, except that you cannot expect people to be able to answer this "question" anymore. There is no doubt that you can uniquely identify the world population with 33 bits, so I guess the problem is to do it with questions people can answer themself.
benstein 13y ago
Do the answers have to be knowable? Time independent? For example, "are you below the median age at this exact second?" That is not a knowable answer, and changes by the second, but it does give you an exact 50/50 split. Repeat N times for each split and we're getting very very close.
psuter 13y ago
Interesting exercise, which I'd call impossible in the given form. Imagine someone magically came up with 32 statistically independent binary indicators. Now you need to come up with the 33th question Q such that if you pick any two persons who are similar up to the 32nd bit, that single question must allow to distinguish them. Sounds hard.
- ronaldx 13y ago
  Question 33 has to split any category of people formed from the first 32 questions - very awkward, as you say. Here is a moderately-functional question 33, though: "Are you further North than any other person who has given the same answers as you for the first 32 questions?"
  - psuter 13y ago
    Excellent :) Of course there's something to be said about the ability to realistically answer reliably.
  - chill1 13y ago
    > "Are you further North than any other person who has given the same answers as you for the first 32 questions?" What if one of the persons was not on the planet at the time?
  - Accredified 13y ago
    Just make questions 33 be the your assigned number then. 0 or 1
aria 13y ago
Question 1: What is the first bit in your unique 33-bit string? Question 2: What is the first bit in your unique 33-bit string? ...
- Peaker 13y ago
  I'm pretty sure you didn't mean what you wrote! But maybe I'm whooshing?
jloughry 13y ago
Added pull requests to extend the address space from 33 bits to 36 bits to accommodate our revered ancestors, and a bit to indicate liveness. TODO: don't implement zombies or ghosts at this time (YAGNI principle).
ealexhudson 13y ago
A useful question might revolve around language or concepts a person knows, but then this becomes a lot more difficult if the questioner doesn't know which language/concepts a person wouldn't understand (and therefore whether they could even answer the question) - and if they do know, there is a priori knowledge effectively.
tinco 13y ago
33 questions is sort of the Shannon-Hartley optimal encoding of identifying information about human beings. That means to come up with them is identical to finding an optimal compression of identifying data. Necessarily, as the second question already implies, for this question to correctly divide the population in half, you would have to group large amounts of small populations together, resulting in very long questions. For example, if you'd like to make another geographical question that's independent of the second one, it would have to divide in half every population of the 6 countries you mentioned. The next question would necessarily have to divide those 12 again. By the way, the first question you ask is already suboptimal when combined with the second question, as those countries together probably do not have a clean 50% male/female split. (if they do, you should really explain that as it's not obvious)
powertower 13y ago
Another problem not mentioned is that the questions should be about the content that does not allow for the answer to change over time. Otherwise the ID is no good.
aleprok 13y ago
If the goal is to have questions which can be answered only with yes or no. I don't think asking for location of the person is good thing, because there would be so many questions as there is locations. "Do you live in China, India, The United States, Indonesia, Brazil or Pakistan?" is not good question.
- tonyarkles 13y ago
  I'm guessing that that question is meant as a yes/no question that would divide the world population in half.
- kalleboo 13y ago
  "Were you born east or west of longitude X" (where X is a longitude that would split the population roughly in half).
  - aleprok 13y ago
    Yes that would work and north of x..
ramanujam 13y ago
On a related note, this has a very interesting significance in the world of privacy and anonymous tracking. http://33bits.org/about/ http://33bits.org/about/
powrtoch 13y ago
I don't think this problem is solvable in any elegant form, but it is solvable. You'll just end up with massively conjunctive questions that you can't even hold in your head at once, like "27: Are you a non-practicing Catholic with exactly three children, or an asian owner of a minivan produced between 1998 and 2004 that isn't green, or a licensed boat mechanic with astigmatism, or..." and so on for the next 6 pages. In short, you can draw categories to include or exclude as precise a number as you like, you just have to be willing to draw really, really complicated boundaries.
- measure2xcut1x 13y ago
  Here's my admittedly naive Sunday afternoon spitball on an elegant solution: I like the idea of a human UUID/GUID type identifier. I would also like to think that this is solvable using strictly biological and physical properties, sampled at birth. Otherwise, time and culture factors would seem make it difficult to produce a static set of "apples to apples" questions and answers. I wonder if the right maths applied to existing genetic and forensics big data sets could produce the 33 questions.
  - ghostdiver 13y ago
    DNA is your UUID/GUID
    - pavel_lishin 13y ago
      Unless you're one of a set of twins/triplets/etc.
      - heynairb 13y ago
        append datetime string of birth. Boom problem solved.
        deleted 13y ago
        [deleted]
sz4kerto 13y ago
> To contribute to the project, open up a pull request and add your question to the list below. All questions are open to debate and discussion. This is a completely wrong way to approach the problem. Because the questions should all divide the population into two parts the questions should be 'matched' to each other. This approach is a bit like doing a PCA by figuring out one component, then the other, then the rest... One way to solve this problem is to have a lot of yes/no questions (like a big Karnaugh-table), then everybody would have a long bitstring as his unique ID. Now you need to compress that bitstring -- like the minimization of the Karnaugh-table. http://en.wikipedia.org/wiki/Karnaugh_map http://en.wikipedia.org/wiki/Karnaugh_map -- you need to generalize this for N number of questions (which can be done), then you'd have 33 complex questions like 'is it true that (you live in NA AND you are male) OR (you live in Canada AND you are white AND ) .. and so on and on.
tehwebguy 13y ago
This reminds me of Akinator: http://en.akinator.com http://en.akinator.com It's a little spammy nowadays, but it's had enough input that it seems pretty amazingly accurate at "guessing" what / who you are thinking of in ~ 25 questions.
- kalleboo 13y ago
  I thought of this too, or at least a site similar to it. It has so much input that it's good at even very obscure people/characters.
- dkokelley 13y ago
  It's similar, except the questions it asks can be crafted based on previous responses.
anilshanbhag 13y ago
33 is not the constraint. If we increase the limit to 50 and these 50 questions can fingerprint an individual then that will be really interesting. Some hard problems :- 1. Distinguish twins 2. Using characters in names as some like Chinese use non-ascii names.
- vinceguidry 13y ago
  You could distinguish twins by first identifying the twins, then by asking which one's name starts earlier in the alphabet, or whatever analogue exists in languages without an alphabet. Encode appropriately.
jpalioto 13y ago
Fun version of that ... http://en.akinator.com/ http://en.akinator.com/
gradys 13y ago
I thought it would be more plausible and probably more interesting to do this in maybe 40 questions. To do this in 33, as several others have pointed out, would require 33 questions that each almost perfectly bisect the population and are almost perfectly independent of each other. With 40 or 45, we could relax that a bit and use questions that are actually meaningful. Two people who are within a few bits of each other would actually be similar in ways we care about, unlike two people who are similar because their transliterated last names both appear in the last half of the alphabet.
stbullard 13y ago
Fun to think about, but in the real world, no question neatly divides people, even the gender one. To quote Reddit's u/tailcalled[1], the exo-software/meatspace world is even less standardized than the software world: Falsehoods programmers believe about gender: http://www.cscyphers.com/blog/2012/06/28/falsehoods-programmers-believe-about-gender/ http://www.cscyphers.com/blog/2012/06/28/falsehoods-programm... Falsehoods programmers believe about names: http://www.kalzumeus.com/2010/06/17/falsehoods-programmers-believe-about-names/ http://www.kalzumeus.com/2010/06/17/falsehoods-programmers-b... Falsehoods programmers believe about addresses: http://www.mjt.me.uk/posts/falsehoods-programmers-believe-about-addresses/ http://www.mjt.me.uk/posts/falsehoods-programmers-believe-ab... Falsehoods programmers believe about time: http://infiniteundo.com/post/25326999628/falsehoods-programmers-believe-about-time http://infiniteundo.com/post/25326999628/falsehoods-programm... More falsehoods programmers believe about time: http://infiniteundo.com/post/25509354022/more-falsehoods-programmers-believe-about-time-wisdom http://infiniteundo.com/post/25509354022/more-falsehoods-pro... Falsehoods programmers believe about geography: http://wiesmann.codiferes.net/wordpress/?p=15187&lang=en http://wiesmann.codiferes.net/wordpress/?p=15187&lang=en [1] http://www.reddit.com/r/programming/comments/1fc147/falsehoods_programmers_believe_about_addresses/ca8sirp http://www.reddit.com/r/programming/comments/1fc147/falsehoo...
- raverbashing 13y ago
  Yes, there's so much about these. Of course, in practice, you usually target your system to a narrow set of users at first. But yeah, if you're facebook, or work with an airline booking system, for example, you will most likely hit every single item on these lists
  - brownbat 13y ago
    > you usually target your system to a narrow set of users at first [but eventually the exceptions show up] Reminded me of the College Humor sketch about security questions: http://www.collegehumor.com/embed/6936880/security-questions-sketch-ucb http://www.collegehumor.com/embed/6936880/security-questions...
    - 13y ago
Laremere 13y ago
Assuming that the person doesn't necessarily need to know their answer (which is important for babies anyways) the answer is trivial. The first question would be "Given that we ordered all humans in order of the time of their birth, would the 1st bit of your position in the ordering be 1?", continue the other 32 questions with the remaining 32 bits.
- fat0wl 13y ago
  lol too much
fmax30 13y ago
So you want to create a data set with entropy = 1 . Think of this in terms of a hash function , You want to create a hash which only has an address space of 33 bits. Something in terms of H(Alice) = 0x12321 {H is a function which generates 0x12321 to store the data of alice) Doesn't this sound like perfect hashing with limited memory. I don't really think that this can be done with such memory constraints. Even now we cannot produce a perfect hash function that uses 1 bit / key. The theoretical best we can do is 1.44 bit / key. And the practical best we have done till now is 2.5 bits per key. [1] This may just be possible without the memory constraint that is , you answer N number of questions which uniquely identify you. (where N > 48 ) [1] http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_p...
Houshalter 13y ago
This is really interesting actually. Your entire "uniqueness" can be summed up in 33 yes or no questions, in theory.
- jeffdavis 13y ago
  I don't think that's quite the right interpretation. Let's say that the human population increased by a factor of 1000. Does that mean you have 10 more bits of uniqueness? You didn't change at all. In actuality, you already had those 10 more bits of uniqueness, and people just need to ask more questions to find out which one of the many unique people you are. This is about identification, not uniqueness.
unfamiliar 13y ago
Are you male? This will not split the population 50/50. One group will be slightly larger, and you then only have 32 questions to subdivide this larger group into further categories which is impossible. This is not possible unless the categories _precisely_ bisect the group each time.
mcphilip 13y ago
I think first you have to show a question exists that effectively separates identical twins before you spend much time working on broad questions like gender and geography.
- edsrzf 13y ago
  Maybe something like "Do you have more older siblings than younger siblings?" would work. One twin has to be born before the other. That question has some problems, but I feel like it could serve as the basis for a more specific question that would define how an only child or middle child would answer without introducing much bias. It would also have to define how half-siblings are counted and probably some other things.
  - pavel_lishin 13y ago
    It's entirely possible that the twins would not know which one was born first.
    - daleharvey 13y ago
      Its entirely possible the person could not know the answer to any of the questions, I dont think that really counts
  - RogerL 13y ago
    So you are going to burn one entire question that is entirely worthless for the vast majority of Chinese that have been born recently?
    - Intermernet 13y ago
      Interesting read: "One Child Policy and Arising of Man-Made Twins". http://paa2013.princeton.edu/papers/130113 http://paa2013.princeton.edu/papers/130113
IsNotMyIp 13y ago
Do you speak english as your main language? Could be a good question too? What do u think?
fat0wl 13y ago
The 33-question issue is a tough one for sure. I'm instead left wondering how many extra questions (35 bits? 36 bits?) it would have to be expanded to in order to produce unique results but without having to be particularly clever in producing the questions. I bet it wouldn't take as many extra as one might be inclined to think.
- pit 13y ago
  Good point, especially because at 33 bits, storing everyone's ID would only take about 29 gigabytes. 7,126,462,675 people * 33 bits per person / 8 bits per byte = 29,396,658,534 bytes World population source: http://www.census.gov/popclock/ http://www.census.gov/popclock/
jv22222 13y ago
Less than half the population will be able to "read" the questions due to not speaking English...
rattray 13y ago
This is a fun exercise, but as others have pointed out likely impossible in its current form. We don't have true constraints on space though; why limit to 33 bits? How could we still provide a meaningful UUID to each person? A UUID based on time and location of birth might be more feasible than any other approach, since neither will change and it's the least likely to be ambiguous. Capturing UTC at the time of cutting or otherwise removing the umbilical cord could be one way of choosing as precise, non-debatable a timestamp as any. Adding lat/long and, say, the first byte of the UTF-8 character of the mother's name (or an aspect of the mother's UUID?) could get you the rest of the way there. Of course, this falls over in places without access to precise timing and geolocation.
- edelans 13y ago
  I think the limitation to 33 bits is because this is the smallest power of 2 which is higher than the world's population: 2^32 = 4.29 billions, 2^33 = 8.58 billions, 2^34 = 17 billions,
- r0muald 13y ago
  Another pitfall of this thought-experiment is that there is no room for the constant number of humans who die and are born every day: the set of 33 questions hypothetical questions of today will not be valid tomorrow.
ye 13y ago
First 33 bits of SHA512(your DNA) First 33 bits of SHA512(your 3D GPS location)
- deathanatos 13y ago
  As someone else mentions, this doesn't work, as the birthday problem[1] applies here. You need to ensure collisions won't happen; SHA512 does not to that. (The probability of a collision in 512 bits is near impossible; in 33 bits, much less so.) [1]: http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem
abentspoon 13y ago
It's not enough to find 33 independent questions that evenly split the world's population. An optimal, though inelegant solution to that goal might look something like this: "Is the {1..33}th bit of sha1(name : location : date of birth) 1?". Clearly you'll have tons of collisions with that solution, as you would have with any solution using 33 independent questions. To uniquely identify people, we'd either need to use more bits, or look very closely at the population and derive very specific questions.
- upquark 13y ago
  > Clearly you'll have tons of collisions with that solution Why? If we assume the hash code assignment to one of the 2^32 people is uniformly random from a set of 2^160 codes, the odds of finding a collision are astronomically small (order of 2^-95 or so). Am I missing something?
  - jules 13y ago
    You are not taking the entire hash, you are only taking the first 33 bits of the hash. Since there are only about 8.5 billion different values for the 33 bits and there are about 7 billion people, the odds are astronomically low that each of those 7 billion people will receive a different one of those 8.5 billion possibilities. This is the birthday paradox with instead of 365 days you have 2^33 possible answer values and instead of 23 people you have 7 billion people. I leave it as an exercise for the reader to fill in these values into one of the formulas to calculate the probability of successfully giving each person a unique 33 bit answer: http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem
    - upquark 13y ago
      > You are not taking the entire hash, you are only taking the first 33 bits Right, my bad, didn't pay attention to the problem we are trying to solve :)
- jules 13y ago
  It is interesting to see your comment way down the thread, even though it is by far the best.
DigitalSea 13y ago
This seems like it would be a lot of work. The intensity and specificity of the questions that would need to be asked would have to be quite unique. It might be possible, but without excluding people of the world because they get lumped into a group, it seems like maybe 33 questions might not be enough to uniquely identify everyone in the world.
S4M 13y ago
Do the questions have to be constant over time? If not it can trivially be solved by asking: Are you born before or after time t? 33 times, where t is the median date of birth of your population. You just need to recompute t 33 times (and know the date of birth of every single person in the world).
tehwalrus 13y ago
The set of questions that would do this is probably a list of genetic questions. "do you have the mumble allele?" etc.
dkokelley 13y ago
Wouldn't the best way to do this be to ask questions related to genetic markers? You require 33 yes/no questions that independently divide the population in half, but has near-uniform distribution otherwise (each populace half has no relationship to the other questions). Are there 33 genetic markers that each has no correlation on the presence of the others?
dinkumthinkum 13y ago
It's an interesting idea ... But no I don't think it is possible in any way that is not turning the list into a set of questions about their genetics or DNA.
brownbat 13y ago
This project assumes we can know things that are not really knowable for everyone. It starts with gender and birthplace, both tricky questions in some situations. So maybe we get to assume we have some oracle that helps us simplify the hard questions. At that stage, it's easy. Begin with, "Assume we build a list of people sorted by time of birth (with some arbitrary tiebreakers, like proximity of birthplace to Barbados, or darkness of hair color...)." Question 1: Are you on the top half or bottom half of this list? Question 2: Are you on the top quarter or bottom quarter of the half? Question 3: ...
- deathanatos 13y ago
  I had come up with something similar: Question 1: Are you north of an east-west line that perfectly divides the population in half? (proceed to continue to divide each section in half.) Of course, determining the position of those lines is damn near impossible. And as soon as someone hops on a plane, the whole thing comes crashing down.
  - brownbat 13y ago
    I like it. Maybe "were you north of an east-west line" when this list was made. I guess it gets tricky when people are born. Wait a minute, just realized this whole question breaks down if we don't recycle numbers from the dead back to the newly born... and there's no guarantee that all of the dead will sufficiently resemble all of the newborns. I want my money back. :)
jayd16 13y ago
I bet you could make a lot of progress by dividing GPS coordinates evenly by population. Simple binary search by primary residence and then leave some space for division within a household.
Zarathust 13y ago
I don't think it is possible with exactly 33 questions. It will probably require more than that. Binary numbers have the property of adding twice as many numbers +1 for every new bit. For example if you already have 7 bits and you add an 8th one, then you'll be able to represent 127 numbers with that bit off and 128 numbers with that bit on. To properly mimic this property with yes/no questions, you will have to come up with questions that divide the whole Earth's population equally AT EVERY NEW QUESTION. Even the most obvious one, "are you (fe)male?" is slightly biased toward men (according to wikipedia). At every question that skew your 50/50, you'll have to add another question beyond 33 to catch up with this.
- thethimble 13y ago
  All questions must be independent. That's too hard. I would be surprised to find even a handful of questions that have no statistical correlation when applied to all people in the world.
- enriquepablo 13y ago
  > To properly mimic this property with yes/no questions, you will have to come up with questions that divide the whole Earth's population equally AT EVERY NEW QUESTION. Not only that: The first question must divide the population in 2; the second question must divide each of the 2 subsets produced by the first question in 2; and the third has to perfectly divide the 4 subsets produced by the second... And this independently of the order in which you make the questions.
knowtheory 13y ago
No one here seems to have mentioned Hunch (http://en.wikipedia.org/wiki/Hunch_(website) http://en.wikipedia.org/wiki/Hunch_(website) ). Picking discrete questions like this is equivalent to building a decision tree for humanity. This is actually something that could be approached as an engineering problem (and there are mechanisms for optimizing decision trees). The problem still remains in the face of both the technological capabilities of decision trees, and practical implementations like Hunch.com, that decision trees are reductive and discrete. Reality is neither discrete nor reductive. It may very well be the case that there is a set of questions that could uniquely identify humans, but the insight that could be drawn from those questions might be essentially pointless. For example: * Were you born in the northern hemisphere? * Were you born on an even numbered year in the Gregorian calendar? * Is the country of your birth governed through a representative system?
stevewilhelm 13y ago
Is the intent of this exercise to build a unique identifier that the individual could reproduce over the course of their life, or does it just uniquely identify them at the time they answered the questions? I ask because questions like number of siblings, favorite movie, etc. would change over time.
fela 13y ago
Even if the questions were perfect (each question splitting the population in two exact halves, and all questions totally independent from each other) and therefore the algorithm would give each person a perfectly random number, the birthday paradox [1] tells us that even for just square(2^33)=~ 93k people we would have 50% probability of having a collision. To work we would need more bits. (Either that or create questions that are _not_ independent, so crafted in a way to make sure each person gets a different number) [1] http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem
- deathanatos 13y ago
  No: the linked article requires that further questions split the previous groups each in half. The first question must split the group in half, the second question must split those two groups in half, and so on. When we hit the last bit, the final question is splitting groups of 2 people into the last bit, and each person has been assigned a unique number. In this manner, 33 bits is enough, and the birthday problem is avoided. The page mentions all this.
yiransheng 13y ago
If anyone is interested in seeing such a application in a fictional setting, I suggest the anime Death Note, if nothing else for its entertainment value. For those who are familiar with the story, the questions L asked in order to narrow down Kira suspects to a limited demographics in a small region in Japan, among billions of candidates, were some good ones. A good article that analyzes the plot from a information theory perspective: [http://www.gwern.net/Death%20Note%20Anonymity](http://www.gwern.net/Death%20Note%20Anonymity) http://www.gwern.net/Death%20Note%20Anonymity](http://www.gw....
josscrowcroft 13y ago
People have so much time on their hands.
vacri 13y ago
How many questions would you need to differentiate between identical twins, particularly if they live and work together? Take identical twin sons of a subsistence farmer - they live together, work together on the same things, know the same people, have the same genetic makeup, and whichever was the first twin born may not have been recorded. You could ask their names, but that's not a yes/no question. Or even twins who are still babies, no work required? Some cultures wouldn't even have named them yet.
- incompatible 13y ago
  Multiple births would be bad enough, and then you have people with dementia who can't remember the answer to most of the questions, and people in a coma who can't answer questions at all. The chance of succeeding with this exercise is approximately zero.
obilgic 13y ago
Possible, You need 33 answers but more than 33 questions.
loganu 13y ago
Could you not have way more than 33 questions created, (maybe a couple hundred) but change what questions are asked based on previous answers? Use the previous answers to determine the strongest next question to ask? If an early answer states the candidate lives in the north hemisphere, there's no point in asking them if they live on a landlocked African country... or whatever much more complicated questions could arrive.
cbr 13y ago
A boring solution: Question n. Consider the number of your birth out of all people currently alive. When you divide by 2^n and take the remainder, is it odd?
ruswick 13y ago
This is a really cool concept, but one that is totally impossible. In the actual world, few things are truly independent. Even if you could find 33 binary questions that did not correlate with each other at all, you still run the risk of having multiple people yield the same 33 answers. Just because two things aren't statistically linked does not mean that they will never overlap.
Strilanc 13y ago
An easy way to construct the questions is to ask for increasingly precise time and location of birth. There will be corner cases, but then so does asking if someone is male.
deleted 13y ago
[deleted]
k__ 13y ago
Isn't this solvable to a degree by just asking a big amount of yes/no questions to a big amout of people and then removing all those questions that didn't identify people any further?

283 points by splike 13y ago

These need to be questions that are invariant over a lifetime: - Were you born in the northern hemisphere or southern? $2^{33}$ is sufficient for those alive now, but the human population is a dynamic function. Set a bit when the person dies?

azatris 13y ago
The Northern Hemisphere has roughly 90% of the population[1]. That is far from 50% what we should be looking for. [1]: http://en.wikipedia.org/wiki/Northern_Hemisphere http://en.wikipedia.org/wiki/Northern_Hemisphere
- sgustard 13y ago
  Are you born above or below the tropic of cancer then: replace with whatever latitude separates humans into equal groups.
  - splike 13y ago
    This make other questions based on geography useless (as in the second question). Thats not to say the already given second question is better than your one
GuiA 13y ago
Even with questions invariant over a lifetime, edge cases like identical twins (same gender, same age, likely same upbringing, etc) are likely to mess with it.

tlongren 13y ago

"As an example, having the questions "Are you male?" and "Are you below the median age?" will not work " First question is "Are you male?". Made me laugh.

psuter 13y ago
You can have one, but not both.
splike 13y ago
I should reword that sentence to make the point clearer. As psuter said, you can have one but not both
- tlongren 13y ago
  It was much more clear after having it pointed out to me.

gkoberger 13y ago

Very interesting thought experiment. A few random thoughts: Reminds me of Panoptic by the EFF: https://panopticlick.eff.org/ https://panopticlick.eff.org/ Everyone's ID would change as time passed (if they move, if they age, if they get a sex change, etc). The best questions for this are inherently "irrelevant", since "relevant" questions tend to be statistically linked. So, questions like "Was the second letter of your first girlfriend's middle name between A and M?" is better than "Were you younger than 20 when you had your first girlfriend?", since we can likely guess the latter based on the other statistics. It's very unlikely every ID will be unique if only asking 33 yes/no questions. I mean, look at two twins living together -- very few questions will be able to differentiate between them. I think it's possible to do based on a random snapshot in time, however less possible if it's meant to last a lifetime. I also think the questions exist, but not in a manner that we'd be able to come up with on our own. As in, I believe that a program that knew every detail about every human could create 33 yes/no questions that differentiated people, however I don't believe we could do it ourselves. I also wonder how many questions would be required to ask non-yes/no questions and get a completely unique ID for everyone. For example, questions like "weight? languages spoken? birth place?".

deleted 13y ago
[deleted]
buo 13y ago
If you allow questions with n possible answers, then you need at least ceil(log_n(7e9)) questions, where log_n means logarithm base n. I don't know if there is a simple formula for the case where different questions allow different number of answers.
Scarblac 13y ago
But""Was the second letter of your first girlfriend's middle name between A and M?" is a bad question on many levels -- people who aren't attracted to females, people who are but have never had a girlfriend (including children), people who got married to their wife as the start of the relationship, and cultures where "girlfriend" would be hard to define because of that sort of thing. I can think of almost perfectly 50/50 questions based on odd/evenness of numbers (is your current weight in grams/age in hours/number of hairs odd or even) but those are completely time dependent.

deletes 13y ago

Seems impossible to me, for example what question would separate two identical twins( identical in dna and when born ). And let's say you find such a question, there is no way that question would divide half of the population.

aroman 13y ago
Well if you had conditional questions, you could ask who was born first.
- deletes 13y ago
  That question doesn't even apply since you can only ask it to two twins, not a single person.
  - 30thElement 13y ago
    Going along with what someone said earlier, your last question can be "Were you born after someone who answered the previous 32 questions the same as you", which works to identify twins as well as people in general. Although I don't know how this would work for triplets (or any larger number of "twins" than 2); you'd have to make the previous 32 questions split them into groups of at most 2.

ZirconCode 13y ago

Just use: - Birthday (19~ bits) - Rough Location (remaining bits) And base the questions around those two, for example, where you born on a 1-15th, does the city you were born in start with the letter's a-k. This part would be an exercise in statistics, I would think. edit: And one bit for if you were the first to be born of two identical twins =p

gkoberger 13y ago
Triplets?
- deletes 13y ago
  Just add time of birth. I don't see how you could split correctly with a bit for twins.
  - mef 13y ago
    What if time is unknown?
deleted 13y ago
[deleted]
bnegreve 13y ago
That would work if people birthdays were uniformly distributed among the dates. But that's not the case. (Most people born 100 years ago are now dead.)
- ronaldx 13y ago
  As long as you split the distribution uniformly into categories with the same number of people, it doesn't matter that it's not uniform by date.
  - bnegreve 13y ago
    Yes, except that you cannot expect people to be able to answer this "question" anymore. There is no doubt that you can uniquely identify the world population with 33 bits, so I guess the problem is to do it with questions people can answer themself.

benstein 13y ago

Do the answers have to be knowable? Time independent? For example, "are you below the median age at this exact second?" That is not a knowable answer, and changes by the second, but it does give you an exact 50/50 split. Repeat N times for each split and we're getting very very close.

psuter 13y ago

Interesting exercise, which I'd call impossible in the given form. Imagine someone magically came up with 32 statistically independent binary indicators. Now you need to come up with the 33th question Q such that if you pick any two persons who are similar up to the 32nd bit, that single question must allow to distinguish them. Sounds hard.

ronaldx 13y ago
Question 33 has to split any category of people formed from the first 32 questions - very awkward, as you say. Here is a moderately-functional question 33, though: "Are you further North than any other person who has given the same answers as you for the first 32 questions?"
- psuter 13y ago
  Excellent :) Of course there's something to be said about the ability to realistically answer reliably.
- chill1 13y ago
  > "Are you further North than any other person who has given the same answers as you for the first 32 questions?" What if one of the persons was not on the planet at the time?
- Accredified 13y ago
  Just make questions 33 be the your assigned number then. 0 or 1

aria 13y ago

Question 1: What is the first bit in your unique 33-bit string? Question 2: What is the first bit in your unique 33-bit string? ...

Peaker 13y ago
I'm pretty sure you didn't mean what you wrote! But maybe I'm whooshing?

jloughry 13y ago

Added pull requests to extend the address space from 33 bits to 36 bits to accommodate our revered ancestors, and a bit to indicate liveness. TODO: don't implement zombies or ghosts at this time (YAGNI principle).

ealexhudson 13y ago

A useful question might revolve around language or concepts a person knows, but then this becomes a lot more difficult if the questioner doesn't know which language/concepts a person wouldn't understand (and therefore whether they could even answer the question) - and if they do know, there is a priori knowledge effectively.

tinco 13y ago

33 questions is sort of the Shannon-Hartley optimal encoding of identifying information about human beings. That means to come up with them is identical to finding an optimal compression of identifying data. Necessarily, as the second question already implies, for this question to correctly divide the population in half, you would have to group large amounts of small populations together, resulting in very long questions. For example, if you'd like to make another geographical question that's independent of the second one, it would have to divide in half every population of the 6 countries you mentioned. The next question would necessarily have to divide those 12 again. By the way, the first question you ask is already suboptimal when combined with the second question, as those countries together probably do not have a clean 50% male/female split. (if they do, you should really explain that as it's not obvious)

powertower 13y ago

Another problem not mentioned is that the questions should be about the content that does not allow for the answer to change over time. Otherwise the ID is no good.

aleprok 13y ago

If the goal is to have questions which can be answered only with yes or no. I don't think asking for location of the person is good thing, because there would be so many questions as there is locations. "Do you live in China, India, The United States, Indonesia, Brazil or Pakistan?" is not good question.

tonyarkles 13y ago
I'm guessing that that question is meant as a yes/no question that would divide the world population in half.
kalleboo 13y ago
"Were you born east or west of longitude X" (where X is a longitude that would split the population roughly in half).
- aleprok 13y ago
  Yes that would work and north of x..

ramanujam 13y ago

On a related note, this has a very interesting significance in the world of privacy and anonymous tracking. http://33bits.org/about/ http://33bits.org/about/

powrtoch 13y ago

I don't think this problem is solvable in any elegant form, but it is solvable. You'll just end up with massively conjunctive questions that you can't even hold in your head at once, like "27: Are you a non-practicing Catholic with exactly three children, or an asian owner of a minivan produced between 1998 and 2004 that isn't green, or a licensed boat mechanic with astigmatism, or..." and so on for the next 6 pages. In short, you can draw categories to include or exclude as precise a number as you like, you just have to be willing to draw really, really complicated boundaries.

measure2xcut1x 13y ago
Here's my admittedly naive Sunday afternoon spitball on an elegant solution: I like the idea of a human UUID/GUID type identifier. I would also like to think that this is solvable using strictly biological and physical properties, sampled at birth. Otherwise, time and culture factors would seem make it difficult to produce a static set of "apples to apples" questions and answers. I wonder if the right maths applied to existing genetic and forensics big data sets could produce the 33 questions.
- ghostdiver 13y ago
  DNA is your UUID/GUID
  - pavel_lishin 13y ago
    Unless you're one of a set of twins/triplets/etc.
    - heynairb 13y ago
      append datetime string of birth. Boom problem solved.
      - deleted 13y ago
        [deleted]

sz4kerto 13y ago

> To contribute to the project, open up a pull request and add your question to the list below. All questions are open to debate and discussion. This is a completely wrong way to approach the problem. Because the questions should all divide the population into two parts the questions should be 'matched' to each other. This approach is a bit like doing a PCA by figuring out one component, then the other, then the rest... One way to solve this problem is to have a lot of yes/no questions (like a big Karnaugh-table), then everybody would have a long bitstring as his unique ID. Now you need to compress that bitstring -- like the minimization of the Karnaugh-table. http://en.wikipedia.org/wiki/Karnaugh_map http://en.wikipedia.org/wiki/Karnaugh_map -- you need to generalize this for N number of questions (which can be done), then you'd have 33 complex questions like 'is it true that (you live in NA AND you are male) OR (you live in Canada AND you are white AND ) .. and so on and on.

tehwebguy 13y ago

This reminds me of Akinator: http://en.akinator.com http://en.akinator.com It's a little spammy nowadays, but it's had enough input that it seems pretty amazingly accurate at "guessing" what / who you are thinking of in ~ 25 questions.

kalleboo 13y ago
I thought of this too, or at least a site similar to it. It has so much input that it's good at even very obscure people/characters.
dkokelley 13y ago
It's similar, except the questions it asks can be crafted based on previous responses.

anilshanbhag 13y ago

33 is not the constraint. If we increase the limit to 50 and these 50 questions can fingerprint an individual then that will be really interesting. Some hard problems :- 1. Distinguish twins 2. Using characters in names as some like Chinese use non-ascii names.

vinceguidry 13y ago
You could distinguish twins by first identifying the twins, then by asking which one's name starts earlier in the alphabet, or whatever analogue exists in languages without an alphabet. Encode appropriately.

jpalioto 13y ago

Fun version of that ... http://en.akinator.com/ http://en.akinator.com/

gradys 13y ago

I thought it would be more plausible and probably more interesting to do this in maybe 40 questions. To do this in 33, as several others have pointed out, would require 33 questions that each almost perfectly bisect the population and are almost perfectly independent of each other. With 40 or 45, we could relax that a bit and use questions that are actually meaningful. Two people who are within a few bits of each other would actually be similar in ways we care about, unlike two people who are similar because their transliterated last names both appear in the last half of the alphabet.

stbullard 13y ago

Fun to think about, but in the real world, no question neatly divides people, even the gender one. To quote Reddit's u/tailcalled[1], the exo-software/meatspace world is even less standardized than the software world: Falsehoods programmers believe about gender: http://www.cscyphers.com/blog/2012/06/28/falsehoods-programmers-believe-about-gender/ http://www.cscyphers.com/blog/2012/06/28/falsehoods-programm... Falsehoods programmers believe about names: http://www.kalzumeus.com/2010/06/17/falsehoods-programmers-believe-about-names/ http://www.kalzumeus.com/2010/06/17/falsehoods-programmers-b... Falsehoods programmers believe about addresses: http://www.mjt.me.uk/posts/falsehoods-programmers-believe-about-addresses/ http://www.mjt.me.uk/posts/falsehoods-programmers-believe-ab... Falsehoods programmers believe about time: http://infiniteundo.com/post/25326999628/falsehoods-programmers-believe-about-time http://infiniteundo.com/post/25326999628/falsehoods-programm... More falsehoods programmers believe about time: http://infiniteundo.com/post/25509354022/more-falsehoods-programmers-believe-about-time-wisdom http://infiniteundo.com/post/25509354022/more-falsehoods-pro... Falsehoods programmers believe about geography: http://wiesmann.codiferes.net/wordpress/?p=15187&lang=en http://wiesmann.codiferes.net/wordpress/?p=15187&lang=en [1] http://www.reddit.com/r/programming/comments/1fc147/falsehoods_programmers_believe_about_addresses/ca8sirp http://www.reddit.com/r/programming/comments/1fc147/falsehoo...

raverbashing 13y ago
Yes, there's so much about these. Of course, in practice, you usually target your system to a narrow set of users at first. But yeah, if you're facebook, or work with an airline booking system, for example, you will most likely hit every single item on these lists
- brownbat 13y ago
  > you usually target your system to a narrow set of users at first [but eventually the exceptions show up] Reminded me of the College Humor sketch about security questions: http://www.collegehumor.com/embed/6936880/security-questions-sketch-ucb http://www.collegehumor.com/embed/6936880/security-questions...
  - 13y ago

Laremere 13y ago

Assuming that the person doesn't necessarily need to know their answer (which is important for babies anyways) the answer is trivial. The first question would be "Given that we ordered all humans in order of the time of their birth, would the 1st bit of your position in the ordering be 1?", continue the other 32 questions with the remaining 32 bits.

fat0wl 13y ago
lol too much

fmax30 13y ago

So you want to create a data set with entropy = 1 . Think of this in terms of a hash function , You want to create a hash which only has an address space of 33 bits. Something in terms of H(Alice) = 0x12321 {H is a function which generates 0x12321 to store the data of alice) Doesn't this sound like perfect hashing with limited memory. I don't really think that this can be done with such memory constraints. Even now we cannot produce a perfect hash function that uses 1 bit / key. The theoretical best we can do is 1.44 bit / key. And the practical best we have done till now is 2.5 bits per key. [1] This may just be possible without the memory constraint that is , you answer N number of questions which uniquely identify you. (where N > 48 ) [1] http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_p...

Houshalter 13y ago

This is really interesting actually. Your entire "uniqueness" can be summed up in 33 yes or no questions, in theory.

jeffdavis 13y ago
I don't think that's quite the right interpretation. Let's say that the human population increased by a factor of 1000. Does that mean you have 10 more bits of uniqueness? You didn't change at all. In actuality, you already had those 10 more bits of uniqueness, and people just need to ask more questions to find out which one of the many unique people you are. This is about identification, not uniqueness.

unfamiliar 13y ago

Are you male? This will not split the population 50/50. One group will be slightly larger, and you then only have 32 questions to subdivide this larger group into further categories which is impossible. This is not possible unless the categories _precisely_ bisect the group each time.

mcphilip 13y ago

I think first you have to show a question exists that effectively separates identical twins before you spend much time working on broad questions like gender and geography.

edsrzf 13y ago
Maybe something like "Do you have more older siblings than younger siblings?" would work. One twin has to be born before the other. That question has some problems, but I feel like it could serve as the basis for a more specific question that would define how an only child or middle child would answer without introducing much bias. It would also have to define how half-siblings are counted and probably some other things.
- pavel_lishin 13y ago
  It's entirely possible that the twins would not know which one was born first.
  - daleharvey 13y ago
    Its entirely possible the person could not know the answer to any of the questions, I dont think that really counts
- RogerL 13y ago
  So you are going to burn one entire question that is entirely worthless for the vast majority of Chinese that have been born recently?
  - Intermernet 13y ago
    Interesting read: "One Child Policy and Arising of Man-Made Twins". http://paa2013.princeton.edu/papers/130113 http://paa2013.princeton.edu/papers/130113

IsNotMyIp 13y ago

Do you speak english as your main language? Could be a good question too? What do u think?

fat0wl 13y ago

The 33-question issue is a tough one for sure. I'm instead left wondering how many extra questions (35 bits? 36 bits?) it would have to be expanded to in order to produce unique results but without having to be particularly clever in producing the questions. I bet it wouldn't take as many extra as one might be inclined to think.

pit 13y ago
Good point, especially because at 33 bits, storing everyone's ID would only take about 29 gigabytes. 7,126,462,675 people * 33 bits per person / 8 bits per byte = 29,396,658,534 bytes World population source: http://www.census.gov/popclock/ http://www.census.gov/popclock/

jv22222 13y ago

Less than half the population will be able to "read" the questions due to not speaking English...

rattray 13y ago

This is a fun exercise, but as others have pointed out likely impossible in its current form. We don't have true constraints on space though; why limit to 33 bits? How could we still provide a meaningful UUID to each person? A UUID based on time and location of birth might be more feasible than any other approach, since neither will change and it's the least likely to be ambiguous. Capturing UTC at the time of cutting or otherwise removing the umbilical cord could be one way of choosing as precise, non-debatable a timestamp as any. Adding lat/long and, say, the first byte of the UTF-8 character of the mother's name (or an aspect of the mother's UUID?) could get you the rest of the way there. Of course, this falls over in places without access to precise timing and geolocation.

edelans 13y ago
I think the limitation to 33 bits is because this is the smallest power of 2 which is higher than the world's population: 2^32 = 4.29 billions, 2^33 = 8.58 billions, 2^34 = 17 billions,
r0muald 13y ago
Another pitfall of this thought-experiment is that there is no room for the constant number of humans who die and are born every day: the set of 33 questions hypothetical questions of today will not be valid tomorrow.

ye 13y ago

First 33 bits of SHA512(your DNA) First 33 bits of SHA512(your 3D GPS location)

deathanatos 13y ago
As someone else mentions, this doesn't work, as the birthday problem[1] applies here. You need to ensure collisions won't happen; SHA512 does not to that. (The probability of a collision in 512 bits is near impossible; in 33 bits, much less so.) [1]: http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem

abentspoon 13y ago

It's not enough to find 33 independent questions that evenly split the world's population. An optimal, though inelegant solution to that goal might look something like this: "Is the {1..33}th bit of sha1(name : location : date of birth) 1?". Clearly you'll have tons of collisions with that solution, as you would have with any solution using 33 independent questions. To uniquely identify people, we'd either need to use more bits, or look very closely at the population and derive very specific questions.

upquark 13y ago
> Clearly you'll have tons of collisions with that solution Why? If we assume the hash code assignment to one of the 2^32 people is uniformly random from a set of 2^160 codes, the odds of finding a collision are astronomically small (order of 2^-95 or so). Am I missing something?
- jules 13y ago
  You are not taking the entire hash, you are only taking the first 33 bits of the hash. Since there are only about 8.5 billion different values for the 33 bits and there are about 7 billion people, the odds are astronomically low that each of those 7 billion people will receive a different one of those 8.5 billion possibilities. This is the birthday paradox with instead of 365 days you have 2^33 possible answer values and instead of 23 people you have 7 billion people. I leave it as an exercise for the reader to fill in these values into one of the formulas to calculate the probability of successfully giving each person a unique 33 bit answer: http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem
  - upquark 13y ago
    > You are not taking the entire hash, you are only taking the first 33 bits Right, my bad, didn't pay attention to the problem we are trying to solve :)
jules 13y ago
It is interesting to see your comment way down the thread, even though it is by far the best.

DigitalSea 13y ago

This seems like it would be a lot of work. The intensity and specificity of the questions that would need to be asked would have to be quite unique. It might be possible, but without excluding people of the world because they get lumped into a group, it seems like maybe 33 questions might not be enough to uniquely identify everyone in the world.

S4M 13y ago

Do the questions have to be constant over time? If not it can trivially be solved by asking: Are you born before or after time t? 33 times, where t is the median date of birth of your population. You just need to recompute t 33 times (and know the date of birth of every single person in the world).

tehwalrus 13y ago

The set of questions that would do this is probably a list of genetic questions. "do you have the mumble allele?" etc.

dkokelley 13y ago

Wouldn't the best way to do this be to ask questions related to genetic markers? You require 33 yes/no questions that independently divide the population in half, but has near-uniform distribution otherwise (each populace half has no relationship to the other questions). Are there 33 genetic markers that each has no correlation on the presence of the others?

dinkumthinkum 13y ago

It's an interesting idea ... But no I don't think it is possible in any way that is not turning the list into a set of questions about their genetics or DNA.

brownbat 13y ago

This project assumes we can know things that are not really knowable for everyone. It starts with gender and birthplace, both tricky questions in some situations. So maybe we get to assume we have some oracle that helps us simplify the hard questions. At that stage, it's easy. Begin with, "Assume we build a list of people sorted by time of birth (with some arbitrary tiebreakers, like proximity of birthplace to Barbados, or darkness of hair color...)." Question 1: Are you on the top half or bottom half of this list? Question 2: Are you on the top quarter or bottom quarter of the half? Question 3: ...

deathanatos 13y ago
I had come up with something similar: Question 1: Are you north of an east-west line that perfectly divides the population in half? (proceed to continue to divide each section in half.) Of course, determining the position of those lines is damn near impossible. And as soon as someone hops on a plane, the whole thing comes crashing down.
- brownbat 13y ago
  I like it. Maybe "were you north of an east-west line" when this list was made. I guess it gets tricky when people are born. Wait a minute, just realized this whole question breaks down if we don't recycle numbers from the dead back to the newly born... and there's no guarantee that all of the dead will sufficiently resemble all of the newborns. I want my money back. :)

jayd16 13y ago

I bet you could make a lot of progress by dividing GPS coordinates evenly by population. Simple binary search by primary residence and then leave some space for division within a household.

Zarathust 13y ago

I don't think it is possible with exactly 33 questions. It will probably require more than that. Binary numbers have the property of adding twice as many numbers +1 for every new bit. For example if you already have 7 bits and you add an 8th one, then you'll be able to represent 127 numbers with that bit off and 128 numbers with that bit on. To properly mimic this property with yes/no questions, you will have to come up with questions that divide the whole Earth's population equally AT EVERY NEW QUESTION. Even the most obvious one, "are you (fe)male?" is slightly biased toward men (according to wikipedia). At every question that skew your 50/50, you'll have to add another question beyond 33 to catch up with this.

thethimble 13y ago
All questions must be independent. That's too hard. I would be surprised to find even a handful of questions that have no statistical correlation when applied to all people in the world.
enriquepablo 13y ago
> To properly mimic this property with yes/no questions, you will have to come up with questions that divide the whole Earth's population equally AT EVERY NEW QUESTION. Not only that: The first question must divide the population in 2; the second question must divide each of the 2 subsets produced by the first question in 2; and the third has to perfectly divide the 4 subsets produced by the second... And this independently of the order in which you make the questions.

knowtheory 13y ago

No one here seems to have mentioned Hunch (http://en.wikipedia.org/wiki/Hunch_(website) http://en.wikipedia.org/wiki/Hunch_(website) ). Picking discrete questions like this is equivalent to building a decision tree for humanity. This is actually something that could be approached as an engineering problem (and there are mechanisms for optimizing decision trees). The problem still remains in the face of both the technological capabilities of decision trees, and practical implementations like Hunch.com, that decision trees are reductive and discrete. Reality is neither discrete nor reductive. It may very well be the case that there is a set of questions that could uniquely identify humans, but the insight that could be drawn from those questions might be essentially pointless. For example: * Were you born in the northern hemisphere? * Were you born on an even numbered year in the Gregorian calendar? * Is the country of your birth governed through a representative system?

stevewilhelm 13y ago

Is the intent of this exercise to build a unique identifier that the individual could reproduce over the course of their life, or does it just uniquely identify them at the time they answered the questions? I ask because questions like number of siblings, favorite movie, etc. would change over time.

fela 13y ago

Even if the questions were perfect (each question splitting the population in two exact halves, and all questions totally independent from each other) and therefore the algorithm would give each person a perfectly random number, the birthday paradox [1] tells us that even for just square(2^33)=~ 93k people we would have 50% probability of having a collision. To work we would need more bits. (Either that or create questions that are _not_ independent, so crafted in a way to make sure each person gets a different number) [1] http://en.wikipedia.org/wiki/Birthday_problem http://en.wikipedia.org/wiki/Birthday_problem

deathanatos 13y ago
No: the linked article requires that further questions split the previous groups each in half. The first question must split the group in half, the second question must split those two groups in half, and so on. When we hit the last bit, the final question is splitting groups of 2 people into the last bit, and each person has been assigned a unique number. In this manner, 33 bits is enough, and the birthday problem is avoided. The page mentions all this.

yiransheng 13y ago

If anyone is interested in seeing such a application in a fictional setting, I suggest the anime Death Note, if nothing else for its entertainment value. For those who are familiar with the story, the questions L asked in order to narrow down Kira suspects to a limited demographics in a small region in Japan, among billions of candidates, were some good ones. A good article that analyzes the plot from a information theory perspective: [http://www.gwern.net/Death%20Note%20Anonymity](http://www.gwern.net/Death%20Note%20Anonymity) http://www.gwern.net/Death%20Note%20Anonymity](http://www.gw....

josscrowcroft 13y ago

People have so much time on their hands.

vacri 13y ago

How many questions would you need to differentiate between identical twins, particularly if they live and work together? Take identical twin sons of a subsistence farmer - they live together, work together on the same things, know the same people, have the same genetic makeup, and whichever was the first twin born may not have been recorded. You could ask their names, but that's not a yes/no question. Or even twins who are still babies, no work required? Some cultures wouldn't even have named them yet.

incompatible 13y ago
Multiple births would be bad enough, and then you have people with dementia who can't remember the answer to most of the questions, and people in a coma who can't answer questions at all. The chance of succeeding with this exercise is approximately zero.

obilgic 13y ago

Possible, You need 33 answers but more than 33 questions.

loganu 13y ago

Could you not have way more than 33 questions created, (maybe a couple hundred) but change what questions are asked based on previous answers? Use the previous answers to determine the strongest next question to ask? If an early answer states the candidate lives in the north hemisphere, there's no point in asking them if they live on a landlocked African country... or whatever much more complicated questions could arrive.

cbr 13y ago

A boring solution: Question n. Consider the number of your birth out of all people currently alive. When you divide by 2^n and take the remainder, is it odd?

ruswick 13y ago

This is a really cool concept, but one that is totally impossible. In the actual world, few things are truly independent. Even if you could find 33 binary questions that did not correlate with each other at all, you still run the risk of having multiple people yield the same 33 answers. Just because two things aren't statistically linked does not mean that they will never overlap.

Strilanc 13y ago

An easy way to construct the questions is to ask for increasingly precise time and location of birth. There will be corner cases, but then so does asking if someone is male.

deleted 13y ago

[deleted]

k__ 13y ago

Isn't this solvable to a degree by just asking a big amount of yes/no questions to a big amout of people and then removing all those questions that didn't identify people any further?