Author |
Topic: How many cities does udakk have? (Read 1064 times) |
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
 |
How many cities does udakk have?
« on: Feb 19th, 2004, 12:46am » |
 Quote  Modify
|
Udakk had at least 12 and at most 28 cities. If two cities did not trade with each other, then there were just two cities which traded with both of them. If they did trade with each other, then no city traded with both of them. How many cities were there?
P.S->i don't know the answer
|
|
 IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: How many cities does udakk have?
« Reply #1 on: Feb 19th, 2004, 6:56am » |
Quote Modify
|
Shouldn't there be a min or a max number?
Besides I am confused here:
You say if two cities dont trade then they have two other cities that trade with them. However if they trade with each other none of the cities trade with them.
Here's the scenario
Consider cities A,B,C,D
A and B don't trade with each other. So by first defintion let's say C and D trades with A and B
so C <-> A
C <-> B
D <-> A
D <-> B
But this doesn't satisfy second condtion. that since C and A trade with each other then it cannot trade with B and similar argument with B. In either case only second condition can be satisfied and we have a pair of two cities. Giving the number of cities = 2n which lies between 12 and 28.
Unless of course i am not understanding the problem correctly 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: How many cities does udakk have?
« Reply #2 on: Feb 19th, 2004, 6:59am » |
Quote Modify
|
Wow. I started by making an undirected graph, but I got lost quickly. With 12 to 28 cities there are going to be a lot of edges...
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: How many cities does udakk have?
« Reply #3 on: Feb 19th, 2004, 7:03am » |
Quote Modify
|
Sameer, the simplest graph that illustrates the problem is a square, with the corners representing nodes.
A - B
B - C
C - D
D - A
Adding even a single node changes the structure, since the requirements effective require you to compare each node to every other node. A brute force method would require astronomical amount of time, so I hope there is a pattern or algorithm for this problem.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How many cities does udakk have?
« Reply #4 on: Feb 19th, 2004, 7:11am » |
Quote Modify
|
I suppose any 4 nodes have to form a square.. Maybe that can help..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: How many cities does udakk have?
« Reply #5 on: Feb 19th, 2004, 7:16am » |
Quote Modify
|
Sameer,
"If they did trade with each other, then no city traded with both of them." means that there is no city that trades with both of them but there are cities which may trade with one of them.
=============================================
My working so far has shown that one should not start with cities that do not trade but two cities that do trade and from then on add cities to it.
I actually managed to draw a 16 node graph but i cannot assure that it satisfies all the condition since manual checking gets tedious with such a complicated figure.
=============================================
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: How many cities does udakk have?
« Reply #6 on: Feb 19th, 2004, 8:27am » |
Quote Modify
|
I think towr has the right idea.
:: I got a seven node graph working. It is two squares connected at a single point, like a figure 8. Each outside node is connected to the opposite outside point. I'm at work and all I have is MS paint, not exactly a useful tool for anything besides crashing. I hope my description works.
Can anyone else extend this pattern? ::
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How many cities does udakk have?
« Reply #7 on: Feb 19th, 2004, 9:30am » |
Quote Modify
|
I can't get a 7 node graph to work..
Are you sure there aren't any cycles of 3 nodes? (because those are clearly disallowed)
I think it might help in construction to color every node with one of two colors, and no two connected nodes may have the same color.
|
| « Last Edit: Feb 19th, 2004, 9:33am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: How many cities does udakk have?
« Reply #8 on: Feb 19th, 2004, 11:43am » |
Quote Modify
|
I got a seven node graph to work. I think the issue may be more lingual. If two cities trade, then they can each trade with any number of other cities as long as exactly two of those cities trade to both of them.
I think the thing to do is construct a graph that has all of the dual trades, i.e. the squares, then to add in extra routes the way you describe -- nodes of the same color may not share an edge.
I strongly suspect that the number of nodes with only two edges must be even, before you add in the extra routes.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How many cities does udakk have?
« Reply #9 on: Feb 19th, 2004, 12:48pm » |
Quote Modify
|
As far as I can gather, the following has to be true in our graph:
(trade is irreflexive and symmetric)
[forall]a,b aRb [to] a[ne]b
[forall]a,b a[ne]b aRb [to] bRa
(either one direct path, and no two-step paths)
[forall]a,b (a[ne]b [wedge] aRb) [to] [lnot][exists]e (e[ne]c [wedge] e[ne]d) [to] aReRb
(or no direct path and exactly two two-step paths)
[forall]a,b (a[ne]b [wedge] [lnot] aRb) [to] [exists]c,d c[ne]d [to] aRcRb [wedge] aRdRb [wedge] [lnot][exists]e (e[ne]c [wedge] e[ne]d) [to] aReRb
now with a seven node graph, in a figure of eight, there's no way not to break them..
If you have
a b
c d e
f g
And start with the edges (a,c) (a,d) (b,d) (b,e) (f,c) (f,d) (g,d) (g,e)
Then you can't escape edges (a,e) (f,e) (b,c) (g,c) (they must be directly connected), and so c and e have 4 routes between them, through a, b, f and g, which violates that there are only two allowed..
|
| « Last Edit: Feb 19th, 2004, 1:02pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Guest
Guest
|
|
Re: How many cities does udakk have?
« Reply #10 on: Feb 19th, 2004, 1:08pm » |
Quote Modify
 Remove
