7 votos

Jessica el estudiante combinatoria, parte 2

La pregunta original sobre Jessica, que me anime a revisar, es el siguiente:

Jessica es el estudio de la combinatoria durante una $7$-periodo de la semana. Ella va a estudiar un número entero positivo de horas cada día durante la $7$ semanas (así, por ejemplo, no estudiar para $0$ o $1.5$ horas), pero ella no estudiar más de $11$ horas $7$días de duración. Demostrar que no debe existir un período de días consecutivos durante el cual Jessica estudios exactamente $20$ horas.

Mi pregunta es esta:

Cuán lejos en el curso (número de días) ¿necesita antes de que usted puede estar seguro de que Jessica ha tenido alguna secuencia de días consecutivos con una veintena de horas de estudio total?

Mi sospecha es que la respuesta es: veinte días. Creo que mi respuesta a la pregunta original se puede utilizar para demostrar que cuatro semanas es sin duda suficiente

6voto

NP-hard Puntos 1872

La prueba consta de dos partes.

  • Parte I: Probar que un período de $20$ días es suficiente de tal manera que debe existir un período de días consecutivos durante el cual totalmente $20$ horas se emplean en el estudio.

  • Parte II: UN contraejemplo, que muestra que las $19$ días no son suficientes se presenta.


La prueba de la Parte I

Vamos $x_1$, $x_2$, $\cdots$, $x_{20} \in \mathbb{N}^+$ indicar el nº de horas dedicadas a estudiar para cada día. Además, puso $$ f(i) = x_1 + x_2 + \cdots + x_i\quad\text{para}\quad 1 \leq i \leq 20 $$ para indicar el número total de horas dedicadas a estudiar antes y en el día $i$. Especialmente, $f(0) = 0$. Es fácil observar que $$ f(0) < f(1) < \cdots < f(20) $$ Vamos $$ A = \{f(0) + 20,\ f(1) + 20,\ \cdots,\ f(11) + 20\} $$ y $$ B = \{f(12),\ f(13),\ \cdots,\ f(20)\} $$

  • Porque $$ f(11) = \color{red}{x_1 + \cdots + x_7} + \color{blue}{x_8 + x_9 + x_{10} + x_{11}} \leq \color{red}{11} + \color{blue}{11 - 3} = 19 $$ tenemos $$ A \subseteq \{f(11) + 1,\ f(11) + 2,\ \cdots,\ f(11) + 20\} \etiqueta{1} $$

  • Porque $$ f(20) = f(11) + \color{red}{x_{12} + \cdots + x_{18}} + \color{blue}{x_{19} + x_{20}} \leq f(11) + \color{red}{11} + \color{blue}{11 - 5} = f(11) + 17 $$ y $$ f(12) = f(11) + x_{12} \geq f(11) + 1 $$ así $$ B \subseteq \{f(11) + 1,\ f(11) + 2,\ \cdots,\ f(11) + 17\} \etiqueta{2} $$

Hay un total $|A| + |B| = 21$ a los valores, sino sólo $20$ ranuras, es decir,$f(11) + 1,\ \cdots,\ f(11) + 20$, existen por $(1)$$(2)$. Por lo tanto, algunos $f(i) + 20 \in A$ $f(j) \in B$ debe ser igual. Es decir, $$f(i) + 20 = f(j)$$

$$\tag*{$\blacksquare$}$$


La prueba de la Parte II

El contraejemplo es fácil: Dejar que el # de horas que se dedican a estudiar todos los días se $1$.

$$\tag*{$\blacksquare$}$$



Cuando el límite es de $12$.

Esta parte contiene una prueba para el caso cuando el límite es de $12$ en lugar de $11$.

En este caso, vamos a lugar $$ A = \{f(0) + 20,\ f(1) + 20,\ \cdots,\ f(10) + 20\} $$ y $$ B = \{f(10),\ f(11),\ \cdots,\ f(20)\} $$ Porque $$ f(10) = \color{red}{x_1 + \cdots + x_7} + \color{blue}{x_8 + x_9 + x_{10}} \leq \color{red}{12} + \color{blue}{12 - 4} = 20 $$ y $$ f(20) = f(10) + \color{red}{x_{11} + \cdots + x_{17}} + \color{blue}{x_{18} + x_{19} + x_{20}} \leq f(10) + \color{red}{12} + \color{blue}{12 - 4} = f(10) + 20 $$ tenemos $$ A \subseteq \{f(10),\ f(10) + 1,\ \cdots,\ f(10) + 20\} $$ y $$ B \subseteq \{f(10),\ f(10) + 1,\ \cdots,\ f(10) + 20\} $$ De un modo tan total $|A| + |B| = 22$ elementos y $21$ ranuras. Así el principio del Palomar se aplica.

5voto

JiminyCricket Puntos 143

Aquí está el código para ejecutar una búsqueda exhaustiva, en la que se confirma su sospecha de que la respuesta es $20$ días.

Curiosamente, todavía es $20$ días si Jessica se les permite trabajar hasta a $14$ horas $7$días de duración. Si ella está permitido trabajar $15$ horas, un patrón que se repite de $5,1,1,1,5,1,1,1,\ldots$ evita cualquier suma de $20$ para cualquier número de días.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X