Graph-like problem

Question

Each shop in a town has an odd number of customers and each pair of shops shares an even number of customers. Prove that there are at least as many customers as there are shops.

Any hints are appreciated.

Answer 1

This is a folklore problem, and the usual solution involves linear algebra. Let's denote the number of shops and customers by $n$ and $m$ respectively.

Hint 1:

Let the signature of a shop be a $0/1$ vector of length $m$, where $1$ indicates that the relevant person is a customer of that shop. Notice that if the vectors are interpreted as elements of $\mathbb{F}_2^m$, then \begin{align}\langle v_i,v_i\rangle &= 1,\\\langle v_i,v_j\rangle &= 0,\end{align} where $\langle x,y\rangle$ denotes the dot product of $x$ and $y$.

Hint 2:

In fact they are all together independent: \begin{align}\left\langle\sum_{i}a_iv_i,v_k\right\rangle = \langle a_kv_k,v_k\rangle = a_k\langle v_k,v_k\rangle = a_k\end{align} so \begin{align} \sum_{i}a_iv_i = \mathbf{0} \implies a_k = \langle\mathbf{0},v_k\rangle = 0 \text{ for all } k.\end{align}

Hint 3:

If vector space has $n$ linearly independent vectors, then the dimension of that space must be at least $n$. Dimension of our space is $m$, hence $m \geq n$.

I hope this helps $\ddot\smile$