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

타오 선생의 구글 플러스[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를 가끔 보는데, 이 블로그에 따르면 골드만 삭스 퀀트 면접문제에 이런 질문이 나왔다고 한다.[1]

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

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

 


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

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] 박스안의 임의의 한 점을 선택해서 단위원 안의 점인지 확인하는 계산이기 때문이다. 따라서 확률은 사분원의 넓이가 된다. 정확도를 높이고 싶으면 자리수를 늘리면 된다.

 


[1] Value of Pi – Estimation using Dice in CSE Blog
[2] 내 백과사전 원주율의 라이프니츠 공식을 수론으로 증명 2012년 7월 5일

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 안에서 돌려봤는데, 많지는 않지만 몇 개 나온다.

.


2019.2.10
전설적인 IMO 문제 (udaqueness.blog)

 


[1] 내 백과사전 Ngô Bảo Châu를 읽는 법 2011년 5월 9일
[2] Why does everyone hate Vieta Jumping? (artofproblemsolving.com)

IBM Research – Ponder This 2014년 2월

출처

만약 정육각형의 한 변에 한 정삼각형을 (다각형의 모든 변은 단위길이) 공통 변으로 붙일 경우, 다섯 개 꼭지점과 다섯 개의 변, 하나의 면을 가지는 오각형을 얻는다.
만약 밑면이 정삼각형 프리즘인 4차원 피라미드와 밑면이 사면체인 4차원 피라미드를 (마찬가지로 모든 변은 단위길이) 공통 사면체로 붙일 경우, 꼭짓점, 변, 면, 공간의 개수는 몇 개가 될까?

원문에 right triangular prism이라고 돼 있는데, 이걸 직각삼각형 프리즘이라고 생각하면 모든 변의 길이가 같지 않게 되고 정사면체 셀도 생기지 않는다. 문맥상 정삼각형 프리즘의 오타가 아닐까 생각한다.

 


간만에 IBM 홈페이지에 이름 올려볼까 싶어서 열라게 계산하고 있는데, 좀 귀찮다-_-

일단 xyz공간에서 정사면체의 네 꼭지점
A(0,0,0,0), B(6,0,0,0), C(3,3\sqrt{3},0,0), D(3,\sqrt{3},2\sqrt{6},0)이라 잡으면, 이 모든 점과 거리가 6인 점을 찾는데, 이건 간단하게 계산 된다.
E(3,\sqrt{3},\frac{\sqrt{6}}{2},\frac{3\sqrt{10}}{2})
그 다음 4차원 피라미드를 이루는 사면체가 이루는 각을 계산하면
xyz공간에 있는 사면체의 normal vector는 (0,0,0,1)이고, 사면체 ABDE의 normal vector는 (0,4\sqrt{2},-2,-\frac{2\sqrt{3}}{\sqrt{5}})이므로 두 벡터가 이루는 예각의 코사인은 \frac{1}{4}가 나온다.

다음으로 프리즘의 여섯 꼭지점의 좌표를 (0,0,0,0), (6,0,0,0), (3,3\sqrt{3},0,0), (0,0,6,0), (6,0,6,0), (3,3\sqrt{3},6,0)이라 두면, 여섯 꼭지점과 거리가 같은 점은 (3,\sqrt{3},3,\sqrt{15})이고,

여기까지 계산했다가 귀찮아서 패스…-_-

ニセコイ 4화의 수학문제

TV 애니메이션 ニセコイ 4화를 보다보니 공부회를 하는 장면에서 슬쩍 수학문제가 등장한다.
nisekoi
뭐 내용 자체는 좀 유치하게 재미있는 내용이라, 어지간한 덕력이 없으면 못 볼 내용이다. ㅋㅋㅋ

여하간 위 문제를 어디서 많이 본 문제라 생각하던 차에 기억을 더듬으니, 2012년 동경대 이과 전기과정 입시문제 4번 문제가 아닌가!

nを2以上の整数とする。自然数(1以上の整数)のn乗になる数をn乗数と呼ぶことにする。以下の問いに答えよ。
(1)連続する2個の自然数の積はn乗数でないことを示せ。
(2)連続するn個の自然数の積はn乗数でないことを示せ。
n을 2이상의 정수라 하자. 자연수(1이상인 정수)의 n승이 되는 수를 n승수라 부르기로 하자. 다음 질문에 답하여라.
(1) 연속하는 2개의 자연수의 곱은 n승수가 될 수 없음을 보여라.
(2) 연속하는 n개의 자연수의 곱은 n승수가 될 수 없음을 보여라.

