返回题库

HMMT 二月 2010 · COMB 赛 · 第 8 题

HMMT February 2010 — COMB Round — Problem 8

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [ 6 ] How many functions f from {− 1005 , . . . , 1005 } to {− 2010 , . . . , 2010 } are there such that the fol- lowing two conditions are satisfied? • If a < b then f ( a ) < f ( b ). • There is no n in {− 1005 , . . . , 1005 } such that | f ( n ) | = | n | .
解析
  1. [ 6 ] How many functions f from {− 1005 , . . . , 1005 } to {− 2010 , . . . , 2010 } are there such that the fol- lowing two conditions are satisfied? • If a < b then f ( a ) < f ( b ). • There is no n in {− 1005 , . . . , 1005 } such that | f ( n ) | = | n | . ( ) 4019 Answer: · · · Note: the intended answer was , but the original answer was incorrect. The 2011 correct answer is: 1173346782666677300072441773814388000553179587006710786401225043842699552460942166630860 5302966355504513409792805200762540756742811158611534813828022157596601875355477425764387 2333935841666957750009216404095352456877594554817419353494267665830087436353494075828446 0070506487793628698617665091500712606599653369601270652785265395252421526230453391663029 1476263072382369363170971857101590310272130771639046414860423440232291348986940615141526 0247281998288175423628757177754777309519630334406956881890655029018130367627043067425502 2334151384481231298380228052789795136259575164777156839054346649261636296328387580363485 2904329986459861362633348204891967272842242778625137520975558407856496002297523759366027 Combinatorics Subject Test 1506637984075036473724713869804364399766664507880042495122618597629613572449327653716600 6715747717529280910646607622693561789482959920478796128008380531607300324374576791477561 5881495035032334387221203759898494171708240222856256961757026746724252966598328065735933 6668742613422094179386207330487537984173936781232801614775355365060827617078032786368164 8860839124954588222610166915992867657815394480973063139752195206598739798365623873142903 28539769699667459275254643229234106717245366005816917271187760792 This obviously cannot be computed by hand, but there is a polynomial-time dynamic programming algorithm that will compute it.