소파 이동하기 문제 Moving sofa problem

두세 명의 사람이 협력하여 좁은 복도를 지나 소파를 통과시키는 일을 본인도 해 본 경험이 있다. 이에 영감을 받은 문제 같은데, 폭이 1이고 직각으로 꺾인 2차원 경계선을 넘지 않고 지나는 최대 넓이의 평면도형을 찾는 문제를 Moving sofa problem이라고 한다. 위키피디아의 항목에 있는 애니메이션을 보면 이해가 빠를 듯 하다.
hammersley_sofa_animated
이 문제는 아직 미해결로서, 위 애니메이션에 나오는 모양은 “Hammersley 소파”라고 이름이 붙은 모양이다.

그런데 오늘 John Baez 선생의 구글플러스[1]를 보니, 이 문제를 약간 변형하여 한쪽 코너가 아니라 두 번 꺾이는 코너를 통과하는 “ambidextrous sofa”를 찾는 문제에서 현재 알려진 solution을 improve한 새로운 해법이 제시되었다 한다.

Dan Romik이라는 수학자가 자신의 홈페이지[2]에 이와 관련된 이야기를 올려 놓았는데, 아래 애니메이션을 보는 것이 이해가 빠를 것이다.
ambidextrous_sofa

위 도형은 6차이하의 18개의 각각 분리된 식으로 정의가능하고 그 넓이는 다음과 같다. preprint를 공개[3]하고 있으니 관심 있으면 읽기 바란다.

\sqrt[3]{3+2\sqrt{2}}+\sqrt[3]{3-2\sqrt{2}}-1+\arctan \left[\frac{1}{2}\left( \sqrt[3]{\sqrt{2}+1}-\sqrt[3]{\sqrt{2}-1}\right)\right] \approx 1.644955

Mathematics Genealogy Project를 찾아보니[4] Romik이라는 수학자는 이스라엘 출신인 것 같다. 스승의 스승의 스승의 스승이 Baez선생의 스승과 겹친다-_-

쓸데없이 오묘하게 생긴게-_- 통로를 쏙쏙 지나가긴 하는데, 저런 모양의 소파를 진짜 팔면 재미있을 듯-_-

 


[1] https://plus.google.com/u/0/117663015413546257905/posts/WxRker8FVTw
[2] https://www.math.ucdavis.edu/~romik/movingsofa/
[3] D. Romik. Differential equations and exact solutions in the moving sofa problem. Preprint, 2016. (pdf)
[4] https://www.genealogy.math.ndsu.nodak.edu/id.php?id=103099

Advertisements

2017학년도 가톨릭대학교 논술 문제 중

2017학년도 가톨릭대학교 논술 문제 중에 divisor function에 대한 문제가 나왔다고 한다. 대략 다음과 같은 형태였다고 한다.

d(n)은 n의 약수의 개수이다. (단, n은 자연수)

\displaystyle a_n = \frac{1}{n}\sum_{k=1}^{n}d(k) 이라 정의하자.

[논제 1]
a_M = 3을 만족하는 M의 값을 구하고, n > M일 때 a_n >3인 사실을 설명하시오.

숫자 맞추기 수능만 열라게 파는 고교생들의 상당수는 정수론 문제를 풀 수 없을 것이라 생각하기 때문에, 상당수의 학생이 당황하지 않았을까 생각한다. ㅋㅋㅋ

Apostol 책[1;p57]에는 일전에 소개한 hyperbola method[2]를 이용하여, Divisor summatory function의 asymptotic size가 x log x임을 보이는 부분이 있다. 즉,

\displaystyle \sum_{n \le x} d(n) = x \log x + (2\gamma -1)x + O(\sqrt{x})

여기서 \gammaEuler–Mascheroni constant이다.

참고로 마지막의 O(\sqrt{x})을 improve하는 문제를 Dirichlet’s divisor problem이라고 하는데, 에러텀을 O(x^{\theta+\epsilon})이라고 둘 때, 모든 \epsilon >0에 대해 참인 가장 작은 \theta의 값을 찾는 문제는 아직 해결되지 않았다고 한다. 위키피디아의 Divisor summatory function 항목에 따르면, 현재까지 가장 좋은 결과[3]는 2003년에 나온 \inf \theta \le 131/416 이라고 한다.

여하간 이 사실을 이용하면 비교적 자명한 결과이긴 한데, 닭 잡는 데 소 잡는 칼을 쓰는 것 같아서 좀 그렇다. ㅋㅋㅋ 좀 더 고교생스러운 방법이 있을지 좀 생각해 봤다.

 


