Qbasicnews.com
September 17, 2019, 08:20:33 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1] 2
  Print  
Author Topic: Alice and Bob  (Read 11312 times)
DefHo
Member
*
Posts: 74



« 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 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!
Logged

hat were we arguing about again?
Andrew Collins
Member
*
Posts: 46


« Reply #1 on: December 31, 2005, 05:56:48 PM »

Well if the deck isn't shuffled isn't this kinda... too easy?
Logged
DefHo
Member
*
Posts: 74



« Reply #2 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.
Logged

hat were we arguing about again?
Deleter
Na_th_an
*****
Posts: 1292



WWW
« Reply #3 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.... :Huh:

I am bad with probability and all that stuff though.
Logged

Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #4 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...
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #5 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:
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
DefHo
Member
*
Posts: 74



« Reply #6 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. Tongue 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!
Logged

hat were we arguing about again?
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #7 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.
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #8 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?
Logged
DefHo
Member
*
Posts: 74



« Reply #9 on: January 02, 2006, 12:52:41 PM »

Any 5 cards.
Logged

hat were we arguing about again?
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #10 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.
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #11 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?
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #12 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...
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
vspickelen
Member
*
Posts: 26



WWW
« Reply #13 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
Logged
Sterling Christensen
Na_th_an
*****
Posts: 1328


« Reply #14 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?
Logged
Pages: [1] 2
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!