There are $n$ MOPpers $p_1,...,p_n$ designing a carpool system to attend their morning class. Each $p_i$'s car fits $\chi (p_i)$ people ($\chi : \{p_1,...,p_n\} \to \{1,2,...,n\}$). A $c$-fair carpool system is an assignment of one or more drivers on each of several days, such that each MOPper drives $c$ times, and all cars are full on each day. (More precisely, it is a sequence of sets $(S_1, ...,S_m)$ such that $|\{k: p_i\in S_k\}|=c$ and $\sum_{x\in S_j} \chi(x) = n$ for all $i,j$. ) Suppose it turns out that a $2$-fair carpool system is possible but not a $1$-fair carpool system. Must $n$ be even? Proposed by Nathan Ramesh and Palmer Mebane
Problem
Source: 2017 ELMO Shortlist C5
Tags: combinatorics
03.07.2017 05:13
12.12.2023 05:38
the answer is no. use 1, 7, 17, 23, 100, 101, 113, 132, 247, 247, ..., 247 2-fair because you can use [1, 1, 113, 132] [7, 7, 101, 132] [17, 17, 100, 113] [23, 23, 100, 101] [247] ... [247] not 1-fair because you can check each combination of two numbers in {100, 101, 113, 132} and none of them can be added with some subset of small numbers to give a sum of 247.
22.10.2024 17:29
CyclicISLscelesTrapezoid wrote: the answer is no. use 1, 7, 17, 23, 100, 101, 113, 132, 247, 247, ..., 247 2-fair because you can use [1, 1, 113, 132] [7, 7, 101, 132] [17, 17, 100, 113] [23, 23, 100, 101] [247] ... [247] not 1-fair because you can check each combination of two numbers in {100, 101, 113, 132} and none of them can be added with some subset of small numbers to give a sum of 247. I believe this is wrong because one person can't drive twice on the same day. Nonconstructive carpool system We consider summing car capacities instead of where each Mopper is. Define an $(m,\chi,C)$ carpool system for multiset $C = \{c_1, \dots, c_k\}$, integral function $\chi$, and integer $m$ as one with $m$ moppers and the sum of the car capacities for Moppers in $S_j$ is $c_j$. We claim that any counterexample where $(m,\chi, 2C)$ is fair but $(m, \chi, C)$ isn't works. Claim: We can instead find an example with any number of Moppers such that the $2$-fair carpool system has an even number of columns. Proof. Suppose we have a counterexample with $m$ moppers instead of $n$. Let $m$ be the number of Moppers and let our $2$-fair carpool system have $2k$ days (which follows if odd / given). Then fix a large odd $N > m+k+2n$ and add $k$ cars with capacity $N - n$ and $N - k - m$ cars with capacity $N$. Call these new cars large cars. Then we can see that any $c$-fair configuration including these larger cars summing to $N$ reduces to one without them summing to $n$, as no two large cars go together. $\blacksquare$ Claim: We can generalize our required day capacities to any multiset $C$. Proof. We fix large odd $N > m + |C| + 2n$ and add $|C|$ cars with capacities $N - c_i$. $\blacksquare$ Claim: We can generalize our car capacities to reals and $\chi, C$ similarly. Proof. We first reduce to positive reals. Let the vector space over linear combinations of outputs of $\chi$ not containing $\alpha$. We replace each $\chi(p_i)$ with $\chi(p_i) + \alpha$ and $c_j \coloneqq c_j + |S_j| \alpha$. Taking large $\alpha$ suffices. Then to finish we repeatedly consider the carpool system we get by truncating $10^N\chi(p_i)$ for large $N$. Since there are finitely many potential $1$-fair carpool systems compared to $C$, we can take a large enough $N$ such that each such carpool system differs from $C$ before the $N$th digit. $\blacksquare$ Now fix $\alpha_1, \alpha_2, \dots$ as a hamel basis of $\mathbb{R}$. Take $n = 1434$ and $N > 4n^2$. Take $2n$ vectors $v_1, v_2, \dots, v_{2n}$ in $\mathbb{Z}^N$ which consist of only $0$s and $1$s that sum to the vector $(2, 2, 2, \dots, 2)$ such that any two of them share a component upon which they are both $1$. This implies linear independence. This can be done by making it so that any two vectors $v_i$ are both one on some component. Let these $n$ vectors span $V$. We now take our vector $\chi = \langle \chi(1)\ \chi(2)\ \dots \chi(n) \rangle$ in order such that \[ \chi \cdot v_j = \alpha_{\left\lfloor \frac{j}{2} \right\rfloor} = \chi(1) v_{j1} + \chi(2) v_{j2} + \dots + \chi(n) v_{n2} = 0 \]so that this gives us a valid $2$-fair system by taking $S_i$ as the components of $v_i$ which are nonzero. Claim: If $v$ is a vector in $\mathbb{Z}^n$ that isn't $v_1, \dots, v_{2n}$ but also consists of only $0$s and $1$s, we can fix our system such that $v \cdot \chi \not\in \{\alpha_1, \dots, \alpha_n\}$. Proof. Let these remaining vectors $v_{2n+1}, \dots, v_{2^{2n}}$ Let $V = \mathbb{Z}^N$ be the span of all these vectors, and order these vectors such that $v_1, \dots, v_N$ form a basis of $V$. Now we extend our constraints such that $\chi \cdot v_k = \alpha_k$ for $1 \le k \le N$. This means that our result holds by definition for $2n+1 \le k \le N$. For $k > N$, since $v_{k}$ is in $V$, we have that for some coefficients $c_i$ that \[ c_1v_1 + c_2v_2 \dots + c_{N}v_{N} = v_k \]Taking $\chi \cdot (\bullet)$ of both sides, this becomes \[ c_1\alpha_1 + c_2\alpha_2 + \dots + c_{N}\alpha_N= \chi \cdot v_{k} \]If $\chi \cdot v_{i+1} = \alpha_t$ for some $1 \le t \le 2n$, then this implies by the linear independence of $\{\alpha_i\}_i$ that $c_i = \delta_{t}(i)$ so $v_{i+1} = v_t$, contradiction. $\blacksquare$ This implies that in this carpool system, any $1$-fair carpool system with the same $\chi$ and days $T_i$ for $1 \le i \le n$, we have that $T_i \in \{S_1, \dots, S_{2n}\}$. Except this is obviously impossible, as any two $S_i, S_j$ share a car in both of them. Remark: With some more work we can actually get that for all sufficiently large $N$, there is a configuration of $N$ Moppers which is $c$-fair for all $c \ge 2$ but not $1$-fair.