Game of Coins

So, I am back again with an interesting puzzle. Credit goes to my dear friend Sambuddha Roy to introduce me to this puzzle as well as its very simple solution.

Here goes the puzzle :

Even number of coins are laid out in a straight line. Coins may have different denominations. Two players p1 and p2 are playing a game. When a player's turn comes he/she has to pick a coin from either end of the line. When all the coins are exhausted, player with the highest amount wins. A tie occurs whent both the player possess the equal amount.

Prove that if p1 goes first, he/she always have the stretagy such that he/she does not loose the game.


Solution :

Solution to this puzzle is very simple and I really felt really stupid when I came to know about the solution and its simplicity. As always, I tried to use induction to prove that p1 always have a winning stretagy ( or non-loosing stretagy). For the case when number of coins is 2, p1 can pick the larger of the two. But then things get complicated when we need to prove the induction step. In fact, I did not spend enough time to prove that using induction.

A very simple solution is that p1 can index the coins from 1 to n. Then, he can calculate sum total of odd-numbered coins as well as even-numbered coins. p1 can always pick coins in a way such that he/she always gets even-numbered or odd-numbered coins depending on which of those will make up a larger amount.

Space v/s Time

Hi all,
I know there has been a long pause on my blog. Well, it was a transition period for me from IRL to IITK. Yes, I have joined its CSE department as a PhD student. Anyways, I know the title is somewhat misleading as many would think this post has something to do with einstein's theory of relativity and the four dimensional world. You are grossly mistaken if you think so.

Actually, as part of my coursework here I am attending a course by Prof Manindra Aggarwal. Well, it is a big mistake on my side that I have not registered for this course. Even the bigger mistake is that I have registered for a course named "Computational Number Theory and Algebra" by Prof Piyush Kurur. The content itself may be interesting but the way that guy teaches the course, makes it difficult. The worst part is that all the exams of this course are "take home" exams.

Anyways, let's get back to the point. It is indeed an honour to sit in Prof Manindra's class and see him deliver some of the toughest content of the course with a flair. All the people with computer science background are aware of the P not equals NP conjecture. This decade old conjecture has still remain unbeaten. In other words, this conjecture states that the set of problems that can be solved by a deterministic turing machine in polynomial time and the set of problems that can be solved by a non-deterministic turing machine in polynomial time are equal.

There is another notion called Space Complexity in computer science. Space complexity is a measure of the space required to solve any problem by an algorithm. One wonders, whether there is any difference between the set of problems which can be solved by a deterministic turing machine in polynomial space , and the set of problems which can be solved by a non-deterministic turing machine in polynomial space. It actually turns out that non-determinism does not give any more power over deterministic mechanism when space is the criterion. Due to Savitch's theorem it is proven that PSPACE equals NPSPACE.

One may wonder why the similar version in time complexity is yet unbeaten? Non-determinism gives the power to explore exponentially many threads of computation simultaneously. If a deterministic turing machine tries to mimic the behaviour of a non-deterministic one, it has to explore all the paths one by one. It costs time to go through all the paths one by one. One has to add up all the time that has been spend. But does one really have to add up the space as well??? I felt really stupid when I come to know that the reason why power of deterministic and non-deterministic turing machine comes out to be same, is that space can be reused!!!!

As a wild thought, may be if a deterministic turing machine can go back in time to explore the alternate future, thus, reusing the time we may as well have P = NP :D.

A few gems in gujarati

I have realised that no medium, tool is good or bad in general. It depends on how you view it or how you use it. Orkut may be a nuisance to some but I could find a few gujarati gems from a community.
----------------------------
પ્યાલો લૈ જ્યાં હું પહોંચ્યો તરસ છીપાવા માટે,
કમનશીબ મારું કે મને જોઈ કીનારા જ સુકાઈ ગયા.

પતઝડ ની કશ્મ્કશ તો જીરવી ગયા અમે પરંતુ,
જીંદગી ના બાગ તો ભરવસંત માં જ ઉજડી ગયા.

તૂફાન માંથી કશ્તી બચાવી લાવનારા એવા ધણા,
છે જેમના વહાણ કીનારે આવી જ ડૂબી ગયા.

મોસમ ની મહેર હોય તો હેલી આવી ચઢે છે ઘરમાં,
અમારા જેવા તો કૈં કીન્તુ ભર વરસાદે પણ કોરા રહી ગયાં.

