| [ QuizWit ] in KIDS 글 쓴 이(By): guest (sol) <maggie.kaist.ac.> 날 짜 (Date): 2002년 8월 27일 화요일 오후 06시 17분 17초 제 목(Title): finding the minimum number of checking 그냥 혼자 생각해 본 문제인데 야구(?) 게임과 비슷합니다. 문제는 다음과 같습니다. 4지 선다형 문제가 N개 주어집니다. 이 문제들은 너무 풀기 어렵습니다. 고로 찍기를 해서 문제를 풀려고 합니다. 답안지가 주어지면 1번부터 N번까지 답을 써서 제출하면 몇 문제를 맞추고 몇 문제를 틀렸는지 알 수 있습니다. 이것을 한번의 시도라 합시다. 시도의 횟수는 최소 몇 번일까요?(즉 tight한 upperbound는 몇일까요?) 예를 들면 N=1인 경우엔 최대3번의 시도로 전체 답을 알 수 있습니다. N=2인 경우엔 최대 4번의 시도로 전체 답을 알아낼 수 있습니다. 그러면 N=k인 경우엔 최대 몇 번의 시도로 답을 알아낼 수 있을까요? 제가 말주면이 없어서 표현을 잘 못했더라도 이해해주시고 또 이런 문제가 기존에 있으면 알려주시구요^^. |