Thanx a lot !!!!!!

That is exactly what I need !

I will be eagerly waiting for subsequent chapters !!!!

I would be reading the first chapter when I have time, but a quick glance to me says that it is quite good. It seems a good (combinatorial) counterpart to v_Enhance's geometry book. Will there be solutions to the exercise problems, or we have to search them ourselves?

May I ask when would the other chapters be posted?

Thanks!

Thank you for your positive feedback! To answer your questions, there may be a gap of about a week before I put up the next chapter since I will be out of town, but after that I should be putting up two to three per week. There will be nine chapters in total, covering algorithms (two chapters), processes, existence, games, counting in two ways, extremal combinatorics, graph theory and the probabilistic method. Eventually I will put them all into a single, complete pdf with a brief appendix on prerequisites as well. I thought I would initially post chapters individually to get some feedback and make changes where required.
As of now I do not have any plans to write solutions to exercise problems, but if you would like a hint/solution sketch to a particular problem you have been working on feel free to pm me. It may also be useful to know that the exercises are (for the most part) arranged in increasing order of difficulty (with exercise 10 being an exception as it is a lemma needed for 11).

I cant find the link for some reason

Maybe you are on a tab or mobile

could you give links for the solutions to the informatics olympiad problems? the others could be found either through google or aops resources.

Most of them should be under greedy algorithms at this link: http://www.iarcs.org.in/inoi/online-study-material/topics/

oh ok. When would the other chapters be posted?

I just uploaded chapter 2. Chapters 3, 4 and 5 should be ready within the next 3 or 4 days

Thank you! I hardly know any olympiad combinatorics, so I guess this is a good chance to learn. Just wondering, what did you use to write this book?

It looks like Microsoft Word.

This work is really impressive! You are very fast.

Here are some comments as I read through the first chapter. Most of these are just little nitpicks and may not be worth weighting very heavily. The stuff I believe more firmly is in italics. If you want to discuss more, you are welcome to email me at .

Introduction
Second paragraph: "Often an algorithm can ... field of number theory". This feels like "fluff" to me, doesn't contribute much to the paragraph and the first sentence seems vacuously true. Also not sure how much I agree with the claim that the Euclidean algorithm is the basis of NT, but that's beside the point

Third paragraph: Perhaps you might want to put this in a preface / chapter 0 of some sort.

Greedy Algorithms
Nice quote

"in each step" might be better as "at each step"

"They aren't always the optimal algorithm in the long run" is kind of awkward and "they" seems not so well-defined.
I suggest "Greedy algorithms are not always optimal in the long run".

Example 1
Solution: You may prefer to use , , for colors and , , for vertices.

Remark: This is good. You might also want to note something to the effect that the greedy algorithms are also _dumb_; they don't take a lot of things into account. To illustrate this point, you might mention Brook's Theorem, which shows that is usually not tight. I think it's useful to point out in this way that the greedy algorithm usually does not always perform optimally.

Example 2
The comment about how the trivial greedy algorithm fails is IMO very good. I don't know why so few books make comments like this.
Actually the entire solution is just very well-explained.

And that remark at the end about boring calculations is hilarious. Please keep it!

Example 3
You might be pushing a little here with the amount of graph theory to assume, but that's probably fine.
You should mention that must be nonempty.
Is there a missing space between "" and "vertices" in the problem statement?

The solution feels a bit more dense here than the preceding solutions. Some paragraph breaks might help, at least.
Moreover, I think the wording in terms of edges/vertices instead of average degree is both confusing and counterintuitive (at one point, I thought that the value of and were changing). I think the following phrasing might be more intuitive:
"If is the average degree, then we want to delete vertices until the minimum degree is at least .
Call a vertex bad if the degree is less than , and begin deleting bad vertices arbitrarily.
... more text ...
Notice that as we delete bad vertices, the average degree of the graph increases, because BLAH "
and then proceed to show the resulting is nonempty. At the very least, I don't think the "(it started as ...)" should be stuffed into a parenthetical.

Is the bound tight? I feel like looking at a case where equality occurs would be useful for understanding what is happening.
Actually I can't tell from reading your solution why can't be replaced by something else, so I think you should definitely elaborate on why the average degree is strictly increasing.

Example 4
Let seems more conventional than . Also, spacing issues. Would appreciate a paragraph break after "call these small sets and big sets respectively".

The explanation of heuristics is very good here in my opinion. So is the remark at the end.

"Suppose the algorithm fails (that is ..." -- Again, I object to the stuffing of content in parentheses, though not quite as strongly as the previous issue.

Invariants / Monovariants
"... and an invariant is quantity that doesn't change." maybe append "at all" to the end of this sentence.
You might also like to talk briefly about how monovariants / invariants are used, namely
(i) monovariants are often used to show that some process terminates, and
(ii) invariants are often used to show that some state cannot be achieved.

Example 5
How would you think of the black/white coloring?

"... making all but the last 2 entries 0 ..." use "two" instead of "2".

Example 6
Oh man this is a really good example problem. You might want to explain more towards the beginning that we choose the weights in such a way that passing towards does not change the sum of the weights.

The and is actually tricky, initially I thought that could just pass in either direction and it would still work. You might want to show explicitly that this is not the case -- that is, explain why actually needs to be careful by showing an example where passes the wrong way and everyone is sad, then go into the and distinction.

