Reducidas de triples y/o dobles a un fallo

Algoritmos, fórmulas, estadísticas...
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Reducidas de triples y/o dobles a un fallo

Mensaje por fortuna »

Introducción.

Se trata de explicar un método de reducción de quinielas para "t" partidos triples en reducción a 1 fallo o "d" dobles a 1 fallo.

En todos los casos se substituye el "1" de la quiniela por un 0, la "X" por un 1 y el "2" por un 2.

Requisitos.

Se requieren conocimientos del sistema de numeración en base 2 y 3.

Se requieren conocimientos mínimos de álgebra lineal.

Reducidas de dobles.

En los dobles, cada columna de n apuestas equivale a n+1 casos con un fallo respecto a esa columna:

Supongamos que tenemos 5 filas. Pongamos una y vemos cuantas apuestas cubre:

Código: Seleccionar todo

0 | 1 0 0 0 0      Estas columnas tienen 1 fallo
0 | 0 1 0 0 0      respecto a la de todo ceros
0 | 0 0 1 0 0 
0 | 0 0 0 1 0      luego cada columna cubre a 		
0 | 0 0 0 0 1      si misma y 5 más con 1 fallo como máximo.
En general se ve que cada columna equivale a 1 columna con todo aciertos y n columnas con 1 fallo, luego, dado que hay 2^d columnas con d dobles para que exista un sistema de reducción perfecto:

Código: Seleccionar todo

		
2^d
---- = entero
d+1
Principio 0


Se supone que el sistema esta combinado de tal forma que cada columna se cubre a si misma con 0 fallos y a d+1 con 1 fallo. Además, cada columna cubre d+1 columnas distintas, que no han sido cubiertas por otra columna de la combinación.

Por ejemplo los casos d=7

Código: Seleccionar todo

2^7   2^7   
--- = --- = 2^(7-3)=2^4=16 
7+1   2^3  
Por ejemplo los casos d=15

Código: Seleccionar todo

2^15  2^15   
----=-----=2^(15-4)=2^11=2048
15+1   2^4

Condiciones deben cumplir las columnas para pertenecer a este sistema.


Veamos lo que pasa si dos columnas C1 y C2 se diferenciaran en menos de tres partidos:

Código: Seleccionar todo

C1 C2
0   0
0   0
0   0 
0   1
0   1
Las columnas:

Código: Seleccionar todo

C3 C4 
0   0
0   0
0   0
1   0
0   1
La columnas C3 y C4 son cubiertas simultáneamente por C1 y C2, con lo que no se verifica la segunda parte del principio 0.

En cambio se ve, que si se diferencian en tres partidos al menos, no habrá solapamiento

Código: Seleccionar todo

C1        	  C2
0               0
0               0
0               1 
0               1
0               1

COBERTURAS

DE C1           DE C2
0 1 0 0 0 0     0 1 0 0 0 0
0 0 1 0 0 0     0 0 1 0 0 0
0 0 0 1 0 0     1 1 1 0 1 1
0 0 0 0 1 0     1 1 1 1 0 1
0 0 0 0 0 1     1 1 1 1 1 0
Se ver que ninguna columna de la cobertura de C1 es igual a ninguna de la cobertura de C2. Por ello definimos, para sistemas con 1 sólo fallo que deben cumplir con la distancia de Hamming.

Distancia de HAMMING


Dos columnas del sistema deben diferenciarse en al menos 3 partidos.

(Distancia de Hamming para la corrección de 1 error. Allí lo que se trata es de dar redundancia a los datos transmitidos por un sistema y con esta redundancia detectar y corregir un posible error en un bit transmitido. Nótese que allí la información redundante no forma parte de los datos. Allí se intenta minimizar la información redundante)

En los siguientes mensajes se explica como generar un sistema de quinielas que respete la distancia de hamming.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Reducidas de dobles

Mensaje por fortuna »

Reducidas de dobles

Principio de dependencia lineal

Para que la fórmula:

Código: Seleccionar todo

2^d
--- = 'entero'
d+1
Para ello se debe verificar que

Código: Seleccionar todo

       (d-d0)
entero=2
y

Código: Seleccionar todo

       d0
(d+1)=2

Por tanto podemos considerar que tenemos d-d0 filas independientes (en el rango 0..1) y que las d0 son dependientes de las d-d0. Supondremos además que son linealmente dependientes.

Para el caso d=7 (d0=3), tendremos que una columna del sistema se forma:

Código: Seleccionar todo

