MathDB

Digraph with infinitely many vertices

Source: Bulgarian IMO TST 2008, Day 2, Problem 3

July 8, 2013

floor functionceiling functioninductionalgebrapolynomialcombinatorics proposedcombinatorics

Problem Statement

Let

G

be a directed graph with infinitely many vertices. It is known that for each vertex the outdegree is greater than the indegree. Let

O

be a fixed vertex of

G

. For an arbitrary positive number

n

, let

V_{n}

be the number of vertices which can be reached from

O

passing through at most

n

edges (

O

counts). Find the smallest possible value of

V_{n}