EventHorizon
-
Posts
578 -
Joined
-
Last visited
-
Days Won
8
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by EventHorizon
-
-
Spoiler
Distance = Speed * Time
If we let one train's speed be relative to the other, we just need to set the two Speed*Time values equal to each other. Both of which will equal the sum of the lengths of the two trains, but since we don't need to calculate it the number of cars in each train is a red herring.
2T(S-RS) = D = T(S+RS)
2TS(1-R) = TS(1+R)
2(1-R) = (1+R)
2-2R = 1+R
1 = 3R
1/3 = R
The Silver Streak passenger train is moving three times the speed of the other. So the ratio is 3:1.
-
6 hours ago, CaptainEd said:
The use of language is tricky here. The OP begins by saying “one of the dice is a 4”. We understand that to mean “at least one of the dice is a 4”, leading to the answer 2/11.
But later, in Bonanova’s response, a paragraph begins “one of his dice has a particular value”, and continues as if we are speaking of one particular die.
Let’s rephrase the original discussion in terms of two distinct dice: a red die and a white die.
Now Aristotle rolls the dice, and Plato says “the red one is a 4”. What is the probability of a seven total? 1/6.
So if we are speaking of one specific die, the answer does not change : 1/6, and Thalia’s answer is right.
The phrase “in each particular case he [Aristotle] reasons the probability of seven changes to a new value” shows that Aristotle has been swindled.
Thank you, Bonanova, this led me to think about the linguistic difficulties faced by Pascal and Fermat, as they initiated the study of probability.
SpoilerInstead of red and white, you could just use "the die Plato said was a 4" and "the other one."
5 hours ago, CaptainEd said:How did all those 2/11 become Thalia’s answer?
draw a 6x6 table, and tally one in each cell each time Plato asks about another number (11 cells per number). When we are done, all 6 of the diagonal elements (11,22,33,44,55,66,) have one tally each, while all of the off diagonal cells have two tallies. Therefore, Aristotle can’t simply average the 2/11s. Once they have been normalized, we (Thalia, Pascal, Fermat and others) see 36 cases, of which 6 have coordinates adding to 7.
SpoilerFirst, Thalia just says the answer is 1/6 without the extra "i can tell you one die is X", so has nothing to do with 2/11. I assume you mean Aristotle.
But why does there need to be a normalization at all? What went wrong such that it was necessary?
SpoilerOn 6/27/2019 at 2:52 AM, bonanova said:A: Hmm...
So I could have rolled 41 42 43 44 45 46 14 24 34 54 or 64,
all with equal likelihood, with 34 and 43 making seven.
That's a probability of 2/11.It is true that P(11)=P(12)=...=P(66). Each possible dice roll can happen with equal probability.
But once Plato says that "one die is a 4," it doesn't merely prune out the ones without 4's. Using Bayes theorem we can see this.
P(41 | one is 4) = P(one is 4 | 41) * P(41) / P(one is 4)
Obviously P(41) is 1/36. P(one is 4) and P(one is 4 | 41) need an assumption on how Plato decides which value to tell. Assuming he would uniformly random choose a die to report on, we can see P(one is 4)=1/6 since all values are equally likely and P(one is 4 | 41)=1/2 since he has two options randomly chosen from.
P(41 | one is 4) = (1/2) * (1/36) / (1/6) = 1/12
This is the same for 42,43,45,46,14,24,34,54,64.
But since 44 only has one value possible to report, the value is different.
P(44 | one is 4) = 1 * (1/36) / (1/6) = 1/6. So given that one is a 4, the roll 44 is twice as likely as the other 10 possibilities.
To finish finding the answer...
P(sum is 7 | one is 4) = P(34 | one is 4) + P(43 | one is 4) = 1/12 + 1/12 = 1/6.
Of course, if Plato always decides to tell the smaller value shown on the dice or anything other than uniformly random, the probability distribution could be wildly different.
-
Spoiler
L=0 (since E-E=L)
N=1 (since the largest two three-digit numbers can sum to is 1998)
A+O = 10 + I (A+O need to have a carry of 1 to make the 4 digit number)
O+1=E
W+E=11 (since N is 1, W+E would be too much so we need to borrow from the next)
2*T = I + 9 (since we borrowed above and the 1000's place has a 1), also I is odd.
O+1=E and W+E=11 => W+O=10
A+O = (W+O) + I => A=W+I
Since I is odd and the smallest W could be is 2, I is at most 7, but could be 5 or 3, too.
Assume I = 7. 2T=9+7 = 16, so T=8. A=W+I => A=W+7, so A=9 and W=2. 10=W+O => 10=2+O => O=8, same as T.
Assume I=5. T=(9+5)/2=7
---> Assume A=9. 9=W+5 => W=4. 10=4+O => O=6. E=6+1=7, same as T
---> Assume A=8. 8=W+5 => W=3. 10=3+O => O=7, same as T
---> A can't be 7 (T is), and W needs to be at least 2 (0 and 1 are taken), so done here.
Assume I=3. T=(9+3)/2=6
---> A can't be 9, it would make W = 6, same as T. A can't be 6, it would make W=I. A can be 8,7,or 5.
---> Assume A=8. 8=W+3 => W=5. 10=5+O => O=5, same as W
---> Assume A=7. 7=W+3 => W=4. 10=4+O => O=6, same as T
---> Assume A=5. 5=W+3 => W=2. 10=2+O => O=8. E=8+1=9. Looks like this is the only solution.
So L=0, N=1, W=2, I=3, A=5, T=6, O=8, E=9.
NINE-TEN=TWO => 1319-691=628
NINE-ONE=ALL => 1319-819=500
-
n factorial (represented as n!) is the product of all positive integers up to n.
So the number you are looking for is 1,000,000! ("one million factorial")
Spoiler12! will fit in a 32 bit integer. 20! can fit in a 64 bit integer. 69! can still be represented by a scientific calculator with 2-digit decimal exponents.
A quick estimate of the number of digits would be on the order of 6,000,000. (I simply took 1,000,000. Saw it would add 6 digits to any number it is multiplied to. 1,000,000^1,000,000 would have 6,000,000 zeroes plus the leading one. 1,000,000 factorial would obviously have less digits than this.) So a file holding the exact decimal expansion in ascii would be around a 6 megabyte file.
I was thinking I would try to estimate the answer using sterling's approximation.
I thought about determining the number of trailing 0's by figuring out the number of factors of 5 it would have. (not too hard... floor(1,000,000/5) + floor(1,000,000/25) + floor(1,000,000/5^3) + ..., which would end up slightly less than 1,000,000/4 since 1/5 + 1/5^2 + 1/5^3 + ... = 1/4. yay for sums of geometric series
)
I thought maybe I'd post the answer as an exponential (e.g., e^some number or 10^some number). This would make it easy as you could simply take the log (base e or 10) of each number up to 1,000,000 then add them all up. 1,000,000! would then be whatever base you chose to the power of the sum. One advantage to using a base 10 logarithm would be that the integer part of the sum of the base 10 logs would be one less than the number of digits in the factorial. The fractional part could then be used to try to figure out the leading digits of the answer (just take 10^(fractional part)).
I thought about posting c++ code to calculate it precisely. I'd have an ever enlarging array of integers and have the multiplies cascade along it with overflows from the previous array entry. (I could still do this if you were supremely interested)
So to start, I decided to look up stirling's approximation on wikipedia's "factorial" page (which is where I took the above info on what factorials will fit in what representations). The section just below sterling's approximation talked about computation of factorials. So I thought I'd take a look for any hints for my code. There it said wolfram alpha will calculate it up to 20,000,000. So since I'm lazy, here's the answer from wolfram alpha.
https://www.wolframalpha.com/input/?i=1,000,000!
8.26393168833124006237664610317266629113534797896387304516777588556337961103564508444653051131146397335160680421087858854146474695064783618230121097542329959011564174624917379888389269193414176545783239319872802472198939... × 10^5565708
So it is a 5565709 digit number. They also give the number of trailing zeroes as 249998.
-
1
-
-
I'm sure I know what BMAD was saying. Yes, ignore the units / squared units difference. The problem doesn't involve a circle though. You need to find a function f(x) such that the area under the curve between two points is the same as the arc length between those two points along the function. Here the arc length is like the length of a string representing the function cut at the two points.
How to find the arc length of a function:
SpoilerIf the function was a straight line, you could use the Pythagorean theorem to find it.
sqrt( (y2-y1)^2 + (x2-x1)^2 )
If you assume the arc length was a straight line, and slowly bring the points on the function closer together, eventually you get the change in y approaching the slope of the line times the difference in x's.
The arc length for that infinitesimally small section is then sqrt( ( f'(x)dx )^2 + dx^2 ) = sqrt( dx^2 * (f'(x)^2 + 1 ) = sqrt( f'(x)^2 + 1 ) dx. Where f'(x) is the derivative of f(x).
Integrate that between two points to get the arc length between those two points.
Example: f(x)=2x
f'(x) = 2
integrate( sqrt( 2^2 + 1 ) dx ) = integrate( sqrt(5) dx) = x*sqrt(5) + c
If you evaluate the integral between 0 and 1 you end up with arc length = sqrt(5). Which is the same as if you just used the Pythagorean theorem. Yeah, I'm too lazy right now to find a function that ends up with a nice arc length function that isn't just a straight line.
Restatement of problem using previous spoiler:
SpoilerFind a function f(x) such that F(x) = integrate( sqrt( f'(x)^2 + 1) ), where F(x) is the indefinite integral of f(x) and f'(x) is the derivative of f(x).
One step further:
SpoilerTaking the derivative of both sides gives
f(x) = sqrt( f'(x)^2 + 1)
One answer is simple, the other is less so.
-
Spoiler
Let granny's age be 'a' and grandpa's be 'b'.
If only one of a and b were odd, the difference of their squares would be odd since squaring doesn't change even/odd. So either both a and b are even, or they are both odd. This means a-b is even. This also means the a+b is even.
The prime factorization of 1988 is 2,2,7,71.
1988= a^2 - b^2 = (a-b)(a+b)
So the prime factors of 1988 must be partitioned into the factors (a-b) and (a+b)
Since both are even, a 2 must be put into both factors.
7 and 71 cannot both be put into (a+b), the obviously bigger factor, or the sum of their ages would be 1988/2 = 994. Aside from being too large for human ages, that would leave (a-b)=2... and granny wouldn't be "quite a bit older than" grandpa.
(a-b)=2*7=14
(a+b)=2*71=142
Solving the system of equations gives...
a+b=142
a-b=14 => a=14+b
(14+b)+b=142
14+2b=142
2b=128
b=64
a=14+(64)
a=78So granny is 78 years old and grandpa is 64.
-
18 hours ago, BMAD said:
Hmmmm, my answer was the reciprocal of yours. Maybe I am wrong. Can you support your answer?
A quick check:
SpoilerThe second biggest term in the denominator is n^(n-1). (n^(n-1))/ (n^n) = 1/n, so as n approaches infinity the second biggest term in the denominator is negligible compared to the biggest. So are all the other terms in the denominator. Since the biggest term in the denominator is the same as the one in the numerator (and since there are no negative terms in either), the limit won't end up being less than 1.
The whole #!:
SpoilerAs shown above, the only term that matters in the denominator is n^n.
Dividing all terms in the numerator by this makes it a sum of values that look like
((n-1)^n)/(n^n) = ((n-1)/n)^n.
Replacing the 1 with -a yields
((n+a)^n)/(n^n) = ((n+a)/n)^n = (1+a/n)^n.
Now, take the limit of this as n approaches infinity...
y = lim (1+a/n)^n
ln y = lim (n * ln(1+a/n))
ln y = lim (ln(1+a/n) / n^-1 )
As n approaches infinity, top and bottom approach 0... L'Hopitals!
ln y = lim (1/ (1+a/n)) * (-a/n^2) / (-n^-2)
ln y = lim (1/ (1+a/n)) * a
ln y = (1/(1+0)) * a
ln y = a
y = e^a
So ((n+a)^n) / n^n approaches e^a in the limit.
Listing the terms in the numerator in decreasing size is
n^n + (n-1)^n + (n-2)^n + ...
Dividing by the only term in the denominator that matters gives
1 + ((n-1)^n)/n^n + ((n-2)^n)/n^n + ...
Using the limit we found and substituting the values in for a gives
1 + e^-1 + e^-2 + ...
A geometric series with ratio 1/e.
The sum of this is then 1/(1-(1/e)) = 1/((e-1)/e) = e/(e-1).
-
Spoiler
e/(e-1)
That is an interesting limit :-)
-
Spoiler
.5*sqrt(2) + .5*sqrt(2)*i or -.5*sqrt(2) - .5*sqrt(2)*i
An interesting thing I was shown was that, if you look at the complex plane, multiplying two complex numbers results in adding the angles and multiplying the magnitudes of the vectors representing the complex numbers being multiplied.
This makes finding an nth root of complex numbers fairly simple. Simply take the nth root of the magnitude, and divide the angle by n. Then you just calculate the real and imaginary parts from the resulting vector using sine and cosine. Finding all the other values for the nth roots is done by simply adding 2pi/n repeatedly to the angle of any found nth roots.
-
Spoiler
Add the odd digits... so the solutions are all '7.'
-
1
-
-
I looked at that for a while. Though it's not much, here's what I got...
Spoiler8^2 = 64 = 6 *(10) +4
9^2 = 81 = 1*(100) -2*(10) +1
10^2 = 100 = 1*(100)
11^2 = 121 = 1*(100) + 2*(10) + 1
? = 12^2 = 144 = 1*(100) + 4*(10) + 4
So I'd guess D. D also is connect diagonally like all the others.
But, I have no idea what the vertical position would mean, nor why 81 would be represented using a white token instead of simply going with an 8 and a 1.
I'm also not sure why the board/grid looks like it does, with that bar at the top.
-
On 1/28/2018 at 2:25 AM, bonanova said:
Prove that any n-diamond tiling of the hexagon will use the three types in equal numbers.
This puzzle is not quite solved yet. So here's my attempt
SpoilerLet e be the number of triangles along one edge of the hexagon.
Now slice the hexagon into layers horizontally at each spot you can without cutting through triangles. Starting at the bottom layer (layer number 1), we have something like V^V^V^V^V. Two of the orientations for diamonds can fit wholly into this layer, while the third (blue in the image given) cannot. This diamond must connect layers, while the others cannot.
In this bottom layer there are e triangles pointing up and e+1 pointing down,. Since the two non-blue diamonds must reside wholly in a given layer and use 1 each of triangles pointing up and pointing down, exactly one blue diamond must be used to take care of the extra triangle pointing down.
The next layer up (layer 2) will look like the previous one, but will have one more triangle pointing up (e+1) and one more pointing down (e+2). Since one triangle pointing up will be used by the blue triangle connecting this layer to the one below, there are two extra triangles pointing down that cannot be used by non-blue diamonds. So this layer will need two blue diamonds to connect it to the third layer and use those extra two triangles that point down.
To connect layer 1 to layer 2 you need exactly 1 blue diamond. To connect layer 2 to layer 3, you need exactly 2 blue diamond tiles. To connect layer x to layer x+1 you need x blue diamond tiles for x up to x=e.
Using symmetry, the top layers need the same number of blue diamond tiles that the bottom layers needed to connect. The number of blue tiles needed per layer connection looks like 1,2,3,..,e-1,e,e-1,...,3,2,1.
So the number of blue diamond tiles needed for a hexagon with edge length e is 1+2+...+(e-1)+e+(e-1)+...+2+1 = 2*(1+2+...+(e-1))+e = 2*(e*(e-1)/2) + e = e*(e-1)+e = e^2.
Now by symmetry you can instead cut the layers using either of the other two directions and find the number of each of the other two tiles must also equal e^2 by the same logic.
-
Alice is so kinky...
SpoilerAs ThunderCloud noted:
On 3/17/2018 at 4:31 PM, ThunderCloud said:P(1) is the sum of the coefficients
So that is my first guess. This lets me know a range that all a_i are in. They can be from 0 to P(1) since all a_i are non-negative and their sum is P(1).
My second guess is the next higher power of 10 greater than P(1). From this I can get every a_i since they will essentially all be listed in the response.
For example, lets say P(x) = 4 + 19*x + 23423433*x^2. P(1) is 4+19+23423433=23423456. The next higher power of 10 is 100000000. P(100000000) = 4 + 19 * 100000000 + 23423433*100000000^2 = 234234330000001900000004. You just need to split the response into groups of digits equal to the number of 0's in the power of 10 guessed, then read off the values. e.g., (23423433)(00000019)(00000004)
So my number of guesses as a function of n is G(n) = 2.
The only thing this won't find is if Alice is keeping a few trailing 0's secret. If a_n = 0, the polynomial is identical the polynomial of one lesser degree and no amount of guesses will find how many trailing coefficients are 0.
-
Proof for (3)
Spoilern cuts result in a maximum of 1+.5*n*(n+1) pieces.
Case 1: n is odd and greater than 2.
Since n is odd, n+1 is even and .5*(n+1) is an integer. So the number of pieces is 1+n*(some integer). The remainder by dividing this by n is clearly 1 since the number of pieces is one more than a multiple of n.
Case 2: n is even and greater than 2.
The number of pieces is 1+(n/2)*(n+1). n is even, so n+1 is odd. (n/2) times an odd number greater than 2 results in n/2 more than a multiple of n. Adding the 1 from the formula makes the number of parts 1+(n/2) plus a multiple of n. Since n is greater than 2, 1+(n/2) is less than n. So the remainder when dividing by n is 1+(n/2).
Since if n>2 there will always be a remainder of either 1 or 1+(n/2), There is no number of cuts greater than 2 that will produce a maximum number of pieces that is evenly divided by the number of cuts.
-
I installed the plus4 app, and it is just a mastermind clone.
+x means you have x numbers in the right spot, and -x means you have x numbers right, but they are in the wrong spots. It could be that a guess would result in +2-2, meaning that you have all the right numbers, but two are in the wrong spots.
Spoiler6437 +1
From this we can see that exactly one of these numbers is correct, and also happens to be in the right position. Looking at the column that 6 is in, you can find another guess with 6 in the first position, so 6 cannot be in the answer. Similarly with 4. So either 3 is in the 3rd position or 7 is in the last position.
1875 -2 and 6872 -2
Since we know 6 is not in the answer, and switching it to 1 doesn't change the result... we know 1 is also not in the answer.
1479 -2
We know 1 and 4 are not in the answer, so 7 and 9 must be. Since we determined only one of 3 and 7 were going to be in the answer, 3 is not in the answer. Also, 7 is in the last position due to 6437 resulting in +1. So the answer known so far is XXX7, which includes a 9 somewhere.
1875 -2 and 3285 -2
Since we know 1 is not in the answer and 7 is, exactly one of 8 or 5 is in the answer. Looking at the second line I listed here, since 3 is not in the answer and only one of 8 and 5 is, 2 must be in the answer. So the answer known so far is XXX7, including a 2 and 9 and one of 8 or 5.
Looking at the columns that 2 appears in, you'll notice that it has been guessed in each column except the third, and has always been in the wrong position. So it must be in the third spot. So the answer so far is XX27, including a 9 and one of 8 or 5.
2048 -2
We know 0 and 4 are not in the answer since the answer is some permutation of 297 and 8 or 5. This means 8 must be in the answer. So the answer is either 9827 or 8927.
1875 -2
Since 8 is in the wrong position in this guess, the answer must be 8927.
So if you happened to keep the game on and check back to brainden hoping to find an answer, you can enter 8927 and win
-
1
1
01 can vacate bottom left square
1
01
01
11
001
01
11
011
001 can vacate immediate neighbors of bottom left square
01
101
011
001
011
1001
011
001
011
1011
0101
001
011
1111
0011
001 can vacate 2x2 area
It may be easier with my other formulation of the problem.
I'll try and vacate
0
00
00
1
1
01
1
02
001
12
002
001
1
03
002
001 notice the 2 and the 3...
12
013
0011
001 notice that the 2 and the 3 swapped relative positions...
01
113
0112
0011
001 the 2 and the 3 swapped again. They'll continue to swap, and will never finish.
So it isn't possible to vacate that area.
So the best you can do is
00
00
or
0
0
...
0
0
000...00
1
1
01
1
01
01
11
001
01
11
011
001
01
101
011
001
11
011
011
001
111
0101
011
001
111
0111
0101
001
111
0111
0111
0001
001
1101
0111
0111
0001
011
1011
0111
0111
0001
111
0111
0111
0111
0001
1111
01101
0111
0111
0001
1111
01111
01101
0111
0001
1111
01111
01111
01101
0001
1111
01111
01111
01111
00001
etc.
-
...
fourth move
1 1 1
0 1 1 1
0 0 0 1
fifth move
1 1 1
0 0 0 1
0 1 1 1
0 0 0 1
...
From step 4 to step 5 the bottom two rows are identical, so you are saying you go from
111
to
111
0001
which should be
111
0111
Handy rule of thumb: Since each move (your moves are actually series of moves) adds one amoeba, check the number of amobae that split and make sure that the total number of amoebae before and after differ by this number.
-
Looks like I misunderstood the initial configuration.
I assumed the x's were already amoeba and not just space to vacate.
Still not solvable...
1
1
01
1
02
001
1
03
003
0001
Still need to vacate
3
03
Which I showed was not possible
-
The first thing this reminded me of was the tower of hanoi puzzle. Simple moves, but a huge number of them.
There is a finite number of moves that will solve this, and even though the sequence of moves may differ the end configuration of all optimal (min moves) solutions will be the same.
There will only ever be 3 amoebae in the first column and only 3 in the first row.
The puzzle can be changed as follows and keep ending configurations and number of required moves the same (just the sequence of moves is altered):
Allow multiple amoebae in each square.
Allow any amoeba to split and add 1 amoeba to the right and above.
End configuration cannot have more than 1 amoeba in each square.
One amoeba and need to vacate it's spot.
1
1
01
Now if we continue and say vacate those spots...
1
01
01
1
02
001
11
011
001
Three amoebae.
1
11
+1 move
2
02
+4 moves
2
04
002
+3+2
1
14
014
0011
+6
13
116
0113
0011
+5+4
02
117
1117
01112
00110
+12+2
0,1
0,1,7,
1,1,1,12
1,1,1,1,7
0,1,1,1,1,1
0,0,1,1,0,0
Example 2 is not looking good. Perhaps it is unsolvable....
Proof no solution exists (for example 2 and therefore for the original problem)
From example 2, after 10 moves we get:
1
14
014
0011
This can be seen as
1
11
011
0011
added to (with shifted position... which doesn't affect number of moves)
3
03
which still needs to vacate their spots.
Assume it takes a finite number of moves, N, to accomplish the needed evacuation and 'flattening' for that second piece. Lets see what happens when we try...
+6 moves
3
06
003
+4+5 moves
2
17
017
0012
This configuration can be thought of as
2
14
014
0012
added to a shifted
3
03
Since the second piece is the original configuration we were trying to flatten, the number of needed moves must be 15 moves + N moves + more to flatten from here. But since we said it was only going to take the N moves and N < 15+N+ another positive number, N cannot be finite.
So it is not possible to evacuate and 'flatten' from the
3
03
configuration.
-
Yay for integer sequences (found using your 19355
)...A002829 - Number of trivalent (or cubic) labeled graphs with 2n nodes.
1, 0, 1, 70, 19355, 11180820, 11555272575, 19506631814670, 50262958713792825, 187747837889699887800, 976273961160363172131825, 6840300875426184026353242750, 62870315446244013091262178375075
A004109 - Number of connected trivalent (or cubic) labeled graphs with 2n nodes.
0, 1, 70, 19320, 11166120, 11543439600, 19491385914000, 50233275604512000, 187663723374359232000, 975937986889287117696000, 6838461558851342749449120000, 62856853767402275979616458240000
A014378 - Number of connected regular graphs of degree 8 with n nodes.
1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 6, 94, 10786, 3459386, 1470293676, 733351105935
If someone can prove that being connected is sufficient to be able to create the cycle with 8-regular graphs, the last integer sequence would contain N... if it went further than 16 nodes/letters...
The factor from one number to the next is:
6
15.6666666
114.7446
320.729
425.015790663
498.778657561
Assuming 500 for each additional letter added beyond 16 gives the estimate of
733351105935 * 50010 = 7.161631894e38
And this should be underestimating it.
For overestimating, we can assume the factor will increase by at least 75 for each letter added (it's clearly increasing at a decreasing rate):
733351105935*575*650*725*800*875*950*1025*1100*1175*1250 = 2.188352274e41
That's a much smaller range than before, but it does require the connected=cycle assumption. The upper bound is still an upper bound without the assumption since you definitely need the graph connected for a cycle to exist.
Ooops. Just noticed that the list is unlabeled nodes, so the number is actually larger.
Set one random edge. There needs to be one, so start anywhere.
Choose one of the nodes attached to this edge. It cannot connect back to the first again with its other edge, so it connects to a third node.
This third node cannot be connected to the previous node with both its edges. If there are more nodes, it cannot attach to the other node from the first edge, as it would mean the graph is not connected.
Proceed this way until all nodes have been added, and the last node connects to the other node from the first edge to finish one big loop.
Since the graph is simply one big loop, there is a cycle.
Time to look at 3-regular graphs... which aren't as simple and quite possibly don't have this property.
Almost all regular graphs are hamiltonian.
Abstract: In a previous article the authors showed that almost all labelled cubic graphs are hamiltonian. In the present article, this result is used to show that almost all r-regular graphs are hamiltonian for any fixed r ⩾ 3, by an analysis of the distribution of 1-factors in random regular graphs. Moreover, almost all such graphs are r-edge-colorable if they have an even number of vertices. Similarly, almost all r-regular bipartite graphs are hamiltonian and r-edge-colorable for fixed r ⩾ 3.
So it looks like we basically just need to find how many 8-regular graphs there are with 26 labeled vertices. It'll be off by a little, but will be a good estimate for N.
-
Other than the organized adjacencies?
Is there an arrangement the "cube" can't cover?
Took me a bit to figure out what phil did. He took all the possibilities and divided by all the orientations of the "cube". 6 faces * 4 rotations * 2 for mirroring. I think this leaves out a shifting position divisor. Can you take a cube arrangement and shift a letter from a center position to an adjacent square and retain adjacencies for all the letters? If so then how many shifts? Off the hip guess would be 3 unless which diagonal set is being shifted into matters. (Center, center edge and diagonal)
So N ?= 26!/(6*4*2*3) for unique possibilities?
I can't think of another way to alter the cube that would retain adjacencies but wouldn't be part of the (6*4*2*3).
a - cdefghij
b - cdefghik
c - abdefghi
d - abcefghi
e - abcdfghi
f - abcdeghi
g - abcdefhi
h - abcdefgi
i - abcdefgh
j - almnzyxw
k - lmnobzyx
l - mnopkjzy
m - nopqlkjz
n - opqrmlkj
o - pqrsnmlk
p - qrstonml
q - rstuponm
r - stuvqpon
s - tuvwrqpo
t - uvwxsrqp
u - vwxytsrq
v - wxyzutsr
w - xyzjvuts
x - yzjkwvut
y - zjklxwvu
z - jklmyxwv
Example cycle: acdefghibklmnopqrstuvwxyzj
Description of above: a through i are all connected to each other, except a is not adjacent to b. Instead of a adjacent to b, a is connected to j and b is connected to k. j through z are in a loop and are adjacent to the ones 4 in front and 4 behind themselves, except j is not adjacent to k to allow the connections to a and b. This means that any cycle found must include "ja" followed by any combination of c through i followed by "bk", or that but reversed. The cube model has no way to represent that the cycle is required to use the connections "aj" and "bk". The cube also cannot have 9 letters all adjacent to each other (except for the 1 missing connection "ab" to allow for a cycle).
-
26!/(6*8) = N, i would think.
as to how to generate all of them evenly, no idea.
N is not going to be that simple to calculate. Any given adjacency you find could have multiple possible cycles that could be found within it (So it may incorrectly be counted multiple times). Adjacencies don't need to be as neatly organized as curr3nt's answer was.
Choose a random ordering with a as the first letter (since there's going to be a cycle anyway). There are 25! of them.
Since the graph is commutative the cycle can go in either direction. 25!/2.
For the rest of the adjacencies, pick 3 numbers between 2 and 12 inclusive for the amount to jump with respect to the cycle (one forward that many steps and one back that many steps for each number picked (to preserve commutativity)). (25!/2) * (12 choose 3) = (25! * 110)
Since each of these has a cycle right in the middle of the others and very neatly ordered, these are not repeated in the count (I think...).
So N > 25! * 110.
Each adjacency list can be treated as 26*8/2 = 104 1's in a lower triangular 26x26 matrix. This means N must be less than (26*(26-1))/2 choose 104 = 1.43e87.
We can easily limit this a little by enforcing exactly 8 x's in the first column.
(25 choose 8) * (25*(25-1)/2 choose 96) = (25 choose 8) * (300 choose 96) = 1081575 * 2.33e80 = 2.52e86
So a crude range for N is...
25! * 110 = 1.706e27 < N < 2.52e86 = (25 choose 8) * (300 choose 96).
A slightly smaller upper bound would be found noticing that after the first 8 are chosen from the first column, there is still an xth letter without any adjacencies set so far. If you then choose 8 for it's adjacencies, it leaves another in the same situation. And once more for the last time you can be sure (since 25-8-8-8=1).
(Edit: Forgot to include the letter itself, so only 3 times...)
N < (25 choose 8) * (24 choose 8) * (23 choose 8) * (22 choose 8) * ((22*(22-1)/2) choose (104-32))
N < 1081575 * 753471 * 490314 * 319770 * (231 choose 72)
N < 1081575 * 753471 * 490314 * 319770 * 9.933e60
N < 1.27e84
If you assume you'll always have 8 more to choose for each letter (an overestimation) you can get the following...
N < Product of i=8 to 25 of (i choose 8)
= 25! * 24! * 23! * 22! * 21! * 20! * 19! * 18! / (8!18 * 7! * 6! * 5! * 4! * 3! * 2!)
= 2.72e69
1.706e27 < N < 2.72e69
Yeah, still a huge range...
1. Randomly pick 8 letters to be adjacent to each letter.
2. Check for commutativity. If not, redo step 1.
3. Check that a cycle of all 26 letters exists. If not, redo step 1.
Now, someone find a way without a large amount of resampling... :-/
-
I think the bit debt idea will always have situations that produce contradictions, so I'm thinking it should be discarded.
I looked over plainglazed's 38, and I think it works. Nice.
Edit: I got another 38. It's slightly more complicated (1 more branch needed), but is based on yours, so I won't bother posting it. It uses 6of8's and 5of8's in combinations instead of groups of 5's in a bigger group of 20.
-
sorry for the delayed response, EH. checked out your post briefly earlier and again just now tho have still not been able to study it in depth. an interesting approach. have highlighted my initial hangup in the quote below. am no doubt a little slow and will continue to ponder but for now am indeed having a hard time following the logic.
I didn't really explain it too well. Here's a (hopefully) better attempt to show that with 3 bits of information, you can get 4 of the next 5 cards right and still end up with 2 bits after
First, I'll simply enumerate all the possibilities and what bits they will produce
ccccc - 0000
cccc1 - 0001
cccc2 - 0010
cccc3 - 0011
ccc1c - 0100
ccc2c - 0101
ccc3c - 0110
cc1cc - 0111 <----the "stray outcome" grouped with the ones above that all have the missed card 4th, 5th, or all correct.
cc2cc - 1000
cc3cc - 1001
c1ccc - 1010
c2ccc - 1011
c3ccc - 1100
1cccc - 1101
2cccc - 1110
3cccc - 1111
where c means correctly guessed, 1 means suit value guessed was 1 higher (mod 4), etc.
Notice that after 3 cards, we can know if the first bit to be produced is a 1 or a 0. So this can be used to guess the fourth card. This is what I meant by "So depending on which group I end up in after those 3 cards, I got another bit of information." In the case of a card missed in the first 3, you actually know all 4 bits of the information produced since only 1 card is going to be missed.
After I see what the fourth card is, assuming none of the first 3 were missed, the possibilities are the following:
ccccc - 0000
cccc1 - 0001
cccc2 - 0010
cccc3 - 0011
ccc1c - 0100
ccc2c - 0101
ccc3c - 0110
(cc1cc - 0111 <-- the stray outcome to complete the two groups of 4.)
Notice that if the fourth card was not missed, the second bit is 0. If the fourth card was missed, the second bit is 1. So we can use this bit to guess the fifth card.
So the possible outcomes were grouped in two groups of 8 to let me know the first bit.... this is because all the outcomes in each group produce the same first bit.
Once grouped into 4s, they all produce the same second bit.
After the fifth card is seen, we know exactly what bits of information were produced, and can leave the last two bits to be used by later cards.
A couple examples
I'll use the orientation on the card to be the left bit, and the other bit of information used is the right.
Next 5 cards: 23013
Bits going out needs to be 10
Next 5 cards in binary: (10)(11)(00)(01)(11)
The fifth card requires a 1 as the right bit, so the second bit produced must be a 1.
The fourth card requires a 1 as the right bit, so the first bit produced must be a 1.
So the bitstring that needs to be produced by these 5 cards is 1110. From the explanation, that means the outcome must be 2cccc.
Orientations: (0)1001 <---with the missed card marked in parenthesis
Determined by the left bit of each (except needing to guess 00 on the first card to miss it by 2 (mod 4))
Bits coming in then must be: (0)10
...Handing the deck over to the guesser...
010 are the bits of information the guesser has once he gets to the group of 5 cards in question.
The first card's orientation is 0. Taking this as the left bit and the 0 from the built up information, means the guesser guesses 0. The card is 2. Outcome = missed by 2 (mod 4).
The second card's orientation is 1. The second bit of information is 1. The guesser guesses 3. The card is 3. Correctly guessed.
The third card's orientation is 0. The last available bit of information is 0. This means the guesser guesses 0. The card is 0. Correctly guessed.
The guesser looks at his page of notes and sees 2cccc, the only outcome with 2cc at the beginning, and knows the bits of information produced are 1110.
The fourth card's orientation is 0. The next bit of information is a 1. The guesser guesses 1 and the card is a 1. Correctly guessed.
The fifth card's orientation is 1. The next bit of information is 1. The guesser guesses 3 and the card is a 3. Correctly guessed.
This leaves 4 correct guessed out of this group of 5 with the bits 10 extra for the next group of cards.
Next 5 cards: 23013
Bits going out needs to be 10
Next 5 cards in binary: (10)(11)(00)(10)(11)
The fifth card requires a 1 as the right bit, so the second bit produced must be a 1.
The fourth card requires a 0 as the right bit, so the first bit produced must be a 0.
So the bitstring that needs to be produced by these 5 cards is 0110. From the explanation, that means the outcome must be ccc3c.
However, this means the fourth card needs to be missed and a 2+3 (mod 4) = 1 must be guessed.
doh...
Example 2 shows that this method does not work as I thought it did, since I reached a contradiction. So back to the drawing board... hopefully something from this can be salvaged.
I think it may still work, but that I can't 'borrow' quite as many bits as I thought. I think there needs to be a 1 bit buffer at all times. Hopefully that solves the issue, but I'll need to look into it.
Probability 101
in New Logic/Math Puzzles
Posted · Edited by EventHorizon
Addendum added
The part you turned red follows directly from the assumption preceding it. Perhaps I didn't make this point explicit enough in my post. P(sum is 7)=1/6, but P(sum is 7 | rolled an N) is dependent upon how the information "rolled an N" is determined and the probability distribution can vary wildly based on it.
I assumed a method that left P(sum is 7 | rolled an N) = 1/6, but as your example shows it is not necessarily the case.
Another example, Lets say Plato always reported the smallest even number rolled, or just the smallest number if no evens are rolled. It is easy to see that P(sum is 7 | rolled a 1) = P(sum is 7 | rolled a 3) = P(sum is 7 | rolled a 5) = 0 because if the other die is the even number necessary to make 7, it would have been reported instead.
I guess what I'm trying to say is that P(sum is 7 | rolled an N) says as much or more about the information "rolled an N" than the probability the dice sum to 7.
To liken it to the Monty Hall problem, the best action depends upon Monty himself. If he would have always opened a door you didn't pick (which doesn't have the prize) and lets you switch, you should switch. If he only makes it seem like he'd always have opened a door without the prize and given you a chance to switch, but simply opens the door you picked if you had picked wrong... you should stay. The problem is, you don't know what is in Monty's head.
addendum:
I didn't come up with this myself. Monty Hall was asked about the Monty Hall problem, and his response was such.