|
I think the answer is 16. Instead of trying to draw a graph, I tried binary numbers. Give each point a 4 digit coordinate. The connections are made by either changing a single coordinate or changing all 4 coordinates. I think that guarantees that any two that are connected will have no others in common (since any point with an even sum of all its coordinates will only be connected to points with an odd sum -- and vice versa -- or to a single point that is 2 steps away from each of its connections), and any two that are not connected will have exactly 2 in common. I could be mistaken.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: How many cities does udakk have?
« Reply #11 on: Feb 19th, 2004, 1:13pm » |
Quote Modify
|
After reading your post and looking at my doodling on my desk blotter, I see the flaw in my logic. Back to the drawing board...
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How many cities does udakk have?
« Reply #12 on: Feb 20th, 2004, 3:30am » |
Quote Modify
|
I'm starting to think Udakk can't exist..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Guest
Guest
|
|
Re: How many cities does udakk have?
« Reply #13 on: Feb 20th, 2004, 8:10am » |
Quote Modify
Remove
|
Is there anything wrong with my answer? If you want to draw the map, just draw a hypercube (you do have a supply of 4-dimensional paper handy, don't you?) and add an extra traderoute connecting opposite corners. Udakk doesn't actually have to live in 4D space, but that demonstrates the predominance of squares. The exceptions, the lines connecting opposite corners, are also part of a quadrilateral (for example, 0000, 0001, 1110, 1111). If you want a 3-D map, just label 16 cities in a circle and create the same numbered traderoutes.
|
|
IP Logged |
|
|
|
Guest
Guest
|
|
Re: How many cities does udakk have?
« Reply #14 on: Feb 20th, 2004, 8:18am » |
Quote Modify
Remove
|
If my solution does work, then I'm guessing the next solution would be a 6 dimensional cube. What would the pattern be? There would need to be more connections than simply adjacent corners and the opposite corner.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: How many cities does udakk have?
« Reply #15 on: Feb 20th, 2004, 9:46am » |
Quote Modify
|
Guest,
Your answer does match my answer (tho i am not sure abt my answer). I would try to work out the graph the way you suggest and see if i get it.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How many cities does udakk have?
« Reply #16 on: Feb 21st, 2004, 5:32am » |
Quote Modify
|
The hypercube doesn't work for me.. I keep getting points that are connected to another point with more than two paths of length 2.. Of course it might be that I just keep messing up the drawing..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Guest
Guest
|
|
Re: How many cities does udakk have?
« Reply #17 on: Feb 21st, 2004, 6:56am » |
Quote Modify
Remove
|
Can you give me an example of too many paths?
|
|
IP Logged |
|
|
|
Stuge
Newbie
Posts: 1
|
|
Re: How many cities does udakk have?  udakk.jpg
« Reply #18 on: Feb 21st, 2004, 10:09am » |
Quote Modify
|
Here is my map of the 16 trade routes. Are there any two-step routes too many?
|
|
IP Logged |
 |
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: How many cities does udakk have?
« Reply #19 on: Feb 21st, 2004, 10:11pm » |
Quote Modify
|
Guest,
i think your method works since it gave me the same 16 node graph i had with me.
Now i am trying to prove (or disprove) guest method is correct. (albeit i do understand the arguments he proposed in his last post ,i think we need to put it more rigorously so that the claim settles once and for all).
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: How many cities does udakk have?
« Reply #20 on: Feb 22nd, 2004, 12:11am » |
Quote Modify
|
on Feb 21st, 2004, 10:11pm, TenaliRaman wrote:Guest,
i think your method works since it gave me the same 16 node graph i had with me.
Now i am trying to prove (or disprove) guest method is correct. (albeit i do understand the arguments he proposed in his last post ,i think we need to put it more rigorously so that the claim settles once and for all). |
|
I also think that Guest's solution is correct (amd very, very neat!). Here's a more formal proof:
In Guest’s coding, define the “distance” between two cities to be the number of different bits in their codes. According to Guest’s scheme, two cities are connected, if their distance is 1 or 4; they are not, if their distance is 2 or 3.
Then, the following cases are possible (in what follows, x’ is a negation of x):
1. Two cities with distance 1 are connected, let’s say, A= abcd and B=a’bcd. Every other city connected to A will have a distance of 2 (e.g. ab’cd) or 3 (a’b’c’d’) from B, therefore no city is connected to both A and B.
2. Two cities with distance 4 are connected: A=abcbd and B=a’b’c’d’. Every other city connected to A will have a distance of 3 (e.g. a’bcd) from B.
3. Two cities with distance 2 are not connected, e.g. A=abcd and B=a’b’cd. The only cities connected to both are a’bcd and ab’cd.
4. Two cities with distance 3 are not connected, e.g. A=abcd and B=a’b’c’d. The only cities connected to both are a’b’c’d’ and abcd’.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How many cities does udakk have?
« Reply #21 on: Feb 22nd, 2004, 7:08am » |
Quote Modify
|
on Feb 21st, 2004, 6:56am, Guest wrote:| Can you give me an example of too many paths? |
|
nope.. and I obviously can't draw either 
I was also off on the idea that you could color the nodes with two colors where none of the connected nodes had the same color..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: How many cities does udakk have?
« Reply #22 on: Feb 23rd, 2004, 4:06am » |
Quote Modify
|
dang! Barukh beat me to it! 
anyways good job Barukh  !
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
rmsgrey
Uberpuzzler
 
Gender:
Posts: 2874
|
|
Re: How many cities does udakk have?
« Reply #23 on: Feb 23rd, 2004, 6:25am » |
Quote Modify
|
As an aside, the "distance" used by Barukh (the number of inverted bits) is known as the Hamming Distance, and is important in coding theory for things such as error-correcting codes. The idea behind error-correcting codes is that any two encoded strings are at least a certain Hamming distance, d, apart, so, as long as the number of bits inverted in transmission, e, satisfies e<d/2, taking the closest actual code string to the recieved string will give the transmitted string. For situations where e=d/2, you can tell there's been an error, but not what the original string was (without some further information) and in situations where you can't guarantee e<d/2 but can be reasonably sure of e<d you can detect errors, but not correct them with confidence.
I'm sure there are other applications and if people are interested, searching the net is probably going to turn up more.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: How many cities does udakk have?
« Reply #24 on: Feb 23rd, 2004, 7:11am » |
Quote Modify
|
Hamming Codes is how the error correcting theory starts!!! Interestingly it still makes me wonder though so old lot of newer codes (block, turbo) etc. still use the same concept. Absolutely brilliant research!!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print