# Rewritable punch cards

Punch cards are boring, primitive, non-rewritable storage devices. Or are they? Indeed, a punch card that is filled to the brim with data seems impossible to write upon. Once you punched a hole through a piece of paper, you cannot unpunch it. But wait a minute! For sure, you can make some new holes at the zero bits left untouched by the previous write. And if that write was made with a little friendlier encoding than plain binary, you might even manage to actually add some data, while making the old data unreadable.

The real question is: can this be more economical than just getting a fresh new card?

Can you (decodably) write to a punch card more than once so that the overall size of the writes adds up to more than the actual capacity of the card?

As you may have guessed by now, the answer is yes. (Sorry for the spoiler). For example, there is a quite elegant way to make a $4$ times writable punch card so that the total amount of information you can store in the four writes (measured in bits) is almost $60 \%$ greater than the card's storage capacity (which would make a great advertising slogan if punch card readers/writers were still a thing).

The task in this puzzle is something a little more daring:

Prove that for any $n$, there is a punch card encoding for which $\frac{\text{total writable data in bits}}{\text{number of punch cells}} > n$.

That should be fairly simple, so

Bonus task: Find some nice, easy-to-explain encodings.

EDIT: The card can be read whenever you want, but you can't rely on data that's not on the card to decode it. The card has to be portable.

• Can the card be read multiple times, once after each new set of holes added? Or can a given card only be read once, after all 'punchings' have been done? – astralfenix Apr 25 '16 at 17:50
• @astralfenix You can read whenever and as many times as you want. – BaSzAt Apr 25 '16 at 17:52
• @humn Yup, I forgot to state that the card needs to contain all information regarding the data that was saved to it. He was being too considerate deleting his answer. It was my fault. – BaSzAt Apr 25 '16 at 18:19
• Great idea, both for a puzzle and punch cards! Never too late to treat us to the solution you had in mind as an additional answer. – humn Apr 25 '16 at 18:28
• This question really confuses me, I am probbably misinterpreting something, but I do not know what. If we have a punch card that is filled to the brim with data and the encoding method was: hole=1; noHole=0. Is it not possible that the data placed on that card was 1111111..... and it is completely full of holes? – Jonathan Allan Apr 25 '16 at 18:47

Have a punch card with $2x$ holes, divided into the first half and the second half, each with $x$ holes. This card will be written $x$ times.

On the $j$th write, $\log_2(x+1-j)$ bits will be encoded; this corresponds to choosing one of $x+1-j$ possibilities. To do this, copy the first half to the second half, then choose one unpunched hole in the first half and punch it. The data can be retrieved easily by noting which hole is punched in the first half and not in the second half.

The total amount of information encoded is $\log_2(x!)$ bits. Since $\frac{\log_2(x!)}{2x}$ increases without bound as $x$ increases, we can always choose an $x$ such that the ratio is greater than $n$.

• So if my math is right, this stores roughly $O(n \log n)$ bits per card. My gut feeling is that this asymptotically the most efficient we can get, I wonder if that can be proven? – 2012rcampion Apr 26 '16 at 2:37
• Thinking greedily, the asymmetry of a card actually makes available all of the $2(x{+}1{-}j)$ unpunched holes on the $j$th write, for an equivalent total bit count of $log_2(2^x x!) \sim \bigl( x{+}\frac12 \bigr) \ln x - (1{-}\ln2) x$, which is still @2012rcampion's $O(n \log n)$. Incidentally, this beats $2^{2x}$-possibilities-at-once for a card with as few as $2x{=}$8 spots, at about 8.6 equivalent bits, whereas a symmetric card would require 18 spots, at about 18.5 equivalent bits. – humn May 3 '16 at 17:16
• @2012rcampion, the (degenerate) first alternative approach in another answer gets $~ O(\log N) ~$ equivalent bits/card, which wouldn't be worth noting except that $N$ is the value being stored, not the number of cells – humn May 22 '16 at 23:54

An adaptation of r's approach, if the requirement is to, for any k, find a B such that N bits of storage can be used to allow kN/B distinct writes, is to pick B=3k, and encode the information as follows.

