Tim
Level: Smitemaster

Rank Points: 1979
Registered: 08-07-2004
IP: Logged

7 was my solution as well. Once you've figured out that 7 CCW = 1 CW, the problem should become easy.

Although I must admit I was expecting more answers with a larger number. (And me telling them they should try harder )

____________________________
The best way to lose customers is to let little kids running loose on a forum with too many mod points.

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

Well, if the arrow only moves clockwise you're always going to run into the problem of all your tokens ending up set to the clockwise position, so I don't see how any solution is possible at all unless you spot the "seven turns the other way" idea.

Here's a really simple proof. If you turn one token CW and another CCW this has no overall effect on the arrow. By induction, given n tokens, k of which are CW, moving to any other position with k tokens CW has no effect. Therefore the maximum number of states is (n + 1), corresponding to the possible values of k from 0 to n. Therefore to get eight states you need seven tokens.

Anyway, TFMurphy is up next....

____________________________
50th Skywatcher

---

[Last edited by Nuntar at 11-23-2008 01:52 AM]

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

Huhm. Fine, let's try this.

Nurikabe is a logic game played on a grid of black and white squares. The goal is to identify which squares are black and white based on the numbers already existing on the grid. Each number is part of a connected area of white cells that is not orthogonally connected to any other connected area of white, where the number of the area is the number of white cells in that area. Furthermore, no area of white exists that does not have a number identifying it.

The black cells in the grid must all be orthogonally connected to each other: you must be able to get from one black cell to any other in the grid using only orthogonal moves. On top of that, no 2x2 block of black cells may exist.

You can find tutorials on this puzzle type off the Wikipedia page. But I'm not going to ask to solve a specific Nurikabe puzzle. Instead, given the basic rules for Nurikabe, determine the following for a 5x5 grid with any particular set of clues, assuming that there is at least one black cell in the grid and that a unique solution can be found via the placement of your clues:

1) What is the minimum number of black cells that can exist?
2) What is the maximum number of black cells that can exist?
3) What is the minimum number of connected white areas that can exist?
4) What is the maximum number of connected white areas that can exist?

Give reasoning and an example starting position that leads to the solution of a particular sub-problem for each.

---

[Last edited by TFMurphy at 11-23-2008 09:12 PM]

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

(1), (3)

- - - - 1
- - - - -
- - - - -
- - - - -
21- - - -

gives the minimum number of black cells (three) and the minimum number of connected white areas (two). Proof -- any grid with only one white area would only have one number clue, and the black squares could be placed by starting in any square other than the clue square and moving to adjacent squares, so there would not be a unique solution. And if there were fewer than three black cells, they could not separate the grid into two disjoint white areas without breaking the rule that the black squares must be orthogonally connected.

(2)

- - - - -
- 1 - 1 -
- - - - -
- 1 - 1 -
- - - - -

gives the maximum number of black squares (21). Proof -- look at the 16 corners between the squares. No corner may be surrounded by four black squares. But the four outermost corners have no adjacent square in common, so at least four white squares are needed.

(4)

1 - 1 - 1
- - - - -
1 - 1 - 1
- - - - -
1 - 1 - 1

gives the maximum number of connected white areas (nine). Proof -- if the black squares did not have to be connected, the maximum would obviously be thirteen, produced by a checkerboard colouring. That leaves twelve black squares to be connected by turning some white areas to black. The second in the top row, last in the second row, first in the fourth row and fourth in the bottom row have no neighbours in common, so at least four are needed.

____________________________
50th Skywatcher

---

[Last edited by Nuntar at 11-23-2008 09:38 PM]

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

I don't think your proof for (3) covers everything satisfactorily (particularly when the single clue is a small number), but the end result matches anyways.

You're up.

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

OK, here's one I posted on the board a while ago but there were no takers.

