Search found 114 matches

by ekim
Mon Jun 27, 2016 10:43 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 1572: "xkcd Survey"
Replies: 366
Views: 131500

Re: 1572: "xkcd Survey"

:(
by ekim
Fri Jan 15, 2016 7:25 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 1572: "xkcd Survey"
Replies: 366
Views: 131500

Re: 1572: "xkcd Survey"

Maybe Time-style we can release one piece of survey datum every hour...
by ekim
Sat Mar 14, 2015 11:13 pm UTC
Forum: Logic Puzzles
Topic: Genie and four coins
Replies: 4
Views: 4992

Re: Genie and four coins

And if interested, see discussion of n-coin variant here
by ekim
Sat Jan 24, 2015 3:39 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

You're right, that gives us <=4 for (almost) everything else, but Nitrodon already gave us 3 everywhere and I was hoping to show 2 almost everywhere (though as you can see it's looking pretty ugly) TBH I was hoping to show the opposite, to just find infinitely many that needed at least 3 hops, but t...
by ekim
Tue Jan 06, 2015 3:52 am UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

I can keep you stuck at the origin, but it will involve disabling quite a few teleporters. As n^2 gets big, the difference between consecutive squares (n+1)^2-n^2 also gets big. So for a given leg length, there's an upper bound on the length of the other leg if we're going to have an...
by ekim
Sun Jan 04, 2015 1:45 am UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

(0,k) can be reached in two hops for all k>2. The solution, though encouraging, isn't terribly enlightening. I've still no idea about the rest of our lattice. For k odd use the m,n,n+1 triples: (2k-1,2k(k-1),2k(k-1)+1) and (2k+1,2k(k+1),2k(k+1)+1) but ...
by ekim
Fri Jan 02, 2015 5:07 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

(1,1) can be done with (-20,21) (21,-20) (0,2) can't be done in 2 hops the two hops will look like (a,-b), (-a,b+2) a^2+b^2=c^2; a^2+(b+2)^2=(c+k)^2 k>2 means c<b, and k=2 gives c=b, so k=1 but (b+2)^2-b^2 = 4b+4 is even, and (c+1)^2-c^2=2c+1 is odd I ...
by ekim
Tue Dec 30, 2014 9:38 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

Lopsidation wrote:Also, solved ekim's "every house exactly once" problem.

[...]

So, modulo working out annoying details, this algorithm works.

ALARMINGLY HAND-WAVEY, but it looks good to me.
Wasn't at all expecting a non-constructive 'yes' answer!
by ekim
Tue Dec 30, 2014 9:31 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

Got Nitrodon's variant in three hops for odd,even destination, four hops for odd,odd and for even,even - and by looking at primitive triples mod 4 (the legs are always (1 or 3,0)) you can see that (2,2) can't be done in fewer than 4. (Not sure about odd,odd. Conceivable that we could do this in two....
by ekim
Mon Dec 29, 2014 9:12 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

Again, Nitrodon's Primitive Pythagorean Teleporter variant, <= 6 hops to arbitrary (a,b). I suspect (hope!) we can improve on this, but I haven't so far been able to. For this solution we'll just be hopping along Pythagorean triples of the form m,n,n+1 (2x+1, 2x(x+1), 2x(2x+1)...
by ekim
Mon Dec 29, 2014 8:49 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7518

Re: The infinite suburb and the teleporter breakdown.

disallow any teleports which pass directly through another teleporter I've got a solution for Nitrodon's variant in <=10 hops, but I think we can do better... 12 + 4 - 15 = 1 5 + 3 - 8 = 0 So Cradarc gives us a method where three hops will shift us an arbitrary 1-distance. This is useful. For any v...
by ekim
Fri Dec 12, 2014 7:28 pm UTC
Forum: Fictional Science
Topic: two planets
Replies: 6
Views: 6650

Re: two planets

This leads us to the central problem of getting into orbit: Reaching orbital speed takes much more fuel than reaching orbital height. I'm curious whether a big space station like this (i.e. non-insignificant percentage of Earth's mass) would make it more or less difficult to ferry things between th...
by ekim
Mon Dec 08, 2014 6:43 pm UTC
Forum: Logic Puzzles
Topic: Two immortals are playing Rock, Paper, Scissors
Replies: 10
Views: 4673

