'Others/Olympiad'에 해당되는 글 17건

지뢰찾기(minesweeper) 게임과 수학
지뢰찾기(minesweeper) 게임란 $m \times n$ 크기의 격자에 주어진 숫자를 바탕으로 각 격자에 숨어 있는 지뢰를 모두 찾는 게임이다. 이 때, 각 격자에 주어지는 숫자는 그 격자에 인접한 8개의 격자에 위치한 지뢰의 개수를 나타낸다. 지뢰찾기 게임에도 다양한 수학적 사실이 숨겨져 있는데, 이번 글에서는 그 중 하나를 살펴보도록 하자. 이제 어떤 $m \times n$ 크기의 지뢰찾기 게임이 주어졌다고 하자. 이 게임에서 지뢰가 숨겨져 있는 모든 격자의 지뢰를 없애고, 반대로 지뢰가 숨겨져 있지 않은 모든 격자에 지뢰를 숨기면 새로운 지뢰찾기 게임을 얻게 된다. 이렇게 얻은 게임을 주어진 지뢰찾기 게임의 쌍대(dual)하고 하자. 예를 들어 아래 두 지뢰찾기 게임은 서로 쌍대 관계이다. 위..
Others/Olympiad  |  2017. 10. 25. 03:49
Problems and Solution #039
Problem #039다음 방정식 \[ \lfloor x \lfloor x \lfloor x \lfloor x \rfloor \rfloor \rfloor \rfloor = 2017 \] 을 만족하는 $x$을 모두 구하여라. (단, $\lfloor x \rfloor$는 $x$를 넘지 않는 최대 정수로 정의한다.) 주어진 방정식을 풀기 전에 먼저 방정식 $x \lfloor x \lfloor x \lfloor x \rfloor \rfloor \rfloor = 2017$의 해를 구하도록 하자. 함수 $f(x) = x \lfloor x \lfloor x \lfloor x \rfloor \rfloor \rfloor$를 정의하면 $f(x)$는 $x>0$인 범위에서 증가함수이고 $x
Others/Olympiad  |  2017. 10. 20. 05:22
Problems and Solutions #036
Problem #036어떤 충분히 큰 정수가 $1$부터 $10000$까지의 수 중에서 정확히 두 개의 수를 제외한 모든 수로 나누어떨어진다고 한다. 이때 제외되는 두 개의 수가 연속인 정수라면, 이 두 수는 어떤 수여야 할까? 문제의 조건을 만족하는 충분히 큰 정수를 $N$이라 하고, $N$을 나누지 않는 두 연속인 정수를 각각 $k$, $k+1$이라 하자. 만약 $k \leq 5000$이라면 $N$은 $k$, $k+1$, $2k$로 나누어떨어지게 되기 때문에 문제의 가정에 모순이다. 따라서 $5000 < k < 10000$임을 알 수 있다. 이제 서로소인 두 정수 $m$과 $n$이 존재하여, $k = mn$과 같이 나타낼 수 있다고 가정해 보자. 만약에 $m$과 $n$이 모두 $N$을 나눈다면 $k$ ..
Others/Olympiad  |  2017. 8. 16. 04:00
에르미트 항등식(Hermite's identity)
정리. 에르미트 항등식(Hermite's identity) 임의의 실수 $x \in \R$와 양의 정수 $n \in \N$에 대하여 다음이 성립한다. \[ \lfloor x \rfloor + \left\lfloor x + \frac{1}{n} \right\rfloor + \left\lfloor x + \frac{2}{n} \right\rfloor + \cdots + \left\lfloor x + \frac{n-1}{n} \right\rfloor = \lfloor nx \rfloor \] 증명. 다음과 같이 함수 $f$를 정의한다. \[ f(x) = \lfloor nx \rfloor - \sum_{k=0}^{n-1} \left\lfloor x + \frac{k}{n} \right\rfloor \] 이제 이..
Others/Olympiad  |  2017. 8. 12. 00:49
Problems and Solutions #034
Problem #034 임의의 실수 $\theta_k \in \R$와 양의 정수 $n \in \N$에 대하여 다음을 증명하여라. \[ \prod_{k=1}^{n} \cos^2 \theta_k - \sum_{k=1}^{n} \cos^2 \theta_k \geq 1 - n \] 풀이1. 우선 $a_k = \cos^2 \theta_k$라 하자. 그러면 모든 $1 \leq k \leq n$에 대하여 $0 \leq a_k \leq 1$이 성립한다. 주어진 부등식은 아래 부등식과 동치이다.\[ \prod_{k=1}^{n} a_k \geq \sum_{k=1}^{n} a_k + 1 - n \]이제 위 부등식을 수학적 귀납법을 이용하여 증명해 보자. 먼저 $n=1$인 경우 부등식이 성립한다. 또한\begin{align*..
Others/Olympiad  |  2017. 8. 8. 07:34
에르미트-아다마르 부등식(Hermite-Hadamard inequality)
에르미트-아다마르 부등식(Hermite-Hadamard inequality)이란 볼록함수에 대해 성립하는 부등식 중 하나로써, 볼록함수(convex function) $f:[a,\,b] \to \R$에 대하여 $f$를 구간 $[a,\,b]$에서 적분한 적분값의 평균을 간단히 근사하는 방법을 제공한다. 이번 글에서는 에르미트-아다마르 부등식을 증명하고, 이를 이용한 몇 가지 예제들을 살펴보고자 한다. 정리. 에르미트-아다마르 부등식(Hermite-Hadamard inequality) 볼록함수(convex function) $f:[a,\,b] \to \R$에 대하여 다음의 부등식이 항상 성립한다. \[ f \left( \frac{a+b}{2} \right) \leq \frac{1}{b-a} \int_{a}^..
Others/Olympiad  |  2017. 7. 8. 02:54
Problems and Solutions #033
Problem #033 $a+b+c$, $ab+bc+ca$, $abc$가 이 순서대로 등차수열이 되게 하는 양의 정수 순서쌍 $(a,\,b,\,c)$를 모두 구하여라. (단, $1 \leq a \leq b \leq c$.) 일반적으로 실수 $x,\,y,\,z$가 이 순서대로 등차수열을 이루면 $2y=x+z$를 만족한다. 따라서 문제의 조건에 의해,\[ 2(ab+bc+ca) = a+b+c + abc \tag*{$(\ast)$} \]위 등식의 양변을 $abc$로 나누어 주고, $\tfrac{1}{a} \geq \tfrac{1}{b} \geq \tfrac{1}{c}$라는 사실을 이용하면 아래의 부등식을 얻는다.\[ \frac{6}{a} \geq 2\left( \frac{1}{a} + \frac{1}{b} + ..
Others/Olympiad  |  2017. 7. 1. 00:20
Problems and Solutions #032
Problem #032 $a-b$는 소수이고 $ab$가 완전제곱수가 되게 하는 양의 정수 쌍 $(a,\, b)$를 모두 찾아라. 적당한 소수 $p$와 양의 정수 $N$에 대하여, $a-b = p$이고 $ab = N^2$이라 하자. 우선 $\gcd(a,\,b)$가 $a-b$를 나누므로, $\gcd(a,\,b)=1$ 또는 $\gcd(a,\,b) = p$여야만 한다. $\gcd(a,\,b)=1$인 경우, $a$와 $b$가 서로소이므로 $ab=N^2$이라는 가정으로부터 ($a$와 $b$가 공통 인수를 가지지 않으므로, $a$와 $b$의 모든 인수들이 모두 짝수번씩 나타나게 되어) $a=m^2$, $b=n^2$과 같이 나타낼 수 있다. 이제 \[ p = a-b = m^2 - n^2 = (m-n)(m+n). \] ..
Others/Olympiad  |  2017. 6. 21. 05:34
Problems and Solutions #031
Problem #031$x,\, y,\, z$가 아래 식들을 만족하는 세 실수라 하자. \[ x + y + z = 15, \qquad xy + yz + zx = 72. \] 이제 $x$가 가질 수 있는 최솟값을 $m$, 최댓값을 $M$이라 할 때, $m + M$의 값을 구하여라. 첫번째 식을 정리하면 $z = 15 - x - y$를 얻는데, 이를 다시 두번째 식에 대입하여 정리하면 \begin{align*} & xy + y(15 - x - y) + (15 - x - y)x = 72 \\[6px] & \qquad \implies xy + 15y - xy - y^2 + 15x - x^2 - xy = 72 \\[6px] & \qquad \implies x^2 + xy + y^2 - 15x - 15y + 72 ..
Others/Olympiad  |  2017. 6. 21. 05:25
Problems and Solutions #029
Problem #029 $n^4 + n^3 + n^2 + n + 1$이 완전제곱수가 되게 하는 모든 정수 $n$을 구하여라. 식을 간단히 하기 위하여, $f(n) := n^4 + n^3 + n^2 + n + 1$로 정의하자. 또한 \begin{align*} a(n) &:= (2n^2 + n)^2 = 4n^2 + 4n^3 + n^2, \\ b(n) &:= (2n^2 + n + 1)^2 = 4n^4 + 4n^3 + 5n^2 + 2n + 1 \end{align*} 로 각각 정의하면, 간단한 계산을 통해 \[ 4f(n) - a(n) = 3n^2 + 4n + 4 = 2n^2 + (n+2)^2 > 0 \] 를 얻는다. 또한 $-1 < n < 3$인 경우, \[ b(n) - 4f(n) = n^2 - 2n - 3 = ..
Others/Olympiad  |  2017. 6. 7. 21:51

티스토리툴바