brain buster

27 posts / 0 new
Last post
Nyarlathotep's picture
brain buster

Imagine a world where cars have a 2 digit serial number. You want to play a game where you check all the cars in a parking lot to see if there is at least one pair that have the same serial number.

Assumptions:

  1. There are 100 possible serial numbers (00, 01, 02, ...,97, 98, 99).
  2. All serial number are equally likely (car factories doesn't favor certain serial numbers).
  3. The serial numbers are independent (these are just random cars).

---------------------------------------
Q: What is the minimum number of cars needed for there to be a 50% (or greater) chance that there is at least 1 duplicated serial number?

Subscription Note: 

Choosing to subscribe to this topic will automatically register you for email notifications for comments and updates on this thread.

Email notifications will be sent out daily by default unless specified otherwise on your account which you can edit by going to your userpage here and clicking on the subscriptions tab.

Whitefire13's picture
Oh god Nyar...haven’t had my

Oh god Nyar...haven’t had my coffee (well, one cup) so taking a quick stab before I look it up.

Here’s public embarrassment coming....

10,000?

Edited to add: go through box containing stuff I taught the oldest kid...we both “forget” once he passes

Nyarlathotep's picture
Well if there are 101 cars,

Well if there are 101 cars, the chance of having a duplicate serial number is 100% (since there is only 100 serial numbers).

If there was 1 car, the chance of having a duplicate serial number is 0%.
--------------------------------
So the number of cars that lead to a 50% of a duplicate must lie between 1 and 101.

Whitefire13's picture
Lol!!! I like my parking lot

Lol!!! I like my parking lot better! I’m a dumbass :)
...at first I was on the right track, then I out-thought myself...

Calilasseia's picture
Here's my reasoning.

Here's my reasoning.

Step 1: The probability of a given serial number appearing in a set of n cars (n<100) is given by n/100.

Step 2: Likewise, the probability of a given serial number appearing in a set of (n+1) cars is given by (n+1)/ 100.

Step 3: The probability of two cars having the same serial number is therefore n(n+1)/10000.

Step 4: To solve for n, given a probability value of 0.5, we have:

n(n+1)/10000 = 0.5

Rearranging this, we end up with a quadratic equation:

n² + n - 5000 = 0.

Solving this quadratic equation yields two solutions, of the form:

n = [-1 ± √(1 + 20000)]/2

Since the solution must by definition be positive, we select as our solution:

(√20001 - 1)/2

which gives us 70.212.

Therefore we need 71 cars to guarantee a repeated serial number with 50% probability.

Nyarlathotep's picture
Calilasseia - Step 3: The

Calilasseia - Step 3: The probability of two cars having the same serial number is therefore n(n+1)/10000.

I think this part has a mistake. The probability that two selected cars share the same number should be 1/100, and should not depend of the number of cars present, imo.

algebe's picture
98

98

CyberLN's picture
51?

51?

Edited to add: sigh, I’m just not smart enough for this....

Grinseed's picture
Busted brains all over my

Busted brains all over my keyboard ....harumph!

dogalmighty's picture
n2 = -71.2

n2 = -71.2

:P

Cognostic's picture
@Calilasseia: Thanks for

@Calilasseia: Thanks for the invite but I think I've got something to do this Friday night. I hope you Tin, Sheldon, White, and Old man have a great time playing poker. Perhaps I can make it next time.

Whitefire13's picture
*****my head hurts FROM all

*****my head hurts FROM all the glass ceilings I’m busting through******

POKER!!!! I love poker! Uh...just a sec

Edited to add: why did I think I could answer Nyar, (evidence) ego - baby - ego!

All guys. Uh - did I misread - is it POKER or POKE-HER

Just for clarity...

Attachments

Attach Image/Video?: 

Yes
Whitefire13's picture
So I got to thinking of a

So I got to thinking of a story about “women and glass ceilings”
(there are a lot of reasons women chose or do not chose to dedicate their lives to a career) and this little story will contain a funny “punchline” (however please keep in mind that men hired me, trained me, befriended me, respected me, answered to me, etc) ...also not all details will be contained in the story for privacy’s sake.

Big presentation day for me. I’m sitting to the left of our CEO, my boss to his right. We’re at a fancy hotel and about to have lunch before presentation of a Project I worked on (inter-provincial, 300 “under” me, one year work before implementation). This roll out is for our Branch Managers first, and lunch is a way to get everyone relaxed, fed, “shooting the shit” beforehand.

Our lunch- table is set in a private room, and like I said, us 3, and as Branch Managers enter, they come over, shake hands, say “hi” and take a
seat at the same table (the smarter ones come early, so they can sit across from “us” - you get the idea).

So near the end of everyone entering and greeting and sitting ...in walks one of the last Branch Managers. Walks strait up to CEO. Big smile (looks a little sweaty on the brow) and shakes his hand aggressively. As he’s smiling, and shaking hand he says to CEO “...so is this pretty lady your wife?”

Lol! Said CEO replied like a champ while I held back a giggle.

BTW...financial “conspiracy” (seriously) We
had a lawyer in our building, office bigger than CEO and he was our financial institutions lawyer. I was never allowed to “use” him - I outsourced all my work. When I asked why I couldn’t use him (our organization paid him) I was just told “I couldn’t”. And when I asked “what he did?” I was told “good question” (no further info). That’s when I first arrived. After that, through “looks” it was clear to not ask about said lawyer and his job.

Bonzo's picture
I do not think there are

