“Greg, Marcia, Peter, Jan, Bobby and Cindy go to a movie and sit next to each other in six adjacent seats. If Marcia and Jan will not sit next to each other, in how many different arrangements can the six people sit?” – GMAT Sample Question
Thankfully my standardized test-taking days are far behind me, but this kind of problem is typical of what one might find on an advanced level standardized test math section. It also so happens to be representative of what mathematicians refer to as a constraint problem.
Constraint problems (also commonly known as constraint satisfaction problems or CSPs) refer to a family of mathematical optimization problems. Wikipedia defines constraint satisfaction as follows: “…the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints.”
With that aside, I’d like to continue with a simple illustration that might help put some understanding behind these abstract definitions. For a moment, just imagine that you are the owner of a chocolate factory…
As a chocolate factory, your company is the sole supplier of three types of chocolate to a retailer whom we shall call “Bradburys.” The three types of candy are Darkness™, Heaven™, and Therapy™ (these don’t actually exist as far as I know but can help with your imagination, YMMV). Now as CEO of your chocolate factory, your task is to maximize profit by keeping production costs low and output high. Seems straightforward, right? However with chocolate production, as in life, things are a little bit more complex.
Your factory has three machines – each producing only one type of candy. This limits the overall production for each type of candy to the capacity of the machine that can produce it. You also have a limited budget, and since chocolate doesn’t grow on trees (OK, technically cocoa does, but you know what I mean), you have to make financial decisions about what quantity of the different chocolates you are willing to produce. And just to make it even more complicated, some chocolate candies can be sold more profitably to Bradbury’s than others. Hmm, some tough decisions to make… Read More…