r/algorithms • u/ColdRainFD • 2d ago

Help Doubt in proof writing

For this problem -

https://cses.fi/ckvo8q5wh/task/3419

How can I go about proving that the solution is true for all N?

The solution by the way is simple - we just have to XOR the row and column indice values for each Aij entry. So, Aij = i ^ j. How can I prove this mathematically?

2 Upvotes

100% Upvoted

7 comments sorted by

3

u/MagicalPizza21 2d ago

What have you tried? Do you have any ideas? What algorithm-proving techniques have you learned?

1

u/ColdRainFD 2d ago

I just intuitively guessed the solution after trying out a few small test-cases. 

1

u/MagicalPizza21 2d ago

Do you have any other ideas? What algorithm-proving techniques have you learned?

1

u/ColdRainFD 2d ago

No ideas in particular. I do know that the XOR functions help with providing unique values for each column and row (no two values in the row and columns would be the same), and that the matrix as a result would be symmetric (i ^ j = j ^ i). But I cannot prove the crucial condition, the MEX property of each row and column.

1

u/jeffgerickson 1d ago

How can I prove this mathematically?

In the context of algorithm design, the answer to that question is almost always “induction”.

1

u/icantseekgod 1d ago

if i did this question i would do an induction proof along the lines of:
for all n belonging to naturals, p(n) -> p(n+1)
where p(n) is " for a matrix of nxn for all i,j belonging to {1, .. , n}, for all c belonging to {1,.., j-1}, matrix[i][c] neqv matrix[i][j] and for all r belonging to {1,..,i-1}, matrix[r][j] neqv matrix[i][j], and <insert part about matrix\[i\]\[j\] being the smallest non neg int that hasnt shown up to the left of row or above col> "