Qbasicnews.com

QbasicNews.Com => Challenges => Topic started by: DefHo on December 31, 2005, 05:52:50 PM



Title: Alice and Bob
Post by: DefHo on December 31, 2005, 05:52:50 PM
Alice and Bob are magicians. Alice asks a volunteer to randomly draw five playing cards from a deck. She takes the cards from the volunteer and looks at them without revealing them to anyone else. Alice then begins showing them to Bob one at a time. After the fourth card, Bob correctly guesses what the fifth card is. The secret to this trick was to come up with an algorithm that when given any five cards, could order four of them so that the fifth could be guessed by this order. (See where this is going yet?)

The challenge is for you to come up with said algorithm and implement it in QB or FB. Your program should describe the algorithm to the user, give him five random cards, ask for four cards back and then return the fifth. In other words, the user will be Alice and the program will be the audience member and Bob. (You just have to make sure that Bob is a separate function or that would be cheating.) There are many possible solutions, most of which are surprisingly simple.

Rules:

1) Don't post your code here! Put it in a folder along with a compiled (.exe) version of your file and fileanchor (http://fileanchor.com) it. You can post a link to it here. This will prevent people that want to solve this themselves from having to see the answer.

2) There will be no time limit on this challenge.

3) The winner will be the first person to come up with a working program that correctly guesses the fifth card every time. However, even if there is already a winner I encourage you to still participate. I would love to see different solutions to this.

4) If you haven't found a solution, don't peek at the others. This is really for your benefit. It's much more satisfying to find a solution yourself than to just read it.

5) If after a week no one has solved this, you can PM me for a hint. After another week, you can PM again for another hint. But like I said, it's much more rewarding to solve this on your own.

6) There won't be a prize for this because, well, I don't have anything  :lol: I guess a hearty pat on the back from me will have to do. And of course all the fame and recognition you get from winning a Qbasicnews challenge!

7) Finally, this isn't my homework assignment so don't harass me with accusations. I have a solution of my own already.


If you have a question about this challenge or need something explained better just post it here. I tried to explain it as plainly as possible but I know it can still sound confusing. Hopefully someone will be able to put it in simpler terms.

Ok. Have fun!


Title: Alice and Bob
Post by: Andrew Collins on December 31, 2005, 05:56:48 PM
Well if the deck isn't shuffled isn't this kinda... too easy?


Title: Alice and Bob
Post by: DefHo on December 31, 2005, 06:29:36 PM
Not exactly. Since the audience member can choose any five cards from the deck it doesn't matter if it's shuffled or not. That was my fault though. I should have described it a little better. I just fixed my post to correct this.


Title: Alice and Bob
Post by: Deleter on December 31, 2005, 08:50:41 PM
Can you really develop that sorta algorithim? Doesn't seem possible to me as it is completely random.... :???:

I am bad with probability and all that stuff though.


Title: Alice and Bob
Post by: Sterling Christensen on December 31, 2005, 09:52:14 PM
You mean like this?

