Puzzle
8 minute read

Ponder This Challenge - November 2013 - K-dim faces of d-dim hypercube

Ponder This Challenge:

A three-dimensional cube has eight vertices, twelve edges, and six faces. Let's call them 0-D, 1-D, and 2-D faces, respectively.
Denote f(d,k) as the number of k-dimensional faces of an d-dimensional hyper cube, so f(3,1)=12.
Find three cubes (with different dimensions d1, d2, and d3) such that the number of k1, k2, and k3 dimension faces are the same, i.e. f(d1,k1) = f(d2,k2) = f(d3,k3).
We are looking for nontrivial solutions, so k1 should be less then d1.
Bonus: Find more than three.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

  • This month's challenge was both too easy and too hard:

    It was too easy, since Wikipedia has the formula (http://en.wikipedia.org/wiki/Hypercube) and one solution is very simple: f(5,0)=f(4,1)=f(16,15)=32

    There are several families of solutions:

    F(x,x-1) = 2x, so we can complete every non-trivial pair into a triplet. One that many of you discovered is f(m+2^m-1,0) = f(2^m,1)

    Yevgeny Pyasetskiy sent us another sequence: f(3*k+2,k) = f(3*k+2,k+1)

    Oleg Vlasii gave us a more complicated sequence:

    f(p_n - 1; q_n) = f(p_n; q_n - 1)

    where p_1=5, q_1=1

    p_2 = 174, q_2 = 30

    p_{n+1} = 34p_n - p_{n-1} + 4

    q_{n+1} = 34q_n - q_{n-1} - 4

    And there are also more sporadic solutions, such as:

    f(7, 2) = f(9, 6) = f(336, 335)

    f(10, 5)= f(64, 62)= f(4032, 4031)

    f(8, 1)= f(10, 0)= f(512, 511)

    f(13, 8)= f(144, 142)= f(20592, 20591)

    f(7, 1)= f(8, 5)= f(224, 223)

    f(15, 11)= f(105, 103) =f(10920, 10919)

    f(13, 4) = f(66, 63) = f(183040, 183039)�

    f(22, 16) = f(154, 151) = f(2387616, 2387615)

    f(83, 48) = f(85, 51) = f(5284246911660441908808151266754560, 5284246911660441908808151266754559)

    But the challenge was also too difficult, since the bonus question was an open one, See Singmaster's conjecture (http://en.wikipedia.org/wiki/Singmaster%27s_conjecture) as a reference to a similar problem.

Solvers

  • Reiner Martin (11/01/2013 04:59 PM EDT)
  • Philipp Seemann (11/01/2013 05:04 PM EDT)
  • Antoine Comeau (11/01/2013 05:29 PM EDT)
  • Gilad Weiss (11/01/2013 05:31 PM EDT)
  • Andrew Gacek (11/01/2013 05:35 PM EDT)
  • Vladimir Sedach (11/01/2013 05:39 PM EDT)
  • Radu-Alexandru Todor (11/01/2013 06:17 PM EDT)
  • Lorenz Reichel (11/01/2013 06:28 PM EDT)
  • William Heller (11/01/2013 07:03 PM EDT)
  • Rick Kaye (11/01/2013 07:46 PM EDT)
  • Kan Shen (11/01/2013 08:30 PM EDT)
  • Don Dodson (11/01/2013 08:55 PM EDT)
  • Antonio García Astudillo (11/01/2013 09:28 PM EDT)
  • Archer (11/01/2013 09:40 PM EDT)
  • Cynthia Beauchemin (11/01/2013 10:01 PM EDT)
  • Seth Cohen (11/01/2013 10:54 PM EDT)
  • Dan Dima (11/01/2013 11:06 PM EDT)
  • Dheeraj Reddy (11/01/2013 11:23 PM EDT)
  • Nicholas Ngiam & Liu Ren Wei (11/01/2013 11:30 PM EDT)
  • Minxi Jiang (11/02/2013 12:52 AM EDT)
  • Manoj vedvistara (11/02/2013 01:08 AM EDT)
  • Sameer Mehta (11/02/2013 01:42 AM EDT)
  • Adam Kozdron (11/02/2013 01:53 AM EDT)
  • Robin Ryder (11/02/2013 01:57 AM EDT)
  • Michael Wilms (11/02/2013 02:08 AM EDT)
  • Stéphane Higueret (11/02/2013 03:00 AM EDT)
  • Michael Liepelt (11/02/2013 03:39 AM EDT)
  • Dezhi Zhao (11/02/2013 04:27 AM EDT)
  • Pawel Milewski (11/02/2013 04:38 AM EDT)
  • Adrian Orzepowski (11/02/2013 05:38 AM EDT)
  • Yevgeny Pyasetskiy (11/02/2013 06:12 AM EDT)
  • Anatoli Plotnikov (11/02/2013 06:56 AM EDT)
  • David Greer (11/02/2013 07:06 AM EDT)
  • Miloš Cubrilo (11/02/2013 08:11 AM EDT)
  • Tim Cieplowski (11/02/2013 08:37 AM EDT)
  • Alex Fleischer (11/02/2013 10:57 AM EDT)
  • Aharon Malachi (11/02/2013 08:04 AM EDT)
  • Chuck Carroll (11/02/2013 11:23 AM EDT)
  • Benjamin Phillabaum (11/02/2013 12:15 PM EDT)
  • Oleg Vlasii (11/02/2013 12:59 PM EDT)
  • Seth Rylan Gainey (11/02/2013 01:04 PM EDT)
  • Henry Liu (11/02/2013 01:52 PM EDT)
  • Shirish Chinchalkar (11/02/2013 02:22 PM EDT)
  • Clive Tong (11/02/2013 02:49 PM EDT)
  • Tatiana Stepanova (11/02/2013 03:05 PM EDT)
  • Rob Sessions (11/02/2013 05:26 PM EDT)
  • Dieter Beckerle (11/02/2013 05:32 PM EDT)
  • José Eduardo Gaboardi de Carvalho (11/02/2013 05:53 PM EDT)
  • Eric Harley (11/02/2013 06:44 PM EDT)
  • Florian Fischer (11/02/2013 06:53 PM EDT)
  • Eugene Lee (11/02/2013 09:05 PM EDT)
  • David Chang (11/02/2013 11:56 PM EDT)
  • Victor Chang (11/03/2013 01:39 AM EDT)
  • Hugo Pfoertner (11/03/2013 07:32 AM EDT)
  • Tofig Kareemov (11/03/2013 08:20 AM EDT)
  • Tao Liu (11/03/2013 08:21 AM EDT)
  • Patrick Keuntje (11/03/2013 08:25 AM EDT)
  • James Dow Allen (11/03/2013 10:59 AM EDT)
  • Hyung Sik Hwang (11/03/2013 12:49 PM EDT)
  • John Tromp (11/03/2013 10:52 AM EDT)
  • Emre Alkan (11/03/2013 02:03 PM EDT)
  • Armin Krauss (11/03/2013 02:42 PM EDT)
  • Maris Van Sprang (11/03/2013 02:50 PM EDT)
  • Alexey Kornilov (11/03/2013 03:07 PM EDT)
  • Aaron Matthews (11/03/2013 05:45 PM EDT)
  • Yiqian Lu (11/03/2013 07:10 PM EDT)
  • Frederick Liu (11/03/2013 08:07 PM EDT)
  • Leandro Araújo (11/03/2013 09:46 PM EDT)
  • Lawrence Hon (11/03/2013 09:48 PM EDT)
  • Guangda Huzhang (11/03/2013 11:44 PM EDT)
  • Guangda (11/04/2013 12:05 AM EDT)
  • Nivrutti Tambe (11/04/2013 02:54 AM EDT)
  • Vukasin Vucevic (11/04/2013 05:53 AM EDT)
  • Hugues Juille (11/04/2013 06:27 AM EDT)
  • Sevag Papazian (11/04/2013 06:58 AM EDT)
  • Kurt Hectic (11/04/2013 07:33 AM EDT)
  • Vivek Viswanathan (11/04/2013 07:28 AM EDT)
  • Kipp Johnson (11/04/2013 09:16 AM EDT)
  • Simon Xu (11/04/2013 09:39 AM EDT)
  • Peter Gerritson (11/04/2013 09:49 AM EDT)
  • Joseph DeVincentis (11/04/2013 10:05 AM EDT)
  • Steve Stuve (11/04/2013 11:51 AM EDT)
  • Michael Gurvich & Chintan Maggu (11/04/2013 12:06 PM EDT)
  • Adrian Liebtrau (11/04/2013 12:22 PM EDT)
  • Shouky Dan & Tamir Ganor (11/04/2013 12:51 PM EDT)
  • Jan Fricke (11/04/2013 01:13 PM EDT)
  • Yasodhar Patnaik (11/04/2013 01:32 PM EDT)
  • Krunoslav Kovac (11/04/2013 02:36 PM EDT)
  • Robert Gauss (11/04/2013 03:48 PM EDT)
  • Daniel Bitin (11/04/2013 04:10 PM EDT)
  • Liubing Yu (11/04/2013 05:59 PM EDT)
  • Benjamin Bogardus (11/04/2013 06:26 PM EDT)
  • Bastiaan Uytterhoeven-Spark (11/04/2013 07:06 PM EDT)
  • Joseph Berman (11/04/2013 08:39 PM EDT)
  • Patrick Conroy (11/04/2013 09:38 PM EDT)
  • Mathias Schenker (11/05/2013 03:05 AM EDT)
  • Harald Bögeholz (11/05/2013 03:07 AM EDT)
  • Christian Blatter (11/05/2013 04:56 AM EDT)
  • Chandrashekar Shankar (11/05/2013 07:39 AM EDT)
  • Guler Amos (11/05/2013 08:54 AM EDT)
  • Andreas Allemann (11/05/2013 09:57 AM EDT)
  • Jacques Guzy (11/05/2013 10:09 AM EDT)
  • Vladimir Kochanov (11/05/2013 10:32 AM EDT)
  • Chris Lewis (11/05/2013 11:56 AM EDT)
  • Mohammad Javaheri (11/05/2013 01:21 PM EDT)
  • Fletcher Dostie (11/05/2013 03:16 PM EDT)
  • Joe Clark (11/05/2013 05:21 PM EDT)
  • Michael Rosola (11/05/2013 05:32 PM EDT)
  • Mark Stuckel (11/05/2013 08:08 PM EDT)
  • Aviv Nisgav (11/06/2013 12:59 AM EDT)
  • Sri Harsha Wdaru (11/06/2013 04:42 AM EDT)
  • Marcel Caria (11/06/2013 04:51 AM EDT)
  • Arthur Breitman (11/06/2013 07:40 AM EDT)
  • Tom Harley (11/06/2013 10:45 AM EDT)
  • Bryan Jacobs (11/06/2013 12:40 PM EDT)
  • Samantha Casanova (11/06/2013 02:21 PM EDT)
  • Max Woghiren (11/06/2013 02:51 PM EDT)
  • Richard Morris (11/06/2013 11:31 PM EDT)
  • David Gower (11/07/2013 04:22 AM EDT)
  • Igor Novak (11/07/2013 09:48 AM EDT)
  • Maciej Snopczynski (11/07/2013 09:59 AM EDT)
  • Gadi Aleksandrowicz (11/07/2013 10:00 AM EDT)
  • David Dodson (11/07/2013 10:35 AM EDT)
  • Sergey Subbotin (11/07/2013 12:48 PM EDT)
  • Will O'Leary (11/07/2013 06:52 PM EDT)
  • Olivier Mercier (11/07/2013 08:47 PM EDT)
  • Børge Nordli (11/08/2013 04:41 AM EDT)
  • Jeffrey Nash (11/08/2013 04:55 AM EDT)
  • Annalisa Bravi (11/08/2013 04:56 AM EDT)
  • Stefano Soccio (11/08/2013 06:27 AM EDT)
  • Ian Barnard (11/08/2013 07:37 AM EDT)
  • Chris Becker (11/08/2013 11:29 AM EDT)
  • Karthik Adimurthi (11/08/2013 04:03 PM EDT)
  • Jonas Lindstrøm Jensen (11/09/2013 03:44 AM EDT)
  • Austin Routt (11/09/2013 11:10 AM EDT)
  • Katherine Oh (11/09/2013 01:02 PM EDT)
  • Hakan Summakoglu (11/09/2013 02:09 PM EDT)
  • Gil Citro (11/09/2013 04:22 PM EDT)
  • Andrea Andenna (11/09/2013 06:43 PM EDT)
  • Jesus Sanz (11/10/2013 04:48 AM EDT)
  • Andreas Stiller (11/10/2013 01:19 PM EDT)
  • Walter Schmidt (11/10/2013 01:57 PM EDT)
  • András Lázár (11/10/2013 05:04 PM EDT)
  • Ramezan Paravi Torghabeh (11/10/2013 10:24 PM EDT)
  • Ratul Das (11/11/2013 04:22 AM EDT)
  • Adi Barshay (11/11/2013 08:08 AM EDT)
  • Payman Karvani (11/11/2013 01:55 PM EDT)
  • Seung Min "Brian" Park (11/11/2013 02:20 PM EDT)
  • Lorenzo Gianferrari Pini (11/11/2013 02:28 PM EDT)
  • Mirzaei Kaveh (11/11/201just o3 05:18 PM EDT)
  • Michael D. Schuresko (11/12/2013 03:35 AM EDT)
  • Kaloyan Todorov (11/12/2013 03:40 AM EDT)
  • Lilesh Ghadi (11/12/2013 06:47 AM EDT)
  • Benjamin Brumfield (11/12/2013 07:07 AM EDT)
  • Fabio Filatrella (11/12/2013 08:18 AM EDT)
  • Rohan Kekatpure (11/12/2013 01:09 PM EDT)
  • David Maze (11/12/2013 02:20 PM EDT)
  • Noble Pendergrass (11/12/2013 04:45 PM EDT)
  • Naftali Peles (11/12/2013 05:11 PM EDT)
  • Stephen Morris (11/12/2013 07:33 PM EDT)
  • Chang Lan (11/12/2013 10:35 PM EDT)
  • François Comeau (11/13/2013 11:16 AM EDT)
  • Christian Pape (11/14/2013 09:37 AM EDT)
  • Michael Chirozzi (11/14/2013 03:44 PM EDT)
  • Boris Rakus (11/15/2013 02:20 AM EDT)
  • Miklós Arthur (11/15/2013 08:42 AM EDT)
  • Álvaro Begué (11/15/2013 12:06 PM EDT)
  • Lee Burnette (11/15/2013 02:00 PM EDT)
  • Jeremy Kerfs (11/15/2013 03:22 PM EDT)
  • William Kang (11/16/2013 08:08 AM EDT)
  • Knop Konstantin (11/17/2013 06:37 AM EDT)
  • Nell Kopel (11/17/2013 03:11 PM EDT)
  • Mahmoud Naser (11/17/2013 08:08 PM EDT)
  • Monakov Gregogy (11/18/2013 06:06 AM EDT)
  • Christopher E. Marks (11/18/2013 12:07 PM EDT)
  • Rodrigo Exterckötter Tjäder (11/18/2013 01:46 PM EDT)
  • Andreas Razen (11/18/2013 03:42 PM EDT)
  • Anoop Ghanwani (11/18/2013 11:12 PM EDT)
  • Edward Sullivan (11/19/2013 08:00 AM EDT)
  • Marco Tulio Reis Rodrigues (11/20/2013 09:10 AM EDT)
  • Alex Zdanowicz (11/20/2013 09:51 AM EDT)
  • Jerry Kearns (11/20/2013 02:22 PM EDT)
  • Brian Mathason (11/20/2013 02:26 PM EDT)
  • Ilya Libis (11/20/2013 03:51 PM EDT)
  • Movin Jain (11/20/2013 04:56 AM EDT)
  • David Friedman (11/20/2013 05:12 PM EDT)
  • Mauro Bampo (11/20/2013 05:13 PM EDT)
  • Sebastian Will (11/21/2013 02:39 PM EDT)
  • Kevin Roche (11/21/2013 07:16 PM EDT)
  • Richard Palfini (11/21/2013 08:10 PM EDT)
  • Satendra Tiwari (11/21/2013 09:26 PM EDT)
  • Alex Wagne (11/22/2013 03:58 PM EDT)
  • Yueru Sun (11/22/2013 05:25 PM EDT)
  • Amit Sinha (11/22/2013 06:19 PM EDT)
  • Om Prakash Pal (11/23/2013 07:55 AM EDT)
  • Miha Muškinja & Matic Lubej (11/23/2013 08:08 AM EDT)
  • Gyozo Nagy (11/23/2013 10:27 AM EDT)
  • SeongWoo Hong (11/23/2013 12:08 PM EDT)
  • Jaesung Son (11/23/2013 03:06 PM EDT)
  • Shmuel Menachem Spiegel (11/23/2013 11:21 PM EDT)
  • Isaac Drachman (11/24/2013 01:27 AM EDT)
  • Rajesh Sathiyanarayanan (11/24/2013 01:27 AM EDT)
  • Kim San (11/24/2013 07:30 AM EDT)
  • Mintao YE (11/24/2013 10:54 AM EDT)
  • Todd Will (11/24/2013 11:24 AM EDT)
  • Vivek Ranjan Nema (11/24/2013 03:22 PM EDT)
  • Moon (Hwan) Lee (11/24/2013 10:16 PM EDT)
  • Xia Dayu (11/25/2013 12:09 AM EDT)
  • Alok Menghrajani (11/25/2013 11:48 PM EDT)
  • Mark Pervovskiy (11/26/2013 10:07 AM EDT)
  • Sakin H.R. Ranke (11/26/2013 09:30 PM EDT)
  • Zhenfei Liu (11/26/2013 03:39 PM EDT)
  • Peter Shim (11/27/2013 11:50 AM EDT)
  • Paul Mandell (11/27/2013 09:07 AM EDT)
  • Motty Porat (11/27/2013 03:31 PM EDT)
  • Andrew Buchanan (11/28/2013 01:20 AM EDT)
  • Surya Kareenahalli (11/29/2013 06:08 AM EDT)
  • Gyorgy Gyomai (11/29/2013 06:56 AM EDT)
  • Marco Quargentan (11/29/2013 09:03 AM EDT)
  • Rajendran Thirupugalsamy (11/29/2013 06:33 PM EDT)
  • Arunkumar R (11/30/2013 07:28 AM EDT)
  • Thomas Glinski (11/30/2013 08:47 AM EDT)
  • Daniel Lincke (11/30/2013 09:17 AM EDT)
  • Michael Lim (11/30/2013 10:19 AM EDT)
  • Sinan Egilmez (11/30/2013 09:01 PM EDT)

Related posts