Seemingly hard problems trivialized by a single simple observation

Revision en3, by WolfBlue, 2021-12-01 19:59:55

Here I've enumerated some of my favorite problems. The solutions appear trivial in retrospect — but the 1 line observation is quite hard to come up with. You have to think really outside of the box for these! I think such problems are quite cool and hard to come by, so please add a comment if you have any other problems of this type that you've seen!

They are arranged from easiest to hardest (in my opinion).

1) For $N<10^6$, what's the Nth palindromic number in base 10 with an even number of digits? (The first is 11, then 22, 33, 44, 55, 66, 77, 88, 99, 1001).

Key observation:

Spoiler

2) A classic: $N < 10^6$ Ants are on a line of length $10^{15}$ at some positions $p_i$. Each has a starting position and direction left or right. They walk at a rate of 1 unit per second, and if 2 collide, both immediately turn around and walk the other way. How long will it be until no ants are on the line?

Key observation:

Spoiler

Source: https://codeforces.com/gym/102966/problem/G and other places

3) $N<10^5$ Rectangles with ODD side lengths are on a $10^9\times 10^9$ grid. The corners of each are at integer lattice points $(x, y)$. Color each of the rectangles one of 4 colors so that no adjacent two rectangles are the same color.

The four-color theorem shows that this is always possible, but provides no further insight for this problem.

Key observation:

Spoiler

4) You've got three $3000\times3000$ matrices $A, B,$ and $C$ containing only the elements 0 and 1. You need to output a boolean: if $AB=C$ with all elements of $AB$ taken mod 2. Note: Your method must work with high probability on ALL possible inputs. Maybe a lot of people want to hack your code.

Solutions that won't work:

Spoiler

Key observation:

Spoiler

Source: A class in complexity theory

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 WolfBlue 2021-12-01 19:59:55 199
en2 WolfBlue 2021-12-01 04:24:06 14 (published)
en1 WolfBlue 2021-12-01 04:23:44 3142 Initial revision (saved to drafts)