d1=d1                                   Parte independiente
d2=d2
d3=d3
d4=d4
------------------------------------
d5=(a11*d1+a12*d2+a13*d3+a14*d4) %2     Parte dependiente
d6=(a21*d1+a22*d2+a23*d3+a24*d4) %2
d7=(a31*d1+a32+d2+a33*d3+a34*d4) %2
Donde d1,d2,d3y d4 varían de 0 a 1 y d5,d6,d7 se calculan como se indica. %2 indica que estamos trabajando en aritmética de módulo 2.

Se trata de deducir un sistema que permita calcular los coeficientes a11..a34, de forma que dados d1,d2,d3,d4 se obtengan los tres partidos correspondientes dependientes y que cumplan con la distancia de Hamming >= 3. En este caso, obtendríamos 2^4 columnas variando los partidos d1 a d4 entre 0 y 1 y calculando d5, d6 y d7.

La parte calculada (d5,d6,d7) anterior se puede escribir como un producto de matrices:

Código: Seleccionar todo

|a11 a12 a13 a14|   |d1|
|a21 a22 a23 a24| x |d2|
|a31 a32 a33 a34|   |d3|
                    |d4|

Llamemos M a la primera matriz.

Código: Seleccionar todo

  |a11 a12 a13 a14|
M=|a21 a22 a23 a24|
  |a31 a32 a33 a34|

Para ver las condiciones que deben cumplir los coeficientes de M, observemos que estamos más interesados en las diferencias entre las columnas del sistema que en las mismas. De aquí las definiciones que se indican en el siguiente mensaje.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

definiciones y operadores de diferencias

Mensaje por fortuna »

Se ha definido la matriz M. Sabemos que debe tener la restricción que haga que las columnas se diferencien en 3 elementos. Ello es lo mismo que decir la diferencia de dos columnas debe ser mayor que 3.

Dado que estamos interesados en las diferencias entre columnas definimos el operador D(Ci,Cj) donde Ci y Cj son dos columnas del sistema, aquel que produce una columna test, donde un elemento vale 0 si las columnas Ci,k y Cj,k son iguales y 1 si son distintas.

Por ejemplo, si Ci y Cj son

Código: Seleccionar todo

Ci Cj          D(Ci,Cj)
|1||0|           |1| 
|0||0|           |0|
|0||0|           |0|
|1||1|           |0| 
|0||1|           |1|
|0||0|           |0|
|0||1|           |1|

Es decir el operador D(Ci,Cj) es el operador diferencia.

Se define el operador H(Ci,Cj) como la suma de los elementos de D(Ci,Cj), es decir, H es la distancia de Hamming. En el caso anterior H(Ci,Cj)=3

Dos columnas del sistema, deben diferenciarse en al menos 3 partidos. Por tanto lo que se busca es un sistema de columnas C, de tal forma que H(Ci,Cj)>=3 para toda columna Ci<>Cj. El sistema esta definido si se conocen los coeficientes de M que verifica la relación anterior.

Llamemos Di(Ci,Cj) al operador D cuando actúa sobre la parte independiente y Hi(Ci,Cj) a la distancia de Hamming de la parte independiente.

Se puede observar que H(Ci,Cj)=Hi(Ci,Cj)+Hd(Ci,Cj), es decir, la distancia entre dos columnas es la distancia entre la parte independiente más la distancia de la parte calculada.

Para determinar los valores de M se observará que condiciones se tienen que verificar si Hi(Ci,Cj) es 0,1,2 o más.

En el siguiente mensaje se explica como a partir de estas definiciones se obtienen las reglas para calcular la matriz M.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Deducción de M para sistemas de dobles

Mensaje por fortuna »

Para determinar los valores de M se observará que condiciones se tienen que verificar si Hi(Ci,Cj) es 0,1,2 o más.

Caso Hi=0

Si Hi(Ci,Cj)=0 indica que Ci=Cj, entonces H(Ci,Cj)=0 y MxCi generará la misma columna que MxCj. Es decir, si la distancia de la parte independiente es 0 las dos columnas serán idénticas. Caso trivial.

Caso Hi=1

Analizamos el caso Hi(Ci,Cj)=1. Indica que las columnas Ci y Cj se diferencian en 1 valor en la parte independiente. Veamos un par de ejemplos:

Di podría ser (recordemos que es una diferencia de columnas y no las columnas propiamente dichas).

Código: Seleccionar todo

|1|
|0|
|0|
|0|
y las diferencias de las columnas calculadas en Ci y Cj serán, al aplicar el producto de matrices:

Código: Seleccionar todo

   |a11 a12 a13 a14|   |1| |a11|
Dd=|a21 a22 a23 a24| x |0|=|a21|
   |a31 a32 a33 a34|   |0| |a31|
                       |0|
