Let $a_0, a_1, \ldots, a_9$ and $b_1 , b_2, \ldots,b_9$ be positive integers such that $a_9<b_9$ and $a_k \neq b_k, 1 \leq k \leq 8.$ In a cash dispenser/automated teller machine/ATM there are $n\geq a_9$ levs (Bulgarian national currency) and for each $1 \leq i \leq 9$ we can take $a_i$ levs from the ATM (if in the bank there are at least $a_i$ levs). Immediately after that action the bank puts $b_i$ levs in the ATM or we take $a_0$ levs. If we take $a_0$ levs from the ATM the bank doesn’t put any money in the ATM. Find all possible positive integer values of $n$ such that after finite number of takings money from the ATM there will be no money in it.
Problem
Source:
Tags: modular arithmetic, combinatorics unsolved, combinatorics
18.01.2011 22:27
Any idea? I need a solution to teach my students. plz help me T_T
19.01.2011 01:09
amparvardi wrote: Find all possible positive integer values of $n$ such that after finite number of takings money from the ATM there will be no money in it. Does this mean, find all $n$ such that for any sequence $\{a_i\}_{i=0}^9$ and $\{b_i\}_{i=1}^9$, we can eventually deplete all the levs in the ATM? Also, what if the last move $a_k$ empties the ATM, but then the bank puts back $b_k$; does that count and emptying the ATM? Suppose $n>1$ and let $p$ be the smallest prime not dividing $n$, let $a_0=a_1= ... = a_9=p$ and let $b_1=...b_9=2p$. Then the money can never be depleted because the number of levs changes by $p$ or $2p$ each time and $n-kp \not = 0$ for any $k\in \mathbb{Z}$. If $n\le 2$ then $n$ will not be larger than the smallest prime dividing it. Thoes cases will probably be easy once we know the intended question.
19.01.2011 18:09
ocha wrote: Does this mean, find all $n$ such that for any sequence $\{a_i\}_{i=0}^9$ and $\{b_i\}_{i=1}^9$, we can eventually deplete all the levs in the ATM? Also, what if the last move $a_k$ empties the ATM, but then the bank puts back $b_k$; does that count and emptying the ATM? Presumably no; it looks like you have to finish by removing $a_0$ levs on your last move. In that case, the problem appears to be a complicated rewording of this one: "For which collections of an integer $a_0$, an integer $n$, and a set $\{b_1 - a_1, \ldots, b_9 - a_9\}$ of nine integers do there exist integers $c_1, \ldots, c_9$ such that $c_1(b_1 - a_1) + \ldots + c_9(b_9 - a_9) \equiv n \pmod{a_0}$?" (Well, I have made a first step already in this simplification: because $n > a_9 < b_9$, we can begin by adding $b_9 - a_9$ levs to the machine arbitrarily many times. In particular, we can do it $N \cdot a_0$ times for some $N$ large enough that all the later steps (those indexed by the $c_i$, before we begin pulling out multiples of $a_0$) leave us with a positive number of levs in the machine.)