After reading Graham's "How to Get Startup Ideas"

Paul Graham's "How to Get Startup Ideas" is a great article. It's main idea, as he summarized in the very end, is "Live in the future and build what seems interesting." In simple words, in order to get organic startup ideas, we should become the people who are likely to have good startup ideas, and these people are usually at the leading edge of some rapidly changing field. FYI, Graham did convince me of his theorem after I read the article.

However, several questions come up as I was reading. The first question is why people always look at Facebook, Microsoft and Apple?? Well that's look at what they have in common. First, all these companies are huge and close to our live and were all brought up by grass-root founders. Second, all the companies are in the high-tech industries. Third, all the founders were rich at very young ages. Are these three points correlated? Probably. But, I want to keep in mind that there are many other kinds of entrepreneurship in other industries, like Priceline and Virgin Group, and it's very hard to be as successful as these three companies.

Another question I wanna ask is about 3D printing. It seems to me, 3D printing is a awesome technology, but why it's not popular and unsuccessful?? Maybe it's gonna work as Kickstarter shows a successful pledge of nearly $3M!

CSC236 SLOG #7

Here's the description of the question:

You are part of a group of friends who choose which to treat to lunch in the following manner:

1. They arrange themselves in an (approximate) circle.
2. They begin reciting the positive natural numbers, in order, in a counter-clockwise direction (viewed from above), starting with the friend at the northern extreme of the circle (who utters "one").
3. As a friend utters an even number, he or she is eliminated from the counting (and consideration for lunch). The counting "wraps around" so that those who avoided one of the dreaded even numbers on the first round may be exposed on subsequent rounds.
4. The last person left is treated to lunc.

For example, if there are friends f1, f2, f3, f4, and f5 arranged counter-clockwise, with f1 at the northern extreme, the first round would eliminate f2 and f4. Then f1 and f5 would be eliminated in the next round, leaving f3 to enjoy the free lunch.

If there are n friends, where should you position yourself to get the free lunch? Do you have a technique that will work for any positive natural number n?

Dec 3

When I first saw the question, I thought it's easy. I started by experimenting with different number of people, and see who gets the free lunch in each case. Below is the result I got from experimenting:

# of ppl:  1  | 2  | 3  | 4   | 5  | 6  | 7  | 8   | 9  | 10 | 11 | 12 | 13  | 14  | 15   | 16 |

winner:   f1 | f1 | f3 | f1 | f3 | f5 | f7 | f1 | f3 | f5  | f7 |  f9 | f11 | f13 | f15 |  f1 |

In each experiment, I draw a circle that fits the number of people, and then start eliminating in a counter-clockwise direction by crossing out the people who utter even numbers.

After contemplating on the question for a period of time, I come to two lemmas:

1. Obviously, people start with even numbers will never get the free lunch, because they will be eliminate in the first round of counting.

2. When n equals an odd number, the first person will never get the free lunch except n = 1, because he/she will be eliminate in the second run.

And then, I realize I can expand the second lemma to say that when n equals an even number, the third person will never get the free lunch. 

Then I struggled to find some points to build on for about an hour, I decide to call it a day.

Dec 4

Today, I tried to solve the problem from another angle, and it was success. Instead of looking at the process of elimination, I tried to look at the winners as a sequence of numbers. Surprisingly, that clearly showed a sequence - occurrence of 2^a of orderly odd numbers as a starts from 0 and orderly odd numbers start at 1. The way I separate the winners in the following groups will show the sequence:

# of ppl 1: f1

# of ppl 2-3: f1, f3

# of ppl 4-7: f1, f3, f5, f7

# of ppl 8-15: f1, f3, f5, f7, f9, f11, f13, f15

...

After a bit of calculation I come up to this formula: (let cap(n) be the smallest power of 2 that is equal to or greater than n) winner = (cap(n+1)/2 - (cap(n+1) - 1 - n)) * 2 - 1 = 2n + 1 - cap(n+1)

But how can I prove the formula is right? Or can I come up of an explanation?

So I tried to make a prove by induction. By the nature of increasing number of people 1 at time, I believed that if induction works, mathematic induction is the right choice. 

The base case is easy: when there is one people, he/she is the only choice. But what about the inductive steps? There is no obvious sign of induction. So I started contemplating the numbers again.

Then I came up with one more clues:

Except when n=1, the last count being eliminated is always (n-1)*2.

And then I realized that if n results in a winner of 7, the winner of n+1 could be either 9 or 1. Up to here, I was stuck. I couldn't any process after that. So I decide to move my mind to other objects.

Dec 5

After a day of fresh air, I came back to the free-lunch problem.

I came up with a thought on subway. I can explain when exactly n will result in a winner of 1. It's actually quite easy to understand. When n is a power of 2, the winner will be 1. The reason is that in every round of elimination, because the number of people is a power of 2, the last number being eliminated will be the first number on the right side of 1, which makes 1 the first number in the next run and the count of 1 will be an odd number. So 1 will be left to the end.

So now we know what will happen if (n+1) is a power of 2. What happens if it's not a power of 2??

After half an hour of contemplating, I realize that the game will not end with a odd counting number, because the game ends when the second last number standing is eliminated and the counting has to be even. Following the logic, the counting before the last counting will be on the winner. Given that, if n people has a winner of x, then the winner of n+1 people will be the that number that counts next after x is eliminated, because the counting is shift up by 1. Given that even number cannot be the winner, the winner of n+1 will be x+2.

So when n+1 is a power of 2, the winner will be 1. If it's not power of 2, the winner will be 2n + 1 - cap(n+1) + 2 given that the winner of n people is 2n + 1 - cap(n+1)  # IH.

Let's see if it real works mathematically. 

when n+1 is a power of 2: 

cap((n+1)+1) = (n+1)*2, thus 2(n+1) + 1 - cap((n+1)+1) = 2n + 3 - 2*(n+1) = 1.

When n+1 is not a power of 2:

cap((n+1+1) = cap(n+1), thus 2(n+1) + 1 - cap((n+1)+1) = 2n + 3 - cap(n+1) = (2n + 1 - cap(n+1)) + 2.

Then, the formula holds in both cases.

Combine the base case and the inductive steps, we can conclude that when n people is playing, the (2n + 1 - cap(n+1))th person will get the free lunch.

Cheers, I have solved the problem finally!!!

CSC236 SLOG#6

I have had a madly busy week. I have worked all day in every day of the week to get the assignments due, which makes me recall a funny incident in my statistic class. In the other day, the professor is asking when would think a bath-tub distribution occurs in real life. And then, a student answered, "the time you spend studying throughout a semester. Haha, that was good.
I have just handed in another computer science assignment tonight. Part of the assignment was asking us to describe a modification on an existing code in order to carry out some extra features. The tricky part is, it does not want us to make the modification, instead, it want us to describe it so other people can understand. Quite frankly, I found the work much harder than and more tedious than modifying the code directly. I was joking to myself maybe that's way I am in computer science instead of social science. Then I realize that codes and the language we use for proof in CSC236 are designed to be concise, uniform and unambiguous, unlike real language. When we try to convey ideas through real language, I have to make assumptions about others' knowledge, intelligence and even emotional state. More importantly, there are many ways to convey the same thing in real language; and what is even more serious is that different things can be conveyed by the same sentences. So I am still struggling between the real language and the computer language...
I am starting to solving a challenging math question that I found on the problem wiki website. The problem I am woking on is the free lunch question. It is quite interesting, and I am already making some progress. I will get it update soon.
Now I need to get some sleep, night!