Mathematical Circles - Days in a month

I chanced across a problem in the book "Mathematical Circles" which I felt was interesting. The problem is described below:

In a certain year there were exactly four Fridays and exactly four
Mondays in January. On what day of the week did the 20th of January fall that
year?

On first look, it looks like a regular high school math question that I would use trial and error to solve. But, is there a more elegant way to deduce the solution?

The suggested solution, which I thought was pretty clever:

  1. Notice that January always has 31 days.
  2. Observe that days 1, 8, 15, 22 and 29 of the month are always the same day in a week since they vary by exactly 1 week/7 days. By the same reasoning, 2, 9 ... 30 and 3, 10 ... 31 are also the same days in a week.
  3. The particular month of January that is described in the problem statement cannot start with Monday, Wednesday, Thursday, Friday, Saturday or Sunday. Otherwise, there would be 5 Mondays or Fridays (we can infer this from point 2). Thus, the only plausible day is Tuesday.
  4. Since January 1 is Tuesday, it is easy to calculate that January 20 is Sunday.
Pretty astute observations and deductions!

Comments

Post a Comment

Popular posts from this blog

USACO - Broken Necklace

I recently completed a mathematical problem "Broken Necklace" on USACO . The abridged problem statement is described below: We have a necklace that contains n  (3 <=  n  <= 350) beads of 3 colors: red ( r ), blue ( b ) and white ( w ). If we break the necklace at some position i , the necklace will clearly have 2 end points x  and y . Starting from each of the end points, we can collect similarly colored  consecutive  beads from each end point (e.g. blue from one end, red from the other) until we reach a bead of a different color. The only exception is, white beads can take on any color. Example: Initially, we have this necklace (sorry for the bad formatting): x y   r b b r r      b r      r r      r b     r b     b b     b b     b r      r b     r b     r r      r  r  b  r We break it at the point between x and y, obtaining the following configuration:                                                  x   brbrrrbbbrrrrr
Keep reading

HackerRank - Search in a 2-D grid

Image
Today, I managed to complete HackerRank 's Grid Search albeit with a little difficulty. In a nutshell, the problem requires us to find a 2-D rectangular pattern in a 2-D rectangular grid. All contents of the pattern and the grid are digits from 0-9. For example: The given grid is: 1 2 3 4 5 6 7 8 9 0 0 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 The given pattern is: 8 7 6 5 4 3 1 1 1 1 1 1 1 1 1 1 1 1 It is not difficult to tell that the pattern exists in the center of the grid (highlighted in red): 1 2 3 4 5 6 7 8 9 0 0 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 The grid's dimensions can be at most 1000 * 1000 and the pattern can be at most as large as the grid itself. Problem source: here What would be your algorithm to solve this problem? On first thought, the naive solution should come to mind: brute-force matching. For every cell in the g
Keep reading

Efficient learning in Competitive Programming

Many competitive programmers (myself included) often face difficult problems that we cannot solve for days on end. This is normal because no one knows everything. But I feel that spending many hours trying to crack a single problem is a waste of time and stems learning. If we cannot solve a particular problem, it could probably be due to the lack of one or more specific skills and/or concepts. For example, how would a beginner programmer know how to use dynamic programming? He or she would not even know that the question requires dynamic programming. As a former beginner, I can emphatize with those sentiments. When I first embarked on my Competitive Programming journey, I could spend an entire day working on a single problem, which turned out to be very trivial after using a few simple tricks. As such, it is imperative to read editorials and other AC (accepted) solutions rather than trying to "challenge ourselves". Learning from others will help prevent us from reinventin
Keep reading