http://fileanchor.com/14880-d
(there are only 3 important parts, they're wrapped in dashed lines ------)

I don't see how else it's possible...


Title: Alice and Bob
Post by: Agamemnus on January 01, 2006, 03:14:05 AM
Happy new year, and you've left out a part of the puzzle. I've googled it and found solutions, but the critical aspect is that you're supposed to let Alice choose what cards she will pick and in what order. It's cheating to give us an algorithm in a paragraph and not give us an exact definition!  :cry:


Title: Alice and Bob
Post by: DefHo on January 01, 2006, 08:43:54 PM
Damn, I forgot to say that Alice looks at the cards first. Agamemnus is right. Alice has to decide which four cards to give to Bob and in what order they go. You're supposed to figure that out by the way the trick plays out but I told it wrong so it's even more confusing. :P I knew this was gonna tough to explain. Please bear with me. This is a really cool challenge once you understand it. I'll edit my original post so it should be correct.

Sorry Sterling. It has to work for any five cards not just consecutive cards. And yes, it is possible. Oh, and happy new year!


Title: Alice and Bob
Post by: Agamemnus on January 01, 2006, 11:20:39 PM
And also... one other thing...

They come up with a strategy beforehand.... of what Bob should reply given a set of 4 cards. Now it's really simple.

Here's the puzzle again in those terms:

Entity C randomly picks 5 cards from a deck of cards. Each card in the deck is unique. Entity C gives these cards to Entity A. Entity A shows 4 of these cards in any order to Entity B. The order of the cards and the identity of each card is the only information Entity B receives after the cards are shown.

Entity A and Entity B can share any information before Entity C picks these cards.

Create an algorithm such that, given these 4 cards, entity B can identify the fifth card.


Title: Alice and Bob
Post by: Sterling Christensen on January 02, 2006, 01:15:08 AM
Quote from: "Agamemnus"
Entity C randomly picks 5 cards from a deck of cards.

Any 5 cards, or any 5 contiguous cards?


Title: Alice and Bob
Post by: DefHo on January 02, 2006, 12:52:41 PM
Any 5 cards.


Title: Alice and Bob
Post by: Agamemnus on January 02, 2006, 06:12:30 PM
You can even do this with up to 124 unique cards. (in the deck)

There is only one way to do this trick with exactly 124 cards. With 52 cards, I tried to find out how many ways, but I couldn't figure out what 6497400! was.


Title: Alice and Bob
Post by: Sterling Christensen on January 03, 2006, 08:19:32 AM
I still don't see how it's possible (I don't want to ruin it by looking up a solution). This is the best I can think of:

Let say the cards in the deck have been assigned numbers 1 to 52.

Volunteer randomly picks 5 cards.

Alice always shows the 4 lowest numbered cards to Bob. This way Bob knows the fifth card is higher than the highest card he's show. The worst case scenario is the first 4 cards get picked - then there are still 48 possibilities. Best case scenario is #51 and #52 getting picked - Bob is shown #51 and knows the fifth has to be #52.

Alice doesn't have to show them to Bob in the same order they were picked, right? Maybe it could mean something different to Bob depending on whether he's first shown the highest of the 4, or the lowest of the 4, etc.
4 * 3 * 2 * 1 = 24 different ways to order the 4 cards. So in the worst case scenario this could cut it down to 48 / 24 = 2 possibilites.

And that's where I get stuck. Can I have a hint?


Title: Alice and Bob
Post by: Agamemnus on January 04, 2006, 03:05:55 AM
I was looking for solutions, but they were all a little too geometrical for me. But here is proof that there is at least one solution:

The number of combinations of 4 cards shown from 52 cards (in one of 24 orderings) is:
(52 choose 4) * 24.

The number of combinations of 5 unsorted cards picked from 52 cards is (52 choose 5).

You can see that these are vastly different amounts. For 124 cards, they are equal, indicating one unique solution.

Numerically, I'm still stumped as to how to solve this problem however...


Title: Alice and Bob
Post by: vspickelen on January 04, 2006, 10:08:48 AM
Hi there,

I thought it would be more convincing to split up the solver,
so that Alice & Bob are two independant entities,
communicating only through a little shared show-file.

You'll find them here:
http://home.graffiti.net/vspickelen:graffiti.net/doos/Cards.zip

Regards,
vspickelen


Title: Alice and Bob
Post by: Sterling Christensen on January 04, 2006, 07:20:53 PM
Quote from: "Cards.zip/readme.txt"
So Alice selects one same-suit card and hides the other,
then uses a permutation of the remaining 3 cards to
encode their distance.

Wait, I thought the volunteer picks all five cards!

You mean the volunteer picks only one card, and Alice gets to pick the other four?


Title: Alice and Bob
Post by: DefHo on January 04, 2006, 09:21:12 PM
I hearby declare vspickelen the winner of this challenge. Special thanks goes to Agamemnus for helping me explain it ;)

Vspickelen, nicely done. That's the same solution I thought of. Not exactly the same but based on the same principles.

Sterling:  (WARNING: spoilers ahead!)
No, the volunteer chooses five cards but Alice gets to decide which card to make the guessed card. She also doesn't need to hide the other suited (signal) card. It just makes it more difficult for the audience to figure out the trick. (BTW, what he meant by "hide" the other card is that by the sum of the shown cards Bob would be able to  determine the location of the same-suited card. For example, if the sum of the four cards divided by four has a remainder of 0, then make the signal card the first card. If the remainder is 1, then make it the second, etc.)

She could, for example, order the cards so that the guessed card always has the same suit as the first card. It's still a bit tricky to solve since now there are only three cards to make a permutation with. (WARNING: more spoilers! Stop here if you want to solve the rest of the problem on your own.) Three cards could only represent six combinations and there are twelve possible cards to guess from. But Alice can choose which of the two suited cards is the guessed card. Now she just orders them so that the following is true:

card1's suit = card5's suit

and

(card1's value + the number shown by the combination [1 through 6]) MOD 13 = card5's value  

(To keep things simple, values could be assigned like: A=1, 2=2, 3=3,.... ,J=11, Q=12, and K=0)
Voila!

Quote
You can even do this with up to 124 unique cards. (in the deck)

 :o  Wow. I didn't know that. Since there wasn't any information left over after my solution, I assumed 52 was the max. That get's me thinking...


Title: Alice and Bob
Post by: vspickelen on January 05, 2006, 02:42:30 PM
Thanks,

I'm in high feathers with my honours,
Cheerz!

vspickelen


Title: Alice and Bob
Post by: Agamemnus on January 06, 2006, 01:20:28 AM
On second thought, I looked at a simpler case of 2 shown cards shown and 3 cards drawn and I don't see how this is possible.. turns out that you just get several different results for every 2 cards.


Title: Alice and Bob
Post by: vspickelen on January 10, 2006, 01:41:34 PM
The 2-card 'message space' is out of proportion to the 52-card deck.
It's far too small to encode the whole 3-card 'uncovered hand space'.
They match only if hand! / (deck - hand + 1) >= 1.

Alie & Ben have recently learned a brilliant strategy from prof. Berlekamp.
Their divination abilities are boundless now. I presented them decks with 8, 27, 52, 124 and even 725 cards.
A fifth card symbol called 'tips' was coined specially for this occasion.

http://home.graffiti.net/vspickelen:graffiti.net/doos/Cardspp.zip

vspickelen


Title: Alice and Bob
Post by: DefHo on January 11, 2006, 02:39:02 AM
But you already won the challenge! Now you're just showing off. (I'm kidding of course :D) It looks interesting. I'll read it more thoroughly when I have time.


Title: Alice and Bob
Post by: vspickelen on January 13, 2006, 07:07:00 AM
Just indulgin', DefHo.
Ain't yo gonna show us what you came up with?


Title: Alice and Bob
Post by: DefHo on January 13, 2006, 05:33:53 PM
My solution to the 52 card problem was pretty much the same as yours. I explained it above. As for the 124 card problem, I brainstormed it but never came up with a working solution. I'll get it eventually.