Existem grades de Sudoku contínuas válidas?

Question

Uma norma https://en.wikipedia.org/wiki/Sudoku é um $9\times 9$ grade preenchida com dígitos de forma que cada linha, coluna e $3\times 3$ caixa contém todos os inteiros de $1$ para $9$.

Estou pensando em uma generalização do Sudoku que chamo de "Sudoku contínuo", que consiste em um quadrado unitário onde cada ponto desse quadrado corresponde a um número real. As regras do Sudoku contínuo são projetadas para serem análogas às regras do Sudoku padrão, e desenvolvi dois conjuntos de regras diferentes:

• O primeiro conjunto de regras eu chamo de Sudoku contínuo "fraco". No Sudoku contínuo fraco, a única restrição é que cada linha e coluna do quadrado contém todos os números reais no intervalo$[0,1]$ exatamente uma vez.
• O segundo conjunto de regras eu chamo de Sudoku contínuo "forte". No Sudoku contínuo forte, aplicam-se as regras do Sudoku contínuo fraco e, além disso, cada sub-região quadrada do quadrado unitário contém todos os números reais no intervalo$[0,1]$pelo menos uma vez. Isso é análogo ao$3\times 3$ restrição de caixa no Sudoku padrão.

Deixei $U = [0,1]$ e $U^2 = U\times U$. Mais precisamente, um Sudoku contínuo fraco é essencialmente uma função$f:U^2\to U$, que satisfaz as quatro propriedades a seguir:

1. E se $x,y_1,y_2\in U$ e $y_1\neq y_2$, então $f(x,y_1)\neq f(x,y_2)$.
2. E se $x_1,x_2,y\in U$ e $x_1\neq x_2$, então $f(x_1,y)\neq f(x_2,y)$.
3. E se $x\in U$ então $\{z: f(x,y)=z,y\in U\} = U$.
4. E se $y\in U$ então $\{z: f(x,y)=z,x\in U\} = U$.

Agora, o Sudoku contínuo forte é um pouco mais difícil de definir com precisão. Um conjunto$S$é uma sub-região quadrada de$U^2$ sse $S\subseteq U^2$ e existe $z = (z_1,z_2)\in U^2$ e $r>0$ de tal modo que $S = \{(x,y)\in U^2:z_1\leq x\leq z_1+r,z_2\leq y\leq z_2+r\}$. Assim, usando esta definição, um Sudoku contínuo forte é um Sudoku contínuo fraco que satisfaz a seguinte propriedade adicional:

1. E se $S$ é uma sub-região quadrada de $U^2$, então $f(S) = U$.

Tenho tentado procurar exemplos específicos de grades contínuas fortes e fracas de Sudoku, mas não obtive sucesso.

Não tenho certeza se existe algum Sudoku contínuo fraco. Minha primeira tentativa:$$ f(x,y)=\begin{cases} x+y &\text{if }x+y\leq 1 \\ x+y-1 & \text{if }x+y>1\end{cases} $$quase funciona. Satisfaz propriedades$3$ e $4$, e quase, mas não totalmente, satisfaz $1$ e $2$. O problema ocorre apenas nos limites do quadrado, por exemplo,$f(0.5,0) = 0.5$ e $f(0.5,1)=0.5$.

Qualquer exemplo de um Sudoku contínuo forte provavelmente precisará ser uma função patológica extremamente descontínua, semelhante ao https://en.wikipedia.org/wiki/Conway_base_13_function. Obviamente, se não houver grades de Sudoku contínuas fracas, não haverá grades de Sudoku contínuas fortes. Mesmo se não houver grades de Sudoku fracas, pode ser possível modificar ligeiramente as definições para permitir pequenas exceções, como no exemplo acima.

A pergunta principal que estou perguntando é: existem grades de Sudoku contínuas fracas e, se existirem, existem grades de Sudoku contínuas fortes?

Answer 1

Sudoku contínuo fraco :

Um Sudoku contínuo fraco pode ser construído com base nas idéias que você já forneceu.

Primeiro, construímos um Sudoku contínuo fraco para o conjunto $U=(0,1]$ ao invés de $U=[0,1]$. Aqui, um Sudoku contínuo fraco pode ser construído usando a função$f$ de sua tentativa, mas como uma função $f:(0,1]^2\to (0,1]$(uma vez que um limite se foi, os problemas que você observou agora também desapareceram). Então, escolha uma bijeção$h:[0,1]\to (0,1]$(uma bijeção explícita pode ser construída se você preferir uma solução construtiva). Então nós definimos$$ g:[0,1]^2\to [0,1], \qquad (x,y)\mapsto h^{-1} (f(h(x),h(y))). $$ Esta função $g$ então pode ser mostrado como um Sudoku contínuo fraco.

