Author |
Topic: Circular Telephone Game. (Read 1072 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Circular Telephone Game.
« on: Oct 14th, 2004, 3:48pm » |
 Quote  Modify
|
There are N people (from around the world).
Each of the N people knows exactly 2 different languages.
The circular telephone game is played between two players.
(who are not part of the N people)
The game is played as follows:
First Player arranges the N people in a circle.
Second Player next chooses a person from the circle and gives him a message he can understand. Now that person passes on that message to the person immediately right of him. (this, he can do so only if both of them understand the same language). This goes on until a circle is complete (ie. The first guy hears the message from the guy left of him) or the message cannot be passed on (ie. Two adjacent guys do not know a common language).
If the circle can be completed, First Player wins, otherwise Second Player wins.
Assuming you are the First Player, give an algorithm to arrange the N people in the circle if a win is possible. The algorithm should also say when there is no win for the First Player. The input to the algorithm is N pairs of languages, one for each of the N people.
[EDIT]
I think I should add a condition.
At each step of passing, the message must be translated.
i.e. if A talks to B in language L, then B must talk to C in a language other than L.
The messages received/told by the player initially chosen by the Second Player are exempt from this rule.
[/EDIT]
|
| « Last Edit: Oct 17th, 2004, 1:57pm by Aryabhatta » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Circular Telephone Game.
« Reply #1 on: Oct 15th, 2004, 1:13am » |
Quote Modify
|
we can probably do something with graphs 
At the very least see if it's connected.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Circular Telephone Game.
« Reply #2 on: Oct 15th, 2004, 5:51am » |
Quote Modify
|
Let's check my intuition: Hamiltonian cycle?
|
|
IP Logged |
|
|
|
NotMe
Guest
|
|
Re: Circular Telephone Game.
« Reply #3 on: Oct 15th, 2004, 11:09am » |
Quote Modify
 Remove
|
on Oct 15th, 2004, 5:51am, Barukh wrote:| Let's check my intuition: ...? |
|
Better try Eulerian circuit... on a different graph though.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular Telephone Game.
« Reply #4 on: Oct 15th, 2004, 1:09pm » |
Quote Modify
|
Towr, yes, a graph is involved 
Barukh, the hamilton cycle approach would work, if each person could know an arbitrary set of languages. In that case, Hamiltonian cycle can easily be reduced to the 'general' Circular Telephone problem, proving it NP-Hard.
But we are given that each person knows exactly 2 languages. That simplifies things.
NotMe is on the right track.
|
| « Last Edit: Oct 15th, 2004, 4:12pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular Telephone Game.
« Reply #5 on: Oct 16th, 2004, 4:08am » |
Quote Modify
|
I think I should add a condition.
At each step of passing, the message must be translated.
i.e. if A talks to B in language L, then B must talk to C in a language other than L.
The messages received/told by the player initially chosen by the Second Player are exempt from this rule.
Also, I think a similar problem has been discussed before here, where there is a line instead of a circle.
The circle version requires a little more work though...
The problem without the translation restriction is interesting too, it would be nice if we could come up with a polynomial time algorithm, or prove it NP-Complete...
Sorry about the foul up. 
|
| « Last Edit: Oct 16th, 2004, 4:28am by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular Telephone Game.
« Reply #6 on: Oct 17th, 2004, 2:07pm » |
Quote Modify
|
The problem without the translation restriction, i.e as was originally stated is NP-complete!!
So Barukh's intuition was right, as usual.
It has been proven by Bertossi in 1981 that Hamiltonian Cycle problem for Line graphs is NP-Complete.
If G(V,E) is a graph, the line graph L(G) of G is defined as:
V(L(G)) = E (i.e L(G) has a vertex corresponding to each edge of G), ei and ej are adjacent in L(G) if they have a common endpoint in G.
Given a graph G with n vertices and m edges, associate with each vertex a different language. Corresponding to each edge if we have a person, who speaks the languages given the the endpoints of that edge, L(G) has a hamiltonian cycle iff the Circular Telephone game has an arrangement in which the first player wins.
Reference to Bertossi Paper is:
[1981] Bertossi, A.A., The edge Hamiltonian path problem is NP-Complete. Info Proc Letters 13 (1981), 157-159.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular Telephone Game.
« Reply #7 on: Oct 17th, 2004, 7:47pm » |
Quote Modify
|
Here is a brief outline of the NP-completeness proof of the (unrestriced) Circular Telephone Game Problem. (I don't know if it is the same as in the Bertossi paper)
It is enough if we show that the Hamiltonian Cycle problem for Line Graphs is NP-Complete.
We will need a definition and a couple of facts.
Def:: CIRCUIT-COVER problem. Does G have a circuit cover?
{
A circuit cover of a graph G is a closed trail C (which does not repeat edges) such that edge each of G, has atleast an endpoint in C.
}
Fact 1) G has a circuit cover if and only if L(G), the line graph of G has a hamiltonian cycle.
Fact 2) The Hamiltonian Cycle problem for 3-regular graphs (3HC) is NP-Complete.
Based on Fact 1) and Fact 2), it is enough we can reduce 3HC to CIRCUIT-COVER.
Let G be a given 3-regular graph. Construct a graph G' as follows. Take each edge of G, insert a new vertex into that edge (sort of like drawing the midpoint of a the edge). So if {u,v} was an edge in G, we insert a new vertex z (call it uv/2) such that {u,v} is replaced by {u,z} and {z,v}.
Suppose G has a hamiltonian cycle. Clearly G' has a circuit-cover, as we can replace an edge {u,v} by {u,uv/2} and {uv/2,v} and since the degree of each vertex of G' is at most 3, each edge must have an endpoint in the resulting circuit.
Let C be a circuit cover of G'. We can easily show that each vertex of G has to appear in C.
Suppose a vertex v of G, which does not appear in C, has the neighbours a,b,c in G. In G' its neighbours are va/2, vb/2 and vc/2. Consider the edges {v,va/2}, {v,vb/2} and {v,vc/2}. {v, va/2} must have an endpoint in C. It cannot be v. So it is va/2. The only way va/2 can appear (without v appearing) is if the edge {a,va/2} appears. But in that case, the only way out of va/2 is to go to v.
If {x,xy/2} occurs in C then it has be to immediately followed by {xy/2,y}. Such pairs of edges could be merged to give a hamiltonian cycle in G as each vertex of G is present in C.
|
| « Last Edit: Oct 17th, 2004, 7:51pm by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Circular Telephone Game.
« Reply #8 on: Oct 18th, 2004, 1:14am » |
Quote Modify
|
Aryabhatta, thanks for posting this interesting result here!
I've got this question: in the variation with the translation restriction, what is the structure of the graph that its Hamitonian cycle solves the problem?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular Telephone Game.
« Reply #9 on: Oct 18th, 2004, 9:16am » |
Quote Modify
|
on Oct 18th, 2004, 1:14am, Barukh wrote:Aryabhatta, thanks for posting this interesting result here!
I've got this question: in the variation with the translation restriction, what is the structure of the graph that its Hamitonian cycle solves the problem? |
|
In the problem with the restriction, we aren't looking for a Hamiltonian cycle but an Euler Circuit in the graph where languages are vertices and edges are people.
For graphs with no Euler Circuit but an Euler trail, every edge must have one of the two odd vertices as an endpoint (a bipartite graph with one partition having exactly 2 vertices and each vertex of the second partition connected to each of the two odd vertices). Not all such graphs lead to a solution.
Basically if there is a solution starting a person i, then there is an Euler Trail starting with that edge. This must be true for every person. So every edge must have an endpoint with an odd vertex if there is no euler circuit.
unless, I have goofed up again .
|
| « Last Edit: Oct 18th, 2004, 9:37am by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Circular Telephone Game.
« Reply #10 on: Oct 19th, 2004, 1:58am » |
Quote Modify
|
on Oct 18th, 2004, 9:16am, Aryabhatta wrote:For graphs with no Euler Circuit but an Euler trail, every edge must have one of the two odd vertices as an endpoint (a bipartite graph with one partition having exactly 2 vertices and each vertex of the second partition connected to each of the two odd vertices). Not all such graphs lead to a solution.
Basically if there is a solution starting a person i, then there is an Euler Trail starting with that edge. This must be true for every person. So every edge must have an endpoint with an odd vertex if there is no euler circuit.
unless, I have goofed up again . |
|
This idea with the Euler Trails is very nice; I haven’t thought about it. However, I feel it won’t work because of the last connection (between the last guy and the first). Please let me know if I am missing something in the following setup:
There are 5 languages A through E, and 6 people: 1 (A,B); 2 (A,C); 3 (A,D); 4 (B,E); 5 (C,E); 6 (D,E). The underlying graph satisfies your conditions, right? How would you set the order then?
on Oct 18th, 2004, 9:16am, Aryabhatta wrote:
In the problem with the restriction, we aren't looking for a Hamiltonian cycle but an Euler Circuit in the graph where languages are vertices and edges are people. |
|
Yes, I understand this – it just states that the natural way to build a graph is as you described it, and look for the Euler circuit in it. I asked whether there is a way to build another graph (how natural is it – that’s another question), so that finding a Hamiltonian circuit solves the problem?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Circular Telephone Game.
« Reply #11 on: Oct 19th, 2004, 10:06am » |
Quote Modify
|
There is a cycle iff the graph is connex and each language is spoken by an even number of persons.
To form the cycle, you just start a string and add people at the end as long as you can. When you can not, that means the language at the end has been used up. But because the number of speakers of that language is even and the speakers are always paired in the string, that implies that the first in the row speaks the same language as the last. So, you can close a first loop.
Then you restart with the rest of the people.
When you have only loops left, the conectivity implies that there is at least one language in the first loop that is spoken in another loop. If not, the first loop would be a disconnected island. Therefore, you can open the 2 loops where the common language is spoken and combine them in a single loop.
You can continue merging loops like that until there is only one large loop left.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Circular Telephone Game.
« Reply #12 on: Oct 19th, 2004, 10:11am » |
Quote Modify
|
on Oct 19th, 2004, 1:58am, Barukh wrote:
This idea with the Euler Trails is very nice; I haven’t thought about it. However, I feel it won’t work because of the last connection (between the last guy and the first). Please let me know if I am missing something in the following setup:
There are 5 languages A through E, and 6 people: 1 (A,B); 2 (A,C); 3 (A,D); 4 (B,E); 5 (C,E); 6 (D,E). The underlying graph satisfies your conditions, right? How would you set the order then?
|
|
The only graph whose Euler trail we are interested in is the path of length 2. (I had mentioned that not all graphs satisfy the restrictions of the problem, In fact all but the path of length 2 do not). This is because there must be an Euler trail such that the first and the last edges of the trail have a common endpoint, which is possible only for the path of length 2.
So the algo is, look for an Euler circuit, If no euler circuit, check for a path of length 2.
Sorry if I wasn't clear.
Quote:
Yes, I understand this – it just states that the natural way to build a graph is as you described it, and look for the Euler circuit in it. I asked whether there is a way to build another graph (how natural is it – that’s another question), so that finding a Hamiltonian circuit solves the problem? |
|
Sorry, I misunderstood your question. That is an interesting question, haven't thought about it.
|
|
IP Logged |
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Circular Telephone Game.
« Reply #13 on: Jan 21st, 2007, 9:31pm » |
Quote Modify
|
I am giving a shot at the implementation. It takes polynomial time.
We can represent the inputs as the number of pairs (fr,de) (de,en) etc. in a nXn grid. n being the number of languages. If (fr,de) has 2 speakers
then
fr de
fr 0 2
de 2 0
Code:
int comm(int startPoint, int i, int j, int langCount)
{
//decrement the (i,j)th cell and (j,i)th cell
a[i][j]--;a[j][i]--;
//check if the n has reached 0 or i==startPoint
if(n==0)
if(startPoint==i)
return 1; //success
else
return 0; //fail
//look for a person who can speak the language
for(int k=0;k<n && k!=i;k++)
if(a[j][k] > 0)
comm(startPoint, j,k, n-1);
return 0; //fail
}
|
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print