논리 퍼즐(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를 선물하세요.
-
AO이으면 직각삼가형 3개 겹치는 형태 하나 더나와서 그걸로 BC길이 절반 구하고...
-
또버크랩스 5
한판더!한판더!한판더!
-
수능전까지 달린다는건 말이 안되겠죠;;;
-
미치겠다 진짜
-
열등감 극복 어떻게함? 10
더프 31111 6모 32111 교육청도 비슷한데 6등급 출신이여서 그런지 열등감이...
-
한문 평가좀요 5
제2외 해야하는데 한문 ㄹㅇ 쌩노베에요..이정도면 다른거 하는게 나을까요..? 설대...
-
주세영
-
ㅇㅇ?
-
26도로 켜도 시원한데 밖에서는 20도 정도로 켜야 시원함 왜지
-
이 제도 있는 이유가 뭐에요?
-
저희 독재는 아침에 1빠로 온 사람이 에어컨 키고 문 열고 다 해요 저는 6시 좀...
-
영어 1-2등급 진동에서 고정1받고싶은데 현강 누가 좋을까요? 3모5모89 6모 7모 9795였어요
-
한번 해볼까여?
-
휴식이 개귀엽네 2
-
혹은 울음을터뜨릴때 혹은 잠잘때 사람은 그때가장아름다운것같다 아무것도 꾸밈이없으니까...
-
같이들을래? 9
일요일 오전 기분 좋게 베이스 한잔해
-
어렸을 때 해봤을 포켓몬스터 블랙/화이트 메인 캐릭터 디자이너랑 작곡가가 당시...
-
날도더운데 입술까지후끈후끈거리네
-
화학 시작 2
지금부터 화학 시작하면 늦겠죠.? 내신 때 화학을 하긴 했는데
-
포기하지마...
-
내 본명은?
-
통새우와퍼 하나밖에 안먹어본 뉴비예요
-
기대안할게..
-
-
그냥 궁금해서 묻는건데 어느 오르비언은 뱃지만 12개가(15개? 헷갈림)...
-
모고보면 문학이랑 문법만 틀리는데 ㅁ ㄴ법은 공부 안해서 그럴수 있다 쳐도 문학은...
-
진짜 죽을 것 같이 아픈 건 아닌데 몸살감기 들면 아픈 거 있잖아요 조금만 움직여도...
-
안녕하세요. 23수능 화미생지 53322 맞았던 22살 사수생입니다. 현역으로...
-
한 학기에 500… 그러면 500*8 = 4천 …? 씨발 ㅠㅠㅠㅠㅠ
-
하
-
미적분 객관식 찍을 때 국룰(?) 같은 게 있나요? 12
저는 찍을 일이 있으면 보통 한 번도 안 나온 번호로 찍는데, 이게 국룰이...
-
진짜 미치겠네 신상혁
-
얼버기 1
-
-
와 레나타 궁 2
대민석
-
한 07년까지만 해도 서울 한남동에 있었습니다 캠퍼스 큰건 아닌데 동네 분위기...
-
사실상 지금 막 공부 시작한 반수생인데요 수학 1컷 탐구는 현역1인데 갈수록...
-
수2 하나 4
설맞이 구경하다가 똑같은거발견해서 폐기
-
비문학 인문 제재 분야별 기출 모음 (15) - 역사관 0
안녕하세요, 디시 수갤·빡갤 등지에서 활동하는 무명의 국어 강사입니다. 오늘은...
-
뇌출혈로 의식 잃어가는 중에도 41초 버텨…韓 관광객 참사 막은 中 버스기사 7
중국에서 한국인 단체 관광객을 태운 중국인 버스 기사가 운전 중 뇌출혈로 의식을...
-
왜살지
-
의사도 마찬가지고 여태까지 휴학한것도 대단하긴했지만 끝낫노 그만하자노~
-
대단하긴 함 얼마나 수학을 잘해야 되는 거야..
-
재종 생각해보니까 국어 사탐 영어는 굳이 현강 들어야되나 싶어서 확통도 굳이고...
-
수업시간에 “성관계 좋은 것, 많이 해봐야” 50대 전 교사가 한 말 5
기사와 직접 관련이 없는 사진. 연합뉴스 고등학교 수업시간에 학생들에게 “너희들...
-
설약 입결 1
언매 미적 생지 기준으로 백분위 99 96 3 97 97 이 되나요 이걸로 설약...
-
이번 6모에서 빈칸추론 ㄱㄴㄷ 나왔잖아요. 문제는 쉬워서 다 맞추긴했는데 이제 그...
-
고1 내신 대비입니다. 난이도 비슷한 편인가요????
-
문학 강e분 0
지금부터 하려면 책만 봐도 될까요? 강의도 봐야하나..
-
일단 현강수업듣는거는 확실히 아니고 인터넷영상으로 수업듣는거랑 시험보는거는...
존재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중 어디에도 함정이 없으므로 <—- 거짓말한 걸수도 있죠
그렇네요 어쩐지 너무 지저분하더라