수학 논리 퀴즈
작성 완료
- 2 이상 50 이하의 두 수 $x, y$를 고려하자
- A에게는 두 수의 곱을 B에게는 두 수의 합을 알려주었다
- 아래 A와 B의 대화를 바탕으로 $x, y$를 맞혀라
A: 두 수가 뭔지 모르겠어
B: 나도 모르겠어
A: 두 수가 뭔지 알겠어!
B: 나도 알겠어!
- 문제적 남자에 출제된 문제이다
- 문제 조건에 상한은 없었는데 다른 문제에는 상한이 있어 동일하게 50으로 설정했다
- A가 처음에 두 수가 뭔지 모르겠다고 했다
- 그런데 두 수의 곱만을 알고서 두 수가 무엇인지 바로 알 수 있을까?
- 예컨대 $xy$가 34라고 해보자
- 34는 2와 17의 곱으로만 만들어지므로 A는 두 수가 무엇인지 바로 알 수 있다
- 하지만 만약 $xy$가 12라면 어떨까
- A의 입장에서는 12가 3과 4의 곱인지 2와 6의 곱인지 현재로선 알 수 없다
- 왜 1과 12는 고려하지 않는거지? ---> 2 이상 50 이하의 수여야 하는데 1은 해당 범위에 포함되지 않음
- $xy$에 대하여 1과 자기 자신을 제외한 약수가 2개를 초과한다면 A는 두 수가 무엇인지 알 수 없다
- 즉 $xy$에 대하여 약수가 4개를 초과한다면 A는 두 수가 무엇인지 알 수 없다
- B는 A의 답변을 듣고 추가 정보를 얻어도 두 수가 뭔지 모르겠다고 했다
- 그런데 A의 답변과 두 수의 합을 알고서 두 수가 무엇인지 알 수 있을까?
- 사실 A의 답변을 듣지 않아도 두 수가 무엇인지 알 수 있는 경우가 존재한다
- 만약 $x+y$가 4또는 5라고 해보자
- $x+y$가 4라면 두 수는 2와 2이고 $x+y$가 5라면 두 수는 2와 3이다
- $x+y$가 이보다 큰 6부터는 두 수를 무엇인지 바로 알 수 없게 된다 (2와 4 또는 3과 3)
- 이제 A의 답변 정보도 추가로 사용해보자
- 일단 두 수는 2이상 50이하이므로 $x+y$의 범위는 4 이상 100 이하이다
- $x+y$를 $T$라고 하자, $T$는 6 이상이다
- 그러면 $T$가 홀수일 때 두 수 $x,y$로 가능한 조합은 $(2, T-2), \cdots, \left(\big\lfloor\frac{T}{2}\big\rfloor, \big\lfloor\frac{T}{2}\big\rfloor + 1 \right)$이고
- $T$가 짝수일 때 두 수 $x,y$로 가능한 조합은 $(2, T-2), \cdots, \left(\frac{T}{2}, \frac{T}{2}\right)$이다
- 가능한 조합 각각에 대하여 $xy$를 계산하고 약수의 개수를 확인하자
- 약수의 개수가 4개 이하라면 정답이 아니므로 제외하면 된다
- 만약 4개 이하라면 A가 답을 맞혔을 것이다
- 그렇게 해서 남아있는 조합이 1개 뿐이라면 B가 정답을 맞혔을 것이다
- 예컨대 $x+y$가 8이라고 하자
- 그러면 가능한 $x,y$의 조합은 $(2, 6), (3, 5), (4,4)$이다
- 각 조합에 대하여 $xy$를 계산하면 $12, 15, 16$이다
- 12의 약수의 개수는 $1,2,3,4,6,12$로 6개이다
- 15의 약수의 개수는 $1,3,5,15$로 4개이다
- 16의 약수의 개수는 $1,2,4,8,16$으로 5개이다
- 만약 $x,y$가 3과 5라면 $xy$는 15이고 15는 3과 5의 곱으로만 이루어지므로 A가 처음에 답을 맞혔을 것이다
- 따라서 약수의 개수가 4개 이하인 15는 $xy$로 가능하지 않다
- 하지만 12와 16은 약수의 개수가 4개 초과이므로 $xy$로 가능하다
- 즉, B는 A의 답변을 듣더라도 $x,y$가 2와 6인지 3과 5인지 알아낼 수 없다
- A는 B의 대답을 듣고 두 수가 무엇인지 알겠다고 했다
- 그런데 A는 두 수의 곱만 알고 두 수의 합은 모르는데 B의 답변 정보를 두 수가 무엇인지 알아내는데 이용할 수 있을까?
- 사실 $xy$만 알아도 이를 바탕으로 $x+y$를 추론할 수 있다
- 만약 $xy$가 12라고 해보자
- 그러면 $x,y$는 2와 6이거나 3과 4이다
- 다르게 얘기하면 $x+y$는 7이거나 8이다
- 즉, $xy$로 $x+y$를 추론할 수 있으므로 B의 답변 정보를 사용할 수 있다!
- B가 나도 모르겠다라고 답변했으니 이를 사용해보자
- 우선 $x+y$가 7이라고 가정해보자
- 그러면 $xy$를 모르고 $x+y$만 알고 있는 B의 입장에서 가능한 $x,y$의 조합은 $(2,5),(3,4)$이다
- 각 조합에 대해 $xy$를 계산하면 $10, 12$이다
- 만약 $x, y$가 2와 5라면 $xy$는 10이며 10은 2와 5의 곱으로만 이루어진다
- 그렇게 되면 A가 처음에 정답을 맞혔을 것이므로 처음에 모르겠다고 답변한 것과 모순된다
- 하지만 $xy$가 12라면 약수의 개수가 6개로 가능한 곱의 조합이 2개 이상이다
- 그러면 A가 처음에 모르겠다고 한 것이 합리적이다
- 즉, B의 입장에서 $x+y$가 7일 때 가능한 $xy$는 12뿐이며 이때의 $x,y$는 3과 4이다
- 그런데 이것이 사실이라면 B가 A의 답변을 듣고 정답을 모르겠다 답변한 것과 모순된다
- 따라서 $x+y$는 7이 될 수 없다
- 이제 $x+y$가 8이라고 가정해보자
- 만약 $x+y$가 8이라고 가정했는데 모순이 안 된다면 A의 입장에선 $xy$는 12이고 $x+y$는 8이므로 $x,y$는 2와 6임을 알아낼 수 있다!
- $x+y$가 8일 때 B의 입장에서 가능한 $x,y$의 조합은 $(2,6), (3,5), (4,4)$이다
- 각 조합에 대해 $xy$를 계산하면 $12, 15, 16$이다
- 만약 $x, y$가 3과 5라면 $xy$는 15이며 15는 3과 5의 곱으로만 이루어진다
- 그렇게 되면 A가 처음에 정답을 맞혔을 것이므로 처음에 모르겠다고 답변한 것과 모순된다
- 하지만 $xy$가 12 또는 16이라면 약수의 개수가 4를 초과하므로 가능한 곱의 조합이 2개 이상이다
- 12라면 2와 6 또는 3과 4. 16이라면 2와 8 또는 4와 4
- 그러면 A가 처음에 모르겠다고 한 것이 합리적이다
- 즉, $x+y$가 8이라면 B의 입장에서 가능한 $xy$는 12 또는 16이며 이때의 $x,y$는 2와 6 그리고 4와 4이다
- 이러면 가능한 $x,y$ 조합이 2개 이상이므로 B의 입장에서는 $x,y$가 2와 6인지 4와 4인지 알 수 없다
- 즉, $xy$가 12라면 B의 답변을 바탕으로 A는 $x+y$가 7이 아닌 8임을 알아낼 수 있다
- 그렇게 되면 A는 $xy$는 12, $x+y$는 8이라는 정보를 바탕으로 $x,y$가 2와 6임을 알아내고 정답을 맞힐 수 있다
- 알고리즘
- A에게 주어진 $xy$를 바탕으로 가능한 $x+y$를 계산한다
- 계산된 $x+y$ 각각에 대해 가능한 $xy$를 계산한다
- $xy$ 집합에 대해 약수의 개수가 4개 이하인 것들을 제외한다
- 그리고 남은 $xy$ 집합의 원소가 1개라면 B가 정답을 맞혔을 것이므로 해당 $x+y$는 제외한다
- 이 과정을 $x+y$ 집합의 모든 원소에 대해 반복한 후 남아있는 원소가 1개 뿐이라면 A가 정답을 맞힐 수 있다
- B는 A의 대답을 듣고 자신도 두 수가 무엇인지 알겠다고 했다
- A의 대답을 이용하기 위해 A의 생각을 따라가보자
- 만약 B에게 $x+y$가 8이라는 정보가 주어졌다고 해보자
- 그러면 가능한 $x,y$의 조합은 $(2,6), (3,5), (4,4)$이다
- 각 조합에 대해 $xy$를 계산하면 $12, 15, 16$이다
- 만약 $x, y$가 3과 5라면 $xy$는 15이며 15는 3과 5의 곱으로만 이루어진다
- 그렇게 되면 A가 처음에 정답을 맞혔을 것이므로 처음에 모르겠다고 답변한 것과 모순된다
- 하지만 $xy$가 12 또는 16이라면 약수의 개수가 4를 초과하므로 가능한 곱의 조합이 2개 이상이다
- 그러면 A가 처음에 모르겠다고 한 것이 합리적이다
- 만약 $xy$가 12라고 해보자
- A의 입장에서 볼 때 $xy$가 12라면 가능한 $x,y$의 조합은 $(2,6),(3,4)$이다
- 각 조합에 대해 $x+y$를 계산하면 $7,8$이다
- 우선 $x+y$가 7이라고 가정해보자
- 그러면 A가 생각했을 때 $xy$를 모르는 B의 입장에서 가능한 $x,y$의 조합은 $(2,5),(3,4)$이다
- 각 조합에 대해 $xy$를 계산하면 $10, 12$이다
- 만약 $x, y$가 2와 5라면 $xy$는 10이며 10은 2와 5의 곱으로만 이루어진다
- 그렇게 되면 A가 처음에 정답을 맞혔을 것이므로 처음에 모르겠다고 답변한 것과 모순된다
- 하지만 $xy$가 12라면 약수의 개수가 6개로 가능한 곱의 조합이 2개 이상이다
- 그러면 A가 처음에 모르겠다고 한 것이 합리적이다
- 즉, A가 생각했을 때 $xy$를 모르는 B의 입장에서 $x+y$가 7이라면 가능한 $xy$는 12뿐이며 이때의 $x,y$는 3과 4이다
- 그런데 이것이 사실이라면 B가 A의 답변을 듣고 정답을 모르겠다 답변한 것과 모순된다
- 따라서 $x+y$는 7이 될 수 없다
- 이제 $x+y$가 8이라고 가정해보자
- $x+y$가 8이라면 A가 생각했을 때 $xy$를 모르는 B의 입장에서 가능한 $x,y$의 조합은 $(2,6), (3,5), (4,4)$이다
- 각 조합에 대해 $xy$를 계산하면 $12, 15, 16$이다
- 만약 $x, y$가 3과 5라면 $xy$는 15이며 15는 3과 5의 곱으로만 이루어진다
- 그렇게 되면 A가 처음에 정답을 맞혔을 것이므로 처음에 모르겠다고 답변한 것과 모순된다
- 하지만 $xy$가 12 또는 16이라면 약수의 개수가 4를 초과하므로 가능한 곱의 조합이 2개 이상이다
- 12라면 2와 6 또는 3과 4, 16이라면 2와 8 또는 4와 4
- 그러면 A가 처음에 모르겠다고 한 것이 합리적이다
- 즉, A가 생각했을 때 $x+y$가 8이라고 가정하면 B의 입장에서 가능한 $xy$는 12 또는 16이며 이때의 $x,y$는 2와 6 그리고 4와 4이다
- 이러면 가능한 $x,y$ 조합이 2개 이상이므로 B의 입장에선 $x,y$가 2와 6인지 4와 4인지 알 수 없다
- 즉, A에게 주어진 $xy$가 12라면 B의 답변 정보를 바탕으로 A는 $x+y$가 7이 아닌 8임을 알아낼 수 있다
- 그렇게 되면 A는 $xy$는 12, $x+y$는 8이라는 정보를 바탕으로 $x,y$가 2와 6임을 알아내고 정답을 맞힐 수 있다
- 즉, $x,y$가 2와 6이라면 A: 두 수가 뭔지 모르겠어, B: 나도 모르겠어, A: 두 수가 뭔지 알겠어! 까지의 과정에 모순되는 점이 없다
- 따라서 $x+y=8$이 주어진 B의 입장에선 $xy$의 후보군으로 12를 고려할 수 있다
- 그렇다면 이제 $xy$가 16이라고 가정하고 A의 입장이 되어 생각해보자
- A의 입장에서 볼 때 $xy$가 16이라면 가능한 $x,y$의 조합은 $(2,8),(4,4)$이다
- 각 조합에 대해 $x+y$를 계산하면 $8,10$이다
- 우선 $x+y$가 8이라고 가정해보자
- 그러면 A가 생각했을 때 $xy$를 모르는 B의 입장에서 가능한 $x,y$의 조합은 $(2,6),(3,5),(4,4)$이다
- 각 조합에 대해 $xy$를 계산하면 $12, 15,16$이다
- 약수의 개수가 4개를 초과해야 하므로 가능한 $xy$는 12 또는 16이다
- $x+y$가 8이라면 B: 나도 모르겠어라는 답변이 합리적이다
- 이제 $x+y$가 10이라고 가정해보자
- 그러면 A가 생각했을 때 $xy$를 모르는 B의 입장에서 가능한 $x,y$의 조합은 $(2,8),(3,7),(4,6),(5,5)$이다
- 각 조합에 대해 $xy$를 계산하면 $16, 21,24,25$이다
- 약수의 개수가 4개를 초과해야 하므로 가능한 $xy$는 16 또는 24이다
- $x+y$가 10이라면 B: 나도 모르겠어라는 답변이 합리적이다
- 따라서 만약 $xy$가 16이라면 A의 입장에서 볼 때 가능한 $x+y$는 8과 10이며 이때의 $x,y$는 4와 4 그리고 2와 8이다
- 그런데 이렇게 되면 A의 입장에선 $x+y$가 8과 10 둘 다 가능하므로 둘 중 어느것인지 알지 못한다
- 그러면 A: 두 수가 뭔지 알겠어!와 같이 대답할 수 없으므로 모순이다
- 즉, 처음 B에게 주어진 $x+y$가 8이라면 $xy$는 16이 될 수 없다
- 따라서, 가능한 $xy$는 12이므로 B는 $x,y$가 2와 6임을 알 수 있고 B: 나도 알겠어!라고 대답할 수 있다
- 위의 풀이는 정답인 2와 6을 시작으로 접근했기에 쉽게 문제를 해결할 수 있었다 (사실 아무 두 수나 정한건데 그게 정답이었다;;)
- 모든 경우를 빠르게 고려하기 위해 파이썬을 사용해보자
- 정답이 2와 6만 존재하는지 다른 경우도 존재하는지 알 수 있을 것이다
- 로직을 정리하고 가자
- 일단 두 수의 곱 $n$이 주어지면 $n = xy$를 만족하는 $(x,y)$ 쌍을 찾는다
- 단, $\min \leq x \leq y \leq \max$
- 곱의 조합 쌍이 2개 이상이면 A는 두 수가 무엇인지 알 수 없다
- 곱의 조합 쌍을 찾자
import math
def find_product_pairs(n, minimum=2, maximum=50):
product_pairs = []
for x in range(minimum, math.isqrt(n) + 1):
if n % x != 0:
continue
y = n // x
if not (x <= y and minimum <= x <= maximum and minimum <= y <= maximum):
continue
product_pairs.append((x, y))
return product_pairs
# 예시
n = 20
minimum = 2
maximum = 50
product_pairs = find_product_pairs(n, minimum, maximum)
print(product_pairs)
- 곱의 조합쌍이 2개 이상이면 A는 정답을 맞힐 수 없다
def has_elements(sequence):
return len(sequence) >= 2
def step1(n, minimum=2, maximum=50):
return find_product_pairs(n, minimum, maximum)
def check_step1(pairs):
"""A가 모르겠다고 한 것이 타당한지 확인"""
return has_elements(pairs)
# 예시
n = 12
minimum = 2
maximum = 50
pairs = step1(n, minimum, maximum)
result = check_step1(pairs)
answer = "압니다" * (1 - result) + "모릅니다" * result
print(f"두 수의 곱으로 {n}이(가) 주어졌을 때 A는 두 수가 무엇인지 압니까?: {answer}")
print(f"현재 A가 정답으로 고려하고 있는 후보군: {pairs}")
- 두 수의 합 $n$이 주어지면 $n = x+y$를 만족하는 $(x,y)$ 쌍을 찾는다
- $(x,y)$ 쌍 각각에 대해 $xy$를 계산한다
- $xy$에 대해 A: 두 수가 뭔지 모르겠어에서 사용한 알고리즘을 적용한다
- 남은 $(x,y)$ 쌍이 2개 이상이면 B는 두 수가 뭔지 알 수 없다
- 합이 $n$인 $x, y$ 조합을 찾자
def find_sum_pairs(n, minimum=2, maximum=50):
sum_pairs = []
for x in range(minimum, maximum + 1):
y = n - x
if not (minimum <= y <= maximum and x <= y):
continue
sum_pairs.append((x, y))
return sum_pairs
# 예시 실행
n = 8
minimum = 2
maximum = 50
sum_pairs = find_sum_pairs(n, minimum, maximum)
print(sum_pairs)
- 각 조합에 대해 곱의 조합쌍이 2개 이상인지 파악하자
def filter_sum_pairs_step2(sum_pairs, minimum=2, maximum=50):
selected_pairs = []
for x, y in sum_pairs:
n = x * y
pairs = step1(n, minimum, maximum)
if not check_step1(pairs):
continue
selected_pairs.append((x, y))
return selected_pairs
def step2(n, minimum=2, maximum=50):
sum_pairs = find_sum_pairs(n, minimum, maximum)
selected_pairs = filter_sum_pairs_step2(sum_pairs, minimum, maximum)
return selected_pairs
def check_step2(pairs):
"""B가 모르겠다고 한 것이 타당한지 확인"""
return has_elements(pairs)
# 예시
n = 8
minimum = 2
maximum = 50
pairs = step2(n, minimum, maximum)
result = check_step2(pairs)
answer = "압니다" * (1 - result) + "모릅니다" * result
print(f"두 수의 합으로 {n}이(가) 주어졌을 때 A의 답변을 들은 B는 두 수가 무엇인지 압니까?: {answer}")
print(f"현재 B가 정답으로 고려하고 있는 후보군: {pairs}")
- 주어진 곱을 $(x, y)$ 쌍으로 나눈다
- 각 곱에 대해 A: 두 수가 뭔지 모르겠어에서 사용한 알고리즘을 적용한다 (15, 21과 같은 수를 스킵하기 위함이다)
- 남은 곱에 대해 합을 구한다
- 각 합에 대해 B: 나도 모르겠어에서 사용한 알고리즘을 적용한다
- 이를 만족하는 합이 2개 이상이면 A는 정답을 맞히지 못한다
- 하지만 A는 두 수가 무엇인지 알아냈으므로 이를 만족하는 합이 단 1개 뿐인 것을 의미한다
-
주어진 곱을 $(x, y)$ 쌍으로 나누자
-
각 쌍에 대해 step1 함수의 알고리즘를 적용하고 남은 쌍에 대해 합을 구하자
-
각 합에 대해 step2 함수를 적용하고 이를 만족하는 합을 고려하자
-
합이 1개만 남았다면 A는 정답을 맞힐 수 있다
def filter_product_pairs_step3(product_pairs, minimum=2, maximum=50):
selected_pairs = []
for x, y in product_pairs:
n = x + y
pairs = step2(n, minimum, maximum)
if not check_step2(pairs):
continue
selected_pairs.append((x, y))
return selected_pairs
def step3(n, minimum=2, maximum=50):
pairs = step1(n, minimum, maximum)
if not check_step1(pairs):
return []
selected_pairs = filter_product_pairs_step3(pairs, minimum, maximum)
return selected_pairs
def check_step3(pairs):
"""A가 두 수가 무엇인지 알겠다고 한 것이 타당한지 확인"""
return len(pairs) == 1
# 예시
n = 12
minimum = 2
maximum = 50
pairs = step3(n, minimum, maximum)
result = check_step3(pairs)
answer = "압니다" * result + "모릅니다" * (1 - result)
print(f"두 수의 곱으로 {n}이(가) 주어졌을 때 B의 답변을 들은 A는 두 수가 무엇인지 압니까?: {answer}")
print(f"현재 A가 정답으로 고려하고 있는 후보군: {pairs}")
- A: 두 수가 뭔지 알겠어! 상황까지 모순이 없음을 가정한다
- 즉, 모든 step 함수에 대해 이전 step 함수까지 모순이 없음을 가정한다
n = 15
minimum = 2
maximum = 50
pairs = step3(n, minimum, maximum)
result = check_step3(pairs)
answer = "압니다" * result + "모릅니다" * (1 - result)
print(f"두 수의 곱으로 {n}이(가) 주어졌을 때 B의 답변을 들은 A는 두 수가 무엇인지 압니까?: {answer}")
print(f"현재 A가 정답으로 고려하고 있는 후보군: {pairs}")
- 두 수의 곱이 15라면 사실 A는 정답을 안다 (두 수는 3과 5이다)
- 하지만 이는 A: 두 수가 뭔지 알겠어! 단계가 아닌 최초에 알았어야 하므로 모른다로 답변하게 설계했다
- 주어진 합을 $(x, y)$ 쌍으로 나누고 곱을 구한다
- 이제 각 곱에 대해 생각해보자
- 각 곱에 대해 A: 두 수가 뭔지 알겠어!에서 사용한 알고리즘을 적용한다
- 남은 곱이 단 하나뿐이라면 B는 정답을 맞힐 수 있다
def filter_sum_pairs_step4(sum_pairs, minimum=2, maximum=50):
selected_pairs = []
for x, y in sum_pairs:
n = x * y
pair = step3(n, minimum, maximum)
if not check_step3(pair):
continue
selected_pairs.append((x, y))
return selected_pairs
def step4(n, minimum=2, maximum=50):
sum_pairs = find_sum_pairs(n, minimum, maximum)
pairs = step2(n, minimum, maximum)
if not check_step2(pairs):
return []
selected_pairs = filter_sum_pairs_step4(sum_pairs, minimum, maximum)
return selected_pairs
def check_step4(pairs):
"""B가 두 수가 무엇인지 알겠다고 한 것이 타당한지 확인"""
return len(pairs) == 1
# 예시
n = 8
minimum = 2
maximum = 50
pairs = step4(n, minimum, maximum)
result = check_step4(pairs)
answer = "압니다" * result + "모릅니다" * (1 - result)
print(f"두 수의 합으로 {n}이(가) 주어졌을 때 A의 답변을 들은 B는 두 수가 무엇인지 압니까?: {answer}")
print(f"현재 B가 정답으로 고려하고 있는 후보군: {pairs}")
def solve(minimum=2, maximum=50, log=True):
if log:
print("#### 두 수의 합과 숫자 쌍 ####")
answer = []
for n in range(minimum * 2, maximum * 2 + 1):
pairs = step4(n, minimum, maximum)
if log:
print(f"{n}: {pairs}")
if not check_step4(pairs):
continue
pair = pairs[0]
answer.append(pair)
return answer
minimum = 2
maximum = 50
solution = solve(minimum, maximum)
print("문제의 정답:", solution)
- 빈 리스트는 중간에 모순이 발견되어 B: 나도 알겠어!까지 도달하지 못한 것을 의미한다
- 두 수의 합이 85인 경우 숫자 쌍이 2개 존재하는데 이는 B: 나도 알겠어!에 모순되는 것을 의미한다 (B는 둘 중 어느 것인지 알지 못한다)
- 8이나 77처럼 숫자 쌍이 하나만 존재하는 것은 B: 나도 알겠어!를 포함한 모든 대화가 모순 없이 이루어졌음을 뜻한다 (즉, 문제의 정답을 의미한다)
- 따라서 문제의 정답은 $(2, 6),\,(35,42),\,(36,44),\,(40,42)$이다
minimum = 10
maximum = 50
solution = solve(minimum, maximum, log=False)
print("문제의 정답:", solution)
- 이때의 정답은 $(10, 21),\,(35,42),\,(36,44),\,(40,42)$이다
minimum = 2
maximum = 100
solution = solve(minimum, maximum, log=False)
print("문제의 정답:", solution)
- 이때의 정답은 $(2, 6),\,(84,88)$이다