47 replies to this topic

[plasmid]

Yep plainglazed, that's me. I've had time to read and think just a little bit about this... not enough to flesh out an algorithm, but enough to appreciate how slick that approach is.

Spoiler for

Using the technique of having the first half of the deck give you info about the second half would, on its own, give you the last half of the deck correct plus one quarter of the first half correct, for 5/8 total. Using sets of three cards where a leading card gives you the color to guess and the orientation of the three cards tells you which suit within that color to guess will get 2/3 of the deck correct. One might be able to do a touch better by sneaking the missed cards into the latter approach.

[plainglazed]

upph - and there you are EH. sorry but deleted that last post as i cant count and am rethinking. hopefully youve seen enough to get you going and can fix it for me.

well - within the spirit of the forum, should not have deleted that WRONG post so here it is...

Spoiler for What if it was an infinite deck?

We've mentioned this before, and plainglazed's new algorithm gives 75% (9 of 12, same as my modification 6 of 8).
I decided to see what would happen if we used plainglazed technique, including my addition of using all the possibilities with less missed cards, and see what happens as the cards in the groupings increases. It turns out that you can get....
80% with 80 cards per grouping.
90% with 1640 cards per grouping.
95% with 2820 cards per grouping.
96% with 3375 cards per grouping.
97% with 4267 cards per grouping.
98% with 5950 cards per grouping.
99% with 10700 cards per grouping.
99.5% with 19399 cards per grouping.
99.9% with 79961 cards per grouping.
99.99% with 633144 cards per grouping.
So with an infinite deck, you can get basically all of them.

kewl - tho getting pretty close to bonanova's "i can or i wont say" thread.

had a different go at 37 somewhat similar to the below but yours got me to the following

EDIT: which if i could add, would have known that this is also a solution for 37

Spoiler for a similar idea to plasmid's above combined with EventHorizon's to get 38

the first card and the top of the second card give the suit to respond to both cards 2 and 3. Will address the case if both are the same suit later but if cards 2 and 3 are different suits, either could be correct giving one bit of extra info or both can be wrong one of two ways also giving that extra bit. The direction of the plane on card 3 then acts as the first card and this process can be repeated. So cards x(2,3) (4,5) (6,7) (8,9) (10,11) (12,13) (14,15) could give 8 bits of extra info in this way, regardless if correct or not (the eighth being the direction of the plane on card 15). Three of those bits could be used to ascertain cards (16) (17) (18) any of which could be intentionally wrong one of three different ways. Then one of the ten groups in parentheses could be intentionally missed 16 different ways or 2^4 thus four more extra bits giving 9 out of 18 correct with 9 extra bits to pick up where EventHorizon's solution for 37 was after 18 cards. Since you now have 9 extra bits but only need 8, it does not matter if one of the first seven pairs compared are the same suit. If two (or more) pairs are both the same suit and thus both correct, then you already have 9 (or more) of the first 15 cards correct with eight extra bits and you don't need to go thru the process of intentionally missing any cards.

getting pretty close to that 3/4s which, anecdotally anyway, does seem like a logical limit after playing with this problem for a bit. but who knows? maybe 40's next. hope y'all dont mind that i've pretty much joined in on the solve.

[EventHorizon]

I've got a strategy that gets 38 (or more) on 99.8% of decks, and needs one more bit on the rest... one bit... grr.

Edit: Hey... 500th post!

v v v v doesn't work
Edit 2: I got a strategy that guarantees 38. I'm going to flush out this idea before posting (hoping I can get 39).

Edited by EventHorizon, 18 November 2012 - 02:21 AM.

[EventHorizon]

Spoiler for Strategy that gets 38 99.8% of the time and 37 otherwise

This is a direct modification of plainglazed's strategy that gets 37. I was trying to get, after 18 cards, 10 correct and 8 bits of information. With that I could continue with my old 37 solution to end up with 38.

I thought I'd try to guarantee some pairs that are both correct, so I introduced a pair offset. This is the difference between the suit to guess for each pair (the first is selected by the orientations, then add offset). I decided to let the suit selected in the first pair signify the offset. If the cards are the same suit, yay, two free cards... and try the next pair. The offset is selected by finding the offset that produces the most correct guesses in the next 7 pairs. And I only needed 2 pairs with 2 correct cards each to get me to the goal (card 18 is guessed correctly from orientations 17 and 18, then get one of the pairs wrong on purpose to get the bits up to 8).