I do not think there are duplicate serial numbers in cars or in and for any kind of product, except there's a mistake.

Nyarlathotep's picture
Bonzo - I do not think there

Bonzo - I do not think there are duplicate serial numbers in cars or in and for any kind of product, except there's a mistake.

Nyarlathotep - Imagine a world where cars have a 2 digit serial number.

Grinseed's picture
first thanks for providing a

first thanks for providing a brain buster to distract us from current problems Nyar. Very nice.
Now lets see, 100 cars and 100 plates 00 to 99. so far so good...
101 cars = 100% for just one set of matching plates with two digits
1 car = 0% therefore
2 cars = 1% hence
3 cars = 2% mmmm...looks like a cagey trap, but...
51 cars = 50%....nahh, this is too easy...Nyar wouldn't put up anything so simple
besides in this selection there might be 51 cars with plates 00 to 50, possible but not probable?
lets take a different tack...with 100 cars, two digits each, ten sets of plates each of value 10, 0* through to 9* (*=wildcard)
soooo to get a 100% chance of number plates with 0* to 9* you'd need only 11 plates to get one match...sounds...I dont know... ok?...jeez Nyar...
uummmm...so with 11 plates with we all the values of ten covered for at least a single match..
how many plates would we need to cover all the single digit value plates on top have the eleven we have already?...should have paid more attention to Prof. Southern in high school...
the eleven we have already would need another 11 plates to get all the single digits values?...sounds like Greek lounge chair logic...but that makes 22 cars....but but but....I don't know...I think Nyar might be a closet sadist....
Ok before I bust my brain again I refer my high school maths experience and say 22 cars because it sounds wrong to me and therefore is more likely to be right...
added later after left over brain busting...make it 44

Nyarlathotep's picture
Well I kind of screwed up.

Well I kind of screwed up. This problem is MUCH harder than I originally thought; and was a poor choice to post here. That being said I think I have the solution, but I had to use some tricks that a majority of posters likely won't know; so this problem seems kind of underhanded.

If anyone is still interested and wants a hint:
-----------------------------------
The probability of getting one or more duplicates (let's call that D), and the probability of not getting any duplicates (let's call that S); have the following relationship:

D + S = 1 (or 100%).

Rearranged that is D = 1 - S. If we knew 1 - S, we would know D. I think 1 - S is "easier" to work with.
-----------------------------------
Working with S:
The probability the first car is a NOT a duplicate is 100/100 = 1; or 100%, since there is no other cars yet.

The probability the 2nd car does NOT match the first is 99/100.

The probability the 3rd car does NOT match either of the first two, is 98/100. We know this because we know the 2 previous cars don't have the same serial number because we are calculating the probability of there being 0 duplicates (S).

The probability the nth car does not match any of the previous cars is (100 - n + 1)/100.

Leading to: S = 100/100 * 99/100 * 98/100 * ... * (100 - n + 1)/100
-----------------------------------
Now to rewrite that in terms of D instead of S:
D = 1 - 100/100 * 99/100 * 98/100 * ... * (100 - n + 1)/100

Cognostic's picture
RE: Brain buster-

RE: Brain buster-

Attachments

Attach Image/Video?: 

Yes
Whitefire13's picture
It’s the whole “chance” thing

It’s the whole “chance” thing. Fuckin’ stupid chance... but I know what you mean. For certainty, yes, 101 cars. And we can estimate a chance at a certain amount...

I still like my parking lot (Cali used my 10,000 so I may not be as dumb as I sometimes think, I just stop thinking things through)

CARS for EVERYONE!!!!!

Nyarlathotep's picture
I'm pretty sure the answer is

I'm pretty sure the answer is 13; which is kind of a blow to my common sense.

I think the point is it is better to think about the number of different pairs of cars we having, instead of the number of actual cars. 13 cars gives us 78 pairs of cars. And that is enough to give about a 50% chance of having at least one duplicate serial number.
-------------------------------
As far as actually calculating it:

Nyarlathotep: D = 1 - 100/100 * 99/100 * 98/100 * ... * (100 - n + 1)/100

That can be rewritten as D = 1 - 100!/[(100 - n)! * 100^n]

That is still a nightmare to work with, however that can be approximated "easily" by a computer: and from the table it seems that 12 is almost enough (more than 49% but not quite 50%). So I think the answer is 13.

Sheldon's picture
Nyarlathotep "I think the

Nyarlathotep "I think the answer is 13."

That's unlucky....

Cognostic's picture
*Waaaaaaaa!!* They are

*Waaaaaaaa!!* They are talking over my head. Make the bad men stop!

Dworkin's picture
Folks,

Folks,

I've never been any good at math. Still trying to work out the square root of -1. (sad smiley here).

D.

algebe's picture
With puzzles like this, the

With puzzles like this, the best response is to pluck a number out of the air and state it with an air of confidence and certainty. There's a 1% probability that you're right, and a 99% probability that 90% of those present won't understand the question either and will think you're inspired.

And that's how you start a religion.

David Killens's picture
42

42

algebe's picture
@David Killens: 42

@David Killens: 42

Heretic! Blasphemer!

dogalmighty's picture
-71.2

-71.2

Donating = Loving

Heart Icon

Bringing you atheist articles and building active godless communities takes hundreds of hours and resources each month. If you find any joy or stimulation at Atheist Republic, please consider becoming a Supporting Member with a recurring monthly donation of your choosing, between a cup of tea and a good dinner.

Or make a one-time donation in any amount.