Problem

1232. Check If It Is a Straight Line

similar question

• 1037. Valid Boomerang
• 149. Max Points on a Line

Java

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    private boolean isColine(int x1, int y1, int x2, int y2, int x3, int y3) {
        int a = (y3 - y2) * (x3 - x1);
        int b = (y3 - y1) * (x3 - x2);
        return a == b;
    }

    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        boolean b;
        for (int i = 0; i < N - 2; i++) {
            b = isColine(coordinates[i][0], coordinates[i][1], coordinates[i + 1][0], coordinates[i + 1][1], coordinates[i + 2][0], coordinates[i + 2][1]);
            if (b == false)
                return false;
        }
        return true;
    }
}

Submission Detail

• 79 / 79 test cases passed.
• Runtime: 1 ms, faster than 22.67% of Java online submissions for Check If It Is a Straight Line.
• Memory Usage: 41 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.

Computational geometry method

© Copyright 2002-2020, Robert Sedgewick and Kevin Wayne.

keys

• Shoelace formula, also known as Gauss’s area formula
• vertices must listed in clockwise(or counterclockwise, increasing order of polar angle) order
• CCW: Given three points a, b, and c, is a→b→c a counterclockwise turn? Determinant (or cross product) gives 2x signed area of planar triangle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

import java.util.Comparator;
import java.util.Arrays;

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        final int N = coordinates.length;
        Point2D[] a = new Point2D[N];
        for (int i = 0; i < N; i++) {
            a[i] = new Point2D(coordinates[i][0], coordinates[i][1]);
        }
        Arrays.sort(a);
        Arrays.sort(a, 1, N, a[0].polarOrder());
        int A = a[N - 1].x() * a[0].y() - a[0].x() * a[N - 1].y();
        for (int i = 0; i < N - 1; i++) {
            A += a[i].x() * a[i + 1].y() - a[i + 1].x() * a[i].y();
        }
        return A == 0;
    }
}

final class Point2D implements Comparable<Point2D> {
    private final int x;
    private final int y;

    public Point2D(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int x() {
        return x;
    }

    public int y() {
        return y;
    }

    public static int ccw(Point2D a, Point2D b, Point2D c) {
        int area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
        if (area2 < 0) return -1;
        else if (area2 > 0) return +1;
        else return 0;
    }

    public int compareTo(Point2D that) {
        if (this.y < that.y) return -1;
        if (this.y > that.y) return +1;
        if (this.x < that.x) return -1;
        if (this.x > that.x) return +1;
        return 0;
    }

    public Comparator<Point2D> polarOrder() {
        return new PolarOrder();
    }

    private class PolarOrder implements Comparator<Point2D> {
        public int compare(Point2D q1, Point2D q2) {
            int dx1 = q1.x - x;
            int dy1 = q1.y - y;
            int dx2 = q2.x - x;
            int dy2 = q2.y - y;

            if (dy1 >= 0 && dy2 < 0) return -1;
            else if (dy2 >= 0 && dy1 < 0) return +1;
            else if (dy1 == 0 && dy2 == 0) {
                if (dx1 >= 0 && dx2 < 0) return -1;
                else if (dx2 >= 0 && dx1 < 0) return +1;
                else return 0;
            } else return -ccw(Point2D.this, q1, q2);
        }
    }
}

Submission Detail

• 79 / 79 test cases passed.
• Runtime: 6 ms, faster than 9.07% of Java online submissions for Check If It Is a Straight Line.
• Memory Usage: 38.8 MB, less than 6.80% of Java online submissions for Check If It Is a Straight Line.

Problem

832. Flipping an Image

similar question : 48. Rotate Image

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        final int N = A.length;
        final int M = A[0].length;
        int tmp;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M/2; j++) {
                tmp = A[i][j];
                A[i][j] = A[i][N-1-j];
                A[i][N-1-j] = tmp;
            }
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                A[i][j] = A[i][j]==0?1:0;
            }
        }
        return A;
    }
}