Para que H(Ci,Cj)>=3, Hd(Ci,Cj) debe ser >=2, dado que Hi(Ci,Cj) ya vale 1. Dicho de otra forma. Si distancia de la parte independiente es 1, la distancia de la parte calculada debe se al menos 2.

Esto implica que

Código: Seleccionar todo

  |a11|
Hd|a21|>=2
  |a31|
Entonces se debe verificar que entre a11,a21 y a31 al menos dos de ellos sean distintos de cero.

Otro ejemplo, para comprobar la afirmación anterior:Si Di fuera

Código: Seleccionar todo

|0|
|1|
|0|
|0|

Código: Seleccionar todo

   |a11 a12 a13 a14|  |0|    |a12|
Dd=|a21 a22 a23 a24|x |1| =  |a22|
   |a31 a32 a33 a34|  |0|    |a32|
                      |0|
Llegamos a la conclusión de que entre a12,a22 y a32 al menos dos de ellos deben ser distintos de cero.

En general ocurrirá para cada posible valor de Di.


Regla 1


En cada columna de M debe haber al menos dos términos distintos de 0

Caso Hi=2


Si Hi(C1,C2)=2 entonces Hd(C1,C2) debe ser >=1 para que H(C1,C2)>=3.

Dicho de otra forma: Si dos columnas se diferencian en 2 en la parte independiente, debe diferenciarse en al menos 1 en la parte calculada.

Si Di fuera

Código: Seleccionar todo

     |1|
     |1|
Di=  |0|
     |0|

     |a11 a12 a13 a14| |1|   |a11+a12|
Dd=  |a21 a22 a23 a24|x|1| = |a21+a22|
     |a31 a32 a33 a34| |0|   |a31+a32|
                       |0|
Esto implica que:

Código: Seleccionar todo

  |a11+a12|
Hd|a21+a22|>=1
  |a31+a32|
Al menos una de las sumas debe ser diferente de 0.

En general, dadas las sumas

a1i+a1j
a2i+a2j
a3i+a3j

Al menos una de ellas debe ser distinta de 0.

Código: Seleccionar todo

|a1i a1j|        |0|
|a2i a2j|x|1| <> |0| en base 2
|a3j a3j| |1|    |0|
Para que cualquiera de esas sumas sea 0, basta con que las columnas sean linealmente independientes y distintas de 0, que en base 2 se traduce a que sean distintas. La demostración se la dejamos a algún matemático que pase por aquí.

Regla 2


En M no puede haber dos columnas iguales


Por último si Di(C1,C2)>=3 ya no hay que imponer restricciones a M, ya que H ya se diferencia en 3.


En el próximo mensaje veremos las conclusiones y varios ejemplos.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Resultados en los sistemas de dobles, ejemplos

Mensaje por fortuna »

Notese que tanto filas como columnas pueden ser intercambiados.

Para calcular las matrices M en base 2, basta con poner todos las posibilidades y quitar las columnas que tienen menos de dos unos.

Vemos entonces que la matriz, para D=7, D0=3 y D-D0=4, luego debemos obtener una matriz de 3 filas (dependiente) y 4 columnas (independiente).

Partimos de todas las posibilidades de una matriz de 3 filas:

Código: Seleccionar todo

|00001111|
|00110011|
|01010101|


Aplicamos la regla 1 y eliminamos todas las que tienen más de 2 ceros.

Código: Seleccionar todo

|0111|
|1011|
|1101|
Es la matriz de paridad para reducidas de 7 dobles.

y observamos que también verifican la regla 2 ya que hemos partido de columnas distintas. Ésto no pasará con las reducidas de triples.

Para 15 partidos, donde también hay reducción perfecta procedemos de forma similar. Para D=15, D0=4 y D-D0=11. Debemos obtener una matriz de 4 filas, para los términos dependientes y 11 columnas, donde variar los independientes.

Código: Seleccionar todo

|0000000011111111|
|0000111100001111|
|0011001100110011|
|0101010101010101|
Aplicando la regla 1, eliminamos las de más de 2 ceros, de forma que queden columnas con al menos dos que no sean 0.

Código: Seleccionar todo

|00001111111|
|01110001111|
|10110110011|
|11011010101|
Que también verifican la regla 2.

Como curiosidad se puede obtener una matriz para 31 dobles.

Código: Seleccionar todo

|10111100001111110000000111|
|11011101110001110000111001|
|11101110110110010111001000|
|11110111011010101010010010|
|11111011101101001100100100|
En el siguiente mensaje se resume lo visto y se desarrolla algún ejemplo.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Resumen de reducidas perfectas de dobles

Mensaje por fortuna »

Resumen:

Para obtener la reducida de 7 partidos al doble se procede de la siguiente forma:

Código: Seleccionar todo

