witzar
-
Posts
237 -
Joined
-
Last visited
-
Days Won
7
Content Type
Profiles
Forums
Events
Gallery
Blogs
Posts posted by witzar
-
-
3 hours ago, Evilhubert said:
There's a solution that I find simple and elegant enough to be satisfying
Evilhubert, your solution is exactly the solution I had in mind, congrats on solving! I'm happy that you found the puzzle enjoyable.
-
3 hours ago, k-man said:
These are some trivial and uninteresting examples and I'm not sure how they help.
These trivial examples show that for small values of N (the numbers of lanterns) the Angel wins.
You seem to be claiming that that the Devil wins for larger values of N, and that all it takes is two OFF lanterns that are not adjacent.
So lets analyze the case of three lanterns that are initially OFF, ON, OFF.
If the Devil does not switch the 1st lantern ON, then the Angel switches the 2nd lantern OFF, winning immediately after.
If the Devil switches the 1st lantern ON, the the Angel does not switch the 2nd lantern, and the Devil cannot switch the 3rd lantern as this would lose immediately.
So after the first "pass" the lanterns are in state ON, ON, OFF, and from here the Angel wins by flipping the first two lanterns.
But maybe this case is also "trivial and uninteresting", but then what is the smallest N where the Devil can actually win, and what is the initial state?
-
Let's consider how the game might go for some small numbers of lanterns.
If there is only one lantern, then the Angel wins immediately, regardless of it's state.
If there are two lanterns, then there are four cases (of initial state of the lanterns):
off, off : The Angel wins immediately.
on, on : The Angel wins immediately.
on, off : The Angel switches the first lantern off, and wins immediately after.
off, on : The Devil has a choice what to do with the first lantern. If the Devil switches it on, then he loses immediately after. If the Devil leaves it off, then the Angel switches the second lantern off, and wins immediately after.
-
Please note the Angel has two ways od winning:
1. Turn all lanterns on.
2. Turn all lanterns off.
-
In the Garden of Eden, there is a circular pathway, where the Angel and the Devil enjoy an infinite stroll, walking side by side. There are lanterns placed along the pathway (a finite number of them). Each lantern can be in one of two states: on or off. The Angel, a servant of light, has control over the illuminated lanterns. Whenever they pass such a lantern, the Angel decides whether it remains on or off. Conversely, the Devil, a servant of darkness, has control over the lanterns that are dark, and can change their states as they pass.
To alleviate their boredom, the Angel and the Devil decide to play a game. The Angel's objective is to bring all the lanterns into complete order, winning immediately if either all lanterns are turned on or all lanterns are turned off. To ensure the game eventually concludes, the celestial beings agree that the game ends if the lanterns return to a previously encountered state. In this case, the Devil is declared the winner.Now, the question is: Who will emerge victorious, and what strategy ensures the win?
-
Spoiler
This is correct, Pickett. No "extra" moves are required (obviously we cannot do better, since there are 2n-1 combinations to test).
Comparing this problem to Towers of Hanoi looks like a good insight to me, since both problems are naturally defined with exactly the same recurrence.
I've played a game today where I had to brute-force such lock. I was just testing subsequent binary numbers (thinking of levers as bits), hence I made more moves then optimal. Even after I gave this problem some thoughts, I'd still be afraid to use "optimal procedure", since I feel that the gain in speed is not worth the risk of making a mistake and starting over. -
There are n binary levers: each lever can be in position 0 or position 1.
Exactly one out of 2n possible combinations of levers opens the lock.
The lock opens immediately as soon as each lever is in proper position.
Changing position of one lever is called a move.
Suppose all levers are initially in position 0.
What is the minimal number of moves that guarantees opening the lock?
In other words: how many moves are required to test each position of levers (the worst case scenario)?Can you also describe the optimal procedure of moving the levers?
-
Fibonacci(2n+1)-1
-
For example you can encode MM using first digit except bottom segment (6^2=64>=60),
you just need to agree on some order or the above 6 display elements, so that they represent MM in binary.
(Each element of display is a binary digit "on"=1, "off"=0.)
Same way you can use second digit to encode seconds.
The remaining 4 elements of display (two bottom segments plus two dots) can be used to encode HH (4^2=16>=12).
I don't see any particular ordering that feels natural. -
To display HH:MM:SS in 12-hour format you need ⌈log
2(12*60*60)⌉ = 16 bits of information, but your display has only 15 elements. Therefore the task is impossible if each element can only be "on" or "off". You need to cheat a little bit, for example add blinking or something like that.Edit:
I miscounted the elements:) The display has 16 not 15 of them, so you
can use it without cheating.-
1
-
-
Let:
p = prob. of getting killed
L = value of your life
S = value of the package
Expected value of going to work:
EVW = p*(-L) + (1-p)(500 + 0.2*S)
Expected value of staying home:
EVH = S
You are indifferent to going to work if and only if above EV's are in equilibrium:
EVW = EVH
p*(-L) + (1-p)(500 + 0.2*S) = S
-p*L + 500 + 0.2*S - p*500 - p*0.2*S - S = 0
p = (500 - 0.8*S)/(500 + L + 0.2*S)
Note however, that if (500 - 0.8*S) < 0, then also p<0, but probability can't be negative,
therefore you can't be indifferent to going to work when S > 625 (in such case staying home is always better for every possible value of p). -
Is there a more elegant reasoning to show why that is?
I was analyzing D
n+1-Dn instead of dividing Dn into 6 triangles, but I don't think that it was more elegant -
Well done, gavinksong.
At first counting colors of D
n looks hard for big n. The trick is to realize that all that matters is n mod 3. -
Paint unit hexagons with three colors so that no two hexagons sharing side have the same color (like
this)
and observe then no matter how you place a trimino, it will cover one unit hexagon of each color. -
There are two ways to get exactly four numbers: aaabcd and aabbcd.
First you can get in 6_choose_3*6*5*4*3 ways, and
second you can get in 6_choose_4*3*6*5*4*3 ways,
making total of (6_choose_3+6_choose_4*3)*6*5*4*3 = (20+15*3)*6*5*4*3 = 23400 ways.
We should not accept the bet if 23400/6^6 > 1/2.
It's close, but we are slight underdog, so we reject. -
Recall a classic: When a chessboard with two squares removed can be covered with 2x1 dominoes? The same approach works here.
-
Given definition of diameter of region directly implies, that any disk of radius 1 (diameter 2) and center in region R will contain the whole R, provided diameter of R <=1. Am I missing something?
-
The set of all subsets of a set S is called a power set (powerset) of S.
According to Cantor's theorem, cardinality of the power set of any set S
is strictly greater then cardinality of S.
PS The Schröder–Bernstein theorem was called Cantor–Bernstein theorem at my set theory classes. -
Here is what I found.
F stands for factorial, S for square root.
I didn't use negation, since it doesn't add anything interesting.
Some parentheses are redundant, feel free to ignore them.
(8+(8+8)) F(S((8+(S(8)*S(8))))) F((8/S(S((8+8))))) F((8/F(S(S((8+8)))))) F(S((8*S(S((8+8)))))) F(S((8*F(S(S((8+8))))))) F((8-S((8+8)))) F(S((F(S((8+8)))-8))) F(S((8+S((8*8)))))
-
This puzzle is inspired by posted by bonanova.
Again we work on a hexagonal tiling of a plane, and the question is about
possibility of covering some shape with triminoes.
Trimino is a "triangle" formed by three unit hexagons sharing common vertex.
The shape to cover is defined as follows:
Let's pick a unit hexagon and call it H1.
Now we recursively define Hn+1 as a sum of Hn and all unit hexagons adjacent to Hn.
So basically Hn is a "hexagon" with side of length n (unit hexagons).
Let Dn be Hn with one unit hexagon at it's center removed.
So, can you cover D2015 with triminoes? -
The answer is "no".
Consider those two squares in the center, that - when removed - disconnect the board into two pieces.
Those two squares can be covered either by one or by two dominoes.
In both cases this disconnects the board into two pieces, that cannot be covered by dominoes,
since they have different number of black and white squares.
To see this, first inspect the case with one domino (just count black squares and white squares of the upper piece).
The difference equals 2 in this case.
Now it is easy to realize that replacing the single domino with two dominoes can fix this difference only by 1 (not enough).-
1
-
-
Suppose the bottom-left corner is black (and so are the other corners).
There is one more black square than white,
therefore the remaining square should be black.
The question remains: could it be any black square?
The answer is "yes".
To see this you can draw a path for the lame King (the one that cannot move diagonally),
that visits each square exactly once (there is no requirement for path to be closed this time as in solution to #1).
Removing one black square breaks the path into two segments of even length (only one segment in case when terminal square of the path is removed),
and obviously we can easily cover each segment with dominoes.-
1
-
-
Consider a lame King (chess piece) that cannot move diagonally.
It's easy to draw a closed path for him to inspect all his kingdom:
a closed path that visits each square exactly once (and returns to starting point).
Obviously such path can be covered by dominoes starting from any square,
as well as any continuous segment of this path of even length.
Removing two squares of different color we break the path into two such segments,
so the answer is "yes".-
1
-
-
The answer is "no".
Consider a rook that can only move on black squares.
Let's call "reachable" the squares that can be reached by this rook
(in finite number of moves) from the bottom-left corner.
Only black squares in rows: 1 (bottom), 3, 5, 7 and 9 are reachable.
This accounts to 25 (5*5) reachable squares total.
Now observe that a quadomino, now matter how placed on the chessboard,
always covers an even (0 or 2) number of reachable squares.
But 25 is odd.-
1
-
Lanterns of Eden.
in New Logic/Math Puzzles
Posted
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.