# 2019-13 Property R

Let $$A_{a, b} = \{ (x, y) \in \mathbb{Z}^2 : 1 \leq x \leq a, 1 \leq y \leq b \}$$. Consider the following property, which we call Property R:

“If each of the points in $$A$$ is colored red, blue, or yellow, then there is a rectangle whose sides are parallel to the axes and vertices have the same color.”

Find the maximum of $$|A_{a, b}|$$ such that $$A_{a, b}$$ has Property R but $$A_{a-1, b}$$ and $$A_{a, b-1}$$ do not.

GD Star Rating

# Notices

1. There will be no POW this week due to 추석 (thanksgiving) break. POW will resume next week.

2. The submission due for POW2019-12 is extended to Sep. 18 (Wed.).

GD Star Rating

# 2019-12 Groups generated by two homeomorphisms of the real line

Let $$I, J$$ be connected open intervals such that $$I \cap J$$ is a nonempty proper sub-interval of both $$I$$ and$$J$$. For instance, $$I = (0, 2)$$ and $$J = (1, 3)$$ form an example.

Let $$f$$ ($$g$$, resp.) be an orientation-preserving homeomorphism of the real line $$\mathbb{R}$$ such that the set of points of $$\mathbb{R}$$ which are not fixed by $$f$$ ($$g$$, resp.) is precisely $$I$$ ($$J$$, resp.).

Show that for large enough integer $$n$$, the group generated by $$f^n, g^n$$ is isomorphic to the group with the following presentation

$<a, b | [ab^{-1}, a^{-1}ba] = [ab^{-1}, a^{-2}ba^2] = id>.$

GD Star Rating

# Solution: 2019-11 Smallest prime

Find the smallest prime number $$p \geq 5$$ such that there exist no integer coefficient polynomials $$f$$ and $$g$$ satisfying
$p | ( 2^{f(n)} + 3^{g(n)})$
for all positive integers $$n$$.

The best solution was submitted by 김태균 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2019-11.

Other solutions were submitted by 고성훈 (2018학번, +3), 조재형 (수리과학과 2016학번, +3), 채지석 (수리과학과 2016학번, +3), 최백규 (생명과학과 2016학번, +3).

GD Star Rating

# Solution: 2019-10 Is there canonical topology for topological groups?

Let $$G$$ be a group. A topology on $$G$$ is said to be a group topology if the map $$\mu: G \times G \to G$$ defined by $$\mu(g, h) = g^{-1}h$$ is continuous with respect to this topology where $$G \times G$$ is equipped with the product topology. A group equipped with a group topology is called a topological group. When we have two topologies $$T_1, T_2$$ on a set S, we write $$T_1 \leq T_2$$ if $$T_2$$ is finer than $$T_1$$, which gives a partial order on the set of topologies on a given set. Prove or disprove the following statement: for a give group $$G$$, there exists a unique minimal group topology on $$G$$ (minimal with respect to the partial order we described above) so that $$G$$ is a Hausdorff space?

The best solution was submitted by 이정환 (수리과학과 2015학번). Congratulations!

Here is his solution of problem 2019-10.

An incomplete solutions were submitted by 채지석 (수리과학과 2016학번, +2).

GD Star Rating

# 2019-11 Smallest prime

Find the smallest prime number $$p \geq 5$$ such that there exist no integer coefficient polynomials $$f$$ and $$g$$ satisfying
$p | ( 2^{f(n)} + 3^{g(n)})$
for all positive integers $$n$$.

GD Star Rating

# Extension of the due date for 10th problem

For the 10th problem for POW this year, I added a condition that we only consider the group topologies which make the given group a Hausdorff space. Since the problem has been modified, I decided to extend the deadline for this problem. Please hand in your solution by 12pm on Friday (May 31st).

GD Star Rating

# 2019-10 Is there canonical topology for topological groups?

Let $$G$$ be a group. A topology on $$G$$ is said to be a group topology if the map $$\mu: G \times G \to G$$ defined by $$\mu(g, h) = g^{-1}h$$ is continuous with respect to this topology where $$G \times G$$ is equipped with the product topology. A group equipped with a group topology is called a topological group. When we have two topologies $$T_1, T_2$$ on a set S, we write $$T_1 \leq T_2$$ if $$T_2$$ is finer than $$T_1$$, which gives a partial order on the set of topologies on a given set. Prove or disprove the following statement: for a give group $$G$$, there exists a unique minimal group topology on $$G$$ (minimal with respect to the partial order we described above) so that $$G$$ is a Hausdorff space?

GD Star Rating

# Solution: 2019-09 Discrete entropy

Suppose that $$X$$ is a discrete random variable on the set $$\{ a_1, a_2, \dots \}$$ with $$P(X=a_i) = p_i$$. Define the discrete entropy
$H(X) = -\sum_{n=1}^{\infty} p_i \log p_i.$
Find constants $$C_1, C_2 \geq 0$$ such that
$e^{2H(X)} \leq C_1 Var(X) + C_2$
holds for any $$X$$.

The best solution was submitted by 길현준 (2018학번). Congratulations!

Here is his solution of problem 2019-09.

Alternative solutions were submitted by 최백규 (생명과학과 2016학번, +3). Incomplete solutions were submitted by, 이정환 (수리과학과 2015학번, +2), 채지석 (수리과학과 2016학번, +2).

GD Star Rating
Suppose that $$X$$ is a discrete random variable on the set $$\{ a_1, a_2, \dots \}$$ with $$P(X=a_i) = p_i$$. Define the discrete entropy
$H(X) = -\sum_{n=1}^{\infty} p_i \log p_i.$
Find constants $$C_1, C_2 \geq 0$$ such that
$e^{2H(X)} \leq C_1 Var(X) + C_2$
holds for any $$X$$.