Author |
Topic: Kabouter communication (Read 7585 times) |
|
Chronos
Full Member
 
Gender: 
Posts: 288
|
 |
Kabouter communication
« on: Sep 17th, 2002, 1:05pm » |
 Quote  Modify
|
I think I'm misunderstanding the Kabouters riddle. 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?
|
| « Last Edit: Sep 17th, 2002, 1:06pm by Chronos » |
 IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Kabouter communication
« Reply #1 on: Sep 17th, 2002, 2:20pm » |
Quote Modify
|
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!
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Kabouter communication
« Reply #2 on: Sep 18th, 2002, 11:17am » |
Quote Modify
|
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!
|
| « Last Edit: Sep 18th, 2002, 11:18am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Kabouter communication
« Reply #3 on: Sep 18th, 2002, 1:26pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Kabouter communication
« Reply #4 on: Sep 18th, 2002, 1:29pm » |
Quote Modify
|
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).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Carl_Cox
Newbie
Gender:
Posts: 23
|
|
Re: Kabouter communication
« Reply #5 on: Sep 18th, 2002, 7:36pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Kabouter communication
« Reply #6 on: Sep 19th, 2002, 10:53am » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Kabouter communication
« Reply #7 on: Sep 19th, 2002, 11:32am » |
Quote Modify
|
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").
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Kabouter communication
« Reply #8 on: Sep 19th, 2002, 11:42am » |
Quote Modify
|
Okay, I've got another one: 
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 ...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: Kabouter communication
« Reply #9 on: Sep 19th, 2002, 3:46pm » |
Quote Modify
|
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.
|
| « Last Edit: Sep 19th, 2002, 3:47pm by Jonathan_the_Red » |
IP Logged |
My arcade cabinet
|
|
|
Carl_Cox
Newbie
Gender:
Posts: 23
|
|
Re: Kabouter communication
« Reply #10 on: Sep 19th, 2002, 7:57pm » |
Quote Modify
|
on Sep 19th, 2002, 11:32am, 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!)
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Kabouter communication
« Reply #11 on: Sep 20th, 2002, 11:22am » |
Quote Modify
|
on Sep 19th, 2002, 3:46pm, 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?
|
| « Last Edit: Sep 20th, 2002, 11:24am by S. Owen » |
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: Kabouter communication
« Reply #12 on: Sep 20th, 2002, 11:42am » |
Quote Modify
|
No, the other reduction is not to the 100 prisoners... it's a lot cleaner, S. If you want a hint, private message me. 
|
|
IP Logged |
My arcade cabinet
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Kabouter communication
« Reply #13 on: Sep 25th, 2002, 8:32pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
luke's new shoes
Guest
|
|
Re: Kabouter communication
« Reply #14 on: Nov 12th, 2002, 3:39pm » |
Quote Modify
 Remove
|
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!
|
|
IP Logged |
|
|
|
Jamie
Newbie
Gender:
Posts: 37
|
|
Re: Kabouter communication
« Reply #15 on: Nov 13th, 2002, 3:46am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 24th, 2003, 4:23pm by Jamie » |
IP Logged |
|
|
|
randy
Guest
|
|
Re: Kabouter communication
« Reply #16 on: Jun 24th, 2003, 3:35pm » |
Quote Modify
Remove
|
on Nov 13th, 2002, 3:46am, 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
|
|
IP Logged |
|
|
|
Jamie
Newbie
Gender:
Posts: 37
|
|
Re: Kabouter communication
« Reply #17 on: Jun 24th, 2003, 4:22pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
MikeM
Guest
|
|
Re: Kabouter communication
« Reply #18 on: Sep 26th, 2003, 4:04am » |
Quote Modify
Remove
|
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
|
|
IP Logged |
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: Kabouter communication
« Reply #19 on: Sep 30th, 2003, 9:53pm » |
Quote Modify
|
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.
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
Matt Brubeck
Guest
|
|
Re: Kabouter communication
« Reply #20 on: Mar 12th, 2004, 8:08pm » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
Komninos
Guest
|
|
Re: Kabouter communication
« Reply #21 on: Oct 17th, 2005, 1:22am » |
Quote Modify
Remove
|
Guys, I think S. Owen already gave you the solution
on Sep 20th, 2002, 11:22am, 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?
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Kabouter communication
« Reply #22 on: Oct 17th, 2005, 3:28pm » |
Quote Modify
|
(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.
|
| « Last Edit: Oct 17th, 2005, 5:24pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Padzok
Junior Member
Gender:
Posts: 104
|
|
Re: Kabouter communication
« Reply #23 on: Oct 23rd, 2005, 4:04am » |
Quote Modify
|
on Oct 17th, 2005, 3:28pm, 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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Kabouter communication
« Reply #24 on: Oct 23rd, 2005, 11:28am » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print