There are $30$ teams in NBA and every team play $82$ games in the year. Bosses of NBA want to divide all teams on Western and Eastern Conferences (not necessary equally), such that number of games between teams from different conferences is half of number of all games. Can they do it?
Problem
Source: All russian olympiad 2016,Day1,grade 11,P1
Tags: combinatorics
09.05.2016 15:57
let the number of teams belonged to Western conference be $x$. the total number of games is $1230$, so if they can do, the number of games between conferences is $615$. Now, we can get the number $82x-615$ which means the twice of the number of games played between western teams. Surely it should be the even number, but whether $x$ is even or odd, it turns to be odd number. contradiction.
09.05.2016 23:16
Well, why should $82x-615$ be twice the number of games played between western teams, it is the number of games played between the western ones plus the number of games played between the eastern? I think, the right soluttion is: lets transfer the teams from west to east one by one. Each time the number of games between the conferences changes by $82-2x$, so in the end, when all the teams are in the eastern conf we'll have an odd number of games between the conferences. But as you can see, this number equals to $0$. Contradiction.
10.05.2016 03:41
MKsh99 wrote: Well, why should $82x-615$ be twice the number of games played between western teams, it is the number of games played between the western ones plus the number of games played between the eastern? I think, $82x$ should be the number of games western teams played. Games between different conferences will be count $615$ in this number. Let's think western team as vertex. So we can get rid of this number of games from western teams, it will be $82x-615$ which means the sum of the degrees of all the western. As edges between vertexes mean games between teams, $82x-615$ will be twice the number of games played between western teams.
21.06.2017 19:58
Hope it is correct: We know in each gragh there are exactly even number of edges with degree odd. We can construct a graph such that its vertexes are the teams and we draw an edge between two teams if they have played with each other (it may be more than one edge between two teams). Now let $A$ be the subgraph with western teams and name $B$ be the easterns We know that there is $615$ edges between $A$ , $B$ . By the following lemma we get that there are even number of vertexes in $A$ with odd degree and because of that the degree of each vertex is $82$ , each of these vertexes send odd number of edges to $B$ (In total even edges) so there must be an even number of edges between $A$,$B$, condraction
09.01.2018 05:08
This is a "parity" problem: Suppose on the contrary that the Bosses could configure an arrangement for the 30 teams that satisfies the problem's conditions. Let the Western Conference have $a$ teams, and the Eastern conference have $30-a$ teams. Assign the kth team with a coordinate pair $(i_k, 82-i_k)$ where the first coordinate is the number of games the team plays within its conference, and the second coordinate is the number of games the team plays with teams of the other conference. Note that $2 \mid \sum_{t=1}^{a} i_t$, and $2 \mid \sum_{t=a+1}^{30} i_t$ since each game within the conference adds two to the intra-game total count [1 per each team in that in-conference game]. Hence it follows that $2 \mid \sum_{t=1}^{a} 82-i_t$ and $2 \mid \sum_{t=a+1}^{30} 82-i_t$. But since each interconference game adds one to the inter-game total count for each conference, $\sum_{t=1}^{a} 82-i_t = \sum_{t=a+1}^{30} 82-i_t$. Then $4 \mid \sum_{t=1}^{a} 82-i_t + \sum_{t=a+1}^{30} 82-i_t$, which is a contradiction since $ \sum_{t=1}^{a} 82-i_t + \sum_{t=a+1}^{30} 82-i_t$ = $\frac{30\cdot 82}{2}$ is not a multiple of 4.
29.05.2020 00:49
The answer is no. Let $S$ be the difference between the total number of intra-conference and inter-conference games; we want $S=0$. Initially, suppose all the teams are in one conference. Then $S=15\cdot 82 \equiv 2 \pmod4$. Suppose we have some configuration of teams, and we move team $i$ across conferences. Say team $i$ had $x_i$ intra-conference games and $82-x_i$ inter-conference games before moving. After moving, it has $82-x_i$ intra-conference games and $x_i$ inter-conference games. So $S$ changed by $2(82-2x_i) \equiv 0 \pmod4$. Therefore, $S \equiv 2 \pmod 4$ is invariant, and hence can never be 0.