Gordon, a puzzle veteran of more than 50 years, knew there was no sense going forward without the approval of Shortz, arguably the best-known puzzle editor in the country.
"I wrote him and said I was having a love affair with a 16-year-old boy," Gordon said. "He wrote and said it was sensational, go right ahead."
And go they did. The two did their work entirely online - the closest they got to seeing each other was an exchange of photographs - and quickly began to explore their multigenerational gap. Or, as Steinberg put it, they found that "we think very differently."
Gordon first sent Steinberg a puzzle referencing a "handsome Harry" - and he answered asking what it was. The puzzle Steinberg sent back had just as many generational pitfalls.
"It had the word Uggs in it," Gordon said. "U-G-G-S. I said, 'What in the world are Uggs?' "
When they finally landed on a crossword puzzle they were satisfied with, they sent it to Shortz. He set it to run the next week. According to Gordon, Shortz said the puzzle was "phenomenal."
Shortz, who had nothing to do with the collaboration before it arrived in his mailbox, said one can generally tell the approximate age of a puzzle-maker from the cultural references. However, the Internet has changed this dynamic: The best puzzle-makers are good enough to look up references spanning several generations and sprinkle them in.
Collaborations, too, have become considerably more common thanks to the Internet than when Shortz began his tenure. Now he publishes a few of them per month.
"It used to be a solitary activity," he said. "It was unusual for a puzzle-maker to know another puzzle-maker."
These days, there are websites, forums, and blogs for crossword enthusiasts - some devoted solely to the Times crossword.
Still, Gordon and Steinberg only know each other in the virtual sense. They plan to meet in the coming months when Steinberg, a rising high school junior, travels to the East Coast to tour colleges and makes a stop in Philadelphia.
Although they grew up in different eras, both have pioneered the art of the crossword. Gordon was the first to submit a puzzle back in the 1950s that substituted symbols for parts of words. Her first substituted an ampersand for "and" sounds - ampersand itself, for instance, would have been ampers&. Now, in her home at Atria Senior Living in Center City, she's working on one that substitutes a symbol for "art" sounds.
Steinberg had his first puzzle accepted at the age of 14. He's now heading up the Pre-Shortzian Puzzle Project to digitize old puzzles and is the editor of the Orange County Register's puzzles.
Steinberg hopes to follow in Gordon's footsteps and keep constructing crossword puzzles for the rest of his life.
"I'm not sure if I could make a career out of it," he said, "but it would be really cool."
Contact Sarah Smith at 215-854-2771, firstname.lastname@example.org, or on Twitter @sarahesmith23.