% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{needspace}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
\usepackage{tabu}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, September 13, 2015 21:58:30}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{TODO}
\newenvironment{todo}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{obsolete}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{obsolete}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{At least $\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert
S\right\vert -1\right)  $ frontiers}
\ohead{\today}
\begin{document}

\title{At least $\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert S\right\vert
-1\right)  $ frontiers: a graph theory problem}
\author{Darij Grinberg}
\date{\today\ (modified version of a note from 2009)}
\maketitle

\section{Problem}

Let $S$ be a finite set. Let $k$ be a positive integer. Let $A$ be a subset of
$S^{k}$ satisfying $\left\vert A\right\vert =\left\vert S\right\vert ^{k-1}$.
Let $B=S^{k}\setminus A$.

For every $v\in S^{k}$ and every $i\in\left\{  1,2,\ldots,k\right\}  $, we
denote by $v_{i}$ the $i$-th component of the $k$-tuple $v$ (remember that $v$
is an element of $S^{k}$, that is, a $k$-tuple of elements of $S$). Then,
every $v\in S^{k}$ satisfies $v=\left(  v_{1},v_{2},\ldots,v_{k}\right)  $.

Let $F$ be the set of all pairs $\left(  a,b\right)  \in A\times B$ for which
there exists an $i\in\left\{  1,2,\ldots,k\right\}  $ satisfying $\left(
a_{j}=b_{j}\text{ for all }j\neq i\right)  $\ \ \ \ \footnote{Of course,
\textquotedblleft for all $j\neq i$\textquotedblright\ means \textquotedblleft
for all $j\in\left\{  1,2,\ldots,k\right\}  $ satisfying $j\neq i$%
\textquotedblright\ here.}. (Speaking less formally, let $F$ be the set of all
pairs $\left(  a,b\right)  \in A\times B$ for which the $k$-tuples $a$ and $b$
differ in at most one position.)

Prove that $\left\vert F\right\vert \geq\left\vert S\right\vert ^{k-1}%
\cdot\left(  \left\vert S\right\vert -1\right)  $.

\section{Remark}

