BR Maths Corner-1

The Technology & Economic Forum is a venue to discuss issues pertaining to Technological and Economic developments in India. We request members to kindly stay within the mandate of this forum and keep their exchanges of views, on a civilised level, however vehemently any disagreement may be felt. All feedback regarding forum usage may be sent to the moderators using the Feedback Form or by clicking the Report Post Icon in any objectionable post for proper action. Please note that the views expressed by the Members and Moderators on these discussion boards are that of the individuals only and do not reflect the official policy or view of the Bharat-Rakshak.com Website. Copyright Violation is strictly prohibited and may result in revocation of your posting rights - please read the FAQ for full details. Users must also abide by the Forum Guidelines at all times.
SaiK
BRF Oldie
Posts: 36388
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 16 Jul 2019 00:59


Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 16 Jul 2019 06:44

International Math Olympiad is taking place in Bath UK.
First paper is tomorrow (July 16th 2019) and the second paper is on July 17, 2019.

Good luck to all participants specially to team USA and team India.

Here is the Team India:
Soumil Aggarwal (Contestant 1) (17 years old)
Bhavya Agrawalla (Contestant 2) (17 years old)
Anubhab Ghosal (Contestant 3) (17 years old)
Ojas Mittal (Contestant 4) (15 years old)
Ritam Nag (Contestant 5) (16 years old)
Pranjal Srivastava (Contestant 6) (15 years old)
C. R. Pranesachar (Leader)

The Team USA:

Vincent Huang (Contestant 1) 18 years old
Luke RobitailleLuke Robitaille (Contestant 2) 15 years old
Colin Shanmo TangColin Shanmo Tang (Contestant 3) 17 years old
Edward WanEdward Wan (Contestant 4) 16 years old
Brandon WangBrandon Wang (Contestant 5) 17 years old
Daniel ZhuDaniel Zhu (Contestant 6) 17 years old
Po-Shen LohPo-Shen Loh (Leader)

SaiK
BRF Oldie
Posts: 36388
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 16 Jul 2019 19:48

Ramanujan machine automatically generates conjectures for fundamental constants

https://phys.org/news/2019-07-ramanujan ... ental.html

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 16 Jul 2019 22:22

Here is an easy problem -
Can you find at least one odd factor of (2019^8 +1) (Without using a calculator/computer).

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 17 Jul 2019 21:38

Here is problem # 6 of IMO 2019. (The exam has just finished a few hours ago - so it is not on official website but has been shared). Nice problem in geometry.

Let I be the incenter of acute triangle ABC with AB is not equal to AC. The incircle w of ABC is tangent to sides BC, CA, and AB at D, E, and F, respectively. The line through D perpendicular to EF meets w again at R. Line AR meets w again at P. The circumcircles of triangles PCE and PBF meet again at Q. Prove that lines DI and PQ meet on the line through A perpendicular to AI

The problem was proposed by Anant Mudgal, India.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 19 Jul 2019 08:50

