Autor Tema: Subconjuntos de un conjunto

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

09 Junio, 2017, 05:51 pm
Leído 1702 veces

Scofield

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 27
  • Karma: +0/-0
  • Sexo: Masculino
Buenas,
he conseguido demostrar que los subconjuntos con un número impar de elementos de un conjunto con n elementos son \( 2^{n-1} \), ya que, mediante el binomio de Newton, y lo siguiente
\( \displaystyle (1+(-1))^n = \sum_{i=0}^n {n \choose i} (-1)^i  \)

\( \displaystyle  2^n = (1+1)^n = \sum_{i=0}^n {n \choose i}  \)
he conseguido demostrar que los subconjuntos con un número par de elementos coinciden con los subconjuntos con un número impar de elementos. Entonces basta dividir el total de subconjuntos que es \( 2^n \) entre 2. Ahora bien, lo que tengo planteado ahora es
¿cuántos subconjuntos con un número de elementos divisibles por 3 tiene un conjunto de n elementos? ¿y con un número de elementos divisibles por 4? ¿se podría extender la demostración anterior para la nueva pregunta o haría falta otra?

Un saludo!

09 Junio, 2017, 07:43 pm
Respuesta #1

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,270
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Buenas,
he conseguido demostrar que los subconjuntos con un número impar de elementos de un conjunto con n elementos son \( 2^{n-1} \), ya que, mediante el binomio de Newton, y lo siguiente
\( \displaystyle (1+(-1))^n = \sum_{i=0}^n {n \choose i} (-1)^i  \)

\( \displaystyle  2^n = (1+1)^n = \sum_{i=0}^n {n \choose i}  \)
he conseguido demostrar que los subconjuntos con un número par de elementos coinciden con los subconjuntos con un número impar de elementos. Entonces basta dividir el total de subconjuntos que es \( 2^n \) entre 2. Ahora bien, lo que tengo planteado ahora es
¿cuántos subconjuntos con un número de elementos divisibles por 3 tiene un conjunto de n elementos? ¿y con un número de elementos divisibles por 4? ¿se podría extender la demostración anterior para la nueva pregunta o haría falta otra?

Un saludo!

En lugar de utilizar el desarrollo de \( (1 - 1)^n \), utiliza el de \( (1\pm{}\omega)^n \), con \( \omega = -\frac{1}{2} + \frac{\sqrt{3}}{2}i \) para múltiplos de \( 3 \), y \( (1 \pm{} i)^n\textrm{ para múltiplos de }4 \). La misma idea para múltiplos de otros números \( m \), se trata de utilizar raíces \( m-simas\textrm{ de }1 \). El resultado te quedará en general en función del resto de \( n \) módulo \( m \).

Saludos,
Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por muchísimo menos ...  (yo)

09 Junio, 2017, 09:50 pm
Respuesta #2

guillem_dlc

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 253
  • País: es
  • Karma: +0/-1
  • Sexo: Masculino
Buenas,
he conseguido demostrar que los subconjuntos con un número impar de elementos de un conjunto con n elementos son \( 2^{n-1} \), ya que, mediante el binomio de Newton, y lo siguiente
\( \displaystyle (1+(-1))^n = \sum_{i=0}^n {n \choose i} (-1)^i  \)

\( \displaystyle  2^n = (1+1)^n = \sum_{i=0}^n {n \choose i}  \)
he conseguido demostrar que los subconjuntos con un número par de elementos coinciden con los subconjuntos con un número impar de elementos. Entonces basta dividir el total de subconjuntos que es \( 2^n \) entre 2. Ahora bien, lo que tengo planteado ahora es
¿cuántos subconjuntos con un número de elementos divisibles por 3 tiene un conjunto de n elementos? ¿y con un número de elementos divisibles por 4? ¿se podría extender la demostración anterior para la nueva pregunta o haría falta otra?

Un saludo!

De \( 0 \), de \( 3 \), de \( 6 \),... elementos. Ponemos \( n=3k+p, p\in \{ 0,1,2\} \)

\( {n \choose 0}+{n \choose 3}+\cdots +{n \choose 3k}=\sum^{k}_{j=0}{n \choose 3j}=\sum^{k}_{j=0}\dfrac{n!}{(3j)!(n-3j)!}=n!\sum^{n}_{j=0}\dfrac{1}{(3j)!(n-3j)!} \)

10 Junio, 2017, 06:07 pm
Respuesta #3

Scofield

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 27
  • Karma: +0/-0
  • Sexo: Masculino
Buenas,
he conseguido demostrar que los subconjuntos con un número impar de elementos de un conjunto con n elementos son \( 2^{n-1} \), ya que, mediante el binomio de Newton, y lo siguiente
\( \displaystyle (1+(-1))^n = \sum_{i=0}^n {n \choose i} (-1)^i  \)

\( \displaystyle  2^n = (1+1)^n = \sum_{i=0}^n {n \choose i}  \)
he conseguido demostrar que los subconjuntos con un número par de elementos coinciden con los subconjuntos con un número impar de elementos. Entonces basta dividir el total de subconjuntos que es \( 2^n \) entre 2. Ahora bien, lo que tengo planteado ahora es
¿cuántos subconjuntos con un número de elementos divisibles por 3 tiene un conjunto de n elementos? ¿y con un número de elementos divisibles por 4? ¿se podría extender la demostración anterior para la nueva pregunta o haría falta otra?

Un saludo!

