Easily solved by taking the [EDIT: seconds digits] modulo the number of children, but I guess that might be difficult while driving.
EDIT: People, please try to think this through before posting an innumerate reply.
Edit: For instance, if there are 59 kids, the first one has twice as good a chance to win as any of the others, because both 0 % 59 and 59 % 59 are 0. In other words, in the set derived from x % 59, for x in {0, 1, ..., 59}, 0 appears twice, and each other number in the range 0-59 only appears once.
I never made the claim you're objecting to. The modulo operator minimizes the bias, it doesn't eliminate it. And it's the most efficient way to solve the problem.
My suggestion is that you stop thinking like a lawyer and start thinking like a scientist.
It's already solved. If there are 3 kids, 1-3 go to kid A, 4-6 to kid B, 7-9 to kid C, and 0 means try again. There's no bias present in this solution. Since it only takes a fraction of a second to generate a new digit with a stopwatch (using the hundredths of seconds digit) it's no big deal if you have to try five times.
Your solution introduces unnecessary arithmetic (what's 47 mod 3?) and unnecessary psychological pressure (will the kids start an argument while you're figuring it out? Will the ones who are better at math start taunting the others?) and it introduces bias in a family as large as ours got (7 or 8 kids can't evenly divide 60; 3, 6, or 7 kids can't evenly divide 100.)
A re-roll is simply a superior solution.
[Appeal to authority: my dad had a math degree and was valedictorian of his engineering college. I have bachelors and masters degrees in applied math. My oldest brother competed at the national level in Mathcounts. We all agree this is the best practical solution for this problem. Based on the votes, so does the bulk of the technically-minded Hacker News community.]
http://stackoverflow.com/questions/10984974/why-do-people-sa...
In other words, digit(s) modulo children.
"Try again" and "modulo" do not mean the same thing.
Try again means you discard a result outside of the range, and then generate a new number without any reference to the value of the first try. If you have 7 kids and you're picking 0-9, you discard any results of 7-8-9 (or 8-9-0) and try again.
Modulo means you take a result outside of the range, divide it by the range, and use the remainder (which is guaranteed to be in the range) as your new answer. The problem with this approach is that it's not evenly distributed -- if you have 7 kids and digits 0-9, three of your kids will get double chances. Even if you use 0-59 as your range, some of the kids will have 9 chances and others will have 8 chances.
n n % 4
-----------
0 0
1 1
2 2
3 3
4 0
5 1
6 2
7 3
8 0
9 1
10 2
11 3
12 0
13 1
14 2
15 3 n n % 4
-----------
0 0
1 1
2 2
3 3
4 0
5 1
6 2
7 3
8 0
9 1
10 2
11 3
12 0
13 1
14 2
15 3
The pattern is clear and ubiquitous -- if you actually know something, and if you're foolish enough to post a clear exposition, the morons who never post anything coherent will downvote your posts with a probability approaching certainty.
The modulo operator is the obvious solution to the original question. And if there were't an atmosphere of pervasive anti-intellectualism at HN, this thread would be much shorted than it is.
0 % 7 = 0
1 % 7 = 1
2 % 7 = 2
.
.
.
56 % 7 = 0
57 % 7 = 1
58 % 7 = 2
59 % 7 = 3
0 appears nine times.
1 appears nine times.
2 appears nine times.
3 appears nine times.
4 appears *eight* times.
5 appears *eight* times.
6 appears *eight* times.
You're arguing against something I never said. Large numbers reduce the bias, they don't eliminate it. Notice that earlier I considered the objection of a hypothetical clever child by using the minute digits as well. All these steps only minimize the bias in favor of small numbers, that cannot be eliminated. Even a 64-bit random number possesses this property. And the classic remedy for this bias is to apply the modulo operator to get the desired range.
You've failed to acknowledge the trade-offs of using your solution versus the OP's solution (or the solution above), and you're calling people who are trying to point out the trade-off "morons", that's why you're getting downvoted.
This makes it less efficient - in this case, 18/60 chance of having to redraw, versus 4/60. Taking the modulus of the largest range you can leaves less residue (what lutusp is alluding to, without realizing others are describing a simple way of getting an exact uniform distribution).
If you want to make it more efficient (in terms of entropy used), you need to save the 1-of-prime (eg bits, trits, etc) that have been successfully chosen (uniformly). For example, with 6 children and an 8 sided die (3 bits), a roll of 6 or 7 would narrow the choices to only children 0-2 or 3-5 respectively. Your subsequent rolls could then be done with a 4 sided die.
Would that solution be "multiply by the number of children and divide by ten"? Let's see:
n n * 7 / 10
---------------
0 0
1 0
2 1
3 2
4 2
5 3
6 4
7 4
8 5
9 6
> ... you're calling people who are trying to point out the trade-off "morons", that's why you're getting downvoted.
No, I am being downvoted because I'm right. Being right is simply rude, but being right about something trivially proven is beyond the pale.
No; his/her solution is: If 0-9 couldn't be divided evenly among the kids present, leftover digits would result in a re-roll, exactly as I said above.
> No, I am being downvoted because I'm right
Are you? This is math we're talking about, right and wrong are very precisely defined. For the sake of discussion, can you repeat the question you claim to have the right/correct solution to, and your answer?
Well it's not fair. Take 4 children for example. random 0 to 9 mod 4 does not have an even distribution over 0-4.
It's also more difficult to explain to children.
That's true, but only because 4 never appears in the result. The possible results for modulo 4 are 0 - 3.
The first child is numbered zero. Shall I explain it in more detail?
n n % 4
-----------
0 0
1 1
2 2
3 3
4 0
5 1
6 2
7 3
8 0
9 1
10 2
11 3
12 0
13 1
14 2
15 3
And rewarding, unless you want your children to grow up innumerate.
It certainly does -- the larger the random number, the fairer the outcome is.
> Even if you're using the seconds of a clock, it doesn't work for 7 children.
For a digits range of 0 - 59? Plus the fallback in the face of a precocious child of adding the number of minutes * 60?
if the stopwatch uses hex, then 0-3 will appear equally often in this case
> if the stopwatch uses hex ...
I think we're safely in the red herring zone now. :)
EDIT: Yes, of course -- when confronted by a correct and reasoned reply, downvote it to discourage any such mistakes in the future.
Digits, not digit, please, and do try to limit the anti-intellectualism and adversarial posture.
Say I have 7 children and I get a number 0-9. If the result is 8, how does doing 8 mod 7 help me at all?
I invite you to locate where I posted an example in base 16.
> Say I have 7 children and I get a number 0-9. If the result is 8, how does doing 8 mod 7 help me at all?
Use both digital watch digits that tally seconds, as in my example.
Let's see how this turns out:
n n * 7 / 10
--------------
0 0
1 0
2 1
3 2
4 2
5 3
6 4
7 4
8 5
9 6
You haven't thought your reply through:
n n % 4
----------
0 0
1 1
2 2
3 3
4 0
5 1
6 2
7 3
8 0
9 1
10 2
11 3
12 0
13 1
14 2
15 3
That doesn't produce the result you think it does. Think a bit harder. If the last digit is 20, and there are four children, the result is 4 * 20 / 10 = 8. There is no eighth child.
With a single generation, you can't uniformly choose from a set of n options with a random number generator that outputs m options, unless n divides m.
Digits, not digit. I doubt this fact will limit the number of airheads who downvote posts containing useful content.
> If the last digit is 20, and there are four children, the result is 4 * 20 / 10 = 8.
Singular "digit."
Look -- I posted the obvious solution to a common problem. Everything else depends on those who can't stand the unwelcome intrusion of simple, easily stated facts.
My "attitude" is that this problem is easily solved, using simple arithmetic. Imagine you're a scientist -- as such, do you object to a useful result because of its source?
You posted a solution that was less correct than the solution you were responding to.
The solution I originally posted is fair and practical. Divide the digits as evenly as you can between the kids, and treat any extras as a do-over. While it's technically possible to never end, in practical terms it produces a fair result within ten seconds. (The fact that you're trying to "fix" this solution confuses me; I wonder if perhaps you didn't understand it in the first place and have been arguing based on a misunderstanding ever since.) By contrast, your solution does not produce a fair result for certain numbers of kids. I promise, the kids in my family would have discovered that bias by the time there were 7 of us.
> "can't stand the unwelcome intrusion of simple, easily stated facts"
One of the reasons you've gotten a lot of downvotes here is because of the combination of:
- posting an incorrect solution
- insisting the incorrect solution is correct, in spite of several people showing you why it is not, and
- complaining that people who are downvoting are the ones in the wrong, including several insults (calling people airheads, innumerate, brainless cyberwarriors, saying they can't stand simple facts, etc.)
At times I really enjoy your comments. I've sent a lot of upvotes your way over the years. But in this case you're wrong, and you've taken to insulting the people who are patiently trying to explain to you why you're wrong. I know you're capable of better. Please take the time to reread and understand the original solution, and stop insulting people.
When you get a downvote, ignore it. It's probably accidental or meaningless and these tend to self correct over a day.
When people downvote a bunch of your posts in a thread IGNORE THE DOWNVOTES. Vindictive downvote sprees are usually corrected over the course of the day. Mentioning the downvotes will usually prevent those corrective upvotes. Me tioning the downvotes in the unpleasant way that you do will attract downvotes.
You may wish to consider how you're presenting the information. If the first table of numbers gets downvotes posting the same table again without more information is going to get the same downvotes.
You could argue that it should not be this way, but it is.
Indeed it is. State facts, back up what you say with evidence, get downvoted. As certain as sunrise.
> If the first table of numbers gets downvotes posting the same table again without more information is going to get the same downvotes.
The alternative is to adopt the standards of religion instead of science. In religion, if you start losing followers, you change the mythology. In science, evidence is evidence, and how people feel about it has no standing.
> When you get a downvote, ignore it. It's probably accidental or meaningless ...
Easily proven false. My downvotes inevitably accompany anything I post that has evidence and/or links to references. If I offer an uncorroborated opinion or philosophical remark, however irrelevant or baseless, it's treated neutrally. This is how science works -- you observe things dispassionately and don't let yourself to be swayed by what people think is true.
Do you disagree with any of the following statements, and if yes, where and why?
- original stopwatch solutions gives equal probability for any of the kid to get picked
- your modulo solution does not give equal probability for any of the kid to get picked
- you argue that the non-uniformness of your solution is not relevant in practice, because number of kids is likely to be an order of magnitude smaller than the readout from the stopwatch (i.e. last two digits)
Okay. I usually expect people to locate the errors in their own thinking, but in this case, I'll make an exception. Here's one of the suggestions: "multiply the last digit by the number of children and divide by ten". Let's see how this works out:
n n * 7 / 10
----------------
0 0
1 0
2 1
3 2
4 2
5 3
6 4
7 4
8 5
9 6
I'm going to avoid your straw men, with this exception:
> you argue that the non-uniformness of your solution is not relevant in practice
I never said that. I said that the error could be minimized. But consider my test of the the alternative listed above. The error inherent with a relatively small number of children and a relatively large original number, say, 0 - 59, is a smaller error than the proposed alternative.
Hey, I asked you three simple questions with pretty much boolean answers, in order to try and clarify where exactly you end up disagreeing with everyone. Please be charitable.
> Here's one of the suggestions: "multiply the last digit by the number of children and divide by ten".
Hey, that one was clearly meant as a joke, and is not the suggestion I was referring to. If something is a strawman here, this is. The one I asked about is the "My parents used the last digit on a stopwatch to decide which of the kids got to pick the radio station in the car and similarly trivial decisions. (If 0-9 couldn't be divided evenly among the kids present, leftover digits would result in a re-roll.)".
In light of that, could you provide the answers?
Anyway, I must say I found the technique I used above quite effective at figuring out continous disagreements. You state some simple true/false statements describing your assumptions and ask the other party to agree/disagree and explain the points of disagreement. Apply recursively if needed. Kind of a discussion equivalent of git bisect ;).