^^^ From what I heard .. No one (except one partial) from India solved the above problem. :( .
(I think it is a neat problem proposed by India)..
(OTOH from partial scores - the person who got partial (IND - 6) is doing quite good had has near perfect score on first 3 problems).. that's good ( This means, I think India has at least one gold).
*** (Scores are partial - not official and not all problems are graded .. Both US and India are at around 20th for total scoring but this will change

Results will be out on July 20, 2019 But it looks like First Gold for India since about 9 years is by a 9th grader 15 year old. (Pranjal Srivastava) . Very Impressive and congratulations to him.

Final Jury meeting in 9PM on July 20 ( See here: https://www.imo2019.uk/)

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 19 Jul 2019 22:23

To me a strange/ironic thing is the last problem (which I posted here) was proposed by an Indian could be solved by none of the Indians (Except Pranjal who got 1 all else got 0)..
( Nice problem by Anant but may be he should also teach Indian team too .. :) )
Last edited by Amber G. on 20 Jul 2019 05:12, edited 1 time in total.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 20 Jul 2019 05:07

FYI: Pranjal got Silver last year, and at that time I was impressed with him. He is getting gold this time! (It is not official - we may have to wait for as much a day .. - but I am quite sure, seeing the partial results). He has two more years to represent India.

I posted this last year:

Amber G. wrote:^^^ For the record ( Name, score (out of 42) and Medal) (*** This is year 2018 **)
IND1 Sutanay Bhattacharya 21 Bronze
IND2 Spandan Ghosh 21 Bronze
IND3 Amit Kumar Malik 10 HM
IND4 Anant Mudgal} 26 Silver
IND5 Pulkit Sinha 26 Silver
IND6 Pranjal Srivastava 28 Silver
(I am specially impressed by Pranjal - He is youngest - had 4 perfect scores (Prob 3 and Prob 6 were missed) - and method used were nice).. I am sure he is going to do very well in the next olympiad and math in general.

***
Prob 3, (which I posted above) turned out to be rather difficult. None of Indian team solved it. Only 2 from USA did it.
I was kind of surprised as I posted above, when I checked, the problem has indeed came in Scientific American. (This is probably 30-40 years late, but I knew how to solve it then :) ..)

Problem is posted above. (With the hint that solution is in SA one can do internet search)..
(Hint: Answer, is one can not find a solution for N>5 (so not solution for 2018))

One solution posted in SA came from 4th grader (for N=6)indeed quite simple.
Last edited by Amber G. on 20 Jul 2019 05:54, edited 1 time in total.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 20 Jul 2019 05:53

Results of the International Math Olympiads are posted.

Top Teams: 1-2 USA / China
3 - Korea
15- India.

USA (and China too) got 6 gold.
India got 1 Gold, 4 Silver, 1 HM.

Individual scores (Out of 42) (Cut-off for Gold was 31 points and Silver was 24)
Pranjal Srivastava 35 (Rel Rank = 97.26%) Gold medal
Ritam Nag .. 27 83.87% Silver medal
Anubhab Ghosal 27 83.87% Silver medal
Bhavya Agrawalla 27 83.87% Silver medal
Ojas Mittal 24 76.94% Silver medal
Soumil Aggarwal 16 51.29% Honourable mention. (Missed Bronze by 1 point)

Specially impressed by Pranjal - except for P6 he got near perfect score.

USA had 2 perfect scores and 6 Golds.
(China too had 2 perfect scores and 6 Golds and tied with USA)
Link: http://imo-official.org/team_r.aspx?code=IND&year=2019

Rahulsidhu
BRFite
Posts: 119
Joined: 22 Mar 2017 06:19

Re: BR Maths Corner-1

Postby Rahulsidhu » 20 Jul 2019 09:17

Amber G. wrote:Here is an easy problem -
Can you find at least one odd factor of (2019^8 +1) (Without using a calculator/computer).


I managed it with a hit and trial approach:

My first thought was to try and cast it in a form similar to Fermat's little theorem:

2019^8 = -1 (mod a)

and we are looking for a. To get a 1 on the RHS, I square:

2019^16 = 1 (mod a)

this equation may admit more solutions than the original one, but with that in mind, I thought at this point I had the solution: 17. But a quick check using modular arithmetic reveals this to be false. Still, we can try higher powers of 16 (or even powers of 8 from the original equation) as they would all produce 1 on the RHS. We need

2019^(a-1) = 1 (mod a)

where a is prime, and (a-1) = 0 (mod 16).

checking : 16*2 = 32 = 33-1 (not prime), 16*3 = 49-1 (not prime), 16*4 = 65-1 (not prime), 16*5 = 81-1 (not prime), 16*6 = 97-1 (prime)

So the next candidate is 97, and indeed, (2019^8)%97 = (79^8)%97 = (6241^4)%97 = (33^4)%97 = (1089^2)%97 = (22^2)%97 = 484%97 = 96 = -1 (mod 97)
is a solution.

Rahulsidhu
BRFite
Posts: 119
Joined: 22 Mar 2017 06:19