애니메이션 히로인인 키리사키는 아주 쉽게 풀던데, 과연…? 뭐 재미삼아 풀어보시라. ㅋㅋ

뒤쪽에 있는 문제도 어디서 본 기억이 나는데, 어디서 본 건지 기억이 안 난다… 좀 찾아봐야겠다.

 


2014.2.9
심심해서 문제 하나 더 투척
2013 동경대 이과 전기과정 5번문제
次の命題Pを証明したい。
命題P : 次の条件(a)、(b)をともに満たす自然数(1以上の整数)Aが存在する。
(a)Aは連続する3つの自然数の積である。
(b)Aは10進法で表したとき、1が連続して99回以上現れるところがある。
以下の問いに答えよ。
(1)yを自然数とする。このとき不等式
x^3 +3yx^2 < (x+y-1)(x+y)(x+y+1) < x^3 +(3y+1)x^2
が成り立つような正の実数xの範囲を求めよ。
(2)命題Pを証明せよ。
다음 명제P를 증명하고자 한다.
명제P : 다음 조건 (a), (b)를 모두 만족하는 자연수(1이상인 정수) A가 존재한다.
(a) A는 연속하는 세 자연수의 곱이다.
(b) A는 10진법으로 나타낼 때, 1이 연속해서 99번 이상 나타나는 곳이 있다.
다음 질문에 답하여라.
(1) y를 자연수라 하자. 이 때 부등식
x^3 +3yx^2 < (x+y-1)(x+y)(x+y+1) < x^3 +(3y+1)x^2
이 성립하도록 하는 양의 실수 x의 범위를 구하여라.
(2) 명제P를 증명하여라.

 


2014.3.14
찾아보니 뒤쪽 문제도 동경대 기출.
2005 동경대 이과 전기과정 4번문제
3以上9999以下の奇数aで、a^2 -aが10000で割り切れるものをすべて求めよ。
3이상 9999이하의 홀수인 a중에 a^2 -a가 10000으로 나누어 떨어지는 것을 모두 구하시오.

15명의 여학생 문제와 Steiner system의 존재성

15명의 여학생 문제라는게 있다. 이게 뭔고 하니, 여학생 15명이 매일 3명씩 다섯 조를 짜서 7일동안 등교하는데, 모든 학생들이 한 번 같은 조였던 사람과는 두 번 다시 조가 되지 않도록 하라는 문제이다. 정답은 위키피디아 링크에 나와 있으니, 퍼즐 좋아하면 먼저 풀어보시라. ㅎ

이를 일반화하여 이런 질문을 해 볼 수 있다.

n개의 원소로 이루어진 집합이 있다. 모든 r개로 된 부분집합들이 딱 \lambda개만 포함되는 q개로 된 부분집합들의 모임 S를 항상 만들 수 있는가?

그러한 q-subsets collection을 ‘design’이라 부르는 모양인데, 특히 \lambda=1일 때, Steiner system이라 부르는 듯. 위 15명의 여학생 문제는 n=15, q=3, r=2인 경우 Steiner system을 찾는 문제이다.

여하간 Steiner system의 존재성 문제는 combinatorics분야에서 꽤 오래되고 중요한 문제인 모양인데, 이 문제가 Peter Keevash 라는 수학자에 의해 얼마전에 풀렸다는 소문[1]이 있다.

특정한 n에 대해 모든 q, r에서 Steiner system이 존재한다는 것을 증명한 듯. Randomised Algebraic Constructions이라는 새로운 method를 창안한 모양인데 뭐 본인은 뭔지 모른다 ㅋ

역사가 깊은 많은 문제가 그러하듯 문제 자체는 쉽게 이해되는 편인데, 풀이는 어떨지 모르겠다. 본인은 논문을 안 읽어봐서… ㅋㅋㅋ

그나저나 15명의 여학생 문제에서 왜 하필 여학생(schoolgirl)일까? 뭐 모르긴해도 마케팅 포인트로서의 여고생의 장점이 있긴 있다-_-[2]

 


2015.6.21
와이어드 ANSWER TO A 150-YEAR-OLD MATH CONUNDRUM BRINGS MORE MYSTERY DATE OF PUBLICATION: 06.20.15. 7:00 AM

 


[1] Amazing: Peter Keevash Constructed General Steiner Systems and Designs in Combinatorics and more
[2] 내 백과사전 세후리에 ILC를! -유치를 위해서는 여고생으로 가자! 2013년 4월 21일

광저우 헝다 홈페이지의 수학문제

YTN 광저우, 수식으로 홈페이지에 ACL 우승 자신감 표출 2013-11-04 16:03

