Bound on the size of a set of a collection of functions from $[n]$ to $\mathbb{Z}$

Question

I'm trying to solve the following problem:

Let $\mathcal{A}$ be a collection of functions from $[n]$ to $\mathbb{Z}$ such that for each distinct function $f, g \in \mathcal{A}$ there is an $i \in [n]$ with $f(i) = g(i) + 1$. Prove that $|\mathcal{A}| \le 2^n$.

I'm trying to replicate some sort of combinatorial proof that would involve finding a linearly independent set of $n$ polynomials that spans $\mathcal{A}$, so I could then get the result (this is based on a hint I've been given).

But I'm not sure how to go about this, can somebody help?

Answer 1

For $f\in \mathcal A$ consider parity of $f(i)$, which produces a new mapping $i \to f(i) \mod 2$. There are only $2^n$ such mappings, so if $|\mathcal A|>2^n$ then, by the pigeonhole principle, two different functions $f,g \in\mathcal A$ map to the same mapping, i.e. have the same parity on all $i\in [n]$. This contradicts the condition that, for some $i$, they differ by 1.