Submission Detail

• 82 / 82 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Flipping an Image.
• Memory Usage: 39.1 MB, less than 16.27% of Java online submissions for Flipping an Image.

It’s easy indeed.

Problem

905. Sort Array By Parity

Java

Two Pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int[] sortArrayByParity(int[] A) {
        final int N = A.length;
        int[] B = new int[N];
        int left=0, right=N-1;
        for(int i=0; i<N; i++) {
            if ((A[i]&1)==0) {
                B[left++]=A[i];
            }
            else {
                B[right--]=A[i];
            }
        }
        return B;
    }
}

Submission Detail

• 285 / 285 test cases passed.
• Runtime: 1 ms, faster than 99.47% of Java online submissions for Sort Array By Parity.
• Memory Usage: 40.1 MB, less than 30.13% of Java online submissions for Sort Array By Parity.

In-Place

© Solution - Approach 3: In-Place

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int[] sortArrayByParity(int[] A) {
        final int N = A.length;
        int left = 0, right = N - 1;
        int temp;
        while (left < right) {
            if ((A[left] & 1)==1 && (A[right] & 1)==0) {
                temp = A[left];
                A[left] = A[right];
                A[right] = temp;
            }
            if ((A[left] & 1) == 0) left++;
            if ((A[right] & 1) == 1) right--;
        }
        return A;
    }
}

Submission Detail

• 285 / 285 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Sort Array By Parity.
• Memory Usage: 39.6 MB, less than 30.13% of Java online submissions for Sort Array By Parity.

Problem

1154. Day of the Year

Java

my solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int dayOfYear(String date) {
        int year = Integer.parseInt(date.substring(0,4));
        int month = Integer.parseInt(date.substring(5,7));
        int day = Integer.parseInt(date.substring(8,10));
        int[] dayOfMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        boolean leapYear = ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0);
        if (leapYear)
            dayOfMonth[1] = 29;
        int dy = day;
        for (int i = 1; i < month; i++) {
            dy += dayOfMonth[i - 1];
        }
        return dy;    
    }
}

Submission Detail

• 246 / 246 test cases passed.
• Runtime: 1 ms, faster than 98.63% of Java online submissions for Day of the Year.
• Memory Usage: 37.1 MB, less than 7.99% of Java online submissions for Day of the Year.

java8 LocalDate

1
2
3
4
5
6
7
8
9

import java.time.LocalDate;
import java.time.format.DateTimeFormatter;

class Solution {
    public int dayOfYear(String date) {
        LocalDate d = LocalDate.parse(date, DateTimeFormatter.ofPattern("yyyy-MM-dd"));
        return d.getDayOfYear();
    }
}

Submission Detail

• 246 / 246 test cases passed.
• Runtime: 16 ms, faster than 6.07% of Java online submissions for Day of the Year.
• Memory Usage: 38.3 MB, less than 7.64% of Java online submissions for Day of the Year.

• Leap year
• Java program to find if the given number is a leap year?

© Career advice - What’s new - By Terence Tao

Advice is what we ask for when we already know the answer but wish we didn’t. (Erica Jong)

If you can give your son or daughter only one gift, let it be enthusiasm. (Bruce Barton)

Sports serve society by providing vivid examples of excellence. (George Will)

A college degree is not a sign that one is a finished product but an indication a person is prepared for life. (Edward Malloy)

Chaque vérité que je trouvois étant une règle qui me servoit après à en trouver d’autres [Each truth that I discovered became a rule which then served to discover other truths]. (René Descartes, “Discours de la Méthode“)

When you have mastered numbers, you will in fact no longer be reading numbers, any more than you read words when reading books. You will be reading meanings. (Harold Geneen, “Managing”)

The history of every major galactic civilization tends to pass through three distinct and recognizable phases, those of Survival, Inquiry and Sophistication, otherwise known as the How, Why, and Where phases. For instance, the first phase is characterized by the question ‘How can we eat?’, the second by the question ‘Why do we eat?’ and the third by the question, ‘Where shall we have lunch?’ (Douglas Adams, “The Hitchhiker’s Guide to the Galaxy“)

