I just overheard the following conversation snippet between Alice and Bob:
Alice: I want to generate three independent variables: one fair die throw and two fair coin flips Bob: Here, I have a die and a coin A: No, I'd like to use only one item B: So throw a die three times and ... A: OK, I'll throw three dice and give you the ordered integer triplet [a,b,c] where 1<=a<=b<=c<=6 B: Hmm, that's not what I had in mind... but if you want I can compute the integer triplet x,y,z from a,b,c such that 0<=x<=1, 0<=y<=1, and 1<=z<=6 A: Great, x and y will be my coin flips and z will be my die B: And I need less than 60 operations for that with no more than four intermediate variables A: Nice. How do you do that? B: I only used operations from the following list: addition, subtraction, multiplication, integer division, integer modulo, integer exponentiation, and binary operation (and, or, xor). A: I can allow unlimited parentheses. So how do you do that? B:
Alas, a noisy bus went by and I missed the rest of the conversation.
Can you help me? Please suggest a possible answer for how Bob proposed to solve this challenge, given that stated above.
Remember that the tosses should be fair and independent, i.e. every combination of x,y,z should have exactly the same probability.
The binary operations are bitwise. Negative numbers are stored in two's complement. To make things simpler, we'll count the number of characters in the expression (parentheses are free) and allow for 125 characters. As an example (5*a)-(b&1234)+9 is counted as 12 characters; ((5*a)-(b&1234)+9)*((5*a)-(b&1234)+9) is 25; alternatively we can compute the same expression with only 15 characters and one intermediate variable: d=(5*a)-(b&1234)+9 and compute d*d.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the firstname.lastname@example.org.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to:email@example.com
30/10/2017 @ 12:00 PM EST Solution:
02/12/2017 @ 12:00 PM EST List Updated:
03/12/2017 @ 12:00 PM EST
People who answered correctly:
Bert Dobbelaere (31/10/17 12:26 AM IDT) Daniëlle van den Berg (31/10/17 12:00 PM IDT) Kang Jin Cho (31/10/17 10:35 am IDT) Ariel Landau (02/11/17 03:05 PM IDT) Chuck Carroll (03/11/17 04:59 AM IDT) Bert Dobbelaere (03/11/17 02:33 PM IDT) Dmitry Kim (03/11/17 04:03 PM IDT) Tom Harley (07/11/17 11:16 PM IDT) Motty Porat (08/11/17 01:34 AM IDT) Andreas Stiller (08/11/17 04:44 PM IDT) Victor Kuznetsov (10/11/17 06:23 PM IDT) Jim Clare (11/11/17 18:47 PM IDT) David Greer (12/11/17 01:07 AM IDT) Alper Halbutogullari (13/11/17 04:28 AM IDT) Tyler Mullen (13/11/17 08:58 AM IDT) Boris Silantyev (15/11/17 06:57 PM IDT) Dan Salajan (15/11/17 07:50 PM IDT) Robert Lang (16/11/17 11:29 AM IDT) Shirish Chinchalkar (19/11/17 06:00 PM IDT) Rocke Verser (20/11/17 04:40 PM IDT) Adam Daire (27/11/17 12:56 AM IDT) Bryce Herdt (28/11/17 10:44 PM IDT) Oscar Volpatti (01/12/17 07:38 AM IDT) Vladimir Volevich (01/12/17 12:47 PM IDT)