d1=|d1|
d2=|d2|
d3=|d3|
d4=|d4|
d5=|1011| |d1|=(d1+d3+d4) %2
d6=|1101|X|d2|=(d1+d2+d4) %2
d7=|1110| |d3|=(d1+d2+d3) %2
          |d4|
donde hay que variar d1..d7 de 0 a 1 y %2 indica trabajar en modulo 2.

El resultado es

Código: Seleccionar todo

d1 0000000011111111 parte independiente
d2 0000111100001111
d3 0011001100110011
d4 0101010101010101
   ----------------
d5 0110011010011001 parte dependiente
d6 0101101010100101
d7 0011110011000011
Si se substituye el 0 por 1, el 1 por X y el por 2, se obtiene la reducida de LAE de 7 dobles.

Se deja a los foristas que hayan tenido la paciencia de llegar hasta aquí la verificación de la distancia de Hamming así como de verificar que cualquier columna de 7 dobles (0-1) está con un fallo, como máximo, en el sistema.

Para obtener la reducida de 15 partidos al doble se procede de la siguiente forma:

Código: Seleccionar todo

d1 =                               |d1 |
d2 =                               |d2 |
d3 =                               |d3 |
d4 =                               |d4 |
d5 =                               |d5 |
d6 =                               |d6 |
d7 =                               |d7 |
d8 =                               |d8 |
d9 =                               |d9 |
d10=                               |d10|
d11=                               |d11|
d12=|1 0 1 1 1 0 0 0 1 1 1|  |d1 | |d1+d3+d4+d5+d9+d10+d11|
d13=|1 1 0 1 1 0 1 1 0 0 1|  |d2 | |d1+d2+d4+d5+d7+d8+d11 |
d14=|1 1 1 0 1 1 0 1 0 1 0|X |d3 |=|d1+d2+d3+d5+d6+d8+d10 |
d15=|1 1 1 1 0 1 1 0 1 0 0|  |d4 | |d1+d2+d3+d4+d6+d7+d9  |
                             |d5 |
                             |d6 |
                             |d7 |
                             |d8 |
                             |d9 |
                             |d10|
                             |d11|
donde hay que variar d1..d11 de 0 a 1 y trabajar en modulo 2.

El desarrollo ocupa 2048 columnas y se omite.

En el próximo mensaje, se explica como hacer lo mismo para reducidas de triples. Se obtendrán las reducidas de 4T, 13T y como curiosidad la de 40 triples.


Saludos.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Reducidas perfectas de triples

Mensaje por fortuna »

Reducidas de tres partidos

En este caso trabajamos en modulo 3

Cada columna de n apuestas equivale a 2n+1 casos:

Supongamos que tenemos 4 filas. Pongamos una y vemos cuantas apuestas cubre:

Código: Seleccionar todo

0|12000000 Estas columnas tienen 1 fallo respecto a la de todo ceros
0|00120000 
0|00001200
0|00000012 luego cada columna cubre a si misma y 8 más
En general se ve que cada columna equivale a 1 columna con todo aciertos y 2n columnas con 1 fallo, luego, para que exista un sistema perfecto:

Código: Seleccionar todo

3^T
----=entero
2T+1
Ejemplo, el caso T=4, T0=2

Código: Seleccionar todo

3^4   3^4   
--- = --- = 3^(4-2)=3^2=9
7*2+1 3^2  

Y el casos T=13, T0=3

Código: Seleccionar todo

3^13     3^13   
------ = ---- = 3^(13-3)=3^10=59049
13*2+1   3^3  

Análogamente al caso de dobles, podemos considerar que tenemos t-t0 filas independientes (en el rango 0..2) y que las t0 son linealmente dependientes de las t-t0.
Para el caso t=4, t0=2,t-t0=2 tendremos que una columna tiene t1 y t2 independientes y t3 y t3 dependen de t1 y t2:

Código: Seleccionar todo

t1=|t1           |  
t2=|t2           |  
t3=|a11*t1+a12*t2|  
t4=|a21*t1+a22*t2|  
o escrito de forma matricial

Código: Seleccionar todo

|t3|= |a11 a12|  |t1|
|t4|  |a21 a22|x |t2|

Trabajando en aritmética de módulo 3

Operamos como en el caso binario.

Llamemos M a la primera matriz.

Código: Seleccionar todo

  |a11 a12|
M=|a21 a22|
y las funciones D, Di, Dd, H Hi y Hd se definen de la misma forma.

En el siguiente mensaje se deducen las reglas para la obtención de M.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Reglas para la obtencion de la matriz de paridad de triples.

Mensaje por fortuna »

Omitimos el caso trivial.

Caso Hi=1