行名失己, 非士也 [One who pursues fame at the risk of losing one’s self, is not a scholar]. (莊子 [Zhuangzi], “大宗師 [The Grandmaster]”)

The three pillars of learning; seeing much, suffering much, and studying much. (Welsh triad; later attributed to Benjamin Disraeli)

Better beware of notions like genius and inspiration; they are a sort of magic wand and should be used sparingly by anybody who wants to see things clearly. (José Ortega y Gasset, “Notes on the novel”)

Every mathematician worthy of the name has experienced … the state of lucid exaltation in which one thought succeeds another as if miraculously… this feeling may last for hours at a time, even for days. Once you have experienced it, you are eager to repeat it but unable to do it at will, unless perhaps by dogged work… (André Weil, “The Apprenticeship of a Mathematician”)

Integrity without knowledge is weak and useless, and knowledge without integrity is dangerous and dreadful. (Samuel Johnson, “Rasselas”)

No profit grows where is no pleasure ta’en;
In brief, sir, study what you most affect.
(William Shakespeare, “The Taming of the Shrew“)

Worse than being blind, is to see and have no vision. (Helen Keller)

Don’t just read it; fight it! Ask your own questions, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? What happens in the classical special case? What about the degenerate cases? Where does the proof use the hypothesis? (Paul Halmos, “I want to be a mathematician”)

Know how to listen, and you will profit even from those who talk badly. (Plutarch)

It is the province of knowledge to speak and it is the privilege of wisdom to listen. (Oliver Wendell Holmes, “The Poet at the Breakfast Table”)

The best teacher is the one who suggests rather than dogmatizes, and inspires his listener with the wish to teach himself. (Edward Bulwer-Lytton)

Millions long for immortality who do not know what to do with themselves on a rainy Sunday afternoon. (Susan Ertz, “Anger in the Sky”)

Every composer knows the anguish and despair occasioned by forgetting ideas which one had no time to write down. (Hector Berlioz)

We must get beyond textbooks, go out into the bypaths… and tell the world the glories of our journey. (John Hope Franklin)

Even fairly good students, when they have obtained the solution of the problem and written down neatly the argument, shut their books and look for something else. Doing so, they miss an important and instructive phase of the work. … A good teacher should understand and impress on his students the view that no problem whatever is completely exhausted.
One of the first and foremost duties of the teacher is not to give his students the impression that mathematical problems have little connection with each other, and no connection at all with anything else. We have a natural opportunity to investigate the connections of a problem when looking back at its solution. (George Pólya, “How to Solve It“)

An education isn’t how much you have committed to memory, or even how much you know. It’s being able to differentiate between what you do know and what you don’t. (Anatole France)

I suppose it is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail. (Abraham Maslow, “Psychology of Science”)

A successful individual typically sets his next goal somewhat but not too much above his last achievement. In this way he steadily raises his level of aspiration. (Kurt Lewin)

It is not the strongest of the species that survives, nor the most intelligent, but the one most responsive to change. (Leon C. Megginson)

If I have ever made any valuable discoveries, it has been owing more to patient attention, than to any other talent. (Isaac Newton)

Think like a wise man, but communicate in the language of the people. (William Butler Yeats)

The mediocre teacher tells. The good teacher explains. The superior teacher demonstrates. The great teacher inspires. (William Ward)

An expert is a man who has made all the mistakes, which can be made, in a very narrow field. (Niels Bohr)

It is a mistake to suppose that men succeed through success; they much oftener succeed through failures. Precept, study, advice, and example could never have taught them so well as failure has done. (Samuel Smiles)

It is much easier to try one’s hand at many things than to concentrate one’s powers on one thing. (Quintilian)