Re: BR Maths Corner-1

Postby Rahulsidhu » 20 Jul 2019 09:35

Just looking at IMO results data, did a quick average rank calculation for the last 10 years (2010-2019)

CHN 1.70
USA 2.10
KOR 4.30
RUS 5.20
PRK 7.43
SGP 8.30
THA 9.00
TWN 11.20
VNM 11.40
JPN 11.60
IRN 13.9
CAN 14.5
UKR 14.8
UNK 16.4
ROU 17.2
AUS 18.7
HUN 19.5
TUR 19.7
SRB 21.6
ITA 22
POL 22.8
GER 23.6
BGR 24
IDN 24.6
KAZ 25.2
PER 25.4
HKG 25.9
BRA 26.7
ISR 27.3
MEX 29.1
HRV 29.6
FRA 30.4
IND 30.4


Results are very interesting in that they seems to correlate neither to country size nor per capita income. East Asian countries dominate.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 20 Jul 2019 22:34

Rahulsidhu wrote:
Amber G. wrote:Here is an easy problem -
Can you find at least one odd factor of (2019^8 +1) (Without using a calculator/computer).


I managed it with a hit and trial approach:

My first thought was to try and cast it in a form similar to Fermat's little theorem:

2019^8 = -1 (mod a)

and we are looking for a. To get a 1 on the RHS, I square:

2019^16 = 1 (mod a)

this equation may admit more solutions than the original one, but with that in mind, I thought at this point I had the solution: 17. But a quick check using modular arithmetic reveals this to be false. Still, we can try higher powers of 16 (or even powers of 8 from the original equation) as they would all produce 1 on the RHS. We need

2019^(a-1) = 1 (mod a)

where a is prime, and (a-1) = 0 (mod 16).

checking : 16*2 = 32 = 33-1 (not prime), 16*3 = 49-1 (not prime), 16*4 = 65-1 (not prime), 16*5 = 81-1 (not prime), 16*6 = 97-1 (prime)

So the next candidate is 97, and indeed, (2019^8)%97 = (79^8)%97 = (6241^4)%97 = (33^4)%97 = (1089^2)%97 = (22^2)%97 = 484%97 = 96 = -1 (mod 97)
is a solution.