In the case $\left\vert S\right\vert =2$, this is an old problem (which
appeared, for example, in a Moscow MO 1962 preparation booklet, and which is a
particular case of Cheeger's inequality for the hypercube).

I use to call the elements of $F$ \textquotedblleft
frontiers\textquotedblright\ between the sets $A$ and $B$.

\section{Solution}

\begin{noncompile}
Only the vershort version of this solution has been proofread!
\end{noncompile}

Since $A\subseteq S^{k}$ and $B=S^{k}\setminus A$, we have $A\cap
B=\varnothing$ and $A\cup B=S^{k}$. Hence, $S^{k}\setminus B=A$.

Define a map $\phi:A\times B\rightarrow F$ as follows:

\begin{vershort}
Let $\left(  u,v\right)  \in A\times B$ be a pair. Then, $u\in A$ and $v\in
B$, so that $u\notin B$ and $v\notin A$ (since $A\cap B=\varnothing$).
\end{vershort}

\begin{verlong}
Let $\left(  u,v\right)  \in A\times B$ be a pair. Then, $u\in A$ and $v\in
B$, so that $u\notin B$\ \ \ \ \footnote{\textit{Proof.} From $u\in
A=S^{k}\setminus B$, we obtain $u\in S^{k}$ and $u\notin B$. This proves
$u\notin B$} and $v\notin A$\ \ \ \ \footnote{\textit{Proof.} From $v\in
B=S^{k}\setminus A$, we obtain $v\in S^{k}$ and $v\notin A$. This proves
$v\notin A$.}.
\end{verlong}

\begin{vershort}
We define a subset $T$ of $\left\{  0,1,2,\ldots,k\right\}  $ by%
\[
T=\left\{  i\in\left\{  0,1,2,\ldots,k\right\}  \mid\left(  v_{1},v_{2}%
,\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B\right\}
\]
\footnote{For $i=0$, the notation $\left(  v_{1},v_{2},\ldots,v_{i}%
,u_{i+1},u_{i+2},\ldots,u_{k}\right)  $ means $\left(  u_{1},u_{2}%
,\ldots,u_{k}\right)  $.
\par
For $i=k$, the notation $\left(  v_{1},v_{2},\ldots,v_{i},u_{i+1}%
,u_{i+2},\ldots,u_{k}\right)  $ means $\left(  v_{1},v_{2},\ldots
,v_{k}\right)  $.}. Then, $0\notin T$ (since $\left(  u_{1},u_{2},\ldots
,u_{k}\right)  =u\notin B$) and $k\in T$ (since $\left(  v_{1},v_{2}%
,\ldots,v_{k}\right)  =v\in B$). In particular, $k\in T$ yields $T\neq
\varnothing$. Thus, the set $T$ has a minimal element (since $T$ is a finite
set). Let $\alpha$ be this minimal element. Then, $\alpha\in T$ and
$\alpha-1\notin T$. We have $\alpha\neq0$ (since $\alpha\in T$ but $0\notin
T$). Thus, $\alpha-1\in\left\{  0,1,2,\ldots,k\right\}  $ (since $\alpha\in
T\subseteq\left\{  0,1,2,\ldots,k\right\}  $).
\end{vershort}

\begin{verlong}
We define a subset $T$ of $\left\{  0,1,2,\ldots,k\right\}  $ by%
\[
T=\left\{  i\in\left\{  0,1,2,\ldots,k\right\}  \mid\left(  v_{1},v_{2}%
,\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B\right\}
\]
\footnote{For $i=0$, the notation $\left(  v_{1},v_{2},\ldots,v_{i}%
,u_{i+1},u_{i+2},\ldots,u_{k}\right)  $ means $\left(  u_{1},u_{2}%
,\ldots,u_{k}\right)  $.
\par
For $i=k$, the notation $\left(  v_{1},v_{2},\ldots,v_{i},u_{i+1}%
,u_{i+2},\ldots,u_{k}\right)  $ means $\left(  v_{1},v_{2},\ldots
,v_{k}\right)  $.}. Then, $0\notin T$\ \ \ \ \footnote{\textit{Proof.} Assume
the contrary. Thus, $0\in T$, so that%
\[
0\in T=\left\{  i\in\left\{  0,1,2,\ldots,k\right\}  \mid\left(  v_{1}%
,v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B\right\}  .
\]
In other words, $0$ is an $i\in\left\{  0,1,2,\ldots,k\right\}  $ satisfying
$\left(  v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B$.
In other words, $0$ is an element of $\left\{  0,1,2,\ldots,k\right\}  $ and
satisfies $\left(  v_{1},v_{2},\ldots,v_{0},u_{0+1},u_{0+2},\ldots
,u_{k}\right)  \in B$. But $\left(  v_{1},v_{2},\ldots,v_{0},u_{0+1}%
,u_{0+2},\ldots,u_{k}\right)  =\left(  u_{1},u_{2},\ldots,u_{k}\right)  =u$,
so that $u=\left(  v_{1},v_{2},\ldots,v_{0},u_{0+1},u_{0+2},\ldots
,u_{k}\right)  \in B$. This contradicts $u\notin B$. This contradiction proves
that our assumption was wrong, qed.} and $k\in T$%
\ \ \ \ \footnote{\textit{Proof.} Clearly, $k$ is an element of $\left\{
0,1,2,\ldots,k\right\}  $ and satisfies $\left(  v_{1},v_{2},\ldots
,v_{k},u_{k+1},u_{k+2},\ldots,u_{k}\right)  =\left(  v_{1},v_{2},\ldots
,v_{k}\right)  =v\in B$. In other words, $k$ is an $i\in\left\{
0,1,2,\ldots,k\right\}  $ satisfying $\left(  v_{1},v_{2},\ldots,v_{i}%
,u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B$. In other words,%
\[
k\in\left\{  i\in\left\{  0,1,2,\ldots,k\right\}  \mid\left(  v_{1}%
,v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B\right\}  =T,
\]
qed.}. Hence, $T$ has at least one element (since $k\in T$), and thus we have
$T\neq\varnothing$. Thus, the set $T$ has a minimal element (since $T$ is a
finite set). Let $\alpha$ be this minimal element. Then, $\alpha$ is the
minimal element of $T$. In particular, $\alpha$ is an element of $T$. In other
words, $\alpha\in T$. Also, $\alpha-1\notin T$%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $\alpha-1\in T$.
\par
But $\alpha$ is the minimal element of $T$. Thus, every element $\beta$ of $T$
satisfies $\beta\geq\alpha$. Applying this to $\beta=\alpha-1$, we obtain
$\alpha-1\geq\alpha$ (since $\alpha-1$ is an element of $T$). But this
contradicts $\alpha-1<\alpha$. This contradiction shows that our assumption
was wrong. Qed.}. We have $\alpha\neq0$\ \ \ \ \footnote{\textit{Proof.} If we
had $\alpha=0$, then we would have $0=\alpha\in T$, which would contradict
$0\notin T$. Thus, we cannot have $\alpha=0$. In other words, we have
$\alpha\neq0$. Qed.}. Combining $\alpha\in T\subseteq\left\{  0,1,2,\ldots
,k\right\}  $ with $\alpha\neq0$, we obtain $\alpha\in\left\{  0,1,2,\ldots
,k\right\}  \setminus\left\{  0\right\}  =\left\{  1,2,3,\ldots,k\right\}  $.
Thus, $\alpha-1\in\left\{  0,1,2,\ldots,k-1\right\}  \subseteq\left\{
0,1,2,\ldots,k\right\}  $.

Recall that $F$ is defined as the set of all pairs $\left(  a,b\right)  \in
A\times B$ for which there exists an $i\in\left\{  1,2,\ldots,k\right\}  $
satisfying $\left(  a_{j}=b_{j}\text{ for all }j\neq i\right)  $. Therefore,
given some pair $\left(  a,b\right)  \in A\times B$, we have $\left(
a,b\right)  \in F$ if and only if there exists an $i\in\left\{  1,2,\ldots
,k\right\}  $ satisfying $\left(  a_{j}=b_{j}\text{ for all }j\neq i\right)
$. In other words, given some pair $\left(  a,b\right)  \in A\times B$, we
have the following logical equivalence:%
\begin{align}
&  \ \left(  \left(  a,b\right)  \in F\right) \nonumber\\
&  \Longleftrightarrow\ \left(  \text{there exists an }i\in\left\{
1,2,\ldots,k\right\}  \text{ satisfying }\left(  a_{j}=b_{j}\text{ for all
}j\neq i\right)  \right)  . \label{long.eq1}%
\end{align}

\end{verlong}

\begin{vershort}
Now, $\alpha\in T$ yields $\left(  v_{1},v_{2},\ldots,v_{\alpha},u_{\alpha
+1},u_{\alpha+2},\ldots,u_{k}\right)  \in B$, while $\alpha-1\notin T$ yields
$\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha},u_{\alpha+1},\ldots
,u_{k}\right)  \notin B$, so that $\left(  v_{1},v_{2},\ldots,v_{\alpha
-1},u_{\alpha},u_{\alpha+1},\ldots,u_{k}\right)  \in S^{k}\setminus B=A$. Set
$a=\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha},u_{\alpha+1}%
,\ldots,u_{k}\right)  $ and \newline$b=\left(  v_{1},v_{2},\ldots,v_{\alpha
},u_{\alpha+1},u_{\alpha+2},\ldots,u_{k}\right)  $. Then, $a=\left(
v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha},u_{\alpha+1},\ldots,u_{k}\right)
\in A$ and \newline$b=\left(  v_{1},v_{2},\ldots,v_{\alpha},u_{\alpha
+1},u_{\alpha+2},\ldots,u_{k}\right)  \in B$, so that $\left(  a,b\right)  \in
A\times B$. Besides, there exists an $i\in\left\{  1,2,\ldots,k\right\}  $
satisfying $\left(  a_{j}=b_{j}\text{ for all }j\neq i\right)  $ (namely,
$i=\alpha\ \ \ \ $\footnote{In fact, $a_{j}=b_{j}$ for all $j\neq\alpha$ (in
fact, for any $j,$ we have $a_{j}=\left\{
\begin{array}
[c]{c}%
v_{j},\text{ if }j<\alpha;\\
u_{j},\text{ if }j\geq\alpha
\end{array}
\right.  $ and $b_{j}=\left\{
\begin{array}
[c]{c}%
v_{j},\text{ if }j\leq\alpha;\\
u_{j},\text{ if }j>\alpha
\end{array}
\right.  $; thus, if $j\neq\alpha$, this simplifies to $a_{j}=\left\{
\begin{array}
[c]{c}%
v_{j},\text{ if }j<\alpha;\\
u_{j},\text{ if }j>\alpha
\end{array}
\right.  $ and $b_{j}=\left\{
\begin{array}
[c]{c}%
v_{j},\text{ if }j<\alpha;\\
u_{j},\text{ if }j>\alpha
\end{array}
\right.  $, so that $a_{j}=b_{j}$ for all $j\neq\alpha$).}). Hence, $\left(
a,b\right)  \in F$ (by the definition of $F$).
\end{vershort}

\begin{verlong}
Now, set $a=\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha},u_{\alpha
+1},\ldots,u_{k}\right)  $ and $b=\left(  v_{1},v_{2},\ldots,v_{\alpha
},u_{\alpha+1},u_{\alpha+2},\ldots,u_{k}\right)  $. Then, $a\in A$%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $a\notin A$.
Combining $a\in S^{k}$ with $a\notin A$, we obtain $a\in S^{k}\setminus A=B$.
\par
Now, $\alpha-1\in\left\{  0,1,2,\ldots,k\right\}  $ and $\left(  v_{1}%
,v_{2},\ldots,v_{\alpha-1},u_{\left(  \alpha-1\right)  +1},u_{\left(
\alpha-1\right)  +2},\ldots,u_{k}\right)  =\left(  v_{1},v_{2},\ldots
,v_{\alpha-1},u_{\alpha},u_{\alpha+1},\ldots,u_{k}\right)  =a\in B$. Thus,
$\alpha-1$ is an element of $\left\{  0,1,2,\ldots,k\right\}  $ and satisfies
$\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\left(  \alpha-1\right)
+1},u_{\left(  \alpha-1\right)  +2},\ldots,u_{k}\right)  \in B$. In other
words, $\alpha-1$ is an $i\in\left\{  0,1,2,\ldots,k\right\}  $ satisfying
$\left(  v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B$.
In other words,%
\[
\alpha-1\in\left\{  i\in\left\{  0,1,2,\ldots,k\right\}  \mid\left(
v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B\right\}
=T.
\]
This contradicts $\alpha-1\notin T$. This contradiction proves that our
assumption was wrong, qed.} and $b\in B$\ \ \ \ \footnote{\textit{Proof.} We
have%
\[
\alpha\in T=\left\{  i\in\left\{  0,1,2,\ldots,k\right\}  \mid\left(
v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B\right\}
.
\]
In other words, $\alpha$ is an $i\in\left\{  0,1,2,\ldots,k\right\}  $
satisfying $\left(  v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots
,u_{k}\right)  \in B$. In other words, $\alpha$ is an element of $\left\{
0,1,2,\ldots,k\right\}  $ and satisfies $\left(  v_{1},v_{2},\ldots,v_{\alpha
},u_{\alpha+1},u_{\alpha+2},\ldots,u_{k}\right)  \in B$. Thus, $b=\left(
v_{1},v_{2},\ldots,v_{\alpha},u_{\alpha+1},u_{\alpha+2},\ldots,u_{k}\right)
\in B$, qed.}. Combining $a\in A$ and $b\in B$, we obtain $\left(  a,b\right)
\in A\times B$. Besides, for every $j\in\left\{  1,2,\ldots,k\right\}  $
satisfying $j\neq\alpha$, we have $a_{j}=b_{j}$%
\ \ \ \ \footnote{\textit{Proof.} Let $j\in\left\{  1,2,\ldots,k\right\}  $ be
such that $j\neq\alpha$. We must prove that $a_{j}=b_{j}$.
\par
We recall that $a=\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha}%
,u_{\alpha+1},\ldots,u_{k}\right)  $. Hence, for every $p\in\left\{
1,2,\ldots,k\right\}  $, we have%
\begin{equation}
a_{p}=%
\begin{cases}
v_{p}, & \text{if }p\leq\alpha-1;\\
u_{p}, & \text{if }p>\alpha-1
\end{cases}
. \label{long.fn1.eq1}%
\end{equation}
\par
Also, $b=\left(  v_{1},v_{2},\ldots,v_{\alpha},u_{\alpha+1},u_{\alpha
+2},\ldots,u_{k}\right)  $. Hence, for every $p\in\left\{  1,2,\ldots
,k\right\}  $, we have%
\begin{equation}
b_{p}=%
\begin{cases}
v_{p}, & \text{if }p\leq\alpha;\\
u_{p}, & \text{if }p>\alpha
\end{cases}
. \label{long.fn1.eq2}%
\end{equation}
\par
Now, we have $j\neq\alpha$. Thus, either $j<\alpha$ or $j>\alpha$. Therefore,
we must be in one of the following two Cases:
\par
\textit{Case 1:} We have $j<\alpha$.
\par
\textit{Case 2:} We have $j>\alpha$.
\par
Let us consider Case 1 first. In this case, we have $j<\alpha$. Hence,
$j\leq\alpha-1$ (since $j$ and $\alpha$ are integers) and $j\leq\alpha$ (since
$j<\alpha$). Now, (\ref{long.fn1.eq1}) (applied to $p=j$) yields $a_{j}=%
\begin{cases}
v_{j}, & \text{if }j\leq\alpha-1;\\
u_{j}, & \text{if }j>\alpha-1
\end{cases}
=v_{j}$ (since $j\leq\alpha-1$). Also, (\ref{long.fn1.eq2}) (applied to $p=j$)
yields $b_{j}=%
\begin{cases}
v_{j}, & \text{if }j\leq\alpha;\\
u_{j}, & \text{if }j>\alpha
\end{cases}
=v_{j}$ (since $j\leq\alpha$). Thus, $a_{j}=v_{j}=b_{j}$. Hence, $a_{j}=b_{j}$
is proven in Case 1.
\par
Let us now consider Case 2. In this case, we have $j>\alpha$. Hence,
$j>\alpha>\alpha-1$. Now, (\ref{long.fn1.eq1}) (applied to $p=j$) yields
$a_{j}=%
\begin{cases}
v_{j}, & \text{if }j\leq\alpha-1;\\
u_{j}, & \text{if }j>\alpha-1
\end{cases}
=u_{j}$ (since $j>\alpha-1$). Also, (\ref{long.fn1.eq2}) (applied to $p=j$)
yields $b_{j}=%
\begin{cases}
v_{j}, & \text{if }j\leq\alpha;\\
u_{j}, & \text{if }j>\alpha
\end{cases}
=u_{j}$ (since $j>\alpha$). Thus, $a_{j}=u_{j}=b_{j}$. Hence, $a_{j}=b_{j}$ is
proven in Case 2.
\par
We have now proven $a_{j}=b_{j}$ in each of the two Cases 1 and 2. Since these
two Cases cover all possibilities, this shows that $a_{j}=b_{j}$ always holds.
The proof of $a_{j}=b_{j}$ is thus complete.}. In other words, $\left(
a_{j}=b_{j}\text{ for all }j\neq\alpha\right)  $. Thus, there exists an
$i\in\left\{  1,2,\ldots,k\right\}  $ satisfying $\left(  a_{j}=b_{j}\text{
for all }j\neq i\right)  $ (namely, $i=\alpha$). Hence, $\left(  a,b\right)
\in F$\ \ \ \ \footnote{\textit{Proof.} From the equivalence (\ref{long.eq1}),
we know that $\left(  a,b\right)  \in F$ holds if and only if there exists an
$i\in\left\{  1,2,\ldots,k\right\}  $ satisfying $\left(  a_{j}=b_{j}\text{
for all }j\neq i\right)  $. Therefore, $\left(  a,b\right)  \in F$ holds
(since there exists an $i\in\left\{  1,2,\ldots,k\right\}  $ satisfying
$\left(  a_{j}=b_{j}\text{ for all }j\neq i\right)  $). Qed.}.
\end{verlong}

Now set $\phi\left(  u,v\right)  =\left(  a,b\right)  $. Thus we have defined
a map $\phi:A\times B\rightarrow F$.

\begin{vershort}
Next, we will prove that $\left\vert \phi^{-1}\left(  \left\{  \left(
a,b\right)  \right\}  \right)  \right\vert \leq\left\vert S\right\vert ^{k-1}$
for every $\left(  a,b\right)  \in F$. In fact, let $\left(  a,b\right)  \in
F$. Since $\left(  a,b\right)  \in F$, we have $\left(  a,b\right)  \in
A\times B$, so that $a\in A$ and $b\in B,$ so that $a\neq b$ (since $A\cap
B=\varnothing$). But since $\left(  a,b\right)  \in F$,%
\begin{equation}
\text{there exists an }i\in\left\{  1,2,\ldots,k\right\}  \text{ satisfying
}\left(  a_{j}=b_{j}\text{ for all }j\neq i\right)  . \label{1}%
\end{equation}
Consider this $i$.

We must have $a_{i}\neq b_{i}$\ \ \ \ \footnote{In fact, otherwise, we would
have $a_{i}=b_{i},$ what, combined with $a_{j}=b_{j}$ for all $j\neq i,$ would
yield $a_{j}=b_{j}$ for all $j\in\left\{  1,2,\ldots,k\right\}  ,$ so that
$a=b,$ contradicting $a\neq b.$}.

Now, consider some $\left(  u,v\right)  \in\phi^{-1}\left(  \left\{  \left(
a,b\right)  \right\}  \right)  $. Then, $\phi\left(  u,v\right)  =\left(
a,b\right)  $. Thus, by the definition of $\phi$, there exists an $\alpha
\in\left\{  0,1,2,\ldots,k\right\}  $ such that%
\begin{equation}
a=\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha},u_{\alpha+1},\ldots
,u_{k}\right)  \ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ b=\left(
v_{1},v_{2},\ldots,v_{\alpha},u_{\alpha+1},u_{\alpha+2},\ldots,u_{k}\right)  .
\label{2}%
\end{equation}
Consider this $\alpha$.