When man is serene and healthy the pulse of the heart flows and connects, just as pearls are joined together or like a string ofred jade then one can speak ofa healthy heart. - Huang Ti (The Yellow Emperor) (2697-2597 BC)
Nei Ching Su Wen, Bk. 5, Sect. 18
(tr. by Ilza Veith in The Yellow Emperor’s Classic of Internal Medicine)

The final sessions of the International Heart Health Conference, held May 24 to 29, 1992, in Victoria, focused on the refinement of the Victoria Declaration on Heart Health. This declaration, along with two supporting documents (“Call for action” and “Framework for policy and action”), was prepared by the Advisory Board of the International Heart Health Conference.

The declaration was authorized by the individual advisory board members and not their respective organizations. Other contributors were the members of the Scientific and Program Committee of the International Heart Health Conference and individual participants at the conference. Readers are invited to use the declaration as their personal document to influence their professional associations and municipal, state, provincial or federal governments. However, no policy statement on cardiovascular disease can ever be complete, so complex is the field. We urge that you build upon the declaration and use it as a starting point for critical re-examination of its relevance to you, your institutions, your community and your country. We, in turn, will continue to pursue adoption of the declaration through advocacy and refinement of the recommendations as needed.

The following is the executive summary and the declaration.

Executive summary

Cardiovascular disease is largely preventable. We have the scientific knowledge to create a world in which heart disease and stroke are rare. In such a world everyone, from infant to elderly person, would have access to and would practise positive healthy living.

In most cases cardiovascular disease is brought about by some combination of the following factors: smoking, high blood pressure, elevated blood cholesterol level, unhealthy dietary habits(including excessive alcohol consumption), obesity, a sedentary lifestyle and psychosocial stress.

Healthy living includes good nutrition, a tobacco-free lifestyle, regular physical exercise and supportive environments. To implement a global policy of cardiovascular disease prevention, we must unite people and their communities with health care professionals,scientists, industry and policymakers.

From studying downward trends in cardiovascular disease in certain industrialized countries, we are learning how to reduce the toll of such disease, although it still remains a major problem.

The primary challenge now is to maintain the downward trend while assisting and encouraging countries where rates of heart disease are increasing(developing countries and those in central and eastern Europe) to prevent the epidemic from spreading.

The prescription is simple. To implement it is more difficult. The promotion of heart health on a global scale requires clear agreement on policy principles, implementation processes and the partnerships to make it happen.

The prevention of cardiovascular disease requires the prevention of the onset of risk factors in children and youth everywhere and in entire populations of countries where cardiovascular disease has not yet reached epidemic proportions as well as the elimination or reduction of risk factors in all populations.

The control of cardiovascular disease requires healthy living for everybody, regardless of age, sex, race or socioeconomic status. It also requires equitable access and appropriate treatment for people who are at high risk of or have cardiovascular disease.

This will require mutual assistance involving people and communities within countries and between nations; a balance between prevention and treatment and between basic, applied and evaluative research; extensive communication, education and feedback evaluation at all levels; and action by individuals, many professional associations, communities and governments.

The advisory board believes that all concerned with improving the health and quality of life of people around the world have a responsibility to heed this “call for action.” It can be done.

Declaration

Recognizing that the scientific knowledge and widely tested methods exist to prevent most cardiovascular disease, the Advisory Board of the International Heart Health Conference calls upon professionals in health care, media, education and social science, and their associations, the scientific research community, government agencies concerned with health, education, trade, commerce and agriculture, the private sector, international organizations and agencies concerned with health and economic development, community health coalitions, voluntary health organizations and employers to join forces in eliminating this modern epidemic through the adoption of policies and the implementation of programs of health promotion and disease prevention, as well as through regulatory change directed at entire populations.

Problem

