Tenali Rama explains alldifferent constraint

King is fond of puzzles and generous in rewarding  puzzle solvers. Rama zealously guards king's wealth by attempting to prove the visiting  puzzle solvers wrong. 

The puzzle is

You have 10 bags of coins, each consisting of 100 rupee coins. One entire bag is counterfeit, but you do not know which one. You do know the weight of a genuine rupee coin, say 1 gram, and you are also told that each counterfeit coin weighs one gram more. You may weigh the coins on a pointer scale. You are allowed to weigh only once. How do you identify the counterfeit coins? Will your method work if it is 100 bags instead of 10 with only one counterfeit bag again?

The visitor solves it by a solution he obtained by the mercy of Namagiri, the consort of Narasimha and claims that is the only solution. Tenali Rama contests the claim by  producing another solution.

Visitor's solution: Take 1, 2, 3,....10 coins from the bags and mark them according to the coins taken. Weigh the coins and the difference in weight between the actual and expected weight gives away the counterfeit bag.

Rama's solution: Take 2, 4, 6,....20 coins from the bags and mark them according to the coins taken. Weigh the coins and the difference in weight between the actual and expected weight gives away the counterfeit bag.

Rama explains that it is necessary and sufficient for any pair to have different numbers so that the sequence of 10 numbers is a solution. He predicts there will be a survey paper in 21st century on alldifferent constraint.

The visitor gets only half the reward because his uniqueness claim is wrong. 

An aside:

A quote from "The Science of Programming" by Gries

"I once listened to two computer scientists discuss exponentiation talk right past each other; each

thought he was talking about the exponentiation routine, not knowing

that the other existed."

Gries himself is guilty by the very title of the book without mentioning alternative scientific approaches like logic programming and a computer language like PROLOG.

Tenali Rama's idea defeated by randomization

I concoct another story to tell my future grandchildren.

King is fond of  poetry. He will reward any poet who produces a poem not known to his court poets. Tenali Rama can recite any poem after listening to it once (EkaSandhagrahi). There are five others who  are DviSandhagrahi, Trisandhagrahi etc. among them. They come to an agreement to recite any poem heard from the visiting poet by volunteering in the order of their abilities. This works. King always comes to the conclusion his poets have known the poem all along and sends away the visiting poet. This creates a commotion among the outside poets. They go to guntur gambli who is a poet as well as a gambler. He hates to visit king's court but yields to the pressure of his friends.

He thinks hard and comes up with a plan to teach the clique of court poets a lesson. His poem is all about the virtues of the king and how the king is favored by the gods in any gamble he accepts.  Guntur Gambli requests the King that the order of the poets to recite the poem be determined by throws of dice. Tenali Rama protests saying God does not play dice. King, high on the praise showered on him by Gambli overrules Rama and   finds his court poets failing to recite the poem. Gambli walks away with a reward and the court poets give up their pretensions to omniscience.

Tenali Rama, a software engineer from 16th Century Andhra

I concocted a story to tell my future grandchildren based on a mathematical problem discussed in a previous post

Tenali Rama (T) and his King Krishnadevaraya (K) decide to send a culture-warrior to one neighboring country. K says he has too many fit for the job. T says he knows a few from his native place Tenali.  A  pool is formed by mixing the cards with the names of candidates and  K and T.

King suggests picking randomly two cards and repeating the following and the winner for the job is the one remaining in the end.

If both belong to same (either K or T), throw them out and put in a new card from K. Notice K has a lot of people for the job.

If both K and T cards turn up, T gets to put back the T card and King throws away K card.

King lets Tenali Rama to  choose the number of T cards to start with. He is confident he can overwhelm with K cards. K always loses in spite of this because of clever choice of Rama.

King thinks hard and comes up with an idea. He tells Rama that he too knows a few other people from Tenali and adds equal number of T cards to whatever number Rama chooses.

Now King wins all the time. We all know why.

We established that the number of black beans does not matter at all in the coffee bean problem if all that we are interested in is color of the bean remaining at the end of the process. Neither does the random choice of the two beans has any effect on the number of steps in the process or on the outcome we are interested in. Only thing that matters is the parity of the number of white beans that remains invariant before, during, and after the process.

