April 30th, 2012 — Math, Puzzle
In this sentence the number of occurrences of 1 is 2, of 2 is 3, of 3 is 2, of 4 is 1.
This self-referential, true sentence is a variant of a puzzle attributed to the logician Raphael Robinson, popularized in Douglas Hofstadter’s book Metamagical Themas. In the book the puzzle appears in the following form:
Fill in the gaps such as to make the sentence true:
In this sentence the number of occurrences of the digit 0 is __, of digit 1 is __, of digit 2 is __, ..., of digit 9 is __.
With some trial and error you can find two different solutions, and it has been shown that no other solutions are possible. The problem has also been studied using some theory from the field of dynamical systems. Here are two interesting links, both containing the solution of the puzzle.
In this post, however, I would like to look at a slightly different puzzle. Instead of counting digits, I am counting the numbers as indivisible units. If, for instance, “15” appears in the sentence, I count it as “15”, not as one “1” and one “5”. In this way the problem is independent of the base in which the numbers are represented.
In both of the following two puzzles the task is to fill in the gaps such as to make the sentences true. In the first sentence the values can be between 1 and n (including 1 and n), in the second sentence the values can be between 0 and n-1 (both included). For what values of n are the problems solvable? How many solutions are there?
In this sentence the number of occurrences of 1 is __, of 2 is __, ..., of n is __.
In this sentence the number of underlined occurrences of 0 is __, of 1 is __, of 2 is __, ..., of n-1 is __.
Think about the puzzles for some time, or scroll down for the solution. Let me know if you find a simpler solution. I also wrote a follow-up post, with a different variant of the problem.
.
.
.
.
.
.
It can be shown that the two problems are equivalent: let’s denote the numbers written in the gaps of the first sentence by f(1), …, f(n). It can be seen easily that f(1), …, f(n) form a solution for the first problem if and only if f(1)-1, …, f(n)-1 form a solution for the second problem. So it’s enough to look at the first puzzle only.
With some case-based analysis we can show that there is no solution for the cases n=1, n=2, n=3 and n=6.
For n=4, there are two solutions, the one given in the beginning of the post and the following: f(1)=3, f(2)=1, f(3)=3, f(4)=1.
For n=5, the solution is given by the sequence: f(1)=3, f(2)=2, f(3)=3, f(4)=1, f(5)=1 and it is unique. These can be verified manually.
For every n>=7, there is a solution, given by f(1)=n-3, f(2)=3, f(3)=2, f(n-3)=2, and f(k)=1, for every k other than 1,2,3, and n-3. Let’s prove that this is the only solution:
Suppose there is some other solution.
If f(1)=n-3, then f(n-3)>=2.
—> If f(n-3)=2, then we need f(2)>=3.
——> If f(2)=3, then we get the same solution.
——> If f(2)>3, then there exist distinct x and y (also different from n-3, 1 and 2), for which f(x)=f(y)=2, so we have a value different from 1 at places 1,2,x,y,n-3, which means that we don’t have enough places to put 1’s, to satisfy f(1)=n-3.
—> If f(n-3)>2, then we have some x (different from 1 and n-3), for which f(x)=n-3. But then there are n-4 places where we need to put x, again not leaving enough places to satisfy f(1)=n-3.
If f(1)>n-3, then f(f(1))>=2.
—> If f(f(1))=2, then we need f(2)>=3 and f(f(2))>=2. We ran out of places for 1’s, since 1,2,f(2) and f(1) are distinct and they map to values different from 1.
—> If f(f(1))>2, then there is some x (other than 1) with f(x)=f(1)>=n-2, which means that we need to fill at least n-3 places with the value x, not leaving enough place for the 1’s.
The interesting case remains when f(1)<n-3. This condition means that in at least 5 places we need to write a number different from 1.
Suppose there are exactly k places, corresponding to the indices x1, …, xk, where we have an entry different from 1. This means that f(x1), …, f(xk) are different from 1 and k>=5. Let x1=1, since we know that in place 1 we have an entry different from 1.
Observe that among f(x1), …, f(xk) there have to be exactly k-1 distinct elements. This is because we need a value different from 1 in all places 1, f(x1), …, f(xk), and unless there are exactly k such places, we reached a contradiction. Since we have k-1 distinct elements all different from 1, the maximum among them is at least k and the second largest element is at least k-1. This means that there is a number t different from 1, such that f(t)>=k-1, therefore, t appears as a count in at least k-2 places. If out of k counts we have k-2 equal, we cannot have k-1 distinct values, so we reached a blatant contradiction. Therefore this case is impossible and the solution given above is unique.
April 14th, 2012 — Language, Puzzle
“Verdi is the Puccini of music” – this quip attributed to the composer Igor Stravinsky appears in Douglas Hofstadter’s book Metamagical Themas. In a similar vein he adds: “The knee is the Achilles’ heel of the leg”. A well-known humorist, probably inspired by the first sentence, uses the line “Beethoven is the Mozart of classical music”. Looking at a lavishly decorated building, we might say “It seems that Baroque has a renaissance”.
What is common in these humorous and somewhat faulty metaphors? Is there a name for this phenomenon? Are there other good examples?
To explain the obvious, suppose we are using analogies or metaphors of the form “X is Y”, where Y is the “source”, whose attributes we borrow, ascribing them to the “target” X. In this set-up, Y seems to play two roles: one concrete, immediate and one abstract, idealized. In the case of Mozart, the concrete role is that of the 18th century composer, while the abstract role is something along “a widely celebrated, brilliant and prolific, classical master of a genre”. Renaissance is the cultural movement started in Europe in the 14th century, but also the revival of a style, in the case of Renaissance itself, mostly of the classical Greek and Roman. Never mind that in this case the capitalization of the word betrays which meaning we are referring to.
The trick for the faulty metaphor to work (or in this case, for it not to work, i.e. to sound broken and to generate tension and/or humor), seems to hinge on our ability to move back and forth between the two roles, the concrete and the abstract. Furthermore, it is necessary that the analogy is understandable, in other words, that the abstract meaning is well established. In fact, the more overused the metaphor, the better it is for comical effect. The “Achilles’ heel of something” clearly fulfills this requirement. Still, “Shakespeare is the Mozart of English literature” and “Stone-washed jeans are having a renaissance” would be perfectly valid, if not very interesting analogies. To produce the effect we are looking for, we need one more ingredient: if we denote by Y1 and Y2 the concrete, resp. the abstract meanings of the source, we should choose Y in such a way that “X is Y2″ sounds fine, but X and Y1 are somehow clashing, for example, by being members of the same category, or by being downright contradictory. In this way, shifting to the “X is Y1″ meaning feels like falling into a trap.
Since there already exist snowclones, malapropisms, solecisms, contronyms, garden path sentences, it seems unfair that such a clearly delimited phenomenon does not have its own name. Can you suggest one? The examples above are all, in some sense, mixed metaphors, but the mixing happens in a well defined way. What would be a good neologism for metaphors broken in this particular way?
Here are some more examples that loosely fit the same structural pattern, although they are not necessarily funny. Please, let me know, if you can think of more!
- The queen is the king of chess pieces.
- The Russian campaign was Napoleon’s Waterloo moment.
- The lizard you keep in the kitchen has become the elephant in the living room in our relationship.
- The gold plating is the crown jewel of that necklace.
- The bald eagle is the canary in the coal mine of the ecosystem.
- The 700 pound gorilla that escaped the zoo is the 800 pound gorilla.
- That blue whale has become his white whale.
- The new fighter jet is the flagship of the army.
- “Raincoat” is an umbrella term for many different products.
- Alexander the Great solved the Gordian knot of defeating the Persian army.
- Theseus performed the herculean task of killing the Minotaur.
- Euro cents are a dime a dozen.
- Luxembourg is the Switzerland of Europe.
- A blue swan would be a black swan.
- A notebook is a textbook example of a stationery product.
- Latin was the lingua franca of medieval Europe.
- The cerebrospinal fluid is the lifeblood of the organism.
- John Smith is the John Doe of English names.
- Saab is Sweden’s answer to the Volvo.
EDIT:
- From niklasni1, over at reddit:
- Humans are the tortoises of the animal kingdom.
- Noah suggests the term Locaphor. Like it!
- Another one, similar to some of the above:
- By crossing the Po, Caesar crossed the Rubicon.
- cnan1u adds:
- Copper is the gold standard of electric wires.
- cnan1u also adds the following:
- Tobacco is the smoking gun of lung cancer.
- Women are the founding fathers of feminism.
- Bison were the bread and butter of early humans.
- The SI unit is the yardstick of measurement.
- Espresso is the barista’s cup of tea.
and many more. Thanks!
- Turns out that Richard Lederer’s book “Anguished English” has some more examples in its chapters “Mixed-Up Metaphors” and “Goldwynisms and Berraisms”.
December 14th, 2011 — Links, Reading
As 2011 approaches its end, as usual, I copy-paste the links to some of the most interesting, most over-the-top, most random and most obscure stuff I read on the internet (in English) throughout the year, in case you desperately need some reading material for dark and long evenings. Much (but not all) of the more opinionated stuff is the kind that I strongly agree with. Note to self: in 2012 read stuff that challenges, rather than reinforces your biases. (Previous links). So here it goes:
Motivation, lighter stuff
Ribbonfarm: In the real world. Also.
Hanging out with a different crowd.
Xamuel: ways to be more present.
Derek Sivers: flip the stick.
Changing perspective.
Anonymous psychedelic experience.
Ribbonfarm: being an illegible person.
Interesting observations, more substantial stuff
Norvig vs. Chomsky.
Ribbonfarm: Legibility.
Ribbonfarm: Bargaining with your right brain.
Daniel Mendelsohn: Arthur Rimbaud’s brief career.
Idlewords: Rocket to Nowhere – the story of the Shuttle.
Roger Ebert on why he hates 3D movies.
Less Wrong: Excuses.
Ribbonfarm: The Milo criterion.
Essay of N.N. Taleb, a summary of his ideas.
Idlewords: The social graph is neither.
Idlewords: Argentina – on two steaks a day.
RIP Michael Hart .
RIP Steve Jobs. Eulogy by Mona Simpson and by ESR.
Startups, Business, Programming
Ribbonfarm: the end of the Middle Class.
Tips for contract work on websites from a Reddit comment.
Raganwald: You need a degree for BigCo.
Why HR did not respond.
Joel: We hire the best 1%.
Joel: Architecture Astronouts.
Some of us just like to program.
Apenwarr: Interoperability, robustness, etc..
Two essays pointing out a pragmatic way towards startups.
Two other pieces of pragmatic advice on a similar topic.
The Gervais principle or office life according to The Office.
Steve Yegge: Code’s worst enemy.
Life at Google, life at Amazon, and a glimpse of both.
Don’t call yourself a programmer.
Maths, Research
Is it really power law?
Terence Tao: Problem solving strategies.
Michael Nielsen: Open access – a summary.
The Uppsala-affair.
Humorous
Two pieces lightly poking fun at Paul Graham.
How to criticize a computer scientist?
Burnout prevention at MIT.
The credit card prank.
Missy the lost cat.
As a bonus, here are the best books I’ve read in 2011:
July 19th, 2011 — Tech
Here’s a small idea I wrote about before: change the desktop wallpaper automatically using random images from Wikipedia. Why Wikipedia and not some other source? Because these images are generally more interesting, more diverse and better quality than any other collection I know.
Click this link a couple of times for some examples of random wiki images:
http://commons.wikimedia.org/wiki/Special:Random/File
Finally I managed to hack it together and here it is for you to download. I only tried it on Linux but probably it can be ran with small modifications on a Mac as well. If you manage to put together something like this on Windows let me know in the comments. Here are the steps:
1. What we need
- feh – this is a nice, lightweight image viewer ( https://wiki.archlinux.org/index.php/Feh )
- convert, mogrify – these are some utilities from the imagemagick set of tools (easily available on most distributions)
- wget – for fetching files from the internet
- sed, awk, grep, xargs – you have these already
If you don’t have the first three, on Ubuntu all you need to do is:
sudo apt-get install feh
sudo apt-get install imagemagick
sudo apt-get install wget
2. The main thing
Make a folder where you put the files needed for this wallpaper-changing-business. For me that is ~/random_wallpaper
Create the file run.sh in this newly created folder and copy the code below into it. The code does the following: it fetches the URL of a random image from Wikipedia, it fetches the image itself, makes an attempt to convert it to a decent size (change resolution in the code if necessary), makes an attempt to add the title of the image to the image, sets it as wallpaper, waits for an hour, removes the image and repeats. Additionally, it saves filenames and timestamps in an archive.txt file, so that if you see something interesting, you can look it up later. Feel free to tweak it to your needs, for example, the 60 minutes repeat period in the end could be made 20s or whatever else.
#!/bin/sh
while true; do
# Remove old file and get new random image
cat filename.txt | xargs rm
echo -n "http://upload" > url.txt
wget -q -O - "$@" http://commons.wikimedia.org/wiki/Special:Random/File | grep -m 1 "href=\"//upload" | sed -e 's/.*href\=\"\/\/upload//g' | sed -e 's/\".*//g' >> url.txt
url=`cat url.txt`
wget -O temp_image.tmp "$url"
echo -n "temp_image." > filename.txt
cat url.txt | sed -e 's/.*\///g' | sed -e 's/.*\.//g' >> filename.txt
filename=`cat filename.txt`
mv temp_image.tmp "$filename"
# Get filename of image for display
echo $url | awk -F"/" '{print $NF}' | awk -F. '{print $1}' > urldisplay.txt
urldisplay=`cat urldisplay.txt`
# Resize image and add title (filename)
mogrify -resize 1024x768\> "$filename"
convert -pointsize 20 -fill red -draw "text 10,30 "$urldisplay"" "$filename" "$filename"
# Set as wallpaper
feh --bg-center "$filename"
# Leave some traces in the logfile
echo -n `date` >> archive.txt
echo -n " " >> archive.txt
echo $url >> archive.txt
# Go to sleep
sleep 60m
done
Make this file executable:
chmod +x run.sh
3. Wrapping it up
All we need now is a way of running our script. If you want to try it out just once, or you want to use it as a slideshow on a birthday party, you can simply run it from the terminal:
./run.sh &
If you want to use it all the time, it should be called at each startup. This can be achieved in different ways, depending a bit on the setup used.
I run Fluxbox as a window manager, which is closely related to Blackbox or Openbox.
Here I add towards the end of my startup file the following:
~/random_wallpaper/run.sh &
If you use Gnome, you could add the same line to your ~/.xinitrc file. The Feh documentation says that to make it play nicely with Feh, you should disable Nautilus’ control of the desktop:
gconftool-2 --set /apps/nautilus/preferences/show_desktop --type boolean false
An alternative way of calling run.sh would be to set up a periodic job using cron. In this case the loop (the while- and the done- lines) are not needed.
Let me know in the comments how it worked out, or if you know a simpler way of setting it all up.
ENJOY!
July 9th, 2011 — Ideas
A few quick web app ideas, to get the ball rolling.. Some previous ones.
1. Your English is so 1890.
There was a popular widget some time ago, in which you paste some text that you wrote (or it processes your blog) and through a statistical analysis of word frequencies it tells you whether you write like Hemingway or more like Virginia Woolf or like Edgar Allan Poe or whoever. Then you get a badge you can put on your blog or on your wall in your favorite social network. It was quite nice and popular, although I can’t find it anymore (EDIT: here it is).
Mine is a tweak on this idea. Google has released a data set with the frequencies of words in books throughout the years (ngrams.googlelabs.com). Say, you might find that “computer” appeared in 5% of the books in 1970 and in 15% of those in 1985 (I am making this up). So, given any year, you can easily find out how likely a certain word is to appear in a randomly picked text. With Bayes rule and some reasonable assumptions we could reverse this and for a given snippet of text, compute the probability that the text was written in 1800 or in 1850 or in 1900, etc. We would pretend that a priori the text is just as likely to come from any year. This is not exactly true, since we know the text comes from the present, or at least we know that the amount of text available from any year grows as we get closer to the present, but let’s ignore all that for a moment. It would be more fun than exact science anyway. However, it could still generate interesting comparisons between the style, choice of words, favorite topics of different people, or the styles of different authors from the past. For example we might discover that some authors had a language that anticipated (or influenced) the future, while others were stuck using the language of the past.
2. World map with radios.
Online radios are a nice tool in learning any language, but often it is hard to find suitable ones. For learning or practicing a language the topic is perhaps less important as long as it is at least mildly interesting and as long as there is sufficient amount of talking (instead of just music), with a clear pronunciation that is representative for a given language/dialect. So what I would like is a world map with a curated list of online radio stations, placed on the map with pins, and for each station it would be given exactly what language/dialect they use, approximately how difficult are the topics discussed, what is the amount of slang, etc.
3. World map with unofficial regions.
Finding a political map with the official borders for countries/states/counties/etc. is easy. There exist however, many other types of regions:
- historical ones (those that in the past might have formed an administrative unit but they don’t anymore)
- linguistic regions (the region where a language/dialect is spoken)
- geographic regions not necessarily corresponding to administrative units (Silicon Valley, Gangetic Plain, etc.)
- regions of scientific interest: (the range of the Neanderthal man, the region of influence of classical Greek culture, the range of the Bengal tiger in 1900)
- etc.
It would be nice to have a tool for annotating maps in this way (possibly based on Google Maps) just as easily as we can add locations or paths between different points. Such regions, once drawn could be saved, embedded, printed, used in presentations, news articles, lectures, etc. or shared similarly to how users can share photos attached to places on Google Maps. Then, instead of the usual political/geographic view of the world, we could choose other filters/overlays created by others.
Another type of overlay would not have strict borders like regions, but would be a mapping of values onto geographical coordinates. The function value could be shown in colors or using contour curves or any other visualization, and the values could come from uploaded datasets or from some specified function. These types of visualizations exist of course, but I don’t know of a simple interface where users could create such maps.
4. World map live postcard.
A simple service that shows an empty world map and generates a unique url on demand. If someone visits the url, their geographic location appears on the map. This can be done of course with analytics software, but the key here is that a) this is real-time b) accessible to everyone who has the url and c) starting a new map is just one click with no registration and then the url can simply be copy/pasted and sent to others.
Example usage: I am regularly visiting a forum, I am curious where the other visitors are from, so I put the link in the message and watch the map in real time.
Example 2: I am chatting with a group of friends and I hear that a common friend of ours is ill. I create a new map, and send the link to everyone, so when they click it, they appear on the map. They can also watch as more and more people click the link. They can also leave one liner messages that will be displayed on the map next to their location. As our friend checks the link, he/she can see “get well soon” messages popping up from all over the world. This is all a bit similar to Wikipediavision, but more user-generated and with throw-away urls.
5. Centralized phpBB spam filter.
PhpBB is a robust, well-known and loved dicussion board (forum) software that has been around for a long time. The main aspect in which I find it inferior to centralized services like Disqus is spam. Spam filtering is something that is simply easier to do in a centralized way than for each individual board separately. This centralized filter would be a subscription-based API that I can call whenever I get a message on my board and it returns a spam/not spam flag. This can be integrated into my phpBB installation and the necessary action is taken automatically. This way, I wouldn’t have to bother users with captcha’s, registration, senseless restrictions, and I could still have them use the familiar interface of phpBB. If such a service works for WordPress comments and other blogging software, surely it can be retrofitted for phpBB (?).
6. Name face search.
When picking a baby name, many parents would like to find out as much as possible about it, including the history and etymology of the name, which historical persons have had that name, current popularity of the name, etc.
In this service you type in a first name and it gives you the photos of 100 random people having that name. Looking at the age of people on the photos, you can guess whether the name was more popular one or two generations ago than it is today. Also useful if you hear a name in a foreign language and you are not sure whether it is a male or female name. Images of faces can be found on Facebook or on Google Images, but there are still some technical difficulties: a) all 100 should be different persons b) the images should be filtered so that they only contain photos of people and not other random images.
July 2nd, 2011 — Math, Puzzle
Bongard problems are a type of puzzle invented by Russian computer scientist M. M. Bongard, intended as challenges for pattern recognition algorithms. Regardless of the possible relevance to computer science, they are much fun simply as puzzles created by people for other people to solve. They were popularized in the Gödel, Escher, Bach book and Hofstadter himself designed many Bongard problems. Harry Foundalis has several pages dedicated to these problems, with an extensive index of example Bongard problems.
The idea of a Bongard problem is the following: given a set A of six figures (examples) and another set B of six figures (counter-examples), discover what is the rule that the figures in A obey and figures in B violate.
Here are some very nice examples of varying difficulty and a much more detailed description:
http://www.foundalis.com/res/diss_research.html
Inspired by these examples I tried my hand at making some Bongard puzzles myself. The modest result is below. If you can solve them, leave the answer in the comments.
Puzzle 1.
Puzzle 2.
Puzzle 3.
Puzzle 4.
May 26th, 2011 — Math
Inequalities are the bread and butter of mathematical proofs, especially those with an “approximate” flavor. I found many useful sources that describe the most important inequalities, there exist even some books dedicated exclusively to inequalities. However, I couldn’t find a concise “cheat-sheet” style summary of the most important ones, so I wrote one myself, collecting information from the sources I found. Check out my useful inequalities cheat sheet.
May 8th, 2011 — Links, Reading
May 7th, 2011 — Links, Reading
May 5th, 2011 — Links, Reading