Example 7
"The second part of the question is trivial" -- I think a little more here would be appreciated. It would probably be sufficient to add something of the form "the sum of the money is invariant".

Example 8
I'm not thinking very well right now, but why is this algorithm optimal? You have this which decreases by for most transfers, but decreases by more if one transfers from to . But the "full algorithm" you specified involves doing the second operation whenever possible; in other words, greedily. Why is that sufficient?

Example 9
"Let the sum of a position ... maximum of the 6 numbers" The wording is a bit clumsy here.
Maybe you want "Let the sum and maximum of a position denote the sum and maximum, respectively, of the six numbers".
And again you may want to use "six" instead of "6".

The explanation of the sub-algorithms is good. Some diagrams might be appreciated.

Misc
At this point my mom is telling me I'm going to a doctor appointment soon, so I'm just skimming now.
The fact that I can still pick up the main idea of the solution is a very positive sign.

Example 10
Nitpick: you ought to be consistent with your (a), (b), (c), (d), since you use double-parens (b) for the label but single-parens b) in the main text.

However, I think your dissection into the (a), (b), (c), (d) observations is very, very good.

Example 11
Now you have a), b), c), d) in the labels. Again, you should try and be consistent.

The prose is very clear though. Again, you motivate the solution very well.

The remark is quite good. I recall being surprised at the low scores for the Problem 6 that year until I remembered what Problem 5 was.
Deputy leaders too good

Example 12
The notation here is really dense. Diagrams would be really helpful here, especially for a problem this difficult.

Exercises
The mixture with CS algorithm flavoring is interesting; I personally like it but don't know if others will. It might be worth defining stuff like so that you don't have to keep repeating yourself now or later.

Problem 4 is from some Putnam, but I don't remember which year. It's possible that Putnam stole it though.

You might be interested in providing hints to the problems: just one or two sentences that outlines the main idea. I can attest that this takes much, much less time than writing full solutions, and has a similarly useful effect.

That's all for now, will write more later. And again, feel free to email me if you want to follow up on anything.

Thank you for all your detailed advice Evan. I'll definitely make the relevant changes in the final book. I agree with all of it apart from a few points.
Introduction: The sentences "Often an algorithm... field of number theory" are intended to contrast with the first paragraph. While the first paragraph asserts that algorithms have several "external" uses - uses outside of mathematics - the second paragraph indicates that the focus of this chapter will be to use algorithms as tools to solve mathematical problems. In fact, I do not think it is that obvious that existence problems like example 3 and 4 can be solved by designing algorithms. Perhaps I should reword these sentences a little to make this clearer.
Example 3: No there's no space missing. It just looks like that because of the italics. But I agree with your other remarks about this problem.
Invariants/monovariants: In the final book there will be a chapter introducing some prerequisites, which will define invariants and monovariants, and also introduce the idea of black and white colorings.
Example 7: Isn't it clear that the total money is invariant? He can only transfer money between accounts, not make or destroy money.
Exercises: I agree with what you said about the "CS algorithm flavoring". Do you think I should put these into a separate section at the end? Also, I think problems 7, 9, 10 and 11 are okay since no algorithm design is required, only analysis.

I appreciate the excitement! I have a few rough drafts in the works, but creating the polished final versions takes time unfortunately. I don't want to commit to any particular date at this point. In the mean time, I hope the introductory problem set serves as some solid material for beginners to work through.

not directly related to last few posts, but I pm-ed you about this sometime back, so I guess I'll post it here as well for anyone who's worked on the problem.

This is under the algorithms chapter (2). People have found ways to do this with linear algebra and brute force (similar to the row reduction method here.)

Does anyone know of a purely combinatorial algorithm approach to this problem?

@MelonGirl no I'm actually not aware of a purely combinatorial solution. For a few of the exercises in the book, I did not know the original source (usually because I saw the problem on some handout at an olympiad training camp). This was one such problem, and I'd actually tried it and hadn't been able to solve it. I figured it would make sense as one of the later exercises in the algorithms chapters, so placed it there without realizing it required linear algebra.

I think the linalgb and matrix makes it easier to see the grid rather than a combinatorial approach. You can check the vectors are independent over .
Turn the the space of the states of the chessboard into a dimensional vector space over . The field with elements with addition .
The only gruesome task is to prove that vectors are not linearly independent.

eagerly waiting for it

the drop box link for thefull pdf isn't working

Is there any hints/solution key here??

no but there's a discussion forum

Let the cells of the chessboard be vertices of a graph . Connect any two neighboring vertices (squares). So, you can change the binary state (0,1) of any vertex and all of its neighbors. It does not matter what a graph is. For any simple graph the same claim holds. It was posted already here, in this forum. Here is a solution using linear algebra. There is a T. Gallai's result saying that the vertices of any graph can be partitioned into two sets such that the subgraphs induced on and have all vertices of even degrees. It's possible the above problem to be proved as a corollary of Gallai's theorem. In this blog post, the converse approach is shown.

Is it a mistake in task 5 [Czech and Slovak Republics 1997] after 1st Chapter?
Shouldn't there be only (2n+1)-gon or am I missing something (pls, explain then)?

Yes, n should be an odd integer
Also here is that problem on aops

That book is a good one. Fairly friendly to newcomers too

Thanks alot. I love your style. Wish all the good thing for you <3

When can we expect the beginner version @Pascal96 ?