1002. Find Common Characters

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public List<String> commonChars(String[] A) {
        List<String> clist = new ArrayList<String>();
        final int N = A.length;
        int[][] counter = new int[26][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < A[i].length(); j++) {
                counter[A[i].charAt(j) - 'a'][i]++;
            }
        }

        int m;
        String s = "";
        for (int i = 0; i < 26; i++) {
            m = counter[i][0];
            for (int j = 1; j < N; j++) {
                if (counter[i][j] < m)
                    m = counter[i][j];
            }
            if (m > 0) {
                s = (char)(i + 'a') + "";
                for (; m > 0; m--) {
                    clist.add(s);
                }
            }
        }
        return clist;
    }
}

Submission Detail

• 83 / 83 test cases passed.
• Runtime: 7 ms, faster than 53.85% of Java online submissions for Find Common Characters.
• Memory Usage: 39.4 MB, less than 7.83% of Java online submissions for Find Common Characters.

Easy indeed! I can do it on leetcode editor without IDE debug.

Problem

1572. Matrix Diagonal Sum

Java

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int diagonalSum(int[][] mat) {
        final int N = mat.length;
        int sum = 0;
        for(int i=0;i<N;i++) {
            sum += mat[i][i];
            if ((N-1)!=2*i)
                sum += mat[i][N-1-i];
        }
        return sum;
    }
}

Submission Detail

• 113 / 113 test cases passed.
• Runtime: 0 ms, faster than 100.00% of Java online submissions for Matrix Diagonal Sum.
• Memory Usage: 39.5 MB, less than 16.30% of Java online submissions for Matrix Diagonal Sum.

by John Lennon

Verse 1

Imagine there’s no heaven
It’s easy if you try
No hell below us
Above us, only sky
Imagine all the people
Living for today
I

Verse 2

Imagine there’s no countries
It isn’t hard to do
Nothing to kill or die for
And no religion too
Imagine all the people
Living life in peace
You

Chorus

You may say I’m a dreamer
But I’m not the only one
I hope someday you’ll join us
And the world will be as one

Verse 3

Imagine no possessions
I wonder if you can
No need for greed or hunger
A brotherhood of man
Imagine all the people
Sharing all the world
You

Chorus

You may say I’m a dreamer
But I’m not the only one
I hope someday you’ll join us
And the world will live as one

• Imagine - John Lennon song
• Imagine

How do you observe something you can’t see? This is the basic question of somebody who’s interested in finding and studying black holes. Because black holes are objects whose pull of gravity is so intense that nothing can escape it, not even light, so you can’t see it directly.

So, my story today about black holes is about one particular black hole. I’m interested in finding whether or not there is a really massive, what we like to call “supermassive” black hole at the center of our galaxy. And the reason this is interesting is that it gives us an opportunity to prove whether or not these exotic objects really exist. And second, it gives us the opportunity to understand how these supermassive black holes interact with their environment, and to understand how they affect the formation and evolution of the galaxies which they reside in.

So, to begin with, we need to understand what a black hole is so we can understand the proof of a black hole. So, what is a black hole? Well, in many ways a black hole is an incredibly simple object, because there are only three characteristics that you can describe: the mass, the spin, and the charge. And I’m going to only talk about the mass. So, in that sense, it’s a very simple object. But in another sense, it’s an incredibly complicated object that we need relatively exotic physics to describe, and in some sense represents the breakdown of our physical understanding of the universe.

But today, the way I want you to understand a black hole, for the proof of a black hole, is to think of it as an object whose mass is confined to zero volume. So, despite the fact that I’m going to talk to you about an object that’s supermassive, and I’m going to get to what that really means in a moment, it has no finite size. So, this is a little tricky.

But fortunately there is a finite size that you can see, and that’s known as the Schwarzschild radius. And that’s named after the guy who recognized why it was such an important radius. This is a virtual radius, not reality; the black hole has no size. So why is it so important? It’s important because it tells us that any object can become a black hole. That means you, your neighbor, your cellphone, the auditorium can become a black hole if you can figure out how to compress it down to the size of the Schwarzschild radius.

