10
$\begingroup$

In a small town, there live 110 magicians, who can be identified by their magical color-changing coats. These magical coats turn green whenever the wearer tells the truth, and red whenever the wearer lies.

Today, there is a special festival. Over the course of this festival, each of the 110 magicians will say "Your coat is red" to each of the other 109 magicians.

At least how many times in total will a coat change color during the festival?

$\endgroup$
10
  • 1
    $\begingroup$ What colour do the coats start as? $\endgroup$ Nov 14, 2021 at 12:50
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Nov 14, 2021 at 13:28
  • $\begingroup$ Someone sent me this question and asked me to solve it. Currently i am asking the person for additional information he can add. Currently, he gives a hint to think the "situation" where when will two magicians says red coats to each other. This the information i can provide at the moment. $\endgroup$ Nov 14, 2021 at 13:54
  • 2
    $\begingroup$ do they speak simultaneously? That is, if two green coats meet, is it "one says 'your coat is red' and then that first one's coat turns red, and the second says 'your coat is red' and the second one's coat stays green" -- or is it "they both say 'your coat is red' at once, and then both turn red at once". Please clarify. $\endgroup$ Nov 14, 2021 at 15:33
  • 1
    $\begingroup$ Alright, the person contacted me just now after i asked him if the magicians' speak simultaneously and he said "there is only one situation that both wizards say red hat to each other which is one red hat and one green hat wizard". If that changes the answer please let me know. Thanks for answering this riddle! $\endgroup$ Nov 15, 2021 at 2:18

2 Answers 2

7
$\begingroup$

I think the least number of coat colour changes is

108

We cannot achieve fewer than this as

When two Magicians of the same colour meet and interact at least one of them changes colour. Hence, at least all but one of the green coats will change colour at least once and at least all but one of the red coats will change at least once.
This proves that the number of changes is greater than or equal to 108.

To show that this total is achievable

Suppose that Magician 1 has a green coat and all other Magicians have red coats.
Firstly, Magician 1 conducts a two-way interaction with all other Magicians and no coats change colour. Then, Magician 2 makes the statement to Magician 3 and Magician 2's coat changes to green. Magician 3 completes the interaction with Magician 2 (note Magician 3's coat colour doesn't change since they are lying) and then Magician 2 conducts a two-way interaction with all other Magicians without a change in coat colour.
If we proceed similarly in this way with Magician X conducting similar interactions with Magicians X+1, X+2, ..., 110, we see that there will be just one colour change each time and Magician 110's coat never changes colour, i.e, there will be exactly 108 coat colour changes after all interactions have been completed.

What if, in a given interaction, both parties speak simulataneously

The answer is still 108.
Consider the previous situation where Magician 1 has a green coat initially and every other Magician has a red coat. Firstly, Magician 1 interacts with every other Magician and no coat changes colour.
Then, Magician 2 and 3 interact and both coats change to green. After this, Magician 2 and 3 interact with every other Magician higher than 3 and no coat changes colour.
Then for 2 <= X < = 54, Magician 2X and Magician 2X+1 interact whereupon both change to green and then each of these Magicians interact with Magicians with numbers greater than 2X+1.
In the end there are still a total of 108 coat colour changes.

$\endgroup$
6
  • $\begingroup$ For all clarity: so you make Magician 2 's coat change from red to green after telling the truth about Magician 3's red coat, meaning: you read 'will be green' as 'will become green'? $\endgroup$ Nov 14, 2021 at 19:00
  • 1
    $\begingroup$ @FirstNameLastName yes, that is my interpretation $\endgroup$
    – hexomino
    Nov 14, 2021 at 20:00
  • $\begingroup$ But then isn't it two color changes each time as in (r,r) to (g,g) since both tell the truth? It does not affect your end total though. $\endgroup$ Nov 14, 2021 at 21:44
  • 1
    $\begingroup$ @FirstNameLastName Only if they speak simultaneously, but as you can see from Magician 2 and 3's interaction, if they speak one at a time, only one coat changes colour. $\endgroup$
    – hexomino
    Nov 14, 2021 at 21:55
  • 1
    $\begingroup$ @FirstNameLastName In fact, the answer will be the same even if they are forced to speak simultaneously, I will add something to clarify this. $\endgroup$
    – hexomino
    Nov 14, 2021 at 21:59
-1
$\begingroup$