Take 3(2^B) holes in pairs, such that after any operation all but one of the pairs will have either neither hole punched or both holes punched. One will always be able to identify which hole was punched by the last operation (since it will be the only hole whose mate is not also punched); on the next operation, its mate will get punched as well as a newly-chosen unpaired hole.

On each operation, encode a value V from 0 to 2^B-1 by punching a hole such that the number of unpunched holes to the left of it is exactly V. Each operation will encode B bits by punching two holes, and one may perform the procedure until the number of holes has dropped below 2^B-1. If one starts with 3(2^B) holes, the number of bits encoded will thus be B(2^B). If B=3K, then the number of bits encoded will be k times the number of holes.

( Jaded by mathematics?   At the end of this answer :  The Case of the Surprisingly Simple Solution )

Bonus task: Find some nice, easy-to-explain encodings. $\require{begingroup}\begingroup \def \Pad #1{\raise{#1}{\small\raise1mu\strut}} \def \Frac #1#2{ \dfrac {\raise-9mu {#1}} {\raise2mu {#2}} } \def \SSfrac #1#2{ \Frac { \scriptsize #1 } { \scriptsize #2 } } \def \Sfrac #1#2{ \Frac { \small #1 } { \small \raise4mu {#2}} } \def \T #1{{ \small\textsf{#1} }} \def \Nsub #1{ n \raise-3mu{\kern1mu\T{#1}} } \def \Tight {\kern -1mu} \def \Hair {\kern 1mu} \def \Hairr {\kern 2mu} \def \MinusL {{\kern 1mu {-} }} \def \MinusLR {{\kern 1mu {-} \kern 1mu}} \def \Minus {{\kern 1mu {-} \kern-1mu}} \def \Minuss {{\kern-1mu {-} \kern-1mu}} \def \MinusR {{ {-} \kern 1mu}} \def \MinusRR {{ {-} \kern 2mu}} \def \MinusXR {{\kern-1mu {-} \kern 1mu}} \def \PlusL {{\kern 1mu {+} }} \def \PlusR {{ {+} \kern 1mu}} \def \Plus {{\kern 1mu {+} \kern-1mu}} \def \Pluss {{\kern-1mu {+} \kern-1mu}} \def \EB { \T {equivalent bits} } \def \AEB { \T {average equivalent bits} } \def \TEB { \T {total equivalent bits} } \def \PC { \T{punch cells} } \def\Ttimes {{ \tiny \kern1mu \raise2mu\times \kern2mu }} \def \SStimes {{ \scriptsize \raise1mu\times }} \def \Stimes {{ \small \kern-1mu\raise1mu\times \kern-1mu }} \def \Logbb { \log_2 } \def \Logb { \log_2 \kern-2mu } \def \Arrow #1{\mathop{ \raise-11mu\rlap{ \displaystyle\small~~~#1 } \raise-1mu\xrightarrow{\hphantom{ \displaystyle\small~~#1 }} }}$

1.   A degenerate trivial-to-explain encoding happens to be unbeatable. Any nonnegative integer $N$ can be conveyed, and the measure in question increases boundlessly with $N$ itself.

$$n ~ = ~~ \Frac{\EB}{\PC} ~~ \approx ~~ \Logb N ~~\Arrow{N\to\infty}~~~~ \infty$$

Just one punchable cell can be reused any number of times to convey an arbitrarily large $N$.
•   First send the unpunched card $N$ times. (Each time amounts to a unary 1.)
•   Then punch that cell and send the punched card once. End of number. End of card.
Although this feels like cheating, similar iteration is required for decreasing-base approaches too, unless a card is considered usable only when a value to be conveyed happens to be within the card's one-shot capacity at the moment.

2.   A more interesting and only slightly less easy-to-explain encoding for fixed-base values seems able, on random average, to get asymptotically maximal use from a punch card. As an example, a single 27-cell card can convey 25 decimal places of $\,\ln 2$, i.e, 0.6931471805599453094172321, one  digit at a time, with only 25 holes punched.

