Page 1 of 1

Maths puzzles

Posted: Tue Jan 30, 2018 2:29 pm
by MehtaRahulC
IMO, this logic puzzle explains an important feature cum shortcoming of islam. For hints, pls google on "Common Knowledge Logic" and see the wiki page.

God created islands and dragons which have following features

(1) An island will have exact 100 dragons

(2) A dragon has red eyes or green eyes. We call red or green
.
(3) Out of 100 dragons on each island, eighty were red and 20 were green

(4) if ALL 80 reds know that ALL 80 reds know that X knows that X is green, THEN
(4a) X will change his eye color and become red within one day OR
(4b) All 80 reds will get together and kill X

(5) but say N <=79 , M<=79 , and if only N reds know that only M reds know that X knows that X is green, but one or more reds doesnt know that X knows X is green, then X wont change N reds will not kill X

(4 + 5) IOW, a green tries his remain green unless there is death threat. And all 80 reds will attempt to kill a green, but only if all 80 reds know that all 80 reds know that green knows that green is green !! Quite a tounge twister, and mind twister, no?

(6) There are no mirrors and no dragon will NOT talk or ask about his or others' eye color

(Q1) God created three islands A , B and C with above characteristics. 1000 days passed. But no dragon changed eye color and no dragon was killed. WHY NOT?

(Q2 to Q4) God was tired of waiting and he sent an Angel to three islands A

(Q2) On island A, Angel called all 100 dragons. All came. Then Angel said - one of you have green eye. And then Angel left. So Angel said something that all dragons knew anyway. But after K days, some greens became reds and some were killed. So why did change/massacre happened? And why didnt it happen till K days passed and happened only after K says? And whats the value of K? Hint : K is around 20

(Q3) On island B, angel called all 100 dragons. But one green could not come and so all 80 reds and only 19 greens were present. Then Angel said - one of you have green eyes. And then Angel left. Will change or massacre happen after K days? How many will be dead or change? Why? Why not? And whats the value of K?

(Q4) On island C, angel called all 100 dragons. But one red could not come and so 79 reds and 20 greens were present. Then Angel said - one of you have green eyes. And then Angel left. Will change or massacre happen after K days? How many will be dead or change? Why? Why not?

Enjoy.
.

Re: Maths puzzles

Posted: Tue Jan 30, 2018 2:35 pm
by MehtaRahulC
This puzzle isnt related to politics etc

Game had Host H and two players S and P.

H selected two numbers 2<=a<=99 , 2<=b<=99, a and b can be same
.
H told a + b i.e. sum to S
H told a * b i.e. product to P

H asked both S and P to guess a and b

first P said : I am unable to guess a, b
then S said : I knew that you wont be able to guess a , b
then S said : And I am unable to guess the numbers too
then P said : Aha , now I know a, b (but doesnt say what a, b are)
then S said : Aha, now I know the numbers too
then both wrote a, b on a paper and gave to H
both were right

So compute a and b that will create such conversation.
.
Hint : I had to write code !!!

Re: Maths puzzles

Posted: Tue Jan 30, 2018 2:43 pm
by MehtaRahulC
This puzzle isnt related to politics etc

The game has Warden and 4 prisoners A, B, C and D

Warden will put any one number between 0 to 3 on hats of all 4 prisoners A to D

repetitions are allowed eg Warden may put (0,1,1,2)

Each can see number of other three and not his own

Each has to write a number on piece of paper and give it to Warden and other three cant see what he writes.

If any one prisoner gets his own number right, then all are spared or all are killed.

So one or more has to be correct. Even if just one is right about his own number , then all are spared

====

Before the game starts, YOU have to give a calculation procedure to each prisoner so that they can live. You can give a different procedure to each prisoner.
.
What procedures will you give ?

Now there are several procedures. But what if prisoners is just class-4 pass? So some computer science procedure may be too complex for them. In such case, what "simple" procedure will you give?
.

Re: Maths puzzles

Posted: Fri May 25, 2018 5:05 pm
by amber g.
Just saw this thread - Few comments - (Odd to see not much discussion - if there is interest will add more)
The first two problems have been asked (and discussed - in quite detail) in BRF dhaga. I first heard a problem similar to problem 2 in a scientific magazine about 50 years ago, and to my knowledge I was the first one to put in a problem set in a math forum in 1998 or so. The problem appeared in USAMTS later. The original problem had two nephews Sanjay (S=Sum) and Pratik (P==Product) who were mathematicians..

