Nota: Este es un comentario extendido, no es una respuesta completa.
Yo no sé ustedes, pero yo no empecé con cualquier buena intuición sobre la respuesta a la pregunta. Me decidí a hacer algunos experimentos informáticos y de visualización.
Escribí el código en Prolog que genera plaza libre y tres mitades libre de palabras sobre un alfabeto. Yo normalmente no uso de Prolog para nada, pero este parecía el tipo de problema que es muy adecuado para. Código fuente y un entorno interactivo está disponible aquí. (Por favor comente si no funciona, el enlace está muerto, etc.) Por favor experimento en su propio demasiado!
La consulta siguiente genera el tres mitades libre de palabras de longitud 5 sobre el alfabeto x,y. En el código que yo he llamado "sándwich " libre" en lugar de "tres mitades-gratis".
?- sandwich_free(L,[x,y],5).
L = [x, y, y, x, x] ;
L = [x, x, y, y, x] ;
L = [y, y, x, x, y] ;
L = [y, x, x, y, y] ;
false.
"?-" es el símbolo del sistema; las cuatro líneas siguientes son los resultados, y "false" indica que no hay más respuestas. (El orden de los resultados es lexicográfica, si usted lee cada resultado de derecha a izquierda.)
Si usted pide el sandwich libre de palabras de longitud 6 sobre el mismo alfabeto, se obtiene 0 resultados:
?- sandwich_free(L,[x,y],6).
false.
He aquí un sándwich libre de palabra de longitud de 500 de más de un 3 letras del alfabeto:
?- sandwich_free(L,[x,y,z],500).
L = [y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, y, x, x, z, z, x, y, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, z, x, x, y, y, x, z, y, x, x, y, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x, z, z, x, y, z, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, y, y, x, x, z, y, y, x, x, y, z, x, y, z, x, x, z, z, y, y, x, x, y, z, x, y, y, x, x, z, y, y, x, x, z, y, y, x, x, y, z, x, y, y, x, x]
...
Usted puede pedir el sándwich libre de palabras de cualquier longitud a través de un determinado alfabeto:
?- sandwich_free_peano(L,[x,y],N).
L = [],
N = zero ;
L = [x],
N = s(zero) ;
L = [y],
N = s(zero) ;
L = [x, x],
N = s(s(zero)) ;
L = [y, x],
N = s(s(zero)) ;
L = [x, y],
N = s(s(zero)) ;
L = [y, y],
N = s(s(zero)) ;
L = [y, x, x],
N = s(s(s(zero)))
...
(Limitaciones técnicas en Prolog me obligó a escribir una versión independiente de sandwich_free
el uso de Peano de los números, cuando estás pasando en un número no ya crear una instancia como una constante.)
También se puede utilizar para comprobar si una determinada lista de sándwich-libre:
?- sandwich_free_peano([x,y,z,z,y],[x,y,z],_).
true ;
false.
(La respuesta es verdadero; falso sólo indica que no hay más respuestas.)
Aquí está una parcela de largo vs el número de metros libre y sandwich libre de palabras de longitud de más de un 3-letra del alfabeto. El crecimiento parece ser exponencial:
La consulta que genera los puntos de datos se
?- numlist(0,23,L),maplist(how_many_sandwich_free_alphabet_3,L,XS).
Los puntos de datos en el gráfico son:
- Plaza libre: 1, 3, 6, 12, 18, 30, 42, 60, 78, 108, 144, 204, 264,
342, 456, 618, 798, 1044, 1392, 1830, 2388, 3180, 4146, 5418 (OEIS A006156)
- Sándwich gratis: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008,
1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428,
86688, 128592 (no en la OEIS en este momento)
Esto me parece una evidencia convincente de que hay arbitrariamente largo, de tres mitades libre de palabras, de hecho exponencialmente muchos como una función de la longitud. También parece muy probable que infinitamente largo, de tres mitades libre de palabras existen.
Editar:
Aquí algunos interesantes datos nuevos: Decir que un sándwich libre de palabra es "extensible" si usted puede agregar una letra más al frente de ella para conseguir otro sándwich-free word. La mayoría de los sándwich libre de palabras son extensibles. Un ejemplo de una que no lo es:
_, y, y, x, x, y, z, z, x, x, z, y, y, x, x
Tratar de llenar el espacio en blanco en la parte delantera.
Más en general podemos hablar de "$k$-extensible" sándwich libre de palabras, por que me refiero a "$k$-extensible, pero no $(k+1)$-extensible". Ahora aquí está una parcela de cómo muchos no extensible y 1-extensible palabras hay de particular longitudes:
(Datos: 1, 3, 9, 18, 36, 72, 108, 180, 288, 432, 648, 1008, 1548, 2376, 3636, 5400, 8172, 12276, 17892, 26532, 39492, 58428, 86688, 128592, 190512, 282492, 418680, 620208, 919044, 1362456, 2012940; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 72, 72, 144, 396, 252, 396, 720, 1044, 1440, 2376, 3456, 5040, 7524, 11088, 16272, 26604, 36864; 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36, 36, 36, 72, 108, 180, 720, 540, 468)