wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Kabouter communication
        
(Message started by: Chronos on Sep 17th, 2002, 1:05pm)
Title: Kabouter communication
Post by Chronos on Sep 17th, 2002, 1:05pm
I think I'm misunderstanding the Kabouters riddle (http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml#kabouters).  By the end of the sorting, every Kabouter must know the color of his own hat.  If nothing else, he just has to look at the hats of the other Kabouters in his group, and if he knows that everyone's sorted properly, then he obviously knows that his own hat is the same color.  Since he didn't know it before, that information has obviously been communicated to him somehow, and the only other folks around to communicate it are other Kabouters.

Now, if the problem statement just said that Kabouters never talk about hat colors, then I could devise some non-verbal method of communication, perhaps something similar to the parity method in the single-file hat execution problem.  But the riddle says "How do they do this without talking or communicating the color of their hats to any of the other kabouters?".  Anything they can possibly do to sort themselves will end up communicating hat colors.

What am I missing?
Title: Re: Kabouter communication
Post by S. Owen on Sep 17th, 2002, 2:20pm
Agreed, "communicating" is a loaded term. I assume it means that no one can say "hey, your hat is green!" or write it on a piece of a paper, or spell it out in semaphore or skywriting or whatever.

So, I think this is just a variant on the red-eyed/brown-eyed monks riddle, and the solution can be translated into a plausible solution here.

Now, I could imagine the riddle is intended to be more like this variant:

blah blah blah...  "At the annual Kabouter convention, the King Kabouter says that all Kabouters with red hats should come back to be counted next Monday, and that all Kabouters with brown hats should come back to be counted next Tuesday. All the Kabouters look around for a bit then return to their homes across the lovely Netherlands. Next Monday, all the Kabouters with red hats show up. How did they do it?"

Now that is hard... I think there is no way this interpretation has an answer. So, I'm sticking to the more lax interpretation. But, I could be wrong!
Title: Re: Kabouter communication
Post by James Fingas on Sep 18th, 2002, 11:17am
Did this strike anyone as similar to the Red-Eyed/Brown-Eyed monks question? Or the simultaneous hat color guessing question?

I think the key here is that they sort themselves, but they don't know the color of their hat until the sorting is done.

Oooh! I just thought of something! They sort themselves, and keep their eyes closed during the sorting. They don't open their eyes again until they are un-sorted again. That way, they never learn the color of their own hat!
Title: Re: Kabouter communication
Post by Chronos on Sep 18th, 2002, 1:26pm

Quote:
Oooh! I just thought of something! They sort themselves, and keep their eyes closed during the sorting. They don't open their eyes again until they are un-sorted again. That way, they never learn  the color of their own hat!
An interesting possibility, but if they all have their eyes closed, then they're going to do a pretty hopeless job of sorting.  Perhaps some method where each Kabouter closes his eyes at some stage in the sorting?  Can you think of any way to implement this?

The way I'm interpreting this, is that the only communication allowed is by moving from one group to the other.  Of course, there are plenty of solutions even so:  For instance, one leader Kabouter uses moving back and forth for Morse code, and "writes" out the color of each individual Kabouter's hat, by name.  Then, some other Kabouter "writes" out the color of the leader's hat.

But I suspect that the riddle writer had something else in mind, here.
Title: Re: Kabouter communication
Post by James Fingas on Sep 18th, 2002, 1:29pm
My solution is pretty cool. It has just one sorting step, where the Kabouters collect information.

After that, they know what to do, and can sort themselves with their eyes closed (well, except for bumping into things--but they're so small they won't hurt themselves when they fall over each other).
Title: Re: Kabouter communication
Post by Carl_Cox on Sep 18th, 2002, 7:36pm
What about this?


One kabouter organizes all the other kabouters by moving them around.  He divides all the others by color hat.  He doesn't have to tell them their color hat, just tell them which group to join.  When he's gone through everyone, there are three groups: one for each color hat, and the dividing kabouter.  Then, one of the other kabouters tells the dividing kabouter which group to join, based on his color hat.  No one has to talk about hats or colors, but they do have to know that that is the criteria.

