วีดีโอ

Really underrated channel bruh! You deserve way more subs

"Hot Garbage, to borrow from scientific terminology" hahaha yeah thats the best scientific terminology ive heard. well done !

Still, in order to win any realistic sized game (either in 20 questions or the Ulam variant) you need probabilistic knowledge (about the category), even then the result is non-deterministic, as one could rarely choose a very rare choice for an animal or something. Might be a good idea for a video to see how this optimal strategy along optimal probabilistic knowledge (assuming some natural distribution of true answers) would work on either variant. I'm almost curious enough to get going with it by hand but it's almost 2 AM.

at 4:30 i had a thought of asking about eqch bit of the number and some kind of an error correction code

Here's my take : we're searching for a N-bit binary number (for simplicity we kind of assume N is a power of 2 but this changes little). First ask for each bit individually (this takes N questions). Then ask if the sum mod 2 of the N/2 first bits is the one you computed. If no, there is a lie, and it's within the first half, then continue this way. If yes, there either isn't a lie or it's located in the second half. So ask if the sum mod 2 of the N/4 first bits of the second half is the one you computed. Etc... When you've narrowed it down to a single bit there are two possibilities : either you at some point learned that there was indeed a lie, so you can tell the correct number by flipping that bit, or this was never revealed and you have to ask which makes one more question. Final worst-case complexity is N+log_2(N). I imagine it's optimal. Funnily, if you have to find the object in a set of n objects (N=log(n)), the complexity is log(n)+log(log(n)). Quite cute to see an appearance of log(log(n)) in the wild :)

What # of items gives you 20 as the optimal strategy, as that's the name of the game & the max number of questions/guesses you can have?

Would a 20 Q strategy be similar to a Guess Who strategy?

I think I have the ultimate, most meta strategy “When will you lie” Obviously not a great strategy, but it was so horrendously meta that I thought I ought to mention it

I'm sorry man the detractors in the comments are correct- this is objectively bad

There's a easier solution. Use self referencing to force the correct answer. Ex: Does your answer correctly answer the following question AND <insert question here>. If the responder decides not to lie. Then it devolves into a normal question. If they decide to lie and the real solution is true. They shall reply false. But replying false makes the first statement false. Which makes the entire expression false. That means they actually have to reply true... It's a paradox. The responder have no option but to reply truthfully. Same solution applies for the false case

Is exactly one of these statements true: "you are using your lie on this question", "the number is bigger than 8"? If they are using their lie on this question and the number is bigger than 8, the true answer is no, but they'll answer yes. If they are using their lie on this question and the number is not bigger than 8, the true answer is yes, but they'll answer no. If they are not using their lie on this question and the number is bigger than 8, the true answer is yes, and they'll answer yes. If they are not using their lie on this question and the number is not bigger than 8, the true answer is no, and they'll answer no. So, no matter if they're lying or not, if the number is bigger than 8, they'll answer 'yes', and if the number is not bigger than 8, they'll answer 'no'. Repeat with every question and you've got yourself the optimal strategy. :)

I always love reading comments on videos like these that get so hyper focused on the original premise (in this case guessing an animal) rather than understanding the point of the premise is to serve as a jumping point for the mathematics being demonstrated in the video. My favourite ones on this video are a phD dissertation on choice bias, an article about the Linnaeus system, and another asking about a blind person that can't see the list of animals.

