[math-fun] Number theory question
Let !n = 0! + 1! + ... + n! = A003422(n) For integer k, is it true that !a == k (mod a) and !b == k (mod b) together imply !c == k (mod c) where c = lcm(a, b) ?
You have to perform a random binary experiment in front of a crowd of people — so no fooling is allowed — in such a way that everyone is convinced that the experiment was fair. The people include some technical experts but many who are not. What is the simplest / easiest / cheapest way to ensure that the crowd will be convinced that the experiment was fair (the two outcomes had an equal chance of occurring) ??? —Dan P.S. I do not have an answer to this, but maybe there is a "best" answer.
I'll pose a slightly different question -- how would a group of physicists assure a 50/50 outcome? One might use a light source and two detectors, one generating 0's the other 1's. But there will be some slight difference in detector sensitivity. You will have to set a spec, like 51/49 or better, and then tweak the experiment. -- Gene On Wednesday, May 31, 2017, 2:30:10 PM PDT, Dan Asimov <asimov@msri.org> wrote:You have to perform a random binary experiment in front of a crowd of people — so no fooling is allowed — in such a way that everyone is convinced that the experiment was fair. The people include some technical experts but many who are not. What is the simplest / easiest / cheapest way to ensure that the crowd will be convinced that the experiment was fair (the two outcomes had an equal chance of occurring) ??? —Dan P.S. I do not have an answer to this, but maybe there is a "best" answer. _______________________________________________
Gene, The people at Fourmilab's "HotBits" site, which publishes random bit based on radioactive decay, have given quite a bit of thought to the problem of transforming a possibly-nonuniform random variable into a uniform one. See https://www.fourmilab.ch/hotbits/how3.html for details. Dan, I'm pretty sure I still don't understand your question. Can you flesh out the situation more completely, with a little more storytelling to elucidate the demonstrator's motivation and the skeptical audience's problem? On Wed, May 31, 2017 at 6:38 PM, Eugene Salamin via math-fun < math-fun@mailman.xmission.com> wrote:
I'll pose a slightly different question -- how would a group of physicists assure a 50/50 outcome? One might use a light source and two detectors, one generating 0's the other 1's. But there will be some slight difference in detector sensitivity. You will have to set a spec, like 51/49 or better, and then tweak the experiment.
-- Gene
On Wednesday, May 31, 2017, 2:30:10 PM PDT, Dan Asimov <asimov@msri.org> wrote:You have to perform a random binary experiment in front of a crowd of people —
so no fooling is allowed — in such a way that everyone is convinced that
the experiment was fair. The people include some technical experts but many
who are not.
What is the simplest / easiest / cheapest way to ensure that the crowd will
be convinced that the experiment was fair (the two outcomes had an equal
chance of occurring) ???
—Dan
P.S. I do not have an answer to this, but maybe there is a "best" answer. _______________________________________________
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
In general, I don't think that any amount of *passive* observation will be convincing. Science is only believable when *independent* experiments are supplied with *independent* random streams of bits; i.e., if I am allowed to perform the experiment myself using my own source of random bits. ("Supply a wiggle in, and see what wiggles out") Of course, this raises the following possibility (sci-fi writers, listen up!): In the future, the NSA will be tasked as a monopoly providing all necessary random bits. It does this by producing quantum entangled pairs of particles, supplying the market with one of each pair, and keeping the other particle in labeled storage. If/when the NSA customer "measures" one of the "market" particles, the entangled particle will also assume the same state, so the customer will have his random bit, and the NSA will also be happy. At 02:31 PM 5/31/2017, Dan Asimov wrote:
You have to perform a random binary experiment in front of a crowd of people  so no fooling is allowed  in in such a way that everyone is convinced that the experiment was fair.
The people include some technical experts but many who are not.
What is the simplest / easiest / cheapest way to ensure that the crowd will be convinced that the experiment was fair (the two outcomes had an equal chance of occurring) ???
ÂDan
P.S. I do not have ann answer to this, but maybe there is a "best" answer.
One must understand that there is no instantaneous action at a distance that alters something about one entangled particle when its partner is measured. It is only when both particles are measured, and the measurements results brought together, at most at light speed, and compared, that the entanglement is manifest. Then, if both parties agree in advance to measure the same state, for example the circular polarization of a photon, that, surprisingly, the distant measurements always happen to agree, or always are opposite. But if one party measures circular polarization, and other measures linear polarization in some direction, the results will have no correlation. If the NSA were providing random bits, it would be simplest to provide standard digital bits, and keep a copy for itself. -- Gene On Wednesday, May 31, 2017, 5:21:36 PM PDT, Henry Baker <hbaker1@pipeline.com> wrote:In general, I don't think that any amount of *passive* observation will be convincing. Science is only believable when *independent* experiments are supplied with *independent* random streams of bits; i.e., if I am allowed to perform the experiment myself using my own source of random bits. ("Supply a wiggle in, and see what wiggles out") Of course, this raises the following possibility (sci-fi writers, listen up!): In the future, the NSA will be tasked as a monopoly providing all necessary random bits. It does this by producing quantum entangled pairs of particles, supplying the market with one of each pair, and keeping the other particle in labeled storage. If/when the NSA customer "measures" one of the "market" particles, the entangled particle will also assume the same state, so the customer will have his random bit, and the NSA will also be happy. At 02:31 PM 5/31/2017, Dan Asimov wrote:
You have to perform a random binary experiment in front of a crowd of people — so no fooling is allowed — in in such a way that everyone is convinced that the experiment was fair.
The people include some technical experts but many who are not.
What is the simplest / easiest / cheapest way to ensure that the crowd will be convinced that the experiment was fair (the two outcomes had an equal chance of occurring) ???
—Dan
P.S. I do not have ann answer to this, but maybe there is a "best" answer.
Announce in advance "an odd number of Heads is outcome A". Everyone in the crowd flips his own coin in private, and reports the answer in a sealed envelope, the "ballot". The ballots are opened in full view, and Heads are counted. No particular problems with a stuffed ballot box, or multiple voting, or individuals choosing to used biased coins or just plain cheat. As long as observers are sure that every ballot is counted, anyone who cares about the outcome has contributed his own version of a random bit. Rich ------------ Quoting Henry Baker <hbaker1@pipeline.com>:
In general, I don't think that any amount of *passive* observation will be convincing.
Science is only believable when *independent* experiments are supplied with *independent* random streams of bits; i.e., if I am allowed to perform the experiment myself using my own source of random bits. ("Supply a wiggle in, and see what wiggles out")
Of course, this raises the following possibility (sci-fi writers, listen up!):
In the future, the NSA will be tasked as a monopoly providing all necessary random bits. It does this by producing quantum entangled pairs of particles, supplying the market with one of each pair, and keeping the other particle in labeled storage.
If/when the NSA customer "measures" one of the "market" particles, the entangled particle will also assume the same state, so the customer will have his random bit, and the NSA will also be happy.
At 02:31 PM 5/31/2017, Dan Asimov wrote:
You have to perform a random binary experiment in front of a crowd of people so no fooling is allowed in in such a way that everyone is convinced that the experiment was fair.
The people include some technical experts but many who are not.
What is the simplest / easiest / cheapest way to ensure that the crowd will be convinced that the experiment was fair (the two outcomes had an equal chance of occurring) ???
Dan
P.S. I do not have ann answer to this, but maybe there is a "best" answer.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If the crowd is allowed to participate, here's what I would do. Each person in the crowd who wants to participate is given a black card and a white card. There is a countdown, and at the end of it, each member of the audience is to raise one card or the other in the air. Official pictures are taken, and the audience is also encouraged to take their own photographs. The generated bit is 1 if there are an odd number of white cards, 0 if there are an even number of white cards. The black cards aren't strictly necessary, but should help resolve ambiguity over whether a given white card is raised. If the crowd is large, it would be better to select a dozen members of the audience to to up on stage, and only those dozen get to choose black or white. They can be positioned with barriers so they cannot see each other, but the audience can see all of them, Of course, this requires those audience members to be randomly selected, in a way that convinces the crowd that the selection process is random. But all the audience needs to be convinced of is that if there is dishonesty, at least one of the selected members is not part of the conspiracy. I've seen methods like throwing an object into the audience, where the person who catches it is supposed to throw it backwards over their head, and the person who catches that throw (or the one after that, but specified in advance) is the selection. To be convinced that the final result is random, I don't need to believe that the audience members are selected with exactly equal probability; I just have to be convinced that a large number of people (larger than the size of the conspiracy) had a reasonable chance of being selected. If you have to convince an audience member who thinks that there is a massive conspiracy, and everyone in the entire crowd except him is in cahoots trying to make him think the selection is random, this doesn't work. Andy On Wed, May 31, 2017 at 5:31 PM, Dan Asimov <asimov@msri.org> wrote:
You have to perform a random binary experiment in front of a crowd of people —
so no fooling is allowed — in such a way that everyone is convinced that
the experiment was fair. The people include some technical experts but many
who are not.
What is the simplest / easiest / cheapest way to ensure that the crowd will
be convinced that the experiment was fair (the two outcomes had an equal
chance of occurring) ???
—Dan
P.S. I do not have an answer to this, but maybe there is a "best" answer. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
Yes: !x (mod a) stops changing at x=a or sooner, since y! = 0 when y>=a. So !c (mod a) = !a (mod a) = k (mod a), and ditto for b replacing a. Therefore, !c = k both (mod a) and (mod b), whence mod LCM(a,b). qed. Rich PS: a=0 needs to be treated as a special case, since congruence mod 0 is a tad squirrely, and LCM(0,x)=0 violates the usual rule LCM(a,b)>=max(a,b), which is implicitly used in the above proof. --R ----- Quoting David Wilson <davidwwilson@comcast.net>:
Let !n = 0! + 1! + ... + n! = A003422(n)
For integer k, is it true that
!a == k (mod a)
and
!b == k (mod b)
together imply
!c == k (mod c)
where
c = lcm(a, b)
?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Allan Wechsler -
Andy Latto -
Dan Asimov -
David Wilson -
Eugene Salamin -
Henry Baker -
rcs＠xmission.com