Nice!
***
From above - all prime factors for (any_number)^8+1 will be of the form 16k+1.
Historically this is how Euler found the factor 641 of (2^32+1) because he knew that all factors have to be of the type (64k+1) .. and ignoring non-primes like 65, 129 etc, found 641.
(See here: http://eulerarchive.maa.org/hedi/HEDI-2007-03.pdf
(Note - One can improve this method in the case of 2 and one can prove all factors of (2^(2^n)+1) have to be of the form (k*(2^(n+2))+1).

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 18 Aug 2019 07:12

A very entertaining lecture by Terence Tao

2007 lecture where Prof. Terence Tao starts from the definition of Primes and goes all the way to outlining the proof of Green_tao Theorem. I recommend it highly. It is just about 50 minutes long (including Q&A).

I suggest that you watch it on your desktop with a Wikipedia page on another tab. That way you can look up terms and definitions which you haven't come across previously.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 19 Aug 2019 00:48

^^^ It is indeed very good. Thanks for posting it.
***
Terry Tao - I have *many* posts about him in this math dhaga - is one of the greatest living mathematician. He is a great teacher, and his blog (*many links about interesting topics are here in this math dhaga ) . He is still the youngest ( he was 9 or 10 the first time he represented his country in International Math Olympics) IMO gold medal(s) winner.

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 19 Aug 2019 07:58

Amber G. wrote:^^^ It is indeed very good. Thanks for posting it.

You are welcome ma'am/sir.

Prof. Terence Tao started taking college-level courses at the age of 9. He first participated in IMO when he was 10. He had a bronze first year, silver next year, and then he finished with a gold when he was 13. He got a Masters by 16 and a PhD from Princeton by the "ripe old" age of 20. He joined UCLA and got promoted to a full professor by the age of 24. Extraordinary brain.

The other I like is Prof. Eric Demaine, EECS at MIT; originally from Canada.

Terence Tao's parents are from Hong Kong who moved to Australia. Tao himself is a Sino-Australian and now working in the US.

Goes to show that academia is sans state boundaries.

SaiK
BRF Oldie
Posts: 36388
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 06 Sep 2019 08:51

Mathematician Wins $3 Million Breakthrough Prize for 'Magic Wand Theorem'


https://www.livescience.com/breakthroug ... nners.html

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 13 Sep 2019 02:22

The following post was a few months old, we now have an answer raised in that post!

Amber G. wrote:In related matter - Interestingly, this is from recent math news - Ramanujan will be proud..

It was thought (but not proven one way or other) that was impossible to write 33 as sum of 3 cubes it was found that
Wow! 33 = 8866128975287528 ^ 3 - 8778405442862239 ^ 3 - 2736111468807040 ^ 3



Some theory: It was known that -
All numbers of the form 9k+4 or 9k+5 can not be written as sum of three cubes. (we can prove this)
for rest of the numbers the answer is not known.

Some numbers are easy. For example 29 = 3^3+1^3+1^3
or 1 = 1^3+0^3+0^3
also 1 = 10^3+9^3-1^3 (Ramanujan!)

Some numbers are not that easy.. and it required a computer to check many answers..

For example 29 is easy but 30 is hard.

***

Till recently only 33 and 42 were two numbers less than 100 which people did not know the answer..
For example see this youtube video; The Uncracked Problem with 33


Okay we now have an answer for 42!
Ramanujan would be proud.

Wow! Thanks to MIT's mathematician Andrew Sutherland, and a little help from worldwide computer network called Charity Engine. We now know:
(-80538738812075974)^3 + (80435758145817515)^3 + (12602123297335631)^3 = 42

So all numbers less than 100, not of the form 9k+-4, can be written as sum of three cubes.
It sure feel Glorious and Overwhelming to find the answer for 42. And thankfully unlike in Adams' search for the truth, the entire Earth wasn't destroyed in the process of finding the answer! :)

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 13 Sep 2019 02:30

SaiK wrote:Mathematician Wins $3 Million Breakthrough Prize for 'Magic Wand Theorem'


https://www.livescience.com/breakthroug ... nners.html

The mathematician honored (along with the winner of the prize) is none other than Maryam Mirzakhani.. The only woman (and Iranian) who have won a Fields Medal in Math.
I wrote about this in brf about a few times .. last time about his death which was mourned all over the world.
https://forums.bharat-rakshak.com/viewtopic.php?p=2185948#p2185948
Amber G. wrote:From an Indian Newspaper Iran media mourns death of mathematician Maryam Mirzakhani, run front page pictures without hijab
(I don't know now but in 70's quite a few bright Iranian students used to come to India (IIT's etc). Iran always did good in International Math competitions - unlike most of the muslim countries)

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 14 Oct 2019 03:00

Just for fun, Here is a problem from last IMO, which is sort of not too difficult. Let 'f' be a function which applies on integers (and result is an integer) which has following property:

f(2a)+2f(b) = f(f(a+b))

Find all such functions which has this property.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 16 Oct 2019 00:00

Another fun - not too difficult if you hit the right idea - problem .. x, y are real numbers, can you find the values:

1/x + 1/2y = (x^2+3y^2)(3x^2+y^2)
1/x - 1/2y = 2 (y^4-x^4)

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 11 Nov 2019 03:47

Spectra in mathematics and in physics

I found this typed manuscript (11 pages long) to be a great read on how the mathematical concept of a spectrum got intertwined with the physical reality of the spectrum of EM waves as well as stability (or lack there off) of celestial mechanics. The last two pages touch on Quantum Mechanics and eigenpairs.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 11 Nov 2019 09:10

For people interested in modern physics, this from renowned Prof Sachdev is VERY nice.
< Moved to Physics dhaga>

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 14 Nov 2019 22:25

From Princeton Alum Weekly - Nice article... Highly recommend.
On Problem Solving - Similar to my thoughts!
"Sometimes there is a ‘eureka’ moment, but it’s more of a hitting-your-head moment: ‘Of course, why was I so dense?’
- Terence Tao.

Mindi of a Mathematician

VKumar
BRFite
Posts: 517
Joined: 15 Sep 1999 11:31
Location: Mumbai,India

Re: BR Maths Corner-1

Postby VKumar » 14 Nov 2019 23:00

Dr. Vashishta Narayan Singh, eminent mathematician passed away in Patna today.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 15 Nov 2019 00:24

^^^ RIP, Our PM's Tweet: https://twitter.com/rashtrapatibhvn/sta ... 40160?s=20
Narendra Modi
@narendramodi

गणितज्ञ डॉ. वशिष्ठ नारायण सिंह जी के निधन के समाचार से अत्यंत दुख हुआ। उनके जाने से देश ने ज्ञान-विज्ञान के क्षेत्र में अपनी एक विलक्षण प्रतिभा को खो दिया है। विनम्र श्रद्धांजलि!

(After his PhD from Berkley he was a prof at IIT Kanpur and was loved by many)

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 15 Nov 2019 00:33

Amber G. wrote:From Princeton Alum Weekly - Nice article... Highly recommend.
On Problem Solving - Similar to my thoughts!
"Sometimes there is a ‘eureka’ moment, but it’s more of a hitting-your-head moment: ‘Of course, why was I so dense?’
- Terence Tao.

Mindi of a Mathematician

Among other things, Prof Tao also gave a rigorous proof to some of my guru's (Madan Lal Mehta) 50 year old unproven "conjecture" (Mehta Dyson Wigner Conjecture) in 2011. [url](https://terrytao.wordpress.com/2011/02/ ... -matrices/[/url]) ..(Math deals here have roots in Ramnujan's work, zeta functions etc.. which we have discussed in the Math dhaga here in brf). ..

From the above article, kind of problem which I have enjoyed and some may like it here (problem is quite hard, if you have not heard it before)
From above: IMAGINE THAT YOU ARE TRAPPED in a room with a hungry lion. Both you and the lion are represented as points in space. Suppose the lion can run faster than you. Suppose you can run faster than the lion. Suppose you and the lion can run at exactly the same speed. How do you avoid being eaten?

Professor Charles Fefferman *69, himself a Fields Medal recipient, remembers asking 9-year-old Terry Tao these hypotheticals, which are part of a field in mathematics and computer science known as pursuit games, in 1984. Tao’s father, Billy, had taken Terry around the world to meet some of the great mathematicians, to determine if his son had talent. In Princeton, Fefferman and Enrico Bombieri at the Institute for Advanced Study were the people Billy Tao wanted to meet.

The room fell silent with pondering for a while, Fefferman recalls, when Bombieri suddenly stood up, threw his arms in the air, roared like a lion, and playfully chased Tao around the room to break the tension. “For me,” Fefferman says, “that was the highlight of the interview.” Unfortunately for posterity, he can’t recall the details but says Tao answered his questions intelligently...

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 15 Nov 2019 02:40

Amber G. wrote:Just for fun, Here is a problem from last IMO, which is sort of not too difficult. Let 'f' be a function which applies on integers (and result is an integer) which has following property:

f(2a)+2f(b) = f(f(a+b)) ---- (1)

Find all such functions which has this property.


My ansatz is that the function is an exponential function with base 2.

2^k, 2^2k, 2^2^k or something like that.

Much simpler.

f(n) = 2n

Some solutions are

f(n) = 2^k n, k integer greater than 0.

Are those the only solutions? I have to think about how to prove that "all" part which means we have to show there are no other functions which satisfy the functional identity (1)

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 15 Nov 2019 03:19

^^^
f(n) = 2^k n, k integer greater than 0.
f(n) = 2^k n will not work, as one can easily see even for k=2 or f(n) = 4 (n)
and if you put a=b=1, LHS = 8+8 =16 while RHS is 32 :(.
*****

f(n) = 2n will work.!

( and so will f(n)=0 but there are/may be :) other solutions)

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 15 Nov 2019 04:49

Amber G. wrote:^^^
f(n) = 2^k n, k integer greater than 0.
f(n) = 2^k n will not work, as one can easily see even for k=2 or f(n) = 4 (n)
and if you put a=b=1, LHS = 8+8 =16 while RHS is 32 :(.
*****

f(n) = 2n will work.!

( and so will f(n)=0 but there are/may be :) other solutions)


Yes. I made a mistake while doing it in my head where I mistakenly did (2^k * 2^k) == 2^(k+1).

One way to proceed is to apply f^-1 of both sides. We will get

f(a+b) = 2(a+b)

Hence f(n) = 2n is one solution, where n >= 0

If f is an automorphism on \script Z, then that would be the only solution. We cannot make this assumption though.

We don't know that. So we have to search for all endomorphisms on \script Z which satisfy identity (1).

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 15 Nov 2019 05:41

Some clever use of mod somewhere, perhaps.
... (thinking) ...

f(n) = 2 (k mod 2) n, k \in \script Z

I think fits the bill. Any more?

Added later: Another trivial one

f(n) = 2 (n mod 2)
Last edited by Vayutuvan on 15 Nov 2019 06:29, edited 2 times in total.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 15 Nov 2019 06:12

One way to proceed is to apply f^-1 of both sides. We will get
..
By f^-1 do you mean inverse function? A mathematician will ask: How do you even know an inverse function exists? :).
(for example f(x) = 6 is a perfectly nice function.. there is no inverse function .. inverse(3) does not exit.

Besides *even* if you can prove there is an inverse function here, you can't assume it is distributive...Most of functions are not... (Check out sin(xy) is not sin(x)sin(y) or sin(x+y) is not sin(x)+ sin(y) and sin(2x) is not 2 sin(x) ityadi..)

Also as to taking mod 2 etc .. will not work as you can easily check it out.

**** BTW, the answer is same/similar even if one changes "integer" to "real" numbers - but it becomes a much harder problem. The actual problem deals with integers only hence solution is a little easier.

****
Hint: (Big Hint) (I will put my answer shortly if there is an interest:
Step 1 - Assume the function is injective (inverse function exists) (This proof is little hard but for the time assume it - If there is interest I will put some simple way to prove it)
Step 2 - What happens when a=0.

:) :)
-

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 15 Nov 2019 06:57

Amber G. wrote:
One way to proceed is to apply f^-1 of both sides. We will get
..
By f^-1 do you mean inverse function? A mathematician will ask: How do you even know an inverse function exists? :).


