After twenty-five years of thinking about this problem I decided to write a web page about it.  Here is the problem:

Can you find three foods such that all three do not go together (by any reasonable definition of foods "going together") but every pair of them does go together?

There are many ways to interpret this "going together" but an example solution would be three pizza toppings---A, B, and C---such that a pizza with A and B is good, and a pizza with A and C is good, and a pizza with B and C is good, but a pizza with A, B, and C is bad. Or you might find three different spices or other ingredients which do not go together in some recipe yet any pair of them is fine.

Alternatively, you could try for an impossibility proof---to demonstrate logically that whenever all three pairs are OK then the triple must be OK.  But I think that would be difficult to show because there are plenty of chemical processes which require three ingredients for a reaction yet no two react. So, to the extent that cooking is chemistry, it seems that one can not rule out an incompatible triad a priori.

History

I learned of The Incompatible Food Triad problem from the philosopher Nuel Belnap when I was a graduate student in the late 1970's. He mentioned it in discussion while we were at a dinner together. In the intervening years, I have occasionally passed it on it at various dinners to my colleagues and graduate students, always without success. Recently, (at a wonderful dinner in southern Spain with a colleague, two graduate students, and a vast platter of tentacles and mysterious seafood,) I realized it has been twenty-five years with zero progress. It was time to start getting serious about finding a solution! First, a Google search found no references at all. Three billion web pages, and none discuss the question. Then I contacted Prof. Belnap to see if he had found a solution in the intervening years. He tells me that has made no progress either. He also informed me that he learned the problem from the philosopher Wilfrid Sellars over a dinner, and that he suspects Sellars is the originator but can not be sure.

Feeling that better minds (or taste buds) than mine must now be brought to bear in this research, I decided to write this web page in August 2003. It is hard to believe that there are any such pressing questions left about which one can write the first web page on the internet. 

Your Job

If you think you have a solution to The Incompatible Food Triad, first be sure and check that all three pairs are compatible. Always (so far) when people think they have a solution, it turns out that they didn't check one of the pairs, and that the incompatibility of the triad can be found to lie in the incompatibility of one of the three pairs. Then, if you are still confident of your answer, please send me an email, and I will collate the answers and report progress below. (YOU could get famous, right here!!!) Of course solutions may be idiosyncratic, with different eaters having different opinions about taste compatibility, so there may be some discussion to follow.

Also, if you find any other discussion of the problem (in print, on a web page, or wherever) please let me know.

Progress

September 2003: Not a solution, but Craig Westerland (at the University of Michigan) responds to the question with a complementary question: Are there three foods which you would eat together, but you wouldn't eat any pair without the third?

December 2003: "Luka" suggests that the tea + milk + lemon juice triad, famously described by Richard Feynman in his autobiographical Surely You're Joking Mr. Feynman, is a solution. I have discussed this triad many times over the years. Most agree that this is not a solution because lemon+milk is a very bad pair. It forms curdles and that is the source of the problem with the triad, which is the point of the Feynman story. However Luka points out that milk+lemon juice is a step in a recipe for what is called "panir" or "paneer" or "queso blanco" or "farmer's cheese". You then strain it in cheese cloth, and press it until it is firm like tofu. My reaction is that if you like this kind of bland cheese and you like milk in your tea, then you would probably like a tea-flavored cheese. I can't test this because I don't like milk in my tea, but someone who does and who also likes to make panir should let us know if a tea-flavored panir is good or bad.

March 2004: Moses Liskov follows up on this with a suggestion for a cheese that would taste worse:

  If you buy the paneer argument, then I think espresso + milk + lemon juice qualifies as a triad.  Espresso + milk is clearly popular.. and Italians often have espresso with lemon.  However, even if tea-flavored cheese might be pleasant, espresso-flavored cheese is a gross concept: paneer is a light, delicate cheese, and I've never had a cheese with a strong non-cheese flavor that I liked (except for hotness, as in pepperjack).

April 2004: Heidi Shook makes a suggestion but also shoots it down:

...potatoes, mayonnaise, and cabbage. Recipes often contain two out of the three, but not all three ingredients. Potatoes & mayo for a potato salad, cabbage & mayo for a coleslaw, and potatoes & cabbage for a veggie side are common, but mixing all three is rare.