હજારો લાશો ને મ્ંઝીલ સુધી પહોંચાડી હતી 'મક્કુ' પરંતુ,
ખુદ અમારાં જનાજા ચાર કાંધા ના મહોતાજ રૈ ગયા.....

----ભાવેશ 'મક્કુ'
----------------------------------
દુઃખમાં રડી લેવાની પણ મઝા અનેરી હોય છે,
હારેલી જીંદગી જીવવાની પણ મઝા અનેરી હોય છે.

કીનારા પર વહાણ હંકારનારાઓ તમને શું ખબર,
તૂફાન માં કશ્તી ગુમાવવાની પણ મઝા અનેરી હોય છે.

તમામ ઉમર જેને પામવાની તડપ હોય પરંતુ,
તેને મેળવીને ગુમાવાની પણ મઝા અનેરી હોય છે.

બે હાથ વડે ઝીંદગી ઉલેચનારાઓ એટલું પણ જાણો કે,
છેલ્લા શ્વાસે હથેળી ખાલી જોવાની પણ મઝા અનેરી હોય છે.

એક વાટ પકડી ને ચાલનારાઓ મંઝીલ જરુર પામે છે,
કીન્તુ માર્ગ માં ભટકી જવાની પણ મઝા અનેરી હોય છે.

દુનીયા જીતનારા ઘણાં સીકંદરો ભૂલાઈ ગયાં 'મક્કુ',
એક-બે ના દીલ જીતી ચાલી જવાની પણ મઝા અનેરી હોય છે...................

--ભાવેશ 'મક્કુ'
--------------------------
પાંદડું કેવી રીતે પીળું થયું કોને ખબર ?
એટલે કે ઝાડમાંથી શું ગયું કોને ખબર ?

શહેર પર ખાંગી થઈ વરસી પડી આખી વસંત,
એક જણ નખશીખ ઉજ્જડ રહી ગયું કોને ખબર ?

શાહીમાંથી આમ કાં ઢોળાય છે તારાં સ્મ્રણ્ ?
એને મારું એક મન ઓછું પડ્યું ? કોને ખબર ?

સ્વપ્નમાં વહેતી'તી નહેરો તારા ચહેરાની સત્ત,
ને સવારે આંખમાંથી શું વહ્યું ? કોને ખબર ?

માછલીએ એકદા જળને પૂછ્યું ઃ તું કોણ છે ?
એનો ઉત્ર શોધવા જળ ક્યાં ગયું, કોને ખબર ?

મેં અરીસાને અમ્સ્તો ઉપલક જોયો, 'રમેશ',
કોણ એમાંથી મને જોતું રહ્યું, કોને ખબર ?

---રમેશ પારેખ
------------------------------------------

ચૂમી છે તને -

ગીતના ઘેઘૂર ગરમાળામાં ચૂમી છે તને,
બે ગઝલની વચ્ચેના ગાળામાં ચૂમી છે તને.

પર્વતો પાછળ સવારે, ને બપોરે ઝીલમાં,
સાંજ ટાણે પંખીના માળામાં ચૂમી છે તને.

સાચું કહું તો આ ગણિત અમથું નથી પાકું,
બે ને બે હોઠોના સરવાળામાં ચૂમી છે તને.

કાળી રાતોમાં છુપાઈને ગઝલની આડમાં,
પાંચ દસ પંક્તિના અજવાળામાં ચૂમી છે તને.

લોકોએ જેમાં ન પગ મુકવાની ચેતવણી દીધી,
પગ મૂકીને એ જ કુંડાળામાં ચૂમી છે તને.

પાંપણો મીંચાય ને ઉઘડે એ પલકારો થતાં,
વાર બહુ લાગી તો વચગાળામાં ચૂમી છે તને.

-મુકુલ ચોકસી
---------------
નદીની રેતમાં રમ્તું નગર મળે ન મળે,
ફરી અ દશ્ય સ્મ્રુતી પટ ઉપર મળે ન મળે,
ભરી લો સ્વાસમાં એની સુગંધનો દરીયો,
પછી આ માટીની ભીની અસર મળે ન મળે,
પરીચીતોને ધરાઈને જોઈ લેવા દો,
આ હસતા ચહેરા; આ મીઠી નજર મળે ન મળે,
ભરીલો આંખમાં રસ્તાઓ, બારીઓ, ભીંતો,
પછી આ શહેર, આ ગલીઓ, આ ઘર મળે ન મળે,
વતનની ધૂળથી માથું ભરી લઉં આજ અહીં,
અરે આ ધૂળ પછી ઉમ્રભર મળે ન મળે,
વળાવા આવ્યા છે એ ચ્હેરા ફરશે આંખમાં,
ભલે સફરમાં કોઇ હમસફર મળે ન મળે,


