HMMT 十一月 2016 · 冲刺赛 · 第 13 题

英文解析

13. [ 9 ] How many functions f : { 0 , 1 } → { 0 , 1 } satisfy the property that, for all ordered triples ( a , a , a )
    1 2 3
    and ( b , b , b ) such that a ≥ b for all i , f ( a , a , a ) ≥ f ( b , b , b )?
    1 2 3 i i 1 2 3 1 2 3
    Proposed by: Eshaan Nichani
    Answer: 20
    Consider the unit cube with vertices { 0 , 1 } . Let O = (0 , 0 , 0), A = (1 , 0 , 0), B = (0 , 1 , 0), C = (0 , 0 , 1),3
    D = (0 , 1 , 1), E = (1 , 0 , 1), F = (1 , 1 , 0), and P = (1 , 1 , 1). We want to find a function f on thesevertices such that f (1 , y, z ) ≥ f (0 , y, z ) (and symmetric representations). For instance, if f ( A ) = 1,
    then f ( E ) = f ( F ) = f ( P ) = 1 as well, and if f ( D ) = 1, then f ( P ) = 1 as well.
    We group the vertices into four levels: L = { O } , L = { A, B, C } , L = { D, E, F } , and L = { P } .
    0 1 2 3
    We do casework on the lowest level of a 1 in a function.
    • If the 1 is in L , then f maps everything to 1, for a total of 1 way.
    • If the 1 is in L , then f ( O ) = 0. If there are 3 1’s in L , then everything but O must be mapped 0
    1 1
    to 1, for 1 way. If there are 2 1’s in L , then f ( L ) = f ( L ) = 1, and there are 3 ways to
    1 2 3
    choose the 2 1’s in L , for a total of 3 ways. If there is one 1, then WLOG f ( A ) = 1. Thenf ( E ) = f ( F ) = f ( P ) = 1, and f ( D ) equals either 0 or 1. There are 3 · 2 = 6 ways to do this. In 1
    total, there are 1 + 3 + 6 = 10 ways for the lowest 1 to be in L .
    • If the lowest 1 is in L , then f ( O ) = f ( L ) = 0. If there are 3 1’s in L , there is one way to make 1
    2 1 2
    f . If there are 2 1’s, then we can pick the 2 1’s in 3 ways. Finally, if there is one 1, then we pickthis 1 in 3 ways. There are 1 + 3 + 3 = 7 ways.
    • The lowest 1 is in L . There is 1 way.
    • There are no 1’s. Then f sends everything to 0. There is 1 way.3
    In total, there are 1 + 10 + 7 + 1 + 1 = 20 total f ’s.