Let \(F\) be a family of nonempty subsets of \([n]=\{1,\dots,n\}\) such that no two disjoint subsets of \(F\) have the same union. In other words, for \(F =\{ A_1,A_2,\dots, A_k\},\) there exists no two sets \(I, J\subseteq [k]\) with \(I\cap J =\emptyset\) and \(\bigcup_{i\in I}A_i = \bigcup_{j\in J} A_j\). Determine the maximum possible size of \(F\).
Solution: 2021-20 A circle of perfect squares
Say a natural number \(n\) is a cyclically perfect if one can arrange the numbers from 1 to \(n\) on the circle without a repeat so that the sum of any two consecutive numbers is a perfect square. Show that 32 is the smallest cyclically perfect number. Find the second smallest cyclically perfect number.
The best solution was submitted by 전해구 (기계공학과 졸업생, +4). Congratulations!
Here is the best solution of problem 2021-20.
Solution: 2021-19 The answer is zero
Suppose that \( a_1 + a_2 + \dots + a_n =0 \) for real numbers \( a_1, a_2, \dots, a_n \) and \( n \geq 2\). Set \( a_{n+i}=a_i \) for \( i=1, 2, \dots \). Prove that
\[
\sum_{i=1}^n \frac{1}{a_i (a_i+a_{i+1}) (a_i+a_{i+1}+a_{i+2}) \dots (a_i+a_{i+1}+\dots+a_{i+n-2})} =0
\]
if the denominators are nonzero.
The best solution was submitted by 이도현 (수리과학과 2018학번, +4). Congratulations!
Here is the best solution of problem 2021-19.
2021-20 A circle of perfect squares
Say a natural number \(n\) is a cyclically perfect if one can arrange the numbers from 1 to \(n\) on the circle without a repeat so that the sum of any two consecutive numbers is a perfect square. Show that 32 is the smallest cyclically perfect number. Find the second smallest cyclically perfect number.
Notice on POW 2021-19
POW 2021-19 is still open. Anyone who first submits a correct solution will get the full credit.
2021-19 The answer is zero
Suppose that \( a_1 + a_2 + \dots + a_n =0 \) for real numbers \( a_1, a_2, \dots, a_n \) and \( n \geq 2\). Set \( a_{n+i}=a_i \) for \( i=1, 2, \dots \). Prove that
\[
\sum_{i=1}^n \frac{1}{a_i (a_i+a_{i+1}) (a_i+a_{i+1}+a_{i+2}) \dots (a_i+a_{i+1}+\dots+a_{i+n-2})} =0
\]
if the denominators are nonzero.
Solution: 2021-18 Independent sets in a tree
Let \(T\) be a tree (an acyclic connected graph) on the vertex set \([n]=\{1,\dots, n\}\).
Let \(A\) be the adjacency matrix of \(T\), i.e., the \(n\times n\) matrix with \(A_{ij} = 1\) if \(i\) and \(j\) are adjacent in \(T\) and \(A_{ij}=0\) otherwise. Prove that the number of nonnegative eigenvalues of \(A\) equals to the size of the largest independent set of \(T\). Here, an independent set is a set of vertices where no two vertices in the set are adjacent.
The best solution was submitted by 전해구 (기계공학과 졸업생, +4). Congratulations!
Here is the best solution of problem 2021-18.
Notice on POW 2021-17, 2021-18
POW 2021-17 and 2021-18 are still open. For each problem, anyone who first submits a correct solution will get the full credit.
2021-18 Independent sets in a tree
Let \(T\) be a tree (an acyclic connected graph) on the vertex set \([n]=\{1,\dots, n\}\).
Let \(A\) be the adjacency matrix of \(T\), i.e., the \(n\times n\) matrix with \(A_{ij} = 1\) if \(i\) and \(j\) are adjacent in \(T\) and \(A_{ij}=0\) otherwise. Prove that the number of nonnegative eigenvalues of \(A\) equals to the size of the largest independent set of \(T\). Here, an independent set is a set of vertices where no two vertices in the set are adjacent.
Solution: 2021-16 Optimal constant
For a given positive integer \( n \) and a real number \( a \), find the maximum constant \( b \) such that
\[
x_1^n + x_2^n + \dots + x_n^n + a x_1 x_2 \dots x_n \geq b (x_1 + x_2 + \dots + x_n)^n
\]
for any non-negative \( x_1, x_2, \dots, x_n \).
The best solution was submitted by 전해구 (기계공학과 졸업생, +4). Congratulations!
Here is the best solution of problem 2021-16.