Sinisterly
Math [Challenge] King me - Printable Version

+- Sinisterly (https://sinister.ly)
+-- Forum: General (https://sinister.ly/Forum-General)
+--- Forum: The Lounge (https://sinister.ly/Forum-The-Lounge)
+---- Forum: Academic Discussion (https://sinister.ly/Forum-Academic-Discussion)
+---- Thread: Math [Challenge] King me (/Thread-Math-Challenge-King-me)



[Challenge] King me - Inori - 10-05-2017

I'm getting horribly bored in my Data Management class, so I'm reading ahead and playing with combinatorics. I half stole this problem from my textbook, but I modified it to provide a decent challenge.

The setup is as follows: you have the following 8x8 checkerboard (zeros represent empty spaces) with one black piece (B) and two white pieces (W). Given the rules of checkers (pieces only move diagonally, single jumps or "captures" are allowed of the opposing color), how many ways can the black piece reach the other side and become a "king"?
Code:
0 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B 0 0

Spoiler: Tip
Pascal's Triangle is awesome for solving pathing problems like this.


Spoiler: My solution
To solve this, the easiest way is to use Pascal's Triangle as mentioned in the hint. It works well because each t(n,r) cell value represents the number of ways to reach that cell.

First, I used the grid provided to structure the frame of an upside-down Pascal's Triangle (i.e. filling in the ones on the outer layer). In the same step, I filled in the first few rows of the triangle because they follow the same summative t(n,r)=t(n-1,r-1)+t(n-1,r) pattern.
Code:
0 0 0 0 0 0 0 0 0 W 0 0 0 0 0 0 1 0 W 0 0 0 0 0 0 1 0 4 0 6 0 ? 0 0 1 0 3 0 3 0 0 0 0 1 0 2 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 B 0 0

Past the third row (technically fourth because B counts as 1), the pattern stops working on the edges because there's no second value to add. To resolve this, we can always "add" zero, making it the same as the previous term.
Code:
0 0 ? 0 ? 0 28 0 0 W 0 ? 0 19 0 9 1 0 W 0 10 0 9 0 0 1 0 4 0 6 0 3 0 0 1 0 3 0 3 0 0 0 0 1 0 2 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 B 0 0

Again, our pattern starts to break down but this time because of the white pieces. This may seem like a difficult edge case, but we can simply use the diagonal preceding the white piece, provided that isn't also a white piece (which is why the top left square stays as zero).
Code:
0 0 12 0 30 0 28 0 0 W 0 11 0 19 0 9 1 0 W 0 10 0 9 0 0 1 0 4 0 6 0 3 0 0 1 0 3 0 3 0 0 0 0 1 0 2 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 B 0 0

Finally, to get the answer we simply sum the first row.
Code:
12 + 30 + 28 = 60



RE: [Challenge] King me - Defeat - 10-13-2017

Grade 12? I remember feeling bad I didn't take maths that year so I tried out data management and wanted to kill myself lol so I dropped it. Thankfully it hasn't cam to bite me yet... will this summer when I'll be taking a required course to graduate uni Sad