f(n) = 2 (k mod 2) n does work out.

if k is odd
f(n) = 2n
else
f(n) = 0
endif

I already said that if one assumes that there exists an injective function, we have f(n) = 2n. This is indeed is a solution. Proof is by plugging into (1). So there is at least one function that is invertible which is a solution.

Assume that the function is a linear function, i.e. f(n) = m.n + c where m and c to be found from (1)

With a = 0, we have 2f(b) = f(f(b)) which is same as 2f(a) = f(f(a))
With b = 0 to get f(2a) = f(f(a))

which gives us 2f(a) + 2f(b) = f(f(a+b))

2 (f(a) + f(b)) = f(f(a+b))

... (to be continued)

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 15 Nov 2019 07:28

Tidbits above the above problem:

The problem was considered an "easy" problem, IIRC something like 2/3 of the contested got at least some credit. I know *all* from Indian team and from US team got a perfect score!
(Even Pakistani team - IIRC someone told me that one (out of 6) was able to do it).

***
I heard the problem just after the contest, and as a physicist (If one believes in "nice" function only - that is if this was a physics problem) I knew the answer within seconds. And it did not take long to confirm/prove it rigorously. (I have used such problems before so techniques are simple and this was not a hard problem. This is why I put it in BRF dhaga.

***
I will put my thinking (how I guessed/got the solution right away) and some-one else's method (which I think is simpler to understand) in the separate message in the next separate post. Hope people like it.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 15 Nov 2019 09:14

Vayutuvan wrote:

f(n) = 2 (k mod 2) n does work out.

if n is odd
f(n) = 2n
else
f(n) = 0
endif


Does it?!
a = 3, b = 5, LHS = f(6)+2f(5) = 0+2*10 = 20 , while RHS = f(f(8)) = f(0) = 0
:)

