Barbeque or Barbecue

[wisehacks]

Janet wish to decide on which two days of the month of July she will invite friends over for a barbeque.However, she wants to schedule the barbeques so that no 3-day period in July has more than one barbeque. How many options do if the order of the two chosen days is not relevant?

I'm not clear on this one, and I don't have the option results to guide me, so I'll do my best (and likely fail).

respuesta: show

La restricción viene a significar que tiene que haber dos días entre una barbacoa y la siguiente. El mes de Julio tiene 31 días, y la forma más fácil de abordar el problema es calcular todas las formas posibles de poner dos barbacoas en Julio, y luego todas las formas posibles de hacerlo rompiendo la restricción. Finalmente, restamos las dos opciones.

Formas de poner dos barbacoas en Julio (el orden no importa):
Formas de poner dos barbacoas rompiendo la restricción:
1. Para el primer y el último día del mes, 2 formas: A B _ _ y A _ B _
2. Para el segundo y penúltimo día del mes, 2 formas: _ A B _ _ y _ A _ B _
3. Para cualquier otro día, 2 formas: _ _ A B _ _ y _ _ A _ B (el orden no importa, por lo que B _ A _ _ es igual que _ _ A _ B).

Es decir, para cualquier día del mes, hay dos formas de colocar la otra barbacoa infringiendo la limitación. Así que, formas de poner las barbacoas violando las normas: . Restando las dos tenemos .

Pues creo que salen 403, pero esto es casi un guess.

[wisehacks]

I like how you try to count the number of choices we should throw out. However, you slightly overestimate this number!

You're right!

respuesta: show

Los últimos días del mes tienen menos opciones. Hay otra forma de verlo que pone de manifiesto la pequeña desviación. Pongamos un día del mes que no sea cercano al principio ni al final del mismo. La pinta que tendría sería tal que así:

_ _ _ B _ _ _

Ahora vamos a marcar con una X los días en los que no puede hacerse la barbacoa:

1) _ X _ B _ _ _
2) _ _ X B _ _ _
3) _ _ _ B X _ _
4) _ _ _ B _ X _

Como podemos observar, para cada día normal (i.e. no en los extremos del mes), hay 4 días prohíbidos: dos anteriores al día elegido, y dos posteriores. Sin embargo, hay que darse cuenta de que los días anteriores ya los hemos contado con anterioridad. Siguiendo con nuestro ejemplo, las dos X previas a B, han sido contadas cuando se revisaron el segundo y tercer día del mes (nótese que el orden no importa, por lo que XB es igual que BX):

1) _ _ B X _ _ _ (ésta es igual que la opción 2 arriba)
2) _ B _ X _ _ _ (ésta es igual que la opción 1 arriba)

Por lo tanto, para cada día podemos considerar que existen dos combinaciones prohíbidas: las dos construídas usando días posteriores. Sin embargo, los días del final del mes no tienen dos días posteriores. Examinamos el penúltimo y el último día:

Penúltimo) _ _ _ _ _ B _ (días prohíbidos aún no contados: 1)
.....Último) _ _ _ _ _ _ B (días prohíbidos aún no contados: 0)

Con estos datos, el número de combinaciones prohíbidas es tal que . O reescrito por simplicidad:

Formas de poner dos barbacoas en Julio (el orden no importa):

Restamos:


Soooo, unless I'm wrong again, the answer is 406.