Re: Two immortals are playing Rock, Paper, Scissors

Assumption: I don't care what happens to my opponent. I just know that losing is an outcome to be avoided at all costs. (so lose-lose is just as bad from my perspective as lose-win) What do our strategies look like when we each have just one stone remaining? If we each have one stone remaining, bein...
by ekim
Mon Dec 01, 2014 3:41 pm UTC
Forum: Logic Puzzles
Topic: Toads and flies (solution thread)
Replies: 22
Views: 11078

Re: Toads and flies (solution thread)

Wow. No, it's not. I think I stopped thinking about halfway through the rules. Oops!
by ekim
Fri Nov 28, 2014 11:24 pm UTC
Forum: Logic Puzzles
Topic: Toads and flies (solution thread)
Replies: 22
Views: 11078

Re: Toads and flies (solution thread)

Probably haven't thought this all through.. start facing straight ahead in any direction (call this 0 degrees) turn 90 degrees right JUMP if closer - divide previous rotation degrees (90) by 2 (to get 45) and turn the opposite direction (so 45 degrees left) - JUMP if...
by ekim
Tue Nov 25, 2014 6:16 am UTC
Forum: Logic Puzzles
Topic: Genie and Many Coins
Replies: 10
Views: 5035

Re: Genie and Many Coins

Actually, the number of steps for the n=4 puzzle is constant no matter what, as described in the thread linked in the OP. After exactly 7 steps, every n=4 sub-puzzle will be all one side. This is not true. The simplest(?) way to see this is to look at parity: an even number of coins flipped preserv...
by ekim
Mon Nov 24, 2014 3:03 pm UTC
Forum: Logic Puzzles
Topic: Genie and Many Coins
Replies: 10
Views: 5035

Re: Genie and Many Coins

jaap wrote:The tricky bit is proving that it works, so I'll leave that as an exercise. :D
Booo!

Looks pretty good, though. Nice work, jaap/Nitrodon.
by ekim
Sun Nov 23, 2014 3:53 pm UTC
Forum: Logic Puzzles
Topic: Genie and Many Coins
Replies: 10
Views: 5035

Genie and Many Coins

I saw a generalization of this problem a few weeks ago. I've got an inkling about the answer, but nothing too solid yet. You are seated at a circular table. In front of you are n coins, equally spaced around the edge of the table, all showing heads. In a moment you will be blindfolded, a Genie will ...
by ekim
Sat Nov 22, 2014 3:52 am UTC
Forum: Logic Puzzles
Topic: Random numbers (a mathy puzzle)
Replies: 8
Views: 3529

Re: Random numbers (a mathy puzzle)

