Catino

Our cat is cute right!

Files given:

For this problem, we need to guess 100 random numbers correctly in a row and we are only given 5000 tries.

1. You start with $0
2. On each round, Catino choose a single digit secret number (0-9)
3. You try to guess Catino secret's number
4. If the guessed number matches the secret, then you earn $1000
5. If the guessed number does not match the secret, then you lose all of your money!
6. You win when you have $100000!
7. The game ends forcefully when the number of round exceeds 5000

We shall first see how the random numbers are generated

ind = 100
randarr = []

def prep():
    global randarr
    print("\nGenerating random numbers....", flush=True)
    n = Decimal(randbits(2048))
    p = Decimal(1/4)
    k = str(n**p).split('.')[1]
    randarr = list(k)
    print("Generation complete!\n", flush=True)

def nextRand():
    global ind
    assert ind < len(randarr)
    res = int(randarr[ind])
    ind += 1
    return res

We see here that the random numbres is simply the decimal places of \(n^{\frac14}\) for a random \(n\). This code gives us the decimal places starting from the \(100\)th decimal place.

To solve this problem, if we have every decimal place, then the number we get, say it is \(x\), would satisfy the following equation:

\[x=n^{\frac14}-10^{-100}\left\lfloor10^{100}n^{\frac14}\right\rfloor\] \[\left(10^{100}x-\left\lfloor10^{100}n^{\frac14}\right\rfloor\right)^4-10^{400}n=0\]

which tells us that if we have the minimal polynomial of \(10^{100}x\) given by \(\sum_{i=0}^4a_i\left(10^{100}x\right)^i=0\), then we can solve for \(n\) with

\[n=10^{-400}\left(\left(\frac{a_3}4\right)^4-a_0\right)\]

Since we can easily approximate the minimal polynomial via LLL or sage’s .algebraic_dependency(4), given enough decimal digits, we can recover \(a_i\), giving us \(n\) and the solution

Solution at solve.sage

Flag: grey{FunFact_OurGreyCatIsActuallyABlackCat_LFP9eux3884hd2ag}