November 22, 2020
If you haven't done so already, I highly recommend my readers to check out a gem that I have found recently on the wild expanse of the World Wide Web: FiveThirtyEight Riddler. The Riddler is a FiveThirtyEight column maintained by a math educator and entrepreneur named Zach Wissner-Gross who publishes a set of curious math puzzles each week. Those puzzles, in my opinion, are interesting and thought-provoking, and for someone like me whose entire motivation for a blog is to invoke a call to action for critical thinking, I could not have come across more apt contents than to share my way of digging through some of those puzzles. I solved my first Riddler puzzle last week, which was the issue of November 13, 2020, and for this week, I decided, for the first time ever, to present my solution on this blog, and thus began "Riddler 1".
(Disclaimer: each week the puzzles are published on the Friday, and the deadline to submit the solution is by Monday at 11:59pm EST. Therefore, if I do post solutions as part of my blog for the puzzles that week, I will NOT actively publicize the blog until the following Tuesday. If you happen to come across my blog before then, out of courtesy of other puzzle solvers, please also do not share until then! Thanks!)
Date published: Friday, November 20, 2020
Please do not share until: Tuesday, November 24, 2020
Friggatriskaidekaphobia is a fear that affects millions around the globe based on it. Apartment buildings skip THAT floor number. Even a horror movie franchise is named after it. Yes, I am talking about Friday the 13th. In the November 20th issue of the Riddler Express, Zach Wissner-Gross published an unfortunate puzzle that asks a very interesting and perhaps a tad morbid question: What is the greatest number of Friday the 13th (Hereby shortened to "Fr13") that can occur in four consecutive calendar years?. For extra credit, if the calendar year does not have to start on Jan 1st, then for any arbitrary calendar year, what is the greatest number of Fr13s that can occur in four consecutive years?
(Original link here).
When I saw this question, the first thing I did was to grab a calendar and starts counting and finding patterns. Then it dawned on me--if I know how many days there are in a calendar year (365 for common and 366 for leap), and I fix the occurrence of any particular date to be on a specific day of the week, say Jan 1st falling on a Sunday, then I know exactly how many Fr13s there will be in that year. If I also know the year, then I know exactly the calendars for the next three years as well, and so by fixing one date, I get a deterministic answer!
This led me to think about using brute-force. I know, the term "brute-force", given the use of the word "brute", draws forth negative connotations about the method. After all, instead of "elegantly" solving a math problem, "brute-force" is taking the longest path to arrive at the answer. However, one nice thing about brute-force is that there are no tricks--once you arrive at the answer, you arrive at the answer because you've searched through ALL possibilities in an exhaustive manner (hence another word for "brute-force" is "exhaustive search"). Given the fact that we live in the age of computers, brute-force is becoming less and less likely the worst method. If the given problem's search space is small enough, and the nature of the problem simply boils down to arithmetic, then there is no reason not to let computer do something that can be much more efficient than if done by its human counterpart. Indeed, for this problem, both the original puzzle and the extra credit have small enough search spaces that brute-force is practical, and it works in getting the correct answers.
First, I am assuming that we are using the Gregorian calendar. The Gregorian calendar is an improvement to the Julian calendar in dividing the calendar year into months that best approximates Earth's orbit around the sun, which is roughly 365.2422 days. Like the Julian calendar, there is a leap year every 4 years, when a year is divisible by 4, where an extra "leap day" is added to the end of February (i.e. Feb 29th). However, unlike the Julian calendar, when a year ends in "00", the whole year has to be divisible by 400 in order for it to be a leap year in the Gregorian version. So for example, the years 1800 and 1900 were NOT leap years. The year 2000 is a leap year, and 2100 will once again be a common year. With a mean calendar year of 365.2425 days, the Gregorian calendar will be out of sync with Earth's orbit by one day every 3030 years! We would eventually need to correct for that around the year 3500, but until then, I think we've got bigger problems to worry about.
Alright, so let's focus on the original puzzle. Here we are assuming that the calendar year starts on Jan 1st and ends on December 31st, and that if we fix, say Jan 13th, to be a particular day of the year, then given the fixed number of days in that year, we would know, deterministically, how many Fr13s there are in that year, and the three years that follows depending on where we insert the leap year, if there is one. Denoting "C" as a common year and "L" as a leap year, we have the following cases for a four-year cycle:
Wait, "CCCC"? Yes, remember, in the Gregorian calendar, there will be years that are divisible by 4 that are not leap years, such as 1900. Therefore, say from 1899-1903, all four years included here are common years.
So, we are going to fix a day of the week for Jan 13, the earliest possible Fr13 appearance in a calendar year. Since there are seven days of the week, there will be \(5 \times 7 = 35\) different cases to consider. Therefore, our search space is 35 cases big. Nothing a computer in the 21st century can't handle!
I am going to use Matlab to construct the brute-force search program, whereby for each of the 35 cases, I am going to count the number of Fr13 occurrences and retrieve the greatest one. I start off by defining a calculation function to get the day of the week for the 13th of the next month given the day fell by the 13th of the current month, as follows:
function newDayOfTheWeek = getDaysAdvanced(curMonthDays, oldDayOfTheWeek)
% Given the number of days of the current month, get the number of days
% advanced ahead in the next month for each same day of the two months,
% and return the new day of the week from the old one.
% For example: if the input is (31, 2), meaning that the current month has
% 31 days (say October), and a particular day in mind (say Oct 13)
% falls on the Tuesday (second arg being 2), then the function would
% return the new day of the week in the following months (i.e. Nov 13
% for this case).
% Days of the week mapping:
% 0 -- Sunday
% 1 -- Monday
% 2 -- Tuesday
% 3 -- Wednesday
% 4 -- Thursday
% 5 -- Friday
% 6 -- Saturday
daysAdvanced = mod(curMonthDays, 7);
newDayOfTheWeek = mod(oldDayOfTheWeek + daysAdvanced, 7);
end
The math is pretty simple. For example, going from Jan 13 to Feb 13 is a period of 31 days, which is the number of days in January (13 is less than 29 so we don't have to worry about skipping months). Therefore, the number of days advanced for Feb 13 is mod(31, 7) = 3. So if Jan 13 is a Monday, Feb 13 would be a Thursday, three days advanced. Of course, if Jan 13 is, say, a Saturday, then Feb 13 cannot be on a ninth day since there are only seven in a week, so we wrap around via mod(oldDayOfTheWeek + daysAdvanced, 7) to get our final answer.
Once we got our date calculations, it's time to construct our four year calendar. As aforementioned, there are five cases to be considered depending on that pesky leap year. Those cases are considered below:
function daysVector = getCalendarFourYears(type)
% This function returns the vector of days in the 48 months of a four
% year calendar span, depending on the span type. For the Gregorian
% Calendar, five types are possible. We denote C as a common
% (non-leap) year and L as a leap year.
% CCCL, CCLC, CLCC, LCCC, CCCC
% Please note that the last CCCC case is possible because years like
% 1900 is NOT a leap year.
commonYearVec = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
leapYearVec = commonYearVec;
leapYearVec(2) = 29;
switch type
case 'CCCL'
daysVector = [commonYearVec, commonYearVec, commonYearVec, leapYearVec];
case 'CCLC'
daysVector = [commonYearVec, commonYearVec, leapYearVec, commonYearVec];
case 'CLCC'
daysVector = [commonYearVec, leapYearVec, commonYearVec, commonYearVec];
case 'LCCC'
daysVector = [leapYearVec, commonYearVec, commonYearVec, commonYearVec];
case 'CCCC'
daysVector = [commonYearVec, commonYearVec, commonYearVec, commonYearVec];
otherwise
error('Invalid type!');
end
end
Once we have our 48 month calendar for all scenarios, along with the date calculator, we can go ahead and count our Fr13s!
function numFr13 = countFr13(type, startDayFr13, varargin)
% This function counts the occurrence of Friday the 13th for one of the
% following valid types:
% CCCL, CCLC, CLCC, LCCC, CCCC
% and given the day of the week that Jan 13 of the first of the four
% years falls under.
% Days of the week mapping:
% 0 -- Sunday
% 1 -- Monday
% 2 -- Tuesday
% 3 -- Wednesday
% 4 -- Thursday
% 5 -- Friday
% 6 -- Saturday
% Please note that the CCCC case is possible because years like
% 1900 is NOT a leap year.
% Varargin if we are in an extended mode, and the first argument is the
% start month (for arbitrary four year windows).
if ~isempty(varargin)
startMonth = varargin{1};
daysVector = getCalendarFourYearsExtended(type, startMonth);
else
daysVector = getCalendarFourYears(type);
end
numFr13 = 0;
if startDayFr13 == 5
numFr13 = 1;
end
% Please note: we don't need the number of days of the December of the
% fourth year.
oldDayOfTheWeek = startDayFr13;
for k = 1:length(daysVector)-1
curMonthDays = daysVector(k);
newDayOfTheWeek = getDaysAdvanced(curMonthDays, oldDayOfTheWeek);
if newDayOfTheWeek == 5
% We got a Fr13!
numFr13 = numFr13 + 1;
end
oldDayOfTheWeek = newDayOfTheWeek;
end
end
The above Fr13 counter takes in the calendar type (e.g. "CCCL") and the starting day of the week, i.e. the day of the week for Jan 13 of the first year, and count the occurrences of Fr13 in a four year calendar period. I gave my next section away a little bit with the "getCalendarFourYearsExtended" function call which will tie into the extra credit, but more on that later. For now, just using the Fr13 counter to solve the original problem, we have the following script:
% This is the counter for the occurrence of Friday the 13th in a four-year
% Gregorian Calendar span, with each calendar year beginning on Jan 1 and
% ending on Dec 31.
clear;
close all;
clc;
%% Beginning of script
types = {
'CCCL';
'CCLC';
'CLCC';
'LCCC';
'CCCC';
};
for j = 1:length(types)
type = types{j};
maxFr13 = 0;
maxStartDay = -1;
for startDay = 0:6
numFr13 = countFr13(type, startDay);
if numFr13 > maxFr13
maxFr13 = numFr13;
maxStartDay = startDay;
end
end
fprintf('For case %s, the most Fr13 occurring is: %d when Jan 13th of the first year falls on a %s.\n',...
type, maxFr13, weekToStr(maxStartDay));
end
We run the script, and lo and behold, we obtain the following interesting result:
For case CCCL, the most Fr13 occurring is: 8 when Jan 13th of the first year falls on a Tuesday. For case CCLC, the most Fr13 occurring is: 8 when Jan 13th of the first year falls on a Friday. For case CLCC, the most Fr13 occurring is: 8 when Jan 13th of the first year falls on a Tuesday. For case LCCC, the most Fr13 occurring is: 9 when Jan 13th of the first year falls on a Friday. For case CCCC, the most Fr13 occurring is: 8 when Jan 13th of the first year falls on a Saturday.
So the answer we are looking for is 9. That is, the greatest number of Fr13s in a four-year period starting on Jan 1st of year one is 9, if that Jan 13th falls on a Friday. The most recent occurrence is in 2012. That is, from Jan 2012 to Dec 2015, we had 9 Fr13s in that four-year period. The previous time before that? From Jan 1984 to Dec 1987. The next time? From Jan 2040 to Dec 2043!
Now the extra credit poses: if the calendar year is to be arbitrary, that is, if it can start on any day of the year, then what is the greatest number of Fr13s that can occur in a four-year period? If we are being naive there, we would have way too many cases to consider, but the previous exercise did give us a lower bound: we cannot do worse than 9. The question is, can we do better than 9? After all, as Zach mentioned, we can have up to 3 Fr13s in a calendar year. Therefore, our upper bound is 12 while our lower bound is 9. Can we get 10? 11? Even 12, if we don't restrict the year to start on Jan 1st?
When I start thinking about the extra credit puzzle, I wanted to draw some equivalences. The first question I asked myself is that does it make a difference if we start on any day? Or would things be the same if I started on the 13th of a particular month? Remember, in my previous brute-force program, I only mentioned starting on the 13th of January as a way to conveniently describe the program. However, the program itself doesn't care which day the calendar started on, just the month (as defined by the "daysVector" variable). Indeed, this is correct, because there is one and only one 13th day in any given month, and so going from 13th of one month to the next will not skip any months in between. Therefore, we only need to consider which month we start.
Furthermore, I looked closer at why the LCCC case produced 9 Fr13s for Jan 13th of year one falling on a Friday, and after looking at a calendar for far too long, I've realized several "equivalencies" in the Gregorian calendar. Here they are:
A group of months are either "in" or "out". So, if say we get a Fr13 on June of a calendar year beginning on Jan 1st, then that would be the ONLY Fr13 in that year because June is "out" as far as month "equivalencies" go since it does not appear in the above list of equivalencies. On the other hand, how do we get three Fr13s in a calendar year beginning on Jan 1st? We get Jan 13th on a Friday for a leap year. Similarly, if we get Feb 13th to fall on a Friday in a common year, it's another scenario for three Fr13s in a calendar year. How (un)lucky!
There are also "cross-year" equivalencies such as Dec-Jun (next year if it's common) or Jun-Feb (next year regardless of common or leap), which will come handy in the extra credit puzzle, but please understand that in the original puzzle, how we got 9 Fr13s in a four-year period is through a passage way beginning on a leap year with Jan 13th being a Friday. This kicked off a "chain reaction": Jan-Apr-Jul, followed by Sep of year 2 (coincidentally the longest period one can go without a Fr13, which is 14 months). This is followed by Dec of the same year since Sep-Dec is an equivalency pair. If you are keeping count, that is 5 Fr13s so far. Next, heading to year three we've got only 1 Fr13 that year which is in June by the Dec-Jun "cross-year" equivalency pair since year three is a common year. This triggered the Feb 13th of the following year, also a common year, to fall on a Friday, therefore giving 3 Fr13s in year four thanks to the Feb-Mar-Nov trio.
This helps to gain some insight into the answer we would expect for the extra credit puzzle. The passage way to getting the greatest number of Fr13s seems to go thorough Jan-Apr-Jul-Sep (of next year)-Dec-Jun-Feb-Mar-Nov. It seemed that any other passageway would obtain less than 9 Fr13s in any four-year period. There seems to be no passageway to obtain 10 or greater Fr13s. However, let's see if we can put brute-force into use here and verify my hypothesis.
Let's analyze the cases here. Since we only care about the month we are starting, that gives us 12 scenarios. For the sequence of years, we must be careful with the "CCCC" case since now the spillover year could either be common (e.g. 1898-1903) or leap (e.g. 1899 to 1904). We would denote this nuanced difference via "CCCCC" and "CCCCL", respectively. We have the similar case for the spillover year in an LCCC case. for all other cases, the spillover year is deterministic to be a common year since we cannot have two leap years less than four years apart. Therefore, to summarize, below are our sequencing cases:
Again, similar to the original puzzle case, whatever month we start, we are going to consider all days of the week that the 13th of that month falls. Therefore, in summary, we have \(12 \times 7 \times 7 = 588\) different cases. A lot more than 35 for sure, but still nothing computers in the 21st century can't handle. So our search space is still small enough to use brute-force!
The only thing different from the original program is the use of the "getCalendarFourYearsExtended" instead of the "getCalendarFourYears" function so that we can have a 48-months calendar beginning on any month. Encapsulating all of our scenarios above, I have the following function:
function daysVector = getCalendarFourYearsExtended(type, startMonth)
% This function returns the vector of days in the 48 months of a four
% year calendar span, depending on the span type. However, please note
% that here we are assuming ANY four year period (e.g. Feb 2014 to Feb
% 2018 or July 1899 to July 1903).
% Note: For the Gregorian Calendar, five types are possible. We denote
% C as a common (non-leap) year and L as a leap year. CCCL, CCLC, CLCC,
% (LCCCL, LCCCC) (CCCCL, CCCCC)
% Please note that the last CCCC case is possible because years like
% 1900 is NOT a leap year.
% The last two cases indicate whether we would have the spillover year
% as a leap year or a common year, respectively.
commonYearVec = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
leapYearVec = commonYearVec;
leapYearVec(2) = 29;
switch type
case 'CCCL'
firstYear = commonYearVec(startMonth:end);
% Spillover year is a common year
spillOverYear = commonYearVec(1:startMonth - 1);
daysVector = [firstYear, commonYearVec, commonYearVec, leapYearVec, spillOverYear];
case 'CCLC'
firstYear = commonYearVec(startMonth:end);
% Spillover year is a common year
spillOverYear = commonYearVec(1:startMonth - 1);
daysVector = [firstYear, commonYearVec, leapYearVec, commonYearVec, spillOverYear];
case 'CLCC'
firstYear = commonYearVec(startMonth:end);
% Spillover year is a common year
spillOverYear = commonYearVec(1:startMonth - 1);
daysVector = [firstYear, leapYearVec, commonYearVec, commonYearVec, spillOverYear];
case 'LCCCL'
% Here the first year, as defined, is a leap year
firstYear = leapYearVec(startMonth:end);
% Spillover year is a leap year
spillOverYear = leapYearVec(1:startMonth - 1);
daysVector = [firstYear, commonYearVec, commonYearVec, commonYearVec, spillOverYear];
case 'LCCCC'
% Here the first year, as defined, is a leap year
firstYear = leapYearVec(startMonth:end);
% Spillover year is a common year (e.g. 1896 to 1900).
spillOverYear = commonYearVec(1:startMonth - 1);
daysVector = [firstYear, commonYearVec, commonYearVec, commonYearVec, spillOverYear];
case 'CCCCC'
firstYear = commonYearVec(startMonth:end);
% Spillover year is a common year
spillOverYear = commonYearVec(1:startMonth - 1);
daysVector = [firstYear, commonYearVec, commonYearVec, commonYearVec, spillOverYear];
case 'CCCCL'
firstYear = commonYearVec(startMonth:end);
% Spillover year is a leap year
spillOverYear = leapYearVec(1:startMonth - 1);
daysVector = [firstYear, commonYearVec, commonYearVec, commonYearVec, spillOverYear];
otherwise
error('Invalid type!');
end
end
The first year starts at the specified month and runs to the end of the year, and the spillover year starts on month 1 and goes to the month right before the specified start month, to complete our four-year arbitrary calendar.
Then we just run our script:
% This is the counter for the occurrence of Friday the 13th in a four-year
% Gregorian Calendar span, with each calendar year beginning on the 1st of
% any arbitrary month and ending on the last day of the previous month of
% the fourth year.
clear;
close all;
clc;
%% Beginning of script
types = {
'CCCL';
'CCLC';
'CLCC';
'LCCCL';
'LCCCC';
'CCCCL';
'CCCCC';
};
for j = 1:length(types)
type = types{j};
maxStartMonth = -1;
maxFr13 = 0;
maxStartDay = -1;
for startMonth = 1:12
maxFr13Temp = 0;
maxStartDayTemp = -1;
for startDay = 0:6
numFr13 = countFr13(type, startDay, startMonth);
if numFr13 > maxFr13Temp
maxFr13Temp = numFr13;
maxStartDayTemp = startDay;
end
end
if maxFr13 < maxFr13Temp
maxFr13 = maxFr13Temp;
maxStartMonth = startMonth;
maxStartDay = maxStartDayTemp;
end
end
fprintf('For case %s, the most Fr13 occurring is: %d when we start on the 13th of %s that falls on a %s.\n',...
type, maxFr13, monthToStr(maxStartMonth), weekToStr(maxStartDay));
end
And here is our result:
For case CCCL, the most Fr13 occurring is: 8 when we start on the 13th of January that falls on a Tuesday. For case CCLC, the most Fr13 occurring is: 8 when we start on the 13th of January that falls on a Friday. For case CLCC, the most Fr13 occurring is: 9 when we start on the 13th of April that falls on a Wednesday. For case LCCCL, the most Fr13 occurring is: 9 when we start on the 13th of January that falls on a Friday. For case LCCCC, the most Fr13 occurring is: 9 when we start on the 13th of January that falls on a Friday. For case CCCCL, the most Fr13 occurring is: 8 when we start on the 13th of January that falls on a Saturday. For case CCCCC, the most Fr13 occurring is: 8 when we start on the 13th of January that falls on a Saturday.
Therefore, the answer to the extra credit puzzle is still 9, in that even if we considered any four-year period, the number of Fr13s in that period would still be 9. However, we now have some options. We still get 9 Fr13s in the LCCC cases, of course, but if we have a CLCC(C) case where the first year starts on an April, and April 13 falls on a Wednesday, then we would obtain 9 Fr13s as well. The passageway to do so is as follows: May-Jan-Apr-Jul-Sep (of next year)-Dec-Jun-Feb-Mar. Here both February and March of the last parts of the sequence fall on a spillover year that is a common year. A challenge to my readers: there is also a passageway to 9 Fr13s if we start a calendar year on a December. Can you figure out which case that would be?
One takeaway from this exercise: brute-force isn't always bad. You just got to know when it's elegant to use it!
Please find the Code Files here.