수학 논리 퀴즈 2
작성 완료
- 수학 논리 퀴즈와 같은 부류의 또 다른 문제이다
- 파이썬 풀이 부분에서 수학 논리 퀴즈에서 사용한 코드를 참고했다
- 유명한 문제이다: https://en.wikipedia.org/wiki/Sum_and_Product_Puzzle
- 위 링크에선 $x < y$인 조건이 있는데 여기선 무시했다
- 2 이상 100 이하의 두 수 $x, y$를 고려하자
- A에게는 두 수의 곱을 B에게는 두 수의 합을 알려주었다
- 아래 A와 B의 대화를 바탕으로 $x, y$를 맞혀라
- A: 도저히 모르겠는데요
- B: 당신이 모를 거란 것쯤은 이미 알고 있었어요
- A: 아, 두 수가 뭔지 알겠습니다
- B: 저도 두 수가 뭔지 알겠습니다
- 두 수의 곱을 $P$라고 하자
- A가 정답을 모르겠다는 것은 $P=xy$를 만족하는 $(x,y)$ 쌍이 2개 이상임을 뜻한다
- 두 수의 합을 $S$라고 하자
- 일단 $S$는 6 이상 198 이하이다
- 그렇지 않다면 B는 A의 답변을 듣지 않고도 정답을 바로 맞힐 수 있다
- $S=x+y$를 만족하는 $(x,y)$쌍을 찾아보자
- $S$가 홀수일 때 두 수 $x,y$로 가능한 조합은 $(2, S-2), \cdots, \left(\big\lfloor\frac{S}{2}\big\rfloor, \big\lfloor\frac{S}{2}\big\rfloor + 1 \right)$이고
- $S$가 짝수일 때 두 수 $x,y$로 가능한 조합은 $(2, S-2), \cdots, \left(\frac{S}{2}, \frac{S}{2}\right)$이다
- 그런데 B는 A가 정답을 모를거라고 확신했다
- 가능한 모든 $(x,y)$쌍에 대해 $xy$를 계산해보자
- 만약 $xy$ 중에 두 소수의 곱이 존재한다면 B는 A가 정답을 알지 못한다고 확신할 수 없다
- 왜냐하면 두 수의 곱이 $P$인 두 수 $(x, y)$ 쌍은 1개만 존재하기 때문이다
- 예컨대 A가 $P=21$을 알고 있다면 두 수는 3과 7뿐이므로 바로 정답을 맞힐 수 있다
- 그런데 어떻게 $S=x+y$를 만족하는 소수 $x,y$가 존재하는지 판단할 수 있을까?
- 쉬운 방법으론 다음이 있다. $S=x+y$를 만족하는 가능한 모든 $(x,y)$ 쌍을 고려하자
- 그리고 $x$와 $y$의 곱을 $P$라고 하자
- 이때 $P=ab$를 만족하는 2 이상 100 이하의 $(a,b)$ 쌍이 단 1개라면 $x,y$는 소수이다
- 즉, B는 당신이 모를 거란 것쯤은 이미 알고 있었어요와 같이 대답할 수 없으므로 모순이다
- 아래는 탐색 시간을 줄이는 알고리즘이다
- 일단 임의의 짝수 $S = x + y$에 대해선 소수 $x,y$가 항상 존재한다
- 여기에는 골드바흐의 추측이 사용된다 (한 번쯤 들어봤을 법하다)
- 밀레니엄 7대 난제 중 하나인 골드바흐의 추측은 $4$이상의 모든 짝수는 두 소수의 합으로 표현 가능함을 뜻한다
- 물론 완전히 증명된건 아니지만 충분히 큰 영역까지 성립함이 보여졌다
- 따라서 이 문제에서 다루는 영역은 당연히 성립한다
- 그럼 $S$가 홀수일 땐 괜찮을까?
- $S$가 홀수일려면 필연적으로 $x,y$ 중 하나는 짝수, 다른 하나는 홀수여야 한다
- 둘 다 짝수이거나 홀수라면 $x+y$는 짝수이기 때문에 그렇다
- $x$와 $y$는 서로 대칭적이므로 임의로 $x$를 짝수 $y$를 홀수라 가정하겠다
- $x$가 만약 2이고 $y$가 소수라면 $xy$는 2와 y의 곱으로만 이루어진다
- 하지만 $x$가 4이상의 짝수라면 $xy$는 합성수이다
- 그런데 이는 상한 100을 고려하지 않은 것으로 $x$가 4이상의 짝수라도 $y$가 50이상의 소수라면 $xy$는 유일한 해 1개를 가진다 (곱의 쌍이 단 1개)
- 그런데 $x$가 4 이상의 짝수이고 $y$가 소수가 아닌 홀수여도 하한과 상한 조건에 의해 $xy$를 나타내는 곱의 쌍이 1개만 존재할 수 있을까?
- $x$가 98, $y$가 95이면 가능하다
- 9310은 95와 98의 곱으로만 가능하다
- 짝수인 $S$는 두 소수의 합으로 표현되므로 정답에서 제외하고 홀수인 $S$에 대해선 브루트 포스로 정답 여부를 판단하자
- 즉, 홀수 $S(=x+y)$를 만족하는 $(x,y)$ 쌍에 대해 $xy$가 $x$와 $y$의 곱으로만 표현된다면 정답이 될 수 없다
- 이 과정을 거쳐 정답으로 가능한 두 수의 합을 $S^*$라고 정의하겠다
- 기본적으로 곱의 쌍이 1개뿐인 수는 배제한다 (첫 단계에서 A가 정답을 맞혔을 것이다)
- $P=xy$를 만족하는 모든 $(x,y)$ 쌍에 대해 다음을 계산하자
- $S=x+y$라 하고 $S=a+b$을 만족시키는 모든 $(a,b)$에 대해 $ab$을 계산하자
- 만약 $ab$중 곱의 쌍이 1개뿐인 수가 존재한다면 B는 A가 모를거라고 확신할 수 없다
- 즉, 해당 $x,y$는 정답이 아닌 것이다
- 그런데 위를 만족하는 $(x,y)$ 조합이 단 1개뿐이라면 A는 두 수가 뭔지 안다
- 예컨대 A가 처음에 전달 받은 $P$가 18이라고 해보자
- 그럼 $x,y$는 2와 9 또는 3과 6이다
- 따라서 A는 도저히 알 수 없다
- 그런데 B는 A가 모를걸 알고 있었다
- 곱이 18이므로 합은 9 아니면 11이다
- 만약 두 수의 합 $S$가 $9$라면 $2,7$이 가능하다
- 그러면 두 수의 곱은 14가 되는데 14는 오직 2와 7의 곱으로만 이루어진다
- 따라서 B는 당신이 모를 거란 것쯤은 이미 알고 있었어요라고 생각할 수 없다
- 이제 두 수의 합이 11이라고 해보자
- 두 수의 합이 11인 쌍은 $(2,9), (3,8),(4,7),(5,6)$이다
- 각 쌍의 원소 곱은 $18, 24, 28, 30$이다
- 이들은 모두 합성수 이므로 A는 정답을 알지 못한다
- 즉, B는 당신이 모를 거란 것쯤은 이미 알고 있었어요라고 생각할 수 있다
- 따라서 A가 전달 받은 두 수의 곱이 18이라면 가능한 합은 11뿐이고 이 때의 $x,y$는 2와 9이다
- 경우의 수가 1개뿐이므로 A는 두 수가 무엇인지 알 수 있다
- A가 아, 두 수가 뭔지 알겠습니다라고 말한 정보를 이용해보자
- 일단 B는 당신이 모를 거란 것쯤은 이미 알고 있었어요라고 말했으므로 두 수의 합으로 가능한 것들은 $S^*$이다
- $S^* = x+y$를 만족하는 $(x, y)$에 대해 $xy$를 계산하면 $xy=ab$를 만족하는 $(a,b)$쌍은 2개 이상이다 (만약 1개뿐이라면 $S^*$일 수 없다)
- 가능한 $(a,b)$쌍 각각에 대해 $a+b$가 $S^*$에 포함되는지 확인하자
- 만약 $a+b$가 $S^*$에 포함되지 않는다면 해당 $(a,b)$는 정답이 될 수 없다 (B가 당신이 모를 거란 것쯤은 이미 알고 있었어요라고 말할 수 없다)
- 가능한 $(a,b)$쌍 중에서 $S^*$에 포함되는 $(a,b)$쌍이 단 1개뿐이라면 A는 아, 두 수가 뭔지 알겠습니다라고 말할 수 있다
- 이 과정을 가능한 모든 $(x,y)$쌍에 적용한 후 단 하나의 $(x,y)$쌍에 대해서만 A가 아, 두 수가 뭔지 알겠습니다라고 말할 수 있다면
- B는 저도 두 수가 뭔지 알겠습니다라고 말할 수 있다
- 로직을 정리하고 가자
- 일단 두 수의 곱 $P$가 주어지면 $P = xy$를 만족하는 $(x,y)$ 쌍을 찾는다
- 단, $\min \leq x \leq y \leq \max$ (여기서 $\min=2, \max=100$)
- 곱의 조합 쌍이 2개 이상이면 A는 두 수가 무엇인지 알 수 없다
- 곱의 조합 쌍을 찾자
import math
def find_product_pairs(n, minimum, maximum):
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 = 42
minimum = 2
maximum = 100
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, maximum):
return find_product_pairs(n, minimum, maximum)
def check_step1(pairs):
"""A가 모르겠다고 한 것이 타당한지 확인"""
return has_elements(pairs)
# 예시
n = 20
minimum = 2
maximum = 100
pairs = step1(n, minimum, maximum)
result = check_step1(pairs)
answer = "압니다" * (1 - result) + "모릅니다" * result
print(f"두 수의 곱으로 {n}이(가) 주어졌을 때 A는 두 수가 무엇인지 압니까?: {answer}")
print(f"현재 A가 정답으로 고려하고 있는 후보군: {pairs}")
- 짝수 $S$는 골드바흐의 추측에 의해 정답이 될 수 없다
- 홀수 $S=x+y$를 만족하는 가능한 모든 $(x,y)$ 쌍을 고려하자
- 모든 $(x,y)$쌍에 대해 $xy$를 계산하고 $xy$중에 곱의 쌍이 1개 뿐인 $xy$가 존재한다면
- 해당 $S$는 처음에 B가 받은 수가 될 수 없다
def use_goldbach_conjecture(num):
if num <= 2:
return False
return is_even(num)
def is_even(num):
return num % 2 == 0
def find_sum_pairs(n, minimum, maximum):
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
def filter_sum_pairs_step2(sum_pairs, minimum, maximum):
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 calculate_s_star(minimum, maximum):
s_star_set = set()
possible_summations = range(minimum * 2, maximum * 2 + 1)
for sum_ in possible_summations:
if use_goldbach_conjecture(sum_):
continue
sum_pairs = find_sum_pairs(sum_, minimum, maximum)
selected_pairs = filter_sum_pairs_step2(sum_pairs, minimum, maximum)
if len(sum_pairs) != len(selected_pairs): # B는 A의 답변을 듣기 전부터 A가 정답을 맞히지 못 할 것을 알고 있었다
continue
s_star_set.add(sum_)
return s_star_set
def check_step2(num):
"""B가 `A는 정답을 못 맞힐 거라고` 말한 것이 타당한지 확인"""
return num in S_STAR
minimum = 2
maximum = 100
S_STAR = calculate_s_star(minimum, maximum)
S_STAR
- 주어진 곱을 $(x, y)$ 쌍으로 나눈다
- 각 곱에 대해 A: 도저히 모르겠네요에서 사용한 알고리즘을 적용한다 (15, 21과 같은 수를 스킵하기 위함이다)
- 남은 곱에 대해 합을 구한다
- 각 합에 대해 B: 당신이 모를 거란 것은 이미 알고 있었어요에서 사용한 알고리즘을 적용한다
- 합이 $S^*$에 속해야 한다, 그렇지 않으면 제외한다
- 하지만 A는 두 수가 무엇인지 알아냈으므로 이를 만족하는 곱의 쌍이 단 1개 뿐인 것을 의미한다
-
주어진 곱을 $(x, y)$ 쌍으로 나누자
-
각 쌍에 대해 step1 함수의 알고리즘를 적용하고 남은 쌍에 대해 합을 구하자
-
각 합에 대해 $S^*$에 속하는지 계산하자
-
$S^*$에 속하는 합이 1개만 남았다면 A는 정답을 맞힐 수 있다
def filter_product_pairs_step3(product_pairs, minimum, maximum):
selected_pairs = []
for x, y in product_pairs:
s = x + y
if not check_step2(s):
continue
selected_pairs.append((x, y))
return selected_pairs
def step3(n, minimum, maximum):
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 = 52
minimum = 2
maximum = 100
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 = 100
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는 정답을 맞힐 수 있다
- 쉽게 말해 각 곱에 대해 다음을 생각하자
- 내가 A라면 A: 아, 두 수가 뭔지 알았습니다라고 말하며 정답을 맞힐 수 있었을까?
- 그렇다면 통과시키고 아니라면 제외한다
- 남은 곱이 1개뿐이면 B도 정답을 맞힐 수 있다
def filter_sum_pairs_step4(sum_pairs, minimum, maximum):
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, maximum):
if not check_step2(n):
return []
sum_pairs = find_sum_pairs(n, minimum, maximum)
selected_pairs = filter_sum_pairs_step4(sum_pairs, minimum, maximum)
return selected_pairs
def check_step4(pairs):
"""B가 두 수가 무엇인지 알겠다고 한 것이 타당한지 확인"""
return len(pairs) == 1
# 예시
n = 41
minimum = 2
maximum = 100
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, maximum, 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 = 100
S_STAR = calculate_s_star(minimum, maximum)
solution = solve(minimum, maximum)
print("문제의 정답:", solution)
- 빈 리스트는 중간에 모순이 발견되어 B: 저도 두 수가 뭔지 알겠습니다까지 도달하지 못한 것을 의미한다
- 11과 같이 숫자 쌍이 2개 이상 존재하는 수는 B: 저도 두 수가 뭔지 알겠습니다에 모순되는 것을 의미한다 (B는 답이 어느 것인지 알지 못한다)
- 17처럼 숫자 쌍이 하나만 존재하는 것은 B: 저도 두 수가 뭔지 알겠습니다를 포함한 모든 대화가 모순 없이 이루어졌음을 뜻한다 (즉, 문제의 정답을 의미한다)
- 따라서 문제의 정답은 $(4,13)$이다