Integer Point on Line
A recent interview question asked in Quant Interview at Millenium
Before we begin this week’s Newsletter
Hey Folks, Our Friends at Optiver are collaborating with Kaggle to provide a one-of-a-kind challenge at the intersection of trading and data science!
We invite the entire data science & quant community to delve into financial markets and develop models forecasting the Nasdaq Closing Cross auction's closing movements. Put your analytical talents to the test over three months, modify your model, and get a sense of the daily issues faced by Optiver's traders, quantitative researchers, and engineers.
Are you up for the challenge? Register by December 13th to compete for a share of the $100,000 prize pool. Find out more about the competition: https://optiver.com/kaggle-and-optiver-predicting-nasdaqs-closing-cross-auction-movements/
Now for this Week’s problem
Calvin and Toby are playing a game on a 2D coordinate plane. An integer point in a plane is a point whose coordinates are integers. Toby challenges Calvin that given any 5 random points on this plane. He can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point.
Can Calvin find 5 such points to prove Toby wrong ?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
Calvin can’t find any such 5 points and the reason is really short and sweet.
There are 4 parities - {Odd, Odd}, {Even, Odd}, {Even, Even}, {Odd, Even}.
By Pigeon Hole Principle, at least 2 points must have the same parity. As we select two points of the same parity, the mid-point has to be an integer point. 🎃
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!