A wizard kidnaps $31$ members from party $A$, $28$ members from party $B$, $23$ members from party $C$, and $19$ members from party $D$, keeping them isolated in individual rooms in his castle, where he forces them to work. Every day, after work, the kidnapped people can walk in the park and talk with each other. However, when three members of three different parties start talking with each other, the wizard reconverts them to the fourth party (there are no conversations with $4$ or more people involved). a) Find out whether it is possible that, after some time, all of the kidnapped people belong to the same party. If the answer is yes, determine to which party they will belong. b) Find all quartets of positive integers that add up to $101$ that if they were to be considered the number of members from the four parties, it is possible that, after some time, all of the kidnapped people belong to the same party, under the same rules imposed by the wizard.
Problem
Source: Argentina TST 2011, Problem 2
Tags: combinatorics proposed, combinatorics, winning positions
01.09.2014 01:14
Each interaction decreases each number of party members by 1 $\mod 4$, and since the ending position is $0,0,0,1\mod4$ we must have one of the numbers be one more than each of the other three. In our case, it's $3,3,3,0$ so it should be possible. In fact, three conversions to party D, two to party C, and twenty six to party B give party B everyone.
11.04.2015 13:19
And part (b)
01.07.2015 21:53
05.12.2022 19:33
For part a): The answer is yes and they will belong to party $B$. Define a quadruple $(a,b,c,d)$ where $a,b,c,d$ are the number of members of parties $A,B,C,D$ respectively. Construction for party $B$. $(31,28,23,19) \rightarrow (30,27,26,18) \rightarrow (29,26,29,17) \rightarrow (28,29,28,16) \rightarrow (27,28,27,19) \rightarrow (26,27,26,22) \rightarrow (25,26,25,25)$ and from this point repeating 25 times we get $(0,101,0,0)$. Now for the reason why only party $B$. Notice that at each move the number of members of all parties decreases by $1$ modulo $4$. In the starting configuration we have $(3,0,3,3)$ modulo $4$ and at ending we will only get $(0,1,0,0)$ modulo $4$. So, only $B$ is the desired party.
17.12.2022 06:34
Let us consider the sum $b_i+2c_i+3d_i \pmod 4$, where $b_i$ is the number of people in party $B$ at some point, and so on. By checking every possible combination, this sum changes by precisely $2 \bmod 4$ every move. Furthermore, this quantity is initially odd, which means that only $B$ and $D$ are possible candidates. Similarly, considering the sum $b_i+2d_i+3c_i$ rules out $D$ as well, so only $B$ is a possible candidate. To see that $B$ indeed works, perform the operation $ABC \to D$ three times, $ABD \to C$ twice, and then $ACD \to B$ 26 times.
13.05.2023 10:05
Solved with SatisfiedMagma. Solution. The answer is only party $B$. Let an ordered tuple $(A,B,C,D)$ denote the number of people at any point of time. The following sequence justifies that $B$ works. \[(31,28,23,19) \mapsto (30,27,26,18) \mapsto (29,26,29,17) \mapsto (28,29,28,16) \mapsto (27,28,27,19) \mapsto (27,28,27,19) \mapsto (26,27,26,22) \mapsto (25,26,25,25)\]Just keep removing members from $A,C,D$ and we will eventually reach $(0,101,0,0)$ as desired. For the other direction, look at the tuple modulo $2$. Initially the tuple $(1,0,1,1)$. It is easy to see that the tuple will change the parity of each element in every iteration. So, the tuple can only reach $(1,0,1,1)$ or $(0,1,0,0)$ in modulo $2$. This clearly means that $101$ can only appear in the $B$ spot and not anywhere else. $\blacksquare$
23.11.2023 06:06
12.12.2023 22:58
I will use a strategy for a problem that previously solves: If there are the same number of members in three parties, then at some point all the kidnapped people will belong to the 4th party. Note that B can never have the same number of members as 2 other parties. Only parties A=C=D can be equal. Party B can never be equal to 3 parties, this is due to: 1) a=If exactly three people from party B C D get together 2) b=If exactly three people from party A C D get together 3) c=If exactly three people from party A B D get together 4) d=If exactly three people from party A B C get together Then the cardinality of each one depends on the following equation: 1.1) A= 31 +3a -b-c-d 1.1) B= 28 +3b -a-c-d 1.1) C= 23 +3c -a-b-d 1.1) D= 19 +3d -a-b-c Suppose A=B then \[31 +3a -b-c-d = 28 +3b -a-c-d \]\[3 +4a -4b = 0\]And the above is not possible due to parity, this is done symmetrically with B = C, B = D and we will arrive at the same contradiction. Therefore, the only way to stay the same party the kidnapped people is for A=C=D to occur at some point. \[2+a-c=0 (A=C)\]\[3+a-d=0 (A=D)\]\[1+c-d=0 (C=D)\]A solution solution is (a,c,d) =(0,2,3). So a solution is with (a,b,c,d) = (0,26,2,3) $(31,28,23,19) \rightarrow (30,27,26,18) \rightarrow (29,26,29,17) \rightarrow (28,25,28,20) \rightarrow (27,24,27,23) \rightarrow (26,23,26,26) \rightarrow (0,101,0,0) $ Therefore, all the kidnapped people can only be in party B. \(\blacksquare\)
29.12.2023 22:26
Umm ig I do not see the following invariant above. Here is a sketch for my solution for part (a). Note that $(|A| + |C| - |B| - |D|)$ and $(|A|+|D|-|B|-|C|)$ are both invariant under $\mod 4$. Thus checking the initial values of each of these invariant, we get that only $B$ can work. Now for the construction, let $A$ denote a move on party $A$. The following set of moves does it, $D\rightarrow D\rightarrow D\rightarrow C\rightarrow C\rightarrow B\rightarrow B\rightarrow \cdots \rightarrow B$ works.
22.07.2024 16:47
\begin{claim} We claim all the kidnapped people can end up at party B. \end{claim} Let the notation $(a,b,c,d)$ denote the number of peple in party $A$,$B$,$C$,$D$ respectively. The construction for group B is as follows: \begin{align} & \text{Convert to party D : 4 time} \\ & \text{Convert to party C twice} \\ & \text{Convert to party B : 26 times} \\ \end{align}For proof that this is the only such possible endpoint for the tuple, take each element of the tuple modulo $4$. Particularly, each activity decreases the number of people in each party by $1 \pmod 4$. By performing the above construction on the initial tuple modulo $4$ , $(3,0,3,3)$ we get $(0,1,0,0)$ which obviously works. $\square$
22.07.2024 18:46
I do,not know about the people but the wizard would go to jail
02.08.2024 04:45
We claim only party $B$ can have all the people at any point in time. Suppose $a$ conversations occur converting $3$ people to party $A$. Define $b$, $c$, $d$ similarly. Then party $A$ will have $$31 + 3a - b - c - d = 31 + 4a - (a + b + c + d)$$people remaining, and similar results hold for other parties. This implies that if $3$ parties have the same number of people, their original number of people in $\pmod{4}$ should be equal. This only occurs with parties $A$, $C$, $D$ so $B$ is the only party that can have all the people. To show sufficiency note that $(a, b, c, d) = (0, 26, 2, 3)$ satisfies the equations hence it is possible.
24.11.2024 06:41
All of the people can belong to party $B$ only. Note that $\pmod 4$, the parties will have to have 1 0 0 0 people at the end (some permutation of that). However, the $\pmod 4$ values never change in respect to each other (after each move, the $\pmod 4$ values all go down by $1\pmod 4$). The original values are 0 3 3 3 people $\pmod 4$. The party that is $0\pmod 4$ (one ahead of everyone else) will be the party that everyone belongs to. The construction is $$ABC\to D\times 3, ABD\to C\times 2, ACD\to B\times 26.$$