If neither of the two suits in the first unequal pair signify an offset that gives at least 2 pairs with both guessed correctly (so they both happen at most once in the seven pairs, giving (7 choose 2)+7+7+1 possibilities out of 4^7 = about .002) then give the offset that will be best (guaranteed to give at least 3 correct pairs by pigeon-hole principle). Doing the same method as before and getting one card wrong on purpose gives 10 correct cards but only 7 bits to work with.

I wondered where I could get that extra bit...
v v v v v doesn't work

Spoiler for so I made like the government and ...

racked up some debt!

I called it bit debt, where I'd 'borrow' from the future and pay it back after processing the group of cards.

It doesn't actually work that way, but it was what I called it. It is actually just grouping outcomes intelligently so you can tell what the first few bits are before seeing all the cards.

Here are the two situations I needed to show are possible for the simplest strategy I found that guarantees 38.

Spoiler for 3 bits, get 4 of 5 cards right, leave 2 bits

Getting four of a group of five cards correct takes 5 bits of information and leaves 4 bits of information afterwards. But then I applied 'debt.'

With the 3 bits, I can look at the first 3 cards.

If one of those cards is wrong, I have my 2 bits of informations right there since I know the last 2 will be correct. There are 9 ways this situation occurs. I group 8 of these possibilities together and group the last one with the possibilities that have the first three cards all guessed correctly (7 possibilities).

This groups the possibilities into two groups of 8. So depending on which group I end up in after those 3 cards, I got another bit of information.

There are 3 ways to get the fourth card wrong. Grouping the stray outcome with these gives a group of 4, so I have another bit to use. This gets me the last card... so I'm done.

Spoiler for 3 bits, get 6 of 8 cards right, leave 3 bits

We've already seen 6 of 8 in my strategy that gets 37. I was quite surprised when I found I only needed 3 bits of information up front.

After seeing 3 cards, the situation can be one of the three below

2 are wrong: (3 choose 2) * 9 = 27 outcomes.

1 was wrong: 3*3 possibilities that could each end up as one of 16 different outcomes. 9*16 = 144 outcomes. (all the rest correct + 3 different ways to miss one of the next 5 cards = 16 outcomes)