De \( 0 \), de \( 3 \), de \( 6 \),... elementos. Ponemos \( n=3k+p, p\in \{ 0,1,2\} \)

\( {n \choose 0}+{n \choose 3}+\cdots +{n \choose 3k}=\sum^{k}_{j=0}{n \choose 3j}=\sum^{k}_{j=0}\dfrac{n!}{(3j)!(n-3j)!}=n!\sum^{n}_{j=0}\dfrac{1}{(3j)!(n-3j)!} \)

muchas gracias por la respuesta, me ha abierto un nuevo camino, pero por qué esa elección de n y p?

10 Junio, 2017, 06:09 pm
Respuesta #4

Scofield

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 27
  • Karma: +0/-0
  • Sexo: Masculino
Buenas,
he conseguido demostrar que los subconjuntos con un número impar de elementos de un conjunto con n elementos son \( 2^{n-1} \), ya que, mediante el binomio de Newton, y lo siguiente
\( \displaystyle (1+(-1))^n = \sum_{i=0}^n {n \choose i} (-1)^i  \)

\( \displaystyle  2^n = (1+1)^n = \sum_{i=0}^n {n \choose i}  \)
he conseguido demostrar que los subconjuntos con un número par de elementos coinciden con los subconjuntos con un número impar de elementos. Entonces basta dividir el total de subconjuntos que es \( 2^n \) entre 2. Ahora bien, lo que tengo planteado ahora es
¿cuántos subconjuntos con un número de elementos divisibles por 3 tiene un conjunto de n elementos? ¿y con un número de elementos divisibles por 4? ¿se podría extender la demostración anterior para la nueva pregunta o haría falta otra?

Un saludo!

En lugar de utilizar el desarrollo de \( (1 - 1)^n \), utiliza el de \( (1\pm{}\omega)^n \), con \( \omega = -\frac{1}{2} + \frac{\sqrt{3}}{2}i \) para múltiplos de \( 3 \), y \( (1 \pm{} i)^n\textrm{ para múltiplos de }4 \). La misma idea para múltiplos de otros números \( m \), se trata de utilizar raíces \( m-simas\textrm{ de }1 \). El resultado te quedará en general en función del resto de \( n \) módulo \( m \).

Saludos,
Esto creo que me queda un poco lejos, es decir, por qué esta expresión  \( (1\pm{}\omega)^n \), con \( \omega = -\frac{1}{2} + \frac{\sqrt{3}}{2}i \) da el número de subconjuntos con un número de elementos divisibles por 3?

10 Junio, 2017, 06:52 pm
Respuesta #5

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,270
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Buenas,
he conseguido demostrar que los subconjuntos con un número impar de elementos de un conjunto con n elementos son \( 2^{n-1} \), ya que, mediante el binomio de Newton, y lo siguiente
\( \displaystyle (1+(-1))^n = \sum_{i=0}^n {n \choose i} (-1)^i  \)

\( \displaystyle  2^n = (1+1)^n = \sum_{i=0}^n {n \choose i}  \)
he conseguido demostrar que los subconjuntos con un número par de elementos coinciden con los subconjuntos con un número impar de elementos. Entonces basta dividir el total de subconjuntos que es \( 2^n \) entre 2. Ahora bien, lo que tengo planteado ahora es
¿cuántos subconjuntos con un número de elementos divisibles por 3 tiene un conjunto de n elementos? ¿y con un número de elementos divisibles por 4? ¿se podría extender la demostración anterior para la nueva pregunta o haría falta otra?

Un saludo!

En lugar de utilizar el desarrollo de \( (1 - 1)^n \), utiliza el de \( (1\pm{}\omega)^n \), con \( \omega = -\frac{1}{2} + \frac{\sqrt{3}}{2}i \) para múltiplos de \( 3 \), y \( (1 \pm{} i)^n\textrm{ para múltiplos de }4 \). La misma idea para múltiplos de otros números \( m \), se trata de utilizar raíces \( m-simas\textrm{ de }1 \). El resultado te quedará en general en función del resto de \( n \) módulo \( m \).

Saludos,
Esto creo que me queda un poco lejos, es decir, por qué esta expresión  \( (1\pm{}\omega)^n \), con \( \omega = -\frac{1}{2} + \frac{\sqrt{3}}{2}i \) da el número de subconjuntos con un número de elementos divisibles por 3?

Porque \( \omega^3 = 1\textrm{ y }\omega^2 = \overline{\omega} \).

Si llamas

\( M_0 = \displaystyle\sum_{k=0}^m{\displaystyle\binom{3m+2}{3k}} \)

\( M_1 = \displaystyle\sum_{k=0}^m{\displaystyle\binom{3m+2}{3k+1}} \)

\( M_2 = \displaystyle\sum_{k=0}^m{\displaystyle\binom{3m+2}{3k+2}} \)

Tienes que

\( n = 3m \;\Rightarrow{}\;M_1 = M_2=\displaystyle\frac{2^{3m}-(-1)^m}{3}, \;\;M_0 = M_1 + (-1)^m \)

\( n = 3m + 1 \;\Rightarrow{}\;M_2 = \displaystyle\frac{2^{3m+1}-2(-1)^m}{3}, \;\;M_0 = M_1 = M_2 + (-1)^m \)

\( n = 3m  +2 \;\Rightarrow{}\;M_0 = M_2=\displaystyle\frac{2^{3m+2}-(-1)^m}{3}, \;\;M_1 = M_0 + (-1)^m \)

Saludos,

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por muchísimo menos ...  (yo)