Mathematically provable foresight, a puzzle

Created: September 12, 2024
Updated: October 04, 2024

A short puzzle

A group of students are taking an exam. After repeated cheating in previous years, the university is taking extreme caution: each student is separately confined to a personal desert island for the week before the exam and for the duration of the exam. The exam is delivered by helicopter on the penultimate day of their stay.

The university has taken all possible steps to ensure they can’t communicate with the other students or the outside world in any way for the entire duration of the exam. Since it will also be necessary to compute the answers to difficult math problems, the university has also furnished each desert island with a computer and power source. All of the computers have equivalent specs. None of them have an internet connection.

Exactly one day after they have all finished the exam, they are each airlifted off their islands and taken to a place where they can finally all communicate with each other.

On the first day of being on the desert island, one particular student, Alice, thinks she has outsmarted the university and has predicted the topic of one of the exam questions. To show off her impressive foresight, she wants to convince her peers that, with high probability, she correctly predicted one of the questions, and did so while on the island. How can she do this?

This problem is very loosely defined and so likely has lots of solutions, two of which are presented down below. But here are some solutions that I definitely want to rule out:

  • Creating a time-stamped file on the computer: This doesn’t work since they could also make the file after the exam has ended, and then fake the time-stamp. Any solution should assume all the students have full access to their computers.
  • Sealing the answer in an envelope at the start of their stay: This doesn’t work because they could have also sealed their “prediction” after the exam.
  • Posting publicly about it on the internet: This also counts as communication, and none of the computers have an internet connection.
  • Encoding the message in smoke signals: This also counts as communication between the students.









Solution

One solution is to make use of the computer. Let’s say that on day one, Alice guessed that “Bouton’s theorem” will be in the exam. She then writes a program that looks something like the following:

import hashlib
import random
import string
import base64

# Given a prefix, find strings whose SHA1 hash starts with that prefix
# when decoded into base32.
def find_sha1_with_prefix(prefix, length=8):
  while True:
    candidate = ''.join(random.choices(string.ascii_lowercase + string.digits), k=length)
    sha1 = hashlib.sha1(candidate.encode())
    binary_sha1 = sha1.digest()

    result = base64.b32encode(binary_sha1).decode('ascii').lower()

    if base32_str.startswith(prefix):
      return candidate, result

prefix = "bouton"

while True:
  candidate, result = find_sha1_with_prefix(prefix)
  print(f"Found string {candidate} with hash {result}")

Executing this would print a steady stream of strings:

Found string kbdopglv with hash boutondu35veycpl4ojn5zripb4er3yt
Found string tjf1detx with hash boutonitf73aoiuhj37qbh5adpdz7vm5
Found string 8zw0zbx9 with hash boutonrigw2kesr6hmqjhej77ewzzjjx
Found string wipipfwx with hash boutonffrn4t3x2dioouynofdur7nirx
Found string notyr26v with hash boutonu4jcsdyhnp3llcny5t2xg65jqg
Found string udbalw4e with hash boutonoltw32aua45p36izrbnl3dbio3
...

When it was exam time, Alice could scribble these hashes onto her exam manuscript. Once she returned home, the hashes would act as a form of proof of work: if Alice’s peers ran the program themselves and estimated the rate at which hashes were produced, they could determine to high probability how long Alice had ran the program while on the island. If she’d been running the program since the start of her stay, and the message contained “Bouton’s theorem”, bragging rights for her impressive foresight would then be guaranteed.

But there is a problem with this scheme as it stands: what would stop Bob, who didn’t really have any predictions but determined at all to pretend he did, to generate hashes before he went to his island? Assuming he had lots of time and computational resources before being taken to his island, he could generate hashes for all possible topics and then only after seeing the contents of the exam pick out the few relevant hashes out of the many he had already calculated.

One way Alice can guarantee she did think of her prediction while on the island is to also include something that she could have only known soon before leaving, like the price of the S&P 500 immediately before her departure (were she able to predict this ahead of time, she would be rich enough that the bragging rights wouldn’t matter). If the price was 5,471 before leaving, then she could set the prefix to boutonX5471X:

Found string 7ot48tjx with hash boutonX5471X6sydqfk2rk5t2xzprwox
Found string 3me7tewm with hash boutonX5471Xns3ooosv3ltyvjmj2bmr
Found string svd8j5wd with hash boutonX5471Xbe4gwoonp3w7nkjhtwm6
Found string gx734s3t with hash boutonX5471Xpbnx52bgonalqxgnmqxc
...

(these hashes don’t really work).

It’s also not necessary to do the proof of work using the computer – another similar solution would be to inscribe “Bouton’s theorem - S&P 5,471” onto as many coconuts as Alice could manage in the time between making the prediction and sitting the exam (unfortunately not using much time for revision). Alice’s peers could then go and see how long inscribing text on coconuts takes, and estimate that it would’ve only been feasible to inscribe that many coconuts if she had started doing so from the start of her stay. Although this does have the disadvantage that she wouldn’t be able to revise at the same time.

This seems like a niche idea, but is actually used all the time in the workings of cryptocurrency: Bitcoin itself is built around a proof-of-work scheme called Hashcash, which requires miners to prove their dedication by finding partial hash inversions like this. There’s also an interesting fictional Wikipedia article about the “Basilisk collection”, a mysterious set of partial hash inversions which “represents a proof-of-work far exceeding the computational capacity of the human race”.



Related posts