Author |
Topic: Equilateral Triangle (Read 1585 times) |
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
 |
Equilateral Triangle
« on: Dec 4th, 2005, 11:59am » |
 Quote  Modify
|
In how many ways can three vertices of an n-dimensional cube be chosen so that the chosen vertices form an equilateral triangle?
|
|
 IP Logged |
Regards,
Michael Dagg
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Equilateral Triangle
« Reply #1 on: Dec 5th, 2005, 11:19am » |
Quote Modify
|
IMHO this is related to Hamming distances. 3 vertices on n-dimensional cube form an equilateral triangle if their corresponding 0-1 encodings have the same mutual Hamming distance. For instance, the following 3 vertices in 4-dimensional space: 0000, 0011, 0101.
I wonder why this question was placed in General section?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Equilateral Triangle
« Reply #2 on: Aug 17th, 2006, 12:28pm » |
Quote Modify
|
Nearly forgot about this one!
If x,y,z are in {0,1}n, let A be the set of bits where x,y differ, and let B the set where x,z differ. Then y,z differ in the symmetric difference of A and B, which has cardinality
|A\B|+|B\A| = |A| + |B| - 2|A n B|.
The points x,y,z form an equilateral triangle iff
|A| = |B| = |A|+|B| - 2|A n B|,
so that |A| = |B| = 2|A n B| = 2k, say, is even.
The first point, x, can be picked in 2n ways. Then we pick subset A in (nC2k) ways, and this determines y. Finally, we pick B by specifying AnB, in (2kCk) ways, and B\A, in (n-2kCk) ways, and this determines z. Now we've counted each triple 3! times, so divide by 6. Thus the number of equilateral triangles of side length sqrt(2k) is
2n (nC2k) (2kCk) (n-2kCk)/6 = 2nn!/[6(n-3k)!k!3].
The total number of triangles is the sum over all k > 0 (note the above is 0 if 3k > n).
The sequence starts
0, 0, 8, 64, 320, 2240, 17920, 121856, 831488, 6215680,
and doesn't seem to be in Sloane.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print