## Search found 114 matches

Mon Jun 27, 2016 10:43 pm UTC
Topic: 1572: "xkcd Survey"
Replies: 366
Views: 131500

### Re: 1572: "xkcd Survey"

Fri Jan 15, 2016 7:25 pm UTC
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...
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
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...
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...
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 ...
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 ...
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!
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....
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)...
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...
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...
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...
Mon Dec 01, 2014 3:41 pm UTC
Forum: Logic Puzzles
Replies: 22
Views: 11078

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
Replies: 22
Views: 11078

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: 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...
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.
Booo!

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: 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 ...
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...
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 ...
Fri Nov 21, 2014 2:51 pm UTC
Forum: Logic Puzzles
Replies: 22
Views: 11078

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: 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.
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?
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...
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?
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."
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...
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.
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.
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 ...
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...
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...
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...
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.
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.
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...
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.
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...
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...`
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...