wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Saint Nicholas assignment
        
(Message started by: Andre on Sep 2^nd, 2007, 4:06pm)

Title: Saint Nicholas assignment
Post by Andre on Sep 2^nd, 2007, 4:06pm

Given N>=3 cards labelled 1 up to N, and N envelopes, also labelled 1 up to N. How can you put a card in each of the envelopes so that
- no envelope holds a card with the same number
- you do not know of any envelope what card number it contains

This is a real world problem. In Holland we celebrate Sinterklaas (Saint Nicholas) on December 5. Young children get presents from Sinterklaas himself, as they are led to believe. Older children and adults form groups (families, friends, school classes). Each group member acts for Sinterklaas, and anonymously creates a "surprise" gift for one other group member. He wraps or presents the gift in a funny or artful way, and includes a poem (rhyme), that the recipient should read aloud.

Title: Re: Saint Nicholas assignment
Post by gotit on Sep 2^nd, 2007, 4:41pm

For filling up the first N-2 cards,we can simply put any card in an envelope provided their numbers do not match.When I am left with the last 2 envelopes the following 3 conditions can arise:

i)Envelope no. are i and j and card numbers are x and y and both x and y are different from both i and j.In this case we can put any card in any of the 2 envelopes.

ii)Exactly one card number matches one envelope number e.g j and x are same.In this case we put x in i and y in j.

iii)Both the card numbers matches the envelope numbers e.g x=i and y=j.In this case we put y in i and x in j.

Title: Re: Saint Nicholas assignment
Post by Eigenray on Sep 2^nd, 2007, 7:16pm

Each person picks a secret number s_n and writes it on a card. The cards are then mixed together; if any two have the same number, start over again.

This way, if person n sees s_m on a card, the only thing they can determine is whether or not m = n. So each person can simply take a card other than their own, and person n buys a present for whoever has card s_n.

Of course, you have to be careful: if you're last to pick, and the only card remaining is yours, you have to start over again, because if you say "hey, anyone want to trade?" people will know your number.

If you're allowed some information loss, as long as nobody can know for certain anyone's card, you can have everyone raise their hand if either: (a) they have their own card, or (b) they don't have their own card, but they (secretly) flipped a coin and it came up heads. Then, everyone with raised hands (and another person picked at random if only one person raised their hand) shuffle the cards amongst themselves and repeat the process.

Of course, the easiest thing to do would be to just ask a third party to do it, human or computer.

Title: Re: Saint Nicholas assignment
Post by Andre on Sep 3^rd, 2007, 12:53am

@gotit
You are not supposed to see in what envelope what card goes

@Eigenray
The assignment must be final. After putting the cards in the envelopes, you are not allowed to redo it.
You are also not allowed to write other things on the cards.

Hint: [hide]valid operations are like: shuffle cards or envelopes randomly, and put a card in an envelope[/hide]

Title: Re: Saint Nicholas assignment
Post by towr on Sep 3^rd, 2007, 1:37am

[hide]Put each envelope with the card with the same number, put them down such that you can't see the numbers, randomize them, pick two, switch the cards, finalize one of the pairs (putting the card in the envelope), pick a new pair, repeat untill all pairs have been picked and switched.[/hide]

Title: Re: Saint Nicholas assignment
Post by FiBsTeR on Sep 3^rd, 2007, 8:32am

Similar to towr's method:

[hide]Match each k^th envelope with the k^th card. Shuffle the pairs while still leaving each card with the envelope of the same number. Arrange the pairs in a circle and finalize the pair of each card with the envelope to its immediate left. Or if you don't like circles, put them in a line and have the leftmost card pair with the rightmost envelope.[/hide]

Title: Re: Saint Nicholas assignment
Post by Grimbal on Sep 3^rd, 2007, 8:40am

(forget it, everybody has the same idea before me... ) :-/

I thought of a similar idea.
Put each card in its own envelope, shuffle them well, make a stack,
take the card from the last envelope (face down),
take out the card from the first envelope, replace it with the card from the last envelope,
take out the card from the second envelope, replace it with the card from the first envelope,
etc.
At the end, put the card in the empty last envelope.

You can also distribute the work by making smaller stacks and process each stack like this.

Title: Re: Saint Nicholas assignment
Post by Andre on Sep 3^rd, 2007, 10:49am

That is correct.
Only, it is recommended to shuffle the envelopes once more just before bringing their faces up again.

Title: Re: Saint Nicholas assignment
Post by Grimbal on Sep 3^rd, 2007, 2:56pm

Good point. Very likely they would end up in a hat.