논리 퍼즐(10000덕)
게시글 주소: https://orbi.kr/00073818317
1, 2, ... n과 같이 번호가 붙어 있는 문 n개(n >1)와 문지기가 있다. 이 문 중 n-1개는 안전하지만, 1개 뒤에는 함정이 설치되어 있다. 당신은 안전한 문을 찾기 위해 문지기에게 질문을 하려고 한다. 질문은 ”a_1번 문, a_2번 문, ... a_k번 문 중 함정이 있는 문이 있나요?”와 같은 형태로 할 수 있다. 물론 “a_1번 문은 함정이 있는 문인가요?”와 같은 질문도 가능하다. 질문은 몇 번이든 할 수 있다.
문지기는 항상 참말만을 하지는 않지만, 거짓말쟁이도 아니다. 따라서, 문지기는 3번 연속으로 참말을 하는 경우도 없고, 3번 연속으로 거짓말을 하는 경우도 없다. 그러나 이 제약 내에서, 문지기는 자신이 원하는 대로 참말이나 거짓말을 할 수 있다.
문지기의 답변과 상관없이 안전한 문을 최소 1개 찾을 수 있게 하는 n의 값이 존재할까? 존재한다면, 그 중 최솟값은 몇일까?
(엄밀하게 말해서, 문지기에게 하는 각 질문은 {1, 2, ... n}의 공집합이 아닌 부분집합 S로 이루어지며, 이에 대한 답은 함정이 있는 문의 번호가 S의 원소인 경우 ‘예’, 아닐 경우 ‘아니오’입니다.)
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
아... 0
kt의 msi우승팀한테1세트땄다도르가..
-
지리네
-
어케 극복해요? 제가 원래 멘탈도 약하고 심리적 요인에 영향을 되게 많이 받는...
-
남수인지 남규인지 닮으셨던데 모의고사 총평 정리해주시는분이요.
-
언미물1화1이고 7모 21323 나왔습니다 만약 바꾼다면 화학을 사문으로 바꾸려는데...
-
안돼
-
치타는 달린다
-
지금 저 티원을 응원할 수 밖에 없는 티붕이임..ㅜㅜㅠㅜㅜ
-
하..
-
친구가 있다는거 자체가 기만 아닌가요?
-
.
-
여사친 특 5
내 주변엔 없음
-
밸런스 게임 2
수능 전 날 의문의 메시지가 왔다
-
올해 생윤 첨하고 메가 1타라 걍 뱔 생각없이 개념 듣고 6모 대비로 혼자 현돌...
-
둘 다 넣음.
-
평가원 표본이었으면 1컷 몇나올까요?
-
반수 공부 시작한지 한달도 안 넘었는데 벌써부터 지친것 같아요...당연하겠지만...
-
몇년도까지?
-
-
만점받고싶다 0
만점받고싶은데 실력이 안느네
-
수학만 유독 점수가 안나와서 한번 들어보고싶은데 지금 들으면 뭐부터 들어야할까요?...
-
젠지좃댓다 2
아이고
-
1.정상이다 2.비정상이다
-
한싸이클만 찾아주면 거기서 나올 수 있는 값들이 곧 첫째항이다. 쉬운데 깔끔해서 좋음
-
티원 바텀 저거 어케 막을거임ㅋㅋ 진짜 하루종일 맞다 끝나는 픽인데
-
-
-
사문 서바 vs 강k 둘중에 하나만 가능하면 뭐하심 7
둘 다 라이브
-
듀로파이크??? 1
어어어엉????
-
강은양 리비에스 2
꼭 사야할까요?ㅠㅠ 그냥 이비에스 사용설명서로만 공부해도 될까요? 교재도 너무...
-
ㄱㅊ을까요 고2 9모 기준 76점정도 나와서 아직수1 부족한거같은데 슬슬 수2도...
-
수시원점수 2
현 고3 고2 아이들 수시 지원시 과탐2과목이 아닌 다른 과목도 원점수가 중요할까요?
-
준킬러 연습을 더 많이하고 싶긴 한데 이러면 드릴보단 커넥션이 낫겟지
-
무묵지 23
부거 휫자 김밥?
-
-
후...
-
벌써 이긴 거 같아
-
기대안할게22
-
ON
-
시험 도중에 학교 침수돼서 진짜 물수능일것임 빨리 스쿠버다이버 자격증을 따세요 여러분!
-
생명 스킬 1
T&S 끝냈는데 계속 회독 돌려야하나요? 아니면 다른 스킬 강의 들어볼까요?
-
이감5-1인데 시간부족하지 않았고 3분 남기고 차분히 다품 그러곤 저 점수나온게...
-
배고파 8
햄부기먹어야지
-
그 설레임을 참는다면
-
그냥 설문조사 해보는 겁니다 ㅋㅋㅋㅋ 국어 뭐가 제일 어려우세요?
-
케틀 럭스 3
Or 드레이븐 칼리스타 그리고 개같이 박살
-
-
방법 알려주셈ㅇㅇ
-
미적 기준 21번 어려움 ..아님말고
-
AO이으면 직각삼가형 3개 겹치는 형태 하나 더나와서 그걸로 BC길이 절반 구하고...
존재x
왜 그런가요사실 찍었어요 ㅈㅅ
3번?
왜인가요논리퍼즐도 확통 경우의 수로 문제나올수 있나..
일단 확실한건 이건 죽어도 못나와요
4번?
n=4인 경우의 전략을 제시하실 수 있나요
질문세개
1. 2,3번중 함정이있나요
2. 1,3번중..
3. 2,3번중..
이러면 최소하나의 안전한문을 찾을수있는거아닌가요 잘모르겠네
아마 되긴 할텐데
최솟값이 n=4는 아니에요
이런문제는 직접만드는건가요?
이번 건 PS하다 본 문제 변형한 거에요
!!!
정답: 3
편의를 위해 n이 3 이상일 때 다음과 같이 이름붙임
{a1} = l / {a2~an-1} = c / {an} = r
l+c+r을 연속으로 물어보면 예가 항상 참이므로 세 연속된 질문 중 참이 반드시 존재한다는 규칙에 따라 세 번의 질문 안에 예라고 답할 것임
이를 첫번째 질문이라고 하면, 두번째 질문과 세번째 질문 중 적어도 하나에는 거짓을 답해야 함
두번째 질문에 l+c, 세번째 질문에 c+r을 물어봄
둘다 아니오일 경우 l, c, r중 어디에도 함정이 없으므로 가능한 대답은 (예, 예), (예, 아니오), (아니오, 예) 뿐임
1. (예, 예)
c에 함정이 존재한다면 두 대답 모두 참이므로 c는 함정이 존재할 수 없음
따라서 c를 고르면 안전
2. (예, 아니오)
l에 함정이 존재한다면 두 대답 모두 참이므로 l은 함정이 존재할 수 없음
따라서 l을 고르면 안전
3. (아니오, 예)
r에 함정이 존재한다면 두 대답 모두 참이므로 r은 함정이 존재할 수 없음
따라서 r을 고르면 안전
따라서 3 이상의 모든 n에 대해 항상 안전한 문을 고를 수 있음
n=2일때 질문의 순서와 관계없이 세 질문 안에 모든 부분집합을 물어볼 수 있음
{a1}, {a2}, {a1,a2} 각각의 질문에 대한 답이 모두 예라면 {a1}이 거짓이거나 {a2}이 거짓 = a2가 함정이거나 a1가 함정이므로 안전한 문을 고를 수 없는 경우가 됨
따라서 최소의 n은 3
아 글을 애매하게 썼을지도
“참말을 한다 = 현실을 반영한 말을 한다“ 에요
그러니까 l에 함정이 있는데 (c, r)을 물어보면 아니오라고 답하는 게 참말인거죠
없는데 있다 하면 그게 거짓말이니까
저도 그렇게 받아들였는데 어디서 틀린건가요
아 다시 읽어보니 그냥 햇갈리신듯요
둘다 아니오일 경우 l, c, r중 어디에도 함정이 없으므로 <—- 거짓말한 걸수도 있죠
그렇네요 어쩐지 너무 지저분하더라