## Re: Friday Puzzler!

1

The cards are all picked randomly, right?

Let's assume that we have a canonical ordering of the 52 cards. There are 4! = 24 ways to order the four drawn cards. (And you'll distinguish among these arrangements using the canonical ordering; all that matters is that the cards don't have any repeat values, which they won't.) That's surely enough possibilities to encode a binary search of the remaining 48 cards, hence uniquely specifying what the fifth card is.

Posted by: dalriata | Link to this comment | 11- 7-14 3:07 PM
2

Of course, that whole 24/48 things makes it look like you're missing a bit.

Posted by: dalriata | Link to this comment | 11- 7-14 3:08 PM
3

This one actually isn't surprising to me, there's enough information in four cards that I figure you could uniquely identify a fifth, no problem. I mean, the answer is going to be something clever that I'm not going to come up with, but if I wanted to spend hours on it I could probably come up with a set of rules. (Things like: if the first and second cards are the same suit, then that's the suit of the fifth card as well. If the first and second are different, then the fifth is the same as the third card. Not that those specifically are the rules you'd want, but like that.)

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:09 PM
4

Yes. Picked randomly. But I don't see how the 24 different ways of ordering allow you to distinguish among 48 possibilities no matter what you call it.

But your framing is certainly more directly to the point on how to view the problem than the path I started down when I first heard it.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 3:12 PM
5

1: The missing information, you can probably make up for by choosing which of the five drawn cards is going to be the secret one.

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:12 PM
6

5: You guys did right on top of this one.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 3:13 PM
7

+get

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 3:14 PM
8

All I know is the answer has to be something about slavery.

Posted by: peep | Link to this comment | 11- 7-14 3:18 PM
9

The pidgeonhole principle says at least two cards will be the same suit, so there should be an easy way to communicate the suit regardless of what's drawn.

Posted by: Eggplant | Link to this comment | 11- 7-14 3:19 PM
10

Jennifer Anniston!

Posted by: CharleyCarp | Link to this comment | 11- 7-14 3:19 PM
11

You don't have to encode for 48 cards -- you throw away one card to encode the suit of the chosen card, then you have three cards in order to encode 12 choices -- which you can't do simply, since 3! == 6, so you have to reduce the space further.

I don't want to say more because I've already encountered this puzzle, I think in a Martin Gardner column.

Posted by: snarkout | Link to this comment | 11- 7-14 3:20 PM
12

I've been trying to decide if this one requires "all" of the information or not. Including the card to guess there are 120 different ways to order them which makes it seem as if there is far more info than you need--but I'm not sure if that is the correct way to quantify it. So meta-problem has been more interesting than the problem.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 3:21 PM
13

It's a fun puzzle (I hadn't seen it before). I hadn't quite gotten to 11.1, but I was thinking in that direction.

Posted by: NickS | Link to this comment | 11- 7-14 3:21 PM
14

Wow, didn't even have time to walk to the bus. Yeah, 5 and 9 get it. Use the ordering of the four cards to reduce it to two cards that are identical except for color (pair higher red suit w/ higher black suit, forget their names). But make sure the card you show is a red one.

Posted by: dalriata | Link to this comment | 11- 7-14 3:23 PM
15

Repeat that slower? I'm probably capable of understanding it, but I don't.

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:25 PM
16

Err, I mean the card to be guessed is known a priori to be red.

Posted by: dalriata | Link to this comment | 11- 7-14 3:25 PM
17

Can't be. You could draw all black cards.

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:26 PM
18

If no one beats me to it, I'll write up an attempt at a complete solution when I'm home since my coherence decreases when I'm on my phone.

Posted by: dalriata | Link to this comment | 11- 7-14 3:27 PM
19

You're right. Shoot.

Posted by: dalriata | Link to this comment | 11- 7-14 3:31 PM
20

So, you've got the numbers one through six, and the suit. How about; if the shown suit card is a seven or less, the secret card is smaller, if it's an eight or more, the secret card is greater. I think that gets it uniquely.

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:31 PM
21

No, that breaks down on the two matching cards being a seven and an eight. Six or less, the secret card is smaller, nine or more, the secret card is greater, eight means seven and seven means eight.

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:33 PM
22

No, that breaks down on the two matching cards being a seven and an eight. Six or less, the secret card is smaller, nine or more, the secret card is greater, eight means seven and seven means eight.

Nice!

Posted by: NickS | Link to this comment | 11- 7-14 3:34 PM
23

No, that still doesn't work. I'm close, but I need to fuss with it.

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:34 PM
24

Okay, right, that doesn't work if your cards are, say, 10 & 2.

But it seems like you're close.

Posted by: NickS | Link to this comment | 11- 7-14 3:35 PM
25

So if the matching cards are a two and a ten (of hearts, say), how do you indicate that?

Posted by: snarkout | Link to this comment | 11- 7-14 3:36 PM
26

Pwned!

Posted by: snarkout | Link to this comment | 11- 7-14 3:36 PM
27

That has to be the best pwnage I've ever managed.

Posted by: NickS | Link to this comment | 11- 7-14 3:39 PM
28

I'm sure what I am calling "require all the information" is equivalent to some mathematical principle.

As an example somewhere in the archives is a discussion (ah, here it is) between James and I on taking a "12-ball 3-weighings find the heavy/light ball" problem where there are 27 outcomes to cover 24 possibilities and realizing there are ways to make a "harder" problem by adding a ball and another condition (no ball is heavy or light) which requires all 27 possible outcomes.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 3:40 PM
29

24, 25: Hmm, in my "solution" email to heebie for that type of example I used 2 and Jack. Almost the same cards.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 3:43 PM
30

Given a canonical ordering of the cards, one can define a canonical ordering of the permutations of any four cards. There are 24 such permutations, so there's more than enough information. You can also communicate the results of a coin flip.

Posted by: Eggplant | Link to this comment | 11- 7-14 3:49 PM
31

Now I want to see if I can do something with high/low. Use the 1-6 to code pairs (that is, 1 means ace or 2, 2 means 3 or 4, and so on, leaving out the shown suit card), and then the only information I need to get out of the shown suit card, beyond the suit is high or low in the indicated pair.

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:50 PM
32

And that doesn't even factor in your ability to choose the mystery card.

Posted by: Eggplant | Link to this comment | 11- 7-14 3:50 PM
33

30: I don't follow. Again, slower?

Posted by: LizardBreath | Link to this comment | 11- 7-14 3:52 PM
34

30: But you can't have total freedom in the ordering of the 4 and retain the suit information you gained.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 3:52 PM
35

I want to say it's something like if there are N red cards and 5-N black cards, pick a {red,black} card to be special based on a function of N, but I always get two cases that look the same. So close.

Posted by: dalriata | Link to this comment | 11- 7-14 3:54 PM
36

I've also tried things like "pick the card with the lowest value" or "pick the card with the middle value" but there are still hands you can be dealt that won't make that good enough.

Posted by: dalriata | Link to this comment | 11- 7-14 3:55 PM
37

34: I dropped the requirement that you use a whole card to communicate the suit.
33: Say you and your confederate have agreed on an ordering of the deck (Hearts Ace, Hearts One, ..., Spades Queen, Spades King, or something). Now say you put four cards on the table in some order. You and your confederate can assign a number (1 through 4) to each of those cards without any communication and still be confident that you've both ranked them the same.

Posted by: Eggplant | Link to this comment | 11- 7-14 4:06 PM
38

Right, dalriata said that in the first comment. I'm not following what you're adding to that.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:08 PM
39

37 cont.: The order you place the cards then will make some permutation of the numbers 1 through 4. One can also order all permutations, starting with (1,2,3,4), then (1,2,4,3), etc. There are 24 such permutations, so by choosing the order you can communicate a number between 1 and 24.

Posted by: Eggplant | Link to this comment | 11- 7-14 4:08 PM
40

38 also to 39. You've got a number between 1 and 24, and you're trying to communicate a number between 1 and 48. Without an additional trick, I think you're still shy.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:09 PM
41

34: I dropped the requirement that you use a whole card to communicate the suit.

But that was efficient, it allowed one card to cut the space by 1/4, whereas just using that card as a bit of information would only double the possibilities that can be defined.

Posted by: NickS | Link to this comment | 11- 7-14 4:09 PM
42

Oops, you're right.

Posted by: Eggplant | Link to this comment | 11- 7-14 4:10 PM
43

39: yes. But you have 48 possibilities.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:10 PM
44

pwned by LB.

Posted by: NickS | Link to this comment | 11- 7-14 4:10 PM
45

41: It doesn't work, but you did get more than a bit from adding the card.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:11 PM
46

A card is not just a bit.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:12 PM
47

41: Actually, I don't know if it was efficient. With a suit-card, we know the suit, but we only have three remaining cards, which give us (by placing them in order, and then doing the permutation) numbers 1-6. Without the suit card, we had (four cards in order, permuted) 1-24. That looks like a tie to me, rather than a gain in efficiency.

We only make a profit on the suit card if we can get the suit and one more bit out of it.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:12 PM
48

Re 41.first, it's exactly the same in terms of the search space, but it makes the problem more comprehensible as a human being.

Posted by: snarkout | Link to this comment | 11- 7-14 4:15 PM
49

So with four cards, you have two ways of choosing a number 1 through 12. I feel this is significant.

Posted by: Eggplant | Link to this comment | 11- 7-14 4:16 PM
50

Really, puzzlers on a Friday afternoon are unfair.

Posted by: Eggplant | Link to this comment | 11- 7-14 4:16 PM
51

Actually I think I'm wrong about 48.

Posted by: snarkout | Link to this comment | 11- 7-14 4:20 PM
52

For each choice of mystery card, you can communicate the face value in one of two ways, for a total of 10 possibilities.

Posted by: Eggplant | Link to this comment | 11- 7-14 4:22 PM
53

We only make a profit on the suit card if we can get the suit and one more bit out of it.

We get higher/lower (whichever one you choose). That doesn't cut it in half, but it reduces the possibilities.

Can you use odd/even somehow?

