Posts posted by witzar
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?
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 ⌈log2(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.
I miscounted the elements:) The display has 16 not 15 of them, so youcan use it without cheating.
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 Dn+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 Dn 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 (likethis)
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).
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.
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".
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.
Let s(t) be the distance Alice covers in time 't'.
We assume s(t) is a continuous and differentiable function of 't' - a reasonable assumption: Since Alice can't disappear and appear in a different spot in zero time (implying infinite speed), and can't instantaneously change her speed to a completely different value (implying infinite acceleration).
This is exactly what meant by the last sentence of my answer:
The question remains: is it possible to run like this?
I'd also add one more condition: s(0)=0, since the runners start moving when the the race starts.
Same restrictions should also apply to Bob,
so another question is: how can he run with a constant positive speed?
Obviously he can't without braking his speed function at 0.
Alice could run fast for 0.2 mile then slow for the rest of the first mile,
and repeat this pattern for the whole marathon.
This way her pace is constant on every 1-mile segment.
Now, after 26 miles of the race she is 26 seconds behind Bob,
and she is going to run fast on remaining 0.2 mile segment of the race.
If she runs fast enough the fast segments, she wins.
The question remains: is it possible to run like this?
Just brute force.
@witzar: what was your approach?
There are five solutions:
a=[0, 1, 1, 2, 2, 3] b=[2, 4, 5, 6, 7, 9]
a=[0, 1, 2, 3, 4, 5] b=[2, 3, 4, 5, 6, 7]
a=[0, 2, 3, 4, 5, 7] b=[2, 3, 3, 4, 4, 5]
a=[1, 2, 2, 3, 3, 4] b=[1, 3, 4, 5, 6, 8]
a=[1, 2, 3, 4, 5, 6] b=[1, 2, 3, 4, 5, 6]
How about saying "smaller" with probability (1/2)+(1/2)^n (where n is the number Victor sees)?
This is incorrect.
If at least one of m or n is odd, player 1 wins. First he removes middle line, then do actions symmetrical to player 2's actions with the removed line.
Consider 3*3 for example. After player 1 removes middle line, player 2 removes some line perpendicular to line just removed, leaving player 1 with 2*2.
This is correct.
if m and n both even, player 2 wins. Every move player 1 make, player 2 make symmetrical move with center point.
in New Logic/Math Puzzles
Posted · Edited by witzar
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.