Peons
November 5th, 2007
This is a cute puzzle. Consider an infinite checkerboard divided in two with an infinite line lying along the x-axis, as depicted below:
Set it Straight!
October 31st, 2007
In this post I will give a basic example of the necessity (or uselessness - its up to you to choose - pun intended) of the axiom of choice. I will also present a less known proof of the Cantor–Bernstein–Schroeder theorem.
The Cantor–Bernstein–Schroeder Theorem
Let A and B be sets. Let f:A->B and g:B->A be injective functions. Then there exists a bijection h:A->B.
Find the Duplicate
October 13th, 2007Dany Valevsky gave me this very cool riddle.
You are given a vector of size N, the elements of which are numbers in the range 1,…,N-1. I.e. there is at least one repeating element. Give an algorithm that finds a repeating element (it does not matter which one, in case there are several) with O(N) time complexity and O(log(N)) memory complexity.
Pirates!
October 13th, 2007
A ship in the plane has integer coordinates. It also has integer velocity (again in ZxZ). Each turn the ship advances according to its velocity. Here is an example of a ship with velocity (3, 1).
Turing Machines in Action
October 7th, 2007
In this post I will define turing machines and demonstrate a simple one in action.
Galois Theory for Dummies - Part I
September 27th, 2007
Galois Theory is an algebraic theory providing a powerful connection between fields and groups. Many complicated problems involving fields can be converted to (possibly) simpler problems involving groups.
Galois Theory, albeit being extremely beautiful (it answers some very elementary questions, which were all open problems until its arrival), is far from being wildly known (i.e. by non-mathematicians). One of the reasons for this, in my opinion, is that is it a vast subject and most books on the topic are filled with too many details and so are inadequate for a quick read.
Seam Carving
August 27th, 2007
I recently watched this interesting video by Shai Avidan and Ariel Shamir from MERL. They developed an extremely cool image resizing technique called seam carving. They explain all about it in this article.
One of the coolest things about their idea is that is it easy to implement. I implemented a semi-optimized version of their algorithm in a couple of hours of coding. All the images in this post were generated by my code.
Piece of Cake
August 23rd, 2007In this article you will find a collection of riddles. They are all either very well known or extremely easy. Enjoy!
Cutting the Cake
How can you cut a circular cake to eight even pieces with 3 cuts? What is the maximum number of pieces possible with 4 cuts?
Maximal Partitions
August 17th, 2007When considering the extra-credit of the 23 and 2000 riddle, I thought of an additional interesting problem.
Let N be a positive integer. A partition of N into m parts (an m-partition of N) is a multiset of m positive integers, such that their sum equals N. A multiset is a set which may contain repeated elements.
23 and 2000
August 13th, 2007You are given 23 whole numbers, not necessarily distinct, in a row.
You cannot change the order of the numbers.
Prove that there exists an arrangement of the symbols ’+’, ‘×’, ‘(’ and ‘)’ in-between the 23 numbers, such that the final result is a valid formula, whose evaluated value equals 0 mod 2000.