[manooooh]

Hola!

Sea \( A=\{a,b,c,e,f,g\} \) un conjunto en donde se define una relación de equivalencia \( E \) y una de orden \( O \), entonces es posible que tengan:

1) \( E \) puede tener 28 pares y \( O \) 21 pares

2) \( E \) puede tener 20 pares y \( O \) 24 pares

3) \( E \) puede tener 14 pares y \( O \) 17 pares

4) \( E \) puede tener 16 pares y \( O \) 18 pares


Me gustó este problema, es interesante de pensarlo ya que (creo) no es mecánico de hacer.

Lo que intenté es:

En primer lugar vamos a trabajar con la matriz de las relaciones, que al ser booleanas, la cantidad de pares ordenados de una relación representa cuántos unos tiene la matriz.

Tanto las de equivalencia como de orden deben ser reflexivas, por lo tanto deben haber 6 unos en la diagonal principal.

Además, en las de orden, la máxima cantidad de unos se consigue si en alguna de las triangulares de la matriz está lleno de unos para que se cumpla la antisimétrica (y como es de orden total, o sea una cadena, luego también es transitiva). Así que en este caso hacemos:

Cantidad de elementos sin la diagonal principal: \( 36-6=30 \)

Tomamos una triangular (la superior por ejemplo): \( 30/2=15 \)

Por lo tanto la máxima cantidad de unos (pares ordenados) es: \( 15+6=21 \) unos. Esto descarta la opción 2) por tener 24 pares.

Ahora bien, yendo a la relación de equivalencia, para que sea simétrica, si agregamos un uno en una triangular, también debe estar su simétrico, por lo tanto los unos vienen "de a pares", por lo tanto como hay 6 unos en la diagonal principal (número par), deberán haber par + par = cantidad par de unos. Esto no da ventaja porque las opciones 1), 3) y 4) ya tienen cantidad pares de unos.

Hasta aquí me quedé.

Pensé en como la de equivalencia produce particiones en el conjunto, y en la matriz de la relación se visualizan como "cajas" de unos, entonces deben haber cuadrados perfectos:

\( 28=x^2+y^2+z^2+t^2+p^2+q^2 \) con \( x,y,z,t,p,q\geq0 \), lo mismo con 14 y 16. Y teniendo en cuenta la cantidad máxima de unos que serían \( 6\cdot6=36 \), pero creo que esto es mucho, hay que andar probando con muchos números. ¿Se podrá continuar desde aquí o hay algún otro atajo?

Entonces, ¿cómo se podría dar con la única opción correcta?

Gracias!!
Saludos

[Luis Fuentes]

Hola

Sea \( A=\{a,b,c,e,f,g\} \) un conjunto en donde se define una relación de equivalencia \( E \) y una de orden \( O \), entonces es posible que tengan:

1) \( E \) puede tener 28 pares y \( O \) 21 pares

2) \( E \) puede tener 20 pares y \( O \) 24 pares

3) \( E \) puede tener 14 pares y \( O \) 17 pares

4) \( E \) puede tener 16 pares y \( O \) 18 pares

Esta es la buena idea:

Pensé en como la de equivalencia produce particiones en el conjunto, y en la matriz de la relación se visualizan como "cajas" de unos, entonces deben haber cuadrados perfectos:

\( 28=x^2+y^2+z^2+t^2+p^2+q^2 \) con \( x,y,z,t,p,q\geq0 \), lo mismo con 14 y 16. Y teniendo en cuenta la cantidad máxima de unos que serían \( 6\cdot6=36 \), pero creo que esto es mucho, hay que andar probando con muchos números. ¿Se podrá continuar desde aquí o hay algún otro atajo?

Donde \( x+y+z+t+p+q=6 \). Ten en cuenta que \( f(x)=x^2+(k-x)^2 \),  es convexa en \( [0,k] \) y tiene el máximo cuando \( x=k \) y el mínimo cuando \( x=k/2 \); es decir en las particiones si divides un conjunto en varios, la suma del cuadrado de sus cardinales disminuye.

