Category Archives: solution

Solution: 2020-12 Draws on a chess tournament

There are \(n\) people participating to a chess tournament and every two players play exactly one game against each other. The winner receives \(1\) point and the loser gets \(0\) point and if the game is a draw, each player receives \(0.5\) points. Prove that if at least \(3/4\) of the games are draws, then there are two players with the same total scores.

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-12.

Another solution was submitted by 고성훈 (수리과학과 2018학번, +3).

GD Star Rating
loading...

Solution: 2020-11 Free group of rank 2

Show that there is a subgroup of a free group of ran 2 that is not finitely generated.

The best solution was submitted by 채지석 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-11.

Other solutions were submitted by 조한슬 (수리과학과 2017학번, +3), 최백규(생명과학과 대학원, +2).

GD Star Rating
loading...

Solution: 2020-09 Displacement of permutations

For a permutation \(\pi: [n]\rightarrow [n]\), we define the displacement of \(\pi\) to be \(\sum_{i\in [n]} |i-\pi(i)|\).

For given \(k\), prove that the number of even permutations of \([n]\) with displacement \(2k\) minus the number of odd permutations of \([n]\) with displacement \(2k\) is \((-1)^{k}\binom{n-1}{k}\).

The best solution was submitted by 홍의천 (수리과학과 2017학번). Congratulations!

Here is his solution of problem 2020-09.

Another solution was submitted by 고성훈 (수리과학과 2018학번, +3).

GD Star Rating
loading...

Solution: 2020-08 Geometric action revisited

In the problem 2019-08 (https://mathsci.kaist.ac.kr/pow/2019/2019-08-group-action/), we considered a group G acting by isometries on a proper geodesic metric space X properly discontinuously and cocompactly. Such an action is called a geometric action. The conclusion was that a geometric action leads to that G is finitely generated.

Would this conclusion still hold in the case the space X is not necessarily proper?

The best solution was submitted by 홍의천 (수리과학과 2017학번). Congratulations!

Here is his solution of problem 2020-08.

GD Star Rating
loading...

Solution: 2020-07 Perfect square

Suppose that \( x, y, z \) are positive integers satisfying
\[
0 \leq x^2 + y^2 – xyz \leq z+1.
\]
Prove that \( x^2 + y^2 – xyz \) is a perfect square.

The best solution was submitted by 임상호 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-07.

Another solution was submitted by 김기수 (수리과학과 2018학번, +3), 홍의천 (수리과학과 2017학번, +3)

GD Star Rating
loading...

Solution: 2020-06 A binary maze

A binary maze consists of \(n\) separate rooms. Each room has a teleportation machine but no doors. The numbers \( a_{i,j}\in [n] \) are given for all \( (i,j)\in [n]\times \{0,1\} \). If you shout a number \( j\in \{0,1\} \) while you are in the room \( i \), then the teleportation machine will teleport you to the room \(a_{i,j}\).

You don’t know the numbers \(a_{i,j}\), but it is given that for any \(i\neq i’ \), there exists a way to reach room \( i’ \) from room \( i \) by shouting numbers \( 0 \) and \( 1 \) in some order.

At the beginning, your enemy will teleport you into one of the rooms while your eyes are closed. Your goal is to visit all rooms at least once with your eyes closed. As your eyes are closed, you don’t know which rooms you have visited before and you don’t know which room you are currently at.

So, you decide to pick a sequence \( b=(b_1,\dots, b_s) \in \{0,1\}^s \) before entering the binary maze and decide to shout the numbers \( b_1,\dots, b_s \) in order. Find a lower bound \( \ell(n) \) and an upper bound \( u(n) \) on the minimum length of a sequence which guarantees that you can visit all \( n \) rooms. If your \( \frac{u(n)}{\ell(n)} \) is smaller than some polynomial of \( n \) for all \( n\in\mathbb{N} \) , then you will get full points.

The best solution was submitted by 홍의천 (수리과학과 2018학번). Congratulations!

Here is his solution of problem 2020-06.

Another solution was submitted by 강한필 (전산학부 2016학번, +3).

GD Star Rating
loading...

Solution: 2020-05 Completion of a metric space

We say a metric space complete if every Cauchy sequence converges.

Let (X, d) be a metric space. Show that there exists an isometric imbedding from X to a complete metric space Y so that the image of X in Y is dense.

The best solution was submitted by 김기수 (수리과학과 2018학번). Congratulations!

Here is his solution of problem 2020-05.

Other solutions were submitted by 고성훈 (수리과학과 2018학번, +3), 구은한 (수리과학과 2019학번, +3), 길현준 (수리과학과 2018학번, +3), 김기택 (수리과학과 2015학번, +3), 이준호 (2016학번, +3).

GD Star Rating
loading...

Solution: 2020-04 Convergence at all but one point

Let \( f_n : [-1, 1] \to \mathbb{R} \) be a continuous function for \( n = 1, 2, 3, \dots \). Define

\[

g_n(y) := \log \int_{-1}^1 e^{y f_n(x)} dx.

\]

Suppose there exists a continuous function \( g: \mathbb{R} \to \mathbb{R} \) and \( y_0 \in \mathbb{R} \) such that \( \lim_{n \to \infty} g_n(y) = g(y) \) for all \( y \neq y_0 \). Prove or disprove that \( \lim_{n \to \infty} g_n(y_0) = g(y_0) \).

The best solution was submitted by 홍의천 (수리과학과 2017학번). Congratulations!

Here is his solution of problem 2020-04.

Other solutions were submitted by 길현준 (수리과학과 2018학번, +3), 김기택 (수리과학과 2015학번, +3), 이준호 (2016학번, +3).

GD Star Rating
loading...

Solution: 2020-03 Graceful permutations

A permutation \( \pi : [n]\rightarrow [n] \) is graceful if \( |\pi(i+1) – \pi(i)| \neq |\pi(j+1)-\pi(j)| \) for all \(i\neq j \in [n-1]\). For a graceful permutation \( \pi :[2k+1] \rightarrow [2k+1] \) with \( \pi(\{2,4,\dots,2k\}) = [k] \), prove that \(\pi(1)+ \pi(2k+1) = 3k+2 \).

The best solution was submitted by 유찬진 (수리과학과 2015학번). Congratulations!

Here is his solution of problem 2020-03.

Other solutions were submitted by 고성훈 (수리과학과 2018학번, +3), 김기수 (수리과학과 2018학번, +3), 김기택 (수리과학과 2015학번, +3), 박현영 (전기및전자공학부 2016학번, +3), 이준호 (2016학번, +3), 조태혁 (수리과학과 2014학번, +3), 채지석 (수리과학과 2016학번, +3), 최고수 (전남과학고등학교, +3).

GD Star Rating
loading...