Question

During a month with 30 days, a team will play at least one game a day but no more than 45 games in all 30 days. Show that there is a stretch of consecutive days during which the team plays exactly 14 games. (Hint: Let \(a_{i}\) be the number of games played on or before the \(i\) th day for \(1 \leq i \leq 30 .)\)

Short answer

There exists a stretch of consecutive days where the team plays exactly 14 games due to the pigeonhole principle.

Step-by-step solution

Define the Sequence

Let \(a_i\) denote the total number of games played by the team after the \(i\)-th day, where \(1 \leq i \leq 30\). Thus, \(a_1, a_2, \ldots, a_{30}\) is a strictly increasing sequence with \(1 \leq a_i \leq 45\).

Consider Shifted Sequence

Define another sequence \(b_i = a_i + 14\) for each \(1 \leq i \leq 30\). Thus, \(b_i\) denotes the number of games played by day \(i\) plus 14 more games. Hence, the sequence \(b_i\) is also strictly increasing.

Combine the Two Sequences

Combine both sequences: \(a_i\) values range from 1 to 45 and \(b_i = a_i + 14\) ranges from 15 to 59. Thus, the union of these two sequences has 60 potential values: \(a_1, a_2, \ldots, a_{30}, b_1, b_2, \ldots, b_{30}\).

Apply Pigeonhole Principle

Since the sequences \(a_i\) and \(b_i\) consist of a total of 60 values (from 1 to 59), and there are only 45 possible unique values for \(a_i\) from 1 to 45, according to the pigeonhole principle, there must be at least one overlap: \(a_i = b_j\).

Find the Overlap Meaning

If \(a_i = b_j\), this implies \(a_i = a_j + 14\), meaning the number of games played from day \(j+1\) to day \(i\) is exactly 14. Thus, there exists a stretch of consecutive days where the team plays exactly 14 games.

Key concepts

Discrete Mathematics

Discrete Mathematics is a branch of mathematics that deals with distinct and separate values or objects. These include topics like counting principles, graph theory, and combinatorics.
It's the opposite of continuous mathematics, which deals with smooth and continuous values such as calculus.
In our exercise, one of the key concepts used is the Pigeonhole Principle. The Pigeonhole Principle states that if you have more items than containers, at least one container must hold more than one item.
This concept is important in proving that a certain outcome must occur, given the constraints.
By applying it to our problem, we proved that there must be some days where exactly 14 games are played. Here’s a simple way to understand this principle:

• Imagine you have 10 pigeons and 9 pigeonholes.
• When each pigeon naturally wants its own hole, one pigeonhole will end up with two birds.

In the exercise, the concept was used to show that with 60 sequence values and only 45 unique options, overlaps are inevitable.

Consecutive Subsequence

A consecutive subsequence is a segment of a sequence where the items are in order one after another, without any interruptions.
Imagine a list like {1, 2, 3, 4, 5}; a subsequence might be {2, 3, 4}.
Within the context of our exercise, a consecutive subsequence refers to the sequence of days during which the team plays exactly 14 games. Consider this closer look:

• Each day the team plays a certain number of games, creating a running total after each day.
• Our task was to find consecutive days where this running total increases by exactly 14 during a certain stretch.

Using consecutive subsequences allows us to isolate these consecutive days within the total given range, linking it with the Pigeonhole Principle to find such a subsequence.

Strictly Increasing Sequence

A strictly increasing sequence is one where each number is greater than the one before it.There are no repetitions, and each functioning part of the sequence rises progressively.
In our exercise, both sequences \(a_i\) and \(b_i\) were strictly increasing.Why is this important?

• It helps ensure that each day, the total number of games played genuinely increases.
• Strict increase prevents any backtracking or repetition that could confuse calculations.

For example:
If we consider a sequence like \{3, 5, 7\}, it's strictly increasing;
each element is higher than the last.
This quality was crucial in combining the sequences \(a_i\) and \(b_i\) since they maintain order and allow us to apply the Pigeonhole Principle effectively.By focusing on their strict nature, we confidently identify overlaps, meaning there must be consecutive days adding up perfectly to 14 games.