CSE Blog - quant, math, computer science puzzles

Source: Sent to me by Vinayak Gagrani (CSE IITB Alumnus 2013) Problem: There are 289 students. We have to divide them into 17 groups of 17 each every day. The groups have to be such that no two students who have been previously on some group together can be formed a group again. How many days can we do this ? Extension: Can this be generalized for any N^2 students? Solution: Highlight the part between the * symbols for the answer. * Answer for 289 = 17^2 students: 18 days. Upper bound: each day, a student shares a group with N - 1 = 16 others, and over d days must meet only distinct people, so d(N-1) <= N^2 - 1, i.e. d <= N+1 = 18. Construction achieving 18 (works for any prime or prime power N, via the affine plane / finite field of order N): label students by pairs (m, k) with m, k in Z_17. Day 0: group g = {(g, k) : all k}... more precisely, on day 0 group by the first coordinate; on day j = 1..17, put students (m, k) and (m', k') in the same group iff k + m*(j-1) ma...

Source: IBM Ponder This - June 2012 - Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m > 1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins. What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ? We are looking for all the moves the first player can make which, assuming he plays correctly, can guarantee him winning the game. Update (24 June 2014): Solution:  Posted by Gowtham Kumar (PhD Student, Stanford, IITM Alumnus) and me in comments!