A conference is attended by $n (n\ge 3)$ scientists. Each scientist has some friends in this conference (friendship is mutual and no one is a friend of him/herself). Suppose that no matter how we partition the scientists into two nonempty groups, there always exist two scientists in the same group who are friends, and there always exist two scientists in different groups who are friends. A proposal is introduced on the first day of the conference. Each of the scientists' opinion on the proposal can be expressed as a non-negative integer. Everyday from the second day onwards, each scientists' opinion is changed to the integer part of the average of his/her friends' opinions from the previous day. Prove that after a period of time, all scientists have the same opinion on the proposal.
Problem
Source: CMO 2022 P4
Tags: combinatorics
22.12.2021 08:27
Consider the graph of friendships is connected. The condition of having two scientists in different groups is equivalent to saying the graph is connected (partition connected components). The condition of having two scientists in the same group is equivalent to saying the graph is not 2-colorable/bipartite (by definition of bipartite). Notice the opinion of all scientists is bounded above by the maximal initial opinion. Therefore the set of options takes a finite number of states and is deterministic, so it eventually enters a cycle. Note that maximal opinion is weakly decreasing, so by periodicity, it is eventually constant. Notice if a maximal vertex is adjacent to a nonmaximal one, it is nonmaximal the next turn. Once it is constant, notice the number of nonmaximal to nonmaximal edges is weakly increasing, so by periodicity it is eventually constant. Also, the number of maximal to maximal edges is weakly decreasing, so by periodicity, it is eventually constant. Since maximal to maximal edges cannot disappear, if there are any then any bordering vertex is always maximal, and so on implying the entire graph is maximal. This is as desired. So consider the case when no maximal to maximal edges exist. Since nonmaximal to nonmaximal edges cannot disappear, no other types of edges can become nonmaximal to nonmaximal edges. This means for any nonmaximal to maximal edge, the nonmaximal vertex must become maximal. So the nonmaximal vertex only borders maximal vertices. Assume some nonmaximal vertex borders only nonmaximal vertices, then by our previous result all of those nonmaximal vertices only border nonmaximal vertices, and so on, implying the entire graph is nonmaximal. This is a contradiction, so all nonmaximal vertices border only maximal vertices. This implies that the set of maximal and nonmaximal vertices are a bipartition of the graph, giving contradiction. So we are done.
22.12.2021 17:41
23.12.2021 01:47
Ignore $$ $$
23.12.2021 04:39
Take the obvious graph interpretation.
24.12.2021 17:17
A similar solution: Let our graph be $G$. It’s given that $G$ is non-bipartite and connected, so there’s an odd cycle $C$ in $G$. The main observation is that the maximum opinion is weakly decreasing, and since it has a lower bound (e.g. $0$), it’s eventually a constant $M$. From this point, we say that a node “is not M” iff at the time its opinion isn’t $M$. It’s clear that if a node isn’t M, all its neighbours aren’t M on the following day. 1) Therefore, starting from any vertex $v_0$, its neighbours won’t be M on the following day, and so do its neighbours’ neighbours. We’ll eventually reach a node $v_1$ in the odd cycle and make it not M (due to connectivity). 2) Knowing that at some point there’s a node in $C$ that’s not M, we can see that the two neighbours of $v_1$ in $C$ won’t be M on the following day, and the neighbours of neighbours won’t be M on the day after... 3) At some point, we’ll arrive at two adjacent nodes in $C$ that are not M at the same time (since $C$ is odd). 4) If there are two “not M” adjacent nodes, their direct neighbours and themselves won’t be M later. These “not M” nodes expand outward and remain to be “not M” since every one of them is connected to at least one “not M” node. Eventually all nodes aren’t M, which is a contradiction! This implies that if the maximum reaches a constant, all opinions are the same (they’re all $M$).
26.04.2022 08:21
I found this video helpful: https://youtu.be/EuLaHqFyTtI
07.04.2023 19:19
Consider the obvious Graph interpretation. Let the given graph be $G$. We know by the conditions that $G$ is connected and not bipartite, and that the maximum vote M cannot increase. Note that after the first day, if a vertex at any given time has not the maximum vote, then it will never: indeed, for a vertex $v$ to have the maximum vote it needs to have all the adjecent nodes' votes M, which will never happen since all its neighbours cannot increase their votes to M because of the presence of $v$. On the converse, due the connectivity of $G$ we know that there exists a vertex $u$ whose vote is M that has a neighbour with a vote numerically less than M, thus $u$'s vote will deacrease. In particular the number of nodes with the maximum vote is strictly decreasing and since M is bounded by $0$ we will reach a state in which all the nodes have the maximum vote, thus the same vote. Remark: I didn't use the fact that $G$ is not bipartite so I'm not sure about this solution.
30.04.2024 16:48
Geometry_lover wrote: Consider the obvious Graph interpretation. Let the given graph be $G$. We know by the conditions that $G$ is connected and not bipartite, and that the maximum vote M cannot increase. Note that after the first day, if a vertex at any given time has not the maximum vote, then it will never: indeed, for a vertex $v$ to have the maximum vote it needs to have all the adjecent nodes' votes M, which will never happen since all its neighbours cannot increase their votes to M because of the presence of $v$. On the converse, due the connectivity of $G$ we know that there exists a vertex $u$ whose vote is M that has a neighbour with a vote numerically less than M, thus $u$'s vote will deacrease. In particular the number of nodes with the maximum vote is strictly decreasing and since M is bounded by $0$ we will reach a state in which all the nodes have the maximum vote, thus the same vote. Remark: I didn't use the fact that $G$ is not bipartite so I'm not sure about this solution. Consider the graph $K_{3,3}$. We obtain that $G$ must be not bipartite.
25.10.2024 22:38
Here is my solution:- Convert this to a graph $\mathcal{G}$ where scientists are the vertices two friends are joined by edges. As per condition $\mathcal{G}$ is a connnected non biparite graph Assuem the contrary at each step color the vertex with the maximum valued opinion as "red" others as blue It is easy to see after a point the values at "red" vertices is fixed. and also we assume number of red vertices are always fixed. It is easy to see that each step for any vertex $v$ all of its neighours are red it becomes red , otherwise blue next day Claim: Two blue vertices can never be joined by an egde. Proof: Assume the contrary $u$ and $v$ are two vertices joined like this. Lemma: None of them will ever turn red after they were together blue. Proof: Say it does happen , It is easy to see both cant turn red for first time on same day after they were blue together say WLOG $u$ turns red first but for $u$ to turn red it neighours must all be red before hand that implies $v$ is red but thats contradiction! Now we prove entually all vertices will become non red ,we induct on the distance between the vertex and $u$ from which it is easy to see . Easy to see any red vertex will always atleast once will turn to blue Now say we have a odd cycle in the graph, $v_1 \to v_2 .... \to v_k \to v_1$ in the graph which clearly has to exist. now observe eventually one vertex turns to blue and as the blue color spreads to its neighours its count grows largely and will not platue eventually cuasing an edge between two blue vertices.