We must have $u_{\alpha}\neq v_{\alpha}$\ \ \ \ \footnote{because otherwise,
we would have $u_{\alpha}=v_{\alpha}$ and thus%
\[
a=\left(  v_{1},v_{2},\ldots,v_{\alpha-1},\underbrace{u_{\alpha}}_{=v_{\alpha
}},u_{\alpha+1},\ldots,u_{k}\right)  =\left(  v_{1},v_{2},\ldots,v_{\alpha
},u_{\alpha+1},u_{\alpha+2},\ldots,u_{k}\right)  =b,
\]
contradicting $a\neq b.$}. Since $a_{\alpha}=u_{\alpha}$ and $b_{\alpha
}=v_{\alpha}$, this yields $a_{\alpha}\neq b_{\alpha}$. Hence, $\alpha=i$
(since otherwise, we would have $\alpha\neq i$, so that $a_{\alpha}=b_{\alpha
}$ by (\ref{1}), contradicting $a_{\alpha}\neq b_{\alpha}$). Thus, (\ref{2})
becomes%
\[
a=\left(  v_{1},v_{2},\ldots,v_{i-1},u_{i},u_{i+1},\ldots,u_{k}\right)
\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ b=\left(  v_{1},v_{2}%
,\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  .
\]


Now, $a=\left(  v_{1},v_{2},\ldots,v_{i-1},u_{i},u_{i+1},\ldots,u_{k}\right)
$ yields $a_{j}=u_{j}$ for all $j\geq i$. Hence,%
\begin{align}
u  &  =\left(  u_{1},u_{2},\ldots,u_{i-1},u_{i},u_{i+1},\ldots,u_{k}\right)
=\left(  u_{1},u_{2},\ldots,u_{i-1},a_{i},a_{i+1},\ldots,a_{k}\right)
\nonumber\\
&  \in S^{i-1}\times\left\{  a_{i}\right\}  \times\left\{  a_{i+1}\right\}
\times\cdots\times\left\{  a_{k}\right\}  . \label{3}%
\end{align}
\footnote{By abuse of notation, we are writing $S^{i-1}\times\left\{
a_{i}\right\}  \times\left\{  a_{i+1}\right\}  \times\cdots\times\left\{
a_{k}\right\}  $ for $\underbrace{S\times S\times\cdots\times S}_{i-1\text{
factors}}\times\left\{  a_{i}\right\}  \times\left\{  a_{i+1}\right\}
\times\cdots\times\left\{  a_{k}\right\}  $ here.}

Also, $b=\left(  v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)
$ yields $b_{j}=v_{j}$ for all $j\leq i$. Hence,%
\begin{align}
v  &  =\left(  v_{1},v_{2},\ldots,v_{i},v_{i+1},v_{i+2},\ldots,v_{k}\right)
=\left(  b_{1},b_{2},\ldots,b_{i},v_{i+1},v_{i+2},\ldots,v_{k}\right)
\nonumber\\
&  \in\left\{  b_{1}\right\}  \times\left\{  b_{2}\right\}  \times\cdots
\times\left\{  b_{i}\right\}  \times S^{k-i}. \label{4}%
\end{align}
\footnote{By abuse of notation, we are writing $\left\{  b_{1}\right\}
\times\left\{  b_{2}\right\}  \times\cdots\times\left\{  b_{i}\right\}  \times
S^{k-i}$ for $\left\{  b_{1}\right\}  \times\left\{  b_{2}\right\}
\times\cdots\times\left\{  b_{i}\right\}  \times\underbrace{S\times
S\times\cdots\times S}_{k-i\text{ factors}}$ here.}

By (\ref{3}) and (\ref{4}), we have%
\[
\left(  u,v\right)  \in\left(  S^{i-1}\times\left\{  a_{i}\right\}
\times\left\{  a_{i+1}\right\}  \times\cdots\times\left\{  a_{k}\right\}
\right)  \times\left(  \left\{  b_{1}\right\}  \times\left\{  b_{2}\right\}
\times\cdots\times\left\{  b_{i}\right\}  \times S^{k-i}\right)
\]
for every $\left(  u,v\right)  \in\phi^{-1}\left(  \left\{  \left(
a,b\right)  \right\}  \right)  $. Thus,%
\begin{align}
&  \left\vert \phi^{-1}\left(  \left\{  \left(  a,b\right)  \right\}  \right)
\right\vert \nonumber\\
&  \leq\left\vert \left(  S^{i-1}\times\left\{  a_{i}\right\}  \times\left\{
a_{i+1}\right\}  \times\cdots\times\left\{  a_{k}\right\}  \right)
\times\left(  \left\{  b_{1}\right\}  \times\left\{  b_{2}\right\}
\times\cdots\times\left\{  b_{i}\right\}  \times S^{k-i}\right)  \right\vert
\nonumber\\
&  =\left\vert S^{i-1}\times\left\{  a_{i}\right\}  \times\left\{
a_{i+1}\right\}  \times\cdots\times\left\{  a_{k}\right\}  \right\vert
\cdot\left\vert \left\{  b_{1}\right\}  \times\left\{  b_{2}\right\}
\times\cdots\times\left\{  b_{i}\right\}  \times S^{k-i}\right\vert
\nonumber\\
&  =\left(  \underbrace{\left\vert S^{i-1}\right\vert }_{=\left\vert
S\right\vert ^{i-1}}\cdot\underbrace{\left\vert \left\{  a_{i}\right\}
\right\vert }_{=1}\cdot\underbrace{\left\vert \left\{  a_{i+1}\right\}
\right\vert }_{=1}\cdot\cdots\cdot\underbrace{\left\vert \left\{
a_{k}\right\}  \right\vert }_{=1}\right)  \cdot\left(  \underbrace{\left\vert
\left\{  b_{1}\right\}  \right\vert }_{=1}\cdot\underbrace{\left\vert \left\{
b_{2}\right\}  \right\vert }_{=1}\cdot\cdots\cdot\underbrace{\left\vert
\left\{  b_{i}\right\}  \right\vert }_{=1}\cdot\underbrace{\left\vert
S^{k-i}\right\vert }_{=\left\vert S\right\vert ^{k-i}}\right) \nonumber\\
&  =\left\vert S\right\vert ^{i-1}\cdot\left\vert S\right\vert ^{k-i}%
=\left\vert S\right\vert ^{k-1} \label{5}%
\end{align}
for every $\left(  a,b\right)  \in F$.

Thus,%
\begin{align*}
\left\vert A\times B\right\vert  &  =\sum_{\left(  a,b\right)  \in
F}\left\vert \left\{  \left(  u,v\right)  \in A\times B\ \mid\ \phi\left(
u,v\right)  =\left(  a,b\right)  \right\}  \right\vert \\
&  =\sum_{\left(  a,b\right)  \in F}\underbrace{\left\vert \phi^{-1}\left(
\left\{  \left(  a,b\right)  \right\}  \right)  \right\vert }_{\substack{\leq
\left\vert S\right\vert ^{k-1}\\\text{(by (\ref{5}))}}}\leq\sum_{\left(
a,b\right)  \in F}\left\vert S\right\vert ^{k-1}\\
&  =\left\vert F\right\vert \cdot\left\vert S\right\vert ^{k-1}.
\end{align*}
But%
\begin{align*}
\left\vert A\times B\right\vert  &  =\left\vert A\right\vert \cdot\left\vert
B\right\vert =\left\vert A\right\vert \cdot\left\vert S^{k}\setminus
A\right\vert =\left\vert A\right\vert \cdot\left(  \left\vert S^{k}\right\vert
-\left\vert A\right\vert \right) \\
&  =\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert S^{k}\right\vert
-\left\vert S\right\vert ^{k-1}\right)  =\left\vert S\right\vert ^{k-1}%
\cdot\left(  \left\vert S\right\vert ^{k}-\left\vert S\right\vert
^{k-1}\right)  ,
\end{align*}
so this becomes%
\[
\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert S\right\vert
^{k}-\left\vert S\right\vert ^{k-1}\right)  \leq\left\vert F\right\vert
\cdot\left\vert S\right\vert ^{k-1},
\]
thus $\left\vert S\right\vert ^{k}-\left\vert S\right\vert ^{k-1}%
\leq\left\vert F\right\vert $, so that%
\[
\left\vert F\right\vert \geq\left\vert S\right\vert ^{k}-\left\vert
S\right\vert ^{k-1}=\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert
S\right\vert -1\right)  ,
\]
qed.
\end{vershort}