The correspondence here is (K = Black Bean) and (T = White Bean).
Tenali Rama always starts the game with an odd number of T cards and wins.
King gets it after a lot of thinking and proposes a change to make the starting number of T cards even. Now no chance for Tenali Rama. King always wins.

The Coffee Can Problem from "The Science of Programming" by Gries

" A coffee can contains some black beans and
white beans. The following process is to be repeated as long as possible.
Randomly select two beans from the can. If they are the
same color, throw them out, but put another black bean
in. (Enough extra black beans are available to do this.)
If they are different colors, place the white one back into
the can and throw the black one away.

Execution of this process reduces the number of beans in the can by one.
Repetition of the process must terminate with exactly one bean in the can,
for then two beans cannot be selected. The question is: what, if anything,
can be said about the color of the final bean based on the number of
white beans and the number of black beans initially in the can?"

When I came across this problem in 1984, I reasoned as follows:
If the can has (1b, 1w)  then final bean is white.
If the can has (2b, 1w)  then final bean is white because after the first draw the  state is (1b, 1w).
If the can has (3b, 1w)  then final bean is white because after the first draw the  state is (2b, 1w).

I stopped and looked at it and said to myself maybe I can prove something here by mathematical induction.
If the can has (nb, 1w)  then final bean is white because after the first draw the  state is ((n-1)b, 1w).
By similar reasoning I could prove
If the can has (nb, 0w)  then final bean is black because after the first draw the  state is ((n-1)b, 0w).

That is nice. Becoming a bit bold,
Starting from  (0b, 2w) first  draw results in (1b, 0w) i.e black in the end.
Starting from  (1b, 2w)  first  draw results in either  (2b, 0w)    or (0b, 2w)  resulting in black in the end.
Starting from  (2b, 2w) first  draw results in either (3b, 0w) or (1b, 2w) resulting in black in the end.
Starting from  (3b, 2w) first  draw results in either (4b, 0w) or (2b, 2w) resulting in black in the end.

By mathematical induction   I could prove
 If the can has (nb, 2w) first  draw results in either ((n+1)b, 0w) or ((n-1)b, 2w) resulting in black in the end.  

These three results together form the theorem of irrelevance of number of black beans. I noticed another regularity. Starting with even (odd) number of white beans results in black (white) in the end. 

By mathematical induction I could prove for any even number
Starting from  (1b, (2*n)w) first  draw results in either (2b, (2*n-2)w) or (0b, (2*n)w) resulting in black in the end.
Similarly for any odd number 
 Starting from  (1b, (2*n+1)w) first  draw results in either (2b, (2*n-1)w) or (0b, (2*n+1)w) resulting in black in the end.

I satisfied myself this is mathematically correct and test cases helped to get the feel for the result.

Gries differs.
"It doesn't help much to try test cases! It doesn't help to see what happens
when there are initially I black bean and I white bean, and then to see
what happens when there are initially 2 black beans and one white bean,
etc. I have seen people waste 30 minutes with this approach.

Instead, proceed as follows. Perhaps there is a simple property of the
beans in the can that remains true as beans are removed and that,
together with the fact that only one bean remains, can give the answer.
Since the property will always be true, we will call it an invariant. Well,
suppose upon termination there is one black bean and no white beans.
What property is true upon termination, which could generalize, perhaps,
to be our invariant? One is an odd number, so perhaps the oddness of the
number of black beans remains true. No, this is not the case, in fact the
number of black beans changes from even to odd or odd to even with
each move. But, there are also zero white beans upon termination
-perhaps the evenness of the number of white beans remains true. And,
indeed, yes, each possible move either takes out two white beans or leaves
the number of white beans the same. Thus, the last bean is black if ini-
tially there is an even number of white beans; otherwise it is white."

That was the first time I heard of importance of  invariant.  It is definitely helpful if we can find such properties. Test cases do help us in getting the feel. Is not Gries himself doing the sort of reasoning he discounts in the previous paragraph?

I leave it to the readers to comment on this.