논리 퍼즐(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를 선물하세요.
-
나만 불하고 재 대립 아니라 생각해서 바로 5번체크하고 넘겼나 3번이 선택률 엄청높았네...
-
설레임.... 2
4칸부터 너무 빡센데 드랍하고 싶네여 하.....
-
치킨 언제와 2
-
시발ㅠㅠㅠㅠㅠ
-
6모 계속 보면서 참...내가 이걸 다 풀고 표점 이득을 볼 수가 있을까 싶네요
-
다시 누우면 편함
-
-
대인라 이정수쌤 대기풀렸는데 수업 많이 어렵나요? 문학 김상훈만하고 나머지는...
-
고구마님 자료 마구마구 제본해야지 으흐흐
-
인생망 2
망망
-
정신병자는 정신병 시기를 지나야 그때가 정신병이엇음을 알게 된다 2
나 3~ 5월에 개정신병자였는데 이정도도 정신병자인가? 싶고 그랫는데 정신병...
-
내가 이상한건가
-
여성가족부 장관에 남자를 임명한다면? (쓴웃음)
-
안녕하세요~ 이투스 승후쌤 연구소 GT SCIENCE ZONE입니다. 작년에 이어...
-
너희들은 전부 원하는 대학 이상으로 간다.
-
7모기준 생윤 32 사문 50 인데 두 과목 투자한 시간은 비슷해요 이거 킵고잉...
-
고2인데 방학되기전에 1학년거 빨리 보고갈려고 샀는데 강의도 다 들어야할까요?
-
수능장 중압감 생각하면 어지간해선 그 긴장감을 재현하지 못함. 24수능 골목안이랑...
-
-
떨린다..
-
본인 비판 글에 매우 예민함
-
군대 가는 것중에 이건 진짜 개어이가 없더만요 ㄹㅇㅋㅋ 3
상근 같은 경우 고졸은 상근이 많이 뜬다고 합니다 고졸이 무슨 벼슬이라고? 대학...
-
ㅈㄱㄴ
-
안보고싶어..
-
현우진 자주 3
급발진하는듯 전에 오르비에서도 난리 한번 났었고
-
부모님이 자식에게 하는건 희생이 아니라 사랑이다. 부모님은 본인이 희생하고 있다...
-
개학 후에 자습 많이 할 텐데 아무래도 눈치가 보여 인강이 필요한 n제는 집에서...
-
ㅜㅜ
-
-
문제 많이 푸는 게 나을까요 아니면 실전개념을 하는 게 나을까요 낮2 정도 나옵니다...
-
맥스택을 불러..!
-
매년 1컷 80초중반으로 한번씩 핵불지름
-
이게 소베이트군에 포위된 베를린에 갇혀있는아돌프에 의해 암살당한 히틀러의 후계이자...
-
신기하다
-
대재명이 수능을 불로 내주실거임.
-
으에에에
-
국어 죽고싶다 0
6모 2라 좀 감잡았나 싶었는데 어김없이 7모 3등급 물론 패드로 풀어서 좀...
-
막 하루 4갑씩 ㄷㄷㄷ 어느 날 돈이 너무 많이 들어서 편의점인가? 가서 ㅈㄴ 많이...
-
m 1 3 5 7 9 나오니까 우변이 1/256 보다 크고 1/1024 보다 작거나...
-
의대 복귀하네요 0
의대 도전할 명분이 하나 더 생겼다..
-
큐브에서 의대보다 한양대 공대들이 더 답변 잘해줌
-
진짜 거지같고 힘든데 사람은 어케든 적응하더라..
-
구스타프 클림트 혹시 누구를 생각하셨습니까?
-
선생이란 직업은 1
온실 속 화초란 말에 제일 잘 어울리는 직업임. 경쟁에서 벗어난 직업이야 다...
-
노랑통닭 시킴 10
-
작수 국어 밀려써서 저 모양이긴 한데 무튼 이 정도면 괜찮나요 작년에 ㄹㅇ 눈테러급...
-
Hello Everyone, My name is Ryan from Centum...
-
역시 이딴 성적으로는 갈수잇는곳이 없군요
-
아는형이 존나쎈 민트사탕먹은 뒤에 냉수넘기는 느낌이라는데 맞아여?
-
ㅈㄴ 재밌음
존재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중 어디에도 함정이 없으므로 <—- 거짓말한 걸수도 있죠
그렇네요 어쩐지 너무 지저분하더라