\begin{verlong}
Next, we will prove that $\left\vert \phi^{-1}\left(  \left\{  \mathbf{p}%
\right\}  \right)  \right\vert \leq\left\vert S\right\vert ^{k-1}$ for every
$\mathbf{p}\in F$.

In fact, let $\mathbf{p}\in F$. Then, $\mathbf{p}\in F\subseteq A\times B$.
Hence, we can write $\mathbf{p}$ in the form $\mathbf{p}=\left(
\mathbf{a},\mathbf{b}\right)  $ for some $\mathbf{a}\in A$ and some
$\mathbf{b}\in B$. Consider these $\mathbf{a}$ and $\mathbf{b}$. We have
$\mathbf{a}\neq\mathbf{b}$\ \ \ \ \footnote{\textit{Proof.} Assume the
contrary. Thus, $\mathbf{a}=\mathbf{b}$, so that $\mathbf{a}=\mathbf{b}\in
B=S^{k}\setminus A$. In other words, $\mathbf{a}\in S^{k}$ and $\mathbf{a}%
\notin A$. But $\mathbf{a}\notin A$ contradicts $\mathbf{a}\in A$. This
contradiction proves that our assumption was wrong, qed.}. Also, $\left(
\mathbf{a},\mathbf{b}\right)  =\mathbf{p}\in F$. Hence,%
\begin{equation}
\text{there exists an }i\in\left\{  1,2,\ldots,k\right\}  \text{ satisfying
}\left(  \mathbf{a}_{j}=\mathbf{b}_{j}\text{ for all }j\neq i\right)
\label{long.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{long.1}):} We can apply (\ref{long.eq1}) to
$\left(  a,b\right)  =\left(  \mathbf{a},\mathbf{b}\right)  $. As a
consequence, we obtain the following logical equivalence:%
\begin{align*}
&  \ \left(  \left(  \mathbf{a},\mathbf{b}\right)  \in F\right) \\
&  \Longleftrightarrow\ \left(  \text{there exists an }i\in\left\{
1,2,\ldots,k\right\}  \text{ satisfying }\left(  \mathbf{a}_{j}=\mathbf{b}%
_{j}\text{ for all }j\neq i\right)  \right)  .
\end{align*}
Hence, we conclude that $\left(  \text{there exists an }i\in\left\{
1,2,\ldots,k\right\}  \text{ satisfying }\left(  \mathbf{a}_{j}=\mathbf{b}%
_{j}\text{ for all }j\neq i\right)  \right)  $ (because we know that $\left(
\mathbf{a},\mathbf{b}\right)  \in F$). This proves (\ref{long.1}).}. Consider
this $i$. Thus,%
\begin{equation}
\mathbf{a}_{j}=\mathbf{b}_{j}\text{ for all }j\neq i. \label{long.1a}%
\end{equation}


