Autor Tema: Contar subconjuntos con cierta condicion

0 Usuarios y 1 Visitante están viendo este tema.

01 Octubre, 2022, 11:18 pm
Leído 147 veces

Nub

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 344
  • País: 00
  • Karma: +0/-0
Hola, tengo estos dos ejercicios que nunca vi y no tengo idea de como resolverlos

1) Contar la cantidad de subconjuntos de \( 4 \) elementos de \( S =\{1,2,...,100\} \) tales que la distancia entre toda pareja de elementos sea de \( 3 \) o más.  Aclaración: dados \( n < m \), la distancia entre \( n \) y \( m \) es \( m − n \).

2) ¿Cuántos subconjuntos de tres elementos de \( \{1, . . . , 100\} \) cumplen que alguno de  sus elementos es el promedio de los dos restantes?

Gracias

02 Octubre, 2022, 12:13 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 52,435
  • País: es
  • Karma: +0/-0
Hola

Hola, tengo estos dos ejercicios que nunca vi y no tengo idea de como resolverlos

1) Contar la cantidad de subconjuntos de \( 4 \) elementos de \( S =\{1,2,...,100\} \) tales que la distancia entre toda pareja de elementos sea de \( 3 \) o más.  Aclaración: dados \( n < m \), la distancia entre \( n \) y \( m \) es \( m − n \).

Si \( \{x_1,x_2,x_3,x_4\} \) es un conjunto en esas condiciones con \( x_1<x_2<x_3<x_4 \) entonces \( \{x_1,x_2-2,x_3-4,x_4-6\} \) es un conjunto de tres cuatro números distintos entre \( 1 \) y \( 94 \). Recíprocamente dados cuatro números distintos \( 1\leq y_1<y_2<y_3<y_4\leq 94  \), entonces \( \{y_1,y_1+2,y_3+4,y_4+6\} \) es un conjunto en las condiciones pedidas.

Por tanto el problema equivale a contar los subconjuntos de \( 4 \) elementos de los números del \( 1 \) al  \( 94 \). Termina...

Citar
2) ¿Cuántos subconjuntos de tres elementos de \( \{1, . . . , 100\} \) cumplen que alguno de  sus elementos es el promedio de los dos restantes?

Basta que notes que en uno de esos conjuntos fijado el menor y el mayor elemento el otro está determinado: es su promedio. Por tanto es el número de subconjunto de dos elementos a distancia par (en otro caso el promedio no es entero).

Entonces es el número de subconjuntos de dos números impares más el número de conjuntos de dos números pares.

¿Puedes terminar?.

Saludos.

CORREGIDO

02 Octubre, 2022, 01:00 am
Respuesta #2

Nub

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 344
  • País: 00
  • Karma: +0/-0
Hola

Hola, tengo estos dos ejercicios que nunca vi y no tengo idea de como resolverlos

1) Contar la cantidad de subconjuntos de \( 4 \) elementos de \( S =\{1,2,...,100\} \) tales que la distancia entre toda pareja de elementos sea de \( 3 \) o más.  Aclaración: dados \( n < m \), la distancia entre \( n \) y \( m \) es \( m − n \).

Si \( \{x_1,x_2,x_3,x_4\} \) es un conjunto en esas condiciones con \( x_1<x_2<x_3<x_4 \) entonces
hasta aca llegue ???
\( \{x_1,x_2-2,x_3-4,x_4-6\} \) es un conjunto de tres números distintos entre \( 1 \) y \( 94 \)
Acá no se porque restas -2,-4 y -6 y tampoco porque es un conjunto de 3 elementos, ahi no hay 4?

02 Octubre, 2022, 09:18 am
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 52,435
  • País: es
  • Karma: +0/-0
Hola

\( \{x_1,x_2-2,x_3-4,x_4-6\} \) es un conjunto de tres números distintos entre \( 1 \) y \( 94 \)
Acá no se porque restas -2,-4 y -6 y tampoco porque es un conjunto de 3 elementos, ahi no hay 4?

Me equivoqué (¿no es obvio?  :D) quise poner cuatro en lugar de tres. De todas formas la idea es comprobar que es lo mismo contar subconjunto de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades cada par que contar subconjutos de \( \{1,2,\ldots,94\} \) de cuatro elementos, sin más.

Lo que te explico es como relacionar unos con otros. Si los elementos distan \( 3 \) o más tienes que:

\( x_2\geq x_1+3 \) y por tanto \( x_2-2\geq x_1+1 \) es decir \( x_2-2>x_1 \)
\( x_3\geq x_2+3 \) y por tanto \( x_3-4\geq x_2-1 \) es decir \( x_3-4>x_2-2 \)
\( x_4\geq x_3+3 \) y por tanto \( x_4-6\geq x_3-3 \) es decir \( x_4-6>x_3-4 \)

Por tanto \( x_1,x_2-2,x_3-4,x_4-6 \) son números distintos. El mayor como máximo vale \( 100-6=94 \).

