본문 바로가기

정수론 퍼즐10

프로베니우스 동전 문제 오늘 소개할 문제는 동전의 액면가에서 파생된 이야기를 담고 있다. 요지는 다음과 같다. 서로소인 두 자연수 a, b에 대해 액면가가 a와 b인 두 동전이 있다. 이 두 동전만으로 지불할 수 없는 금액들은 얼마일까? 특히, 그런 값들의 상한이 존재할까? 한다면 지불 불능 최고 금액은 얼마일까? 위 문제를 확장해 일반적인 n개의 동전에 대해 지불 불가능한 최대값을 찾는 문제를 프로베니우스 동전 문제(Frobenius coin problem)라 한다. 현재까지 n이 3이하일때만 해법이 알려져있는데, 우리의 관심은 n=2일때, 즉 두 동전만을 대상으로 한다. 필자가 이 문제를 처음 접한 것은 '재미있는 영재들의 수학퍼즐2'(박부성 지음)이지만, 단순 손계산으로 푸는 꼼수가 통하지 않도록 충남대학교 수학경시대회 .. 2020. 9. 13.
직소 퍼즐, 테두리 vs 내부 일반적인 직사각형 모양의 직소퍼즐 판을 생각해보자. 이 때 각 직소퍼즐 조각의 모양을 보아 테두리조각과 내부조각, 이렇게 두 부류로 쉽게 나눌 수 있다. 왜냐하면 내부조각은 모든 변이 올록볼록한 반면 테두리조각은 반드시 평평한 변이 최소 하나 있어야하기 때문이다. 직소퍼즐을 맞출 때 가장 많이 쓰는 전략으로 바로 이렇게 두 부류의 조각으로 나눈 뒤 퍼즐을 맞추는 경우가 많을 것이다. 그림과 같이 12조각짜리 직소퍼즐(4x3)과 120조각짜리 직소퍼즐(12x10)을 살펴보자. 12조각짜리의 경우 내부가 테두리보다 개수가 적다. 한편 120조각짜리의 경우 테두리가 내부보다 개수가 적다. 직소퍼즐의 크기가 점점 커지면서 이 두 부류의 조각들의 개수 차가 뒤바뀔 것이다. 그렇다면 문제. 테두리와 내부 조각의 수.. 2019. 3. 3.
퀴즈쇼 결승 이야기 철수, 영수, 그리고 민수가 퀴즈쇼 결승에 올랐다. 퀴즈쇼 결승은 여러 문제영역으로 구성되며, 각 문제영역마다 1등은 x, 2등은 y, 3등은 z라는 점수를 얻는다. 이때, x, y, z는 서로 다른 양의 정수이다. 철수는 총 20점을 받았고, 영수는 총 10점, 민수는 총 9점을 받았다. 영수가 상식영역에서 1등을 했다면 인물영역에서는 누가 2등을 했을까? Solving Mathematical Problems(by Terence Tao)에서 나온 문제를 약간 수정. 기묘한 문제이다. 주어진 정보가 너무나 부족한 상황에서 문제를 풀어야한다. x, y, z만 대입해도 수백가지 상황이 가능할 것 같지만 실제로는 오직 한가지 경우만이 가능하다. 주먹구구식으로 대입하여 답을 찾아낼 수도 있겠지만 정수적 특성을 .. 2017. 7. 23.
2의 29승 주의! 계산기 금지2의 29승은 아홉자리 숫자로, 서로다른 9개의 숫자로 이루어져있다고 한다. 0~9중 쓰이지 않은 숫자는 무엇일까? Peter Winkler의 Mathematical Mind-Bender에서 가지고 왔습니다.(원출처 : E. Berlekamp, J.P. Buhler(1990-2007). "Puzzle Column." Emissary) 풀이2^29 = 536870912 이므로 답은 4.계산기 없이 이 퍼즐을 푸는 방법은 바로 9배수 판정법 원리에 있다. 9배수 판정법:각 자리의 숫자를 더한 수가 9배수라면 원래 수도 9배수이다.예시) 3456의 각 자리 숫자를 더하면 3+4+5+6=18, 9배수이다. 실제로 3456=9×384이다. 퍼즐을 풀기 위해서는 결과를 조금 확장해야한다.정리각 자.. 2016. 8. 28.
합과 곱이 같을 때 어떤 두 양의 정수의 합과 곱이 같았다고 한다. 이때 두 정수는 무엇무엇일까? 간단한 이 문제의 답은 모두 2라는 것이다.(2+2=4=2×2)여기에서 문제. 1)다음 방정식의 해를 구하라. 단 모두 양의 정수여야 한다.(a)(b) 2) 일반적으로 이런 일이 항상 일어날까? 즉, 합과 곱이 같은 어떤 k개의 양의 정수들이 항상 존재할까? 모든 k에 대하여 항상 양의 정수 해가 존재하는가? 풀이1)3+2+1=3×2×14+2+1+1=4×2×1×1 2)그렇다. 항상 존재한다.우선 미지수가 많은 것은 별로 좋지 않으니 앞의 두 미지수를 제외하고 모두 1이라고 생각하자. 그리고 편하게 x_1과 x_2를 각각 x와 y라고 하자. 그러면,-> -> 고로 엄청 간단히 x-1=k-1, y-1=1로 두면 x=k, y=2라는.. 2016. 7. 3.
2014에서 2015로 다시 한 해가 왔다. 다사다난했던 지난 해를 보내고 다가오는 이번 해는 조금 더 평화롭기를 바라며 새로운 연도 퍼즐을 만들어보았다. 2014는 어떤 세 개의 자연수 L. M. N에 대해서 L×M+N으로 표현할 수 있다. 이 때 덧셈과 곱셈의 순서를 바꾸면(L+M×N) 2014였던 식의 값이 2015가 된다고 한다. 그렇다면 세 자연수 L, M, N은 무엇무엇일까? 해답 L+MN=2015- ) LM+N=2014 -------------------- L+MN-LM-N=1 2015식에서 2014식을 빼면 L+MN-LM-N=1을 얻고, 좌변을 인수분해하면L+MN-LM-N=MN-LM+L-N=M(N-L)-(N-L)=(M-1)(N-L) 따라서 (M-1)(N-L)=1이다. 그런데 L, M, N이 모두 자연수이므로 M-.. 2015. 1. 1.

티스토리툴바