At that point, what’s going to happen? At that point gravity wins. Gravity wins over all other known forces. And the object is forced to continue to collapse to an infinitely small object. And then it’s a black hole. So, if I were to compress the Earth down to the size of a sugar cube, it would become a black hole, because the size of a sugar cube is its Schwarzschild radius.

Now, the key here is to figure out what that Schwarzschild radius is. And it turns out that it’s actually pretty simple to figure out. It depends only on the mass of the object. Bigger objects have bigger Schwarzschild radii. Smaller objects have smaller Schwarzschild radii. So, if I were to take the sun and compress it down to the scale of the University of Oxford, it would become a black hole.

So, now we know what a Schwarzschild radius is. And it’s actually quite a useful concept, because it tells us not only when a black hole will form, but it also gives us the key elements for the proof of a black hole. I only need two things. I need to understand the mass of the object I’m claiming is a black hole, and what its Schwarzschild radius is. And since the mass determines the Schwarzschild radius, there is actually only one thing I really need to know.

So, my job in convincing you that there is a black hole is to show that there is some object that’s confined to within its Schwarzschild radius. And your job today is to be skeptical. Okay, so, I’m going to talk about no ordinary black hole; I’m going to talk about supermassive black holes.

So, I wanted to say a few words about what an ordinary black hole is, as if there could be such a thing as an ordinary black hole. An ordinary black hole is thought to be the end state of a really massive star’s life. So, if a star starts its life off with much more mass than the mass of the Sun, it’s going to end its life by exploding and leaving behind these beautiful supernova remnants that we see here. And inside that supernova remnant is going to be a little black hole that has a mass roughly three times the mass of the Sun. On an astronomical scale that’s a very small black hole.

Now, what I want to talk about are the supermassive black holes. And the supermassive black holes are thought to reside at the center of galaxies. And this beautiful picture taken with the Hubble Space Telescope shows you that galaxies come in all shapes and sizes. There are big ones. There are little ones. Almost every object in that picture there is a galaxy. And there is a very nice spiral up in the upper left. And there are a hundred billion stars in that galaxy, just to give you a sense of scale. And all the light that we see from a typical galaxy, which is the kind of galaxies that we’re seeing here, comes from the light from the stars. So, we see the galaxy because of the star light.

Now, there are a few relatively exotic galaxies. I like to call these the prima donna of the galaxy world, because they are kind of show offs. And we call them active galactic nuclei. And we call them that because their nucleus, or their center, are very active. So, at the center there, that’s actually where most of the starlight comes out from. And yet, what we actually see is light that can’t be explained by the starlight. It’s way more energetic. In fact, in a few examples it’s like the ones that we’re seeing here. There are also jets emanating out from the center. Again, a source of energy that’s very difficult to explain if you just think that galaxies are composed of stars.

So, what people have thought is that perhaps there are supermassive black holes which matter is falling on to. So, you can’t see the black hole itself, but you can convert the gravitational energy of the black hole into the light we see. So, there is the thought that maybe supermassive black holes exist at the center of galaxies. But it’s a kind of indirect argument.

Nonetheless, it’s given rise to the notion that maybe it’s not just these prima donnas that have these supermassive black holes, but rather all galaxies might harbor these supermassive black holes at their centers. And if that’s the case – and this is an example of a normal galaxy; what we see is the star light. And if there is a supermassive black hole, what we need to assume is that it’s a black hole on a diet. Because that is the way to suppress the energetic phenomena that we see in active galactic nuclei.

If we’re going to look for these stealth black holes at the center of galaxies, the best place to look is in our own galaxy, our Milky Way. And this is a wide field picture taken of the center of the Milky Way. And what we see is a line of stars. And that is because we live in a galaxy which has a flattened, disk-like structure. And we live in the middle of it, so when we look towards the center, we see this plane which defines the plane of the galaxy, or line that defines the plane of the galaxy.

Now, the advantage of studying our own galaxy is it’s simply the closest example of the center of a galaxy that we’re ever going to have, because the next closest galaxy is 100 times further away. So, we can see far more detail in our galaxy than anyplace else. And as you’ll see in a moment, the ability to see detail is key to this experiment.

