An Paradox Breithlá

Philip J. Erdelsky

4 Iúil, 2001

Cuir r-phost tuairimí, ceartúcháin agus breiseanna chuig an stiúrthóir gréasáin ag pje@efgh.com .

Is fadhb is fearr leat i gcúrsaí dóchúlacht agus staitisticí tosaigh an Fadhb Breithlá: Cad é an dóchúlacht go bhfuil ar a laghad dhá cheann de N daoine a roghnaíodh go randamach ar an lá breithe céanna? (Mí same agus lá, ach ní gá an bhliain chéanna.)

Tá an dara cuid de na fadhbanna: Cé chomh mór a bheith N ionas go mbeidh an dóchúlacht níos mó ná 50 faoin gcéad? Is é an freagra 23, a bhuaileann daoine is mó mar míréasúnta beag. Ar an ábhar sin, tá an fhadhb a dtugtar go minic an Paradox Breithlá. Molann roinnt sharpies gealltóireachta, ar fiú airgead, go bhfuil breithlaethanta dhúbailt i measc aon ghrúpa de 23 nó níos mó daoine. Is dócha, tá roinnt suckers droch-eolas a bheidh ag glacadh leis an geall.

Is é an fhadhb simplithe de ghnáth ag glacadh dhá rud:

  1. Rugadh aon duine ar an 29 Feabhra.
  2. Daon breithlaethanta a dháileadh go cothrom ar fuaid an 365 lá eile den bhliain.

Ceann de na rudaí chéad a faoi deara faoin bhfadhb seo ná go bhfuil sé i bhfad níos éasca chun an fhadhb a réiteach comhlántach: Cad é an dóchúlacht go bhfuil N daoine a roghnaíodh go randamach gach breithlaethanta éagsúla? Is féidir linn a scríobh seo mar fheidhm athchúrsach:

different_birthdays dúbailte (int n) 

  tuairisceán n == 1? 1.0: different_birthdays (n-1) * (365.0- (n-1)) / 365.0; 
}

Gan amhras, d'N = 1 is é an dóchúlacht 1. N> 1, is é an dóchúlacht an táirge de dhá dóchúlachta:

  1. Go bhfuil na chéad daoine N-1 breithlaethanta go léir éagsúla.
  2. Go bhfuil an duine N-ú lá breithe difriúil ó aon cheann de na chéad N-1.

Téann clár a chur ar taispeáint na dóchúlachtaí rud éigin mar seo:

neamhní príomh (neamhní) 

  int n; 
  do (n = 1; n <= 365; n ++) 
    printf ( "% 3d:% e \ n", n, 1.0-different_birthdays (n)); 
}

Is é an toradh rud éigin mar seo:

 1: 0.000000e 00 + 
  2: 03 2.739726e- 
  3: 03 8.204166e- 
  4: 02 1.635591e- 
  5: 2.713557e-02 
      *** 
 20: 01-4.114384e 
 21: 4.436883e-01 
 22: 4.756953e- 01 
 23: 01 5.072972e- 
 24: 5.383443e-01 
 25: 5.686997e-01 
      ***

An dóchúlacht go bhfuil ar a laghad dhá cheann de na daoine N ardaíonn breithlá céanna thuas 0.5 nuair N = 23.

ACH CAD FAOI LEAP BLIAIN?

Is féidir leis an fhadhb a bunaidh a réiteach le riail sleamhnán, a bhfuil díreach cad a rinne mé nuair a chuala mé an chéad go leor é, blianta fada ó shin.

Má chur linn 29 Feabhra go dtí an meascán, faigheann sé i bhfad níos casta. Sa chás seo, a dhéanamh linn ar roinnt toimhdí breise:

  1. líon céanna daoine a bheirtear ar laethanta eile ná 29 Feabhra.
  2. Tá líon na ndaoine a rugadh ar an 29 Feabhra ceathrú de líon na ndaoine a rugadh ar aon lá eile.

