긴 여행 끝에 확률의 마법사를 만났다. 마법사는 다음 퍼즐을 풀면 소원을 하나 들어주겠다고 약속한다.
마법사는 먼저 두 정수 N과 K를 알려준다. 그다음 1 이상 N 이하의 정수를 하나 몰래 고르고, 그 값은 알려주지 않는다.
목표는 이 비밀 숫자를 정확히 맞히는 것이다. 답을 말하기 전에 그 숫자를 두고 참 또는 거짓으로 답이 돌아오는 질문을 K번 할 수 있다. 예를 들어 "그 숫자는 짝수입니까", "그 숫자는 7 이상 10 이하입니까", "그 숫자는 17 또는 22입니까", "그 숫자는 소수입니까" 같은 질문이다. 마법사는 언제나 정직하게 참이나 거짓으로 답한다. 질문 K개에 모두 답을 받은 뒤에는 숫자를 하나 말해야 한다. 맞히면 소원이 이루어지고, 틀리면 날개 달린 원숭이가 된다.
형식적으로 질문은 집합 {1,2,…,N}에서 참과 거짓 두 값으로 가는 함수이고, 마법사는 자신이 고른 비밀 숫자에서 이 함수가 어떤 값인지 알려준다. 앞선 질문의 답을 본 뒤에 다음 질문을 정해도 된다.
N과 K가 주어질 때, 마법사가 어떤 숫자를 고르더라도 질문 K개만으로 비밀 숫자를 항상 알아낼 수 있는지 판정하라.