12
$\begingroup$
INT. JULIAN'S HOUSE – BASEMENT

JULIAN, rumpled, tired, and bewildered, sits at a shabby card table poring over
BLUEPRINTS of a complicated mechanism.  NAOMI hastily enters the room carrying a
PAD OF GRAPH PAPER and a BALLPOINT PEN.  She's just as sleep-deprived, but she's
taking it better.  She sits next to Julian.  He shoves the blueprints away and
leans back in his chair.

                                     JULIAN
        I've got nothing.  Even if the duplicator could hit one of
        these parts, we'd just jam the lock.  There's not enough room
        in here.

                                     NAOMI
        Don't worry about it.  We don't have to hit the lock.

Julian raises an eyebrow, intrigued…

                                 NAOMI (cont'd)
        The mechanism runs on dot numbers.  Like this.

On the graph paper she draws
A MULTIPLICATION PROBLEM:

                                       ●○●●
                                        ●○●
                                     ------
                                       ●○●●
                                      ○○○○
                                     ●○●●
                                     ------
                                     ●○○●●●

                                 NAOMI (O.S.)
        The black circles are dots, and act like ones in binary.  The
        white circles are blanks and act like zeros.  Every dot number
        begins and ends with a dot, and they're multiplied like regular
        binary numbers—with one exception.  See that first blank in the
        result?  That's there 'cause there's no regrouping when the
        intermediate products are added.
BACK TO THE CONSPIRATORS

                                     JULIAN
        With you so far.

                                     NAOMI
        The lock's cryptosystem needs one dot number as its key, which
        it reads from a 10-meter punched tape that's fed in… here.  The
        key's supposed to be prime; it should only have lone dots and
        itself as factors.  If it's composite, any combination will get
        us in.

                                     JULIAN
        So you want to hit some symbols on the tape with the duplicator?
BACK TO THE GRAPH PAPER

                                 NAOMI (O.S.)
        Right.  Like, say we hit the blank in this prime.

She writes down ●●○● and then the same number with its blank duplicated:
●●○○●.

                                 JULIAN (O.S.)
        Er, that's no good.  It's still prime.

                                 NAOMI (O.S.)
        Ah, but the duplicator's power level can be set past 100%.  If
        we fired it at 200% or more, we'd only get that number for the
        first minute or so.  Since there'd still be a full charge's
        worth of duplication on the original blank, the number'd turn
        into this—

She writes ●●○○○● = ●○●● ✕ ●●●.

                              NAOMI (O.S., cont'd)
        —after the tape cooled down.  There'd be another duplication
        after another minute if we'd given it 300%, but we'd be in the
        safe by the time that happened.
BACK TO THE CONSPIRATORS

                                     JULIAN
        Not bad.  There's just one problem.

                                     NAOMI
        Yeah?

                                     JULIAN
        The tape is behind the safe's walls, where we can't see it.  We
        won't know what number is punched on it, and, while the material
        indicator will tell us when we're aiming at the tape, we won't
        know which symbol the duplicator's pointed at when we fire.

Naomi leans back and looks smug.  She's already thought of that.

What's Naomi's plan? If at most $n$ symbols can fit on a 10-meter tape, how many shots should the conspirators fire and at what power levels to guarantee that they will eventually get inside?

$\endgroup$
  • 3
    $\begingroup$ @JLee How does this look? The big code block was because I wanted proper screenplay formatting, but the markdown on Stack Exchange doesn't really do that. $\endgroup$ – Edward Jun 15 '15 at 16:45
  • 1
    $\begingroup$ Couple of questions: Is the tape already full of symbols? Meaning if we duplicate, we get $N+1$ symbols and one that exists on the tape is pushed off? If that is the case, which direction are the values pushing, toward the most or least significant bit? Finally, is there a maximum power level for the duplicator shot? $\endgroup$ – tfitzger Jun 17 '15 at 13:41
  • 1
    $\begingroup$ @Edward: Just to be sure I've understood the puzzle, I'll rephrase: The safe has a random dot-number of n characters. The code-crackers can (with each "shot") insert a character at position "p" which has to be duplicate of the character currently at "p". (so there are now 2 identical characters). If there is more strength, then they insert another and another etc at same position (so that there are now X identical characters). Each of this "steps" is evaluated for the win-situation. They "win" if the resulting dot-number is not a prime number. But: "p" is chosen randomly. Correct? $\endgroup$ – BmyGuest Jul 8 '15 at 10:58
  • 1
    $\begingroup$ An interesting point I discovered: although the 'dot numbers' bear some resemblance to the polynomials over GF(2), they don't form a field (or even a group!) since the sum of two dot numbers (which are always odd) are even, and is therefore not a dot number (plus there are no multiplicative inverses). $\endgroup$ – 2012rcampion Jul 9 '15 at 18:48
  • 2
    $\begingroup$ @2012rcampion If you allow negative powers and define an equivalence relation $\sim$ by $p\sim q$ iff $p=qx^n$ for some $n$, then the polynomial operations induce a multiring on the equivalence classes, and multiplication in that multiring is exactly dot-number multiplication. So, yep, definitely related. (That said, no knowledge of algebraic structures is necessary to solve this puzzle.) $\endgroup$ – Edward Jul 11 '15 at 4:09
7
$\begingroup$

If we use multiple shots, we have to account for the possibility that they all hit the same the same spot. Assuming that the duplicator has no power limit, we might as well use a single shot that is the sum of all the other shots' power levels. The question is to find how large of a shot this requires. $n=1$ is solved with a shot at 300% and $n=2$ takes 200%. The rest of this answer assumes that $n\ge3$.


First of all, Bmyguest's answer shows a pattern: every prime dot number except ●● has an odd number of filled dots. This is because any dot number with an even number of filled dots is divisible by ●●. If our shot hits a ●, then the dot number will become divisible by ●●. Therefore, we should assume that our shot will hit a ○. (As it turns out, the following strategy works even if we hit ● and don't consider divisibility by ●●.)

Let the original dot number be $P$. The ○ we hit divides $P$ into two parts. Let $A$ be the part on the left, with a length of $a$, and let $B$ be the part on the right, with a length of $b$, so that $n=a+b+1$.

Each dot number is equivalent to a polynomial in $\mathbb{Z}_2[x]$, and a dot number divides another if and only if their corresponding polynomials do. We have $P(x)=A(x)x^{b+1}+B(x)$ and we need to find some $i\in\mathbb{Z}^+$ such that $A(x)x^{b+1+i}+B(x)$ is composite.

$P(x)$ has degree $n-1$, so there are $2^{n-1}$ residue classes mod $P(x)$. Because $P(x)$ is irreducible, the order of $x$ mod $P(x)$ is a factor of $2^{n-1}-1$, so $P(x)$ divides $x^{2^{n-1}-1}-1$. Then, $A(x)x^{b+2^{n-1}}+B(x)\\=(A(x)x^{b+2^{n-1}}+B(x))-(A(x)x^{b+1}+B(x))+(A(x)x^{b+1}+B(x))\\=A(x)x^{b+1}(x^{2^{n-1}-1}-1)+P(x)$

Therefore, $P(x)$ divides $A(x)x^{b+2^{n-1}}+B(x)$, and we can take $i=2^{n-1}-1$. Translating back to dot numbers, if we fire a shot at $(2^{n-1}-1)\times100\%$ power, we are guaranteed to get a composite dot number (either divisible by ●● or by $P$).


This is probably extreme overkill: a brute force search shows that 200% is good enough for $n=7$, where this strategy would require a shot at 6300%.

$\endgroup$
  • 1
    $\begingroup$ To justify your statements: Multiplying a number by three converts runs of $1$s into a pair of $1$s separated by $0$s: $$ \begin{align} x &= \ldots 011\ldots 110 \ldots \\ 3x &= \ldots 100\ldots 010 \ldots \end{align} $$ Since the $1$s all occur in these pairs, every multiple of three has even parity. Going the other way, for every number with even parity, the $1$s can be gathered into pairs, which when divided by three, turn into a run of $1$s; therefore every number with even parity is divisible by three. $\endgroup$ – 2012rcampion Jul 10 '15 at 0:34
  • $\begingroup$ +1 for making the parity observation; adding an odd number of ●s is a nice simple way to breach the safe. But remember that they cannot aim for a particular symbol, so they might hit all ○s. $\endgroup$ – Edward Jul 11 '15 at 4:01
  • $\begingroup$ @Edward I've edited my answer to include a solution that accounts for hitting ○s. $\endgroup$ – f'' Jul 20 '15 at 11:03
  • 1
    $\begingroup$ Now nobody's going to believe me about "no knowledge of algebraic structures is necessary to solve this puzzle" :/. But still, that's a very pretty proof! $\endgroup$ – Edward Jul 25 '15 at 21:12
  • 1
    $\begingroup$ @BmyGuest Posted. Let me know if it's unclear. $\endgroup$ – Edward Jul 27 '15 at 1:58
5
$\begingroup$

Work in progress....

If I understood the puzzle correctly, then:

  • The safe has a random dot-number of n characters length which is a prime number.
  • The safe is cracked if this number is modified, such that it is no longer a prime number.
  • The number is modified by 'duplicating' a character at random position p up to c times, where c is the charge of the duplicator.
  • The safe-crackers can chose to fire x times with a chosen charge c, and we should find which c is needed, and how large x needs to be to guarantee success.
  • Only c is a parameter which can be chosen!

It is important to notice that

  • Dot-numbers start and end with a ●, so they have to be odd numbers
  • A Dot-number is prime if it can not be produced by multiplication of two other dot-numbers, where 'multiplication' follows the rules outlined in the puzzle and not regular binary multiplication.

With the above, my strategy to 'solve' this puzzle is to first

look at all (smaller) 'prime' numbers and try to establish a 'pattern'.

and then, in a second step

find how this pattern can be reliably 'broken' by duplicating characters at any position for up to c times.

There is maybe / quite likely a way to find dot-number primes more easily, but not being able to see this, I've started with a brute-force search for dot-number primes.

Primes up to 9 digits (unless I made a mistake) are:
dot( 1): ●
dot( 3): ●●
dot( 7): ●●●
dot( 11): ●○●●
dot( 13): ●●○●
dot( 19): ●○○●●
dot( 25): ●●○○●
dot( 31): ●●●●●
dot( 37): ●○○●○●
dot( 41): ●○●○○●
dot( 47): ●○●●●●
dot( 55): ●●○●●●
dot( 59): ●●●○●●
dot( 61): ●●●●○●
dot( 67): ●○○○○●●
dot( 73): ●○○●○○●
dot( 87): ●○●○●●●
dot( 91): ●○●●○●●
dot( 97): ●●○○○○●
dot(1○3): ●●○○●●●
dot(1○9): ●●○●●○●
dot(115): ●●●○○●●
dot(117): ●●●○●○●
dot(131): ●○○○○○●●
dot(137): ●○○○●○○●
dot(143): ●○○○●●●●
dot(145): ●○○●○○○●
dot(157): ●○○●●●○●
dot(167): ●○●○○●●●
dot(171): ●○●○●○●●
dot(185): ●○●●●○○●
dot(191): ●○●●●●●●
dot(193): ●●○○○○○●
dot(2○3): ●●○○●○●●
dot(211): ●●○●○○●●
dot(213): ●●○●○●○●
dot(229): ●●●○○●○●
dot(239): ●●●○●●●●
dot(241): ●●●●○○○●
dot(247): ●●●●○●●●
dot(253): ●●●●●●○●
dot(283): ●○○○●●○●●
dot(285): ●○○○●●●○●
dot(299): ●○○●○●○●●
dot(3○1): ●○○●○●●○●
dot(313): ●○○●●●○○●
dot(319): ●○○●●●●●●
dot(333): ●○●○○●●○●
dot(351): ●○●○●●●●●
dot(355): ●○●●○○○●●
dot(357): ●○●●○○●○●
dot(361): ●○●●○●○○●
dot(369): ●○●●●○○○●
dot(375): ●○●●●○●●●
dot(379): ●○●●●●○●●
dot(391): ●●○○○○●●●
dot(395): ●●○○○●○●●
dot(397): ●●○○○●●○●
dot(415): ●●○○●●●●●
dot(419): ●●○●○○○●●
dot(425): ●●○●○●○○●
dot(433): ●●○●●○○○●
dot(445): ●●○●●●●○●
dot(451): ●●●○○○○●●
dot(463): ●●●○○●●●●
dot(471): ●●●○●○●●●
dot(477): ●●●○●●●○●
dot(487): ●●●●○○●●●
dot(499): ●●●●●○○●●
dot(5○1): ●●●●●○●○●
dot(5○5): ●●●●●●○○●

From this one can notice:

- Dot-number primes come in symmetric pairs, i.e. any prime can be read from first to last digit or from last to first digit and remains a prime.
- With increasing digits there are 1, 1, 1, 2, 3, 6, 9, 18, 30 prime numbers.
- ...? T.B.C

$\endgroup$
4
$\begingroup$

(This is the solution I was thinking of when I gave the puzzle, given in response to a query by BmyGuest. It avoids the use of facts about fields, but is conceptually almost identical to the accepted answer by f'', and could be read as an exposition of that argument.)

As f'' says, all the shots may hit the same symbol, so we might as well just use one shot. And as argued in the other answers, if the duplicator hits any ● with at least 300% charge, entry is guaranteed. We just need to know how much charge hitting a ○ would require.

Call a dot number with only two dots a translation (cf. the subexpression $x^{2^{n-1}-1}-1$ in the answer by f''). By adding a translation to some other dot number $x$ at an appropriate location, we can move one of $x$ 's dots around. For example, we can take the second dot in ●○●○●●● and slide it far to the left:

●○●○●●● ●○○○○○○○● ---------- ●○○○○○●○○○●●●
By adding a translation in several places, we can shift an entire portion of a dot number (cf. the subexpression $A(x)x^{b+1}(x^{2^{n-1}-1}-1)$ in the answer by f''). In particular, we can replicate the effects of the duplicator hitting a ○ at $(\mathrm{length}(t) - 1)\cdot 100$%:

●○●○●●● ●○○○○○○○● ●○○○○○○○● ----------- ●○●○○○○○○○○○●●●
So if we call the original dot number $x$ and have a translation $t$ that is divisible by $x$, hitting a ○ in $x$ at $(\mathrm{length}(t) - 1)\cdot 100$% (or more) power will yield a sum of numbers divisible by $x$, i.e., a non-prime.

How then can we find a suitable, and preferably short $t$? Let's start by asking a simpler question: if we have two dot numbers, $x$ and $y$, how can we check whether $x$ is a factor of $y$?

With natural numbers, we would work the long multiplication backwards to see if there's a number that, when multiplied by $x$, produces $y$; this process is just long division. The same working-backwards strategy applies here, but we have to remember that the addition did not carry, so our subtraction (the part that works the addition backwards) must not borrow. For instance, here's Naomi's original problem as long division, where getting no remainder tells us that ●○○●●● is divisible by ●○●●:

●○● ------ ●○●●|●○○●●● -●○●● ------ ○●○●● - ○○○○ ------ ●○●● - ●○●● ------
(Notice how the first subtraction does not borrow, just as the corresponding addition did not carry.)

In this case our $y$ should be a short translation, so let's run the division on $●○\cdots$ and stop the moment that a dot on the end would have given us no remainder, assuming such a moment ever comes. An example, with some intermediate values labeled for later:

●○●●●... -------- ●○●●|●○○○○○○○... ←z_0 -●○●● ------ ○●●○○○○... ←z_1 - ○○○○ ------ ●●○○○○... ←z_2 - ●○●● ------ ●●●○○... ←z_3 - ●○●● ------ ●○●○... ←z_4 - ●○●● -------- ○○●... ←z_5
Here we wanted that last ○ to be a ●, which tells us that ●○○○○○○● is the shortest translation divisible by ●○●●.

Now observe the $z$s. While the first $\mathrm{length}(x) - 1$ symbols could be anything but all blanks, the rest must be ○s, so the $z$s can take on at most $2^{\mathrm{length}(x) - 1}-1$ distinct values; make these values the vertices of a graph (cf. the $2^{n-1}-1$ residue classes in the answer by f''). Continuing, if we know $z_i$, we can deduce $z_{i+1}$ by xoring $x$ at the beginning only if $z_i$ begins with a ●; let this pattern define the directed edges of our graph, making it functional. Similarly, if we know $z_{i+1}$, we can recover $z_i$ by xoring $x$ at the end of its prefix, but only when that prefix ends with a ●. Therefore, the graph's reverse is also functional.

But a functional graph whose reverse is also functional must be the disjoint union of directed cycles. So if we start with $●○\cdots$, we must eventually get back there, and thus find a lone dot that can be eliminated from the remainder by the other end of our translation. Which is to say that $t$ exists, and in particular corresponds to a charge of 100% times the length of the cycle containing $●○\cdots$.

This cycle length is no more than the number of vertices, $2^{\mathrm{length}(x) - 1}-1$, which is in turn no more than $2^{n-1}-1$. So one shot at $\max(3,2^{n-1}-1)\cdot 100$% power will do.

$\endgroup$
  • $\begingroup$ What's the etiquette on asker's solutions to challenge questions? I can't get this in a comment; should I make it community wiki so I'm not scumming rep off my own question? $\endgroup$ – Edward Jul 27 '15 at 2:00
  • 1
    $\begingroup$ "Scumming?" Personally, seeing how much thought went into this solution, I think you deserve it! +1! $\endgroup$ – 2012rcampion Jul 27 '15 at 2:41
  • $\begingroup$ Well, all of the key points were already covered by f''. I've edited the answer to make this clearer. $\endgroup$ – Edward Jul 27 '15 at 3:28
  • $\begingroup$ Thanks. I'll have to digest this in a peaceful period - just like I needed for the question to sink in. Don't worry about self-rep. Rep should indicate that you're doing 'good' in the spirit of the site. Addin a clean answer, doing edits and making sure your posting plus answer is of good 'value' for futire absolutely is worth all the rep you get! It is not a high score for puzzle solving! $\endgroup$ – BmyGuest Jul 27 '15 at 5:01
2
$\begingroup$

The conspirators should fire

$n$ shots, all at a $1\times$ charge.

Consider a dot number such that every other digit is zero:

$$ x = 10a0b\ldots 0c01_2 $$

Partition the digits into pairs (with an implicit leading zero):

$$ x = 01\ 0a\ 0b\ldots0c\ 01_2 $$

Now triple this number (multiply it by $11_2$):

$$ \begin{array}{rrrrrrr} x & 01&0a&0b&\ldots&0c&01_2\\ \oplus~2x & 10&a0&b0&\ldots&c0&10_2\\ \hline 3x & 11&aa&bb&\ldots&cc&11_2 \end{array} $$

Thus,

If we duplicate every digit of a number, the resulting number ($3x$) is guaranteed to be a product of three and the same number with every other digit zeroed ($x$), and therefore not a dot-prime.

$\endgroup$
  • $\begingroup$ Very clever! But I'm afraid there's no guarantee that distinct shots hit distinct locations. $\endgroup$ – Edward Jul 11 '15 at 4:03
  • $\begingroup$ @Edward That's what I thought, but it was worth a try =) $\endgroup$ – 2012rcampion Jul 11 '15 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.