Or is that too much communicating?
Title: Re: Kabouter communication
Post by James Fingas on Sep 19th, 2002, 10:53am
There are a lot of solutions to this problem that work, but most of them are tantamount to the Kabouters telling each other the color of their hats.

I believe that I've come up with the "correct" solution, because each Kabouter figures out which group to join, without knowing what hat color he/she has.

Only when the groups start to form up will the Kabouters learn their hat colors. And as I said, if the Kabouters could form their groups with eyes closed, and then successfully dissipate from those groups with eyes closed, they would never have to know their hat color.

This is different from the "leader" solution, because although everyone except the leader could be formed into groups with eyes closed, thus not knowing their hat colors, you can't sort the leader without both the leader and at least one other Kabouter knowing their own hat colors.
Title: Re: Kabouter communication
Post by Chronos on Sep 19th, 2002, 11:32am

Quote:
This is different from the "leader" solution, because although everyone except the leader could be formed into groups with eyes closed, thus not knowing their hat colors, you can't sort the leader without both the leader and at least one other Kabouter knowing their own hat colors.
It's not quite that bad:  The leader is the only one who needs to gain information.  The fellow who sorts the leader would need to tell him his hat color, but he doesn't need to look at anyone other than the leader, and doesn't need to see which group the leader goes to.  Of course, that's still not good enough.

Come to think of it, though, I think I've just figured out James' solution.  Good thing, too, or I would have spent the rest of the week thinking about it instead of doing my homework ;).  It's similar to a few other riddles here, actually.  And it does seem to work, as long as nobody knows who else is in his group (so when you trip over someone else with your eyes closed, you don't say "Sorry about that, Bob").
Title: Re: Kabouter communication
Post by James Fingas on Sep 19th, 2002, 11:42am
Okay, I've got another one:  8)

All Kabouters, take off your hats and look at them. Red Kabouters to the left, blue Kabouters to the right. Hop to it, there's no time to waste!

No, no, my left! ... stupid Kabouters ...
Title: Re: Kabouter communication
Post by Jonathan_the_Red on Sep 19th, 2002, 3:46pm
Eureka! I do believe I have it as well. Nifty.

As it turns out, the solution to this problem is not very similar to the red-eyes-brown-eyes problem, but it is very similar to a different problem.
Title: Re: Kabouter communication
Post by Carl_Cox on Sep 19th, 2002, 7:57pm

on 09/19/02 at 11:32:07, Chronos wrote:
Come to think of it, though, I think I've just figured out James' solution.  Good thing, too, or I would have spent the rest of the week thinking about it instead of doing my homework ;).

Curse you!  there goes my homework!