The answer given by me below is wrong. I had made the following assumption :

It does not matter who speaks first and to whom, who speaks second and to whom, who speaks third and to whom, etc. The number of times the coats change color after all the interaction has taken place will always be the same number.

This assumption has been proven to be wrong by @bobble in the comments section. Anyhow, following is my wrong answer :

______________________________________

Before any magician speaks, let there be m magicians with green coats and p magicians with red coats. m+p =110

After all the statements have been spoken, the total number of times the coats change color will be

$2m^2-220m+11882$ if $m \neq 0$ & $p \neq 0$

$(110-1)^2= 11881$ if $p = 0 $

$(110-1)^2= 11881$ if $m = 0 $

Proof : I am making two assumptions here.

  1. No two magicians speak simultaneously,

  2. It does not matter who speaks first and to whom, who speaks second and to whom, who speaks third and to whom, etc. The number of times the coats change color after all the interaction has taken place will always be the same number. I still don't know how to prove this although I tried doing it though induction. Request someone to help me prove this.

Since, we are assuming that it won't matter in which order the magicians speak, we will choose the following order.

  1. All the m green coat magicians speak to each of the p red coat magicians.
  2. All the p red coat magicians speak to each of the m green coat magicians.
  3. All the m magicians now interact among themselves.
  4. All the p magicians interact among themselves .

Now, let us look at these 4 scenarios in detail.

Firstly, all the ones wearing a green coat make a statement to all the people wearing a red color. Number of times the coat colors change in these interactions = 0

Now, each person wearing a red coat makes the statement to each person wearing a green coat. Number of times the coat color changes in these interactions = 0.

All the m magicians speak to all the other m-1 magicians . All these have green coats before they start interacting among themselves. Let us put all these m green coat magicians in a line.

Firstly, m-1 greens say their statement to the first green. All these m-1 change color. It now looks like :
Green followed by (m-1) Red.
Total color change = m-1.

Now, m-1 people speak to the second magician. After everybody has spoken, it will look like :
Green Red (m-2)*Green
Total color change = m-2

Now, m-1 people speak to the third magician. After everybody has spoken, it will look like
Red Red Green (m-3)*Red.
Total color change = m-2

And, so on.

Thus, m-1 coats change color when the statement is made to the first magician in the line. When the statement is made to the other m-1 magicians, coats change color (m-2)*(m-1) times. Total color change after these m magicians have interacted among themselves = $(m-1)$+$(m-2)*(m-1)$ = $(m-1)^2$ = $m^2-2m+1$

Now, the p magicians interact among themselves. Let us put these p magicians in a line. Their coat color before any of them has spoken among themselves is red.

Firstly, all the p-1 magicians speak to the first person in line. After everybody has spoken, the line will look like
Red (p-1)*Green .
Total times the coats changed color in this interaction = p-1

Now, p-1 magicians speak to the second person in line. After everybody has spoken, the line will look like,
Red Green (p-2)*Red.
The number of times the coat color changes in this interaction = p-2

Now, p-1 magicians speak to the third person in line. After everybody has spoken, the line will look like,
Green Green Red (p-3)*Green.
The number of times the coat color changes in this interaction = p-2.

And, so on.

Thus, p-1 coats change color when the statement is made to the first magician in the line. When the statement is made to the other p-1 magicians, coats change color (p-2)*(p-1) times. Total color change after these p magicians have interacted among themselves =
$(p-1)+(p-2)*(p-1) = (p-1)^2$

Substituting $p = 110-m$,
$(109-m)^2 = m^2-218m+11881$

Therefore, total times the coats color change =

$2m^2-220m+11882$ if $m \neq 0$ & $p \neq 0$
$(110-1)^2= 11881$ if p= 0 $(110-1)^2= 11881$ if m= 0

$\endgroup$
2
  • $\begingroup$ This seems to contradict the other answer which has a lower bound - can you explain why? $\endgroup$
    – bobble
    May 7, 2022 at 20:01
  • 2
    $\begingroup$ Counterexample to assumption #2 with Ag,Bg,Cr: Ag>Cr, Bg>Cr, Cr>Ag, Cr>Bg, Ag>Bg, Bg>Ar has 1 change, but if you instead do Ag>Bg, Ar>Cr note the are already 2 color changes. Therefore order matters. (Ag>Bg means green A talked to green B) $\endgroup$
    – bobble
    May 8, 2022 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.