•   The card's 27 punch cells are weighted 1, 1, 1, 2, 2, 2, 3, 3, 3, . . . , 8, 8, 8, 9, 9, 9.
•   To read the current value, take the last digit of the sum of all currently-punched cells' weights.
•   To store a new value, punch the fewest not-yet-punched cells whose weights add up to the difference, modulo 10, between the current and new values. Except, though, if the new value matches the old value, when no new holes need to be punched. And if no combination of new holes can achieve the new value then the card is considered used up. $$n ~ = ~~ \Frac {\TEB}{\PC} ~~ = ~~ \Sfrac{ 25 \Logb 10 }{ 27 } ~~ = ~ 3.1$$

Not bad, as the most information this card could possibly convey, even if its history were in play, is a little more than the equivalent of 31 decimal digits for $~ \Nsub{perfect} = 3.8 ~$ (elaborated later).

Calling $n$ of the generalized approach here $\Nsub{additive} \Hair$, if the formulation that follows is valid then, for an arbitrary $m$, a card with $~ c = m \Hair 2^m \,\Pad{2mu}$ punchable cells yields (“$\small \sim$” being asymptotic equivalence):

$$\Nsub{additive} ~~\Arrow{ c = m \Hair 2^m \to \, \infty }~~~ m ~~\sim~~ \Logb c ~~\sim~~ \Nsub{perfect}$$

This approach always encodes a base-$\raise1mu{\small(} 2^m \raise2mu{{\scriptsize\kern-1mu +}} 1 \raise1mu{\small)}$ value from $0$ through $2^m$ and, for the sake of simpler calculations, differs in inconsequentially detrimental ways from the 27-cell example above.

•   Each cell is weighted by a random integer from $1$ through $2^m \Tight$.
•   To read a card's current value, add up the weights of all punched cells, modulo $2^m\Pluss1$.
•   To store a new value, when different from the current value, punch one not-yet-punched cell whose weight is the difference, modulo $2^m\Pluss1 \Pad{-2mu}$. If that weight is not available for punching, revise the card's current value by punching a random hole, then try again to store the same new value.

Here comes a table with supporting formulations, optimistically without rigor. For convenience:
$\kern2em \llap{b} ~ = ~~ \rlap{ 2^m + 1 } \Pad{6mu}\Pad{-6mu} \kern7em$ (fixed base of values, which range from $0$ through $2^m$)
$\kern2em \llap{p} ~ = ~~ \rlap{ \Sfrac{1}{b\Minus1} ~~ = ~~ m{/}c } \kern7em$ (probability that a random non-0 value matches a given non-0 value)
$\kern2em \llap{q} ~ = ~~ \rlap{ 1 - p } \Pad{4mu} \kern7em$ (probability that a given cell has an undesired weight)