Posted by: JRoth | Link to this comment | 11- 7-14 4:24 PM
54

I might be wrong (obviously. I find this kind of puzzle fascinating, but I'm not good at them), but I think it's what I said in 47; that if the suit card is just the suit card, it doesn't change things, but if you can get the suit plus one more bit from the suit card, you're golden.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:24 PM
55

It's also been tempting to always pick as special the lowest card. If we say in our order that all red cards are higher than all black cards, and our search based on the permutation gets it down to one black and one red card, that will always work *except* in the case where four red cards are shown. Then the lowest card could be a red card lower than the lowest shown, or any black card. Bah.

It's annoying to have *almost* a bit of information.

Posted by: dalriata | Link to this comment | 11- 7-14 4:26 PM
56

54 to 48/51.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:26 PM
57

53/55: Yeah, there are a whole bunch of things I can think of that will almost always work.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:28 PM
58

I can't get odd/even to work, because you can't count on having either to work with (that is, your matching cards could be both even, both odd, or mixed).

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:29 PM
59

I have to go drive for five hours, but now I have something to think about. Fun!

Posted by: dalriata | Link to this comment | 11- 7-14 4:29 PM
60

LB is both right and (wrong) in 54.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:30 PM
61

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:31 PM
62

Well, hold on, how many possible pairs are there? Can we make a rule about which one goes down first that narrows the possibilities? E.g., if you put show a 2, the other card must be 3, 5, 7, 9, Q, A; if your pair is a 2 and another even card, you show the other even.

I can't figure out if that's workable.

Posted by: JRoth | Link to this comment | 11- 7-14 4:32 PM
63

Can the people involved be unionists instead of confederates?

Posted by: Lord Castock | Link to this comment | 11- 7-14 4:35 PM
64

59: Ha! When I first heard the "half or double money in the envelope" problem (Friday Puzzler discussion here from 2008) I immediately left on a similar length drive. I was concentrating on the problem so much that I did not notice the fuel gauge and ran out of gas on I-86 near Jamestown, NY.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:35 PM
65

No, because they're dishonest tricksters.

Posted by: JRoth | Link to this comment | 11- 7-14 4:36 PM
66

64 is hilarious (and a bummer).

Posted by: JRoth | Link to this comment | 11- 7-14 4:36 PM
67

Really, puzzlers on a Friday afternoon are unfair.

I'm actually being productive at work right now. Which, annoyingly, means I can't think about the puzzle as much as I'd like.

Posted by: NickS | Link to this comment | 11- 7-14 4:37 PM
68

But then it would make sense that they're smart enough to solve the puzzle.

Posted by: Lord Castock | Link to this comment | 11- 7-14 4:37 PM
69

68 to 65.

Posted by: LC | Link to this comment | 11- 7-14 4:37 PM
70

You have the freedom to choose a number 1 to 120. Your confederate will learn the remainder of that number modulo 24. Choose the number so that it is equal to its remainder.

Posted by: Eggplant | Link to this comment | 11- 7-14 4:39 PM
71

Okay, the matching suit cards are a draw of two from the numbers 1 through 13, which if I'm right are 15 pairs where both are even, 15 where both are odd, and 48 where they're mixed.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:41 PM
72

It was on a Friday night as well. On a college visit with my daughter (to the school she did end up attending).

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:41 PM
73

71 gets me nowhere.

Posted by: LizardBreath | Link to this comment | 11- 7-14 4:43 PM
74

A hint or maybe just further frustration to chew on while I drive home.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 4:51 PM
75

Got it, I think. In rot13 to avoid spoilers:

Svefg pneq vf gur fnzr fhvg nf gur uvqqra pneq. Erznvavat guerr pneqf rapbqr n ahzore bar gb fvk. Vs gur fhz bs gur enaxf bs gur erznvavat pneqf vf rira, nqq gur ahzore lbh trg gb gur fhvg pneq (jenccvat nebhaq sebz X gb N) gb trg gur uvqqra pneq, vs gur fhz bs gur enaxf vf bqq, fhogenpg gur ahzore vafgrnq. Rvgure gur cbfvgvir be artngvir qvssrerapr jvyy or jvguva fvk. Hfr gur fhz bs gur enaxf bs gur erznvavat pneqf gb qrgrezvar juvpu bs gur gjb fnzr-fhvgrq pneqf lbh cvpx gb uvqr.

Posted by: Dave W. | Link to this comment | 11- 7-14 5:30 PM
76

And that seems to fit with Stormcrow's hint, so I'm pretty sure that's the idea.

Posted by: Dave W. | Link to this comment | 11- 7-14 5:33 PM
77

70: Hello modulo our old friend,
We've com to speak with you again...

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 5:33 PM
78

Since you have five choices of mystery card, and for each mystery card there is a permutation that leaves you one bit shy of specifying it, signal the color of the mystery card by the color of the first card. There is always at least one way of doing this because there are four possibilities of combinations (rr,rb,br,bb) and five choices.

Posted by: Eggplant | Link to this comment | 11- 7-14 5:33 PM
79

+e

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 5:33 PM
80

75: Yes, I think that works, although there is what I think is a more straightforward way to apply the key principle.

... and rot13 in and of itself is a pretty good hint.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 5:35 PM
81

Help! How do I get my iPhone to stop displaying a particular name under "recent"?

Posted by: Engelbert Dollfuss | Link to this comment | 11- 7-14 5:37 PM
82

64 is great.

Posted by: heebie-geebie | Link to this comment | 11- 7-14 5:41 PM
83

Turning a card over allows you to use each card as a binary bit. You can encode a number up to 16 with four cards, the suit of the first card turned over is the suit of the hidden card. The resultant binary number is the value of the card. In the corner case of all 5 being from the same suit, you just arrange it so the fifth is a number you can encode by turning one card over.

Posted by: Asteele | Link to this comment | 11- 7-14 5:43 PM
84

83 violates the original condition: "The other person then correctly deduces what the fifth card is purely from the sequence of the cards turned over (no tricks with timing or whatnot)". Using the orientation of the cards (and not all cards are asymmetric anyway) would violate this.

Posted by: Dave W. | Link to this comment | 11- 7-14 5:48 PM
85

I got it! The 5th card is always the 5 of diamonds.

Posted by: JRoth | Link to this comment | 11- 7-14 5:51 PM
86

75, 80: Pubbfr lbhe "fhvg cnve" n naq o. Gurl ner thnenagrrq gb or jvguva 6 bs rnpu bgure pbhagvat zbqhyb 13. Rapbqr gung qvfgnapr naq chg gur pneq sebz juvpu lbh pbhag "hc" nf gur bar fubjvat naq gur bgure nf gur uvqqra pneq.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 5:53 PM
87

Perhaps we don't *have* to turn all 4 hinting cards over.

First card tells us the suit; 12 possibilities left in that suit.

3 cards my left-to-right; turn the 1st one and it's in the low value 3rd of the 12, middle in the middle 3rd, etc.

Two cards and four possibilities left; choice of card now reduces it to two possibilities, as in previous step.

If I turn over the last one, it's the lower-value of the two, if I don't turn it over, the higher-value. I believe this is now a halting problem and am off for tea with Achilles.

--

Oh ho I think I got there. I'm assuming we can't re-order the five cards dealt, just peek and turn them over. Well, of the two that match in suit -- teh first one over, and to-be-guessed -- if the first one over is on the left, the guessed is the lower-value of the possibilities at the end there, otherwise the higher-value.

Posted by: clew | Link to this comment | 11- 7-14 5:53 PM
88

Oh, I'm sorry, I should have refreshed and then I'd have rot-13d too.

Posted by: clew | Link to this comment | 11- 7-14 5:55 PM
89

87: As presented, you can re-order, and must turn over all of the cards. Your variant might be interesting to look at.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 5:56 PM
90

...gratified to see that our solutions aren't superficially alike, though.

Posted by: clew | Link to this comment | 11- 7-14 5:57 PM
91

I was assuming 87, I can choose to turn over a card or not.

I'll think a bit.

Posted by: Asteele | Link to this comment | 11- 7-14 5:58 PM
92

89: Hey, parse me the OP and say where it says we can re-order. Also, I think 87.last solves the whole thing, where's the whole?

Posted by: clew | Link to this comment | 11- 7-14 5:58 PM
93

-w

I should type more slowly

Posted by: clew | Link to this comment | 11- 7-14 5:58 PM
94

The re-order or not is actually irrelevant if you must turn over all the cards--the order you turn them over in is what matters. It does look like that works if you do not have to turn them all over--added the extra bit by choice of turn over the last card or not.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 6:05 PM
95

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 6:06 PM
96

Ha! 64 is great. I will strive to pay more attention to my gas gauge.

I've tried lots of modular arithmetic but nothing quite works, and the Somerset rest area doesn't have a rot13 decoder.

Posted by: dalriata | Link to this comment | 11- 7-14 6:06 PM
97

92.1: The other person then correctly deduces what the fifth card is purely from the sequence of the cards turned over

If you were just turning over four random cards in the random order they were dealt, there'd be no information at all passed on beyond "The hidden card isn't one of these four." For the information to be in the sequence, the sequence must have been chosen deliberately.

And ah, to 87. It's interesting, using modulo really isn't in my mental vocabulary, and it's clearly useful in these kinds of information-passing puzzles. I was beating my head against "But how do you tell which one's bigger", and that solves it neatly.

Posted by: LizardBreath | Link to this comment | 11- 7-14 6:09 PM
98

I meant ah to 86.

Posted by: LizardBreath | Link to this comment | 11- 7-14 6:10 PM
99

64 was also facilitated by what I consider a minor design flaw in what was a relatively new car at the time (thanks in-laws!). The individual gauges were set relatively deeply in the dash. In my natural sitting position the gas gauge was barely visible to me so I had to remember to tilt my head down a bit to look at it.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 6:11 PM
100

I'm now not at all sure that one can get enough information out of choosing which of the matching-suit cards to turn over, if one can't decide what order to lay them out in. If one can, no problem.

Posted by: clew | Link to this comment | 11- 7-14 6:11 PM
101

the problem in 100 is what 75 solves so nicely, duh.

Posted by: clew | Link to this comment | 11- 7-14 6:16 PM
102

97.2: I just use the clock metaphor. In this case it basically reduce to "it's always within a half hour of being on the hour."

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 6:18 PM
103

97.2: two uses of `order': the physical order on the table, probably the deal order, vs. the order in which player 1 turns them over.

Blithering: I couldn't get into _Ready Player One_ at all; went through the whole thing thinking God, my generation will consume *any nostalgia at all*. Defender of novel said well, sure, the Boomers have been doing it to us for decades, our turn; and I said well look what it's done to them! Then we realized we were surrounded by Boomers, fortunately not particularly nostalgic ones, and stopped.

Posted by: clew | Link to this comment | 11- 7-14 6:19 PM
104

100: I think I understand you now, and you can only turn them over in order, not rearrange them too. (That is, I think you're envisioning having four physical locations on the table, A-D, and being able to turn the cards over in order, 1-4, so you could deal your first card into slot C, coding it as 1C, your second into A, coding it as 2A, and so on. No, you only get to transmit the temporal order they were flipped in, not an additional distinct spacial order as well.)

Posted by: LizardBreath | Link to this comment | 11- 7-14 6:20 PM
105

102: I understand it fine when someone explains it, I just don't reach for it as a tool -- I would have been beating my head on how to get that last bit out of the suit card for ages, and I don't think modulo would have occurred to me without help. This is one of those things where I remember there's a finite number of tricks, and you just have to keep on picking them up.

Posted by: LizardBreath | Link to this comment | 11- 7-14 6:23 PM
106

103.2: Oddly, Newt picked that up and is loving it, which seems bizarre to me -- I haven't read it yet, but I thought, as you said, it was marketed as Gen X nostalgia.

Posted by: LizardBreath | Link to this comment | 11- 7-14 6:24 PM
107

106: It's also Boy Finds Hands and gamer success fantasy. Much less weird for an actual teen or tween to enjoy.

Posted by: clew | Link to this comment | 11- 7-14 6:27 PM
108

102: What I meant was I tend to use the actual clock visualization in my head while searching for a solution, modulo itself is generally too abstract for me to reason further about. But just referencing "modulo" in explanations is more confusing and status-enhancing parsimonious.

But yes, it is basically a trick in the tool bag.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 6:30 PM
109

103, 106, 107: I found it a compelling quick read (and it was one of my kids who gave it to me to read when they were finished). Basically just one element was stupidly annoying to me.

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 6:34 PM
110

Am I totally misunderstanding or don't the two confederates have to be working together for this to work? The setup of the problem seemed to imply that Confederate A was trying to trick Confederate B.

Posted by: urple | Link to this comment | 11- 7-14 7:00 PM
111

If they're not cooperating, I think it would be true in every sense that A holds all the cards. (Also, what else does 'confederate' mean?)

Posted by: LizardBreath | Link to this comment | 11- 7-14 7:02 PM
112

Yes they are working together. It would be a trick if presented to an implied observer(s).

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 7:06 PM
113

Okay, well that's less impressive. I thought Confederate B was supposedly using this method to get the correct answer regardless of what A did, which didn't seem possible.

Posted by: urple | Link to this comment | 11- 7-14 7:09 PM
114

I've heard that Austin Grossman's YOU: A Novel is like a better version of Ready Player One.

Posted by: snarkout | Link to this comment | 11- 7-14 7:19 PM
115

111: I thought he was just seeing the scene by making the two characters Lost Causers. (Joke has already been made, don't care)

Posted by: dalriata | Link to this comment | 11- 7-14 7:25 PM
116

I just decoded 75. AWESOME!

Posted by: dalriata | Link to this comment | 11- 7-14 7:28 PM
117

I guess I should've rot13'd 78, but (a) I was on my phone and (b) I trust that my normal writing is indecipherable enough.

Posted by: Eggplant | Link to this comment | 11- 7-14 7:30 PM
118

What do you mean by signal in 78? That your first card and the hidden card will have the same color? I'm not convinced that you can always do that, but I don't have an easy proof either way.

Posted by: dalriata | Link to this comment | 11- 7-14 7:34 PM
119

What do you mean by signal in 78? That your first card and the hidden card will have the same color? I'm not convinced that you can always do that, but I don't have an easy proof either way.

Posted by: dalriata | Link to this comment | 11- 7-14 7:34 PM
120

The solution doesn't work if the selected cards are 4 aces and a joker.

Posted by: Spike | Link to this comment | 11- 7-14 7:35 PM
121

Joker?

Posted by: JP Stormcrow | Link to this comment | 11- 7-14 7:42 PM
122

There are 4! = 24 ways to order the four drawn cards.

Can't you get to 5! = 120 by adjusting the placement of the final card? Like, if you line them up on the table, and the card remaining down is the second card in the line, vs. being the fourth card in the line, that positioning also communicates information.

That gets you enough bandwidth to have room for the joker, and also that card with the advertising on it. It would also work for the 108 cards of an Uno deck.

Posted by: Spike | Link to this comment | 11- 7-14 7:50 PM
123

Yeah, you gotta count the joker. It comes in the box, doesn't it?

That's the kind of requirement which is never in the spec, but you can't assume its not there or your system is liable to crash at the worst possible time.

Posted by: Spike | Link to this comment | 11- 7-14 7:55 PM
124

Are there jokers in MS Solitaire?

Posted by: clew | Link to this comment | 11- 7-14 8:04 PM
125

119: I thought I had a proof... (c) Incompetence.

Posted by: Eggplant | Link to this comment | 11- 7-14 8:05 PM
126

Ooh ooh by talking it out in person at Snark (who as you know knew the solution already) I got there! You'll be pleased when you do.

Posted by: redfoxtailshrub | Link to this comment | 11- 7-14 8:10 PM
127

A somewhat different solution:

Jvgu sbhe pneqf fubjvat, gurer ner 48 cbffvovyvgvrf sbe gur ynfg pneq. Jr unir 4!=24 crezhgngvbaf va juvpu jr pna cerfrag bhe pubfra sbhe. Gurersber jr bayl arrq bar zber ovg bs vasbezngvba gb anvy qbja gur haghearq pneq. Abgvpr gung rira jura jr'ir svkrq gur crezhgngvba jr'yy hfr, jr fgvyy unir pbzcyrgr serrqbz nf gb juvpu sbhe bs gur svir jr erirny. Gura gur rkgen ovg jr pbzzhavpngr pna or jurgure gur ragver unaq vf nyy gur fnzr pbybe, juvpu jr pna trg npebff ol sbyybjvat gur ehyr gung vs vg'f cbffvoyr gb erirny pneqf bs obgu pbybef, jr qb fb. (Vs nyy gur erirnyrq pneqf ner gur fnzr pbybe, vg pna or vasreerq gung gur svsgu vf gung pbybe nf jryy.)

Posted by: lambchop | Link to this comment | 11- 7-14 8:12 PM
128

Are there jokers in MS Solitaire?

Yes, but you never see one. Every time it comes up, you get a Blue Screen of Death.

Posted by: Spike | Link to this comment | 11- 7-14 8:13 PM
129

Oh I see that you are now all hashing out different versions of the solution anyway.

Posted by: redfoxtailshrub | Link to this comment | 11- 7-14 8:15 PM
130

Just for fun, here's how I'd explain it, rot-13:

Gurer jvyy nyjnlf or ng yrnfg gjb pneqf va gur bevtvany frg bs svir gung funer n fhvg. Gur pneq-neenatvat pbasrqrengr pna pubbfr gurfr nf gur pneq gb or thrffrq naq gur svefg pneq va gur frdhrapr bs sbhe. Gur svefg pneq jvyy guhf fvtany gur fhvg bs gur pneq gb or thrffrq.

Gura gurer ner 6 crezhgngvbaf cbffvoyr sbe gur erznvavat frg bs guerr (nffhzvat lbh'ir beqrerq gur fhvgf): ybj-zvqqyr-uvtu, ybj-uvtu-zvqqyr, zvqqyr-ybj-uvtu, rgp. Nffvta rnpu n ahzore sebz bar gb fvk naq zrzbevmr gung.

Gur fhvg-fvtanyvat pneq naq gur pneq gb or thrffrq ner thnenagrrq gb or fvk be srjre pneqf ncneg ba gur "pybpx" bs enaxf. Qrpvqr nurnq bs gvzr jvgu lbhe pbasrqrengr gung lbh'er pbhagvat "pybpxjvfr" (hc naq nebhaq, vs lbh jvyy). Fvtany gur qvfgnapr jvgu gur bgure guerr pneqf naq pubbfr sbe gur fhvg-fvtanyvat pneq juvpurire bs gur gjb vf gur "ybjre" be "yrsgjneq" pneq npebff gung fubegre tnc.

Posted by: redfoxtailshrub | Link to this comment | 11- 7-14 8:28 PM
131

78 doesn't quite work, I think. It's true that by the appropriate choice of permutation you can specify the mystery card up to one bit's worth of ambiguity. But it's not true that you can always arrange for that ambiguity to correspond to the color of the mystery card.

Put differently: You communicate an extra bit of information by the color of the card. But that bit doesn't
necessarily encode the bit of information necessary to complete identification of the mystery card.

Here's a proof: The solution space contains 48 cards. By choice of permutation we reduce the search space to a two-element set. Equivalently, we can partition the original 48-element search space into 24 pairs, and eliminate all but one pair via choice of permutation. Can we always arrange for that pair to contain cards of different colors? That requires that we can always arrange for the 48 element search space to contain equal numbers of red and black cards. But we can only do that if the color split of our five-card hand is 3/2.

Posted by: lambchop | Link to this comment | 11- 7-14 8:32 PM
132

That your first card and the hidden card will have the same color? I'm not convinced that you can always do that, but I don't have an easy proof either way.

Without the jokers, and when player 1 can choose which card is the card to guess, the pigeonhole principle does this: there are four suits (holes) and five cards (pigeons), so there must be at least one hole with two pigeons in it.

Posted by: clew | Link to this comment | 11- 7-14 8:39 PM
133

I now realize my 127 suffers from essentially the same flaw described in 131.

What's crucial is that it's not enough to communicate one bit of information beyond the choice of permutation. We also have to have freedom of choice as to whether we send a 0 or a 1 for that bit.

Posted by: lambchop | Link to this comment | 11- 7-14 8:46 PM
134

On further reflection, 133 isn't quite right (I hope I'm not being tedious). What's necessary and sufficient for a solution is that the information we communicate in the extra bit be guaranteed to partition the 48-element search space into two equally-sized subsets. Having freedom of choice in what bit we send is clearly sufficient for that (we can adopt whatever convention we like about the meaning of 0 and 1 in that case), but I don't see why it might be necessary. In any case, neither of the schemes proposed in 78 and 127 is sufficient.

Posted by: lambchop | Link to this comment | 11- 7-14 9:51 PM
135

Without having read the thread, I feel like this problem is either trivial or impossible. It's trivial in the sense that there is clearly enough information in the order in which the cards are turned over that the two confederates can agree in advance on a mapping from that ordering to cards, however they like, and use it. It's impossible if they're not allowed to discuss this mapping in advance and we're to think there is some obviously preferred canonical choice.

Posted by: essear | Link to this comment | 11- 7-14 10:03 PM
136

61 to 135.

Posted by: teofilo | Link to this comment | 11- 7-14 10:07 PM
137

The idea is: what, specifically, would be a good system to set up with your confederate to make this work? I didn't find it trivial. I'm not sure whether this is a matter of essear is extra snappy at analysing this sort of thing or a matter of essear didn't catch all the constraints.

Posted by: redfoxtailshrub | Link to this comment | 11- 7-14 10:09 PM
138

there is clearly enough information in the order in which the cards are turned over that the two confederates can agree in advance on a mapping from that ordering to cards

This is wrong, for information-theoretic reasons that have been touched on multiple times in the thread.

Posted by: lambchop | Link to this comment | 11- 7-14 10:34 PM
139

Here's a bodge for a pack with jokers in it: if you get a joker, turn it up first, which is the signal to your confederate to trip over the table and either restart the game or give the punters their money back.

Posted by: clew | Link to this comment | 11- 7-14 10:35 PM
140

It kind of annoying me that the canonical numbering of permutations isn't intuitive. My brain wants to treat it like a numeral system, but it's just not. Is there a name for encoding a number as a permutation?

Posted by: Yawnoc | Link to this comment | 11- 7-14 11:00 PM
141

139: If I scratch my nose and turn the third card sideways, the secret card is the rules of the game/advertisement for other Bicycle products card.

Posted by: dalriata | Link to this comment | 11- 7-14 11:04 PM
142

140: This appears to do that, but I'm too addled to make sense of it.

Posted by: dalriata | Link to this comment | 11- 7-14 11:10 PM
143

142: That at least affirms how counter-intuitive the encoding is.

Posted by: Yawnoc | Link to this comment | 11- 7-14 11:15 PM
144

143: definitely. Thinking about permutations is weird and even showing that they can be represented as series of transpositions is hard. But counting them is easy.

Posted by: dalriata | Link to this comment | 11- 7-14 11:26 PM
145

I thought 70 had been sufficient to crack the case, but I think it (that is, the thing I thought of) fails for the reasons lambchop identified in 131. And I should sleep.

Posted by: nosflow | Link to this comment | 11- 8-14 12:35 AM
146

137 I'm not sure whether this is a matter of essear is extra snappy at analysing this sort of thing or a matter of essear didn't catch all the constraints.

138 This is wrong, for information-theoretic reasons that have been touched on multiple times in the thread.

Skimming the thread a little, I guess the difference is that I assumed you can place the five cards on the table in any order you like, so that the position of the unturned card carries information. I see that it's trickier if you assume the order is fixed, because then superficially you can only distinguish 24 things. You could always put information in how you turn the cards over: do you flip from the left side, the right side, the top, the bottom? But maybe that isn't what we're supposed to be looking for either.

Posted by: essear | Link to this comment | 11- 8-14 6:09 AM
147

No, the information transmitted is only in the sequence of cards revealed. Nothing about physical positioning, nothing about timing other than the order (no pauses). What Confederate B has to work from is an ordered list of four cards, nothing else.

Posted by: LizardBreath | Link to this comment | 11- 8-14 6:17 AM
148

Okay. So somehow the extra information has to come from your choice of which one of the five cards to leave unturned, and the tricky part is figuring out how to encode something useful in that choice. At least now I understand that the puzzle is neither trivial nor impossible.

Posted by: essear | Link to this comment | 11- 8-14 6:22 AM
149

Also the table is glass and confederate B has mirrors on his shoes.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:43 AM
150

Magicians are the best at upskirts.

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:44 AM
151

Also they're allowed to talk.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 7:03 AM
152

And set fires.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 7:04 AM
153

It's interesting, I read the puzzle and thought it was as unambiguous as one could possibly imagine for something written in colloquial English (or, to be precise, I read it and didn't spend a moment thinking about ambiguities and loopholes). "Purely from the sequence of the cards turned over" seemed to me to be enough to exclude anything about physical positioning or timing.

I guess I'm not sure exactly what's interesting about that, other than that I'm surprised it wasn't a universal reaction, but it clearly wasn't, and I wonder what that kind of reaction means about approaches to puzzles generally.

Posted by: LizardBreath | Link to this comment | 11- 8-14 7:05 AM
154

Have I mentioned that Jammies took all three kids to Kansas for the weekend? My goal is not to talk to anyone for three days.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 7:05 AM
155

That is the best. In the Peace Corps, I used to get the occasional holiday weekend when the students would go home to their families, and so would the other teachers, and I would have the whole school compound to myself, just me and the pack of feral dogs. It was awesome.

Posted by: LizardBreath | Link to this comment | 11- 8-14 7:26 AM
156

Does it work without feral dogs?

Posted by: Moby Hick | Link to this comment | 11- 8-14 7:33 AM
157

Seems to be!

Posted by: heebie-geebie | Link to this comment | 11- 8-14 7:43 AM
158

I basically see this as a bandwidth problem, and I think the ambiguity of the rules allows for quite a bit of room to maneuver.

In theory, if you added another layer of encoding based on the rotation of the cards as you put them down, you could have enough bandwidth to spell out "QUEEN OF HEARTS" in ASCII. But this really only works if your confederates are autistic savants.

Posted by: Spike | Link to this comment | 11- 8-14 7:48 AM
159

The feral dogs added a certain frisson.

Posted by: LizardBreath | Link to this comment | 11- 8-14 7:57 AM
160

154 sounds amazing. I would like to be the parent who gets to stay home while the other takes three children somewhere, but it doesn't work like that here. (Kansas is even an option! I'll talk up the greatness of Jammies and see if it gets me anywhere, I guess.)

Posted by: Thorn | Link to this comment | 11- 8-14 8:00 AM
161

Sorry, that came out bitchier than it should have been. I signed on for this and I know the deal.

Posted by: Thorn | Link to this comment | 11- 8-14 8:02 AM
162

This is the second time this has happened since Hawaii was born. The last time was about three years ago. It's so much more refreshing than going off on a weekend by yourself, although Jammies feels the opposite way. It's really magical.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 8:04 AM
163

159: I'm going to leave that fruit on the ground.

Posted by: Moby Hick | Link to this comment | 11- 8-14 8:06 AM
164

Next to the peanut butter?

Posted by: heebie-geebie | Link to this comment | 11- 8-14 8:07 AM
165

158 - Let's rephrase the problem. Alice and Bob are confederates in a union of stage magical tricksiness. They pick a volunteer, Carol, at random from the audience. Carol is not colluding with them in any way. Bob leaves the room. Carol chooses five cards from a fair deck of 52 cards (no jokers). Alice keeps one of the cards and hands the other four back to Carol in a specified order, then leaves the room. Bob returns. Carol reads Bob the names of the four cards she was handed (in the same order). Bob then names the card Alice is holding.

Posted by: snarkout | Link to this comment | 11- 8-14 8:15 AM
166

153: Yeah, probably a better way to put it would be something like: A perfectly innocent volunteer picks five cards of her choice (excluding jokers or those other junk cards) from a perfectly fair deck. From that set of five, confederate A picks one card to put in an envelope and puts the other four cards in whatever order she likes. Then she hands the four cards to the volunteer, who reads them aloud in order. This is sufficient to give confederate B the information she needs to guess the card in the envelope. The confederates have the opportunity to collude beforehand, but the only new information B has to work from once the volunteer gets involved is the identity and order of those four cards.

Posted by: redfoxtailshrub | Link to this comment | 11- 8-14 8:18 AM
167

Oh, hello.

Posted by: redfoxtailshrub | Link to this comment | 11- 8-14 8:18 AM
168

Posted by: heebie-geebie | Link to this comment | 11- 8-14 8:20 AM
169

We are in a union of stage magical tricksiness. Like little hobbit Houdini Wobblies.

Posted by: snarkout | Link to this comment | 11- 8-14 8:22 AM
170

Bob & Carol & Feral Dogs & Alice

Posted by: Moby Hick | Link to this comment | 11- 8-14 8:25 AM
171

Do Dallas

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 10:08 AM
172

JP, you are responsible for me having to go in to work today to make sure the process I was rushing to launch yesterday is working properly. I was getting close, but losing focus and getting fatigued, when you posted this damnable thing.

Posted by: Eggplant | Link to this comment | 11- 8-14 12:05 PM
173

I'm here for you, Eggplant.

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 12:10 PM
174

Ok, we need to test this for real. You are my confederates.

52 cards, no jokers. Ace is worth 1 and king is worth 12 [ed: he means 13]. Assume the suits are ranked clubs (lowest), followed by diamonds, hearts, and spades. So a 4 of hearts is considered "higher" than a 4 of diamonds, but a 5 of clubs beats both of them.

I will pick 5 cards. The first card in this list will be the same suit as the mystery card. Take the value of this as the base value.

For the next three cards, pay attention to the order - low (L), medium(M), or high(H).

If the order is LMH, add 1 to the base value.
If the order is LHM, add 2.
If the order is MLH, add 3.
If the order is MHL, add 4.
If the order is HLM, add 5.
If the order is HML, add 6.

You will now know the suit and value of the card.

Ok, I'm picking some cards now from a real deck.... are you ready?

3 of Hearts
Ace of Clubs (remember, Ace is low)
Queen of Clubs
Seven of Diamonds

What is the fifth card?

Posted by: Spike | Link to this comment | 11- 8-14 2:14 PM
175

And another one:

10 of Diamonds
10 of Hearts
8 of Hearts

Write you answer of the back of a five dollar bill and mail it to....

Posted by: Spike | Link to this comment | 11- 8-14 2:18 PM
176

5 of hearts, 8 of spades.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 2:22 PM
177

Yup. You and me should go card counting in Vegas.

Posted by: Spike | Link to this comment | 11- 8-14 2:24 PM
178

First I'm going to teach my daughters how to make some money off their classmates.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 2:25 PM
179

153: the people who jump to "they're using mirrors!" have been exposed to the wrong type of puzzles, that's all. They just need to meet the right puzzlemaster to find happiness. Cue a remix of "Hold On, We're Going Home", starring Martin Gardner as Drake.

Posted by: torque | Link to this comment | 11- 8-14 2:26 PM
180

3 of Hearts,
7 of Clubs,
6 of Diamonds

Ogged should write an app for this.

Posted by: Spike | Link to this comment | 11- 8-14 2:28 PM
181

It kind of annoying me that the canonical numbering of permutations isn't intuitive. & the rest of 140 & 142, I must be missing something, because given a known number of elements, it seems to me that the only thing that makes having a canonical numbering of permutations difficult is deciding whether permutation #1 is the one where they're all increasing or where they're all decreasing (assuming they're all distinct).

Posted by: nosflow | Link to this comment | 11- 8-14 2:36 PM
182

180: 8 of hearts. I hope somebody here is around later this afternoon to play confederate when I show this to the girls.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 2:47 PM
183

8 of hearts it is.

No idea if I'll be around or not. I might.

Posted by: Spike | Link to this comment | 11- 8-14 3:13 PM
184

OP. Sorry, this was an outsourced Google interview. You all fail. Fortunately Heebie and Stormcrow still get paid.

103 et al. A friend of mine, who was present at the creation for most of the "puzzles" in Ready Player One said "It's unbelieveable that no one figured these out in the first couple of weeks."

I once (actually, twice) did the Tomb of Horrors D&D module, which is key to RPO, and so I got that one in no time. I know Zork as well so that one was easy, too.

It should have had something actually hard, like the last point in original Adventure.

Posted by: DaveLMA | Link to this comment | 11- 8-14 5:34 PM
185

153, 165, 166: Thanks for providing more unambiguous versions. Something I struggle with on these puzzles, which I tend to have heard and told in person in a give-and-take fashion. Really liked (and still like) doing that on logic puzzles and the like with my kids. (A game I'd recommend as kids get old enough is Crack the Case which has that kind of flow--never played it myself, but the kids enjoyed the hell out of it.) And actually I like seeing the different interpretations and approaches although I know the vagueness can annoy some folks (hi teo!).

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 5:43 PM
186

The need for 165, 166 type of setup reminds me of the various cheating scandals in tournament bridge. Unsurprising given so many subtle ways humans can signal information. And probably sometime not even consciously.

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 5:50 PM
187

And I am somewhat similarly reminded of something from a juggling class I took. I was OK, and had a fair number of basic 3-ball variations but nothing much beyond that. However, my "best" trick was being able to juggle with my eyes closed. So I mentioned that to the guy teaching the class and he did a whole thing on see-through blindfolds and all the ways to make look like you can;t see, but you can. I just liked juggling with them closed. (It is one of the best, most "zen-like" physical things I've done--the balls just plop gently into your hands and you lose all sense of them actually going through the air, very relaxing. Although I never got to where I could keep it up for a really significant length of time--a minute or so of it was great.)

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:07 PM
188

Okay, they're here. Anyone available to be a confederate?

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:14 PM
189

Sure, now that I've read Spike's rules.

Posted by: ydnew | Link to this comment | 11- 8-14 6:21 PM
190

Awesome. ydnew, meet Maura and SiobhÃ¡n, M & S, meet ydnew. I'll have them draw five, and then I'll put down the four.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:22 PM
191

Hi, girls.

Posted by: ydnew | Link to this comment | 11- 8-14 6:24 PM
192

9 of clubs
8 of hearts
Queen of hearts
5 of hearts

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:28 PM
193

I'm a confederaspectator.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:28 PM
194

10 of clubs!

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:29 PM
195

I'm an idiot! Hang on.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:30 PM
196

Uh, keep confederaspectating.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:30 PM
197

King of clubs.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:30 PM
198

"That's creepy."

Once more?

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:31 PM
199

It's my destiny to be the king of clubs.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:31 PM
200

The guesses are coming from inside the house!

Posted by: Eggplant | Link to this comment | 11- 8-14 6:32 PM
201

A race...

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:32 PM
202

I've noticed none of the examples so far seem to have wrapped.

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:33 PM
203

Sure, have at it!

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:33 PM
204

5 of clubs
4 of clubs
9 of clubs

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:34 PM
205

And I assume in Spike's rules, king is actually 13 not 12.

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:34 PM
206

King of clubs?

Posted by: ydnew | Link to this comment | 11- 8-14 6:34 PM
207

That was my silliness in 194 - I was acting as if the ordering had to start at 9 and wrap.

Posted by: heebie-geebie | Link to this comment | 11- 8-14 6:34 PM
208

205: Yes, that's why I was a little slow on the draw.

Posted by: ydnew | Link to this comment | 11- 8-14 6:35 PM
209

206 is pwned but correct.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:35 PM
210

6 of clubs

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:35 PM
211

210 is correct. "That's interesting."

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:36 PM
212

You guys were supposed to wait with the correct guesses until M&S had put money on the table.

Posted by: Eggplant | Link to this comment | 11- 8-14 6:37 PM
213

One of the girls has an itch behind her left ear.

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:37 PM
214

Sorry! Didn't refresh before posting while I was counting on fingers (9, 10, 11, . . . )

Not everyone has fancy math degrees. If I can do it, they can do it.

Posted by: ydnew | Link to this comment | 11- 8-14 6:38 PM
215

Hi it's SiobhÃ¡n. We aredvarw impressed.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:40 PM
216

-varwhr4234tt5

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:40 PM
217

-varw

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:41 PM
218

You can guess what's happening here.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:41 PM
219

When they start ripping off classmates, I want to hear what their cover story is. Mind reading? ESP?

Posted by: ydnew | Link to this comment | 11- 8-14 6:42 PM
220

They're btock-style!

Posted by: JP Stormcrow | Link to this comment | 11- 8-14 6:45 PM
221

181: So, I think it's intuitive to use lexicographic ordering for permutations (as Spike did in 174) so long as the elements themselves are ordered. What wasn't intuitive to me, at least at first blush, is what the algorithm would be for encoding a given number as a permutation, unless it's something like a three-element permutation where it's trivial to enumerate them all. That the factorial number system and Lehmer codes provide a way to do this is, I think, neat.

Posted by: lourdes kayak | Link to this comment | 11- 8-14 6:51 PM
222

I need to do a better job of hiding the bourbon.

Posted by: Jesus McQueen | Link to this comment | 11- 8-14 6:54 PM
223

181: What's the canonical number of [3,1,4,2] (in the range [0,23])? Show your work and explain why it's intuitive.

Posted by: Yawnoc | Link to this comment | 11- 8-14 6:57 PM
224

Or, more or less, 221.

Posted by: Yawnoc | Link to this comment | 11- 8-14 6:58 PM
225

181: I was pretty addled by tiredness and melatonin then. Still am, actually. So I haven't actually read that article in detail. In Yawnoc's example I can produce "13" for [3,1,4,2], same as the Wiki page, but I can't do it quickly, nor can I go back-and-forth between those representations and a composition-of-transpositions representation. So I should read the page.

Definitely using this as a party trick at the next board-games-and-poker geek gathering.

Posted by: dalriata | Link to this comment | 11- 8-14 7:04 PM
226

And I assume in Spike's rules, king is actually 13 not 12.

D'oh! Maybe someone with the keys to the blog could fix it, in case anyone needs to refer to those rules in the future? I'd hate for my documentation errors to lead to a failed party trick.

Posted by: Spike | Link to this comment | 11- 8-14 7:16 PM
227

Done! I am obedient!

Posted by: heebie-geebie | Link to this comment | 11- 8-14 8:15 PM
228

The successful and also slightly wonky real world + online execution of the trick above is just delightful.

Posted by: redfoxtailshrub | Link to this comment | 11- 8-14 8:21 PM
229

Yes, the aredvarw were quite impressive.

Posted by: Eggplant | Link to this comment | 11- 8-14 8:23 PM
230

Just so!

Posted by: redfoxtailshrub | Link to this comment | 11- 8-14 8:26 PM
231

Thanks heebs!

Posted by: Spike | Link to this comment | 11- 8-14 8:35 PM
232

225: As I understand the article, the factorial-base digits don't represent transpositions, but rather selections from a progressively diminishing set. There might be an alternative way of seeing them as transpositions that I'm not catching.

Posted by: lourdes kayak | Link to this comment | 11- 8-14 8:37 PM
233

So, Jammies is at his cousin's wedding. Pokey is a ring-bearer (in Wranglers and boots, no kidding). Pokey got down the aisle and handed off the ring. Then he went behind the minister. Ok, fine. Jammies is in the audience, trying to corral Ace.

Then Pokey starts playing with the hay from some decorative bales of hay. Then he takes some of the straw and starts PRETENDING TO WIPE HIS ASS WITH IT. During the ceremony. It sounds like it was widely visible. (Then he stopped and went back to tackling the groomsmen's legs.)

Posted by: heebie-geebie | Link to this comment | 11- 8-14 8:51 PM
234

So, he won the wedding.

Posted by: Moby Hick | Link to this comment | 11- 8-14 8:55 PM
235

He just needs to deflower the bride and go home.

Posted by: Moby Hick | Link to this comment | 11- 8-14 8:57 PM
236

That's still a thing in Kansas.

Posted by: Moby Hick | Link to this comment | 11- 8-14 9:01 PM
237

Heh. The pregnant bride?

Posted by: heebie-geebie | Link to this comment | 11- 8-14 9:04 PM
238

People are playing Men at Work, because I'm not the most drunk person here.

Posted by: Moby Hick | Link to this comment | 11- 8-14 9:05 PM
239

237: He's that good.

Posted by: Moby Hick | Link to this comment | 11- 8-14 9:06 PM
240

Be sure to tell this story at his own wedding.

Posted by: teofilo | Link to this comment | 11- 8-14 9:20 PM
241

The patriarchy hurts toddlers too.

Posted by: Moby Hick | Link to this comment | 11- 8-14 9:29 PM
242

You people should say things when the people at the bar have conservation pauses.

Posted by: Moby Hick | Link to this comment | 11- 8-14 9:46 PM
243

Which pauses happen when you mention how one accidentally happens upon websites that have dinosaurs fucking cars.

Posted by: Moby Hick | Link to this comment | 11- 8-14 9:51 PM
244

You need to let us know when the pauses happen, dude. It's not like we have a damn webcam in there.

Posted by: teofilo | Link to this comment | 11- 8-14 9:52 PM
245

Also the canonical website is dragons fucking cars, not dinosaurs.

Posted by: teofilo | Link to this comment | 11- 8-14 9:53 PM
246

That's very important to teo, because dragons are clearly not birds.

Posted by: Thorn | Link to this comment | 11- 8-14 9:54 PM
247

Thorn gets me.

Posted by: teofilo | Link to this comment | 11- 8-14 9:55 PM
248

My apologies to the dragons.

Posted by: Moby Hick | Link to this comment | 11- 8-14 9:56 PM
249

They forgive you.

Posted by: teofilo | Link to this comment | 11- 8-14 9:57 PM
250

You don't know me, Alaska man.

Posted by: Opinionated Smaug | Link to this comment | 11- 8-14 10:02 PM
251

I took a poll of all the dragons, and you were in the minority.

Posted by: teofilo | Link to this comment | 11- 8-14 10:10 PM
252

Only because the asshole with the bow killed me.

Posted by: Moby Hick | Link to this comment | 11- 8-14 10:24 PM
253

That sounds like a pretty rough bar.

Posted by: teofilo | Link to this comment | 11- 8-14 10:25 PM
254

I told my kids this question. They didn't figure it out, but after I explained it we pulled out some cards and my kids and i were able to do it pretty easily. We used a non canological
Ordering.

High medium low - 1
High low medium- 2
Medium high low - 3
Medium low high-4
Low high low 5
Low medium high -6

Diamond
Heart
Club

As the tie breakers

Posted by: Lemmy caution | Link to this comment | 11- 9-14 12:52 AM
255

252 was supposed to be from Opinionated Smaug also.

Posted by: Moby Hick | Link to this comment | 11- 9-14 5:31 AM
256

Club Diamond Heard Spade works better for me because they are alphabetical, which helps the 'ol memory.

Posted by: Spike | Link to this comment | 11- 9-14 5:57 AM
257

I thought the canonical suit ordering went spades, hearts, clubs, diamonds, and that you signal to your partner these using 1, 2, 3, or 4 fingers, if you are a cheating sort. Because a spade has a single point, hearts have two bumps, clubs have three, and diamonds have four.

Posted by: heebie-geebie | Link to this comment | 11- 9-14 6:54 AM
258

Bridge, and I thought card games where suit ordering mattered generally, uses the alphabetical order--CDHS.

Posted by: LizardBreath | Link to this comment | 11- 9-14 7:39 AM
259

Yeah, 257 is not actually canonical. I just remember learning it as a way to cheat in Euchre, because it lends itself to hand signals.

Posted by: heebie-geebie | Link to this comment | 11- 9-14 7:54 AM
260

258. True in my experience, but the pedia thing suggests that the order can be different in other games. Most of the games it mentions, however, aren't widely played in the English speaking world and I'd never heard of them, so. I have a vague idea that back in the mists of time either Spades was the low suit or Clubs was high, so that the colours grouped together, but I can't remember where I heard that so it may be BS

Posted by: chris y | Link to this comment | 11- 9-14 7:55 AM
261

181: What's the canonical number of [3,1,4,2] (in the range [0,23])? Show your work and explain why it's intuitive.

13. Here is my work:

>>> from itertools import permutations
>>> [n for (n, perm) in enumerate(permutations([1, 2, 3, 4], 4)) if perm == (3,1,4,2)]
[13]

It's intuitive for the reason lourdes kayak gave: So, I think it's intuitive to use lexicographic ordering for permutations.

Going from a permutation to a number is what I understand the task of "numbering permutations" to be. I admit that going from a number to a permutation is going to be trickier (if you haven't settled in advance the number of elements to be permuted).

Posted by: nosflow | Link to this comment | 11- 9-14 8:32 AM
262

I think any solution that requires you to iterate over all the preceding values is not particularly intuitive. I'm stretching the meaning of intuitive a bit, but I don't think it shows a very well grokked space. And to also violate the analogy ban, it's like saying you understand Roman numerals because you can convert them to regular numerals but only if you also get to convert all the preceding numbers. I don't think that counts as an intuitive understanding.

Posted by: dalriata | Link to this comment | 11- 9-14 8:51 AM
263

Wow, I never noticed that was alphabetical...

Posted by: Unfoggetarian: "Pause endlessly, then go in." (9) | Link to this comment | 11- 9-14 9:16 AM
264

I learned it as an arbitrary ordering -- I only noticed it was alphabetical as a mnemonic teaching it to my kids.

Posted by: LizardBreath | Link to this comment | 11- 9-14 9:22 AM
265

Yeah, you know, I do understand what a lexicographic ordering is. My point is that I don't think I'd be able to explain the permutation &rarrow; canonical number mapping well enough that an average confederate could do it in their head.

Posted by: Yawnoc | Link to this comment | 11- 9-14 9:35 AM
266

Darn, meant to do a preview on that. I don't actually know HTML entity names; I just guess them.

Also, obviously, my concern here is for an arbitrary-length permutation. Folks here seem to have the mapping onto [1,6] under control.

Posted by: Yawnoc | Link to this comment | 11- 9-14 9:36 AM
267

265: well, intuitive ≠ tractable in one's head.

Posted by: nosflow | Link to this comment | 11- 9-14 1:27 PM
268

I think any solution that requires you to iterate over all the preceding values is not particularly intuitive.

Well, here's the broader claim for intuitiveness. Let's take the BROAD view.

There's nothing, remotely, intuitive about 3, 4, 1, 2 => 13. What is intuitive it the idea of a lexical ordering of permutations, and it's a result of that that the particular permutation 3, 4, 1, 2 is assigned 13. The intuitiive thing is the broader context.

Posted by: nosflow | Link to this comment | 11- 9-14 1:29 PM
269

There's nothing, remotely, intuitive about 3, 4, 1, 2 => 13

Right, since 3, 4, 1, 2 => 16.

Posted by: JP Stormcrow | Link to this comment | 11- 9-14 4:07 PM
270

Touché!

Posted by: Yawnoc | Link to this comment | 11- 9-14 5:13 PM
271

That is CLEALRY not the point.

Posted by: nosflow | Link to this comment | 11- 9-14 5:14 PM
272

CLEALRY, I say.

Posted by: nosflow | Link to this comment | 11- 9-14 5:15 PM
273

Coming in late, but surely there is enough information to identify a card uniquely? You have 4! different ways you can turn over the four cards. Then you can muck around with the ordering of the cards' values as well. So, if you turn them over in the order (1,2,3,4) you can subdivide that depending on where the highest-ranked card is - whether it's the third card you turn over or the first or whatever. So the total number of possibilities is 4(4!) which is 96, twice as many as you need.

Let's say you encode the number of the hole card (the one you don't turn over) in the order in which you turn over the other four. (The four cards are A-D, left to right).

ABCD - ace
ACBD - 2
ABDC - 3
...

And then you encode the suit of the card in the position of the highest-ranked card, left to right. So if the hole card is a club, you put the highest-ranked card in position A. If it's a heart, in position B. And so on.

Example:

You have been dealt king of hearts, two of diamonds, seven of spades, jack of diamonds, four of hearts. You decide to pick the four of hearts as your hole card.

You lay out the other four cards in this order left to right:
king of hearts - two of diamonds - seven of spades - jack of diamonds

and you turn them over in this order:
king of hearts
jack of diamonds
two of diamonds.

Your confederate looks at those and goes "OK, the highest ranking card is the king of hearts, in the left hand slot, which means the hole card is a heart. And ajay turned them over in the order ADCB, which means it's a four. Four of hearts."

Posted by: ajay | Link to this comment | 11-10-14 3:49 AM
274

Sorry, typo.
Coming in late, but surely there is enough information to identify a card uniquely? You have 4! different ways you can turn over the four cards. Then you can muck around with the ordering of the cards' values as well. So, if you turn them over in the order (1,2,3,4) you can subdivide that depending on where the highest-ranked card is - whether it's the third card you turn over or the first or whatever. So the total number of possibilities is 4(4!) which is 96, twice as many as you need.

Let's say you encode the number of the hole card (the one you don't turn over) in the order in which you turn over the other four. (The four cards are A-D, left to right).

ABCD - ace
ACBD - 2
ABDC - 3
...

And then you encode the suit of the card in the position of the highest-ranked card, left to right. So if the hole card is a heart, you put the highest-ranked card in position A. If it's a club, in position B. And so on.

Example:

You have been dealt king of hearts, two of diamonds, seven of spades, jack of diamonds, four of hearts. You decide to pick the four of hearts as your hole card.

You lay out the other four cards in this order left to right:
king of hearts - two of diamonds - seven of spades - jack of diamonds

and you turn them over in this order:
king of hearts
jack of diamonds
two of diamonds.

Your confederate looks at those and goes "OK, the highest ranking card is the king of hearts, in the left hand slot, which means the hole card is a heart. And ajay turned them over in the order ADCB, which means it's a four. Four of hearts."

Posted by: | Link to this comment | 11-10-14 3:51 AM
275

I don't think you've fully got it.

Posted by: heebie-geebie | Link to this comment | 11-10-14 4:08 AM
276

That wouldn't work?

Posted by: ajay | Link to this comment | 11-10-14 4:24 AM
277

And then you encode the suit of the card in the position of the highest-ranked card,

This bit doesn't work.

(There's probably lots of ways to resolve your solution, some which preserve the bit above, but your solution doesn't have enough complexity yet.)

Posted by: heebie-geebie | Link to this comment | 11-10-14 4:37 AM
278

Why wouldn't that bit work? There will always be a highest-ranked card (if there are two kings, say, you just pre-arrange that the suits outrank each other in some set order) and it has one of four possible positions left to right.

Posted by: ajay | Link to this comment | 11-10-14 5:26 AM
279

You read the problem in a way that it wasn't intended, which gives you more information to play with, if I understand what you're doing. You're using both the temporal order in which the cards are turned over, and the spatial order in which they are arranged -- in the problem as it was intended to be stated, you don't get both.

Read 165 and 166 for redfox and snarkout simultaneously explaining a more bulletproof statement of the intended problem.

Posted by: LizardBreath | Link to this comment | 11-10-14 5:35 AM
280

Your solution does work (I'm pretty sure) for the problem you were working on, but it's an easier problem than the one intended.

Posted by: LizardBreath | Link to this comment | 11-10-14 5:36 AM
281

Ah, I see. Thanks.

Posted by: ajay | Link to this comment | 11-10-14 5:58 AM
282

Sally, given the problem, went straight for slight angular rotations of the cards as placed on the table. A) Not allowed, and B) you've got a lot of faith in the accuracy of your card placement and your confederate's perceptions, don't you?

Posted by: LizardBreath | Link to this comment | 11-10-14 6:00 AM
283

Yeah, despite my sentiments for relative ambiguity per 185, it is clear that the problem statement needs to more explicitly rule out information from the physical placement of the cards. I did not think to add it as it was not something that had occurred to me as an approach.

Posted by: JP Stormcrow | Link to this comment | 11-10-14 6:29 AM
284

I was misunderstanding Ajay's error, for the record. I thought that Ajay thought that...no one cares, do they.

Posted by: heebie-geebie | Link to this comment | 11-10-14 6:38 AM
285

I'm sure the conservative majority of the Supreme Court would rule that I have to allow positional information if it suited the perceived interests of their perceived constituents.

Posted by: JP Stormcrow | Link to this comment | 11-10-14 6:42 AM
286

Either I'm missing something in the solution, or it was mentioned somewhere in the thread and I missed that.

The solution depends on a taking a base value (the rank of the first card) and adding (wrapping from King to Ace if necessary) a number in the range 1-6 (determined by the order of the other three cards) to get the rank of the hole card. The suit of the hole card is the suit of the first card.

But doesn't it also depend on selecting the hole card such that adding (as opposed to subtracting) works? For example if you have the 4 of clubs and the Jack of clubs, you must pick the Jack as the hole card.

I don't recall that ever being explicitly stated in the "rules."

Posted by: DaveLMA | Link to this comment | 11-10-14 6:51 AM
287

It was mentioned in one of Stormcrow's rot13 comments.

Posted by: LizardBreath | Link to this comment | 11-10-14 6:58 AM
288

Ah, thanks! I thought I'd read all of those but I guess I didn't.

Posted by: DaveLMA | Link to this comment | 11-10-14 7:09 AM
289

The comment I was thinking of is 86, and I guess it depends how explicit you mean by explicit.

Posted by: LizardBreath | Link to this comment | 11-10-14 7:30 AM
290

||

In relation to a geneological inquiry, I just googled my grandfather's full name -- first middle last. The first hit for that name is a clown who was arrested on child porn charges.

|>

Posted by: LizardBreath | Link to this comment | 11-10-14 7:35 AM
291

Is the problem made easier by the fact that you don't have to convey the value of an arbitrarily chosen card? You don't get told "here are four cards, use them to tell your confederate that the fifth card is the eight of clubs". You get given five cards and you get to pick which one of them you want to have as the hole card. So you could, for example, pre-arrange that you are always going to pick the highest card of the five. Or that the colour will always be the same as the colour of the first card you turn over...

Posted by: ajay | Link to this comment | 11-10-14 7:38 AM
292

291: Yes, that's a necessary part of it. You couldn't do the problem under the given rules if it were "Use four randomly chosen cards to convey a randomly chosen fifth card." (Or, maybe you could, but I don't think so and the solution we've been talking about wouldn't work.)

Posted by: LizardBreath | Link to this comment | 11-10-14 7:43 AM
293

A... literal clown? Like Francis Xavier Breath, aka Jumbles the Clown?

Posted by: snarkout | Link to this comment | 11-10-14 7:47 AM
294

Yes. Literal clown. With a clown name along the lines of Jumbles the Clown.

Posted by: LizardBreath | Link to this comment | 11-10-14 7:48 AM
295

To be abundantly clear, different guy. My grandfather never intentionally made another human being laugh in his life.

Posted by: LizardBreath | Link to this comment | 11-10-14 7:49 AM
296

And it wasn't your grandfather? Just some guy with the same name?

Posted by: Moby Hick | Link to this comment | 11-10-14 7:49 AM
297

And pwned.

Posted by: Moby Hick | Link to this comment | 11-10-14 7:50 AM
298

Anyway, I know how your grandfather might feel about it. I have the exact same name as a law professor.

Posted by: Moby Hick | Link to this comment | 11-10-14 7:50 AM
299

Also, a chemistry professor. He seems to be doing very well, but if he recent picture is still accurate, I have nicer glasses.

Posted by: Moby Hick | Link to this comment | 11-10-14 7:54 AM
300

That wouldn't work?

Not in the revision that snarkout and rtfs suggest, because there's no way to separate the order of the cards from the order in which which card is revealed.

Posted by: nosflow | Link to this comment | 11-10-14 8:08 AM
301

I just found out that one of our pretty obviously cuckoo (we made lots of jokes about how he was going to shoot the place up) neighbors in NM was a convicted child pornographer. Strange how utterly vile a backyard pool for the neighborhood kids can seem in retrospect (as far as I know, he didn't harm anyone in NM--the conviction was in the past and I never let our kid go over there--but pretty clearly he still got off on little kids).

Posted by: ogged | Link to this comment | 11-10-14 8:18 AM
302

It was mentioned in one of Stormcrow's rot13 comments.

And miiiiiiiine.

Posted by: redfoxtailshrub | Link to this comment | 11-10-14 8:18 AM
303

Strange how utterly vile a backyard pool for the neighborhood kids can seem in retrospect

Not everybody has the chops for being a clown.

Posted by: Moby Hick | Link to this comment | 11-10-14 8:19 AM
304

The first confederate card trick I learned involving laying out the cards according to the placement of the suit pips on the lower-right card, then using that card as a "map" and pointing to the representative pip on it.

Posted by: k-sky | Link to this comment | 11-10-14 8:20 AM
305

Not everybody has the chops for being a clown.

True. This guy absolutely wouldn't have made it as a clown.

Posted by: ogged | Link to this comment | 11-10-14 8:21 AM
306

I liked Lord Vetinari's Lovecraftian explanation of what clowns are for: you're not supposed to find them funny, you're supposed to find them horrifying, because they're a reminder that the universe is not in fact rational and comprehensible, but chaotic and random and uncaring.

Posted by: ajay | Link to this comment | 11-10-14 8:58 AM
307

So, in fact, they serve a purpose.

Posted by: nosflow | Link to this comment | 11-10-14 9:02 AM
308

Seeing the huge elephants not murder their keepers and change the crowd serves the same purpose.

Posted by: Moby Hick | Link to this comment | 11-10-14 9:03 AM
309

On the OP, I'm still noodling on how to show that this in some manner uses "all" of the information. It seems like it does--it certainly does for this particular solution scheme--but not sure how to show that the extra single bit is the most you can get out of your freedom to pick the down card from the 5 original (which is nominally a little more than 2 bits). The question is there some other possible scheme that would work for say a 4-suit 15-card deck? (And noted that the suit/deck construction is just for human convenience it really is a statement about 52 items with a canonical order, so could it go to 60 items for instance and take out the same number of cards?)

Anyway, not there yet on showing it and really must do some urgent work, but in trying to think it through this seems to be the of sequence of decks of max cards for which *this* solution scheme works (decks of 2*n!+n cards divided into n suits of 2*(n-1)!+1 cards each.)

Suits, cards in suit, total cards in deck
2, 3, 6
3, 5, 15
4, 13, 52
5, 49, 245
6, 241, 1446

Posted by: JP Stormcrow | Link to this comment | 11-10-14 9:49 AM
310

I'm still not convinced it uses all the information, but my efforts to show this were fruitless.

Posted by: Eggplant | Link to this comment | 11-10-14 10:19 AM
311

I'm not convinced yet, either, but I'm guessing that it is. It is true that there are "draws" you get in which multiple configuration lead to the right answer. For instance if all the cards are of the same suit, there are 10 different combinations of the hidden and suit cards that can yield the right answer--basically 1/2 of all the possible combos (20)--those with the right "polarity". This differs from something like the 12/13/14-ball puzzle described in 28, where in the one that uses all of the information there is no fortuitous selection of balls which allows you any "choice"--your hand is forced the entire way and there is one unique result for each path. So in some sense this problem is not "using" all the info, but there may still not be anything that can. (I'm guessing this all maps onto some actual formal mathematical conceptual space ... but one that I have no inkling of nor background to understand if I did.)

Posted by: JP Stormcrow | Link to this comment | 11-10-14 10:37 AM
312

Here's the puzzler which I don't think quite warrants front page posting, which my advisor told me:

Countably infinitely many prisoners lined up on a wall, each of them facing the tail of the infinite line. Ie they can all see infinitely many prisoners behind them, but not the finitely many prisoners in front of them. Each of them is wearing a red or blue hat.

On the count of three, they must all shout what hat color they're wearing - ie no communication or signaling between any of them. If only finitely many of them guesses wrong, they all go free. If infinitely many of them guess wrong, then they all get punished, presumably involving the silly hats.

What should their strategy be? Hint: it involves the Axiom of Choice, and is totally unsatisfying as an answer.

Posted by: heebie-geebie | Link to this comment | 11-10-14 11:18 AM
313

Why does your advisor care what you put on the front page?

Posted by: Moby Hick | Link to this comment | 11-10-14 11:21 AM
314

Since their potential punishers can't possibly tally whether infinitely many of them have guessed wrong in finite time, they should just yell whatever.

On the other hand, I suppose their potential punishers might have some temporal tricks up their sleeve to match the spatial tricks employed to imprison, and line up against a wall, infinitely many people.

Posted by: nosflow | Link to this comment | 11-10-14 11:22 AM
315

He's worried I'd include so many details that people could follow what I was saying.

Posted by: heebie-geebie | Link to this comment | 11-10-14 11:22 AM
316

Anytime someone mentions the Aciom of Choice I reach for one of infinitely many guns.

Posted by: Eggplant | Link to this comment | 11-10-14 11:24 AM
317

Or maybe gins.

Posted by: Moby Hick | Link to this comment | 11-10-14 11:25 AM
318

I'm going to recycle a joke from Facebook!

What did David Hilbert and Tommy Durden have in common?

Each postulated a hotel in which you can always find a room, no matter how crowded it gets.

Posted by: nosflow | Link to this comment | 11-10-14 11:27 AM
319

Since their potential punishers can't possibly tally whether infinitely many of them have guessed wrong in finite time, they should just yell whatever.

Well, this is just silly. There are infinitely many punishers, in one-to-one correspondence with each prisoner, and each assigned to a power of 1/2, and they are given strict instructions that they have exactly their (1/2)^n of a minute to register whether their corresponding prisoner answered correctly. Just wait a couple minutes.

Posted by: heebie-geebie | Link to this comment | 11-10-14 11:28 AM
320

Whenever the prison gets crowded they just reassemble it at twice its current volume.

Posted by: Eggplant | Link to this comment | 11-10-14 11:31 AM
321

they have exactly their (1/2)^n of a minute

This is exactly the kind of temporal trick I was thinking of.

Next you'll tell me that each prisoner is half as wide as the previous and that's how they can all be lined up against a ten-foot wall.

Posted by: nosflow | Link to this comment | 11-10-14 11:32 AM
322

There's a normal distribution of prisoner size, as in their total area has been normed to equal 1.

Posted by: heebie-geebie | Link to this comment | 11-10-14 11:33 AM
323

You going to leave us hanging with the answer, heebie? I'm not smart enough to figure it out on my own.

Posted by: Spike | Link to this comment | 11-11-14 6:21 PM
324

I finally looked it up on Wikipedia. Unsatisfying! Though I guess I learned something about the axiom of choice. The properties of infinite sets at issue are too loopy to be at all visualizable in the context of the prisoner story; it's not snappily counterintuitive like Hilbert's infinite hotel.

Posted by: lourdes kayak | Link to this comment | 11-11-14 9:28 PM
325

I heard the puzzle in 312 before. It bothered me much more than the Banach-Tarski paradox, for some reason. I never really got why Banach-Tarski makes people uncomfortable with the Axiom of Choice, since it seemed like the uncomfortable thing is dealing with sets that aren't measurable.

Posted by: essear | Link to this comment | 11-11-14 9:41 PM
326

But then I think I eventually decided the uncomfortable thing here was infinitely communicative dwarves, or something. Didn't this come up here before?

Posted by: essear | Link to this comment | 11-11-14 9:43 PM
327

Oh right.

Posted by: essear | Link to this comment | 11-11-14 9:47 PM
328

I wasn't smart enough, either. Partition the sequences as follows: a set consists of all sequences (of reds and blue) that eventually share the same tail. In other words, any two sequences in any set differ in a finite number of places.

The axiom of choice says that you can always pick a representative from an infinite set. Pick a representative from each of the sets of sequences. Have all prisoners memorize all representatives, one from each set. Since all prisoners can see the tail, they answer according to the representative sequence, and only finitely many of them are wrong.

Unsatisfying!

Posted by: heebie-geebie | Link to this comment | 11-11-14 9:50 PM
329

Oh, right. The dwarves need infinite memories. Yeah. That wasn't a very convincing solution.

Posted by: essear | Link to this comment | 11-11-14 9:52 PM
330

I don't believe in choice, because if I had a choice why would I be getting up early tomorrow to fly halfway around the world to a meeting I don't care about?

Posted by: essear | Link to this comment | 11-11-14 9:55 PM
331

Good question. I am also getting up early tomorrow to catch a flight, but it's a much shorter one.

Posted by: teofilo | Link to this comment | 11-11-14 9:58 PM
332

That puzzle makes me angry.

Posted by: Eggplant | Link to this comment | 11-11-14 9:59 PM
333

I was exaggerating a little. I'm only going to be seven hours ahead.

Posted by: essear | Link to this comment | 11-11-14 10:05 PM
334

I also don't understand the solution.

Posted by: Eggplant | Link to this comment | 11-11-14 10:08 PM
335

My flight will take about an hour.

Posted by: teofilo | Link to this comment | 11-11-14 10:14 PM
336

What throws is that the dwarves (I like that they're dwarves now) have eagle eyes that can look into infinity and encompass the entirety of the countably infinite tail even before they match it to one of the uncountably infinite set of tails in their head. (I think the set of tails would be uncountable?) No wonder they're all on death row.

Posted by: lourdes kayak | Link to this comment | 11-11-14 10:27 PM
337

This is great.

Posted by: essear | Link to this comment | 11-11-14 10:28 PM
338

What bothers me is that no dwarf has any information about his hat. For any integer n, I can make a new line of dwarves starting at the nth dwarf and I'll still be garanteed a finite number of errors?

Posted by: Eggplant | Link to this comment | 11-11-14 10:32 PM
339

337: I know, right? Just fantastic.

Posted by: teofilo | Link to this comment | 11-11-14 10:34 PM
340

338: Apparently. "Because the prisoners have no information about the color of their own hat and would make the same guess whichever color it has, each prisoner has a 50% chance of being killed. It may seem paradoxical that an infinite number of prisoners each have an even chance of being killed and yet it is certain that only a finite number are killed. However, there is no contradiction here, because this finite number can be arbitrarily large and no probability can be assigned to any particular number being killed."

Posted by: lourdes kayak | Link to this comment | 11-11-14 10:34 PM
341

I propose we limit ourselves to computable dwarf hats.

Posted by: Eggplant | Link to this comment | 11-11-14 10:47 PM
342

337 is a timely reminder that there are probably at least 20 of those in my dissertation draft, and possibly several in documents I have prepared for my employer. It's really hard for me to turn that part of my mind off.

Posted by: lurid keyaki | Link to this comment | 11-11-14 11:46 PM
343

336: Yeah, the number of sequences in each set is countably infinite (precede the given tail with all possible finite prefixes, which is countable), so if the number of sets was countable, then the total number of sequences would be a countably infinite union of countably infinite sets, which would itself be countably infinite. But the total number of sequences can be put in 1-1 correspondence with the binary representation of the real numbers from 0 to 1, which is uncountably infinite. Hence the number of sets must be uncountable, by contradiction.

Posted by: Dave W. | Link to this comment | 11-12-14 2:34 AM
344

340: Huh? So 50% of infinity is finite? Nope, I don't buy it. Next, they'll be trying to convince you that 1 - 2 + 3 - 4.... = 1/4.

Posted by: Spike | Link to this comment | 11-12-14 4:42 AM
345

Half of infinity is 6.03x10^23.

Posted by: Moby Hick | Link to this comment | 11-12-14 4:51 AM
346

342: My dissertation was like that, but in a stroke of dumb luck, I messed up a minor detail in formatting (I think there was a wrong font in the table of contents because of a template error). It turned out that such an error meant an electronic copy wouldn't be deposited until I had corrected and uploaded it, but I would graduate without any delay. There was no deadline for fixing the (tiny) error, so I used the extra time to actually edit the dumb thing. I'm sure it's still a mess, but I felt a lot better that I got to edit it over several weeks to fix things me advisor had added and changed that bugged me.

Posted by: ydnew | Link to this comment | 11-12-14 5:05 AM
347

337, 339: Yes.

Posted by: JP Stormcrow | Link to this comment | 11-12-14 7:12 AM
348

347: Oops! Clearly I need to start rearranging my schedule so I don't keep missing comments here. I had also overlooked most of the rot13 The Good Wife discussion.

Posted by: essear | Link to this comment | 11-12-14 7:36 AM
349

Flight canceled!

Posted by: teofilo | Link to this comment | 11-12-14 8:24 AM
350

337 is a timely reminder that there are probably at least 20 of those in my dissertation draft, and possibly several in documents I have prepared for my employer. It's really hard for me to turn that part of my mind off.

This is why LaTeX is a boon: you can put that shit in comments.

Posted by: nosflow | Link to this comment | 11-12-14 8:25 AM
351

So 50% of infinity is finite? Nope, I don't buy it

Infinity is that quantity than which nothing can be bigger. Half of that number cannot logically also be that quantity than which nothing can be bigger - something is bigger than it, namely infinity.Therefore half of infinity is finite. Simple!

Posted by: ajay | Link to this comment | 11-12-14 8:28 AM
352

There were only two moles on the ark, everything is made of moles of molecules, therefore 345 is right. Or would have been if I was able to remember what a mole was correctly.

Posted by: Moby Hick | Link to this comment | 11-12-14 8:30 AM