## Search found 114 matches

- Mon Jun 27, 2016 10:43 pm UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1572: "xkcd Survey"
- Replies:
**366** - Views:
**124885**

- Fri Jan 15, 2016 7:25 pm UTC
- Forum: Individual XKCD Comic Threads
- Topic: 1572: "xkcd Survey"
- Replies:
**366** - Views:
**124885**

### Re: 1572: "xkcd Survey"

Maybe Time-style we can release one piece of survey datum every hour...

- Sat Mar 14, 2015 11:13 pm UTC
- Forum: Logic Puzzles
- Topic: Genie and four coins
- Replies:
**4** - Views:
**4646**

### Re: Genie and four coins

And if interested, see discussion of n-coin variant here

- Sat Jan 24, 2015 3:39 pm UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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...

- Tue Jan 06, 2015 3:52 am UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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...

- Sun Jan 04, 2015 1:45 am UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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 ...

- Fri Jan 02, 2015 5:07 pm UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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 ...

- Tue Dec 30, 2014 9:38 pm UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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!

- Tue Dec 30, 2014 9:31 pm UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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....

- Mon Dec 29, 2014 9:12 pm UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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)...

- Mon Dec 29, 2014 8:49 pm UTC
- Forum: Logic Puzzles
- Topic: The infinite suburb and the teleporter breakdown.
- Replies:
**26** - Views:
**7112**

### 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...

- Fri Dec 12, 2014 7:28 pm UTC
- Forum: Fictional Science
- Topic: two planets
- Replies:
**6** - Views:
**6425**

### 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...

- Mon Dec 08, 2014 6:43 pm UTC
- Forum: Logic Puzzles
- Topic: Two immortals are playing Rock, Paper, Scissors
- Replies:
**10** - Views:
**4485**

### 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...

- Mon Dec 01, 2014 3:41 pm UTC
- Forum: Logic Puzzles
- Topic: Toads and flies (solution thread)
- Replies:
**22** - Views:
**10667**

### Re: Toads and flies (solution thread)

Wow. No, it's not. I think I stopped thinking about halfway through the rules. Oops!

- Fri Nov 28, 2014 11:24 pm UTC
- Forum: Logic Puzzles
- Topic: Toads and flies (solution thread)
- Replies:
**22** - Views:
**10667**

### 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...

- Tue Nov 25, 2014 6:16 am UTC
- Forum: Logic Puzzles
- Topic: Genie and Many Coins
- Replies:
**10** - Views:
**4776**

### 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...

- Mon Nov 24, 2014 3:03 pm UTC
- Forum: Logic Puzzles
- Topic: Genie and Many Coins
- Replies:
**10** - Views:
**4776**

### Re: Genie and Many Coins

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

Looks pretty good, though. Nice work, jaap/Nitrodon.

- Sun Nov 23, 2014 3:53 pm UTC
- Forum: Logic Puzzles
- Topic: Genie and Many Coins
- Replies:
**10** - Views:
**4776**

### 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 ...

- Sat Nov 22, 2014 3:52 am UTC
- Forum: Logic Puzzles
- Topic: Random numbers (a mathy puzzle)
- Replies:
**8** - Views:
**3405**

### 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...

- Fri Nov 21, 2014 11:48 pm UTC
- Forum: Logic Puzzles
- Topic: Random numbers (a mathy puzzle)
- Replies:
**8** - Views:
**3405**

### 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 ...

- Fri Nov 21, 2014 2:51 pm UTC
- Forum: Logic Puzzles
- Topic: Toads and flies (solution thread)
- Replies:
**22** - Views:
**10667**

### 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...

- Fri Nov 21, 2014 2:20 pm UTC
- Forum: Logic Puzzles
- Topic: Random numbers (a mathy puzzle)
- Replies:
**8** - Views:
**3405**

### Re: Random numbers (a mathy puzzle)

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

Nice work though, @somehow. Your solution does look good.

- Thu Nov 06, 2014 8:25 pm UTC
- Forum: Logic Puzzles
- Topic: Demonstrating objects are of equal weight
- Replies:
**12** - Views:
**5105**

### 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?

- Thu Nov 06, 2014 8:22 pm UTC
- Forum: Logic Puzzles
- Topic: Balance Scale Variants
- Replies:
**0** - Views:
**2621**

### 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...

- Wed Nov 05, 2014 5:32 pm UTC
- Forum: Logic Puzzles
- Topic: Twelve Steel Balls
- Replies:
**3** - Views:
**2656**

### 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?

- Tue Oct 28, 2014 2:36 pm UTC
- Forum: Logic Puzzles
- Topic: Two guards, two doors, no instructions
- Replies:
**63** - Views:
**16747**

### 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:**

- Tue Oct 28, 2014 2:33 pm UTC
- Forum: Logic Puzzles
- Topic: Two guards, two doors, no instructions
- Replies:
**63** - Views:
**16747**

### 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...

- Fri Oct 17, 2014 5:22 pm UTC
- Forum: Logic Puzzles
- Topic: Scratch it
- Replies:
**8** - Views:
**3158**

### 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.

- Fri Oct 17, 2014 5:14 pm UTC
- Forum: Logic Puzzles
- Topic: Scratch it
- Replies:
**8** - Views:
**3158**

### 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.

- Fri Oct 17, 2014 2:03 pm UTC
- Forum: Logic Puzzles
- Topic: Scratch it
- Replies:
**8** - Views:
**3158**

### 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 ...

- Fri Oct 17, 2014 2:00 pm UTC
- Forum: Logic Puzzles
- Topic: Scratch it
- Replies:
**8** - Views:
**3158**

### 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...

- Tue Sep 30, 2014 5:07 am UTC
- Forum: Logic Puzzles
- Topic: Emulating a die roll with a weighted coin
- Replies:
**7** - Views:
**3375**

### 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...

- Tue Sep 30, 2014 4:57 am UTC
- Forum: Logic Puzzles
- Topic: Emulating a die roll with a weighted coin
- Replies:
**7** - Views:
**3375**

### 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...

- Tue Sep 30, 2014 4:28 am UTC
- Forum: Logic Puzzles
- Topic: Emulating a die roll with a weighted coin
- Replies:
**7** - Views:
**3375**

### 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.

- Tue Sep 30, 2014 4:23 am UTC
- Forum: Logic Puzzles
- Topic: Eulerian paths in infinite graphs?
- Replies:
**15** - Views:
**6531**

### 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.

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.

- Sat Sep 27, 2014 3:01 am UTC
- Forum: Logic Puzzles
- Topic: Emulating a die roll with a weighted coin
- Replies:
**7** - Views:
**3375**

### 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...

- Sat Sep 27, 2014 2:29 am UTC
- Forum: Logic Puzzles
- Topic: Eulerian paths in infinite graphs?
- Replies:
**15** - Views:
**6531**

### 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.

- Sat Sep 27, 2014 1:22 am UTC
- Forum: Logic Puzzles
- Topic: Eulerian paths in infinite graphs?
- Replies:
**15** - Views:
**6531**

### 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...

- Fri Sep 26, 2014 2:44 pm UTC
- Forum: Logic Puzzles
- Topic: Eulerian paths in infinite graphs?
- Replies:
**15** - Views:
**6531**

### 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...

- Fri Sep 26, 2014 5:33 am UTC
- Forum: Logic Puzzles
- Topic: Emulating a die roll with a weighted coin
- Replies:
**7** - Views:
**3375**

### 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...