Technology

Popular myth but untrue.

The ROM is exactly 40 kiB or 40 960 bytes. The NES outputs video at a resolution of 256×240=61 440 pixels. The game never switches palettes mid-frame and thus the highest possible number of colors (of the 64 available ones, of which 55 are distinct) in any screenshot is: 4 sprite palettes × 3 non-transparent colors per palette = 12 colors among all sprites; plus 4 background palettes × 3 selectable colors per palette + 1 selectable color shared between all palettes = 13 colors in the background; or 25 colors in total.

Even one of the most basic lossless image formats, GIF, can use an n-bit palette of 2ⁿ−1 arbitrary colors plus transparent, where 1≤n≤8. For n=5, we can store up to 31 colors at 5 bits per pixel, or 307 200 bits total, which is 38 400 bytes. The palette entries, size etc. will take about 200 bytes at most, and LZW compression built into the format (or even better, whatever PNG uses) can be used to reduce the file size further (significanly because there are huge areas filled with solid color or patterns).

I'd bet it's possible to make an NES ROM that does nothing but fill the screen with noise-like tiles and switches the colors mid-frame, likely in just 8 kiB of video ROM plus 2 kiB of program ROM, whose screenshots will never compress to below 10 kiB in PNG format, though.