요런 기사가 있던데, 역시 국내 언론답게 출처가 없어서 확인해봤다. ‘광저우 헝다‘가 축구단 이름인 줄도 모르고 처음에는 광저우 정부 공식 홈페이지에 저 포스터가 나와있는 줄 알고 한참 삽질했다-_- 광저우에 연고지를 두고 있는 축구단이라고 한다. 광저우 헝다의 홈페이지에 다음과 같은 수학문제가 올라와 있다.

http://www.gzevergrandefc.com/
Guangzhou_hungda_homepage

우측은 물론 유명한 오일러 선생의 공식이다. 좌측은 라마누전의 289번 문제이다. 일전에 풀이를 소개한 적이 있다. ㅋㅋ

결국 광저우 헝다의 의도는 3대 0이라는 말씀. 나는 저 점수가 실현돼서 저 포스터가 유명해졌으면 좋겠다. ㅋㅋ 광저우 꼭 3:0으로 이겨라! ㅋ

검색해보니 이 포스트에 관해 무슨 인터뷰 비슷한 기사가 있던데, 북경어로 추정되는 언어라서 못 읽고 있다-_-

텐센트QQ 《体坛周报》之学霸来了! 恒大海报文理新版 2013-11-06 09:36

abelian이 Hausdorff가 될 때

The College Mathematics Journal을 보다가 흥미로운 기사가 있어 소개한다. 지금부터 작성하는 내용은 모두 [1]을 근거로 작성한 것이다. 불충분하다고 생각되면 원본을 보시기 바란다.

 


정상적인 학부 수학교육-_-을 받은 수학과 학생이라면 이미 풀어봤음직한 두 개의 연습문제를 소개한다.

[2, Exercise 3, p. 221] A group G is abelian if and only if \Delta (G) is a normal subgroup of G \times G where \Delta (G) = \{ (g,g) | g \in G \}, the diagonal of G.

[3, Exercise 13, p. 100] A topological space X is Hausdorff if and only if \Delta (X) is closed in X \times X where \Delta (X) = \{ (x,x) | x \in X \}, the diagonal of X.

그렇다. 본인도 따로따로 풀어본 문제인데, 이 두 문제가 관련이 있다고 생각해 본 적이 없었다. 젠장-_- 두 문제를 다음 방법으로 연결해보자.

주어진 group내의 conjugacy class를 이미 알고 있을 터이다. 이게 뭐냐하면, U_h = \{ ghg^{-1} | g \in G\} 로 집합을 정의하면 equivalence class가 된다. 이 각각의 set들이 topology의 basis가 되도록 group에 topology를 준다. 이 topological space를 \mathcal{T}(G)라고 하자. 이 대목에서 topological group을 떠올리는 사람도 적지않을 터인데, 미묘하게 다르다. 그 이야기는 조금 후에 하기로 하자.

여하간 [1]에 다음 정리들의 증명이 소개되어 있는데, 학부수준의 연습문제로 풀어볼만하기에 여기에는 그냥 증명없이 간다. 각자 식후 커피한잔 마시는 여유로 재미삼아 풀어보시기 바란다. 본인도 topology 연습문제를 하도 간만에 풀었더니 굳은 머리에서 자갈소리가 간만에 나는구나 ㅋ

Proposition 1. G is abelian if and only if \mathcal{T}(G) is Hausdorff.

Proposition 2. H \triangleleft G if and only if H is closed in \mathcal{T}(G).

따라서 두 연습문제가 연결된다.

또한 group homomorphism도 continuous map이 될 수 있는데, 정리는 다음과 같다.

Proposition 3. If \phi : G \to \Gamma is a group homomorphism, then for \gamma \in \Gamma, \phi^{-1}(U_{\gamma}) is an open set in \mathcal{T}(G).

마지막으로, 이렇게 topology를 준 group이 항상 topological group이 되는 것은 아니다. topological group의 정의에서 group operation map \mu : G \times G \to G, \mu(g, h) = gh이 continuous 해야 되는데, 안 되는 경우가 있다.

Proposition 4. In S_3, the symmetric group, \mu^{-1}(U_e) is not open in \mathcal{T}(S_3 \times S_3).

우왕 굿.

 


[1] Timothy Kohl, “When Abelian = Hausdorff”, The College Mathematics Journal, Vol. 43, No. 3 (May 2012), pp. 213-215
[2] J. Gallian, Contemporary Abstract Algebra, 4th ed., Houghton Mifflin, Boston, 1998.
[3] James Munkres, Topology, A First Course, Prentice Hall, Upper Saddle River NJ, 1975.