Esto muestra como conseguir a partir de un subconjunto de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades, un subconjunto de \( \{1,2,\ldots,94\} \) de cuatro elementos (sin más).

Recíprocamente dado un subconjunto de \( \{1,2,\ldots,94\} \) de cuatro elementos (sin más) \( \{y_1,y_2,y_3,y_4\} \), entonces \( \{y_1,y_2+2,y_3+4,y_4+6\} \) es un subconjunto de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades.

Esto muestra que es lo mismo contar unos que otros; y los segundos son simplemente el número de subconjuntos de \( 4 \) elementos de un conjunto de \( 94 \): \( \displaystyle\binom{94}{4} \).

Técnicamente si llamas:

\( A \)=subconjuntos de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades.
\( B \)=subconjuntos de \( \{1,2,\ldots,94\} \) de cuatro elementos.

Lo que hemos hecho es definir una aplicación biyectiva entre \( A \) y \( B \) y por tanto ambos conjuntos tienen el mismo cardinal.

Saludos.

02 Octubre, 2022, 05:07 pm
Respuesta #4

Nub

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 344
  • País: 00
  • Karma: +0/-0
Hola

\( \{x_1,x_2-2,x_3-4,x_4-6\} \) es un conjunto de tres números distintos entre \( 1 \) y \( 94 \)
Acá no se porque restas -2,-4 y -6 y tampoco porque es un conjunto de 3 elementos, ahi no hay 4?

Me equivoqué (¿no es obvio?  :D) quise poner cuatro en lugar de tres. De todas formas la idea es comprobar que es lo mismo contar subconjunto de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades cada par que contar subconjutos de \( \{1,2,\ldots,94\} \) de cuatro elementos, sin más.

Lo que te explico es como relacionar unos con otros. Si los elementos distan \( 3 \) o más tienes que:

\( x_2\geq x_1+3 \) y por tanto \( x_2-2\geq x_1+1 \) es decir \( x_2-2>x_1 \)
\( x_3\geq x_2+3 \) y por tanto \( x_3-4\geq x_2-1 \) es decir \( x_3-4>x_2-2 \)
\( x_4\geq x_3+3 \) y por tanto \( x_4-6\geq x_3-3 \) es decir \( x_4-6>x_3-4 \)

Por tanto \( x_1,x_2-2,x_3-4,x_4-6 \) son números distintos. El mayor como máximo vale \( 100-6=94 \).

Esto muestra como conseguir a partir de un subconjunto de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades, un subconjunto de \( \{1,2,\ldots,94\} \) de cuatro elementos (sin más).

Recíprocamente dado un subconjunto de \( \{1,2,\ldots,94\} \) de cuatro elementos (sin más) \( \{y_1,y_2,y_3,y_4\} \), entonces \( \{y_1,y_2+2,y_3+4,y_4+6\} \) es un subconjunto de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades.

Esto muestra que es lo mismo contar unos que otros; y los segundos son simplemente el número de subconjuntos de \( 4 \) elementos de un conjunto de \( 94 \): \( \displaystyle\binom{94}{4} \).

Técnicamente si llamas:

\( A \)=subconjuntos de \( \{1,2,\ldots,100\} \) de cuatro elementos distanciados \( 3 \) o más unidades.
\( B \)=subconjuntos de \( \{1,2,\ldots,94\} \) de cuatro elementos.

Lo que hemos hecho es definir una aplicación biyectiva entre \( A \) y \( B \) y por tanto ambos conjuntos tienen el mismo cardinal.

Saludos.
Ahora entendí bastante :)
Basta que notes que en uno de esos conjuntos fijado el menor y el mayor elemento el otro está determinado: es su promedio.
No entendí esto, fijamos el menor elemento y el mayor?

02 Octubre, 2022, 05:12 pm
Respuesta #5

Nub

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 344
  • País: 00
  • Karma: +0/-0
Aun asi, encontré las soluciones que dieron pero son bastante inentendibles ;D porque definen cosas sin decir el porque o yo no me doy cuenta
A)

B)

¿Cual seria la idea general de estas? porque la solución de Luis de la parte A es entendible, el mismo la dijo, comprobar que es lo mismo contar sub conjunto de {1,2,…,100} de cuatro elementos distanciados 3 o más unidades cada par que contar subconjutos de {1,2,…,94} de cuatro elemento

02 Octubre, 2022, 06:08 pm
Respuesta #6

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 52,435
  • País: es
  • Karma: +0/-0
Hola

Citar
ink=topic=121446.msg490019#msg490019 date=1664662422]
Basta que notes que en uno de esos conjuntos fijado el menor y el mayor elemento el otro está determinado: es su promedio.
No entendí esto, fijamos el menor elemento y el mayor?

No. Lo que quiero decir es que si tenemos tres elementos de manera que uno es la media aritmética de los otros dos, entonces conocidos el menor y el mayor el del medio queda conocido. Por ejemplo si los tres números son \( 3,8,13 \), conocidos el \( 3 \) y el \( 13 \), entonces \( (13+3)/2=8 \) es el número de en medio.

