# Calendar Calculations with Cards

As readers of this previous post will know, I’m rather fond of mental calendar calculations. My friend Al Stanger, with whom I share a passion for recreational mathematics, came up with a remarkable procedure for finding the day of the week corresponding to any date in history using just a handful of playing cards. What’s particularly noteworthy about Al’s algorithm is that it involves no calculations whatsoever, and the information which needs to be looked up can be cleanly displayed on one of the cards.

When you work through Al’s procedure, it will feel like you’re performing a card trick on yourself – you will be amazed, surprised, and will likely have no idea how it works. I’ve never seen anything quite like this before, and I’m grateful to Al for allowing me to share his discovery with the public for the first time here on this blog.

# Zero Knowledge Identification and One-Way Homomorphisms

Sounds too good to be true, right?

In fact, such password schemes do exist, and they’re quite easy to implement. They are known as zero knowledge authentication systems. In this post, I’ll explain the main idea behind such protocols using the notion of a “one-way homomorphism”. Before diving into the technicalities, though, here’s a useful thought experiment which conveys the main idea.

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets $A_1, A_2,\ldots, A_n$ and you wish to find distinct elements $x_1 \in A_1,\ldots, x_n \in A_n$.  (In our solitaire example, take $A_j$ to be the values of the cards in the $j^{\rm th}$ pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset $J \subset \{ 1,\ldots, n \}$, the set $A_J:= \bigcup_{j \in J} A_j$ contains at least $\#J$ elements.  Hall’s theorem asserts that these conditions are also sufficient. Continue reading