Category Archives: problem

2016-7 Sum-free

For a set \( A \subset \mathbb{R} \), let \( f(A) \) be the size of the largest set \( B \subset A \) such that \( (B+B) \cap B = \emptyset \). For a positive integer \( n \), let \( f(n) = \min_{0 \notin A, |A|=n} f(A) \). Prove that \( f(n) \geq n/3 \).

2016-6 Convex function

Suppose that \( f \) is a real-valued convex function on \( \mathbb{R} \). Prove that the function \( X \mapsto \mathrm{Tr } f(X) \) on the vector space of \( N \times N \) Hermitian matrices is convex.

2016-5 Partition into 4 sets

Let \(A_1,A_2,\ldots,A_n\) be subsets of \(\{1,2,\ldots,n\}\) such that \(i\notin A_i\) for all \(i\). Prove that there exist four sets \(C_1,C_2,C_3,C_4\) such that \(C_1\cup C_2\cup C_3\cup C_4=\{1,2,\ldots,n\} \) and for all \(i\) and \(j\), if \(i\in C_j\), then \( \lvert A_i\cap C_j\rvert \le \frac12 \lvert A_i\rvert\).

2016-4 Distances in a tree

Let \(T\) be a tree on \(n\) vertices \(V=\{1,2,\ldots,n\}\). For two vertices \(i\) and \(j\), let \(d_{ij}\) be the distance between \(i\) and \(j\), that is the number of edges in the unique path from \(i\) to \(j\). Let \(D_T(x)=(x^{d_{ij}})_{i,j\in V}\) be the \(n\times n\) matrix. Prove that \[ \det (D_T(x))=(1-x^2)^{n-1}.\]

2016-3 Non-finitely generated subgroup

Let \( G \) be a subgroup of \( GL_2 (\mathbb{R}) \) generated by \( \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix} \) and \( \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \). Let \( H \) be a subset of \( G \) that consists of all matrices in \( G \) whose diagonal entries are \( 1 \). Prove that \( H \) is a subgroup of \( G \) but not finitely generated.

2016-1 Flipping signs

Prove that for every \( x_1, x_2,\ldots,x_n\in [0,1]\), there exist \(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n\in\{1/2,-1/2\}\) such that for all \(k=1,2,\ldots,n-1\), \[ \left\lvert \sum_{i=1}^k \varepsilon_i x_i-\sum_{i=k+1}^n \varepsilon_i x_i \right\rvert\le 1.\]

2015-24 Hölder inequality for matrices

Let \( A, B \) are \( n \times n \) Hermitian matrices and \( p, q \in [1, \infty] \) with \( \frac{1}{p} + \frac{1}{q} = 1 \). Prove that
\[
| Tr (AB) | \leq \| A \|_{S^p} \| B \|_{S^q}.
\]
(Here, \(\| A \|_{S^p} \) is the \(p\)-Schatten norm of \( A \), defined by
\[
\| A \|_{S^p} = \left( \sum_{i=1}^n |\lambda_i|^p \right)^{1/p},
\]
where \( \lambda_1, \lambda_2, \dots, \lambda_n \) are the eigenvalues of \( A \).)

2015-23 Fixed points

Let \(f:[0,1)\to[0,1)\)  be a function such that \[ f(x)=\begin{cases} 2x,&\text{if }0\le 2x\lt 1,\\ 2x-1, & \text{if } 1\le 2x\lt 2.\end{cases}\] Find all \(x\) such that \[ f(f(f(f(f(f(f(x)))))))=x.\]