12 votos

Si cada chico conoce a r chicas y cada chica conoce a r chicos, entonces el número de chicos=chicas

Otra pregunta más de los nacionales de BdMO 2013:

En una clase, todos los chicos saben $r$ número de chicas y cada chica sabe $r$ Demuestre que hay el mismo número de chicos y de chicas [Asuma que la amistad es simétrica, es decir, si A conoce a B entonces B conoce a A].

Esta pregunta se planteó en la sección de Secundaria de los Nacionales.En la sección Junior,se planteó una pregunta similar pero más fácil.

En una clase, todos los chicos saben $3$ número de chicas y cada chica sabe $3$ Si hay 13 chicos, encuentra el número de chicas en la clase.

He resuelto esta pregunta observando que (i) Si hay 3 niños en la clase, el número de niñas también tiene que ser 3. (ii) Si hay 4 chicos, el número de chicas también es 4. Esto nos da la herramienta necesaria para resolver el problema.

$13$ chicos= $(3+3+3)+4$ chicos

Por cada 3 chicos, necesitamos 3 chicas[De (i)]. Por lo tanto,(3+3+3) chicos implica que hay $3+3+3=9$ De (ii), sabemos que si hay 4 niños, necesitamos 4 niñas en la clase.

Resumiendo, $(3+3+3)+4$ los chicos necesitan $(3+3+3)+4$ chicas, es decir, 13 chicas.

Sin embargo, no veo cómo voy a generalizar este problema. No importa, aquí está mi trabajo.

MI INTENTO: Una vez más, utilizamos los siguientes hechos:

(i) Si hay 3 niños en la clase, el número de niñas también debe ser 3. (ii)Si hay 4 chicos, el número de chicas necesario es también 4.

Así que si podemos reescribir $r$ en la forma $3k+4z$ hemos terminado.

Lema: Cada número entero $r\ge 3$ excepto el 5 que puede escribirse en la forma $3k+4z$ [k y z son enteros positivos, no ambos $0$ ]

PRUEBA: Un número mayor o igual a 3 es de la forma $3p$ , $3p+1$ , $3p+2$ para algún número entero positivo p.Tratamos los casos individualmente[debemos notar que 5 no puede ser expresado como una suma de múltiplos de 3 y 4.Para esto,consideramos $p\ge 2$ . Por lo tanto, consideramos los casos r=3,4,5 por separado y vemos que el número de chicos y chicas es efectivamente igual].

$3p$ : Si r=3p para algún número entero positivo p,entonces al conectar k=p y z=0 obtenemos

3p=3(p)+4(0)

y hemos terminado.

$3p+1$ : Conectando k=p-1 y z=1, obtenemos

3(p-1)+4=3p+1

$3p+2$ : Conectando k=p-2 y z=2, obtenemos

3(p-2)+4(2)=3p+2

y la prueba está completa.

Dado que r siempre puede escribirse en la forma $3k+4z$ ,

(1)El número de niñas necesarias para 3k niños es 3k[De (i)].

(2)El número de chicas necesario para 4z números de chicos es 4z[De (ii)].

Por lo tanto, el número total de chicas=3k+4z=r y ya está, ¿estoy en lo cierto?

22voto

Oli Puntos 89

Dejemos que $b$ sea el número de niños, y $g$ el número de chicas.

Para cualquier niño $B$ y la chica $G$ que se conocen, escriban en un papelito " $B$ y $G$ se conocen". Contamos el número de papelitos de dos maneras diferentes.

Como todo niño sabe $r$ chicas, hay $br$ trozos de papel.

Como todas las chicas saben $r$ chicos, hay $gr$ trozos de papel.

Así, $br=gr$ y por lo tanto $b=g$ (si $r\ne 0$ ).

Observación: Para una versión más romántica, supongamos que cada pareja de chicos y chicas que se conocen se besan (una vez). En lugar de contar papelitos, cuente los besos.

4voto

Tim Ratigan Puntos 5455

Obsérvese que las relaciones entre géneros forman un gráfico bipartito $G$ con subgrafos $A$ (los vértices son chicas) y $B$ (los vértices son chicos). El gráfico es regular, es decir, todos los vértices tienen el mismo grado $r:=\deg{v}$ . Sin embargo, también observamos que para cada arista incidente en un vértice de $B$ el otro extremo de la arista incide en $A$ ya que $G$ es bipartita. De ello se deduce que $\deg B=\deg A\Longrightarrow r|B|=r|A|\Longrightarrow |B|=|A|$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X