So, how do astronomers prove that there is a lot of mass inside a small volume? Which is the job that I have to show you today. And the tool that we use is to watch the way stars orbit the black hole. Stars will orbit the black hole in the very same way that planets orbit the sun. It’s the gravitational pull that makes these things orbit. If there were no massive objects these things would go flying off, or at least go at a much slower rate because all that determines how they go around is how much mass is inside its orbit.

So, this is great, because remember my job is to show there is a lot of mass inside a small volume. So, if I know how fast it goes around, I know the mass. And if I know the scale of the orbit I know the radius. So, I want to see the stars that are as close to the center of the galaxy as possible. Because I want to show there is a mass inside as small a region as possible. So, this means that I want to see a lot of detail. And that’s the reason that for this experiment we’ve used the world’s largest telescope.

This is the Keck observatory. It hosts two telescopes with a mirror 10 meters, which is roughly the diameter of a tennis court. Now, this is wonderful, because the campaign promise of large telescopes is that is that the bigger the telescope, the smaller the detail that we can see. But it turns out these telescopes, or any telescope on the ground has had a little bit of a challenge living up to this campaign promise. And that is because of the atmosphere. Atmosphere is great for us; it allows us to survive here on Earth. But it’s relatively challenging for astronomers who want to look through the atmosphere to astronomical sources.

So, to give you a sense of what this is like, it’s actually like looking at a pebble at the bottom of a stream. Looking at the pebble on the bottom of the stream, the stream is continuously moving and turbulent, and that makes it very difficult to see the pebble on the bottom of the stream. Very much in the same way, it’s very difficult to see astronomical sources, because of the atmosphere that’s continuously moving by.

So, I’ve spent a lot of my career working on ways to correct for the atmosphere, to give us a cleaner view. And that buys us about a factor of 20. And I think all of you can agree that if you can figure out how to improve life by a factor of 20, you’ve probably improved your lifestyle by a lot, say your salary, you’d notice, or your kids, you’d notice.

And this animation here shows you one example of the techniques that we use, called adaptive optics. You’re seeing an animation that goes between an example of what you would see if you don’t use this technique – in other words, just a picture that shows the stars – and the box is centered on the center of the galaxy, where we think the black hole is. So, without this technology you can’t see the stars. With this technology all of a sudden you can see it. This technology works by introducing a mirror into the telescope optics system that’s continuously changing to counteract what the atmosphere is doing to you. So, it’s kind of like very fancy eyeglasses for your telescope.

Now, in the next few slides I’m just going to focus on that little square there. So, we’re only going to look at the stars inside that small square, although we’ve looked at all of them. So, I want to see how these things have moved. And over the course of this experiment, these stars have moved a tremendous amount. So, we’ve been doing this experiment for 15 years, and we see the stars go all the way around.

Now, most astronomers have a favorite star, and mine today is a star that’s labeled up there, SO-2. Absolutely my favorite star in the world. And that’s because it goes around in only 15 years. And to give you a sense of how short that is, the sun takes 200 million years to go around the center of the galaxy. Stars that we knew about before, that were as close to the center of the galaxy as possible, take 500 years. And this one, this one goes around in a human lifetime. That’s kind of profound, in a way.

But it’s the key to this experiment. The orbit tells me how much mass is inside a very small radius. So, next we see a picture here that shows you before this experiment the size to which we could confine the mass of the center of the galaxy. What we knew before is that there was four million times the mass of the sun inside that circle. And as you can see, there was a lot of other stuff inside that circle. You can see a lot of stars. So, there was actually lots of alternatives to the idea that there was a supermassive black hole at the center of the galaxy, because you could put a lot of stuff in there.

But with this experiment, we’ve confined that same mass to a much smaller volume that’s 10,000 times smaller. And because of that, we’ve been able to show that there is a supermassive black hole there. To give you a sense of how small that size is, that’s the size of our solar system. So, we’re cramming four million times the mass of the sun into that small volume.

