Determine maximum real $ k$ such that there exist a set $ X$ and its subsets $ Y_{1}$, $ Y_{2}$, $ ...$, $ Y_{31}$ satisfying the following conditions: (1) for every two elements of $ X$ there is an index $ i$ such that $ Y_{i}$ contains neither of these elements; (2) if any non-negative numbers $ \alpha_{i}$ are assigned to the subsets $ Y_{i}$ and $ \alpha_{1}+\dots+\alpha_{31}=1$ then there is an element $ x\in X$ such that the sum of $ \alpha_{i}$ corresponding to all the subsets $ Y_{i}$ that contain $ x$ is at least $ k$.
Problem
Source: Tuymaada 2007, Problem 4
Tags: combinatorics proposed, combinatorics
iura
18.07.2007 00:10
If any element belongs to at most $ 25$ of the sets we can choose $ \alpha_{i}=\frac 1{31}$ and the sum calculated for each element will be at most $ \frac{25}{31}$. Otherwise, there exist an element $ x$ that belongs to all sets except $ m$ of them where $ 1\leq m \leq 5$. In this case, we may assign $ \alpha_{i}=\frac{1}{m}$ if $ x\notin A_{i}$ and $ \alpha_{0}=0$ otherwise. Every element will not belong to at least one of the $ m$ sets (because otherwise there is no set containing neither it neither $ x$), so the sum associated to it is at most $ 1-\frac{1}{m}\leq 1-\frac{1}{5}<\frac{25}{31}$. We have proven that $ k\leq \frac{25}{31}$. Now we prove $ k$ can be $ \frac{25}{31}$. $ 31=5^{2}+5+1$ where $ 5$ is prime. Therefore by considering a projective plane for $ p=5$ we get a set of $ 31$ elements anf $ 31$ subsets $ B_{1}, B_{2}, \ldots, B_{31}$ of it such that each pair of elements belongs to (exactly) one set and each set consists of $ 6$ elements while each element belongs to $ 6$ sets (and also any two sets have intersection one element, so there is a complete correspondence between elements and sets). Now just let $ A_{i}$ be the complement of $ B_{i}$, having $ 25$ elements, and each element belonging to $ 25$ sets. Then no matter how we assign the $ \alpha_{i}$, if we sum all the sums obtained for the $ 31$ elements, we get each $ \alpha_{i}$ $ 25$ times, so a total of $ 25$. Then at least one of the assigned sums is at least $ \frac{25}{31}$, as desired. Note: The projective plane for a prime $ p$ is a well-known example and is constructed as follows: Consider a set of $ p^{3}-1$ triplets $ (x,y,z)\neq (0,0,0)$ where $ x,y,z\in \mathbb{Z}_{p}$. We consider two triplets $ (a,b,c)$ and $ (d,e,f)$ equivalent if and only if $ (a,b,c)=(\lambda d, \lambda e, \lambda f)$ for some $ \lambda \in \mathbb{Z}_{p}\setminus \{0\}$. Each class of equivalency consists of $ p-1$ elements so we get $ p^{2}+p+1$ classes of equivalency. Now let the element associated to the class of equivalency of $ (a,b,c)$ belong to the set associated to the class of equivalency of $ (d,e,f)$ if and only if $ ad+be+cf=0$ (in $ \mathbb{Z}_{p}$). It is easy to check the definition is proper. Also each elee ment belongs to $ p+1$ sets, each set contains $ p+1$ elements, for every pair of elements there is exactly one set containing them, and every pair of sets intersect in exactly one element.