Trickier Roots of Unity Filter

by pinetree1, Aug 13, 2017, 11:03 PM

Problem: Let $p$ be a prime and let $n\ge p$ be a positive integer. In addition, let $a_1$, $a_2$, $\dots$, $a_n$ be arbitrary integers. Define $f_0=1$, and for $k\ge 1$ let $f_k$ be the number of subsets $I\subset \{1, 2, \dots, n\}$ such that $|I|=k$ and $p\mid \sum_{i\in I} a_i$. Prove that $p\mid f_0-f_1+\dots+(-1)^nf_n$.

Source: AMSP NT3, St. Petersburg

Solution
Comments
This post has been edited 2 times. Last edited by pinetree1, Aug 20, 2017, 10:44 PM

Comment

3 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Gabriel is pro

I agree
This post has been edited 1 time. Last edited by pinetree1, Aug 15, 2017, 3:08 AM

by bluephoenix, Aug 14, 2017, 10:46 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
This is originally from St. Petersburg.

How did you find that?
This post has been edited 1 time. Last edited by pinetree1, Aug 20, 2017, 10:44 PM

by HKIS200543, Aug 20, 2017, 1:31 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
It's in Straight From the Book.

by HKIS200543, Aug 24, 2017, 9:32 AM

Shout for contrib!

avatar

pinetree1
Archives
+ March 2018
+ February 2018
+ April 2016
+ November 2015
Shouts
Submit
  • orz blog

    by Yiyj1, Nov 2, 2024, 3:45 AM

  • @below orz

    by resources, Jul 23, 2024, 10:24 AM

  • 2 year bump ig...

    by impromptuA, Dec 30, 2023, 9:48 PM

  • Wow! great solution!

    by PickleSauce, Jul 29, 2021, 4:16 AM

  • Hello! $           $

    by HamstPan38825, Jun 26, 2021, 6:08 PM

  • awesome blog !!! :clap: :coolspeak: :omighty:

    by lneis1, Apr 21, 2021, 1:28 PM

  • Really Good!

    by L567, Dec 29, 2020, 6:29 AM

  • hello pinetree

    by fukano_2, Oct 31, 2020, 10:35 AM

  • how is pinetree1 so pro?

    by aops5234, Jul 30, 2020, 1:00 AM

  • $\text {Bring Gold at IMO 2020} $

    by Physicsknight, Jul 12, 2020, 12:35 PM

  • thx! $\phantom{}$

    by GeronimoStilton, Jul 4, 2020, 8:20 PM

  • yep $ $ $ $

    by pinetree1, Jul 4, 2020, 4:21 PM

  • does shouting for contrib work?

    by GeronimoStilton, Jul 4, 2020, 1:00 AM

  • omg HI A02
    and hi pinetree

    by anyone__42, Jul 2, 2020, 12:13 PM

  • HI PINETREE!!!

    by A02, Jul 1, 2020, 6:55 PM

141 shouts
Tags
About Owner
  • Posts: 1205
  • Joined: May 9, 2012
Blog Stats
  • Blog created: May 13, 2014
  • Total entries: 188
  • Total visits: 34750
  • Total comments: 282
Search Blog