Tag Archives: Puzzles

The blue-haired wine math puzzle

A king is going to throw a party and has set aside 240 cases of wine. The king’s spies have just discovered that, unfortunately, an anarchist has snuck a substance into one of the cases that will completely and forever turn your hair blue overnight, even if you drink only a drop.

Five loyal dukes have volunteered to try the wine first, and there are only two nights to test as many cases of wine as possible. How many cases can you guarantee are safe? Note that once a duke’s hair has been turned blue, consuming more of the wine has no effect, so he is then useless for further testing.

Give up? The solution is here.

A puzzle, I wonder

One time a friend needed to come up with a password for something we were working on and I suggested the technique of using the first letters of a phrase that you know, so for example you might pick “That’s one small step for a man” which would give you the password “tossfam.”

So my friend thought about it for a moment and suggested “iatvmoammg.”

I’ll let that sit with you for a minute…

Continue reading

No, really: stop me if you’ve heard this one before

Silicon Alley Insider is running an article titled 15 Google Interview Questions That Will Make You Feel Stupid. Several of the questions are interesting, but several are chestnuts that if you know puzzles, you barely remember where you heard them the first time. On the other hand, if you aren’t a puzzle person you’re not likely to solve them quickly and under pressure during a job interview, making them less than useless. It doesn’t help that the article doesn’t display a good understanding of the puzzles, and gets several answers wrong.

Here they are:

Stupid Interview Questions

Continue reading

Stop me if you’ve heard this one before…

New Scientist is running an article about intelligence where they claim that a high IQ doesn’t mean you’re smart. I agree in general, but one example they give is just silly. They cite:

Test your thinking

When researchers put the following three problems to 3400 students in the US, only 17 per cent got all three right. Can you do any better?

1) A bat and a ball cost $1.10 in total. The bat costs $1 more than the ball. How much does the ball cost?

2) If it takes five machines 5 minutes to make five widgets, how long would it take 100 machines to make 100 widgets?

3) In a lake, there is a patch of lily pads. Every day, the patch doubles in size. If it takes 48 days for the patch to cover the entire lake, how long would it take for the patch to cover half of it?

I can believe that only a small percentage of students got all three right, but I wonder what the researchers thought they proved. The above three questions are the puzzle equivalent of knock-knock jokes: if you are at all interested in word puzzles, you learned these somewhere around the fifth grade.

This reminds me of a job interview I once had, where the interviewer decided to ask me an interview puzzle. I think he started with the doorway choice: you have two doors to choose from, one leading to certain death, and two robots (or brothers, or villagers…) to help you, one of which always tells the truth, one of which always lies. What one question can you ask to make the decision. I told him I already knew the puzzle. So he asked me another, about timing 45 minutes with two ropes that will each burn in an hour. I knew that one as well. So he asked me another. And another. And another. He wouldn’t give up, but he apparently didn’t know any puzzles that I didn’t know. Eventually I asked him if it was alright for me to bring up a puzzle I had recently been working on and describe how I had solved it. He agreed and we moved on. (I got the job)

The problem in both cases is that to anyone who has an interest, the problems aren’t problems at all, and they do nothing to test the individual’s actual ability, but only their level of interest in the field of puzzles and ability to recall old chestnuts; while to anyone who has no interest, obviously they will underperform because they have no interest. If the researchers thought they were testing for intelligence by asking those three tired puzzles, they were sorely mistaken. They were really testing for a general interest in puzzles.

But perhaps an interest in puzzles correlates with intelligence. I’d certainly like to think so ūüėČ

I’m curious how many people reading this were familiar with the above three puzzles.

A solution to Einav’s programming puzzle

Here’s a solution to the array problem my friend¬†Einav posed. If you haven’t looked at the puzzle, check it out first. A summary: you have a 9×27 array of positive and negative¬†numbers. You can flip the sign of an entire row or column (as many of them¬†as you like). The goal is to make all the rows and columns sum to positive¬†numbers (or zero), and then to find the solution (there are more than one)¬†that has the lowest overall sum.

Here’s the code that finds the solution, in the J programming language:

list=:_9]\33 30 10 _6 18 _7 _11 23 _6 16 _19 9 _26 _8 _19 _8 _21 _14 17 12 _14 31 _30 13 _13 19 16 _6 _11 1 17 _12 _4 _7 14 _21 18 _31 34 _22 17 _19 20 24 6 33 _18 17 _15 31 _5 3 27 _3 _18 _20 _18 31 6 4 _2 _12 24 27 14 4 _29 _3 5 _29 8 _12 _15 _7 _23 23 _9 _8 6 8 _12 33 _23 _19 _4 _8 _7 11 _12 31 _20 19 _15 _30 11 32 7 14 _5 _23 18 _32 _2 _31 _7 8 24 16 32 _4 _10 _14 _6 _1 0 23 23 25 0 _23 22 12 28 _27 15 4 _30 _13 _16 _3 _3 _32 _3 27 _31 22 1 26 4 _2 _13 26 17 14 _9 _18 3 _20 _27 _32 _11 27 13 _17 33 _7 19 _32 13 _31 _2 _24 _31 27 _31 _29 15 2 29 _15 33 _18 _23 15 28 0 30 _4 12 _32 _3 34 27 _25 _18 26 1 34 26 _21 _31 _10 _13 _30 _17 _12 _26 31 23 _31 _19 21 _17 _10 2 _23 23 _3 6 0 _3 _32 0 _10 _25 14 _19 9 14 _27 20 15 _5 _27 18 11 _6 24 7 _17 26 20 _31 _25 _25 4 _16 30 33 23 _4 _4 23
sumOfRows =: ([: +/"1 [: |: ] * [: |: _1 + 2 * [: #: [: i. 2 ^ #)"1 list
rowSigns =: (;/@:,/@:>)"2 {|:(_1;_1 1;1) {~ (_1&<+0&<) sumOfRows
candidates =:,/((_4]\4#"3 (_1 + 2 * #:i.2^9) (* &. |:)" 1 _ list)  * (>rowSigns))
theAnswers =: (] #~ [: (0&<@:+/@:(0&<) * */@:(_1&<)) [: |: +/"2) candidates
theSums =: +/"1 +/"1 theAnswers
theBestAnswer =: ~. ((theSums = ] theBestSum =: <./ theSums) # theAnswers)

 

The basic method is:

1. sumOfRows: Find the sums of all the rows for each permutation of flipping the columns (9 columns = 512 flipping permutations.

2. rowSigns: Find how the rows will have to be flipped in order to make them all positive for each of the column permutations. Note that if any of the rows sum to zero, then they have to be accounted for both ways. The most number of zeroes in any row is two, so that means that some of the column permutations have four possible row solutions.

3. candidates: Find the actual resulting arrays for each column permutation/row solutions. There are 624.

4. theAnswers: Find all the candidates where all the columns are positive after the row solution has been applied. There are 368.

5. theSums: Find the sums of all the answers.

6. theBestAnswer/theBestSum: Find the smallest sum and the corresponding answer. This is kind of cheating on the line count since I did a double assignment, but that’s perfectly acceptable in J. I just don’t particularly like the way I did it. The double reference to theSums is annoying. Line 5 is annoying in general. If I figured out how to do just a single reference to theSums in this line, I would sub in line 5 and get rid of it.

Interesting to note: I had originally thought to look for the solution by first manipulating the signs of the numbers individually to find the smallest possible positive sums, and then work up through them to see which were possible. I didn’t figure out a way to do that, so I fell back on this (relatively) brute force method.¬†Obviously, my first plan would have worked best if the correct answer was fairly low in the sequence; if I ended up trying many potential solutions that didn’t work, it could take as long as the brute force method I ended up with.¬†The interesting thing is that for this particular array, the smallest possible result was in fact possible. I tried another random array to see if (for some unforeseen reason) that is always the case, and it isn’t.

A programming puzzle from Einav

Updated: Never post late at night. The below array is the correct source.

My friend Einav gave me this programming puzzle to work on. Given this array of positive and negative numbers:

33 30 10 -6 18 -7 -11 23 -6 16 -19 9 -26 -8 -19 -8 -21 -14 17 12 -14 31 -30 13 -13 19 16 -6 -11 1 17 -12 -4 -7 14 -21 18 -31 34 -22 17 -19 20 24 6 33 -18 17 -15 31 -5 3 27 -3 -18 -20 -18 31 6 4 -2 -12 24 27 14 4 -29 -3 5 -29 8 -12 -15 -7 -23 23 -9 -8 6 8 -12 33 -23 -19 -4 -8 -7 11 -12 31 -20 19 -15 -30 11 32 7 14 -5 -23 18 -32 -2 -31 -7 8 24 16 32 -4 -10 -14 -6 -1 0 23 23 25 0 -23 22 12 28 -27 15 4 -30 -13 -16 -3 -3 -32 -3 27 -31 22 1 26 4 -2 -13 26 17 14 -9 -18 3 -20 -27 -32 -11 27 13 -17 33 -7 19 -32 13 -31 -2 -24 -31 27 -31 -29 15 2 29 -15 33 -18 -23 15 28 0 30 -4 12 -32 -3 34 27 -25 -18 26 1 34 26 -21 -31 -10 -13 -30 -17 -12 -26 31 23 -31 -19 21 -17 -10 2 -23 23 -3 6 0 -3 -32 0 -10 -25 14 -19 9 14 -27 20 15 -5 -27 18 11 -6 24 7 -17 26 20 -31 -25 -25 4 -16 30 33 23 -4 -4 23
You can flip the sign of entire rows and columns, as many of them
as you like. The goal is to make all the rows and columns sum to positive
numbers (or zero), and then to find the solution (there are more than one)
that has the smallest overall sum. So for example, for this array:
33  30 -10
-16  19   9
-17 -12 -14
You could flip the sign for the bottom row to get this array:
33  30 -10
-16  19   9
17  12  14
Now all the rows and columns have positive sums, and the overall total is 108.
But you could instead flip the second and third columns, and the second row, to get this array:
33  -30  10
16   19    9
-17   12   14
All the rows and columns still total positive, and the overall sum is just 66. So this solution is better (I don’t know if it’s the best)
A pure brute force solution would have to try over 30 billion solutions. I wrote code to solve this in J. I’ll post that separately.