Posts

Balancing Act Puzzle

Source: Australian Mathematical Society Gazette Puzzle Corner 35 Problem: There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total of W grams. Suppose W is less than the number of weights on the left multiplied by the number of weights on the right. Is it always true that we can remove some, but not all, of the weights from each side and still keep the two sides balanced?

"Flawless Harmony" Puzzle

Source: AUSTMS Puzzle Corner 35 Problem: Call a nine-digit number flawless if it has all the digits from 1 to 9 in some order. An unordered pair of flawless numbers is called harmonious if they sum to 987654321. Note that (a, b) and (b, a) are considered to be the same unordered pair. Without resorting to an exhaustive search, prove that the number of harmonious pairs is odd. Update (23 Oct 2014): Solution: Posted by me (Pratik Poddar) in comments!

Minimum sum of numbers in an array

Source:  Asked to me on quora (  cseblog.quora.com ) Problem: Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array? Example 1: 1 2 2 3 4 Answer : 0 (-1+2-2-3+4) Example 2: 2 3 4 7 13 Answer: 1 (+2-3-4-7+13)

Caterer's Problem

Source: Puzzle Toad CMU Problem: You are organizing a conference, with a festive dinner on the first day. The catering service has 1024 different dinner choices they know how to make, out of which you need to choose 10 to be in the dinner menu (each participant will choose one of these during the dinner). You send an email to the 6875 participants of the conference, with the list of all 1024 choices, asking them to rank the choices in linear order from their favorite to their unfavorite. You want to find a list L of 10 choices, such that for any dinner choice d not in the list L, if we run a vote of d against L, at least half of people will favor one of the choices in L over d (it may be different dish for different people). Is it always possible to produce such a list?

3D Tic Tac Toe Puzzle

Source:  Shared by Alok Mittal (Cannan Partners) Problem: A 3x3 tic tac toe has 8 "winning lines" (3 horizontal, 3 vertical and 2 diagonals). How many "winning lines" does the 3x3x3 3D tictactoe have? There is a brute force solution, and then there is the aha! solution. Update (23 Oct 2014) Solution:  Posted in comments by Anti, Taz, Javier, Shubham Gupta, Leela. Detailed solution and much more advanced problems in the document  http://library.msri.org/books/Book42/files/golomb.pdf

Mad Robot Puzzle

Source: http://nrich.maths.org/ Problem: A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions: SUB JOURNEY     DISTANCE = 1000     WHILE (DISTANCE > 0.001)         MOVE DISTANCE         STOP         ROTATE(90, DEGREES, CLOCKWISE)         DISTANCE = DISTANCE / 2     END WHILE     EXPLODE END SUB Where does the robot explode? Update (23 Oct 2014): Solution:  Posted by me (Pratik Poddar) in comments!

Social Network Friendship Paradox

Problem / Observation: The friendship paradox is the phenomenon first observed by the sociologist Scott L. Feld in 1991 that most people have fewer friends than their friends have, on average. Prove it mathematically. Update (23 Oct 2014): Solution:  Posted by Mike Earnest and Taz in comments!