MathDB

3

Part of 2005 Italy TST

Problems(2)

Multiplicative function for coprime m,n

Source:

11/9/2010
The function ψ:N→N\psi : \mathbb{N}\rightarrow\mathbb{N} is defined by ψ(n)=∑k=1ngcd⁡(k,n)\psi (n)=\sum_{k=1}^n\gcd (k,n).
(a)(a) Prove that ψ(mn)=ψ(m)ψ(n)\psi (mn)=\psi (m)\psi (n) for every two coprime m,n∈Nm,n \in \mathbb{N}. (b)(b) Prove that for each a∈Na\in\mathbb{N} the equation ψ(x)=ax\psi (x)=ax has a solution.
functionnumber theory proposednumber theory
Alberto and Barbara play a game

Source:

11/9/2010
Let NN be a positive integer. Alberto and Barbara write numbers on a blackboard taking turns, according to the following rules. Alberto starts writing 11, and thereafter if a player has written nn on a certain move, his adversary is allowed to write n+1n+1 or 2n2n as long as he/she does not obtain a number greater than NN. The player who writes NN wins. (a)(a) Determine which player has a winning strategy for N=2005N=2005. (b)(b) Determine which player has a winning strategy for N=2004N=2004. (c)(c) Find for how many integers N≤2005N\le 2005 Barbara has a winning strategy.
inductioncombinatorics unsolvedcombinatorics