일단 노가다로-_- 정답이 M=15 임을 알 수 있다. M=18까지 계산하면 3M과 \sum d(n)의 차가 4 이상 벌어진다. 18 이후의 자연수를 세 개 단위로 그룹을 만들어보자. 각 그룹에는 반드시 2의 배수와 3의 배수가 포함된다.

그룹 안에서 2의 배수와 3의 배수가 다를 경우
2X의 경우 1, 2, X, 2X 로 약수가 적어도 네 개 이상, 3X의 경우도 1, 3, X, 3X으로 그룹 전체 약수의 총 개수는 (남은 한 수가 소수라고 해도) 적어도 2+4+4=10 이상이 된다. 따라서 3M과 \sum d(n)의 차는 더 벌어진다.

그룹 안에서 2의 배수와 3의 배수가 겹칠 경우
6X의 경우 1, 2, 3, 6, X, 2X, 3X, 6X로 여덟 개가 나온다. 따라서 약수의 총 개수는 2+2+8=12 이상이 되므로 3M과 \sum d(n)의 차는 더 벌어진다.

따라서 3M과 \sum d(n)의 차가 4 이상 벌어지면, 각 그룹안에 소수가 두 개 들어 있는 경우가 나타나도 역전되지 않는다.

 


[1] Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, MR0434929, ISBN 978-0-387-90163-3
[2] 내 백과사전 Dirichlet’s hyperbola method 2010년 10월 27일
[3] Huxley, M. N. (2003). “Exponential sums and lattice points III”. Proc. London Math. Soc. 87 (3): 591–609. doi:10.1112/S0024611503014485

내접 정사각형 문제 Inscribed square problem

임의의 평면 Jordan curve (즉, plane simple closed curve)가 주어질 때, 정사각형의 네 꼭지점이 되는 curve 위의 네 점을 항상 찾을 수 있는가? 하는 문제가 있다고 한다. Inscribed square problem인데, 아직까지 미해결이라고 한다.

여기까지는 뭐 산처럼 많은 미해결들 중의 하나인데, 조건을 정사각형에서 직사각형으로 조금 완화하면 항상 가능하다. 더구나 증명도 무척 간단하다!!! 이 문제를 쌈빡하게 증명을 할 뿐만 아니라, 수학을 잘 모르는 사람까지도 증명을 이해할 수 있도록 만든 매우매우매우 훌륭한 영상을 발견하였으므로 포스팅해본다. ㅋㅋㅋ

매우 친절하게도 자막까지 있으니, 자막을 켜면 리스닝이 안 돼도 대충 볼 수 있다. 이야 친절 그 자체다 ㅋㅋㅋㅋ

수학을 알지만 영상은 보기 귀찮은 사람을 위해 요약을 하면 다음과 같다.

 


Jordan curve위의 점과 interval [0,1) 과의 자연스러운 continuous mapping을 생각할 수 있고, [0,1)x[0,1)과 torus와의 canonical mapping도 당연히 있으므로, Jordan curve위의 임의의 ordered pair는 torus위의 한 점과 자연스럽게 대응된다. 뭐 이건 상식. ㅋ

한편 [0,1)x[0,1)에서 unordered pair는 [0,1)x[0,1)을 반으로 접어 직각이등변삼각형으로 만들면 되는데, 이 때 identification이 되는 (즉, 꿰메는) 두 boundary를 붙이면 Möbius strip이 된다. 여기서 주목할 점은 대각선 (x,x)에 있는 점은 Möbius strip의 boundary라는 부분이다.

Jordan curve위의 직사각형을 이루는 네 점을 찾는 문제는, Jordan curve위의 두 점을 이어 만든 선분들 중 중점이 일치하고 길이가 같은 두 선분을 찾는 문제와 같다. 주어진 Jordan curve 위의 가능한 모든 선분의 중점들에서 각각 위쪽 방향으로 선분의 길이와 같은 z좌표를 넣어, Jordan curve를 boundary로 하는 곡면을 생각할 수 있다. 이 곡면이 homeomorphic하게 구면과 같은 지, 아니면 자기자신과 겹치는 점이 있는지를 통해 직사각형의 존재여부를 확인할 수 있다.

