2
$\begingroup$

I have been observing her for just over a week now. She had seen me but didn't know she was being watched. As people pass she hands them a piece of paper. Some even stop and put money in a cigar box at her feet. When that happens, I write down the word found in the discarded piece of paper—but I am not perfect, no one is.

The following strings seem to be valid...

GB1XUH   
XMATFU   
91A6JY   
CXSOZQ   
KA40A5   
WMYMDC   
43RM26   
7330GE   
MOE21I

But the following strings do not seem to be valid...

EPWC4X
YK7JSA
NOS0QZ
GSIG0C
S5QH80
9W2JVM
JN8J2H
STVFSS
PXGSG7

How do I generate a valid string? I am getting desperate, I need that money so much...

Hint:

1 out of 36 random strings is a valid string

$\endgroup$
  • 1
    $\begingroup$ You might want to add some negative cases: without the hint, all strings are valid is a perfectly fine answer $\endgroup$ – boboquack Sep 22 '17 at 8:34
  • $\begingroup$ @boboquack Thank you for your feedback! Edited. $\endgroup$ – DIVVS IVLIVS Sep 22 '17 at 8:55
  • $\begingroup$ @JonMarkPerry Thank you for your feedback! Edited. $\endgroup$ – DIVVS IVLIVS Sep 22 '17 at 9:50
2
$\begingroup$

I am pretty sure this is not an intended solution, I just want to point out that the way the questions is posed is not completely satisfying.

There are a lot of solutions which separate the sets. Let us consider just a simple mapping $f:C \rightarrow \mathbb{Z}_{36}$, where each word is an element in $C^6$ and $(c_1,...c_6) \in C^6$ is evaluated as $\sum f(c_i) \bmod 36$. Here is such a mapping

{'1': 10, '0': 32, '3': 5, '2': 35, '5': 25, '4': 13, '7': 26, '6': 23, '9': 2, '8': 18, 'A': 4, 'C': 3, 'B': 1, 'E': 34, 'D': 20, 'G': 6, 'F': 0, 'I': 15, 'H': 8, 'K': 30, 'J': 2, 'M': 21, 'L': 9, 'O': 29, 'N': 16, 'Q': 17, 'P': 7, 'S': 14, 'R': 11, 'U': 19, 'T': 0, 'W': 12, 'V': 33, 'Y': 31, 'X': 28, 'Z': 17}

which produces an element-wise sum congruent $0 \bmod 36$.

43RM26 0 7330GE 0 MOE21I 0 GB1XUH 0 XMATFU 0 91A6JY 0 KA40A5 0 WMYMDC 0 CXSOZQ 0 ......... EPWC4X 25 YK7JSA 35 NOS0QZ 17 GSIG0C 4 S5QH80 6 9W2JVM 33 JN8J2H 9 STVFSS 3 PXGSG7 15

Another is

{'1': 24, '0': 3, '3': 17, '2': 4, '5': 8, '4': 29, '7': 2, '6': 25, '9': 18, '8': 9, 'A': 30, 'C': 13, 'B': 0, 'E': 19, 'D': 33, 'G': 14, 'F': 1, 'I': 16, 'H': 15, 'K': 8, 'J': 6, 'M': 23, 'L': 31, 'O': 22, 'N': 26, 'Q': 20, 'P': 28, 'S': 7, 'R': 10, 'U': 21, 'T': 35, 'W': 11, 'V': 32, 'Y': 5, 'X': 34, 'Z': 12}

This fits with the hint that a randomly chosen string is valid with probability $1/36$.

It is easy to find since most of the strings in the valid set have one or more free variables which can be used to zero out the sum. Just pick a random map for the variables that occur at least twice. Then, pick the remaining ones such that it does not occur in the set (I am assuming here that the map is invertible -- if it is not, the problem is even easier). This requires little bit of iteration. Then check if the invalid strings are all non-zero. Otherwise, repeat.

$\endgroup$
  • $\begingroup$ ^vote for the analysis. I nonetheless trust there's something particularly interesting about the specifically intended solution. $\endgroup$ – humn Sep 22 '17 at 22:07

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.