Shrove Tuesday is a term used in several countries for the day preceding the first day of lent. I learned from Wikipedia that " The word shrove is the past tense of the English verb shrive, which means to obtain absolution for one's sins by way of Confession and doing penance. Thus Shrove Tuesday gets its name from the shriving that English Christians were expected to do prior to receiving absolution immediately before Lent begins.
Shrove Tuesday is the last day of "shrovetide", the English equivalent to the Carnival tradition that developed separately in countries of Latin Europe. The term "Shrove Tuesday" is no longer widely known in the United States outside of Liturgical Traditions, such as the Lutheran, Episcopal, and Roman Catholic Churches. [3][4] because of the increase in many immigrant populations and traditions since the 19th century. "Mardi Gras" is much more widely-used. The festival is widely associated with the eating of foods such as pancakes, and often known simply as Pancake Day, originally because these used up ingredients such as fat and eggs, the consumption of which was traditionally restricted during Lent."
I found out that some call the previous saturday, "Egg Saturday", and the monday before Shrove Tuesday is known as "Collop Monday" (A collop is chunk of meat or fat), and the cool mathword on the Sunday before is "Quinquagesima Sunday" which means the fiftieth day; Easter then, would be the first day in the string.
So here is the problem... I cooked up a bunch (call it n) of pancakes for pancake Tuesday, but the stack was not as neat as I wanted. I really wanted them to be stacked with the largest diameter on bottom and the smallest on top. I decided I wanted to restack them by inserting the spatula into the stack somewhere under the top x of them, and flip them over on top of the n-x below. Using only this process, what is the maximum number of times I would have to flip cakes to get them in my preferred order, no matter how they had been originally stacked?
Now pass the maple syrup someone, please?
4 comments:
Flip-sorting an n-stack of pancakes... I think this is right, but I may be missing something.
The most work we can hope to see from two pancakes is one flip.
If we add a third pancake, the largest number of necessary flips to move the largest to the bottom would be two: one flip to move the largest to the top, a second flip to turn the whole stack. This leaves only two pancakes on top, which could require a third flip.
In fact, as we add each new pancake, we would need at most two flips to move the largest to the bottom. When the largest of the n pancakes is at the bottom, we approach the top n-1 pancakes. The largest of these could take at most two flips to move to the bottom, then we get a stack of n-2. When we have only two pancakes left, we need only one flip at most. Two flips for each of the largest n-2 pancakes, one flip for the last two.
Therefore, for any given n, the number of flips necessary is 2*(n-2)+1=2n-3.
The optimum (or most flippant) arrangement which would require the most flips could be found by working backward from the last flip.
Example: n=5. Assume 1 is the smallest and 5 the biggest, the bottom of the stack is at the right. We work backwards:
7=(2n-3): {12345} finished
6. {21345} three down (one flip remaining)
5. {31245} find 3
4. {13245} 4 down
3. {42315} find 4
2. {24315} 5 down
1. {51342} find 5
.. {31542} unsorted
Step 3 must be arranged such that when 3 is flipped down, the remaining (1 and 2) are in the least convenient order (21).
Step 5 must be arranged so that when the 4 is flipped down, the remaining (1,2,and 3) are in the least convenient order (132).
The least convenient order could therefore be constructed by the placement of each larger pancake up to n, giving a stack which actually demands 2n-3 flips.
Nice work Nate, I was going to publish a solution, but I can't imagine I would have been as clear as you were. Now the question is... are you up for the followup? I have in mind a little probability problem about the average "difficulty" of a stack... stay tuned..
and thanks for providing a really good explanation.
Just to clarify, lets take the following example
Py - z = Pancake y with a diameter of z
I have the following:
P5 - 8
P4 - 3
P3 - 9
P2 - 4
P1 - 6
If I flip the stack at P3, I would have the following:
P3 - 9
P4 - 3
P5 - 8
P2 - 4
P1 - 6
Is this correct?
Brian K
Brian, Yes, assuming P1 is the bottom pancake in the stack and P5 is at the top... I just label pancakes by size (1 for smallest etc..) then write the stack from top down as
4, 1, 5, 2, 3 for your starting stack, and then 5, 1, 4, 2, 3 after you flip the top 3, which I lable T(3)
Post a Comment