6
$\begingroup$

I wrote the following puzzle a couple of years ago. Since I no longer remember the solution, I feel it's a good enough puzzle to share.

On accusation of littering, you and your assistant are arrested and charged by a corrupt government. The government is attempting to follow the remnants of its misunderstood constitution, while incarcerating as many criminals as possible. The prosecutor explains what will happen:

  1. You and your assistant will be allowed as much time as necessary to prepare for your defense. The prosecutor's office will monitor your preparations.
  2. The court will separate you until the end of the trial.
  3. The court will give to each of you a list of ten words you may not speak at trial. If you speak any of these words at trial, you will be held in contempt and jailed.
  4. You will each enter a statement. Your statement may be any one of the words in the court's official dictionary.
  5. The court will inform each of you of the statement made by the other.
  6. You will each give testimony. Your testimony must be any one of the words in the court's official dictionary. If your testimonies do not match you will be convicted of perjury and imprisoned.
  7. The court will ask the prosecution to present its case. If this happens, the prosecution will present no evidence and you will be released.

The prosecutor gives you two copies of the court's official dictionary which you may use during the proceedings. A review on the cover says that it contains over one hundred and seventy thousand different words.

You have a strong feeling that the prosecutor's office and the court will collude in any and every way possible to either convict you or hold you in contempt. The court may decide to issue different lists of banned words to each of you. The court may wait to prepare the list of proscribed words for one of you until after the other has entered a statement. It is unlikely that, if you are jailed for contempt or imprisoned for perjury, you will ever be released. You and your assistant are given time to prepare.

What do you do?

$\endgroup$
  • $\begingroup$ Give up, they're unspeakable, no point in even trying :D $\endgroup$ – warspyking Feb 16 '15 at 4:06
  • $\begingroup$ Point 6 says "testimonies". Are you giving multiple testimonies, or is your assistant giving one as well? $\endgroup$ – Bulldogg6404 Feb 16 '15 at 5:11
  • $\begingroup$ @Bulldogg6404 Your assistant is giving one as well. Each of you submits only a single word of testimony. $\endgroup$ – Cirdec Feb 16 '15 at 5:15
  • 1
    $\begingroup$ > <spoiler> Answer: remain at step 1. :) </spoiler> $\endgroup$ – Lawrence Feb 16 '15 at 5:59
  • $\begingroup$ Trying to incarcerate as many criminals as possible does not necessarily indicate corruption, and the procedures outlined here are not very good for achieving that result. Perhaps you mean they're trying to incarcerate as many suspects as possible, without bothering to find out if they're actually criminals, $\endgroup$ – Mike Scott Feb 16 '15 at 13:12
6
$\begingroup$

As a statement, enter a word such that

  1. You can legally say any word starting with the same letter
  2. The dictionary contains at least 11 words starting with the same letter

Your assistant's statement should be a number n such that for every letter, he can play the nth word in the dictionary that starts with that letter. There will always be an n less than or equal to 11. Of course in practice your assistant has to give a word instead of a number (unless numbers are in the dictionary!). Just use the nth word in the dictionary to represent n.

As testimony, you both give the nth word starting with the letter you indicated.

You may have to adapt this method if the official dictionary is as pernicious as the rest of the trial, specifically if fewer than 11 letters have 11 or more words. But since it sounds like you're given the dictionary ahead of time, you have time to coordinate this.

$\endgroup$
  • $\begingroup$ Perfect. There are two classes of solutions that I know about. This one takes advantage of the fact there are at least (10 [bans]+1)^(2 [prisoners]) words in the dictionary. The other class of solutions takes advantage of the fact there are at least (2 [prisoners]+1)^(10 [bans]) words in the dictionary. It requires about five hundred times as much work. I'm sure your assistant will appreciate only needing to use (and count through) a page or two from the dictionary rather than a third of the tome. $\endgroup$ – Cirdec Feb 16 '15 at 10:14
1
$\begingroup$

After much thought, I came up with a solution.