모든 Jordan curve의 선분들은 unordered pair이므로 Möbius strip위의 모든 점과 자연스러운 bijection이 생기는데, 이 map에서 unordered pair {x,x}는 곡면의 boundary이자 동시에 Möbius strip의 boundary의 한 점이 되므로 이 문제는 Möbius strip의 boundary를 Jordan curve위에 꿰메는 문제가 된다. 이것은 자신이 겹치지 않으면 3차원에서 불가능하므로 항상 존재한다! ㅋㅋ

 


2016.12.12
위 영상을 만든 3Blue1Brown[1]에서 리만 제타 함수를 시각적으로 설명하는 재미있는 영상을 만들었는데, 이것도 재미있으니 함 보시라. 타오 선생도 소개[2]하고 있다.

 


[1] http://www.3blue1brown.com/
[2] https://plus.google.com/u/0/+TerenceTao27/posts/gXiteLyAu7A

자전거 바퀴자국 퀴즈

간만에 FUTILITY CLOSET 블로그[1]를 보니 재미있는 퀴즈가 올라와 있다.
2016-05-10-left-or-right-1
그림과 같은 자전거가 지나간 바퀴자국이 있다. 이 자전거는 왼쪽에서 오른쪽으로 이동했을까? 아니면 오른쪽에서 왼쪽으로 이동했을까?

정답은 [1]에 있음. ㅎ

 


[1] Left or Right? in FUTILITY CLOSET

시겔의 역설 Siegel’s Paradox

배리 섀흐터 등 저/이은주 역, “퀀트 30년의 기록“, 효형출판, 2008

p164-166

쿠퍼네프와 같은 옵션거래 회사는 면접을 볼 때 상당히 까다로운 질문을 많이 하기로 유명했다. 나도 예외는 아니었다. 그러나 나는 오히려 면접관이 내 놓은 문제에 대해 막힘없이 설명을 해새서 그의 기를 단단히 꺾어놓았다. 마침 운 좋게도 평소에 많이 생각하고 있던 분야에 관한 질문을 해 온 것이다. 금융계에 종사하는 사람들이 골치아파하는 문제는 복잡한 확률 문제 따위가 아니었다. 이들을 애먹이는 것은 다음과 같은 유형의 문제이다.

달러 대 마르크의 환율이 1.00이라고 하자. 이것이 동일한 확률로 1.50 혹은 0.50이 될 수 있다고 하자. 공정하격은 1.00달러다. 이제 이를 뒤집어 마르크대 달러의 관점에서 바라보자. 기대가격이 1.33마르크이기 때문에 이 비율은 0.67 혹은 2.00이 될 수 있다. 그래서 공정가격은 0.75가 된다. 여기에 대해 어떻게 생각하는가?

그때는 잘 몰랐지만 이 문제는 금융 실무자들은 물론이고 학자들 사이에서도 골치 아픈 난제로 통하고 있었다. 오죽하면 이를 두고 ‘시겔의 역설‘이라 했겠는가? 유능한 실무자와 학자 몇몇은 달러 투자자가 외국환에 투자를 할 때 얻게 되는 표면자유곡률ostensible free curvature 획득에 관한 내용을 주제로 한 논문을 쓰기도 했다. 면접관은 이런 골치 아픈 문제를 내게 던진 것이다. 그러나 나는 ‘역설’도 뭣도 존재하지 않거나, 최소한 긍정적인 기대가치의 거래 기회는 없다고 본다고 말했다. 달러 대 마르크와 마르크 대 달러는 각기 다른 측정 단위로 가격이 결정된다. 구매력 차익거래purchasing power arbitrage의 여지가 없다면 여기에는 장점이나 역설같은 것이 존재하지 않는다. 동일한 통화로 거래되는 두 가지 금융상품이 있는데 하나는 가격 X에, 또 하나는 가격 1/X에 거래되는 것과 같은 상황이라고 보면 된다. 만약 이런 상황이라면 어디서든 프리 감마free gamma 상태가 된다. 감마란 기초자산의 가격 변화에 따라 델타가 변하는 정도를 나타내는 지표이며, 다른 말로 하자면 금융자산가격 1단위의 변화에 대한 델타의 변동량을 의미한다. 하지만 외환거래의 대상이 된 통화의 환율은 이러한 패러다임에 적합하지 않다.