***
BTW, as I already said, F(n) = 2n is one solution (your one), another one is f(n)= 0 .
Hint: You are close - Only other solution is f(n) = 2n + c where c is any constant integer.

*** Added later: Just saw:
Assume that the function is a linear function, i.e. f(n) = m.n + c where m and c to be found from (1)

If you assume it is a linear function.. *everything is solved* .. (Then function is injective .. and if you plug it in (1) you get either (m=0, c=0 )or m=2. (Only possible solutions)

(Critical part is to prove that f(x) is indeed a linear function )

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 15 Nov 2019 12:52

sorry. it should read

if k is odd, f(n) = 2n else f(n) = 0. that simply captures both cases f(n) = 2n and f(n) = 0.

as for the function having an inverse, I think I can prove that. I am multitasking. I will have to attempt tomorrow.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 15 Nov 2019 22:01

Vayutuvan wrote:sorry. it should read

if k is odd, f(n) = 2n else f(n) = 0. that simply captures both cases f(n) = 2n and f(n) = 0.

as for the function having an inverse, I think I can prove that. I am multitasking. I will have to attempt tomorrow.

What is k? (How does it relate to f(n)? - f is a simple - single variable function onlee :) )
***
Yes, proving the function is injective was the critical work - some proofs were shorter some very many pages long .. so it will be interesting to see another proof. Thanks.

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 15 Nov 2019 23:16

