/sci/ - Science & Math

[Anonymous No.5195594]

I have a nice riddle for you /sci/.

In how many ways can a king move from the upper-left corner of an nxn-chessboard to the down-right corner if he only moves down, right or diagonally down-right?

[Serkit !eSpvUDpflw No.5195598]

a lot

[Anonymous No.5195612]

maths msc here. well the shortest path is 7 the longest is 14, so there are 14 - 7 = 7 different ways.

[Anonymous No.5195640]

>>5195612
Not OP, but there's at least 12 ways to do it.

1 right, 7 down, 6 right
2 over, 7 down, 5 right
3 over, 7 down, 4 right
...

And
1 down, 7 right, 6 down
2 down, 7 right, 5 down
3 down, 7 right, 4 down
...

[Anonymous No.5195654]

>>5195594
Ignoring the diagonal move for now.
All paths are a permutation of n Rights and n Downs.
Now, with diagonals,
Given a permutation of the above, if you find RD (not DR, only need to consider one of them)in it you can replace with a diagonal to create another path.

go play with factorials. I hope my reasoning is right

[Anonymous No.5195680]

The following argument gives a lower bound to the amount of ways.
For any mxm box incident to the lower right corner the king will have 4*m-1 ways to get in it.
So there are at least [sum_(n=1)^8 (4n-1)] = 136 ways.
This might be exactly it though.

[Anonymous No.5195684]

Too tired to think this through properly, so correct me if I'm wrong.

For every square, excluding those in the rightmost coloumn and downmost row, there are 3 possible moves you can take. Thus, your number of paths witing the (n-1)x(n-1) section from the top left corner of the board would be x^(n-1)^2. Am I correct so far?

[Anonymous No.5195687]

>>5195680
Disregard that, I suck cocks.

[Anonymous No.5195721]

>>5195684
>x^(n-1)^2
I meant 3^(n-1)^2

[Anonymous No.5195742]

>>5195654
>Ignoring the diagonal move for now.
>All paths are a permutation of n Rights and n Downs.
Actually (n-1) Rights and (n-1) Downs.
>Now, with diagonals,
>Given a permutation of the above, if you find RD (not DR, only need to consider one of them)in it you can replace with a diagonal to create another path.
>go play with factorials. I hope my reasoning is right
This already goes in the right direction.
Without diagonal moves the formula can be written in a single binomial coefficent.

>>5195680
>So there are at least [sum_(n=1)^8 (4n-1)] = 136 ways.
For n=8 there are 48639 ways. So your lower bound is not the best one.

>>5195721
It is much less than this since you don't move through every square.

[Anonymous No.5195747]

>>5195684
To follow up on the rightmost coloumn and downmost row (I'd love to wright this in Latex, but I haven't learned it yet):

Starting from the top left square, there (2m-1)n number of ways to get to the square that is m squares away from the down right corner in the left or up direction, where m is less than or equal to n. The number of ways to get to the goal then becomes sum of (2m-1)n from m=0 to m=n. Since this goes for both the rightmost coloumn and downmost row, this is multiplied by two. So to answer your question:

The number of possible paths on a nxn chessboard given you restrictions, is equal to
3^(n-1)^2 * sum (2m-1)n from m=0 to m=n

[Anonymous No.5195751]

>>5195747
>(2m-1)n
(2m-1)(n-1)+1, actually. So my answer becomes:
3^(n-1)^2 * sum ((2m-1)(n-1)+1) from m=0 to m=n

[Anonymous No.5195761]

>>5195751
>3^(n-1)^2 * sum ((2m-1)(n-1)+1) from m=0 to m=n
Damnit, last correction.
3^(n-1)^2 + 2 * sum ((2m-1)(n-1)+1) from m=0 to m=n

[Anonymous No.5195762]

>>5195594
If you disregard the diagonal steps, it's 2^14 minus all cases where the number of steps taken in each direction doesn't equal 7.

[Anonymous No.5195765]

>>5195751
This formula already gives 984150 for n=4.

[Anonymous No.5195770]

>>5195742
>It is much less than this since you don't move through every square.
All right, disregard my posts then. What's the solution?

[Anonymous No.5195774]

Fuckers.

