Metamath Proof Explorer < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >  birthday Unicode version

Theorem birthday 20732
 Description: The Birthday Problem. There is a more than even chance that out of 23 people in a room, at least two of them have the same birthday. Mathematically, this is asserting that for and , fewer than half of the set of all functions from to are injective. (Contributed by Mario Carneiro, 17-Apr-2015.)
Hypotheses
Ref Expression
birthday.s
birthday.t
birthday.k ;
birthday.n ;;
Assertion
Ref Expression
birthday
Distinct variable groups:   ,   ,
Allowed substitution hints:   ()   ()

Proof of Theorem birthday
StepHypRef Expression
1 birthday.k . . . 4 ;
2 2nn0 10184 . . . . 5
3 3nn0 10185 . . . . 5
42, 3deccl 10342 . . . 4 ;
51, 4eqeltri 2471 . . 3
6 birthday.n . . . 4 ;;
7 6nn0 10188 . . . . . 6
83, 7deccl 10342 . . . . 5 ;
9 5nn 10082 . . . . 5
108, 9decnncl 10341 . . . 4 ;;
116, 10eqeltri 2471 . . 3
12 birthday.s . . . 4
13 birthday.t . . . 4
1412, 13birthdaylem3 20731 . . 3
155, 11, 14mp2an 654 . 2
16 log2ub 20728 . . . . . 6 ;; ;;
175nn0cni 10179 . . . . . . . . . . . 12
1817sqvali 11402 . . . . . . . . . . 11
1917mulid1i 9039 . . . . . . . . . . . 12
2019eqcomi 2405 . . . . . . . . . . 11
2118, 20oveq12i 6046 . . . . . . . . . 10
22 ax-1cn 8995 . . . . . . . . . . 11
2317, 17, 22subdii 9428 . . . . . . . . . 10
2421, 23eqtr4i 2424 . . . . . . . . 9
2524oveq1i 6044 . . . . . . . 8
2617, 22subcli 9322 . . . . . . . . . 10
27 2cn 10016 . . . . . . . . . 10
28 2ne0 10029 . . . . . . . . . 10
2917, 26, 27, 28divassi 9716 . . . . . . . . 9
30 1nn0 10183 . . . . . . . . . 10
31 2p1e3 10049 . . . . . . . . . . . . . . . 16
32 eqid 2401 . . . . . . . . . . . . . . . 16 ; ;
332, 2, 31, 32decsuc 10351 . . . . . . . . . . . . . . 15 ; ;
341, 33eqtr4i 2424 . . . . . . . . . . . . . 14 ;
3534oveq1i 6044 . . . . . . . . . . . . 13 ;
362, 2deccl 10342 . . . . . . . . . . . . . . 15 ;
3736nn0cni 10179 . . . . . . . . . . . . . 14 ;
38 pncan 9257 . . . . . . . . . . . . . 14 ; ; ;
3937, 22, 38mp2an 654 . . . . . . . . . . . . 13 ; ;
4035, 39eqtri 2421 . . . . . . . . . . . 12 ;
4140oveq1i 6044 . . . . . . . . . . 11 ;
42 eqid 2401 . . . . . . . . . . . . 13 ; ;
43 0nn0 10182 . . . . . . . . . . . . 13
4427mulid1i 9039 . . . . . . . . . . . . . . 15
4544oveq1i 6044 . . . . . . . . . . . . . 14
4627addid1i 9199 . . . . . . . . . . . . . 14
4745, 46eqtri 2421 . . . . . . . . . . . . 13
482dec0h 10344 . . . . . . . . . . . . . 14 ;
4944, 48eqtri 2421 . . . . . . . . . . . . 13 ;
502, 30, 30, 42, 2, 43, 47, 49decmul2c 10376 . . . . . . . . . . . 12 ; ;
5130, 30deccl 10342 . . . . . . . . . . . . . 14 ;
5251nn0cni 10179 . . . . . . . . . . . . 13 ;
5337, 27, 52, 28divmuli 9714 . . . . . . . . . . . 12 ; ; ; ;
5450, 53mpbir 201 . . . . . . . . . . 11 ; ;
5541, 54eqtri 2421 . . . . . . . . . 10 ;
5619, 1eqtri 2421 . . . . . . . . . . 11 ;
57 3p2e5 10057 . . . . . . . . . . 11
582, 3, 2, 56, 57decaddi 10372 . . . . . . . . . 10 ;
595, 30, 30, 55, 3, 2, 58, 56decmul2c 10376 . . . . . . . . 9 ;;
6029, 59eqtri 2421 . . . . . . . 8 ;;
6125, 60eqtri 2421 . . . . . . 7 ;;
6261, 6oveq12i 6046 . . . . . 6 ;; ;;
6316, 62breqtrri 4192 . . . . 5
64 2rp 10563 . . . . . . 7
65 relogcl 20412 . . . . . . 7
6664, 65ax-mp 8 . . . . . 6
67 5nn0 10187 . . . . . . . . . . 11
682, 67deccl 10342 . . . . . . . . . 10 ;
6968, 3deccl 10342 . . . . . . . . 9 ;;
7061, 69eqeltri 2471 . . . . . . . 8
7170nn0rei 10178 . . . . . . 7
72 nndivre 9981 . . . . . . 7
7371, 11, 72mp2an 654 . . . . . 6
7466, 73ltnegi 9517 . . . . 5
7563, 74mpbi 200 . . . 4
7673renegcli 9308 . . . . 5
7766renegcli 9308 . . . . 5
78 eflt 12659 . . . . 5
7976, 77, 78mp2an 654 . . . 4
8075, 79mpbi 200 . . 3
8166recni 9049 . . . . 5
82 efneg 12640 . . . . 5
8381, 82ax-mp 8 . . . 4
84 reeflog 20414 . . . . . 6
8564, 84ax-mp 8 . . . . 5
8685oveq2i 6045 . . . 4
8783, 86eqtri 2421 . . 3
8880, 87breqtri 4190 . 2
8912, 13birthdaylem1 20729 . . . . . . . 8
9089simp2i 967 . . . . . . 7
9189simp1i 966 . . . . . . 7
92 ssfi 7279 . . . . . . 7
9390, 91, 92mp2an 654 . . . . . 6
94 hashcl 11580 . . . . . 6
9593, 94ax-mp 8 . . . . 5
9695nn0rei 10178 . . . 4
9789simp3i 968 . . . . . 6
9811, 97ax-mp 8 . . . . 5
99 hashnncl 11586 . . . . . 6
10090, 99ax-mp 8 . . . . 5
10198, 100mpbir 201 . . . 4
102 nndivre 9981 . . . 4
10396, 101, 102mp2an 654 . . 3
104 reefcl 12630 . . . 4
10576, 104ax-mp 8 . . 3
106 1re 9037 . . . 4
107106rehalfcli 10162 . . 3
108103, 105, 107lelttri 9146 . 2
10915, 88, 108mp2an 654 1
 Colors of variables: wff set class Syntax hints:   wi 4   wb 177   wceq 1649   wcel 1721  cab 2387   wne 2564   wss 3277  c0 3585   class class class wbr 4167  wf 5404  wf1 5405  cfv 5408  (class class class)co 6034  cfn 7059  cc 8935  cr 8936  cc0 8937  c1 8938   caddc 8940   cmul 8942   clt 9067   cle 9068   cmin 9237  cneg 9238   cdiv 9623  cn 9946  c2 9995  c3 9996  c5 9998  c6 9999  cn0 10167  ;cdc 10328  crp 10558  cfz 10989  cexp 11323  chash 11559  ce 12605  clog 20391 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1662  ax-8 1683  ax-13 1723  ax-14 1725  ax-6 1740  ax-7 1745  ax-11 1757  ax-12 1946  ax-ext 2382  ax-rep 4275  ax-sep 4285  ax-nul 4293  ax-pow 4332  ax-pr 4358  ax-un 4655  ax-inf2 7543  ax-cnex 8993  ax-resscn 8994  ax-1cn 8995  ax-icn 8996  ax-addcl 8997  ax-addrcl 8998  ax-mulcl 8999  ax-mulrcl 9000  ax-mulcom 9001  ax-addass 9002  ax-mulass 9003  ax-distr 9004  ax-i2m1 9005  ax-1ne0 9006  ax-1rid 9007  ax-rnegex 9008  ax-rrecex 9009  ax-cnre 9010  ax-pre-lttri 9011  ax-pre-lttrn 9012  ax-pre-ltadd 9013  ax-pre-mulgt0 9014  ax-pre-sup 9015  ax-addf 9016  ax-mulf 9017 This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2256  df-mo 2257  df-clab 2388  df-cleq 2394  df-clel 2397  df-nfc 2526  df-ne 2566  df-nel 2567  df-ral 2668  df-rex 2669  df-reu 2670  df-rmo 2671  df-rab 2672  df-v 2915  df-sbc 3119  df-csb 3209  df-dif 3280  df-un 3282  df-in 3284  df-ss 3291  df-pss 3293  df-nul 3586  df-if 3697  df-pw 3758  df-sn 3777  df-pr 3778  df-tp 3779  df-op 3780  df-uni 3972  df-int 4007  df-iun 4051  df-iin 4052  df-br 4168  df-opab 4222  df-mpt 4223  df-tr 4258  df-eprel 4449  df-id 4453  df-po 4458  df-so 4459  df-fr 4496  df-se 4497  df-we 4498  df-ord 4539  df-on 4540  df-lim 4541  df-suc 4542  df-om 4800  df-xp 4838  df-rel 4839  df-cnv 4840  df-co 4841  df-dm 4842  df-rn 4843  df-res 4844  df-ima 4845  df-iota 5372  df-fun 5410  df-fn 5411  df-f 5412  df-f1 5413  df-fo 5414  df-f1o 5415  df-fv 5416  df-isom 5417  df-ov 6037  df-oprab 6038  df-mpt2 6039  df-of 6258  df-1st 6302  df-2nd 6303  df-riota 6499  df-recs 6583  df-rdg 6618  df-1o 6674  df-2o 6675  df-oadd 6678  df-er 6855  df-map 6970  df-pm 6971  df-ixp 7014  df-en 7060  df-dom 7061  df-sdom 7062  df-fin 7063  df-fi 7365  df-sup 7395  df-oi 7426  df-card 7773  df-cda 7995  df-pnf 9069  df-mnf 9070  df-xr 9071  df-ltxr 9072  df-le 9073  df-sub 9239  df-neg 9240  df-div 9624  df-nn 9947  df-2 10004  df-3 10005  df-4 10006  df-5 10007  df-6 10008  df-7 10009  df-8 10010  df-9 10011  df-10 10012  df-n0 10168  df-z 10229  df-dec 10329  df-uz 10435  df-q 10521  df-rp 10559  df-xneg 10656  df-xadd 10657  df-xmul 10658  df-ioo 10866  df-ioc 10867  df-ico 10868  df-icc 10869  df-fz 10990  df-fzo 11080  df-fl 11143  df-mod 11192  df-seq 11265  df-exp 11324  df-fac 11508  df-bc 11535  df-hash 11560  df-shft 11823  df-cj 11845  df-re 11846  df-im 11847  df-sqr 11981  df-abs 11982  df-limsup 12206  df-clim 12223  df-rlim 12224  df-sum 12421  df-ef 12611  df-sin 12613  df-cos 12614  df-tan 12615  df-pi 12616  df-dvds 12794  df-struct 13412  df-ndx 13413  df-slot 13414  df-base 13415  df-sets 13416  df-ress 13417  df-plusg 13483  df-mulr 13484  df-starv 13485  df-sca 13486  df-vsca 13487  df-tset 13489  df-ple 13490  df-ds 13492  df-unif 13493  df-hom 13494  df-cco 13495  df-rest 13591  df-topn 13592  df-topgen 13608  df-pt 13609  df-prds 13612  df-xrs 13667  df-0g 13668  df-gsum 13669  df-qtop 13674  df-imas 13675  df-xps 13677  df-mre 13752  df-mrc 13753  df-acs 13755  df-mnd 14631  df-submnd 14680  df-mulg 14756  df-cntz 15057  df-cmn 15355  df-psmet 16635  df-xmet 16636  df-met 16637  df-bl 16638  df-mopn 16639  df-fbas 16640  df-fg 16641  df-cnfld 16645  df-top 16904  df-bases 16906  df-topon 16907  df-topsp 16908  df-cld 17024  df-ntr 17025  df-cls 17026  df-nei 17103  df-lp 17141  df-perf 17142  df-cn 17231  df-cnp 17232  df-haus 17319  df-cmp 17390  df-tx 17533  df-hmeo 17726  df-fil 17817  df-fm 17909  df-flim 17910  df-flf 17911  df-xms 18289  df-ms 18290  df-tms 18291  df-cncf 18847  df-limc 19692  df-dv 19693  df-ulm 20232  df-log 20393  df-atan 20646
 Copyright terms: Public domain W3C validator