返回题库

HMMT 二月 2022 · COMB 赛 · 第 2 题

HMMT February 2022 — COMB Round — Problem 2

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

题目详情

  1. Compute the number of ways to color 3 cells in a 3 × 3 grid so that no two colored cells share an edge.
解析
  1. Compute the number of ways to color 3 cells in a 3 × 3 grid so that no two colored cells share an edge. Proposed by: Akash Das Answer: 22 Solution: If the middle square is colored, then two of the four corner squares must be colored, and 4 there are = 6 ways to do this. If the middle square is not colored, then after coloring one of 2 the 8 other squares, there are always 6 ways to place the other two squares. However, the number of possibilities is overcounted by a factor of 3, so there are 16 ways where the middle square is not colored. This leads to a total of 22.