Now, truth in advertising. Right? I have told you my job is to get it down to the Schwarzchild radius. And the truth is, I’m not quite there. But we actually have no alternative today to explaining this concentration of mass. And, in fact, it’s the best evidence we have to date for not only existence of a supermassive black hole at the center of our own galaxy, but any in our universe. So, what next? I actually think this is about as good as we’re going to do with today’s technology, so let’s move on with the problem.

So, what I want to tell you, very briefly, is a few examples of the excitement of what we can do today at the center of the galaxy, now that we know that there is, or at least we believe, that there is a supermassive black hole there. And the fun phase of this experiment is, while we’ve tested some of our ideas about the consequences of a supermassive black hole being at the center of our galaxy, almost every single one has been inconsistent with what we actually see. And that’s the fun.

So, let me give you the two examples. You can ask, “What do you expect for the old stars, stars that have been around the center of the galaxy for a long time, they’ve had plenty of time to interact with the black hole.” What you expect there is that old stars should be very clustered around the black hole. You should see a lot of old stars next to that black hole.

Likewise, for the young stars, or in contrast, the young stars, they just should not be there. A black hole does not make a kind neighbor to a stellar nursery. To get a star to form, you need a big ball of gas and dust to collapse. And it’s a very fragile entity. And what does the big black hole do? It strips that gas cloud apart. It pulls much stronger on one side than the other and the cloud is stripped apart. In fact, we anticipated that star formation shouldn’t proceed in that environment.

So, you shouldn’t see young stars. So, what do we see? Using observations that are not the ones I’ve shown you today, we can actually figure out which ones are old and which ones are young. The old ones are red. The young ones are blue. And the yellow ones, we don’t know yet. So, you can already see the surprise. There is a dearth of old stars. There is an abundance of young stars, so it’s the exact opposite of the prediction.

So, this is the fun part. And in fact, today, this is what we’re trying to figure out, this mystery of how do you get – how do you resolve this contradiction. So, in fact, my graduate students are, at this very moment, today, at the telescope, in Hawaii, making observations to get us hopefully to the next stage, where we can address this question of why are there so many young stars, and so few old stars. To make further progress we really need to look at the orbits of stars that are much further away. To do that we’ll probably need much more sophisticated technology than we have today.

Because, in truth, while I said we’re correcting for the Earth’s atmosphere, we actually only correct for half the errors that are introduced. We do this by shooting a laser up into the atmosphere, and what we think we can do is if we shine a few more that we can correct the rest. So this is what we hope to do in the next few years. And on a much longer time scale, what we hope to do is build even larger telescopes, because, remember, bigger is better in astronomy.

So, we want to build a 30 meter telescope. And with this telescope we should be able to see stars that are even closer to the center of the galaxy. And we hope to be able to test some of Einstein’s theories of general relativity, some ideas in cosmology about how galaxies form. So, we think the future of this experiment is quite exciting.

So, in conclusion, I’m going to show you an animation that basically shows you how these orbits have been moving, in three dimensions. And I hope, if nothing else, I’ve convinced you that, one, we do in fact have a supermassive black hole at the center of the galaxy. And this means that these things do exist in our universe, and we have to contend with this, we have to explain how you can get these objects in our physical world.

Second, we’ve been able to look at that interaction of how supermassive black holes interact, and understand, maybe, the role in which they play in shaping what galaxies are, and how they work.

And last but not least, none of this would have happened without the advent of the tremendous progress that’s been made on the technology front. And we think that this is a field that is moving incredibly fast, and holds a lot in store for the future. Thanks very much. (Applause)

• The Royal Swedish Academy of Sciences has decided to award the 2020 Nobel Prize in Physics with one half to Roger Penrose and the other half jointly to Reinhard Genzel and Andrea Ghez.
• Physics Nobel Awarded for Black Hole Breakthroughs