Si Hi(Ci,Cj)=1, para que H(Ci,Cj)>=3, Hd(Ci,Cj) debe ser >=2.

Di podría ser

|1|
|0|

y las diferencias de las columnas calculados en Ci y Cj serán

Código: Seleccionar todo

   |a11 a12| |1|   |a11|         |a11|
Dd=|a21 a22|x|0| = |a21|,   -> Hd|a21|>=2
A diferencia del caso binario ahora Di podría ser también los siguientes valores:

Di podría ser

Código: Seleccionar todo

|2|
|0|

Código: Seleccionar todo

   |a11 a12| |2|   |2*a11|        |2*a11|
Dd=|a21 a22|x|0| = |  a21|,  -> Hd|  a21|>=2
Se debe verificar lo mismo para

Código: Seleccionar todo

|0| y |0|
|1|   |2|
La única solución es, como en el caso binario:

Regla 1

En cada columna de M debe haber al menos dos términos distintos de 0

Caso Hi=2

Si Hi(Ci,Cj)=2 tenemos, Hd(Ci,Cj)>=1:

ocurren en los siguientes casos de Di(Ci,Cj):

Código: Seleccionar todo

         |1| |1| |2| |2|
Di(Ci,C)=|1|,|2|,|1|,|2|
Los valores de Dd y requerimientos de Hd son

Código: Seleccionar todo


|a11 a12| |1|   |a11+a12|            |a11+a12|
|a21 a22|x|1| = |a21+a22|,     ->  Hd|a21+a22|>=1

|a11 a12| |2|   |2*a11+a12|          |2*a11+a12|
|a21 a22|x|1| = |2*a21+a22|,   ->  Hd|2*a21+a22|>=1,


|a11 a12| |1|   |a11+2*a12|          |a11+2*a12|
|a21 a22|x|2| = |a21+2*a22|,   ->  Hd|a21+2*a22|>=1,


|a11 a12| |2|   |2*a11+2*a12|        |2*a11+2*a12|
|a21 a22|x|2| = |2*a21+2*a22|, ->  Hd|2*a21+2*a22|>=1

Las 4 expresiones anteriores se pueden poner de la forma

Código: Seleccionar todo

|a11 a12| |k1|    |0|
|a21 a22|x|k2| <> |0| en base 3
Siendo k1 y k2 ambos distintos de cero, la última desigualdad se verifica en base 3 si

Código: Seleccionar todo

|a11 a12|
|a21 a22| 
es linealmente independiente, lo cual nos lleva a la


Regla 2

Cada par de columnas de M deben ser linealmente independientes
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Reducidas perfectas de triples: Resultados

Mensaje por fortuna »

Resultados

Aplicando las dos reglas anteriores se obtiene para T=4, T0=2

Código: Seleccionar todo

          |1 1|
M(4,3)=   |1 2|
Para T=13 reducimos la siguiente matriz posible, T0=3

Detallemos la obtención de la reducida de 13 partidos.

Como T-T0=10 serán 10 columnas. Como T0=3 serán tres filas, las de los partidos dependientes.

Código: Seleccionar todo

|000000000111111111222222222| 
|000111222000111222000111222|  
|012012012012012012012012012|
Aplicamos la regla 1 y eliminamos las que dejen menos de dos términos distintos de 0, como hay 3 filas, eliminamos los que tengan más de un 0.

Código: Seleccionar todo

|00001111111122222222| 
|11220011122200111222|  
|12121201201212012012|

Y después la regla 2, sabiendo que 1*2=2*1=2 y que 2*2=1, será eliminar aquellas que sean unas múltiplo de 2 de otra anterior, por ejemplo, las columnas indicadas son linealmente dependientes:

Código: Seleccionar todo

|0| |0| 
|2|=|1|x2  
|2| |1|

Código: Seleccionar todo

|2| |1|
|2|=|1|x2
|1| |2|

Nos queda:

Código: Seleccionar todo

|0011111111| 
|1100121122|  
|1212001212|
Es la matriz de paridad de la reducida de 13T.

En incluso para T=40 , T0=4

Código: Seleccionar todo

|000000000000000000000000000111111111111111111111111111222222222222222222222222222|
|000000000111111111222222222000000000111111111222222222000000000111111111222222222| 
|000111222000111222000111222000111222000111222000111222000111222000111222000111222|  
|012012012012012012012012012012012012012012012012012012012012012012012012012012012|
Aplicando la regla 1

Código: Seleccionar todo

|000000000000000000001111111111111111111111111122222222222222222222222222|
|000011111111222222220000000011111111122222222200000000111111111222222222|
|112200111222001112220011122200011122200011122200111222000111222000111222|
|121212012012120120121201201201201201201201201212012012012012012012012012|

Y por la regla 2