grr on you all!  (but don't tell me!)
Title: Re: Kabouter communication
Post by S. Owen on Sep 20th, 2002, 11:22am

on 09/19/02 at 15:46:51, Jonathan_the_Red wrote:
As it turns out, the solution to this problem is not very similar to the red-eyes-brown-eyes problem, but it is very similar to a different problem.

OK, here was my reduction to the monks problem:

Mayor Kabouter: "All Kabouters with red hats should gather in the town square here at midnight to be counted."

Kabouter 1: "But we don't know the colors of our own hats!"

Mayor Kabouter: "Oh right, I almost forgot - I can tell you that at least one of you has a red hat. Does that help? Remember, only folks who have red hats can show up! If nobody shows up tonight, well, we'll try to meet again on the following night."

Kabouter 2: "What about the brown hats?"

Mayor Kabouter: "Easy... everyone who isn't counted when the red hats gather should gather on the following night to be counted."


Now, this assumes that there is at least one red hat out there, and that they all know who gathers or doesn't gather each night in the town square, but it works, no?


Is the other reduction to the 100 prisoners problem? Is it cleaner?
Title: Re: Kabouter communication
Post by Jonathan_the_Red on Sep 20th, 2002, 11:42am
No, the other reduction is not to the 100 prisoners... it's a lot cleaner, S. If you want a hint, private message me. :)
Title: Re: Kabouter communication
Post by Chronos on Sep 25th, 2002, 8:32pm
It's easy to find a solution that ends up letting them know their hat color.  But that's not what we want.  In the "true" solution, what happens is something like this:

All Kabouters show up in the town square.
The Mayor Kabouter gives them instructions (skip this step if they're used to this and already know the plan).
All Kabouters look around for a while, and make a decision.
They all then put on blindfolds (or, if you don't trust them to keep blindfolds on, they wait for nightfall).
Then, each Kabouter walks over to the east end or the west end of the town square.
They're now sorted.
Then, they all mingle back together randomly.
Finally, they take their blindfolds off (or wait for dawn).
At this point, no Kabouter knows his hat color, still.

I might also add that this solution does not require Kabouters to be particularly clever.  It might take a little time, but there's no math or logic involved above a very basic level (more basic than the monks).
Title: Re: Kabouter communication
Post by luke's new shoes on Nov 12th, 2002, 3:39pm
i didnt think it was a hard question, but the story line behind it was confusing. i chose to rewrite it..

Kabouters: very small (up to 10 cm) people living in the forests, in mushrooms and roots. Wearing old-fashioned clothes AND they all wear a pointed hat. Those are kabouters...

In the forests of the Netherlands live a large number of kabouters wearing two different colors of pointy hats. Kabouters consider it very rude to talk about the color of the hat they are wearing, so much so that they don't even know the color of their own hat. They are able to look and distinguish the color of the hats on other kabouters. (They just won't talk about it.) One day the kabouters decide to split up into two groups, based on the colour of their hats. How do they do so?

********************************************

SOLUTION: the kabouters form a line. the first two kabouters in the line form two groups. if the both have the same colour hat then none of the other kabouters move and they therefore know they have the same colour hat and make a single group. if they have different colour hats then the next kabouter in line joins a random group. he tell weather he is in the right group by the actions of the next kabouter in line and so on until we reach the last kabouter. if he joins the wrong group then noone else moves until he swaps. if he joins the right group they all go home!
Title: Re: Kabouter communication
Post by Jamie on Nov 13th, 2002, 3:46am
It seems to me that this still involves communication between the Kabouters, albeit non-verbal. A solution that seems to work, and that allows the Kabouters to form the two groups blindfolded (and therefore never learn their own hat colour) is as follows:

[hide]
Let's assume the hat colours are red and blue. The Kabouters gather in the town square and look around. Each Kabouter, if he sees an even number of blue hats goes to the left, otherwise he goes to the right.
[/hide]
Title: Re: Kabouter communication
Post by randy on Jun 24th, 2003, 3:35pm

on 11/13/02 at 03:46:43, Jamie wrote:
It seems to me that this still involves communication between the Kabouters, albeit non-verbal. A solution that seems to work, and that allows the Kabouters to form the two groups blindfolded (and therefore never learn their own hat colour) is as follows:


Let's assume the hat colours are red and blue. The Kabouters gather in the town square and look around. Each Kabouter, if he sees an even number of blue hats goes to the left, otherwise he goes to the right.


You mentioned this will let them do it blindfolded...but they you require that he "sees an even number of hats"  Contradictory
Title: Re: Kabouter communication
Post by Jamie on Jun 24th, 2003, 4:22pm
Good point; let me clarify. They can't decide which group (left or right) to join without looking around, but at that point the groups are both empty, so knowing which group they are going to join doesn't tell them their hat colour. They can then be blindfolded and form the groups blindfolded (without learning their own hat colour).
Title: Re: Kabouter communication
Post by MikeM on Sep 26th, 2003, 4:04am
all right, think I've got a solution, albeit a slightly complicated one.  

Someone mentioned before that you could easily blindfold all the kabouters but one, and then have that one sort the rest, but what do you do with him?  Suicide's an option, but I think a better way is this:

After he finishes sorting everyone out to opposite sides of the town square (or wherever they are) he picks one group, goes up to them, and selects a random number of kabouters to lead to the center of the square.  Out of them, he picks two special ones, and designates them Kabouter A and Kabouter B.  Next, he walks over to the other group, picks out a random number of them to join him in the center, and leads them back.  Now, most of the kabouters are still separated into their respective colors, but Kabouter A, Kabouter B, and the original Kabouter (plus a few other randomly selected kabouters) are standing in the middle.

The original kabouter and Kabouter A then separate themselves a bit from the randomly selected group at the middle of the square.  He puts on a blindfold, and both he and Kabouter A spin round so they lose their bearings, and can't remember which side of the square has which colored hats.  Kabouter A then removes his blindfolded, looks at the original kabouter's hat, and sends him to the appropriate side.  Because he spun around, Kabouter A doesn't know what side he, himself, was originally sorted into, and because there are a random number of kabouters of both sides in the center, he doesn't know which group he came with.  He puts his blindfold back on, and spins round once more so he's disoriented again.  

The rest of the Kabouters, (besides Kabouter A and Kabouter B) all return to their original side (remember, they never spun around, so they'll know which way to go, but not what color theyr'e returning to.)   Now, it's just Kabouter A and Kabouter B standing in the middle of the square.  Kabouter A doesn't have a clue which side is which, but Kabouter B knows which side they came from, so he leads him back.  Now all the Kabouters are sorted properly, and none of them will know what colour hat they have.  They won't need to see to count themselves, as the riddle states that they need to do.

Does that work?  Anyone still interested in this?

Mike
Title: Re: Kabouter communication
Post by Mike_V on Sep 30th, 2003, 9:53pm
I like it. Interesting (and like you said complicated) way. Of course it does require a lot of communication among the Kabouters. I think the best answer was posted a bit back by Jamie. That way can be done purely on instinct. With no information passed from one to another at all.
Title: Re: Kabouter communication
Post by Matt Brubeck on Mar 12th, 2004, 8:08pm
I came up with another method, different from the ones already posted.  My method does not sort the Kabouters into two separated areas, but instead sorts them into a line with all the red hats at the front of the line and all the green hats at the back of the line.  It can be done without any Kabouter learning the color of its own hat, though not as elegantly as the best solution already posted.  Hint: The line grows one Kabouter at a time, and once a Kabouter has joined the line it does not change places with other Kabouters already in the line.
Title: Re: Kabouter communication
Post by Komninos on Oct 17th, 2005, 1:22am
Guys, I think S. Owen already gave you the solution


on 09/20/02 at 11:22:53, S. Owen wrote:
OK, here was my reduction to the monks problem:

Mayor Kabouter: "All Kabouters with red hats should gather in the town square here at midnight to be counted."

Kabouter 1: "But we don't know the colors of our own hats!"

Mayor Kabouter: "Oh right, I almost forgot - I can tell you that at least one of you has a red hat. Does that help? Remember, only folks who have red hats can show up! If nobody shows up tonight, well, we'll try to meet again on the following night."

Kabouter 2: "What about the brown hats?"

Mayor Kabouter: "Easy... everyone who isn't counted when the red hats gather should gather on the following night to be counted."


Now, this assumes that there is at least one red hat out there, and that they all know who gathers or doesn't gather each night in the town square, but it works, no?


Is the other reduction to the 100 prisoners problem? Is it cleaner?


The clue is that all Kabouters no how many blue hats and red hats there are except their own hat. So let's say there are 6 red and 4 blue.
Everyone with a blue hat sees 6 red and 3 blue and guesses that it's either 7 red or 6 if he's not a red hat wearer.
Everyone with a red hat sees 5 red and 4 blue and guesses that it's 6 red or 5 red if he isn't a red hat wearer.
So those with red hats will chose to gather on the 6 night while those with blue would have chosen to gather on the 7th.
Right?
Title: Re: Kabouter communication
Post by Icarus on Oct 17th, 2005, 3:28pm
(You might want to note, Komninos, that the people you are trying to talk to ended their conversation 2 years ago, with the exception of the last post before yours, at 1.5 years ago. It's doubtful any of them are still around (the ones I know about have not visited in quite a while.))

S.Owen's solution works, but it requires a lot of time, and intelligent kabouters. Jamie's solution (which was James Fingas' unpublished one), requires only enough time and intelligence for each kabouter to count how many red hats they see.

However, both solutions have a fatal flaw, as has been pointed out in other threads for this riddle: any kabouter who knows the final counts (which was the purpose of this grouping exercise) will know his own hat color, as one of the counts will be 1 more than the count he took when sorting himself.

MikeM's solution avoids this difficulty, as long as the kabouters are wise enough not to count each other at the gathering until they are blindfolded.
Title: Re: Kabouter communication
Post by Padzok on Oct 23rd, 2005, 4:04am

on 10/17/05 at 15:28:59, Icarus wrote:

S.Owen's solution works, but it requires a lot of time...

Jamie's solution (which was James Fingas' unpublished one), requires only ....

However, both solutions have a fatal flaw... ...any kabouter who knows the final counts (which was the purpose of this grouping exercise) will know his own hat color ....

MikeM's solution avoids this difficulty, as long as the kabouters are wise enough not to count each other at the gathering until they are blindfolded.



Quote:
Kabouters: very small (up to 10 cm) people living in the forests, in mushrooms and roots. Wearing old-fashioned clothes AND they all wear a pointed hat. Those are kabouters...

In the forests of the Netherlands live a large number of kabouters wearing two different colors of pointy hats. Kabouters consider it very rude to talk about the color of the hat they are wearing, so much so that they don't even know the color of their own hat. They are able to look and distinguish the color of the hats on other kabouters. (They just won't talk about it.) Now every year all kabouters need to be counted and traditionally they present themselves in two groups divided by the color of their hats. How do they do this without talking or communicating the color of their hats to any of the other kabouters?  



As far as answering the original riddle goes, both Jamie's and MikeM's work.  None of the Kabouters will know the colour of their own hat unless they are also told the result of the count (and in MikeM's case, not even then unless they also knew how many they had seen of at least one colour).

S Owens' solution actually requires that they all find out the colour of their hat in order for the solution to work at all.  Maybe it's just semantics, but it seems as thought they have each had the colour of their own hat "communicated" to them by the behaviour of  the group.

Of course, if it does not matter if you know your own hat colour, it only matters that you are not told directly, then all 3 solutions achieve that.
Title: Re: Kabouter communication
Post by Icarus on Oct 23rd, 2005, 11:28am
It is true that by S.Owen's method, everyone will realize their hat color as part of the process. By Jamie's (and James Fingas's) method, only those who know the total count will know their own hat color. But this will include at least one Kabouter and probably more.

The puzzle does not state that Kabouters intentionally do not know their own hat color, so one can certainly claim that this is not a problem (indeed, I believe that Jamie's is the intended answer). However, the fact that they have gotten this far without finding out would indicate that they have actively avoided discovery of the color. And if this is the case, then even Jamie's solution is going to be unacceptable, as nobody will want to know the final count, and someone must know it for the exercise to have any value.

In this respect, MikeM's solution is superior. For then all those who deal with the count can avoid learning their hat color simply by not counting how many hats of each color they see when not blindfolded.
Title: Re: Kabouter communication
Post by Padzok on Oct 23rd, 2005, 12:14pm

on 10/23/05 at 11:28:36, Icarus wrote:
By Jamie's (and James Fingas's) method, only those who know the total count will know their own hat color. But this will include at least one Kabouter and probably more...

In this respect, MikeM's solution is superior. For then all those who deal with the count can avoid learning their hat color simply by not counting how many hats of each color they see when not blindfolded.



Quote:
Now every year all kabouters need to be counted and traditionally they present themselves in two groups divided by the color of their hats.


I suppose the puzzle is ambiguous as to whether they simply need to divide themselves into groups, and only the total number of Kabouters is required; or whether they need to divide themselves into groups and count the number in each group.

Because I had assumed it was the latter, I had assumed the counting would be done by a non-Kabouter (or mechanically).  If not (ie if a Kabouter does the count), then clearly whoever does the counting HAS to know the colour of their own hat, regardless of the method of separating the groups.

However, if it is the former (ie only the total number is required), then I don't think Jamie's solution is any worse than MikeM's.  Am I missing something?
Title: Re: Kabouter communication
Post by Icarus on Oct 23rd, 2005, 7:10pm
If it were the former (only the total number of kabouters is needed), there would be no need to break up into groups at all, so I interpret the puzzle to mean that a count of each hat color was required. I also assumed that this was an internal kabouter thing, as otherwise, you could have all the kabouters blindfold themselves, and have a non-kabouter separate them and count them.

And MikeM's solution allows counting without any kabouter knowing which group he is in - provided those responsible for collecting the count from each group are never informed of the totals by color themselves. (They each present their count to a clerk, who has left his group to go to another room after he himself is counted. He sees the two come in and knows their hat color, so he knows which group they counted, but he has no idea which came from his group. And since he leaves his group before the count is finished, he does not know the outcome beforehand.)
Title: Re: Kabouter communication
Post by Padzok on Oct 24th, 2005, 11:13am
That's a good method of ensuring the Kabouter who knows the final count does not inevitably have to find out the colour of his own hat to know the final scores for each group.   It's also possible to use more than one "divider" so that the divider does not accidentally count them as he is dividing.

However, of course, any Kabouter who already knows  all of the other Kabouters - and how many of each group he can see - will inevitably know the colour of his own hat as soon as he is told the final scores.

So either there have to be additional contraints on that final Kabouter (to prevent him knowing all the others) or else Kabouter society must be such (eg  thousands of the little blighters in lots of far-scattered communities) such that no Kabouter knows all the others.  
Title: Re: Kabouter communication
Post by DewiMorgan on Jan 8th, 2007, 10:22am
Personally, I think only Matt Brubeck's answer is suitable for large numbers, but everyone seems to be ignoring that one.

It does cause them to self-segregate (which is what I think the question asks), and does mean that nobody needs to know how to count or recognise an odd or an even number, but does assume that "the one who counts" can tell the difference between the hats. But that's sort of assumed by all other solutions anyway.

The other solution, where there's a single person doing the segregation, you just divide into three groups and let "the one who counts" add him appropriately to the relevant group.
Title: Re: Kabouter communication
Post by towr on Jan 8th, 2007, 11:00am

on 01/08/07 at 10:22:50, DewiMorgan wrote:
Personally, I think only Matt Brubeck's answer is suitable for large numbers, but everyone seems to be ignoring that one.
He fell in between two large intervals of inactivity of the thread.  It happens.

Growing the line one at a time, though, would take rather long if there are a lot of kabouters.
Divide and conquer might help. Sorting smaller groups first, and then joining the sorted groups appropriately.
Title: Re: Kabouter communication
Post by Icarus on Jan 8th, 2007, 5:00pm
Matt's method sorts the kabouters, but I don't see any good means of obtaining a count out of it without the counter knowing which group he belongs to.

What makes you think the other methods are inappropriate for large groups? Obviously James & Jamie's solution is going to be very difficult as the group gets bigger, as is S. Owen's. But I don't see how MikeM's is any worse than Matt's.
Title: Re: Kabouter communication
Post by towr on Jan 9th, 2007, 1:01am

on 01/08/07 at 17:00:08, Icarus wrote:
Matt's method sorts the kabouters, but I don't see any good means of obtaining a count out of it without the counter knowing which group he belongs to.
You can do the same sort of thing as in MikeM's solution. It's pretty much the same process anyway.
Title: Re: Kabouter communication
Post by Icarus on Jan 9th, 2007, 5:12pm
Maybe I should mention Matt's actual method (at least, what I believe his method to be, since he doesn't specify it).

The kabouters form a line with reds on the left and greens on the right. They do this by joining the line one at a time at the division between the two colors. When a kabouter's turn comes to join, he simply goes to the dividing point, pushes the two kabouters on each side out a little to make room, and steps in line there. Everyone keeps moving out as they receive more pushes.

For them not to learn their own hat color, though, they must blind-fold themselves upon joining the line, and then spin around until they are completely disoriented (if they aren't disoriented, then they will know if they are being forced to move in the red direction or green direction). The next kabouter can line them up with the approriate direction of travel when he joins.

But here is the rub: once they are done, no-one knows exactly where the division is. The last guy to join knows it is on one side of him or the other - but he doesn't know which side. For a count to be made, someone has to see where to stop counting reds and start counting greens.

The simplest solution I can think of is this: the last guy doesn't join the line. It is his job to count everyone else. He does this, and then everyone mills about until they are well mixed and then removes their blindfolds. He hunts down the king (or whoever needs the numbers) and tells the results to him. The king adds one to the appropriate count for the counter himself. The counter goes off, and carefully avoids any source that would tell him the official totals for that year.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board