논리 퍼즐(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를 선물하세요.
-
오 이런 3
안 읽씹하려던거 실수로 읽어버렸다
-
할머니 내년에 칠순이신데 어제 칠순 선물로 600만원짜리 팔찌 해주시면서 "당신...
-
문제 먼저 안풀어온다는데 킬러급도 그냥 즉석에서 슥슥 해설해 줌
-
시대인재 라이브 1
생1 듣고싶어서 찾아봤는데 지금 진도가 서바 푸는 것 같더라구요 저는 서바보다는...
-
이거 연계햇으면 몰랐겠네 왜그러냐 ㄹㅇ.... 페이커
-
오늘 좀 지난주꺼 한번에 기록하느라 귀찮노 ㅋㅋㅋㅋ 7서프 82 (높2) 7모도...
-
진지
-
창업 관련 자료를 조사하다가 우연히 서강대 졸업생 선배님 글을 보게 되었는데 초반엔...
-
정보) 내일은 투수 이름이다
-
아니 왜 0
우리집 소득 상위 10퍼냐.. 어이없네 ㅋㅋ
-
공통 느려 터져서 미적 풀 줄 알아도 풀 시간이 없음ㅠㅠㅠ
-
7모 사문 난이도 11
그렇게 쉽진 않은거 같은데 1컷이 47이나 되길래 좀 놀람 도표 찍맞이 되서 그런가
-
트랙 팬츠 국밥이긴 한데 고딩들 입는 거 보면 돈이 존나 많나 머징
-
대치러들 6
이 러인에 맛집 추천 좀 해주세요
-
현강커리 1월부터 쭉 탔는데 이쯤오니까 이게 의미가 있나하는생각이 쪼금 드네요 ㅠ...
-
자연계열 일반과 기준으로 대략 어느정도 봐야되나요?
-
One word is inextricably associated with...
-
킬캠 1회 지난주 70점 12 - 계산 밀었어야 14 - 대칭성 바로보고 쓱쓱 15...
-
29번. 답이 답인 것에 대해서는 감히 이의를 가질 수 없습니다. 그러나 4번...
-
이새끼왜자살준비함
-
게시글 잇음 옆자리 아저씨 또 트름해서 냄새 직격탄 ㅅㅂ.. 걸을 때 하수구 냄새도...
-
우인 : 어리석은 사람. (영리한 사냥꾼 이라는 뜻도 있으나, 지문에선 이런 뜻으로...
-
유교남이라 잘모르겠네
-
계산량ㄷㄷㄷㄷ
-
MSI트로피
-
못하면 ㅈㄴ욕하는편임 해체해라 그냥
-
답정너가 많은것 같음. 다른 근거나 의견을 들으려는게 아니라 본인의 생각을 확인받고...
-
어느 시험이든 교육청이든 핑까원이든 사설이든 수능이든 나는 꼭 틀렸거나 약한 유형
-
아 니 오 미 파 같은 근본없는 조합으로도 저정도나 해주는구나,,,
-
서바시즌에 대기 잘 안빠지나요? 5월말쯤 걸엇는데 갈 수 있을까요
-
와우..
-
티원 까비여
-
의대 복귀 관련해서 18
올해 1학기에 휴학하면서 수능 다시 준비하신분들 꽤 많은걸로 알고 있는데 그런분들도...
-
-
9모전까지 모고 몇개만 돌리면서 감유지하고 국수에 집중하고 9모 이후에 해도 가능할라나
-
25 전국 서바 6회총평 -72점 14번 – 계산 실수. 분수식에 8b^2를...
-
최애 적고 가셈
-
파엠 쵸비 캬캬 8
-
ㅇㅇ
-
페이커랑 5살 차이 나긴 한데
-
고2 방학 독서 2
바로 기출 하면 됨? 수시러긴 한데 2학기 내신으로 독서 + 교과 쓰려면 최저...
-
안 되면 말고 >> 너네 밸류 조합도 못하잖아..
-
선행을 했든 몰아서 공부했든 사교육을 했든 아무 상관없이 안정 1등급~100까지
-
강케이 말려서 풀 수 있는 문제도 틀려서 너무 아쉬운데… 걍 실력 올리면 말리는...
-
10월부터 3회독 드간다
-
ㅈㅈ 8
-
긴급속보
-
X를 눌러 조의를 표해주세요 사유는 그냥입니다
-
ㄹㅇ 그래서 그런가 역대급 미드차이네 ㅈㅈ
-
제우스 도란 6
원래 제우스였으면 어케 될것같음?
존재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중 어디에도 함정이 없으므로 <—- 거짓말한 걸수도 있죠
그렇네요 어쩐지 너무 지저분하더라