MathDB

Labeling edges of a cube

Source: Problem 3, Polish NO 1989

October 1, 2005

geometry3D geometrycombinatorics unsolvedcombinatorics

Problem Statement

The edges of a cube are labeled from

1

12

. Show that there must exist at least eight triples

(i, j, k)

with

1 \leq i < j < k \leq 12

so that the edges

i, j, k

are consecutive edges of a path. Also show that there exists labeling in which we cannot find nine such triples.