CaptainEd

First, I define Restricted and Unrestricted coins, then describe and prove the algorithm for Restricted coins. Next, I request a slight tweak to the OP conditions--one additional coin known to be good. Then comes the definition of the procedure for Unconstrained coins, followed by the edge case (how many coins with only one weighing), and the formula for the Unconstrained case, since the OP requests the Unconstrained formula. Then come the first few values.

cant do this compactly with iPhone. I'll answer sooon. (1) yes I'll make better demonstration about Restricted approach. (2) yes, I'll describe complete Unrestricted approach, which gives larger number

sorry, my attempt to remove the post failed.

[spoiler=answer maybe]in N weighings, can distinguish bad coin out of M=Sum(3^i), i=0...N-1 Can't always tell whether heavy or light[/spoiler] [spoiler=Background: restricted vs unrestricted]if you weigh coins in the balance scale, and the Left pan is heavy, then the coins in that pan are "restricted": each one is either Good or Heavy, while the coins in the other pan are restricted as either Good or Light. I abbreviate "heavy or good" as "H", and "light or good" as "L". We can distinguish among 3^N restricted coins in N weighings. [/spoiler] [spoiler=Strategy]However, we are starting with coins we know nothing about (and maybe one coin known to be good) So we will weigh a number of coins (p), leaving some of them (q) unweighed. Once you weigh the first batch, they become restricted, and you can resolve one of them in ceil(log base 3 (p)). If they balanced, then you have N-1 weighings to resolve the remaining q coins. So our initial task when approaching a set of coins is to choose p and q so that the number of weighings for p restricted coins equals number of weighings for q unrestricted coins. [/spoiler]

More thoughts Let's divide the problem into three parts: I think I see how to solve two of them, but the third suffers from the challenge identified by Gavin. [spoiler=Carry Flags]once you find one or more flags, drag them behind the roomba. In detail, move the lead flag forward (whatever direction you aim to be moving), and then work your way back in your chain of flags, moving each one forward. Then go the front of the chain and move forward, checking for a new flag. Keep going until you hit a wall. If you run across a new flag, move it to the back, and put it in a linked list. (Remember that we can pre-establish a fixed amount of memory. Let's allocate, say, 5 memory cells for each of 1000 potential flags. While we can't expect to have cells be large enough to count absolute coordinates, but we can count "local" coordinates, such as distance from one to the next in a chain.) [/spoiler] [spoiler=gather flags on a wall]once you hit a wall, use the standard policy of traversing with your right hand on the wall, and dragging the chain of flags with you. As soon as all of the flags are adjacent to the wall, drop the chain. Now continue around the wall until you hit more flags. When you hit a flag, follow the flags to see if you've run into your dropped chain. If the number of flags is different from the chain you dropped, then these are new flags, so drag them back to the dropped chain and concatenate them. Then continue around the wall. If the new chain of flags is the same length, and has exactly the same shape as your dropped chain, then let's see if it is the same chain: tweak the chain (by moving the tail element backward, leaving a gap from the rest of the chain, for example). Document the chain you are dragging with you with this tweak, then leave it here and traverse backward until you hit a chain of flags. It must be the first one you dropped. Does it have the same tweak that you just made to the "new chain"? If so, they are the same chain, and you have completely circumnavigated the island. If not, they are separate chains, so bring the first one forward to merge with the new one, and continue forward around the boundary. As long as you have two or more flags when you find an island, you'll be able to gather all the flags adjacent to that island, and be sure that you have seen its entire perimeter. [/spoiler] [Spoiler=Pledge won't work]You can't distinguish the outer boundary from large internal islands. The Pledge algorithm won't work, because the maze can be so large that an internal island can have a spiral so much longer than the side of the maze, that our rotation counter will overflow clockwise before it starts restoring counterclockwise. Still, we can treat the outer boundary exactly like a large internal island. So we can (a) wander around in open space, gathering a chain of flags, (b) attach a chain of flags to an island, and unambiguously gather all flags adjacent to that island. [/spoiler] [spoiler=remaining challenge] Our only challenge remaining is the first one Gavin pointed out: how can we ensure we will wander over the entire reachable space? I dunno. Maybe we have to emulate growing plants: make little directional experiments when wandering open space. Can't specify or prove [/spoiler].

Gavin, I don't see any rules saying where you can put the randomly generated bit. do we imagine that it can be placed into our finite memory? I like your suggestion that the random bit might contribute to a Roomba-like exploration :-) of course I don't see how yet.

I'm missing something.

I think that after we check 4, we know that fox is in an odd number right now, and will move to an even one that night.

Don't watch the video!!! it is a good video, it clearly states the problem, but then it gives the answer! (Clearly stated as well) if you watch the video, stop after the problem statement. I enjoy the problem, and I appreciated the ingenious solution, nice job!

My analysis was incomplete. If you skip the Center X, then a string of alternating C and F (with E between) is constrained by the number of E. With 12 E, at most 13 (C,F) can be interleaved with them. And, because there are only 6 F, that means the upper limit on a path would use 7 Cs and 6Fs. So as Rocdocmac says, if it's possible without touching X, it must start and end with C: CEFECEFECEFECEFECEFECEFEC. Either way, with or without the X cell, 25 appears to be the upper bound, and Thalia found one.

(Sorry I don't know how to make spoiler on iPhone, but it seems Thalia is the winner, so I'm not surprising anyone) Here's why 25 is max: Lets label a corner C, Edge Center E, Face Center F, and the hidden Center X. There are 12 E, 8C, 6F, and 1X. Because of the required 90 degree turn at each cell, CE can only be followed by EF (or Exit). All possible moves are: CE : EF FE : EC or EF EC: CE EF : FE or FX FX : XF FE : EC Notice only F can reach X, so the Sequence of moves must include FXF, if the Center is to be reached at all. Also notice that once you have moved from C to E, you can only move from E to F. For each C, you can pass through one F. (In CEFE sequence). But while there are 8 C, there are only 6 F, so the total sequence can have only 6 C, and the maximum is only 25. Good news is, there are enough E to join all the C and F, so the sequence could look like ECEF ECEF ECEF X FECE FECE FECE A path that avoids X would have to have an E between two Fs, which would waste an E, leaving only 24.

I hope this is clear: Oops! Plasmid beat me to it on the 8:13 version of this puzzle.

Bonanova, cute puzzle! Pickett, great solve! Thank you both, that was fun to watch!

Can't do spoilers on my phone.