Order or Not

Solution time?? Solution time. Puzzle last time was the one about magical balloons. The solution is far from unique, but here is the one I found:

Step 1: Name the balloons 1,2,3,4, measure 1 and 2 in the machine. If the machine tells you that either zero or two of them are magical, you can just test the other two balloons one at a time using your remaining two measurements. So proceed assuming we got a result of one.

Step 2: Test 2 and 3 in the machine. If the result is zero, you know 1 is magical and you can test 4 alone. If the result is two, you know 1 isn't magical and agian you can test 4 alone. If the result is one, then either 1 and 3 are both magical and 2 is not, or 2 is and 1 and 3 are not.

Step 3: Test 1, 3, 4 together in the machine. The result being odd will point at 4 being magical, while being even will indicate 4 is not magical. The result being two or three will mean 1 and 3 are magical and 2 is not, while the result being zero or one will mean 1 and 3 are not magical and 2 is.

One flaw that I didn't like about this strategy is that it isn't memoryless, the tests I intend to do each step depends on the results of previous steps, and you can come up with memoryless strategies. However, if you look at the last path of my strategy: Test 1&2, then 2&3, then 1&3&4, that will work to be a memoryless strategy, you just have to analyise your results when you are done. I do not know of any strategy that is totally memoryless, that is, one that there is no path through it that you couldn't have just used from the start as a memoryless strategy.

Other things I don't know about this puzzle: how the heck to generalize it to N balloons and K measurements, so thats a thing to work on.

Magical Balloons

Alright, time to make a post so that I have at least managed to keep up 1 a year. I have a new puzzle Ben gave me ages ago, but I still haven't solved it and would feel wrong posting it when I have no ready solution. In the meantime, here is a puzzle I got from Tanya Khovanova's Math Blog:

You have 4 balloons (blue, red, green, and yellow, if you like) and some of them might be magical. You have a machine that you may put any number of balloons in and it will tell you how many balloons inside are magical. Find all the magical balloons using the machine not more than 3 times.

If you like you can also generalise, replace 4 with N and 3 with K, for which K can you solve the N balloon problem?