|
| |
|
|
A253548
|
|
Minimal width k for a paper tape such that n symbols can be encoded on a k-hole paper tape so that a used paper tape can always be reused at least once.
|
|
0
|
|
|
|
1, 2, 3, 3, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
This sequence is the inverse of A253426.
Since many people are not familiar with punch paper tape technology, we provide the following more formal description of the sequence, where each row on an a(n)-hole paper tape is represented as an a(n)-digit binary string, and nonzero bits correspond to punched holes.
a(n) is the minimum number of binary digits that allows n symbols to be encoded as a(n)-bit binary strings, such that the symbol set S has two separate a(n)-bit encoding schemes (E1 and E2), and for each pair of symbols s and t (where s != t), the E1 encoding of s can be transformed to the E1 or E2 encoding of t by flipping one or more bits from 0 to 1.
Each symbol in S has exactly one encoding in E1. Each symbol in S has one or more encodings in E2.
Each a(n)-bit encoding in E1 and E2 must map to exactly one symbol; thus, two different symbols cannot share the same a(n)-bit encoding.
This sequence was inspired by the Punch-22 puzzle (see Kennedy link).
Ronald L. Rivest and Adi Shamir explored these types of problems extensively in their 1982 paper entitled 'How to Reuse a "Write-Once" Memory' (see Links). The paper provides a solution to the Punch-22 puzzle; thus, a(26) <= 7. The paper states that a(29) cannot be 7. Using notation from their paper, a(n) is equal to the minimum k such that an <n>^2/k WOM-code exists.
Juan Cristobal Olivares solved the Punch-22 puzzle (see Links).
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Example for n = 2: Symbol set S is ('A', 'B'). Encoding scheme E1 is ( 'A' => 00, 'B' => 01 ), and encoding scheme E2 is ( 'A' => 11, 'B' => 10 ). The symbol 'A' encoded as 00 can be transformed to 'B' encoded as 10 by flipping the leftmost bit from 0 to 1. The symbol 'B' encoded as 01 can be transformed to 'A' encoded as 11 by flipping the leftmost bit from 0 to 1.
Example for n = 4: Symbol set S is ('A', 'B', 'C', 'D'). Encoding scheme E1 is ( 'A' => 000, 'B' => 001, 'C' => 010, 'D' => 100 ), and encoding scheme E2 is ( 'A' => 111, 'B' => 110, 'C' => 101, 'D' => 011 ). The symbol 'B' encoded as 001 can be transformed to 'C' encoded as 101 by flipping the leftmost bit from 0 to 1. The symbol 'B' encoded as 001 can be transformed to 'A' encoded as 111 by flipping the leftmost two bits from 0 to 1.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more,hard
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