We must have $\mathbf{a}_{i}\neq\mathbf{b}_{i}$%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $\mathbf{a}%
_{i}=\mathbf{b}_{i}$.
\par
Now, we shall show that $\mathbf{a}_{j}=\mathbf{b}_{j}$ for every
$j\in\left\{  1,2,\ldots,k\right\}  $.
\par
Indeed, fix $j\in\left\{  1,2,\ldots,k\right\}  $. We must prove that
$\mathbf{a}_{j}=\mathbf{b}_{j}$. If $j\neq i$, then this follows from
(\ref{long.1a}). Hence, we can WLOG assume that we don't have $j\neq i$.
Assume this.
\par
We have $j=i$ (since we don't have $j\neq i$). Thus, $\mathbf{a}%
_{j}=\mathbf{a}_{i}=\mathbf{b}_{i}=\mathbf{b}_{j}$ (since $i=j$).
\par
Thus, we have proven that $\mathbf{a}_{j}=\mathbf{b}_{j}$.
\par
Now, let us forget that we fixed $j$. We thus have proven that $\mathbf{a}%
_{j}=\mathbf{b}_{j}$ for every $j\in\left\{  1,2,\ldots,k\right\}  $. In other
words, $\mathbf{a}=\mathbf{b}$. This contradicts $\mathbf{a}\neq\mathbf{b}$.
This contradiction proves that our assumption was wrong, qed.}.

We record a fundamental fact: If $\mathfrak{U}$ and $\mathfrak{V}$ are two
finite sets, and if $\gamma:\mathfrak{U}\rightarrow\mathfrak{V}$ is a map,
then%
\begin{equation}
\left\vert \gamma\left(  \mathfrak{U}\right)  \right\vert \leq\left\vert
\mathfrak{U}\right\vert . \label{long.gamma}%
\end{equation}