Código: Seleccionar todo

|000000000011111111111111111111111111|
|001111111100000000111111111222222222|
|110011122200111222000111222000111222|
|121201201212012012012012012012012012|
Es la matriz de paridad de la reducida perfecta de 40 triples.

El desarrollo, ya lo comentamos en otro post, ocupa 5.596.921 TeraBytes en formato ascii en Linux (sólo LF no CR+LF) y no cabe, que yo sepa, en ningún ordenador del mundo.
Última edición por fortuna el Mar 28 Mar, 2006 5:03 pm, editado 1 vez en total.
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Resumen de reducidas perfectas de triples

Mensaje por fortuna »

Resumen

Para obtener la reducida de 9 partidos al triple se procede de la siguiente forma:


Código: Seleccionar todo

t1=           |t1     |
t2=           |t2     |
t3=|1 1| |t1|=|t1+t2  |%3
t4=|1 2|X|t2| |t1+2*t2|%3

donde hay que variar t1..t2 de 0 a 2 y %3 indica trabajar en modulo 2.

El resultado es

Código: Seleccionar todo

t1 000111222 parte independiente
t2 012012012
------------ 
t3 012120201 parte dependiente
t4 021102210
Si se sustituye 0 por 1, 1 por X y 2 por 2 se obtiene la reducida de 4T de LAE.

Se deja al lector la verificación de la distancia de Hamming así como de verificar que cualquier columna de 4 triples (0-3) esta con un fallo, como máximo, en el sistema.

La expansión de M(13,3) es demasiado larga para este documento, pero muy fácil de realizar mediante programación. Joan tiene una aplicación que graba en un fichero las reducidas perfectas conocidas, así como la reducida de 11T a dos fallos que se obtiene por un método similar.


Todo lo anterior es aplicable a sistemas de base >3 pero la base debe ser un numero primo, para que los productos,
utilizados en Hd (distancia de Hamming de la parte dependiente), en dicha base cumplan: a*b<>0 si a y b <>0. (p.e (2*2) mod 4=0). Por ejemplo en quinigol se puede obtener con la base de 5 partidos.

Próximo tema:

Tablas de reducción perfectas.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Quiero agradecer públicamente el trabajo que ha publicado Fortuna sobre las reducciones perfectas. Trabajo al que tuve el privilegio de conocer hace unos meses y como consecuéncia del qual realicé este pequeño programa que hace las reducciones perfectas con el método espuesto por Fortuna.

Es increible la velocidad con que se realiza. Incluso la reducción de 13 triples al 13 se realiza en un tiempo muy breve (tened en cuenta que la mayor parte del tiempo se consume escribiendo el fichero de salida).


Podeis descargar el programa en este link:

http://www.mytempdir.com/479435

Muchas grácias Fortuna por este estupendo trabajo.
Saludos

https://www.quinielista.es/dnp1x2/joand/
Peña agrupada en la "Piedra_Filosofal"
Avatar de Usuario
Salva(ALBO2001)
12
12
Mensajes: 1059
Registrado: Vie 26 Dic, 2003 5:34 pm
Ubicación: Zaragoza

Mensaje por Salva(ALBO2001) »

Hola Fortuna y Joan,

¡¡¡¡¡Impresionante!!!!!! el trabajo realizado tanto por Fortuna como por Joan, ¡¡¡¡¡Enhorabuena!!!! a los dos.

¡¡¡¡¡Muchisimas gracias!!!!!!

Saludos

Salva
futbolin
10
10
Mensajes: 47
Registrado: Mié 18 Ene, 2006 2:22 am

Mensaje por futbolin »

felicitaros a ambos por vuestro trabajo y daros las gracias por compartirlo
saludos
Avatar de Usuario
lee_bran
12
12
Mensajes: 1379
Registrado: Vie 09 Dic, 2005 5:18 pm
Contactar:

Mensaje por lee_bran »

Pues yo os agradezco a los dos este esfuerzo dedicado: una auténtica joyita.

Sólo una cosa respecto al programa: para los dobles podemos generar todas las soluciones equivalentes posibles sin mas que cambiar el valor de la base, pero para los triples creo que no porque necesitarían 2 bases. No hace falta que lo cambies, es sólo un apunte.

Por lo demás me parece perfecto, de hecho seguramente lo use para jugar alguna quiniela de las de verdad, pues me encantan estas reducciones.

Un saludo.
Avatar de Usuario
Locuaz
13
13
Mensajes: 3416
Registrado: Lun 15 Ago, 2005 1:30 pm

Mensaje por Locuaz »

Yo me he quedado en los requisitos,no los superaba así que me he limitado a flipar :shock: ,tan sólo quiero agradecer a gente cómo FORTUNA su participación en este foro ya que hacen que esto sea ALGO MÁS que un foro de discusión.

