I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'm a high schooler).

Well, here's the original post:

Consider a game between two players, Paul and Carol. Carol thinks of a number k between 1 and n, while Paul must guess the number. The goal is to correctly the guess the number in as little questions as possible, and Paul can only ask questions of the form 'Does the binary of k have substring x? Carol, on the other hand, wants to prolong the length of the game, and is allowed to lie about exactly one of Paul's questions.

This type of question is clearly a variation on standard Prefix Questions in Remyi Ulam Liar Games (see here: https://www.sciencedirect.com/science/article/pii/0097316588900039). My goal is to try and find a strategy for Paul so he can minimize the number of questions needed to guess k.

It is important to note that Carol does not necessarily have to think of a number, but rather, answer Paul's questions such that there exists at least 1 satisfying value of k at any point.

At this point, all I am trying to do is algorithmize the game. I am having a hard time wrapping my head around the strategy of Carole. I've read as much literature I could find on the game, and no paper explicitly stated the strategy of Carole. I've read many things about what Paul should do, but never Carol.

Is it fruitful to continue this way, and think about the strategy of each player at each individual turn, or instead look at the game holistically? I've thought about reducing the game to essentially several simultaneous games of the traditional Prefix question, and proceeding from there, but I can't seem to do anything tangible. I suppose I could limit the length of the substring that Paul asks about, consider the sizes of the truth and lie sets, and slowly buildup, but the dilemma about Carol's choice still exists.

Any thoughts?

Thank you!

I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'm a high schooler).

Well, here's the original post:

Consider a game between two players, Paul and Carol. Carol thinks of a number k between 1 and n, while Paul must guess the number. The goal is to correctly the guess the number in as little questions as possible, and Paul can only ask questions of the form 'Does the binary of k have substring x? Carol, on the other hand, wants to prolong the length of the game, and is allowed to lie about exactly one of Paul's questions.

This type of question is clearly a variation on standard Prefix Questions in Rényi Ulam Liar Games (see here: https://www.sciencedirect.com/science/article/pii/0097316588900039). My goal is to try and find a strategy for Paul so he can minimize the number of questions needed to guess k.

It is important to note that Carol does not necessarily have to think of a number, but rather, answer Paul's questions such that there exists at least 1 satisfying value of k at any point.

At this point, all I am trying to do is algorithmize the game. I am having a hard time wrapping my head around the strategy of Carole. I've read as much literature I could find on the game, and no paper explicitly stated the strategy of Carole. I've read many things about what Paul should do, but never Carol.

Is it fruitful to continue this way, and think about the strategy of each player at each individual turn, or instead look at the game holistically? I've thought about reducing the game to essentially several simultaneous games of the traditional Prefix question, and proceeding from there, but I can't seem to do anything tangible. I suppose I could limit the length of the substring that Paul asks about, consider the sizes of the truth and lie sets, and slowly buildup, but the dilemma about Carol's choice still exists.

Any thoughts?

Thank you!