Can You Solve This Challenging Math Riddle?

[daniel_i_l]

Assume you have 27 cards numbered 1-27. You and your partner have do devise some strategy so that for any 4 cards that you pick (without your partner seeing) you'll be able to tell him what they are by showing him only three of them. The only way that you can use the three cards that you show him (other than their respective numbers) is the order in which you present them to him - no patterns or physical properties of the cards are allowed.
For example, if there were only nine cards, then for any three that you show your partner the forth card would be 1 out of 6 possibilities (nine minus the three you showed him), since there're 6 ways to order 3 cards you could use the order to tell your partner what the forth card is.
The trick is to do it with 27 cards.

 

[qntty]

There are 6 permutations of any three cards, so if order is the only way to communicate, I don't think it's possible.

 

[DaleSwanson]

I think it's possible. The first thing that struck me was using each card as a binary number, that gives 2^3 = 8 possibilities. The problem is what properties of the number you use to convey info, and if you don't have enough cards with that property.

EDIT: Well I tried using each card as a bit to answer some yes or no question about the 4th card. 1st card is it odd or even, 2nd is it over 13, 3rd is it divisible by 4 (add 1 to odd numbers). For example 20, 9, 14 displayed says that the 4th card is even (because 20 is even), under 13 (because 9<13), and not divisible by 4 (because 14 isn't). The problem is that this only limits it down to 3 or 4 cards (in this case 2, 6, 10). Right now I'm trying to figure out someway to communicate which of those 3 it is, maybe by making the lowest or highest of the 3 displayed match the position. I don't think it's going to work though since it will mess with the ordering.

 

[qntty]

You're not guaranteed to have any cards with opposite parity, or which are divisible by a number. One would have to find a way to have each card communicate one of three things about the 4th cards. Using position only allows this to be done with the first card, but my original point isn't valid because I realized that the choice of which card is the 4th card is up to you.

Edit: misread your post. I realize now that odd/even/divisibility were the questions that you have to ask. This would work but it's still only communicating 1 of 8 things.

 

[daniel_i_l]

It is definitely possible. I just want to make it clear that it doesn't have to possible for any 3 out of the 4 cards - only for one set of three for every set of four.

 

[yyat]

Let M be the set {1,2,3,...,27}, A the set of 4-element subsets of M, B the set of 3-element subsets of M. Note that A has 17550 elements, B has 2925 elements and that 17550/2925=6.
The problem is then equivalent to finding a function F from A to B such that F^-1(b), the set of preimages of b, is a 6-element subset of A for any b in B and $$F(a)\subset a$$.

To see this, assume you and your partner agree on such a function and also a numbering 1,..,6 of the elements of F^-1(b) for each b. Then, for any set a of four cards, you show the cards F(a) and use the permutation to communicate which of the six preimages of F(a) is a.

It seems plausible that such a function exists, although I have not yet found an elegant construction.

 

[daniel_i_l]

yyat - you're on the right track

 

[Strilanc]

- Draw 4 cards.
- Divide the cards into groups {1 to 9}, {10 to 18}, {19 to 27}.
- You have at least two cards from one of the groups. One of them is lower than other (lower defined as fewer increments for == (mod 9)). Show the lower card and note the other as the target.
- There are now only 4 cards that could be validly guessed as the target (the 4 following the one you showed; wrapping around from 9 to 1, 18 to 10, 27 to 19).

... and that's as far as I get. Next two cards only give 1 bit of the 2 required bits of information.

 

[DaleSwanson]

- Draw 4 cards.
- Divide the cards into groups {1 to 9}, {10 to 18}, {19 to 27}.
- You have at least two cards from one of the groups. One of them is lower than other (lower defined as fewer increments for == (mod 9)). Show the lower card and note the other as the target.
- There are now only 4 cards that could be validly guessed as the target (the 4 following the one you showed; wrapping around from 9 to 1, 18 to 10, 27 to 19).

... and that's as far as I get. Next two cards only give 1 bit of the 2 required bits of information.

This is interesting, but either I don't understand something, or there is a problem. Say I pulled 6 9 13 22. 6 and 9 would be my two in one group, 9 is "lower" because 9 mod 9 is 0. I show 9, however I don't see how that tells you any info about what the other card is (other than it must be 1-8).

Edit: Ok, I've gone over your method a bit, and I think I misunderstood. In the above example I would show 6 instead. The pair must always be within 4 cards of each other, and one will be lower in that way. It's pretty hard to explain clearly, but I think I understand now what you are doing.

 

[Soca fo so]

Umm, I might be being really silly but couldn't you just show the same card more than once (i.e. up to 3 times)?

Then you would have 3³ = 27 different pieces of information you could show with the 3 cards, or was that what you meant by no patterns?

 

[chronon]

In general you pick n cards out of a pack of P=n!+n-1 cards and are allowed to show your partner n-1 of them. He then has to be able to work out what the remaining one is based on a rule which you have agreed.
-----------------------------------------------------------
For n=1, P=1. You pick the only card in the pack but keep it hidden. I think your partner can work out what it is.
-----------------------------------------------------------
For n=2,P=3. You pick two cards and show one of them. Your cards must be adjacent modulo 3 (i.e. they must be 1,2 2,3 or 3,1) you show the first of the pair, and your partner adds one to get the next card
-----------------------------------------------------------
For n=3, P=8. You pick three cards and show two of them. Here you have to think about the gaps between the cards. There are seven possibilities:

1,1,6
1,2,5
2,1,5
1,3,4
3,1,4
2,2,4
2,3,3

You and your partner memoise these possibilities. For each of these you show two cards with a certain gap between them e.g.

1,1,6 ~ 7
1,2,5 ~ 6
2,1,5 ~ 5
1,3,4 ~ 4
3,1,4 ~ 1
2,2,4 ~ 2
2,3,3 ~ 3

Say you picked 2,3,7. The gaps here are 1,4,3 i.e. the 3,1,4 pattern. You show the 2 and the 3 with a gap of 1 and your partner knows that the next gap must be 4, giving the 7 card.
-----------------------------------------------------------
For n=4, P=27. It looks like you would need a code for 650 different possibilities. As the case for n=3 seems pretty ad hoc, I'm not sure that it gives much help.
-----------------------------------------------------------
Note that for n=3 and n=4 we have P=(n-1)^3 . I'm not sure whether this just confuses things or whether it might help by expressing each card as a 3 digit binary or ternary numbe respectively.

 

[Soca fo so]

Umm, I might be being really silly but couldn't you just show the same card more than once (i.e. up to 3 times)?

Then you would have 3³ = 27 different pieces of information you could show with the 3 cards, or was that what you meant by no patterns?

Sorry I see where I was being stupid now, you want all four cards.

It does seem possible since the number of ordered 3 element subsets of the 27 cards is 17550 and the number of unordered 4 element subsets is also 17550, but then you've got the complication that the 3-subset you show to your partner has to be included in the 4-subset you're describing.

So for every unordered 3 element subset there are 24 unordered 4 element subsets it could be included in, and for every 6 ordered 3 element subsets that share the same elements there are also 24 unordered 4 element subsets they could be included in. So by splitting the 24 4-subsets into 6 in some way, you could narrow it down to 4 cards that it could be.

That's as far as I get so far, I keep running into this problem that I'm left with 4 cards it could be.

 

[bpet]

Sum the numbers on the four cards, take the remainder M modulo 4 (taking 0 as 4), and drop the Mth smallest card. For the 3 remaining cards there are exactly 6 possible cards that the other one could be, and this is determined by the permutation number of the order of the cards presented.

The strategy works for n=1,2,3 and I'd guess for higher n-values too but I don't know of an elegant proof (i.e. not involving brute force).

 

[maze]

I wrote a small program to construct yyat's function by brute force. Here is the resulting mapping in a text file, all 17000+ entries (file is about 500 kb):
http://www.wikiupload.com/download_page.php?id=101732

 

[yyat]

Sum the numbers on the four cards, take the remainder M modulo 4 (taking 0 as 4), and drop the Mth smallest card. For the 3 remaining cards there are exactly 6 possible cards that the other one could be, and this is determined by the permutation number of the order of the cards presented.

The strategy works for n=1,2,3 and I'd guess for higher n-values too but I don't know of an elegant proof (i.e. not involving brute force).

Say, for example, I pick 1, 4, 6, 8. That sums to 19=3 mod 4, so I hide 6 show the cards 1, 4, 8 in a certain permutation. Say my partner knows (but how?) that the remaining card is =2 mod 4. But then there are 7 possibilities: 2, 6, 10, 14, 18, 22, 26.

 

[bpet]

Say, for example, I pick 1, 4, 6, 8. That sums to 19=3 mod 4, so I hide 6 show the cards 1, 4, 8 in a certain permutation. Say my partner knows (but how?) that the remaining card is =2 mod 4. But then there are 7 possibilities: 2, 6, 10, 14, 18, 22, 26.

For the cards 1, 4, 8 the only 6 possibilities are 6, 11, 15, 19, 23, 27. All the other cards would result in one of 1, 4, 8 being hidden.

 

[Soca fo so]

Can I ask a stupid question - does the partner need to know (or be able to work out) what the permutations mean before they know what 3 cards (not order though) I show them?

Otherwise couldn't I just cheat and divide the 24 cards into 6 sets of 4 and put 1 odd card in a set together with 3 evens, and 1 even in a set together with 3 odds, and so on..., and after showing my partner the permutation with 1 odd or 1 even say "guess which card." ?

 

[yyat]

I think I now understand bpet's algorithm.

You and your partner agree on a numbering 1,2,3,4,5,6 of the permutations of a three element set.

You take four cards with numbers a,b,c,d between 1 and 27.

Let S be the unique number between 1 and 4 congruent to a+b+c+d mod 4.
The S'th card has a number, say w, and the other cards have some numbers x,y,z.
Define K=w-S, this is a number between 0 and 23.
Compute P=floor(K/4), a number between 0 and 5.

You show your partner the cards x,y,z in the permutation given by P.

Now your partner can compute K=(-x-y-z mod 4) + P*4, and this gives w easily as follows:
We can assume x<y<z.
If K<x then w=K+1.
If x-1<K<y-1 then w=K+2.
If y-2<K<z-2 then w=K+3.
If z-3<K then w=K+4.

This should work!

 

[Soca fo so]

I think I might see how bpet's method could generalise to the n card case.

You pick n cards out of a pack of P=n!+n-1 cards and are allowed to show your partner n-1 of them. This leaves you to represent n! cards with (n-1)! permutations, so you have to cut down the number of possible cards by a factor of n!/(n-1)!=n.

To do this you sum the n cards you picked, and take the remainder M modulo n, with M=0 taken as M=n, and drop the Mth smallest card which hopefully leaves you with (n-1)! possible cards for which you can use the permutation number to distinguish.

So for n=2 you have the cards a,b and use M modulo 2 to choose which one not to show, for n=3 you use M modulo 3, n=4 M modulo 4, and so on.

Hopefully this would also work for n=5 and higher but I haven't checked that.

EDIT.

Okay I think I'm beginning to understand why it works, because there are only n possible values of M (taking M=0 and M=n as the same) that each of the n!+n-1-(n-1) cards (when summed with the (n-1) you show) can have, it gives each card a place in the sequence of th resulting n cards which may or may not match it's place in the sequence when the cards are sorted in ascending order, and iff there are exactly (n-1)! cards (when summed with the n-1 cards you have shown) in a set of n!+(n-1) cards (less the (n-1) you've shown) that have the remainder M that puts them in the correct place in the sequence when the cards are sorted in ascending order, then it does the job you need of cutting the possibilities by a factor n.

EDIT 2.

I'm not sure this is correct, but I think I possibly understand now why M modulo n would choose exactly (n-1)! cards for a given n-1 cards you show. Because as you go through checking the n!+(n-1)-(n-1)=n! cards left in ascending order you find that the values of M repeat every n cards, and for every n cards only one of them can be the correct size for it's value of M. So for the n! cards only n!/n=(n-1)! have the correct value of M.

 

[pinchharmonic]

assumptions:
you can use the 4th card, but it is face down always
you don't have to face up all the cards, but just at most 3 like rule states
don't have to show 3 cards, can show less

partner must sort all cards 1-27, forget about the 1-24

if 4 cards are shown, turn it into a 4-bit binary, giving us 1-16 possibilities. Face up is 1, face down is 0.

** However, The one problem here is the 4th card is always face down, and because of that the 1-1-1-1 cannot be used. 1-1-1-1 in binary is 16, so we remove one possibility giving is 1-15. We conveniently turn that into the 1-15 of the 27 cards

if 3 cards are shown, turn it into a 3-bit binary giving us 8 possibilities, just correspond those to 16-23

if 2 cards are shown, turn that into a 2-bit binary giving 4 possibilities, correspond those to 24-27

the problem is solved at this point, but you still have the ability to do a 1-bit binary so i guess you could have another 2 cards so the problem could be changed to 29 cards?

 

[hillzagold]

Ok, so you can only show him the number of the 3 cards you have in a particular order? You can't, say, turn one card upside down, another card face down, a third card hidden?

Alright, if the only things I can guarantee are there are 27 cards total, I have 4. Of those 4 cards, you have the S card, the M card, the L card, and the XL card. You can pick any of these 3 cards in any order to reveal what the last card is. That means the possible orders are:
XL L M - S
XL L S - M
XL M L - S
XL M S - L
XL S L - M
XL S M -L
times 4 because you get the idea now.

This of course, could form a simple code for to represent a number [1, 24] if you could manage to convey which size your hidden card is. All your partner sees are the 3 cards you show, and to him they go S M L, so all he sees is:
LMS
LMS
LSM
LMS
LSM
LSM
times 4 again
It's very late where I am so I won't be able to finish this problem, but I figure there must be a way to convey what your hidden card size is using the 3 revealed card sizes, and then using the 4 card sizes to find the 4th card's value. Since you can choose what size the hidden card has, I'm guessing this is somehow possible.