Mar sin tá an dóchúlacht gur rugadh duine a roghnaíodh go randamach ar an 29 Feabhra 0.25 / 365.25, agus is é an dóchúlacht gur rugadh duine roghnaíodh go fánach ar an lá sonraithe eile 1 / 365.25.

Is é an dóchúlacht go bhfuil N daoine, b'fhéidir, lena n-áirítear ceann a rugadh ar an 29 Feabhra, breithlaethanta leith suim dhá dóchúlachta:

  1. Go rugadh na daoine N ar N laethanta éagsúla seachas 29 Feabhra.
  2. Go rugadh na daoine N ar N laethanta éagsúla, agus ina measc tá duine amháin a rugadh ar an 29 Feabhra.

Na dóchúlachtaí a chur mar go bhfuil an dá chás comheisiatach.

Anois is féidir le gach dóchúlacht a chur in iúl hathchúrsach:

dúbailte different_birthdays_excluding_Feb_29 (int n) 

  tuairisceán n == 1? 365.0 / 365.25: 
    different_birthdays_excluding_Feb_29 (n-1) * (365.0- (n-1)) / 365.25; 

Dúbailte different_birthdays_including_Feb_29 (int n) 

  tuairisceán n == 1? 0.25 / 365.25: 
    different_birthdays_including_Feb_29 (n-1) * (365.0- (n-2)) / 365.25 + 
    different_birthdays_excluding_Feb_29 (n-1) * 0.25 / 365.25; 
}

Téann clár a chur ar taispeáint na dóchúlachtaí rud éigin mar seo:

neamhní príomh (neamhní) 

  int n; 
  do (n = 1; n <= 366; n ++) 
    printf ( "% 3d:% e \ n", n, 1.0-different_birthdays_excluding_Feb_29 (n) - 
      different_birthdays_including_Feb_29 (n)); 
}
Is é an toradh rud éigin mar seo:

  1: 18 -8.348357e- 
  2: 03 2.736445e- 
  3: 03 8.194354e- 
  4: 02 1.633640e- 
  5: 2.710333e-02 
      *** 
 20: 01-4.110536e 
 21: 4.432853e-01 
 22: 4.752764e -01 
 23: 5.068650e-01 
 24: 5.379013e-01 
 25: 5.682487e-01 
      ***

Mar súil leis, is iad na dóchúlachta beagán níos ísle, toisc go bhfuil dóchúlacht níos ísle laethanta breithe meaitseáil nuair nach bhfuil breithlaethanta níos mó is féidir. Ach tá an méid is lú a bhfuil dóchúlacht níos mó ná 0.5 fóill 23.

Ar ndóigh, is féidir le purist matamaiticiúla mhaíomh nach bhfuil blianta leap teacht i gcónaí gach ceithre bliana, mar sin ní mór na ríomhanna breise modhnú. Mar sin féin, bhí an bhliain seo caite quadrennial nach raibh mbliain bhisigh 1900, agus beidh an chéad cheann eile a bheith 2100. Tá líon na ndaoine a chónaíonn anois rugadh i 1900 chomh beag sin ceapaim go bhfuil ár n-comhfhogasú bailí chun gach críche praiticiúla. Ach tá fáilte romhat a dhéanamh na modhnuithe is gá más mian leat.

Tá impleachtaí níos faide ná saol na parlús gealltóireachta An Paradox Breithlá. Is teicníc caighdeánach i stóráil sonraí a shannadh gach mír uimhir a dtugtar cód hash. Is é an rud atá stóráilte ansin i mbosca ar comhréir lena cód hash. Luasanna sé seo suas aisghabháil mar ní mór ach araid amháin a chuardach. Léiríonn an Paradox Breithlá go bhfuil an dóchúlacht go mbeidh beirt nó níos mó míreanna deireadh suas sa bhosca bruscair céanna ard fiú má tá líon na n-ítimí i bhfad níos lú ná líon na n-araidí. Mar sin tá láimhseáil éifeachtach araidí bhfuil dhá cheann nó níos mó nithe is gá i ngach cás.