Un saludo.
Imagen
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Recuerdo que hace unos meses Fortuna puso la matriz de la reducción de 40 triples. En aquel entonces vi que las otras matrices (la de 4 y 13 triples al 13) eran hijas de esta. No lo publiqué entonces por respeto a la voluntad de Fortuna.

Pero ahora que ya lo ha hecho público me atrevo a mostrar este hecho: en azul los elementos de la matriz de reducción de 13 triples, y en rojo los de 4 triples.

|Imagen
Saludos

https://www.quinielista.es/dnp1x2/joand/
Peña agrupada en la "Piedra_Filosofal"
Avatar de Usuario
lee_bran
12
12
Mensajes: 1379
Registrado: Vie 09 Dic, 2005 5:18 pm
Contactar:

Mensaje por lee_bran »

Para las reducciones del QuiniGol del tipo 4-4-4-1-1-1, 8-8-8-1-1-1 y 16-16-16-1-1-1 al 5 por 8, 32 y 128 euros que he sacado he utilizado criterios de generación y he conseguido sacar la mínima teórica posible, todas partiendo de la mas pequeña, como Joan (bueno, al revés). La de 9-9-9-9-1-1 al 4 por 27 también utiliza mas o menos el mismo criterio.

Aún creo que con métodos deductivos podría sacar alguna más, pero después de haber visto el desarrollo de otras reducciones récord hasta ahora he considerado necesario utilizar criterios de búsqueda automática, ya que parece que no tienen un patrón lógico de generación.

Pues en eso estamos, y a ver hasta donde llegamos...
fortuna
12
12
Mensajes: 1693
Registrado: Vie 15 Abr, 2005 2:43 am
Ubicación: Frente a la pantalla del ordenador
Contactar:

Re:

Mensaje por fortuna »

lee_bran escribió:Para las reducciones del QuiniGol del tipo 4-4-4-1-1-1, 8-8-8-1-1-1 y 16-16-16-1-1-1 al 5 por 8, 32 y 128 euros que he sacado he utilizado criterios de generación y he conseguido sacar la mínima teórica posible, todas partiendo de la mas pequeña, como Joan (bueno, al revés). La de 9-9-9-9-1-1 al 4 por 27 también utiliza mas o menos el mismo criterio.

Aún creo que con métodos deductivos podría sacar alguna más, pero después de haber visto el desarrollo de otras reducciones récord hasta ahora he considerado necesario utilizar criterios de búsqueda automática, ya que parece que no tienen un patrón lógico de generación.

Pues en eso estamos, y a ver hasta donde llegamos...
El número de columnas teóricas se desarrolla siguiendo el binomio de Newton.

Para N partidos de P posibilidades cada uno, P^N es el total de casos para los N.

Si estamos interesados en un fallo, de los P casos, 1 acierta y P-1 son fallos, es decir P=(P-1) fallos +1 acierto.

P^N=(P-1+1)^N. Aplicando el binomio de Newton a P^N tenemos:

P^N=((P-1)+1)^N=C(N,0)+C(N,1)*(P-1)*1+C(N,2)*(P-1)^2*1^2+...

El primer término es el acierto, 1 caso

El segundo término son los casos donde tenemos 1 fallo exactamente, C(N,1)*(P-1)

La suma de los dos son los casos donde fallamos como mucho 1 partido de N.

Para reducidas a un fallo, por tanto los casos que cubre una columna de N partidos con P posibilidades es

1+C(N,1)*(P-1)=1+N*(P-1)

Por tanto para hacer una reducida perfecta ideal, será el cociente:

R(N partidos,P posibilidades,1 fallos)=P^N/(1+N*(P-1))

Para el caso que expone lee_bran, 4-4-4 (no pongo los fijos) tenemos:

R(3,4,1)=4^3/(1+3*3)=64/10=6,4. Como no es posible tener fracciones, redondeamos a 7. Lee la hace con 8 y me parece muy buen resultado.

Para el caso 8-8-8 :

R(3,8,1)=8^3/(1+3*7)=512/21=24,38. Como no es posible tener fracciones, redondeamos a 25. Lee la hace con 32 y me parece también muy buen resultado.

Para el caso 16-16-16 :

R(3,8,1)=16^3/(1+3*16)=4096/49=83,59. Redondeamos a 84. Lee la hace con 128 y ya no me parece tan buena.

Para reducidas a dos fallos, tomamos un término más del binomio de Newton.

cobertura de una columna=1+N*(P-1)+(1/2)*N*(N-1)*(P-1)^2

