Self-ref #math
Expected solvable difficulty
-
3samples+: experienced solvers -
keywords+: most solvers
Level design
Tupper’s self-referential formula is a formula that visually represents itself when graphed at a specific location in the (x, y) plane.
Tupper’s self-referential formula, Wikipedia
\frac{1}{2} < \left\lfloor \mathrm{mod}\left(\left\lfloor \frac{y}{17} \right\rfloor 2^{-17 \lfloor x \rfloor - \mathrm{mod}\left(\lfloor y\rfloor, 17\right)},2\right)\right\rfloorThis level was again inspired by a video by Numberphile a few years ago. I used to design this level as simple as possible, just throw in the image, and use the lower Y axis number as the answer. However, unfortunately, 739…944 is just too long for file names for compatibility purpose. (I literally cannot push the folder with such a long file name to GitHub.) When come to shorten an integer for checking answers, the first solution came to me was 1 000 000 007, the first 10-digit prime number, commonly used in programming competitions. I finally managed to squeeze in the number in the third sample question.
Surprisingly, the first winning team reached this question before 3samples was unlocked, way before what I was expecting when ordering the questions. Hence was confused for how such a small number was reached from the long chain of digits. I could have done better by putting the %10^9+7 hint in the actual question to make it easier.
Expected thought process
Looking at the hints,
- Find the video on the Tupper’s self-referential formula from YouTube,
- Look for the formula in the second sample, or
- Lookup for the repository on GitHub by KellyHill that starts with T,
…to know that the question is asking about the Tupper’s self-referential formula. Then convert the graph accordingly into numbers, and then apply \mod (10^9+7) to the answer.
Leave a Reply