Let $A=\{a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_n\}$ be a set with $2n$ distinct elements, and $B_i\subseteq A$ for any $i=1,2,\cdots,m.$ If $\bigcup_{i=1}^m B_i=A,$ we say that the ordered $m-$tuple $(B_1,B_2,\cdots,B_m)$ is an ordered $m-$covering of $A.$ If $(B_1,B_2,\cdots,B_m)$ is an ordered $m-$covering of $A,$ and for any $i=1,2,\cdots,m$ and any $j=1,2,\cdots,n,$ $\{a_j,b_j\}$ is not a subset of $B_i,$ then we say that ordered $m-$tuple $(B_1,B_2,\cdots,B_m)$ is an ordered $m-$covering of $A$ without pairs. Define $a(m,n)$ as the number of the ordered $m-$coverings of $A,$ and $b(m,n)$ as the number of the ordered $m-$coverings of $A$ without pairs. $(1)$ Calculate $a(m,n)$ and $b(m,n).$ $(2)$ Let $m\geq2,$ and there is at least one positive integer $n,$ such that $\dfrac{a(m,n)}{b(m,n)}\leq2021,$ Determine the greatest possible values of $m.$
Problem
Source:
Tags: combinatorics, set
11.11.2021 17:05
(1) To calculate $a(m,n)$, we just consider one element $e$. $e$ must belong to some number of sets, and the number of ways is $2^m-1$, as $e$ can be in $B_i$ or not for all $i=1,2,\dots,m$, giving $2^m$ ways. But we have to subtract 1 to discount the possibility that $e$ is not in any of the sets. Thus, repeating the process for all $2n$ elements, we have \[a(m,n)=(2^m-1)^{2n}.\]To calculate $b(m,n)$, we consider a pair of elements $(a_i,b_i)$. First we suppose $a_i$ belongs in $k$ sets. There are $\binom{m}{k}$ ways to choose the $k$ sets. $b_i$ must belong in the other $m-k$ sets, and we may assign it in $2^{m-k}-1$ ways. It follows that \[b(m,1)=\sum_{k=1}^{m-1}\binom{m}{k}(2^{m-k}-1)=3^m-2^m-2^m+1=3^m-2^{m+1}+1,\]where we have evaluated the sum using the binomial formula. Thus, \[b(m,n)=\left(3^m-2^{m+1}+1\right)^n.\] (2) We calculate the least value of $m$ such that $\frac{a(m,1)}{b(m,1)}>2021$. Noting that $\frac{a(m,1)}{b(m,1)}\sim \frac{4}{3}$, we try $m=27$ as the least integer such that $\left(\frac{4}{3}\right)^m>2021$ is $m=27$. It turns out for $m=27$, the fraction evaluates to $2362.44\dots$, which is larger than $2021$, but for $m=26$, the fraction evaluates to $1771.86\dots$. Thus, the desired value of $m$ is 26.