Olimpiada Tuymaada Junior 2017 Problema 3

En un país, cada 2 ciudades están conectadas por una ruta directa de autobús o un vuelo directo. Una $clique$ es un conjunto de ciudades tal que cada 2 ciudades en el conjunto están conectadas por un vuelo directo. Una $cluque$ es un conjunto de ciudades tal que cada 2 ciudades en el conjunto están conectadas por un vuelo directo, y cada 2 ciudades en el conjunto están conectadas al mismo número de ciudades por una ruta de autobús. Una $claque$ es un conjunto de ciudades tal que cada 2 ciudades en el conjunto están conectadas por un vuelo directo, y cada 2 números de rutas de autobús desde una ciudad en el conjunto son diferentes. Demuestre que el número de ciudades de cualquier clique es como máximo el producto del mayor número posible de ciudades en una cluque y el mayor número posible de ciudades en una claque.

23

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados