Math Prize for Girls Olympiad P4

I loved this question from the math prize for girls. Here it is and my solution:

A lattice point is a point in the plane whose two coordinates are both integers. A lattice line is a line in the plane that contains at least two lattice points. Is it possible to color every lattice point either red or blue such that every lattice line contains exactly k=2017 red lattice points? Prove your answer is correct. 

At first I thought the answer is no! It’s easy to prove that if k=1 then it’s impossible: assume such a coloring exists, by construction, every lattice line contains exactly one red lattice point. Choose two red lattice points on separate lines and draw the line containing them—you now have a lattice line containing at least two red lattice points.   —><—

Next, I tried to construct a coloring for k=2 and prematurely convinced myself it wasn’t possible. A day later, with the problem still fresh in my mind I kept thinking about maybe proving the problem via induction, but was troubled by the fact that it doesn’t hold for the base case k=1!

Unconvinced about the answer being no, I kept thinking that the case k=1 is somehow special, and that the real base case starts with k=2. In hindsight this is obvious, but it took me a bit to see it. The case k=1 is special because one lattice point does not uniquely determine a line; infinitely many lattice lines go through any one lattice point. For every other k, we have that the k lattice points uniquely determine the line through them. So maybe the answer is yes for all k > 1.

I couldn’t imagine a way to explicitly generate the coloring so I convinced myself that to prove it’s possible we have to do it via induction. For this we need to be able to enumerate all possible lattice lines. In order to do this we need to show that the set of all lattice lines in R^2 is countable. Basic properties of countability tell us that all pair of integers are countable, and all pairs of pairs of integers, and thus all lattice lines since each one can be specified as a pair of pairs of integers.

Great, so since the set of all lattice lines is countable then we can enumerate all lattice lines as L:={l1, l2, l3….}. Next thing I noticed is that any lattice line must necessarily contain an infinite set of lattice points on it. * We now construct the desired coloring:

  1. Start by coloring each lattice point blue.
  2. At each step t in {1,2,3,…} we will recolor a finite number of the lattice points red. At each step t, we will also partition L into two disjoint sets S1 and S2:                         S1:={l1,l2,…,l(t-1)} and S2:={l{t}, l(t+1),…} (for t=1 S1 is empty). So that at step t>1 each line in S1 contains exactly 2017 red lattice points and each line in S2 contains at most 2017 red lattice points. Note that at step t there are a finite number of red lattice points on the lattice plane, hence there a finite number of lattice lines which contain at least two red lattice points. So that the set of lines with exactly 2017 red lattice points is also finite. Let F be the finite set of lines with exactly 2017 red points. Look at line lt, and note that every line in L (except lt) intersects it in at most one point. Let I be the finite set of points which are intersection points between lt and a line in F. Because I is finite and at most 2017 points of lt are red, there are infinitely many lattice points on lt that are neither in I nor currently red. Recolor up to 2017 of these points red until lt has exactly 2017 red lattice points.
  3. We prove that we can repeat the previous step for every step t. We proceed by induction:
    • The base case t=1 holds since by construction we start with the all-blue coloring.
    • Suppose that the procedure is possible for step t.
    • Consider step t+1, since every line except lt itself intersects lt in at most one point, every line except lt will gain at most one red point during time (t+1). By construction, at step t+1 the lines in S1 will still each contain exactly 2017 red points, and lt itself will have exactly 2017 red points before we move onto step (t+2) (by appropriate recoloring). Whereas every line in S2 at step (t+1) will have at most 2017 red points before we move onto step (t+2) (since we don’t recolor any lines in S2 which already contain exactly 2017 red points), completing our proof by induction.

By taking this process to its limit, i.e., repeating for infinitely many steps, we get the desired coloring of the lattice plane.

Q.E.D.

Note how the ability to enumerate all lattice lines allows us to construct such a coloring via an abstract but systematic process. Approaching this problem by trying to explicitly color the plane makes it much harder to tackle!

*By contraction, assume that there is some lattice line with finitely many lattice points. Choose the two lattice points with the smallest distance and construct the right-angled triangle containing these two points as vertices. By replicating this triangle in both directions along this line, by similar triangles, we can show that repeating vertices are all lattice points and infinitely many of them lie on the line. —><—

Thank you to Ken Fan at Girls’ Angle for initially pointing out that the induction cannot be done on the lines in set L. Can you see why not?

 

 

 

 

 

Advertisements

The Matrix and Meditation

I think people that know about this will agree that the mind cannot be located in the brain. Given my own model of how we interact with reality I find this to be true. I think the mind is outside of us, basically like some kind of space-filling invisible substance which embeds information, and we connect and interact with it in ways which are not clear. The mind—one mind really—is readily available for each of us to plug into it. We don’t possess mind; it was here before us and it will be here after us, but we do interact and possibly alter it.

Each of our brains is unique. Our brains–as a result of our beliefs and mental models of how the universe works—can be thought of as a highly complex 3-dimensional adjacency matrix which can be mapped onto neural synapses. So that each person has their own unique matrix which embeds their own unique version and experience of reality.

This matrix is dynamic, that is it changes and updates along with our beliefs. I like to think of each matrix as gradually and consistently developing an energy cloud around it, with a unique distribution of energy for each individual. The cloud is an emergent property of the matrix itself and it varies in accordance with it’s underlying matrix.

In all of this, I think there’s some housekeeping involved on our part. The matrix–unless consciously maintained and it’s energy efficiently guided–will operate suboptimal and its connection to universal mind diminished. This is where I think meditation comes into play: we should meditate in order to properly and efficiently guide the energy in our clouds, and in order to upkeep and further enhance the strength of our signal to mind. The strength of this signal is imperative—from here we gather intuition and guidance as to how the universe operates and what our role in it is.

Meditation is gaining interest; as I think it should. We find it necessary to bathe, do laundry, clean house, and exercise. Yet, most of the world for most of history it seems has applied the same tired, dysfunctional, and outdated mind day in and day out. Nothing new or great is going to come out of such a practice. Humanity needs guidance and I think there is great help and insight waiting for us once we understand the power and help of meditation. Meditation at its core is the conscious effort of syncing our vibrations and of strengthening our matrix and its energy into a more cohesive and predictive whole. Meditation can come in as many forms as there are people and its on each of us to figure out our own best practice.

Here is the meditation app I use (developed by Sam Harris whose podcast I also follow):

Waking Up Course

Hedge Funds and Income Inequality

I just got off the phone with a young hedge fund, which will remain nameless, but let’s call it HF. Below is a list of the technical questions I was asked.

Round 1: 15 seconds to answer, and she announces when five remain and when she needs an answer:

  1. Estimate the number of reptile species in world
  2. Estimate the number of lakes in the world
  3. Estimate the GDP of beef jerky in the world
  4. What percentage of people in the USA are under twenty years old
  5. What’s the weight in kilos of a gold iphone
  6. Give numeric answer to the derivative of x^x solved at x=2
  7. Compute ln(314)
  8. Compute 4^3.8
  9. Compute E(min(Y)*max(Y)) where Y is rolling U(0,1) three times
  10. Expected number of times one has to roll a 100-sided die to get the same number twice

Round 2: 20 or 30 seconds to answer:

  1. X in [1,2,3] what is it’s standard deviation
  2. in 11. you take sum three times what is standard deviation of this
  3. E(X)=V(X)=10 what is E(X^2)

The interviewer didn’t seem like she had a solid foundation of basic math; when she asked for my thought process in 13 it took forever to explain to her that Var(x) = E((X-E(X))^2)…maybe I should have started to count down.

It’s so easy to rip apart this interview process and the company that uses this as a screener; so let’s not do that especially since the kind of people of who can succeed in this interviews is very parallel to the kind of people who could become filthy rich. Maybe even, let’s play devil’s advocate and say that this process actually is incredibly efficient at filtering out for the best traders, quants and developers, and these incredibly talented people (as determined by this interview process) go on to make themselves and the company founders insanely rich.

A subset of the next generation of super wealthy Americans will undoubtedly come from places like HF. So, what kind of people thrive in such places? For one thing, I can see an autistic savant totally nailing this interview. Nothing at all against autistic savants–or any group of people for that matter, but it’s interesting to carry things out and examine any implications about society and its makeup in this setup.

People who aren’t questioning the underlying machinery too much, but are calculation and estimation machines–programmers included– may gain a huge monetary advantage by such institutions. Scientists with a penchant for more careful, methodical, slower thought processes will be penalized. The existence of companies that reward fast and competitively timed thinking skews the representation of power: a talented math undergraduate with the right pedigree is much more likely to try and game the hedge fund system than pursue a career as a high school physics teacher, for example. The top of a teaching career—money-wise and power-wise—is not really nearly as attractive. Now, I’m picking on hedge funds because it hits close to home and paints a striking picture, but the analogy holds across institutions and careers. Just think about silicon valley, medicine, lawyers etc…

In a world where incentive structures are completely skewed, we create vastly suboptimal social structures and as a result people’s life energy is hugely underutilized. In order for people to better use their energy, and thus to create a more vibrant and productive society, we should heed the words of Joe Campbell and follow our bliss. This is already very difficult to do and is made harder still by competing monetary incentives.

I’m all for capitalism—but capitalism predominantly for the service of people and communities—not for sheer blind profit.  What if we re-imagined payouts in every career: so that, for example, it’s possible for an inner-city teacher to make as much money as a very successful lawyer if she were amazing at her job. And to generally have enough power and visibility to be able to reform education.

Generally, for any job, there should be some mean level of income, but the distribution of pay should have fat tails skewed to the right, so it’s possible to make a very large amount of money if one is a total out-performer at their job. The range of the means of these distributions should also be much more narrow: so people work in what resonates most with them and the influence of money and power is subdued. In addition, there should be nets in society—besides for a failure in societal and institutional organization and optimization—there is no reason to still have the level of poverty we see in the bottom ten or twenty percent.

We have enough resources to afford a very good life for all, we just haven’t given enough resources or thought to the problem. I don’t want to live in some Ayn Rand inspired sheltered  and cut off community. Where the “best and the brightest” have to protect themselves from lesser mortals—militia style. It’s much better for everyone if we step back, re-imagine society by starting with an understanding of the fact that a diverse representation in the upper echelons of society forms the backbone for a much stronger—and happier— organism.

The Future is Female

I was jogging along the Hudson river–just outside of my apartment–and saw a woman wearing a white t-shirt with bold black letters which read: the future is female. I agree and hope–to a specific extent– that this is the case.

My mind instantly traveled back to my teenage years when I was struck by the male-dominated intellectual giants of history; where are all the women?

Then I had a baby.

It’s been ten months since Max was born and I’ve had a taste of what being a woman entailed for almost all women for almost all of history: no time at all to oneself. Even if women were educated in the same way as men, nurturing children is all-consuming and an art in itself. Add to this: housework, cooking, laundry and being the primary emotional provider to one’s family, there’s little if any stamina left for the rigorous, systematic development of ideas which are a prerequisite for any progress. The great women of history are only indirectly visible in the great men of history, whose minds and hearts they molded to reflect the burning, unmanifested, piercing insight and spirit within them.

I recalled Tesla’s biography, where he says that his genius is a direct inheritance of his mother’s. For it was his mother–a restless tinkerer and inventor of all sorts of gadgets and household appliances–who inspired him to think of the unthinkable and to then bring it to life. Surely history has no recollection of this woman.

So why should the future be any different?

Economics. For the first time is history women are being given the opportunity to financially support themselves and their families. The consequences of this are huge: women are now given the opportunity to mold themselves and their futures as they wish. Their existence and survival are no longer byproducts of outside forces. Surely, raising a family is still difficult, but progress in ideas is possible with sufficient imagination, help, and financing. In this way the influence of women’s imaginative and intellectual creations on the future will be greater than at any prior time.

But, there’s another way I hope the future is female: in the predominance–or at least the proper incorporation–of feminine principles such as love, intuition, inner strength, and community. The world is at an evolutionary crossroads, the next century can either repeat the immense heartache, violence, and shortsighted patriotism and dogma of the 20th century–or it can achieve unprecedented progress via understanding and the incorporation of a more feminine approach: one which understands the immense potential in a newborn, a potential which can only be realized via unconditional love, support, and community. One which also realizes that in a sense we are all infants–humans in progress. In at least this capacity, hopefully the future is female.

Why Startups Fail

There are many reasons. Here is my experience:

  1. Greed. Don’t start something motivated by ego and/or monetary gain. The things which feed ego and greed usually work against long-term success and sustainability. This is true in life and in business.
  2. Don’t use people. This is especially true for very early stages where each person is critical to success. The clearer you are about the value-add of an early-on individual and what their responsibilities are, the better off everyone will be.
  3. Paranoid culture. If employees feel like there’s always someone looking over their shoulder, or if employees are directly compared to one another, rest assured the company is headed towards doom.  Such an environment stifles the mind and body. True progress is never a byproduct of paranoid cultures.
  4. Lack of transparency and trust. If I don’t know why decisions are made, or how my work effects the bottom line or the overall vision of the company, I’m going to be unhappy. The only way lack of transparency is okay–and only for short periods of time–is if there is intense trust between coworkers and upper management. I.e., if I can rationalize not understanding the motivation behind a decision by feeling that it’s in my best interest. But this will only fly for a short time, eventually transparency has to be the rule rather than the exception.
  5. Wrong hires. I don’t care how qualified someone is; if she doesn’t complement the current skills of the team, and if her intentions don’t meaningfully align with the company’s–trouble will ensue. Hire the right people, not just categorically smart people. Also, intentions matter—all around.

What other factors play an important role in preventing/expediting failure? Please share below.

 

Women and Startups

I restrict the word startup to a newly founded business in either technology or the hedge fund space.

Many startups are headed by very young men—most under thirty or in their early thirties. Most startups also employ a disproportionate number of males. I want to examine, a) why this is the case, and b) given that this is the case, it takes an exceptionally wise and insightful leader to successfully retain female employees as early hires.

In prior times, a different argument could be made as to why females were almost never the head of companies, but in today’s age, even though things are changing (albeit slowly, like most change), the vast majority of startup founders are male. This is even more the case in areas such as technology and hedge funds– the space I’m in–and the ones I’d like to focus on. One reason people give for this is that it’s a ‘numbers’ game’: there’s a disproportionate number of top male engineers when compared to female ones and this is thus reflected in the disproportionate number of male founders. Another, is that by their late-twenties or early thirties, males and females have different motivations and goals.

Let’s tackle the first reason. Even though there may be (slightly) more top male engineers*, the proportion of male engineers to female ones is still not at all accurately reflected in the proportion of the gender of startup founders–we should still see more female founders. A more compelling argument points to the second reason and boils down to biological differences. One treads dangerous waters when an argument about the differences between the sexes is attributed to the immutable laws of biology, but although biological differences exist, the differences in outcome can be greatly balanced via environment: women thrive in different environments than men do, and right now the startup culture greatly favors men. Let’s explore this in more detail.

Women of a certain age feel they have much more at stake then men of the same age. So the intrinsic risk of a startup is multiplied for women since we feel that we are also sacrificing aspects of family creation and development in pursuit of business success. Even if a young woman thinks she can “do-it-all” the physical demands of pregnancy and child rearing fall disproportionally on women. These things will almost certainly eat away at stamina–a key attribute of any successful startup founder.

Add to this the cultural evolution of many male-dominated startups into fraternities. After long hours at the office it becomes almost standard to go out and drink or fraternize in other ways. Such behavior goes to implicitly reinforce the “all-in” attitude pervasive in start-ups, so that if one’s not partaking in all activities then this is seen as a lack of commitment to the team and goal. For me this holds little appeal. At the end of a productive day, I’d much rather go home, do some yoga or go for a walk, and spent time with my family. If you add kids to the equation, I’d rather spend time raising and being with my kids than fraternize. Such preferences or downright obligations definitely make it seem that women don’t have the right attitude or commitment to start-up life.

There are also deeper psychological reasons. For one, I think when women succeed we are much more likely to attribute it to hard work rather than talent. So that if a woman is at the top of her class or field, she will think that she just works harder, missing out on the fact that everyone is working hard, if she has succeeded at that level it is most likely because of talent.

One can ask why haven’t a bunch of smart women gotten together and started their own startup on their own terms? This probably will happen in the future, but I suspect the reason for this right now is two-fold:

1. Many barriers to entry for women, some of which have already been explored here.
2. Women tend to take relationships more seriously and personally than men–even business relationships. A man can more easily work with another man he does not personally like, and he can more readily segregate business life from personal life. Women tend to have a harder time doing so. We take relationships more seriously and tend to extend the public into the personal more. If a woman dislikes another woman she finds it more difficult to put aside her personal feelings and work at a strictly professional impersonal level. I suspect this psychological difference has attributed to the historical lack of corporate and institutional organization in women.

The barriers to entry are complex and varied. How do we change culture to better favor women? How do we level the playing field to create a more egalitarian environment?

I’ll leave exploring an answer to this for another post, but I suspect a solution includes exploring something Einstein had been attributed with saying. Something along the lines of:

Everyone can live a much better life if only organization caught up with scientific progress. I strongly agree.

* Top Engineering Program Statistics

Response to the New York State Common Core Math Curriculum

To Whom It May Concern (New York State Common Core Administrators?),

Upon returning from a walk, I found my doorman speaking on the phone with a very concerned and frustrated tone. With little instigation on my part, he approached and showed me a math problem, the nature of which I have never seen before. His six-year-old son had been stuck on such problems for the previous three hours and my doorman and his mother were trying to help him to no avail. As I looked as the problem, I kept reading and rereading the problem with the eager hope that each subsequent reading would reveal something new to me about what it was asking, but my efforts proved useless. The picture and “math sentence” at the bottom only added to my confusion, and served no purpose to my understanding whatsoever.

After 10 minutes, with my husband’s (MIT dual degrees in Math and Computer Science) joined efforts, and numerous internet searches, we came up with what we could only guess was an acceptable “solution”. I write this letter, not so much out of anger which would ultimately serve no purpose, but more so out of SERIOUS concern for what and how our children are being educated. If we turn something which has been around for millennia and serves as the most basic building blocks of modern society into something obscure, difficult, and frustrating, what can we expect further down the road? The primary goal of an educator, especially at this level, is to instill a love of learning in his/her pupil and to make the wonders of the universe more transparent not more opaque. Surely, the Gausses, Newtons and Einsteins of this world evolved from a very different medium of learning and education.

Please reconsider your methods of education. Basic addition and subtraction, in whatever method you choose to teach them, should not make a mathematics PhD think 10 minutes about what the problem is asking and how “to make ten from 12-4”. The frustration and anger these kids feel now very much paints their understanding and sentiment of mathematics further down the road, when it matters even more. We need to bring as much light into math as possible, not add to the darkness, especially during such a formative and impressionable age.

Sincerely,

Doris Dobi, Math PhD