R(N,P,2)=P^N/(1+N*(P-1)+(1/2)*N*(N-1)*(P-1))

Para el caso 9-9-9-9 N=4,P=9 a dos fallos:

R(4,9,2)=9^4/(1+4*8+(1/2)*4*3*64)=6561/417=15,7. Lee la hace por 27 y no parece que esté mal del todo.

Por último la reducida 5-5-5-5-5-5 la hago, siguiendo el mismo método descrito anteriormente por 625.

R(6,5,1)=6^5/(1+6*4)=15625/(1+24)=625. Imposible de mejorar, dado que es perfecta.

La matríz de redución, aplicando la regla 1 y 2 explicadas anteriormente es:

|11111|
|01234|

Saludos.
Avatar de Usuario
lee_bran
12
12
Mensajes: 1379
Registrado: Vie 09 Dic, 2005 5:18 pm
Contactar:

Mensaje por lee_bran »

Fortuna, cuando dije mínimas teóricas no me refería a las que se pueden sacar con el binomio de Newton, sino mas bien a las que aparecen en las tablas que te acabo de enviar al correo. Tal vez he utilizado un término poco "afortunado" al decir teóricas y debí decir prácticas o exactas.

Se supone que mediante otros métodos se han ampliado esos mínimos teóricos y mediante búsquedas o generaciones se han conseguido igualar. Pues las que yo he sacado coinciden exactamente con esos mínimos posibles. No es posible obtener mejores reducciones para esas combinaciones, dado que no son perfectas.
Avatar de Usuario
JoanD
12
12
Mensajes: 2657
Registrado: Vie 19 Dic, 2003 6:35 pm
Ubicación: Barcelona
Contactar:

Mensaje por JoanD »

Introducción
Se trata de encontrar las reducciones perfectas que puedan existir en combinaciones formadas por dobles y triples sin condicionar y a 1 fallo .

Puede que no existan pero he aquí un intento por encontrarlas.

Reducciones perfectas

¿Existe la reducción perfecta en combinaciones formadas por dobles y triples?

Veamos. El desarrollo integral de una combinación formada por d dobles y t triples consta de 2^d * 3^t columnas.

Cada columna se cubre a sí misma y a d+2*t columnas, luego para que la reducción fuera perfecta debería cumplirse :

Código: Seleccionar todo

2^d * 3^t
----------- = entero
1+d+2*t

El valor de <entero> se conoce como cota de Hamming la cual indica el valor máximo de columnas que pueden existir a una distancia igual o mayor a la distancia de Hamming. Con mas columnas habría solapamiento y con menos no se podría cubrir el 100%.

Para que <entero> se verifique el denominador tiene que poderse expresar como:

Código: Seleccionar todo

2^n*3^m 
siendo n<= d y m<= t

En la siguiente tabla se indica la cota de Haming para cualquier combinación de dobles y triples. Puede verse, en color verde, las combinaciones cuya cota de Hamming es un numero entero.

Imagen

Elección de la parte independiente

El desarrollo sin reducir de la parte independiente debe constar de un numero de columnas igual a la cota de Hamming. Por lo tanto para que exista una reducción perfecta hay que elegir un conjunto de dobles y triples cuyo desarrollo integral coincida con la cota de Hamming.

Veamos el caso mas sencillo formado por 3 dobles + 1 triple, la cota de Hamming és 4, luego la parte independiente estará formada por el desarrollo integral de 2 dobles que justamente son 4 columnas. Si hubiéramos elegido 1 triple + 1 doble su desarrollo (6 columnas) estaría por encima de la cota de Hamming y no seria posible alcanzar la reducción perfecta. Tampoco valdría 1 triple ya que estaríamos por debajo de la cota de Hamming y no alcanzaríamos la reducción al 100%.

Veamos el caso de 3 dobles + 2 triples, la cota de Hamming se sitúa, según nos indica la tabla, en el valor 9, luego la parte independiente no puede estar formada por los 3 dobles ya que sólo alcanza el valor 8, sin embargo con los 2 triples se alcanza exactamente la cota deseada (9).

Siempre es posible encontrar una parte independiente que coincida con la cota de Hamming. El numero de dobles de la parte independiente (di) y el numero de triples a usar en la parte independiente (ti) es tal que debe cumplir:

Código: Seleccionar todo

1+d+2*t = 2^di*3^ti
Para los casos indicados en la tabla anterior la parte independiente estaría formado por el numero de dobles y triples que se indica en la siguiente tabla:

Imagen
Última edición por JoanD el Sab 04 Mar, 2006 9:48 pm, editado 3 veces en total.
Saludos

https://www.quinielista.es/dnp1x2/joand/
Peña agrupada en la "Piedra_Filosofal"
Responder