# 2021-07 Odd determinant

Let $$A_N$$ be an $$N \times N$$ matrix whose entries are i.i.d. Bernoulli random variables with probability $$1/2$$, i.e.,

$\mathbb{P}( (A_N)_{ij} =0) = \mathbb{P}( (A_N)_{ij} =1) = \frac{1}{2}.$

Let $$p_N$$ be the probability that $$\det A_N$$ is odd. Find $$\lim_{N \to \infty} p_N$$.

GD Star Rating

# Notice: Mid-term break

POW will resume on Apr. 30.

GD Star Rating

# Solution: 2021-06 A nondecreasing subsequence

Let $$\mathcal{A}_n$$ be the collection of all sequences $$\mathbf{a}= (a_1,\dots, a_n)$$ with $$a_i \in [i]$$ for all $$i\in [n]=\{1,2,\dots, n\}$$. A nondecreasing $$k$$-subsequence of $$\mathbf{a}$$ is a subsequence $$(a_{i_1}, a_{i_2},\dots, a_{i_k})$$ such that $$i_1< i_2< \dots < i_k$$ and $$a_{i_1}\leq a_{i_2}\leq \dots \leq a_{i_k}$$. For given $$k$$, determine the smallest $$n$$ such that any sequence $$\mathbf{a}\in \mathcal{A}_n$$ has a nondecreasing $$k$$-subsequence.

The best solution was submitted by 고성훈 (수리과학과 2018학번, +4). Congratulations!

Here is his solution of problem 2021-06.

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

GD Star Rating

# Solution: 2021-05 Finite generation of a group

Prove or disprove that if all elements of an infinite group G has order less than n for some positive integer n, then G is finitely generated.

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

Here is his solution of problem 2021-05.

Other solutions were submitted by 강한필 (전산학부 2016학번, +3), 고성훈 (수리과학과 2018학번, +3), Late solutions are not graded.

GD Star Rating

# 2021-06 A nondecreasing subsequence

Let $$\mathcal{A}_n$$ be the collection of all sequences $$\mathbf{a}= (a_1,\dots, a_n)$$ with $$a_i \in [i]$$ for all $$i\in [n]=\{1,2,\dots, n\}$$. A nondecreasing $$k$$-subsequence of $$\mathbf{a}$$ is a subsequence $$(a_{i_1}, a_{i_2},\dots, a_{i_k})$$ such that $$i_1< i_2< \dots < i_k$$ and $$a_{i_1}\leq a_{i_2}\leq \dots \leq a_{i_k}$$. For given $$k$$, determine the smallest $$n$$ such that any sequence $$\mathbf{a}\in \mathcal{A}_n$$ has a nondecreasing $$k$$-subsequence.

GD Star Rating

# Solution: 2021-04 Product of matrices

For an $$n \times n$$ matrix $$M$$ with real eigenvalues, let $$\lambda(M)$$ be the largest eigenvalue of $$M$$. Prove that for any positive integer $$r$$ and positive semidefinite matrices $$A, B$$,

$[\lambda(A^m B^m)]^{1/m} \leq [\lambda(A^{m+1} B^{m+1})]^{1/(m+1)}.$

The best solution was submitted by 고성훈 (수리과학과 2018학번, +4). Congratulations!

Here is his solution of problem 2021-04.

Another solutions was submitted by 김건우 (수리과학과 2017학번, +3),

GD Star Rating

# 2021-05 Finite generation of a group

Prove or disprove that if all elements of an infinite group G has order less than n for some positive integer n, then G is finitely generated.

GD Star Rating