Notice that there are at least 170000 words in the dictionary; both you and the assistant assume that there are exactly 170000 words. Assign one individual to partition the dictionary the first way, and the other to do the second way.

  • Way #1:

    Notice that the 10 different words effectively partition the dictionary. By default they partition it into 11 pieces, but if we act as if the dictionary wraps around, we actually partition it into 10 pieces. This means that there must be a partition of length at least $\frac{170000}{10}-1 = 16999$. This first individual chooses the first word of this partition as the statement.

  • Way #2:

    This time, let's just treat the words as numbers to make this easier. Separate all the words into mod 10 equivalent classes (bins). There are $17000$ words in each bin. If one bin doesn't have a banned word, then choose the smallest word in that bin as our partition. If every bin does have a banned word, then choose any bin and choose the smallest word after the banned word. In this way, we guarantee a bin size of $16999$, just like in Way #1.

    Alternatively, you could just separate into mod 16999 (or smaller) equivalent bins, and choose any bin without a banned word that is largest in size. These two partitions are guaranteed to overlap. Each person chooses the first overlapping word (regular dictionary order) as the testimony.

  • $\endgroup$
    • $\begingroup$ This looks correct and is essentially equivalent to cew's answer. The smallest dictionary you can use contains 400 words - 10 partitions one way x 2 words in case the first one is banned, squared to handle the other way. This can be done, probably in a slightly simpler manner, using only 121 words. $\endgroup$ – Cirdec Feb 16 '15 at 10:18
    • $\begingroup$ The first hint I would have given for this problem was, "You can treat the dictionary as containing whatever words you want, as long as it doesn't have more than 170001 words". $\endgroup$ – Cirdec Feb 16 '15 at 10:23
    0
    $\begingroup$

    If I'm interpreting this correctly, the statement is just one word and the testimony is just one word. Our goal is to get the testimony of you and your assistant to match. That shouldn't be too hard (unless I misinterpreted anything). Here's what you do:

    Make your statement the first word in the court dictionary that you ARE allowed to speak. Your assistant should make her statement the first word in the dictionary that SHE is allowed to speak.

    Once you've done that, it's time for your testimony:

    Your testimony should be whichever of the two words comes later in the dictionary.

    Of course, you'll run into a small problem:

    Given that it's a corrupt government and you're at risk of going to jail for life for littering, they'll probably get you in the end.

    $\endgroup$
    • 1
      $\begingroup$ The court is pernicious. After monitoring your preparations, the court prepares the lists of banned words. They hand you a list containing the 1st word in the dictionary, but not the 2nd. Your assistant gets a list containing the 2nd word in the dictionary, but not the 1st. You submit your statement to the court, 2nd, the first word in the dictionary that you are allowed to speak. Your assistant submits a statement, 1st, the first word not on her banned list. You have agreed that your testimony should be 2nd, but 2nd is on your assistant's banned list; she is held in contempt. $\endgroup$ – Cirdec Feb 16 '15 at 5:12
    • 2
      $\begingroup$ Cirdec beat me to it, I was about to point out that the court was monitoring the preparations and knew your strategy. The plan here will be to make a strategy that, even if the court knows it, they cannot beat. $\endgroup$ – Bulldogg6404 Feb 16 '15 at 5:15
    • $\begingroup$ Those jerks! Thank you for pointing out the flaw in my solution. I'll keep thinking. Am I right in my interpretation that the statement and testimony are each limited to one word or can they be longer? $\endgroup$ – Duncan Feb 16 '15 at 5:15
    • $\begingroup$ @Duncan You are correct in thinking that the statement and testimony are each limited to one word. It's a good thing your testimony only needs to be one word long (it would be great if you didn't have to give any and could skip to having the charges dropped). It would probably be nice if you could submit a longer statement though; I suspect the court got tired of hearing one hundred sixty-nine thousand nine hundred and ninety word statements. $\endgroup$ – Cirdec Feb 16 '15 at 5:20
    • $\begingroup$ Heh, well if the statement could be more than one word then it would only need to be 10 words long. Each person would just submit the 10 words that come right AFTER their banned words. Each person would know both lists of banned words, then, and could agree to speak the first (or last) word that isn't banned. $\endgroup$ – Duncan Feb 16 '15 at 5:25

    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.