Course is over?

I'm both happy and sad that this course, following the final, will be over! It has definitely been interesting and fun to pursue these logical endeavours, but I'm also excited to move on to other things using the concepts I've learned in this course. I believe that even in other math courses than MAT137 I'll be able to apply proof structures or other logical thinking to my studies. It's been a pleasure!

Free Lunch

I also looked at the Free Lunch problem.
I represent the circle in a linear manner, with (f1 f2 f3 ... fn) and an x for each eliminated friend. Each trial is separated in the parentheses by a comma.
Given 2 friends, f1 will be treated to lunch. (1 2)
Given 3 friends, f3 will be treated to lunch. (1 2 3, 4 x 5)
Given 4 friends, f1 will be treated to lunch. (1 2 3 4, 5 x 6 x)
Given 5 friends, f3 will be treated to lunch. (1 2 3 4 5, 6 x 7 x 8)
Given 6 friends, f5 will be treated to lunch. (1 2 3 4 5 6, 7 x 8 x 9 x, 10 x x x 11 x)
Given 7 friends, f7 will be treated to lunch. (1 2 3 4 5 6 7, 8 x 9 x 10 x 11, x x 12 x x x 13)
Given 8 friends, f1 will be treated to lunch. (1 2 3 4 5 6 7 8, 9 x 10 x 11 x 12 x, 13 x x x 14 x x x)
Given 9 friends, f3 will be treated to lunch. (1 2 3 4 5 6 7 8 9, 10 x 11 x 12 x 13 x 14, x x 15 x x x 16 x x)
Given 10 friends, f5 will be treated. (1 2 3 4 5 6 7 8 9 10, 11 x 12 x 13 x 14 x 15 x, 16 x x x 17 x x x 18 x)
Given 11 friends, f3 will be treated. (1 2 3 4 5 6 7 8 9 10 11, 12 x 13 x 14 x 15 x 16 x 17, x x 18 x x x 19 x x x 20)
Given 12 friends, f9 will be treated. (1 2 3 4 5 6 7 8 9 10 11 12, 13 x 14 x 15 x 16 x 17 x 18 x, 19 x x x 20 x x x 21 x x x, 22 x x x x x x x 23 x x x)

I made a graph of this data, and it seems that there isn't a pattern. Maybe I'm calculating the friend treated wrong, especially for when there are 9 friends. I guess if I didn't calculate wrong, to know where to sit you would have to memorize this data. If I was wrong and when there are 9 friends f7 is treated, you would have to memorize the pattern shown in the graph (with the point for the number of friends as 9 fixed).

String Steps

I also looked at the String Steps problem.
I believe that it is possible to arrange binary strings in this way, given that the first string equates to zero (all 2^n digits are 0) and the last string is all zeroes except for the very first digit. Beyond n = 3 it gets a bit complicated, but I believe that if it is possible for n= 3 at least, it is possible for all positive n >= 1.
n =1
0
1
n = 2
00
01
11
10
n = 3
000
001
011
010
110
111
101
100

Symbol Migration

I looked also at Symbol Migration.
This also seems deceptively easy to figure out. Since it takes three moves for the symbols to swap as shown in the problem outline, the number of moves needed for a field filled with n rows of '> <' should just be 3n.

Actually, I did read the problem wrong, so no wonder this seems so surprisingly easy.
n = 0 requires 0 moves, as there is nothing to move
n = 1 requires 3 moves
n = 2 requires 8 moves
>> <<
> ><<
> <><
> <<>
>< <>
<> <>
< ><>
< <>>
<< >>
n = 3 requires 15 moves
>>> <<<
>> ><<<
>> <><<
>> <<><
>> <<<>
>>< <<>
><> <<>
<>> <<>
<>>< <>
<><> <>
<<>> <>
<<> ><>
<<> <>>
<< ><>>
<< <>>>
<<< >>>
so where M(n) is the number of moves for n symbols on each side, as n increases by 1, M(n) seems to be increasing at an increasing rate: 3, 5, 7. So M(4) should be 24.
With this theory, M(n) = M(n-1) + 2(n+1) - 1 for n >= 1.

Simple Cartography

Another problem I looked at was the Simple Cartography problem. My favourite part of the problem outline is that the number was specified as non-negative, because of course we all know how negative lines drawn on a sheet of paper appear.
Many solutions to this problem have the minimum number of colours as two, but I think this is incorrect after the number of lines is greater than two. Those who assume two is the minimum talk about how their papers or spaces would be symmetrical, but for a non-symmetrical space, more than two would be needed. Or that's what I thought. In MS Paint, I tried making difficult lines to show that more than two colours would be needed, but eventually after I ended up with this picture, I found myself to be wrong. Well, this is why testing is important :)

Space Slicing

I also looked at the Space Slicing problem. It seems deceptively simple; as with no lines, there is one region, with one there are two, with two there are four, and with three there are seven. With R(n) being the number of regions in the space divided by n lines, R(0) = 1 and R(n) = R(n-1) + n for n <= 1. I feel like I could be wrong though as this seems too easy.

TryThisProblem

Today I looked at the problem titled, "TryThisProblem" on the Problemsolving Wiki.

Here is what I think. To prove that the statement is true for every positive natural number, we must just prove that it is possible to get the function, through its layers, down to 2 or some power of 2, because then it will ultimately get down to 1 by the definition of f(n).
I believe this is possible to show by testing the single-digit naturals. Larger natural numbers will eventually boil down to these (although I am unable to prove this), so by testing these it can show that the larger numbers follow the rule of the statement.

f(1) = 3(1) + 1 = 4 / 2 = 2 / 2 = 1. so F(3, 1) = 1
f(2) = 2 / 2 = 1. so F(1, 2) = 1
f(3) = 3(3) + 1 = 10 / 2 = 5 * 3 + 1 = 16 / 2 = 8 / 2 = 4 / 2 = 2 / 2 = 1. so F(7, 3) = 1
f(4) = 4 / 2 = 2 / 2 = 1. so F(2, 4) = 1
f(5) = 3(5) + 1 = 16 / 2 = 8 / 2 = 4 / 2 = 2 / 2 = 1. so F(5, 5) = 1.
f(6) = 6 / 2 = 3 * 3 + 1 = 10 / 2 = 5 * 3 + 1 = 16 / 2 = 8 / 2 = 4 / 2 = 2 / 2 = 1. so F(8 , 6) = 1
f(7) = 3(7) + 1 = 22 / 2 = 11 * 3 + 1 = 34 / 2 = 17 * 3 + 1 = 52 / 2 = 26 / 2 = 13 * 3 + 1 = 40 / 2 = 20 / 2 = 10 / 2 = 5 * 3 + 1 = 16 / 2 = 8 / 2 = 4 / 2 = 2 / 2 = 1. so F(16, 7) = 1
f(8) = 8 / 2 = 4 / 2 = 2 / 2 = 1. so F(3, 8) = 1
f(9) = 3(9) + 1 = 28 / 2 = 14 / 2 = 7 * 3 + 1 = 22 / 2 = 11 * 3 + 1 = 34 / 2 = 17 * 3 + 1 = 52 / 2 = 26 / 2 = 13 * 3 + 1 = 40 / 2 = 20 / 2 = 10 / 2 = 5 * 3 + 1 = 16 / 2 = 8 / 2 = 4 / 2 = 2 / 2 = 1. so F(19, 9) = 1

Although all that would be needed to disprove my hypothesis is a counterexample.