이때가 1980년대였다는 점을 기억하기 바란다. 당시는 콴토라는 말이 등장하기도 전이었고, 당연히 이런 말을 사용하는 사람도 없었다. 콴토란 수량조정 옵션quantity-adjusting option의 준말로, A통화로 표시된 기초자산이 B통화로 표시되는 결제통화에 대해 고정환율로 현금결제가 이루어지는 파생상품을 말한다. 그런데도 내가 이른바 ‘역설’이라 불리는 이러한 문제에 관심을 가졌던 이유는 젠센 부등식이 고정수익증권 관련 논문에서 얼마나 뭇매를 맞았는지 잘 알고 있었기 때문이다. 특히, 금리와 채권가격에 대한 기대연산자expectation operator를 함부로 상호교환하는 것에도 주목했다. 이러한 유형의 오차는 환율표본에서 발생하는 오차만큼의 주목을 받지는 못했지만, 나는 이 두 가지 사이의 연관성이 충분히 있다고 보았기 때문에 그런 대답을 한 것이다. 그들은 이러한 문제들에 대해 자신감있게 설명하는 모습을 보고 나를 채용하기로 결정한 것 같다. 그렇게 나는 당시 금융시장에서 가장 까다롭기로 정평이 난 회사의 옵션연구 담당 이사가 되었다.

비교적 단순하면서도 원인을 짐작하기 어려운 이 패러독스에 대해 잠시 검색을 해 봤는데, 위키피디아 항목에서는 역수의 기대값과 기대값의 역수가 다르기 때문이라고 설명되어 있다. 1/x가 아래로 볼록한 함수라서 젠센 부등식 때문인 듯.

구글 검색으로 조재호 서울대학교 경영대학 교수의 Seoul Business Letter 2012년판에 기고된 글을 발견할 수 있는데, 환율 차익거래로 환율의 방향에 상관없이 항상 매매이익을 볼 수 있는 재미있는 상황에 대한 설명이 읽을만하다.

테렌스 타오 아들의 수학문제

타오 선생의 구글 플러스[1]를 보니 아들래미 학교에서 아들 수준에는 놀라울 정도로 어려운 수학 문제가 나왔다고 한다. 해커뉴스[2]에서도 화제가 되고 있다.

Three farmers were selling chickens at the local market. One farmer had 10 chickens to sell, another had 16 chickens to sell, and the last had 26 chickens to sell. In order not to compete with each other, they agreed to all sell their chickens at the same price. But by lunchtime, they decided that sales were not going so well, and they all decided to lower their prices to the same lower price point. By the end of the day, they had sold all their chickens. It turned out that they all collected the same amount of money, $35, from the day’s chicken sales. What was the price of the chickens before lunchtime and after lunchtime?

본인도 타오처럼 문제가 잘못된 게 아닌지 한참 생각했다. 아니면 내 독해가 잘못됐던가… -_- 켁. 댓글을 쭉 읽어보니 잘못된 문제는 아닌 것 같다.

이걸 보면 아들의 나이가 별로 안 될 듯 한데, 프로그래밍을 가르치고 있는 모양[3]이니 아들도 엄청 똑똑한 듯-_-

 


[1] https://plus.google.com/114134834346472219368/posts/CR1ZoNe9ojQ
[2] https://news.ycombinator.com/item?id=8486324
[3] 내 백과사전 Untrusted – 사용자 자바스크립트 게임 2014년 4월 14일

골드만 삭스 퀀트 면접 문제 중

브레인 티저가 올라오는 블로그 CSE Blog를 가끔 보는데, 이 블로그에 따르면 골드만 삭스 퀀트 면접문제에 이런 질문이 나왔다고 한다.

Value of Pi – Estimation using Dice in CSE Blog

주사위 하나로 원주율을 추정하시오.
Estimate the value of pi using a dice.

아무래도 뷔퐁의 바늘 문제 비스무리하게 풀지 않을까 싶다. 근데 바닥에 선 그어서 던져 푸는 거 말고 쌈빡한 아이디어 없을까?

 


2014.4.8
주사위 숫자와 계산만으로 기대값이 원주율에 수렴하는 방법에 대해 곰곰 생각해봤는데, series를 이용하면 될 것 같다. 설명의 편의상 라이프니츠 공식을 쓰고 있긴 하지만, 더 빠른 수렴 공식에도 적용가능하다.

1이 나올 때까지 주사위를 던진 회수를 확률변수 X라고 하면, 확률분포는 P(X=n)= \left( \frac{5}{6} \right)^{n-1} \cdot \frac{1}{6} 이 된다. 그래서 이를 반복 시행하여 \frac{24}{2X-1}\left( -\frac{6}{5}\right)^{X-1} 의 값을 반복 계산한다. 이 시행의 평균값은 다음과 같이 원주율에 수렴하게 된다.

