In a class of $26$ students, everyone is being graded on five subjects with one of three possible marks. Prove that if $25$ of these students have received their marks, then we can grade the last one in such a way that their marks differ from these of any other student on at least two subjects.
Problem
Source: Bulgaria National Olympiad 2023 Problem 6
Tags: combinatorics
02.05.2023 15:09
Does anybody have a solution?
07.05.2023 19:55
Assume that each pair of the $25$ students is given different marks in at least one subject, otherwise we can remove one of these students. I claim that we can assign the last student marks in each of the first three subjects such that they differ in at least two subjects in all except at most $6$ other students, and even for these students they differ in one subject. Since $6<9$ we can assign marks for the last two subjects such that they don't perfectly match any of the $6$ students, forcing the desired. Note that for the first subject there must be some mark that is achieved by at most $8$ of the $25$ students. Assign this to the last student, and note that at most $2$ of the $17$ other students can differ from the last student in only one of the first three subjects (being the first subject). Now for the $8$ remaining students, there exists a mark that only at most $2$ students achieve; assign this to the last student. Once again only $2$ of the $6$ other students can now differ from the last student in only one of the first three subjects. For the third subject assign the last student the mark that none of the two remaining students got. This enforces the fact that the last student did not get the exact same marks as any other in the first three subjects. Notice that in each of the three stages, at most two students were found to differ from the last in only one subject. Thus at most $6$ students do, and so we're done.
08.05.2023 12:40
asbodke wrote: ... Note that for the first subject there must be some mark that is achieved by at most $8$ of the $25$ students. Assign this to the last student, and note that at most $2$ of the $17$ other students can differ from the last student in only one of the first three subjects (being the first subject). ... Why the red text should be true? It seems you think that there are no two students among the 25 ones with the same marks for the first 3 subjects! But it is not for granted.
26.07.2023 07:16
https://download.wezhan.cn/contents/sitefiles2057/10287724/files/716860..pdf?response-content-disposition=inline%3Bfilename%3D2023%25e5%25b9%25b4%25e4%25bf%259d%25e5%258a%25a0%25e5%2588%25a9%25e4%25ba%259a%25e6%2595%25b0%25e5%25ad%25a6%25e5%25a5%25a5%25e6%259e%2597%25e5%258c%25b9%25e5%2585%258b%25e8%25af%2595%25e9%25a2%2598%25e8%25a7%25a3%25e6%259e%2590-%25e6%259d%258e%25e6%25b1%259d%25e6%259b%25a6%25e9%2587%2591%25e9%2580%25b8%25e8%2588%25aa%25e9%25ab%2598%25e6%25b5%25b7%25e5%25b2%25a9%28%25e9%2595%25bf%25e9%2583%25a1%25e4%25b8%25ad%25e5%25ad%25a6%29-%25e4%25bf%25ae%25e6%25ad%25a3%25e7%2589%2588.pdf&response-content-type=application%2Fpdf&auth_key=1690344827-601494e0b6c54a7cb38c326c4a20054a-0-1abb22c020497f80fb9f136e6595cdfb
09.10.2023 16:33
Let $ X$ be the space of all ternary strings of length $ 5,$ that is, $$\displaystyle X=\{(s_1,s_2,s_3,s_4, s_5) : s_i\in\{0,1,2\} \}.$$For two objects $ x,y\in X$ we define the distance $ d(x,y)$ between $ x$ and $ y$ as the number of positions at which $ x$ and $ y$ differ. This is a kind of Hamming distance but in case of ternary strings. Thus, $ 0\le d(x,y)\le 5$ and $ d(x,y)=0$ only if $ x=y.$ Next, for any $ x\in X$ we consider a ball $B_1(x)$ with center $ x$ and radius $ 1$ defined as $\displaystyle B_1(x):= \{y\in X: d(x,y)=1\}.$ The problem statement can be read as: It is impossible to cover $ X$ with $ 25$ balls with radius $ 1.$ Actually, something stronger is true - it's impossible to cover $ X$ with $26$ balls, which can be done by refining the following solution. The least number of balls needed is $27$. Let's prove it here for $25$, as in the original statement. Suppose on the contrary it is possible and let $ S$ be the set of the centers of these balls. So if $ s\in S$ then $ s=(s_1,s_2,s_3,s_4,s_5), s_i\in \{0,1,2\}.$ Let us denote $$ \displaystyle A=\{(s_1,s_2,s_3): s\in S, s=(s_1,s_2,s_3)\}\,;\, B:=\{(s_4,s_5): s\in S\}.$$We know that $ |A|\le 26, |B|\le 3\cdot 3=9.$ Actually, it can be easily seen that $ |B|=9.$ Indeed, since $ |A|\le 26,$ there exists $ (x,y,z)\in \{0,1,2\}^3$ that is outside $ A.$ If there exists $ (u,v)\in \{0,1,2\}^2$ that is outside $ B,$ then $ (x,u,z,u,v)$ doesn't lie in any ball of $ S.$ Hence, $ |B|=9.$ Consider a bipartite graph $ G(A,B)$ and connect $ a\in A$ to $ b\in B$ if $ ab\in S.$ Thus, we can interpret (map) $ S$ as the edges of $ G(A,B).$ Since there are $ 25$ edges, there exists $ b_0\in B$ with $ \deg(b_0)\le 2$ and let $ a_1,a_2\in A$ be the vertices connected to $ b_0.$ Let $ X_0\subset X$ be the set of all strings in $ X$ whose last two coordinates are equal to $ b_0.$ Thus, $ |X_0|=3^3=27.$ The main plan is to show that $ X_0$ cannot be covered by the balls centered at $ S.$ (that is, by the edges of $ G(A,B)$), except in some pathological case. But, if so, we take another plausible vertex and it turns out that it's impossible to hit only pathological cases. One can see the details in my blog.