I thought you would bring it up because this may help lower the number of questions (maybe, I'm not that good at math): what if we go all meta and ask about the lie itself?

There's a bunch of logic puzzles that I could never solve that involves self-references and ANDs and ORs. I wonder if asking those type of questions could make it faster

Nice, I figured out the idea of just "adding the lie to he tree" myself. Granted, the exact tree design still eluded me.

Me who can't even comprehend simple high-school math: 👁👄👁 Also it's me from the disc

Maybe I'm too sleep deprived or ill to understand but how exactly do I to apply numbers, letters and binary to trying to guess the animal in Ulam's game? Am I wrong to assume that quizzing about seemingly arbitrary numbers to represent the subject matter won't help because that's not in the premise of the game itself? The logic sounds right but the premise feels off. I'm now frazxled.

whats the maximum number of categories you could have while still being able to win with 20 questions? Really love the video btw

nice trick. now, to add an extra twist. what if he can lie twice? I believe the rules more or less still apply but will require a few modifications to take into account a second lie.

Of course, there's some real world factors to consider here. 1. If someone picks a beluga whale and you ask if it's bigger than a microwave oven, they will answer confidently and immediately yes. 2. If someone picks a beluga whale and you ask if it's bigger than a Greenland shark, they will look at their phone or give you the very helpful "I don't know" or "sometimes" or "clarify the question." If they have to do any of these you are definitely extracting more than 1 bit of information from them. And if they don't, you also get more than 1 bit of information. 3. It takes a lot longer to compare entities which are similar in the dimension being compared but don't follow a strict cached ordering when it comes to that quantity. Everyone knows the relative size of an elk and a caribou but what about an alligator and a caribou? Whether they have to think about it / say I don't know / use their phone / etc also tells you whether your reference point is similar in TYPE to the object and not just dimension. Even a small pause to think could be worth extra information. Note also that it's possible for them to lie by taking longer but not shorter to answer a question. So if you're usually answering instantly and they have to think all of the sudden you may be on to something. You know not just the yes or no answer but also whether or not it was ambiguous or uncertain and how long they took to answer. Finally, there is choice bias. Try as you might, you are not gonna pick a random animal. You are either gonna pick an animal that's well known and nonspecific in type, or one which is "weirdly specific" but probably not actually arbitrary from the several hundred to several thousand animals you might be aware of. Biasing questions to the distribution of how people pick things is a very powerful optimization. For much the same reason it's a powerful optimization for guessing passwords.

Also keep in mind with the "asking twice" that just locates the lie. It doesn't tell you what the truth is. If you want the truth you'd need to ask that question thrice.

Youre assuming there is a one-to-one correspondence between a set of integers and any and all arbitrary lists. Perhaps if the list were infinite this may not be true; its not clear. Did you perhaps want to clarify the rules of the game?

Is the list of animals a prescribed list that both players can know ahead of time? Does only the one player know the list from which he chose the animal, and the other player is blind? Youve been very vague about the rules of the game.

1:52 But once youve identified the lie you dont have to keep asking questions twice.

Animals are fairy well categorized by the Linnaeus system. Much thought would have to be put into what the best question would be based not just on number of animals in each category. In classification there are 7 phyla but cordata includes all animals with backbones. Despite being no where near 1/7th of animal species, I would guess that half or more selected answers will be in thus category. Therefore I would ask "Does it have a backbone?" First.

why is this so underrated

It is not correct that you guarantee the correct answer in 4 questions. You need 5. In your example, there is a branch that ends with the numbers 1 and 2, and the question is "is it 2". You only get that correct in 4 guesses if the answer actualy is 2. If it is not, then you have to ask again "is it 1", which is your fifth question. Otherwise you never gave the correct answer.

What if only one lie can be told, but a lie once told can or even must be repeated?

The quality and everything is so good. You'll grow to be one of the best out there. Keep it up mate!

I'll add something here that wasn't included in the video. The answers to the last three questions give the following results: NNN => 6 NNY => 10 NYN => 15 YNN => 13 YYN => 14 YNY => 14 NYY => 14 YYY => 14

Amazing video, thankyou

Adjacent questions. I like how <5? and even would best fit the others.

We can ask twice on Question q if they've lied before q YY-> lied previously YN-> didn't lie until q NN-> haven't lied yet NY-> didn't lie until q+1

This is kinda incorrect though. The optimal strategy is not necessarily the strategy that has the best worst case scenario. It is instead the strategy that, well, wins more often, ie. Guesses the right answer in less than 20 questions more often. Say we have a strategy that has a 51% chance of getting it right in 20 questions, but then they have a 0% chance to get it right in the next 80 questions, and finally the remaining 49% chance to get it right in only 101 questions (ignore how this doesn't make sense). Compare that to a strategy that gets it right 50% of the time in 20 questions and 50% of the time in 21 questions. Even though this strategy's worse case scenario is 80 questions shorter, it's a worse strategy because you only win 50% of the time, instead of the 51% of the time the first strategy gave.

Okay now do 20 answers.

What if the responder never uses the one lie? Should the rules state one lie must be used?

Your algorithm involves playing a complete game of twenty questions and only then trying to detect the lie. Can you prove that is optimal, rather than some other strategy that incorporates error correction from the beginning? Come to that, are you even claiming it's optimal?

The doubke ask fails if they lie on the second

Great first video! Waiting for the next one!

14:49 Isn't 15 (all yes) impossible for that set of questions (as in the true answer being all yes, if the no on the 3rd question was the lie) since the 4th question (which must be truthful) says it's not 15 (caused by 15 being only 3 layers down in the binary tree rather than 4 so it can't be in the "yes" set of the 4th layer) I don't think it makes any difference(?) assuming it's there for the next step looking at the tree of t, a, b, c, and d for the number of questions, but that's only if the true answer isn't 15 11:01 would all be possible though Cool topic tho I remember this in error correction

- Is it a duck? - Yes. - So I won. - No, I lied.

Is it duck, horse, platypus, crocodile, ... 1582 items later ... , or a cat?

I'm amazed that even with a lie, you could still win 20 questions for 1000 items. What's the most number of items for which you could still win in 20 questions?

One thing I think you should have clarified is the simplification to numbers. Questions which are directly asking "is it X" remain valid but questions like "is it less than 5" don't remain valid in the switch back from numbers to animals. That's ok because the general strategy you have works for any set of answers but it wasn't clear at that point in the video

Can you ask "have you lied yet?" in Ulam's game?

fantastic video!

6:52 Slight correction, but that is not a binary search tree (BST). It is just a binary tree. A binary tree is just a tree where nodes have at most 2 children. A BST additionally requires that the left subtree contains only nodes lesser than the root, the right subtree contains only nodes greater than the root, and that both subtrees are BSTs. The advantage of a BST is that at every node it can be determined which child to recursively search to find a target node. This property is not present (nor does it appear useful) in the example in the video.

Ask a question, ask “was the previous answer a lie?” ,repeat until they say “yes” , then ask on more time to make sure that the “yes” wasn’t a lie, then continue as normal

Oh yes, the social annoyance you get when you play 20 questions in the car and ask your friend to provide a numbered list of all people on earth. That’s what people get for being friends with mathematicians. It’s a blessing and a curse…

What a great video!