An online store is selling rings, necklaces, bracelets, and pendants. Suppose there are $m$ different types of each of these four commodities. A typical customer wants to buy one item of each of the four products, where for each item she has a subset of $\frac{m}{3}$ of the corresponding types and is equally happy with any of them. Prove that there is a scheme that enables each such customer to send the store at most $\log_2 m + 10$ bits (for each possible collection of $\frac{m}{3}$ types of each item), enabling the store to satisfy her request.
My ideas are as follows: we have $4$ different commodities and for each commodity, the customer will be happy with a third of the types. If we index every type for each commodity from $1$ to $m$, let's say that the customer is happy with a certain subset of the indices for each commodity. By Pigeonhole principle, at least two of the commodities will share at least one index of a type that the customer will like. Considering this scenario, I tried to minimize the number of bits required, but could not get to a tight enough bound that is $\log_2 m + 10$. Any ideas on how to proceed? May also be helpful to consider the types as vertices on a graph.
I think a random approach works here.
Let $A_i$ denote the sets of all types of commodity $i$ for $i\in\{1,2,3,4\}$. Then $|A_i|=m$ for all $i$. Let $A=A_1\times A_2 \times A_3\times A_4$ and consider a random subset $K$ of $A$ with $k=1024m$ elements. Here each such subset $K$ is chosen with probability $p=1/\binom{|A|}{k}=1/\binom{m^4}{1024m}$.
For every collection $B_1, B_2, B_3, B_4$ of subsets of $A_1,A_2,A_3,A_4$ with $|B_i|=m/3$ let $B=B_1\times B_2\times B_3\times B_4$ and consider a probability $p_0$ that we have $B\cap K=\emptyset$. This probability is equal to number of subsets of size $k$ of $A\setminus B$ divided by the total number of sets of size $k$ chosen from $A$. So
$$p_0=\binom{|A\setminus B|}{k}/\binom{|A|}{k}=\binom{m^4-m^4/81}{1024m}/{\binom{m^4}{1024m}}< (80/81)^{1024m}.$$
Here in the last inequality expand the binomials and use that $x/y> (x-1)/(y-1)$ when $x<y$.
From this you have $p_0<(0.000003)^m$. So the probability that a random chosen $K$ does not intersect a given $B_1\times \cdots \times B_4$ is tiny.
Now, there are $N=\binom{m}{m/3}^4\leq (2^m)^4$ possible choices for $B_1,\ldots B_4$, so let $C_1,\ldots, C_N$ be the events that the corresponding choice of $B_1,\ldots,B_4$ has an empty intersection with $K$. Then $\mathbb{P}(C_i)=p_0$ for all $i$, and $$\mathbb{P}(\cup C_i)\leq \sum \mathbb{P}(C_i)=p_0N\leq (3\cdot 10^{-6})^m \cdot 16^m<1.$$
So probability that at least one $C_i$ happens is bounded away from 1, and so the probability that none of $C_i$ happens is positive. We now "derandomize": since the probability of none of $C_i$'s happening is positive, there is some choice of $K$ such that for all choices of $B_1,\ldots B_4$ the intersection $B_1\times B_2\times B_3\times B_4$ with $K$ is nonempty.
Now fix such a $K$ and enumerate elements of $K$ with numbers $\{1, \ldots, 1024m\}$. If the customer has a preference $B_1, \ldots, B_4$, then there is an element $k\in K$ such that $k\in B_1\times \cdots \times B_4$. Customer then send the index of the element $k$ to the store.
What course/book is this from?