Now, consider some $\mathbf{q}\in\phi^{-1}\left(  \left\{  \mathbf{p}\right\}
\right)  $. Thus, $\phi\left(  \mathbf{q}\right)  \in\left\{  \mathbf{p}%
\right\}  $. In other words, $\phi\left(  \mathbf{q}\right)  =\mathbf{p}%
=\left(  \mathbf{a},\mathbf{b}\right)  $.

We have $\mathbf{q}\in\phi^{-1}\left(  \left\{  \mathbf{p}\right\}  \right)
\subseteq A\times B$. In other words, there exist $u\in A$ and $v\in B$ such
that $\mathbf{q}=\left(  u,v\right)  $. Consider these $u$ and $v$.

On the other hand, let us define $T$, $\alpha$, $a$ and $b$ as in our above
definition of the map $\phi$ (using the value of $\left(  u,v\right)  $ that
we have just introduced). Thus, the following observations
hold\footnote{Indeed, all of these observations were made during the
definition of the map $\phi$.}:

\begin{itemize}
\item We have $T=\left\{  i\in\left\{  0,1,2,\ldots,k\right\}  \mid\left(
v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  \in B\right\}  $.

\item The number $\alpha$ is the minimal element of $T$.

\item We have $\alpha\in\left\{  1,2,3,\ldots,k\right\}  $.

\item We have $a=\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha}%
,u_{\alpha+1},\ldots,u_{k}\right)  $ and $b=\left(  v_{1},v_{2},\ldots
,v_{\alpha},u_{\alpha+1},u_{\alpha+2},\ldots,u_{k}\right)  $.

\item We have $a\in A$ and $b\in B$.

\item For every $j\in\left\{  1,2,\ldots,k\right\}  $ satisfying $j\neq\alpha
$, we have $a_{j}=b_{j}$.

\item We have $\phi\left(  u,v\right)  =\left(  a,b\right)  $.
\end{itemize}

From $\left(  a,b\right)  =\phi\underbrace{\left(  u,v\right)  }_{=\mathbf{q}%
}=\phi\left(  \mathbf{q}\right)  =\left(  \mathbf{a},\mathbf{b}\right)  $, we
obtain $a=\mathbf{a}$ and $b=\mathbf{b}$.

We have $a_{\alpha}\neq b_{\alpha}$\ \ \ \ \footnote{\textit{Proof.} Assume
the contrary. Thus, $a_{\alpha}=b_{\alpha}$.
\par
Recall that%
\begin{equation}
\text{for every }j\in\left\{  1,2,\ldots,k\right\}  \text{ satisfying }%
j\neq\alpha\text{, we have }a_{j}=b_{j}. \label{long.1b.fn1.1}%
\end{equation}
\par
Now, we have $a_{j}=b_{j}$ for every $j\in\left\{  1,2,\ldots,k\right\}  $.
\par
[\textit{Proof:} Let $j\in\left\{  1,2,\ldots,k\right\}  $. We must prove that
$a_{j}=b_{j}$. If $j\neq\alpha$, then this follows from (\ref{long.1b.fn1.1}).
Hence, for the rest of this proof, we can WLOG assume that we don't have
$j\neq\alpha$. Assume this.
\par
We have $j=\alpha$ (since we don't have $j\neq\alpha$). Hence, $a_{j}%
=a_{\alpha}=b_{\alpha}=b_{j}$ (since $\alpha=j$). Thus, $a_{j}=b_{j}$ is
proven.]
\par
Now we have proven that $a_{j}=b_{j}$ for every $j\in\left\{  1,2,\ldots
,k\right\}  $. In other words, $a=b$. Hence, $\mathbf{a}=a=b=\mathbf{b}$. This
contradicts $\mathbf{a}\neq\mathbf{b}$. This contradiction proves that our
assumption was wrong, qed.}. Hence, $\alpha=i$%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $\alpha\neq i$.
Also, $\alpha\in\left\{  1,2,3,\ldots,k\right\}  =\left\{  1,2,\ldots
,k\right\}  $. Thus, (\ref{long.1a}) (applied to $j=\alpha$) shows that
$\mathbf{a}_{\alpha}=\mathbf{b}_{\alpha}$. Since $\mathbf{a}=a$ and
$\mathbf{b}=b$, this rewrites as $a_{\alpha}=b_{\alpha}$. This contradicts
$a_{\alpha}\neq b_{\alpha}$. This contradiction proves that our assumption was
wrong, qed.}. Now,%
\begin{align*}
a  &  =\left(  v_{1},v_{2},\ldots,v_{\alpha-1},u_{\alpha},u_{\alpha+1}%
,\ldots,u_{k}\right) \\
&  =\left(  v_{1},v_{2},\ldots,v_{i-1},u_{i},u_{i+1},\ldots,u_{k}\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\alpha=i\right)
\end{align*}
and%
\begin{align*}
b  &  =\left(  v_{1},v_{2},\ldots,v_{\alpha},u_{\alpha+1},u_{\alpha+2}%
,\ldots,u_{k}\right) \\
&  =\left(  v_{1},v_{2},\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\alpha=i\right)  .
\end{align*}


