yeongminb의 PS 블로그

학원에서 수업시간에 딴짓$($?$)$을 하다 학원 벽에 '주어진 삼각형을 유한개의 오목사각형으로 채울 수 있을까?'라는 문장이 무려 '낙서'로 써져있는 것을 봤다. 못 채울 것이라는 생각을 가지고 몇 번 그림을 그려보니 정말 채워지지 않았다. '오 이거 증명해봐야겠다!'라는 충동을 느끼고 학원에서 증명해보았다. 생각보다 잘 증명한 것 같아서 여기에 남겨보았다.   주요 아이디어는 삼각형에만 국한하지 않고 일반적인 볼록다각형에 대해서 채울 수 있는지를 확인하는 것이었다. 삼각형은 항상 볼록하므로 일반적인 볼록다각형에 대해서 불가능하다는 것을 증명하는 것으로 충분하다. 그래서 오목사각형으로 이루어진 도형이 오목할 수 밖에 없다는 것을 증명하였다.  Proposition 1) 임의의 오목다각형에 오목사각형을 ..

경기과학고등학교 수학 브릿지 프로그램으로 수리창의문제해결 프로젝트라는 것을 하길래 문제를 풀어보았다. 1차 문제로 2개가 있었는데 하나는 사고력$(?)$을 요하는 증명 문제였고 나머지 하나는 경우의 수를 세는 기하문제였다. 이 기간동안 몸이 좀 아파서 집에만 있었는데 친구들 풀이 읽고 문제 풀고 하는게 재미있어서 이것만 했었다 ㅎㅎ  P1.  이 문제에는 어떤 한 열쇠 구멍을 돌릴 때, 그 열쇠 구명과 같은 열, 같은 행에 있는 모든 열쇠 구멍도 똑같이 돌아가지는 이상한 금고가 나온다. 이 금고에서 모든 구멍이 바닥과 수평인 방향의 모양으로 바꾸어 금고를 열 수 있는지 증명하는 문제이다.    처음에 친구들이 불가능하다고 증명을 해놨었는데 친구들의 풀이를 다 읽어보니까 공통적인 오류가 보였다. 그래서 열..

KMO 2차에 수열 관련해서 수학적 귀납법으로 증명하는 문제가 많이 보이는 것 같아서 가장 대표적인 수열인 피보나치 수열에 대해 정리해보려고 한다. PS에서도 자주 나오니까 도움이 될 것 같다.   2023 중캠 2차 3번 (AOPS링크) Math Message Boards FAQ & Community Help | AoPSSomething appears to not have loaded correctly.artofproblemsolving.com  피보나치 수열 관련된 문제로 이런 문제가 있는데, $a_{n} = 4{F_{2n-1}}^2 + {F_{2n}}^2$임을 증명하는 (더러운)문제이다. (솔직히 사람이 이걸 어떻게 생각하는지 모르겠다)  정의피보나치 수열은 자연수 $n$에 대해 아래와 같이 정의된..