રડી લો આજ સંબંધોને વીંટળાઈ અહીં,
પછી કોઇને કોઇની કબર મળે ન મળે,


--આદીલ મન્સૂરી
-----------------------
ઘણાં વરસો પછી આવ્યા છો એનો એ પુરાવો છે,
જે મહેંદી હાથ ને પગ પર હતી એ કેશ પર લાગી છે..............
-----------------------
માછલી સાથે જ દરીયો નીકળ્યો,
લ્યો ઋણાનુબંધ પાછો નીકળ્યો.

હુંજ મારા ભાર થી થાકી ગયો,
હું હતો એ 'હું' જ ખોટો નીકળ્યો.

ચાંદની સમજી અમે મુઠ્ઠી ભરી,
મૂઠ ખોલી ત્યાંજ તડકો નીકળ્યો.

સાંજ પડતાંયે ફર્યુ ના એટલે,
શોધવા પંખીને માળો નીકળ્યો.

આશરો કેવળ નદીને જ હતો,
એક સાગર એય ખારો નીકળ્યો.

આગીયાઓ ઉજળા છેકે પછી-,
વેશ બદલી સૂર્જ ઊડતો નીકળ્યો.

થોભવાનો થાક વસમો હોય છે,
માર્ગ સમજ્યો એ ઉતારો નીકળ્યો............................

----ધૂની માંડલીય
------------------------------
લીધો છે જન્મ પ્રેમ મેં કરવા બધાંની સાથ,
એમાં જરાક આપ વધારે ગમી ગયાં........
-------------------------------
આવ મારી જાત ઓઢાળુ તને...
સાહેબા, શી રીતે સંતાડુ તને...

ઘર સુધી તુ આવવાની જીદ ના કર...
ઘર નથી, નહીતર હું ના પાડુ તને?
-------------------------
મને એ જ સમજાતું નથી કે આવું શાને થાય છે.
ફૂલડાં ડૂબી જતાં ને પથ્થરો તરી જાય છે.

ટળવળે તરશર્યાં તારાં જે વાદળી વેરણ બને.
તે જ રણમાં ઘૂમ મુસળધાર વરસી જાય છે.

ઘર-હીણાં ઘૂમે હજારો ઠોકરાતાં ઠેર ઠેર
ને ગગન-ચુમ્બી મહાલો જનસૂનાં રહી જાય છે.

દેવડીએ દંડ પામે ચોર મૂઠી જારના:
લાખ ખાંડી લૂંટનારા મહેફિલે મંડાય છે.

કામધેનુને જડે ના એક સૂકું તણખલું
ને લીલાંછમ ખેતરો સૌ આખલા ચરી જાય છે.

છે ગરીબોના કુબામાં તેલ ટીપુંય દોહ્યલું ?
ને શ્રીમંતોની કબર પર ઘીના દીવા થાય છે.
--------------------------------------------
સમય જાતાં બધું સહેવા હૃદય ટેવાઇ જાયે છે
ગમે તેવું દુઃખી હો, પણ જીવન જીવાઇ જાયે છે.

હૃદયના દર્દની વાતો કદી છાની નથી રહેતી
હૃદય ગભરાય છે ત્યારે નયન ભીંજાઇ જાયે છે.

સમય બદલે તો બદલે, પણ પ્રણય રંગો નહીં બદલે
હૃદય રંગાઇ જાયે છે તો બસ રંગાઇ જાયે છે.

મુસીબતના દહાડા એ કસોટીના દહાડા છે.
છે પાણી કેટલું કોના મહીં જોવાઇ જાયે છે.

જીવન સારું જીગરની આહ થી ફૂંકી દઉં ‘ઘાયલ’
કદીક મારા ઉપર મને ય એવી ખાઇ જાયે છે.

- અમૃત ઘાયલ
-------------------------------------
સારું છેે એની સાથે કશી ગુફતગુ નથી,
નહીંતર હું કંઈક ભુલ કરત બોલચાલમાં.
કરતો હતો જે પહેલાં તે પર્સતાવના ગઈ,
લઈ લઉં છું એનું નામ હવે બોલ્ચાલમાં.
એ 'ના' કહીને સહેજમાં છુટી ગયા 'મરીઝ્',
કરવી ન જોઈતી'તી ઉતાવળ સવાલમાં...........
------------------------------------------
લેવા ગયો જો પ્રેમ તો વહેવાર પણ ગયો,
દર્શનની ઝંખના હતી, અણસાર પણ ગયો.

