Suma de $n$ vectores en $(\mathbb Z/n)^k$

Question

Dejemos que $n,k$ sean enteros positivos. ¿Cuál es el valor más pequeño de $N$ tal que para cualquier $N$ vectores (pueden repetirse) en $(\mathbb Z/(n))^k$ se puede elegir $n$ vectores cuya suma es $0$ ?

Mi opinión es $N=2^k(n-1)+1$ . Es ciertamente agudo: uno puede escoger nuestro conjunto para ser $n-1$ copias del conjunto $(a_1,...,a_k)$ con cada $a_i=0$ o $1$ . El caso $k=1$ es alguna pregunta de concurso de matemáticas (creo, pero no recuerdo la referencia exacta). ¿Alguien sabe de alguna referencia? Gracias.

---

Gracias a todos. Me gustaría poder aceptar todas las respuestas, ¡son muy útiles!

Answer 1

Para $k$ mayor que uno el valor más pequeño será igual o menor que $n^{k-1}(2n-2)+1$ . Para ver esto utilice el principio de encasillamiento para la primera $k-1$ coordenadas sólo hay $n^{k-1}$ conjuntos de valores posibles por lo que un conjunto de estas coordenadas debe tener $2n-1$ elementos podemos elegir n de ellos que tengan coordenadas $k$ suman a cero por el teorema de Erdős-Ginzburg-Ziv entonces como la primera $k-1$ las coordenadas son fijas también sumarán a cero y tendremos el conjunto deseado de vectores que suman a cero.

Para $k=2$ existe la conjetura de Kemnitz de que es $4n-3$ .

Ahora veo que esta conjetura está demostrada. Ver:

http://www.springerlink.com/content/h2w35453626952n0/ Podemos entonces aplicar el argumento del primer párrafo y obtener para $k=2$ o más el valor más pequeño debe ser menor o igual a $n^{k-2}(4n-4)+1$ .

Para que el patrón continúe el siguiente caso sería para k=3 sería $8m-7$ hay un contraejemplo de hecho para todo impar k y n mayor que 3 no es cierto. El siguiente documento fue mencionado en otra respuesta la última frase del resumen tiene el resultado general. http://www.ma.rhul.ac.uk/~elsholtz/WWW/papers/papers08harborth.pdf Hay un factor de 1,125 a la $d/3$ potencia para que haya un exponente mayor que dos como límite inferior.