Sudoku contínuo forte :

Quanto ao Sudoku contínuo forte, as coisas ficam mais complicadas e seria muito trabalhoso explicar minha construção em todos os detalhes, mas posso fornecer um esboço.

Primeiro, a bijeção $h$ acima deve ser escolhido de modo que cada intervalo em $[0,1]$ contém um subintervalo $[ a,b ]$ de tal modo que $h(x)=x$ para todos $x\in[a,b]$, veja os comentários abaixo para tal construção. Além disso, ele usa uma bijeção$j:[0,1]\to [0,1]$ de tal modo que $j((c,d))$ é denso em $[0,1]$ para todos os intervalos $(c,d)$, veja os comentários abaixo para tal construção para $j$.

Em seguida, pode-se misturar as linhas ou colunas do Sudoku fraco anterior de acordo com $j$, ie $\tilde g(x,y)=g(j(x),y)$. Esta função$\tilde g$deve então ser um forte Sudoku contínuo. Deixe-me fornecer um esboço de como isso pode ser feito.

Deixei $S$ ser uma sub-região quadrada de $[0,1]^2$. Deixei$S_2=[a,b]\times [c,d]\subset S$ ser uma sub-região quadrada menor, onde $a<b,c<d$ são tais que $h(x)=x$ vale para todos $x\in[a,b]\cup[c,d]$ (tal sub-região existe devido aos comentários acima sobre a escolha de $h$) Basta mostrar que$\tilde g(S_2)=[0,1]$ ao invés de $\tilde g(S)=[0,1]$.

Deixei $t\in [0,1]$seja dado. Deixei$m:=(c+d)/2$. Desde a$j([a,b])$ é denso em $[0,1]$, os valores da função $\{\tilde g(x,m)| x\in[a,b]\}$ também são densos em $[0,1]$. Deixei$s\in[a,b]$ seja tal que $\tilde g(s,m)$ é perto de $t$ no sentido de que $$ t-\frac{d-c}{2} < \tilde g(s,m) < t+\frac{d-c}{2}. $$ Explorando as definições de $\tilde g,g,f$ temos $\tilde g(s,m+x)=\tilde g(s,m)+x$ para $x\in (-\frac{d-c}{2},\frac{d-c}{2})$ (com a exceção de que os valores envolvem em $1$) Pela configuração$x=\tilde g(s,m)-t$, Nós temos $t=\tilde g(s,m+x)$ e $(s,m+x)\in S_2 = [a,b]\times [c,d]$. portanto$t$ pode ser alcançado e a condição (5.) para um Sudoku forte e contínuo é satisfeita.

sobre a existência de uma função $h$:

Podemos definir $h:[0,1]\to (0,1]$ pela configuração $h(0)=1/2$, $h(1/2)=1/3$, $h(1/3)=1/4$, etc., e $h(x)=x$ para todos os outros $x$. Então, para cada intervalo, pode-se encontrar um subintervalo suficientemente pequeno$[a,b]$ de tal modo que $h(x)=x$ para todos $x\in[a,b]$.

sobre a existência de uma função $j$:

Isso é mais complicado, então deixe-me fazer um esboço. Deixei$(q_k)_k$ ser uma enumeração dos números racionais em $[0,1]$ e deixar $I_k$ ser um intervalo de comprimento $2^{3-2k}$ centrado em $q_k$. Nós definimos os conjuntos$$ A_k := I_k\setminus \bigcup_{l>k} I_l.$$ Esses conjuntos formam uma partição de $[0,1]$ e cada conjunto $A_k$ tem cardinalidade igual a $[0,1]$.

Deixei $(B_k)_k$ ser outra sequência de subconjuntos de $[0,1]$ que formam uma partição de $[0,1]$ tal que cada $B_k$ é denso e tem cardinalidade igual a $[0,1]$ (tal partição existe, pode-se anexar conjuntos contáveis ​​densos com outros elementos suficientes para formar conjuntos $B_k$, mas acho que isso requer o axioma de escolha). Então nós construímos$j$ por mapeamento (bijetivamente) $A_k$ para $B_k$.

Uma vez que os comprimentos dos conjuntos $A_k$ ficam cada vez menores e os racionais $q_k$ são densos, cada intervalo tem um subintervalo da forma $I_k$. Desde a$I_k$ contém $A_k$ e $A_k$ é mapeado para um conjunto denso $B_k$, obtemos a propriedade desejada que $j(I_k)$ é denso em $[0,1]$.

Answer 2

Aqui está uma solução fraca. Usando sua bijeção favorita, substitua$[0,1]$ com o grupo Cantor $2^\mathbb N$de infinitas sequências binárias. Então deixa$f(x,y)=x+y$. Ou seja, basta usar a operação de grupo: XOR pontual.