એની બહુ નજીક જવાની સજા છે એ,
મળતો હતો જે દૂરથી સહકાર પણ ગયો.

રહેતો હતો કદી કદી ઝુલ્ફોની છાંયમાં,
મારા નસીબમાંથી એ અંધકાર પણ ગયો.

સંગતમાં જેની સ્વર્ગનો આભાસ હો ખુદા,
દોઝખમાં કોઈ એવો ગુનેગાર પણ ગયો ?

એ ખુશનસીબ પ્રેમીને મારી સલામ હો,
જેનો સમયની સાથે હ્રદયભાર પણ ગયો ?

એ પણ છે સત્ય એની ઉપર હક નથી હવે,
એવુંય કંઈ નથી કે અધિકાર પણ ગયો.

સાકી છે સ્તબ્ધ જોઈ નશાની અગાઢ ઊંઘ,
પીનારા સાથે કામથી પાનાર પણ ગયો.

કેવી મજાની પ્રેમની દીવાનગી હશે !
કે જ્યાં ‘મરીઝ’ જેવો સમજદાર પણ ગયો.
------------------------------------------------
િલ મા કોઇની યાદ ના પગલાં રહી ગયા,
ઝાંકળ ઊડી ગયું અને ડાઘાં રહી ગયા.

એને મળ્યા છતાંય કોઇ વાત ના થઇ,
ગંગા સુધી ગયા અને પ્યાસા રહી ગયા.

ફૂલો લઇને બાગથી હું નીકળી ગયો,
ને પાનખરના હાથમાં કાંટા રહી ગયા.

વરસ્યા વિના જંતી રહી શિર પરથી વાદળી,
‘આદિલ’ નજર ઉઠાવીને જોતા રહી ગયા.
-----------------------------------------

Lion's Hunger

Here goes yet another puzzle, not as good as the one with the thieves.


Problem
------------

In a zoo far far away ( I am being a little dramatic, eh? :D ), there was a cage filled with n lions. One day the care taker of the zoo put in only one huge meat loaf in the cage. If any lion eats the meat, he will feel dizzy and will fall asleep. Now, that the lion has fallen asleep, he would serve as meat for other lions. Also, assume hypothetically that all lions are intelligent, so none of them would want to get killed.

If you are one of the lion and given an option to eat the meat, would you go for it??


Solution
-----------

Like many of the interesting problem in mathematics, this can be solved using the principle of mathematical induction.

If you are the only lion in the cage, you can go ahead and have your food.

If two lions are there, none of them would eat. why?? Because, if any one of them eat the meat then he is going to be killed by the other lion.

What if three lions are there? you know that if you eat the meat, you will fall asleep. Though you will be as good as meat for other two lions during your slumber, none of them would eat you for the reason stated above.

It is easy to generalize and see that you can have your meal if odd number of lions (including yourself ) are in the cage. For the case of even number of lions, it is better to stay hungry :p.

આવ મારા આંસુની ચમક આપું તને ..

Hi,
Found this nice poem in the "about me" section of rushi's Orkut profile.
------------------------------
આવ મારા આંસુની ચમક આપું તને ..
તું મને જોઇને બહુ ઝાંખી રીતે મલકાય છે .. ..
•.¸¸.•♥´¨`♥•.¸
મદમસ્ત એવી ચાલ ચાલ ના ,
કેટલાય મુસાફરોની મંઝીલ બની જઇશ ..
સંભાળીને રાખ તારા કાજળભર્યા નયન ,
બેફામ વરસ ના , કાતીલ બની જઇશ ..
આ રીતે ઝુલ્ફોને હાથોથી પસવાર ના ,
કેટલાયે શાયરોની ગઝલ બની જઇશ ..
આટલું ધ્યાન દઇને ગઝલ વાંચ ના ,
કોઇના પ્રેમમાં પાગલ બની જઇશ .. ..
█▓▒░
તું નથી આ સુરના શણગારમાં ..
તું નથી આ શબ્દના આકારમાં ..
ક્યા નજાકત તારી ને , ક્યા આ જગત ..
સાચવું તેથી જ તને ધબકારમાં .. ..
•.¸¸.•♥´¨`♥•.¸
ટોળે વળે છે કોઇની દીવાનગી ઉપર ..
દુનીયાના લોકો કેવા મીલનસાર હોય છે .. ..
█▓▒░
વાત મારી નીકળી તો હશે ..
સાંભળી પાંપણો ઢળી તો હશે ..
મૌન પાળ્યું હશે છતાં "ઘાયલ" ..
આહ આંખોમાં સળવળી તો હશે .. ..