Amber G. wrote:
Vayutuvan wrote:sorry. it should read

if k is odd, f(n) = 2n else f(n) = 0. that simply captures both cases f(n) = 2n and f(n) = 0.

as for the function having an inverse, I think I can prove that. I am multitasking. I will have to attempt tomorrow.

What is k? (How does it relate to f(n)? - f is a simple - single variable function onlee :) )
***
Yes, proving the function is injective was the critical work - some proofs were shorter some very many pages long .. so it will be interesting to see another proof. Thanks.


I was sloppy in my notation.

f_k(n) = 2n (k mod 2), k in Z.

this devides the solution functions into two equivalence classes.

as for existence of injective functions, I thought I can do it. I am missing some thing some key insight.

as for the assumption of linear function, this trick I learned in a book on geometric probability. first chapter starts with Buffon needle problem and the author uses this assumption and solves the problem. then he went onto say that Buffon needle problem actually started Geometric Probability area.

after first chapter, I figured out the book doesn't contain what I was looking for so I abandoned. I was working on developing an algorithm for certain kinds of stochastic linear programming problems. I never got around to the problem which I was looking at during my PhD as one of the chapters. But then my advisor said I had done enough and publish finish the thesis and defend.

even shortest path problem with edge distances stochastic is NP Complete (I think, but surely NP hard). all I can hope for is a bounded error probabilistic or quantum probabilistic algorithm. That also may not be possible since it is believed that BQP doesn't include any problem from NPC.

If somebody can get a BQP algorithm for say stochastic distance shortest path problem, then it would be a big, very big, result.
Last edited by Vayutuvan on 16 Nov 2019 09:12, edited 2 times in total.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 16 Nov 2019 01:15

Here is the solution of the fun problem I posted some time ago and was discussed in last few posts. Hope it generates some interest in Math. I am putting the problem and solution in one post.

Problem:
Just for fun, Here is a problem from last IMO, which is sort of not too difficult. Let 'f' be a function which applies on integers (and result is an integer) which has following property:

f(2a)+2f(b) = f(f(a+b)) (Eq 1)

Find all such functions which has this property.


As said before, when I saw the problem, as a physicist the answer came out fast:

