Skip to main content

Week 10: How to solve a problem

Hello my good friends!

This week is the coveted fall reading break, and I hope you all are doing something useful with your time, like me, who is currently writing my SLOG.

Now that the course is nearing its end, I would like to take it back to the beginning and try to solve one of those logic puzzles, using the Polya method we learned in class. I am, afterall, an amateur logician now, am I not?

So here is the puzzle I have found from the problem solving wiki page.

So without further ado, I present to you:

Walk Tilings

Suppose you have tiles that are 1x2 rectangles, and you have to tile a walk that is 2x3 units long. You've got three choices: 3 vertical tiles, 1 vertical tile followed by two horizontal tiles, or two horizontal tiles followed by one vertical tiles.

How many choices do you have in tiling a 2x4 walk? How about a 2xn walk, where n is some natural number? Do you have a procedure that works for any n?
  1. Understanding the Problem
    • Ultimately we want to know the number of ways you can tile a 2 by n walk using 1 by 2 tiles.
    • This is the notation I have used in my notebook:
      • Since the walk is always 2 units wide, we can use a notation that is just 1 unit wide since the possibilities will always be a mirror image if you put a line through the middle of the 2 unit width.
      • Furthermore, I will represent the horizontal tiles as h and the vertical tiles as v (we must remember that h is always 2 units long, and v is 1 unit long) 
      • For example, a 2x9 walk may be tiled as such:
        • hhvvvvv
        • Since 2 * 2 = 4 and 5 * 1 = 5 and 4 + 5  = 9, this notation works
  2. Devising a Plan
    • My plan was simple: to map out a few of those walks and find a pattern! Sounds reasonable, but boy was I unprepared.
    • A part of my plan was to keep track of 
      1. Which n I was on, and what the total options were
      2. What was the breakdown of h's and v's and how many options they produced in relation to n
      3. Look out for any constants that seemed to repeat for certain groups
      4. I had a feeling that even and odd n's would produce 2 separate patterns, so I would look out for patterns in only odd or even n's
  3. Carrying Out the Plan
    • After carrying out my 'plan', I realized that this was no simple problem to solve!
    • I drew out the tiles for up to n = 9, which took a long time (thinking back I should have just written a program on python to have done it, oh silly me)
    • While I was able to find some sort of constant for the odds and evens (1 + (n - 1) = n for odd n's and 1 + (n - 1) + 1 for even n's), all the other variables seemed very random and had lost relation to n or the h's and v's once it got to n = 9
  4. Looking Back
    • The solution I obtained in the end was non-conclusive; as I did not know how to find just the right way to look at the numbers
    • As I mentioned before, I will definitely utilize my programming mini-powers (as the are by no means superpowers as of yet) to help speed things up
    • I will not look at the solution just yet as I would like to tackle this problem once more at a different time
So it turned out that my problem solving adventure gave no results, however I will not be discouraged! I will definitely come back to this and try to solve more problems.

Have a nice fall break everyone!
Lana :)


Labels:

Comments

Post a Comment

Popular posts from this blog

Week 12: Halting Problem Visualized

Hello readers! I'm sure you're all hard at work trying to finish assignment 3. I just wanted to take a few minutes to share with you a video I found on the halting problem. It may be a tad overdramatic (especially with the music) and corny, but it does explain the problem quite well. Here's part 1 (which can be skipped if you want): And part 2, which is where the real explanation of the halting function starts (skip to 2:33 if you don't like corny dialogue): Hopefully this helps with your endeavors (or at least is a bit entertaining)! Good luck with the assignment! Lana :)
Post a Comment
Read more

Week 5: Tracing Recursion

Hello readers! How have you guys been recently? I have been bombarded with a myriad of tests, labs, and assignments, as usual, but I'll holding up alright! Today's blurb is on tracing recursion! As you all know, a recursive function is basically any function that is called within itself. You'll need it any time a bigger problem can be solved by solving smaller versions of a same type of problem until you get your answer to the big one. Kind of. At least that's how I see it. Anyhow, tracing recursion is not as bad as it sounds, it takes some bit of practice, of course, but all in all it will eventually click. Tracing recursion was on the test this week went successfully I should think. The quasi-solution I came out with with involved the function we needed to trace giving the maximum length of any lists that were fed into it, including the length of the overall list. If I am correct, then my tracing would have been successful. We shall see in due time! Bu...
Post a Comment
Read more