Algorithm Puzzle

[evildogbot100]

Given a positive integer n which Albert and Barry both know. Albert suddenly thinks of a number between 1 and 2^n inclusive. Barry wants to know what number Albert think of so he ask Albert some questions. Barry can only ask 3n questions with this format "Is your number between a and b?" with a and b real number. Then Albert will answer yes or no. However, Albert can lie to Barry at most n times. Can Barry know what number is Albert's? (assuming he knows that the number is between 1 and 2^n inclusive and he also knows Albert can lie up to n times). If yes please explain how Barry do it, if no please give explanation/prove.

[Nich]

I totally forgot how to do infinity proofs but here goes

Set of possible numbers is [1, 2^infinity] but 2^infinity = infinity so the set is [1, infinity]
Minimum number of guesses required is infinity/2^infinity - 1 (continuously divide the set in half minus the fact that the final set is a half number assuming Albert cant lie)
However infinity/2^infinity - 1 = infinity # of guesses

Finally Albert can lie infinity

If Albert could not lie it would be possible to guess the number but because Albert can lie for every guess required in the set it is impossible to know the answer.

Am I close or did I mess up infinity sets?

[Nich]

Or alternatively if you can prove it is impossible for 1 number in the set then it does not mater what value is used for n as you can not guarantee it is possible.

Thus I give you 1. 2^1 = 2 and your set is [1, 2]
you only get 3*1 guesses [1 guess]
Albert can lie 1 time

Thus it is impossible to guess as no mater if you guess is the number between 0 and 2 or 1 and 3 Albert is free to lie for your only guess.

[daniel34]

Thus I give you 1. 2^1 = 2 and your set is [1, 2]
you only get 3*1 guesses [1 guess]
Albert can lie 1 time

Thus it is impossible to guess as no mater if you guess is the number between 0 and 2 or 1 and 3 Albert is free to lie for your only guess.

3*1 guesses are 3 guesses, not 1.

[Nich]

epic fail ROFL. I was stuck in infinity mode lol

[Nich]

Ok lets go with 10

2^10 is 1024

you get 30 guesses

Albert can lie 10

Set 1 (assumes he will only lie on the first division)
First 21 have to be used to use up the lies

Pick 512-1025 after 21 guesses you will know the correct path 9th more cutting the sets in half you can guess the number in exactly 30 guesses

Set 2 (assume he will only lie on the second number)

Pick top half. Wait for the truth Pick top half 21 times once you have 11 for 1 half you can then mine down in 8 more guessing allowing you to guess the exact number in 30 guesses.

Finally because set 1 and set 2 are mutually exclusive ( due to our assumptions) and each require 30 unique guesses the sum of set 1 and set 2 (because Albert is not actually constrained by our assumptions) would require a minimum of 60 guesses. The rest of the possible sets are irrelevant.

[Koub]

Owww It is in fact easier than I had thought.

First, I'll assume you know that when there is no lying, guessing the "find a number between 1 and 2^n inclusive" needs n guesses at most with dichotomy.
Dichotomy being aiming the middle, and asking is it higher or lower (or is it between this guess and 2^n or 1 and this guess)
If I have 3n guesses, then I can replay dichotomy fully 3 times.
Up to one lie, I can still solve it (replay the dichotomy twice, and keep the result that came out twice out of three).

With two lies max, Albert can lie either 0, 1 or twice (and I can't know how many time he lied)
If he lies 0 times, I'll get 3 times the same result => easy
If he lies 1 time, it will be the same as the "up to one lie"
If he lies 2 times, he may lie either once during two dichotomy runs, or twice in the same run, and I won't be able to guess which it is.

So with just two lies he can defeat my 3n guesses.

This works only for n>1 obviously, with n=1, I have to guess a number between 1 and 2, I have 3 guesses, and he can lie only 1 time.

[Nich]

You missed the fact that you can use up his lies like my example. You are wasting a lot of guesses running the full tree. I spent all night thinking about this and every time I come up with a solution that requires exactly 30 guesses but requires some knowledge of when Albert will lie.

[evildogbot100]

Honestly I don't have the answer yet too. I'm thinking an approach not using binary tree but by dividing remaining possible solution to half. Every question divides the number set to 2: The interval Barry asked (we call this set S1), and the rest of them (we call this S2). Every time Albert answer, his answer is equivalent to answering which part the number located S1 or S2. So if Albert answer S1, all numbers in S2 has one less life for them since Albert need to use one lie if his number is in S2 and vice versa. The hard part is structuring the question so that after 3n questions, no matter how Albert answer them there would always only 1 remaining number that still has life considering each number has n life initially. If we can do that, we know which number is Albert's since all other number is impossible because Albert will exceed his lie quota if his number is other than the one that still has life.

[Sephrat]

This is quite a headache We gave it a thought at the office.
n=1 is very easy to solve but starting from n=2 it's hard to be sure of anything. We couldn't find any strategy for Barry to guess it, Albert always found a way to trick him.

We strongly believe it is impossible for Albert to win but we can't prove anything because we can't make abstraction of any strategy Albert or Barry could use, even by "reductio ad absurdum" (prove that Barry can't guess Albert's number for n=2 and you proved the "theorem" is wrong).

[Nich]

Follow the Yes

Given 3 guess for each level of half correctly determined
2 guesses for each lie forced

Ask top and bottom and confirm single yes 4 options
YY (1 lie) +2 guesses repeat
NN (1 lie) +2 guesses repeat
YN (2 lies) unknown needs confirmation
-Y confrim (1 lie) unknown needs confirmation
-Y changed to N (1 lie) +2 guesses
-Start Building a table as long as you have pair you know you have at least 1 lie
Currently we would have YN N_
-At this point I am unsure if you should confirm N on the bottom or top I suspect Top to keep questions even for both sides because
YN NN is equilivent to NN YN at which point you would reconfirm the yes

NY Confirm Yes and advance to the next level

The next level gets a bit tricky
4 options
YY Albert would never answer this way as if he lied on level one wasting 3 lies this would waste 2 more
NN This is the real tricky bit If Albert lied on the first level he used up 3 lies which would give us 6 additional questions. Yes we have questions to waste here now but if we waste 1 too many solving the puzzle is impossible. But if he told the truth at level 1 we have 2 extra questions. I am still trying to think of a set of 2 or 3 questions that can force a lie and guarantee more questions for us.
YN case 1 with confirm Albert lied on level 1 meaning we now have a total of 5 lies
YN case 2 with confirm Albert did not lie on level 1 meaning we now have a total of 2 lies (unconfirmed)
NY only 1 case because Albert had to tell the truth on the first level if he is telling the truth on this level.

BAH and I just realized that if Albert saves all his lies to the end and doesn't use any we will know the number but cant prove it because Albert still has all 10 lies to use and we will be out of questions

[Nich]

I still think the only way to prove this is using infinity's it has just been so long I forgot how to do infinity math