Design a DROD room (or describe the set-up; I don't require an actual hold attachment) to meet the following requirements.

It must contain exactly two orbs and a number of doors.

The object is to decide on the assignation of orbs to doors so that the player, in playing the room, is able to create a maximum number of different room states.

In case any of that was unclear, here is the solution for the corresponding problem with one orb:

The maximum number of different room states is three. Have two doors, have the orb toggle door 1 and open door 2, and have both doors start closed. The player can reach the states (1 closed, 2 closed), (1 open, 2 open) and (1 closed, 2 open).

Now solve it for two orbs. (If you can find a general formula for n orbs I'd be very impressed, but the two-orb case is tricky enough for justify making that the only requirement for now.)

____________________________
50th Skywatcher

---

[Last edited by Nuntar at 11-24-2008 01:07 AM]

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

I don't think your proof for (3) covers everything satisfactorily (particularly when the single clue is a small number), but the end result matches anyways.

Wouldn't it be possible to have the whole board be one big, connected white area (ie put a 25 anywhere on the board)? There's nothing in the rules that says that there must be at least 1 black square.

____________________________
Progress Quest Progress

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

Yes there is: "assuming that there is at least one black cell in the grid".

____________________________
50th Skywatcher

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

I think I've got Nuntar's orb puzzle. I tried to have a bunch of orbs and then use doors to figure out which orbs were struck in which order.



____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

---

[Last edited by lopsidation at 11-26-2008 11:44 PM]

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

The number of possible states using that method turns out to be really hard, so in lieu of that here's the result for two orbs.


____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

---

[Last edited by lopsidation at 11-26-2008 11:44 PM]

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

Alright, I can't figure out a closed-form expression for n orbs but I figured out a way to find the answer for any n. Sorry for the triple post by the way.

The weird thing is how huge these numbers are. I mean, shouldn't orb puzzles with just 3 orbs be easy to solve? Now it turns out you might need 9 hits!
Anyways, that was an awesome puzzle Nuntar! It was hard!

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

---

[Last edited by lopsidation at 11-27-2008 12:45 AM : Permutation, not combination]

TFMurphy
Level: Smitemaster
Rank Points: 3118
Registered: 06-11-2007
IP: Logged

A little too huge. You're overshooting by a fair amount.

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

Twenty-nine is, however, not correct.

Using your method, we have seven doors, A through G, with the following configuration:
Orb 1 toggles A, opens B, opens E, closes F, toggles G
Orb 2 toggles C, opens D, closes E, toggles F, closes G

Doors A-D ensure that the sequences 0, 1, 11, 2, 22 give unique states and that all sequences with both orbs struck at least once give states different from these five.

Assuming both orbs are struck at least once, we can know which orb was struck last (from E), the parity of the total number of strikes of each orb (from A and C) and the parity of the number of times the last-struck orb was struck after the last striking of the other orb (from whichever of F and G was not closed by the last change to E). This gives four two-way choices, for 16 possible states. Five and sixteen are twenty-one.

I'll give you the credit anyway because your general solution is even more impressive than anything I asked you to find, but I won't mod up all of your triple posts

Your turn.

[EDIT: TFMurphy posted while I was typing this. I think the fairest is to mod up both of you, but lopsidation still gets to go next for doing most of the work, and his solution only requires a small modification.]

____________________________
50th Skywatcher

---

[Last edited by Nuntar at 11-27-2008 01:11 AM]

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

Oops. Well, how about if I change
[Some subset of {P(a), P(b), ... P(n)}, in order], [P(z)], [a possibility of n-1 orbs]
to
[Some subset of {a, b, ... n}, in order], [P(z)], [a possibility of n-1 orbs]
That should work I suppose? For two,
0 - 1
P(x) - 2*2 = 4
P(x) P(y) - 2*4 = 8
x P(y) P(x) - 2*4 = 8
1 + 4 + 8 + 8 = 21, which is what Nuntar got

For three,
0 - 1
P(x) - 2*3 = 6
P(x) P(y) - 4*6 = 24
x P(y) P(x) - 4*6 = 24
x y P(z) - 2*6 = 12
x y P(z) P(x) - 4*6 = 24
x y P(z) P(x) P(y) - 8*6 = 48
x y P(z) x P(y) P(x) - 8*6 = 48
1 + 6 + 24*3 + 12 + 48*2 = 187

You're right, I was off by quite a bit.
Assuming these are right, I'll have a puzzle by Thursday or so.

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

21 is right, so it's your turn.

The correct answer for three orbs is 439, but I didn't ask for that Have fun proving it!

____________________________
50th Skywatcher

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

Oh, I forgot that x, y, xy, or nothing could come before the P(z)'s. With that in mind, how about I change it to
[P(a), P(b), ... P(n)], [P(z)], [a possibility of n-1 orbs]?
It should work now:
0 - 1
P(x) - 2*3 = 6
P(x) P(y) P(x) - 8*6 = 48 <-- for both P(y) P(x) and x P(y) P(x)
P(x) P(y) P(z) - 8*6 = 48
P(x) P(y) P(z) P(x) - 16*6 = 96
P(x) P(y) P(z) P(x) P(y) P(x) - 64*6 = 384
1 + 6 + 48 + 48 + 96 + 384 = 583
Dang, it still doesn't work. Oh well, if someone gets the 3-orb problem before I post a new puzzle on Thursday, I suppose they can have the next turn.

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

Okay, I've got one.
There are two prisoners in a jail with a system of computers. (The warden decided to upgrade from his old system of hats and lightbulbs.) The warden tells them that he will put each of them in separate rooms. One of them, let's say Alice, will go into a room with a computer that can send numbers to the person in the other room, Bob. The warden will tell Alice a number, 1, 2, or 3, that Alice has to communicate to Bob. Alice can send the number 1, 2, or 3 on her computer as many times as she wants, but every time she wants to send a number the warden can block off one of her choices. If Bob can figure out the right number eventually, they both go free, but if he's wrong, they both die.

Alice and Bob can come up with a plan the night before of course, but the warden will listen in and block off numbers accordingly. Give a method for Bob to find the right number or prove it's impossible. Let's assume the warden forces Alice to send a number exactly every minute so time doesn't affect the puzzle.

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

In the meantime, here's my reasoning for three orbs:



____________________________
50th Skywatcher

---

[Last edited by Nuntar at 11-27-2008 03:25 PM]

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

I get it except for

(c) everything we could find out in the two-orb case for the other two orbs for the period after the last striking of that orb -- sixteen choices.

Why isn't it 21 choices? Is there something in this new two-orb case that overlaps with what you already know?

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

Nuntar
Level: Smitemaster

Rank Points: 4968
Registered: 02-20-2007
IP: Logged

Because we're considering the period after the last striking of the orb that had its last striking first, both the other two orbs must be struck at least once, which eliminates five cases from the previous two-orb solution.

I've been working on your puzzle and it intrigues me, but sadly I'm visiting my sister this weekend so I shall probably come back to see someone else has already solved it. From the thinking I've done so far, I would guess it's impossible, except that I know with puzzles of this type it's nearly always possible and incredibly difficult to find a way....

____________________________
50th Skywatcher

---

[Last edited by Nuntar at 11-28-2008 02:25 AM]

Sillyman
Level: Smiter

Rank Points: 339
Registered: 09-08-2006
IP: Logged

lopsidation wrote:
Okay, I've got one.
There are two prisoners in a jail with a system of computers. (The warden decided to upgrade from his old system of hats and lightbulbs.) The warden tells them that he will put each of them in separate rooms. One of them, let's say Alice, will go into a room with a computer that can send numbers to the person in the other room, Bob. The warden will tell Alice a number, 1, 2, or 3, that Alice has to communicate to Bob. Alice can send the number 1, 2, or 3 on her computer as many times as she wants, but every time she wants to send a number the warden can block off one of her choices. If Bob can figure out the right number eventually, they both go free, but if he's wrong, they both die.

Alice and Bob can come up with a plan the night before of course, but the warden will listen in and block off numbers accordingly. Give a method for Bob to find the right number or prove it's impossible. Let's assume the warden forces Alice to send a number exactly every minute so time doesn't affect the puzzle.

I've got it, assuming the warden will release them/die/insert event that will cause them to go free regardless of the puzzle before they die of starvation or thirst (and judging by the fact you said "eventually", that is the case).

To encode:
If the answer is 1, send 1 if possible.
If the answer is 2 or 3, and 2 has not been sent, send 2 if possible.
If the answer is 2, and 2 has been sent, send 1 if possible.
If the answer is 3, and 2 has been sent, send 2 if possible.
If what you want to send is blocked, send 3.

To decode:
If 3 is sent, ignore it.
If 2 is sent, and 2 was not previously sent, remember that it has been sent.
If 1 is sent, and 2 was not previously sent, the answer is 1.
If 1 is sent, and 2 was previously sent, the answer is 2.
If 2 is sent, and 2 was previously sent, the answer is 3.

Edit: This solution can be generalized. Basically, set the same number aside to be ignored as can be blocked, and then communicate what data you can with what you have left.

____________________________
Who, me?
FNORD

---

[Last edited by Sillyman at 11-28-2008 06:07 AM]

RoboBob3000
Level: Smitemaster

Rank Points: 1982
Registered: 10-23-2003
IP: Logged

Either I don't understand this puzzle or it is missing some elements.

What about the case where the warden blocks every transmission? Then no information is ever sent and nothing can ever be known.

Do we get to operate on the assumption that Alice knows when a transmission has been blocked? That Bob knows? That both know? That neither know?

____________________________
http://beepsandbloops.wordpress.com/

TripleM
Level: Smitemaster
Rank Points: 1379
Registered: 02-05-2003
IP: Logged

My understanding of the problem was that at each step, the warden chooses one of the numbers, and Alice must send one of the other two.

Under this assumption, Sillyman's solution doesn't work at all, since if you were asked to transmit 1, then 1 would be blocked every time.

Dex Stewart
Level: Smiter
Rank Points: 355
Registered: 01-19-2007
IP: Logged

Bob definitely knows when a trasmission is blocked, since a minute has passed and he hasn't received anything.

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

No, it's not 'blocking transmissions' as in 'being in another room intercepting the number Alice sent'. The warden is in the room with Alice, telling Alice which number not to send each time. If Alice doesn't send one of the other two numbers exactly every minute, the warden kills them both. Sorry if I was unclear about that.

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

How about this?
A string of any amount of 1's (more than 0) followed by a 2 is a 2. A sting of any amount of 1's (more than 0) followed by a 3 is a 3. A string of any amount of 2's followed by a 3 is a 1.

So to send a 2: post 1, or if blocked post 3's until 1 is open, then post 1's until 1 is blocked then post 2.

To send a 3: post 1, or if blocked post 3's until 1 is open, then post 1's until 1 is blocked then post 3.

To send a 1: Post 2 or post 3's until 3 is blocked, then post 2's until 2 is blocked then post 3.

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

If the number is 1, the warden can block off 2 every time. Doesn't work.

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Ok, I think I have a proof of impossibility. I'm not completely satisfied with it, but I think it illustrates the basic problem.

Suppose that Alice and Bill come up with a plan that works. What this means is that not matter what number, X, the Warden requires Alice to transmit, there is a finite sequence of numbers that will indicate unambiguously to Bill that the number is X. Suppose that the longest of the sequences that indicates '1' to Bill is N1, N2, N3 ... Nm, A. Such a longest sequence must exist because of the finite requirement. Now, what that means is that after receiving Nm, Bill must still not know that the target number is '1' (otherwise Alice wouldn't need to transmit A) and that after receiving A, Bill must know that that the number is '1'. Consider the sequences N1, N2, N3 ... Nm, B and N1, N2, N3 ... Nm, C. At least one of these must NOT indicate '1' (if all three sequences indicated 1, then BIll would have been able to decode '1' before Alice sent Nm). So either sequence B indicates 1 as well and C doesn't (or C does and B doesn't), or both B and C indicate numbers other than 1. Suppose that both B and C indicate numbers other than 1. Then the warden could block A on the (m+1)st bit and Alice wouldn't be able to signal 1 to Bill (since that's the longest sequence required to signal 1). Suppose that B indicates 1 and C indicates 'not 1'. Then the warden could block C and Alice wouldn't be able to transmit something other than 1. Either way the warden is able to block at least one target number.

Now, if Alice has a choice of 4 numbers and the warden can only block 1 number each time, then Alice and Bill could work out a binary code where 1 and 2 represent 0's and 3 and 4 represent 1's. The warden wouldn't be able to block both numbers which represent either bit.

Alternatively, in the current problem, Alice could just keep transmitting random numbers until the warden dies. But that's not really keeping with the spirit of the problem (besides, the "warden" could be a computer and a wrong guess from Bill could trigger an emission of poisonous gas).

____________________________
Progress Quest Progress

lopsidation
Level: Master Delver

Rank Points: 176
Registered: 05-30-2008
IP: Logged

Great job stigant, that's right! I like this one because there's a lot of "How about this method?" before someone proves it impossible.

____________________________
"Happiness is like a cat. If you pay no attention to it and go about your business, you'll find it rubbing against your legs and jumping into your lap."

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Ok, here's one:

A knight and a dragon live on an (otherwise) deserted island. On this island, there are 10 wells (W1, W2, W3, ... W10) that all contain poisonous water which will kill you in exactly one hour (you exhibit no symptoms of poisoning until 60 minutes are up, and then you just drop dead). However, if the water in a higher numbered well is consumed AFTER (and within an hour) of the consuming of the water in a lower numbered well, then the poisons will neutralize each other. For example, you could drink from W3, then hustle over to W6 and have a drink, and be fine. But if you do it the other way around, you're dead (after 60 minutes of consuming the water in W6). Furthermore, W10 is reachable only by the dragon (it's way up high on a mountain top to which the dragon can fly, but to which the knight, in his clunky armor, cannot climb. (And he has no other clothes and he's too modest to attempt the climb naked) The other wells (W1...W9) are all within easy reach (and less than an hour's travel from anywhere on the island) of both the dragon and the knight.

Now the dragon and the knight hate eachother (this is not an unusual state of affairs between knights and dragons), but neither seems to be able to kill the other. The dragon is a bit of a pansy, and the knight left his lance at home. So one day, the dragon suggests a contest. "Let us both bring a glass of water from one of the wells for the other to drink. Then, after we have consumed the other's water, we will go about doing something about it, and whoever lives lives, and whoever dies dies."

"Hmmm, that doesn't sound very fair," thought the knight. "I mean, the dragon will surely bring me a glass of W10, and I won't be able to drink from a higher numbered well. And I can't do the same to him since I can't reach that well. So he'll be able to drink my poison and then run off to W10 to get the antidote." But he accepted the duel anyway since he hated the dragon so much he would rather die (in combat, and a duel, even of the mind, is combat) than continue to live on the same island with him.

So the next day, the two met on the beach, each with a glass of water which the other drank. An hour later the knight was still alive and the dragon was dead. What happened?

____________________________
Progress Quest Progress