All correct: all correct + 3 ways each to miss 1 of the 5 cards + (5 choose 2) * 9 = 106 (don't need 21 of them though)

It was nice that when 1 card was wrong it could be one of 16 outcomes. Group 8 of those together for 128 outcomes, and 1 with the rest. The other group is (106-21)+27+16=128.

If 1 card was incorrect, you could look at the next 4 cards since they are already in groups of 16. If any of those 4 cards are wrong, you know the last card is correct. If they are all wrong, it leaves 4 possibilities (last card can be wrong in 3 ways or be correct). This is a group of 4 so you can look at the final card.

If the situation seen is in the second group, we can look at 1 more card due to the group of 128 outcomes.

If the fourth card is the first incorrect card seen then the outcome could be one of 13. There are 3 ways for the fourth card to be wrong, so there are 3 groups of 13 outcomes. Add 3 from the 27 outcomes (2 wrong in first 3), to reach 16 (can look at the next 3 cards, leaves a group of 4 (final card could be wrong 3 ways or correct)).

If the fourth card was correct, that leaves (4 choose 2) * 9 + 13 = 67 - 21 (extra outcomes above the needed 2^8) possible outcomes with all correct so far, and the 18 (27-9 from the 3*3 borrowed) from 2 of the first 2 wrong. Grouping the 18 with 46 gives a group of 64. Look at the next card.

If the 5th card is the first missed card, it could be one of 10 outcomes. Group each of the 10 outcomes representing the 3 ways this could happen with 6 outcomes from 2 of the first 3 being wrong. Each of those are a group of 16.

If all 5 cards were guessed correctly, there are 1 (all correct) + 3 * 3 (one cards missed in final 3) + (3 choose 2) * 9 - 21 (extra outcomes above 2^8) = 16.

Since we're down to a group of 16, look at 2 more cards.

If one of those two cards is missed, it could be one of 4 possible outcomes (last card wrong in one of 3 ways or correct). Since we only needed 16 outcomes in this region on possibilities and we've grouped them down to 4 (only needed them down to 8), we're done. We can look at the final card and get the final bits of info.


Sorry if that was hard to follow, I was describing a mess that covered half a page.

Spoiler for 38!

Get the first three orientations to give three bits of information. Miss the first 3 cards.

Group the next 40 cards in groups of 8 and get 6 cards correct in each group.

Get 4 of the next 5 cards correct leaving 2 bits.

Get the next 2 cards correct using those 2 bits.

Get the final 2 cards correct.

3+8+8+8+8+8+5+2+2=52
0+6+6+6+6+6+4+2+2=38

Spoiler for Beyond 38

Checking outcomes to make sure the bit 'debt' works fine is tiresome. I thought of writing a program to calculate maximum debt for each situation, but that seemed like a lot of work. I may still do that later. (I did already write one to calculate bits produced by missed cards, and used that to find '6 of 8' and large groups to claim you can get 'all' of an infinite deck.)

I did find a heuristic that seems pretty good. It is basically to make sure that the amount of outcomes without a missed card yet can be put into groups that halve with each successive card taking into consideration the superfluous outcomes greater than the needed power of 2.

Using this I found two groupings that work according to the heuristic, but I'm currently to lazy to make sure:
6 bits > 18 of 23 correct > 6 bits
6 bits > 15 of 18 correct > 2 bits

For 39 then, start by pairing cards (2 3) (4 5) (6 7) and using plainglazed's plasmid inspired method to get 3 correct and 4 bits of info. Miss one card on purpose (or not... 1 more outcome) to give 2 extra bits.

This means after 7 cards, you have 2 correct and 6 bits of info.

7+23+18+2+2=52
2+18+15+2+2=39

bits after each group
6,6,2,0,0



Other possible 39s with one main grouping that I haven't even checked the bit debt heuristic yet:

9+39+2+2=52
3+32+2+2=39
7,3,1,1

7+41+2+2=52
2+33+2+2=39
6,4,2,2

The extra bits left over could make the groupings possible by not needing to use as many outcomes. Half off per extra bit.

Here's some 40s that would require crazy debt, but haven't checked the heuristic (numbers are bigger than I want to work with by hand). I also have to wonder if 2 or 3 bits is enough, but there are 9 or 10 missed in the group which creates crazy amounts of outcomes. Who knows...

2+46+2+2=52
0+36+2+2=40
2,3,1,1

3+45+2+2=52
0+36+2+2=40
3,2,0,0

3+45+2+2=52
1+35+2+2=40
2,4,2,2

[plainglazed]

sorry for the delayed response, EH. checked out your post briefly earlier and again just now tho have still not been able to study it in depth. an interesting approach. have highlighted my initial hangup in the quote below. am no doubt a little slow and will continue to ponder but for now am indeed having a hard time following the logic.

Spoiler for 3 bits, get 4 of 5 cards right, leave 2 bits

Getting four of a group of five cards correct takes 5 bits of information and leaves 4 bits of information afterwards. But then I applied 'debt.'
With the 3 bits, I can look at the first 3 cards.
If one of those cards is wrong, I have my 2 bits of informations right there since I know the last 2 will be correct. There are 9 ways this situation occurs. I group 8 of these possibilities together and group the last one with the possibilities that have the first three cards all guessed correctly (7 possibilities).
This groups the possibilities into two groups of 8. So depending on which group I end up in after those 3 cards, I got another bit of information.
There are 3 ways to get the fourth card wrong. Grouping the stray outcome with these gives a group of 4, so I have another bit to use. This gets me the last card... so I'm done.

[EventHorizon]

sorry for the delayed response, EH. checked out your post briefly earlier and again just now tho have still not been able to study it in depth. an interesting approach. have highlighted my initial hangup in the quote below. am no doubt a little slow and will continue to ponder but for now am indeed having a hard time following the logic.

I didn't really explain it too well. Here's a (hopefully) better attempt to show that with 3 bits of information, you can get 4 of the next 5 cards right and still end up with 2 bits after

Spoiler for 3bits > 4of5 > 2bits

First, I'll simply enumerate all the possibilities and what bits they will produce
ccccc - 0000
cccc1 - 0001
cccc2 - 0010
cccc3 - 0011
ccc1c - 0100
ccc2c - 0101
ccc3c - 0110
cc1cc - 0111 <----the "stray outcome" grouped with the ones above that all have the missed card 4th, 5th, or all correct.
cc2cc - 1000
cc3cc - 1001
c1ccc - 1010
c2ccc - 1011
c3ccc - 1100
1cccc - 1101
2cccc - 1110
3cccc - 1111
where c means correctly guessed, 1 means suit value guessed was 1 higher (mod 4), etc.

Notice that after 3 cards, we can know if the first bit to be produced is a 1 or a 0. So this can be used to guess the fourth card. This is what I meant by "So depending on which group I end up in after those 3 cards, I got another bit of information." In the case of a card missed in the first 3, you actually know all 4 bits of the information produced since only 1 card is going to be missed.

After I see what the fourth card is, assuming none of the first 3 were missed, the possibilities are the following:
ccccc - 0000
cccc1 - 0001
cccc2 - 0010
cccc3 - 0011
ccc1c - 0100
ccc2c - 0101
ccc3c - 0110
(cc1cc - 0111 <-- the stray outcome to complete the two groups of 4.)

Notice that if the fourth card was not missed, the second bit is 0. If the fourth card was missed, the second bit is 1. So we can use this bit to guess the fifth card.

So the possible outcomes were grouped in two groups of 8 to let me know the first bit.... this is because all the outcomes in each group produce the same first bit.
Once grouped into 4s, they all produce the same second bit.

After the fifth card is seen, we know exactly what bits of information were produced, and can leave the last two bits to be used by later cards.

A couple examples

Spoiler for Example 1 - one of the first 3 cards is missed

I'll use the orientation on the card to be the left bit, and the other bit of information used is the right.


Next 5 cards: 23013
Bits going out needs to be 10

Next 5 cards in binary: (10)(11)(00)(01)(11)

The fifth card requires a 1 as the right bit, so the second bit produced must be a 1.
The fourth card requires a 1 as the right bit, so the first bit produced must be a 1.

So the bitstring that needs to be produced by these 5 cards is 1110. From the explanation, that means the outcome must be 2cccc.

Orientations: (0)1001 <---with the missed card marked in parenthesis

Determined by the left bit of each (except needing to guess 00 on the first card to miss it by 2 (mod 4))

Bits coming in then must be: (0)10



...Handing the deck over to the guesser...



010 are the bits of information the guesser has once he gets to the group of 5 cards in question.

The first card's orientation is 0. Taking this as the left bit and the 0 from the built up information, means the guesser guesses 0. The card is 2. Outcome = missed by 2 (mod 4).

The second card's orientation is 1. The second bit of information is 1. The guesser guesses 3. The card is 3. Correctly guessed.

The third card's orientation is 0. The last available bit of information is 0. This means the guesser guesses 0. The card is 0. Correctly guessed.

The guesser looks at his page of notes and sees 2cccc, the only outcome with 2cc at the beginning, and knows the bits of information produced are 1110.

The fourth card's orientation is 0. The next bit of information is a 1. The guesser guesses 1 and the card is a 1. Correctly guessed.

The fifth card's orientation is 1. The next bit of information is 1. The guesser guesses 3 and the card is a 3. Correctly guessed.

This leaves 4 correct guessed out of this group of 5 with the bits 10 extra for the next group of cards.

Spoiler for Example 2 - the fourth card is missed

Next 5 cards: 23013
Bits going out needs to be 10

Next 5 cards in binary: (10)(11)(00)(10)(11)

The fifth card requires a 1 as the right bit, so the second bit produced must be a 1.
The fourth card requires a 0 as the right bit, so the first bit produced must be a 0.

So the bitstring that needs to be produced by these 5 cards is 0110. From the explanation, that means the outcome must be ccc3c.

However, this means the fourth card needs to be missed and a 2+3 (mod 4) = 1 must be guessed.

doh...

Example 2 shows that this method does not work as I thought it did, since I reached a contradiction. So back to the drawing board... hopefully something from this can be salvaged.

I think it may still work, but that I can't 'borrow' quite as many bits as I thought. I think there needs to be a 1 bit buffer at all times. Hopefully that solves the issue, but I'll need to look into it.

[plainglazed]

Came back to this one once again with a couple of thoughts on how to eek out a little more info from the lay of the cards then before.

Spoiler for first thought

if you can go about getting your initial "extra bits" in two different and distinguishable ways, that yields another bit -

Spoiler for example

(a) x(2,3) (4,5) (6,7) (8,9) missing one of the four pairs gives 3 of 9 w/7 extra bits of info.

or

(b) x(2,3) (4,5) (6,7) (8,9) (10,11) (12,13) missing none gives 6 of 13 w/7 extra bits.

so depending on which of the two methods above are indicated gives each method another bit.

Spoiler for second thought

selectively using the extra bits in different combinations might produce more bits. -

Spoiler for example

EH already showed that with using eight extra bits, one or two suits could be missed intentionally resulting in six out of eight correct suit predictions with eight new bits remaining (8C2 * 3^2 + 8C1 * 3 > 2^8) --> 6 of 8 w/8.

Here are some other combinations:

2 of 3 w/3
4 of 5 w/4
3 of 5 w/6
2 of 5 w/8
10 of 11 w/5
9 of 12 w/12

now combining groups of the above in different orders could give more info. 4 of 5 w/4 is the most efficient and so i played with the three different groups starting with five bits like this -

4 of 5 and 3 of 5 or 3 of 5 and 4 of 5, depending on which, gives another bit. here's the nomenclature i'll use:

(6) 7 of 10 +1 (34, 43) - starting with a minimum of six bits, seven of ten suits can be predicted correctly with the original number of bits plus one remaining.

here are some more:

(5) 6 of 10 +2 - (33)
(5) 5 of 10 +5 - (32, 23)
(5) 4 of 10 +6 - (22)
(6) 11 of 15 +0 - (443, 434, 344)
(6) 10 of 15 +3 - (442,424, 244, 334, 343, 433)
(5) 9 of 15 +5 - (234, 243, 342, 324, 432, 423)
(8) 15 of 20 +0 - (4443, 4434, 4344, 3444)
(7) 14 of 20 +3 - 4442, 4424, 4244, 2444, 4433, 4343, 4334, 3443, 3434, 3344)
(7) 13 of 20 +5 - (4432, 4423, 4342, 4324, 4243, 4234, 2434, 2443, 2344, 3424, 3442, 3244)