Use pascals triangle/binomial cunt squared

[Anonymous No.5195789]

>>5195774
I was unclear.

On a n x n tile, take the sum of (n-1 choose k), k to (n-1) and square the sum.

Why? Cause the amount of possibilities to get to a square is the same as the binomial coefficient.

[Anonymous No.5195796]

Sup /sci/. This problem seems quite easy but it confused me quite a lot. I can almost see the link but can't find exactly. It should me something to do with factorising.

abcd+abc+bcd+cda+dab+ab+bc+cd+da+ac+bd+a+b+c+d=2009 (so it's basicall all posible combinations you can get with a, b, c and d)
What is the value of a+b+c+d?

[Anonymous No.5195799]

>>5195796
Oh, wanted to start a new thread but let it be here.

[Anonymous No.5195800]

>>5195796
2009.
a = 2009
b=c=d=0.

[Anonymous No.5195804]

>>5195796
(a+1) (b+1) (c+1) (d+1) = abcd+abc+bcd+cda+dab+ab+bc+cd+da+ac+bd+a+b+c+d + 1

[Anonymous No.5195806]

One. Moving only down will not get him to the opposite corner, neither will only moving right. Diagonally down-right is the only option. Stay mad, mathfags.

[Anonymous No.5195810]

>>5195800
Sorry, forgot to tell they are positive integers.
>>5195804
This is the factorising I was looking for, I'll try to work on that, thanks.

[Anonymous No.5195827]

>>5195804
Still don't get it. I'll try tomorrow, my brain is probably too tired.

[Anonymous No.5195871]

You can just generate a directed graph and count the number of paths from start to end.

[Anonymous No.5196002]

n = 2 -> 3
n = 3 -> 19
n = 4 -> 139
n = 5 -> 1083
n = 6 -> 8723
n = 7 -> 71715

I haven't calculated bigger n's than 7 because so far. Im too tired to try to make a formula to fit these values for now but if someone isn't check the formula for different n's with these result. I PROMISE THEY ARE CORRECT.
The way i calculated them was the sameway as salman khan does it in this video with a similiar but simpler problem: http://www.youtube.com/watch?v=9QduzzW10uA&feature=edu&list=PL4DD9C4B87E960720

I did the same way but considering the diagonal moves aswell.

[Anonymous No.5196048]

2012 ways.

[Anonymous No.5196071]

Interesting question OP! Have a bump for starters while I think.

>>5195598
Get out.

[Anonymous No.5196079]

public class ChessThing {
public static void main(String[] args) {
int[][] board = new int[9][9];
board[0][0] = 1;
for (int i = 1; i < 9; i++ ) {
for (int j = 1; j < 9; j++) {
board[i][j] = board[i-1][j] + board[i][j-1] + board[i-1][j-1];
} }
System.out.println(board[8][8]);
} }

output: 48639

[Anonymous No.5196089]

>>5196079
>making a whole class for a simple function

[Anonymous No.5196093]

>>5196089
that's java, isn't it..?

[Anonymous No.5196095]

>>5196089
>>5196093
Yeah, in java, everything is in a class.

[Anonymous No.5196098]

>>5196093
Yes it's java. The other poster is either teasing or being a retard.

[Anonymous No.5196191]

>>5196098
probably the latter

[Anonymous No.5196209]

Sum[Binomial[2 k, k]*Binomial[n - 1 + k, n - 1 - k], {k, 0, n - 1}]
For n=8, the answer is 48639

[Anonymous No.5196291]

Why don't we run it through a computer and find out?

[Anonymous No.5196322]

<div class="math">f(x,y)=\begin{cases}1 &\mbox{if } x = 1 \mbox{or } y = 1\\
f(x-1,y)+f(x,y-1)+f(x-1,y-1) \mbox{otherwise }\end{cases}</div>

[Anonymous No.5196335]

f(x,y) = 1 when x or y equals 1
f(x,y) = f(x-1,y) + f(x,y-1) + f(x,y) otherwise

[Anonymous No.5196349]

f(x,y) = 1 when x or y equals 1
f(x,y) = f(x-1,y) + f(x,y-1) + f(x-1,y-1) otherwise

[Anonymous No.5196389]

>>5196291
Because time-complexity.

[Сергей No.5196482]

Discretization of a calculus of variations problem?

[Anonymous No.5196875]

>>5196209
This formula is correct.

[Anonymous No.5196923]

Some people have it right, but other people are trying to program bullshit instead of just thinking about it. So think about it. Break it into cases. If we only move diagonally, we have one way to do it. Say we wanted to move 4 squares right (and correspondingly we are forced to move 4 squares down and 2 squares diagonally). Then simply permute the string UUUUDDDDXXX where U is an up move, D is a down move, and X is a diagonal move.

You end up with 7!/(0!0!7!) + 8!/(1!1!6!) + 9!/(2!2!5!) + 10!/(3!3!4!) + 11!/(4!4!3!) + 12!/(5!5!2!) + 13!/(6!6!1!) + 14!/(7!7!0!) = 48,639 ways.

[Anonymous No.5197009]

It actually pascal triangles out from the top left to the bottom right.
The number of ways to get to one spot is the sum of the number of ways to get to the spot above it and the number of ways to get to the spot to the left of it.
Therefore the number of ways to get to the last square would be 14C7 = 3432

[Anonymous No.5198260]

Reminded me of: projecteuler.net/problem=15

[Anonymous No.5198323]

Excel is surprisingly handy for this kind of problem.

[Anonymous No.5198425]

>>5197009
This is wrong

[not op No.5198451]

an opponents knight is standing on D4.
how many possible ways?

[Anonymous No.5198466]

>>5198451
If you are not allowed to kill the knight and he does not move, 1072.

[Anonymous No.5198480]

>>5198451
>>5198466
If you are allowed to kill the knight, all of these ways are added and there is a total of 5245 possibilities.

[Anonymous No.5198483]

>>5198260
that was my first thought, but that problem devolves into an exceedingly trivial combinatorial problem (how many combinations of n "L"s and n "R"s) that was one problem I solved on my calculator. With diagonals this is a little more difficult.

[Anonymous No.5198517]

>>5195594
That is not a Chessboard. A Chessboard always has a white square in the bottom right-hand corner.
A Chessboard is always 8x8. Some people use M x N boards (including 8x8) to play Chess-like games, but it's not Chess it's "Faerie Chess" and only perverts do it.
Your pic may or may not be a draughts / checkers board but I don't care because that game is solved.
Don't get it wrong again or I'll tell mom, and then you'll be sorry.

[Anonymous No.5198523]

>>5198517
It's a chessboard turned to the side you autist.
Also, it's obviously Kg7.

[Anonymous No.5198535]

I think the answer to OP is:

sum k from 0 to 7:
[7! / (7-k)!k!] 8^k

(Sorry for my clumsy notation.)

case 0: make 7 diagonal moves.

case 1: extract the rightward move from one of 7 diagonals, and place it in one of 8 places between or at either end of those (once) diagonal moves

case 2: extract the rightward moves from two of 7 diagonals, and place each between one 8 places between or at either end of those (once) diagonal moves

etc.

[Anonymous No.5198546]

>>5198535
First, show that
>>5198323
doesn't work.

[Anonymous No.5198547]

>>5198535
but where are you placing the down moves?

[Anonymous No.5198570]

>>5198547
down and right hold the same value.

[Anonymous No.5198569]

>>5198547
Yeah, I guess I was pretty unclear.
Call diagonal x, down d, right r.

Start with xxxxxxx.
case 1: extract the right movement from one of the diagonals, leaving a d in that position, eg: xxdxxxx. Then place that r in one of the gaps between those seven letters, or at the ends, eg: xxdxxrxx

So you don't explicitly place the down moves, they appear as a consequence of extracting the r move from a diagonal. Clumsily said, I know.

[Anonymous No.5198575]

>>5198569
You're still double counting in several different ways.

[Anonymous No.5198576]

>>5198569
That's wrong. You'd have to add a d and an r.

It'd be
xxxxxxx
drxxxxxx
drdrxxxxx
drdrdrxxxx
etc.

[Anonymous No.5198588]

thank god for functional programming
one minute in ocaml

let rec moves pos = match pos with
(8,8) -> 0
| (x,8) -> 1 + (moves (x+1,8))
| (8,x) -> 1 + (moves (8,x+1))
| (x,y) -> 3 + (moves (x,y+1)) + (moves (x+1,y)) + (moves (x+1,y+1))
;;

print_int (moves (1,1));;
print_string "\n";;

output is 132863, anybody else get that?

[Anonymous No.5198598]

>>5198576
What I'm saying is this: Start with seven diagonal moves. Split one of the seven into dr. Leave the d in that same position, but move the r into one of eight possible positions.

This can happen 7 x 8 ways.

Then split any two of the diagonal moves, and move each of the two r moves into any of eight available positions. 7C2 x 8^2 ways.

etc.

I certainly could be double counting something.

[Anonymous No.5198611]

>>5198598
The second spot loses me too. Have to account for dubs

[Anonymous No.5198654]

#include <iostream>

int** N;

int compute(int x, int y)
{
if (x < 0 || y < 0)
return 0;
if (N[x][y] != -1)
return N[x][y];
N[x][y] = compute(x,y-1) + compute(x-1,y) + compute(x-1,y-1);
return N[x][y];
}

int main(int argc, char** argv)
{
N = new int*[8];
for(int i = 0; i < 8; ++i)
{
N = new int[8];
for (int j = 0; j < 8; ++j)
N[j] = -1;
}
N[0][0] = 1;
compute(7,7);
std::cout << N[7][7] << std::endl;
return 0;
}
48639

[Anonymous No.5198666]

>>5198654
Just use MATLAB

n=8;
A=ones(n);
for i=2:n
for j=2:n
A(i,j)=A(i-1,j-1)+A(i-1,j)+A(i,j-1);
end
end
A(n,n),

[Anonymous No.5198668]

Let k be the number of diagonal movements. Then we have (7-k) right moves and equally many down moves, for a total of 2(7-k) moves. Since the order of moves matter, we can see it as picking out (7-k) elements out of a set of 2(7-k) elements, something that of course can be done in (2(7-k))!/((7-k)!)² ways. Then each of the k diagonal moves can be inserted anywhere in the sequence, at a possible (7-k)+1=8-k different spots, so we have the extra factor (8-k)^k for the final expression
<div class="math">N = \sum_{k=0}^7 \frac{(2(7-k))!}{((7-k)!)^2 }(8-k)^k</div>
This formula at least works for the extremal case k=7 giving just 1 possible route, and I think my reasoning is correct.

[Anonymous No.5198684]

>>5198668
This gives N=34429 using Mathematica.Writing something like this in C is adorable.

[Anonymous No.5198692]

>>5198668
It is <span class="math">{14 - k \choose k}[/spoiler] instead of (8-k)^k.

[Anonymous No.5198700]

>>5198666
My first thought was to use DP (dynamic programming), but I see from a solution above that this is not necessary when all squares are computed and in this particular order. Your methlab solution, however, suffers from those problems DP would otherwise solve.

[Anonymous No.5198702]

>>5198692
Why? You have 8-k possible locations in the sequence to place the diagonal moves and the placement of one doesn't alter the situation for placing the next one (they commute, so to speak).

[Anonymous No.5198729]

>>5198702
Not only do you have 15 - 2k possible locations you also count some more than once.

[Anonymous No.5198756]

adding diagonnal movement makes more of a bitch.

[Anonymous No.5198776]

>>5198729
Oh shit... I see what you mean, yeah. Dont even know why I had 8-k there in the first place. The overcounting is at least somewhat subtle, that is just plain retarded. The reasoning should be that total number of moves are k+14-2k=14-k, and we need to pick k of those to be diagonal, so yeah, we should have <div class="math">{14 - k \choose k}</div>. Then the sought number is instead 48639.

[Anonymous No.5198855]

http://www.wolframalpha.com/input/?i=sum+1+to+7+C%282k%2C+k%29*C%282k%2B1%2C+7-k%29++%2B+1
Output is 35891.
Anybody else get what I found ? (for n = 8)

[Anonymous No.5198886]

The answer was already posted, if you didn't notice.
>>5198323

[mathguy No.5199204]

{2 (n - 1) \choose n - 1} (no diagonal)