$$\def \L {\kern-7mu} \def \R {\kern-16mu} \def \Star { ~~~~~~ \color{#9c0}{\huge\raise-1mu\star} } \def \U #1{ \underline{\strut~{#1}~} } \def \Thirds #1#2#3#4#5{ \kern#1 \llap{#2} {#3} \rlap{#4} \kern#5 } \def \POf #1#2{ \Thirds {1.6em} {#1} {~\T{of}\,~} {#2} {1.4em} } \def \PHalves #1#2{ \rlap{ \kern 4.2em \llap{#1~~} \rlap{#2} } } \def \PUses #1#2#3{ \Thirds {4.2em} {#1} {#2} {#3} {4.1em} } \def \AOf #1{ \Thirds {1.7em} {#1} {~\T{of}\,~} {b} {1.7em} } \def \AHalves #1#2{ \rlap{ \kern 5.1em \llap{#1~~} \rlap{#2} } } \def \AUses #1#2#3{ \Thirds {6.8em} {#1} {#2} {#3} {2.9em} } \def \POfT #1#2{ \POf{\T{#1}}{#2} } \def \PUsesTimes #1#2{ \PUses {#1 \kern1mu} {\kern2mu \SStimes \,} {#2} } \def \PUsesLog #1#2{ \PUsesTimes { \big( 1 \PlusR \Sfrac{1}{#1} \big) \! }{ \Logb #2 } } \def \PUsesOne #1{ \PUsesTimes { \Sfrac{1}{1} \kern#1 }{ 1 } } \def \AOfT #1{ \AOf{\T{#1}} } \def \AUsesTimes #1#2{ \AUses { #1 \big( #2 \big) \kern-1mu } {\kern2mu \SStimes \,} {\kern1mu \Logb b } } \def \AUsesQ #1{ \AUsesTimes { ( 1 \MinusXR #1 ) } { 1 \PlusR \Sfrac{1}{b\Minus1} } } \begin{array}{c|cc|cc} \L & \U{\Nsub{perfect}} & \U{\Nsub{perfect} } & \U{\Nsub{additive}} & \U{\Nsub{additive}} \R\\[-1mu] \L \T{Number of} & \T{ Number of } & \T{ Expected } & \T{ Number of } & \T{ Expected } \R\\[-5mu] \L \T{unpunched} & \T{ possible } & \T{number of uses } & \T{ possible } & \T{number of uses } \R\\[-5mu] \L \T{ cells } & \T{ values } & \SStimes ~ \T{equivalent bits} & \T{ values } & \SStimes ~ \T{equivalent bits} \R\\[11mu] \hline \L c & \POf { 1 }{ 2 } & \PUsesOne{ 14mu } & \AOf {1} & \AUsesTimes{\Sfrac{1}{b}~}{\Sfrac{1}{b\Minus1}} \R\\ \L c-1 & \POfT {all}{ c } & \PUsesLog{c\Minus1}{ c } & \AOf {b\Minus1} & \AUsesQ { q^ c } \R\\ \L c-2 & \POfT {all}{c\Minus1} & \PUsesLog{c\Minus2}{(c\Minus1)} & \AOfT {all} & \AUsesQ { q^{c\Minus1} } \R\\[-.5ex] \L \vdots & & \PUses {}{\vdots}{} & & \AUses {\vdots\kern34mu}{}{} \R\\[.5ex] \L 2 & \POfT {all}{ 3 } & \PUsesLog{ 2 }{ 3 } & \AOfT {all} & \AUsesQ { q^3 } \R\\ \L 1 & \POfT{both}{ 2 } & \PUsesLog{ 1 }{ 2 } & \AOfT {all} & \AUsesQ { q^2 } \R\\ \L 0 & \POf { 1 }{ 2 } & \PUsesOne{ 6mu } & \AOfT {all} & \AUsesQ { q } \R\\[1ex] \hline \L \Pad{1ex} \L \T{ Total } & \PHalves{ c \Ttimes \Nsub{perfect} ~ = }{ } & & \AHalves{ c \Ttimes \Nsub{additive} ~ = }{ } & \R\\[-.5ex] \L \raise2ex\T{bits} & & \kern8.9em \llap{ \displaystyle 2 + \sum_{i=2}^c \Logb i + \sum_{i=2}^c\Sfrac{\Logb i}{i \MinusL 1} } & & \AUsesTimes{ \Sfrac{1}{b^2{-}b} + \Big( c - \Sfrac{q \MinusR q^{c \PlusL 1}}{1 \MinusRR q} \Big) }{ \Sfrac{b}{b\Minus1} } \R\\[.5ex] \L & \PHalves{ \sim }{ \Logbb c \Hairr ! } & & \AHalves{ \Arrow{c = m \Hair 2^m \to \, \infty} }{ \big( c \MinusL \Sfrac{1}{\raise-1mu p} \big) \Hair \Logbb (2^m\Pluss1) } & \R\\[1ex] \L & \PHalves{ \sim }{ \Logb \Hair \sqrt{2 \pi c} \, \big( \Sfrac{c}{e} \big)^c } & & \AHalves{ \sim }{ c \Hairr m - \Sfrac{m}{m{/}c} } & \R\\[1ex] \L & \PHalves{ \sim }{ c \Hair \Logb c } & & \AHalves{ \sim }{ c \Hairr m } & \R\\[2ex] \hline \L \Pad{1ex} \L n & \PHalves{ \Nsub{perfect} ~ \sim }{ \Sfrac{c \Hair\Logb c}{c} } & & \AHalves{ \Nsub{additive} ~ \sim }{ \Sfrac{c \Hairr m}{c} ~~ = ~~~ m \Star } & \R\\[-.5ex] \L & \PHalves{ = }{ \Logb c \Star } & & \AHalves{ = }{ \Logb 2^m } & \R\\[.7ex] \L & & & \AHalves{ \sim }{ \Logbb (m \Hair 2^m) } & \R\\[.7ex] \L & & & \AHalves{ = }{ \Logb c ~~~~~~ \Star } & \R\\ \end{array}$$

Sure enough, looks like $~ \Nsub{additive} ~\sim~ m ~\sim~ \Logb c ~\sim~ \Nsub{perfect} \Hair$.

“$\T{Number of possible values}$” is interestingly anomalous for unpunched cards as well as for fully punched cards. Their values here are debatable, but at least they don't affect asymptotic behavior.

“$\T{Expected number of uses}$” combines one or two probabilities. In the row for $2$ unpunched cells, e.g:
i.  $(1 \MinusRR q^3) ~\Pad{11mu}\Pad{-4mu}$ under $\Nsub{additive}$ is the probability that the desired value-difference weight happened to be available for punching when the card had $3$ unpunched cells.
ii.  $\big( 1 \PlusR \Sfrac{1}{b\Minus1} \big) ~\Pad{16mu}\Pad{-12mu}$ under $\Nsub{additive}$ indicates that, whenever a card is used as punched, it gets an average of $~ \Sfrac{1}{b\Minus1} ~$ additional uses for free, as subsequent values might repeat the current value. The corresponding $~ \big( 1 \PlusR \Sfrac{1}{2} \big) \Hair\Pad{9mu}\Pad{-9mu}$ under $\Nsub{perfect}$ varies by row, because so does the number of values that would not be repeats. By the way, $~ \Sfrac {1}{b\Minus1} = \Sfrac {1}{b} \Stimes\Sfrac {b\Minus1}{b}\Stimes\Hair 1 \,\T {extra use} + \Sfrac{1}{b^2}\Stimes\Sfrac{b\Minus1}{b} \Stimes\Hairr 2 \,\T{extra uses} + \cdots \,$.

About that 27-cell example and $\Nsub{perfect}$
For $~ c = 27 \Pad{21mu}$, the table gives $~ \displaystyle c \Ttimes \Nsub{perfect} = 2 + \sum_{i=2}^{27} \Logb i + \sum_{i=2}^{27} \Sfrac{\Logb i}{i \MinusL 1} = 103.5$ total equivalent bits, so $\Pad{5mu}\Pad{-11mu} ~ \Nsub{perfect} = \Frac {\TEB}{\PC} = \Sfrac {103.5}{27} = 3.8 \Hair$. Likewise, the formulation of $\, c \Ttimes \Nsub{additive} \,$ predicts an expected average measure, instead of the $~ n=3.1 ~$ achieved in the example, of $~ \Nsub{decimal} = ~ \Big( \Sfrac{1}{90} + \Bigg( 27 - \Sfrac{\SSfrac89 \MinusLR \big( \SSfrac89 \big)^{\! 28}} {\SSfrac19} \Bigg) \Sfrac{10}{9}\Logb 10 \Big) { \large / } 27 = 2.6^+ \Pad{28mu}\Pad{-24mu}$, which is ever so close to the $~ n = \Sfrac{ 21 \Logb 10 }{ 27 } = 2.6^- ~\Pad{-14mu}$ that corresponds to the 21 decimal places conveyed before the two holes for the 22nd digit were selected nonrandomly.

Side note: The Degenerate Case of the Fourfold Use

Back to the smaller-is-better idea of a 1-cell card, binary use of a single-cell card works surprisingly well too. Using 27 single-cell cards for the same value as in the 27-cell example, $\ln 2 \Hair$, a whopping 121 fraction bits are conveyed: 0.1 011 0001 0111 001 00001 01111111 011111 01 000111 001111 01111 0011 01 01 01111 001 001111 000111 011 00111 0011 000000000111111 001 01111 011 01. That's equivalent to 36.5 decimal places and a surreal $~ n_{\small 27} \, = \Sfrac{121}{27} = \, 4.5 ~$ bits/cell. However:
•   The segment 000000000111111 is quite an outlier. Disregarding its 15 bits makes some difference, leaving $n_{\small 26} \, = \Sfrac{106}{26} = \, 4.1$ bits/cell.
•   For binary, $~ n \approx 4 ~$ actually does make sense. Each value can be expected to have an average of one additional reuse due to consecutively repeated values. And the hole doesn't need to be punched for the initial value of any card except the very first, as that value will be $0$ for each subsequent card.

Epilogue: The Case of the Surprisingly Simple Solution

It all began like so many puzzles here. No sooner had a poster posed a puzzle with an alluring premise than a thrilling solution was pulled off in broad daylight by a f''amiliar perpetrator. A solution so swift and devious that the original poser felt compelled to display their ur  solution as well. Not much else left to do, apparently, except to strew some smarty-pants comments.
With that accomplished, something nonetheless seemed amiss. Was a different solution still on the loose? The poser dangled fresh bait by mounting a companion piece on a fixed base. The puzzle became an adventure when a discarded early hunch —okay, a smarty-pants comment— returned as a clue, leading to the hidey-hole of the one-eyed punch card. (Encoding #1 at the top of this post.) For reassurance that all solutions had at last been rounded up, Sherlock Holmes outlined a crudely outlandish scheme as an impossibility to be eliminated. But Scotland Yard botched the mathematical labwork and mistakenly considered this straw-man scenario plausible after all (a nascent encoding #2 of this post).
Ensuing paperwork inevitably revealed many flaws, so the investigation was appropriately shelved. While off duty, the inspectors regrouped, tried to rework the embarrassingly improbable into the possibly probabilistic, and seemed to be onto something, but didn't know how to present probable cause to the grand jury.
For instance, the detectives had zeroed in on some prime evidence on $\large e$ Street but the puzzle had been committed some distance away, at the $\small\rm Log_2\!$ Club. In the spirit of peccable puzzle-police work, this was resolved by disguising that evidence and planting it at the original scene. For this, two bit players, $b$ and $c$, plucked from a number-lineup, agreed to help in exchange for a sweet taste of power (2m&m's).

So encoding #2 was assembled from a variety of surprising pieces, some unmentioned. Many of the steps were characteristic of a bumbling Inspector Clouseau stumbling over serendipitous answers while trying to complicate things with one shot in the dark after another. After chancing on some optimal pieces, a puzzle-within-a-puzzle was to find similar-enough pieces that would fit together without toooo much mathematical mess. Thanks to the largesse of large numbers and the ratio-nullifying nature of logarithms, some intuitively contrived formulations could stand in for optimal ones that they only vaguely resemble. (Then again, the later labwork may contain mistakes too.) $\endgroup$

Maybe I'm too early to post this, but an alternative approach (similar to what f'' did):

Have a card with $4k$ punchable cells. The first write will encode a number from $1$ to $4k$, simply by punching the hole at that offset. For $j>1$, the $j$th write always selects a hole with no holes adjacent to it, and punches a hole next to it (before or after; doesn't matter), and encodes a number $m$ from $1$ to $4(k-j+1)$ by punching a hole at the $m$th of those offsets that are not adjacent to any hole (this is decodable). There are $k$ writes (at least), and a total of $\log_2 (4(k!))$ bits of data to encode, and $\frac{\log_2 (4(k!))}{4k}$ is unbounded.

And just as a curiosity, here is a fixed-base 3 times writable encoding that works on smaller cards too (thus possibly more practical).

• So to decode we need to figure out how many times the card has been written; and this is available from the number of adjacent holes on the card? Could you explain what happens when adding adjacent holes makes 3 in a row? – Jonathan Allan Apr 25 '16 at 18:57
• @JonathanAllan You don't need to know that. Just count the cells not adjacent to any holes (starting from the left), until you arrive to the first such cell that is itself a hole. What you counted is what was encoded. – BaSzAt Apr 25 '16 at 19:01
• @JonathanAllan 3 in a row makes no difference. The only constraining circumstance is that adding an adjacent hole can, in the worst case, decrease the number of offsets suitable for $m$ by 4. – BaSzAt Apr 25 '16 at 19:04
• OK got it, we are encoding much smaller number in our writes than capacity. – Jonathan Allan Apr 25 '16 at 19:04
• @JonathanAllan Correct. But we are encoding very many numbers : ) – BaSzAt Apr 25 '16 at 19:05