Honour among thieves???

Hi All,
Seems I have been too frequent in posting on my blog now a days. Thanks to my friends Sanjeet, Pranjal, Ashok ... with whom I discuss interesting problems. Just like my previous post, this post is also regarding a technical interview question asked in some company. Anyways, coming directly to the point.

Problem
-----------
There are five thieves T1, T2, T3, T4 and T5. They robbed 100 gold bars from a bank. For dividing the gold bars they came up with following idea.

- Starting from T5 to T1, a thief T_i will come up with a scheme to divide the gold bars amongst the thieves.
- Voting will happen in favour or against this scheme. If Majority ( Strictly greater than 50 % ) votes in favour then the division will happen according to the scheme. If not, then T_i will be killed and it will be T_i-1's turn to come up with a scheme.

Please keep in mind that
1) All thieves are intelligent.
2) All are very greedy, so they would try to get as much wealth as possible.
3) They all would like to kill as many thieves as possible. Of course, this motive stands at a lower priority level as compared to their greed for the gold.

If you are T5, what scheme would you come up with? Obviously, your motive would be to survive but try to come up with a scheme where you will get away with as much gold as possible.
PS:- Smallest unit of division is a gold bar. A bar can not be further divided.

-----
Solution
----
The answer is that if you are T5, you can get away with as much as 97 gold bars and still survive!!! Puzzled!! Read further to discover how.

Let's try to situation one by one from thieves perspective.

If T1 is the only person left, he will take all the gold bars.

If T1 and T2 are the only persons alive, no matter what scheme T2 comes up with, he is going to be killed and T1 would take everything. Because T2 can not get the majority ( > 50% ). Obviously, T2 would do anything to keep T3 alive.

T3 knows that T2 is going to support him no matter what scheme he comes up with. T3 can take away all 100 gold bars as he will have the majority no matter what. ( T3+T2 = 66% votes ). Obviously, T3 would like T4 to get killed so that he can take everything.

T4 knows that T3 would want him to be killed. If T4 is killed, T1 and T2 would not get anything. So T4 would give one gold bar to T1 and T2 each. Now, T4 will get the majority ( T1 + T2 + T4 = 75%) and he can take as much as 98 gold bars.

You are T5. If you get killed, you know that T3 would not get anything. So to take T3 into confidence you will give him a gold bar. If you get killed, T1 and T2 each get a gold bar. As you want to optimize the amount that you can get away with, you would give one of T1 or T2 2-gold bars. You can get away with as much as 97 gold bars!!!

Young Tableau

Hi All,
The other day me, sanjeet, and pranjal were discussing a few questions ( or puzzles ) which are likely to be asked in technical interviews. One of the question that was asked to someone in google was about finding out a specific element in an n x n Young Tableau.

Let me first define, what a young tableau is. It is an m x n array with the following property.

for all j = 1 to n-1, A[p][i] <= A[p][i+1]
and for all , i = 1 to m-1 , A[i][q] <= A[i+1][q] It is easy to see that following statement holds for a young tableau.

1. For any sub-matrix of a young tableau, the top-left element is the smallest element within that sub-matrix.
2. For any sub-matrix of a young tableau, the bottom-right element is the largest element within that sub-matrix.

Now, the problem is to find out a given element within an n x n young tableau.

----
Method -1
----

