Ponder This Challenge - March 2013 - Buying 5 products

Ponder This Challenge:

There are five products in a store; let's call them A, B, C, D, and E.

The prices of those products are all integers between one and five cents each.

Let's assume that your account is fined with half a point every time your purchase is not an integer multiple of five cents.

The price of A is one cent, but you don't know anything about the prices of B-E, nor are you aware of the amount you pay or the fines you accumulate along the way. The only information you get, at the end of the month, is whether the cumulative number of points you were fined is an integer or not.

For example, after buying the following six purchases: AB AC AABC AAABCC AAABBC BBBBC you can know whether B and C are both 4 or not.

Can you devise a set of purchases, one for each day, such that at the end of the month you'd be able to know whether or not the prices of B-E have exactly two different values?

Please submit your answer as at most 31 lines (one per day) where each line contains a list of items you buy on that day.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Using methods similar to the example given in the challenge, one can implement any function from {1,2,...,p}^d to {0,1} using unlimited fan-in mod-p gates connected to a single mod-2 (xor) gate. Using the general method described above, we get a 28-day solution. But, as many of you realized, one can solve it in one week: BCDDDDEEEE BCCCCDEEEE BCCCCDDDDE BCDEE BCDDE BCCDE BBCDE

  A nice way to prove the correctness of this solution was sent to us by Luke Pebody: Expressing these in modular arithmetic terms, you get fined for each B + C = D + E (mod 5) B + D = C + E (mod 5) C + D = B + E (mod 5) B + C + D = 3E (mod 5) B + C + E = 3D (mod 5) B + D + E = 3C (mod 5) C + D + E = 3B (mod 5)

  Obviously, the number of fines is constant when rearranging B, C, D, and E, and performing any invertible linear transformation on B, C, D, E. So all you need to check to prove correctness is one candidate from each equivalence class: 0, 0, 0, 0 (0 fines) 0, 0, 0, 1 (7 fines) 0, 0, 1, 1 (5 fines) 0, 0, 1, 2 (6 fines) 0, 0, 1, 4 (4 fines) 0, 1, 2, 3 (6 fines)

  Note that 0=5 (mod 5).

Solvers

• Florian Fischer (03/01/2013 04:02 PM EDT)
• Jaeseung Ha (03/02/2013 10:03 AM EDT)
• Marla Slusky (03/02/2013 03:04 PM EDT)
• János Kramár (03/02/2013 05:00 PM EDT)
• Todd Will (03/06/2013 05:14 PM EDT)
• Alex Wagner (03/06/2013 05:19 PM EDT)
• Harald Bögeholz (03/06/2013 05:51 PM EDT)
• Jan Fricke (03/07/2013 10:55 AM EDT)
• Luke Pebody (03/07/2013 11:35 AM EDT)
• Lorenz Reichel (03/07/2013 05:33 PM EDT)
• Liubing Yu (03/07/2013 06:08 PM EDT)
• Peter Holdsworth (03/09/2013 11:50 AM EDT)
• Ariel Landau (03/10/2013 06:09 AM EDT)
• Javier Rodriguez (03/14/2013 01:37 PM EDT)
• Tom Sirgedas (03/15/2013 04:44 PM EDT)
• Adrian Orzepowski (03/16/2013 10:05 AM EDT)
• Lorenzo Gianferrari Pini & Radu-Alexandru Todor (03/16/2013 10:43 AM EDT)
• Mark Pervovskiy (03/16/2013 04:04 PM EDT)
• Armin Krauss (03/19/2013 08:31 AM EDT)
• Wu Hao (03/23/2013 11:30 AM EDT)
• Shirish Chinchalkar (03/23/2013 02:38 PM EDT)
• Olivier Mercier (03/25/2013 06:03 PM EDT)
• Luis Ramada Pereira (03/30/2013 06:47 PM EDT)
• Sergey Grishaev (03/31/2013 03:51 PM EDT)