\displaystyle \begin{gathered} E\left(\frac{24}{2X-1}\left( -\frac{6}{5}\right)^{X-1} \right) \hfill \\ \qquad = \sum_{n=1}^{\infty} \frac{24}{2n-1}\left( -\frac{6}{5}\right)^{n-1} \left( \frac{5}{6} \right)^{n-1} \cdot \frac{1}{6} \\ \qquad = 4 \sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2n-1} \hfill \\ \qquad = \pi \hfill \end{gathered}

뭐 그냥 원주율이 되도록 앞에 식을 끼워 넣은 것에 지나지 않지만… -_-

본인이 생각한 방법이 하나 더 있다. 주사위를 여섯 번 던졌을 때 나온 숫자를 a, b, c, d, e, f라 하면 다음 식이 성립하는 사건을 X라 하자.

\displaystyle \left( \frac{a-1}{6}+\frac{b-1}{6^2}+\frac{c-1}{6^3}\right)^2 + \left( \frac{d-1}{6}+\frac{e-1}{6^2}+\frac{f-1}{6^3}\right)^2 <1

전체사건에서 X가 일어난 비율을 4배하면 원주율에 수렴한다. 왜 그럴까? ㅋㅋ 그 이유는 기하학적으로 위 식이 사실 6진법으로 소수점 이하 세 자리수까지 [0,1]x[0,1] 박스안의 임의의 한 점을 선택해서 단위원 안의 점인지 확인하는 계산이기 때문이다. 따라서 확률은 사분원의 넓이가 된다. 정확도를 높이고 싶으면 자리수를 늘리면 된다.

Vieta jumping

페북의 수학 그룹에서 흥미로운 사실을 알았다. 일단 다음 문제를 보시라.

a, b가 모두 정수일 때, \displaystyle \frac{a^2 + b^2}{ab+1}가 자연수라면 이 수는 제곱수임을 보여라.

꽤 어려우니 흥미있는 사람은 함 풀어보시라. 이리저리 시도해도 잘 안 되는데, Vieta jumping으로 푸는 문제라고 누가 말하는게 아닌가. 과연 위키피디아의 Vieta jumping 항목에 위 문제의 풀이가 나온다.

위키피디아에 따르면 1988년 IMO 6번 문제로 출제되었다는데, 당시 여섯 명의 오스트레일리아 출제위원 아무도 이 문제를 풀 수 없었다고 한다. 또한 오스트레일리아의 정수론 수학자 4명에게 보냈는데도 여섯 시간 동안 아무도 풀 수 없었다고 한다. 그래서 너무 어렵다는 이유로 반려될 뻔한 모양인데, 긴 토론 끝에 결국 마지막 문제로 출제하기로 결정했다고 한다. 이 시험에서 11명의 학생이 완벽한 답안을 제출했다고 하는데, 그 중 한 명은 미래 필즈메달을 수상하게 될 Ngô Bảo Châu였다고 한다. 헐… 그러니까 이 친구는 이 기법을 모르고 푼 거 아닌가! 될 나무는 역시 떡잎부터 다른건가… -_- 참고로 이 아저씨 이름 읽는 법[1]에 대해 일전에 포스팅한 적이 있다. ㅎㅎ

여하간 이 기법에 이런 이름이 들어간 이유는 중고교생들이 흔히 ‘근과 계수와의 관계’라는 이름으로 알고 있는 Vieta’s formulas를 이용해 한 근에서 다른 근으로 폴짝 뛰어 넘어가는 느낌을 줘서 그런 것 같다. (공상력을 발휘해 보자! ㅋ)

이 문제가 히트를 친 탓인지 이후에 이런 기법을 변형해서 많이 문제가 나온 모양인데, 너무 많이 나온 탓인지 몰라도 싫어하는 사람이 꽤 많은 듯.[2]

크게 복잡한 기법은 아닌데, 비교적 근래 개발된 테크닉이라 하니 좀 신기하다. ㅎㅎ

근데 실제로 저런 복잡한 조건을 만족하는 자연수가 있긴 있을까? sage로 1000×1000 안에서 돌려봤는데, 많지는 않지만 몇 개 나온다.

 


[1] 내 백과사전 Ngô Bảo Châu를 읽는 법 2011년 5월 9일
[2] Why does everyone hate Vieta Jumping? in Art of Problem Solving