Optimization problem for routes

Question

Let a group of farms each have a $p$-letter name. No two farms have the same name, however, and they all only consist of x's and z's. For example, if $p=2$, then xx, zz, xz, zx are the farms in the state. Bus rides take farmers from farm to farm but they only have routes from and to farms that differ in name by exactly one letter. For example, there is a bus ride connecting xx and xz. The state has stores on different farms.

(a) If the state government only places stores on farms in a way as to allow farms access to one store via a single bus ride, what, in terms of $p$, can the max number of stores that the state has in total be?

(b) If the government instead wants every farm to have access via a single bus ride or less to a store, what is the minimum number of stores, in terms of $p$, that the state can have in total?

Answer 1

I believe this is in general an open problem. Each store is either on or adjacent to a total of $p+1$ farms, so if no farm can access a multiple stores, then there will be at most $$ \frac{2^p}{p+1} $$ stores. Similarly, if every farm can access at least one store, there will be at least that many stores.

If $p+1$ is a power of two, then that number is an integer, and it can be attained for both problems.

Assume $p+1=2^n$. Consider a particular farm. Let $b_i$ be a sequence of $p$ numbers, each $0$ or $1$ according to whether the $i^{th}$ letter of that farm's name is $z$ or $x$. Furthermore, let $v_1,v_2,\dots,v_p$ be a list without repeats of the nonzero vectors in $\mathbb F_2^n$ (vectors of length $n$ with entries in $\{0,1\}$, with addition and scaling coordinate-wise $\pmod 2$). Note there are $2^n-1=p$ such vectors. Then that farm will be labeled with the vector $$ \sum_{i=1}^p b_iv_i\in \mathbb F_2^n $$ Perform this labeling for every farm. The farms labeled with the zero vector will be the ones who are given a store. You can show that exactly $2^{p-n}$ vectors are given a store, and every farm will either have a store or be adjacent to exactly one store.

When $p+1$ is not a power of two, I believe it is as of yet an open problem to determine the optimal packing and covering numbers. An upper (lower) bound is given by rounding $2^p/(p+1)$ down (up) to the nearest integer. For the best known packing numbers for various values of $p$, see the first column of the table in https://www.win.tue.nl/~aeb/codes/binary-1.html. The number in the row labeled $q$ gives the largest number of non-overlapping stores you can have when $p=q-1$. For example, for farms with names of length $p=18$, you can have at least $10496$ but certainly no more than $13104$ stores.