Entonces el máximo valor posible es \( 6^2=36 \).

El segundo máximo valor posible es \( 5^2+1^2=26 \). Eso ya descarta (1) (\( E \) con 28  pares).

(2) \( 20=4^2+2^2+1^2 \) puede darse.

(3) \( 14=3^2+2^2+1^2 \) puede darse.

(4) \( 16 \) NO puede darse. El máximo tamaño posible de un subconjunto de la partición sería \( 3 \). Las opciones con una clase de tamaño \( 3 \) son: \( 3^2+3^2=18 \), \( 3^2+2^2+1^2=14<16 \) (si subdividimos más todavía hay menos pares). Y si la más grande tiene tamaño dos, a lo sumo serían \( 2^2+2^2+2^2+1^2=13<16 \).

En cuanto a las relaciones de orden, desde luego como mínimo hay \( 6 \) pares (cada elemento consigo mismo).

Después cada par de elementos a lo sumo aparece una vez. Por tanto el máximo número de pares posibles sería \( 6+\displaystyle\binom{6}{2}=21 \) Eso descarta (2).

Así que la única opción posible sería la (3). Si tomamos la relación de orden con dos ramas \( a\leq b\leq c\leq d\leq e\leq f \) y luego \( a\leq g \), tiene \( 6+\displaystyle\binom{5}{2}+1=17 \) pares.

Saludos.

[manooooh]

Hola Luis, muchas gracias!!

Vaya, me parece que la respuesta se complicó bastante. En la asignatura no se vieron los números combinatorios ni se estudia la convexidad de funciones (apenas se tratan relaciones y funciones).

¿No existe un camino más sencillo y, si es posible, en la misma línea de lo primero que planteé? ¿O quizás trabajando con las "cajas" de unos pero de manera más asequible? Pude descartar 1 opción, me faltarían otras 2 usando lo primero que planteé.

Saludos

[Luis Fuentes]

Hola

Vaya, me parece que la respuesta se complicó bastante. En la asignatura no se vieron los números combinatorios ni se estudia la convexidad de funciones (apenas se tratan relaciones y funciones).

Estás viendo complicaciones donde no las hay, créeme.  Olvídate de la convexidad. Y por otra parte con los números combinatorios sólo se están haciendo conteos elementales que puede entender cualquiera que sepa las cuatro reglas.

En cuanto a las relaciones de equivalencia, el número de pares factibles con todas las posibles sumas:

\( S=a^2+b^2+c^2+d^2+e^2+f^2 \) con \( a+b+c+d+e+f=6 \) enteros no negativos. Supón que están ordenados de mayor a menor.

Si \( a=6 \) entonces \( S=36 \).
Si \( a=5 \) entonces \( S=25+1=26 \).
Si \( a=4 \) entonces las posiblididades para \( S \) son \( 4^2+2^2=20 \) ó \( 4^2+1^2+1^2=18 \).
Si \( a=3 \) entonces las posibilididades para \( S \) son \( 3^2+3^2=18 \) ó \( 3^2+2^2+1^2=14 \) ó \( 3^2+1^2+1^2+1^2=12 \).

Si \( a=2 \) las opciones son \( S=2^2+2^2+2^2=12 \) ó \( S=2^2+2^2+1^2+1^2=10 \) ó \( S=2^2+1^2+1^2+1^2+1^2+1^2=8 \).

Si \( a=1 \) la única posibilidad es \( S=6 \).

Con eso descartas (1) y (4) (he enumerado todas las opciones; pero si sólo queremos descartar esas se puede argumentar ligeramente más rápido).

En cuanto a las de orden cuando escribo el número combinatorio \( \displaystyle\binom{n}{2} \) simplemente estoy contando las formas de emparejar \( n \) elementos en parejas de elementos distintos (cada pareja una sóla vez). Son \( n\cdot (n-1) \) y como la pareja \( (a,b) \) no quiero que aparezca en el orden \( (b,a) \) divido por dos.

Saludos.