Mr. Fat and Ms. Taf play a game. Mr. Fat chooses a sequence of positive integers $ k_1, k_2, \ldots , k_n$. Ms. Taf must guess this sequence of integers. She is allowed to give Mr. Fat a red card and a blue card, each with an integer written on it. Mr. Fat replaces the number on the red card with $ k_1$ times the number on the red card plus the number on the blue card, and replaces the number on the blue card with the number originally on the red card. He repeats this process with number $ k_2$. (That is, he replaces the number on the red card with $ k_2$ times the number now on the red card plus the number now on the blue card, and replaces the number on the blue card with the number that was just placed on the red card.) He then repeats this process with each of the numbers $ k_3, \ldots k_n$, in this order. After has has gone through the sequence of integers, Mr. Fat then gives the cards back to Ms. Taf. How many times must Ms. Taf submit the red and blue cards in order to be able to determine the sequence of integers $ k_1, k_2, \ldots k_n$?
Problem
Source: USA TST 2008, Day 3, Problem 8
Tags: algorithm, induction, algebra unsolved, algebra
09.04.2009 17:16
Ms. Taf only needs to submit the cards once. Let $ r_i$, $ b_i$ denote the numbers on the red and blue cards at stage i (after Mr. Fat has just carried out the rewriting process with number $ k_i$), where $ r_0$, $ b_0$ are the initial numbers. Ms. Taf can choose $ r_0 > b_0$. The given algorithm translates to ($ 0 \leq i < n$) $ r_{i + 1} = k_{i + 1}r_i + b_i$ $ b_{i + 1} = r_i$ It can be proved by induction that $ r_i > b_i$. Now show by backwards induction that Ms. Taf can determine $ r_i$, $ b_i$ for $ 0 \leq i \leq n$. We further show if she knows $ r_i,b_i$ then she can find $ k_i$. She knows $ r_n,b_n$. Suppose she knows $ r_i,b_i$. By the division algorithm there is a unique integer k, and $ r < b_i$ such that $ r_i = kb_i + r = kr_{i - 1} + r$ But $ r_i = k_ir_{i - 1} + b_{i - 1}$ with integer $ k_i$ and $ b_{i-1} < r_{i-1}$. Thus $ k = k_i$, and Ms. Taf can find $ k_i$ if she can divide. She can find $ r_{i - 1} = b_i$ and $ b_{i - 1} = r_i - k_ir_{i - 1}$, finishing the induction step. Thus she can determine all numbers from 1 submission.
28.11.2015 05:02
Let $x_i,y_i$ be the numbers on the red, blue card at the $i$th step. So Mrs. Taf initially chooses $x_0,y_0$, and receives $x_n,y_n$ at the end, where for all $i$ $x_i=k_ix_{i-1}+y_{i-1}$ and $y_i=x_{i-1}$. We claim that only $1$ card is needed: choose $x_0=2,y_0=1$ (or any initial values satisfying $x_0>y_0>0$). Note that $x_i=k_ix_{i-1}+y_{i-1}>x_{i-1}=y_i$ for all $i$. Now if we are given $x_n,y_n$, then $x_n=k_{n}y_n+y_{n-1}$ for $y_{n-1}<y_n$, so $k_n$ can be uniquely determined by performing the division algorithm on $x_n$ and $y_n$. From this we also recover $y_{n-1}$ and of course $x_{n-1}$, so inductively we can determine all $x_i,y_i,$ and $k_i$ from this one initial choice.