返回题库

HMMT 十一月 2019 · GEN 赛 · 第 7 题

HMMT November 2019 — GEN Round — Problem 7

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. In Middle-Earth, nine cities form a 3 by 3 grid. The top left city is the capital of Gondor and the bottomright city is the capital of Mordor. How many ways can the remaining cities be divided among the twonations such that all cities in a country can be reached from its capital via the grid-lines without passingthrough a city of the other country?
    2 2
解析

英文解析

  1. In Middle-Earth, nine cities form a 3 by 3 grid. The top left city is the capital of Gondor and the bottomright city is the capital of Mordor. How many ways can the remaining cities be divided among the twonations such that all cities in a country can be reached from its capital via the grid-lines without passingthrough a city of the other country?
    Proposed by: Shengtong Zhang
    Answer: 30
    For convenience, we will center the grid on the origin of the coordinate plane and align the outer cornersof the grid with the points ( ± 1 , ± 1), so that ( − 1 , 1) is the capital of Gondor and (1 , − 1) is the capital of
    Mordor.
    We will use casework on which nation the city at (0 , 0) is part of. Assume that is belongs to Gondor.
    Then consider the sequence of cities at (1 , 0) , (1 , 1) , (0 , 1). If one of these belongs to Mordor, then all of theprevious cities belong to Mordor, since Mordor must be connected. So we have 4 choices for which citiesbelong to Mordor. Note that this also makes all the other cities in the sequence connected to Gondor.
    Similarly, we have 4 (independent) choices for the sequence of cities (0 , − 1) , ( − 1 − 1) , ( − 1 , 0). All of thesechoices keep (0 , 0) connected to Gondor except the choice that assigns all cities in both sequences to
    Mordor. Putting this together, the answer is 2(4 · 4 − 1) = 30.
    2 2