- Easy go see f(x) = 0 as one solution.

- Also if one puts a=0 in eq 1 we get

f(0)+ 2 f(b) = f(f(b)) (Eq 2)

If we substitute f(0) = c (a constant) and f(b) = x (a variable) we get
c+2x = f(x)

So f(x) = 2x + c is another solution. :)

So the answer was easy to guess.. if we can prove that the function is injective we are done. It happens that these are the *only* possible solution. But this has to be proved.
(Proving the rest part - many used many pages of proof and some complicated math but here is an easy method which follows)
**
Putting a=1 and b=x, in (eq1) we get:

f(2) + 2 f(x) = f(f(x+1) -- eq 3

and putting b= x+1 in eq 2 we get
f(0) + 2 f(x+1) = f(f(x+1) eq 4

eq 3 and eq 4 (RHS is same) gives:
f(2) + 2 f(x) = f(0) + 2 f(x+1)
or
f(x+1) - f(x) = (f(2)-f(0))/2 ---- let us call = m eq 4



Rest is simple, since it is true for every x , substitute x=0 , 1.. etc...
so if m = 0 then f(0)=f()=f(2) ...... = 0 (easy to prove that c has to be zero)
if m is not zero then repeatedly applying eq 4
x=0 ==> f(1)-f(0) = m so f(1) = m+c (since f(0) = c)
x=1 ==> f(2) - f(1) = m so f(2) = m+m+c = 2m+c
x=2 ==> f(3)-f(2) = m so f(3) = 3m+c ..
So f(n) = m*n + c
(Basically since f(x+1)-f(x) is constant, the difference is constant the function is linear of the type mx+c)
Rest is easy if you put f(x) = mx+c in eq (1) and substitute a=x, and b=y
m(2x)+c + 2 (my+c) = f(m(x+y)+c) = m(m(x+y)+c) + c
or (x+y)(2m - m^2) = mc - c
Since this is true for *all* values of x and y we would need m^2-2m = 0 = mc-c which gives m=2, or m=0=c
QED
Only solutions:

m=0=c ==> f(x) = 0
m=2 ===> f(x) = 2x+c

Vayutuvan
BRF Oldie
Posts: 10223
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 16 Nov 2019 04:44

Great. I will go through that. So it proves in continuous setting as well or not?

I am thinking something like

1. Assume the solution function is analytic and is a polynomial of degree k.
2. Show that all functions satisfying the given condition are of degree 1 or f(x) = 0.

Other possibility is to

1. assume that the solution function(s) are analytic.
2. Derive one or a system of differential equations from the given identity.
3. Solve that system of differential equations by usual methods.

Amber G.
BRF Oldie
Posts: 6690
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 16 Nov 2019 06:32

Vayutuvan wrote:Great. I will go through that. So it proves in continuous setting as well or not?

I am thinking something like
<see above for details >

Nice observation and A great question..:)

If you expand it to real numbers (instead of integers only) the problem becomes harder. For rational numbers (Q) domain it is still not that hard but to extend it all real number is harder -- this is why they did not give it in the exam.
(I can easily prove for rationals with a simple method but for reals I need much more complicated math - above brf dhaga :) ). Though it is true for reals too (in the sense that these are the only solutions) but the proof is beyond the scope here :).

****
Just a few years ago, there was a very similar problem where domain was real numbers. Again if one dealt with integers that problem was as easy as the one I posted above. But to prove for whole domain of real numbers came out pretty hard --- very few people were able to do it . (IIRC none (or may be 1 only) from Indian team got full marks).

I thought the problem was beautiful. Here it is:

Find all functions (over real numbers to real numbers) such that: (in other words x, f(x) are real numbers)

f(f(x).f(y)) + f (x+y) = f(xy)


***
(Note here too f(x)=0 is obvious solution, and other solution(s) are all linear, if one assumes that solution is very easy
but to prove that only linear solutions exist is much much harder)


Return to “Technology & Economic Forum”

Who is online

Users browsing this forum: No registered users and 14 guests