Start with the top-right element of the tableau. Compare this element e with the element to be found x.
if e > x then
discard the column in which e appears. ( Because e is the first(smallest ) element of that column.
else
discard the row in which e appears.
end if.
Repeat this exercise until the element is found or the tableau is exhausted.

It is easy to see that time complexity of Method-1 is O(n). As at every step we will discard either row or column which will take at most 2n steps.

---------
Method - 2
---------
Do a binary search over the diagonal of the tableau. If we find the desired element x then we are done. If not, we will have two element u and v where u <> u is the bottom-right element and v is the top-left element. The elements that we will discard at each step would be at least half of the elements in the original matrix.
Here is why,

i^2 + (n-i)^2 function is minimum where i=n/2. With i=n/2 the value of the function is (n^2)/2.

Now, if we do the analysis with respect to number of elements.
T(n^2) = 2T((n^2)/4) + logn

or

T(m) = 2T(m/4) + 0.5 logm

Solution of this recurrence, turns out to be O(m^(0.5)) = O(n). So, there is no improvement over the complexity as compared to the first method. Besides, this second method fails when the sub-matrices that were discarded were not square. In which case, the remaining two sub-matrices will not be square either.
----
Method 3
------
Compare the central element e with the desired element x.
if e > x then discard the bottom-right quadrant of the tableau.
else discard the top-left quadrant of the tableau.

Now , we are left with three sub-matrices of the size n/2 x n/2.

The recurrence would be

T(n) = 3T(n/2) + O(1).

Solving it would give us n^(log_2 3) = n^1.585. It turns out that even though in Method-1 you discard n elements and in this method you discard (n^2)/4, the complexity does not favour Method-3. Anyways, it was a good exercise to do this analysis.

Necklace puzzle - yet another solution

Hi all,

I am posting here another solution to "Necklace Puzzle". The solution is by my friend Vaibhav Gupta

-------

Let A and B are the 2 necklaces with N gemstones. A and B has three types of
gemstones which are equal in number.

A = A[1] A[2] ... A[N]
B = B[1] B[2] ... B[N]

Where A[i] is the ith gemstone in Necklace A.
B[i] is the ith gemstone in Necklace B.

Let Color(A[i]) represents the type of the gemstone A[i].

We construct a bipartite graph G = (X,Y,E), with the following condition:

For each gemstone A[j] in A we create a node X_j in X. So |X| = N
Foe each gemstone B[j] in B we create a node Y_j in Y. So |Y| = N
E is the edges set from node in X to node in Y.

E = { (u,v) | u \in X and v \in Y and Color(u) = Color(v)}

|E| = (N^2) / 3 since each node has exactly N/3 edges.

We define weight to each edge in E:
Weight(e) = orientation of the string.
OR Mathematically
Weight((X_i,Y_j)) = i - j if i>=j
= N+i-j otherwise

0 <= Weight((X_i,Y_j)) <= N-1 since 1<=i<=N, 1<=j<=N So there are N possible values of weight.

Now we just need to prove that there are atleast N/3 edges of same weight.
This can be proved by pigon hole principle. There are (N^2) / 3 edges and
each edge has N possible values of weight so there must exist a set of
ceil(|E|/N) edges of same weight

|E| / N >= N/3

Hence proved.

For general case :

For 3 gemstone types
( a^2 + b^2 + c^2 ) / (a + b + c)

Where a is the number of gemstone of type 1.
b is the number of gemstone of type 2.
c is the number of gemstone of type 3.

For m gemstone types:
(N_1^2 + N_2^2 + N_3^2 ... + N_m^2) / (N_1+N_2+N_3 ..+N_m)

where N_i is the number of gemstone of type i.

---------

Quote by John Von Neumann

"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is"
-- John Von Neumann

I saw this quote as saket's status message in google talk.

Necklace Theorem - Solutions to puzzles

Hi All,
So I am back again after some gap. This post will describe the solutions to the two puzzle that I posed as part of my prequel post "Necklace Theorem". For the sake of clarity I am copying the puzzles again over here.

1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.
As shown in the figure on the left, let us consider a baseline B. The circle represent the point set we are interested in. Refer to the prequel of this post and convince yourself that it is possible to have a line in any given direction which divides the point set into two equal half. Hence, it is also possible to have two orthogonal lines both of which will divide the point set into two equal half. ( When I say, two equal half, I mean that division in two portion satisfying the constraint "less or equals n/2" ). As both p and q divides the point set into two equal half, the region which is captured on top-left and bottom-right will be equal ( call it x, or to be more precise "less or equal x" ). Similarly, tom-right and bottom-left would be equal ( call it y). Let us have a function f(x,y) = (x-y) = v. By rotating p and q , 90 degrees we will have function value exactly negative, as x and y would swap their places. From intermediate value theorem we can argue that there will be a configuration where x = y = n/4.

2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.

With respect to the baseline B, we can have two lines p and q, each dividing the point set into equal half and region trapped as shown in figure would be equal to n/6 on each side. ( n/6 is written outside the circle to make it readable ). Now, as shown in the prequel post, we can have a line r which will divide the two point sets ( each of size n/3 ) into two equal half. This line r need not be concurrent with p and q. Let the triangle trapped between these three lines is equal to A. As we rotate this configuration 180 degree the area will become -A. Again, from intermediate value theorem we can state that area will be 0 at some configuration making r concurrent to p and q. Thus, each segment will have size n/6.