Por tanto en realidad para contar conjuntos con esas características sólo hay que contar las formas de elegir los elementos menor y mayor de cada conjunto. La única condición es que sean números distintos y de la misma paridad, o los dos pares, o los dos impares, porque si uno fuese par y otro impar el promedio no sería un número entero. En definitiva contamos las formas de elegir o bien dos números pares o bien dos impares.

Si trabajamos con los números del \( 1 \) al \( 100 \), hay \( 50 \) pares  y \( 50 \) impares. Por tanto queda:

\( \displaystyle\binom{50}{2}+\displaystyle\binom{50}{2} \)

B)


Ahí resuelve el último problema que acabo de explicarte de manera totalmente diferente; lo que dice es que en tres números tales que el del medio es promedio de los otros dos, fijado ese elemento central, los otros equidistan de él, de manera que si el del medio es \( k \) los otros dos son \( k-i \) y \( k+i \); si \( k \) es más pequeño o igual que \( 50 \) entonces \( i \) varía entre \( 1 \) y \( k \); si es mayor entre \( 1 \) y \( 100-k \). De ahí el conteo que plantea.

Saludos.

P.D. Has puesto la misma foto en los dos problemas.

02 Octubre, 2022, 07:49 pm
Respuesta #7

Nub

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 344
  • País: 00
  • Karma: +0/-0
Hola

Citar
ink=topic=121446.msg490019#msg490019 date=1664662422]
Basta que notes que en uno de esos conjuntos fijado el menor y el mayor elemento el otro está determinado: es su promedio.
No entendí esto, fijamos el menor elemento y el mayor?

No. Lo que quiero decir es que si tenemos tres elementos de manera que uno es la media aritmética de los otros dos, entonces conocidos el menor y el mayor el del medio queda conocido. Por ejemplo si los tres números son \( 3,8,13 \), conocidos el \( 3 \) y el \( 13 \), entonces \( (13+3)/2=8 \) es el número de en medio.

Por tanto en realidad para contar conjuntos con esas características sólo hay que contar las formas de elegir los elementos menor y mayor de cada conjunto. La única condición es que sean números distintos y de la misma paridad, o los dos pares, o los dos impares, porque si uno fuese par y otro impar el promedio no sería un número entero. En definitiva contamos las formas de elegir o bien dos números pares o bien dos impares.

Si trabajamos con los números del \( 1 \) al \( 100 \), hay \( 50 \) pares  y \( 50 \) impares. Por tanto queda:

\( \displaystyle\binom{50}{2}+\displaystyle\binom{50}{2} \)

Bien ahora entiendo
B)

Ahí resuelve el último problema que acabo de explicarte de manera totalmente diferente; lo que dice es que en tres números tales que el del medio es promedio de los otros dos, fijado ese elemento central, los otros equidistan de él, de manera que si el del medio es \( k \) los otros dos son \( k-i \) y \( k+i \); si \( k \) es más pequeño o igual que \( 50 \) entonces \( i \) varía entre \( 1 \) y \( k \); si es mayor entre \( 1 \) y \( 100-k \). De ahí el conteo que plantea.

Saludos.
"si \( k \) es más pequeño o igual que \( 50 \) entonces \( i \) varía entre \( 1 \) y \( k \); si es mayor entre \( 1 \) y \( 100-k \)"
Porque es asi exactamente :-\?
Citar
P.D. Has puesto la misma foto en los dos problemas.
Ya lo arregle ;)

02 Octubre, 2022, 11:09 pm
Respuesta #8

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 52,435
  • País: es
  • Karma: +0/-0
Hola

"si \( k \) es más pequeño o igual que \( 50 \) entonces \( i \) varía entre \( 1 \) y \( k \); si es mayor entre \( 1 \) y \( 100-k \)"
Porque es asi exactamente :-\?

Por que ten en cuenta que vamos a tomar los números \( k-i,k,k+i \). Tiene que cumplirse que:

\( 1\leq k-i \) es decir \( i\leq k-1 \)
\( k+i\leq 100 \) es decir \( i\leq 100-k \)

Para que se cumplan las dos cosas al tiempo \( i \) tiene que ser menor o igual que el mínimo de ambos.

Saludos.

02 Octubre, 2022, 11:14 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 52,435
  • País: es
  • Karma: +0/-0
HOla

Aun asi, encontré las soluciones que dieron pero son bastante inentendibles ;D porque definen cosas sin decir el porque o yo no me doy cuenta
A)


Ahí lo hace de otra manera. ¿Qué no entiendes exactamente? Grosso modo: lo que dice es que dado un conjunto de cuatro números en las condiciones dadas, puede definir otro de cinco números: el primero de ellos, la diferencia entre los pares siguientes y lo que le falta al cuarto para llegar a \( 100 \). Todos ellos suman \( 100 \). De esta forma reduce el problema a uno de contar soluciones de unas variables de suma prefijada.

Saludos.