EventHorizon
-
Posts
578 -
Joined
-
Last visited
-
Days Won
8
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by EventHorizon
-
-
On 3/24/2024 at 8:40 AM, witzar said:
My intention was to define repetition (Devil's win) as a repeated state of the lanterns and a repeated position of Devil and Angel, but looks like I failed to do it properly. My apologies.
SpoilerIt is interesting that the angel still wins even with a much more favorable definition of state for the devil than was intended (just the lantern configuration looking forward from the pair's position).
The strategy given for the angel to win with the intended definition of a state doesn't work when applied to the other (e.g., 1001010101 -> 0101010101 first two get flipped then march through a bunch of repeated states). So there's still some things to uncover about this, but it's an interesting problem with either definition. Good job Evilhubert.
-
1 hour ago, phil1882 said:
actually this seems pretty straight forward to me, the angel simply turns off all lit lanterns and wins.
SpoilerHere's the last example from above, but with the angel turning off the first lantern it sees lit.
111110 D 1->1
111101 D 1->1
111011 D 1->1 ***(state that is repeated)
110111 D 1->0
101110 D 1->1
011101 A 0->1 Angel turns off this lantern.
111011 *** A state is repeated. Angel loses. -
Was there an easier method?
SpoilerFor all non-square convex quadrilaterals, area < 1/16 * perimeter^2
Case 1: Not all side lengths are equal
Let a convex quadrilateral (Q1) consist of side lengths s1, s2, s3,and s4, where s1 is consecutive to s2, s2 to s3, s3 to s4, and s4 to s1. Since the quadrilateral is convex, the diagonals cross inside the shape. Let s1≠s2.
Split the quadrilateral into two triangles consisting of sides lengths s1, s2, and d (length of the diagonal) for the first triangle (T1A) and s3, s4, and d for other triangle (T2A).
Construct a new triangle, T1B, with side lengths (s1+s2)/2, (s1+s2)/2, and d. By Lemma 2 and since s1≠s2, the area of T1A is less than the area of T1B.
Similarly, construct triangle T2B with side lengths (s3+s4)/2, (s3+s4)/2, and d. By Lemma 2, the area of T2A is less than or equal to the area of T2B.
Connect T1B and T2B along the side of length d to create quadrilateral Q2. Q2 has the same perimeter as Q1, and the area of Q2 is greater than the area of Q1.
Now split Q2 along the diagonal which is not the diagonal shared by T1B and T2B. Let the length of this diagonal be d2.
This will create triangle T3A with side lengths (s1+s2)/2, (s3+s4)/2, and d2 and triangle T4A with the same side lengths.
Construct T3B, T4B, and ultimately Q3 by the same process as before.
Q3 has the same perimeter as Q2, and the area of Q3 is greater than or equal to the area of Q2.
Q3 has four sides of length (s1+s2+s3+s4)/4, so Q3 is a rhombus. The area of a rhombus is base times height. The base is just a side length, and the height is the side length times the sine of one of the angles. So the area is ((s1+s2+s3+s4)/4)^2 * sin Z, where Z is one of the angles of the rhombus.
Let Q4 be a square with four sides of length (s1+s2+s3+s4)/4. The area of Q4 is ((s1+s2+s3+s4)/4)^2 = (1/16)*(s1+s2+s3+s4)^2.
Q4 has the same perimeter as Q3, and the area of Q4 is greater than or equal to the area of Q3 since sin Z <= 1.
So Area(Q1) < Area(Q2) <= Area(Q3) <= Area(Q4) = (1/16)*(s1+s2+s3+s4)^2.
So the area of Q1 is less than one sixteenth of its perimeter squared.
Case 2: All side lengths are equal.If all side lengths are equal, but the quadrilateral is not a square, then it is a rhombus.
The sine value of all rhombus angles are the same, and since it is not a square, this sine value is less than 1. Let Z be an angle measure in the rhombus.
The area is then side^2 * sin Z < side^2 = (perimeter/4)^2 = (1/16)perimeter^2.
Lemma 1: The product of two unequal non-negative real numbers is less than their average squared.
Let a,b be unequal non-negative real numbers.
ab = (((a+b)/2) + ((a-b)/2)) * (((a+b)/2) - ((a-b)/2))
= ((a+b)/2)^2 - ((a-b)/2)^2
< ((a+b)/2)^2, since ((a-b)/2)^2 is positive.
Lemma 2: A triangle with side lengths a, b, and c has an area less than the area of a triangle with side lengths (a+b)/2, (a+b)/2, c, if a≠b. Equal areas if a=b.Case 1: a≠b
Let triangle T1 have side lengths a, b, and c, where a≠b.
Let triangle T2 have side lengths (a+b)/2, (a+b)/2, and c.The semiperimeter of both triangles s = (a+b+c)/2.
Using Heron's formula, the area of T1 is sqrt( s(s-a)(s-b)(s-c) ).
Similarly, the area of T2 is sqrt( s(s-(a+b)/2)(s-(a+b)/2)(s-c) ).Notice that all of s, (s-a), (s-b), (s-c), and (s-(a+b)/2) are non-negative.
The average of (s-a) and (s-b) is (s-(a+b)/2).
By Lemma 1, (s-a)(s-b) < (s-(a+b)/2)(s-(a+b)/2)
Therefore s(s-a)(s-b)(s-c) < s(s-(a+b)/2)(s-(a+b)/2)(s-c).
And since those are both non-negative reals, sqrt( s(s-a)(s-b)(s-c) ) < sqrt( s(s-(a+b)/2)(s-(a+b)/2)(s-c) )
So the area of T1 is less than the area of T2.
Case 2: a=b
If a=b, then both triangles have the same side lengths. Therefore they have the same areas.
Concave
SpoilerGiven a concave quadrilateral Q0. Let V1 be the vertex of Q0 that has an interior angle greater than 180 degrees. Let the vertices V2 and V4 be the vertices connected to V1, and V3 be the remaining vertex.
Mirror V1 across the line connecting V2 and V4 to point P1.
Construct quadrilateral Q1 by connecting the points P1, V2, V3, V4.
Q1 has the same perimeter as Q0, and the area of Q1 is greater than the area of Q0.
Above was shown that the area of a convex non-square quadrilateral was less than one sixteenth of its perimeter squared, so Area(Q0) < Area(Q1) < (1/16)Perimeter(Q1)^2 = (1/16)Perimeter(Q0)^2.
So the area of Q0 is less than one sixteenth of its perimeter squared.
If V1 and V3 share the same point and Q1 happens to end up a square, the area of Q0 is 0 which is less than one sixteenth its perimeter.
-
34 minutes ago, harey said:
P.S. I am not touchy (did not even think it could be interpreted this way), but I think things over. In the last time, I wrote a lot of nonsense, i.e. my first answer.
Good. Yeah, I overthink everything and can get rather paranoid.
37 minutes ago, harey said:You suppose the devil turns the lantern 5 on. But what if he turns the lantern 4 and not 5 on?
111110 <one lit lantern (interpret 0 as "on" and 1 as "off")
111010 your turnSpoilerThe bit on the left is the lantern the angel and devil are currently at. Numbering lanterns doesn't quite work well with the configuration continually rotating. Assuming the devil doesn't light any more lanterns until the angel extinguishes one, it would go like this.
111110 (Initial configuration) Devil's choice since they are at an off lantern (leftmost bit). The devil doesn't light the lantern.
111101 Devil's choice and he lights the lantern (the rightmost 0 on the next line).
111010 Devil's choice and leaves it off. (Is this the situation you intended?)
110101 Devil's choice and leaves it off. (I believe the Devil lights this lantern in my code's output. 110101 -> 101010)
101011 Devil's choice and leaves it off.
010111 Angel's choice and extinguishes it. Back to 1 lit lantern.
101111 Devil's choice and if he doesn't light it the angel will extinguish the last lit lantern on the next step.
011110 Angel's choice and leaves it on. Now there are two lit lanterns next to each other.
111100Here's if the Devil lights the lantern two away on the other side (and keeps no more than 2 lit lanterns).
111110 D 1->1
111101 D 1->1
111011 D 1->1
110111 D 1->0
101110 D 1->1
011101 A 0->0 Angel needs to wait to turn off the other lit lantern.
111010 D 1->1
110101 D 1->1
101011 D 1->1
010111 A 0->1 Back to 1 lit lantern
101111 D 1->0 Needs to light or lose at the next lantern.
011110 A 0->0 Two lit lanterns next to each other.
111100 -
And by "put the devil in his place", I didn't mean you @harey. I reread that and remembered you said "As I am a nice guy, I let you the role of the angel." So if you found that belittling, I apologize, as that was not my intent. I am sure you see things I don't and vice-versa.
-
First, let's nail down the definition of configuration so we know exactly when the devil wins.
It cannot simply be the state of the lanterns, since not changing a lantern on a given step would then repeat the configuration.
So the location of the devil and angel need to be part of it. There are two ways I see of incorporating this.
- Include which lantern number the devil and angel are at and the string of lantern states. Which could be notated by a location marked in a string of lantern states (e.g., "01101;001") or a number and the string (6,01101001).
- The lantern numbers don't matter, just look forward from the lantern the angel and devil are at (e.g., ";00101101"). And then you don't need the location marker ";" because it is always at the front.
Option 1 has more states, lanterns x 2^lanterns compared to just 2^lanterns. Let's choose option 2 since less states means more of a chance of repeat and gives the devil a better chance. That is the notation I used for my code.
On 1/28/2024 at 4:35 PM, harey said:I assume that if they make a turn without changing the state of any lantern. a "previously encountered state" occurs (otherwise, they could walk around endlessly).
I notice that you use the word "turn" to sometimes mean one whole stroll around all the lanterns. That is something that threw me off a little. I'd call that a revolution or a full rotation.
Alright, time to put the devil in his place.
SpoilerSo given your situations, going back to a situation doesn't take into account the location of the angel and devil. This is actually very important since the angel's first goal is to make the devil have two lit lanterns closer and closer. Once they are together they act simply as one as far as the devil is concerned. Then you need to light another, which the angel makes you move closer to the pair of lit lanterns, etc.
Lets see how this works. After you have lit a second lantern, being the angel, I look at which segment of the circle has less distance between the two lit lanterns. I turn off the lantern at the beginning of that segment. This means you either turn on the next one after that, leaving a segment with one less lantern, or wait and leave an even smaller distance to the remaining lit lantern. Obviously, you need to light one before letting me turn that one off or I would win.
Here's an example from my code's 6 lantern output:
111110 <one lit lantern (interpret 0 as "on" and 1 as "off")
111101 <one lit lantern
111011 <one lit lantern
110110
101101
011011
110111 <back to one lit lantern, but it is 1 lantern closer than the last time.
101110 <devil lit the next oneIn this way the angel forces the devil to light lanterns closer together until they are right next to each other. A process which is then repeated, without the need to find which segment is shorter... since the pair together make the configuration unique. So just move the new one around until it meets the pair of lit lanterns.
It looks like there are other tricks the devil pulls, but as my code showed the configurations can be ordered in such a way that the devil's choice is always between one step forward and many steps forward towards the angel's eventual winning state.
-
I couldn't follow that, harey.
SpoilerSince you use some numbers >32, I assume there are 6 lanterns.
I couldn't find a 33 that has one lantern lit from my code output.
"110100 33 11" <-- This state is 33 steps from the angel winning in my code, it has 3 on and 3 off.
"100001 11 33" <-- Internal representation is 33, 4 lanterns are lit since 0 means on due to misremembering the story.
14 hours ago, harey said:Before you turn 33 off, I have to light a lantern:
I don't know how I'd turn a configuration off, so 33 refers to a single lantern?
14 hours ago, harey said:b) 33 in this turn or the next one
I don't know how to interpret this. Turn off 33 in two different possible turns?
Clearly I am very confused. Could you rewrite your post with the string of lanterns shown each step? You could either use 1 as on (makes sense) or 1 as off (like my code due to my misremembering the story). Or like you did before ("(off) on on on")
Or perhaps just explain in more detail?
-
Just saw your post harey.
SpoilerThe person who posted this solution in your link said they copied it from "INGENIOUS
Mathematical Problems and Methods" by L.A. Graham, published by Dover
Publications, Inc., New York, 1959.Converting the $7.11 to 711 cents, we are left with a massive
Diophantine problem of finding four factors of 711,000,000 that add up to
711. In order to produce the six zeros in the final product, the result of
any individual multiplication must end in zero. Since the other two figures
could not furnish more than 5 zeros, the first figure of such a product
then not being 2 or 5, and since the unit digits must add up to 1; the only
possibilities are 0, 0, 0, 1 or 0, 0, 5, 6. The factors of 711,000 are
(2)^6, (3)^2, (5)^6, and (79), and in order to fulfill the above conditions
79 must be multiplied by 4, since if multiplied by 5, the four factors
would have to add up to more than 711, because even if the other three
factors could be equal, which gives the smallest sum, they would add up to
more than 711 minus 395. This derives from the general relation that the
factors of a number add up to the least amount when they are equal. We
therefore know that one factor is 316 and the other three factors which end
in 5, 0, and 0 respectively add up to 395. Since the cube root of the
remaining product is 131, none of the three factors can depart much from
this average. This leaves only a few combinations to try before arriving at
the figures of 120, 125, and 150.
Therefore, the costs of the four items were $3.16, $1.50, $1.25, and
$1.20 which when added together total $7.11 and when multiplied together
total $7.11 also.(Ctrl-F) "79 must be multiplied by 4" is a starting point, but why not by 3?
79 x 3 = 237. A one's digit of 7 can't work with the two possibilities of 0,0,0,1 and 0,0,5,6 determined beforehand.
"This leaves only a few combinations" would need some more clarification, too."We therefore know that one factor is 316 and the other three factors which end in 5, 0, and 0 respectively add up to 395." The product of the remaining factors is 2250000.
Lets determine the largest that the largest number of the remaining 3 can be. I'll start counting up from 2250000^(1/3) = 131.0370697.
2250000/135 = 16666.66667, not an integer
2250000/140 = 16071.42857, not an integer
2250000/145 = 15517.2413, not an integer
2250000/150 = 15000.
2250000/155 = 14516.12903, not an integer
2250000/160 = 14062.5, not an integer
2250000/165 = 13636.36364, not an integer
2250000/170 = 13235.29412, not an integer
2250000/175 = 12857.14286, not an integer
2250000/180 = 12500.If it is 180, the remaining sum is 215 and product 12500. (215/2)^2 maximizes the possible product of the last two numbers at 11556.25. So 180 is too large. (155 is too large by this method, too)
The only possibility then is 150, leaving a remaining sum of 245 and product of 15000. The final two are simple at this point.
-
recreating the results of the code...
SpoilerWe work backwards. If you haven't seen the configuration of lanterns (excluding the furthest one), then it must be the angel's choice... because if it was the devil's choice he would have chosen the other choice to avoid helping the angel. If we have seen the configuration before, then it must have been the devil's choice this time... otherwise the angel would have chosen something better.
I'll show this with 4 lanterns.
The final result is off,off,off,off. I'll represent this by 0000... opposite of the code. I wrote the code after misremembering the story as the angel goes around with the power to light lanterns and the devil to extinguish.
(000)0 - We haven't seen 000 before, so must have been the angel's choice, so prepend a 1.
(100)00 - new conf, angel's choice, add 1.
(110)000 - new conf, angel's choice, add 1.
(111)0000 - new conf, but since 1111 would have been a win state it's the devil's choice, add 0.
(011)10000 - new conf, angel's choice, add 1.
(101)110000 - new conf, angel's choice, add 1.
(110)1110000 - seen before, devil's choice, add 0.
(011)01110000 - seen before, devil's choice, add 0.
(001)101110000 - new conf, angel's choice, add 1.
(100)1101110000 - seen before, devil's choice, add 0.
(010)01101110000 - new conf, angel's choice, add 1.
(101)001101110000 - seen before, devil's choice, add 0.
(010)1001101110000 - seen before, devil's choice, add 0.
(001)01001101110000 - seen before, devil's choice, add 0.
(000)101001101110000 - seen before, but 0000 is a win state so cannot continue.
It just happens that 000101001101110000 covers all lantern configurations (except 1111, which is a win state anyway).
So, we just need to prove this happens for any number of lanterns. An easy way to determine the angel's choice would be nice too.
-
sorted configurations with 6 lanterns (and added devil best choices I omitted before)
Spoiler1 111110 | 111100 D> 111101 | 62 | 45 61
1 111101 | 111010 D> 111011 | 61 | 53 60
1 111011 | 110110 D< 110111 | 60 | 59 56
1 110110 | 101100 D> 101101 | 59 | 39 58
1 101101 | 011010 D> 011011 | 58 | 34 57
1 011011 | 110110 A> 110111 | 57
1 110111 | 101110 D< 101111 | 56 | 55 47
1 101110 | 011100 D> 011101 | 55 | 25 54
1 011101 | 111010 A< 111011 | 54
1 111010 | 110100 D> 110101 | 53 | 33 52
1 110101 | 101010 D< 101011 | 52 | 51 49
1 101010 | 010100 D> 010101 | 51 | 19 50
1 010101 | 101010 A> 101011 | 50
1 101011 | 010110 D> 010111 | 49 | 40 48
1 010111 | 101110 A> 101111 | 48
1 101111 | 011110 D< 011111 | 47 | 46 1
1 011110 | 111100 A< 111101 | 46
1 111100 | 111000 D> 111001 | 45 | 24 44
1 111001 | 110010 D< 110011 | 44 | 43 37
1 110010 | 100100 D> 100101 | 43 | 30 42
1 100101 | 001010 D> 001011 | 42 | 20 41
1 001011 | 010110 A< 010111 | 41
1 010110 | 101100 A< 101101 | 40
1 101100 | 011000 D> 011001 | 39 | 13 38
1 011001 | 110010 A> 110011 | 38
1 110011 | 100110 D< 100111 | 37 | 36 27
1 100110 | 001100 D> 001101 | 36 | 14 35
1 001101 | 011010 A< 011011 | 35
1 011010 | 110100 A< 110101 | 34
1 110100 | 101000 D> 101001 | 33 | 18 32
1 101001 | 010010 D< 010011 | 32 | 31 28
1 010010 | 100100 A< 100101 | 31
1 100100 | 001000 D> 001001 | 30 | 8 29
1 001001 | 010010 A> 010011 | 29
1 010011 | 100110 A> 100111 | 28
1 100111 | 001110 D< 001111 | 27 | 26 2
1 001110 | 011100 A< 011101 | 26
1 011100 | 111000 A< 111001 | 25
1 111000 | 110000 D> 110001 | 24 | 12 23
1 110001 | 100010 D< 100011 | 23 | 22 16
1 100010 | 000100 D> 000101 | 22 | 9 21
1 000101 | 001010 A< 001011 | 21
1 001010 | 010100 A< 010101 | 20
1 010100 | 101000 A< 101001 | 19
1 101000 | 010000 D> 010001 | 18 | 7 17
1 010001 | 100010 A> 100011 | 17
1 100011 | 000110 D< 000111 | 16 | 15 3
1 000110 | 001100 A< 001101 | 15
1 001100 | 011000 A< 011001 | 14
1 011000 | 110000 A< 110001 | 13
1 110000 | 100000 D> 100001 | 12 | 6 11
1 100001 | 000010 D< 000011 | 11 | 10 4
1 000010 | 000100 A< 000101 | 10
1 000100 | 001000 A< 001001 | 9
1 001000 | 010000 A< 010001 | 8
1 010000 | 100000 A< 100001 | 7
1 100000 | 000000 D> 000001 | 6 | 0 5
1 000001 | 000010 A> 000011 | 5
1 000011 | 000110 A> 000111 | 4
1 000111 | 001110 A> 001111 | 3
1 001111 | 011110 A> 011111 | 2
1 011111 | 111110 A> 111111 | 1
1 111111 | 111110 D? 111111 | 0 | 62 05 lanterns
Spoiler1 11110 | 11100 D> 11101 | 30 | 20 29
1 11101 | 11010 D> 11011 | 29 | 25 28
1 11011 | 10110 D< 10111 | 28 | 27 22
1 10110 | 01100 D> 01101 | 27 | 11 26
1 01101 | 11010 A< 11011 | 26
1 11010 | 10100 D> 10101 | 25 | 15 24
1 10101 | 01010 D> 01011 | 24 | 16 23
1 01011 | 10110 A> 10111 | 23
1 10111 | 01110 D< 01111 | 22 | 21 1
1 01110 | 11100 A< 11101 | 21
1 11100 | 11000 D> 11001 | 20 | 10 19
1 11001 | 10010 D< 10011 | 19 | 18 13
1 10010 | 00100 D> 00101 | 18 | 7 17
1 00101 | 01010 A< 01011 | 17
1 01010 | 10100 A< 10101 | 16
1 10100 | 01000 D> 01001 | 15 | 6 14
1 01001 | 10010 A> 10011 | 14
1 10011 | 00110 D< 00111 | 13 | 12 2
1 00110 | 01100 A< 01101 | 12
1 01100 | 11000 A< 11001 | 11
1 11000 | 10000 D> 10001 | 10 | 5 9
1 10001 | 00010 D< 00011 | 9 | 8 3
1 00010 | 00100 A< 00101 | 8
1 00100 | 01000 A< 01001 | 7
1 01000 | 10000 A< 10001 | 6
1 10000 | 00000 D> 00001 | 5 | 0 4
1 00001 | 00010 A> 00011 | 4
1 00011 | 00110 A> 00111 | 3
1 00111 | 01110 A> 01111 | 2
1 01111 | 11110 A> 11111 | 1
1 11111 | 11110 D? 11111 | 0 | 30 04 lanterns
Spoiler1 1110 | 1100 D> 1101 | 14 | 8 13
1 1101 | 1010 D< 1011 | 13 | 12 10
1 1010 | 0100 D> 0101 | 12 | 5 11
1 0101 | 1010 A> 1011 | 11
1 1011 | 0110 D< 0111 | 10 | 9 1
1 0110 | 1100 A< 1101 | 9
1 1100 | 1000 D> 1001 | 8 | 4 7
1 1001 | 0010 D< 0011 | 7 | 6 2
1 0010 | 0100 A< 0101 | 6
1 0100 | 1000 A< 1001 | 5
1 1000 | 0000 D> 0001 | 4 | 0 3
1 0001 | 0010 A> 0011 | 3
1 0011 | 0110 A> 0111 | 2
1 0111 | 1110 A> 1111 | 1
1 1111 | 1110 D? 1111 | 0 | 14 03 lanterns
Spoiler1 110 | 100 D> 101 | 6 | 3 5
1 101 | 010 D< 011 | 5 | 4 1
1 010 | 100 A< 101 | 4
1 100 | 000 D> 001 | 3 | 0 2
1 001 | 010 A> 011 | 2
1 011 | 110 A> 111 | 1
1 111 | 110 D? 111 | 0 | 6 0Edit: Another thing of note. The devil and angel both choose between the same 2 options once each (except the choice between 000...00 and 000...01 for angel and 111...10 and 111...11 for devil, due to angel win conditions).
-
On the "ugly strategy"
SpoilerI guess I knew why it works. The grey code is ordered such that both moves the devil can make result in configurations further in the grey code (one moving one space forward, the other further). This was ensured by how I used the fixed point algorithm. What I don't know it is why such an ordering exists, how to explain it simply, and an easy way to know what move to make without searching through binary vomit.
Edit: Another consequence is, for the angel, one move is one further in the grey code and the other move is back somewhere. So one wrong move and the devil wins.
-
Edit: Oops. I guess switch to 1 meaning off and 0 meaning on to match the story.
Who wins?
SpoilerThe angel will win.
Ugly Strategy with not much intuition as to how/why it works. (Obviously, I don't consider this as the answer...)
SpoilerFind the current configuration (looking ahead from where the pair are) in the following string of lanterns (1-on 0-off), and make the lantern match the lantern just to the right past where the current configuration was found.
11111111111011111011111101111011111110111011101111111101101110111101101111011101101111101101101101111111110101101111110101110111110101111011110101111101110101101101110101110101111110110101101110110101110110110101111010110101111111010101101111010101110111010101111011010101101011010101111101010101101101010101110101010101011111111110010111111110011011111110011101111110010101111110011110111110010110111110011010111110011111011110010111011110011011011110011101011110010101011110011110011111101110010111101110011011101110011101101110010101101110011110101110010110101110011010101110011111001110010111001110011111110110010111110110011011110110011101110110010101110110011110110110010110110110011010110110011100110110011111010110010111010110011011010110011101010110010101010110011110010110010110011111100110010111100110011011100110011101100110010101100110011001111111101001011111101001101111101001110111101001010111101001100111101001111011101001011011101001101011101001110011101001111101101001011101101001101101101001110101101001010101101001100101101001111001101001011001101001101001111110101001011110101001101110101001110110101001010110101001100110101001111010101001011010101001101010101001110010101001111100101001011100101001101100101001110100101001010100101001111111001001011111001001101111001001110111001001010111001001100111001001111011001001011011001001101011001001110011001001010011001001111101001001011101001001101101001001110101001001010101001001100101001001111001001001011001001001101001001001001111111110001011111110001101111110001001111110001110111110001010111110001100111110001111011110001011011110001101011110001001011110001110011110001010011110001111101110001011101110001101101110001001101110001110101110001010101110001100101110001111001110001011001110001101001110001001001110001110001111110110001011110110001101110110001001110110001110110110001010110110001100110110001111010110001011010110001101010110001001010110001110010110001010010110001111100110001011100110001101100110001001100110001110100110001010100110001100100110001111000110001011000110001111111010001011111010001101111010001001111010001110111010001010111010001100111010001111011010001011011010001101011010001001011010001110011010001010011010001100011010001111101010001011101010001101101010001001101010001110101010001010101010001100101010001111001010001011001010001101001010001001001010001110001010001010001111110010001011110010001101110010001001110010001110110010001010110010001100110010001111010010001011010010001101010010001001010010001110010010001010010010001100010010001111100010001011100010001101100010001001100010001110100010001010100010001100100010001000111111110000101111110000110111110000100111110000111011110000101011110000110011110000100011110000111101110000101101110000110101110000100101110000111001110000101001110000110001110000111110110000101110110000110110110000100110110000111010110000101010110000110010110000100010110000111100110000101100110000110100110000100100110000111000110000101000110000110000111111010000101111010000110111010000100111010000111011010000101011010000110011010000100011010000111101010000101101010000110101010000100101010000111001010000101001010000110001010000111110010000101110010000110110010000100110010000111010010000101010010000110010010000100010010000111100010000101100010000110100010000100100010000111000010000101000010000111111100000101111100000110111100000100111100000111011100000101011100000110011100000100011100000111101100000101101100000110101100000100101100000111001100000101001100000110001100000100001100000111110100000101110100000110110100000100110100000111010100000101010100000110010100000100010100000111100100000101100100000110100100000100100100000111000100000101000100000110000100000100000111111000000101111000000110111000000100111000000111011000000101011000000110011000000100011000000111101000000101101000000110101000000100101000000111001000000101001000000110001000000100001000000111110000000101110000000110110000000100110000000111010000000101010000000110010000000100010000000111100000000101100000000110100000000100100000000111000000000101000000000110000000000100000000000111111111111
Yeah, it's a cool shifting grey code. I haven't quite figured it out yet.
Yay code
Spoiler#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <memory.h>using namespace std;
int move(int conf, int setvalue);
void printconf(int conf);int lanterns;
int movemask;
int lastspot;int main(int argc, char *argv[])
{
if (argc >= 2) lanterns = atoi(argv[1]);
else {cout << "Need number of lanterns to use." << endl; return 0;}
if ((lanterns < 2) || (lanterns > 20)) {cout << "Lantern number must be between 2 and 20."; return 0;}
movemask = (1 << lanterns)-1;
lastspot = 1 << (lanterns-1);
int *bestchoice = new int[1 << lanterns];
int **next = new int*[2];
next[0] = new int[1 << lanterns];
next[1] = new int[1 << lanterns];
int *winstates = new int[1 << lanterns];
int *stepstowin = new int[1 << lanterns];
//initialize
for(int i = 0; i < (1<<lanterns); i++) {bestchoice[i] = -1; winstates[i] = 0; next[0][i] = move(i,0); next[1][i] = move(i,1); stepstowin[i] = -1;}
winstates[0] = 1;
winstates[movemask] = 1;
stepstowin[0] = 0;
stepstowin[movemask] = 0;
//fixed point algorithm
while(true)
{
int changed = 0;
for(int i = 0; i < (1<<lanterns); i++)
{
if (winstates[i]) continue;
if (i%2)
{//devil's choice
//if both choices results in win states for angel, mark as win state for angel
if (winstates[next[0][i]] && winstates[next[1][i]])
{
changed=1; winstates[i]=1;
if (stepstowin[next[0][i]] < stepstowin[next[1][i]]) stepstowin[i] = stepstowin[next[1][i]]+1;
else stepstowin[i] = stepstowin[next[0][i]]+1;
}
}
else
{//angel's choice
if (winstates[next[0][i]]){changed=1; bestchoice[i]=0; winstates[i]=1; stepstowin[i]=stepstowin[next[0][i]]+1;}
if (winstates[next[1][i]]){changed=1; bestchoice[i]=1; winstates[i]=1; stepstowin[i]=stepstowin[next[1][i]]+1;}
}
}
int all = 1;
for(int i = 0; i < (1<<lanterns); i++) all &= winstates[i];
//print status
if (all) // (true)
{
cout << endl << endl;
for(int i = 0; i < (1<<lanterns); i++)
{
cout << winstates[i] << " "; printconf(i); cout << " | "; printconf(next[0][i]);
if (i%2) {cout << " D";} else {cout << " A";}
if (bestchoice[i]==-1) cout << "? ";
if (bestchoice[i]==0) cout << "< ";
if (bestchoice[i]==1) cout << "> ";
printconf(next[1][i]);
cout << " | " << stepstowin[i];
if (i%2)
{
cout << " | " << stepstowin[next[0][i]] << " " << stepstowin[next[1][i]];
}
cout << endl;
}
}
if (all) {cout << "All states are win states for the angel." << endl; break;}
if (changed == 0)
{
break;
}
}
//print configurations in order of steps to win
cout << endl;
for(int j = movemask-1; j >= 0; j--)
{
for(int i = 1; i < (1<<lanterns); i++) //started at 1 to skip all lanterns off configuration
if (stepstowin[i] == j)
{
printconf(i);
cout << " " << j << " " << i << endl;
}
}
//print full shifting grey code
cout << endl;
for(int j = movemask-1; j >= 0; j--)
{
for(int i = 1; i < (1<<lanterns)-1; i++) //started at 1 to skip all lanterns off configuration
if (stepstowin[i] == j)
{
cout << (i%2);
}
}
printconf(movemask);
cout << endl;
delete[] next[0];
delete[] next[1];
delete[] next;
delete[] winstates;
delete[] bestchoice;
delete[] stepstowin;
return 0;
}int move(int conf, int setvalue)
{
return ((conf >> 1) + (setvalue * lastspot)) & movemask;
}void printconf(int conf)
{
for(int j = 0; j < lanterns; j++)
{
if (conf & (1<<j)) cout << "1";
else cout << "0";
}
}Code output for 4 lanterns
Spoiler1 0000 | 0000 A? 0001 | 0
1 1000 | 0000 D? 0001 | 4 | 0 3
1 0100 | 1000 A< 1001 | 5
1 1100 | 1000 D? 1001 | 8 | 4 7
1 0010 | 0100 A< 0101 | 6
1 1010 | 0100 D? 0101 | 12 | 5 11
1 0110 | 1100 A< 1101 | 9
1 1110 | 1100 D? 1101 | 14 | 8 13
1 0001 | 0010 A> 0011 | 3
1 1001 | 0010 D? 0011 | 7 | 6 2
1 0101 | 1010 A> 1011 | 11
1 1101 | 1010 D? 1011 | 13 | 12 10
1 0011 | 0110 A> 0111 | 2
1 1011 | 0110 D? 0111 | 10 | 9 1
1 0111 | 1110 A> 1111 | 1
1 1111 | 1110 D? 1111 | 0 | 14 0
All states are win states for the angel.1110 14 7
1101 13 11
1010 12 5
0101 11 10
1011 10 13
0110 9 6
1100 8 3
1001 7 9
0010 6 4
0100 5 2
1000 4 1
0001 3 8
0011 2 12
0111 1 14
1111 0 15111010110010001111
5 lanterns
Spoiler1 00000 | 00000 A? 00001 | 0
1 10000 | 00000 D? 00001 | 5 | 0 4
1 01000 | 10000 A< 10001 | 6
1 11000 | 10000 D? 10001 | 10 | 5 9
1 00100 | 01000 A< 01001 | 7
1 10100 | 01000 D? 01001 | 15 | 6 14
1 01100 | 11000 A< 11001 | 11
1 11100 | 11000 D? 11001 | 20 | 10 19
1 00010 | 00100 A< 00101 | 8
1 10010 | 00100 D? 00101 | 18 | 7 17
1 01010 | 10100 A< 10101 | 16
1 11010 | 10100 D? 10101 | 25 | 15 24
1 00110 | 01100 A< 01101 | 12
1 10110 | 01100 D? 01101 | 27 | 11 26
1 01110 | 11100 A< 11101 | 21
1 11110 | 11100 D? 11101 | 30 | 20 29
1 00001 | 00010 A> 00011 | 4
1 10001 | 00010 D? 00011 | 9 | 8 3
1 01001 | 10010 A> 10011 | 14
1 11001 | 10010 D? 10011 | 19 | 18 13
1 00101 | 01010 A< 01011 | 17
1 10101 | 01010 D? 01011 | 24 | 16 23
1 01101 | 11010 A< 11011 | 26
1 11101 | 11010 D? 11011 | 29 | 25 28
1 00011 | 00110 A> 00111 | 3
1 10011 | 00110 D? 00111 | 13 | 12 2
1 01011 | 10110 A> 10111 | 23
1 11011 | 10110 D? 10111 | 28 | 27 22
1 00111 | 01110 A> 01111 | 2
1 10111 | 01110 D? 01111 | 22 | 21 1
1 01111 | 11110 A> 11111 | 1
1 11111 | 11110 D? 11111 | 0 | 30 0
All states are win states for the angel.11110 30 15
11101 29 23
11011 28 27
10110 27 13
01101 26 22
11010 25 11
10101 24 21
01011 23 26
10111 22 29
01110 21 14
11100 20 7
11001 19 19
10010 18 9
00101 17 20
01010 16 10
10100 15 5
01001 14 18
10011 13 25
00110 12 12
01100 11 6
11000 10 3
10001 9 17
00010 8 8
00100 7 4
01000 6 2
10000 5 1
00001 4 16
00011 3 24
00111 2 28
01111 1 30
11111 0 3111110110101110010100110001000011111
6 lanterns
Spoiler1 000000 | 000000 A? 000001 | 0
1 100000 | 000000 D? 000001 | 6 | 0 5
1 010000 | 100000 A< 100001 | 7
1 110000 | 100000 D? 100001 | 12 | 6 11
1 001000 | 010000 A< 010001 | 8
1 101000 | 010000 D? 010001 | 18 | 7 17
1 011000 | 110000 A< 110001 | 13
1 111000 | 110000 D? 110001 | 24 | 12 23
1 000100 | 001000 A< 001001 | 9
1 100100 | 001000 D? 001001 | 30 | 8 29
1 010100 | 101000 A< 101001 | 19
1 110100 | 101000 D? 101001 | 33 | 18 32
1 001100 | 011000 A< 011001 | 14
1 101100 | 011000 D? 011001 | 39 | 13 38
1 011100 | 111000 A< 111001 | 25
1 111100 | 111000 D? 111001 | 45 | 24 44
1 000010 | 000100 A< 000101 | 10
1 100010 | 000100 D? 000101 | 22 | 9 21
1 010010 | 100100 A< 100101 | 31
1 110010 | 100100 D? 100101 | 43 | 30 42
1 001010 | 010100 A< 010101 | 20
1 101010 | 010100 D? 010101 | 51 | 19 50
1 011010 | 110100 A< 110101 | 34
1 111010 | 110100 D? 110101 | 53 | 33 52
1 000110 | 001100 A< 001101 | 15
1 100110 | 001100 D? 001101 | 36 | 14 35
1 010110 | 101100 A< 101101 | 40
1 110110 | 101100 D? 101101 | 59 | 39 58
1 001110 | 011100 A< 011101 | 26
1 101110 | 011100 D? 011101 | 55 | 25 54
1 011110 | 111100 A< 111101 | 46
1 111110 | 111100 D? 111101 | 62 | 45 61
1 000001 | 000010 A> 000011 | 5
1 100001 | 000010 D? 000011 | 11 | 10 4
1 010001 | 100010 A> 100011 | 17
1 110001 | 100010 D? 100011 | 23 | 22 16
1 001001 | 010010 A> 010011 | 29
1 101001 | 010010 D? 010011 | 32 | 31 28
1 011001 | 110010 A> 110011 | 38
1 111001 | 110010 D? 110011 | 44 | 43 37
1 000101 | 001010 A< 001011 | 21
1 100101 | 001010 D? 001011 | 42 | 20 41
1 010101 | 101010 A> 101011 | 50
1 110101 | 101010 D? 101011 | 52 | 51 49
1 001101 | 011010 A< 011011 | 35
1 101101 | 011010 D? 011011 | 58 | 34 57
1 011101 | 111010 A< 111011 | 54
1 111101 | 111010 D? 111011 | 61 | 53 60
1 000011 | 000110 A> 000111 | 4
1 100011 | 000110 D? 000111 | 16 | 15 3
1 010011 | 100110 A> 100111 | 28
1 110011 | 100110 D? 100111 | 37 | 36 27
1 001011 | 010110 A< 010111 | 41
1 101011 | 010110 D? 010111 | 49 | 40 48
1 011011 | 110110 A> 110111 | 57
1 111011 | 110110 D? 110111 | 60 | 59 56
1 000111 | 001110 A> 001111 | 3
1 100111 | 001110 D? 001111 | 27 | 26 2
1 010111 | 101110 A> 101111 | 48
1 110111 | 101110 D? 101111 | 56 | 55 47
1 001111 | 011110 A> 011111 | 2
1 101111 | 011110 D? 011111 | 47 | 46 1
1 011111 | 111110 A> 111111 | 1
1 111111 | 111110 D? 111111 | 0 | 62 0
All states are win states for the angel.111110 62 31
111101 61 47
111011 60 55
110110 59 27
101101 58 45
011011 57 54
110111 56 59
101110 55 29
011101 54 46
111010 53 23
110101 52 43
101010 51 21
010101 50 42
101011 49 53
010111 48 58
101111 47 61
011110 46 30
111100 45 15
111001 44 39
110010 43 19
100101 42 41
001011 41 52
010110 40 26
101100 39 13
011001 38 38
110011 37 51
100110 36 25
001101 35 44
011010 34 22
110100 33 11
101001 32 37
010010 31 18
100100 30 9
001001 29 36
010011 28 50
100111 27 57
001110 26 28
011100 25 14
111000 24 7
110001 23 35
100010 22 17
000101 21 40
001010 20 20
010100 19 10
101000 18 5
010001 17 34
100011 16 49
000110 15 24
001100 14 12
011000 13 6
110000 12 3
100001 11 33
000010 10 16
000100 9 8
001000 8 4
010000 7 2
100000 6 1
000001 5 32
000011 4 48
000111 3 56
001111 2 60
011111 1 62
111111 0 6311111011011101010111100101100110100100111000101000110000100000111111
-
Which angles correspond to which sides? There are two sides that create a given angle and two away.
-
Proof 3: Factors of x^5-x
SpoilerIf x differs by x^5 by a multiple of 10, they must have the same one's digit.
x^5-x = x * (x^4-1)
= x * (x^2-1) * (x^2+1)
= x * (x-1) * (x+1) * (x^2+1)
Since x and x-1 are factors, x^5-x is even and we only need to show it is also a multiple of 5.If x is a multiple of 5 or one away from a multiple of 5, x^5-x is a multiple of 5 since x, x-1, and x+1 are all factors. The remaining possibilities to check differ from multiples of 5 by 2, so lets substitute them into the final factor.
x^2+1 = (5a +/- 2) * (5a +/- 2) + 1
= (25a^2 +/- 20a + 4) + 1
= 25a^2 +/- 20a +5
= 5 * (5a^2 +/- 4a + 1)Since x^5-x will always be a multiple of 10, x and x^5 must have the same one's digit.
-
Proof 1: Modulus 10
SpoilerThe last digit is just the number mod 10.
(x * y) mod z = ((x mod z) * (y mod z)) mod z, so we just need to check x^5 mod 10 for each of 0-9.
x,^2,^3,^4,^5
0,0,0,0,0
1,1,1,1,1
2,4,8,6,2
3,9,7,1,3
4,6,4,6,4
5,5,5,5,5
6,6,6,6,6
7,9,3,1,7
8,4,2,6,8
9,1,9,1,9Done.
Proof 2: Modulus 5
SpoilerLet n be a natural number. n can be represented as 5x + a, where x is an integer and a is one of {-2,-1,0,1,2} .
Case 1: a = 0
Any power of an odd multiple of 5 remains an odd multiple of 5, and must have a 5 in the ones digit.
Any power of an even multiple of 5 remains an even multiple of 5, and must have a 0 in the evens digit.
So n^5 has the same ones digit as n.Case 2: a = 1 or -1
(5x +/- 1) * (5x +/- 1)
= 25x^2 +/- 10x + 1
= 1 mod 5
Squaring again it remains 1 mod 5.Case 3: a = 2 or -2
(5x +/- 2) * (5x +/- 2)
= 25x^2 +/- 20x + 4
= 4 mod 5
From case 2, we see if we square something 4 mod 5 (a=-1), it becomes 1 mod 5.Finishing cases 2 and 3:
n^4 = 1 mod 5, so it can be represented as 5y+1 for an integer y.
(5y+1)*(5x+a)
= 25xy + 5x + 5ay + a
= a mod 5.
So n^5 mod 5 = a mod 5 = n mod 5.
n^5 mod 2 = n mod 2 since any power of an even number remains even and any power of an odd number remains odd.
n^5 mod 10 = n mod 10, because 5 and 2 are relatively prime.
Same mod 10 = same last digit.Done.
It's also interesting from this proof... n^4 ends in 1 for odd non multiples of 5, n^4 ends in 6 for even non multiples of 5.
Also, no fourth power of any integer ends in 2,3,4,7,8, or 9.I have a third proof idea... I'll see if I can flush it out later.
Are you a math professor/researcher? If not, where do you find / get inspiration for these?
-
Constant fraction of current money to maximize the median/mode:
SpoilerThe median/mode happens when you win 50 times and lose 50 times. Therefore, if you maximize the amount of money you have after 1 win and 1 loss, that should maximize after 50 of each.
m = (1-b)(1+2b) = 1+b-2b^2
dm/db = 1-4b
dm/db=0 => b = 1/4
The constant fraction bet that maximizes median payout is 1/4 of current money.
After 1 win and 1 loss = 3/4 * 3/2 = 9/8. After 50 wins and losses = (9/8)^50 = 361.0988642 times initial money.
Code output (assumes infinitely divisible money):
SpoilerThis is output for betting 1/4 of current money each time.
wins: probability, final money, cumulative probability, money*prob, running total of money * prob = sums to the expected value
0: 7.88861e-31, 3.2072e-13, 7.88861e-31, 2.53004e-43, 2.53004e-43
1: 7.88861e-29, 6.4144e-13, 7.9675e-29, 5.06007e-41, 5.08537e-41
2: 3.90486e-27, 1.28288e-12, 3.98454e-27, 5.00947e-39, 5.06033e-39
3: 1.27559e-25, 2.56576e-12, 1.31543e-25, 3.27286e-37, 3.32346e-37
4: 3.0933e-24, 5.13152e-12, 3.22484e-24, 1.58733e-35, 1.62057e-35
5: 5.93914e-23, 1.0263e-11, 6.26162e-23, 6.09537e-34, 6.25742e-34
6: 9.40364e-22, 2.05261e-11, 1.00298e-21, 1.9302e-32, 1.99277e-32
7: 1.26277e-20, 4.10522e-11, 1.36307e-20, 5.18396e-31, 5.38324e-31
8: 1.46797e-19, 8.21044e-11, 1.60428e-19, 1.20527e-29, 1.2591e-29
9: 1.5006e-18, 1.64209e-10, 1.66102e-18, 2.46411e-28, 2.59002e-28
10: 1.36554e-17, 3.28418e-10, 1.53165e-17, 4.48468e-27, 4.74368e-27
11: 1.11726e-16, 6.56835e-10, 1.27043e-16, 7.33857e-26, 7.81294e-26
12: 8.28636e-16, 1.31367e-09, 9.55679e-16, 1.08855e-24, 1.16668e-24
13: 5.60923e-15, 2.62734e-09, 6.56491e-15, 1.47374e-23, 1.5904e-23
14: 3.48574e-14, 5.25468e-09, 4.14223e-14, 1.83164e-22, 1.99068e-22
15: 1.99849e-13, 1.05094e-08, 2.41271e-13, 2.10028e-21, 2.29935e-21
16: 1.0617e-12, 2.10187e-08, 1.30297e-12, 2.23155e-20, 2.46149e-20
17: 5.24603e-12, 4.20374e-08, 6.549e-12, 2.2053e-19, 2.45145e-19
18: 2.419e-11, 8.40749e-08, 3.0739e-11, 2.03377e-18, 2.27892e-18
19: 1.04399e-10, 1.6815e-07, 1.35138e-10, 1.75547e-17, 1.98336e-17
20: 4.22816e-10, 3.363e-07, 5.57954e-10, 1.42193e-16, 1.62027e-16
21: 1.61073e-09, 6.72599e-07, 2.16868e-09, 1.08337e-15, 1.2454e-15
22: 5.78398e-09, 1.3452e-06, 7.95266e-09, 7.7806e-15, 9.026e-15
23: 1.96152e-08, 2.6904e-06, 2.75679e-08, 5.27728e-14, 6.17988e-14
24: 6.29322e-08, 5.38079e-06, 9.05001e-08, 3.38625e-13, 4.00424e-13
25: 1.91314e-07, 1.07616e-05, 2.81814e-07, 2.05884e-12, 2.45927e-12
26: 5.51867e-07, 2.15232e-05, 8.33681e-07, 1.18779e-11, 1.43372e-11
27: 1.51252e-06, 4.30463e-05, 2.34621e-06, 6.51087e-11, 7.94459e-11
28: 3.94337e-06, 8.60927e-05, 6.28958e-06, 3.39495e-10, 4.18941e-10
29: 9.79043e-06, 0.000172185, 1.608e-05, 1.68577e-09, 2.10471e-09
30: 2.31707e-05, 0.000344371, 3.92507e-05, 7.97931e-09, 1.0084e-08
31: 5.23209e-05, 0.000688741, 9.15716e-05, 3.60356e-08, 4.61196e-08
32: 0.000112817, 0.00137748, 0.000204389, 1.55403e-07, 2.01523e-07
33: 0.000232471, 0.00275497, 0.00043686, 6.40451e-07, 8.41974e-07
34: 0.000458105, 0.00550993, 0.000894965, 2.52413e-06, 3.3661e-06
35: 0.000863856, 0.0110199, 0.00175882, 9.51957e-06, 1.28857e-05
36: 0.00155974, 0.0220397, 0.00331856, 3.43762e-05, 4.72619e-05
37: 0.00269793, 0.0440795, 0.00601649, 0.000118923, 0.000166185
38: 0.00447288, 0.0881589, 0.0104894, 0.000394324, 0.000560509
39: 0.00711073, 0.176318, 0.0176001, 0.00125375, 0.00181426
40: 0.0108439, 0.352636, 0.028444, 0.00382393, 0.00563819
41: 0.0158691, 0.705271, 0.044313, 0.011192, 0.0168302 <---------last situation where you lose money
42: 0.0222923, 1.41054, 0.0666053, 0.0314442, 0.0482744
43: 0.0300686, 2.82108, 0.096674, 0.0848262, 0.133101
44: 0.0389526, 5.64217, 0.135627, 0.219777, 0.352878
45: 0.0484743, 11.2843, 0.184101, 0.547, 0.899878
46: 0.0579584, 22.5687, 0.242059, 1.30804, 2.20792
47: 0.0665905, 45.1374, 0.30865, 3.00572, 5.21364
48: 0.073527, 90.2747, 0.382177, 6.63763, 11.8513
49: 0.0780287, 180.549, 0.460205, 14.088, 25.9393
50: 0.0795892, 361.099, 0.539795, 28.7396, 54.6789
51: 0.0780287, 722.198, 0.617823, 56.3521, 111.031
52: 0.073527, 1444.4, 0.69135, 106.202, 217.233
53: 0.0665905, 2888.79, 0.757941, 192.366, 409.599
54: 0.0579584, 5777.58, 0.815899, 334.859, 744.459
55: 0.0484743, 11555.2, 0.864373, 560.128, 1304.59
56: 0.0389526, 23110.3, 0.903326, 900.206, 2204.79
57: 0.0300686, 46220.7, 0.933395, 1389.79, 3594.59
58: 0.0222923, 92441.3, 0.955687, 2060.73, 5655.31
59: 0.0158691, 184883, 0.971556, 2933.92, 8589.23
60: 0.0108439, 369765, 0.9824, 4009.68, 12598.9
61: 0.00711073, 739530, 0.989511, 5258.6, 17857.5
62: 0.00447288, 1.47906e+06, 0.993984, 6615.66, 24473.2
63: 0.00269793, 2.95812e+06, 0.996681, 7980.8, 32454
64: 0.00155974, 5.91624e+06, 0.998241, 9227.8, 41681.8
65: 0.000863856, 1.18325e+07, 0.999105, 10221.6, 51903.3
66: 0.000458105, 2.3665e+07, 0.999563, 10841.1, 62744.4
67: 0.000232471, 4.733e+07, 0.999796, 11002.9, 73747.2
68: 0.000112817, 9.46599e+07, 0.999908, 10679.2, 84426.5
69: 5.23209e-05, 1.8932e+08, 0.999961, 9905.39, 94331.9
70: 2.31707e-05, 3.7864e+08, 0.999984, 8773.34, 103105
71: 9.79043e-06, 7.57279e+08, 0.999994, 7414.09, 110519
72: 3.94337e-06, 1.51456e+09, 0.999998, 5972.46, 116492
73: 1.51252e-06, 3.02912e+09, 0.999999, 4581.61, 121073
74: 5.51867e-07, 6.05823e+09, 1, 3343.34, 124417
75: 1.91314e-07, 1.21165e+10, 1, 2318.05, 126735
76: 6.29322e-08, 2.42329e+10, 1, 1525.03, 128260
77: 1.96152e-08, 4.84659e+10, 1, 950.67, 129210
78: 5.78398e-09, 9.69317e+10, 1, 560.651, 129771
79: 1.61073e-09, 1.93863e+11, 1, 312.261, 130083
80: 4.22816e-10, 3.87727e+11, 1, 163.937, 130247
81: 1.04399e-10, 7.75454e+11, 1, 80.9567, 130328
82: 2.419e-11, 1.55091e+12, 1, 37.5165, 130366
83: 5.24603e-12, 3.10182e+12, 1, 16.2722, 130382
84: 1.0617e-12, 6.20363e+12, 1, 6.58638, 130389
85: 1.99849e-13, 1.24073e+13, 1, 2.47958, 130391
86: 3.48574e-14, 2.48145e+13, 1, 0.864969, 130392
87: 5.60923e-15, 4.9629e+13, 1, 0.278381, 130392
88: 8.28636e-16, 9.92581e+13, 1, 0.0822488, 130392
89: 1.11726e-16, 1.98516e+14, 1, 0.0221795, 130392
90: 1.36554e-17, 3.97032e+14, 1, 0.00542165, 130392
91: 1.5006e-18, 7.94065e+14, 1, 0.00119157, 130392
92: 1.46797e-19, 1.58813e+15, 1, 0.000233133, 130392
93: 1.26277e-20, 3.17626e+15, 1, 4.0109e-05, 130392
94: 9.40364e-22, 6.35252e+15, 1, 5.97368e-06, 130392
95: 5.93914e-23, 1.2705e+16, 1, 7.5457e-07, 130392
96: 3.0933e-24, 2.54101e+16, 1, 7.8601e-08, 130392
97: 1.27559e-25, 5.08201e+16, 1, 6.48256e-09, 130392
98: 3.90486e-27, 1.0164e+17, 1, 3.96891e-10, 130392
99: 7.88861e-29, 2.03281e+17, 1, 1.6036e-11, 130392
100: 7.88861e-31, 4.06561e+17, 1, 3.2072e-13, 130392So the expected value for this strategy is 130392 times original money, the median/mode is 361 times original money. The chance of losing money is about 4.43%. Since the loss multiplier is half the win multiplier, you double your money for each extra win.
bet, expected value, median, probability you end up with more money than before.
0 exp=1 median=1 probwinmoney=0
0.01 exp=1.64667 median=1.62843 probwinmoney=0.999563
0.02 exp=2.70481 median=2.58804 probwinmoney=0.999563
0.03 exp=4.43205 median=4.0168 probwinmoney=0.999105
0.04 exp=7.24465 median=6.09185 probwinmoney=0.999105
0.05 exp=11.8137 median=9.03264 probwinmoney=0.999105
0.06 exp=19.2186 median=13.1007 probwinmoney=0.998241
0.07 exp=31.1914 median=18.5947 probwinmoney=0.998241
0.08 exp=50.5049 median=25.8399 probwinmoney=0.998241
0.09 exp=81.5885 median=35.1698 probwinmoney=0.996681
0.1 exp=131.501 median=46.9016 probwinmoney=0.996681
0.11 exp=211.469 median=61.3044 probwinmoney=0.996681
0.12 exp=339.302 median=78.563 probwinmoney=0.993984
0.13 exp=543.201 median=98.7393 probwinmoney=0.993984
0.14 exp=867.716 median=121.737 probwinmoney=0.993984
0.15 exp=1383.08 median=147.27 probwinmoney=0.989511
0.16 exp=2199.76 median=174.848 probwinmoney=0.989511
0.17 exp=3491.19 median=203.772 probwinmoney=0.989511
0.18 exp=5529.04 median=233.151 probwinmoney=0.9824
0.19 exp=8738 median=261.942 probwinmoney=0.9824
0.2 exp=13780.6 median=289.002 probwinmoney=0.9824
0.21 exp=21688.4 median=313.164 probwinmoney=0.971556
0.22 exp=34064.2 median=333.315 probwinmoney=0.971556
0.23 exp=53393.3 median=348.481 probwinmoney=0.971556
0.24 exp=83522.3 median=357.903 probwinmoney=0.955687
0.25 exp=130392 median=361.099 probwinmoney=0.955687
0.26 exp=203163 median=357.903 probwinmoney=0.955687
0.27 exp=315927 median=348.481 probwinmoney=0.933395
0.28 exp=490326 median=333.315 probwinmoney=0.933395
0.29 exp=759537 median=313.164 probwinmoney=0.933395
0.3 exp=1.17431e+06 median=289.002 probwinmoney=0.903326
0.31 exp=1.81217e+06 median=261.942 probwinmoney=0.903326
0.32 exp=2.79125e+06 median=233.151 probwinmoney=0.903326
0.33 exp=4.29134e+06 median=203.772 probwinmoney=0.864373
0.34 exp=6.58546e+06 median=174.848 probwinmoney=0.864373
0.35 exp=1.00876e+07 median=147.27 probwinmoney=0.864373
0.36 exp=1.54241e+07 median=121.737 probwinmoney=0.815899
0.37 exp=2.35415e+07 median=98.7393 probwinmoney=0.815899
0.38 exp=3.58671e+07 median=78.563 probwinmoney=0.815899
0.39 exp=5.45495e+07 median=61.3044 probwinmoney=0.757941
0.4 exp=8.2818e+07 median=46.9016 probwinmoney=0.757941
0.41 exp=1.25518e+08 median=35.1698 probwinmoney=0.757941
0.42 exp=1.89905e+08 median=25.8399 probwinmoney=0.69135
0.43 exp=2.86832e+08 median=18.5947 probwinmoney=0.69135
0.44 exp=4.32497e+08 median=13.1007 probwinmoney=0.69135
0.45 exp=6.51042e+08 median=9.03264 probwinmoney=0.617823
0.46 exp=9.78388e+08 median=6.09185 probwinmoney=0.617823
0.47 exp=1.4679e+09 median=4.0168 probwinmoney=0.617823
0.48 exp=2.19871e+09 median=2.58804 probwinmoney=0.539795
0.49 exp=3.28803e+09 median=1.62843 probwinmoney=0.539795
0.5 exp=4.90909e+09 median=1 probwinmoney=0.460205
0.51 exp=7.31767e+09 median=0.598925 probwinmoney=0.460205
0.52 exp=1.08907e+10 median=0.349599 probwinmoney=0.460205
0.53 exp=1.61828e+10 median=0.198726 probwinmoney=0.382177
0.54 exp=2.40089e+10 median=0.109915 probwinmoney=0.382177
0.55 exp=3.55646e+10 median=0.0591004 probwinmoney=0.382177
0.56 exp=5.26014e+10 median=0.0308622 probwinmoney=0.30865
0.57 exp=7.76806e+10 median=0.0156355 probwinmoney=0.30865
0.58 exp=1.14544e+11 median=0.0076763 probwinmoney=0.30865
0.59 exp=1.68646e+11 median=0.00364769 probwinmoney=0.242059
0.6 exp=2.47934e+11 median=0.00167546 probwinmoney=0.242059
0.61 exp=3.63958e+11 median=0.000742812 probwinmoney=0.184101
0.62 exp=5.33494e+11 median=0.000317381 probwinmoney=0.184101
0.63 exp=7.80864e+11 median=0.000130469 probwinmoney=0.184101
0.64 exp=1.14128e+12 median=5.15071e-05 probwinmoney=0.135627
0.65 exp=1.66567e+12 median=1.94892e-05 probwinmoney=0.135627
0.66 exp=2.42753e+12 median=7.05253e-06 probwinmoney=0.096674
0.67 exp=3.53286e+12 median=2.43495e-06 probwinmoney=0.096674
0.68 exp=5.13428e+12 median=8.00017e-07 probwinmoney=0.0666053
0.69 exp=7.45124e+12 median=2.49421e-07 probwinmoney=0.0666053
0.7 exp=1.07988e+13 median=7.35571e-08 probwinmoney=0.0666053
0.71 exp=1.56289e+13 median=2.04488e-08 probwinmoney=0.044313
0.72 exp=2.25887e+13 median=5.33818e-09 probwinmoney=0.044313
0.73 exp=3.26036e+13 median=1.303e-09 probwinmoney=0.028444
0.74 exp=4.69955e+13 median=2.95973e-10 probwinmoney=0.028444
0.75 exp=6.76503e+13 median=6.22302e-11 probwinmoney=0.0176001
0.76 exp=9.72543e+13 median=1.2039e-11 probwinmoney=0.0176001
0.77 exp=1.3963e+14 median=2.12852e-12 probwinmoney=0.0104894
0.78 exp=2.00207e+14 median=3.41297e-13 probwinmoney=0.0104894
0.79 exp=2.86695e+14 median=4.91983e-14 probwinmoney=0.00601649
0.8 exp=4.10019e+14 median=6.312e-15 probwinmoney=0.00601649
0.81 exp=5.85642e+14 median=7.12434e-16 probwinmoney=0.00331856
0.82 exp=8.35432e+14 median=6.97946e-17 probwinmoney=0.00331856
0.83 exp=1.19027e+15 median=5.84155e-18 probwinmoney=0.00175882
0.84 exp=1.69369e+15 median=4.09957e-19 probwinmoney=0.000894965
0.85 exp=2.40706e+15 median=2.35913e-20 probwinmoney=0.000894965
0.86 exp=3.41668e+15 median=1.08355e-21 probwinmoney=0.00043686
0.87 exp=4.84384e+15 median=3.84322e-23 probwinmoney=0.00043686
0.88 exp=6.85882e+15 median=1.01045e-24 probwinmoney=0.000204389
0.89 exp=9.70029e+15 median=1.87014e-26 probwinmoney=9.15716e-05
0.9 exp=1.37025e+16 median=2.27983e-28 probwinmoney=3.92507e-05
0.91 exp=1.9333e+16 median=1.67718e-30 probwinmoney=3.92507e-05
0.92 exp=2.72449e+16 median=6.61327e-33 probwinmoney=1.608e-05
0.93 exp=3.83497e+16 median=1.1836e-35 probwinmoney=6.28958e-06
0.94 exp=5.3918e+16 median=7.5368e-39 probwinmoney=2.34621e-06
0.95 exp=7.57185e+16 median=1.17058e-42 probwinmoney=8.33681e-07
0.96 exp=1.06211e+17 median=2.35582e-47 probwinmoney=9.05001e-08
0.97 exp=1.48815e+17 median=1.87685e-53 probwinmoney=2.75679e-08
0.98 exp=2.0827e+17 median=4.13129e-62 probwinmoney=2.16868e-09
0.99 exp=2.91152e+17 median=5.13823e-77 probwinmoney=1.35138e-10
1 exp=4.06561e+17 median=0 probwinmoney=7.88861e-31The median values are centered around 1/4 and mirrored exactly... which makes sense given the parabolic nature of the median outcome. As harey correctly pointed out, the expected value for the strategy increases with the bet. So if you want to maximize the expected value, bet everything every time.... but the odds of ending up with more than nothing is 1/2^100. Alternatively, the lower the bet the better chance you walk away with more than you started with.
A little more math:
SpoilerMaximizing median outcome for arbitrary probability of winning and win multiplier (rounds drops out of analysis):
m=((1-b)^(r(1-p))) * ((1+wb)^rp)
dm/db = r * ((1-b)^(r(1-p)-1)) * ((1+wb)^(rp-1)) * (wp(1-b)-(1-p)(1+wb))
setting derivative to 0 means we only care about that last bit...
0 = (wp(1-b)-(1-p)(1+wb))
0 = wp-wpb+p+wpb-1-wb
0 = wp+p-1-wb
b = (wp+p-1)/w
For a win probability of 1/2, b=(w-1)/2w. Which is 1/4 when w=2... like the OP.
For win probability of 1/2 and win multiplier of 1, b = 0.
-
It seems my initial guess and idea about how the probabilities would end up were... umm, bad.
Yay code...
Spoiler#include <stdio.h>
#include <stdlib.h>#include <iostream>
#include <fstream>#include <math.h>
#include <cstring> //for memcpyusing namespace std;
const long double third = 1/3.0d;
const long double quarter = 1/4.0d;
const long double fifth = 1/5.0d;long double probs[100];
long double probsnew[100];long double probleft;
long double currenttaken;
long double expect;
int holechecked;
int lasthole;
int daynum;
ofstream *out;void initprobs()
{
probleft = 1;
expect = 0;
daynum = 0;
lasthole = -1;
for(int i = 0; i < 100; i++) probs[i] = .01d;
}void stepprobs()
{
probs[0] *= third;
probs[1] *= quarter;
probs[99] *= third;
probs[98] *= quarter;
for(int i = 2; i < 98; i++) probs[i] *= fifth;
probsnew[0] = probs[0] + probs[1] + probs[2];
probsnew[1] = probsnew[0] + probs[3];
probsnew[2] = probsnew[1] + probs[4];
probsnew[99] = probs[99] + probs[98] + probs[97];
probsnew[98] = probsnew[99] + probs[96];
long double currentprob = probsnew[2];
for(int i = 3; i <= 97; i++)
{
currentprob += probs[i+2] - probs[i-3];
probsnew[i] = currentprob;
}
memcpy(probs,probsnew,sizeof(long double)*100);
daynum++;
}long double checkhole(int holenum)
{
lasthole = holechecked;
holechecked = holenum;
if ((holenum < 0) || (holenum >= 100)) {currenttaken = 0 ; return 0;}
currenttaken = probs[holenum];
probleft -= currenttaken;
probs[holenum] = 0;
expect += daynum * currenttaken;
return currenttaken;
}long double sanitycheck()
{
long double total = probleft;
for(int i = 0; i < 100; i++) total-=probs[i];
return total;
}void printstatus()
{
*out << holechecked << "," << (holechecked-lasthole) << "," << (1-probleft) << "," << probleft << "," << currenttaken << "," << (currenttaken/probleft) << "," << sanitycheck() << "," << expect << ",";
*out << (expect + ((daynum+1)*(probleft))) << ",";
if (currenttaken>0) *out << (expect + ((daynum+((probleft/currenttaken)-1))*probleft)) << ",";
else *out << "inf" << ",";
*out << (expect + (1000000000000*probleft)) << ",";
for(int j = 0; j < 100; j++)
{
*out << "," << probs[j];
}
*out << endl;
if (daynum % 100 == 0) cout << daynum << "," << probleft << "," << (expect + ((daynum+((probleft/currenttaken)-1))*probleft)) << endl;
}void printheaders()
{
*out << "holechecked" << "," << "holediff" << "," << "taken" << "," << "probleft" << "," << "currenttaken" << "," << "currenttaken/probleft" << "," << "probleft error" << "," << "expect" << ",";
*out << "expectmin" << ",";
*out << "expectapprox" << ",";
*out << "expectlarge" << ",";
for(int j = 0; j < 100; j++)
{
*out << "," << "hole " << j;
}
*out << endl;
}int findmax(int mode) //0leftmost,1rightmost,2closest
{
int maxhole = 0;
for(int i = 1; i < 100; i++)
{
if (probs[maxhole] < probs[i]) maxhole = i;
else if (probs[maxhole] == probs[i])
{
switch (mode)
{
case 0://do nothing
break;
case 1:
maxhole = i;
break;
case 2:
if (abs(holechecked-maxhole) > abs(holechecked-i))
maxhole = i;
break;
}
}
}
return maxhole;
}void doday(int hole) {checkhole(hole); printstatus(); stepprobs();}
int main(int argc, char *argv[])
{
ofstream outfile;
outfile.open("output.csv");
out = &outfile;
initprobs();
printheaders();
/* //1000 -- 81.9813
doday(94);
doday(97);
for(int j = 0; j <= 33; j++)
{
for(int i = 2; i <= 14; i+=3) doday(i);
for(int i = 18; i <= 30; i+=3) doday(i);
for(int i = 34; i <= 97; i+=3) doday(i);
}
*/
/* //1000 -- 82.0348
doday(92);
doday(2);
doday(97);
for(int i = 0; i <= 1000; i++)
{
doday(findmax(0));
}
*/
/* //9000 -- 862.492
for(int i = 0; i <= 9000; i++) doday(49);
*/
/* //9000 -- 782.726
for(int i = 0; i <= 4500; i++) {doday(2); doday(97);}
*/
outfile.close();
}My best approach so far...
SpoilerI calculated an expected value for the day to catch the rat for this as about 81.9813 days.
First, check hole 95, then 98. Then, starting with hole 3, check every third hole (moving an extra hole twice... 19 instead of 18, then 35 instead of 34). Go back to hole 3 and begin checking every 3rd hole again with the same modifications, and repeat.My code is 0-based, so add 1 to those if you want the holes numbered 1-100.
doday(94);
doday(97);
for(int j = 0; j <= 33; j++)
{
for(int i = 2; i <= 14; i+=3) doday(i);
for(int i = 18; i <= 30; i+=3) doday(i);
for(int i = 34; i <= 97; i+=3) doday(i);
}It seems we calculate the expected value for the day the rat is found differently.
SpoilerI have that Evilhubert's approach would take 862.492 days. (And my initial guess wasn't much better, at 782.726)
-
Is this just spam? The link at the bottom of that page seems shady.... installyourfiles dot com? No thanks.
It looks another like this was posted recently too. "can anyone out there solve this puzzle?" -- that is also hosted on sites.google.com and goes to getafilenow dot com.
-
Spoiler
Add 1 to the second number, then multiply instead of add.
2 + 5 => 2 * 6 = 12
3 + 6 => 3 * 7 = 21
8 + 11 => 8 * 12 = 96
-
Hey Bob, welcome to the den. It's been a while since I've checked this site.
This puzzle, at first glance, seemed similar to "Groundhog in a Hole." -- http://brainden.com/forum/topic/11943--/
I have posted a couple variations, too. -- http://brainden.com/forum/topic/12010--/ and http://brainden.com/forum/topic/18524-groundhog-in-a-hole-yet-again/
Anyway, I thought I'd ask for some clarification. If the rat is in hole 10 on day 1, does that mean on day 2 it has an equal chance (20% each) of having gone to holes 8, 9, 10 (stayed there), 11, or 12? If the rat is in hole 2 on day 1, on day 2 is there an equal chance (25% each) of being in holes 1, 2, 3, or 4? And a third chance each for holes 1, 2, and 3 if starting right on the edge in hole 1? And does the rat have an equal chance of being in any given hole on day 1 (1% each)? Just thought I'd nail down the way the probabilities move.
Here's a quick guess before checking... anything really...
SpoilerAlternate checking holes 3 and 98.
Holes 3 and 98 are both two away from the edges, and it is where I assume probability of this random walk should accumulate. Alternating might help reduce the impact of reduced probabilities due to repeatedly checking the area. I chose two away from the edge to still have 5 holes that could go to it each day.
-
Alternatively,
Spoilerx,0
(f(x)-f(0))/(3x) = f(0)-11
f(x)-f(0) = 3x * (f(0)-11) = ax, for some constant a.
clearly f(x) is linear.f(x) = ax+b
(f(x+y)-f(xy))/(3x) = f(y/(3x))-11-y
(a(x+y)+b-axy-b)/3x = ay/3x+b-11-y
(ax+ay-axy)/3x = ay/3x +b-11-y
a/3 + ay/3x - ay/3 = ay/3x +b-11-y
a/3 - ay/3 = b-11-y
ay/3 = y since the variable terms must be equal
a = 3
a/3 = b-11
1 = b-11
b=12f(x) = 3x+12
-
Spoiler
1,0
(f(1)-f(0))/3 = f(0)-11
f(1) = 4*f(0)-33-1,0
(f(-1)-f(0))/(-3) = f(0)-11-y
f(-1) = -2*f(0)+33-1,1
(f(0)-f(-1))/(-3) = f(-1/3)-12
f(0)-f(-1) = 36 - 3*f(-1/3)1,-1
(f(0)-f(-1))/(3) = f(-1/3)-10
f(0)-f(-1) = 3*f(-1/3) - 303*f(-1/3) - 30 = 36 - 3*f(-1/3)
6*f(-1/3) = 66
f(-1/3) = 11
f(0)-f(-1) = 3(f(0)-3) = -2*f(0)+33
3*f(0) = 36
f(0) = 12
f(-1) = 9f(1) = 4*(12)-33
f(1) = 48-33 = 15f(x) = 3x+12??
(f(x+y)-f(xy))/(3x) = f(y/(3x))-11-y
(3(x+y)+12 - (3xy+12))/3x = (y/x +12)-11-y
(3x+3y+12-3xy-12)/3x = y/x +1 -y
(3x+3y-3xy)/3x = y/x +1 -y
1+y/x-y = y/x +1 -y
yup.f(x) = 3x+12
-
Spoiler
2f(1/x)-f(x) = 2x/3 (plugging in x/2 for x then adding to this gives original)
f(x) = 2f(1/x) - 2x/3 (rearrange)
f(1/x) = 2f(x) - 2/3x (substitute 1/x for x)
f(x) = 2(2f(x) - 2/3x) - 2x/3 (replace f(1/x) from two above)
f(x) = 4f(x) - 4/3x - 2x/3
3f(x) = 4/3x + 2x/3
f(x) = (2/9)(x+2/x)
-
Spoiler
hf+gh+fg-fh-hg-gf = 26x - 52
hf+gh-fh-hg = 26x - 52
hf-fh = 26x - 52 - 16x + 72 = 10x + 20
2hf = 10x + 20 + 2x^2 + 10x + 30 = 2x^2 + 20x +50
-2fh = 10x + 20 - 2x^2 - 10x - 30 = -2x^2 - 10hf = x^2 + 10x + 25 = (x+5)^2
fh = x^2 + 5seems like...
f(x) = x+5
h(x) = x^2(x + 5) * g(x) = x^2 - 3x - 40
(x + 5) * g(x) = (x-8)*(x+5)
g(x) = x-8check...
fg = x-3 = gf(x^2 + 10x + 25) + g(h(x)) + (x-3) = 2x^2 + 11x + 14
gh = 2x^2 + 11x + 14 - (x^2 + 11x + 22) = x^2 - 8(x^2 + 5) + h(g(x)) + (x-3) = 2x^2 - 15x + 66
hg = 2x^2 - 15x + 66 - (x^2 + x + 2) = x^2 - 16x + 64 = (x-8)^2h(g(x)) - g(h(x)) = -16x + 72
Looks like it checks out.
f(x) = x+5
g(x) = x-8
h(x) = x^2
Lanterns of Eden.
in New Logic/Math Puzzles
Posted
Yeah, that's not a very interesting definition of the state. Try the one I described.
So if the angel and devil are approaching lantern 5, the state would be the state of lantern 5, followed by the state of lantern 6,..., ending with the state of lantern 4.
This would be equivalent to cyclically bit shifting the binary number so the next lantern the angel and devil will visit is at the front.
Say there are 5 lanterns: 1 is on, 2 is on, 3 is off, 4 is off, 5 is off. If the angel and devil are approaching lantern 4, the state is 00110. This is because looking forward from the pair's position they see off,off,on,on,off.