返回题库

HMMT 二月 2017 · 团队赛 · 第 6 题

HMMT February 2017 — Team Round — Problem 6

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

题目详情

英文原题

  1. [ 40 ] Let r be a positive integer. Show that if a graph G has no cycles of length at most 2 r , then it has
    2016
    at most | V | cycles of length exactly 2016 r , where | V | denotes the number of vertices in the graph
    G .
解析

英文解析

  1. [ 40 ] Let r be a positive integer. Show that if a graph G has no cycles of length at most 2 r , then it has
    2016
    at most | V | cycles of length exactly 2016 r , where | V | denotes the number of vertices in the graph
    G .
    Proposed by: Yang Liu
    The key idea is that there is at most 1 path of length r between any pair of vertices, or else you geta cycle of length ≤ 2 r. Now, start at any vertex ( | V | choices) and walk 2015 times. There’s at most
    2016
    | V | ways to do this by the previous argument. Now you have to go from the end to the start, andthere’s only one way to do this. So we’re done.