[일반] 만줄 바르가바의 제자,이석형 연구원이 낸 문제

[익명(125.133)]

A가 1이상 n이하의 자연수 하나를 정하면,

B가 '이 숫자 이상입니까?' 라고 질문하고,

A는 반드시 예 또는 아니오라고 대답해야한다.

m번의 질문에 대해 A가 답변을 마치면 B는 답을 말해야 한다.

보통 이경우에는 n이 2^m 이하이면 B가 항상 A가 정한 자연수를 맞출수 있다.

여기서 변형을 해서

A는 m번의 질문에 대해 반드시 1번만 거짓된 답변을 한다고 할때,

B가 항상 A가 정한 자연수를 맞출 수 있는 n의 최댓값은 얼마인가?

[ScARfaCE(kayuaao)]

[익명(123.213)]

외쳐!! 수학과 갑은 뭐다? 프린스턴이다~~~

[익명(222.118)]

이 숫자 이상이면 예라고 답하겠습니까? 라 물으면 똑같은데 그런 변형은 허용치 않겠지

[익명(125.133)]

무조건 이 숫자이상입니까 라는 질문만 가능

[익명(122.34)]

변형이 허용되면 뭐가 달라짐?

[익명(222.118)]

이중부정을 써서 상대가 참을 말하든 거짓을 말하든 그 진위여부를 한번에 판단할 수 있음

[익명(125.133)]

많은 사람들이 이문제에 대해 충분히 봤다고 여겨질때, 관련 논문을 올리도록하겠습니다.

[익명(141.223)]

2^(m-1) 이상인건 알겠음

[익명(125.176)]

문제 거꾸로 이해햇네 그냥 최댓값이라고 생각함ㅋㅋ