Next, let us define a map $\mathbf{X}:S^{i-1}\rightarrow S^{k}$ by%
\[
\left(
\begin{array}
[c]{l}%
\mathbf{X}\left(  \left(  q_{1},q_{2},\ldots,q_{i-1}\right)  \right)  =\left(
q_{1},q_{2},\ldots,q_{i-1},\mathbf{a}_{i},\mathbf{a}_{i+1},\ldots
,\mathbf{a}_{k}\right) \\
\ \ \ \ \ \ \ \ \ \ \text{for every }\left(  q_{1},q_{2},\ldots,q_{i-1}%
\right)  \in S^{i-1}%
\end{array}
\right)  .
\]
Then,%
\[
u\in\mathbf{X}\left(  S^{i-1}\right)
\]
\footnote{\textit{Proof.} We have $\mathbf{a}=a=\left(  v_{1},v_{2}%
,\ldots,v_{i-1},u_{i},u_{i+1},\ldots,u_{k}\right)  $. Compared with
$\mathbf{a}=\left(  \mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}%
_{k}\right)  $, this shows that $\left(  \mathbf{a}_{1},\mathbf{a}_{2}%
,\ldots,\mathbf{a}_{k}\right)  =\left(  v_{1},v_{2},\ldots,v_{i-1}%
,u_{i},u_{i+1},\ldots,u_{k}\right)  $. In other words,%
\begin{equation}
\mathbf{a}_{p}=%
\begin{cases}
v_{p}, & \text{if }p<i;\\
u_{p}, & \text{if }p\geq i
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for every }p\in\left\{  1,2,\ldots,k\right\}  .
\label{long.3.fn3.pf.1}%
\end{equation}
\par
Now, we have%
\begin{equation}
u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for every }p\in\left\{  1,2,\ldots,k\right\}  .
\label{long.3.fn3.pf.2}%
\end{equation}
\par
[\textit{Proof of (\ref{long.3.fn3.pf.2}):} Let $p\in\left\{  1,2,\ldots
,k\right\}  $. We need to prove that $u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
$.
\par
We must be in one of the following two cases:
\par
\textit{Case 1:} We have $p<i$.
\par
\textit{Case 2:} We have $p\geq i$.
\par
Let us first consider Case 1. In this case, we have $p<i$. Now, $%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
=u_{p}$ (since $p<i$), so that $u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
$. Hence, $u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
$ is proven in Case 1.
\par
Let us next consider Case 2. In this case, we have $p\geq i$. Now, $%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
=\mathbf{a}_{p}$ (since $p\geq i$). Hence, $%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
=\mathbf{a}_{p}=%
\begin{cases}
v_{p}, & \text{if }p<i;\\
u_{p}, & \text{if }p\geq i
\end{cases}
$ (by (\ref{long.3.fn3.pf.1})). Hence, $%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
=%
\begin{cases}
v_{p}, & \text{if }p<i;\\
u_{p}, & \text{if }p\geq i
\end{cases}
=u_{p}$ (since $p\geq i$), so that $u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
$. Hence, $u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
$ is proven in Case 2.
\par
Now, $u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
$ is proven in both Cases 1 and 2. Since these two Cases cover all
possibilities, this shows that $u_{p}=%
\begin{cases}
u_{p}, & \text{if }p<i;\\
\mathbf{a}_{p}, & \text{if }p\geq i
\end{cases}
$ always holds. This proves (\ref{long.3.fn3.pf.2}).]
\par
From (\ref{long.3.fn3.pf.2}), we obtain $\left(  u_{1},u_{2},\ldots
,u_{k}\right)  =\left(  u_{1},u_{2},\ldots,u_{i-1},\mathbf{a}_{i}%
,\mathbf{a}_{i+1},\ldots,\mathbf{a}_{k}\right)  $. Compared with
$\mathbf{X}\left(  \left(  u_{1},u_{2},\ldots,u_{i-1}\right)  \right)
=\left(  u_{1},u_{2},\ldots,u_{i-1},\mathbf{a}_{i},\mathbf{a}_{i+1}%
,\ldots,\mathbf{a}_{k}\right)  $ (by the definition of $\mathbf{X}$), this
shows that $\mathbf{X}\left(  \left(  u_{1},u_{2},\ldots,u_{i-1}\right)
\right)  =\left(  u_{1},u_{2},\ldots,u_{k}\right)  =u$. Hence, $u=\mathbf{X}%
\left(  \underbrace{\left(  u_{1},u_{2},\ldots,u_{i-1}\right)  }_{\in S^{i-1}%
}\right)  \in\mathbf{X}\left(  S^{i-1}\right)  $, qed.}.

Furthermore, let us define a map $\mathbf{Y}:S^{k-i}\rightarrow S^{k}$ by%
\[
\left(
\begin{array}
[c]{l}%
\mathbf{Y}\left(  \left(  r_{1},r_{2},\ldots,r_{k-i}\right)  \right)  =\left(
\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{i},r_{1},r_{2},\ldots
,r_{k-i}\right) \\
\ \ \ \ \ \ \ \ \ \ \text{for every }\left(  r_{1},r_{2},\ldots,r_{k-i}%
\right)  \in S^{k-i}%
\end{array}
\right)  .
\]
Then,%
\[
v\in\mathbf{Y}\left(  S^{k-i}\right)
\]
\footnote{\textit{Proof.} We have $\mathbf{b}=b=\left(  v_{1},v_{2}%
,\ldots,v_{i},u_{i+1},u_{i+2},\ldots,u_{k}\right)  $. Compared with
$\mathbf{b}=\left(  \mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}%
_{k}\right)  $, this shows that $\left(  \mathbf{b}_{1},\mathbf{b}_{2}%
,\ldots,\mathbf{b}_{k}\right)  =\left(  v_{1},v_{2},\ldots,v_{i}%
,u_{i+1},u_{i+2},\ldots,u_{k}\right)  $. In other words,%
\begin{equation}
\mathbf{b}_{p}=%
\begin{cases}
v_{p}, & \text{if }p<i+1;\\
u_{p}, & \text{if }p\geq i+1
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for every }p\in\left\{  1,2,\ldots,k\right\}  .
\label{long.3.fn4.pf.1}%
\end{equation}
\par
Now, we have%
\begin{equation}
v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for every }p\in\left\{  1,2,\ldots,k\right\}  .
\label{long.3.fn4.pf.2}%
\end{equation}
\par
[\textit{Proof of (\ref{long.3.fn4.pf.2}):} Let $p\in\left\{  1,2,\ldots
,k\right\}  $. We need to prove that $v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
$.
\par
We must be in one of the following two cases:
\par
\textit{Case 1:} We have $p\leq i$.
\par
\textit{Case 2:} We have $p>i$.
\par
Let us first consider Case 1. In this case, we have $p\leq i$. Hence, $p\leq
i<i+1$. Now, $%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
=\mathbf{b}_{p}$ (since $p\leq i$). Hence, $%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
=\mathbf{b}_{p}=%
\begin{cases}
v_{p}, & \text{if }p<i+1;\\
u_{p}, & \text{if }p\geq i+1
\end{cases}
$ (by (\ref{long.3.fn4.pf.1})), so that $%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
=%
\begin{cases}
v_{p}, & \text{if }p<i+1;\\
u_{p}, & \text{if }p\geq i+1
\end{cases}
=v_{p}$ (since $p<i+1$). In other words, $v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
$. Hence, $v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
$ is proven in Case 1.
\par
Let us next consider Case 2. In this case, we have $p>i$. Thus, $%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
=v_{p}$ (since $p>i$), so that $v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
$. Hence, $v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
$ is proven in Case 2.
\par
Now, $v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
$ is proven in both Cases 1 and 2. Since these two Cases cover all
possibilities, this shows that $v_{p}=%
\begin{cases}
\mathbf{b}_{p}, & \text{if }p\leq i;\\
v_{p}, & \text{if }p>i
\end{cases}
$ always holds. This proves (\ref{long.3.fn4.pf.2}).]
\par
From (\ref{long.3.fn4.pf.2}), we obtain $\left(  v_{1},v_{2},\ldots
,v_{k}\right)  =\left(  \mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}%
_{i},v_{i+1},v_{i+2},\ldots,v_{k}\right)  $. Compared with $\mathbf{Y}\left(
\left(  v_{i+1},v_{i+2},\ldots,v_{k}\right)  \right)  =\left(  \mathbf{b}%
_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{i},v_{i+1},v_{i+2},\ldots,v_{k}\right)
$ (by the definition of $\mathbf{Y}$), this shows that $\mathbf{Y}\left(
\left(  v_{i+1},v_{i+2},\ldots,v_{k}\right)  \right)  =\left(  v_{1}%
,v_{2},\ldots,v_{k}\right)  =v$. Hence, $v=\mathbf{Y}\left(
\underbrace{\left(  v_{i+1},v_{i+2},\ldots,v_{k}\right)  }_{\in S^{k-i}%
}\right)  \in\mathbf{Y}\left(  S^{k-i}\right)  $, qed.}.