I did find two exceptions on google--corned beef, cabbage and potatoes can be served with a horseradish sauce on the side. I'm not a corned beef eater, but I am guessing the sauce is for the meat. Anyway, the sauce sometimes contains mayonnaise and the recipes aren't specific about which foods get sauce treatment. The other exception is somebody has come up with a corned beef salad that actually contains all three ingredients mixed together. That recipe doesn't seem to be widely known, leaving me to think it must taste as terrible as it sounds to me.

May 2004: Joanne Murray at first suggests the following:

chocolate, chicken and honey

there's honey-butter chicken (yummy)
chicken with mole (chocolate) sauce (mexican)
and all kinds of sweets with chocolate-honey sauce

but chocolate-honey-chicken sounds revolting.  google supports this.  you can find many recipes for "honey chicken" "chocolate honey" and "mole chicken" but nothing whatever for "chocolate honey chicken" "honey chocolate chicken" "honey mole chicken" or "mole honey chicken".

But then she found a counter-example and sent me this:

http://www.kraftfoods.com/recipes/PoultryEntrees/GrilledBroiled/MoleBBQChicken.html

oh well, sorry to bother you with a loser.  (though i still say chocolate-honey-chicken sounds disgusting to me).

May 2004: Vincent Tsoi suggests "Chocolate, Strawberry, Milkshake" but I disagree, having made end enjoyed milk shakes from vanilla, chocolate and strawberry mixed together.

June 2004:  Carolyn Williams apparently feels there is no solution (for her) as she comments "Get pregnant, and you can eat anything!"

September 2004: Gwen Fisher suggests:

a. Salted cucumbers
b. Sugar
c. Yogurt.

a and b in sweet pickles
a and c in tzaziki (sp?), the greek yogurt dish.
b and c is common.

a, b,and c together is pretty gross.  I was trying to make tzaziki once, and
accidentally used sweetened vanilla yogurt.  I had to throw it out.  Yuck.

I can't comment on this, as I draw the line at a+c.

September 2004: Joshua Harwood suggests a solution with mixed drinks:

A = gin

B = tonic water

C = orange guice

A+B goes together.  (Gin & tonic.)

B+C goes together.  (Orange fizzer, prom date punch.)

C+A goes together.  (Gin & juice.)

A+B+C does not go together.  (Wretched surprise!)

I'll have to do an experiment, since I don't see what the surprising problem might be.

October 2004: Melinda Green suggests lemon-cocoa-curry:

lemon-cocoa = chocolate covered candied lemon rinds (yum!),
cocoa-curry = mole,
lemon-curry = thai

Can there not be a lemon mole?

. . .

<It turns out this page started generating far more mail than I could keep up with, so I quickly stopped adding posts.> 

One critical email I received may deserve printing:

Quantitative Algorithmic Approach:

I asked some folks at Google if they could automate the question by selecting a set of food words, enumerating all pairs and triples of them, then searching within recipe pages and tabulating the page counts of  foods, looking for a triple with the correct property.  But it was apparently too much of a challenge even for Google to determine what words are foods and what pages are recipes.

Funniest Answer:

I love the answer by Noah Snyder and his colleagues at U.C. Berkeley, who suggest these three items: a shot of tequila, a shot of tequila, a shot of tequila.

Expert Answer:

In January, 2010, I received this authoratative comment from Hervé This of the AgroParisTech. For more about him, see This's blog. I will present it here as perhaps my final word on the subject:

Dear George Hart, 

May I tell you that your question is wrong, and this is why there is no
solution. 

Indeed, there is a myth called "food pairing", but it is not scientific, as
food appreciation is a question of art... and art always espapes (aesthetics)
laws. 

Moreover, think of Munster Cheese, durian fruits, hot brain of apes in
skulls... If someone had it when young, it's good!

Finally, an anecdote: I asked once to my friend Pierre Gagnaire if he would
be able to mix the impossible pair camembert cheese+raspberries... and he 
did it at once. The recipe is in my book "Cooking, a quintessential art", at
California University Press. Moreover, in this case, you need absolutely a
poor camembert to get a "good" result. A discussion is given also in the 
final chapter of my book "Building a meal" (Columbia University Press)

Best regards
Hervé This

Physico-chimiste
Directeur scientifique de la Fondation Science & Culture Alimentaire
(Académie des sciences)
Membre correspondant de l'Académie d'agriculture de France
Membre associé de l'Académie royale des sciences, des arts et des lettres de
Belgique
Président du Comité Pédagogique des Hautes Etudes du Goût
Conseiller Scientifique de la revue Pour la Science

Groupe de Gastronomie Moléculaire
Laboratoire de Chimie, AgroParisTech