HMMT 十一月 2016 · 冲刺赛 · 第 13 题
HMMT November 2016 — Guts Round — Problem 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
解析
- [ 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 3 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), 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 these vertices 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. 0 • 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 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. Then 1 f ( E ) = f ( F ) = f ( P ) = 1, and f ( D ) equals either 0 or 1. There are 3 · 2 = 6 ways to do this. In total, there are 1 + 3 + 6 = 10 ways for the lowest 1 to be in L . 1 • 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 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 pick this 1 in 3 ways. There are 1 + 3 + 3 = 7 ways. • The lowest 1 is in L . There is 1 way. 3 • There are no 1’s. Then f sends everything to 0. There is 1 way. In total, there are 1 + 10 + 7 + 1 + 1 = 20 total f ’s.