Deepak Surti
  • Blog
  • Mobile Apps
  • Projects
  • Graphics Demo
  • Me

The digital diary of a
​programmable programmer!!!

Setless Set (ITA Archived Puzzle, Analyzed)

7/3/2011

0 Comments

 
Please refer to the setless set problem on this page.

Analysis

It can be easily deduced that the collection of 81 cards, contiains 27 SETs where each set contains the same cards.

Now in order to find the number of ways in which we can collect 20 cars such that it contains no set, we can use the following formula:
$$ N_{20\,cards\,without\,set} = N_{all\,possible\,collections\,of\,20\,cards} - N_{collection\,of\,20\,cards\,with\,atleast\,1\,set}$$


Find out set with different cards

Now if \(n_{same}\) is the number of sets with same cards, we already know that
$$n_{same} = 27$$

If we want to form a set that contains different cards, we can first pick an equal set and then pick a card from that set. Repeating this thrice will give us a set that contains different cards.

Thus total number of sets with different cards  \(n_{different}\) can be defined as 
$$n_{different} = (27 * 3) * (26 * 3) * (25 * 3) $$

Thus total number of possible sets \(n_{sets}\) can be defined as:
$$n_{sets} = n_{same} + n_{different}$$

Now we can easily find out the number of ways to pick k sets from \(n_{sets}\). A collection of 20 cards will contain a minimum of 1 set and a maximum of 6 sets. Thus number of ways to collect 'at the most' 6
sets can be defined as
$$n_{6\,sets} = \sum_{k = 1}^{k = 6} \binom {n_{sets}} {k}$$

Thus to find out N ways in which we can collect 20 cards that does not contain a set is
$$ N = \binom {81} {20} - n_{6\,sets}$$

Implementation

We can now write code that
  • Computes \(n_{6\,sets}\)
  • For a given j (j = 20 in the example), finds out the maximum number of ’k’ sets possible
  • Computes the number of ways in which you can pick k sets that is \(n_{k\,sets}\)
  • Computers the number of ways in which you can pick j cards from 81 cards
  • Finally computes the number of ways in which you can pick j cards such that it contains no set.
0 Comments

Your comment will be posted after it is approved.


Leave a Reply.

    Picture

    Me

    I am a 3D graphics software engineer.

    profile for dmsurti at Stack Overflow, Q&A for professional and enthusiast programmers

    Archives

    December 2011
    November 2011
    October 2011
    September 2011
    August 2011
    July 2011
    June 2011
    May 2011
    April 2011
    August 2010
    January 2010
    December 2009
    September 2009
    August 2009

    Categories

    All
    Books
    Code
    Continuations
    Css
    Drakma
    Education
    Express Card
    External Drive
    Html
    Ita
    Learning
    Life
    Lisp
    Mac
    Macros
    Mercurial
    Puzzle
    Reading
    Rss
    Simplicity
    Sudoku
    Work

    RSS Feed

    Picture
    me @ delicious
To see a miracle, be the miracle
  • Blog
  • Mobile Apps
  • Projects
  • Graphics Demo
  • Me
✕