CaptainEd

Nice job, araver! Nice puzzle, bonanova

Maybe this is clearer and more accurate than my previous try. Point one:

It's been a long time. Here's a recharacterization that recognizes a much smaller search space: Overview Definitions and additional constraint LineSplittingMValues.xlsx BonanovaSequence.xlsx

Gavin, I agree, a permeable chain is necessary. Here’s a simplified (and still incomplete) proposal:

Bonanova, I see your point (forehead slap echo). BMAD fooled us.

Thanks, BMAD, I understand now

I’m the only one who doesn’t know how the game works. Here are a couple of questions that may help me understand. do we all play simultaneously? Or are purchases made sequentially (so that each player is able to meet the requirement of avoiding numbers others have chosen)? Once everyone has played, how is it determined who has won? If more than person chooses a number, is that number removed, and the lowest number chosen by only one person is the determiner?

Kudos to both of you! Nice problem and nice solution!

Buddyboy300 has a much better answer than I did: moving the vertical stroke of the plus sign over to diagonally cross the equal sign.

Assuming the gray square can only touch each red square corner-to-corner or corner-to-edge, my answer is ...

Dang, I blew my spoiler again...I’ll be back. I’ve got an answer...sigh

“Touch” elucidation question: Does the gray square overlap red squares? Or can only edges overlap? Or can they only share single points?

Nice compact proof, Bonanova, thank you!

Part b

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.