I thought I have heard all the "hat" problems, but have not heard the version as in problem 3.. Cute problem, since solution which I got is quite simple and easy to discover. (Think if there are only 2 hats)..

Anyway I will use separate posts to discuss each problem for convenience.

Re: Maths puzzles

Posted: Fri May 25, 2018 5:26 pm
by amber g.
MehtaRahulC wrote:
Tue Jan 30, 2018 2:43 pm
This puzzle isnt related to politics etc

The game has Warden and 4 prisoners A, B, C and D

Warden will put any one number between 0 to 3 on hats of all 4 prisoners A to D

repetitions are allowed eg Warden may put (0,1,1,2)

Each can see number of other three and not his own

Each has to write a number on piece of paper and give it to Warden and other three cant see what he writes.

If any one prisoner gets his own number right, then all are spared or all are killed.


So one or more has to be correct. Even if just one is right about his own number , then all are spared

====

Before the game starts, YOU have to give a calculation procedure to each prisoner so that they can live. You can give a different procedure to each prisoner.
.
What procedures will you give ?

Now there are several procedures. But what if prisoners is just class-4 pass? So some computer science procedure may be too complex for them. In such case, what "simple" procedure will you give?
.
Thanks. Nice problem it also introduces useful application of modulo math.
The solution will work not only for 4 hats but any number of hats say N >1.
First each prisoner, as is customary in any Indian film, ought to be known by number ' 0 to (N-1)'
Now All Kaidi number 'n' does :

sum up all the "numbers" on the hat say this is = s, and one's guess is (n-s)

** all modulo N of course **

This way kaidi number 'n''s guess will be correct.

