2016 영국수학올림피아드 2라운드 2번문제

영희는 자기가 생각하기에 잘 하는 순서대로 20개의 하키팀의 순서를 정하였는데 어떤 순서로 정했는지는 비밀로 하였다. 철수가 영희에게 3개 팀을 말해주면 영희는 이 셋중에 가장 약한 팀을 알려주거나 혹은 가장 강한 팀을 알려주지만, 어느 것을 말하는지는 알려주지 않는다. 철수는 원하는만큼 많은 질문을 할 수 있다. 이때 철수가 질문들을 잘 구성하면 팀 $N$개의 나열 $T_1,T_2,\ldots,T_N$을 잘 추측해서 모든 $1\le i\lt N$에 대해 영희는 $T_i$가 $T_{i+1}$보다 낫다는 것을 입증할 수 있다고 할 때 가능한 최대의 $N$ 값을 구하여라.

GD Star Rating
loading...
이 글은 조합 카테고리에 분류되었고 mo님에 의해 작성되었습니다. 고유주소 북마크.