返回题库

HMMT 十一月 2009 · 冲刺赛 · 第 18 题

HMMT November 2009 — Guts Round — Problem 18

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

题目详情

  1. [ 9 ] Let f be a function that takes in a triple of integers and outputs a real number. Suppose that f satisfies the equations f ( a + 1 , b, c ) + f ( a − 1 , b, c ) f ( a, b, c ) = 2 f ( a, b + 1 , c ) + f ( a, b − 1 , c ) f ( a, b, c ) = 2 f ( a, b, c + 1) + f ( a, b, c − 1) f ( a, b, c ) = 2 for all integers a, b, c . What is the minimum number of triples at which we need to evaluate f in order to know its value everywhere? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nd 2 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 7 NOVEMBER 2009 — GUTS ROUND
解析
  1. [ 9 ] Let f be a function that takes in a triple of integers and outputs a real number. Suppose that f satisfies the equations f ( a + 1 , b, c ) + f ( a − 1 , b, c ) f ( a, b, c ) = 2 f ( a, b + 1 , c ) + f ( a, b − 1 , c ) f ( a, b, c ) = 2 f ( a, b, c + 1) + f ( a, b, c − 1) f ( a, b, c ) = 2 for all integers a, b, c . What is the minimum number of triples at which we need to evaluate f in order to know its value everywhere? Answer: 8 Note that if we have the value of f at the 8 points: (0 , 0 , 0) , (1 , 0 , 0) , (0 , 1 , 0) , (0 , 0 , 1) , (0 , 1 , 1) , (1 , 0 , 1) , (1 , 1 , 0) , (1 , 1 , 1), we can calculate the value for any triple of points because we have that f ( a + 1 , b, c ) − ( a, b, c ) constant for any a , if b and c are fixed (and similarly for the other coordinates). To see why we cannot do this with less points, notice that we need to determine what the value of these 8 points anyways, and there is no ”more efficient” way to determine them all in fewer evaluations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . nd 2 ANNUAL HARVARD-MIT NOVEMBER TOURNAMENT, 7 NOVEMBER 2009 — GUTS ROUND