Mrs.Chaos asked me, “I need some help. I have five tables, each with six people. I’m going to have three rounds of games where I want everyone to rotate tables and meet as many unique people as possible.” It’s straight out of my college Putnam prep class.
The thing about problem solving in preparation for the Putnam exam is that while every problem could be proveable solved using mathematics, most problems could ALSO be solved using some sort of brute force algorithm I could write a program for. I was also always confident I could write the program to brute force it, but not always confident I could figure out the mathematics to solve.
So when Mrs.Chaos asked me that question I thought to myself, “I might be able to solve this problem using combinatorics or linear algebra, but I *KNOW* I can write a program that will solve this program."
I cranked on it for an hour, and wrote a great a basic genetic algorithm to solve it. I say, basic, because it randomly generates solutions and then checks the average number of other people everyone gets to sit with. Repeat forever and keep tracking of the best solution.
I gave the best solution to Mrs.Chaos and she started looking and said, “Oh. Sorry. People can’t be at the same table more than once.” Hmm, now it was more like one of those crazy algorithm interviews I’ve done. You solve the problem and then they add an arbitrary constraint onto the problem.
Simple enough, I added the contraint, “no one can sit at the same table more than once” and ran 1,000,000 iterations. No solution. I ran another 1,000,000 iterations. No solution.
I can trivially construct a non-optimal solution in my mind, so I know it’s possible, it’s just, apparently, rare. I made it a weak constraint, “optimize towards people not sitting at the same table.” After running another few million iterations I got a solution where only 2 people repeat tables and everyone sits with an average of 13.5 other people.
Anyway - now is the real question: do I rewrite it to actually solve the problem or just call it a day?
The Putnam Exam. Man that thing was crazy - the hardest major undergrate math exam. There are three problems and the median score is zero out of ten. The scoring:
1 point - you solve the problem
2 points - you get the optimal answer to the problem
3 points - you prove you got the optimal answer to the problem