Spoiler for 38 ???

(a1) 3 of 9 w/7+1 and 15 of 20 +0 = 18 of 29 w/8--> 4 of 5 -1 + 4 of 5 -1 + 4 of 5 -1 + 5 of 5 = 35 of 49.
(a2) 3 of 9 w/7+1 and 14 of 20 +3 = 17 of 29 w/11--> 10 of 11 +5--> 4 of 5 -1 + 4 of 4 = 35 of 49.

or

(b1) 6 of 13 w/7+1 and 15 of 20 +0 = 21 of 33 w/8--> 4 of 5 -1 + 4 of 5 -1 + 6 of 6 = 35 of 49.
(b2) 6 of 13 w/7+1 and 14 of 20 +3 = 20 of 33 w/11--> 10 of 11 +5 + 5 of 5 = 35 of 49.

so whether a1 or a2 or b1 or b2 gives the extra bit to get the 36th card out of 50 and the last two as before.

again, hoping all that is in place and works. seemed like so many combinations were close but not quite. 39 might be tough…

Edited by plainglazed, 13 November 2012 - 03:04 PM.
poor cut and paste

[EventHorizon]

I think the bit debt idea will always have situations that produce contradictions, so I'm thinking it should be discarded.

I looked over plainglazed's 38, and I think it works. Nice.

Edit: I got another 38. It's slightly more complicated (1 more branch needed), but is based on yours, so I won't bother posting it. It uses 6of8's and 5of8's in combinations instead of groups of 5's in a bigger group of 20.

Edited by EventHorizon, 18 November 2012 - 02:04 AM.