Greedy method: flip until there are enough outcomes to cover our die. Eat those. Flip again (to double remaining outcomes) until there are enough to cover. Repeat. So for k=5 we flip three times (8 outcomes), and eat five. Flip once more (six outcomes now - the three we had left over from before, do...
by ekim
Fri Nov 21, 2014 11:48 pm UTC
Forum: Logic Puzzles
Topic: Random numbers (a mathy puzzle)
Replies: 8
Views: 3529

Re: Random numbers (a mathy puzzle)

I can certainly come up with decent methods of emulating a k-sided die with coin-flips, but don't know how to even begin to show that one is optimal. I'm feeling a little frustrated here - maybe someone can help me out: With a totally unbiased coin, I had imagined that the 'natural' conversion to a ...
by ekim
Fri Nov 21, 2014 2:51 pm UTC
Forum: Logic Puzzles
Topic: Toads and flies (solution thread)
Replies: 22
Views: 11078

Re: Toads and flies (solution thread)

I've always assumed that ptveite meant that you weren't allowed to sort-of-triangulate by building a hierarchy of jumps, sorting them from closest to least close. This would be a much more sophisticated frog than one we've discussed, and your two-state-machine frog would be much simpler. I suppose y...
by ekim
Fri Nov 21, 2014 2:20 pm UTC
Forum: Logic Puzzles
Topic: Random numbers (a mathy puzzle)
Replies: 8
Views: 3529

Re: Random numbers (a mathy puzzle)

Qaanol wrote:@somehow, that is indeed optimal.
So - are we just taking your word for that?

Nice work though, @somehow. Your solution does look good.
by ekim
Thu Nov 06, 2014 8:25 pm UTC
Forum: Logic Puzzles
Topic: Demonstrating objects are of equal weight
Replies: 12
Views: 5325

Demonstrating objects are of equal weight

Given N objects drawn from pools of objects with two distinct weights, how many balance-scale tests are required to show that they're actually all the same weight?
by ekim
Thu Nov 06, 2014 8:22 pm UTC
Forum: Logic Puzzles
Topic: Balance Scale Variants
Replies: 0
Views: 2699

Balance Scale Variants

Oh boy, we've seen a lot of weighing-things problems over the ages. I got sick of wading through them to figure out if I'm a duplicate, and it seemed like maybe it would be good to collect them all in one place. Here's a small attempt with my new one up front. Let me know if I'm missing any (or if a...
by ekim
Wed Nov 05, 2014 5:32 pm UTC
Forum: Logic Puzzles
Topic: Twelve Steel Balls
Replies: 3
Views: 2734

Re: Twelve Steel Balls

Do we have the variant where they're drawn from a set of balls with two different weights; now how many pan-balance tests are required to show that they're actually all the same weight?
by ekim
Tue Oct 28, 2014 2:36 pm UTC
Forum: Logic Puzzles
Topic: Two guards, two doors, no instructions
Replies: 63
Views: 17613

Re: Two guards, two doors, no instructions

Oh, ha. I had actually assumed Xeno's bracketed [setup] part of the answer was much more explicit. Now it occurs to me it probably wasn't meant to be:

Spoiler:
"I'm the liar, she's the truth-teller, and that door will get you to freedom. I hate you."
by ekim
Tue Oct 28, 2014 2:33 pm UTC
Forum: Logic Puzzles
Topic: Two guards, two doors, no instructions
Replies: 63
Views: 17613

Re: Two guards, two doors, no instructions

Or is the question whether they can keep their own identities ambiguous while making the scenario (one liar, one truth-teller, one door each) unambiguous? "I always tell the truth, he always lies, and this problem is only interesting if the doors don't go to the same place so you can probab...
by ekim
Fri Oct 17, 2014 5:22 pm UTC
Forum: Logic Puzzles
Topic: Scratch it
Replies: 8
Views: 3247

Re: Scratch it

The topological component means that we're not a poset game (Chomp is), but I think Sprague-Grundy should still apply. It only really cares that things are symmetric between the two players.
by ekim
Fri Oct 17, 2014 5:14 pm UTC
Forum: Logic Puzzles
Topic: Scratch it
Replies: 8
Views: 3247

Re: Scratch it

Goahead52 wrote:A turn (except the first one) is 2 steps

Thanks, that clears it up. And sorry - looks like my example didn't even describe a valid sequence of events.
by ekim
Fri Oct 17, 2014 2:03 pm UTC
Forum: Logic Puzzles
Topic: Scratch it
Replies: 8
Views: 3247

Re: Scratch it

Also, winning condition is slightly ambiguous: Say I'm the last person to play, I choose a square with the number '4' in it, and then scratch the final two open squares on the board. Have I won (by being the last to make a legal move, scratching those two squares) or have I lost (by being unable to ...
by ekim
Fri Oct 17, 2014 2:00 pm UTC
Forum: Logic Puzzles
Topic: Scratch it
Replies: 8
Views: 3247

Re: Scratch it

Homework? This one ( chomp is, I think, the classic example) is nice because it's fairly easy to answer the question you asked ( Does a winning strategy exist? ) without worrying about finding such a strategy (harder!). I imagine that any such strategy would be heavily de...
by ekim
Tue Sep 30, 2014 5:07 am UTC
Forum: Logic Puzzles
Topic: Emulating a die roll with a weighted coin
Replies: 7
Views: 3461

Re: Emulating a die roll with a weighted coin

just going nuts extracting die rolls out of the entropy that we would otherwise throw away on the retries This is a great idea. To generalize only slightly what you've said: on a 3H1T or 1H3T throw we pull two bits out (location of the 1 H/T) for an unbiased bit sequence. We then use whatever cleve...
by ekim
Tue Sep 30, 2014 4:57 am UTC
Forum: Logic Puzzles
Topic: Emulating a die roll with a weighted coin
Replies: 7
Views: 3461

Re: Emulating a die roll with a weighted coin

I'm feeling a little frustrated here - maybe someone can help me out: With a totally unbiased coin, I had imagined that the 'natural' conversion to a six-sided die (where we take the flips to be a binary sequence <1 where the nth flip adds 1/2^n to our total, divide our [0,1] interval into sixths, a...
by ekim
Tue Sep 30, 2014 4:28 am UTC
Forum: Logic Puzzles
Topic: Emulating a die roll with a weighted coin
Replies: 7
Views: 3461

Re: Emulating a die roll with a weighted coin

notzeb wrote:Some what shockingly, the easier problem of trying to extract an unbiased coinflip from a biased coin with unknown bias in the fewest expected flips has been proven to have no optimal solution. Check out this paper: http://projecteuclid.org/euclid.aop/1176993384.


Oof. Brutal.
by ekim
Tue Sep 30, 2014 4:23 am UTC
Forum: Logic Puzzles
Topic: Eulerian paths in infinite graphs?
Replies: 15
Views: 6794

Re: Eulerian paths in infinite graphs?

Nice induction on the complete-naturals-graph.

Another infinite-degree vertex graph with an Euler path would be a slightly modified star, where for vertices Z, 0 is connected to everyone, and -x is connected to x. Lots of triangles around zero.
by ekim
Sat Sep 27, 2014 3:01 am UTC
Forum: Logic Puzzles
Topic: Emulating a die roll with a weighted coin
Replies: 7
Views: 3461

Re: Emulating a die roll with a weighted coin

So I had a truly excellent algorithm. My plan was simple: just keep flipping the coin until you get four consecutive tosses with two heads and two tails among them. There are six ways to order 2 and 2, all equally likely even with our weighted coin. Done. The expected number of tosses seemed a littl...
by ekim
Sat Sep 27, 2014 2:29 am UTC
Forum: Logic Puzzles
Topic: Eulerian paths in infinite graphs?
Replies: 15
Views: 6794

Re: Eulerian paths in infinite graphs?

I was thinking that this might be a nicer definition for infinite e.path -- a map from either N or Z to vertices that hits each edge once.
by ekim
Sat Sep 27, 2014 1:22 am UTC
Forum: Logic Puzzles
Topic: Eulerian paths in infinite graphs?
Replies: 15
Views: 6794

Re: Eulerian paths in infinite graphs?

Yakk's third example, three copies of the naturals joined at zero has exactly one vertex of odd degree (do I understand you right, that this is a counterexample of the type you were looking for?): A-- B_1 - B_2 - ... |\- C_1 - C_2 - ... \-- D_1 - D_2 - ... And this is sort of a stupid / tautological...
by ekim
Fri Sep 26, 2014 2:44 pm UTC
Forum: Logic Puzzles
Topic: Eulerian paths in infinite graphs?
Replies: 15
Views: 6794

Re: Eulerian paths in infinite graphs?

Quite right. And the second half isn't true either (to borrow your example for a moment):

Code: Select all

  o---o---o---o...
  |\  |\  |\  |...
  | o | o | o |...
  |  \|  \|  \|...
  o---o---o---o...
by ekim
Fri Sep 26, 2014 5:33 am UTC
Forum: Logic Puzzles
Topic: Emulating a die roll with a weighted coin
Replies: 7
Views: 3461

Emulating a die roll with a weighted coin

This is given as an 'easier bonus question' from this thread , but it doesn't look like it ever got answered (and more importantly, it looks interesting to me) so I'm re-asking it. What's an algorithm that efficiently (i.e. smallest expected flip count, not smallest max flip count) emulates a fair s...

Go to advanced search