For example: In case of (0,1,1,2)
K0 sees (1,1,2) so her guess would be 0-4 == 4-4 = 0 (mod 4)
K1 sees (0,1,2) so her guess would be 1-3 == 5-3 = 2 (mod 4)
K2 sees (0,1,2) so her guess would be (2-3) == 6-3 = 3 (mod 4)
K3 sees (1,1,1) so her guess would be (3-3 ==0 = 0 (mod 4)
Try any other combination..

Hope this was fun.

Re: Maths puzzles

Posted: Fri May 25, 2018 5:40 pm
by amber g.
^^^ The above makes a much cuter problem - I may use it in one of the competition..
10 Prisoners - call them K-10, K-11, K-12, ...... K-19...
Their hats similarly numbered (10,11,12,.....19)
ityadi ityadi ...

Now solution for even a first grader..
Sum up all the numbers (do not worry about carry over.. just the unit digit only.)=s
Subtract n-s (just worry about unit digit only..

So K15 - sees sum whose unit digit is 4 .. he will guess his number as 15-4=11.
Try it out and see why it will work.

Re: Maths puzzles

Posted: Fri May 25, 2018 6:09 pm
by amber g.
Minor corrections to post I posted before .. looks like I can not edit the post ...
Just saw this thread - Few comments - (Odd to see not much discussion - if there is interest will add more)
The first two problems have been asked (and discussed - in quite detail) in BRF dhaga. I first heard a problem similar to problem 2 in a scientific magazine about 40 years ago, and to my knowledge I was the first one (or one of the first one) to put in a problem set in a math forum in 1998 or so. The problem appeared in USAMTS later. The original problem had two nephews Sanjay (S=Sum) and Pratik (P==Product) who were mathematicians... Their are few versions of the problem, wordings/solutions may be little different. One key factor needs to be added for problem to be accepted as math problem is "Both contestants are good mathematicians" (that is when they say "I am unable" implies that there is NO way any one can deduct it by logic - and that is very important).

I thought I have heard all the "hat" problems, but have not heard the version as in problem 3.. Cute problem, since solution which I got is quite simple and easy to discover. (Think if there are only 2 hats)..

Anyway I will use separate posts to discuss each problem for convenience.

Re: Maths puzzles

Posted: Sat May 26, 2018 3:20 pm
by amber g.
Are people visiting or interested in this thread?

Re: Maths puzzles

Posted: Sat May 26, 2018 11:47 pm
by amits
Yes, please post.

Re: Maths puzzles

Posted: Sun May 27, 2018 3:32 am
by MehtaRahulC
amber g. wrote:
Fri May 25, 2018 5:26 pm
MehtaRahulC wrote:
Tue Jan 30, 2018 2:43 pm
This puzzle isnt related to politics etc

The game has Warden and 4 prisoners A, B, C and D

Warden will put any one number between 0 to 3 on hats of all 4 prisoners A to D

repetitions are allowed eg Warden may put (0,1,1,2)

Each can see number of other three and not his own

Each has to write a number on piece of paper and give it to Warden and other three cant see what he writes.

If any one prisoner gets his own number right, then all are spared or all are killed.


So one or more has to be correct. Even if just one is right about his own number , then all are spared

Before the game starts, YOU have to give a calculation procedure to each prisoner so that they can live. You can give a different procedure to each prisoner.
.
What procedures will you give ?

Now there are several procedures. But what if prisoners is just class-4 pass? So some computer science procedure may be too complex for them. In such case, what "simple" procedure will you give?
Thanks. Nice problem it also introduces useful application of modulo math.
The solution will work not only for 4 hats but any number of hats say N >1.
First each prisoner, as is customary in any Indian film, ought to be known by number ' 0 to (N-1)'
Now All Kaidi number 'n' does :

sum up all the "numbers" on the hat say this is = s, and one's guess is (n-s)

** all modulo N of course **

This way kaidi number 'n''s guess will be correct.

For example: In case of (0,1,1,2)
K0 sees (1,1,2) so her guess would be 0-4 == 4-4 = 0 (mod 4)
K1 sees (0,1,2) so her guess would be 1-3 == 5-3 = 2 (mod 4)
K2 sees (0,1,2) so her guess would be (2-3) == 6-3 = 3 (mod 4)
K3 sees (1,1,1) so her guess would be (3-3 ==0 = 0 (mod 4)
Try any other combination..

Hope this was fun.
One solution is using modulo-4 as you described above.
.
Another is using XOR (or XNOR). It goes as follows

Say 0 <= A, B, C, D <= 3 are four numbers on hats of A , B , C and D. repitions allowed.
.
Asays = number A will speak

Asays = 0 xor B xor C xor D
Bsays = A xor 1 xor C xor D
Csays = A xor B xor 2 xor D
Dsays = A xor B xor C xor 3

This will work

--------

Now mod-N solution works even when N isnt power of 2

I am didnt check if xor solution works when N isnt power of 2.

Re: Maths puzzles

Posted: Sun May 27, 2018 3:40 am
by MehtaRahulC
A prison warden calls 25 prisoners and tells them

(1) Tomorrow , I will make all of you stand in a one line in any order I decide

(2) Then I will put a RED hat or WHITE hat on top of each of your head in any order I decide

(3) Each one can see hats in FRONT of him, but NOT his own hat and NOT had of people behind him. So last one can see all 24 , and first one can see NONE.

(4) Each one has to say RED or WHITE.

(5) If the color he says is same as color in his head , then he lives or he dies

(6) You can decide any method you like.

(7) But I will be hearing your conversation, and I may use a coloring scheme that may break your method

What method should prisoners follow to reduce death count?

Whats the LEAST POSSIBLE death count?

Also, what if prisoners dont know any computer science and logic, but know only very very elementary maths? Then what methods should 25 prisoners follow?

Re: Maths puzzles

Posted: Sun May 27, 2018 6:51 am
by amber g.
MehtaRahulC wrote:
Sun May 27, 2018 3:32 am
amber g. wrote:
Fri May 25, 2018 5:26 pm

Thanks. Nice problem it also introduces useful application of modulo math.
The solution will work not only for 4 hats but any number of hats say N >1.
First each prisoner, as is customary in any Indian film, ought to be known by number ' 0 to (N-1)'
Now All Kaidi number 'n' does :

sum up all the "numbers" on the hat say this is = s, and one's guess is (n-s)

** all modulo N of course **

One solution is using modulo-4 as you described above.
.
Another is using XOR (or XNOR). It goes as follows

Say 0 <= A, B, C, D <= 3 are four numbers on hats of A , B , C and D. repitions allowed.
.
Asays = number A will speak

Asays = 0 xor B xor C xor D
Bsays = A xor 1 xor C xor D
Csays = A xor B xor 2 xor D
Dsays = A xor B xor C xor 3

This will work

--------

Now mod-N solution works even when N isnt power of 2

I am didnt check if xor solution works when N isnt power of 2.
Yes, sum / mod method will work for any N. The proof is very simple too. XOR etc may work when N is power of 2 as shown below:

I am sure you have realized that, XOR and ordinary sum are equivalent! (For N=2, or just one bit, sum (mod 2) and XOR is same. For N=4 or two bits, again if you switch 2 and 4 for hat numbers -- which should not make any difference in logic -- it is the same.

Thanks for the problem.

Re: Maths puzzles

Posted: Sun May 27, 2018 6:53 am
by amber g.
MehtaRahulC wrote:
Sun May 27, 2018 3:40 am
A prison warden calls 25 prisoners and tells them

(1) Tomorrow , I will make all of you stand in a one line in any order I decide

(2) Then I will put a RED hat or WHITE hat on top of each of your head in any order I decide

(3) Each one can see hats in FRONT of him, but NOT his own hat and NOT had of people behind him. So last one can see all 24 , and first one can see NONE.

(4) Each one has to say RED or WHITE.

(5) If the color he says is same as color in his head , then he lives or he dies

(6) You can decide any method you like.

(7) But I will be hearing your conversation, and I may use a coloring scheme that may break your method

What method should prisoners follow to reduce death count?

Whats the LEAST POSSIBLE death count?

Also, what if prisoners dont know any computer science and logic, but know only very very elementary maths? Then what methods should 25 prisoners follow?
This problem -- at least a simpler version -- too, has been asked/discussed in BRF math dhaga so if someone wants to peek it is there. :)

Re: Maths puzzles

Posted: Sun May 27, 2018 3:03 pm
by amber g.
^^^ Okay, I just thought of modifying the above problem:
What if the choice of color of hat is not only "RED" and "WHITE".. the choice is 7 colors (all rainbow).
Hint1: Problem is VERY simple if one thinks in the right direction.
Hint2: Really, the above hint ought to be enough :).

Re: Maths puzzles

Posted: Tue May 29, 2018 11:30 pm
by amber g.
^^^ Still very few comments...
Believe it or not, for any given value of M, and N where N= Number of prisoners and M= choice of hat colors, the answer is simple and surprising if you have not heard it before. (And it may not depend on the jailor knowing your strategy :)).

Generally the question is asked when M=2 (red and white) but the problem becomes much more interesting for M>2..

***
When question is asked the answers generally goes like ..
(Non mathematicians) -"no interest ", "who cares" or some kind of "wise-guy-joke or remark"
(Very little math) ==> random answer .. expected value of correct answers is about N/M --- minimum can be zero
(Slight math) ==> first tell the color of next in line, second is right ... that way about N/2 people will be saved.

Real mathematicians can do much better.
(Put comments and your answer below --- if you want to peek, the problem is discussed in Bharat-Rakshak math dhaga for 2 colors so it may give you hint.

Re: Maths puzzles

Posted: Wed May 30, 2018 1:48 am
by MehtaRahulC
amber g. wrote:
Sun May 27, 2018 3:03 pm
^^^ Okay, I just thought of modifying the above problem:
What if the choice of color of hat is not only "RED" and "WHITE".. the choice is 7 colors (all rainbow).
Hint1: Problem is VERY simple if one thinks in the right direction.
Hint2: Really, the above hint ought to be enough :).

when hats are red/while = 0/1 , use xor
when hats have seven colors, form 001 to 111 , use bitwise xor

Re: Maths puzzles

Posted: Wed May 30, 2018 10:01 pm
by amber g.
^^^The answer I was thinking is unbelievably simple!!!
All you have to know is how to add and subtract.. and very simple logic!!!

(specially knowing mod method just shown above)


Let the hats choices be (1,2,...M) and the first person, instead of guessing simply shouts out loud the sum (of the rest of the hat's colors) :!: :!:

The second person can now guess correctly because she knows the total sum and sees all the hats except her

And the next person too, sees all the hats in front, and has heard the color of all of the rest of the people behind her too, because she heard them).

Simple only!

Only thing, if the sum is greater than M, one simply takes modulo M :).. thus making it a legitimate guess for a hat color.
((Modulo math works as well as ordinary sum etc.. so logic is understood by any person who can add and subtract!)
(It will work for any number of hats or people.. all except the first will be okay)

Re: Maths puzzles

Posted: Wed May 30, 2018 11:57 pm
by amber g.
MehtaRahulC wrote:
Wed May 30, 2018 1:48 am

when hats have seven colors, form 001 to 111 , use bitwise xor ..
And what do you do when result is "000" hannji : ) ( Colors are from B'001 to B'111" -- there is no color = b'000')
(As with your previous problem xoring works only for 2 (or 4, or 8 etc) colors.

Re: Maths puzzles

Posted: Thu May 31, 2018 2:13 am
by amber g.
Hope some people are interested .. few comments on all the "undiscussed" problems posted here before..
Dragon Problem
Apart from wiki page -This problem has appeared in various forms in many places.. teaches some nice tools in Math/Physics so it has also been a home-work problem in some colleges. (Hint: for googling check out IIT/MIT archives).

Terry Tao (one of the greatest mathematician who writes wonderful blog for aam abduls too)'s discussion (google it) is very nice.

For me, to get the insight, try to solve it for N=2 (or N=3) dragons to get a hang of it.

Interesting insight is when Angel says "there is at least one dragon with green eyes".. it does give information though it seems that that fact is known to all the dragons.

You may like this:

https://terrytao.wordpress.com/2008/02/ ... rs-puzzle/

Re: Maths puzzles

Posted: Thu May 31, 2018 2:50 am
by amber g.
amber g. wrote:
Fri May 25, 2018 5:05 pm
Just saw this thread - Few comments - (Odd to see not much discussion - if there is interest will add more)
The first two problems have been asked (and discussed - in quite detail) in BRF dhaga. I first heard a problem similar to problem 2 in a scientific magazine about 50 years ago, and to my knowledge I was the first one to put in a problem set in a math forum in 1998 or so. The problem appeared in USAMTS later. The original problem had two nephews Sanjay (S=Sum) and Pratik (P==Product) who were mathematicians..

I thought I have heard all the "hat" problems, but have not heard the version as in problem 3.. Cute problem, since solution which I got is quite simple and easy to discover. (Think if there are only 2 hats)..

Anyway I will use separate posts to discuss each problem for convenience.
I still remember 50 years ago when I first saw the problem (or similar one) in Scientific American 40+years ago (I used to subscribe to that magazine) and I did solve it and found it lot of fun.

Few math related concepts which makes the problem easier..
1. All even numbers can be written as sum of two primes. (Goldbach's conjecture): This ==> Sum can not be even!
2. All odd numbers of the form 2+p (p is prime) can be written as sum of two primes too, obviously.
3. So for S you only have to consider values {11,17,23,27,29....}
4. Two numbers are one odd, other even, product even, sum odd.
5. P= (2^n)*p (p prime, n>1) are the numbers where "P can say "I can guess the numbers" (because all other products will be even and sum would be even.

****
The answer(s)
a+b < 60 is given there are NO solutions.
If a+b < 100 (or 200) only solution is (4,13)
if there is no upper bound, then there are many solutions... eg (4,13), (4,61)...

Re: Maths puzzles

Posted: Sun Jul 08, 2018 10:54 pm
by amber g.
The International Math Olympiads 2018 are currently in process.

Good luck to Alll, specially Indian and US teams.
US Team:
- James Lin (Contestant 1)(19 years old, Gold in IMO 2017)
• Participation at IMO: 2017 (G)
- Adam Ardeishar (Contestant 2)(16 years old)
- Mihir Anand Singhal (Contestant 3)(17 Years old)
- Andrew GuAndrew Gu (Contestant 4) (17 years old), Gold in IMO 2017)
- Michael RenMichael Re ((Contestant 5) (18 years old
- Vincent HuangVincent Huan (Contestant 6)(17 years old, Silver in 2017)
• Participation at IMO: 2017 (S)

Hi, and Good luck to Po-Shen Loh (Leader)(A well know mathematics family, both brothers and sister has won gold medals for US in past - Time passes fast have known him for 20+ years)

Indian Team:
- Sutanay Bhattacharya (Contestant 1) (17 years old, Bronze in 2016, HM in 2017)
- Spandan GhoshSpandan Ghosh (Contestant 2)(16 years old)
- Amit Kumar Mallik (Contestant 3)( 16 years old)
- Anant Mudgal (Contestant 4) (17 years old, 2015 HM, 2016 Bronze, 2017 Bronze)
- Pulkit Sinha (Contestant 5) ( 18 years old)
- Pranjal Srivastava (Contestant 6) (14 Years old)

Re: Maths puzzles

Posted: Sat Jul 14, 2018 4:51 pm
by amber g.
I have put some comments about IMO in BRF math dhaga.