(Workshop for women in computational topology in August: see here. For a post about these kinds of workshops see here.)
(I have already posted twice on stuff I saw or heard at the Gathering Conference here and here,)
Meta Point- At the Gathering for Gardner conference I learned lots of math (prob more accuarte to say I learned ABOUT lots of math) that I want to tell you about which is why this is my third post on it, and I post more.
The pamplets of Lewis Carol: Games, Puzzles, and related pieces: This was mostly puzzles that are by now familiar, but one new (to me) struck me: an aloof word is a word where if you change any one letter to anything else then its no longer a word. I think aloof is such a word.
Some talk don't know which one was about the Piet Hein Egg, also called a superegg. The talk (which differs slightly from he page pointed to) said it was a solid whose surface has the equation
(x/a)2.5 + (y/a)2.5 + (z/b)2.5
and its an egg which can stand on its end. (Note the x/a,y/a,z/b- that is correct, not a typo).
(Personal Note: Piet Hein invented Soma Cubes which is a puzzle where you put together 3-d pieces
made of small cubes into a large cube or other shapes. I learned about these in a Martin Gardner column and bought a set. I was very good at this- I put together every figure in the booklet within a week. This was the ONLY sign that I was GOOD at math when I was a kid, though there are many signs that was INTERESTED in math. About 30 years ago my girlfriend at that time and I went to a restaurant and there was a SOMA set on the table, assembled into a cube. I took it apart and she said ``Bill, you'll never be able to put it back together!!!'' I then ``tried'' to and ended up putting together instead a bathtub, a dog, a wall, and a W. But gee, it ``seemed'' like I was fumbling around and couldn't get a cube. ``Gee Bill, I think you've seen this puzzle before''. And who is this insightful girlfriend? My wife of over 20 years!)
Magic Magic Square (Sorry, dont know which talk) Try to construct a 4x4 magic square where (as usual) all rows and columns sum to the same thing. But also try to make all sets of four numbers that form a square (e.g., all four corners) also add to that number. Can you? If you insist on using naturals then I doubt it. Integers I also doubt it. But you CAN do it with rationals. How? If you want to figure it out yourself then DO NOT go to the answer which is at this link: here
Droste Effect: When a picture appears inside itself. For an example and why its called that see here
Black Hole Numbers: If you have a rule that takes numbers to numbers, are there numbers that ALL numbers eventually goto? If so, they are black hole numbers for that rule.
Map a number to the number of letters in its name
20 (twenty) --> 6 (six) --> 3 (three) --> 5 (five) --> four (4) --> four(4) --> ...
It turns out that ANY number eventually goes to 4.
Map a number to the sum of the digits of its divisors
12 has divisors 1,2,3,4,6,12 --> 1+2+3+4+6+1+2=19
19 has divisors 1,19 so --> 1+1+9 = 11
11 has divisors 1,11 so --> 1+1+1 = 3
3 has divisors 1,3 so --> 1+3=4
4 has divisors 1,2,4 so --> 1+2+4=7
7 has divisors 1,7 so --> 1+7=8
8 has divisors 1,2,4,8, --> 15
15 has divisors 1,3,5,15 --> 1+3+5+1+5 = 15
AH. It turns out ALL numbers eventually get to 15.
Boomerang Fractions: Given a fraction f do the following:
x1=1, x2=1+f, x3- you can either add f to x2 or invert x2. Keep doing this. Your goal is to get back to 1 as soo nas possible. Here is a paper on it: here. This notion can be generalized: given (s,f) start with s and try to get back so s. Can you always? how long would it take? Upper bounds?
Liar/Truth teller patterns on a square plane b Kotani Yoshiyuki. You have an 4 x 4 grid. Every grid point has a person. They all say ``I have exactly one liar adjacet (left, right, up, or down) to me.''
How many ways can this happen. This can be massively generalized.
Speed Solving Rubit's cube by Van Grol and Rik. A robot can do it in 0.9 seconds: here.
Showing posts sorted by relevance for query Gathering. Sort by date Show all posts
Showing posts sorted by relevance for query Gathering. Sort by date Show all posts
Tuesday, May 24, 2016
Sunday, October 10, 2021
I have a book out on muffins (you prob already know that)
Lance: How come you haven't blogged on your muffin book? You've blogged about two books by Harry Lewis (see here and here) one book by the lesswrong community (see here), and you even did a mashup of a post by two different Scott A's (see here), but not on your own work.
Bill: I thought I did a post on my muffin book.
Lance: No. You have blogged about the muffin problem, and sometimes you mention either the book or the problem in passing, but you haven't had a post that says
HEY, I wrote a book!
And this is all the more strange since you asked me to have the book on our blog page.
Bill: (Searches blog with keyword muffin and finds no ref to muffin book). Well pierce my ears and call be drafty! I have not posted on the muffin book! Do you recall my thoughts on when to tell people you are working on a book?
Lance: No
Bill: I had a college roommate who was an aspiring science fiction writer who told me there are two kinds of people: Those who talk about writing a book, and those who write a book. I have adapted this to:
Do not tell people you are writing a book until you are picking out the cover art.
Lance: I posted about my book when I hadn't even decided on the title. But your cover art is picked out (see here). And, by the way, its very nice, though it makes me hungry. So I think you can begin talking about the book.
Bill: Indeed! I will!
------------------------------------------------------------------------------------
Hey I have a book! (See here to buy it on amazon.)
Title: Mathematical Muffin Morsels: Nobody Wants a Small Piece
by Gasarch, Metz, Prinz, Smolyak
(The other authors were undergraduates when we wrote the book. Prinz and Smolyak are now grad students in CS, Metz is in Finance.)
Origin:
Martin Gardner wrote a Mathematics Recreational column for Scientific American for many years, starting in 1956 and ending in the early 1980s. For many STEM people of my generation (Using my fake birthday of Oct 1, 1960, I am 62 years old) Martin Gardner's columns were both an inspiration and an early exposure to mathematics. His columns also made the line between Mathematical Recreation and so-called serious mathematics thin or nonexistent. (See here for a review of Martin Gardner in the 21st century, a book about the kind of math Gardner wrote of. The book makes a mockery of the distinction between recreational and serious mathematics.) He passed away in 2010 at the age of 95.
There is a gathering in his honor that is hold roughly every 2 years, called Gathering For Gardner. (It was cancelled in Spring 2020 and Spring 2021 because of COVID- though its in Atlanta where the CDC is, so they could have had it as an experiment and told the CDC the results). You have to be invited to goto it. I got an invite for 2016 from my contact at World Scientific who published my previous book, Problems with a Point: Exploring Math and Computer Science co-authored with Clyde Kruskal (I had two blogs on it, here and here, and you can buy it on amazon here.) I did three posts on G4G-2016 (here, here, and here).
Aside from seeing some great talks that I understood and liked, I also picked up a pamphlet titled:
The Julia Robinson Math Festival
A Sample of Mathematical Puzzles
Compiled By Nancy Blackman
One of the problems, credited to Alan Frank, was
How can you divide and distribute 5 muffins for 3 students so that everyone gets 5/3 and the smallest piece is as big as possible?
They had some other values for muffins and students as well.
I solved the (5,3) problem and the other ones as well. That was fun.
When I got home I began looking at the problem for m muffins and s students. I let f(m,s) be the biggest smallest piece possible for giving out m muffins to s students. I proved a general theorem, called the Floor-Ceiling theorem, that always gives an upper bound, FC(m,s) on f(m,s). I worked out formulas for
f(m,1) (trivial),
f(m,2) (trivial),
f(m,3) (its always FC(m,3),
f(m,4) (its always FC(m,4)).
While working on f(m,5) I found that f(m,5) was always FC(m,5) EXCEPT for m=11. So what's up with f(11,5)?
By the Floor Ceiling theorem f(11,5) \le 11/25. We (at that point several ugrads and HS students had joined the project) were unable to find a protocol that would show f(11,5)\ge 11/25. Personally I thought there WAS such an protocol but perhaps it was more complicated than the ones we had found (We were finding them by hand using some easy linear algebra.) Perhaps a computer program was needed. We did find a protocol for f(11,5)\ge 13/30, which surely was not optimal.
While on an Amtrak I began working out the following train of thought: The protocol for f(11,5)\le 11/25 MUST have
(1) every muffin cut into two pieces,
(2) 3 students get 4 pieces,
(3) 2 students get 5 pieces.
While working on getting a protocol for f(11,5)\le 11/25 with these properties I found that... there could be no such protocol! Then by reworking what I did I found that f(11,5)\le 13/30. So it was done! and we had a new technique, which we call The Half Method. To see the full proof see my slides here
The story above is typical: We get f(m,k) for all 1\le k\le SOMETHING, we get stuck, and then we find ANOTHER technique to show upper bounds (which in this case are limits on how well we can do). This happened about 8 times depending on how you count. After a while we realized that this could not just be an article, this was a book! World Scienfiic agreed to publish it, and its out now.
Misc Notes
1) I got a conference paper out of it, in the Fun with Algorithms Conference, with some of the co-authors on the book, and some other people. here is the conf paper.
2) Early on we realized that f(m,s) = (m/s)f(s,m) so we only had to look at the m>s case.
3) The fact that f(m,s) exists and is rational is not obvious, but is true. In fact, f(m,s) can be found by a mixed-int program.
4) Late on in the process I found that there was a by-invite-only math newsgroup that had discussed the problem, and in fact was where Alan Frank first posted it. I obtained their materials and found that they had already shown f(m,s)=(m/s)f(s,m) and also that the answer is always rational and exists. Aside from that our results did not overlap.
5) Even later in the process Scott Huddleston emailed me (out of the blue) that he had a program that solved the muffin problem quickly. I was skeptical at first, but he did indeed have a whole new way to look at the problem and his code was very fast (I had Jacob Prinz, one of the co-authors on the book, recode it). Later Richard Chatwin (see here) seems to have proven that Scott's method always works. The approach of Scott and Richard is where to go if you want to do serious further research on Muffins. My book is where you want to go if you want to learn some easy and fun math (a HS student could read it).
6) I co-authored a column with Scott H, Erik Metz, Jacob Prinz on Muffins, featuring his technique, in Lane's complexity column, here.
7) I had an REU student, Stephanie Warman, write a muffin package based on the book.
8) I gave a talk an invited talk on The Muffin Problem at a Joint AMS-MAA meeting.
9) I gave a talk at Gathering for Gardner 2018 on The Muffin Problem.
10) I often give talks on it to groups of High School students.
11) When I teach Discrete Math Honors I talk about it and assign problems on it- it really is part of the course. As such its a good way to reinforce the pigeon hole principle.
12) I contacted Alan Frank about my work. We arranged to meet at an MIT combinatorics seminar where I was to give a talk on muffins. He brought 11 muffins, with 1 cut (1/2,1/2), 2 cut (14/30,16/30),
and 8 cut (13/30,17/30) so that the 11 of us could each get 11/5 with smallest piece 13/30.
13) Coda:
Why did I keep working on this problem? I kept working on it because I kept hitting barriers and (with co-authors) breaking them with new techniques that were interesting. If early on a barrier was not breakable then I would have stopped. If (say) Floor-ceiling solved everything than I might have gotten a paper out of this, but surely not a book.
Lesson for all of us: look around you! Its not clear what is going to inspire a project!
Lasting effect: I am reluctant to throw out old math magazines and pamphlets since you never know when one will lead to a book.
Sunday, May 01, 2016
Some more bits from the Gathering for Gardner
I posted about the Gathering for Gardner conference and about some of the talks I saw here. Today I continue with a few more talks.
Playing Penney's game with Roulette by Robert Vallin. Penney;'s game is the following: let k be fixed. Alice and Bob pick different elements of {H,T}^k. They flip a coin until one of their sequences shows up, and that person wins. Which sequences have the best probability of winning?
New Polyhedral dice by Robert Fathauer, Henry Segerman, Robert Bosch. This is a good example of how my mentality (and possibly yours) differs from others. When I hear ``60-sided dice'' I think ``p1,...,p60 where are all between 0 and 1 and add up to 1'' I also thought that only the platonic solids could be usedvto form fair dice (so only 4-sided, 6-sided, 8-sided, 12-sided, and 20-sided dice can be made). NOT so. These authors actually MAKE real dice and they do not have to be platonic solids. Here is their website.
Numerically balance dice by Robert Bosch (paper is here). Why do dice have the opposite sides sum to the same thing? Read the paper to find out!
Secret messages in juggling and card shuffling by Erik Demaine. Erik Demaine was one of about 4 theoretical computer scientists I met at the conference, though Erik is so well rounded that calling him a theoretical computer scientist doesn't seem quite right. I had never met him before which surprised me. In this talk he showed us some new fonts- one using juggling. See here for an example of juggling fonts, co-authored with his father Martin.
Fibonacci Lemonade by Andrea Johanna Hawksley. Put in the leomon and sugar in fib number increments. Here is their website. In my first post I said the talks were on a variety of topics and then presented mostly math talks. This talk is an example of that variety. There were other talks involving the Fib numbers. I was surprised by this since they aren't that special (see here).
Penis Covers and Puzzles: Brain Injuries and Brain Health by Gini Wingard-Phillips. She recounted having various brain injuries and how working on mathematical puzzles, of the type Martin Gardner popularized as HELPING HER RECOVER! As for the title- people with brain injuries sometimes have a hard time finding the words for things so they use other words. In this case she wanted her husband to buy some condoms but couldn't think of the word so she said Penis Covers instead.
Loop- Pool on an Ellipse by Alex Bellos. Similar in my mind to the Polyhedral dice talk (you'll see why). We all know that if you built an elliptical pool table with a hole at one of the foci then if the ball is placed at the other foci and hit hard enough it WILL go into the other hole. But Alex Bellos actually MAKES these pool table (see here if you want buy one for $20,000). He told us the history- someone else tried to make one in 1962 but nobody bought them (I wonder if anyone are going to buy his), and Alex had problems with friction as you may recall that it only works on a frictionless surface. So his game does require some skill. The similarity to dice is that I (and you?) are used to thinking about dice and ellipses abstractly, not as objects people actually build.
This post is getting long so I'll stop here and report more in a later post. Why so mny posts? Six minute talks that I an actually understand and are delighted to tell you about!
Monday, March 23, 2020
What to do while ``stuck'' at home/Other thoughts on the virus
Lance had a great post on what to do while you are stuck at home, which is of course relevant to whats happening now. Lance's post is here.
I will add to it, and then have other comments.
1) In our current electronic society we can do a lot from home. Don't think of it as being `stuck at home'
2) Lance points out that you should read a paper, read a textbook, etc. I of course agree and add some advice. Be Goldlocks!
This paper is too hard (e.g., a text on quantum gravity)
This paper is too easy (e.g., a discrete math textbook for a freshman course)
This paper is just right (e.g., working out the large canonical Ramsey theorem)
3) If you catch up on your TV viewing on your DVR then beware: you will see commercials for Bloomberg.
4) DO NOT binge watch TV. You will hate yourself in the morning.
5) Simons Inst Theory talks:
https://simons.berkeley.edu/videos
TCS+ talks
https://sites.google.com/site/plustcs/past-talks
or
https://sites.google.com/site/plustcs/
The Gathering for Gardner records all of their talks and puts the on you-tube
so goto youtube and search for Gathering for Gardners. These are Goldilocks talks since they
are easy but on stuff you prob don't know.
6) Keep fit. I used to go on treadmill for 45 minutes a day, now I am doing an hour.
7) Go for walks with a person who already shares your house, but avoid other people.
8) Book reviews, surveys, orig articles, that you were putting off writing- now write them.
but see next item.
10) Catch up on your blog reading. My favorite was Scott Aaronson's blog post about Davos:here. I also read every single comment. I hated myself in the morning. So that part may have been a mistake.
OTHER THOUGHTS
1) Do you really have more free time? No commuting, no teaching, but you still have the rest of your job, and perhaps it is harder if some things are easier at work. And calling relatives and friends to make sure they are okay, and just to talk, is a great thing to do, but its time consuming.
2) I'm beginning to lose track of what day-of-the-week it is since I don't have school to keep me on track, and I only watch TV shows on DVR so I watching a show on a day does not mean I know what day it is.
3) Avoid being price-gouged. The first few days that I tried to buy TP for my mom on amazon (I do this in normal times--- I order lots for my mom on amazon--- she is tech shy. She is also over 90.) her usual brand was out of stock, and the other brands were either higher quality so higher prices or just
absurdly priced. She wisely said to wait a week. She was right- it was easy to get at the usual price.
4) More generally, it seems like the shortages are people-created. For example, if in a store you see they are low on X, then you buy LOTS of X, and everyone does that, so then their really is a shortage of X. But I think thats calmed down some.
5) It important to have a `we will recover from this, life will go on' attitude (while following the things ALL experts say- wash your hands a lot, drink lots of water, get lots of sleep, which is prob
good advice anyway) and hence I will try to, for the next few weeks, blog on NORMAL things----Hilberts's 10th problem, Large Ramsey, etc.
ADDED LATER- there is a very nice contrarian view in the comment by Steve, the first comment. You should read that!
I will add to it, and then have other comments.
1) In our current electronic society we can do a lot from home. Don't think of it as being `stuck at home'
2) Lance points out that you should read a paper, read a textbook, etc. I of course agree and add some advice. Be Goldlocks!
This paper is too hard (e.g., a text on quantum gravity)
This paper is too easy (e.g., a discrete math textbook for a freshman course)
This paper is just right (e.g., working out the large canonical Ramsey theorem)
3) If you catch up on your TV viewing on your DVR then beware: you will see commercials for Bloomberg.
4) DO NOT binge watch TV. You will hate yourself in the morning.
5) Simons Inst Theory talks:
https://simons.berkeley.edu/videos
TCS+ talks
https://sites.google.com/site/plustcs/past-talks
or
https://sites.google.com/site/plustcs/
The Gathering for Gardner records all of their talks and puts the on you-tube
so goto youtube and search for Gathering for Gardners. These are Goldilocks talks since they
are easy but on stuff you prob don't know.
6) Keep fit. I used to go on treadmill for 45 minutes a day, now I am doing an hour.
7) Go for walks with a person who already shares your house, but avoid other people.
8) Book reviews, surveys, orig articles, that you were putting off writing- now write them.
but see next item.
10) Catch up on your blog reading. My favorite was Scott Aaronson's blog post about Davos:here. I also read every single comment. I hated myself in the morning. So that part may have been a mistake.
OTHER THOUGHTS
1) Do you really have more free time? No commuting, no teaching, but you still have the rest of your job, and perhaps it is harder if some things are easier at work. And calling relatives and friends to make sure they are okay, and just to talk, is a great thing to do, but its time consuming.
2) I'm beginning to lose track of what day-of-the-week it is since I don't have school to keep me on track, and I only watch TV shows on DVR so I watching a show on a day does not mean I know what day it is.
3) Avoid being price-gouged. The first few days that I tried to buy TP for my mom on amazon (I do this in normal times--- I order lots for my mom on amazon--- she is tech shy. She is also over 90.) her usual brand was out of stock, and the other brands were either higher quality so higher prices or just
absurdly priced. She wisely said to wait a week. She was right- it was easy to get at the usual price.
4) More generally, it seems like the shortages are people-created. For example, if in a store you see they are low on X, then you buy LOTS of X, and everyone does that, so then their really is a shortage of X. But I think thats calmed down some.
5) It important to have a `we will recover from this, life will go on' attitude (while following the things ALL experts say- wash your hands a lot, drink lots of water, get lots of sleep, which is prob
good advice anyway) and hence I will try to, for the next few weeks, blog on NORMAL things----Hilberts's 10th problem, Large Ramsey, etc.
ADDED LATER- there is a very nice contrarian view in the comment by Steve, the first comment. You should read that!
Sunday, April 24, 2016
Some short bits from the Gathering for Gardner Conference
I attended G4G12 (Gathering for Gardner) a conference that meets every 2 years (though the gap between the first and second was three years) to celebrate the work of Martin Gardner. Most of the talks were on Recreational mathematics, but there were also some on Magic and some are hard to classify.
Martin Gardner had a column in Scientific American called Mathematical Games from 1956 to 1981. His column inspired man people to go into mathematics. Or perhaps people who liked math read his column. The first theorem I ever read outside of a classroom was in his column. It was, in our terminology, a graph is Eulerian iff every vertex has even degree.
For a joint review of six G4G proceedings see here. For a joint review of six books on recreational math including three of Gardner's, see here. For a review of a book that has serious math based on the math he presented in his column see here.
The talks at G4G are usually 6 minutes long so you can learn about a nice problem and then work on it yourself. Their were a large variety of talks and topics. Many of the talks do not have an accompanying paper. Many of them are not on original material. But none of this matters--- the talks were largely interesting and told me stuff I didn't know.
64=64 and Fibonacci, as Studied by Lewis Caroll, by Stuart Moshowitz. This was about a Lewis Caroll puzzle where he put together shapes in one way to get a rectangle of area 65, and another way to get a square of area 64, The following link is NOT to his talk or a paper of Moshowitz, but it is about the problem: here
How Math can Save your life by Susan Marie Frontczak. This was part talk about bricks and weights and then she stood on the desk and sang this song (thats not her signing it).
Twelve ways to trisect and angle by David Richeson. This was NOT a talk about cranks who thought they had trisected and angle with straightedge and compass. It was about people who used ruler, compass, and JUST ONE MORE THING. I asked David later if the people who trisected the angle before it was shown impossible had a research plan to remove the ONE MORE THING and get the real trisection. He said no- people pretty much knew it was impossible even before the proof.
The Sleeping Beauty Paradox Resolved by Pradeep Mutalik. This paradox would take an entire blog post to explains so here is a pointer to the wikipedia entry on it: here. AH, this one DOES have a paper associated to it, so you can read his resolution here
Larger Golomb Rulers by Tomas Rokicki. A Golomb Ruler is a ruler with marks on it so that the all of the distances between marks are distinct. The number of marks is called the order of the ruler. Construction a Golumb ruler is easy (e.g., marks at the 1,2,4,8,... positions I think works). The real question is to get one of shortest length. They had some new results but, alas, I can't find them on the web.
Chemical Pi by John Conway. There are people who memorize the first x digits of pi. John Conway does something else. He has memorized the digits of pi and the chemical elements in the following way:
HYDROGEN 3.141592653 HELIUM next 10 digits of pi LITHIUM etc
that is, he memorized the digits of pi by groups of 10 and separated by the chemical elements in the order they are on the Periodic table. He claims this makes it easier to answer questions like: What is the 87th digits of pi. He also claims it gives a natural stopping point for how many digits of pi you need to memorize (need? maybe want). (ADDED LATER WHEN I CORRECTED HELIUM TO HYDROGEN: here are some mnemonic devices: here.
This post is getting long so I may report on more of the talks in a later post.
Monday, April 30, 2018
Gathering for Gardner 13 - the first or third of many posts
I attended G4G13 (Gathering for Gardner- meeting 13). Martin Gardner was the Scientific American Mathematical Recreations columnist from 1956 until 1981. He had a great influence on many math-people of my generation.
Most of the talks were 5 minutes so they could tell you a problem or thought of interest but not much more. This is GOOD in that I UNDERSTOOD most of the talks! There were also some talks on Magic and on science literacy (or perhaps science illiteracy) which were also interests of Martin Gardner.
I posted on one problem and its solution so this is either my first or third post on G4G13.
Withouth further ado, here are my descriptions of some of the talks. OR you could just go here
My descriptions are long- I may have lots of posts on G4G13!
EXTENDING THE 10958 PROBLEM by Bill Ames.
(paper on arxiv here)
In 2014 Taneja proposed the following math problem:
Take the digits 1,2,3,4,5,6,7,8,9.
You can put any of +, -, *, /, and powers you want between the digits, or erase the comma to get (for example) 34. Use parenthesis freely. Which natural numbers can you produce?
Here are some examples:
1 = 1 + (2 - 3) - (4 - 5) - (6 - 7) + (8 - 9)
30 = 1 + 2^3 - 4*5 + 6*7 + (8-9)
Which numbers can you get?
Taneja got all the numbers between 0 and 11,111 EXCEPT 10958.
(Is 10958 possible? The talk didn't say.)
Using other operations- square roots and factorials- you can get 10958. The talk was about adding more operations and getting all numbers between 0 and 111,111
THIRTEEN BOUNCES by Gary Antonick.
Since this was G4G13 there were several talks about the number 13. The hotel did not have a 13th floor, and no room was of the form X13 (I was in room 515 and sometimes overshot my room since I assumed it would go 511-513-515, not 511-515). Martin Gardner would have OBJECTED to the lack of a 13th floor and would have condemned triskaidekaphobia (fear of the number 13 and the longest word I ever spelled correctly) as irrational. And he would be right. But I am preaching to the converted (also known as preaching to the choir).
The talk was about firing a cannoball at a perfect reflector. If the cannon is positioned just right the ball will go back into the cannon. Can you make it do this after taking 13 bounces? What if you an only use a compass and straightedge for your calculations?
A GRAMMATICAL APPROACH TO THE CURLING NUMBER CONJECTURE by Duane Bailey.
(For more on the Curling Conjecture Google "Curling Number Conjecture"-- I was going to give a list of papers but there are just too many. There is no wikipedia entry on it, though I did learn about the sport of Curling!)
Take any finite sequence of integers (we will just use natural numbers) for example
2 3 2 3
Write it as X Y Y Y ... Y with as many Y's as possible.
for example
(2 3)2
The number 2 is the Curling Number of the sequence. Append it to the sequence
2 3 2 3 2
Now take the Curling number of this sequence. It is 2 since the sequence is
2 (3 2)2
Append it to the sequence:
2 3 2 3 2 2
Now the Curlng number of this sequence is 1 and we stop.
The conjecture is that if you start with any sequence you will eventually get to 1.
The talk relates the conjecture to aperiodic grammars.
Most of the talks were 5 minutes so they could tell you a problem or thought of interest but not much more. This is GOOD in that I UNDERSTOOD most of the talks! There were also some talks on Magic and on science literacy (or perhaps science illiteracy) which were also interests of Martin Gardner.
I posted on one problem and its solution so this is either my first or third post on G4G13.
Withouth further ado, here are my descriptions of some of the talks. OR you could just go here
My descriptions are long- I may have lots of posts on G4G13!
EXTENDING THE 10958 PROBLEM by Bill Ames.
(paper on arxiv here)
In 2014 Taneja proposed the following math problem:
Take the digits 1,2,3,4,5,6,7,8,9.
You can put any of +, -, *, /, and powers you want between the digits, or erase the comma to get (for example) 34. Use parenthesis freely. Which natural numbers can you produce?
Here are some examples:
1 = 1 + (2 - 3) - (4 - 5) - (6 - 7) + (8 - 9)
30 = 1 + 2^3 - 4*5 + 6*7 + (8-9)
Which numbers can you get?
Taneja got all the numbers between 0 and 11,111 EXCEPT 10958.
(Is 10958 possible? The talk didn't say.)
Using other operations- square roots and factorials- you can get 10958. The talk was about adding more operations and getting all numbers between 0 and 111,111
THIRTEEN BOUNCES by Gary Antonick.
Since this was G4G13 there were several talks about the number 13. The hotel did not have a 13th floor, and no room was of the form X13 (I was in room 515 and sometimes overshot my room since I assumed it would go 511-513-515, not 511-515). Martin Gardner would have OBJECTED to the lack of a 13th floor and would have condemned triskaidekaphobia (fear of the number 13 and the longest word I ever spelled correctly) as irrational. And he would be right. But I am preaching to the converted (also known as preaching to the choir).
The talk was about firing a cannoball at a perfect reflector. If the cannon is positioned just right the ball will go back into the cannon. Can you make it do this after taking 13 bounces? What if you an only use a compass and straightedge for your calculations?
A GRAMMATICAL APPROACH TO THE CURLING NUMBER CONJECTURE by Duane Bailey.
(For more on the Curling Conjecture Google "Curling Number Conjecture"-- I was going to give a list of papers but there are just too many. There is no wikipedia entry on it, though I did learn about the sport of Curling!)
Take any finite sequence of integers (we will just use natural numbers) for example
2 3 2 3
Write it as X Y Y Y ... Y with as many Y's as possible.
for example
(2 3)2
The number 2 is the Curling Number of the sequence. Append it to the sequence
2 3 2 3 2
Now take the Curling number of this sequence. It is 2 since the sequence is
2 (3 2)2
Append it to the sequence:
2 3 2 3 2 2
Now the Curlng number of this sequence is 1 and we stop.
The conjecture is that if you start with any sequence you will eventually get to 1.
The talk relates the conjecture to aperiodic grammars.
Monday, April 23, 2018
Find an 8-digits number such that ....
(June 29th, co-located with STOC, will be a workshop to celebrate Vijay Vazarani's 60th birthday. As computer scientists shouldn't we use 64 as the milestone? See here for details about the workshop, not about 60 vs 64.)
I will likely post a lot about Gathering For Gardner 13, but for now I will just give one problem I saw there. I will not say the speaker or the title of the talk as that might be a clue. I'll give the answer in my next post which will be this week
Find an 8-digit number
d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0
such that
d_0 is the number of 0's in the number
d_1 is the number of 1's in the number
d_2 is the number of 2's in the number
.....
d_6 is the number of 6's in the number
but
d_7 is NOT necc the number of 7's
d_7 is the number of DISTINCT DIGITS in d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0
You could prob find such a number by computer search- but don't.
Feel free to comment. I will not block comments (except those we usually block- usually spam) but by the same token, if you don't want hints, don't read the comments.
I will likely post a lot about Gathering For Gardner 13, but for now I will just give one problem I saw there. I will not say the speaker or the title of the talk as that might be a clue. I'll give the answer in my next post which will be this week
Find an 8-digit number
d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0
such that
d_0 is the number of 0's in the number
d_1 is the number of 1's in the number
d_2 is the number of 2's in the number
.....
d_6 is the number of 6's in the number
but
d_7 is NOT necc the number of 7's
d_7 is the number of DISTINCT DIGITS in d_7 d_6 d_5 d_4 d_3 d_2 d_1 d_0
You could prob find such a number by computer search- but don't.
Feel free to comment. I will not block comments (except those we usually block- usually spam) but by the same token, if you don't want hints, don't read the comments.
Monday, February 03, 2014
Contribute to the Martin Gardner Centennial
Dana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments here. I left a comment there, but I expand it for this blog entry.
When I got interested in mathematics in high school I went to the public library looking for math books (this was before Al Gore invented the internet). I found some books by Martin Gardner and began reading them. They were just right for the level of math I was on at the time. My very first proof that I read on my own (outside of a class) was in those books- the proof that (in the terminology I use now) a graph is Eulerian iff every vertex has even degree.
I learned about SOMA cubes (I bought a set and did every puzzle in the book in about 2 days.This is the only evidence that as a kid I was good at math). I learned the unexpected hanging paradox which confused me then (and still does). I learned the hercules-hydra game and other games that go on for a LOOOOOOOOOONG time. They are related to things in logic. I also learned about NIM games which I have used as a starting point for several student projects.
There have been some conferences in his honors, the Gathering-for-Gardner. I had the pleasure of reviewing some of the books from it. (My review is here.) These articles show that while his work was recreational this is not a well defined term- some if relates to very important and deep mathematics, and some deep math has arisen from such problems. The books also have articles about Gardner the Magician.
In the 2000's some of his books were reprinted and I was asked to review them for my SIGACT News book review column. I took this opp to do a joint review of several math recreational books. What a delight to reread his books and contrast them to those of his successors. And I STILL learned some math that I didn't know from them. (My review is here.)
Shortly before a column appears I always email the authors-of-books, authors-of-reviews, and publishers a first draft of my column. His publisher told me that he didn't use email (he was in his 90's!) so I postal mailed him my review. He read it, corrected some typos, but otherwise was quite happy with the review. He died a few months later. I was happy to have some contact, albeit short, with the man who helped keep me interested in math in high school and beyond.
When I got interested in mathematics in high school I went to the public library looking for math books (this was before Al Gore invented the internet). I found some books by Martin Gardner and began reading them. They were just right for the level of math I was on at the time. My very first proof that I read on my own (outside of a class) was in those books- the proof that (in the terminology I use now) a graph is Eulerian iff every vertex has even degree.
I learned about SOMA cubes (I bought a set and did every puzzle in the book in about 2 days.This is the only evidence that as a kid I was good at math). I learned the unexpected hanging paradox which confused me then (and still does). I learned the hercules-hydra game and other games that go on for a LOOOOOOOOOONG time. They are related to things in logic. I also learned about NIM games which I have used as a starting point for several student projects.
There have been some conferences in his honors, the Gathering-for-Gardner. I had the pleasure of reviewing some of the books from it. (My review is here.) These articles show that while his work was recreational this is not a well defined term- some if relates to very important and deep mathematics, and some deep math has arisen from such problems. The books also have articles about Gardner the Magician.
In the 2000's some of his books were reprinted and I was asked to review them for my SIGACT News book review column. I took this opp to do a joint review of several math recreational books. What a delight to reread his books and contrast them to those of his successors. And I STILL learned some math that I didn't know from them. (My review is here.)
Shortly before a column appears I always email the authors-of-books, authors-of-reviews, and publishers a first draft of my column. His publisher told me that he didn't use email (he was in his 90's!) so I postal mailed him my review. He read it, corrected some typos, but otherwise was quite happy with the review. He died a few months later. I was happy to have some contact, albeit short, with the man who helped keep me interested in math in high school and beyond.
Monday, April 18, 2016
Its hard to tell if a problem is hard. Is this one hard?
Here is a problem I heard about at the Gathering for Gardner. Is it hard? easy? boring? interesting? I don't know.
Let N={1,2,3,...}
PROBLEM: parameters are s (start point) and f (not sure why to call it f). both are in N
Keep in mind the sequence, in order, of operations:
DIVIDE BY f, SUBTRACT f, ADD f, MULTIPLY by f.
form the following sequence of numbers in N
a(0)= s
Assume a(0),...,a(n) are known. Let A = {a(0),...,a(n)}. N-A are the elements in N that are NOT in A.
If a(n)/f is in N-A then a(n+1)=a(n)/f
Else
If a(n)-f is in N-A then a(n+1)=a(n)-f
Else
If a(n)+f is in N-A then a(n+1)=a(n)+f
Else
If a(n)*f is in N-A then a(n+1) = a(n)*f
Else
If none of the above holds then the sequence terminates.
Lets do an example! Let a=14 and f=2
14, 7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 24, 22, 11, 9, 18, 16, 32, 30, 15, 13, 26, 28, 56, 54, 27, 25, 23, 21,
19, 17, 34, 36, 38, 40, 20, STOP since 10, 18, 22, 40 are all on the list.
Lets do another example! Let a=7, f=2
7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 9, 11, 13, 15, 17, ... (keeps going)
If f=2 and you get to an odd number x so that ALL of the odds less than x have already appeared but NONE of the odd numbers larger than x have appeared, then the sequence will go forever
with x, x+2, x+4, ...
QUESTIONS and META QUESTIONS
1) Can one characterize for which (s,f) the sequence stops.
2) Is it decidable to determine for which (s,f) the sequence stops.
3) Both (1) and (2) for either fixed s or fixed f.
4) Are the above questions easy?
5) Are the above questions interesting?
There are four categories:
Easy and Interesting- Hmmm, if its TOO easy (which I doubt) then I supposed can't be interesting.
Easy and boring.
Hard and interesting. This means that some progress can be made and perhaps connections to other mathematics.
Hard and Boring. Can't solve and are not enlightened for the effort.
Let N={1,2,3,...}
PROBLEM: parameters are s (start point) and f (not sure why to call it f). both are in N
Keep in mind the sequence, in order, of operations:
DIVIDE BY f, SUBTRACT f, ADD f, MULTIPLY by f.
form the following sequence of numbers in N
a(0)= s
Assume a(0),...,a(n) are known. Let A = {a(0),...,a(n)}. N-A are the elements in N that are NOT in A.
If a(n)/f is in N-A then a(n+1)=a(n)/f
Else
If a(n)-f is in N-A then a(n+1)=a(n)-f
Else
If a(n)+f is in N-A then a(n+1)=a(n)+f
Else
If a(n)*f is in N-A then a(n+1) = a(n)*f
Else
If none of the above holds then the sequence terminates.
Lets do an example! Let a=14 and f=2
14, 7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 24, 22, 11, 9, 18, 16, 32, 30, 15, 13, 26, 28, 56, 54, 27, 25, 23, 21,
19, 17, 34, 36, 38, 40, 20, STOP since 10, 18, 22, 40 are all on the list.
Lets do another example! Let a=7, f=2
7, 5, 3, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 9, 11, 13, 15, 17, ... (keeps going)
If f=2 and you get to an odd number x so that ALL of the odds less than x have already appeared but NONE of the odd numbers larger than x have appeared, then the sequence will go forever
with x, x+2, x+4, ...
QUESTIONS and META QUESTIONS
1) Can one characterize for which (s,f) the sequence stops.
2) Is it decidable to determine for which (s,f) the sequence stops.
3) Both (1) and (2) for either fixed s or fixed f.
4) Are the above questions easy?
5) Are the above questions interesting?
There are four categories:
Easy and Interesting- Hmmm, if its TOO easy (which I doubt) then I supposed can't be interesting.
Easy and boring.
Hard and interesting. This means that some progress can be made and perhaps connections to other mathematics.
Hard and Boring. Can't solve and are not enlightened for the effort.
Friday, June 22, 2018
The Muffin Problem
I've been meaning to post on THE MUFFIN PROBLEM for at least a year. Its a project I've been working on for two years, but every time I wanted to post on it I thought.
I'm in the middle of a new result. I'll wait until I get it!
However, I was sort of forced to finally post on it since Ken Regan (with my blessing) posted on it. In fact its better this way- you can goto his post for the math and I get to just tell you other stuff.
The problem was first defined by Alan Frank in a math email list in 2009.
I'll define the problem, though for more math details goto Ken's post: here.
You have m muffins and s students. You want to give each student m/s piece and
divide the muffins to maximize the min piece. Let f(m,s) be the size of the min piece
in an optimal divide-and-distribute procedure.
Go and READ his post, or skim it, and then come back.
Okay, you're back. Some informal comments now that you know the problem and the math
1) I saw the problem in a pamplet at the 12th Gathering for Gardner. Yada Yada Yada I have 8 co-authors and 200 pages, and a paper in FUN with algorihtms You never know when a problem will strike you and be worth working on!
(The 8 coauthors are Guangiqi Cui, John Dickerson, Naveen Dursula, William Gasarch, Erik Metz,
Jacob Prinze, Naveen Raman, Daniel Smolyak, Sung Hyun Yoo. The 200 pages are here. The FUN with algorithms paper, only 20 pages, is here)
2) Many of the co-authors are HS students. The problem needs very little advanced mathematics (though Ken thinks it might connect to some advanced math later). This is a PRO (HS students can work on it, people can understand it) and a CON (maybe harder math would get us more unified results)
3) The way the research had gone is a microcosm for math and science progress:
We proved f(m,s) = (m/s)f(s,m) (already known in 2009) by Erich Friedman in that math email list)
Hence we need only look at m>s.
First theorem: we got a simple function FC such that
f(m,s) ≤ FC(m,s)
for MANY m,s we got f(m,s) = FC(m,s).
GREAT! - conjecture f(m,s) = FC(m,s)
We found some exceptions, and a way to get better upper bounds called INT.
GREAT! - conjecture f(m,s) = MIN(FC(m,s),INT(m,s))
We found some exceptions, and a way to get better upper bounds called ... We now have
conjecture
f(m,s) = MIN(FC(m,s), INT(m,s), ERIK(m,s), JACOB(m,s), ERIKPLUS(m,s), BILL(m,s))
and it looks like we still have a few exceptions.
This is how science and math works- you make conjectures which are false but the refutations lead
to better and better results.
Also, we have over time mechanized the theorems, a project called:
Making Erik Obsolete
since Erik is very clever at these problems, but we would like to not have to rely on that.
4) I have worked hard on this problem as is clear from this: picture
I'm in the middle of a new result. I'll wait until I get it!
However, I was sort of forced to finally post on it since Ken Regan (with my blessing) posted on it. In fact its better this way- you can goto his post for the math and I get to just tell you other stuff.
The problem was first defined by Alan Frank in a math email list in 2009.
I'll define the problem, though for more math details goto Ken's post: here.
You have m muffins and s students. You want to give each student m/s piece and
divide the muffins to maximize the min piece. Let f(m,s) be the size of the min piece
in an optimal divide-and-distribute procedure.
Go and READ his post, or skim it, and then come back.
Okay, you're back. Some informal comments now that you know the problem and the math
1) I saw the problem in a pamplet at the 12th Gathering for Gardner. Yada Yada Yada I have 8 co-authors and 200 pages, and a paper in FUN with algorihtms You never know when a problem will strike you and be worth working on!
(The 8 coauthors are Guangiqi Cui, John Dickerson, Naveen Dursula, William Gasarch, Erik Metz,
Jacob Prinze, Naveen Raman, Daniel Smolyak, Sung Hyun Yoo. The 200 pages are here. The FUN with algorithms paper, only 20 pages, is here)
2) Many of the co-authors are HS students. The problem needs very little advanced mathematics (though Ken thinks it might connect to some advanced math later). This is a PRO (HS students can work on it, people can understand it) and a CON (maybe harder math would get us more unified results)
3) The way the research had gone is a microcosm for math and science progress:
We proved f(m,s) = (m/s)f(s,m) (already known in 2009) by Erich Friedman in that math email list)
Hence we need only look at m>s.
First theorem: we got a simple function FC such that
f(m,s) ≤ FC(m,s)
for MANY m,s we got f(m,s) = FC(m,s).
GREAT! - conjecture f(m,s) = FC(m,s)
We found some exceptions, and a way to get better upper bounds called INT.
GREAT! - conjecture f(m,s) = MIN(FC(m,s),INT(m,s))
We found some exceptions, and a way to get better upper bounds called ... We now have
conjecture
f(m,s) = MIN(FC(m,s), INT(m,s), ERIK(m,s), JACOB(m,s), ERIKPLUS(m,s), BILL(m,s))
and it looks like we still have a few exceptions.
This is how science and math works- you make conjectures which are false but the refutations lead
to better and better results.
Also, we have over time mechanized the theorems, a project called:
Making Erik Obsolete
since Erik is very clever at these problems, but we would like to not have to rely on that.
4) I have worked hard on this problem as is clear from this: picture
Sunday, June 19, 2022
Guest post by Prahalad Rajkumar: advice for grad students
I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a hard thing to search for. However, they were all written WAY AFTER Lance and I actually were grad students. Recently a former grad student at UMCP, Prahalad Rajkumar, emailed me that he wanted to do a post about advice for grad students. Since he has graduated more recently (Master degree in CS, topic was Monte Carlo Techniques, in 2009, then a job as a programmer-analyst) his advice may be better, or at least different, than ours was.
Here is his guest post with an occasional comment by me embedded in it.
----------------------------
I Made this Fatal Mistake when I Joined a Graduate Program at Maryland
Getting accepted to a graduate program in a good school is an honor.
It is also an opportunity to do quality work and hone your skills. I made one fatal mistake at the start of my master’s degree at the University of Maryland which took me down a vicious rabbit hole. I believed that I was not cut out for this program.
The Only Person Who Gave an Incorrect Answer
Before the start of my graduate studies, there was an informal gathering held for newer students and some faculty members. A faculty member asked a basic algorithm question.
Everyone in the room gave one answer. I gave another answer.
This is real life and not Good Will Hunting, and of course, I was wrong. I had misunderstood the question. It would have been a simple matter to shrug and move forward. But the paternal voice in my head saw a good opportunity to continue to convince me that I was an imposter who did not belong here.
Who is Smarter than Whom?
Some of my fellow incoming graduate students, who TAed with me for Bill Gasarch’s class, played an innocent looking game.
“That guy is so smart”.
“I wish I were as smart as her”.
They couldn’t know that this would affect me. I too did not know that this could affect me. But it did. I asked myself “Am I smarter than person X?”. Each time, the paternal voice in my head was quick to answer “No”. And each time I took this “No” seriously.
NOTE FROM BILL: Professors also play who is smarter than who game and we shouldn't.
I Didn’t Choose My Classes Wisely
I made a few mistakes in choosing my classes. I chose Concrete Complexity with Bill, which I later realized I had no aptitude for. I chose an undergraduate class taught by a professor whose style did not resonate with me. Mercifully, I chose a third class that I liked and excelled in. A class which did not destroy my confidence.
In retrospect, though I chose a couple of classes that were not my cup of tea, I compounded my problems with the stories I told myself. I had several good options available to me. I could redouble my efforts in the said classes and give it my best shot. I could accept my inevitable “B” grades in these classes, and be mindful to choose better classes in the upcoming semesters.
I, however, did the one thing I should not have done: I further convinced myself that I was not cut out to be a graduate student.
NOTE FROM BILL: Some students wisely ask around to find out who is a good teacher? Prahalad points out that this is just the first question. A class may be appropriate for you or not based on many factors, not just if the instructor is a good teacher.
I Fell Victim to Impostor Syndrome
I kept compounding my woes in my second and third semesters. Things got bad -- I took up a position as a research assistant in my third semester. My confidence was low -- and I struggled to do basic tasks that fall under my areas of competence.
In my fourth semester, I convinced myself that I could not code. In a class project where I had to do some coding as a part of a group project, I struggled to write a single line of code.
When I confessed this to one of my group members, he got me out of my head. He got me to code my part more than capably. I’ve written about this experience here.
It Does Not Matter in the Slightest
I wish I could tell the 2007 version of myself the following: It doesn’t matter who is smarter than whom. In any way whatsoever. We are on our individual journeys. In graduate school. In life.
Comparing myself with another person is as productive as playing several hours of angry birds.
The Admission Committee Believed in Me.
There was one good reason I should have rejected the thought that I did not belong in the program. The admission committee believed that I belonged here. Consisting of several brilliant minds. If they thought I should be here, why should I second guess them?
NOTE FROM BILL: While the Admissions committee DID believe in Prahalad and was CORRECT in this, I would not call the committee brilliant. As is well known, the IQ of a committee is the IQ of its dumbest member divided by the number of people on the committee.
Bill Gasarch’s Secret Sauce
Since I took a class with Bill and TAed for him, I had occasion to spend a lot of time with Bill.
In one conversation, Bill told me something profound. He told me the secret sauce behind his accomplishments. No, it was not talent. It was his willingness to work as hard as it takes.
And working hard is a superpower which is available to anyone who is inclined to invoke it. I wish I had.
BILL COMMENT: The notion that hard work is important is of course old. I wonder how old. One of the best expressions of this that I read was in a book Myths of Innovation which said (a) Great ideas are over rated, (b) hard work and follow through are underrated. There are more sources on this notion in the next part of Prahalad's post. (Side Note- I got the book at the Borders Books Going Out of Business Sale. Maybe they should have read it.)
Talent is Overrated.
I read a few books in the last couple of years that discussed the subject of mastery: Mastery by Robert Greene, Peak by Anders Ericsson, Talent is Overrated by Geoff Colvin, The Talent Code by Daniel Coyle, Grit by Angela Duckworth, Mindset by Carol Dweck
There was one point that all of these books made: talent is not the factor which determines a person’s success. Their work ethic, their willingness to do what it takes, and several hours of deliberate practice is the secret of success. Of course, talent plays a part -- you can’t be 5’1 and hope to be better than Michael Jordan. But in the graduate school setting, where a majority are competent, it really is a matter of putting in the effort.
Follow the Process
Bill Walsh signed up as the coach of the languishing 49ers football team. The title of his bestselling book describes his coaching philosophy: The Score Takes Care of Itself. He established processes. Focusing on the smallest of details. Walsh made everyone in the football team and in the administrative departments follow their respective processes. Long story short: the score took care of itself. The 49ers won 3 super bowls among other impressive performances.
If I had to do it all again: I would get out of my head. And keep going with a disciplined work ethic. Establish a process. Follow the process. And let the results take care of themselves.
All’s Well That Ends Well
I grinded and hustled and successfully completed my Masters degree. However, instead of making the journey a joyride, I got in my own way and complicated things for no good reason.
Final Thoughts
As William James said, a person can change his life by changing his attitude. All I needed to do was change my thinking -- work hard -- and the “score would have taken care of itself”.
I thought I was alone. But I found out in other spheres that a non-negligent percentage of people fall prey to the impostor syndrome. I wanted to write this to help any student who may be going through the problem that I did. If you are going through self-doubt, my message to you is to get out of the head, believe that you are capable (and make no mistake, you certainly are), do the work diligently,
follow the process, and let the score take care of itself.
Thursday, May 17, 2012
Meetings/Conferences/Workshops/Seminars- whats in a name?
In June 11-14 will be a new workshop: Algorithmic Frontiers.
How many venues do we have for meetings?
Algorithmic Frontiers seems to be a 4-day open workshop that has invited talks only. I don't know how big it will be but I would guess between 100 and 200.
Do the gatherings that we go to work? As my Software engineering friend Jim Purtilo often says If you don't know your goals you are not going to achieve them. So, what are the goals? Ultimately to help both us as individuals and us as a community in our research. The hope is we learn things and get inspired to work on problems. And these can be done by the formal talks in the ballroom and informal talks in the hallways. Does this happen? Yes. Is it cost effective (not just money but time)? Debatable, as this and other blogs have debated. Here are my experiences. What are yours?
What venues to YOU get the most out of? Why or why not?
How many venues do we have for meetings?
- What the call themselves:
Meetings (e.g., MATHFEST), Conferences (e.g., STOC), Workshops (Barriers), Seminars (e.g., Dagstuhl), Tutorials, Lunches. More?
(six options)
- Criteria for getting a paper in: Refereed (e.g., STOC): lightly refereed (I think MATHFEST), unrefereed, talks-by-invite-only (Algorithmic Frontiers, Barriers)
(four options)
- Participants: Open (most)or by-invite-only (Dagstuhl and Bertinoro) (two options)
- Size: This is more informal. However, CCC is small (100), STOC is larger (around 400), FCRC larger still, and Supercomputing is expecting 11,000. Medical conventions can get around 20,000.
(five options, though could be more or less depending on your mood.)
- Variety of activities: A venue can have any combination of the following: contributed talks (unrefereed), refereed talks (typical STOC), invited talks, rump sessions,
tutorials, workshops, short courses. (128 combinations, though in reality only about 5 options actually happen, so I'll take it as 5)
- Length: Number of days can be anything from 1 day to 2 months. However, I don't think all 60 options really exist. I've seen 1,2,3,4,5 days, 1 week, 2 weeks, 1 month, and 2 months. nine options.
- Expense: Either expensive or VERY expensive.
Algorithmic Frontiers seems to be a 4-day open workshop that has invited talks only. I don't know how big it will be but I would guess between 100 and 200.
Do the gatherings that we go to work? As my Software engineering friend Jim Purtilo often says If you don't know your goals you are not going to achieve them. So, what are the goals? Ultimately to help both us as individuals and us as a community in our research. The hope is we learn things and get inspired to work on problems. And these can be done by the formal talks in the ballroom and informal talks in the hallways. Does this happen? Yes. Is it cost effective (not just money but time)? Debatable, as this and other blogs have debated. Here are my experiences. What are yours?
- DAGSTUHL SEMINARS. These are specialized one-week long meetings by
invitation only. The talks need not be on the latest/greatest thing and hence are understandable. (I've been to DAGSTUHL- Complexity 3 times.)
- Bertinoro is similar to Dagstuhl. I've been to the RATLOCC 2011 and
RATLOCC 2009 which are on Ramsey Theory and Logic. Here there were even more talks
that were surveys or historical-perhaps because math moves slower than computer science.
If the talks were on the INTERSECTION Of Ramsey Theory and Logic then it would be too specialized.
(I've worked in both, but not quite together.)
As is, its a nice mix.
But the main point- I understood the talks.
- The Center for Intractability sponsors workshops which anyone can go to
but the speakers are picked by them. I've been to one of the Barriers workshops and it was very good. The speakers have more time then at conferences,
which is a plus. The Algorithmic Frontiers workshop seems to be in this model.
- The last few CCC's and STOC's that I've gone to I have enjoyed and gotten stuff out of, but not as much as the smaller venues.
Partly because the talks are shorter.
which is a plus. The Algorithmic Frontiers workshop seems to be in this model.
- MATHFEST is nice in that there is a VARIETY Of activities- workshops, seminar, tutorials, invited talks.
Very large which is both good (that's why they can have all of these things and bad (I never met the same person twice).
- One of my colleagues, Jeff Hollingsworth, is organizing SC12, Supercomputing 2012.
This will have 11,000 people at it. The program committee has over 100 people
on it. This seems... large. They seem to have a variety of activities
so it more like MATHFEST.
- Of course the talks are only part of the reason to go to these things. Even so, for me they are a big reason.
What venues to YOU get the most out of? Why or why not?
Tuesday, August 21, 2012
Fellow blogger Abie Flaxman named Top Innovator!
(Guest post from William Heisel, Assistant Director for External Relations, Institute for Health Metrics and Evaluation, University of Washington, 2301 5th Avenue, Suite 600,Seattle, WA 98121)
Abraham (Abie) Flaxman who writes the Healthy Algorithms blog
(which is on Complexity Blogs' Blog Roll) has been named one of the world's top young innovator by MIT. This is a sign that algorithms are finally getting a little respect in the global health and technology worlds.
In global health the rock stars are the vaccines, new toilets, and bed nets. Health measurement is considered something for bean counters whose pasty skin never sees the blistering Sub-Saharan African sun. But what about the tech junkies? They must see the value in crunching all those numbers to do the world some good? Not so much. Techies get excited about apps and gadgets and new ways to monetize web hits.
Finally, Technology Review, MIT's tech industry Bible, is naming a health measurement pioneer (who happens to work at the Instutite for Health Metrics and Evaluation (IHME) IHME) to its list of the world's top young technology pioneers. Here is the official press release:
For the first time, a prestigious technical innovation honor from the Massachusetts Institute of Technology (MIT) will go to an expert in health measurement: Abraham Flaxman, an Assistant Professor of Global Health at the Institute for Health Metrics and Evaluation (IHME) at the University of Washington (UW).
Since 1999, MIT's Technology Review has honored the world's top innovators under the age of 35 (TR35), in fields such as biotechnology, software, and energy. Until this year, the TR35 judges have not named an innovator in health measurement. Dr. Flaxman was selected from more than 250 nominations by a panel of expert judges and the editorial staff of Technology Review. Past winners include Facebook founder Mark Zuckerberg and Google co-founders Sergey Brin and Larry Page.
Abie's technical innovations in the field of global health have been game changing in our ability to measure health and health interventions, IHME Director Dr. Christopher Murray said. He has - and continues to be - at the forefront of pioneering methods that improve our ability to measure health outcomes and the effectiveness of interventions that address the world's greatest health challenges.
Nowhere is this more important than in the upcoming Global Burden of Disease (GBD) 2010 Study. Dr. Flaxman is the youngest member of the core team for the ambitious study that aims to provide the most comprehensive assessment to date of the burden from death and disability for more than 300 diseases, risk factors and injuries. Dr. Flaxman advanced a new way of disease modeling that allows researchers to combine all of the world's data on prevalence incidence, remission, and mortality and produce consistent estimates of the way diseases progress through the population, as a function of age, time, sex, and geography. When the GBD study is published, it will give governments and health program funders the best picture yet of how the world has advanced or fallen behind in efforts to improve population health. We are able to understand what is truly causing the greatest amount of mortality and disability in the world because of technical advancements that can be traced back to Abie scribbling on a white board in his office, said Dr. Mohsen Naghavi, Associate Professor of Global Health at IHME and one of the lead researchers on the GBD project.
Dr. Flaxman also has made significant advancements in verbal autopsy methods for gathering health data in low-resource settings. His machine learning algorithm for computer-certified verbal autopsy takes the results of a health interview of relatives about a recently deceased person and automatically determines the cause of death. He also created a stock-and-flow model for tracking the distribution of insecticide-treated bed nets to prevent malaria. The results are updated annually and included in the World Health Organization's World Malaria Report. The advancements Dr. Flaxman and colleagues have made in data-driven data quality audits (D3QA) were recently recognized at the Symposium on Computing for Development. Their publication on the development of the D3QA tool won on the best-paper award. The tool can be used to ensure that health data and other data gathered from household surveys are accurate. It is currently being used in research aimed at estimating mortality from war-related causes in Iraq.
Dr. Flaxman has accomplished all of this in just four years. He was on track to join the legions of computer scientists who staff technology giants such as Microsoft and Amazon. While working at Microsoft Research in 2008, he applied for an IHME Post-Graduate Fellowship. His extraordinary work as a Post-Graduate Fellow propelled him to being hired as a UW faculty member.
The world is not lacking in health data, and yet certain basic information has never been quantified, Dr. Flaxman said. I realized four years ago that I could use computational algorithms to solve some of these measurement challenges in global health. And I am incredibly honored to have been recognized by the TR35 judges for this work. Dr. Flaxman will discuss his work alongside other TR35 honorees at the EmTech MIT 2012 conference at the MIT Media Lab in Cambridge, October 24-26. All the TR35 winners for 2012 will be featured in the Sept/Oct issue of Technology Review
The Institute for Health Metrics and Evaluation (IHME) is an independent global health research center at the University of Washington that provides rigorous and comparable measurement of the world's most important health problems and evaluates the strategies used to address them. IHME makes this information freely available so that policymakers have the evidence they need to make informed decisions about how to allocate resources to best improve population health.
For more information about IHME, please visit: here. Technology Review, Inc., is an independent media company owned by MIT It publishes Technology Review magazine, the world's longest-running technology magazine (established 1899). Additional information about TR35 winners and judges is available here For more information about EmTech MIT 2012, please visit: here.
Abraham (Abie) Flaxman who writes the Healthy Algorithms blog
(which is on Complexity Blogs' Blog Roll) has been named one of the world's top young innovator by MIT. This is a sign that algorithms are finally getting a little respect in the global health and technology worlds.
In global health the rock stars are the vaccines, new toilets, and bed nets. Health measurement is considered something for bean counters whose pasty skin never sees the blistering Sub-Saharan African sun. But what about the tech junkies? They must see the value in crunching all those numbers to do the world some good? Not so much. Techies get excited about apps and gadgets and new ways to monetize web hits.
Finally, Technology Review, MIT's tech industry Bible, is naming a health measurement pioneer (who happens to work at the Instutite for Health Metrics and Evaluation (IHME) IHME) to its list of the world's top young technology pioneers. Here is the official press release:
For the first time, a prestigious technical innovation honor from the Massachusetts Institute of Technology (MIT) will go to an expert in health measurement: Abraham Flaxman, an Assistant Professor of Global Health at the Institute for Health Metrics and Evaluation (IHME) at the University of Washington (UW).
Since 1999, MIT's Technology Review has honored the world's top innovators under the age of 35 (TR35), in fields such as biotechnology, software, and energy. Until this year, the TR35 judges have not named an innovator in health measurement. Dr. Flaxman was selected from more than 250 nominations by a panel of expert judges and the editorial staff of Technology Review. Past winners include Facebook founder Mark Zuckerberg and Google co-founders Sergey Brin and Larry Page.
Abie's technical innovations in the field of global health have been game changing in our ability to measure health and health interventions, IHME Director Dr. Christopher Murray said. He has - and continues to be - at the forefront of pioneering methods that improve our ability to measure health outcomes and the effectiveness of interventions that address the world's greatest health challenges.
Nowhere is this more important than in the upcoming Global Burden of Disease (GBD) 2010 Study. Dr. Flaxman is the youngest member of the core team for the ambitious study that aims to provide the most comprehensive assessment to date of the burden from death and disability for more than 300 diseases, risk factors and injuries. Dr. Flaxman advanced a new way of disease modeling that allows researchers to combine all of the world's data on prevalence incidence, remission, and mortality and produce consistent estimates of the way diseases progress through the population, as a function of age, time, sex, and geography. When the GBD study is published, it will give governments and health program funders the best picture yet of how the world has advanced or fallen behind in efforts to improve population health. We are able to understand what is truly causing the greatest amount of mortality and disability in the world because of technical advancements that can be traced back to Abie scribbling on a white board in his office, said Dr. Mohsen Naghavi, Associate Professor of Global Health at IHME and one of the lead researchers on the GBD project.
Dr. Flaxman also has made significant advancements in verbal autopsy methods for gathering health data in low-resource settings. His machine learning algorithm for computer-certified verbal autopsy takes the results of a health interview of relatives about a recently deceased person and automatically determines the cause of death. He also created a stock-and-flow model for tracking the distribution of insecticide-treated bed nets to prevent malaria. The results are updated annually and included in the World Health Organization's World Malaria Report. The advancements Dr. Flaxman and colleagues have made in data-driven data quality audits (D3QA) were recently recognized at the Symposium on Computing for Development. Their publication on the development of the D3QA tool won on the best-paper award. The tool can be used to ensure that health data and other data gathered from household surveys are accurate. It is currently being used in research aimed at estimating mortality from war-related causes in Iraq.
Dr. Flaxman has accomplished all of this in just four years. He was on track to join the legions of computer scientists who staff technology giants such as Microsoft and Amazon. While working at Microsoft Research in 2008, he applied for an IHME Post-Graduate Fellowship. His extraordinary work as a Post-Graduate Fellow propelled him to being hired as a UW faculty member.
The world is not lacking in health data, and yet certain basic information has never been quantified, Dr. Flaxman said. I realized four years ago that I could use computational algorithms to solve some of these measurement challenges in global health. And I am incredibly honored to have been recognized by the TR35 judges for this work. Dr. Flaxman will discuss his work alongside other TR35 honorees at the EmTech MIT 2012 conference at the MIT Media Lab in Cambridge, October 24-26. All the TR35 winners for 2012 will be featured in the Sept/Oct issue of Technology Review
The Institute for Health Metrics and Evaluation (IHME) is an independent global health research center at the University of Washington that provides rigorous and comparable measurement of the world's most important health problems and evaluates the strategies used to address them. IHME makes this information freely available so that policymakers have the evidence they need to make informed decisions about how to allocate resources to best improve population health.
For more information about IHME, please visit: here. Technology Review, Inc., is an independent media company owned by MIT It publishes Technology Review magazine, the world's longest-running technology magazine (established 1899). Additional information about TR35 winners and judges is available here For more information about EmTech MIT 2012, please visit: here.
Tuesday, March 17, 2020
Richard Guy passed away at the age of 103
Richard Guy passed away on March 9, 2020 at the age of 103. Before he died he was the worlds oldest living mathematician (see here for a list of centenarians who are famous scientists or mathematicians). He was also the oldest active mathematician-- he had a paper on arxiv (see here) in October of 2019. (ADDED later since a commenter pointed it out to me--- a paper by Berlekamp and Guy posted in 2020: here)
I met him twice- once at a Gathering for Gardner, and once at an AMS meeting. I told him that Berlekamp-Conway-Guy had a great influence on me. He asked if it was a positive or negative influence. He also seemed to like my talk on The Muffin Problem, though he might have been being polite.
I did a blog about Richard Guy on his 103rd birthday, so I recommend readers to go there
for more about him. One point I want to re-iterate:
Richard Guy thought of himself of an amateur mathematician. If he means someone who does it for love of the subject then this is clearly true. If it is a measure of how good he is (the term `amateur' is sometimes used as an insult) then it is clearly false. If it means someone who does not have formal training than it is partially true.
I met him twice- once at a Gathering for Gardner, and once at an AMS meeting. I told him that Berlekamp-Conway-Guy had a great influence on me. He asked if it was a positive or negative influence. He also seemed to like my talk on The Muffin Problem, though he might have been being polite.
I did a blog about Richard Guy on his 103rd birthday, so I recommend readers to go there
for more about him. One point I want to re-iterate:
Richard Guy thought of himself of an amateur mathematician. If he means someone who does it for love of the subject then this is clearly true. If it is a measure of how good he is (the term `amateur' is sometimes used as an insult) then it is clearly false. If it means someone who does not have formal training than it is partially true.
Friday, April 13, 2018
Lance and Bill Gather for Gardner
Every two years in Atlanta, recreational mathematicians gather to honor Martin Gardner, whose Scientific American column Mathematical Games through the 60's and the 70's. Those columns inspired budding mathematicians of a certain age including Bill and I.
Bill came down to this years Gathering for Gardner 13. Talks are only six minutes long. Bill talked on the Muffin Problem right after an 8-year old and right before Stephan Wolfram.
We also did a short vidcast from the exhibition room.
Bill came down to this years Gathering for Gardner 13. Talks are only six minutes long. Bill talked on the Muffin Problem right after an 8-year old and right before Stephan Wolfram.
We also did a short vidcast from the exhibition room.
Tuesday, June 30, 2009
The NSF Annual Report
The NSF has been getting very strict about having PIs (primary investigators) fill out an annual report listing publications and activities related to their grants. The report is due 90 days before the anniversary of the start of the grant, so if you have a grant that started in the fall you are probably getting notices reminding you that your report is now overdue.
There are few academic tasks more painful than filling out annual grant reports but best to just grit your teeth and do it or the NSF could cut off your money. Would you rather the alternative, not having to do a report because you don't have a grant?
Annual reports are used more for gathering information than for evaluation so you don't need to worry about the style as much as you might for a grant proposal.
There is one confusing part of the reporting system on NSF Fastlane: There are separate sections for conferences and publications. Most of our conferences don't show up under conferences so best to just list your other conference papers as proceedings in the publications section, probably under "Books or Other One Time Publications".
Fastlane reporting is a one-size fits all system so it is not well designed for the way computer science handles conferences. But we computer scientists always know how to implement the Kludge.
Update 7/10: NSF Theory Program Director Richard Beigel makes available a Sample Report (Dan Spielman) and Sample Findings (Mihir Bellare).
Tuesday, October 31, 2017
The k=1 case is FUN, the k=2 case is fun, the k\ge 3 case is... you decide.
(All of the math in this post is in here.)
The following problem can be given as a FUN recreational problem to HS students or even younger: (I am sure that many of you already know it but my point is how to present it to HS students and perhaps even younger.)
Alice will say all but ONE of the elements of {1,...,1010}in some order.
Bob listens with the goal of figuring out the number. Bob cannot possibly store 1010 numbers in his head. Help Bob out by giving him an algorithm which will not make his head explode.
This is an easy and fun puzzle. The answer is in the writeup I point to above.
The following variant is a bit harder but a bright HS student could get it: Same problem except that Alice leaves out TWO numbers.
The following variant is prob more appropriate for a HS math competition than for a FUN gathering of HS students: Same problem except that Alice leaves out THREE numbers.
The following variant may be easier because its harder: Alice leaves out k numbers, k a constant. Might be easier then the k=3 case since the solver knows to NOT use properties of 3.
I find it interesting that the k=1, k=2, and k≥ 3 cases are on different levels of hardness. I would like a more HS answer to the k≥ 3 case.
The following problem can be given as a FUN recreational problem to HS students or even younger: (I am sure that many of you already know it but my point is how to present it to HS students and perhaps even younger.)
Alice will say all but ONE of the elements of {1,...,1010}in some order.
Bob listens with the goal of figuring out the number. Bob cannot possibly store 1010 numbers in his head. Help Bob out by giving him an algorithm which will not make his head explode.
This is an easy and fun puzzle. The answer is in the writeup I point to above.
The following variant is a bit harder but a bright HS student could get it: Same problem except that Alice leaves out TWO numbers.
The following variant is prob more appropriate for a HS math competition than for a FUN gathering of HS students: Same problem except that Alice leaves out THREE numbers.
The following variant may be easier because its harder: Alice leaves out k numbers, k a constant. Might be easier then the k=3 case since the solver knows to NOT use properties of 3.
I find it interesting that the k=1, k=2, and k≥ 3 cases are on different levels of hardness. I would like a more HS answer to the k≥ 3 case.
Monday, September 30, 2019
Richard Guy is 103 years old today
Richard Guy is a mathematician. He co-authored the classic book Winning Ways for your Mathematical Plays with Elywn Berlekamp and John Conway.
On Sept 30 (today) he turned 102. According to this list he is the oldest living mathematician, and he would need to live to 110 to be the oldest mathematician ever.
I have met him twice. He was at the Gathering for Gardner Conference as a young 98-year old. I told him that his book Winning Ways had a great influence on me. He asked it if was positive or negative. I later saw him at a Math conference where he went to my talk on The Muffin Problem. So he is still active.
His Wikipedia site says that he says he regards himself as an Amateur Mathematician. While it is awkward to disagree with how someone sees himself, I'll point out that he is an author or co-author of 11 books, has many papers, and has solved Erdos Problems. He has taught some but I couldn't really find out what his source of income is or was. This takes us back to the word `amateur' which has several meanings:
Amateur: Someone who does X for the love of X (Amor is Love in Spanish), and not for money. This could be true of Richard Guy. This notion of amateur may be lost on my younger readers since this it used to be a thing to NOT take money since it somehow soils what you do. In those days Olympic athletes could not have played professionally beforehand. We can't imagine that now.
Amateur: Someone who dabbles in something but is not really that good. This could NOT be true of Richard Guy.
Aside from games he has also worked in Number Theory. His book Unsolved Problems in Number Theory has inspired many (including me).
So happy birthday Richard Guy!
He is the also the oldest living person we have honored on this blog. Second oldest was Katherine Johnson, see who is still alive.
ADDED LATER- some people emailed me if Richard Guy was still actively doing mathematics. Here is a recent paper of his: here
On Sept 30 (today) he turned 102. According to this list he is the oldest living mathematician, and he would need to live to 110 to be the oldest mathematician ever.
I have met him twice. He was at the Gathering for Gardner Conference as a young 98-year old. I told him that his book Winning Ways had a great influence on me. He asked it if was positive or negative. I later saw him at a Math conference where he went to my talk on The Muffin Problem. So he is still active.
His Wikipedia site says that he says he regards himself as an Amateur Mathematician. While it is awkward to disagree with how someone sees himself, I'll point out that he is an author or co-author of 11 books, has many papers, and has solved Erdos Problems. He has taught some but I couldn't really find out what his source of income is or was. This takes us back to the word `amateur' which has several meanings:
Amateur: Someone who does X for the love of X (Amor is Love in Spanish), and not for money. This could be true of Richard Guy. This notion of amateur may be lost on my younger readers since this it used to be a thing to NOT take money since it somehow soils what you do. In those days Olympic athletes could not have played professionally beforehand. We can't imagine that now.
Amateur: Someone who dabbles in something but is not really that good. This could NOT be true of Richard Guy.
Aside from games he has also worked in Number Theory. His book Unsolved Problems in Number Theory has inspired many (including me).
So happy birthday Richard Guy!
He is the also the oldest living person we have honored on this blog. Second oldest was Katherine Johnson, see who is still alive.
ADDED LATER- some people emailed me if Richard Guy was still actively doing mathematics. Here is a recent paper of his: here
Thursday, July 07, 2011
Scooped by 400 years
This
article claims that finding the area under a curve by dividing up the region into
rectangles is helpful. Maybe they could take some sort of... limiting process where
the rectangles get skinnier. Who knows- they may be able to get an EXACT formula
for, say, the area under the curve y=x2 from x=0 to a.
(The Wikipedia entry on the article claims that it rediscovered the
trapezoid rule. See here.)
I was going to begin an April fools day post with the above; however since the article (which is real) is already out there and being criticized here, here, here, here, and here, I decided to not go that direction. I have a different angle.
How often do you get a result and then find that someone else already had it? Is this MORE or LESS common in the internet age? There are several competing forces:
I was going to begin an April fools day post with the above; however since the article (which is real) is already out there and being criticized here, here, here, here, and here, I decided to not go that direction. I have a different angle.
How often do you get a result and then find that someone else already had it? Is this MORE or LESS common in the internet age? There are several competing forces:
- With Search tools its EASIER to find whats already out there.
- With email or various websites like stack exchange it is EASIER to ASK if something is already known.
- Some people are gathering up stuff and putting it on line making it EASIER to find- if you know where to look. (Examples: Website of all of Ronald Graham's papers, or Website of some number theory related to VDW stuff). I thought I found a website of secret sharing papers and when I tried to find it again I hit several sites about different kinds of secrets.) ADDED LATER: updated site for Ron Graham's papers: here, and list (but not links) of papers on secret sharing are here.)
- Areas are getting more specialized and each use their own terminology making it HARDER to know if what you have done is original.
- There is so much is out there that it is HARDER to see whats already been done.
- NOT everything is online. The material that is not online might be HARDER to find then they used to be.
Wednesday, February 19, 2014
Analog Adventures
I just finished a new book on D&D Of Dice and Men by David Ewalt. Ewalt tells three interlocking stories: The history of D&D, Ewalt's personal journey into the game, and some campaigns he's embarked on from the characters' point of view. Gary Gygax and Dave Arneson originally created the game but Dave soon left the company and was written out of the books. Gary mismanaged the company which has bounced around from various owners every since. I hadn't really kept up with D&D after college and I'm surprised that it has so many incompatible versions (reminds me of LaTeX and Python). A fifth version of D&D to unite them all is due for release this summer.
My daughter's school just put on a production of She Kills Monsters, a play about a woman who discovers her late sister through the sister's D&D adventures. My daughter played an evil cheerleader and her line "We're way too powerful for you" reminded us both of her classic role as NP.
These days we have immersive rich interactive games on our Play Stations and smart phones but still there is still nothing like gathering around a table transformed into a tavern as we meet our fellow adventurers and embark on the next quest.
Subscribe to:
Posts (Atom)