Combining $u\in\mathbf{X}\left(  S^{i-1}\right)  $ with $v\in\mathbf{Y}\left(
S^{k-i}\right)  $, we obtain $\left(  u,v\right)  \in\mathbf{X}\left(
S^{i-1}\right)  \times\mathbf{Y}\left(  S^{k-i}\right)  $. Thus,
$\mathbf{q}=\left(  u,v\right)  \in\mathbf{X}\left(  S^{i-1}\right)
\times\mathbf{Y}\left(  S^{k-i}\right)  $.

Now, let us forget that we fixed $\mathbf{q}$. We thus have proven that
$\mathbf{q}\in\mathbf{X}\left(  S^{i-1}\right)  \times\mathbf{Y}\left(
S^{k-i}\right)  $ for every $\mathbf{q}\in\phi^{-1}\left(  \left\{
\mathbf{p}\right\}  \right)  $. In other words,%
\[
\phi^{-1}\left(  \left\{  \mathbf{p}\right\}  \right)  \subseteq
\mathbf{X}\left(  S^{i-1}\right)  \times\mathbf{Y}\left(  S^{k-i}\right)  .
\]
Hence,%
\begin{align*}
&  \left\vert \phi^{-1}\left(  \left\{  \mathbf{p}\right\}  \right)
\right\vert \\
&  \leq\left\vert \mathbf{X}\left(  S^{i-1}\right)  \times\mathbf{Y}\left(
S^{k-i}\right)  \right\vert =\underbrace{\left\vert \mathbf{X}\left(
S^{i-1}\right)  \right\vert }_{\substack{\leq\left\vert S^{i-1}\right\vert
\\\text{(by (\ref{long.gamma}), applied to}\\\mathfrak{U}=S^{i-1}\text{,
}\mathfrak{V}=S^{k}\text{ and }\gamma=\mathbf{X}\text{)}}}\cdot
\underbrace{\left\vert \mathbf{Y}\left(  S^{k-i}\right)  \right\vert
}_{\substack{\leq\left\vert S^{k-i}\right\vert \\\text{(by (\ref{long.gamma}),
applied to}\\\mathfrak{U}=S^{k-i}\text{, }\mathfrak{V}=S^{k}\text{ and }%
\gamma=\mathbf{Y}\text{)}}}\\
&  \leq\underbrace{\left\vert S^{i-1}\right\vert }_{=\left\vert S\right\vert
^{i-1}}\cdot\underbrace{\left\vert S^{k-i}\right\vert }_{=\left\vert
S\right\vert ^{k-i}}=\left\vert S\right\vert ^{i-1}\cdot\left\vert
S\right\vert ^{k-i}=\left\vert S\right\vert ^{\left(  i-1\right)  +\left(
k-i\right)  }\\
&  =\left\vert S\right\vert ^{k-1}\ \ \ \ \ \ \ \ \ \ \left(  \text{since
}\left(  i-1\right)  +\left(  k-i\right)  =k-1\right)  .
\end{align*}


Let us now forget that we fixed $\mathbf{p}$. We thus have proven that
$\left\vert \phi^{-1}\left(  \left\{  \mathbf{p}\right\}  \right)  \right\vert
\leq\left\vert S\right\vert ^{k-1}$ for every $\mathbf{p}\in F$.

Now, $\sum_{\mathbf{h}\in A\times B}1=\left\vert A\times B\right\vert
\cdot1=\left\vert A\times B\right\vert $, so that%
\begin{align*}
\left\vert A\times B\right\vert  &  =\sum_{\mathbf{h}\in A\times B}%
1=\sum_{\mathbf{p}\in F}\underbrace{\sum_{\substack{\mathbf{h}\in A\times
B;\\\phi\left(  \mathbf{h}\right)  =\mathbf{p}}}}_{\substack{=\sum
_{\substack{\mathbf{h}\in A\times B;\\\phi\left(  \mathbf{h}\right)
\in\left\{  \mathbf{p}\right\}  }}\\\text{(because the condition }\left(
\phi\left(  \mathbf{h}\right)  =\mathbf{p}\right)  \\\text{is equivalent to
}\left(  \phi\left(  \mathbf{h}\right)  \in\left\{  \mathbf{p}\right\}
\right)  \text{)}}}1\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split the sum }\sum_{\mathbf{h}\in A\times B}1\\
\text{according to the value of }\phi\left(  \mathbf{h}\right)
\end{array}
\right)  \\
&  =\sum_{\mathbf{p}\in F}\underbrace{\sum_{\substack{\mathbf{h}\in A\times
B;\\\phi\left(  \mathbf{h}\right)  \in\left\{  \mathbf{p}\right\}  }%
}}_{\substack{=\sum_{\mathbf{h}\in\phi^{-1}\left(  \left\{  \mathbf{p}%
\right\}  \right)  }}}1=\sum_{\mathbf{p}\in F}\underbrace{\sum_{\mathbf{h}%
\in\phi^{-1}\left(  \left\{  \mathbf{p}\right\}  \right)  }1}_{=\left\vert
\phi^{-1}\left(  \left\{  \mathbf{p}\right\}  \right)  \right\vert
\leq\left\vert S\right\vert ^{k-1}}\leq\sum_{\mathbf{p}\in F}\left\vert
S\right\vert ^{k-1}=\left\vert F\right\vert \cdot\left\vert S\right\vert
^{k-1}.
\end{align*}
Since%
\begin{align*}
\left\vert A\times B\right\vert  &  =\left\vert A\right\vert \cdot\left\vert
\underbrace{B}_{=S^{k}\setminus A}\right\vert =\left\vert A\right\vert
\cdot\underbrace{\left\vert S^{k}\setminus A\right\vert }_{=\left\vert
S\right\vert ^{k}-\left\vert A\right\vert }=\underbrace{\left\vert
A\right\vert }_{=\left\vert S\right\vert ^{k-1}}\cdot\left(  \left\vert
S^{k}\right\vert -\underbrace{\left\vert A\right\vert }_{=\left\vert
S\right\vert ^{k-1}}\right)  \\
&  =\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert S^{k}\right\vert
-\left\vert S\right\vert ^{k-1}\right)  =\left\vert S\right\vert ^{k-1}%
\cdot\left(  \left\vert S\right\vert ^{k}-\left\vert S\right\vert
^{k-1}\right)  ,
\end{align*}
this rewrites as%
\[
\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert S\right\vert
^{k}-\left\vert S\right\vert ^{k-1}\right)  \leq\left\vert F\right\vert
\cdot\left\vert S\right\vert ^{k-1}.
\]
We can divide this inequality by $\left\vert S\right\vert ^{k-1}$ (since
$\left\vert S\right\vert ^{k-1}$ is positive). As a result, we obtain
$\left\vert S\right\vert ^{k}-\left\vert S\right\vert ^{k-1}\leq\left\vert
F\right\vert $. In other words,%
\[
\left\vert F\right\vert \geq\left\vert S\right\vert ^{k}-\left\vert
S\right\vert ^{k-1}=\left\vert S\right\vert ^{k-1}\cdot\left(  \left\vert
S\right\vert -1\right)  ,
\]
qed.
\end{verlong}


\end{document}