Project Euler/301 - Revision history

Unknown user: /* Notes */

2025-04-19T23:55:50Z

Notes

← Older revision		Revision as of 23:55, 19 April 2025
Line 21:		Line 21:
	** <math>a \oplus b = 0 \quad \mbox{iff} \quad a=b, a \oplus a = 0</math>		** <math>a \oplus b = 0 \quad \mbox{iff} \quad a=b, a \oplus a = 0</math>
	** XOR is associative and commutative		** XOR is associative and commutative





	[[Image:ProjectEuler301.png\|500px]]		[[Image:ProjectEuler301.png\|500px]]

			Solution in 0.4 seconds using Firefox

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Notes */

2025-04-19T23:55:16Z

Notes

← Older revision		Revision as of 23:55, 19 April 2025
Line 21:		Line 21:
	** <math>a \oplus b = 0 \quad \mbox{iff} \quad a=b, a \oplus a = 0</math>		** <math>a \oplus b = 0 \quad \mbox{iff} \quad a=b, a \oplus a = 0</math>
	** XOR is associative and commutative		** XOR is associative and commutative

			[[Image:ProjectEuler301.png\|500px]]

			==Flags==

			{{ProjectEulerFlag}}

Unknown user: /* Notes */

2025-04-19T23:42:33Z

Notes

← Older revision		Revision as of 23:42, 19 April 2025
Line 19:		Line 19:

	* XOR/Bitwise operations:		* XOR/Bitwise operations:
	** <math>a \oplus b = 0 \~~qquad~~ \mbox{iff} \\quad a=b, a \oplus a = 0</math>		** <math>a \oplus b = 0 \quad \mbox{iff} \quad a=b, a \oplus a = 0</math>
	** XOR is associative and commutative		** XOR is associative and commutative

Unknown user: /* Notes */

2025-04-19T23:42:18Z

Notes

← Older revision		Revision as of 23:42, 19 April 2025
Line 19:		Line 19:

	* XOR/Bitwise operations:		* XOR/Bitwise operations:
	** <math>a \oplus b = 0 \mbox{iff} a=b, a \oplus a = 0</math>		** <math>a \oplus b = 0 \qquad \mbox{iff} \\quad a=b, a \oplus a = 0</math>
	** XOR is associative and commutative		** XOR is associative and commutative

Unknown user: /* Notes */

2025-04-19T23:42:03Z

Notes

← Older revision		Revision as of 23:42, 19 April 2025
Line 16:		Line 16:
	** The Nim-sum is calculated using the bitwise XOR operation		** The Nim-sum is calculated using the bitwise XOR operation
	** The given 3-heap problem has a Nim-sum <math>X(n_1, n_2, n_3) = n_1 \oplus n_2 \oplus n_3</math>		** The given 3-heap problem has a Nim-sum <math>X(n_1, n_2, n_3) = n_1 \oplus n_2 \oplus n_3</math>
			** The given condition <math>X(n, 2n, 3n)=0</math> translates to <math>n \oplus 2n \oplus 3n = 0</math>

			* XOR/Bitwise operations:
			** <math>a \oplus b = 0 \mbox{iff} a=b, a \oplus a = 0</math>
			** XOR is associative and commutative

Unknown user: Created page with "==Problem statement== The problem asks for the number of positive integers $n \leq 2^{30}$ such that the Nim game position (n, 2n, 3n) is a losing position for the..."

2025-04-19T23:40:10Z

Created page with "==Problem statement== The problem asks for the number of positive integers <math>n \leq 2^{30}</math> such that the Nim game position (n, 2n, 3n) is a losing position for the..."

New page

==Problem statement==

The problem asks for the number of positive integers <math>n \leq 2^{30}</math> such that the Nim game position (n, 2n, 3n) is a losing position for the player whose turn it is, assuming perfect play.

The function X(n1, n2, n3) determines this: X=0 for a losing position and X!=0 for a winning position

==Notes==

Key mathematical topics:
* Game theory (impartial game, available moves only depend on the state of the game and not on which player is moving)
** P-positions (previous player winning, current player will lose if opponent plays optimally) and N-positions (next player winning)
** Problem statement says, X(a,b,c)=0 corresponds to a P-position

* Bouton's Theorem (fundamental to solving Nim)
** States that a Nmim position <math>(n_1, n_2, ..., n_k)</math> is a P-position iif and only if the nim-sum of the heap sizes is zero
** The Nim-sum is calculated using the bitwise XOR operation
** The given 3-heap problem has a Nim-sum <math>X(n_1, n_2, n_3) = n_1 \oplus n_2 \oplus n_3</math>

Project Euler/301 - Revision history

Unknown user: /* Notes */

Unknown user: /* Notes */

Unknown user: /* Notes */

Unknown user: /* Notes */

Unknown user: /* Notes */

Unknown user: Created page with "==Problem statement== The problem asks for the number of positive integers n \leq 2^{30} such that the Nim game position (n, 2n, 3n) is a losing position for the..."

Unknown user: Created page with "==Problem statement== The problem asks for the number of positive integers $n \leq 2^{30}$ such that the Nim game position (n, 2n, 3n) is a losing position for the..."