Problem 671

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
Posts: 4
Joined: Tue May 21, 2019 1:20 pm

Problem 671

Post by amagri »


On the last problem, I wanted some clarifications on the first example F4(3)=104.

Question 1:
Is it authorized to have a tile (eg. 1x3) adjacent to itself?
« Adjacent tiles must be of different colours », but here we only have 1 tile.

Question 2:
I have a similar question regarding the 2nd rule: « It is not permitted for four tiles to have their corners meeting at a single point ». For n=3, we may have « four corners meeting at a point », but with only 2 or 3 tiles. Is it also forbidden?

Many thanks in advance

PS: these clarifications only concern cases where n<=3
Posts: 483
Joined: Sun Mar 22, 2015 2:30 pm
Location: India

Re: Problem 671

Post by MuthuVeerappanR »

Problem 671 (View Problem)

Hi All,
Tiling which are identical after rotating the loop about its axis considered different? Only if I consider them different, I get F_4(3) = 104. Else am stuck at 92.

I'm not sure whether 'reflecting horizontally or vertically would give a different tiling, these tilings are to be counted separately' covers this or not.

Can someone please clarify?

It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
User avatar
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm

Re: Problem 671

Post by jaap »

I have not solved this question yet, but have worked out F_4(3) on paper.

I believe those are indeed forbidden, so for both those reasons you cannot use a 1x3 tile when n=3.

I think rotations around the axis of the loop are not considered different. I get 24+24+24+24+8 = 104 tilings for this. If rotations were different, I'd get 72+72+72+72+24 = 312 tilings.

In my opinion the question should also state that turning the loop upside down, just like horizontal or vertical reflection (and is in fact equivalent to doing both reflections), is also considered to be different. If it were not, I think that for F_4(3) there would be only 104/2 = 52 tilings.
Posts: 4
Joined: Tue May 21, 2019 1:20 pm

Re: Problem 671

Post by amagri »

Thank you jaap for your inputs.

I have not yet solved problem #671, but I am now able to compute F4(3), as well as the other provided examples.

I confirm the points:
- when rotated with rotations Ri (i=1..n-1), loops don’t lead to different loops
- all other transformations (vertical or horizontal reflections, rotating/turning the loop upside down) lead to different loops
- for small n, a tile cannot be adjacent to itself, and the "no four corners meet at a point" rule is applicable regardless of the number of tiles involved

Thank you to both of you for this exchange, and mutual support, good luck!
Post Reply