$FTC$는 Fundamental Theorem of Calculus(미적분학의 기본 정리)로 미적분을 배운다면 알 수밖에 없는 가장 기본적인 정리이다. 나중에 증명과정이 필요할 수도 있기 때문에 증명과정을 정리해보겠다. $F.T.C.\space1)$ 구간 $[a,b]$에서 연속인 $f(x)$와 $F(x) = \int_{a}^{x} f(t)dt$ 에 대해 다음이 성립한다. $$F^{\prime}(x) = f(x)\space\space (x\in [a,b]) $$ p.f) $$F^{\prime}(x)=\lim_{h→0}\frac{F(x+h)−F(x)}{h}$$$$=\lim_{h→0}\frac{\int_{a}^{x+h}f(t)dt-\int_{a}^{x}f(t)dt}{h}$$$$=\lim_{h→0}\frac{..

이항게수와 관련된 PS를 하다가 범위가 큰 $n$과 범위가 큰 $r$에 대해서 ${n \choose r}$의 일의 자리 수를 구해야하는 일이 생겼다. 일반적인 콤비네이션 계산($O(n)$)을 하고 일의 자리수를 구하면 시간초과가 나서 다른 방법이 필요했다. 이 포스팅에서는 이와 관련된 내용을 적어보려고 한다.1. 조합을 계산하는 일반적인 방법 가장 쉬운 방법으로는 정의식대로 $n!$, $(n-r)!$, $r!$을 모두 계산해주고 연산해주는 것이다. 하지만 $n$과 $r$이 조금만 커져도 계산 시간이 오래걸리고 PS에서는 정수형 범위나 심지어는 long long 범위까지 넘어갈 수 있기 때문에 좋지 않은 방법이다.int factorial(int n){ int output = 1; for(int ..

오늘은 크게 어렵진 않지만 그래도 생각해볼 가치가 있는 문제를 가져와보았다. 이 문제는 quant라는 곳에서 인터뷰 문제로 나온 적이 있다고 한다. One hundred people are in line to board a plane which has exactly 100 seats. Each passenger has a ticket assigning them to a specific seat, and the passengers board one at a time. The first person to board is drunk, picks a random seat, and sits in it. The remaining passengers board; if they find their assigned se..

$n^2$개의 정삼각형으로 이루어진 정삼각형 격자에서 정삼각형의 개수는 어떻게 셀까? 이 포스팅에서는 이에 대한 일반화를 해보려고 한다.  먼저 이러한 문제는 점화식으로 접근하는 것이 쉬울 것 같다. 먼저 사용할 점화식을 정의해주자.$a(n,k) :=$ |한 변의 길이가 $n$인 정삼각형 격자에서 한 변의 길이가 $k$인 정삼각형의 개수| 자명하게 $a(n,1) = n^2, a(n,n) = 1$이다. 이제 $a(n,k)$에 대해서 생각해보자. $a(n,k)$을 계산할 때 위 그림에서도 볼 수 있듯이 $a(n-1,k)$에 새로 추가되는 정삼각형들을 더해주면 된다. 그럼 새로 추가되는 정삼각형의 개수를 구해보자. 1) 큰 정삼각형과 변이 평행한 정삼각형이 경우는 구하는 정삼각형은 보라색 정삼각형이므로, $n..

아마 대부분의 사람들이 픽의 정리를 들어본 적이 없을 것이다. 우리나라 교과과정에도 없고 KMO에서도 전혀 나오지 않는 내용이기 때문이다. 최근에 학원에서 이 정리에 대해 짧게 배운 적이 있다. 학원에서 들었을 때 꽤 흥미롭고 재미있어 보여서 추가로 찾아보았다. 여기서는 그런 내용들을 정리할 것이다. 또 이와 관련된 문제를 만들었는데, 그것도 풀어볼 것이다.픽의 정리 꼭짓점이 격자점인 다각형에서 다각형의 내부에 있는 격자점의 수를 I 라고 하고, 다각형의 선분 위에 있는 격자점의 개수를 B라 할 때, 다각형의 넓이는                                                                        S = I + B/2 -1로 나타낼 수 있다.  이것이 무슨 의..

몬즈의 정리(Monge's Theorem)는 KMO 2차에 자주 나오는 정리로 근축에 대해 배울 때 꼭 배워야히는 정리 중 하나이다. 여기서는 몬즈의 정리와 이와 관련된 재미있는 문제 몇 개를 풀어볼 것이다.몬즈의 정리 : 세 원 A,B,C가 두 점에서 서로 교차할 때, 세 공통현은 한 점에서 만난다. ( 세 원의 근축들은 공점선이다.) 참고하면 좋은  사이트 : https://en.wikipedia.org/wiki/Power_center_(geometry) Power center (geometry) - WikipediaFrom Wikipedia, the free encyclopedia For 3 circles, the intersection of the radical axes of each pair D..

아마 KMO를 공부했던 사람이라면 페르마 포인트(Fermat Point)나 스타이너 포인트(Steiner Point)에 대해 들어본 적이 있을 것이다. 이들 모두 주어진 임의의 점들에 대한 기하 중앙값(Geometric median)과 관련이 있다. 이 글에서는 이들의 증명과 가중치가 주어질 경우에 대해서는 어떻게 하는지에 대한 내용을 정리하려고 한다. 아직 일반적인 증명을 할 정도까지의 수준은 아니기 때문에 삼각형과 사각형에 대해서 다룰 것이다.  기하 중앙값(Geometric median)의 정의 : 유클리드 평면에서 주어진 샘플 점들에 대해, 각각의 점들까지의 거리의 합이 최소가 되도록 하는 점 출처 : https://en.wikipedia.org/wiki/Geometric_median Geomet..