Category Archives: problem

2021-21 Different unions

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\).

GD Star Rating
loading...

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.

GD Star Rating
loading...

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.

GD Star Rating
loading...

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.

GD Star Rating
loading...

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 \).

GD Star Rating
loading...

2021-14 Perfectly normal product

Let X, Y be compact spaces. Suppose \(X \times Y\) is perfectly normal, i.e, for every disjoint closed subsets E, F in \(X \times Y\), there exists a continuous function \( f: X \times Y \to [0, 1] \subset \mathbb{R} \) such that \( f^{-1}(0) = E, f^{-1}(1) = F \). Is it true that at least one of X and Y is metrizable?

(added Sep. 11, 8AM: Assume further that \( X \times Y\) is Hausdorff.)

GD Star Rating
loading...

2021-13 Not convex

Prove or disprove the following:

There exist an infinite sequence of functions \( f_n: [0, 1] \to \mathbb{R} , n=1, 2, \dots \) ) such that

(1) ( f_n(0) = f_n(1) = 0 ) for any ( n ),

(2) ( f_n(\frac{a+b}{2}) \leq f_n(a) + f_n(b) ) for any ( a, b \in [0, 1] ),

(3) ( f_n – c f_m ) is not identically zero for any ( c \in \mathbb{R} ) and ( n \neq m ).

GD Star Rating
loading...

2021-12 A graduation ceremony

In a graduation ceremony, \(n\) graduating students form a circle and their diplomas are distributed uniformly at random. Students who have their own diploma leave, and each of the remaining students passes the diploma she has to the student on her right, and this is one round. Again, each student with her own diploma leave and each of the remaining students passes the diploma to the student on her right and repeat this until everyone leaves. What is the probability that this process takes exactly \(k \) rounds until everyone leaves.

GD Star Rating
loading...