MathDB

Philena and Nathan are playing a game. First, Nathan secretly chooses an ordered pair

(x, y)

of positive integers such that

x \leq 20

and

y \leq 23

. (Philena knows that Nathan’s pair must satisfy

x \leq 20

and

y \leq 23

.) The game then proceeds in rounds; in every round, Philena chooses an ordered pair

(a, b)

of positive integers and tells it to Nathan; Nathan says YES if

x \leq a

and

y \leq b

, and NO otherwise. Find, with proof, the smallest positive integer

N

for which Philena has a strategy that guarantees she can be certain of Nathan’s pair after at most

N

rounds.

Problem Statement