Math and Logic Puzzles: Redux

[Charles510]

1/4
1/5
1/6

[implosion]

Spoiler: Answer

p/q in lowest terms is sent to a/b such that a*p = 1 mod (p + q) and a + b = p + q.

In other words, find p's multiplicative inverse in the ring of integers mod p + q (which must exist uniquely since p and q (and thus p and p + q) are relatively prime with p/q in lowest terms). Set the numerator to that value, and set the denominator such that the sum of the numerator and denominator is preserved.

[Scigatt]

1/4
1/5
1/6

1/4
1/5
1/6

Spoiler: Answer

p/q in lowest terms is sent to a/b such that a*p = 1 mod (p + q) and a + b = p + q.

In other words, find p's multiplicative inverse in the ring of integers mod p + q (which must exist uniquely since p and q (and thus p and p + q) are relatively prime with p/q in lowest terms). Set the numerator to that value, and set the denominator such that the sum of the numerator and denominator is preserved.

Spoiler: Response

This answer has no actual resemblance to how I'm actually implementing the function. I think it's possible that the the two methods are equivalent. Proving that they are seems to be quite the task. I'll get to working on it. PM me if you want my implementation.

[Charles510]

3/4
2/5
3/5
4/5

[Scigatt]

3/4
2/5
3/5
4/5

5/2
4/3
3/5
7/2

[StrangerCoug]

0.99999

[Scigatt]

0.99999

199997/2

[Scigatt]

implosion's answer was basically correct, though my implementation was dissimilar enough that only now can I prove the equivalence.

Spoiler: Explanation of my procedure and proof

What I did with a given input essentially was to find it on the Stern-Brocot tree, making note of the sequence of turns. I then reversed this sequence, and used that to traverse the tree to get the output.

To traverse the Stern-Brocot tree easily, you need to have a left and right 'ancestor' and their 'descendant', which is their mediant. It is possible to calculate the ancestors from the descendant, but it's much easier to just keep track of the ancestors. To go 'left' on the tree, the mediant of the left ancestor and the descendant becomes the new descendant, and the old descendant becomes the right ancestor. To go to the right the process is analogous.

By convention, the left ancestor is taken as smaller than the right. It is more convenient, however, for this proof to reverse this convention.

Since all iterated descendants of two given ancestors are between them, to capture all positive rationals we need to start with 1/0 as the left ancestor and 0/1 as the right ancestor. Also, it will be helpful to keep track of the numerators and denominators of the ancestors in matrix form(numerator on top). Thus the starting point of the tree is:

Code: Select all

[1 0]
[0 1]

The following matrices then represent going left and right on the tree respectively, if we multiply them in on the right:

Code: Select all

[1 1]  [1 0]
[0 1]  [1 1]

Note all the previous matrices have determinant 1, therefore so does the matrix of any path down the tree. Also, the elements of each path matrix are all integers.
The crux of the proof comes down to two lemmas.

Lemma 1:

From path matrix M get M' by path reversal. Then M' is the 'anti-transpose' on M where m'_ij = m_{(n-j+1)(n-i+1)}, assuming 1-indexing.

This can be proven by induction.

Lemma 2:

Given a 2x2 matrix A, let s be the sum of all elements and r_i, k_j represent row and column sums respectively. The following equation holds:
r_ik_j = a_ijs - det(A)*(-1^(ij))

This can be proven directly.

These two lemmas along with some facts we observed earlier, immediately imply that implosion's method is equivalent to to the path reversal method.

[Jake The Wolfie]

The hell is going on here

[StrangerCoug]

I should probably come up with a good logic puzzle, come to think of it. Hmm...

[Jake The Wolfie]

What lives in the woods, is brown, and is made of concrete?

[StrangerCoug]

Here's an easy sudoku puzzle I created:

	6				7	3	9
3			6					2
	9			5			1
					6			4
	7						3
1			4
	8			1			2
7					2			3
	1	5	3				4

Edit:

Sudoku corrected; three of the numbers were one cell too far to the right.

What lives in the woods, is brown, and is made of concrete?

A cabin?

[Jake The Wolfie]

A cabin?

No

[StrangerCoug]

If you prefer a little more of a challenge, I've got this sudoku, too:

		1			8		5
			9		5	8		3
		8		1			9
2	9
				6
							6	5
	3			7		1
6		4	1		9
	1		8			4

[StrangerCoug]

Any takers for the Sudoku puzzles? I had a solution to the first one DM'd to me on Discord a couple nights ago, but I can't officially accept it unless and until it's posted here.

[Kcdaspot]

Hey StrangerCoug

Spoiler: This look right to you?

ALL OF THe PAIRS

[StrangerCoug]

Spoiler: This look right to you?

That is correct

The sudoku in #213 is still available to solve.

[StrangerCoug]

Or, if you want a harder puzzle than the one in #213, here is a Sudoku X puzzle. On top of the normal rules, each corner-to-corner diagonal must also contain each number from 1 to 9 exactly once.

[Charles510]

If you prefer a little more of a challenge, I've got this sudoku, too:

		1			8		5
			9		5	8		3
		8		1			9
2	9
				6
							6	5
	3			7		1
6		4	1		9
	1		8			4

Spoiler:

Code: Select all

921348657
467925813
358716294
296587341
175463928
843291765
532674189
684139572
719852436

[StrangerCoug]

If you prefer a little more of a challenge, I've got this sudoku, too:

		1			8		5
			9		5	8		3
		8		1			9
2	9
				6
							6	5
	3			7		1
6		4	1		9
	1		8			4

Spoiler:

Code: Select all

921348657
467925813
358716294
296587341
175463928
843291765
532674189
684139572
719852436

Looks good to me

[StrangerCoug]

Or, if you want a harder puzzle than the one in #213, here is a Sudoku X puzzle. On top of the normal rules, each corner-to-corner diagonal must also contain each number from 1 to 9 exactly once.

This puzzle turns not to have a unique solution (not sure why SudokuWiki didn't catch this and gave it a grade anyway), so I'll give you two more clues from the intended solution:

Should still be plenty hard, though

[Charles510]

this one is impossible

[StrangerCoug]

I think it's fair to just put up another puzzle.

[Charles510]

yes, please do

[StrangerCoug]

After work